/ Chinese Word Segmentation

贝叶斯定理和中文分词

1 前言

1.1 中文分词问题

中文分词(Chinese Word Segmentation) 指的是将一个汉字序列切分成一个个单独的单词,属于自然语言处理的范畴.对于中文搜索引擎而言,分词是必不可少的一个重要环节.在搜索引擎响应用户的搜索请求时,最重要的并不是呈现出所有网页结果(因为数量太过庞大),而是将与用户输入的内容最相关的内容排列在最前,这称为相关度排序.没有分词技术的出现,计算机并不会认识用户输入的句子中哪些是词语,这样搜索引擎也就无法工作.

我们知道,对于英文来说,单词是自然地以空格作为分节符,而中文却并不如此,即使有句子、段落之间的划分,我们还是无法直接找到词语与词语之间的分界符.从历史原因上分析,这是因为古代汉语除了专有名词,词语以单音词居多,并不需要特别的分词书写,而现代汉语中复音词居多,一个字不再等同于一个词.对此直观的感受是,翻译一篇文言文的字数明显多于原文.

1.2 引入:拼写纠正与贝叶斯定理

如今Word等文字处理软件都能够对用户输入不存在的单词进行纠正,比如用户输入了thew,那么他真正表达的可能是the或者they等,对拼写进行纠正就运用了贝叶斯定理.这个问题用形式化的语言描述:记\(h_{i}\)为对用户真正想输入的单词进行的假设(hypothesis),这些假设\(h_1, h_2, \dots, h_n\)都属于一个有限而且离散的空间\(H\)(因为单词的总数是有限的);\(D\)为用户实际输入的单词(观测数据),那么这个问题就变为求

$$
P(h_i|D)
$$

概率中最大的一个.
运用一次贝叶斯公式,可以得到:

$$
P(h_i | D) = \frac{P(h_i) \cdot P(D | h_i)}{P(D)}
$$

对于不同的具体假设\(h_1, h_2, \dots, h_n\),\(P(D)\)都是一样的,因此在比较不同的\(P(h_i | D)\)时可以忽略它,即只需要知道:

$$
P(h_i | D) \propto P(h_i) \cdot P(D | h_i)
$$

这个公式的抽象意义是:对于给定观测数据,一个假设的好坏取决于这个假设本身独立的可能性大小(先验概率, prior)和这个假设生成观测到数据的可能性大小(似然, likelihood)的乘积.具体到thew这个例子上来说,用户实际想输入the的可能性大小取决于the本身在词汇表中被使用的可能性(频繁程度)大小(先验概率)和想输入the却输入成thew的可能性大小(似然)的乘积.

2 贝叶斯定理在分词问题中的应用

2.1 中文分词形式化描述

分词问题形式化的描述是:令\(X\)为字串(句子),\(Y\)为词串(一种特定的分词假设),问题的解即为使得\(P(Y|X)\)最大的\(Y\).使用一次贝叶斯公式:

$$
P(Y | X) \propto P(Y) \cdot P(X | Y)
$$

用自然语言来说就是这种分词方式(词串)的可能性乘以这个词串生成句子的可能性.进一步可以看到:可以近似地将\(P(X | Y)\)看作是恒等于\(1\)的,因为任何一种分词方式都可以精确地生成一个句子。因此只要寻找一种分词方式使得词串的概率最大.

2.2 \(N\)元语言模型与局限

对于一个词串\(W_1, W_2, \dots , W_n\),如何计算其可能性呢?根据联合概率公式展开:

$$
P(W_1, W_2, \dots, W_n) = P(W_1) \cdot P(W_2 | W_1) \cdot \ldots \cdot P(W_n | W_{n - 1}, \dots, W_1)
$$

于是,通过一系列的条件概率(等号右边)的乘积来求整个联合概率.注意到等号右边最后一项,\(W_n\)这个单词依赖于它前\(n - 1\)个单词,称为\(N\)元语言模型(\(N\)-gram).

对于这类问题,有一些缺陷:

  1. 参数空间过大,不可能实用化:
    在依靠概率统计模型中的分词技术是依赖语料库的数据得出分词方式的可能性,然而语料库再大也无法统计出有说服力的\(P(W_n | W_{n - 1}, W_{n - 2}, \dots, W_1)\)值.
  2. 数据稀疏(也称高维诅咒):
    当数据空间维度增加时,空间的体积提高太快而可用数据变得稀疏.通常情况下,为了获得在统计学上正确并且有可靠的结果,用来支撑这一结果所需要的数据量通常随着维数的提高而呈指数级增长.而且,在组织和搜索数据时也有赖于检测对象区域,这些区域中的对象通过相似度属性而形成分组.然而在高维空间中,所有的数据都很稀疏,从很多角度看都不相似,因而平常使用的数据组织策略变得极其低效.

2.3 马尔科夫假设

为了缓解这些缺陷,可以假设句子中一个词的出现仅仅依赖于它前面有限的\(k\)个词[\(k\)一般不超过\(3\),如果仅依赖于前面一个词,就称为\(2\)元语言模型(\(2\)-gram),\(2\)元语言模型也称马尔科夫假设或**“有限地平线”假设**,同理有\(3\)元语言模型(\(3\)-gram) 等].

引入马尔科夫假设后,可以得到:

$$
P(W_1, W_2, \dots, W_n) = P(W_1) \cdot P(W_2 | W_1) \cdot P(W_3 | W_2) \cdot \ldots \cdot P(W_n | W_{n - 1})
$$

这样统计\(P(W_i | W_{i - 1})\)就不再受到数据稀疏问题的困扰了.

