更好的贝叶斯过滤

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'' and mailed'' 都简化为词根“mail”。他们可能觉得他们被迫这样做是因为他们的语料库规模太小，但如果是这样的话，这是一种过早的优化。

第四，他们计算概率的方式不同。他们使用了所有标记，而我只使用了最重要的 15 个标记。如果你使用所有标记，你就会错过较长的垃圾邮件，这种垃圾邮件中有人会告诉你他们的生活故事，直到他们通过某种多层次营销计划致富。而且这种算法很容易被垃圾邮件发送者欺骗：只需添加一大段随机文本来抵消垃圾邮件术语即可。

最后，它们不会对误报产生偏见。我认为任何垃圾邮件过滤算法都应该有一个方便的旋钮，你可以旋转它来降低误报率，但代价是过滤率。我通过对非垃圾邮件语料库中的标记出现次数进行双倍计数来实现这一点。

我认为将垃圾邮件过滤视为直接的文本分类问题不是一个好主意。您可以使用文本分类技术，但解决方案可以并且应该反映文本是电子邮件，特别是垃圾邮件的事实。电子邮件不仅仅是文本；它有结构。垃圾邮件过滤不仅仅是分类，因为误报比误报更糟糕，所以您应该将它们视为不同类型的错误。错误的来源不仅仅是随机变化，而是一个活跃的人类垃圾邮件发送者在积极地破坏您的过滤器。

代币

我在 Slashdot 文章之后听说的另一个项目是 Bill Yerazunis 的CRM114 [5]。这是与我刚才提到的设计原则相反的一个例子。它是一个纯文本分类器，但却非常有效，它几乎完美地过滤了垃圾邮件，甚至都不知道它在做什么。

在我理解了 CRM114 的工作原理后，我似乎不可避免地最终必须从基于单个单词的过滤转向这样的方法。但首先，我想看看我能用单个单词走多远。答案是，出乎意料的远。

我主要致力于更智能的标记化。对于当前的垃圾邮件，我已经能够实现接近 CRM114 的过滤率。这些技术与 Bill 的技术大体上是正交的；最佳解决方案可能结合了两者。

“垃圾邮件计划”对标记的定义非常简单。字母、数字、破折号、撇号和美元符号都是组成字符，其他所有字符都是标记分隔符。我还忽略了大小写。

现在我对令牌有了更复杂的定义：

案件得以保存。

感叹号是组成字符。

如果句号和逗号出现在两位数字之间，则它们属于组成部分。这样我就可以完整地获取 IP 地址和价格。

20-25 美元的价格范围会产生两种代币，分别为 20 美元和 25 美元。

出现在收件人、发件人、主题和返回路径行中或 URL 中的标记会进行相应标记。例如， foo'' in the Subject line becomes主题*foo''。（星号可以是任何您不允许作为组成部分的字符。）

这些措施增加了过滤器的词汇量，使其更具辨别力。例如，在当前过滤器中，主题行中的“免费”垃圾邮件概率为 98%，而正文中的相同标记垃圾邮件概率仅为 65%。

以下是当前的一些可能性[6]：

主题免费 0.9999 免费!! 0.9999 收件人免费 0.9998 主题免费 0.9782 免费! 0.9199 免费 0.9198 网址免费 0.9091 免费 0.8747 来自*免费 0.7636 免费 0.6546

在“垃圾邮件计划”过滤器中，所有这些标记的概率都相同，均为 0.7602。该过滤器识别了大约 23,000 个标记。当前过滤器识别了大约 187,000 个标记。

拥有更大范围的标记的缺点是，漏掉的几率更大。将语料库分散到更多标记上的效果与缩小语料库的效果相同。例如，如果您将感叹号视为组成部分，那么您可能最终无法计算出带有七个感叹号的 free 的垃圾邮件概率，即使您知道仅带有两个感叹号的 free 的概率为 99.99%。

解决此问题的一个方法是我所说的退化。如果您找不到与某个标记完全匹配的标记，请将其视为不太具体的版本。我认为结尾感叹号、大写字母以及出现在五个标记上下文之一中会使标记更具体。例如，如果我找不到 Subject*free!'' 的概率，我会查找 Subject*free''、 free!'', and free'' Subject*free!'', I look for probabilities for ，并取距离 .5 最远的那个。

