最小熵原理（二）：“当机立断”之词库构建

在本文，我们介绍“套路宝典”第一式——“当机立断”：1、导出平均字信息熵的概念，然后基于最小熵原理推导出互信息公式；2、并且完成词库的无监督构建、给出一元分词模型的信息熵诠释，从而展示有关生成套路、识别套路的基本方法和技巧。

这既是最小熵原理的第一个使用案例，也是整个“套路宝典”的总纲。

你练或者不练，套路就在那里，不增不减。

为什么需要词语 #

从上一篇文章可以看到，假设我们根本不懂中文，那么我们一开始会将中文看成是一系列“字”随机组合的字符串，但是慢慢地我们会发现上下文是有联系的，它并不是“字”的随机组合，它应该是“套路”的随机组合。于是为了减轻我们的记忆成本，我们会去挖掘一些语言的“套路”。第一个“套路”，是相邻的字之间的组合定式，这些组合定式，也就是我们理解的“词”。

平均字信息熵 #

假如有一批语料，我们将它分好词，以词作为中文的单位，那么每个词的信息量是$-\log p_w$，因此我们就可以计算记忆这批语料所要花费的时间为

$$-\sum_{w\in \text{语料}}\log p_w\tag{2.1}$$
这里$w\in \text{语料}$是对语料逐词求和，不用去重。如果不分词，按照字来理解，那么需要的时间为
$$-\sum_{c\in \text{语料}}\log p_c\tag{2.2}$$
根据前一节的理解，分词其实就是为了减轻记忆负担，那么理论上应该有
$$-\sum_{w\in \text{语料}}\log p_w < -\sum_{c\in \text{语料}}\log p_c\tag{2.3}$$
当然，很多词语是重复出现的，因此我们可以把相同项合并：
$$-\sum_{w\in \text{词表}}N_w\log p_w < -\sum_{c\in \text{字表}}N_c\log p_c\tag{2.4}$$
其中$N_w,N_c$分别是在语料中统计得到词和字的频数。对式$(2.4)$两边除以语料的总字数，那么右端就是
$$-\sum_{c\in \text{字表}}\frac{N_c}{\text{总字数}}\log p_c = -\sum_{c\in \text{字表}}p_c \log p_c\tag{2.5}$$
其中$N_c/\text{总字数}=p_c$即为字$c$的频率，所以上式就是每个字的平均信息，而$(2.4)$左端可以变形为
$$\begin{aligned}\mathcal{L} =& -\sum_{w\in \text{词表}}\frac{N_w}{\text{总字数}}\log p_w \\ =& \left(-\sum_{w\in \text{词表}}\frac{N_w}{\text{总词数}}\log p_w\right)\div \left(\frac{\text{总字数}}{\text{总词数}}\right)\\ =&\left(-\sum_{w\in \text{词表}}\frac{N_w}{\text{总词数}}\log p_w\right)\div \left(\frac{\sum\limits_{w\in \text{词表}}N_w l_w}{\text{总词数}}\right)\\ =&\left(-\sum_{w\in \text{词表}}\frac{N_w}{\text{总词数}}\log p_w\right)\div \left(\sum\limits_{w\in \text{词表}}\frac{N_w}{\text{总词数}} l_w\right)\\ =&\frac{\mathcal{H}}{l}\end{aligned}\tag{2.6}$$
其中$N_w/\text{总词数}=p_w$是词$w$的频率，$l_w$是词$w$的字数，所以$\mathcal{H}$是平均每个词的信息量，$l$是每个词的平均字数：
$$\mathcal{H} = -\sum_{w\in\text{词表}} p_w\log p_w,\quad l=\sum_{w\in\text{词表}} p_w l_w\tag{2.7}$$
因此$\mathcal{L}$实际上是按词来记忆时平均每个字的信息量，是我们要比较和优化的终极目标。我们将总的信息量转化为平均到每个字的信息量，是为了得到一个统一的度量标准。

丰富你的词汇量 #

是不是真如期望一样，分词有助于降低了学习难度？我简单统计了一下，对微信公众号的文章做一个基本的分词后，$\mathcal{H}\approx 10.8$比特，每个词平均是1.5个字，也就是$l\approx 1.5$，那么$\mathcal{L}=7.2$比特，这明显小于逐字记忆的9.65比特。这就说明了在中文里边，按词来记忆确实比按字来记忆要轻松。

“分词”这个操作，降低了中文的学习难度，这也是“分词”通常都作为中文NLP的第一步的原因。

简单来想，对语言进行分词之后，我们需要记忆的词表变大了，但是每个句子的长度变短了，整体来说学习难度是降低了。所以这也就不难理解为什么要学好英语，就得去背单词，因为丰富我们的词汇量能降低学习语言的难度。

套路是如何炼成的 #

反过来，我们也可以由$\mathcal{L}$的最小化，来指导我们无监督地把词库构建出来。这就是“套路是如何炼成的”这门课的重点内容了。

套路之行，始于局部 #

首先我们将平均字信息熵$\mathcal{L}$局部化。所谓局部化，是指考察怎样的两个基本元素合并成一个新的元素后，会导致$\mathcal{L}$降低，这样我们就可以逐步合并以完成熵最小化的目标。这里用“基本元素”来描述，是为了将问题一般化，因为字可以合并为词，词可以合并为词组，等等，这个过程是迭代的，迭代过程中“基本元素”是变化的。

“局部化”是接下来大部分内容的基础，其推导过程虽然冗长，但都是比较简单的运算，稍加思考即可弄懂。

假设目前$i$的频数为$N_i$，总频数为$N$，那么可以估算$p_i=N_i/N$，假设$i$的字数为$l_i$，那么就可以算出当前的

$$\mathcal{L}=\frac{\mathcal{H}}{l}=\frac{-\sum\limits_i p_i\log p_i}{\sum\limits_i p_i l_i}\tag{2.8}$$
如果将两个相邻的$a,b$合并成一项呢？假设$(a,b)$的频数为$N_{ab}$，那么在合并前可以估计$p_{ab}=N_{ab}/N$。如果将它们合并为一个“词”来看待，那么总频数实际上是下降了，变为$\tilde{N}=N-N_{ab}$，而$\tilde{N}_a=N_a-N_{ab}$，$\tilde{N}_b = N_b-N_{ab}$，其他频数不变，因此我们就可以重新估计各个频率
$$\begin{aligned}\tilde{p}_{ab}=&\frac{N_{ab}}{\tilde{N}}=\frac{p_{ab}}{1-p_{ab}}\\ \tilde{p}_{a}=&\frac{\tilde{N}_{a}}{\tilde{N}}=\frac{p_a - p_{ab}}{1-p_{ab}},\,\tilde{p}_{b}=\frac{\tilde{N}_{b}}{\tilde{N}}=\frac{p_b - p_{ab}}{1-p_{ab}}\\ \tilde{p}_{i}=&\frac{N_{i}}{\tilde{N}}=\frac{p_i}{1-p_{ab}},\, (i\neq a,b) \end{aligned}\tag{2.9}$$
于是
$$\begin{aligned}\tilde{\mathcal{H}}=&-\frac{1}{1-p_{ab}}\Bigg\{p_{ab}\log\Big(\frac{p_{ab}}{1-p_{ab}}\Big) + \\ &\qquad \sum_{i=a,b}(p_i - p_{ab})\log\Big(\frac{p_i - p_{ab}}{1-p_{ab}}\Big)+\sum_{i\neq a,b} p_i\log \Big(\frac{p_i}{1-p_{ab}}\Big)\Bigg\}\\ =&\frac{1}{1-p_{ab}}(\mathcal{H}-\mathcal{F}_{ab})\end{aligned}\tag{2.10}$$
其中
$$\begin{aligned}\mathcal{F}_{ab}= &p_{ab}\log \frac{p_{ab}}{p_a p_b} -(1-p_{ab})\log(1-p_{ab}) \\ &+ \sum_{i=a,b}(p_i-p_{ab})\log\Big(1-\frac{p_{ab}}{p_i}\Big)\end{aligned}\tag{2.11}$$
而
$$\begin{aligned}\tilde{l}=&\frac{p_{ab}}{1-p_{ab}}(l_a + l_b) + \sum_{i=a,b}\frac{p_i - p_{ab}}{1-p_{ab}}l_i + \sum_{i\neq a,b} \frac{p_i}{1-p_{ab}} l_i\\ =&\frac{l}{1-p_{ab}} \end{aligned}\tag{2.12}$$
因此
$$\frac{\tilde{\mathcal{H}}}{\tilde{l}}-\frac{\mathcal{H}}{l}=-\frac{\mathcal{F}_{ab}}{l}\tag{2.13}$$
我们的目的是让$\tilde{\mathcal{H}}/\tilde{l}$变小，所以很明显，一个好的“套路”应该要使得$\mathcal{F}_{ab} \gg 0$。

