贝叶斯推断及其互联网应用(一)：定理简介.docx

作者： 阮一峰
日期： 2011年8月25日
一年前的这个时候，我正在翻译Paul Graham的《黑客与画家》。
那本书的第八章，写了一个非常具体的技术问题----如何使用贝叶斯推断过滤垃圾邮件（英文版）。
我没完全看懂那一章。当时是硬着头皮，按照字面意思把它译出来的。虽然译文质量还可以，但是心里很不舒服，下决心一定要搞懂它。
一年过去了，我读了一些概率论文献，逐渐发现贝叶斯推断并不难。原理的部分相当容易理解，不需要用到高等数学。
下面就是我的学习笔记。需要声明的是，我并不是这方面的专家，数学其实是我的弱项。欢迎大家提出宝贵意见，让我们共同学习和提高。
=====================================
贝叶斯推断及其互联网应用
作者：阮一峰

一、什么是贝叶斯推断
贝叶斯推断（Bayesian inference）是一种统计学方法，用来估计统计量的某种性质。
它是贝叶斯定理（Bayes' theorem）的应用。英国数学家托马斯·贝叶斯（Thomas Bayes）在1763年发表的一篇论文中，首先提出了这个定理。

贝叶斯推断与其他统计学推断方法截然不同。它建立在主观判断的基础上，也就是说，你可以不需要客观证据，先估计一个值，然后根据实际结果不断修正。正是因为它的主观性太强，曾经遭到许多统计学家的诟病。
贝叶斯推断需要大量的计算，因此历史上很长一段时间，无法得到广泛应用。只有计算机诞生以后，它才获得真正的重视。人们发现，许多统计量是无法事先进行客观判断的，而互联网时代出现的大型数据集，再加上高速运算能力，为验证这些统计量提供了方便，也为应用贝叶斯推断创造了条件，它的威力正在日益显现。
二、贝叶斯定理
要理解贝叶斯推断，必须先理解贝叶斯定理。后者实际上就是计算"条件概率"的公式。
所谓"条件概率"（Conditional probability），就是指在事件B发生的情况下，事件A发生的概率，用P(A|B)来表示。

根据文氏图，可以很清楚地看到在事件B发生的情况下，事件A发生的概率就是P(A∩B)除以P(B)。

因此，

同理可得，

所以，

即

这就是条件概率的计算公式。
三、全概率公式
由于后面要用到，所以除了条件概率以外，这里还要推导全概率公式。
假定样本空间S，是两个事件A与A'的和。

上图中，红色部分是事件A，绿色部分是事件A'，它们共同构成了样本空间S。
在这种情况下，事件B可以划分成两个部分。

即

在上一节的推导当中，我们已知

所以，

这就是全概率公式。它的含义是，如果A和A'构成样本空间的一个划分，那么事件B的概率，就等于A和A'的概率分别乘以B对这两个事件的条件概率之和。
将这个公式代入上一节的条件概率公式，就得到了条件概率的另一种写法：

四、贝叶斯推断的含义
对条件概率公式进行变形，可以得到如下形式：

我们把P(A)称为"先验概率"（Prior probability），即在B事件发生之前，我们对A事件概率的一个判断。P(A|B)称为"后验概率"（Posterior probability），即在B事件发生之后，我们对A事件概率的重新评估。P(B|A)/P(B)称为"可能性函数"（Likelyhood），这是一个调整因子，使得预估概率更接近真实概率。
所以，条件概率可以理解成下面的式子：
　　后验概率　＝　先验概率 ｘ 调整因子
这就是贝叶斯推断的含义。我们先预估一个"先验概率"，然后加入实验结果，看这个实验到底是增强还是削弱了"先验概率"，由此得到更接近事实的"后验概率"。
在这里，如果"可能性函数"P(B|A)/P(B)>1，意味着"先验概率"被增强，事件A的发生的可能性变大；如果"可能性函数"=1，意味着B事件无助于判断事件A的可能性；如果"可能性函数"<1，意味着"先验概率"被削弱，事件A的可能性变小。
五、【例子】水果糖问题
为了加深对贝叶斯推断的理解，我们看两个例子。