如何保证其中任意一个单词出现的概率只受到它前面的\(2\)个或\(3\)个单词的影响呢?别说\(3\)个,有时候一个单词的概率受到上一句话的影响都是绝对可能的.那么为什么这个假设在实际中的表现却不比决策树差呢?有人对此提出了一个理论解释,并且建立了什么时候朴素贝叶斯的效果能够等价于非朴素贝叶斯的充要条件.这个解释的核心就是:有些独立假设在各个分类之间的分布都是均匀的,所以对于似然的相对大小不产生影响;即便不是如此,也有很大的可能性各个独立假设所产生的消极影响或积极影响互相抵消,最终导致结果受到的影响不大.

事实上,统计机器学习方法所统计的东西往往处于相当表层(shallow)的层面,在这个层面机器学习只能看到一些非常表面的现象.越是往表层去,世界就越是繁复多变.从机器学习的角度来说,特征(feature) 就越多,成百上千维度都是可能的.特征一多,数据会变得稀疏,以至于无法使用.而人类的观察水平显然比机器学习的观察水平要更深入一些,为了避免数据稀疏我们不断地发明各种装置(最典型就是显微镜)来帮助我们直接深入到更深层的事物层面去观察更本质的联系,而不是在浅层对表面现象作统计归纳.

2.4 分词案例:朴素贪婪方法与贝叶斯定理的比较

下面通过一个例子来介绍贝叶斯定理与朴素贪婪法分词相比的优点.假设需要分词的句子是“上网站联盟加入我们”.

按照从左到右的贪婪方法分词(即最长匹配机械分词,通过“查字典”得到每次最长能够划分的单词),那么“上网”首先会被划分出来,接着对于剩下的部分“站联盟”,最理想的情况是划分为“站”和“联盟”,最后是“加入”和“我们”.这样的情况下,这个句子就被分词为“上网| 站| 联盟| 加入| 我们”,这显然不是正确的结果.

利用贝叶斯定理,不妨设\(X\)为句子“上网站联盟加入们”,\(Y_i\)为一种分词方案,比如“上 | 网站联盟 | 加入 | 我们”等,需要找到一个\(Y_i\)使得\(P(Y | X)\)最大.假设现在有一个庞大的语料库,包含大量常见单词在文章中的出现次数.那么对于上述贪婪法的分词结果:首先分析“上网”–“站”这一单词对,显然这一对单词对不符合中文的习惯,故其概率为0(通常情况下在统计语言模型中不会设置为0,而是按照平滑的原则设为一个足够小的值),同理,对于“站”–“联盟”也是一样.如果更换一种划分,按照“上| 网站| 联盟”,“上”–“网站”这个词组经常出现,能够在统计文本中找到它的概率,而“网站”–“联盟”也是如此,这样贝叶斯定理就能使得后面这一种更符合中文习惯和直觉的分词方案胜出.

3 优化:动态规划与贝叶斯定理

3.1 时间复杂度分析

下面进一步分析这个问题的具体操作.应用贝叶斯定理后,需要做的就是枚举句子的各种划分,然后在语料库中寻找各划分的统计概率,进而求出在\(2\)元语言模型下概率最大的切分,即最终的分词结果.然而,对于一个长度为\(n\)的句子(即含有\(n\)个汉字),尝试各种不同切分的时间复杂度为\(O(2^n)\)(因为\(n\)个汉字之间有\(n - 1\)个空隙,每个空隙都可以选择分割或者不分割).对于这样一个指数级的时间复杂度,仅32个汉字的划分就需要进行20亿次计算,一般的计算机很难在理想的时间内得出结果.

3.2 建模:动态规划

对这个过程进行观察,一个词串\(Y\)的概率\(P(Y)\)等于分出第一个词first的概率\(P(first)\)乘以剩下的词串remain的概率\(P(remain)\):

$$
P(Y) = P(first) \cdot P(remain)
$$

这个性质对于求解它的子问题remain的划分同样适用,即满足子问题重用性,也就是说可以通过递归解决.进一步看,发现:

$$
P(Y)_{\mathrm{max}} = P(first) \cdot P(remain)_{\mathrm{max}}
$$

也就是说,整个问题的最优解由子问题的最优解构成,满足最优子结构(optimal sub-structure).

满足以上两个性质,整个算法可以使用动态规划(dynamic programming) 建模.

3.3 具体过程以及时间复杂度分析

具体的做法,仍然以“上网站联盟加入我们”为例.在求解子问题“网站联盟加入我们”时,已经得到它的最优解是“网站 | 联盟 | 加入 | 我们”.那么当求解“上网站联盟加入我们”时,如果尝试在“上”和“网站”之间切分,得“上”“网站联盟加入我们”这两块,只需要“上”这一划分的概率.而“网站联盟加入我们”划分的概率最大值已经求解过了,直接返回,和“上”的概率相乘,得到其中一个候选结果(candidate).在这一个递归层面继续枚举,求出概率最大的分词方案(optimal candidate),返回上一层,如此迭代.一般地,动态规划问题都可以通过自底向上(bottom-up) 和记忆化(memoization) 两个策略进行优化,在此不再赘述.特别地,设定最长的单词不会超过\(L\),那么函数递归的效率为\(O(nL)\),加上每一次调用递归函数时,需要进行\(O(L)\)次的切分枚举,所以整个算法的复杂度为\(O(nL^2)\).

如上所述,整个问题的复杂度从指数级降低到了多项式级,算法的效率提高了不少.事实上,这也正是维特比算法(Viterbi algorithm)的实现,用于记录子问题最优解的表叫做维特比表(Viterbi table).

参考文献

[1] 数学之美番外篇:平凡而又神奇的贝叶斯方法,刘未鹏

[2] 情人节浪漫呈献——贝叶斯与中文分词,李志健