Michael Collins NLP Lecture 2

课程主页：http://www.cs.columbia.edu/~cs4705/

课程网盘地址：

链接：https://pan.baidu.com/s/1KijgO7yjL_MVCC9zKZ7Jdg
提取码：t1i3

这一讲主要介绍了三元语言模型以及参数估计的问题。

1.3 三元语言模型

有多种方法可以定义语言模型，本章将介绍一个特别重要的例子，即三元语言模型（trigram language model）。这将是如上一节所述的马尔可夫模型对语言建模问题的直接应用。在本节中，我们将给出三元模型的基本定义，讨论了三元模型的最大似然参数估计，最后讨论了三元模型的优点和缺点。

1.3.1 基本定义

与马尔可夫模型一样，我们将每个句子建模为$n$个随机变量的序列，$X_1,X_2,…,X_n$。长度$n$本身是一个随机变量（它可以在不同的句子中变化）。我们总是有$X_n =\text{STOP}$。在二阶马尔可夫模型下，任何句子$x_1…x_n$的概率是

$P(X_1=x_1,X_2= x_2,...,X_n=x_n)= \prod_{i=1}^n P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1})$

这里我们和之前一样假设

$x_0=x_{-1}= *$

我们假设对于任意$i$和任意$x_{i-2},x_{i-1},x_i$，

$P(X_i=x_i|X_{i-2}=x_{i-2},X_{i-1}=x_{i-1}) =q(x_i| x_{i-2},x_{i-1})$

其中$q(w|u,v)$是模型的参数（对于任意$(u,v,w)$）。我们很快就会看到如何从我们的训练语料库中推导出参数$q(w|u,v)$的估计值。对于任意$x_1…x_n$，我们的模型采用如下形式

$p(x_1...x_n) =\prod_{i=1}^n q(x_i|x_{i-2},x_{i-1})$

这引出了如下定义：

定义 2 （三元语言模型）

一个三元语言模型由有限集$\mathcal V$，以及如下参数构成

$q(w|u,v)$

每个三元组$(u,v,w)$满足

$\begin{aligned} w&\in \mathcal V\cup \{\text{STOP}\}\\ u,v&\in \mathcal V \cup \{*\} \end{aligned}$

$q(w|u,v)$的值可以解释为在二元组$(u,v)$之后看到单词$w$的概率。对于任何满足$x_i\in\mathcal V,i=1…(n-1)$以及$x_n = \text{STOP}$的句子$x_1…x_n$，在三元语言模型下句子对应的概率为

$p(x_1...x_n) =\prod_{i=1}^n q(x_i|x_{i-2},x_{i-1})$

这里我们定义

$x_0=x_{-1}= *$

例如，对于句子

$\text{the dog barks STOP}$

我们有

$p(\text{the dog barks STOP})= q(\text{the}|\text{*, *})\times q(\text{dog}|\text{*, the})\times q(\text{barks}|\text{the, dog})\times q(\text{STOP}|\text{dog, barks})$

请注意，在此表达式中，每个单词仅取决于前两个单词：这是三元组假设。

对于任意三元组$u,v,w$，参数满足如下限制

$q(w|u,v)\ge 0$

对于任意二元组$u,v$

$\sum_{w\in \mathcal V\cup \{\text{STOP}\}}q(w|u,v) =1$

因此$q(w|u,v)$定义了给定二元组$(u,v)$，$w$的条件分布。

现在关键问题是估计模型的参数，即

$q(w|u,v)$

其中

$\begin{aligned} w&\in \mathcal V\cup \{\text{STOP}\}\\ u,v&\in \mathcal V \cup \{*\} \end{aligned}$

模型中有大约有$|\mathcal V|^3$个参数。这可能是一个非常大的数字。例如，$|\mathcal V|=10000$（这是一个现实中的数字，按照现代标准还很可能很小），我们有$|\mathcal V|\approx 10^{12}$。

1.3.2 最大似然估计

我们首先从估计问题的最通用解决方案开始，即最大似然估计。我们将看到这些估计值有致命的缺陷，但我们将展示如何推导出在实际中非常有效的相关估计值。