第一个例子。两个一模一样的碗，一号碗有30颗水果糖和10颗巧克力糖，二号碗有水果糖和巧克力糖各20颗。现在随机选择一个碗，从中摸出一颗糖，发现是水果糖。请问这颗水果糖来自一号碗的概率有多大？
我们假定，H1表示一号碗，H2表示二号碗。由于这两个碗是一样的，所以P(H1)=P(H2)，也就是说，在取出水果糖之前，这两个碗被选中的概率相同。因此，P(H1)=0.5，我们把这个概率就叫做"先验概率"，即没有做实验之前，来自一号碗的概率是0.5。
再假定，E表示水果糖，所以问题就变成了在已知E的情况下，来自一号碗的概率有多大，即求P(H1|E)。我们把这个概率叫做"后验概率"，即在E事件发生之后，对P(H1)的修正。
根据条件概率公式，得到

已知，P(H1)等于0.5，P(E|H1)为一号碗中取出水果糖的概率，等于0.75，那么求出P(E)就可以得到答案。根据全概率公式，

所以，

将数字代入原方程，得到

这表明，来自一号碗的概率是0.6。也就是说，取出水果糖之后，H1事件的可能性得到了增强。
六、【例子】假阳性问题
第二个例子是一个医学的常见问题，与现实生活关系紧密。

已知某种疾病的发病率是0.001，即1000人中会有1个人得病。现有一种试剂可以检验患者是否得病，它的准确率是0.99，即在患者确实得病的情况下，它有99%的可能呈现阳性。它的误报率是5%，即在患者没有得病的情况下，它有5%的可能呈现阳性。现有一个病人的检验结果为阳性，请问他确实得病的可能性有多大？
假定A事件表示得病，那么P(A)为0.001。这就是"先验概率"，即没有做试验之前，我们预计的发病率。再假定B事件表示阳性，那么要计算的就是P(A|B)。这就是"后验概率"，即做了试验以后，对发病率的估计。
根据条件概率公式，

用全概率公式改写分母，

将数字代入，

我们得到了一个惊人的结果，P(A|B)约等于0.019。也就是说，即使检验呈现阳性，病人得病的概率，也只是从0.1%增加到了2%左右。这就是所谓的"假阳性"，即阳性结果完全不足以说明病人得病。
为什么会这样？为什么这种检验的准确率高达99%，但是可信度却不到2%？答案是与它的误报率太高有关。（【习题】如果误报率从5%降为1%，请问病人得病的概率会变成多少？）
有兴趣的朋友，还可以算一下"假阴性"问题，即检验结果为阴性，但是病人确实得病的概率有多大。然后问自己，"假阳性"和"假阴性"，哪一个才是医学检验的主要风险？
===================================
关于贝叶斯推断的原理部分，今天就讲到这里。下一次，将介绍如何使用贝叶斯推断过滤垃圾邮件。
（未完待续）
贝叶斯推断及其互联网应用（二）：过滤垃圾邮件

作者： 阮一峰
日期： 2011年8月27日
上一次，我介绍了贝叶斯推断的原理，今天讲如何将它用于垃圾邮件过滤。
========================================
贝叶斯推断及其互联网应用
作者：阮一峰

（接上文）
七、什么是贝叶斯过滤器？
垃圾邮件是一种令人头痛的顽症，困扰着所有的互联网用户。
正确识别垃圾邮件的技术难度非常大。传统的垃圾邮件过滤方法，主要有"关键词法"和"校验码法"等。前者的过滤依据是特定的词语；后者则是计算邮件文本的校验码，再与已知的垃圾邮件进行对比。它们的识别效果都不理想，而且很容易规避。
2002年，Paul Graham提出使用"贝叶斯推断"过滤垃圾邮件。他说，这样做的效果，好得不可思议。1000封垃圾邮件可以过滤掉995封，且没有一个误判。
另外，这种过滤器还具有自我学习的功能，会根据新收到的邮件，不断调整。收到的垃圾邮件越多，它的准确率就越高。
八、建立历史资料库
贝叶斯过滤器是一种统计学过滤器，建立在已有的统计结果之上。所以，我们必须预先提供两组已经识别好的邮件，一组是正常邮件，另一组是垃圾邮件。
我们用这两组邮件，对过滤器进行"训练"。这两组邮件的规模越大，训练效果就越好。Paul Graham使用的邮件规模，是正常邮件和垃圾邮件各4000封。
"训练"过程很简单。首先，解析所有邮件，提取每一个词。然后，计算每个词语在正常邮件和垃圾邮件中的出现频率。比如，我们假定"sex"这个词，在4000封垃圾邮件中，有200封包含这个词，那么它的出现频率就是5%；而在4000封正常邮件中，只有2封包含这个词，那么出现频率就是0.05%。（【注释】如果某个词只出现在垃圾邮件中，Paul Graham就假定，它在正常邮件的出现频率是1%，反之亦然。这样做是为了避免概率为0。随着邮件数量的增加，计算结果会自动调整。）
有了这个初步的统计结果，过滤器就可以投入使用了。
九、贝叶斯过滤器的使用过程
现在，我们收到了一封新邮件。在未经统计分析之前，我们假定它是垃圾邮件的概率为50%。（【注释】有研究表明，用户收到的电子邮件中，80%是垃圾邮件。但是，这里仍然假定垃圾邮件的"先验概率"为50%。）
我们用S表示垃圾邮件（spam），H表示正常邮件（healthy）。因此，P(S)和P(H)的先验概率，都是50%。

