更好的贝叶斯过滤
Original2003年1月
(这篇文章是在2003年反垃圾邮件大会上发表的讲话。它描述了我为提高《反垃圾邮件计划》中描述的算法的性能所做的工作,以及我未来的计划.)
我想在这里提出的第一个发现是一种论文惰性求值算法。你只需写下你想写的任何内容,而不需要引用任何以前的工作,愤怒的读者就会给你发送你应该引用的所有论文的参考。我在《反垃圾邮件计划》[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的技术大多是正交的;一个最优解可能会结合两者。
《反垃圾邮件计划》使用了一个非常简单的令牌定义。字母、数字、连字符、单引号和美元符号是组成字符,其他一切都是令牌分隔符。我也忽略了大小写。
现在我有了一个更复杂的令牌定义:
保留大小写。
感叹号是组成字符。
句号和逗号在两个数字之间时是组成字符。这让我能完整地获取IP地址和价格。
$20-25这样的价格范围会产生两个令牌,$20和$25。
出现在To、From、Subject和Return-Path行或网址中的令牌会被相应地标记。例如,Subject行中的"foo"会变成"Subject*foo"。(星号可以是任何你不允许作为组成字符的字符。)
这种措施增加了过滤器的词汇量,使其更具辨别能力。例如,在当前的过滤器中,"free"在主题行有98%的垃圾邮件概率,而在正文中只有65%。
以下是一些当前的概率[6]:
主题免费 0.9999 免费!! 0.9999 到免费 0.9998 主题免费 0.9782 免费! 0.9199 免费 0.9198 网址免费 0.9091 免费 0.8747 从*免费 0.7636 免费 0.6546
在垃圾邮件过滤器计划中,所有这些令牌的概率都是相同的,为 .7602。该过滤器识别了大约 23,000 个令牌。当前过滤器识别约 187,000 个。
令牌宇宙变大的缺点是更容易出现遗漏。将语料库分散到更多令牌上就像缩小它一样。如果将感叹号视为构成部分,那么即使你知道只有两个感叹号的"免费"的概率为 99.99%,你也可能没有七个感叹号的"免费"的垃圾邮件概率。
解决这个问题的一个办法是我所说的退化。如果找不到令牌的确切匹配,就将其视为更不具体的版本。我认为末尾的感叹号、大写字母和出现在五个标记上下文中的令牌都更具体。例如,如果我没有找到 "Subject免费!" 的概率,我会查找 "Subject免费"、"免费!" 和 "免费" 的概率,并选择最远离 .5 的那个。
如果过滤器在主题行中看到 "免费!!!" 而没有相应的概率,以下是它将考虑的替代方案 [7]。
Subject免费!!! Subject免费!! Subject免费! Subject免费 Subject*免费 免费!!! 免费!! 免费! 免费 免费 免费
如果这样做,一定要考虑首字母大写版本以及全大写和全小写版本。垃圾邮件更倾向于使用祈使语气,在这种情况下动词首字母大写的垃圾邮件概率高于全小写。在我的过滤器中,"行" 的垃圾邮件概率为 98%,"行" 只有 62%。
如果增加过滤器的词汇量,你可能会根据旧的"相同"定义多次计算同一个词。从逻辑上来说,它们不再是同一个令牌了。但如果这仍然让你困扰,让我从经验中告诉你,你似乎在多次计算的那些词正是你想要的。
较大词汇量的另一个影响是,当你查看传入的邮件时,你会发现更多有趣的令牌,也就是那些概率远离 .5 的令牌。我用 15 个最有趣的令牌来决定邮件是否是垃圾邮件。但当你使用固定数量时,可能会遇到一个问题。如果你发现很多最有趣的令牌,结果可能会被决定于决定同样有趣的令牌顺序的任何随机因素。解决这个问题的一种方法是将一些令牌视为比其他令牌更有趣。
例如,令牌"dalco"在我的垃圾邮件语料库中出现 3 次,在我的合法语料库中从未出现过。令牌"Url*optmails"(意味着 url 中的"optmails")出现了 1223 次。然而,按我以前计算令牌概率的方式,这两个令牌的垃圾邮件概率是相同的,即 .99 的阈值。
这感觉不太对。理论上有理由给这两个令牌大不相同的概率(Pantel 和 Lin 这么做),但我还没有尝试过。至少看起来,如果我们发现 15 个以上只出现在一个语料库中的令牌,我们应该优先考虑那些出现次数较多的。所以现在有两个阈值。对于只出现在垃圾邮件语料库中的令牌,如果出现次数超过 10 次,概率为 .9999,否则为 .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 脚本发送邮件给第三方的垃圾邮件。仅根据内容很难过滤这种垃圾邮件,因为标头是无害的,他们也很注意所用的单词。尽管如此,我通常还是能捕捉到它们。这一封只有 .88 的概率,刚好低于 .9 的阈值。
当然,查看多个令牌序列就可以很容易地捕捉到它。"下面是您反馈表单的结果"就是一个明确的标志。
第四个垃圾邮件就是我所谓的 "未来垃圾邮件",因为这就是我预期垃圾邮件的 演化方向:一些完全中性的 文字后跟一个URL。在这种情况下,是有人 说他们终于完成了他们的主页,并让我去看看。 (当然,这个页面是一个色情网站的广告。)
如果垃圾邮件发送者小心对待标题,并使用一个 新的URL,那么"未来垃圾邮件"就没有什么能让 过滤器注意到的。当然,我们可以通过派遣 爬虫来查看该页面。但这可能不是必需的。 "未来垃圾邮件"的响应率一定很低,否则 每个人都会这样做。如果足够低, 它不会有利可图,垃圾邮件发送者就不会 发送它,我们也不需要太费力地对其进行过滤。
现在敲响的是更加令人震惊的新闻:在同一个一个月 的期间,我收到了三个假阳性。
某种程度上来说,收到一些假阳性是 令人欣慰的。当我写《反垃圾邮件的计划》时,我还没有 收到任何假阳性,我也不知道它们会是什么样子。 现在我已经收到了几个,我很庆幸发现 它们没有我担心的那么糟糕。
统计过滤器产生的假阳性都是那些听起来非常像垃圾邮件的邮件, 这些往往是你最不介意错过的 [9]。
两个假阳性是我曾购买过东西的公司发来的电子通讯。 我从未要求接收它们,所以可以说它们 是垃圾邮件,但我将它们算作假阳性,因为 在此之前我并没有把它们当作垃圾邮件删除。过滤器 捕获它们的原因是,这两家公司在 一月份转而使用商业电子邮件发送商, 标头和正文都变得更像垃圾邮件。
第三个假阳性确实很糟糕。它是 来自埃及的人,全部用大写写的。这是 区分大小写造成的直接结果;"垃圾邮件计划"过滤器 是不会捕捉到这种情况的。
很难说整体的假阳性率是多少, 因为我们处于噪音之中,从统计学上看。 任何从事过滤器工作的人(至少是有效的过滤器)都会 意识到这个问题。 对于某些电子邮件,很难说它们是垃圾邮件还是不是, 这些就是当你的过滤器 真正严格起来时你最终要查看的内容。例如,到目前为止,过滤器 已经捕获了两封发到我地址的电子邮件,这是因为 有人打错了字,还有一封发给我的电子邮件, 是别人误以为我是别人。从某种程度上说, 这些既不是我的垃圾邮件,也不是我的正常邮件。
另一个假阳性是来自Virtumundo副总裁的。 我假装成一个客户给他们写信, 由于回复通过Virtumundo的 邮件服务器发送,它有最具有 "罪证性"的标头。从某种程度上说,这不算是一个真正的假阳性, 而是一种"海森堡不确定性效应":我只是因为 在撰写垃圾邮件过滤问题而收到它。
不计算这些,到目前为止我共有5个假阳性, 在大约7740封正常电子邮件中,错误率为0.06%。 另外两个是一个我购买的商品 补货的通知,以及一个来自Evite的聚会提醒。
我认为这个数字是不可靠的,部分是因为 样本规模太小,部分是因为 我认为我可以修改过滤器,不去捕捉 其中的一些。
在我看来,假阳性似乎是一种不同于 假负的错误类型。过滤率是性能的一种度量。我把假 阳性更像是一种bug。我把提高 过滤率视为优化,减少假阳性视为调试。
所以这五个假阳性就是我的bug清单。例如, 来自埃及的邮件被抓获,是因为大写文本 使它在过滤器看来像一封尼日利亚垃圾邮件。 这确实有点像bug。与 html一样,电子邮件全部大写实际上是一个 整体特征,而不是每个单词一个特征。我需要以 更复杂的方式处理大小写。
那么这0.06%意味着什么?我认为不太多。你可以 将其视为一个上限,考虑到样本规模很小。 但在这个阶段,它更多地衡量的是我的实现中的bug, 而不是贝叶斯过滤的某种固有假阳性率。
未来展望
接下来怎么办?过滤是一个优化问题, 关键在于分析瓶颈。不要 猜测你的代码哪里慢,因为你会猜错。查看 你的代码哪里慢,并修复那里。 在过滤中,这意味着:看一看 你错过的垃圾邮件,弄清楚你 本可以做些什么来捕捉它们。
例如,垃圾邮件发送者现在正努力 规避过滤器,其中一项做法是 拆分和错拼单词,以防止过滤器识别它们。 但这不是我的首要任务,因为我仍然很容易 捕捉到这些垃圾邮件 [10]。
我目前确实有麻烦处理的两种类型垃圾邮件。 一种是假装来自女士的电子邮件,邀请你去聊天 或查看她在约会网站上的个人资料。这些能通过 过滤,因为它们是一种不需要使用销售话语的销售pitch。 它们使用与普通电子邮件相同的词汇。
另一种我很难过滤的垃圾邮件是 来自保加利亚等国家提供合同编程服务的公司发送的。 它们能通过,因为我也是程序员, 这些垃圾邮件充满了与我真正邮件相同的词语。
我可能会先关注那种个人广告类型。我认为如果 仔细观察,我应该能发现它们和我真正邮件之间的 统计差异。写作风格肯定是不同的, 但可能需要多词过滤才能捕捉到。 另外,我注意到它们倾向于重复URL, 而正常邮件的发件人不会这样做 [11]。
外包类型很难捕捉。即使 你让爬虫去那个网站,也找不到明确的线索。 也许唯一的答案是维护一个 垃圾邮件中出现的域名的中央列表 [12]。 但这种类型的邮件应该不会太多。如果剩下的 只有来自保加利亚提供合同编程服务的未经请求的邮件, 我们可能就可以转而去解决其他问题了。
过滤统计真的能达到那一点吗? 我不知道。就我个人而言,目前垃圾邮件并不是个问题。但是,垃圾邮件发送者还没有认真尝试欺骗统计过滤器。当他们这么做时会发生什么?
我对网络级过滤器不太乐观[13]。 当有一个值得绕过的静态障碍时,垃圾邮件发送者能够非常高效地绕过它。已经有一家名为Assurance Systems的公司会帮你测试邮件是否会被Spamassassin过滤掉。
网络级过滤器并非完全无用。它们可能足以杀死所有"选择加入"垃圾邮件,也就是来自像Virtumundo和Equalamail这样的公司,它们声称在运营选择加入名单。你可以仅根据标头来过滤这些,不管它们在正文中说了什么。但是任何愿意伪造标头或使用开放中继的人,显然包括大多数色情垃圾邮件发送者,如果他们想的话,应该能让一些信息通过网络级过滤器。(当然不是他们想发送的信息,这已经是一种限制了。)
我对这种基于每个用户邮件计算概率的过滤器感到乐观。这些过滤器不仅能更好地避免误报,而且过滤效果也更好:例如,在一条消息中找到收件人的电子邮件地址是一个非常好的垃圾邮件指标。
但是个人过滤器的真正优势在于它们都是不同的。如果每个人的过滤器都有不同的概率,这将使垃圾邮件发送者的优化循环,程序员所谓的编辑-编译-测试周期,令人沮丧。他们不能再只是调整一条垃圾邮件直到它通过他们桌面上的某个过滤器,而是必须对每次调整都进行测试发送。这就像在没有交互式顶层的语言中编程,我也不希望任何人遭受这种折磨。
注释
[1] 保罗·格拉汉姆。 "垃圾邮件的计划"。2002年8月。 http://paulgraham.com/spam.html。
该算法中的概率是使用贝叶斯规则的退化情况计算的。有两个简化假设:特征(即单词)的概率是独立的,我们对电子邮件是垃圾邮件的先验概率一无所知。
第一个假设在文本分类中广泛使用。使用它的算法被称为"朴素贝叶斯"。
我做出第二个假设,是因为我收到的垃圾邮件与正常邮件的比例在一天之内波动如此之大(实际上是从一小时到一小时都在变),以至于整体的先验比率似乎作为一个预测因子毫无用处。如果你假设P(spam)和P(nonspam)都是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] 比尔·叶拉尼斯。"稀疏二进制多项式哈希消息过滤和CRM114判别器"。2003年垃圾邮件会议论文集。
[6] 在"垃圾邮件的计划"中,我使用了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] 史蒂文·豪泽。"统计垃圾邮件过滤器对我有效"。 http://www.sofbot.com。
[9] 误报并不都是一样的,我们在比较阻止垃圾邮件的技术时应该记住这一点。 而许多过滤器造成的误报将是几乎是垃圾邮件的邮件,你可能不会介意错过它们,但黑名单造成的误报却是来自选择了错误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再次提供了这个过滤器所依赖的大部分基础设施。
相关:
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
SubjectFree!!! Subjectfree!!! SubjectFREE! SubjectFree! Subjectfree! SubjectFREE SubjectFree Subjectfree FREE!!! Free!!! free!!! FREE! Free! free! FREE Free free