译者电邮：liji@brandeis.edu
其它有关贝叶生过滤器的翻译文章：
 | 一个对付垃圾邮件的计划 |
| 更好的贝叶斯过滤法 |
| 零散二元多项式散列法（SBPH），及CRM114判别式 |
William S. Yerazunis
在2004年麻省理工垃圾邮件大会上的讲话
麻省,剑桥,2004年1月18日
内容摘要:如今贝叶生过滤器已成为邮件过滤的标准.但不幸的是,大多数贝叶生过滤器似乎都达到一个99.9%的瓶颈.本文将以实验的方法,将TEFT,TOE,TUNE以及纯贝叶生法,token袋,token序列,SBPH,马可夫判别式等方法进行比较.本文将以实验结果说明TUNE是最适合训练用的方法,但它在计算上太繁冗.而马可夫判别式被认为比贝叶生更准确,只是不够达到四:九准确率.另外,接种以及其他技术手法也将被提到.
关键词:垃圾邮件,贝叶生,过滤器,电子邮件,马可夫.
内容简介:SpanAssasin,Brightmail等已有的启动式邮件过滤器都属加权式过滤器,它们以人工反应的方式来管制特征值并进行工作.这些过滤器用一个固定的特征侦察集,然后给所谓"太垃圾化的"邮件加一个槛值.第一代过滤器另外还有一个人工生成的权集,而现在大部分启动式过滤器都用一个中性集,或者用别的分散机制的系统,以便优化特征加权过程.举例说,SpanAssassin是用的三百余个手制Perl程序来作特征识别器.
在不久的过去,启动式过滤器被贝叶生过滤器盖过了风头.Paul Graham先是在<一个关于垃圾邮件治理的计划>[1]中描述了这种过滤器.贝叶生过滤器具有特高的精确率,并且特别不容易被破坏,因此现在已成为邮件过滤的中流砥柱.它们不是用现作现用的手制特征识别器,而是使用两个文本集,一个给垃圾邮件,一个给常规邮件.假设一个文本文件只包含一个特定词的话,贝叶生过滤器分别计算这个词在垃圾邮件集和常规邮件集里的出现频率,然后用这个比率来决定这个文件作为垃圾邮件的局部概率.
一句话,贝叶生过滤器第一个重要优势已经很明显,因为这里面不需要用到任何人为的方式来作特征识别.一个简单的双端空白识别器,就可以把文件分割成单个的词,然后每个词都是数据库里的一个特征.
有的贝叶生过滤器还具有数据库剪辑功能,用来在执行的时候,从数据库里抽取仅几百或者几千个最"垃圾味儿"的或是最"不垃圾味儿"的词.大部分的贝叶生过滤器还会用一个测试剪辑方案,只有头十个或头二十个"垃圾味儿"或"非垃圾味儿"的词被认为是最紧要的.
不管做不做数据库或测试剪辑,贝叶生过滤器的下一步总是对单个特征词语的局部概率作一个统计归拢.典型的局部概率是这样的:
Plocal-spam = Nspam / ( Nspam+Nnonspam)
同时加上适合的数界来避免除零错误.更高级点的局部概率公式,是将概率数据的确定性同不确定性一同考虑在内,特别是当这个特征的出现率很低的时候,例如:
(Nspam - Nnonspam )
Plocal-spam = 0.5 +___________________________________________________________
C1 *( Nspam+Nnonspam + C2)
这样就使低出现率特征的局部概率很大地靠近0.5.举例说,如果C1=2,C2=1,并且这个词只有一个情况下是垃圾的,那么一个包含了这个词的文件的局部概率就被设定成是0.75.但假如这个词有十个情况是垃圾的,并且从不出现在非垃圾邮件中,那么我们得到的局部概率就会是95.4%.所以前者作为垃圾的可能性算很低,后者则是理由充分的高得多了.
每个特征词有一个这样的局部概率.接着,我们用贝叶生链式法则,把这些局部概率计算成一个总体的文本作为垃圾邮件的概率.如上所说,有的贝叶生过滤器会用数据库或测试剪辑,来使总体计算量最小化.贝叶生链式法则是这样的:
P(feat | in class) * P (in class)
P (in class | feature) = ______________________________________________________________
P(feat | class) * P (in class) + P(feat | not in class) * P (not in class)
这样重复进行,把每个局部概率分别算到总体概率里去.
贝叶生链式法则的失败之处在于,严格地说,它只能对所有特征均统计上相互独立的情况管用.毫无疑问,这是不现实的:词语通常都有很强的相互关联,而非随机选择出来.贝叶生文本归类的特别可取之处在于,甚至是在这种惊人的本质错误的存在下,它居然还是相当管用的.
为纠正这个错误,我们可以用chi-squared或者别的合并法则.SpamBayes是用的一个改装过的chi-squared合并法则.
贝叶生过滤器的总体成就体现在两个方面.其一,是免费可用的过滤器的数量之大.上个计数表明,在Sourseforge.net上有超过二十个不同的贝叶生类邮件过滤器.几乎所有这些过滤器都具有99.9%的准确率.可与之对照的是,一个人在区分垃圾邮件和正常邮件时,只能达到约99.84%的准确率(Yerazunis 2003).所以这些过滤器比一个"私人应答秘书"还更管用.
即使在那些垃圾邮件散发者,那些生计跟垃圾邮件过滤器密切相关的人身上,贝叶生过滤器的效果也得到了极其的体现.这些垃圾散发者在对付简单的checksumming过滤时,只要加点随机生成或者胡说八道的词到文件和标题里去就行了.作为垃圾邮件的掩体,当下他们的最常用手段有:
|
"悠长故事"邮件---头一两页看上去完全是正常的. |
|
"字典拼盘"邮件---这种邮件的绝大部分都是随机摘取的字典词汇. |
|
"新的故事"邮件---最开头是从什么新闻里逐字抄来的,跟垃圾邮件的主题毫不相关. |
|
"Habeas Haiku"邮件---故事是这样的.Habeas Haiku一首短诗,拥有者是一个叫Habeas的由律师组成的公司.Habeas Haiku最开始是被注册给那些遵守Habeas邮件发送协议的公司用的.而现在这个haiku已经被垃圾邮件滥用,以至于统计地讲,haiku的存在就意味着这个邮件是垃圾邮件了.在过滤史上,这个从"非垃圾"到"垃圾"的意味转换,发生在2003年12月早期的一个星期之内. |
垃圾邮件散发者开始了另一个很有趣的战术,他们开始渗入那些口碑良好的散发面广的邮件组,好比同学会,或者是有关某个特别兴趣的小组.这些口碑良好的邮件组,一般都在接受者的白名单上,这样垃圾邮件就不会经过任何过滤.
方法比较以及贝叶生过滤法的变形
对于不同的过滤方法之间的一致比较,需要一致地针对一份数据流来进行.每天的垃圾邮件有大量的变形,因此我们将采用2003年4月的标准对SpamAssassin网页上的数据进行测试.
这个测试集包括有4147个邮件,分类为垃圾邮件,容易的非垃圾邮件,困难的非垃圾邮件.在这些邮件当中,有1400个是垃圾.
这个测试是对过滤法的一个痛苦折磨:在这个测试里,作者本人只能勉强做到大约90%的准确率.而在现实生活中,作者能达到大约99.84%的准确率.
为了提供一个更大的测试集,这个4147个邮件的集子将被重整十次,每个重整提供一个有效的随机邮件集.我们将保留所有十次重整,以便使每个实验配置得到相同的十组邮件集.
除非另行通知,每次重整产生的最后500个邮件将被"保留"用作最后的评估测试集,错误最后叠加,于是每个实验配置都有5000个测试尝试.这样我们的原始输出数据将是5000个邮件里的错误数.
如同在现实生活中一样,这个测试要经过所有的4147个邮件,在包括最后500个(评估)邮件运行中,训练将在指定中进行.等整个4147个邮件都结束后,数据库将清空,这样下一趟测试不光是针对一个不同的重组来进行,而且没有预设的试验结果干扰.
训练方法比较
第一个实验集是用来决定不同训练方法之间的相对特性.关于零散二元多项式拆分(Sparse Binary Polynomial Hash)特征以及贝叶生链式法则,我们已经有了相当的的经验,所以接下来我们建立一个SBPH/BCR归类法,来对以下几种方法进行训练:
|
TEFT---训练所有---针对每次重组得到的集子,进行归类,记录输出(不管正确与否),然后强迫训练这段文本到正确的类别. |
|
TOE---只训练错误---针对每个重组,进行归类,记录输出(不管正确与否),假如文本的归类不正确,把这段文本训练到正确的类别里去. |
|
TUNE---训练直到无错误---针对起先的500个邮件,重复进行分类并且在错误的情况下对之训练.等过了这个强化训练之后,记录最后的500个文本,假如出错就训练.(由于无法保证收敛,在训练集中只有少数邮件没有被训练的情况下,训练会中止.在十次重组产生的42470个邮件中,只有三个没有被正确归类.) |
以下的表格1是最后结果.执行器是一台Transmeta 666和Red Hat Linux 7.3,以及128兆内存.特征词杂烩集的大小被约束到1000000格,格数用光时旧格被随机删除.
| 训练方法名称 | 每5000邮件中的错误 | 10次重组所用的时间估计 |
| TEFT | 149 | 6小时 |
| TOE | 69 | 3小时 |
| TUNE | 54 | 20小时 |
表格1:TEFT,TOE,TUNE三钟训练方法的比较
我们看到TOE训练跟TUNE几乎一样好,而所用的CPU时间却只有很小一部分.
虽然TUNE比TOE要更准确那么一点点,但是TUNE要求把所有不管是垃圾邮件还是非垃圾邮件的历史信息全部保留下来.在重复进行的测试环境当中,这倒是可行的,不过到了现实生活使用这就得要求每个使用者都有一个巨大的存储空间.一个粗略估计得是
在重复垃圾邮件从数据库及时删除的情况下,每个使用者每年250兆.
TUNE所需要的额外CPU时间不是寻常的.在4147个邮件的训练中,它用了约2小时时间来重归类和重训练.这个过程将在发生任何训练的情况下重复进行.假如是对一个个人用户的专用CPU,如此尚算可行.但哪怕是一个小型ISP(好比说有1000个帐号),也不至于能承担得起如此一个系统.
贝叶生过滤法推广之间的比较
表格1的结果告诉我们,TOE(只在错误时训练)的方法在性能和准确度方面都是可接受的.我们现在来看看一个贝叶生过滤器的不同推广方法之间的精确程度比较.
在这些实验中,我们还是用4147条信息,十个重组,在每两个重组之间清楚所有记忆.每个推广法都将使用相同的十个重组,每个都用TOE方法进行训练.每个方法都被允许使用1000000个特征格子,而且都是随机删除旧格来给新信息留空间.不过话说回来,没有一个方法最后需要清楚旧的数据.
测试采用的不同推广法包括:
|
标准贝叶生---每个词都是一个特征.这是Graham提出的方法,正在被大部分防垃圾过滤器使用.它不使用任何数据库或文本剪辑.所有特征都被保留,在评估里使用. |
|
TOKEN抓取袋---由五个词组成的流动窗口在文本上移动.所有这五个词的组合(不过一定要用到窗口中的第一个词)都被以不计次序的方式抓取.所有这样的无序组合成为一个特征. |
|
TOKEN序列敏感器---由五个词组成的流动窗口在文本上方移动.所有词语删减的组合都被抓取(另外要求窗口中的第一个词不能被删除),这样结果得到的有序词集就成为一个特征. |
|
零散二元多项式拆分(Sparse Binary Polynomial Hashing)以及贝叶生链式法则(SBPH/BCR)---正如Yerazunis[2]所描述的,这是在文本上方移动的一个五词组成的窗口.一个特征即是一个序列空白敏感体,由这五个词构成的所有可能组合构成的集子,条件是总得包括第一个词. |
|
峰值零散二元多项式拆分(Peaking Sparse Binary Polynomial Hashing)---这个同SBPH/BCR相似,只不过对所有的窗口位置来说,只有那些具有极端概率(远离0.5)的特征被采用.在同一个窗口位置产生的其他特征将被弃用.这个尝试是为了"分拆"文本中出现的词语序列,以便使贝叶生链式法则更适用. |
|
马可夫链匹配---这个同SBPH相似,不过在这里,单个的特征被赋予变量加权.这些加权用一种累加的方式进行,这样如果一个特征比任何子特征都包括更多词,它的加权也将超过它的所有子特征的总和. |
这些测试同训练测试用一样的系统进行.测试时间同表格1里的SBPH/BCR法TOE没有很大区别.
| 评估者 | 每5000个中的错误数 |
| 标准贝叶生 | 92 |
| 峰值窗口 | 80 |
| TOKEN序列敏感器 | 78 |
| TOKEN抓取袋 | 71 |
| SBPH | 69 |
| 马可夫链匹配 | 56 |
表格2:不同推广方法的准确程度
有趣的是,从数字上看来,TOKEN序列敏感器(TSS)是比TOKEN抓取袋(TGB)还要弱的系统,而且还是统计上不可小觑的程度.本来的猜想会是,TSS给过滤法加上了更多信息,性能也应该随之提高.可很明显的,在这种随机词语插入的垃圾邮件对付方法中,我们发现TSS并没有TGB的性能好.有趣的是,SBPH跟TGB在性能上很相似.
在所有过滤法中,马可夫链匹配法是性能最好的一个,所以我们在下面给一些技术详情.
为方便计算故,马可夫链匹配过滤法并不是对文本生成真正的马可夫模型,而是在每个文本集中,用已知例文本的拆散表示,作为大的(一般未知)垃圾邮件和非垃圾邮件的马可夫模型的局部片断.
这个实施起来很简单.我们不用链接TOKEN(如同被Zdziarski[3]描述过的那样),而是给特征加权,这样在更长的特征里发现的证据就被得到更大的利用.
举例说,在文本"The quick brown fox jumped"中,特征及其加权如下所示
|
特征 |
加权 |
|---|---|
|
The |
1 |
|
The quick |
4 |
|
The <skip> brown |
4 |
|
The quick brown |
16 |
|
The <skip> <skip> fox |
4 |
|
The quick <skip> fox |
16 |
|
The <skip> brown fox |
16 |
|
The quick brown fox |
64 |
|
The <skip> <skip> <skip> jumped |
4 |
|
The quick <skip> <skip> jumped |
16 |
|
The <skip> brown <skip> jumped |
16 |
|
The quick brown <skip> jumped |
64 |
|
The <skip> <skip> fox jumped |
16 |
|
The quick <skip> fox jumped |
64 |
|
The <skip> brown fox jumped |
64 |
|
The quick brown fox jumped |
256 |
表格3:马可夫匹配中加权的一个例子
在这个试验中,我们用了下列公式所示的累加加权法.
Weight = 22N
如此一来,对于包含有1,2,3,4,5个词的特征,其加权将分别是1,4,16,64,256.这些加权被用于使短特征的局部概率远离0.5,如下所示:
(Nspam - Nnonspam ) * Weight
Plocal-spam = 0.5 + _____________________________________________________
C1 *( Nspam+Nnonspam + C2) * WeightMax
对于观测到的马可夫法准确度的理论说法
有人也许会问,为什么马可夫过滤法能比别的哪怕与之相似的SBPH过滤法更精确.一个猜想是,SBPH过滤法依旧是线性的,而马可夫过滤法用了累加的加权,就不再线性了.我们不难把SPBH的过滤域设想成在一个高维超空间里(每个特征占一个超空间维度),而垃圾邮件和非垃圾邮件之间的分离不过是这个超空间里的一个二维平面:平面这边的文本被认为是垃圾的,平面那边的则是非垃圾的.
Minsky和Papert[4]指出,这样一个线性过滤器不能实施任何复杂程度等同于XOR计算的事情,也就是说,线性过滤器不能学会(或甚至表达!)任何复杂程度有如"A或者B但不能是二者"的事情.古典贝叶生过滤器依旧是线性的,例如,贝叶生过滤器不能被训练成能接受"viagra"和"pharmacy"而不接受二者放在一起.
马可夫过滤器用了累加加权就不再是线性的了,因为任何长度为N的特征,都能远远超过那些长度为1,2,...,N-1的特征.
马可夫过滤器能很简单的学会识别在什么情况下"A或者B但不是二者"是正确的分离方法.用一个长度为五的流动窗口,马可夫法能把特征的分离沿着一个五阶平面展开,甚至哪怕那个片面不是连通的.
不幸的是,以上理论说法未被验证.也许还存在别的原因,使得这些测试中马可夫法比贝叶生法在准确程度上高出一大截.这就是说,这个事情可以被认为是"有可能",但绝不是科学意义上说"解决了"的.
并且我们应该注意到,马可夫法比之贝叶生法的优越性不是一点半点---用相同的数据流测试,马可夫法的错误要少40%.不过在过滤法而言,考虑到当前逐月提高的垃圾邮件数量,40%的准确率提高只不过意味着几个月的缓滞期.假如垃圾散发者利用口碑良好的邮件组的话,甚至马可夫法也不是一个办法,可这种垃圾散发者的伎俩已经越来越普遍.
接种和布雷
下一代的垃圾邮件过滤法可以利用DeSade观察结果---也就是说,此人的痛苦是彼人的快乐所在.在这件事上,我们用某个人收到一个垃圾邮件的苦痛来训练不光是他/她自己的过滤器,还包括其朋友的.这样的话,系统针对可识别垃圾邮件的错误率,就可与参与者的人数成反比.假如有十个朋友来参加,那你就得到了十倍的过滤提高.然而,这只是一个人为思考出来的训练,所以人为错误因素也得考虑进去.
不管这个,我们已经编译了这种接种性的系统,并且当前结果显示其运作良好.
第二个观察结果是基于站点而非基于个人的.假如对绝大部分垃圾邮件散发活动进行观察,就会发现此同一垃圾邮件散发者会在极短时间内对某一站点内其所掌握的所有帐户进行攻击.有一个实例就是,一个小站点的所有帐户在十秒钟内全部被攻击到.
正是因为垃圾邮件的这种迅速传播速度,人为反应总嫌太慢---在第一个人读到这个垃圾邮件之前,所有的邮箱都已经接受或者拒绝了这个邮件.
为应付这种攻击方式,你可以加上所谓"邮件雷区"防御工事.一个邮件雷区是指,在某站点的地址栏加上一大堆的无用邮件地址,然后这些地址就被故意泄漏给垃圾散发者知道.
实际上没人会法邮件给这些额外的无用地址,这样任何发到这些地址的邮件,就预先被打上垃圾邮件的标签了.
更有效的是,垃圾散发者一般喜欢伪造他们的台头,并隐藏IP.然而,在从垃圾散发者到雷区地址的SMTP交易过程中,他们必须暴露自己的实际IP.这些IP地址是没法伪装的,因为SMTP必须用到至少是RCPT OK程序以让这个交易能正确地达到垃圾散发者手中,这非得要垃圾散发者在接点安装过程中暴露其真实IP才行.
在这当口,目标站点及其合作站点能立刻将进攻者的IP地址送上黑名单.这个黑名单可以是"接受然后扔掉"型的,也可以是"拒绝连接"型的.
不幸的是,正如John Graham-Cumming[5]所指出的,用一个贝叶生过滤器进攻另一个贝叶生过滤器是可能的.在这个过程中,那个"邪恶"贝叶生里包含有大量词汇;它持续散发由随机词语构成的垃圾邮件到另一个"善良"贝叶生,然后当"善良"贝叶生正确地发现垃圾邮件时,"邪恶"方收到相应讯息.Graham-Cumming报告说,那个"邪恶"贝叶生可以把那些最有可能被"善良"贝叶生错误接纳的字典词汇整合起来,用作击穿对方的武器.
这个结果,可对任何过滤算法适用:Graham-Cumming指出,对付它的唯一正确方法,只能是永远不向发送者输回讯息.如此,我们的布雷法也必须以这个形式进行,以避免暴露到哪些帐号是雷区帐号,那些帐号是真实个人的---到达两种帐号的所有邮件都要接收,假如是知道来自垃圾散发者的IP地址的,只能在事后进行删除.
幸运的是,给予垃圾散发者便利以攻击一个系统中所有帐号的交通迅捷,也给了一个系统向别的系统传输来者IP的更快捷的交通.在这种共享实时雷区中,只要在雷区帐号上一有动作,多个合作站点就可在很短的时间内(几小时到几天),动态地将个体IP地址弄进黑名单上.
更有甚者,因为在意识到垃圾邮件攻击和交换IP地址上动态雷区同时覆盖了多个站点,很大量的帐户就可以被相对轻松地保护起来,而无需用人力去把IP地址加进或者撤出黑名单.
这样方式下的动态雷区目前正经测试.这是将来研究的课题.
结论
贝叶生过滤法也许是达到了准确率的一个极限.提高或许是可能的,但特定邮件中包含的信息量毕竟有限,而质量不断提高的过滤器并不可行.
幸运的是,不管有没有人力因素干涉,来自多个帐号的相关邮件将能作为不可忽视的信息源泉,而且是有不可忽视的高极限的源泉.
感谢和鸣谢
本文作者多谢CRM114的所有工作人员,以及Darren Leigh, Erik Piip.
[1] Graham, Paul, "A Plan For Spam",2003.
[2] Yerazunis, William S., "Sparse Binary Polynomial Hashing and the CRM114 Discriminator", MIT Spam Converence 2003.
[3] Zdzairsky, Jonathan, "Advanced Language Classification using Chained Tokens", MIT Spam Conference 2004
[4] Minsky and Papert, 1969, PERCEPTRONS
[5] John Graham-Cumming, "How to Beat a Bayesian Spam Filter", MIT Spam Conference 2004