语言模型问题的定义

词汇表：\(V \) = {the, man, telescope, ...}

语句：\(V^{+}\)，无限多个，由词汇表中的若干个词加上结尾处的STOP标记组成；例如，the fan saw Beckham STOP，甚至the the the STOP也属于这其中。

输入：训练样本，各种各样实际中使用的句子，可以从报纸来，也可以从网页来。

输出：一个面向语句的概率分布，满足以下条件；实际表达的意义就是让像人话的句子概率更高，反之则更低。

\[ p(x) >= 0, \sum_{x \in V^{+}} p(x) = 1\]

这个模型有啥用

原始的出发点是语音识别，因为一段语音通常可以被识别成不同的句子，例如，recognize speech vs wrench a nice beach，但是前者明显更像人话，这时应用语言模型就可以辨识出这段话是前者的可能性更大。

另外，语言模型中的估计方法（estimation/smoothing method）也会很广泛地应用到NLP的其它问题之中，这也算是一个用途吧。

一个简单的方法

想解决语言模型问题，实际就是想得到一个合适的\(p(x)\)，如何做呢？一个简单的方法就是记数，假设训练样本的规模是N，统计下训练样本中每个x出现的次数，然后\( p(x) = C(x) / N\)。但是这样做的问题是，如果有一个训练样本中从未出现的句子，那么它的概率就是0了，也就是说这个未出现的句子无论具体内容是啥，\( p(x)\)都认为它不是人话。

马尔科夫模型

马尔科夫模型假设第n个词出现的可能性只依赖于它的前k个词，即第n-1至第n-k个词。由于后面要讲是三元模型，所以这里用的是就三阶马尔科夫模型。具体来说，

\[p(x_1, ..., x_n) = p(x_1)*p(x_2|x_1)*p(x_3|x_1, x_2)*...*p(x_n|x_1, ..., x_{n-1})\]

这个是没有加入马尔科夫的链式规则，精确的等式，但是如果我们想用这个来算语言模型的话，就得从训练数据中估计出每个\(p(x_i|x_1, x_2, ..., x_{i-1}) \)，这样我们就需要估计出\(O(|V|^{n})\)个参数。参数太多显然是没法搞的，因为参数越多，需要的训练数据就越多，否则就是造成参数极不稳定，甚至没什么意义。

如果加入前面提到的三阶马尔科夫假设的话，问题就简化了

\[p(x_1, ..., x_n) = p(x_1)*p(x_2|x_1)*p(x_3|x_1, x_2)*...*p(x_n|x_{n-2}, x_{n-1})\]

这样参数的个数就降到了\(O(|V|^3)\)（其实这个量级仍然太大，后面会讲到解决方法）。如果我们假设\(x_{-1} = x_0 = *\)，表示开始符号，那么就可以将上式写成

\[p(x_1, ..., x_n) = \Pi_{i=1...n} p(x_i|x_{i-2}, x_{i-1})\]

还有个问题，就是上式只能表示长度为n的句子，而我们想要的是对任意长度的任意句子都有效的分布p。实际上，融合我们前面的定义\(x_n = STOP\)，我们已经可以表示任意的句子了。

三元语法模型

把前面的三阶马尔科夫模型直接应用，就是三元语法模型，它包括以下两个部分

• 一个有限的词汇表\(V\)
• 对每个\(w \in V \cup {STOP}, u, v \in V \cup {*}\)，都有一个参数\(q(w|u, v)\)

于是对任何一个句子\(x_1, ..., x_n\)，其中\(x_1, ..., x_{n-1} \in V, x_n = STOP\)，都可以直接它所对应的概率

\[p(x_1, ..., x_n) = \Pi_{i=1,...,n} q(x_i|x_{i-2}, x_{i-1})\]

举个例子，

\[p(the dog barks STOP) = q(the|*, *) * q(dog|*, the) * q(barks|the, dog) * q(STOP|dog barks)\]

