[我们是这样理解语言的-2]统计语言模型

记得最早学习 语言模型 是在研究生的《 统计自然语言处理 》课上，由哈工大关毅老师主讲，从噪声信道模型切入，到 N-Gram 语言模型的构建、平滑、评价（KL 距离/相对熵、交叉熵、困惑度），接着以音字转换系统（即拼音输入法）为应用实践，最终还引出 Markov 模型和最大熵模型。

后来又接触到前腾讯副总裁，现 Goolge 研究员吴军撰写的《 数学之美 》， 微软拼音输入法团队博客 （微软拼音输入法最初由哈工大王晓龙、关毅等老师完成），逐渐领悟到语言模型，尤其是统计语言模型在众多领域中发挥着重要作用，如下：

• 中文分词： P(已/ 结婚/ 的/ 和/ 尚未/ 结婚/ 的/ 青年 | 已结婚的和尚未结婚的青年) > P(已/ 结婚/ 的/ 和尚/ 未/ 结婚/ 的/ 青年 | 已结婚的和尚未结婚的青年)
• 机器翻译： P( high  winds tonite | 今晚有大风) > P( large  winds tonite | 今晚有大风)
• 拼写纠错/Query 改写 ：P(about fifteen  minutes  from) > P(about fifteen  minuets  from)
• 语音识别 ：P(I saw a van) >> P(eyes awe of an)
• 音字转换 ：P( 机器 翻译 及其 应用 激起 了人们 极其 浓厚的学习兴趣 | ji qi fan yi ji qi ying yong ji qi le ren men ji qi nong hou de xue xi xing qu) > P( 机器 翻译 机器 应用 激起 了人们 极其 浓厚的学习兴趣 | ji qi fan yi ji qi ying yong ji qi le ren men ji qi nong hou de xue xi xing qu)
• 自动文摘 、问答系统 、 OCR、… …

2011 年刚加入腾讯时，完成的第一个项目是在线广告系统中的 Keyword Extraction，曾尝试对 query log、bidterm、广告创意等建立统计语言模型，计算 Candidate Keyword 的生成概率，作为排序阶段的重要特征之一。

接下来，我们不妨一起看下语言模型，尤其是 N-Gram 语言模型的数学表示、效果评估、模型平滑及模型训练（尤其是分布式），为我们后续介绍神经网络语言模型和中文分词技术打个好基础。

语言模型介绍

以上语言模型的各种应用场景可以形式化统一表示如下：

$p(S)=p(w_1,w_2,…,w_n)=/prod_{i=1}^{n} p(w_i|w_1,w_2,…,w_{i-1})$

$p(S)$  就是语言模型，即用来计算一个句子 $S$ 概率的模型。

那么，如何计算 $p(w_i|w_1,w_2,…,w_{i-1})$   呢？最简单、直接的方法是计数后做除法，即最大似然估计（Maximum Likelihood Estimate），如下：

$p(w_i|w_1,w_2,…,w_{i-1})=/frac {count(w_1,w_2,…,w_{i-1},w_i)} {count(w_1,w_2,…,w_{i-1})}$ 

其中， $count(w_1,w_2,…,w_{i-1},w_i)$ 表示词序列$(w_1,w_2,…,w_{i-1},w_i)$   在语料库中出现的频率。这里面临两个重要的问题：数据稀疏严重和参数空间过大，导致无法实用。

实际中，我们一般较常使用的是 N 元语法模型（N-Gram），它采用了马尔科夫假设（ Markov Assumption ），即认为语言中每个单词只与其前面长度 N-1 的上下文有关。

• 假设下一个词的出现依赖它前面的一个词，即 bigram，则有：

$p(S)=p(w_1) p(w_2|w_1) p(w_3|w_1,w_2)…p(w_n|w_1,w_2,…,w_{n-1}) //=p(w_1)p(w_2|w_1)p(w_3|w_2)…p(w_n|w_{n-1})$

• 假设下一个词的出现依赖它前面的两个词，即 trigram，则有：

$p(S)=p(w_1) p(w_2|w_1) p(w_3|w_1,w_2)…p(w_n|w_1,w_2,…,w_{n-1}) //=p(w_1)p(w_2|w_1)p(w_3|w_1,w_2)…p(w_n|w_{n-2},w_{n-1})$

那么，我们在面临实际问题时，如何选择依赖词的个数，即 N 呢？

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

理论上，n 越大越好，经验上，trigram 用的最多，尽管如此，原则上， 能用 bigram 解决，绝不使用 trigram。 four-gram 及以上往往只是用于理论研究，实际应用中很少有人使用。

从本质上说，这种统计语言模型描述的是有限状态的正则文法语言，而自然语言是不确定性语言，因此与真实语言差异较大，表达能力有限，尤其无法较好的处理长距离依赖语言现象。但是，其抓住了自然语言中的局部性约束（Local Constrain）性质，因此该模型在实际应用中取得了较大的成功。

