更好的贝叶斯过滤

2003年1月

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

我想在这里介绍的第一个发现是一个研究论文的懒人评估算法。只要写你想写的内容，不引用任何之前的工作，愤怒的读者就会给你发送所有你应该引用的论文的引用。我在"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行中，或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%的概率。

解决这个问题的一个方法是所谓的退化。如果你找不到标记的精确匹配，就把它当作一个不太具体的版本。我认为尾随感叹号、大写字母和在五个标记上下文中出现会使标记更具体。例如，如果我没有找到"Subjectfree!“的概率，我会寻找"Subjectfree”、“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的阈值。

当然，查看多个标记序列会很容易抓住它。“Below is the result of your feedback form"是一个即时的提示。

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

如果垃圾邮件发送者对邮件头很小心，使用一个新的URL，那么在未来的垃圾邮件中就没有什么可以让过滤器注意的。我们当然可以通过发送爬虫去看这个页面来应对。但这可能没有必要。未来垃圾邮件的响应率必须很低，否则每个人都会这样做。如果它足够低，垃圾邮件发送者发送它就不会有利可图，我们就不必太努力地过滤它。

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

在某种程度上，收到一些误报是一种解脱。当我写"A Plan for Spam"时，我还没有任何误报，我不知道它们会是什么样子。现在我有了几个，我很欣慰地发现它们没有我担心的那么糟糕。统计过滤器产生的误报往往是听起来很像垃圾邮件的邮件，这些往往是你最不介意错过的邮件 [9]。

两个误报是来自我买过东西的公司的通讯。我从未要求接收它们，所以可以说它们是垃圾邮件，但我把它们算作误报，因为我之前没有把它们作为垃圾邮件删除。过滤器抓住它们的原因是，这两家公司在1月份都改用商业邮件发送者而不是从他们自己的服务器发送邮件，邮件头和正文都变得垃圾邮件味十足。

第三个误报很糟糕，虽然。它来自埃及的某人，全部用大写字母写。这是使标记区分大小写的直接结果；垃圾邮件过滤计划过滤器不会抓住它。

很难说总体误报率是多少，因为我们在统计上处于噪声水平。任何从事过过滤器工作的人（至少是有效的过滤器）都会意识到这个问题。有些邮件很难说它们是垃圾邮件还是不是，当你把过滤器调得很紧时，你最终会看到这些邮件。例如，到目前为止，过滤器抓住了两封因为地址拼写错误而发送给我的邮件，还有一封因为相信我是别人而发送给我的邮件。可以说，这些既不是我的垃圾邮件也不是我的非垃圾邮件。

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

不算这些，到目前为止我总共有五个误报，来自约7740封合法邮件，0.06%的比率。另外两个是我买的东西缺货的通知，以及来自Evite的派对提醒。

我认为这个数字不能信任，部分是因为样本太小，部分是因为我认为我可以修复过滤器不抓住其中的一些。

误报对我来说是不同于漏报的错误类型。过滤率是性能的衡量标准。误报我更倾向于视为bug。我把提高过滤率视为优化，把减少误报视为调试。

所以这五个误报是我的bug列表。例如，来自埃及的邮件被抓住是因为大写文本让过滤器认为它像尼日利亚垃圾邮件。这确实有点像bug。就像html一样，邮件全部大写实际上是一个概念上的特征，而不是每个词一个。我需要以更复杂的方式处理大小写。

那么如何看待这个0.06%？我认为不能太当回事。你可以把它视为一个上限，记住样本量很小。但在现阶段，这更多的是衡量我实现中的bug，而不是贝叶斯过滤的某种内在误报率。

未来

下一步是什么？过滤是一个优化问题，优化的关键是分析。不要试图猜测你的代码哪里慢，因为你会猜错。看看你的代码哪里慢，然后修复那里。在过滤中，这转化为：看看你错过的垃圾邮件，弄清楚你能做些什么来抓住它们。

例如，垃圾邮件发送者现在正在积极地试图逃避过滤器，他们做的事情之一是拆分和拼错词以防止过滤器识别它们。但研究这个不是我的首要任务，因为我仍然能毫不费力地抓住这些垃圾邮件 [10]。

目前我有两种垃圾邮件难以过滤。一种是假装是来自女性的邮件，邀请你去聊天或看她在约会网站上的个人资料。这些能通过是因为它们是唯一一种你可以不用销售语言就能做的销售宣传。它们使用与普通邮件相同的词汇。

另一种我难以过滤的垃圾邮件是来自保加利亚等地的公司提供的合同编程服务。这些能通过是因为我也是程序员，垃圾邮件中充满了与我的真实邮件相同的词。

我可能会先关注个人广告类型。我认为如果我仔细看，我能找到这些和我的真实邮件之间的统计差异。写作风格当然不同，虽然可能需要多词过滤来抓住这一点。另外，我注意到它们倾向于重复URL，而包含URL的合法邮件发送者不会这样做 [11]。