好了，到这里，剩下的最后一个问题就是参数\(q(w|u, v)\)怎么从训练数据中估计出来了，最简单的方式就是MLE（极大似然估计法），即

\[q(x_i|x_{i-2}, x_{i-1}) = \frac{Count(x_{i-2}, x_{i-1}, x_i)}{Count(x_{i-2}, x_{i-1})}\]

正如前面所述的，这里参数的个数是\(O(|V|^3)\)，依然不少，要使用这种方法得到稳定的参数估计值就需要使用大量的数据。否则的话，上式的分子分母都极有可能是零，那么得到的参数意义就不大了。

使用Perplexity对模型进行评估

假设我们除了有用于训练模型参数的训练数据之外，还有一些测试数据，表示为\(s_1, s_2, ..., s_m\)，那么就可以用这些测试数据来评估训练得到的模型的可用性。这里定义了perplexity这个概念，本质上就是模型对这些测试数据的对数似然性：

\[Perplexity = 2^{-l}, where l = \frac{1}{M} \sum_{i=1...m} log p(s_i)\]

其中M表示测试数据是总的单词数据，因此l代表的就是模型对单个词的似然性；测试数据与模型的适应程度越好，似然性越大，perplexity就越小。

下面是对几个模型的比较

• 均匀分布：\(q(w|u, v) = \frac{1}{|V|+1}\)，无论上下文是啥，也不管当前词是啥，这个概率值总是固定的，这是一个很粗的模型，所以perplexity也很高为\(|V|+1\)；
• 一元语法模型：也就是unigram，就是在训练数据上记数，完全不管上下文，在Goodman的实验中（|V|=50000），它的perplexity为955；
• 二元语法模型：就是只考虑前一个单词对当前词的影响，同一个实验中perplexity为137；
• 三元语法模型：就是前面花大篇幅讲的那个模型，考虑当前词前面两个单的影响，perplexity为74；这已经是足够好的效果了。

但是三元语法模型也有它的不足，它无法捕获长距离的依赖关系，但是考虑的上下文太多了，就又会出现sparse data的问题，使参数估计很困难。其实这里也就是一个bias-variance tradeoff，上下文考虑得多，自然bias就小，但是由于训练数据相对不足，variance就大了；相反地，如果上下文考虑得少，variance小，但是bias就大了，所以不得不做一些折衷， 讲师说trigram的方法就是一个比较好的折衷。

参数平滑方法

我觉得下面这些内容才是这段课程的重点，就是怎样解决前面提到的由于数据稀疏问题而造成的MLE估计不可靠的问题。课程里介绍了两个方法，一种是线性插值，另一种是katz-backoff的类递归方法。实际上还有很多其它的方法，可以参考Foundations of Statistical Natural Language Processing中的第6章，也许未来这章的内容我也会总结一下写在blog上。

线性插值

这个方法的动机就是上一小节最后提到的bias-variance trade-off，既然unigram的variance小，而trigram的bias小，为啥不想个办法整合一下呢？于是就有了

\[q(w_i|w_{i-1}, w_{i-2}) = \lambda_1 \dot q_{ML}(w_i|w_{i-1}, w_{i-2}) + \lambda_2 \dot q_{ML}(w_i|w_{i-1}) + \lambda_3 q_{ML}(w_i)\]

\[\lambda_1 + \lambda_2 + \lambda_3 = 1, \lambda_i >=0\]

容易证明这个线性插值所产生的\(q(w_i|w_{i-1}, w_{i-2})\)也是一个合法的概率分布，符合归一化及>=0的条件。