语言模型训练

通常，通过计算最大似然估计（Maximum Likelihood Estimate）构造语言模型，这是对训练数据的最佳估计，如 bigram 公式如下：

$p(w_i|w_{i-1}) = /frac {count(w_{i-1}, w_i)} {count(w_{i-1})}$

如给定句子集“<s> I am Sam </s>

<s> Sam I am </s>

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

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

$count(w_i)$ 如下:

$count(w_{i-1}, w_i)$  如下:

则 bigram 为：

那么，句子“ <s> I want chinese food </s> ”的概率为：

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

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

推荐开源语言模型工具：

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

推荐开源 n-gram 数据集：

• Google Web1T5-gram（ http://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html ）

Total number of tokens: 1,306,807,412,486

Total number of sentences: 150,727,365,731

Total number of unigrams: 95,998,281

Total number of bigrams: 646,439,858

Total number of trigrams: 1,312,972,925

Total number of fourgrams: 1,396,154,236

Total number of fivegrams: 1,149,361,413

Total number of n-grams: 4,600,926,713

• Google Book N-grams（ http://books.google.com/ngrams/ ）
• Chinese Web 5-gram（http://www.ldc.upenn.edu/Catalog/catalogEntry.jsp?catalogId=LDC2010T06）

语言模型效果评估

语言模型构造完成后，如何确定其好坏呢？目前主要有两种评价方法：

• 实用方法：通过查看该模型在实际应用（如拼写检查、机器翻译）中的表现来评价，优点是直观、实用，缺点是缺乏针对性、不够客观；
• 理论方法：迷惑度/困惑度/混乱度（preplexity），其基本思想是给测试集赋予较高概率值的语言模型较好，公式如下：

由公式可知，迷惑度越小，句子概率越大，语言模型越好。使用《华尔街日报》，训练数据规模为38million words，构造 n-gram 语言模型，测试集规模为 1.5million words，迷惑度如下表所示：

数据稀疏与平滑技术

大规模数据统计方法与有限的训练语料之间必然产生数据稀疏问题，导致零概率问题，符合经典的 zip’f 定律。如 IBM, Brown：366M 英语语料训练 trigram，在测试语料中，有14.7% 的 trigram 和 2.2% 的bigram 在训练语料中未出现。

数据稀疏问题定义：“The problem of data sparseness, also known as the zero-frequency problem arises when analyses contain configurations that never occurred in the training corpus.  Then it is not possible to estimate probabilities from observed frequencies, and some other estimation scheme that can generalize (that configurations) from the training data has to be used. —— Dagan”。

人们为理论模型实用化而进行了众多尝试与努力，诞生了一系列经典的平滑技术，它们的基本思想是“降低已出现 n-gram 的条件概率分布，以使未出现的 n-gram 条件概率分布非零”，且经数据平滑后一定保证概率和为1，详细如下：

• Add-one（Laplace） Smoothing

加一平滑法，又称拉普拉斯定律，其保证每个 n-gram 在训练语料中至少出现 1次，以 bigram 为例，公式如下：

其中，V 是所有 bigram 的个数。

承接上一节给的例子，经 Add-one Smoothing 后， $c(w_{i-1}, w_i)$ 如下所示：

则 bigram 为：

在$V >> c(w_i)$时，即训练语料库中绝大部分 n-gram 未出现的情况（一般都是如此），Add-one Smoothing后有些“喧宾夺主”的现象，效果不佳。

那么，可以对该方法扩展以缓解此问题，如 add-δ smoothing (Lidstone, 1920; Jeffreys, 1948)。δ 可以是一个小于 1 的数，但是 δ 如何确定呢？也是一个问题。

• Good-Turing Smoothing

其基本思想是利用频率的类别信息对频率进行平滑。如下图所示：

其中，$N_c$表示出现次数为 c 的 n-gram 的个数。调整出现频率为 c 的 n-gram 频率为 $c^{*}$：

但是，对于较大的 c，可能出现$N_{c+1}=0$ 或者 $N_c > N_{c+1}$ 的情况，反而使得模型质量变差，如下图所示：

直接的改进策略就是“对出现次数超过某个阈值的gram 不进行平滑，阈值一般取8~10，其他方法请参见“ Simple Good-Turing ”。

实际中，很少单独使用 Good Turing 平滑，而是结合 backoff 平滑算法使用。

• Interpolation  Smoothing

不管是 Add-one，还是 Good Turing 平滑技术，对于未出现的 n-gram 都一视同仁，难免存在不合理性（事件发生概率存在差别），所以这里再介绍一种线性插值平滑技术，其基本思想是将高阶模型和低阶模型作线性组合，利用低元 n-gram 模型对高元 n-gram 模型进行线性插值。因为在没有足够的数据对高元 n-gram 模型进行概率估计时，低元 n-gram 模型通常可以提供有用的信息。公式如下（下方为上下文相关的扩展表示）：