外包类型将很难抓住。即使你发送爬虫去网站，你也不会找到确凿的统计证据。也许唯一的答案是维护一个在垃圾邮件中做广告的域名中央列表 [12]。但这种类型的邮件不会太多。如果剩下的唯一垃圾邮件是来自保加利亚的未请求的合同编程服务，我们可能都可以继续做其他事情了。

统计过滤真的能让我们达到那个地步吗？我不知道。现在，对我来说，垃圾邮件不是问题。但垃圾邮件发送者还没有认真尝试欺骗统计过滤器。当他们这样做时会发生什么？

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

网络层面的过滤器不会完全没用。它们可能足以杀死所有"选择加入"的垃圾邮件，意思是来自像Virtumundo和Equalamail这样声称他们真的在运行选择加入列表的公司的垃圾邮件。你可以仅基于邮件头过滤这些，不管他们在正文中说什么。但任何愿意伪造邮件头或使用开放中继的人，可能包括大多数色情垃圾邮件发送者，如果他们想要的话应该能够通过一些消息通过网络层面的过滤器。（当然不是他们想要发送的消息，这是另一回事。）

我乐观的是那种基于每个用户的邮件计算概率的过滤器。这些可以更有效，不仅在避免误报方面，而且在过滤方面：例如，在消息的任何地方找到收件人的电子邮件地址base-64编码是一个很好的垃圾邮件指标。

但个人过滤器的真正优势是它们都会不同。如果每个人的过滤器都有不同的概率，这将使垃圾邮件发送者的优化循环，程序员会称之为他们的编辑-编译-测试循环，变得极其缓慢。他们不能只是调整垃圾邮件直到它通过他们桌面上的某个过滤器副本，而是必须为每个调整做一次测试邮寄。这就像在没有交互式顶层环境的语言中编程，我不会希望任何人这样做。

注释

[1] Paul Graham. “A Plan for Spam.” 2002年8月. https://paulgraham.com/spam.html.

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

第一个假设在文本分类中很普遍。使用它的算法被称为"朴素贝叶斯”。

我做出第二个假设是因为我的收件箱中垃圾邮件的比例从一天到另一天（实际上从一小时到另一小时）波动如此之大，以至于整体的先验比率似乎作为预测因子毫无价值。如果你假设P(spam)和P(nonspam)都是0.5，它们会抵消，你可以从公式中删除它们。

如果你在垃圾邮件与非垃圾邮件的比率一直很高或（特别是）很低的情况下做贝叶斯过滤，你可能可以通过纳入先验概率来改进过滤器性能。要做到这一点，你必须按时间跟踪比率，因为垃圾邮件和合法邮件量都有明显的每日模式。

[2] Patrick Pantel和Dekang Lin. “SpamCop– A Spam Classification & Organization Program.” AAAI-98文本分类学习研讨会论文集。

[3] Mehran Sahami, Susan Dumais, David Heckerman和Eric Horvitz. “A Bayesian Approach to Filtering Junk E-Mail.” AAAI-98文本分类学习研讨会论文集。

[4] 当时我在约4,000封合法邮件中有零误报。如果下一封合法邮件是误报，这将给我们0.03%。这些误报率不可靠，正如我后面解释的。我在这里引用一个数字只是为了强调，无论误报率是多少，它都小于1.16%。作为这些结果差异有多大的一个指标，一个简单地寻找"click"这个词的过滤器在2002年8月会抓住79.7%的我的垃圾邮件，有1.2%的误报率。

[5] Bill Yerazunis. “Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator.” 2003年垃圾邮件会议论文集。

[6] 在"A Plan for Spam"中我使用了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. “Statistical Spam Filter Works for Me.” http://www.sofbot.com.

[9] 误报并不都是平等的，我们在比较阻止垃圾邮件的技术时应该记住这一点。虽然过滤器造成的许多误报会是那些你不会介意错过的接近垃圾邮件的邮件，但黑名单造成的误报，例如，会是来自选择了错误ISP的人的邮件。在两种情况下你都抓住了接近垃圾邮件的邮件，但对黑名单来说接近是物理的，对过滤器来说是文本的。公平地说，应该补充说新一代负责任的黑名单，如SBL，造成的误报比早期黑名单如MAPS RBL少得多，后者故意造成大量误报以引起ISP的注意。

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

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

[11] 一般来说，垃圾邮件比普通邮件更重复。他们想要把信息灌输进去。我目前不允许在15个顶级标记中有重复，因为如果发送者碰巧多次使用某个不好的词，你可能会得到误报。（在我的当前过滤器中，“dick"有0.9999的垃圾邮件概率，但它也是一个名字。）似乎我们应该至少注意到重复，所以我可能会尝试允许每个标记最多出现两次，就像Brian Burton在SpamProbe中做的那样。

[12] 一旦垃圾邮件发送者被推向使用填空技术生成消息中的其他一切，这就是像Brightmail这样的方法将退化为的东西。

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

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

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