如果过滤器在主题行中看到“免费！！！”并且没有概率，则会考虑以下替代方案[7]。

主题免费！！！主题免费！！！主题免费！主题免费！主题免费！主题免费主题免费主题免费主题免费免费！！！免费！！！免费！！！免费！免费！免费！免费！免费免费

如果您这样做，请务必考虑首字母大写以及全大写和全小写的版本。垃圾邮件往往包含更多祈使语气的句子，其中第一个单词是动词。因此首字母大写的动词比全小写的动词具有更高的垃圾邮件概率。在我的过滤器中， Act'' is 98% and for act'' 的垃圾邮件概率仅为 62%。

如果您增加过滤器的词汇量，您最终可能会多次计算同一个单词，这符合您对“相同”的旧定义。从逻辑上讲，它们不再是同一个标记。但如果这仍然困扰着您，让我根据经验补充一点，您似乎多次计算的单词往往正是您想要的单词。

词汇量更大的另一个影响是，当你查看收到的邮件时，你会发现更多有趣的标记，也就是那些概率远高于 0.5 的标记。我使用 15 个最有趣的标记来判断邮件是否为垃圾邮件。但是当你使用像这样的固定数字时，你可能会遇到问题。如果你发现很多最有趣的标记，结果可能最终由决定同样有趣的标记顺序的随机因素决定。处理这个问题的一种方法是将一些标记视为比其他标记更有趣。

例如，标记dalco'' occurs 3 times in my spam corpus and never in my legitimate corpus. The token 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 的阈值。

当然，查看多个标记序列就可以轻松发现它。“以下是您的反馈表的结果”是一个即时赠品。

第四封垃圾邮件是我所说的未来垃圾邮件，因为我认为垃圾邮件会演变成这样：一些完全中性的文本，后面跟着一个网址。在这种情况下，有人说他们终于完成了主页，问我是否愿意去看看。（该页面当然是色情网站的广告。）

如果垃圾邮件发送者对标头很谨慎，并使用新的 URL，那么未来的垃圾邮件就不会被过滤器注意到。我们当然可以通过发送爬虫来查看页面来反击。但这可能没有必要。未来垃圾邮件的响应率必须很低，否则每个人都会这样做。如果响应率足够低，垃圾邮件发送者发送它就不需要付费，我们也不必太费力地过滤它。

现在真正令人震惊的消息是：在同一个月内，我得到了三次假阳性。

在某种程度上，得到一些误报是一种解脱。当我写《垃圾邮件计划》时，我还没有得到任何误报，也不知道它们会是什么样子。现在我已经得到了一些，我很高兴地发现它们没有我担心的那么糟糕。统计过滤器产生的误报结果是听起来很像垃圾邮件的邮件，而这些邮件往往是你最不介意错过的邮件[9]。

其中两封误报来自我购买过商品的公司发来的新闻通讯。我从未要求接收它们，因此可以说它们是垃圾邮件，但我将它们算作误报，因为我之前没有将它们作为垃圾邮件删除。过滤器之所以能捕获它们，是因为这两家公司在 1 月份都改用商业电子邮件发送器，而不是从自己的服务器发送邮件，因此邮件头和正文都变得更加垃圾。

不过，第三个误报很糟糕。它来自埃及的某人，并且全部用大写字母书写。这是将标记设为区分大小写的直接结果；垃圾邮件过滤器计划不会捕获它。

很难说总体误报率是多少，因为从统计上看，我们处于噪音之中。任何使用过过滤器（至少是有效过滤器）的人都会意识到这个问题。有些电子邮件很难说它们是否是垃圾邮件，而这些正是您在过滤器非常严格时最终要查看的邮件。例如，到目前为止，过滤器已经捕获了两封由于输入错误而发送到我的地址的电子邮件，还有一封是我认为是别人而发送给我的。可以说，这些既不是我的垃圾邮件，也不是我的非垃圾邮件。

另一个误报来自 Virtumundo 的一位副总裁。我假装自己是客户给他们写信，由于回复是通过 Virtumundo 的邮件服务器发回的，所以回复的标题是最能说明问题的。可以说这也不是真正的误报，而是一种海森堡不确定性效应：我之所以收到它，只是因为我当时正在写有关垃圾邮件过滤的文章。

不算这些，到目前为止，我在大约 7740 封合法电子邮件中总共收到了 5 封误报，误报率为 0.06%。另外两封是通知我购买的某件商品缺货，以及 Evite 的派对提醒。

