31 Oct 2017

如何使用N-gram语言模型来进行篇章单元分类？

一、 什么是N-gram语言模型(Language Model)

N-gram是自然语言处理（NLP）中一个非常重要的概念，通常在NLP中，人们基于一定的语料库，可以利用N-gram来做以下几类事情：

  1. 预计或者评估一个句子是否合理；
  2. 评估两个字符串之间的差异程度，这也是模糊匹配中常用的一种手段；
  3. 语音识别；
  4. 机器翻译；
  5. 文本分类。

我们主要使用N-gram语言模型来进行文本分类。假定S表示某个有意义的句子，由一串特定顺序排列的词w1,w2,w3,..,wn组成，n是句子的长度。想知道S在文本中(语料库)出现的可能性，也就是数学上所说的概率P(S)：

P(S)=P(w1,w2,w3,..,wn)=P(W1)P(W2|W1)P(W3|W1,W2)..P(Wn|W1,W2,..,Wn−1)

由于要计算wi出现的概率，就要去统计前i-1词出现的情况，假设词库中有n个词，就有n^(i-1)种可能，这样每增加一个单词，模型的计算成本都指数倍的增长。于是，我们做一个简单的马尔科夫假设（Markov Assumption）来简化问题：假设第i个词出现的概率只与前面的N-1个词有关，这就是N-gram语言模型的由来。比如计算的概率时候，我们假设单词wi出现的概率只与前面出现的N个词有关：

  • 当N=1的时候，为一元模型（Unigram model）：P(S)=P(w1,w2,w3,..,wn)=P(W1)*P(W2)*…*P(Wn)
  • 当N=2的时候，叫二元模型（Bigram model）：P(S)=P(w1,w2,w3,..,wn)=P(W1|start)*P(W2|W1)*…*P(Wn|Wn-1)
  • 当N=3的时候，叫 三元模型（trigram model）：P(S)=P(w1,w2,w3,..,wn)=P(W2|start,W1)*P(W3|W1,W2)*…*P(Wn|Wn-1,Wn-2)

也许你已经意识到，N是一个超参数，在面临实际问题时，我们应该如何选择依赖词的个数？

  • 更大的n：对下一个词出现的约束信息更多，具有更大的辨别力；
  • 更小的n：在训练语料库中出现的次数更多，具有更可靠的统计信息，具有更高的可靠性。

理论上，n越大越好，但在经验上看，trigram用的最多，尽管如此，原则上，能用bigram解决，绝不使用trigram。

对于每一个概率计算我们使用最大似然估计法（Maximum Likelihood Estimate）来做：

p(w1|wi-1) = count(wi-1, wi) / count(wi-1)

如给定句子集：

<s> I am Sam </s>

<s> Sam I am </s>

<s> I do not like green eggs and ham </s>

部分bigram语言模型如下所示：

bigram语言模型

二、 基于N-gram模型的篇章单元分类器

NLP领域大牛Dan Jurafsky 和 Chirs Manning在他们的斯坦福大学自然语言处理课程中，他们用训练集的9222个句子来统计的部分二元单词分布情况：

表1 部分二元单词分布情况表

部分二元单词分布情况表

第一行，第二列表示给定前一个词是 “i” 时，当前词为“want”的情况一共出现了827次。据此，我们便可以算得相应的频率分布表如下：

表2 频率分布表

频率分布表

因为我们从表1中知道 “i” 一共出现了2533次，而其后出现 “want” 的情况一共有827次，所以P(want|i)=827/2533≈0.33。

假设我们现在有一个标记为背景（Background）语料库（由于现在只有两句，所以我们就不画上面的单词分布情况表以及频率分布表了）如下，其中<BG>是句首标记，</BG>是句尾标记：

<BG>yes no no no no yes</BG>

<BG>no no no yes yes yes no</BG>

下面我们的任务是来评估如下这个句子属于“背景”这个篇章单元类别的概率：

s=<BG>yes no no yes</BG>（先假设这句话的所属篇章单元类别为“背景”，这样我们可以提取第一个单词和最后一个单词的与“背景”相关的特征）

我们来演示利用trigram模型来计算概率的结果：

P(yes|<BG>) = 1/2

P(no|<BG>,yes) = 1

P(no|yes,no) = 1/2

P(yes|no,no) = 2/5

P(</BG>|no,yes) = 1/2

P(s) = 1/2*1*1/2*2/5*1/2 = 0.05，即句子s属于“背景”的概率为0.05。

为了避免数据溢出、提高性能，通常会使用取log后使用加法运算替代乘法运算。

log(p1*p2*p3*p4) = log(p1) + log(p2) + log(p3) + log(p4)

那么我们如何用N-gram来做篇章单元的分类器呢？其实很简单了，只要根据每个类别的语料库训练各自的语言模型，也就是上面的频率分布表，实质上就是每一个篇章单元的类别都有一个概率分布，当新来一个篇章单元的时候，只要根据各自的语言模型，计算出每个语言模型下这个篇章单元的发生概率，篇章单元在哪个模型的概率大，这篇文本就属于哪个类别了。

三、 工具与数据集

推荐开源语言模型工具：

  1. SRILM（http://www.speech.sri.com/projects/srilm/）
  2. IRSTLM（http://hlt.fbk.eu/en/irstlm）
  3. MITLM（http://code.google.com/p/mitlm/）
  4. BerkeleyLM（http://code.google.com/p/berkeleylm/）

推荐开源n-gram数据集：

  1. Google Web1T5-gram（http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html）
  2. Google Book N-grams（http://books.google.com/ngrams/）
  3. Chinese Web 5-gram（http://www.ldc.upenn.edu/Catalog/catalogEntry.jsp?catalogId=LDC2010T06）

四、 参考文献

  1. 斯坦福大学自然语言处理第四课“语言模型（Language Modeling）：http://52opencourse.com/111/%E6%96%AF%E5%9D%A6%E7%A6%8F%E5%A4%A7%E5%AD%A6%E8%87%AA%E7%84%B6%E8%AF%AD%E8%A8%80%E5%A4%84%E7%90%86%E7%AC%AC%E5%9B%9B%E8%AF%BE-%E8%AF%AD%E8%A8%80%E6%A8%A1%E5%9E%8B%EF%BC%88language-modeling%EF%BC%89
  2. N-gram语言模型文本分类器：http://blog.csdn.net/shiwei1003462571/article/details/43482881
  3. Ngram语言模型：https://flystarhe.github.io/2016/08/16/ngram/
Tags:
Stats: