数学之美番外篇平凡而又神奇的贝叶斯方法.docx
《数学之美番外篇平凡而又神奇的贝叶斯方法.docx》由会员分享，可在线阅读，更多相关《数学之美番外篇平凡而又神奇的贝叶斯方法.docx（22页珍藏版）》请在冰点文库上搜索。
数学之美番外篇平凡而又神奇的贝叶斯方法
数学之美番外篇：
平凡而又神奇的贝叶斯方法
By刘未鹏（pongba）
C++的罗浮宫（
TopLanguage（
概率论只不过是把常识用数学公式表达了出来。
——拉普拉斯
记得读本科的时候，最喜欢到城里的计算机书店里面去闲逛，一逛就是好几个小时；有一次，在书店看到一本书，名叫贝叶斯方法。
当时数学系的课程还没有学到概率统计。
我心想，一个方法能够专门写出一本书来，肯定很牛逼。
后来，我发现当初的那个朴素归纳推理成立了——这果然是个牛逼的方法。
——题记
目录
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贝叶斯图像识别，AnalysisbySynthesis
4.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在键盘上离得很紧，无名指一抽筋就不小心多打出一个w来，the就变成thew了。
而另一方面thaw被错打成thew的可能性就相对小一点，因为e和a离得较远而且使用的指头相差一个指头（一个是中指一个是小指，不像e和w使用的指头靠在一块——神经科学的证据表明紧邻的身体设施之间容易串位）。
OK，很好，因为你现在已经是在用最大似然方法了，或者直白一点，你就是在计算那个使得P（D|h）最大的h。
而贝叶斯方法计算的是什么？
是P（h）*P（D|h）。
多出来了一个P（h）。
我们刚才说了，这个多出来的P（h）是特定猜测的先验概率。
为什么要掺和进一个先验概率？
刚才说的那个最大似然不是挺好么？
很雄辩地指出了the是更靠谱的猜测。
有什么问题呢？
既然这样，我们就从给最大似然找茬开始吧——我们假设两者的似然程度是一样或非常相近，这样不就难以区分哪个猜测更靠谱了吗？
比如用户输入tlp，那到底是top还是tip？
（这个例子不怎么好，因为top和tip的词频可能仍然是接近的，但一时想不到好的英文单词的例子，我们不妨就假设top比tip常见许多吧，这个假设并不影响问题的本质。
）这个时候，当最大似然不能作出决定性的判断时，先验概率就可以插手进来给出指示——“既然你无法决定，那么我告诉你，一般来说top出现的程度要高许多，所以更可能他想打的是top”）。
以上只是最大似然的一个问题，即并不能提供决策的全部信息。
最大似然还有另一个问题：
即便一个猜测与数据非常符合，也并不代表这个猜测就是更好的猜测，因为这个猜测本身的可能性也许就非常低。
比如MacKay在《InformationTheory:
InferenceandLearningAlgorithms》里面就举了一个很好的例子：
-13711你说是等差数列更有可能呢？
还是-X^3/11+9/11*X^2+23/11每项把前项作为X带入后计算得到的数列？
此外曲线拟合也是，平面上N个点总是可以用N-1阶多项式来完全拟合，当N个点近似但不精确共线的时候，用N-1阶多项式来拟合能够精确通过每一个点，然而用直线来做拟合/线性回归的时候却会使得某些点不能位于直线上。
你说到底哪个好呢？
多项式？
还是直线？
一般地说肯定是越低阶的多项式越靠谱（当然前提是也不能忽视“似然”P（D|h），明摆着一个多项式分布您愣是去拿直线拟合也是不靠谱的，这就是为什么要把它们两者乘起来考虑。
），原因之一就是低阶多项式更常见，先验概率（P（h））较大（原因之二则隐藏在P（D|h）里面），这就是为什么我们要用样条来插值，而不是直接搞一个N-1阶多项式来通过任意N个点的原因。
以上分析当中隐含的哲学是，观测数据总是会有各种各样的误差，比如观测误差（比如你观测的时候一个MM经过你一不留神，手一抖就是一个误差出现了），所以如果过分去寻求能够完美解释观测数据的模型，就会落入所谓的数据过配（overfitting）的境地，一个过配的模型试图连误差（噪音）都去解释（而实际上噪音又是不需要解释的），显然就过犹不及了。
所以P（D|h）大不代表你的h（猜测）就是更好的h。
还要看P（h）是怎样的。
所谓奥卡姆剃刀精神就是说：
如果两个理论具有相似的解释力度，那么优先选择那个更简单的（往往也正是更平凡的，更少繁复的，更常见的）。
过分匹配的另一个原因在于当观测的结果并不是因为误差而显得“不精确”而是因为真实世界中对数据的结果产生贡献的因素太多太多，跟噪音不同，这些偏差是一些另外的因素集体贡献的结果，不是你的模型所能解释的——噪音那是不需要解释——一个现实的模型往往只提取出几个与结果相关度很高，很重要的因素（cause）。
这个时候观察数据会倾向于围绕你的有限模型的预测结果呈正态分布，于是你实际观察到的结果就是这个正态分布的随机取样，这个取样很可能受到其余因素的影响偏离你的模型所预测的中心，这个时候便不能贪心不足地试图通过改变模型来“完美”匹配数据，因为那些使结果偏离你的预测的贡献因素不是你这个有限模型里面含有的因素所能概括的，硬要打肿脸充胖子只能导致不实际的模型，举个教科书例子：
身高和体重的实际关系近似于一个二阶多项式的关系，但大家都知道并不是只有身高才会对体重产生影响，物理世界影响体重的因素太多太多了，有人身材高大却瘦得跟稻草，有人却是横长竖不长。
但不可否认的是总体上来说，那些特殊情况越是特殊就越是稀少，呈围绕最普遍情况（胖瘦适中）的正态分布，这个分布就保证了我们的身高——体重相关模型能够在大多数情况下做出靠谱的预测。
但是——刚才说了，特例是存在的，就算不是特例，人有胖瘦，密度也有大小，所以完美符合身高——体重的某个假想的二阶多项式关系的人是不存在的，我们又不是欧几里德几何世界当中的理想多面体，所以，当我们对人群随机抽取了N个样本（数据点）试图对这N个数据点拟合出一个多项式的话就得注意，它肯定得是二阶多项式，我们要做的只是去根据数据点计算出多项式各项的参数（一个典型的方法就是最小二乘）；它肯定不是直线（我们又不是稻草），也不是三阶多项式四阶多项式..如果硬要完美拟合N个点，你可能会整出一个N-1阶多项式来——设想身高和体重的关系是5阶多项式看看？
3.2模型比较理论（ModelComparasion）与贝叶斯奥卡姆剃刀（BayesianOccam’sRazor）
实际上，模型比较就是去比较哪个模型（猜测）更可能隐藏在观察数据的背后。
其基本思想前面已经用拼写纠正的例子来说明了。
我们对用户实际想输入的单词的猜测就是模型，用户输错的单词就是观测数据。
我们通过：
P（h|D）∝P（h）*P（D|h）
来比较哪个模型最为靠谱。
前面提到，光靠P（D|h）（即“似然”）是不够的，有时候还需要引入P（h）这个先验概率。
奥卡姆剃刀就是说P（h）较大的模型有较大的优势，而最大似然则是说最符合观测数据的（即P（D|h）最大的）最有优势。
整个模型比较就是这两方力量的拉锯。
我们不妨再举一个简单的例子来说明这一精神：
你随便找枚硬币，掷一下，观察一下结果。
好，你观察到的结果要么是“正”，要么是“反”（不，不是少林足球那枚硬币:
P），不妨假设你观察到的是“正”。
现在你要去根据这个观测数据推断这枚硬币掷出“正”的概率是多大。
根据最大似然估计的精神，我们应该猜测这枚硬币掷出“正”的概率是1，因为这个才是能最大化P（D|h）的那个猜测。
然而每个人都会大摇其头——很显然，你随机摸出一枚硬币这枚硬币居然没有反面的概率是“不存在的”，我们对一枚随机硬币是否一枚有偏硬币，偏了多少，是有着一个先验的认识的，这个认识就是绝大多数硬币都是基本公平的，偏得越多的硬币越少见（可以用一个beta分布来表达这一先验概率）。
将这个先验正态分布p（θ）（其中θ表示硬币掷出正面的比例，小写的p代表这是概率密度函数）结合到我们的问题中，我们便不是去最大化P（D|h），而是去最大化P（D|θ）*p（θ），显然θ=1是不行的，因为P（θ=1）为0，导致整个乘积也为0。
实际上，只要对这个式子求一个导数就可以得到最值点。
以上说的是当我们知道先验概率P（h）的时候，光用最大似然是不靠谱的，因为最大似然的猜测可能先验概率非常小。
然而，有些时候，我们对于先验概率一无所知，只能假设每种猜测的先验概率是均等的，这个时候就只有用最大似然了。
实际上，统计学家和贝叶斯学家有一个有趣的争论，统计学家说：
我们让数据自己说话。
言下之意就是要摒弃先验概率。
而贝叶斯支持者则说：
数据会有各种各样的偏差，而一个靠谱的先验概率则可以对这些随机噪音做到健壮。
事实证明贝叶斯派胜利了，胜利的关键在于所谓先验概率其实也是经验统计的结果，譬如为什么我们会认为绝大多数硬币是基本公平的？
为什么我们认为大多数人的肥胖适中？
为什么我们认为肤色是种族相关的，而体重则与种族无关？
先验概率里面的“先验”并不是指先于一切经验，而是仅指先于我们“当前”给出的观测数据而已，在硬币的例子中先验指的只是先于我们知道投掷的结果这个经验，而并非“先天”。
然而，话说回来，有时候我们必须得承认，就算是基于以往的经验，我们手头的“先验”概率还是均匀分布，这个时候就必须依赖用最大似然，我们用前面留下的一个自然语言二义性问题来说明这一点：
Thegirlsawtheboywithatelescope.
到底是Thegirlsaw-with-a-telescopetheboy这一语法结构，还是Thegirlsawthe-boy-with-a-telescope呢？
两种语法结构的常见程度都差不多（你可能会觉得后一种语法结构的常见程度较低，这是事后偏见，你只需想想Thegirlsawtheboywithabook就知道了。
当然，实际上从大规模语料统计结果来看后一种语法结构的确稍稍不常见一丁点，但是绝对不足以解释我们对第一种结构的强烈倾向）。
那么到底为什么呢？
我们不妨先来看看MacKay在书中举的一个漂亮的例子：
图中有多少个箱子？
特别地，那棵书后面是一个箱子？
还是两个箱子？
还是三个箱子？
还是..你可能会觉得树后面肯定是一个箱子，但为什么不是两个呢？
如下图：
很简单，你会说：
要是真的有两个箱子那才怪了，怎么就那么巧这两个箱子刚刚好颜色相同，高度相同呢？
用概率论的语言来说，你刚才的话就翻译为：
猜测h不成立，因为P（D|h）太小（太巧合）了。
我们的直觉是：
巧合（小概率）事件不会发生。
所以当一个猜测（假设）使得我们的观测结果成为小概率事件的时候，我们就说“才怪呢，哪能那么巧捏？
！
”
现在我们可以回到那个自然语言二义性的例子，并给出一个完美的解释了：
如果语法结构是Thegirlsawthe-boy-with-a-telecope的话，怎么那个男孩偏偏手里拿的就是望远镜——一个可以被用来saw-with的东东捏？
这也忒小概率了吧。
他咋就不会拿本书呢？
拿什么都好。
怎么偏偏就拿了望远镜？
所以唯一的解释是，这个“巧合”背后肯定有它的必然性，这个必然性就是，如果我们将语法结构解释为Thegirlsaw-with-a-telescopetheboy的话，就跟数据完美吻合了——既然那个女孩是用某个东西去看这个男孩的，那么这
升级会员 