漫谈 Language Model (1): 原理篇

本文是“漫谈 Language Model 系列”中的第 1 篇，参见本系列的其他文章。原本只是想简单地谈一下 Lanugage Model ，而且之前的漫谈 Clustering 系列还没有写完，似乎又起一个系列不太好，但是在脑子里构思了一下，要说的东西好像也不少，放到一起似乎真的有点长了，而且一时半会估计也写不完，所以还是觉得做成一个系列吧。

Language Model 中文就叫做“语言模型”吧，这实际上是一个概率分布模型 $P$ ，对于语言里的每一个字符串 $S$ 给出一个概率 $P(S)$ 。稍微正式一点的定义可以这样说：假设有一个符号的集合 $\{w\}$ ，我们不妨把每一个 $w_i$ 称作一个“单词”，由零个或多个单词连接起来就组成了一个字符串 $S = w_1w_2\cdots w_n$ ，字符串可长可短，例如实际语言中的句子、段落或者文档都可以看作一个字符串。所有合法（例如，通过一些语法约束）的字符串的集合称作一个语言，而一个语言模型就是这个语言里的字符串的概率分布模型。

在上面的非正式的定义中，我使用了“单词”、“字符串”这样的字眼，然而 Language Model 实际上非常通用，任何由一些基础单元组成的序列都可以使用 Language Model 的方法来分析，例如 Speech Recognition 里的音频信号，Bioinformatics 里的基因序列等。其实文本分析的那一套词汇“单词”、“字符串”之类的也是可以代表更通用的意义的。

那么 Language Model 有什么用呢？给出一个字符串的概率，可以用来干什么呢？随便举一些例子：

1. 一篇文档，也许是通过扫描 OCR 识别得到的，或者是部分破译的密文，以及部分损坏了的文档等等，总之有一些地方字词缺失，有一些不同的可能，这个时候就可以用 Language Model 来计算并选择概率最大的那一种。
2. 专门建立特定的 Language Model 也是很常见的，比如，如果把程序看成是一个指令的序列的话，那么可以分别构建两个 Language Model ：$\mathcal{M}_1$ 和 $\mathcal{M}_2$ ，分别代表正常程序和病毒的模型，给定一个程序，只要分别用两个模型计算出对应的概率，比较一下谁大谁小，就可以判断出该程序是不是病毒了。
3. 也有像搜索引擎那样建立很多个 Language Model 的情况，通常搜索引擎在检索时会先通过倒排表等非常高效的手段从海量的数据里找出相关的内容，然后会使用相对复杂但是更精确一些的算法来为这些结果排序（毕竟大部分用户都只会关心第一页甚至只是前几项搜索结果），抛开著名的 PageRank 不说，使用 Language Model 也是一种比较常见的手段。具体做法是每个文档会有一个对应的 Language Model ，在 rank 的时候使用这些 Language Model 来计算 query 的概率，最后按照概率值由大到小排序即可。

这样看来 Lagnuage Model 倒是挺诱人的样子，好像干什么都可以。而这也正是典型的 Generative Model 的特点（Language Model 算是一种 Generative Model），Discrimitive Model 致力于解决一个特定的问题，而 Generative Model 则试图寻求数据的本质，一但成功构造出数据的实际模型，就可以用它来做（几乎）任何事情。不过，一切都建立在能够正确够找出 the true model 的前提下。且不谈在实际实现时会遇到的各种工程上的难题，就算是仅仅从理论上来讲，也是无法给出什么保证的，就现实中的问题，我们构建 Language Model 的方法通常都是提出一个模型假设，然后根据训练数据使用最优化的方法求得模型——一方面，训练数据是有限的；另一方面，模型的复杂度也必须要限制在可以处理的程度内。所以，通过在不同的地方“放水”，我们会得到各种近似的结果。

不过话也说回来，这并不是 Language Model 的错，几乎所有机器学习的算法都有这样的限制。只是想表明前面举的查毒或者 rank 的例子，虽然都是轻描淡写似的，但是其实真正做起来还是很复杂的；而 Language Model 也不是神话，只是解决问题的 yet another way 而已。 :p 幸运的是，许多看起来非常粗糙的近似方法，在某些特定的领域其实能得到不错的结果，最典型的一个例子也许应当属于垃圾邮件过滤领域的“朴素贝叶斯”方法了。

不过，在朴素贝叶斯之前，我们还是先来看看 Language Model 究竟如何来构建。前面说了，一个 Language Model 要给出一个字符串的概率：$P(S) = P(w_1w_2\cdots w_n)$ ，了解一点概率论知识的人应该都知道这个式子可以像这样分解：

\[ \displaystyle \begin{aligned} P(S) & = P(w_1w_2\cdots w_n) \\ & = P(w_n|w_1w_2\cdots w_{n-1})P(w_1w_2\cdots w_{n-1}) \\ & = P(w_n|w_1w_2\cdots w_{n-1})P(w_{n-1}|w_1w_2\cdots w_{n-2})P(w_1w_2\cdots w_{n-2}) \\ & = P(w_1)\prod_{i=2}^n P(w_i|w_1\cdots w_{i-1}) \end{aligned} \]

