更优贝叶斯滤波
2003年1月
（本文为作者在2003年垃圾邮件会议上的演讲稿。文中介绍了我在《垃圾邮件计划》所述算法性能改进方面所做的工作，以及未来的规划。）
我在这里想呈现的第一个发现，是一种实现研究论文懒加载的算法。只需随心所欲地撰写，不引用任何先前工作，那些愤愤不平的读者就会把该引用的所有论文都发给你。我在《垃圾邮件计划》[1]登上Slashdot之后发现了这一算法。
垃圾邮件过滤是文本分类的一个子领域，而文本分类早已是成熟学科，但专门针对贝叶斯垃圾邮件过滤的首批论文，似乎是1998年同一会议上发表的两篇，一篇来自Pantel和Lin [2]，另一篇出自微软研究院的一个团队[3]。
听闻这些工作后，我有些惊讶。如果人们四年前就已经涉足贝叶斯过滤，为什么没有人人都在使用它？当我读到那些论文时，我明白了其中缘由。Pantel和Lin的过滤器是两者中效果较好的，但也仅能拦截92%的垃圾邮件，误报率为1.16%。
而我尝试编写贝叶斯垃圾邮件过滤器时，它拦截了99.5%的垃圾邮件，误报率低于0.03% [4]。当两个人尝试同样的实验却得到大相径庭的结果时，总是令人警惕。这里尤其如此，因为这两组数字可能导向完全相反的结论。不同用户有不同需求，但我认为对许多人来说，92%的过滤率加上1.16%的误报率意味着过滤并非可接受的解决方案，而99.5%的过滤率加上低于0.03%的误报率则意味着可行。
那么为何我们得到了如此不同的数字？我并未尝试复现Pantel和Lin的结果，但通过阅读论文，我发现了可能造成差异的五个方面。
其一，他们的过滤器仅在非常少的数据上训练：160封垃圾邮件和466封非垃圾邮件。在如此小的数据集上，过滤器的性能应该仍在攀升。因此他们的数字甚至可能无法准确衡量其算法的性能，更不用说作为贝叶斯垃圾邮件过滤的普遍表现了。
但我认为最重要的差异可能是他们忽略了邮件头。对任何从事垃圾邮件过滤研究的人来说，这似乎是个反常的决定。然而在我最初尝试编写的过滤器中，我也忽略了邮件头。为什么？因为我想保持问题的简洁性。那时我对邮件头了解不多，觉得其中充满了杂乱信息。这里有个过滤器编写者应吸取的教训：不要忽略数据。你可能会觉得这个教训太过明显而不值一提，但我自己就不得不反复学习了好几次。
第三，Pantel和Lin对标记进行了词干还原，即将”mailing”和”mailed”都归约为词根”mail”。他们或许觉得由于语料库规模太小而不得不这样做，但若是如此，这是一种过早优化。
第四，他们计算概率的方式不同。他们使用了所有标记，而我仅使用最显著的15个。如果使用所有标记，往往会漏掉更长的垃圾邮件——那种讲述某人如何通过多层营销计划致富的完整人生故事。而且这种算法很容易被垃圾邮件发送者欺骗：只需加入一大段随机文本即可抵消垃圾邮件特征词。
最后，他们没有对误报进行偏置处理。我认为任何垃圾邮件过滤算法都应该有一个方便的旋钮，可以牺牲过滤率来降低误报率。我通过将非垃圾邮件语料库中的标记出现次数加倍来实现这一点。
我认为将垃圾邮件过滤纯粹视为文本分类问题并非好主意。你可以使用文本分类技术，但解决方案可以且应该反映这样一个事实：这些文本是电子邮件，尤其是垃圾邮件。电子邮件不只是文本，它有结构。垃圾邮件过滤也不仅仅是分类，因为误报的代价远高于漏报，应当将它们视为不同类型的错误。而且错误来源不仅仅是随机波动，还有活跃的垃圾邮件发送者在积极地试图攻破你的过滤器。
标记
在Slashdot那篇文章之后，我听说另一个项目是Bill Yerazunis的CRM114 [5]。这正是我刚才提到的设计原则的反例。它是一个纯粹的文本分类器，但效果惊人地出色，甚至不需要知道自己正在做垃圾邮件过滤，就能近乎完美地完成工作。
一旦我理解了CRM114的工作原理，就意识到我最终必然要从基于单词的过滤转向类似的方法。但我想，先看看用单词能走多远。答案是：出乎意料地远。
我主要致力于更智能的标记化。面对当前的垃圾邮件，我已能实现接近CRM114的过滤率。这些技术大多与Bill的方法正交；最优解可能结合两者。
《垃圾邮件计划》对标记的定义非常简单。字母、数字、连字符、撇号和美元符号为组成字符，其他一切均为标记分隔符。我还忽略了大小写。
现在我有了更复杂的标记定义：
保留大小写。
感叹号是组成字符。
句点和逗号如果出现在两个数字之间，则为组成字符。这样我可以完整提取IP地址和价格。
像$20-25这样的价格范围产生两个标记：$20和$25。
出现在收件人（To）、发件人（From）、主题（Subject）和回信路径（Return-Path）行或URL中的标记会被相应标注。例如，主题行中的”foo”变为”Subject*foo”。（星号可以是任何你不允许作为组成字符的字符。）
这些措施增加了过滤器的词汇量，使其更具辨别力。例如，在当前过滤器中，主题行中的”free”垃圾邮件概率为98%，而正文中同一标记的垃圾邮件概率仅为65%。
以下是当前的一些概率[6]：
SubjectFREE 0.9999 free!! 0.9999 Tofree 0.9998 Subjectfree 0.9782 free! 0.9199 Free 0.9198 Urlfree 0.9091 FREE 0.8747 From*free 0.7636 free 0.6546
在《垃圾邮件计划》的过滤器中，这些标记的概率都相同，为0.7602。那个过滤器识别约23,000个标记。当前的过滤器识别约187,000个标记。
更大的标记宇宙的劣势是漏掉的可能性增加。将语料库分散到更多标记上，效果等同于缩小语料库。例如，如果你将感叹号视为组成字符，那么即使你知道带两个感叹号的”free”概率为99.99%，也可能无法获得带七个感叹号的”free”的垃圾邮件概率。
一个解决方案是我所称的”退化”（degeneration）。如果找不到标记的精确匹配，就将其视为较不具体的版本。我将会话末尾的感叹号、大写字母以及出现在五个标记上下文之一视为使标记更具体。例如，如果找不到”Subjectfree!”的概率，我会查找”Subjectfree”、”free!”和”free”的概率，并取最远离0.5的那个。
当过滤器看到主题行中的”FREE!!!”但没有对应概率时，以下是考虑的备选项[7]：
SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free
如果这样做，务必考虑首字母大写的版本以及全大写和全小写版本。垃圾邮件往往包含更多祈使句，而祈使句的首词是动词。因此首字母大写的动词比全小写时有更高的垃圾邮件概率。在我的过滤器中，”Act”的垃圾邮件概率为98%，而”act”仅为62%。
如果增加过滤器的词汇量，按照旧的”相同”定义，你会发现自己多次统计同一个单词。从逻辑上讲，它们已不再是同一个标记了。但如果这仍然困扰你，让我根据经验补充一句：那些看似被重复统计的单词，往往正是你希望被重复统计的。
更大词汇量的另一个效果是，检查来信时会发现更多有趣的标记，即概率远离0.5的标记。我用15个最有趣的标记来判断邮件是否为垃圾邮件。但使用这样的固定数字可能会遇到问题。如果找到大量极其有趣的标记，结果可能最终取决于决定同等有趣标记排序的随机因素。一种处理方式是将某些标记视为比其他标记更有趣。
例如，标记”dalco”在垃圾邮件语料库中出现3次，在合法邮件语料库中从不出现。标记”Url*optmails”（即URL中的”optmails”）出现1223次。然而，按照我过去计算标记概率的方式，两者的垃圾邮件概率相同，都是0.99的阈值。
这感觉不太对劲。理论上应该给这两个标记显著不同的概率（Pantel和Lin就是这么做的），但我尚未尝试。至少似乎应该这样：如果我们找到超过15个仅出现在一个语料库中的标记，应该优先考虑出现频率高的那些。所以现在有两个阈值。对于仅出现在垃圾邮件语料库中的标记，如果出现超过10次，概率为0.9999，否则为0.9998。在另一端，对于仅出现在合法语料库中的标记也同理。
我可能之后会大幅调整标记概率，但这点微调至少确保了标记按正确方式排序。
另一个可能性是不仅考虑15个标记，而是考虑所有超过某个有趣度阈值的标记。Steven Hauser在他的统计垃圾邮件过滤器[8]中就这么做。如果使用阈值，务必设得很高，否则垃圾邮件发送者可以通过塞入更多无害词汇来欺骗你。
最后，如何处理html？我尝试了从完全忽略到完全解析的所有选项。忽略html是个糟糕的主意，因为它充满了有用的垃圾邮件特征。但如果全部解析，过滤器可能会退化为纯粹的html识别器。最有效的方法似乎是中间路线：注意某些标记而忽略其他。我查看a、img和font标签，忽略其余。链接和图片当然应该查看，因为它们包含URL。
我或许可以在处理html方面更聪明些，但我觉得不值得投入大量时间。充满html的垃圾邮件很容易过滤。聪明的垃圾邮件发送者已经在避免使用它了。因此未来的性能不应太依赖于如何处理html。
性能
从2002年12月10日到2003年1月10日，我收到了约1750封垃圾邮件。其中4封漏掉了。过滤率约为99.75%。
漏掉的四封垃圾邮件中有两封之所以漏网，是因为它们恰好使用了我的合法邮件中经常出现的词汇。
第三封属于利用不安全的cgi脚本向第三方发送邮件的类型。这类邮件仅基于内容很难过滤，因为邮件头是清白的，而且用词谨慎。即便如此，我通常也能抓住它们。这一封以0.88的概率勉强通过，刚好低于0.9的阈值。
当然，如果查看多标记序列，就能轻易抓住它。”Below is the result of your feedback form”（以下是你反馈表单的结果）一看就是明显的破绽。
第四封垃圾邮件我称之为“未来垃圾邮件”，因为这是我预期垃圾邮件会演变成的样子：一段完全中性的文字后跟一个网址。这封邮件来自某个人，说来信者终于完成了他的主页，希望我去看看。（那个页面自然是某个色情网站的广告。）
如果垃圾邮件发送者在邮件头上下功夫并使用全新的网址，那么“未来垃圾邮件”里就没有任何东西能让过滤器注意到。我们当然可以通过派送爬虫去查看页面来应对，但这或许并无必要。“未来垃圾邮件”的回应率想必很低，否则大家都会这么干。如果回应率低到一定程度，垃圾邮件发送者觉得无利可图，我们也就无需费力去过滤了。
接下来是真正令人震惊的消息：在那同一月份里，我收到了三个误报。
某种程度上，遇到一些误报反而让人松了口气。当我写《垃圾邮件计划》时，我没有任何误报，也不知道它们会是什么样子。现在我有了一些误报，发现它们并没有我担心的那么糟糕，这让我感到宽慰。统计过滤器产生的误报，往往是那些听起来很像垃圾邮件的邮件，而这些恰恰是你最不介意错过的那些[9]。
其中两个误报是我购买过东西的公司发来的新闻通讯。我从未要求接收这些邮件，因此严格来说它们也算是垃圾邮件，但我之所以将其视为误报，是因为以前我并没有把它们当作垃圾邮件删除。过滤器捕捉到它们的原因是这两家公司在一月份都转向了商业邮件发送服务，而非使用自己的服务器发送邮件，导致邮件头和正文都变得更加像垃圾邮件。
不过第三个误报情况比较糟糕。它来自埃及的某个人，且全是大写字母。这直接源于我将词条处理为区分大小写；《垃圾邮件计划》中的过滤器本不会捕捉到它。
很难说整体误报率是多少，因为从统计数据来看，我们已经处于噪声之中。任何从事过滤器工作（至少是有效过滤器）的人都会意识到这个问题。对于某些邮件，很难判断它们是否是垃圾邮件，而当你将过滤器调得非常严格时，最终你不得不查看的正是这些邮件。例如，到目前为止，过滤器捕捉到两封因拼写错误而误发到我地址的邮件，以及一封误以为我是别人而发给我的邮件。严格来说，这些既不算我的垃圾邮件，也不算我的正常邮件。
另一个误报来自Virtumundo公司的一位副总裁。我假装成客户给他们写信，由于回复经由Virtumundo的邮件服务器返回，其邮件头具有最可疑的特征。严格来说这也不算真正的误报，而是一种海森堡不确定性效应：我之所以收到它，仅仅是因为我正在写关于垃圾邮件过滤的文章。
不计这些，到目前为止，我总共遇到了五个误报，而合法邮件约有7740封，误报率为0.06%。另外两个误报分别是一封关于我购买的商品缺货待补的通知，以及一封来自Evite的派对提醒。
我认为这个数字并不可靠，一方面因为样本太小，另一方面因为我认为我可以调整过滤器以避免捕捉到其中一些邮件。
在我看来，误报与漏报是不同的错误类型。过滤率是性能的衡量标准。误报在我看来更像是缺陷。我将提高过滤率视为优化，而将减少误报视为调试。
所以这五个误报就是我的缺陷列表。例如，那封来自埃及的邮件因为全大写文本让过滤器看起来像尼日利亚垃圾邮件而被捕捉。这确实是一种缺陷。与HTML类似，邮件全大写实际上概念上应视为一个特征，而非每个单词一个特征。我需要以更精细的方式处理大小写问题。
那么如何解读这0.06%呢？我认为意义不大。你可以将其视为一个上限，同时记住样本量很小。但在现阶段，这更多地反映了我实现中的缺陷，而非贝叶斯过滤固有的误报率。
未来
接下来怎么办？过滤是一个优化问题，而优化的关键在于性能剖析。不要试图猜测代码哪里慢，因为你会猜错。要观察代码哪里慢，然后修复那里。在过滤中，这转化为：检查你漏掉的垃圾邮件，弄清楚本可以做些什么来捕捉它们。
例如，垃圾邮件发送者现在正积极规避过滤器，他们采取的手段之一是拆分单词和故意拼错，以防止过滤器识别。但解决这个问题并非我的首要任务，因为我目前仍然能轻松捕捉这些垃圾邮件[10]。
目前我真正难以处理的有两类垃圾邮件。一类是伪装成女性发来的邮件，邀请你去聊天或查看她在约会网站上的资料。这些邮件之所以能通过，是因为它们是一种无需使用销售话术的推销方式，使用的词汇与普通邮件相同。
另一类难以过滤的垃圾邮件来自保加利亚等地的公司，提供外包编程服务。这些邮件能通过是因为我也是程序员，这些垃圾邮件中充满了与我正常邮件相同的词汇。
我可能会首先专注于处理个人广告类垃圾邮件。我想如果仔细观察，我会发现它们与我的正常邮件之间存在统计差异。写作风格肯定不同，尽管可能需要多词过滤才能捕捉到这一点。此外，我注意到它们倾向于重复网址，而正常邮件中包含网址的人不会这样做[11]。
外包服务类垃圾邮件将很难捕捉。即使你派爬虫去查看网站，也找不到统计上的确凿证据。也许唯一的答案是一个集中管理垃圾邮件中广告域名的列表[12]。但这种类型的邮件数量不可能那么多。如果剩下的垃圾邮件只是来自保加利亚的主动提供的合同编程服务，我们大概都可以转而处理其他事情了。
统计过滤真的能让我们达到那个地步吗？我不知道。目前，就我个人而言，垃圾邮件不是问题。但垃圾邮件发送者尚未认真尝试欺骗统计过滤器。当他们这样做时会发生什么？
我对在网络层面工作的过滤器并不乐观[13]。当有值得绕过的静态障碍时，垃圾邮件发送者绕过它的效率相当高。已经有一家名为Assurance Systems的公司，可以让你的邮件通过Spamassassin检测，并告诉你它是否会被过滤掉。
网络层面的过滤器并非完全无用。它们可能足以消灭所有“选择加入”垃圾邮件，即来自像Virtumundo和Equalamail这样声称真正运营选择加入列表的公司的垃圾邮件。无论正文说什么，你仅基于邮件头就可以过滤这些邮件。但任何愿意伪造邮件头或使用开放中继的人，大概包括大多数色情垃圾邮件发送者，只要他们愿意，应该都能设法让某些邮件绕过网络层面的过滤器。（不过绝不是他们本来想发送的那种邮件，这总算有点安慰。）
我持乐观态度的过滤器类型是基于每个用户个人邮件计算概率的过滤器。这些过滤器可以更加有效，不仅在避免误报方面，在过滤效果上也是如此：例如，在邮件中任何位置发现收件人邮箱地址的Base64编码，就是一个很好的垃圾邮件指标。
但个人过滤器的真正优势在于它们各自不同。如果每个人的过滤器都有不同的概率，这将使垃圾邮件发送者的优化循环，即程序员所谓的编辑-编译-测试周期，变得极其缓慢。他们不能只是微调一封垃圾邮件，直到它通过他们桌面上的某个过滤器副本，而必须为每次微调进行一次测试发送。这就像用一种没有交互式顶层的语言编程，我不希望任何人经历那种痛苦。
注释
[1] Paul Graham. 《垃圾邮件计划》. 2002年8月. http://paulgraham.com/spam.html.
该算法中的概率计算使用了贝叶斯规则的一个退化情形。有两个简化假设：特征（即单词）的概率是独立的，并且我们对一封邮件是垃圾邮件的先验概率一无所知。
第一个假设在文本分类中很常见。使用该假设的算法被称为“朴素贝叶斯”。
第二个假设是因为我收到的邮件中垃圾邮件的比例每天（甚至每小时）波动很大，以至于整体先验比例作为预测指标似乎毫无价值。如果你假设P(垃圾)和P(非垃圾)都是0.5，它们会相互抵消，可以从公式中移除。
如果你在垃圾邮件与非垃圾邮件比例持续非常高或（尤其是）非常低的情况下使用贝叶斯过滤，那么引入先验概率可能会提高过滤器性能。要做到这一点，你必须按一天中的时间段跟踪比例，因为垃圾邮件和合法邮件的数量都有各自明显的每日模式。
[2] Patrick Pantel 和 Dekang Lin. “SpamCop—— 垃圾邮件分类与组织程序.” 收录于AAAI-98文本分类学习研讨会论文集.
[3] Mehran Sahami, Susan Dumais, David Heckerman 和 Eric Horvitz. “过滤垃圾邮件的贝叶斯方法.” 收录于AAAI-98文本分类学习研讨会论文集.
[4] 当时我在约4000封合法邮件中有零误报。如果下一封合法邮件被误报，那将得到0.03%。正如我稍后解释的，这些误报率都不可靠。我在这里引用一个数字只是为了强调无论误报率是多少，它都低于1.16%。
[5] Bill Yerazunis. “稀疏二元多项式哈希消息过滤及CRM114判别器.” 收录于2003年垃圾邮件会议论文集.
[6] 在《垃圾邮件计划》中，我使用了0.99和0.01的阈值。使用与语料库规模成比例的阈值似乎更加合理。由于我现在每种类型的邮件都有约10,000封，我使用0.9999和0.0001。
[7] 这里有一个我可能应该修复的缺陷。目前，当“Subjectfoo”退化为仅“foo”时，意味着你得到的是“foo”在正文或未标记的邮件头行中出现次数的统计数据。我应该做的是跟踪“foo”整体以及具体版本的统计数据，并从“Subjectfoo”退化为“Anywhere*foo”而非“foo”。大小写处理也同理：我应该从大写退化为任意大小写，而不是小写。
对价格也这样做可能会有好处，比如从“$129.99”退化为“$–9.99”、“$–.99”和“$–”。
你也可以从单词退化为词干，但这可能只在语料库较小的早期阶段才会提高过滤率。
[8] Steven Hauser. “统计垃圾邮件过滤对我有效.” http://www.sofbot.com.
[9] 误报并不都是等同的，在比较阻止垃圾邮件的方法时我们应该记住这一点。过滤器造成的大量误报将是你不会介意错过的接近垃圾邮件的邮件，而黑名单造成的误报则只是来自选错ISP的人们的邮件。两种情况都是捕捉到接近垃圾邮件的邮件，但对黑名单而言，接近是物理上的，而对过滤器而言则是文本上的。
[10] 如果垃圾邮件发送者变得足够擅长混淆词条以至于这成为问题，我们可以通过简单移除空白、句点、逗号等，然后使用词典从结果序列中识别单词来应对。当然，以这种方式找到在原始文本中不可见的单词本身就能作为垃圾邮件的证据。
挑选出这些词语并非易事。这不仅仅是重构词边界那么简单；垃圾邮件发送者既会添加（如“xHot nPorn cSite”）也会省略（如“P#rn”）字母。视觉研究或许在此有所助益，因为人类视觉正是此类伎俩所逼近的极限。
[11] 总体而言，垃圾邮件比常规邮件更具重复性。它们旨在强化信息传递。目前，我在前15个令牌中不允许重复，因为如果发件人恰好多次使用了某个不良词汇，可能会造成误报。（在我当前的过滤器中，“dick”的垃圾邮件概率为0.9999，但它同时也是一个名字。）不过，我们似乎至少应当注意到重复现象，因此我可能会尝试允许每个令牌出现至多两次，正如Brian Burton在SpamProbe中所做的那样。
[12] 一旦垃圾邮件发送者被迫采用“疯狂填词”技术来生成邮件中的其他内容，类似Brightmail的方法就会退化至此。
[13] 有时人们会争论说，我们应当在网络层面进行过滤，因为这样效率更高。当人们这样说时，通常意味着：我们目前已在网络层面进行过滤，且不愿从头再来。但你不能为了适应自己的解决方案而强行规定问题。
从历史上看，在软件设计的辩论中，关于稀缺资源的论点往往处于下风。人们通常只用它来为由其他原因做出的选择（尤其是不作为）进行辩护。