【自然语言处理】中文分词技术（二）
1.3 统计分词
随着大规模语料库的建立，统计机器学习方法的研究和发展，基于统计的中文分词算法渐渐成为主流。
其主要思想是把每个词看作是由词的最小单位的各个字组成的，如果相连的字在不同的文本中出现的词数越多，就证明这相连的字很可能就是一个词。因此我们就可以利用字与字相邻出现的频率来反映成词的可靠度，统计语料中相邻共现的各个字的组合的频度，当组合频度高于某一个临界值时，我们便可认为此字组可能会构成一个词语。
基于统计的分词，一般要做如下两步操作：
- 建立统计语言模型。
- 对句子进行单词划分，然后对划分结果进行概率计算，获得概率最大的分词方式。这里就用到了统计学习算法，如隐含马尔可夫（HMM）、条件随机场（CRF）等。
下面针对其中的一些相关技术做简要介绍。
1.3.1 统计语言模型
统计语言模型在信息检索、机器翻译、语音识别中承担着重要的任务。用概率论的专业术语描述如下：
假定 $S$ 表示某一个有意义的句子，由一连串特定顺序排列的词 $\omega$1, $\omega$2, …, $\omega$$n$组成，这里 $n$ 是句子的长度。现在，我们想知道 $S$ 在文本中出现的可能性，也就是数学上所说的 $S$ 的概率 $P(S)$。
既然 $S$ = $\omega$1, $\omega$2, $\cdots$, $\omega$$n$，那么不妨把 $P(S)$ 展开表示：
$$ P(S) = P(w_1, w_2, \cdots, w_n) \quad \quad (1.1)$$
利用条件概率的公式，$S$ 这个序列出现的概率等于每一个词出现的条件概率相乘，于是 $ P(w_1, w_2, \cdots, w_n) $ 可展开为：
$$
P(w_1, w_2, \cdots, w_n)
= P(w_1)·P(w_2|w_1)·P(w_3|w_1, w_2) \cdots P(w_n|w_1, w_2, \cdots, w_{n-1} )\quad (1.2)
$$
其中 $P(w_1)$ 表示第一个词 $w_1$ 出现的概率（更准确的描述是 $P(w_1|< s >)$，即这个词在句子开头条件下的概率）；$P(w_2|w_1)$ 是在已知第一个词的前提下，第二个词出现的概率；以此类推。不难看出，到了词 $w_n$，它的出现概率取决于它前面的所有词。
从计算上看，第一个词的条件概率 $P(w_1)$ 很容易算，第二个词的条件概率 $P(w_2|w_1)$ 也还不太麻烦，第三个词的条件概率 $P(w_3|w_1, w_2)$ 已经非常难算了，因为它涉及到三个变量 $w_1, w_2, w_3$，每个变量的可能性都是一种语言字典的大小。到了最后一个词 $w_n$，条件概率 $P(w_n|w_1, w_2, \cdots, w_{n-1})$ 的可能性太多，无法估算。
19 世纪到 20 世纪初，俄罗斯有个数学家叫马尔可夫（Andrey Markov），他给了个偷懒但还颇为有效的方法，也就是每当遇到这种情况时，就假设任意一个词 $w_i$ 出现的概率只同它前面的词 $w_{i-1}$ 有关，于是问题就变得很简单了。这种假设在数学上称为马尔可夫假设。现在，$S$ 出现的概率就变得简单了：
$$ P(S) = P(w_1)·P(w_2|w_1)·P(w_3|w_2)···P(w_i|w_{i-1})···P(w_n|w_{n-1}) \quad \quad (1.3)$$
这个公式对应的统计语言模型是二元模型（Bigram Model）。这个模型的假设前提是，句子中的每个词只和前面一个词有关，而和更前面的词就无关了，这似乎太简化了，或者说近似得过头了。确实是这样，读者很容易找到一些例子：某个词和前面第二个词有关，比如说 "美丽的花朵"，花朵其实和美丽有关。因此，更普遍的假设是某个词和前面若干个词有关。
假定文本中的每个词 $w_i$ 和前面 $N-1$ 个词有关，而与更前面的词无关，这样当前词 $w_i$ 的概率只取决于前面 $N-1$ 个词 $P(w_{i-N+1}, w_{i-N+2}, ···, w_{i-1})$。因此 $P(w_i|w_1, w_2, ···, w_{i-1} )$ 的计算可简化为：
$$ P(w_i|w_1, w_2, ···, w_{i-1} )\approx P(w_i|w_{i-N+1}, w_{i-N+2}, ···, w_{i-1}) \quad \quad (1.4)$$
公式（1.4）的这种假设被称为 $N-1$ 阶马尔可夫假设，对应的语言模型称为 $N$ 元模型（N-Gram Model）。$N=2$ 的二元模型就是公式（1.3），而 $N=1$ 的一元模型实际上是一个上下文无关的模型，也就是假定当前词出现的概率与前面的词无关，这无疑是完全损失了句中的词序信息，所以一元模型的效果并不理想。而在实际应用中最多的是 $N=3$ 的三元模型，更高阶的模型就很少使用了。
为什么 $N$ 一般取值都这么小呢？这里面主要有两个原因。首先，$N$ 元模型的大小（或者说空间复杂度）几乎是 $N$ 的指数函数，即 $O(|V|^N)$。
这里 $|V|$ 是一种语言词典的词汇量，一般在几万到几十万个。而使用 $N$ 元模型的速度（或者说时间复杂度）也几乎是一个指数函数，即 $O(|V|^{N-1})$。因此，$N$ 不能很大。当 $N$ 从 1 到 2，再从 2 到 3 时，模型的效果上升显著。而当模型从 3 到 4 时，效果的提升就不是很显著了，而资源的耗费增加却非常快，所以，除非是不惜资源为了做到极致，很少有人使用四元以上的模型。Google 的罗塞塔翻译系统和语言搜索系统，使用的是四元模型，该模型存储于 500 台以上的 Google 服务器中。
还有一个问题，是否三元或者四元甚至更高阶的模型就能覆盖所有的语言现象呢？答案显然是否定的。因为在自然语言中，上下文之间的相关性可能跨度非常大，甚至可以从一个段落跨到另一个段落。因此，即使模型的阶数再提高，对这种情况也无可奈何，这就是马尔可夫假设的局限性，这时就要采用其他一些长程的依赖性（Long Distance Dependency）来解决这个问题了。
接下来的问题就是如何估计条件概率 $P(w_i|w_{i-1})$。根据它的定义：
$$ P(w_i|w_{i-1}) = \frac {P(w_{i-1}, w_i)} {P(w_{i-1})} \quad \quad (1.5)$$
而估计联合概率 $P(w_{i-1}, w_i)$ 和边缘概率 $P(w_{i-1})$，现在变得很简单。因为有了大量机读文本，也就是专业人士讲的语料库（Corpus），只要数一数 $w_{i-1}, w_i$ 这对词在统计的文本中前后相邻出现了多少次 $\mbox{#} (w_{i-1}, w_i)$，以及 $w_{i-1}$ 本身在同样的文本中出现了多少次 $\mbox{#}(w_{i-1})$，然后用两个数分别除以语料库的大小 $\mbox{#}$，即可得到这些词或者二元组的相对频度：
$$ f(w_{i-1}, w_i)= \frac {\mbox{#}(w_{i-1}, w_i)} {\mbox{#}} \quad \quad (1.6)$$
$$ f(w_{i-1}) = \frac {\mbox{#}(w_{i-1})} {\mbox{#}} \quad \quad (1.7)$$
根据大数定理，只要统计量足够，相对频度就等于频率，即
$$ P(w_{i-1}, w_i)\approx \frac {\mbox{#}(w_{i-1}, w_i)} {\mbox{#}} \quad \quad (1.8)$$
$$ P(w_{i-1}) \approx \frac {\mbox{#}(w_{i-1})} {\mbox{#}} \quad \quad (1.9)$$
而 $P(w_i|w_{i-1})$ 就是这两个数的比值，再考虑到上面的两个概率有相同的分母，可以约掉，因此
$$ P(w_i|w_{i-1}) \approx \frac {\mbox{#}(w_{i-1}, w_i)} {\mbox{#}(w_{i-1})} \quad \quad (1.10)$$
使用语言模型需要知道模型中所有的条件概率，我们称之为模型的参数。通过对语料的统计，得到这些参数的过程称作模型的训练。比如对于二元模型（1.3），就是拿两个数字，$(w_{i-1}, w_i)$ 在语料中同现的次数 $\mbox{#}(w_{i-1}, w_i)$ 和 $(w_{i-1})$ 在语料中单独出现的次数 $\mbox{#}(w_{i-1})$，计算一下比值即可。但问题是，如果同现的次数 $\mbox{#}(w_{i-1}, w_i)= 0$ 怎么办，是否意味着条件概率 $P(w_i|w_{i-1})=0$？反过来如果 $\mbox{#}(w_{i-1}, w_i)$ 和 $\mbox{#}(w_{i-1})$ 都只出现了一次，是否敢得出 $P(w_i|w_{i-1})=1$ 这样非常绝对的结论？这就涉及到统计的可靠性问题了。
在数理统计中，我们之所以敢于用对采样数据的观察结果来预测概率，是因为有大数定理（Law of Large Numbers）在背后做支持，它的要求是有足够的观测值。
