NLP语言模型_bi-gram

语言模型

  一个语言模型通常构建为字符串$s$的概率分布$p(s)$，$p(s)$试图反应的是字符串$s$作为一个句子出现的概率，用来判断这个句子该不该出现，例如，在一个描述人类说话的语言模型中，如果一个句子说“这只鸡把人吃了”，即便这句话的语法正确，它出现的概率仍然为0。语言模型就是这样一个计算句子概率的东西。

1 基本概念

  对于一个句子$s=w_1{w}_2\cdots w_m$，其概率计算公式可以表示为：
$$p(s)=p(w_1)p(w_2|w_1)p(w_3|w_1{w}_2)\cdots p(w_m|w_1{w}_2\cdots w_{m-1})=\prod _{i=1}^{m}p(w_i|w_1\cdots w_{i-1})$$
这个概率公式就是条件概率的乘法规则，需要注意的是当$i=1$时，$p(w_1|w_0)=p(w_1)$。该式中的$w_i$叫做统计基元（基元），它可以是字、词、短语或词类等，为了方便表述，通常以“词”代之。$w_i$的概率由$w_1\cdots w_{i-1}$决定，一般地我们把前$i-1$个词$w_1\cdots w_{i-1}$称为第$i$个词的“历史”。

1.1 一个问题

  随着历史中基元数量的增加，不同的“历史”按指数级增长。现在对于第$i$个基元来说，历史基元的个数为$i-1$，如果一共有$L$个不同的基元（假设$L$为词汇集的大小），理论上每一个基元都有可能出现在$i-1$个位置中的任意一处，那么$i$基元就有$L^{i-1}$种不同的历史情况。这样的话，我们必须考虑在所有的$L^{i-1}$种不同的历史情况下产生第$i$个基元的概率。那么模型中就有$L^m$个自由参数。$p(w_m|w_1{w}_2\cdots w_{m-1})$。指数级的增长对运算带来的负担是非常大的，如果$L=5000,m=3$，自由参数的数目为1250亿。

1.2 问题的解决方法

  设法减少历史基元的个数，将$w_1\cdots w_{i-1}$映射到等价类$S=(w_1{w}_2\cdots w_{i-1})$，使等价类的数目远远小于原来不同历史基元的数目。则有：
$$p(w_i|w_1\cdots w_{i-1})=p(w_i|S=(w_1{w}_2\cdots w_{i-1}))$$
划分等价类的规则是，将两个历史映射到同一个等价类，当且仅当这两个历史中的最近$n-1$个基元相同，即：
$$\begin{gathered} H_1:w_1{w}_2\cdots \cdots (w_{i-n+1}{w}_{i-n+2}\cdots w_{i-1})w_i\cdots \cdots \\ {H}_2:v_1{v}_2\cdots \cdots (v_{k-n+1}{v}_{k-n+2}\cdots v_{k-1})v_k\cdots \cdots \end{gathered}$$
对于上面两个串中的$w_i$和$v_k$，它们的历史最近的$n-1$个基元，也就是括号括起来的那部分，如果这些基元相同，则$w_i$和$v_k$的历史就可以映射到同一个等价类$S(w_1\cdots w_{i-1})=S(w_k\cdots w_{k-1})$。换句话说，这么做的目的就是让一个基元$w_i$的概率只和其最近的$n-1$个历史有关，这样便大大地减少了历史基元的数量。

1.3 n-gram

  在上述情况下的语言模型就称为n元文法/语法模型（n-gram model）。当然，$n$不能取太大，否则历史基元的数量一样很多。一般都用4或5元，效果好。$n$取不同值有一些特别的叫法：

• $n=1$时，也就是说第$i$位上的基元$w_i$独立于历史，一元文法也被写为uni-gram或monogram；
• $n=2$时，2-gram（bi-gram）被称为1阶马尔可夫链；
• $n=3$时，3-gram（tri-gram）被称为2阶马尔可夫链。

以此类推。

  n-gram实际上就是$n$个临近词构成的一个$n$元词组，或称词序列，例如：Today is Tuesday.

• bi-grams就是：Today is, is Tuesday, Tuesday.
• tri-grams就是：Today is Tuesday, is Tuesday.