各个\(q_{ML}\)都可以从训练数据中直接计算得到，那么剩下的事就是如何计算\(\lambda_i\)了。这里使用的方法是搞一份validation data，记这份数据中各个三词序列出现次数为\(c'(w_1, w_2, w_3)\)，那么log-likelihood的表达式即为

\[L(\lambda_1, \lambda_2, \lambda_3) = \sum_{w_1, w_2, w_3} c'(w_1, w_2, w_3)logq(w_3|w_1, w_2)\]

表达式中未知参数只有\(\lambda_i\)，所以使用这个表达式对其求偏导应该就可以了。另外，前面提到的perplexity实际就是log-likelihood的变形，所以这种方法就也是在寻找一组参数，使perplexity最大化。

再进一步，前面这种方式得到是一个不依赖于具体\(w_1, w_2\)的\(\lambda_i\)。极端情况下，如果我们已知\(w_1, w_2\)出现的次数足够多，还不如直接用trigram就好了（\(\lambda_3 = 1\)，其它两个为0），相反地如果\(w_1, w_2\)出现极少，那么\(\lambda_1\)就应该相应的更重一些。总结一下就是说，最好是能让\(\lambda_i\)能随着具体\(w_1, w_2\)出现的次数而变化。于是就出现了下面\(\Pi(w_{i-2}, w_{i-1})\)这个东西

\[C(w_{i-2}, w_{i-1}) = 0, \Pi(w_{i-2}, w_{i-1}) = 1\]

\[1 <= C(w_{i-2}, w_{i-1})  <= 2, \Pi(w_{i-2}, w_{i-1}) = 2\]

\[3 <= C(w_{i-2}, w_{i-1})  <= 5, \Pi(w_{i-2}, w_{i-1}) = 3\]

\[C(w_{i-2}, w_{i-1}) >= 5, \Pi(w_{i-2}, w_{i-1}) = 4\]

再然后就是依赖于\(\Pi(w_{i-2}, w_{i-1})\)的\(q\)

\[q(w_i|w_{i-1}, w_{i-2}) = \lambda^{\Pi(w_{i-2}, w_{i-1})}_1 q_{ML}(w_i|w_{i-1}, w_{i-2}) + \lambda^{\Pi(w_{i-2}, w_{i-1})}_2 q_{ML}(w_i|w_{i-1}) + \lambda^{\Pi(w_{i-2}, w_{i-1})}_3 q_{ML}(w_i)\]

实际上就是按照每个\(w_i\)的context出现的次数，即\(C(w_{i-2}, w_{i-1})\)，来对\(w_i\)分组，每组使用一套\(\lambda\)参数。

Katz Back-off Model

这种方法的动机的是从训练数据里得到的ML估计是对存于在训练数据里的词的过高估计（尤其是对仅出现一次的词），而对未登陆词的过低估计（ML估计都是0），所以需要从已有词的概率中抽取出一部分，分给这些未登陆词。以bigram为例，已存在词的次数被折掉了一部分(0.5这个数是个经验值，也可以使用前面的validation set方法来估计出来)，

\(Count^{*}(w_{i-1}, x) = Count(w_{i-1}, x) - 0.5\)

而折掉的概率一共是

\[\alpha(w_{i-1}) = 1 - \sum_{w} \frac{Count^{*}(w_{i-1}, w)}{Count(w_{i-1})}\]

这些概率会根据unigram中各个x的概率比例再重新分配。具体如下：定义两个集合，\(A(w_{i-1}) = \{w: Count(w_{i-1}, w) > 0\}, B(w_{i-1}) = \{w: Count(w_{i-1}, w) = 0\}\)，则有

\[q_{BO}(w_i|w_{i-1}) = Count^{*}(w_{i-1}, w_i) / Count(w_{i-1}), w_i \in A(w_{i-1})\]

\[q_{BO}(w_i|w_{i-1}) = \alpha(w_{i-1}) \frac {q_{ML}(w_i)} {\sum_{B}q_{ML}{w_j}}, w_i \in B(w_{i-1})\]

也就是说如果\(w_i\)出现在了训练语料中就使用高阶模型，否则的话就回退到低阶的模型中，在bias和variance中取一个折衷。基于上面bigram的定义，可以继续定义trigram模型，使未登陆词回退到bigram中。

最后是说可能对trigram模型的进一步改进方法，包括topic model，语法模型等，但是"It's generally hard to improve on trigram models though!!"