简明优美的近似 #

$\mathcal{F}_{ab}$的表达式过于复杂，以至于难以发现出规律来，我们可以做一些近似。$p_{ab} \leq p_a, p_b$总是成立的，而很多时候甚至可以认为$p_{ab}\ll p_a,p_b$，这样一来在使用自然对数时就有

$$\begin{aligned}&\ln(1-p_{ab})\approx -p_{ab}\\ &\ln\Big(1-\frac{p_{ab}}{p_i}\Big)\approx -\frac{p_{ab}}{p_i}\end{aligned}\tag{2.14}$$
因为这个近似的条件是要使用自然对数（$\ln(1+x)\approx x$），所以我们将下面的$\log$全部改为自然对数$\ln$。代入$\mathcal{F}_{ab}$的表达式并去掉$p_{ab}$的二次以上的项，得到
$$\mathcal{F}_{ab}\approx F_{ab}^*=p_{ab} \left(\ln \frac{p_{ab}}{p_{a} p_{b}}-1\right)\tag{2.15}$$
这个指标就比较简明漂亮了，其中$PMI(a, b)=\ln\frac{p_{ab}}{p_{a} p_{b}}$我们称之为点互信息。

利用泰勒级数，可以得到更一般的展开式为
$$\mathcal{F}_{ab} = p_{ab} \left(\ln \frac{p_{ab}}{p_{a} p_{b}}-1\right)+\frac{1}{2}\left(\frac{1}{p_a}+\frac{1}{p_b}-1\right)p_{ab}^2+\dots$$
可见（也可以严格证明）$F_{ab}^*$的近似总是小于$\mathcal{F}_{ab}$的真实值，因此$F_{ab}^* = p_{ab} \left(\ln \frac{p_{ab}}{p_{a} p_{b}}-1\right)\gg 0$其实是$\mathcal{F}_{ab}\gg 0$的一个充分条件。

上面讨论的是两个元素的合并，如果是$k$个基本元素$\boldsymbol{a}=(a_1,\dots,a_k)$的合并，那么同样可以推得

$$\begin{aligned}\mathcal{F}_{\boldsymbol{a}}= &p_{\boldsymbol{a}}\ln \frac{p_{\boldsymbol{a}}}{\prod\limits_{i\in \boldsymbol{a}} p_i} -\big[1-(k-1)p_{\boldsymbol{a}}\big]\ln\big[1-(k-1)p_{\boldsymbol{a}}\big] \\ &\qquad+ \sum_{i\in\boldsymbol{a}}(p_i- p_{\boldsymbol{a}})\ln\Big(1-\frac{ p_{\boldsymbol{a}}}{p_i}\Big)\end{aligned}\tag{2.16}$$
其近似公式为
$$\mathcal{F}_{\boldsymbol{a}}\approx \mathcal{F}_{\boldsymbol{a}}^* = p_{\boldsymbol{a}} \left(\ln \frac{p_{\boldsymbol{a}}}{\prod\limits_{i\in\boldsymbol{a}} p_i}-1\right)\tag{2.17}$$

