本栏目来源于对Coursera 在线课程 NLP（by Michael Collins）的理解。课程链接为：https://class.coursera.org/nlangp-001

1. 语言模型定义：

Model Representation：

• V：集合V包含语料中所有单词，例如：V={the,dog,laughs,saw,barks,cat,...}；
• x₁x_2...x_n：x₁x_2...x_n为句子序列，其中n≥1，x_n为句子的STOP符（结束标志）；
•  p(x₁,x₂,...,x_n)：集合V的一种可能的分布，其中对任意<x₁x_2...x_n>,p(x_1,x_2,...,x_n)≥0，且 ∑_<x1x2...xn>p(x₁,x₂,...,x_n)=1；

例如：假设c(x₁x_2...x_n)是x₁x_2...x_n在语料中出现的频次，N是语料句子总数，定义 p(x₁,x₂,...,x_n)=c(x₁x_2...x_n)/N  但是该模型效果很差由于其无法预测语料中未出现的新单词。

2. 马尔科夫模型（Markov Model）

2.1 定长序列的马尔科夫模型

假设单词序列x₁x_2...x_n为定长的n,对于联合概率P(X₁=x₁,X₂=x₂,...X_n=x_n),可见x₁x_2...x_n有|V|ⁿ种组合。

• 在一阶马尔科夫过程中，假设第i个单词出现与否取决于其前面的单词x_i-1：

因此序列x₁x_2...x_n出现的概率为：

• 在二阶马尔科夫过程中（trigram），假设每个单词的出现取决于其前面的两个单词：

因此序列x₁x_2...x_n出现的概率为：

PS：定义x₀=x_-1=*，即句子序列开始符。

2.1 变长序列的马尔科夫模型

假设单词序列x₁x_2...x_n为可变长度的句子序列，即n为随机变量，此时假设x_n为STOP符唯一的表示句子的结尾。继续使用前面的假设，对于二阶马尔科夫过程：

其中x_n=STOP

计算流程为：

• (1)初始化i=1，x₀=x_-1=*；
• (2)在分布中计算x_i：P(X_i=x_i|X_i-2=x_i-2,X_i-1=x_i-1);
• (3)若x_i=STOP,返回序列x₁x_2...x_i。否则令i=i+1，重复步骤（2）

3. Trigram语言模型

假设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)是模型的参数，w属于集合{V,STOP}，u,v属于集合{V,*},x₀ = x_-1 =*,模型形式如下：

其中q(w|u,v)≥0 且

 例如：句子序列 the dog barks STOP

p(the dog barks STOP)=q(the|*,*)×q(dog|*,the)×q(barks|the,dog)×q(STOP|dog,barks)

4. 极大似然估计（Maximum-Likelihood Estimates）

定义c(u,v,w)为trigram(u,v,w)在训练语料中出现的频次，例如c(the,dog,barks)即 “the dog barks”序列在语料中出现的次数，同理c(u,v)为bigram(u,v)在语料中出现的频次，对任意u,v,w，定义：

例如：q(the,dog,barks)估计为：

由于词数量庞大，该方法的问题有：

• 许多词项会出现q(w|u,v)=0由于c(u,v,w)=0，而将未在训练语料中出现的序列组合计算为0是不合理的；
• 当c(u,v)为0时，该定义式无解；

5. 语言模型评估：复杂度（Perplexity）

 假设测试集为x⁽¹⁾,x⁽²⁾,...x⁽ⁿ⁾.其中x⁽ⁱ⁾为序列,x₁⁽ⁱ⁾x₂⁽ⁱ⁾...x_ni⁽ⁱ⁾，ni为第i个测试句子的长度并以STOP作为结束符。一种模型的评价标准为计算整个测试集句子出现的概率，即：

PS：概率值越大，模型对新词的预测效果越好。

• M：测试语料集词的总数
• ni：第i个测试句子的长度

平均log概率为：

模型复杂度定义为 2^-l ，其中 

PS:复杂度越小，模型对于预测新数据的效果越好。

例如：对于语言模型 q(w|u,v)=1/N，这时该模型的复杂度为N，可见是很差的模型。

6 Trigram模型的平滑估计

借助bigram和unigram的结果来平滑trigram模型。可以使用linear interpolation（线性插值）和discounting methods。

6.1 Linear Interpolation

定义trigram,bigram和unigram的极大似然估计为：

其中c(w)是词w在训练语料中出现的次数，c()是训练语料的总词数。trigram,bigram和unigram有各自的优缺点。unigram不会出现算式分子或分母为0的情况，但是却忽略了句子上下文的关系；相反，trigram充分利用了文本关系但很多算式结果为0.

Linear Interpolation应用如下定义来平滑模型：

其中λ₁≥0,λ₂≥0,λ₃≥0是模型的另外参数，且λ₁+λ₂+λ₃=1。为trigram,bigram和unigram的权重参数。

• 最优λ计算方法：我们从训练语料和测试语料中分离出新的集合称为development data，定义为c‘(u,v,w)为development data集合中trigram(u,v,w)出现的频次。development data集合的log似然估计为：

目标函数：

在实际应用中，当c(u,v)很大时，可以增大λ₁（由于大的c(u,v)说明trigram更加有效）；当c(u,v)=0时，令λ₁=0（由于此时q_ML(w|u,v)没有定义）；同理若c(u,v),c(v)都为0，我们就需要λ₁=λ₂=0（由于trigram,bigram都无定义）.

• 还有一种简单计算λ的方法：

其中γ>0，该方法相对粗糙，可能并非最优，但是很简单。

6.2 Discounting Methods

定义discounted counts：其中任意bigram c(v,w)>0，β在0和1之间；

因此定义：

例如：对如下数据，词"the"在语料中共出现了48次，下表列出了所有的bigram。另外我们利用discounted count c^*(x)=c(x)-β。且β=0.5 最后计算c^*(x)/c(the).该定义造成了一些概率丢失，定义如下：

本例中，，

完整定义如下： A(v)={w:c(v,w)>0}且B(v)={w:c(v,w)=0}

本例中，A(the)={dog,woman,man,park,job,telescope,manual,afternoon,country,street},B(the)是此表中其余集合。

 因此，若c(v,w)>0,返回c^*(v,w)/c(v);否则，将α(v)成比例地分给unigram来评估q_ML(w)。

•  该方法也可以用来计算trigram模型，对任意bigram(u,v)定义：

A(u,v)={w:c(u,v,w)>0}且B(u,v)={w:c(u,v,w)=0}

• 定义trigram的discounted count：

故trigram模型为：

其中：

• 求解最优β：通常使用在development data上计算似然概率的方法来求解最优β。定义c‘(u,v,w)为development data中trigram(u,v,w)出现的频次，log似然概率为：

通常我们为β设置可能的数值集合（例如{0.1,0.2,0.3,...,0.9}）分别计算其log似然概率，从中选出令log似然概率最大的β即可。

本文为原创博客，若转载请注明出处。

Language Modeling---NLP学习笔记（原创）