数学之美番外篇平凡而又神奇的贝叶斯方法

数学之美番外篇平凡而又神奇的贝叶斯方法BY刘未鹏–SEPTEMBER21,2008POSTEDIN:数学,机器学习与人工智能,计算机科学概率论只不过是把常识用数学公式表达了出来。——拉普拉斯记得读本科的时候，最喜欢到城里的计算机书店里面去闲逛，一逛就是好几个小时；有一次，在书店看到一本书，名叫贝叶斯方法。当时数学系的课程还没有学到概率统计。我心想，一个方法能够专门写出一本书来，肯定很牛逼。后来，我发现当初的那个朴素归纳推理成立了——这果然是个牛逼的方法。——题记目录0.前言1.历史1.1一个例子：自然语言的二义性1.2贝叶斯公式2.拼写纠正3.模型比较与贝叶斯奥卡姆剃刀3.1再访拼写纠正3.2模型比较理论（ModelComparasion）与贝叶斯奥卡姆剃刀（BayesianOccam’sRazor）3.3最小描述长度原则3.4最优贝叶斯推理4.无处不在的贝叶斯4.1中文分词4.2统计机器翻译4.3贝叶斯图像识别，AnalysisbySynthesis4.4EM算法与基于模型的聚类4.5最大似然与最小二乘5.朴素贝叶斯方法（又名“愚蠢者的贝叶斯（idiot’sbayes）”）5.1垃圾邮件过滤器5.2为什么朴素贝叶斯方法令人诧异地好——一个理论解释6.层级贝叶斯模型6.1隐马可夫模型（HMM）7.贝叶斯网络0.前言这是一篇关于贝叶斯方法的科普文，我会尽量少用公式，多用平白的语言叙述，多举实际例子。更严格的公式和计算我会在相应的地方注明参考资料。贝叶斯方法被证明是非常general且强大的推理框架，文中你会看到很多有趣的应用。1.历史托马斯·贝叶斯（ThomasBayes）同学的详细生平在这里。以下摘一段wikipedia上的简介：所谓的贝叶斯方法源于他生前为解决一个“逆概”问题写的一篇文章，而这篇文章是在他死后才由他的一位朋友发表出来的。在贝叶斯写这篇文章之前，人们已经能够计算“正向概率”，如“假设袋子里面有N个白球，M个黑球，你伸手进去摸一把，摸出黑球的概率是多大”。而一个自然而然的问题是反过来：“如果我们事先并不知道袋子里面黑白球的比例，而是闭着眼睛摸出一个（或好几个）球，观察这些取出来的球的颜色之后，那么我们可以就此对袋子里面的黑白球的比例作出什么样的推测”。这个问题，就是所谓的逆概问题。实际上，贝叶斯当时的论文只是对这个问题的一个直接的求解尝试，并不清楚他当时是不是已经意识到这里面包含着的深刻的思想。然而后来，贝叶斯方法席卷了概率论，并将应用延伸到各个问题领域，所有需要作出概率预测的地方都可以见到贝叶斯方法的影子，特别地，贝叶斯是机器学习的核心方法之一。这背后的深刻原因在于，现实世界本身就是不确定的，人类的观察能力是有局限性的（否则有很大一部分科学就没有必要做了——设想我们能够直接观察到电子的运行，还需要对原子模型争吵不休吗？），我们日常所观察到的只是事物表面上的结果，沿用刚才那个袋子里面取球的比方，我们往往只能知道从里面取出来的球是什么颜色，而并不能直接看到袋子里面实际的情况。这个时候，我们就需要提供一个猜测（hypothesis，更为严格的说法是“假设”，这里用“猜测”更通俗易懂一点），所谓猜测，当然就是不确定的（很可能有好多种乃至无数种猜测都能满足目前的观测），但也绝对不是两眼一抹黑瞎蒙——具体地说，我们需要做两件事情：1.算出各种不同猜测的可能性大小。2.算出最靠谱的猜测是什么。第一个就是计算特定猜测的后验概率，对于连续的猜测空间则是计算猜测的概率密度函数。第二个则是所谓的模型比较，模型比较如果不考虑先验概率的话就是最大似然方法。1.1一个例子：自然语言的二义性下面举一个自然语言的不确定性的例子。当你看到这句话：Thegirlsawtheboywithatelescope.你对这句话的含义有什么猜测？平常人肯定会说：那个女孩拿望远镜看见了那个男孩（即你对这个句子背后的实际语法结构的猜测是：Thegirlsaw-with-a-telescopetheboy）。然而，仔细一想，你会发现这个句子完全可以解释成：那个女孩看见了那个拿着望远镜的男孩（即：Thegirlsawthe-boy-with-a-telescope）。那为什么平常生活中我们每个人都能够迅速地对这种二义性进行消解呢？这背后到底隐藏着什么样的思维法则？我们留到后面解释。1.2贝叶斯公式贝叶斯公式是怎么来的？我们还是使用wikipedia上的一个例子：一所学校里面有60%的男生，40%的女生。男生总是穿长裤，女生则一半穿长裤一半穿裙子。有了这些信息之后我们可以容易地计算“随机选取一个学生，他（她）穿长裤的概率和穿裙子的概率是多大”，这个就是前面说的“正向概率”的计算。然而，假设你走在校园中，迎面走来一个穿长裤的学生（很不幸的是你高度近似，你只看得见他（她）穿的是否长裤，而无法确定他（她）的性别），你能够推断出他（她）是男生的概率是多大吗？一些认知科学的研究表明（《决策与判断》以及《RationalityforMortals》第12章：小孩也可以解决贝叶斯问题），我们对形式化的贝叶斯问题不擅长，但对于以频率形式呈现的等价问题却很擅长。在这里，我们不妨把问题重新叙述成：你在校园里面随机游走，遇到了N个穿长裤的人（仍然假设你无法直接观察到他们的性别），问这N个人里面有多少个女生多少个男生。你说，这还不简单：算出学校里面有多少穿长裤的，然后在这些人里面再算出有多少女生，不就行了？我们来算一算：假设学校里面人的总数是U个。60%的男生都穿长裤，于是我们得到了U*P(Boy)*P(Pants|Boy)个穿长裤的（男生）（其中P(Boy)是男生的概率=60%，这里可以简单的理解为男生的比例；P(Pants|Boy)是条件概率，即在Boy这个条件下穿长裤的概率是多大，这里是100%，因为所有男生都穿长裤）。40%的女生里面又有一半（50%）是穿长裤的，于是我们又得到了U*P(Girl)*P(Pants|Girl)个穿长裤的（女生）。加起来一共是U*P(Boy)*P(Pants|Boy)+U*P(Girl)*P(Pants|Girl)个穿长裤的，其中有U*P(Girl)*P(Pants|Girl)个女生。两者一比就是你要求的答案。下面我们把这个答案形式化一下：我们要求的是P(Girl|Pants)（穿长裤的人里面有多少女生），我们计算的结果是U*P(Girl)*P(Pants|Girl)/[U*P(Boy)*P(Pants|Boy)+U*P(Girl)*P(Pants|Girl)]。容易发现这里校园内人的总数是无关的，可以消去。于是得到P(Girl|Pants)=P(Girl)*P(Pants|Girl)/[P(Boy)*P(Pants|Boy)+P(Girl)*P(Pants|Girl)]注意，如果把上式收缩起来，分母其实就是P(Pants)，分子其实就是P(Pants,Girl)。而这个比例很自然地就读作：在穿长裤的人（P(Pants)）里面有多少（穿长裤）的女孩（P(Pants,Girl)）。上式中的Pants和Boy/Girl可以指代一切东西，所以其一般形式就是：P(B|A)=P(A|B)*P(B)/[P(A|B)*P(B)+P(A|~B)*P(~B)]收缩起来就是：P(B|A)=P(AB)/P(A)其实这个就等于：P(B|A)*P(A)=P(AB)难怪拉普拉斯说概率论只是把常识用数学公式表达了出来。然而，后面我们会逐渐发现，看似这么平凡的贝叶斯公式，背后却隐含着非常深刻的原理。2.拼写纠正经典著作《人工智能：现代方法》的作者之一PeterNorvig曾经写过一篇介绍如何写一个拼写检查/纠正器的文章（原文在这里，徐宥的翻译版在这里，这篇文章很深入浅出，强烈建议读一读），里面用到的就是贝叶斯方法，这里我们不打算复述他写的文章，而是简要地将其核心思想介绍一下。首先，我们需要询问的是：“问题是什么？”问题是我们看到用户输入了一个不在字典中的单词，我们需要去猜测：“这个家伙到底真正想输入的单词是什么呢？”用刚才我们形式化的语言来叙述就是，我们需要求：P(我们猜测他想输入的单词|他实际输入的单词)这个概率。并找出那个使得这个概率最大的猜测单词。显然，我们的猜测未必是唯一的，就像前面举的那个自然语言的歧义性的例子一样；这里，比如用户输入：thew，那么他到底是想输入the，还是想输入thaw？到底哪个猜测可能性更大呢？幸运的是我们可以用贝叶斯公式来直接出它们各自的概率，我们不妨将我们的多个猜测记为h1h2..（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)对于不同的具体猜测h1h2h3..，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，单词里面就有充分的信息使得我们的大脑在常数时间内把可能性narrowdown到explanation这个单词上，至于具体是根据哪些线索——如音节——来提取，又是如何在生物神经网络中实现这个提取机制的，目前还是一个没有弄清的领域）。然后，我们对这有限的几个猜测做一个top-down的预测，看看到底哪个对于观测数据（即错误单词）的预测效力最好，而如何衡量预测效率则就是用贝叶斯公式里面的那个P(h)*P(D|h)了——虽然我们很可能使用了一些启发法来简化计算。后面我们还会提到这样的bottom-up的关联提取。3.模型比较与奥卡姆剃刀3.1再访拼写纠正介绍了贝叶斯拼写纠正之后，接下来的一个自然而然的问题就来了：“为什么？”为什么要用贝叶斯公式？为什么贝叶斯公式在这里可以用？我们可以很容易地领会为什么贝叶斯公式用在前面介绍的那个男生女生长裤裙子的问题里是正确的。但为什么这里？为了回答这个问题，一个常见的思路就是想想：非得这样吗？因为如果你想到了另一种做法并且证明了它也是靠谱的，那么将它与现在这个一比较，也许就能得出很有价值的信息。那么对于拼写纠错问题你能想到其他方案吗？不管怎样，一个最常见的替代方案就是，选择离thew的编辑距离最近的。然而the和thaw离thew的编辑距离都是1。这可咋办捏？你说，不慌，那还是好办。我们就看到底哪个更可能被错打为thew就是了。我们注意到字母e和字母w在键盘上离得