为了保证条件概率在$i=1$时有意义，同时为了保证句子内所有字符串的概率和为1，即${\sum }_{s}p(s)=1$，可以在句子首尾两端增加两个标志：<BOS>$w_1{w}_2\cdots w_m$<EOS>。不失一般性，对于$n>2$的n-gram，$p(s)$可以分解为：
$$p(s)=\prod _{i=1}^{m+1}p(w_i|w_{i-n+1}^{i-1})$$
其中$w_i^j$表示词序列$w_i\cdots w_j$，$w_0$为<BOS>，$w_{m+1}$为<EOS>。举例：
给定句子：John read a book
首先增加标记：<BOS>John read a book <EOS>
Uni-gram：<BOS>,John,read,a,book,<EOS>
Bi-gram：(<BOS>John),(John read),(read a),(a book), (book<EOS>)
Tri-gram：(<BOS>John read),(John read a),(read a book),(a book<EOS>)
拿bi-gram来说，句子的概率为:
$$p(Johnreadabook)=p(John|<BOS>)\ast p(read|John)\ast p(a|read)\ast p(book|a)\ast p(<EOS>|book)$$

1.4 n-gram的应用

  1）音字转换问题：给定拼音之后可能的汉字串可能有很多，利用n-gram可以找到概率最大的字串
  2）汉语分词问题：给定汉字串，可以切分的方法很多，利用n-gram可以找到切分后概率最大的切分方法。
  问题是：如何获得n元语法模型？也就是说我用来计算句子概率的那些条件概率怎么来的。

2 参数估计

  参数估计中的两个重要概念：

• 训练预料（training data）：用于建立模型，确定模型参数的已知语料。
• 最大似然估计（maximum likelihood Evaluation, MLE）：用相对频率计算概率的方法。

对于n-gram来说，参数$p(w_i|w_{i-n+1}^{i-1})$可由最大似然估计求得：
$$p(w_i|w_{i-n+1}^{i-1})=f(w_i|w_{i-n+1}^{i-1})=\frac{c(w_{i-n+1}^i)}{{\sum }_{w_i}c(w_{i-n+1}^i)}$$
其中，${\sum }_{w_i}c(w_{i-n+1}^i)$是历史串$w_{i-n+1}^{i-1}$在给定语料中出现的次数，即$c(w_{i-n+1}^{i-1})$，不管$w_i$是什么。$f(w_i|w_{i-n+1}^{i-1})$是在给定$w_{i-n+1}^{i-1}$的条件下$w_i$出现的相对频度，分子为$w_{i-n+1}^{i-1}$与$w_i$同时出现的次数。下面举例说明。

2.1 一个例子

  给定一个训练预料：

"John read Moby Dick" "Mary read a different book" "She read a book by Cher" 我们来看根据bi-gram来求"John read a book"的概率

  根据1.3最后的式子，我们需要计算其中的每一个条件概率：
$$\begin{gathered} p(John|<BOS>)=\frac{c(<BOS>John)}{{\sum }_{w_i}c(<BOS>w_i)}=\frac{1}{3} \\ p(read|John)=\frac{c(Johnread)}{{\sum }_{w_i}c(John{w}_i)}=\frac{1}{1} \\ p(a|read)=\frac{c(reada)}{{\sum }_{w_i}c(read{w}_i)}=\frac{2}{3} \\ p(book|a)=\frac{c(abook)}{{\sum }_{w_i}c(a{w}_i)}=\frac{1}{2} \\ p(<EOS>|book)=\frac{c(book<EOS>)}{{\sum }_{w_i}c(book{w}_i)}=\frac{1}{2} \end{gathered}$$
最后：
$$p(Johnreadabook)=p(John|<BOS>)\ast p(read|John)\ast p(a|read)\ast p(book|a)\ast p(<EOS>|book)\approx 0.06$$
最后这些概率相乘就是句子的概率了。但是现在考虑另外一个句子"Cher read a book"，我们计算$p(Cher|<BOS>)$和$p(read|Cher)$的时候会发现是0，但这个句子怎么看都是很合理的，这就是数据匮乏（稀疏）引起零概率的问题。解决这个问题要使用数据平滑的方法。

3 数据平滑

  数据平滑的基本思想是调整最大似然估计的概率值，使零概率增值，使非零概率下调，劫富济贫，消除零概率，改进模型的整体正确率。基本目标是使测试样本的语言模型困惑度越小越好。基本约束：