然后，对这封邮件进行解析，发现其中包含了sex这个词，请问这封邮件属于垃圾邮件的概率有多高？
我们用W表示"sex"这个词，那么问题就变成了如何计算P(S|W)的值，即在某个词语（W）已经存在的条件下，垃圾邮件（S）的概率有多大。
根据条件概率公式，马上可以写出

公式中，P(W|S)和P(W|H)的含义是，这个词语在垃圾邮件和正常邮件中，分别出现的概率。这两个值可以从历史资料库中得到，对sex这个词来说，上文假定它们分别等于5%和0.05%。另外，P(S)和P(H)的值，前面说过都等于50%。所以，马上可以计算P(S|W)的值：

因此，这封新邮件是垃圾邮件的概率等于99%。这说明，sex这个词的推断能力很强，将50%的"先验概率"一下子提高到了99%的"后验概率"。
十、联合概率的计算
做完上面一步，请问我们能否得出结论，这封新邮件就是垃圾邮件？
回答是不能。因为一封邮件包含很多词语，一些词语（比如sex）说这是垃圾邮件，另一些说这不是。你怎么知道以哪个词为准？
Paul Graham的做法是，选出这封信中P(S|W)最高的15个词，计算它们的联合概率。（【注释】如果有的词是第一次出现，无法计算P(S|W)，Paul Graham就假定这个值等于0.4。因为垃圾邮件用的往往都是某些固定的词语，所以如果你从来没见过某个词，它多半是一个正常的词。）
所谓联合概率，就是指在多个事件发生的情况下，另一个事件发生概率有多大。比如，已知W1和W2是两个不同的词语，它们都出现在某封电子邮件之中，那么这封邮件是垃圾邮件的概率，就是联合概率。
在已知W1和W2的情况下，无非就是两种结果：垃圾邮件（事件E1）或正常邮件（事件E2）。

其中，W1、W2和垃圾邮件的概率分别如下：

如果假定所有事件都是独立事件（【注释】严格地说，这个假定不成立，但是这里可以忽略），那么就可以计算P(E1)和P(E2)：

又由于在W1和W2已经发生的情况下，垃圾邮件的概率等于下面的式子：

即

将P(S)等于0.5代入，得到

将P(S|W1)记为P1，P(S|W2)记为P2，公式就变成

这就是联合概率的计算公式。如果你不是很理解，点击这里查看更多的解释。
十一、最终的计算公式
将上面的公式扩展到15个词的情况，就得到了最终的概率计算公式：

一封邮件是不是垃圾邮件，就用这个式子进行计算。这时我们还需要一个用于比较的门槛值。Paul Graham的门槛值是0.9，概率大于0.9，表示15个词联合认定，这封邮件有90%以上的可能属于垃圾邮件；概率小于0.9，就表示是正常邮件。
有了这个公式以后，一封正常的信件即使出现sex这个词，也不会被认定为垃圾邮件了。
（完）
文档信息
§ 版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0
§ 原文网址：
§ 最后修改时间：2013年9月29日 20:24
§ 付费支持： | 

