【专栏】数学之美番外篇：平凡而又神奇的贝叶斯方法（2）

拼写纠正

经典著作《人工智能：现代方法》的作者之一Peter Norvig曾经写过一篇介绍如何写一个拼写检查/纠正器的文章（原文在这里，徐宥的翻译版在这里，这篇文章很深入浅出，强烈建议读一读），里面用到的就是贝叶斯方法，这里我们不打算复述他写的文章，而是简要地将其核心思想介绍一下。

首先，我们需要询问的是：“问题是什么？”

问题是我们看到用户输入了一个不在字典中的单词，我们需要去猜测：“这个家伙到底真正想输入的单词是什么呢？”用刚才我们形式化的语言来叙述就是，我们需要求：

P(我们猜测他想输入的单词|他实际输入的单词)

这个概率。并找出那个使得这个概率最大的猜测单词。显然，我们的猜测未必是唯一的，就像前面举的那个自然语言的歧义性的例子一样；这里，比如用户输入：thew，那么他到底是想输入the，还是想输入thaw？到底哪个猜测可能性更大呢？幸运的是我们可以用贝叶斯公式来直接出它们各自的概率，我们不妨将我们的多个猜测记为h1 h2……（h代表hypothesis），它们都属于一个有限且离散的猜测空间H（单词总共就那么多而已），将用户实际输入的单词记为D（D代表Data，即观测数据），于是：

P(我们的猜测1|他实际输入的单词)

可以抽象地记为：

P(h1|D)

类似地，对于我们的猜测2，则是P(h2|D)。不妨统一记为：

P(h|D)

运用一次贝叶斯公式，我们得到：

P(h|D)=P(h)*P(D|h)/P(D)

对于不同的具体猜测h1 h2 h3……，P(D)都是一样的，所以在比较P(h1|D)和P(h2|D)的时候我们可以忽略这个常数。即我们只需要知道：

P(h|D)∝P(h)*P(D|h)（注：那个符号的意思是“正比例于”，不是无穷大，注意符号右端是有一个小缺口的。）

这个式子的抽象含义是：对于给定观测数据，一个猜测是好是坏，取决于“这个猜测本身独立的可能性大小（先验概率，Prior）”和“这个猜测生成我们观测到的数据的可能性大小”（似然，Likelihood）的乘积。具体到我们的那个thew例子上，含义就是，用户实际是想输入the的可能性大小取决于the本身在词汇表中被使用的可能性（频繁程度）大小（先验概率）和想打the却打成thew的可能性大小（似然）的乘积。

下面的事情就很简单了，对于我们猜测为可能的每个单词计算一下P(h) * P(D | h)这个值，然后取最大的，得到的就是最靠谱的猜测。

一点注记：Norvig的拼写纠正器里面只提取了编辑距离为2以内的所有已知单词。这是为了避免去遍历字典中每个单词计算它们的P(h) * P(D | h)，但这种做法为了节省时间带来了一些误差。但话说回来难道我们人类真的回去遍历每个可能的单词来计算他们的后验概率吗？不可能。实际上，根据认知神经科学的观点，我们首先根据错误的单词做一个bottom-up的关联提取，提取出有可能是实际单词的那些候选单词，这个提取过程就是所谓的基于内容的提取，可以根据错误单词的一些模式片段提取出有限的一组候选，非常快地缩小的搜索空间（比如我输入explaination，单词里面就有充分的信息使得我们的大脑在常数时间内把可能性narrow down到explanation这个单词上，至于具体是根据哪些线索——如音节——来提取，又是如何在生物神经网络中实现这个提取机制的，目前还是一个没有弄清的领域）。然后，我们对这有限的几个猜测做一个top-down的预测，看看到底哪个对于观测数据（即错误单词）的预测效力最好，而如何衡量预测效率则就是用贝叶斯公式里面的那个P(h) * P(D | h)了——虽然我们很可能使用了一些启发法来简化计算。后面我们还会提到这样的bottom-up的关联提取。

（待续；此文的修订版已收录《暗时间》一书，由电子工业出版社2011年8月出版。作者于2009年7月获得南京大学计算机系硕士学位，现在微软亚洲研究院创新工程中心从事软件研发工程师工作。）