首先，定义一些符号。将$c(u,v,w)$定义为在训练语料库中三元组$(u,v,w)$出现的次数：例如，$c(\text{the},\text{dog},\text{barks})$是在训练语料库中序列the dog barks出现的次数。类似的，将$c(u,v)$定义为在语料库中二元组$(u,v)$出现的次数。对于任何$w,u,v$，我们定义

$q(w|u,v) = \frac{c(u,v,w)}{c(u,v)}$

举个例子，我们对$q(\text{barks}|\text{the},\text{dog})$的估计是

$q(\text{barks}|\text{the},\text{dog}) = \frac{c(\text{the},\text{dog},\text{barks})}{c(\text{the},\text{dog})}$

这个估计是非常自然的：分子是三元组the dog barks的出现次数，而分母是二元组the dog出现的次数。我们简单地考虑这两项的比值。

不幸的是，这种估计参数的方法遇到了一个非常严重的问题。回想一下，我们的模型中有很多参数（例如，词汇量大小为$10000$，我们有大约$10^{12}$个参数）。因此，我们的许多计数将为零。这导致两个问题：

由于分子中的计数为$0$，上述很多估计将为$0$，即$q(w|u,v)=0$。这将导致许多三元组概率被低估：将概率$0$分配给任何未见的三元组似乎是不合理的。注意到与训练语料库中的单词数量相比，模型的参数数量通常非常大，所以上述低估现象将经常会发生。
在分母$c(u,v)$等于零的情况下，估计不是定义良好的。

我们将很快看到如何得到解决这些问题的修改后的估计。首先，我们讨论如何评估语言模型，然后讨论三元语言模型的优缺点。

1.3.3 评估语言模型：困惑度（Perplexity）

那么我们如何衡量语言模型的质量呢？一种非常常见的方法是评估模型对held-out数据的困惑度（Perplexity）。

方法如下。假设我们有一些测试句子$x^{(1)},x^{(2)},…,x^{(m)}$。对于$i\in \{1…m\}$的每个测试句子$x^{(i)}$，它是单词序列$x_1^{(i)},…,x_{n_i}^{(i)}$，其中$n_i$是第$i$个句子的长度。和以前一样，我们假设每个句子都以STOP符号结束。

至关重要的是，测试句子是”held out”，因为它们不是用于估计语言模型的语料库的一部分。从这个意义上说，它们是新的，没见过的句子。

对于任何测试句子$x^{(i)}$，我们可以在语言模型下计算其概率$p(x^{(i)})$。衡量语言模型质量的一个自然衡量标准是它分配给整套测试句子的概率，即

$\prod_{i=1}^m p(x^{(i)})$

直觉如下：这个数量越大，语言模型在建模看不见的句子时就越好。

测试语料库中的困惑度是作为该数量的直接变换而导出的。将$M$定义为测试语料库中的单词总数。更确切地说，根据定义，$n_i$是第$i$个测试句子的长度，那么

$M = \sum_{i=1}^m n_i$

然后将模型下的平均对数概率定义为

$\frac 1 M \log_2 \prod_{i=1}^m p(x^{(i)})=\frac 1 M \sum_{i=1}^m\log_2 p(x^{(i)})$

这只是整个测试语料库的对数概率除以测试语料库中的单词总数。同样，这个数量越高，语言模型越好。

然后将困惑度定义为

$2^{-l}$

其中

$l =\frac 1 M \sum_{i=1}^m\log_2 p(x^{(i)})$

我们取平均对数概率的相反数，然后取$2$次幂。困惑度是一个正数。困惑度的值越小，语言模型在未见过的数据上表现就越好。

困惑背后的一些直觉如下。假设我们有一个词汇表$|\mathcal V|$，其中$|\mathcal V\cup \text{ STOP}|=N$，然后对所有$u,v,w$，模型预测

$q(w|u,v) =\frac1 N$

因此，这是一个简单的模型，它简单地预测为条件概率为词汇表以及STOP符号上的均匀分布。在这种情况下，可以表明困惑等于$N$。

事实上，此时

$p(x^{(i)}) = \frac 1 {N^{n_i}}$

所以

$\begin{aligned} l &= \frac 1 M \sum_{i=1}^m\log_2 p(x^{(i)}) \\ &= -\frac 1 M \sum_{i=1}^m n_i \log_2 N \\ &=-\log_2 N \\ 2^{-l}&=N \end{aligned}\\$

