更好的贝叶斯过滤

2003年1月

（本文是2003年垃圾邮件会议上的演讲稿。它描述了我为改进垃圾邮件过滤方案中描述的算法性能所做的工作，以及我未来计划做的事情。）

我想在这里介绍的第一个发现是一种用于研究论文的惰性评估算法。只需写下你想要的任何内容，不要引用任何以前的工作，愤慨的读者会向你发送你应该引用的所有论文的参考文献。在``垃圾邮件过滤方案'' [1] 登上Slashdot之后，我发现了这个算法。

垃圾邮件过滤是文本分类的一个子集，这是一个成熟的领域，但是关于贝叶斯垃圾邮件过滤本身的第一批论文似乎是1998年在同一个会议上发表的两篇，一篇是Pantel和Lin [2]的，另一篇是来自Microsoft Research [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的技术大多是正交的；一个最佳的解决方案可能会结合两者。

``垃圾邮件过滤方案''使用了一个非常简单的词条定义。字母、数字、破折号、撇号和美元符号是组成字符，其他一切都是词条分隔符。我也忽略了大小写。

现在我对词条有一个更复杂的定义：

1. 保留大小写。

2. 感叹号是组成字符。

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

4. 像$20-25这样的价格范围会产生两个词条，$20和$25。

5. 出现在To、From、Subject和Return-Path行中，或在URL中的词条，会相应地被标记。例如，Subject行中的foo''变为Subject*foo''。（星号可以是你不允许作为组成部分的任何字符。）

这些措施增加了过滤器的词汇量，使其更具辨别力。例如，在当前的过滤器中，Subject行中的``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的垃圾邮件概率，即使你知道带有两个感叹号的free的概率为99.99％。

解决这个问题的一个方法是我称之为退化。如果你找不到词条的完全匹配项，则将其视为不太具体的版本。我认为终端感叹号、大写字母以及出现在五个标记的上下文中的任何一个都使词条更具体。例如，如果我找不到Subject*free!''的概率，我会查找Subject*free''、free!''和free''的概率，并选择离0.5最远的一个。

如果过滤器在Subject行中看到``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的阈值。

当然，查看多个词条序列可以很容易地抓住它。``以下是你的反馈表的结果''是一个即时暴露。

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

如果垃圾邮件发送者对邮件头很小心并使用新的URL，那么未来垃圾邮件中没有任何过滤器可以注意到的东西。我们当然可以通过发送一个爬虫来查看该页面来反击。但这可能没有必要。未来垃圾邮件的回复率一定很低，否则每个人都会这样做。如果它足够低，垃圾邮件发送者就不会为此付出代价，我们也不必努力过滤它。

现在是真正令人震惊的消息：在同一个月的时间里，我收到了_三_个误报。

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

两个误报是我从购买过东西的公司收到的新闻通讯。我从未要求收到它们，因此可以说它们是垃圾邮件，但我将它们视为误报，因为我以前没有将它们作为垃圾邮件删除。过滤器抓住它们的原因是，这两家公司在1月份都改用商业电子邮件发送者，而不是从他们自己的服务器发送邮件，并且邮件头和正文都变得更加垃圾。

第三个误报很糟糕。它来自埃及的某个人，并且全部用大写字母书写。这是使词条区分大小写的直接结果；垃圾邮件过滤方案过滤器不会抓住它。

很难说总体误报率是多少，因为我们在统计上处于噪声中。任何从事过滤器（至少是有效过滤器）工作的人都会意识到这个问题。对于某些电子邮件，很难说它们是否是垃圾邮件，而这些邮件是你最终在过滤器真正收紧时查看的邮件。例如，到目前为止，该过滤器已经抓住了两封由于拼写错误而发送到我的地址的电子邮件，以及一封认为我是其他人的电子邮件。可以说，这些既不是我的垃圾邮件，也不是我的非垃圾邮件。

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

不算这些，到目前为止，我总共收到了五个误报，在约7740封合法电子邮件中，误报率为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] 这里有一个我可能应该修复的缺陷。目前，当“Subjectfoo”退化为仅“foo”时，这意味着你正在获得“foo”在正文或邮件头行（而不是我标记的那些）中出现的统计信息。我应该做的是跟踪“foo”的总体统计信息以及特定版本，并且从“Subjectfoo”退化不是到“foo”而是到“Anywhere*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] 一旦垃圾邮件发送者被迫使用疯狂的lib技术来生成消息中的其他所有内容，像Brightmail这样的方法将退化为这种方法。

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

从历史上看，稀缺资源论点一直是关于软件设计辩论中的失败方。人们往往只使用它们来证明出于其他原因（特别是无所作为）所做的选择。

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

相关：