Language Modeling

N-Gram

这里首先有个语料库，记录了很多条句子，然后预测给定句子出现的概率。给定一个句子，这里句子的长度为n，也就是\(|V|=n\)，第i个单词用字母\(x_i\)表示，那么概率公式表示为：\(P(X_1=x_1,X_2=x_2,...X_n=x_n)\)

使用马尔科夫假设第i个单词出现只与前面几个单词有关，这里如果和前面的全部单词有关，则有： \[ P(X_1=x_1,X_2=x_2,...X_n=x_n)=P(X_1=x_1)\prod_{i=2}^{n}{P(X_i=x_i|X_1=x_1,...,X_{i-1}=x_{i-1})} \] 如果是TRIGRAM LANGUAGE MODELS ，有 \[ P(X_1=x_1,X_2=x_2,...X_n=x_n)=\Pi_{i=1}^{n}{P(X_i=x_i|X_{i-2 }=x_{i-2},X_{i-1}=x_{i-1})} \] 即\(p(x_1,x_2,...,x_n)=\Pi_{i=1}^{n}q(x_i|x_{i-2},x_{i-1})\)，而\(q(w|u,v)=\frac{c(u,v,w)}{c(u,v)}\)

这里如果我们使用bigram模型的话，且\(x_0=x_{-1}=*\)，该式子就变为如下： \[ P(X_1=x_1,X_2=x_2,...X_n=x_n)=\prod_{i=1}^{n}{P(X_i=x_i|X_{i-1}=x_{i-1})} \] 摘抄这个博客举的例子：假设语料库总词数为13,748 词和词频表如下所示：

那么对于句子I want to eat Chinese food，其概率 \[ P(I\, want\, to \,eat\, Chinese\, food)\\ =P(I)*P(want|I)*P(to|want)*P(eat|to)*P(Chinese|eat)*P(food|Chinese)\\ =0.25*1087/3437*786/1215*860/3256*19/938*120/213\\ =0.000154171 \]

这里讲一下参数个数是\(|V|^2\)，可以从上面的第二个图中看到，是词序列频度的大小。

Evaluating Language Models：Perplexity

这里给出了评估语言模型的指标——困惑度，选取一些句子，这些句子不在语料库中，也就是新的句子，用\(x^{(i)}\)表示第i个句子，其中第i个句子又由单词\(x_{1}^{(i)},x_{2}^{(i)},x_{3}^{(i)},...\)组成，那么对于这些测试的句子，计算所有句子的概率积： \[ \Pi_{i=1}^{m}p(x^{(i)}) \]

直观的感受是该结果越大，说明语言模型越好。[至于此处为什么，我也讲不清楚，可以理解成模型对未知句子的预测能力吧] 这里设第i个句子的长度是\(n_i\)，那么记\(M=\sum_{i=1}^{m}n_{i}\)，定义平均log概率如下： \[ \frac{1}{M}log_2\prod_{i=1}^mp(x^{(i)})\\ =\frac{1}{M}\sum_{i=1}^{m}log_2p(x^{(i)}) \]

定义困惑度为\(2^{-l}\)，其中\(l=\frac{1}{M}\sum_{i=1}^{m}log_2p(x^{(i)})\)。于是有困惑度越低，语言模型在未知数据上表现越好，最后给出了对于词汇表为50000时，trigram模型的困惑度是74，bigram模型的困惑度是137，unigram模型的困惑度是955

Smoothed Estimation of Trigram Models

比较常见的两种平滑技术 linear interpolation和 discounting methods。

Linear interpolation

\[ 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()} \] 这个主要的思想是将上面三个评估相加，如下： \[ q(w|u,v)=\lambda_1q_{ML}(w|u,v)+\lambda_2q_{ML}(w|v)+\lambda_3q_{ML}(w) \] 其中\(\lambda_1\geq 0,\lambda_2\geq 0,\lambda_3\geq 0\)且\(\lambda_1+\lambda_2+\lambda_3=1\)

那么如何得到参数\(\lambda_1,\lambda_2,\lambda_3\)呢，这里用到log似然估计，其中选取held-out data（记 development data），这部分数据独立于training和test数据，其中记\(c'(u,v,w)\)为development data中trigram\((u,v,w)\)出现的次数，L函数如下： \[ 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_1q_{ML}(w|u,v)+\lambda_2q_{ML}(w|v)+\lambda_3q_{ML}(w)) \] 然后求解如下式子： \[ arg\,\,\,\,max_{\lambda_1,\lambda_2,\lambda_3}\,\,L(\lambda_1,\lambda_2,\lambda_3)\\ \lambda_1\geq 0,\lambda_2\geq 0,\lambda_3\geq 0\\ \lambda_1+\lambda_2+\lambda_3=1 \] 当然还有bucketing方法来求解\(\lambda\)，这里就不记录了，在Michael Collins上有

Discounting Methods

notes上讲的也很清楚，就是设置一个参数\(\beta\)，且\(\beta\)在0到1之间。

然后对于bigram模型来说，将原来的\(c(v,w)\)减去\(\beta\)作为\(c^*(v,w)\)，这里针对的是语料库，那么本来有\(\sum_{c(v,w)>0}\frac{c(v,w)}{c(v)}=1\)，但是变为\(c^*(v,w)\)后就小于1了，这里记 \[ \alpha (v)=1-\sum_{c(v,w)>0}\frac{c^*(v,w)}{c(v)} \]

定义如下两个集合： \[ A(v)=\{w:c(v,w)>0\} \\ B(v)=\{w:c(v,w)=0\} \] A(v)表示在语料库中有的，B(v)表示在语料库中没有的，主要是B(v)，虽然语料库中没有，但不能为0，所以将其变为N-1 gram，这里变为unigram，具体公式如下： \[ q_D(w|v)=\left\{\begin{matrix} \frac{c^*(v,w)}{c(v)}& If \,\,w\in A(v) \\ \alpha(v) \frac{q_{ML}(w)}{\sum_{w \in B(v)}q_{ML}(w)} & If\,\,w\in B(v) \end{matrix}\right. \]

trigram模型同理，见notes。 那么怎么估计\(\beta\)呢，和前面的一样，使用log似然函数，即： \[ \sum_{u,v,w}c'(u,v,w)log\,q(w|u,v) \] 然后给定一组\(\beta\)集合{0.1,0.2,0.3,…0.9}，然后用上面的公式计算最大值对应的值就为\(\beta\)的值。