因此在均匀分布概率模型下，困惑度等于词汇量大小。困惑度可以被认为是模型下的有效词汇量：例如，如果模型的困惑度为$120$（即使词汇量大小为$10000$），那么这大致相当于具有有效的词汇量大小为$120$。

为了给出更多困惑度产生的动机，很容易发现困惑度等于

$\frac 1 t$

其中

$t = \sqrt[M]{\prod_{i=1}^m p(x^{(i)})}$

这里我们用$\sqrt[M] z$表示$z$的$M$次根：所以$t$是满足$t^M=\prod_{i=1}^m p(x^{(i)})$的值。给定

$\prod_{i=1}^m p(x^{(i)}) = \prod_{i=1}^m \prod_{j=1}^{n_i} q(x_j^{(i)}|x_{j-2}^{(i)},x_{j-1}^{(i)})$

和$M =\sum_{i}n_i$，$t$的值是$\prod_{i=1}^m p(x^{(i)})$中出现的$q(x_j^{(i)}|x_{j-2}^{(i)},x_{j-1}^{(i)})$项的几何平均值。例如，如果困惑度等于$100$，则$t=0.01$，表示几何平均值为$0.01$。

关于困惑度的另一个有用的事实如下。对于测试数据中的任意三元组$u,v,w$，如果我们有估计

$q(w|u,v)=0$

那么困惑度将是$\infty$。要看到这一点，请注意在这种情况下，模型的测试语料库的概率为$0$，平均对数概率为$-\infty$。因此，如果我们将困惑度作为衡量语言模型的标准，那么我们应该不惜一切代价避免给出$0$估计值。

最后，给出一些关于困惑度的“典型”值的直觉。 Goodman（“A bit of progress in language modeling”）评估英语数据的一元，二元和三元语言模型，词汇量为$50000$。在二元模型中，我们参数$q(w|v)$，以及

$p(x_1...x_n) =\prod_{i=1}^n q(x_i|x_{i-1})$

因此，每个单词仅取决于句子中的前一个单词。在一元模型中，我们有参数$q(w)$，以及

$p(x_1...x_n) =\prod_{i=1}^n q(x_i)$

因此，每个单词的选择完全独立于句子中的其他单词。

Goodman报告三元模型的困惑度约为$74$，二元模型为$137$，一元模型为$500$。简单地分配给词汇表中每个单词概率$1/50000$的困惑度为$50000 $。因此，三元组模型明显比二元和一元模型有了很大的改进，并且相对于给词汇表中的每个单词分配$1/50000$的概率有了巨大的改进。

1.3.4 三元语言模型的优缺点

三元组假设可以说是相当强大的，并且在语言上是自然的（参见讲座幻灯片以供讨论）。总之，它是实际中非常有用的模型。

1.4 三元模型的平滑估计

如之前所述，三元语言模型具有非常多的参数。最大似然参数估计采用如下形式

$q(w|u,v) = \frac{c(u,v,w)}{c(u,v)}$

对于稀疏数据，这将产生严重问题。即使有大量的训练句子，许多$c(u,v,w)$以及$c(u,v)$也会很低，或者等于零。

在本节中，我们将介绍平滑估计方法，它可以缓解稀疏数据中发现的许多问题。关键的想法是依靠低阶统计估计——特别是，利用二元组或一元组的计数来“平滑”三元组估计。我们将讨论了两种在实际中非常常用的平滑方法：第一种是线性插值(linear interpolation); 第二，折扣方法(discounting)。

1.4.1 线性插值

线性插值的三元模型按如下方式导出。我们将三元，二元和一元最大似然估计定义为

$\begin{aligned} q_{ML}(w|u,v)&= \frac{c(u,v,w)}{c(u,v)} \\ q_{ML}(w|v)&= \frac{c(v,w)}{c(v)} \\ q_{ML}(w)&= \frac{c(w)}{c()} \end{aligned}$

我们扩展了我们的符号：$c(w)$是在训练语料库中看到单词$w$的次数，$c()$是在训练语料库中看到的单词总数。

三元，二元和一元估计有不同的优点和缺点。一元估计永远不会有分子或分母等于$0$的问题：因此估计总是定义明确的，并且总是大于$0$（规定每个单词在训练语料库中至少出现一次，这是一个合理的假设）。但是，一元估计完全忽略了上下文（前两个单词），因此丢弃了非常有价值的信息。相比之下，三元组估计确实利用了上下文，但是它有许多计数都是$0$的问题。二元估计值介于这两个极端情形之间。