相关文章
§ 2013.03.31: 相似图片搜索的原理（二）
二年前，我写了《相似图片搜索的原理》，介绍了一种最简单的实现方法。
§ 2013.03.26: TF-IDF与余弦相似性的应用（三）：自动摘要
有时候，很简单的数学方法，就可以完成很复杂的任务。
功能链接
§ 前一篇：贝叶斯推断及其互联网应用（一）：定理简介
§ 后一篇：经济增长是如何换来的？
§ 更多内容请访问：首页 » 档案 » 算法
§
窗体顶端
站内搜索： 
窗体底端
§ Feed订阅： 
广告（购买广告位）

留言（50条）
49Degree 说：
难怪现在收的开发票垃圾邮件，都是以附件图片显示内容了
2011年8月27日 18:09 | 档案 | 引用
屎蛋 说：
Mark 先！
估计发展一下可以变成炒股公式
2011年8月27日 20:16 | 档案 | 引用
3tgame 说：
将P(S|W1)记为P1，P(S|W1)记为P2
第二个是否应为W2？
2011年8月27日 20:58 | 档案 | 引用
小年 说：
理论性太强啊~~~
2011年8月27日 21:23 | 档案 | 引用
zc 说：
不怕漏，漏一点没关系，怕被误杀
而且中文的是不是还要加语义分析？
2011年8月27日 22:26 | 档案 | 引用
水人 说：
能不能说明文章中一些数据，比如：“如果某个词只出现在垃圾邮件中，Paul Graham就假定，它在正常邮件的出现频率是1%，反之亦然。随着邮件数量的增加，计算结果会自动调整。”中的1%，请问是不是经验值
2011年8月27日 22:48 | 档案 | 引用
Allen 说：
P(E1)+P(E2)不等於1嗎？
2011年8月27日 23:01 | 档案 | 引用
Bill 说：
整个过程讲的很清晰，谢谢阮大哥分享，不过，推导中有两个地方我不太明白：
1. P(E1)=P(S|W1)*P(S|W2)*P(S) (why?)
2. P=P(E1)/(P(E1)+P(E2)) 像楼上Allen说的，直觉是P(E1)+P(E2)=1
能否解释一下E1和E2在样本空间中的精确含义呢？
我的理解是E1=S && W1 && W2，也就是说有E1封邮件，满足以上三个条件，总邮件S+H封，P(E1)=E1/(S+H)
能否解释一下1和2的理由？
谢谢！！
2011年8月28日 00:36 | 档案 | 引用
Paul Graham中文站 说：
本人也是 Paul Graham 的粉丝，也看过你翻译的黑客与画家，
但还是凭直觉认为 PG 不可能是Bayes filtering的发明者，你看看这个就知道了：http://en.wikipedia.org/wiki/Bayesian_spam_filtering#History
96年就有人发布了。
2011年8月28日 08:14 | 档案 | 引用
hyh 说：
看这里, 96年就有人发明了Bayes Filtering, PG怎么可能是发明者。
2011年8月28日 08:15 | 档案 | 引用
new4everlau 说：
挺好的文章，我是来学习的！
在第十一节上面倒数第二行有点表述错误，不过不影响阅读！
“将P(S|W1)记为P1，P(S|W1)记为P2，公式就变成”
“将P(S|W1)记为P1，P(S|W2)记为P2，公式就变成”
2011年8月28日 08:22 | 档案 | 引用
阮一峰 说：
@3tgame：谢谢指出，已经更正了。
@水人：对，是经验值。好在可以根据新收的邮件不断调整。
@Allen：E1和E2是指后面三个事件同时发生，所以它们的和不等于1。
@hyh：Paul Graham发明的是现在这一套计算方法，大大提高了过滤效果，而不是发明用贝叶斯推断过滤邮件的概念。
2011年8月28日 08:24 | 档案 | 引用
阮一峰 说：
引用Bill的发言：
1. P(E1)=P(S|W1)*P(S|W2)*P(S) (why?)
E1代表三个独立事件同时发生，因此E1的概率是后面三个概率的乘积。
引用Bill的发言：
2. P=P(E1)/(P(E1)+P(E2)) 像楼上Allen说的，直觉是P(E1)+P(E2)=1
如果P(E1)=P(S|W1W2)，那么P(E1)+P(E2)确实等于1。
但是，我们规定E1是三个事件同时发生，因此P(E1)等于P(W1)P(W2)P(S)，所以它与P(E2)的和不会等于1。