例如，对于字符串 He eats apple ，我们有 P([He][eats][apple]) = P([He])P([eats]|[He])P([apple]|[He][eats]) ，其中 P([apple]|[He][eats]) 里 [He][eats] 是 [apple] 的上下文（也许称“上文”在这里更加形象一些），同一个单词，在不同的上下文中出现的概率实际上是不一样的，特别是在一个字符串中越靠后的词，它将有越“长”的上下文 。

在构造模型的时候，我们可以通过统计训练数据里各个单词（在各个 context 之下）出现的频率来近似逼近它的概率，问题在这里就会出现了，本身随着 context 长度的增长，可能的情况会爆炸性地增长，训练数据不可能覆盖所有可能的数据，更严重的是，要存储这些频率值所需的空间也是指数增长的。例如，一个语言里只有 10 个单词，如果要记录一个词的长度为 6 的 context ，如果不考虑语法规则之类的限制，允许单词的各种组合的话，那么就是 10⁶ 种情况，于是可以想想规模稍大的语言里会达到什么样的复杂度了。

为了避免这种爆炸性的复杂度增长，有人做了一个很大胆的近似方法：抛弃所有的上下文信息。现在一个单词在不同的地方出现，对于这个模型来说都是同等对待了，我们知道 apple 做主语的概率肯定比做宾语的概率要小（姑且认为是这样吧 ^_^bb），我们也知道 look 作为动词和作为名词的情况应该区别对待的，我们有许多许多的理由来否定这个模型，简直太 Naive 了！没错，就是 Naive ，这种方法的名字就是 Naive Bayes ，中文叫做朴素贝叶斯。

朴素贝叶斯直接抛弃所有上下文信息，这样 $P(w_n|w_1w_2\cdots w_{n-1})=P(w_n)$ ，因此：

\[ \displaystyle \begin{aligned} P(S) & = P(w_1w_2\cdots w_n) \\ & = P(w_1)\prod_{i=2}^n P(w_i|w_1\cdots w_{i-1}) \\ & = \prod_{i=1}^nP(w_i) \end{aligned} \]

这样，这个模型只需要提供所有单词的概率，那么任意复杂的字符串的概率都可以直接分解计算出来，并且单词的概率也更加容易求得，只需要用训练数据中每个单词出现的次数除以总的单词数目即可，并且不需要太多（相对于考虑上下文的情况）的文档就可以训练出比较精确的模型来。

不过，虽然连名字里都带了个 Naive ，然而这种方法在某些地方效果还是相当不错的，例如垃圾邮件过滤。具体步骤是这样的：

1. 我们会有一些训练数据，就是一些垃圾邮件和一些正常邮件。
2. 分别用这两类邮件训练出两个 Language Model ，亦即统计出两类邮件中各个单词出现的频率，进而计算出它的（近似）概率。
3. 对于待分类的文档 d ，根据贝叶斯公式，我们有 P(d)P(spam|d) = P(spam)P(d|spam) 以及 P(d)P(ham|d) = P(ham)P(d|ham) ，这样 P(spam|d) – P(ham|d) 正比于 P(spam)P(d|spam) – P(ham)P(d|ham) 。
   • 其中 P(spam) 和 P(ham) 是先验概率，是两个常量，通常根据 domain specific 的知识估计出来，或者直接设置为 0.5 。
   • 而 P(d|spam) 和 P(d|ham) 就分别是两个 language model 所给出的概率了。展开来就是文档 d 的字符串里的单词分别在两个 language model 里的概率值的乘积。
4. 这样，差值大于零时就可以判断为垃圾邮件，否者则为正常邮件。还可以设置一个阈值，在差值的绝对值小于这个阈值的时候表示无法判断，以降低判断的错误率。

这就是完整的朴素贝叶斯方法。然而，在很多时候，这样的模型还是太简单了，造成了比较大的 bias ，效果并不好。因此有折衷的方法就是考虑一定长度以内的上下文，例如，仅考虑长度为 1 的上下文，亦即每个单词的前一个单词，那么

\[ P(S) = P(w_1)P(w_2|w_1)P(w_3|w_2)\cdots P(w_n|w_{n-1}) \]

另外还有长度为 2 的上下文，这些在 Speech Recognition 以及 Natural Language Processing 里面用得比较多，更长上下文的模型则不那么常见了。对于上下文长度为 2 的模型，我们总是考虑三个连续单词 $w_1w_2w_3$ 组成的元组，称作 trigram ，类似的有 unigram 和 bigram ，以及通用的 n-gram 。

最后要提一下，虽然在英文里按照单词的界限是很明显的，但是对于中文来说，一个“词”的划分却要复杂许多，因此构建 n-gram 也有两种不同的方法，通常根据应用的需要可以直接在“字”的基础上构建 n-gram ；也可以先分词之后以“词”为基本元素构建 n-gram 。这里生成的 n-gram 用于构建 language model ，其实又可以反过来帮助完成分词的任务，在存在多种可能的划分里选择最佳的一种。对于这样一个句子“研究生命起源”，它可能是字符串“研究 生命 起源”或者“研究生 命 起源”，如果我们有一个 Language Model ，那么只需要计算两个字符串的概率，取概率最大的那一个就可以了。