线性插值的想法是使用全部三个估计，通过定义三元组估计如下：

$q(w|u,v) = \lambda_1 \times q_{ML}(w|u,v) + \lambda_2 \times q_{ML}(w|v) + \lambda_3 \times q_{ML}(w)$

这里$\lambda_1,\lambda_2,\lambda_3$是该模型的三个额外参数，它们满足

$\lambda_1\ge 0,\lambda_2\ge 0,\lambda_3\ge 0$

以及

$\lambda_1+\lambda_2 +\lambda_3 = 1$

因此，我们采用三个估计的加权平均值。

有许多估计$\lambda $的方法。常见的一个如下。我们还有一些held-out数据，这些数据与我们的训练以及测试语料库分开。我们将此数据称为开发数据。将$c’(u,v,w)$定义为在开发数据中看到三元组$(u,v,w)$的次数。很容易证明开发数据的对数似然，作为参数$\lambda_1,\lambda_2,\lambda_3$的函数，是

$\begin{aligned} L(\lambda_1,\lambda_2,\lambda_3) &= \sum_{u,v,w}c'(u,v,w)\log q(w|u,v)\\ &=\sum_{u,v,w}c'(u,v,w)\log(\lambda_1 \times q_{ML}(w|u,v) + \lambda_2 \times q_{ML}(w|v) + \lambda_3 \times q_{ML}(w)) \end{aligned}$

我们想选择$\lambda$的值来使$L(\lambda_1,\lambda_2,\lambda_3)$尽可能高。因此，我们应该选择

$\arg \max_{\lambda_1,\lambda_2,\lambda_3} L(\lambda_1,\lambda_2,\lambda_3)$

满足

$\lambda_1\ge 0,\lambda_2\ge 0,\lambda_3\ge 0$

以及

$\lambda_1+\lambda_2 +\lambda_3 = 1$

找到$\lambda$的最优值是相当直接的。

如上所述，我们的方法有三个平滑参数，$\lambda_1,\lambda_2,\lambda_3$。这三个参数可以解释为每个三元，二元和一元估计值上的置信度或权重。例如，如果$\lambda_1$接近$1$，这意味着我们对三元组估计$q_{ML}(w|u,v)$给出了高权重; 相反，如果$\lambda_1$接近于$0$，我们对三元组估计放置了一个低权重。

在实际中，通过允许$\lambda_1,\lambda_2,\lambda_3$的值依赖二元组$(u,v)$来增加额外的自由度是很重要的。特别地，当$c(u,v) $更大时，该方法允许$\lambda_1$更大——直觉是较大的$c(u,v)$的应该转化为我们对三元组估计更有信心。

注意，当$c(u,v)=0$时，该方法将确保$\lambda_1=0$，因为在这种情况下，三元组估计

$q_{ML}(w|u,v)= \frac{c(u,v,w)}{c(u,v)}$

没有意义。类似地，如果$c(u,v)$和$c(v)$都等于$0$，我们需要定义$\lambda_1=\lambda_2=0$，因为三元和二元极大似然估计此时都是未定义的。

该方法的一个扩展，通常称为bucketing，在1.5.1节中描述。此外，另一个更简单的方法是定义

$\begin{aligned} \lambda_1&= \frac{c(u,v)}{c(u,v)+\gamma} \\ \lambda_2&= (1-\lambda_1)\times \frac{c(v)}{c(v)+\gamma} \\ \lambda_3&=1-\lambda_1-\lambda_2 \end{aligned}$

其中$\gamma>0$是该方法的唯一参数。很容易验证

$\lambda_1\ge 0,\lambda_2\ge 0,\lambda_3\ge 0$

以及

$\lambda_1+\lambda_2 +\lambda_3 = 1$

在该定义下，可以看出$\lambda_1$随着$c(u,v)$的增加而增加，并且类似地$\lambda_2$随着$c(v)$的增加而增加。此外，如果$c(u,v)=0$，则$\lambda_1=0$，如果$c(v)=0$，则$\lambda_2=0$。$\gamma$的值可以通过最大化一组开发数据的对数似然来选择。

