更好的贝叶斯过滤

2003年1月

(本文是在2003年垃圾邮件会议上发表的演讲。 它描述了我为提高 在A Plan for Spam中描述的算法性能所做的工作， 以及我未来的计划。)

我想在这里介绍的第一个发现是一个用于 懒惰评估研究论文的算法。只需 写下你想写的内容，而不引用任何先前的工作，愤怒的读者会给你发送所有你 应该引用的论文的参考文献。我是在``A Plan for Spam'' [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的技术正交； 一个最佳解决方案可能会结合两者。

``A Plan for Spam''使用了一个非常简单的 标记定义。字母、数字、破折号、撇号， 和美元符号是组成字符，其他所有的都是标记分隔符。我也忽略了大小写。

现在我有了一个更复杂的标记定义：

保留大小写。

感叹号是组成字符。

如果句点和逗号出现在两个数字之间，则它们是组成字符。这让我可以完整地获取IP地址 和价格。

像$20-25这样的价格范围产生两个标记， $20和$25。

在To、From、Subject和Return-Path行内，或在网址内出现的标记， 会相应地被标记。例如，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

在Plan for Spam过滤器中，所有这些标记的概率都是 相同的，0.7602。该过滤器识别了大约23,000 个标记。当前的过滤器识别了大约187,000个。

拥有更大标记宇宙的缺点是 错过的机会更多。 将你的语料库分散到更多标记上 与使其变小的效果相同。 例如，如果你将感叹号视为 组成字符，那么你可能最终没有 对于带有七个感叹号的free的垃圾邮件概率，即使你知道只有两个 感叹号的free的概率为99.99%。

解决这个问题的一种方法是我称之为退化。如果你 找不到标记的确切匹配， 就将其视为较不具体的 版本。我认为终端感叹号、大写字母，以及出现在五个标记上下文中的标记使其更具体。 例如，如果我没有找到Subject*free!''的概率，我会寻找 Subject*free''、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'' （意味着在网址内的``optmails''）出现1223次。 然而，当我用来计算标记概率时， 这两个标记的垃圾邮件概率都是0.99的阈值。

这感觉不对。对于这两个标记给予实质上不同的 概率有理论上的理由（Pantel和Lin确实这样做），但我还没有尝试过。 至少似乎如果我们发现超过15个 只出现在一个语料库中的标记，我们应该 优先考虑出现频率高的标记。因此，现在有两个阈值。对于只出现在垃圾邮件语料库中的标记，如果它们 出现超过10次，概率为0.9999，否则为0.9998。在合法语料库中只发现的标记也是如此。

我可能会在稍后大幅调整标记概率， 但至少这种微小的调整确保了 标记以正确的方式排序。

另一种可能性是考虑的不仅仅是 15个标记，而是所有超过某个 有趣程度阈值的标记。Steven Hauser在他的统计垃圾邮件过滤器中这样做 [8]。 如果你使用阈值，请将其设定得非常高，否则 垃圾邮件发送者可能会通过填充更多无辜的单词来欺骗你。

最后，应该如何处理html？我尝试了整个选项范围，从 忽略它到解析它所有的内容。忽略html是个坏主意， 因为它充满了有用的垃圾邮件迹象。但如果你解析 所有内容，你的过滤器可能会退化为一个简单的html 识别器。最有效的方法 似乎是中间路线，注意某些标记而忽略其他标记。我查看a、img和font标签，并忽略其余部分。链接和图像你当然应该查看，因为 它们包含网址。

我可能在处理html方面可以更聪明，但我 认为不值得花太多时间在这上面。 充满html的垃圾邮件很容易过滤。更聪明的 垃圾邮件发送者已经避免使用它。因此 未来的性能不应过多依赖于你 如何处理html。

性能

在2002年12月10日至2003年1月10日之间，我收到了大约 1750封垃圾邮件。 其中4封通过了。这是约99.75%的过滤 率。

我错过的四封垃圾邮件中有两封是因为它们 恰好使用了我合法电子邮件中常见的单词。

第三封是利用 不安全的cgi脚本向第三方发送邮件的那种。 仅仅根据内容很难过滤它们，因为头部是无辜的， 而且他们对所使用的单词非常小心。即便如此，我通常可以 捕获它们。这封邮件以0.88的概率侥幸通过，刚好低于0.9的阈值。

当然，查看多个标记序列 会轻松捕获它。``以下是 您的反馈表的结果''是一个明显的标志。

第四封垃圾邮件是我称之为 未来垃圾邮件的，因为这是我期望垃圾邮件 演变成的样子：一些完全中性的 文本后面跟着一个网址。在这种情况下，它是来自 某人说他们终于完成了他们的主页 我能否去看看。（该页面当然是一个 色情网站的广告。）

如果垃圾邮件发送者对头部非常小心并使用一个 新的网址，那么在未来的垃圾邮件中，过滤器 没有什么可以注意的。当然，我们可以通过发送一个 爬虫去查看页面来反击。但这可能不是必要的。 未来垃圾邮件的响应率必须 很低，否则每个人都会这样做。 如果它足够低， 它不会支付给垃圾邮件发送者发送它，我们就不必在过滤它上费太多力气。

现在是非常令人震惊的消息：在同一个一个月的 时间里，我收到了三个假阳性。

在某种程度上，得到一些假阳性是 一种解脱。当我写``A Plan for Spam''时，我没有遇到过假阳性，我不知道它们会是什么样子。现在我有了一些假阳性，我很高兴发现 它们并没有我想象的那么糟糕。 统计 过滤器产生的假阳性结果是听起来很像垃圾邮件的邮件，而 这些往往是你最不介意错过的邮件 [9]。

两个假阳性是来自我购买过商品的公司的新闻通讯。我从未 要求接收它们，因此可以说它们 是垃圾邮件，但我将它们视为假阳性，因为 我之前没有将它们删除为垃圾邮件。过滤器捕获它们的原因是这两家公司在 1月份切换到了商业电子邮件发送者 而不是从自己的服务器发送邮件， 因此头部和正文变得更加垃圾邮件化。

不过，第三个假阳性是一个糟糕的例子。它来自 埃及的某人，且全部为大写字母。这是 使标记区分大小写的直接结果；Plan for Spam过滤器不会捕获它。

很难说整体假阳性率是多少， 因为我们在噪声中，统计上。 任何在过滤器上工作过的人（至少是有效的过滤器）都会 意识到这个问题。 对于某些电子邮件， 很难说它们是否是垃圾邮件，而这些邮件 正是当你将过滤器设置得非常严格时你最终会查看的邮件。例如，到目前为止，过滤器捕获了两封因 拼写错误而发送到我地址的电子邮件，以及一封因为我被认为是 其他人而发送给我的邮件。可以说，这些既不是我的垃圾邮件 也不是我的非垃圾邮件。

另一个假阳性是来自Virtumundo的一位副总裁。 我假装是客户写信给他们， 由于回复通过Virtumundo的 邮件服务器返回，因此它具有最具指控性的 头部。可以说这也不是真正的假阳性，而是一种海森堡不确定性 效应：我之所以收到它是因为我在写关于垃圾邮件 过滤的内容。

不计算这些，我到目前为止总共收到了五个假阳性， 大约7740封合法电子邮件，假阳性率为0.06%。 另外两个是假通知，告知我购买的某样东西 缺货，以及来自Evite的聚会提醒。

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

在我看来，假阳性与 假阴性是不同类型的错误。 过滤率是性能的衡量标准。假阳性我认为更像是错误。 我将提高 过滤率视为优化，而减少假阳性视为调试。

因此，这五个假阳性是我的错误列表。例如， 来自埃及的邮件被捕获是因为大写文本 使其在过滤器中看起来像尼日利亚垃圾邮件。 这确实算是一种错误。与 html一样，电子邮件全部为大写实际上是概念上一个 特征，而不是每个单词一个特征。我需要以 更复杂的方式处理大小写。

那么，这0.06%该如何看待？我认为没什么。你可以 将其视为上限，考虑到样本量小。 但在这个阶段，它更像是我实现中的错误 而不是贝叶斯过滤的某种内在假阳性率。

未来

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

例如，垃圾邮件发送者现在正在积极工作以 规避过滤器，而他们正在做的事情之一是 拆分和拼写错误单词，以防止过滤器 识别它们。但在这方面工作并不是我的首要任务，因为我仍然没有问题捕获这些 垃圾邮件 [10]。

我目前确实有两种类型的垃圾邮件 有麻烦。 一种是伪装成来自 女性的电子邮件，邀请你去与她聊天或查看她在约会 网站上的个人资料。这些邮件通过了，因为它们是唯一一种 可以不使用销售术语的销售推销。它们使用 与普通电子邮件相同的词汇。

我在过滤的另一种垃圾邮件是来自例如保加利亚的公司，提供合同编程 服务。这些邮件通过了，因为我也是程序员， 而且这些垃圾邮件充满了与我真实邮件相同的单词。

我可能会首先关注个人广告类型。我认为如果 我仔细观察，我将能够找到这些与我真实邮件之间的统计差异。写作风格 当然不同，尽管可能需要多词过滤 才能捕获这一点。 此外，我注意到它们往往重复网址， 而在合法邮件中包含网址的人不会这样做 [11]。

外包类型的垃圾邮件将很难捕获。即使 你发送爬虫到网站，你也不会找到明显的 统计证据。 也许唯一的答案是一个中央列表，列出 在垃圾邮件中宣传的域名 [12]。但这种类型的邮件不可能有那么多。如果剩下的唯一 垃圾邮件是来自保加利亚的合同编程 服务的未经请求的报价，我们可能都可以转向 处理其他事情。

统计过滤真的能让我们达到那个点吗？ 我不知道。对我个人而言，垃圾邮件 现在不是问题。但垃圾邮件发送者尚未认真 努力伪造统计过滤器。那他们这样做时会发生什么？

我对在 网络层面工作的过滤器并不乐观 [13]。 当有一个值得克服的静态障碍时，垃圾邮件发送者 在克服它方面非常高效。 已经有一家名为Assurance Systems的公司会 通过Spamassassin运行你的邮件，并告诉你 它是否会被过滤掉。

网络级过滤器不会完全无用。 它们可能足以消灭所有“选择加入” 垃圾邮件，这意味着来自像Virtumundo和 Equalamail这样的公司声称他们实际上在运行选择加入列表的垃圾邮件。 你可以仅根据头部过滤这些，无论他们在正文中说什么。但任何愿意 伪造头部或使用开放转发的垃圾邮件发送者，显然包括 大多数色情垃圾邮件发送者，应该能够在他们想要的情况下让某些消息通过 网络级过滤器。（但绝对不是他们想要发送的消息，这是一回事。）

我对那种 根据每个用户的邮件计算概率的过滤器感到乐观。 这些过滤器可以更有效，不仅在 避免假阳性方面，而且在过滤方面：例如， 在消息中找到收件人的电子邮件地址的base-64编码是一个非常好的垃圾邮件指示器。

但个别过滤器的真正优势在于它们都是 不同的。如果每个人的过滤器具有不同的概率， 这将使垃圾邮件发送者的优化循环，程序员 所称的编辑-编译-测试周期，变得极其缓慢。 他们不仅仅是调整垃圾邮件，直到它通过他们桌面上的某个过滤器的副本，他们还必须为每个调整进行一次 测试邮件。这就像在没有交互式顶层的语言中编程， 我不希望任何人经历这种情况。

注释

[1] 保罗·格雷厄姆。 ``A Plan for Spam.'' 2002年8月。 http://paulgraham.com/spam.html。

该算法中的概率是 使用贝叶斯规则的退化情况计算的。存在 两个简化假设：特征（即单词）的概率 是独立的，并且我们对电子邮件是 垃圾邮件的先验概率一无所知。

第一个假设在文本分类中广泛存在。 使用它的算法被称为“天真的贝叶斯”。

我做第二个假设是因为我收到的垃圾邮件比例 在我的传入邮件中每天波动很大（实际上， 每小时波动），因此整体先验比例似乎 毫无价值作为预测。如果你假设P（垃圾邮件）和 P（非垃圾邮件）都是0.5，它们会相互抵消，你可以 将它们从公式中去掉。

如果你在垃圾邮件与非垃圾邮件的比例 始终非常高或（尤其）非常低的情况下进行贝叶斯过滤， 你可能会通过结合先验概率来改善过滤器 性能。要做到这一点，你必须按时间跟踪比例，因为 垃圾邮件和合法邮件的数量都有明显的日常 模式。

[2] 帕特里克·潘特尔和德康·林。 ``SpamCop-- 垃圾邮件 分类与组织程序。'' 1998年AAAI会议 文本分类学习研讨会的论文。

[3] 梅赫兰·萨哈米、苏珊·杜梅斯、戴维·赫克曼和埃里克·霍维茨。 ``一种贝叶斯方法过滤垃圾邮件。'' 1998年AAAI会议 文本分类学习研讨会的论文。

[4] 当时我在大约4000封 合法电子邮件中没有假阳性。如果下一封合法电子邮件是 假阳性，这将给我们0.03%。这些假阳性 率是不可靠的，正如我稍后解释的那样。我在这里引用 一个数字只是为了强调无论假阳性率 是多少，它都低于1.16%。

[5] 比尔·耶拉祖尼斯。 ``稀疏二进制多项式哈希消息 过滤和CRM114鉴别器。'' 2003年 垃圾邮件会议的论文。

[6] 在``A Plan for Spam''中，我使用了0.99和0.01的阈值。 使用与语料库大小成比例的阈值似乎是合理的。由于我现在大约有10,000封每种类型的邮件，我使用0.9999和0.0001。

[7] 这里有一个缺陷，我应该修复。目前， 当Subject*foo''退化为foo''时，这意味着 你正在获取foo''在 正文或头部行中出现的统计数据，而不是我标记的那些。 我应该跟踪foo'' 的整体统计数据以及特定版本，并从 Subject*foo''退化为Anywhere*foo''。对于 大小写也是如此：我应该从大写退化为任何大小写，而不是 小写。

对价格也这样做可能会有好处， 例如，从$129.99''退化为$--9.99''、$--.99'' 和$--''。

你也可以从单词退化为它们的词干， 但这可能只会在你拥有小语料库时提高过滤率。

[8] 史蒂文·豪泽。 ``统计垃圾邮件过滤器对我有效。'' http://www.sofbot.com。

[9] 假阳性并不都是平等的，我们在比较阻止垃圾邮件的技术时应该记住这一点。 虽然许多过滤器造成的假阳性 将是接近垃圾邮件的邮件，而你不会介意错过， 但例如，由黑名单造成的假阳性将只是 来自选择错误ISP的人的邮件。在这两种情况下，你捕获的是接近垃圾邮件的邮件，但对于黑名单来说，接近是物理上的，而对于过滤器来说是文本上的。

[10] 如果垃圾邮件发送者在模糊标记方面变得足够聪明以至于这成为问题，我们可以通过简单地删除 空格、句点、逗号等来回应，并使用字典从 结果序列中挑选出单词。 当然，以这种方式找到在 原始文本中不可见的单词本身就是垃圾邮件的证据。

挑选出单词并不简单。它需要 的不仅仅是重建单词边界；垃圾邮件发送者 既添加（xHot nPorn cSite''）又省略（P#rn''）字母。 视觉研究可能在这里有用，因为人类视觉是 这些把戏将接近的极限。

[11] 一般来说，垃圾邮件比普通电子邮件更具重复性。 他们想要强调这个信息。我目前不 允许在前15个标记中出现重复，因为 如果发件人恰好多次使用某个坏词，你可能会得到假阳性。（在我当前的过滤器中，``dick''的垃圾邮件概率为0.9999，但它也是一个名字。） 不过，我们至少应该注意到重复， 所以我可能会尝试允许每个标记最多出现两个，就像布赖恩·伯顿在 SpamProbe中所做的那样。

[12] 这就是像Brightmail这样的接近 一旦垃圾邮件发送者被迫使用疯狂的填空 技术生成消息中的其他所有内容时将退化成的样子。

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

历史上，稀缺资源的论点在软件设计辩论中一直处于失败的一方。 人们往往只会用它们来为 （特别是无所作为）做出的选择辩护。