垃圾邮件的一种应对方法
翻译自：A Plan for Spam。
（这篇文章描述了应用在 Arc 语言的练习作品——防垃圾在线邮件阅读器中的垃圾过滤技术。改进后的算法在《更好的贝叶斯过滤》中描述。）
我认为阻止垃圾邮件是可能的，并且基于内容的过滤器是一种方法。垃圾邮件制作者的阿喀琉斯之踵正是他们的信息。他们可以绕过你设置的任何其他障碍。至少到目前为止他们已经做到了。但他们必须要递送他们的信息，不论这信息是什么。如果我们可以写一个能识别他们信息的软件，那他们就没有任何办法避开了。
对接收者来说，垃圾邮件很容易识别。如果你雇某人来阅读你的邮件并挑出垃圾邮件，他可能不会遇到什么困难。那么在不用人工智能的情况下，我们需要做多少工作来自动化这个过程？
我认为我们可以用一个相当简单的算法来解决这个问题。实际上我发现你可以仅仅用单词的垃圾概率的一个贝叶斯组合就可以对现今（2002 年）的垃圾邮件过滤得不错。使用一个稍微调整过的（如下面描述）贝叶斯过滤器，我们现在在每 1000 封垃圾邮件中漏过滤少于 5 封，并且误判为 0。
人们开始写垃圾过滤器时常常并不会一开始就尝试统计的方法。许多黑客的直觉是试着写一个能识别垃圾邮件的独特属性的软件。你看着垃圾邮件并且想，这些无耻的家伙试着给我发送一些由“亲爱的朋友”开头或者主题完全由大写字母组成并且以八个感叹号结尾的邮件。我用一行代码就可以过滤掉这些东西。
然后你就这么做了，并且刚开始时它确实管用。一点简单的规则就能过滤掉不少垃圾邮件。在我的垃圾邮件语料里，仅仅用“click”这个单词就能过滤出 79.7%，而且只有 1.2% 的误报率。
在尝试统计方法之前我用了大概六个月来写识别独立的垃圾邮件特征的软件。我发现识别剩下的那一点垃圾邮件非常困难，当把过滤器调整得更严格之后会产生更多的误报。
误报是指清白的邮件被错误地判断为垃圾邮件。对大多数用户来说，错过正常邮件比收到垃圾邮件严重得多，一个过滤器产生误判就像痤疮药可能致死一样。
用户收到的垃圾邮件越多，他就越不容易注意到垃圾邮件箱里的无辜邮件。并且怪异的的是，你的过滤器越好，误判的危害就越大，因为当过滤器足够好时，用户会更加倾向于忽略所有被过滤的邮件。
我不知道为啥我这么长时间都避免去使用统计方法。我觉得是因为我太沉醉于亲自挑出垃圾邮件的特征，就像在跟垃圾邮件发送者玩着什么竞技游戏一样。（非黑客常常并不会注意到这点，但大多数的黑客是非常争强好胜的。）当我尝试统计分析时，我发现这比我原先的做法聪明得多。它发现了，其实是显而易见的，诸如“virtumundo”和“teens”这样的词是垃圾邮件的好指示器。但是它也发现了“per”、“FL”和“ff0000”也是好的特征。实际上“ff0000”（html 中代表红色）对垃圾邮件分辨程度和其他色情词语差不多。
下面是我如何做统计过滤的一个概述。我以一个垃圾邮件语料库和一个正常邮件语料库开始。当时每个里面都有大约 4000 封邮件。我扫描检查了每个语料库的整个文本，包括头部和嵌入的 html 和 javascript。我目前把字母数字组成的单词、连接号、撇号和美元符号作为词法元素，剩下的其他符号作为词法元素的分隔符。（这里可能有提高的空间。）我忽略了全部由数字组成的词法元素，并且我也忽略了 html 注释，甚至不把其看做分隔符。
我计算了每个词（目前忽略大小写）在每个语料库里出现的次数。在这个阶段我得到了两个大哈希表，每个语料库一个，从单词映射到它们出现的次数。
之后我创建了第三个哈希表，这次从每个单词映射到当一个邮件包含它们时为垃圾邮件的概率，计算方法如下：
|
|
其中 word 是我们正计算的单词的概率，good 和 bad 是我在第一步中创建的哈希表，ngood 和 nbad 是正常邮件和垃圾邮件对应的个数。
我用代码来解释是为了展示一些重要的细节。我想轻微地让概率偏向于避免误判，通过试错我发现把 good 中的计数翻倍是个好方法。这有助于区分偶尔在正常邮件中出现而几乎从不在垃圾邮件中出现的单词。我只考虑出现总数超过 5 次的单词（实际上因为翻倍，在正常邮件中出现 3 次就够了）。然后是应该给只在一个语料库中出现的单词什么概率的问题。同样通过试错我选择了 0.01 和 0.99。此处应该还有很多的调整空间，不过随着语料库增长这种调整会自动发生。
特别善于观察的会发现我在把每个语料库当做一个长文本流来计算单词出现次数时，我使用每个语料库的邮件个数，而不是它们的总和，来作为计算垃圾邮件概率的分母。这轻微地偏向于减少误判。
当新的邮件到达时，它会被扫描分成单词，然后取其中最有趣的 15 个单词——这里有趣度由它们的垃圾邮件概率和原始 0.5 的差距衡量——来计算这个邮件是垃圾邮件的概率。如果 probs 是这 15 个单词概率的一个列表，你可以这样计算组合概率：
|
|
实际应用中会有一个问题是如何给一个从未见过的单词赋以概率，比如一个在单词概率哈希表中没出现过的单词。我发现，依旧通过试错，0.4 是一个不错的值。如果你从未见过一个单词，那它很可能是无辜的；垃圾邮件的单词一般很相似。
在结尾的附录中有这个算法应用于实际邮件的例子。
我把此算法给出的概率大于 0.9 的邮件当做垃圾邮件。不过在实践中这个阈值的具体位置似乎影响不大，因为最终没几个概率在范围中间。
统计方法的一个重要的优势是你不用再去阅读那么多垃圾邮件了。在过去的 6 个月里，我逐字阅读了上千封垃圾邮件，这确实让人恶心。Norbert Wiener 说过如果你和奴隶竞争你就会变成一个奴隶，和垃圾邮件发送者竞争也是如此。为了识别出独立的垃圾邮件特点你必须设法理解垃圾邮件发送者的想法，但坦率地说我想在垃圾邮件发送者的想法上花的时间越少越好。
但是贝叶斯方法的真正优势，显而易见的，是你知道你在测量什么。如 SpamAssassin 这种特点识别过滤器赋予邮件一个垃圾“分数”。贝叶斯方法则赋予一个实际的概率。“分数”的问题在于没人知道它的含义。用户不知道它的含义，更糟的是，过滤器开发者也不知道。一个包含单词“sex”的邮件应该得到多少分？一个概率可能是错误的，但它的含义或者如何结合证据来计算却没有多大歧义。基于我的语料库，“sex”指出包含它的邮件有 0.97 的概率为垃圾邮件，同时“sexy”有 0.99 的概率。贝叶斯法则，同样无歧义，指出同时包含这两个单词的邮件，在没有其他证据的情况下（不太可能），有 99.97% 的可能是垃圾邮件。
理想中，每个用户的概率应该独立计算。我有许多包含“Lisp”这个单词的正常邮件，并且没有一封垃圾邮件包含这个。所以像这样的单词确实是一个给我发送邮件的密码。在我之前的垃圾邮件过滤软件中，用户可以建立一个这样的单词列表，如果有邮件包含它们则就会自动通过过滤器。在我的列表中我放入了如“Lisp”这样的单词和我的邮编，这样（可能有点像垃圾邮件的）在线订单的收据就能通过。我曾认为我这样很聪明，但我发现贝叶斯过滤器为我做了同样的事，此外还发现了更多的我想不到的单词。
我之前说的我们的过滤器在 1000 封邮件中漏过滤少于 5 封并且没有误判，这是指在我的语料库上过滤我的邮件。但这些数字并没有误导，因为这是我所支持的方法：根据各个用户的正常邮件和垃圾邮件的语料库来过滤它们自己的邮件。本质上，每个用户应该有两个删除按钮，普通的删除和作为垃圾邮件的删除。每个被作为垃圾邮件删除的进入垃圾邮件语料库，而所有其他的进入正常邮件语料库。
你可以让用户以一个种子过滤器开始，但最终每个用户都会拥有自己的基于他实际收到的邮件的单词概率。这（a）让过滤器更有效，（b）让每个用户决定自己关于垃圾邮件的精确定义，并且（c）可能最好的是让垃圾邮件发送者很难调整邮件来通过过滤器。如果很多的过滤器智慧是在个人独立的数据库中，他们仅仅调整垃圾邮件来通过种子过滤器并不会保证他们能够通过独立用户的多样化的并经过更多训练的过滤器。
基于内容的垃圾邮件过滤器通常会搭配一个白名单，这个名单包含可以不过滤而直接通过的发送者。一种建立这种白名单的方法是维护一个用户曾发送过邮件的目标地址。如果一个邮件阅读者有一个作为垃圾删除按钮，那你可以把用户以普通删除的每封邮件的地址添加到其中。
我是一个白名单的支持者，但是作为节约计算的一种方法而不是提升过滤能力。我曾经认为白名单能让过滤更容易，因为你只用过滤那些来自不认识的人的邮件，并且第一次给你发邮件的人被按惯例地限制为他们能对你说的话。某些你已经认识的人可能会给你发关于性的邮件，但第一次给你发邮件的人一般不会这么做。问题是，人们可以有多于一个的邮箱地址，所以一个新的发件地址并不能保证发送者是第一次给你写信。一个老朋友突然用一个新的邮件地址给你写信并不常见（特别是如果他是一个黑客的话），你不能承担因严格过滤未知邮件地址而带来的误报率。
从某种意义上说，我的过滤器确实包含了一种白名单（和黑名单），因为它们基于整个信息，包括头部。所以它们“知道”信任的发送者的邮件地址，甚至是发送给我的邮件所通过的路由。它们也知道有关垃圾邮件的这些信息，包括服务器地址、客户端版本和协议。