该方法相对粗糙，并且不太可能是最佳的。然而，它非常简单，并且在某些应用中它的实际效果很好。

1.4.2 折扣方法(Discounting Methods)

我们现在描述一种替代的估计方法，它在实际中也是常用的。首先考虑一种估计二元语言模型的方法，也就是说，我们的目标是定义

$q(w|v)$

对于任意

$\begin{aligned} w&\in \mathcal V\cup \{\text{STOP}\}\\ u,v&\in \mathcal V \cup \{*\} \end{aligned}$

第一步是定义折扣计数。对于任何满足$c(v,w)>0$的二元组$c(v,w)$，我们将折扣计数定义为

$c^*(v,w) =c(v,w)-\beta$

其中的$\beta$介于$0$和$1$之间（通常$\beta=0.5$）。因此，我们只需从计数中减去一个常数值。这反映了这样的直觉：如果我们从训练语料库中获取计数，我们将系统地高估在语料库中出现的二元组的概率（以及低估不出现在语料库中二元组）。

对于任何满足$c(v,w)>0$的二元组$c(v,w)$，我们定义

$q(w|v) = \frac{c^*(v,w) }{c(v)}$

因此，分子为折扣计数，分母为常规计数。

对于任何单词$v$，该定义导致一些丢失的概率质量，定义为

$\alpha(v) = 1-\sum_{w:c(v,w)>0} \frac{c^*(v,w) }{c(v)}$

例如，考虑图1.1中示例中显示的计数。这里展示所有满足$u=the,c(u,v)>0$的二元组$(u,v)$。我们使用折扣值$\beta=0.5 $。在这种情况下，我们有

$\sum_{w:c(v,w)>0} \frac{c^*(v,w) }{c(v)}= \frac{14.5}{48} +\frac{10.5}{48}+\frac{9.5}{48}+ \frac{4.5}{48}+\frac{1.5}{48} + 5\times \frac{0.5}{48} =\frac {43}{48}$

丢失的概率质量为

$\alpha(the)= 1-\frac {43}{48}=\frac {5}{48}$

折扣方法背后的直觉是将这个“缺失质量”分配给使得$c(v,w)=0$的$w$。

更具体地说，估计的完整定义如下。对于任何$v$，定义集合

$\mathcal A(v) = \{w:c(v,w)>0\}$

以及

$\mathcal B(v) = \{w:c(v,w)=0\}$

例如，对于图1.1中的数据，我们有

$\mathcal A(the) = \{dog, woman, man, park, job, telescope, manual, afternoon, country, street \}$

以及$\mathcal B(the)$为词汇表中剩余的词汇。

然后将估计定义为

$q_D(w|v) = \begin{cases} \frac{c^*(v,w) }{c(v)} &如果w\in \mathcal A(v)\\ \alpha(v) \times \frac{q_{ML}(w)}{\sum_{w\in \mathcal B(v)} q_{ML}(w)} & 如果w\in \mathcal B(v) \end{cases}$

因此，如果$c(v,w)>0$，我们返回

$\frac{c^*(v,w) }{c(v)}$

否则我们将剩余概率质量$\alpha(v)$按照一元估计$q_{ML}(w)$的比例划分。

Katz Back-Off Models

该方法可以以自然的递归方式推广到三元语言模型(Katz Back-Off Models)：对于任何二元组$(u,v)$，定义

$\mathcal A(u,v) = \{w:c(u,v,w)>0\}$

以及

$\mathcal B(u,v) = \{w:c(u,v,w)=0\}$

按如下方式定义三元组$(u,v,w)$的折扣计数

$c^*(u,v,w) =c(u,v,w)-\beta$

其中$\beta$是折扣值。那么三元模型为

$q_D(w|u,v) = \begin{cases} \frac{c^*(u,v,w) }{c(u,v)} &如果w\in \mathcal A(u,v)\\ \alpha(u,v) \times \frac{q_{D}(w|v)}{\sum_{w\in \mathcal B(u,v)} q_{D}(w|v)} & 如果w\in \mathcal B(u,v) \end{cases}$

其中

$\alpha(u,v) = 1-\sum_{w\in \mathcal A(u,v) } \frac{c^*(u,v,w) }{c(u,v)}$