我认为这个数字不可信，部分原因是样本太小，部分原因是我认为我可以修复过滤器以免捕获其中的一些。

在我看来，误报是一种不同于误报的错误。过滤率是衡量性能的标准。我认为误报更像是错误。我认为提高过滤率是优化，降低误报是调试。

所以这五个误报就是我的错误列表。例如，来自埃及的邮件被拒收，因为大写文本让过滤器看起来像是尼日利亚垃圾邮件。这确实是一种错误。与 html 一样，电子邮件全部大写实际上是概念上的一个功能，而不是每个单词一个功能。我需要以更复杂的方式处理大小写。

那么，这个 0.06% 是怎么回事呢？我认为，没什么大不了的。考虑到样本量很小，你可以把它当作上限。但在这个阶段，它更多的是衡量我实现中的错误，而不是贝叶斯过滤的某些固有误报率。

未来

接下来做什么？过滤是一个优化问题，而优化的关键是分析。不要试图猜测代码在哪里运行缓慢，因为你会猜错。看看代码在哪里运行缓慢，然后修复它。在过滤中，这意味着：查看你错过的垃圾邮件，并找出你可以做些什么来捕获它们。

例如，垃圾邮件发送者现在正在努力逃避过滤器，他们所做的一件事就是拆分和拼写错误单词，以防止过滤器识别它们。但这不是我的首要任务，因为我仍然很容易就能发现这些垃圾邮件[10]。

目前有两种垃圾邮件让我很头疼。一种是假装是女性发来的电子邮件，邀请你去和她聊天或查看她在约会网站上的个人资料。这些垃圾邮件之所以能被识破，是因为它们是一种不用推销词就可以进行的推销方式。它们使用的词汇与普通电子邮件相同。

另一种让我难以过滤的垃圾邮件是来自保加利亚等提供合同编程服务的公司发来的垃圾邮件。这些垃圾邮件之所以能通过，是因为我也是程序员，而这些垃圾邮件里满满的都是和我的真实邮件一样的字眼。

我可能首先会关注个人广告类型。我认为如果我仔细观察，我就能发现这些邮件与我的真实邮件之间存在统计差异。写作风格肯定不同，尽管可能需要多词过滤才能发现这一点。此外，我注意到他们倾向于重复 URL，而在合法邮件中包含 URL 的人不会这样做 [11]。

外包类型的邮件很难抓到。即使你向该网站发送了爬虫，你也不会找到确凿的统计数据。也许唯一的答案是垃圾邮件中公布的域名中央列表 [12]。但这种邮件不会那么多。如果剩下的垃圾邮件都是保加利亚主动提供的合同编程服务，我们可能都会转而从事其他工作。

统计过滤真的能让我们达到这个程度吗？我不知道。目前，对我个人而言，垃圾邮件不是问题。但垃圾邮件发送者尚未认真努力欺骗统计过滤器。如果他们这样做，会发生什么？

我对在网络层工作的过滤器并不乐观[13]。当存在一个值得克服的静态障碍时，垃圾邮件发送者非常善于绕过它。目前已经有一家名为 Assurance Systems 的公司会将您的邮件通过 Spamassassin 并告诉您是否会将其过滤掉。

网络级过滤器并非完全无用。它们可能足以杀死所有“选择加入”垃圾邮件，即来自 Virtumundo 和 Equalamail 等公司声称他们确实在运行选择加入列表的垃圾邮件。您可以仅根据标题过滤这些垃圾邮件，而不管它们在正文中说了什么。但任何愿意伪造标题或使用开放中继的人（大概包括大多数色情垃圾邮件发送者）都应该能够让一些消息通过网络级过滤器（如果他们愿意的话）。（但绝不是他们想发送的消息，这很重要。）

我看好的过滤器是那些根据每个用户的邮件计算概率的过滤器。这些过滤器不仅能避免误报，还能过滤，因此效率更高：例如，在邮件的任何地方找到以 base-64 编码的收件人电子邮件地址就是很好的垃圾邮件指示器。

但单独使用过滤器的真正优势在于它们都是不同的。如果每个人的过滤器都有不同的概率，那么垃圾邮件发送者的优化循环（程序员称之为“编辑-编译-测试”循环）就会变得非常慢。他们不能只是调整垃圾邮件直到它通过他们桌面上的某个过滤器的副本，而是必须对每个调整进行测试。这就像使用一种没有交互式顶层的语言进行编程，我不希望任何人遇到这种情况。