$/lambda s$可以通过 EM 算法来估计，具体步骤如下：

• 首先，确定三种数据：Training data、Held-out data 和Test data；

• 然后，根据 Training data 构造初始的语言模型，并确定初始的$/lambda s$（如均为1）；

• 最后，基于 EM 算法迭代地优化$/lambda s$ ，使得 Held-out data 概率（如下式）最大化。

• Katz Backoff

其基本思想是如果 n-gram 出现频率为 0，就 backoff 到(n-1)-gram 近似求解，如下是所示：

其中，$P^{*}$为折扣概率，而不直接使用 MLE 的概率，比如使用 Good-Turing，这样才能保证 ，$/alpha$是归一化因子，求解公式如下：

• 其他的平滑算法，还有 Absolute discounting，Kneser-Ney Smoothing，Interpolated Kneser-Ney Smoothing 等，在此不再一一详述。
• Web-scale LMs

面对 Google N-gram 语料库，压缩文件大小为 27.9G，解压后 1T 左右，如此庞大的语料资源，使用前一般需要先剪枝（Pruning）处理，缩小规模，如仅使用出现频率大于 threshold 的 n-gram，过滤高阶的 n-gram（如仅使用 n<=3 的资源），基于熵值剪枝，等等。

另外，在存储方面也需要做一些优化，如使用 trie 数据结构存储，借助 bloom filter 辅助查询，把 string 映射为 int 类型处理（基于 huffman 编码、varint 等方法），float/double 转成 varint 或 int 类型（如概率值精确到小数点后 6 位，然后乘 10E6，即可将浮点数转为整数）。

2007 年 Google Inc. 的 Brants et al. 提出了针对大规模 n-gram 的平滑技术——“ Stupid Backoff ”，已成功应用于 Google 翻译 、 语音搜索 和 自动语音识别 等产品中。其 backoff 策略简单粗暴，甚至不保证 n-gram 的概率意义（用 S 代替 P，只说一个相对大小的 Score），公式如下：

数据平滑技术是构造高鲁棒性语言模型的重要手段，且数据平滑的效果与训练语料库的规模有关。训练语料库规模越小，数据平滑的效果越显著；训练语料库规模越大，数据平滑的效果越不显著，甚至可以忽略不计——锦上添花。

语言模型训练实战

n-gram 语言模型的训练流程如下图所示：

以 MLE 为例，可以将模型训练拆分成三个 MapReduce 任务（在此基础上很容易增加平滑功能），如下表所示：

语言模型变种

• Class-based N-gram Model

该方法基于词类建立语言模型，以缓解数据稀疏问题，且可以方便融合部分语法信息。

• Topic-based N-gram Model

该方法将训练集按主题划分成多个子集，并对每个子集分别建立N-gram语言模型，以解决语言模型的主题自适应问题。架构如下：

• Cache-based N-gram Model

该方法利用 cache 缓存前一时刻的信息，以用于计算当前时刻概率，以解决语言模型动态自适应问题。

-People tends to use words as few as possible in the article.

-If a word has been used, it would possibly be used again in the future.

架构如下：

猜测这是目前 QQ、搜狗、谷歌等智能拼音输入法所采用策略，即针对用户个性化输入日志建立基于 cache 的语言模型，用于对通用语言模型输出结果的调权，实现输入法的个性化、智能化。由于动态自适应模块的引入，产品越用越智能，越用越好用，越用越上瘾。

• Skipping N-gram Model & Trigger-based N-gram Model

二者核心思想都是刻画远距离约束关系。

• 指数语言模型：最大熵模型 MaxEnt、最大熵马尔科夫模型 MEMM、条件随机域模型 CRF

传统的 n-gram 语言模型，只是考虑了词形方面的特征，而没有词性以及语义层面上的知识，并且数据稀疏问题严重，经典的平滑技术也都是从统计学角度解决，未考虑语法、语义等语言学作用。

MaxEnt、MEMM、CRF 可以更好的融入多种知识源，刻画语言序列特点，常用于解决序列标注问题。

• 神经网络语言模型（Neural Network Language Model）

神经网络语言模型最早由 Bengio 提出，并进行系统的研究[Bengio, 2000, 2003]。 随着深度学习的发展，神经网络相关研究越来越深入，神经网络语言模型受到学术界和工业界越来越多的关注，成为了自然语言处理领域最热门的话题之一。神经网络语言模型可以看做一种特殊的模型平滑方式。

特别的，在神经网络语言模型有一个副产品—词嵌入（Word Embedding），应用非常广泛。词嵌入源于 Hinton 在 Learning distributed representations of concepts 提出的 Distributed Representation，Bengio[Bengio, 2003] 将其引入到语言模型建模中，提出了神经网络语言模型。