是“丢失”概率质量。请注意，我们将丢失的概率质量按照之前定义的二元组估计值$q_{D}(w|v)$成比例地进行了划分。

这种方法的唯一参数是折扣值$\beta$。与线性插值模型一样，选择此参数值的常用方法是优化开发语料库的似然性，这也是和训练以及测试语料库分开的数据集。将$c’(u,v,w)$定义为三元组$(u,v,w)$出现在此开发语料库的次数。那么开发数据的对数似然函数是

$\sum_{u,v,w} c'(u,v,w) \log q_D(w|u,v)$

其中$q_D(w|u,v)$的定义如上。参数估计$q_D(w|u,v)$将随着$\beta$的变化而变化。通常我们会测试$\beta$的一组可能值——例如，我们可能会测试集合$\{0.1,0.2,0.3,…,0.9\}$中的所有值——我们对每个值都会计算开发数据的对数似然。然后，我们选择最大化此对数似然的$\beta$。

1.5 高级主题

1.5.1 结合桶的线性差值(Linear Interpolation with Bucketing)

在线性插值模型中，参数估计定义为

$q(w|u,v) = \lambda_1 \times q_{ML}(w|u,v) + \lambda_2 \times q_{ML}(w|v) + \lambda_3 \times q_{ML}(w)$

其中$\lambda_1,\lambda_2,\lambda_3$是该方法中的平滑参数。

在实际中，重要的是允许平滑参数随着二元组$(u,v)$的变化而变化，特别是，$c(u,v)$越大，$\lambda_1 $应该越大。（并且类似地，$c(v)$越大，$\lambda_2$越大）。实现这一目标的经典方法是通过一种通常被称为“桶”(bucketing)的扩展。

此方法的第一步是定义一个将二元组$(u,v)$映射到$\Pi(u,v)\in \{1,2,…,K\}$的函数$\Pi$，其中$K$是桶的数量。因此，该函数将二元组分划分为$K$个不同的子集。该函数是手动定义的，通常取决于训练数据中的计数。$K=3$时，一个例子为

$\begin{aligned} \Pi(u,v) &= 1 &如果c(u,v) > 0\\ \Pi(u,v) &= 2 &如果c(u,v) = 0且c(v)>0\\ \Pi(u,v) &= 3 &其他 \end{aligned}$

这是一个非常简单的定义，该定义根据$c(u,v)$和$c(v)$是否等于$0$来定义。

再看另一个稍微复杂的定义，它对二元组$(u,v)$的频率更敏感

$\begin{aligned} \Pi(u,v) &= 1 &如果100\le c(u,v)\\ \Pi(u,v) &= 2 &如果50\le c(u,v) < 100\\ \Pi(u,v) &= 3 &如果20\le c(u,v) < 50\\ \Pi(u,v) &= 4 &如果10\le c(u,v) < 20\\ \Pi(u,v) &= 5 &如果5\le c(u,v) < 10\\ \Pi(u,v) &= 6 &如果2\le c(u,v) <5\\ \Pi(u,v) &= 7 &如果 c(u,v)=1\\ \Pi(u,v) &= 8 &如果 c(u,v)=0,c(v)>0\\ \Pi(u,v) &= 9 &其他 \end{aligned}$

给定函数$\Pi(u,v)$的定义，对于任意$k\in \{1,2,…,K\}$，我们引入平滑参数$\lambda_1^{(k)},\lambda_2^{(k)},\lambda_3^{(k)}$。因此，每个桶具有其自己的一组平滑参数。对于所有$k\in \{1,2,…,K\}$，我们有如下约束

$\lambda_1^{(k)}\ge 0,\lambda_2^{(k)}\ge 0,\lambda_3^{(k)}\ge 0$

以及

$\lambda_1^{(k)}+\lambda_2^{(k)}+\lambda_3^{(k)} =1$

线性插值估计将是

$q(w|u,v) = \lambda_1^{(k)} \times q_{ML}(w|u,v) + \lambda_2^{(k)} \times q_{ML}(w|v) + \lambda_3^{(k)} \times q_{ML}(w)$

其中

$k =\Pi (u,v)$

因此，我们已经关键地引入了平滑参数对于$\Pi(u,v)$的依赖性。所以，每个桶都有自己的一组平滑参数; 平滑参数的值可以根据$\Pi(u,v)$的值而变化（通常与$c(u,v),c(v)$直接相关）。