笔记

[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] 当时，我在大约 4,000 封合法电子邮件中没有发现任何误报。如果下一封合法电子邮件是误报，那么误报率将为 0.03%。这些误报率不可信，我稍后会解释。我在这里引用一个数字只是为了强调，无论误报率是多少，它都低于 1.16%。

[5] Bill Yerazunis。“稀疏二进制多项式哈希消息过滤和 CRM114 鉴别器。”2003 年垃圾邮件会议论文集。

[6] 在《垃圾邮件计划》中，我使用了 0.99 和 0.01 的阈值。使用与语料库大小成比例的阈值似乎是合理的。由于我现在每种邮件的数量约为 10,000 封，因此我使用了 0.9999 和 0.0001。

[7] 这里有一个缺陷，我可能应该修复。目前，当Subject*foo'' degenerates to just foo'' 时，这意味着你正在获取foo'' in the body or header lines other than those I mark. What I should do is keep track of statistics for ，并且从Subject*foo'' not to退化为“Anywhere*foo”，而不是 foo''。大小写也一样：我应该从大写字母退化为任意大小写，而不是小写字母。

在价格方面也这样做可能也会有好处，例如从$129.99'' to降为 --9.99 美元、 $--.99'', and -- 美元。

您还可以从单词退化为其词干，但这可能只会在语料库较小时提高早期的过滤率。

[8] Steven Hauser.“统计垃圾邮件过滤器对我有用。”http://www.sofbot.com。

[9] 误报并不完全相同，我们在比较阻止垃圾邮件的技术时应该记住这一点。虽然过滤器造成的许多误报都是类似垃圾邮件的邮件，您不会介意错过，但黑名单等造成的误报只是来自选择了错误 ISP 的人的邮件。在这两种情况下，您都会捕获类似垃圾邮件的邮件，但对于黑名单来说，类似性是物理上的，而对于过滤器来说，类似性是文本上的。

[10] 如果垃圾邮件发送者能够熟练地隐藏标记，从而造成问题，我们可以采取简单的措施，删除空格、句号、逗号等，并使用字典从结果序列中挑选出单词。当然，以这种方式找到原始文本中看不到的单词本身就是垃圾邮件的证据。

挑选单词并非易事。它需要的不仅仅是重建单词边界；垃圾邮件发送者既添加（ xHot nPorn cSite'') and omit ( P#rn''）字母。视觉研究在这里可能很有用，因为人类视觉是此类技巧所能达到的极限。

[11] 一般而言，垃圾邮件比普通邮件更具有重复性。他们想让大家记住这个信息。我目前不允许前 15 个标记中出现重复，因为如果发件人碰巧多次使用某个脏话，您可能会得到误报。（在我目前的过滤器中，“dick”的垃圾邮件概率为 0.9999，但它也是一个名字。）不过，我们似乎至少应该注意到重复，所以我可能会尝试允许每个标记最多出现两个，就像 Brian Burton 在 SpamProbe 中所做的那样。

[12] 一旦垃圾邮件发送者被迫使用疯狂的技术来生成邮件中的其他所有内容，Brightmail 之类的方法就会退化成这种状况。

[13] 有人有时会说，我们应该在网络层面上进行过滤，因为这样效率更高。人们这样说的意思是：我们目前在网络层面进行过滤，我们不想从头开始。但你不能强迫问题适应你的解决方案。

从历史上看，稀缺资源论在软件设计辩论中一直是失败的一方。人们只倾向于用它们来证明出于其他原因而做出的选择（尤其是不作为）是合理的。

感谢Sarah Harlin、Trevor Blackwell 和 Dan Giffin 阅读本文草稿，并再次感谢 Dan 提供此过滤器运行的大部分基础设施。

有关的：

主题免费 0.9999 免费!! 0.9999 收件人免费 0.9998 主题免费 0.9782 免费! 0.9199 免费 0.9198 网址免费 0.9091 免费 0.8747 来自*免费 0.7636 免费 0.6546

主题免费！！！主题免费！！！主题免费！主题免费！主题免费！主题免费主题免费主题免费主题免费免费！！！免费！！！免费！！！免费！免费！免费！免费！免费免费