推导尽，词库现 #

现在我们可以看到，要使得目标让$\tilde{\mathcal{H}}/\tilde{l}$变小，就应该要有$\mathcal{F}_{ab} \gg 0$，而$\mathcal{F}_{ab}$的一个下界近似是$F_{ab}^*$，所以我们可以用$F_{ab}^*\gg 0$来进行确定哪些元素是需要合并，而对应于词库构建的过程，$F_{ab}^*\gg 0$实际上告诉我们哪些字是需要合并成词的。

根据$F_{ab}^*$的特点不难看出，$F_{ab}^* \gg 0$的一个必要的条件是$\ln \frac{p_{ab}}{p_{a} p_{b}} > 1$，也就是说互信息至少要大于1，这个必要条件下，互信息越大越好，$a,b$的共现频率也越大越好，这就告诉我们要从共现频率和互信息两个角度来判断是否要把元素合并。

在词库构建这个事情上，还有一个巧妙的招数，那就是对$F_{ab}^*$的“逆运用”：式$F_{ab}^*$告诉我们满足$\mathcal{F}_{ab}^* \gg 0$时，两个元素就应该合并。那么反过来，$\mathcal{F}_{ab}^*$小于某个$\theta$时，是不是就应该切分呢？（逆向思维，从确定哪些要“合并”变为确定哪些要“切分”，所谓“当机立断”。）这样的话我们只需要用两个元素合并的公式来指导我们对语料进行一个粗糙的切分，然后对切分结果进行统计筛选，就可以得到很多词了。

这样，我们就得到一种简单有效的构建词库的算法：

1、统计：从大量的语料中统计每个字的频率（$p_a,p_b$），以及统计相邻两字的共现频率($p_{ab}$)；

2、切分：分别设定出现频率的阈值$min\_prob$和互信息的阈值$min\_pmi$，然后在语料中将$p_{ab} < min\_prob$或$\ln\frac{p_{ab}}{p_a p_b} < min\_pmi$的邻字切开（“当机立断”，相当于一次粗糙的分词）；

3、截断：经过第2步的切分后，统计各个“准词语”的频率$p_{w'}$，仅保留$p_{w'} > min\_prob$部分；

以前三步得到的词典还是有冗余的，这体现为：直接用这个词典构建一个一元分词模型，那么词典中的有些词永远都不会被分出来，因为那些词可以用它们的子词表示出来，并且子词的概率乘积还大于它本身的概率。比如在实验中，因为“的、主”以及“主、要”的互信息都大于1，所以词库中出现了“的主要”这个“词”，但统计发现$p(\text{的主要}) < p(\text{的})p(\text{主要})$，那么这个词在一元模型分词的时候是不会分出来的，这个“词”放在词库中只会浪费内存，所以要去掉“的主要”这个词，并且把“的主要”的频数加到“的”和“主要”这两个词上面。

因此，根据这个原则，我们可以过滤掉一部分的候选词：

4、去冗：将词典的候选词按字数从多到少排列，然后依次将每个候选词在词库中删除掉，用剩下的词和词频将这个候选词分词，计算原词与子词之间的互信息，根据式$(2.17)$，如果互信息大于1，则恢复这个词，否则保持删除，并且更新切分出来的子词的词频。

“去冗”这一步的作用还是很明显的，可以去掉30%甚至50%以上的“不及格”的候选词，以下就是筛选出来的一部分（100个）：