使用开发数据集再次估计平滑参数。如果我们再次将$c’(u,v,w)$定义为三元组$(u,v,w)$出现在开发数据中的次数，开发数据的对数似然性是

$\begin{aligned} &\sum_{u,v,w} c'(u,v,w) \log q_D(w|u,v)\\ =&\sum_{u,v,w} c'(u,v,w) \log\Big( \lambda_1^{(\Pi(u,v))} \times q_{ML}(w|u,v) + \lambda_2^{(\Pi(u,v))} \times q_{ML}(w|v) + \lambda_3^{(\Pi(u,v))} \times q_{ML}(w) \Big) \\ =&\sum_{k=1}^K\sum_{u,v,w:\Pi(u,v)=k} c'(u,v,w) \log\Big( \lambda_1^{(k)} \times q_{ML}(w|u,v) + \lambda_2^{(k)} \times q_{ML}(w|v) + \lambda_3^{(k)} \times q_{ML}(w) \Big) \end{aligned}$

我们选择$\lambda_1^{(k)},\lambda_2^{(k)},\lambda_3^{(k)}$来使上述函数最大化。

本讲测验题

Coursera部分

1.

可以产生的句子为

the
the dog
the dog runs

所以答案为$3$

2.

c,e,f

3.

the dog runs STOP

$p_1= 1\times 0.5\times 1\times 1= \frac 1 2$

the cat walks STOP

$p_2= 1\times 0.5\times 1\times 1 = \frac 1 2$

the dog runs STOP

$p_3= 1\times 0.5\times 1\times 1 = \frac 1 2$

所以困惑度为

$\frac 1 {\sqrt[12] \frac 1 8} \approx 1.189$

4.

$\begin{aligned} q_{ML}(\text{book}|\text{the},\text{green})&= \frac{1}{1} \\ q_{ML}(\text{book}|\text{green})&= \frac{1}{2} \\ q_{ML}(\text{book})&= \frac{3}{14} \end{aligned}$

所以

$q_{LI}(\text{book}|\text{the},\text{green}) =\frac 1 3 \times 1+\frac 1 3\times \frac 1 2 +\frac 1 3 \times \frac 3 {14} \approx0.571$

5.

因为

$\begin{aligned} \sum_{w\in \mathcal V} q(w|u,v) &= \lambda_1 \times\sum_{w\in \mathcal V} q_{ML}(w|u,v) + \lambda_2 \times \sum_{w\in \mathcal V} q_{ML}(w|v) + \lambda_3 \times\sum_{w\in \mathcal V} q_{ML}(w)\\ &=\lambda_1+\lambda_2+\lambda_3\\ &=1 \end{aligned}$

所以(a)不会发生。

(b)可能会发生，只要$q_{ML}(w|v)= q_{ML}(w)=0$

(c)可能会发生，只要$q_{ML}(w|u,v)=0, q_{ML}(w|v)= q_{ML}(w)=1$

6.

注意到

$\begin{aligned} \alpha(v) &= 1-\sum_{w:c(v,w)>0} \frac{c^*(v,w) }{c(v)}\\ &=1-\sum_{w:c(v,w)>0} \frac{c(v,w)-\beta }{c(v)} \\ &=\sum_{w:c(v,w)>0}\frac{\beta}{c(v)} \end{aligned}$

所以

$\alpha(\text{the})= 15\times 0.3 / 70\approx 0.0642$

7.

注意到

$c(\text{his},\text{book}) =0 ,c(\text{his})= 1,c(\text{his},\text{house}) =1$

所以

$\alpha(\text{his}) = 1- \frac{1-0.5}{1} =\frac 1 2$

此时用估计式

$\alpha(v)\times\frac{q_{ML}(w)}{\sum_{w\in \mathcal B(v)} q_{ML}(w)}$

因为

$\begin{aligned} q(\text{book})&=\frac 1 6\\ q(\text{the})&=\frac 16\\ q(\text{STOP})&=\frac 26\\ q(\text{his})&=\frac 16\\ \mathcal B(\text{his})&=\{\text{the,book,STOP,his}\} \end{aligned}$

所以

$\frac{q_{ML}(\text{book})}{\sum_{w\in \mathcal B(\text{his})} q_{ML}(w)} = \frac{1/6}{1/6+1/6+2/6+1/6} =\frac 1 5$