$$\sum _{w_i}p(w_i|w_1{w}_2\cdots w_{i-1})=1$$

3.1 加1法

  基本思想是每一种情况出现的次数加1，例如对于uni-gram来说，设$w_1,w_2,w_3$三个词的概率分别为$\frac{1}{3},0,\frac{2}{3}$，每个词出现的次数加1后就变为了$\frac{2}{6},\frac{1}{6},\frac{3}{6}$。对于bi-gram则有：
$$p(w_i|w_{i-n+1}^{i-1})=\frac{1+c(w_{i-1}{w}_i)}{{\sum }_{w_i}[1+c(w_{i-1}{w}_i)]}=\frac{1+c(w_{i-1}{w}_i)}{|V|+{\sum }_{w_i}c(w_{i-1}{w}_i)}$$
其中$V$为被考虑预料的词汇量（全部可能的基元数），现在回到上面的例子"Cher read a book"：
$$\begin{gathered} p(Cher|<BOS>)=\frac{1+c(<BOS>Cher)}{|V|+{\sum }_{w_i}c(<BOS>w_i)}=\frac{1+0}{11+3} \\ p(read|Cher)=\frac{1+c(Cherread)}{|V|+{\sum }_{w_i}c(Cher{w}_i)}=\frac{1+0}{11+1} \\ p(a|read)=\frac{1+c(reada)}{|V|+{\sum }_{w_i}c(read{w}_i)}=\frac{1+2}{11+3} \\ p(book|a)=\frac{1+c(abook)}{|V|+{\sum }_{w_i}c(a{w}_i)}=\frac{1+1}{11+2} \\ p(<EOS>|book)=\frac{1+c(book<EOS>)}{|V|+{\sum }_{w_i}c(book{w}_i)}=\frac{1+1}{11+2} \end{gathered}$$
得到概率：
$$p(Cherreadabook)=p(Cher|<BOS>)\ast p(read|Cher)\ast p(a|read)\ast p(book|a)\ast p(<EOS>|book)\approx 0.00003$$
  在实际应用中，最简单的平滑技术之一就是加法平滑方法，这种方法的基本思想是上述bi-gram方法的通用化，不是假设每个n元语法发生的次数比实际统计次数多一次，而是假设它比实际出现情况多发生$\delta$次，$0\le \delta \le 1$，那么就有加法平滑法的通用形式：
$$p_{add}(w_i|w_{i-n+1}^{i-1})=\frac{\delta +c(w_{i-n+1}^i)}{\delta |V|+{\sum }_{w_i}c(w_{i-n+1}^i)}$$

3.2减值法/折扣法（Discounting）

  基本思想是修改训练样本中事件的实际计数，使样本中（实际出现的）不同事件的概率之和小于1，剩余的概率量分配给未见概率。

3.2.1 古德-图灵（Good-Turing）估计法

  Good-Turing估计法是很多平滑技术的核心。假设$N$是原来训练样本数据的大小，$n_r$是在样本中正好出现$r$次的事件的数目（此处事件为n-gram），即出现1次的n-gram有$n_1$个，出现2次的n-gram有$n_2$个，$\cdots$出现$r$次的n-gram有$n_r$个。基本思路是，对于任何一个出现$r$次的$n$元语法，都假设它出现了$r^{\ast }$次，这里：
$$r\ast =(r+1)\frac{n_{r+1}}{n_r}$$
$n_r$是训练预料中恰好出现$r$次的n元语法的数目。要把这个统计数转化为概率，只需要进行归一化处理：对于统计数为$r$的n元语法，其概率为：
$$p_r=\frac{r^{\ast }}{N}$$
其中，$N={\sum }_{r=0}^{\infty }{n}_r{r}^{\ast }$。需要注意的是：
$$N=\sum _{r=0}^{\infty }{n}_r{r}^{\ast }=\sum _{r=0}^{\infty }(r+1)n_{r+1}=\sum _{r=1}^{\infty }{n}_{r}r$$
也就是说，$N$等于这个分布中最初的计数。这样，原样本中所有事件的概率之和为：
$$\sum _{r>0}{n}_r{p}_r=1-\frac{n_1}{N}<1$$
因此，有$\frac{n_1}{N}$的剩余的概率量就可以均分给所有的未见事件(r=0)。
  Good-Turing估计法适用于大词汇集产生的符合多项式分布的大量的观察数据。有关Good-Turing方法的详细推导可以参考论文：on Turing’s Formula for Word Probabilities