的研究, 上的, 的一个, 的方法, 是在, 在中国, 的主要, 的一, 性的, 系统的, 是中国, 发展的, 方面的, 的方式, 的社会, 以上的, 传统的, 化的, 我们的, 的功能, 的需要, 的各种, 中国人, 的形成, 问题的, 为一, 物质的, 名的, 产品的, 的数据, 里的, 组织的, 时期的, 来的, 的结构, 的信息, 式的, 好的, 的一些, 的传统, 文化的, 的标准, 的目标, 主要的, 为中国, 和社会, 人们的, 规定的, 的规定, 的支持, 的最大, 在一个, 主义的, 的价值, 所谓的, 国家和, 的主, 的特征, 量的, 能力的, 在中, 世界的, 系统中, 者的, 的空间, 成立的, 的最高, 的方向, 是不, 一般的, 是通过, 建立的, 在他, 的最后, 后来的, 体的, 的重大, 等方面的, 这里的, 力的, 领域的, 人之, 具体的, 的反应, 度的, 明显的, 面的, 的电子, 的一切, 民族的, 的数量, 的发现, 技术和, 早期的, 的发生, 知识的, 是美国, 项目的, 的优势, 在一

可以发现，除了“中国人”这个外，其他确实都是我们认识中的“不及格”的词语。

PS：“去冗”这一步需要一些人工规则来对长词进行降权，因为有限的语料对长词的统计是很不充分的，因此长词的概率估计会偏高。而既然是“人工规则”，那就让读者自由发挥了，这里不明确给出。

难道就这么简单？ #

当然，哪怕是经过上述4步，这个算法看起来还是过于简单，以至于会让人怀疑它的效果。有读者应该会想到，$\ln\frac{p_{ab}}{p_a p_b} < min\_pmi$不意味着$\ln\frac{p_{abc}}{p_a p_b p_c} < min\_pmi$呀，也就是相邻两个字的互信息很小，但三个字的互信息可能就大了，只根据两字的互信息来切分是不是过于武断了？

确实有这样的例子，比如在某些语料中，“共和国”中的“和”、“国”，“林心如”中的“心”、“如”，两个字的互信息是比较小的，但三字的互信息就很大了。然而事实上，落实到中文词库构建这个应用上，这种情况并不多，因为中文跟英文不同，英文基本单位是字母，也就是只有26个，它们两两组合才676个，甚至三三组合也才一万多个，而汉字本身就有数千个，而理论上汉字对（即2-gram）就有数百万个了，所以只需要统计2-gram就能得到相对充分地反映汉字的组合特征。所以如果出现了这种错例，很大可能是因为这些词不是我们输入语料的显著词，说白了，错了就错了呗。

因此我们基本上不必要讨论三个或三个以上元素合并的公式，用上述的邻字的判别算法即可，在很多情景下它都可以满足我们的需求了。如果要对它进行改进的话，都无法避免引入三阶或更高阶的语言模型，并且还可能需要引入动态规划算法，这会大大降低算法效率。也就是说，改进的思路是有的，但改进的代价会有点大。

识别第一种套路 #

现在我们可以找出一些自然语言的“套路”——也就是词语了。接下来的问题是，给我们一句话，如何识别出这句话中的套路呢？而对于“词”这个套路，说白了，就是有了词库和词频后如何分词呢？

一元分词新诠释 #

有了前述讨论，其实就很简单了，自始至终，我们找套路就是为了减轻记忆负担，降低语料总的信息量，而我们有

$$-\sum_{w\in \text{语料}}\ln p_w = -\sum_{w\in \text{句子}\subset \text{语料}}\ln p_w\tag{2.18}$$
也就是最小化总的信息量等价最小化每个句子的信息量。所以对于一个给定的句子，它的最好的分词方案——假设为$w_1,w_2,\dots,w_n$——那么应该使得该句子的总信息量
$$-\sum_{k=1}^n \ln p(w_k)=-\ln\prod_{k=1}^n p(w_k)\tag{2.19}$$
最小，这其实就是一元分词模型——使得每个词的概率乘积最大，但这里我们通过最小熵原理赋予了它新的诠释。

