更好的贝叶斯过滤

原文：Better Bayesian Filtering
作者：Paul Graham　发表：2003-01
译者：Claude（baoyu-translate）

2003 年 1 月

（本文是 2003 年 Spam Conference 上的演讲稿。介绍我对《垃圾邮件计划》中所述算法的改进工作，以及未来的方向。）

我想在这里介绍的第一项发现，是一种“研究论文的惰性求值算法“——你只管想写什么写什么，不引用任何已有工作，愤怒的读者就会把你本该引用的所有论文的参考资料一股脑发给你。这套算法是我在《垃圾邮件计划》[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 对 token 做了词干提取——比如把 “mailing” 和 “mailed” 都归约到词根 “mail”。他们大概觉得是受语料库太小所迫；但即便如此，这也是一种过早优化。

第四，他们计算概率的方法不同。他们用了所有 token，而我只用最显著的 15 个。如果你用所有 token，就更容易漏掉那种长长的垃圾邮件——发件人先絮叨一遍自己的人生故事，最后说自己怎么靠某个传销暴富。这种算法也很容易被发垃圾邮件者糊弄：往邮件里塞一大段随机文本，把垃圾邮件用词的“分量“稀释掉就行了。

最后，他们对误报没有偏置。我认为任何垃圾邮件过滤算法都应当有一个方便的“旋钮“——你可以拧它，以略微牺牲过滤率为代价、降低误报率。我的做法是把非垃圾邮件语料里的 token 出现次数按双倍计。

我不认为把垃圾邮件过滤当成一个直接的文本分类问题处理是好主意。你可以借用文本分类的技术，但解决方案能够、也应当反映出这样一个事实：你处理的文本是邮件，且尤其是垃圾邮件。邮件不只是文本——它有结构。垃圾邮件过滤也不只是分类——因为误报远比漏报糟糕，应当作为另一类错误来对待。而错误的来源不只是随机的统计涨落，还有一个活生生的、正主动想攻破你过滤器的人。

Token

在 Slashdot 那篇文章之后我听说的另一个项目，是 Bill Yerazunis 的 CRM114（著名垃圾邮件过滤器）[5]。它正好是上面那条设计原则的反例——它就是一个直接的文本分类器，但它有效到惊人的程度——它甚至根本不知道自己在过滤垃圾邮件，却能近乎完美地把垃圾邮件过滤掉。

理解了 CRM114 是怎么工作的之后，我意识到自己迟早得从“基于单个词的过滤“迁移到这种思路。但我想，先看看用单个词能走多远。结果是：能走得出乎意料地远。

我大部分时间都花在更聪明的 token 化上。在当下的垃圾邮件上，我已经能达到接近 CRM114 的过滤率。这些技术和 Bill 的基本上是正交的——最优解或许会两者并用。

《垃圾邮件计划》里对 token 的定义非常简单：字母、数字、连字符、撇号、美元符号是构成字符，其他一切都是 token 分隔符。我也忽略大小写。

现在我对 token 的定义复杂了一些：

1. 保留大小写。

2. 感叹号是构成字符。

3. 当句点和逗号出现在两位数字之间时，它们是构成字符。这让我能把 IP 地址和价格完整保留下来。

4. 一个像 $20-25 这样的价格区间会切成两个 token：$20 和 $25。

5. 出现在 To、From、Subject、Return-Path 这些字段里、或者出现在 URL 里的 token，会被相应地标记。比如 Subject 行里的 foo 会变成 Subject*foo。（星号可以换成任何不被你允许作为构成字符的字符。）

这些手段会增大过滤器的词汇量，让它的判别能力更强。比如在当前过滤器里，Subject 行中出现的 free 的垃圾邮件概率是 98%，而正文中同样的 token 概率只有 65%。

下面是当前的一些概率值 [6]：

Subject*FREE      0.9999
free!!            0.9999
To*free           0.9998
Subject*free      0.9782
free!             0.9199
Free              0.9198
Url*free          0.9091
FREE              0.8747
From*free         0.7636
free              0.6546

在《垃圾邮件计划》那个过滤器里，这些 token 全都会有同一个概率：0.7602。那个过滤器认得约 23,000 个 token；当前这个认得约 187,000 个。

token 总量变大的副作用是漏匹配的可能性也变大。把语料分散到更多的 token 上，效果跟把语料变小一样。比如，如果你把感叹号当作构成字符，你可能就会缺少“带七个感叹号的 free“的概率——尽管你已经知道带两个感叹号的 free 概率是 99.99%。

一个解法是我所说的“退化“。当你找不到某个 token 的精确匹配时，把它当成一个不那么具体的版本来处理。我把“末尾的感叹号”、“大写”、“出现在五种被标记的上下文之一中“视为让 token 更具体的因素。比如，如果我没找到 Subject*free! 的概率，我会去查 Subject*free、free!、free 的概率，取离 0.5 最远的那一个。

下面是当过滤器在 Subject 行看到 FREE!!!、却没有它的概率时，所考虑的备选项 [7]：

Subject*Free!!!
Subject*free!!!
Subject*FREE!
Subject*Free!
Subject*free!
Subject*FREE
Subject*Free
Subject*free
FREE!!!
Free!!!
free!!!
FREE!
Free!
free!
FREE
Free
free

你这么做时，记得既要考虑首字母大写的版本，也要考虑全大写和全小写的版本。垃圾邮件里祈使句更多，而祈使句的第一个词是动词。所以首字母大写的动词，比起全小写的同一个动词，垃圾邮件概率更高。在我的过滤器里，Act 的垃圾邮件概率是 98%，act 只有 62%。

如果你扩大词汇量，可能会出现“按你旧版本’同一个词’的定义、同一个词被算了多次“的情况。从逻辑上讲，它们已经不是同一个 token 了。但如果你仍然为此不安，让我从经验上补一句：那些看起来被算多次的词，恰恰就是你会希望算多次的词。

更大词汇量的另一个效应是：当你看一封到来的邮件时，你会发现更多“有意思的“token——也就是概率离 0.5 较远的那些。我用其中最有意思的 15 个来判定一封邮件是不是垃圾邮件。但用这种“固定数字“的做法会带来一个问题：如果你找到一大堆“最大化有意思“的 token，结果可能就被“等价 token 之间的随机排序“决定了。一种应对办法是把“有些 token“看得比“另一些“更有意思。

比如，token dalco 在我的垃圾邮件语料里出现 3 次，在正常邮件语料里 0 次。token Url*optmails（指 URL 里的 optmails）出现 1223 次。但按我以前算 token 概率的方式，两者会有同一个垃圾邮件概率：阈值 0.99。

这感觉不对。理论上有理由给这两个 token 大不相同的概率（Pantel 和 Lin 就是这么做的），但我还没试。至少看起来：如果我们找到超过 15 个只在某一边语料里出现的 token，我们应当优先选其中出现次数多的那些。所以现在有两个阈值——对于只在垃圾邮件语料里出现的 token，如果出现超过 10 次，概率为 0.9999；否则为 0.9998。正常邮件语料一端同理。

之后我可能会对 token 概率做更大幅度的缩放，但目前这一点小小的缩放至少能保证 token 被排到正确的位置。

另一种可能性是：不只考虑前 15 个 token，而是考虑所有“有意思度“超过某个阈值的 token。Steven Hauser 在他的统计垃圾邮件过滤器里就是这么做的 [8]。如果你用阈值，记得设得很高，否则发垃圾邮件者可以通过往邮件里塞更多无害词来糊弄你。

最后，HTML 怎么处理？我把所有选项都试过了——从完全无视，到全部解析。无视 HTML 是个坏主意，因为它里面塞满了有用的垃圾邮件信号。但如果你全部解析，过滤器可能就退化成一个“HTML 识别器“。最有效的做法似乎是中间路线——只关注一部分 token，而非全部。我看 a、img、font 标签，其余的忽略。链接和图片你当然得看，因为它们里面有 URL。

我对 HTML 的处理大概可以更聪明，但我不觉得值得投太多时间。塞满 HTML 的垃圾邮件本来就好过滤；更聪明的发垃圾邮件者已经在避免它了。所以未来的过滤性能不应当太依赖你怎么处理 HTML。

效果

2002 年 12 月 10 日到 2003 年 1 月 10 日之间，我大约收到 1750 封垃圾邮件。其中 4 封漏过去了。也就是过滤率约 99.75%。

漏过去的 4 封中有 2 封，是因为它们碰巧用了在我正常邮件中常出现的词。

第三封是那种“利用一个不安全的 CGI 脚本向第三方发邮件“的——只看内容很难过滤，因为头部是无辜的，且它们对用词很小心。即便如此我通常也能逮住。这一封以 0.88 的概率溜了过去——刚好在 0.9 的阈值之下。

当然，如果看多 token 序列就能轻易抓到它。“Below is the result of your feedback form”（“以下是您反馈表单的结果”）一句就当场露馅。

第四封是我所说的“未来的垃圾邮件“——我预计垃圾邮件未来会进化成这种形态：一段完全中性的文字，后面附一个 URL。这一封说的是某人终于把自己的主页做完了，问我能不能过去看看。（那页面当然是个色情站点的广告。）

如果发垃圾邮件者把头部弄得很干净、用一个新鲜的 URL，那“未来的垃圾邮件“里就没有任何东西可供过滤器抓住。我们当然可以反制——派一个爬虫去看那个页面。但这或许并不必要。“未来的垃圾邮件“的回应率必定很低，否则人人都会这样做了。如果回应率足够低，发垃圾邮件者就不划算发它，我们也不必为过滤它太费心。

现在到了真正令人震惊的消息：在那同一个月里，我有三个误报。

某种意义上，遇到几个误报反而让人松一口气。当我写《垃圾邮件计划》时，我一个误报都没有过——也不知道它们会是什么样。现在见了几个，我松一口气地发现：它们没我害怕的那么糟。统计过滤器造成的误报，往往是那种听起来很像垃圾邮件的邮件——而这些恰恰是你最不介意漏掉的那种 [9]。

三个误报中有两个，是来自我曾经买过东西的公司发来的简报。我从没要求过收到它们——所以严格说也算垃圾邮件——但我把它们算作误报，因为我之前并没有把它们当垃圾邮件删掉。过滤器抓到它们，是因为这两家公司都在 1 月份从“自己服务器发邮件“切换成了商业群发服务，头部和正文都变得垃圾邮件味重多了。

第三个误报就比较糟了。它来自埃及的某个人，全大写。这是我把 token 设为大小写敏感的直接后果——《垃圾邮件计划》里那个过滤器是不会抓到它的。

整体的误报率很难说清，因为我们处在统计噪声里。任何在过滤器（至少是有效的过滤器）上工作过的人都意识得到这个问题：有些邮件根本说不清是不是垃圾邮件，而当你把过滤器调得很紧时，最后看的就是这种邮件。比如，到目前为止过滤器已经抓到两封“因发件人手抖打错了我地址而发来的邮件“，以及一封“发件人误以为我是别人“的邮件。严格说，这些既不是我的垃圾邮件，也不是我的正常邮件。

另一个误报来自 Virtumundo 的一位副总裁。我假装是他们的客户给他们写信，回信经过 Virtumundo 的邮件服务器，所以头部带着所有可以想见的“罪证“。严格说这也不是真正的误报，而更像一种海森堡不确定性效应（观察行为本身改变被观察对象）——我之所以收到它，正是因为我在研究垃圾邮件过滤。

不算这些，到目前为止我一共有 5 个误报，分母是约 7740 封正常邮件，比率是 0.06%。剩下的两封是“我买的东西缺货“的通知，以及一封 Evite（美国电子邀请函网站）发来的派对提醒。

我认为这个数字不能太当真——一是样本太小，二是我觉得我能改过滤器、不让它抓到其中一些。

误报在我看来是与漏报不同种类的错误。过滤率是性能指标。误报我更倾向于看作bug。我把“提升过滤率“当成优化来做，把“降低误报“当成调试来做。

所以这 5 个误报就是我的 bug 列表。比如那封埃及来的邮件之所以被抓，是因为全大写文本让过滤器以为它是一封“尼日利亚式诈骗“垃圾邮件。这真的算 bug。和 HTML 一样，“邮件全大写“在概念上其实是一个特征，而不是每个词上的一个特征。我得用更精细的方式处理大小写。

那 0.06% 怎么解读？我觉得没什么好解读的。你可以把它当成上限——同时记住样本极小。但在现阶段，它更像是我实现里 bug 数量的一个度量，而不是“贝叶斯过滤“本身的某种内在误报率。

未来

接下来呢？过滤是一个优化问题，而优化的关键在于性能剖析。别去猜你的代码哪里慢，因为你会猜错。去看你的代码哪里慢，然后修。在过滤上，这翻译成：看你漏掉的那些垃圾邮件，想想你本可以做什么把它们抓住。

比如说，发垃圾邮件者现在正激进地想躲过过滤器，他们做的一件事是把词拆开、拼错，让过滤器认不出来。但这不是我目前的首要任务，因为这种垃圾邮件我还没遇到困难 [10]。

我现在确实头疼的有两类垃圾邮件。一类是假装一位女士邀请你去和她聊天、或者去看她在交友网站上个人页面的那种。它们能溜过去，是因为这是唯一一种“不用销售话术“也能做出推销的形式。它们用的是普通邮件的词汇。

另一类我难以过滤的，是来自比如保加利亚的公司发来的“承包编程服务“的邮件。它们能溜过去，是因为我自己也是程序员，这些邮件里塞满了和我真实邮件一样的词。

我大概会先盯个人广告那一类。我觉得仔细看，应能找到它们和我真实邮件之间的统计差异。写作风格肯定不一样——虽然也许要靠多词组合过滤才能抓住。另外我注意到它们倾向于重复 URL，而一个在正经邮件里包含 URL 的人不会这么做 [11]。

外包那一类会很难抓。哪怕你派爬虫去那个站点看，也找不到一杆“统计学的冒烟枪“。也许唯一的解，是一个集中维护的“被垃圾邮件推广的域名“列表 [12]。但这种邮件的总量不会太大。如果剩下的垃圾邮件就只剩“保加利亚来的、未经请求的承包编程服务报价“，我们大概都可以转头去做别的事了。

统计过滤真能把我们带到那一步吗？我不知道。眼下，对我个人而言，垃圾邮件不是问题。但发垃圾邮件者也还没认真发力去糊弄统计过滤器——等他们真的发力时，会发生什么？

我对在网络层面做过滤的方案不乐观 [13]。当存在一个值得绕过的静态障碍时，发垃圾邮件者会很高效地把它绕过去。已经有一家叫 Assurance Systems 的公司提供这样的服务：把你的邮件丢进 Spamassassin 跑一遍，告诉你它会不会被过滤掉。

网络层面的过滤器也不会完全没用。它们或许足以干掉所有那些“opt-in“垃圾邮件——也就是 Virtumundo、Equalamail 这样宣称自己真的在跑“opt-in 列表“的公司发的那种。这种你只看头部就能过滤掉，正文写什么无所谓。但任何愿意伪造头部、或者用开放中继的人——大概包括大多数色情垃圾邮件者——只要他们想，就总能让某种邮件溜过网络层面的过滤器。（不见得是他们最想发的那种内容——这本身已经是收获了。）

我看好的过滤器，是那种基于每个用户自己的邮件计算概率的过滤器。它们能有效得多——不只是在避免误报上，也在过滤上：比如说，如果在邮件里任意位置发现收件人的邮箱地址被 base-64 编码后塞着，这就是一个非常强的垃圾邮件信号。

但个人化过滤器真正的优势在于：它们人人不同。如果每个人的过滤器概率都不一样，发垃圾邮件者的优化循环——程序员所说的“编辑-编译-测试循环“——会慢得令人发指。他们不能再光是在自己桌面上的某份过滤器副本上调一调、看能不能溜过去；每改一次，他们都得做一次实测群发。这就像在一门**没有交互式顶层（REPL）**的语言里编程——我可不希望任何人遭这种罪。

注释

[1] Paul Graham. ``A Plan for Spam.‘’ August 2002. http://paulgraham.com/spam.html.

该算法中的概率是用贝叶斯定理的一种退化情形计算的。其中有两个简化假设：一是各特征（即词）的概率彼此独立；二是我们对“一封邮件是垃圾邮件“的先验概率一无所知。

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

第二个假设我之所以用，是因为我邮箱里垃圾邮件的比例每天乃至每小时都在剧烈波动——整体先验比作为预测器看起来毫无价值。如果你假设 P(spam) 和 P(nonspam) 都是 0.5，它们就会抵消掉，可以从公式里去掉。

如果你在一种“垃圾比正常一直非常高“或（尤其是）“非常低“的场景下做贝叶斯过滤，那把先验概率纳入进来很可能能改善过滤性能。要做对，你得按“一天里的不同时段“分别追踪比例——因为垃圾邮件和正常邮件的流量都有明显的日内规律。

[2] Patrick Pantel and Dekang Lin. ``SpamCop—— A Spam Classification & Organization Program.‘’ Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[3] Mehran Sahami, Susan Dumais, David Heckerman and Eric Horvitz. ``A Bayesian Approach to Filtering Junk E-Mail.‘’ Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[4] 当时我从约 4,000 封正常邮件里得到了零个误报。如果下一封正常邮件正好是误报，那就给出 0.03%。这些误报率不可信——后文有解释。我在这里报一个数字，只是为了强调：不管真正的误报率是多少，反正都低于 1.16%。

[5] Bill Yerazunis. ``Sparse Binary Polynomial Hash Message Filtering and The CRM114 Discriminator.‘’ Proceedings of 2003 Spam Conference.

[6] 在《垃圾邮件计划》里我用的阈值是 0.99 和 0.01。把阈值按语料规模成比例调整看起来是合理的。既然我现在每边大约都有 10,000 封邮件，我用的阈值是 0.9999 和 0.0001。

[7] 这里有个我可能该修的缺陷。目前，当 Subject*foo 退化成只是 foo 时，所对应的统计量是 “foo” 出现在正文或者那些我没有标记的头部行里时的次数。我应当做的是——既追踪 “foo” 整体上出现的统计量，也追踪它的具体版本——然后让 Subject*foo 不退化成 foo，而是退化成 Anywhere*foo。大小写同理：我应当从大写退化到任意大小写，而不是退化到小写。

对价格大概也是同样的赢——比如把 $129.99 退化成 $--9.99、$--.99、$--。

你也可以把单词退化到它的词干，但这件事大概只在你语料还很小的早期阶段才能改善过滤率。

[8] Steven Hauser. ``Statistical Spam Filter Works for Me.‘’ http://www.sofbot.com.

[9] 误报并非全都等价——在比较各种“阻挡垃圾邮件“的技术时，我们应当记住这一点。过滤器造成的误报多半是“近似垃圾邮件“——你不太介意漏掉；但例如黑名单造成的误报，则只是“选错了 ISP 的人“发来的邮件。两种情形下你都误抓了“接近垃圾邮件“的邮件——但黑名单的“接近“是物理上的，过滤器的“接近“是文本上的。

[10] 如果发垃圾邮件者擅长到能让“模糊 token“成为问题，我们可以这样应对——直接去掉空白、句点、逗号等，再用一部词典从余下的字符序列里挑出词。当然，这种方式找到的、原文里看不见的词，本身就是垃圾邮件的证据。

挑词不是平凡操作。它不只是要重建词边界——发垃圾邮件者既会加字母（“xHot nPorn cSite”），也会省字母（“P#rn”）。视觉研究在这里也许有用——人的视觉，正是这些把戏所逼近的极限。

[11] 总体上，垃圾邮件比一般邮件更爱重复——它们想把那条信息一锤一锤砸进你脑子。我目前不允许在前 15 个 token 里有重复——因为如果发件人碰巧把某个“坏词“用了好几次，可能就误报了。（在我目前的过滤器里，dick 的垃圾邮件概率是 0.9999，但它也是个名字。）但似乎我们至少应当注意到重复——所以我可能会试着允许每个 token 最多算两次，就像 Brian Burton 在 SpamProbe 里那样。

[12] 一旦发垃圾邮件者被推到了“用填空式技巧（像 Mad Libs 词语填空游戏一样自动套模板）生成邮件其余一切“的地步，像 Brightmail 这种思路就会退化成这种集中域名列表。

[13] 有时人们会说我们应当在网络层面做过滤，因为那样更高效。他们这样说时，通常的真实意思是：“我们目前就在网络层面过滤，我们不想从头再来。“但你不能把问题硬掰成你解的形状。

历史上，“资源稀缺“这一类论证在软件设计辩论中一向是输的一边。人们倾向于用这种论证去为出于其他原因做出的选择（尤其是“什么都不做”）找说辞。

致谢 Sarah Harlin、Trevor Blackwell、Dan Giffin 通读本文初稿；再次感谢 Dan——这个过滤器跑在他搭的大部分基础设施之上。