一年前的这个时候&＃xff0c;我正在翻译Paul Graham的《黑客与画家》。
那本书的第八章&＃xff0c;写了一个非常具体的技术问题----如何使用贝叶斯推断过滤垃圾邮件&＃xff08;英文版&＃xff09;。
我没完全看懂那一章。当时是硬着头皮&＃xff0c;按照字面意思把它译出来的。虽然译文质量还可以&＃xff0c;但是心里很不舒服&＃xff0c;下决心一定要搞懂它。
一年过去了&＃xff0c;我读了一些概率论文献&＃xff0c;逐渐发现贝叶斯推断并不难。原理的部分相当容易理解&＃xff0c;不需要用到高等数学。
下面就是我的学习笔记。需要声明的是&＃xff0c;我并不是这方面的专家&＃xff0c;数学其实是我的弱项。欢迎大家提出宝贵意见&＃xff0c;让我们共同学习和提高。
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
贝叶斯推断及其互联网应用
作者&＃xff1a;阮一峰
一、什么是贝叶斯推断
贝叶斯推断&＃xff08;Bayesian inference&＃xff09;是一种统计学方法&＃xff0c;用来估计统计量的某种性质。
它是贝叶斯定理&＃xff08;Bayes&＃39; theorem&＃xff09;的应用。英国数学家托马斯·贝叶斯&＃xff08;Thomas Bayes&＃xff09;在1763年发表的一篇论文中&＃xff0c;首先提出了这个定理。
贝叶斯推断与其他统计学推断方法截然不同。它建立在主观判断的基础上&＃xff0c;也就是说&＃xff0c;你可以不需要客观证据&＃xff0c;先估计一个值&＃xff0c;然后根据实际结果不断修正。正是因为它的主观性太强&＃xff0c;曾经遭到许多统计学家的诟病。
贝叶斯推断需要大量的计算&＃xff0c;因此历史上很长一段时间&＃xff0c;无法得到广泛应用。只有计算机诞生以后&＃xff0c;它才获得真正的重视。人们发现&＃xff0c;许多统计量是无法事先进行客观判断的&＃xff0c;而互联网时代出现的大型数据集&＃xff0c;再加上高速运算能力&＃xff0c;为验证这些统计量提供了方便&＃xff0c;也为应用贝叶斯推断创造了条件&＃xff0c;它的威力正在日益显现。
二、贝叶斯定理
要理解贝叶斯推断&＃xff0c;必须先理解贝叶斯定理。后者实际上就是计算"条件概率"的公式。
所谓"条件概率"&＃xff08;Conditional probability&＃xff09;&＃xff0c;就是指在事件B发生的情况下&＃xff0c;事件A发生的概率&＃xff0c;用P(A|B)来表示。
根据文氏图&＃xff0c;可以很清楚地看到在事件B发生的情况下&＃xff0c;事件A发生的概率就是P(A∩B)除以P(B)。
上图中&＃xff0c;红色部分是事件A&＃xff0c;绿色部分是事件A&＃39;&＃xff0c;它们共同构成了样本空间S。
在这种情况下&＃xff0c;事件B可以划分成两个部分。
即
第一个例子。两个一模一样的碗&＃xff0c;一号碗有30颗水果糖和10颗巧克力糖&＃xff0c;二号碗有水果糖和巧克力糖各20颗。现在随机选择一个碗&＃xff0c;从中摸出一颗糖&＃xff0c;发现是水果糖。请问这颗水果糖来自一号碗的概率有多大&＃xff1f;
我们假定&＃xff0c;H1表示一号碗&＃xff0c;H2表示二号碗。由于这两个碗是一样的&＃xff0c;所以P(H1)&＃61;P(H2)&＃xff0c;也就是说&＃xff0c;在取出水果糖之前&＃xff0c;这两个碗被选中的概率相同。因此&＃xff0c;P(H1)&＃61;0.5&＃xff0c;我们把这个概率就叫做"先验概率"&＃xff0c;即没有做实验之前&＃xff0c;来自一号碗的概率是0.5。
再假定&＃xff0c;E表示水果糖&＃xff0c;所以问题就变成了在已知E的情况下&＃xff0c;来自一号碗的概率有多大&＃xff0c;即求P(H1|E)。我们把这个概率叫做"后验概率"&＃xff0c;即在E事件发生之后&＃xff0c;对P(H1)的修正。
根据条件概率公式&＃xff0c;得到
已知某种疾病的发病率是0.001&＃xff0c;即1000人中会有1个人得病。现有一种试剂可以检验患者是否得病&＃xff0c;它的准确率是0.99&＃xff0c;即在患者确实得病的情况下&＃xff0c;它有99%的可能呈现阳性。它的误报率是5%&＃xff0c;即在患者没有得病的情况下&＃xff0c;它有5%的可能呈现阳性。现有一个病人的检验结果为阳性&＃xff0c;请问他确实得病的可能性有多大&＃xff1f;
假定A事件表示得病&＃xff0c;那么P(A)为0.001。这就是"先验概率"&＃xff0c;即没有做试验之前&＃xff0c;我们预计的发病率。再假定B事件表示阳性&＃xff0c;那么要计算的就是P(A|B)。这就是"后验概率"&＃xff0c;即做了试验以后&＃xff0c;对发病率的估计。
根据条件概率公式&＃xff0c;
&＃xff08;接上文&＃xff09;
七、什么是贝叶斯过滤器&＃xff1f;
垃圾邮件是一种令人头痛的顽症&＃xff0c;困扰着所有的互联网用户。
正确识别垃圾邮件的技术难度非常大。传统的垃圾邮件过滤方法&＃xff0c;主要有"关键词法"和"校验码法"等。前者的过滤依据是特定的词语&＃xff1b;后者则是计算邮件文本的校验码&＃xff0c;再与已知的垃圾邮件进行对比。它们的识别效果都不理想&＃xff0c;而且很容易规避。
2002年&＃xff0c;Paul Graham提出使用"贝叶斯推断"过滤垃圾邮件。他说&＃xff0c;这样做的效果&＃xff0c;好得不可思议。1000封垃圾邮件可以过滤掉995封&＃xff0c;且没有一个误判。
另外&＃xff0c;这种过滤器还具有自我学习的功能&＃xff0c;会根据新收到的邮件&＃xff0c;不断调整。收到的垃圾邮件越多&＃xff0c;它的准确率就越高。
八、建立历史资料库
贝叶斯过滤器是一种统计学过滤器&＃xff0c;建立在已有的统计结果之上。所以&＃xff0c;我们必须预先提供两组已经识别好的邮件&＃xff0c;一组是正常邮件&＃xff0c;另一组是垃圾邮件。
我们用这两组邮件&＃xff0c;对过滤器进行"训练"。这两组邮件的规模越大&＃xff0c;训练效果就越好。Paul Graham使用的邮件规模&＃xff0c;是正常邮件和垃圾邮件各4000封。
"训练"过程很简单。首先&＃xff0c;解析所有邮件&＃xff0c;提取每一个词。然后&＃xff0c;计算每个词语在正常邮件和垃圾邮件中的出现频率。比如&＃xff0c;我们假定"sex"这个词&＃xff0c;在4000封垃圾邮件中&＃xff0c;有200封包含这个词&＃xff0c;那么它的出现频率就是5%&＃xff1b;而在4000封正常邮件中&＃xff0c;只有2封包含这个词&＃xff0c;那么出现频率就是0.05%。&＃xff08;【注释】如果某个词只出现在垃圾邮件中&＃xff0c;Paul Graham就假定&＃xff0c;它在正常邮件的出现频率是1%&＃xff0c;反之亦然。这样做是为了避免概率为0。随着邮件数量的增加&＃xff0c;计算结果会自动调整。&＃xff09;
有了这个初步的统计结果&＃xff0c;过滤器就可以投入使用了。
九、贝叶斯过滤器的使用过程
现在&＃xff0c;我们收到了一封新邮件。在未经统计分析之前&＃xff0c;我们假定它是垃圾邮件的概率为50%。&＃xff08;【注释】有研究表明&＃xff0c;用户收到的电子邮件中&＃xff0c;80%是垃圾邮件。但是&＃xff0c;这里仍然假定垃圾邮件的"先验概率"为50%。&＃xff09;
我们用S表示垃圾邮件&＃xff08;spam&＃xff09;&＃xff0c;H表示正常邮件&＃xff08;healthy&＃xff09;。因此&＃xff0c;P(S)和P(H)的先验概率&＃xff0c;都是50%。
其中&＃xff0c;W1、W2和垃圾邮件的概率分别如下&＃xff1a;
如果假定所有事件都是独立事件&＃xff08;【注释】严格地说&＃xff0c;这个假定不成立&＃xff0c;但是这里可以忽略&＃xff09;&＃xff0c;那么就可以计算P(E1)和P(E2)&＃xff1a;
Google告诉你&＃xff0c;这个词是不存在的&＃xff0c;正确的拼法是separate。
这就叫做"拼写检查"&＃xff08;spelling corrector&＃xff09;。有好几种方法可以实现这个功能&＃xff0c;Google使用的是基于贝叶斯推断的统计学方法。这种方法的特点就是快&＃xff0c;很短的时间内处理大量文本&＃xff0c;并且有很高的精确度&＃xff08;90%以上&＃xff09;。Google的研发总监Peter Norvig&＃xff0c;写过一篇著名的文章&＃xff0c;解释这种方法的原理。
下面我们就来看看&＃xff0c;怎么利用贝叶斯推断&＃xff0c;实现"拼写检查"。其实很简单&＃xff0c;一小段代码就够了。
一、原理
用户输入了一个单词。这时分成两种情况&＃xff1a;拼写正确&＃xff0c;或者拼写不正确。我们把拼写正确的情况记做c&＃xff08;代表correct&＃xff09;&＃xff0c;拼写错误的情况记做w&＃xff08;代表wrong&＃xff09;。
所谓"拼写检查"&＃xff0c;就是在发生w的情况下&＃xff0c;试图推断出c。从概率论的角度看&＃xff0c;就是已知w&＃xff0c;然后在若干个备选方案中&＃xff0c;找出可能性最大的那个c&＃xff0c;也就是求下面这个式子的最大值。
P(c|w)
根据贝叶斯定理&＃xff1a;
P(c|w) &＃61; P(w|c) * P(c) / P(w)
对于所有备选的c来说&＃xff0c;对应的都是同一个w&＃xff0c;所以它们的P(w)是相同的&＃xff0c;因此我们求的其实是
P(w|c) * P(c)
的最大值。
P(c)的含义是&＃xff0c;某个正确的词的出现"概率"&＃xff0c;它可以用"频率"代替。如果我们有一个足够大的文本库&＃xff0c;那么这个文本库中每个单词的出现频率&＃xff0c;就相当于它的发生概率。某个词的出现频率越高&＃xff0c;P(c)就越大。
P(w|c)的含义是&＃xff0c;在试图拼写c的情况下&＃xff0c;出现拼写错误w的概率。这需要统计数据的支持&＃xff0c;但是为了简化问题&＃xff0c;我们假设两个单词在字形上越接近&＃xff0c;就有越可能拼错&＃xff0c;P(w|C)就越大。举例来说&＃xff0c;相差一个字母的拼法&＃xff0c;就比相差两个字母的拼法&＃xff0c;发生概率更高。你想拼写单词hello&＃xff0c;那么错误拼成hallo&＃xff08;相差一个字母&＃xff09;的可能性&＃xff0c;就比拼成haallo高&＃xff08;相差两个字母&＃xff09;。
所以&＃xff0c;我们只要找到与输入单词在字形上最相近的那些词&＃xff0c;再在其中挑出出现频率最高的一个&＃xff0c;就能实现 P(w|c) * P(c) 的最大值。
二、算法
最简单的算法&＃xff0c;只需要四步就够了。
第一步&＃xff0c;建立一个足够大的文本库。
网上有一些免费来源&＃xff0c;比如古登堡计划、Wiktionary、英国国家语料库等等。
第二步&＃xff0c;取出文本库的每一个单词&＃xff0c;统计它们的出现频率。
第三步&＃xff0c;根据用户输入的单词&＃xff0c;得到其所有可能的拼写相近的形式。
所谓"拼写相近"&＃xff0c;指的是两个单词之间的"编辑距离"&＃xff08;edit distance&＃xff09;不超过2。也就是说&＃xff0c;两个词只相差1到2个字母&＃xff0c;只通过----删除、交换、更改和插入----这四种操作中的一种&＃xff0c;就可以让一个词变成另一个词。
第四步&＃xff0c;比较所有拼写相近的词在文本库的出现频率。频率最高的那个词&＃xff0c;就是正确的拼法。
根据Peter Norvig的验证&＃xff0c;这种算法的精确度大约为60%-70%&＃xff08;10个拼写错误能够检查出6个。&＃xff09;虽然不令人满意&＃xff0c;但是能够接受。毕竟它足够简单&＃xff0c;计算速度极快。&＃xff08;本文的最后部分&＃xff0c;将详细讨论这种算法的缺陷在哪里。&＃xff09;
三、代码
我们使用Python语言&＃xff0c;实现上一节的算法。
第一步&＃xff0c;把网上下载的文本库保存为big.txt文件。这步不需要编程。
第二步&＃xff0c;加载Python的正则语言模块&＃xff08;re&＃xff09;和collections模块&＃xff0c;后面要用到。
import re, collections
第三步&＃xff0c;定义words()函数&＃xff0c;用来取出文本库的每一个词。
def words(text): return re.findall(&＃39;[a-z]&＃43;&＃39;, text.lower())
lower()将所有词都转成小写&＃xff0c;避免因为大小写不同&＃xff0c;而被算作两个词。
第四步&＃xff0c;定义一个train()函数&＃xff0c;用来建立一个"字典"结构。文本库的每一个词&＃xff0c;都是这个"字典"的键&＃xff1b;它们所对应的值&＃xff0c;就是这个词在文本库的出现频率。
def train(features):
model &＃61; collections.defaultdict(lambda: 1)
for f in features:
model[f] &＃43;&＃61; 1
return model
collections.defaultdict(lambda: 1)的意思是&＃xff0c;每一个词的默认出现频率为1。这是针对那些没有出现在文本库的词。如果一个词没有在文本库出现&＃xff0c;我们并不能认定它就是一个不存在的词&＃xff0c;因此将每个词出现的默认频率设为1。以后每出现一次&＃xff0c;频率就增加1。
第五步&＃xff0c;使用words()和train()函数&＃xff0c;生成上一步的"词频字典"&＃xff0c;放入变量NWORDS。
NWORDS &＃61; train(words(file(&＃39;big.txt&＃39;).read()))
第六步&＃xff0c;定义edits1()函数&＃xff0c;用来生成所有与输入参数word的"编辑距离"为1的词。
alphabet &＃61; &＃39;abcdefghijklmnopqrstuvwxyz&＃39;
def edits1(word):
splits &＃61; [(word[:i], word[i:]) for i in range(len(word) &＃43; 1)]
deletes &＃61; [a &＃43; b[1:] for a, b in splits if b]
transposes &＃61; [a &＃43; b[1] &＃43; b[0] &＃43; b[2:] for a, b in splits if len(b)>1]
replaces &＃61; [a &＃43; c &＃43; b[1:] for a, b in splits for c in alphabet if b]
inserts &＃61; [a &＃43; c &＃43; b for a, b in splits for c in alphabet]
return set(deletes &＃43; transposes &＃43; replaces &＃43; inserts)
edit1()函数中的几个变量的含义如下&＃xff1a;
&＃xff08;1&＃xff09;splits&＃xff1a;将word依次按照每一位分割成前后两半。比如&＃xff0c;&＃39;abc&＃39;会被分割成 [(&＃39;&＃39;, &＃39;abc&＃39;), (&＃39;a&＃39;, &＃39;bc&＃39;), (&＃39;ab&＃39;, &＃39;c&＃39;), (&＃39;abc&＃39;, &＃39;&＃39;)] 。
&＃xff08;2&＃xff09;beletes&＃xff1a;依次删除word的每一位后、所形成的所有新词。比如&＃xff0c;&＃39;abc&＃39;对应的deletes就是 [&＃39;bc&＃39;, &＃39;ac&＃39;, &＃39;ab&＃39;] 。
&＃xff08;3&＃xff09;transposes&＃xff1a;依次交换word的邻近两位&＃xff0c;所形成的所有新词。比如&＃xff0c;&＃39;abc&＃39;对应的transposes就是 [&＃39;bac&＃39;, &＃39;acb&＃39;] 。
&＃xff08;4&＃xff09;replaces&＃xff1a;将word的每一位依次替换成其他25个字母&＃xff0c;所形成的所有新词。比如&＃xff0c;&＃39;abc&＃39;对应的replaces就是 [&＃39;abc&＃39;, &＃39;bbc&＃39;, &＃39;cbc&＃39;, ... , &＃39;abx&＃39;, &＃39; aby&＃39;, &＃39;abz&＃39; ] &＃xff0c;一共包含78个词&＃xff08;26 × 3&＃xff09;。
&＃xff08;5&＃xff09;inserts&＃xff1a;在word的邻近两位之间依次插入一个字母&＃xff0c;所形成的所有新词。比如&＃xff0c;&＃39;abc&＃39; 对应的inserts就是[&＃39;aabc&＃39;, &＃39;babc&＃39;, &＃39;cabc&＃39;, ..., &＃39;abcx&＃39;, &＃39;abcy&＃39;, &＃39;abcz&＃39;]&＃xff0c;一共包含104个词&＃xff08;26 × 4&＃xff09;。
最后&＃xff0c;edit1()返回deletes、transposes、replaces、inserts的合集&＃xff0c;这就是与word"编辑距离"等于1的所有词。对于一个n位的词&＃xff0c;会返回54n&＃43;25个词。
第七步&＃xff0c;定义edit2()函数&＃xff0c;用来生成所有与word的"编辑距离"为2的词语。
def edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1))
但是这样的话&＃xff0c;会返回一个 (54n&＃43;25) * (54n&＃43;25) 的数组&＃xff0c;实在是太大了。因此&＃xff0c;我们将edit2()改为known_edits2()函数&＃xff0c;将返回的词限定为在文本库中出现过的词。
def known_edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)
第八步&＃xff0c;定义correct()函数&＃xff0c;用来从所有备选的词中&＃xff0c;选出用户最可能想要拼写的词。
def known(words): return set(w for w in words if w in NWORDS)
def correct(word):
candidates &＃61; known([word]) or known(edits1(word)) or known_edits2(word) or [word]
return max(candidates, key&＃61;NWORDS.get)
我们采用的规则为&＃xff1a;
&＃xff08;1&＃xff09;如果word是文本库现有的词&＃xff0c;说明该词拼写正确&＃xff0c;直接返回这个词&＃xff1b;
&＃xff08;2&＃xff09;如果word不是现有的词&＃xff0c;则返回"编辑距离"为1的词之中&＃xff0c;在文本库出现频率最高的那个词&＃xff1b;
&＃xff08;3&＃xff09;如果"编辑距离"为1的词&＃xff0c;都不是文本库现有的词&＃xff0c;则返回"编辑距离"为2的词中&＃xff0c;出现频率最高的那个词&＃xff1b;
&＃xff08;4&＃xff09;如果上述三条规则&＃xff0c;都无法得到结果&＃xff0c;则直接返回word。
至此&＃xff0c;代码全部完成&＃xff0c;合起来一共21行。
import re, collections
def words(text): return re.findall(&＃39;[a-z]&＃43;&＃39;, text.lower())
def train(features):
model &＃61; collections.defaultdict(lambda: 1)
for f in features:
model[f] &＃43;&＃61; 1
return model
NWORDS &＃61; train(words(file(&＃39;big.txt&＃39;).read()))
alphabet &＃61; &＃39;abcdefghijklmnopqrstuvwxyz&＃39;
def edits1(word):
splits &＃61; [(word[:i], word[i:]) for i in range(len(word) &＃43; 1)]
deletes &＃61; [a &＃43; b[1:] for a, b in splits if b]
transposes &＃61; [a &＃43; b[1] &＃43; b[0] &＃43; b[2:] for a, b in splits if len(b)>1]
replaces &＃61; [a &＃43; c &＃43; b[1:] for a, b in splits for c in alphabet if b]
inserts &＃61; [a &＃43; c &＃43; b for a, b in splits for c in alphabet]
return set(deletes &＃43; transposes &＃43; replaces &＃43; inserts)
def known_edits2(word):
return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)
def known(words): return set(w for w in words if w in NWORDS)
def correct(word):
candidates &＃61; known([word]) or known(edits1(word)) or known_edits2(word) or [word]
return max(candidates, key&＃61;NWORDS.get)
使用方法如下&＃xff1a;
>>> correct(&＃39;speling&＃39;)
&＃39;spelling&＃39;
>>> correct(&＃39;korrecter&＃39;)
&＃39;corrector&＃39;
四、缺陷
我们使用的这种算法&＃xff0c;有一些缺陷&＃xff0c;如果投入生产环境&＃xff0c;必须在这些方面加入改进。
&＃xff08;1&＃xff09;文本库必须有很高的精确性&＃xff0c;不能包含拼写错误的词。
如果用户输入一个错误的拼法&＃xff0c;文本库恰好包含了这种拼法&＃xff0c;它就会被当成正确的拼法。
&＃xff08;2&＃xff09;对于不包含在文本库中的新词&＃xff0c;没有提出解决办法。
如果用户输入一个新词&＃xff0c;这个词不在文本库之中&＃xff0c;就会被当作错误的拼写进行纠正。
&＃xff08;3&＃xff09;程序返回的是"编辑距离"为1的词&＃xff0c;但某些情况下&＃xff0c;正确的词的"编辑距离"为2。
比如&＃xff0c;用户输入reciet&＃xff0c;会被纠正为recite&＃xff08;编辑距离为1&＃xff09;,但用户真正想要输入的词是receipt&＃xff08;编辑距离为2&＃xff09;。也就是说&＃xff0c;"编辑距离"越短越正确的规则&＃xff0c;并非所有情况下都成立。
&＃xff08;4&＃xff09;有些常见拼写错误的"编辑距离"大于2。
这样的错误&＃xff0c;程序无法发现。下面就是一些例子&＃xff0c;每一行前面那个词是正确的拼法&＃xff0c;后面那个则是常见的错误拼法。
purple perpul
curtains courtens
minutes muinets
successful sucssuful
inefficient ineffiect
availability avaiblity
dissension desention
unnecessarily unessasarily
necessary nessasary
unnecessary unessessay
night nite
assessing accesing
necessitates nessisitates
&＃xff08;5&＃xff09;用户输入的词的拼写正确&＃xff0c;但是其实想输入的是另一个词。
比如&＃xff0c;用户输入是where&＃xff0c;这个词拼写正确&＃xff0c;程序不会纠正。但是&＃xff0c;用户真正想输入的其实是were&＃xff0c;不小心多打了一个h。
&＃xff08;6&＃xff09;程序返回的是出现频率最高的词&＃xff0c;但用户真正想输入的是另一个词。
比如&＃xff0c;用户输入ther&＃xff0c;程序会返回the&＃xff0c;因为它的出现频率最高。但是&＃xff0c;用户真正想输入的其实是their&＃xff0c;少打了一个i。也就是说&＃xff0c;出现频率最高的词&＃xff0c;不一定就是用户想输入的词。
&＃xff08;7&＃xff09;某些词有不同的拼法&＃xff0c;程序无法辨别。
比如&＃xff0c;英国英语和美国英语的拼法不一致。英国用户输入&＃39;humur&＃39;&＃xff0c;应该被纠正为&＃39;humour&＃39;&＃xff1b;美国用户输入&＃39;humur&＃39;&＃xff0c;应该被纠正为&＃39;humor&＃39;。但是&＃xff0c;我们的程序会统一纠正为&＃39;humor&＃39;。
&＃xff08;完&＃xff09;
京公网安备 11010802041100号