核心的动态规划 #

一元分词模型可以通过动态规划来求解。动态规划是NLP中的核心算法之一，它是求满足马尔可夫假设的图模型的最优路径的方法。

一般的最优路径是一个复杂度很高的问题，然而由于马尔可夫假设的存在，使得这里存在一个高效的算法，效率为$\mathcal{O}(n)$，这个算法称之为动态规划，也称为viterbi算法，是由安德鲁·维特比(Andrew Viterbi)于1967年提出。动态规划的其根本思想是：一条最优路径如果拆分为两部分，那么每一部分都是一条（局部）最优路径。

具体来讲，在最短路径分词中，动态规划就是说：从左往右扫描句子，扫描到当前字时，只保留直到当前字的最优分词结果，以及经过当前字的所有“准最优序列”（防止过早地误切）。

比如，对于句子“中外科学名著”，首先扫描“中”，它就是唯一的分词结果，这个结果被保存下来，经过“中”字的词还有“中外”，因此也要保存下来，也就是说，当扫描到第一个字时，临时变量存的是“中”、“中外”两个候选结果。第二步，扫描“外”字，这时我们知道“中外”可以有“中 / 外”分成两字，或者直接就“中外”成一个词两种选择，当然，后者概率更大，因此“中 / 外”的结果不保留，只保留“中外”，但是，经过“外”的词还有“外科”，那么应当保留“中 / 外科”的可能性，也就是说，扫描到第二字时，所存的就是“中外”、“中 / 外科”两个候选结果。

接下来到“科”字，由于“中外 / 科”的概率没有“中 / 外科”概率那么大，因此到这一步最优的分词方案是“中 / 外科”，但是经过“科”字的词语还有“科学”，因此此时还有保留“中外 / 科学”的可能性，所以扫描到第三字是，所存的就是“中 / 外科”和“中外 / 科学”。依此类推，直到最后一字，就可以成功分出“中外 / 科学 / 名著”。整个过程的原则就是：保留至当前字最优的方案，以及不放过经过当前字的所有词（避免过早误切）。

在此，笔者觉得，动态规划在NLP中的作用是怎么强调都不为过的，不管你面对的是传统机器学习还是深度学习，都必须掌握动态规划算法，不仅要懂得用，还要懂得自己完整写出来（结合Trie树或者AC自动机）。

解码语言之美 #

尽管我们只是初步完成了无监督构建词库这件事情，但含义远不止于此。读者不妨头脑风暴一下，我们前面做的是一件非常神奇的事情：我们并不是人为总结一些机械的规则来构建词库，我们是找到了平均字信息熵这个目标，然后试图最小化它，然后就把词库构建出来了。

这似乎有点“重演文明”的味道？我们像一个天真的孩童，纯粹在没有目的地自娱自乐，最终却成功地解码了语言的奥秘。

做过实验的读者可能又会反驳：你这出来的东西，很多都不是我们认识的“词”呀？笔者认为，只要让模型具有了演化的能力和方向，那么它究竟演化出什么样子的结果来其实是不重要的。就好比分词，我们并不是为了分词而分词，我们分词是为了后面的任务做准备的，既然如此，何必关心分出来的词准不准的？前面都已经说了，分词的目的是为了降低任务难度罢了。我们真正要关心的，是对最后的任务的处理能力。

听起来有点耍无赖，但事实上这才是真正有人工智能的味道——假如一群真正具有智慧的机器人慢慢地从零开始发展文明，凭什么他发展出来的结果要跟我们的一样呢？

当然，分词只是第一步，事实上出现误差的本质原因是因为我们只关心了分词，而没有做更复杂的语言结构和语义分析。我们后面还会试图做更多的工作，推导更多的“套路”，读者将会慢慢发现，我们最后得到的结果确实是跟语言学现象吻合的。

转载到请包括本文地址：https://kexue.fm/archives/5476

更详细的转载事宜请参考：《科学空间FAQ》