3.2.2 Back-off（后备/后退方法，Katz平滑方法）

  当某一事件在样本中出现的频率大于阈值$k$（通常取$k$为0或1）时，运用最大似然估计的减值法来估计其概率；而当时间的出现的频率小于$k$值时，使用低阶的语法模型作为代替高阶语法模型的后备，即(n-1)gram的概率替代n-gram概率，而这种替代需受归一化因子$\alpha$的作用。
  另一种理解就是，对于每个计数$r<0$的n元语法的出现次数减值，把因减值而节省下来的剩余概率根据低阶的(n-1)gram分配给未见事件。

3.2.3 绝对减值法（Absolute discounting）

  基本思想是从每个计数$r$中减去同样的量，剩余的概率量由未见事件均分。设$R$为所有可能事件的数目（当事件为n-gram时，如果统计基元为词，且词汇集的大小为$L$，则$R=L^n$）
  那么，样本出现了$r$次的事件的概率可以由如下公式估计：
p r = { r − b N   r > 0 b ( R − n 0 ) N n 0   r = 0 p_r=

$$\begin{cases} \cfrac{r-b}{N} & \ r>0 \\ \cfrac{b(R-n_0)}{Nn_0} &\ r=0 \end{cases}$$ pr​=⎩⎪⎪⎨⎪⎪⎧​Nr−b​Nn0​b(R−n0​)​​ r>0 r=0​
其中，$n_0$为样本中未出现的事件的数目。$b$为减去的常量，$b\le 1$。$b(R-n_0)/N$是由于减值而产生的概率量。$N$为样本中出现了$r$次的事件总次数：$n_r\ast r$。$b$为自由参数，可以通过留存数据方法求得$b$的上限为：
$$b\le \frac{n_1}{n_1+2n_2}<1$$
详细可以参考论文：Estimating Small Probabilities by Leaving-one-Out.

3.2.4 线性减值法（Linear discounting）

  基本思想是从每个计数$r$中减去与该计数成正比的量（减值函数为线性的），剩余概率量$\alpha$被$n_0$个未见事件均分。
p r = { ( 1 − α ) r N   r > 0 α n 0   r = 0 p_r=

$$\begin{cases} \cfrac{(1-\alpha)r}{N} & \ r>0 \\ \cfrac{\alpha}{n_0} & \ r=0 \\ \end{cases}$$ pr​=⎩⎪⎪⎨⎪⎪⎧​N(1−α)r​n0​α​​ r>0 r=0​
自由参数$\alpha$的优化值为$\frac{n_1}{N}$。
  绝对减值法产生的n-gram通常优于线性减值法。

3.2.5 四种减值法的比较

• Good-Turing：对非0事件按公式削减出现的次数，节留出来的概率均分给0概率事件。
• Katz：对非0事件按Good-Turing法计算减值，节留出来的概率按低阶分布分给0概率事件。
• 绝对减值法：对非0事件无条件削弱某一固定的出现次数值，节留出来的概率均分给0概率事件。
• 线性减值法：对非0事件根据出现次数按比例削减次数值，节留出来的概率均分给0概率事件。

3.3 删除插值法（Deleted interpolation）

  基本思想是用低阶语法估计高阶语法，即当3-gram的值不能从训练数据中准确估计时，用2-gram来替代，同样，当2-gram的值不能从训练语料中准确估计时，可以用1-gram的值来代替。插值公式：
$$p(w_3|w_2{w}_1)={\lambda }_3{p}^{\prime }(w_3|w_1{w}_2)+{\lambda }_2{p}^{\prime }(w_3|w_2)+{\lambda }_1{p}^{\prime }(w_3)$$
其中，${\lambda }_1+{\lambda }_2+{\lambda }_3=1$，他们的确定是将训练语料分为两部分，即从原始语料中删除第一部分作为留存数据。第一部分用于估计$p^{\prime }(w_3|w_1{w}_2),p^{\prime }(w_3|w_2),p^{\prime }(w_3)$，第二部分用于计算${\lambda }_1,{\lambda }_2,{\lambda }_3$：使语言模型对留存数据的困惑度最小。

参考资料：《统计自然语言处理》宗成庆