从而

$q_{D}(\text{book}|\text{his}) =\frac 1 2 \times \frac 1 5 = \frac 1 {10}$

课内部分

1.

因为概率和为$1$，所以类似三元模型，可以定义

$\alpha(t, u, v)= 1- \sum_{w \in \mathcal{A}(t, u, v)} \frac{c^{*}(t, u, v, w)}{c(t, u, v)}$

2.

2a：

如果存在$p(x^{(i)})=0$，那么$l\to -\infty$，$2^{-l}\to \infty$，因此最大值为$\infty$。

2b：

因为$p(x^{(i)})\le 1$，所以

$\begin{aligned} l&=\frac{1}{M} \sum_{i=1}^{m} \log _{2} p(x^{(i)}) \le 0\\ 2^{-l}&\ge 1 \end{aligned}$

所以最小值为$1$。

2c：

训练语料：

$\text{the a STOP}$

测试语料：

$\text{a the STOP}$

2d：

训练语料：

$\text{the a STOP}$

测试语料：

$\text{the a STOP}$

3.

3a：

$\begin{aligned} & q(w | u, v) \\ =\quad& \alpha \times q_{M L}(w | u, v)+(1-\alpha) \times\left(\beta \times q_{M L}(w | u)+(1-\beta) \times q_{M L}(w)\right) \\ =\quad& \alpha \times q_{M L}(w | u, v) +(1-\alpha)\times\beta\times q_{M L}(w | u) +(1-\alpha)\times (1-\beta)\times q_{M L}(w) \end{aligned}$

所以

$\begin{aligned} \lambda_1 &=\alpha\\ \lambda_2 &=(1-\alpha)\beta\\ \lambda_3 &=(1-\alpha)(1-\beta) \end{aligned}$

如果

$\alpha =\beta =\frac 12$

那么

$\begin{aligned} \lambda_1 &=\frac 1 2\\ \lambda_2 &=\frac 1 4\\ \lambda_3 &=\frac 1 4 \end{aligned}$

3b：

$\begin{aligned} \sum_w q(w | u, v) &=\sum_w \alpha(u, v) \times q_{M L}(w | u, v) +(1-\alpha(u, v)) \times \left(\beta(u) \times q_{M L}(w | u)+(1-\beta(u)) \times q_{M L}(w)\right)\\ &= \alpha(u, v) +(1-\alpha(u, v)) \times (\beta(u) +1-\beta(u))\\ &= \alpha(u, v) + (1-\alpha(u, v))\\ &=1 \end{aligned}$

3c：

直觉是如果$(u,v),u$出现的次数较多，那么$q_{M L}(w | u, v),q_{M L}(w | u)$占的权重应该较大，$C_1,C_2$是为了防止分母为$0$并且决定权重趋于$0$的速度。

3d：

只要说明$q(w|u,v)>0$即可，因为

$\begin{aligned} q(w | u, v) = \alpha(u, v) \times q_{M L}(w | u, v) +(1-\alpha(u, v)) \times \left(\beta(u) \times q_{M L}(w | u)+(1-\beta(u)) \times q_{M L}(w)\right) \end{aligned}$

因为任取测试语料库中的单词$u$，我们有$\text{Count}(u)>0$，所以

$\begin{aligned} q(w | u, v) &\ge (1-\alpha(u, v)) \times (1-\beta(u)) \times q_{ML}(w)\\ &=\frac{C_1}{\text{Count}(u,v) +C_1}\times \frac{C_2}{\text{Count}(u) +C_2} \times q_{ML}(w) \\ &>0 \end{aligned}$

4.

第一个命题错误，反例如下

$\text{Count}^* (u,v) = 1-1.5=-0.5$

第二个命题正确，因为：

$\begin{aligned} \sum_{w} q_{B O}(w | v) &= \sum_{w\in \mathcal A(v)} \frac{\text{Count}^{*}\left(v, w\right)} {\text{Count}\left(v\right)}+ \sum_{w\in \mathcal B(v)} \alpha(v)\frac{\text{Count}^{*}\left(v, w\right)} {\text{Count}\left(v\right)}\\ &=1-\alpha(v)+\alpha(v)\\ &=1 \end{aligned}$