2011年8月28日 09:48 | 档案 | 引用
hyh 说：
这类文章真有必要让国内媒体看看。南方周末、南都周刊上面全是垃圾评论，什么炒股赚钱之类。国人人海战术的水平还蛮高的⋯⋯
2011年8月28日 09:57 | 档案 | 引用
天天向上 说：
如果概率论老师能像这样讲些具体应用，我上课也不至于睡觉了
2011年8月28日 14:36 | 档案 | 引用
fengyh 说：
P1应该是P（W1|S）吧？
2011年8月28日 15:15 | 档案 | 引用
mw3000 说：
http://science.solidot.org/article.pl?sid=11/08/06/147202
贝叶斯定理以18世纪的长老教会牧师Thomas Bayes的名字命名，目的是为了解决一些本质问题：当更多信息涌入时我们如何改变信仰？是顽固的直到旧有假说完全站不住脚？还是在怀疑第一次出现后立即抛弃旧观念？贝叶斯的推导已经变成了无价的科学工具，它帮助我们一步步认清现实。也许人人都应该像贝叶斯那样思考。

贝叶斯理论的核心依赖于巧妙的转变思路：如果你想评估根据证据提出的假说的有力程度，你必须先评估证据的有力程度。面对着不确定性，贝叶斯提出了三个问题：对最初树立的信念的真实性我有多大的信心？如果对最初的信念坚信不疑，对新证据的准确性我有多大的信心？如果对最初的信念摇摆不定，对新证据的准确性我有多大的信心？大卫·休谟就是一位贝叶斯主义者，他就是通过证据的可能性质疑神迹的准确性。
这一段话我没有看得太懂, 博主能不能帮解释一下.
2011年8月28日 16:34 | 档案 | 引用
cumirror 说：
粗略看了一遍，很精彩的文章。
2011年8月28日 17:13 | 档案 | 引用
呆子 说：
第十步的推导建立在三个量的独立性上，即P(S|W1)、P(S|W2)、P(S)，或者说是这三者的相关性很小，可以忽略。但就在这样的基础上，我们得到了
P(S)=P(S|W1)XP(S|W2)/(P(S|W1)XP(S|W2)+(1-P(S|W1))X(1-P(S|W2)))
然而这个关系式很清楚的给出了P(S|W1)、P(S|W2)、P(S)三者的关系。这是不是让我们很遗憾，尽管整个过程是没有问题的，但我们觉得很别扭。由无关的假设，却得到了真真切切的关系。
而笔者似乎忘记了最简单的计算P(S)的方法：
P(S)=P(S|W1)XP(W1)+P(S|W2)XP(W2)+P(S|W3)XP(W3)+……
这里P(W1)P(W2)P(W3)……是W1W2W3出现的频率。
而且这样做是没有理论上的缺陷的。是否可以考虑一下？
2011年8月28日 18:57 | 档案 | 引用
清风剑 说：
引用zc的发言：
不怕漏，漏一点没关系，怕被误杀
而且中文的是不是还要加语义分析？
对，中文要分词再做以上步骤，但分词就表明了你是怎么理解一个句子的，纠结。。
2011年8月28日 20:31 | 档案 | 引用
Bill 说：
@ Mw3000:
贝叶斯理论的核心依赖于巧妙的转变思路：如果你想评估根据证据提出的假说的有力程度，你必须先评估证据的有力程度。面对着不确定性，贝叶斯提出了三个问题：
对最初树立的信念的真实性我有多大的信心？ ---> P(A)
如果对最初的信念坚信不疑，对新证据的准确性我有多大的信心？---> P(B|A)
如果对最初的信念摇摆不定，对新证据的准确性我有多大的信心？---> P(B)
Bayesian Inference:
P(A|B)=P(A)*P(B|A)/P(B)
该文揭示了公式中每一项的现实含义。谢谢分享，我一直在想公式里的每一项有什么直接朴素的内涵，这三个问题回答了我的疑问。
2011年8月28日 23:54 | 档案 | 引用
Chuan 说：
请问有什么即有趣，又实用的概率论方面的书吗？
2011年8月29日 14:31 | 档案 | 引用
Michael.Z 说：
越来越多的邮件采取图片和附件的方式发送垃圾邮件。这方面的鉴别方法又是如何的？
2011年8月29日 16:43 | 档案 | 引用
宁静致远 说：
在华尔街的高频交易系统，70%的股票交易由计算机算法完成，而算法并不总是很可靠。2010年5月算法曾引起股市在短时间内崩盘，它在20分钟内抛出了价值26亿美元的股票，导致其它高频交易算法跟随，引发金融市场混乱。
这种算法的推广的结果是，下个5000天会产生60亿个相当于人脑一样复杂的机器在互联网上.
2011年8月29日 17:04 | 档案 | 引用
mw3000 说：
@Bill:
谢谢你的解释.
2011年8月29日 19:54 | 档案 | 引用
I believe I can fly 说：
不是很明白：
P(S)=p(E1)/(P(E1)+P(E2))
求解释
2011年9月 1日 21:10 | 档案 | 引用
Jin 说：
引用Bill的发言：
整个过程讲的很清晰，谢谢阮大哥分享，不过，推导中有两个地方我不太明白：
1. P(E1)=P(S|W1)*P(S|W2)*P(S) (why?)
2. P=P(E1)/(P(E1)+P(E2)) 像楼上Allen说的，直觉是P(E1)+P(E2)=1
感觉推导跳过了几步：
P(S|W1 W2) = P(W1 W2|S)P(S) / (P(W1 W2|S)P(S) + P(W1 W2|~S)P(~S))
W1,W2独立：P(W1 W2) = P(W1)P(W2), P(W1 W2|S) = P(W1|S)P(W2|S) (？)
上式 = P(W1|S)P(W2|S)P(S) / (P(W1|S)P(W2|S)P(S) + P(W1|~S)P(W2|~S)P(~S))
应用Bayesian 原理，将 P(Wi|S) 用 P(S|Wi) 表示：
上式 = (P(S|W1)P(S|W2)P(S) * P(W1)P(W2) / P(S)^2) / ((P(S|W1)P(S|W2)P(S) * P(W1)P(W2) / P(S)^2) + (P(~S|W1)P(~S|W2)P(~S) * P(W1)P(W2) / P(~S)^2))
在 P(S) = P(~S) = 50% 的条件下：
上式 = P(S|W1)P(S|W2) / (P(S|W1)P(S|W2) + P(~S|W1)P(~S|W2))
= P1P2 / (P1P2 + (1-P1)(1-P2));
2011年9月 7日 15:26 | 档案 | 引用
fly 说：
根据 Jin 的方法，得到的结果是
p(S|W1W2) = P(~S)P1P2/(P(~S)P1P2 + P(S)(1-P1)(1-P2))
我觉得Jin是正确的。
2011年9月16日 00:13 | 档案 | 引用
ttldreams 说：
现在垃圾留言的干扰符号/文字/异形字越来越多，变种也很多，这种算法奏效吗
2011年9月18日 18:08 | 档案 | 引用
C楠R诺 说：
实在很佩服作者！您的文章给了我学习很大的帮助！非常感谢。
2011年9月24日 19:29 | 档案 | 引用
rrandom 说：
最近在看斯坦福的在线课程.
ml-class.org.对比着这篇文章.收获蛮大..
2011年11月19日 21:12 | 档案 | 引用
fafa 说：
学习了 不过后面的联合概率部分有点懵
2011年11月30日 11:30 | 档案 | 引用
liput 说：
非常感谢你的文章，看了受益匪浅！
2012年2月15日 10:56 | 档案 | 引用
Quady 说：
又由于在W1和W2已经发生的情况下，垃圾邮件的概率等于下面的式子：
P=P(E1)/(P(E1)+P(E2))
我来尝试解释一下，呵呵
在上面已经说明了，E1是在W1和W2同时出现的情况下垃圾邮件的事件，E2是W1和W2同时出现情况下正常邮件的事件，注意这里的前提都是“在W1和W2同时出现的情况下”。
那么，P=P(E1)/P(W1,W2)，其意思是W1和W2共同出现的情况下是垃圾邮件的概率，而P(W1,W2)实际就是P(E1)+P(E2)
所以，P=P(E1)/(P(E1)+P(E2))
2012年3月29日 15:42 | 档案 | 引用
futuredo 说：