MEILLEUR FILTRAGE BAYÉSIEN

January 2003

(Cet article a été présenté lors de la conférence Spam de 2003. Il décrit le travail que j'ai réalisé pour améliorer les performances de l'algorithme décrit dans A Plan for Spam, et ce que je prévois de faire à l'avenir.)

La première découverte que j'aimerais présenter ici est un algorithme pour l'évaluation paresseuse des articles de recherche. Écrivez simplement ce que vous voulez et ne citez aucun travail précédent, et des lecteurs indigné vous enverront des références à tous les articles que vous auriez dû citer. J'ai découvert cet algorithme après que ``A Plan for Spam'' [1] ait été publié sur Slashdot.

Le filtrage des spams est un sous-ensemble de la classification de texte, qui est un domaine bien établi, mais les premiers articles sur le filtrage bayésien des spams semblent avoir été deux présentés lors de la même conférence en 1998, l'un par Pantel et Lin [2], et l'autre par un groupe de Microsoft Research [3].

Quand j'ai entendu parler de ce travail, j'étais un peu surpris. Si les gens s'étaient intéressés au filtrage bayésien il y a quatre ans, pourquoi tout le monde ne l'utilisait-il pas ? En lisant les articles, j'ai compris pourquoi. Le filtre de Pantel et Lin était le plus efficace des deux, mais il ne capturait que 92 % des spams, avec 1,16 % de faux positifs.

Lorsque j'ai essayé d'écrire un filtre de spam bayésien, il a capturé 99,5 % des spams avec moins de 0,03 % de faux positifs [4]. C'est toujours alarmant lorsque deux personnes essayant la même expérience obtiennent des résultats très divergents. C'est particulièrement alarmant ici car ces deux ensembles de chiffres pourraient donner des conclusions opposées. Différents utilisateurs ont des exigences différentes, mais je pense que pour beaucoup de gens, un taux de filtrage de 92 % avec 1,16 % de faux positifs signifie que le filtrage n'est pas une solution acceptable, tandis que 99,5 % avec moins de 0,03 % de faux positifs signifie que c'est le cas.

Alors pourquoi avons-nous obtenu des chiffres si différents ? Je n'ai pas essayé de reproduire les résultats de Pantel et Lin, mais en lisant l'article, je vois cinq choses qui expliquent probablement la différence.

L'une est simplement qu'ils ont entraîné leur filtre sur très peu de données : 160 spams et 466 mails non-spams. Les performances du filtre devraient encore augmenter avec des ensembles de données aussi petits. Donc, leurs chiffres peuvent même ne pas être une mesure précise de la performance de leur algorithme, sans parler du filtrage bayésien des spams en général.

Mais je pense que la différence la plus importante est probablement qu'ils ont ignoré les en-têtes de message. Pour quiconque a travaillé sur des filtres de spam, cela semblera une décision perverse. Et pourtant, dans les tout premiers filtres que j'ai essayé d'écrire, j'ai également ignoré les en-têtes. Pourquoi ? Parce que je voulais garder le problème propre. Je ne savais pas grand-chose sur les en-têtes de mail à l'époque, et ils me semblaient pleins de choses aléatoires. Il y a une leçon ici pour les rédacteurs de filtres : ne pas ignorer les données. On pourrait penser que cette leçon serait trop évidente pour être mentionnée, mais j'ai dû l'apprendre plusieurs fois.

Troisièmement, Pantel et Lin ont réduit les tokens, ce qui signifie qu'ils ont réduit par exemple à la fois mailing'' et mailed'' à la racine ``mail''. Ils ont peut-être estimé qu'ils étaient contraints de le faire par la petite taille de leur corpus, mais si c'est le cas, c'est une sorte d'optimisation prématurée.

Quatrièmement, ils ont calculé les probabilités différemment. Ils ont utilisé tous les tokens, tandis que j'utilise seulement les 15 les plus significatifs. Si vous utilisez tous les tokens, vous aurez tendance à manquer les spams plus longs, le type où quelqu'un vous raconte son histoire de vie jusqu'au moment où il est devenu riche grâce à un schéma de marketing à plusieurs niveaux. Et un tel algorithme serait facile à tromper pour les spammeurs : il suffit d'ajouter un gros morceau de texte aléatoire pour contrebalancer les termes de spam.

Enfin, ils n'ont pas biaisé contre les faux positifs. Je pense que tout algorithme de filtrage de spam devrait avoir un bouton pratique que vous pouvez tourner pour diminuer le taux de faux positifs au détriment du taux de filtrage. Je fais cela en comptant les occurrences de tokens dans le corpus non-spam deux fois.

Je ne pense pas qu'il soit judicieux de traiter le filtrage des spams comme un simple problème de classification de texte. Vous pouvez utiliser des techniques de classification de texte, mais les solutions peuvent et doivent refléter le fait que le texte est un email, et le spam en particulier. L'email n'est pas juste du texte ; il a une structure. Le filtrage des spams n'est pas juste une classification, car les faux positifs sont tellement pires que les faux négatifs que vous devriez les traiter comme un type d'erreur différent. Et la source de l'erreur n'est pas juste une variation aléatoire, mais un spammeur humain actif travaillant pour contourner votre filtre.

Tokens

Un autre projet dont j'ai entendu parler après l'article de Slashdot était celui de Bill Yerazunis, CRM114 [5]. C'est le contre-exemple au principe de conception que je viens de mentionner. C'est un classificateur de texte simple, mais tellement efficace qu'il parvient à filtrer le spam presque parfaitement sans même savoir que c'est ce qu'il fait.

Une fois que j'ai compris comment CRM114 fonctionnait, il semblait inévitable que je devrais finalement passer d'un filtrage basé sur des mots uniques à une approche comme celle-ci. Mais d'abord, je pensais, je vais voir jusqu'où je peux aller avec des mots uniques. Et la réponse est, étonnamment loin.

Principalement, j'ai travaillé sur une tokenisation plus intelligente. Sur le spam actuel, j'ai pu atteindre des taux de filtrage qui approchent ceux de CRM114. Ces techniques sont principalement orthogonales à celles de Bill ; une solution optimale pourrait incorporer les deux.

``A Plan for Spam'' utilise une définition très simple d'un token. Les lettres, chiffres, tirets, apostrophes et signes dollar sont des caractères constitutifs, et tout le reste est un séparateur de token. J'ai également ignoré la casse.

Maintenant, j'ai une définition plus compliquée d'un token :

La casse est préservée.

Les points d'exclamation sont des caractères constitutifs.

Les points et les virgules sont des constituants s'ils se trouvent entre deux chiffres. Cela me permet d'obtenir des adresses IP et des prix intacts.

Une plage de prix comme $20-25 produit deux tokens, $20 et $25.

Les tokens qui se trouvent dans les lignes To, From, Subject et Return-Path, ou dans les urls, sont marqués en conséquence. Par exemple, foo'' dans la ligne Subject devient Subject*foo''. (L'astérisque pourrait être n'importe quel caractère que vous n'autorisez pas comme constituant.)

De telles mesures augmentent le vocabulaire du filtre, ce qui le rend plus discriminant. Par exemple, dans le filtre actuel, ``free'' dans la ligne Subject a une probabilité de spam de 98 %, tandis que le même token dans le corps a une probabilité de spam de seulement 65 %.

Voici quelques-unes des probabilités actuelles [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

Dans le filtre Plan for Spam, tous ces tokens auraient eu la même probabilité, 0.7602. Ce filtre reconnaissait environ 23 000 tokens. Le filtre actuel reconnaît environ 187 000.

L'inconvénient d'avoir un univers de tokens plus large est qu'il y a plus de chances de manquer des spams. Élargir votre corpus sur plus de tokens a le même effet que de le rendre plus petit. Si vous considérez les points d'exclamation comme des constituants, par exemple, alors vous pourriez finir par ne pas avoir de probabilité de spam pour free avec sept points d'exclamation, même si vous savez que free avec juste deux points d'exclamation a une probabilité de 99,99 %.

Une solution à cela est ce que j'appelle la dégénération. Si vous ne pouvez pas trouver une correspondance exacte pour un token, traitez-le comme s'il s'agissait d'une version moins spécifique. Je considère que les points d'exclamation terminaux, les lettres majuscules et le fait de se trouver dans l'un des cinq contextes marqués rendent un token plus spécifique. Par exemple, si je ne trouve pas de probabilité pour Subject*free!'', je cherche des probabilités pour Subject*free'', free!'', et free'', et je prends celui qui est le plus éloigné de 0,5.

Voici les alternatives [7] considérées si le filtre voit ``FREE!!!'' dans la ligne Subject et n'a pas de probabilité pour cela.

SubjectFree!!!
Subjectfree!!!
SubjectFREE!
SubjectFree!
Subjectfree!
SubjectFREE
SubjectFree
Subjectfree
FREE!!!
Free!!!
free!!!
FREE!
Free!
free!
FREE
Free
free

Si vous faites cela, assurez-vous de considérer les versions avec des majuscules initiales ainsi que toutes les majuscules et toutes les minuscules. Les spams ont tendance à avoir plus de phrases à l'impératif, et dans celles-ci, le premier mot est un verbe. Donc, les verbes avec des majuscules initiales ont des probabilités de spam plus élevées que s'ils étaient en minuscules. Dans mon filtre, la probabilité de spam de Act'' est de 98 % et pour act'' seulement 62 %.

Si vous augmentez le vocabulaire de votre filtre, vous pouvez finir par compter le même mot plusieurs fois, selon votre ancienne définition de ``même''. Logiquement, ce ne sont plus le même token. Mais si cela vous dérange encore, laissez-moi ajouter par expérience que les mots que vous semblez compter plusieurs fois ont tendance à être exactement ceux que vous voudriez.

Un autre effet d'un vocabulaire plus large est que lorsque vous regardez un mail entrant, vous trouvez plus de tokens intéressants, c'est-à-dire ceux avec des probabilités éloignées de 0,5. J'utilise les 15 les plus intéressants pour décider si un mail est un spam. Mais vous pouvez rencontrer un problème lorsque vous utilisez un nombre fixe comme celui-ci. Si vous trouvez beaucoup de tokens maximaux intéressants, le résultat peut finir par être décidé par quel que soit le facteur aléatoire qui détermine l'ordre des tokens également intéressants. Une façon de gérer cela est de traiter certains comme plus intéressants que d'autres.

Par exemple, le token dalco'' apparaît 3 fois dans mon corpus de spam et jamais dans mon corpus légitime. Le token Url*optmails'' (signifiant ``optmails'' dans une url) apparaît 1223 fois. Et pourtant, comme je calculais des probabilités pour les tokens, les deux auraient eu la même probabilité de spam, le seuil de 0,99.

Cela ne semble pas juste. Il y a des arguments théoriques pour donner à ces deux tokens des probabilités substantiellement différentes (Pantel et Lin le font), mais je n'ai pas encore essayé cela. Il semble au moins que si nous trouvons plus de 15 tokens qui n'apparaissent que dans un corpus ou l'autre, nous devrions donner la priorité à ceux qui apparaissent beaucoup. Donc maintenant, il y a deux valeurs seuils. Pour les tokens qui n'apparaissent que dans le corpus de spam, la probabilité est de 0,9999 s'ils apparaissent plus de 10 fois et de 0,9998 sinon. Idem à l'autre extrémité de l'échelle pour les tokens trouvés uniquement dans le corpus légitime.

Je pourrais plus tard ajuster considérablement les probabilités des tokens, mais cette petite quantité d'ajustement garantit au moins que les tokens sont triés de la bonne manière.

Une autre possibilité serait de considérer non seulement 15 tokens, mais tous les tokens au-dessus d'un certain seuil d'intérêt. Steven Hauser fait cela dans son filtre de spam statistique [8]. Si vous utilisez un seuil, faites-le très élevé, sinon les spammeurs pourraient vous tromper en remplissant des messages avec des mots plus innocents.

Enfin, que devrait-on faire à propos du html ? J'ai essayé tout le spectre d'options, de l'ignorer à tout analyser. Ignorer le html est une mauvaise idée, car il est plein de signes de spam utiles. Mais si vous l'analysez tout, votre filtre pourrait dégénérer en un simple reconnaisseur de html. L'approche la plus efficace semble être la voie du milieu, remarquer certains tokens mais pas d'autres. Je regarde les balises a, img et font, et j'ignore le reste. Les liens et les images, vous devriez certainement les examiner, car ils contiennent des urls.

Je pourrais probablement être plus intelligent dans le traitement du html, mais je ne pense pas qu'il vaille la peine d'y consacrer beaucoup de temps. Les spams remplis de html sont faciles à filtrer. Les spammeurs plus intelligents l'évitent déjà. Donc, les performances à l'avenir ne devraient pas dépendre beaucoup de la façon dont vous traitez le html.

Performance

Entre le 10 décembre 2002 et le 10 janvier 2003, j'ai reçu environ 1750 spams. Parmi ceux-ci, 4 ont réussi à passer. Cela donne un taux de filtrage d'environ 99,75 %.

Deux des quatre spams que j'ai manqués ont réussi à passer parce qu'ils utilisaient des mots qui apparaissent souvent dans mes emails légitimes.

Le troisième était l'un de ceux qui exploitent un script cgi non sécurisé pour envoyer des mails à des tiers. Ils sont difficiles à filtrer uniquement sur le contenu car les en-têtes sont innocents et ils sont prudents quant aux mots qu'ils utilisent. Même ainsi, je peux généralement les attraper. Celui-ci a réussi à passer avec une probabilité de 0,88, juste en dessous du seuil de 0,9.

Bien sûr, regarder des séquences de tokens multiples le capturerait facilement. ``Below is the result of your feedback form'' est un indice instantané.

Le quatrième spam était ce que j'appelle un spam-du-futur, car c'est ce à quoi je m'attends que le spam évolue : un texte complètement neutre suivi d'une url. Dans ce cas, c'était de quelqu'un disant qu'il avait enfin terminé sa page d'accueil et me demandait d'aller la voir. (La page était bien sûr une annonce pour un site pornographique.)

Si les spammeurs sont prudents avec les en-têtes et utilisent une nouvelle url, il n'y a rien dans le spam-du-futur que les filtres puissent remarquer. Nous pouvons bien sûr contrer cela en envoyant un crawler pour regarder la page. Mais cela pourrait ne pas être nécessaire. Le taux de réponse pour le spam-du-futur doit être faible, sinon tout le monde le ferait. S'il est suffisamment bas, cela ne paiera pas pour les spammeurs de l'envoyer, et nous n'aurons pas à travailler trop dur pour le filtrer.

Maintenant pour la nouvelle vraiment choquante : pendant cette même période d'un mois, j'ai eu trois faux positifs.

D'une certaine manière, c'est un soulagement d'avoir quelques faux positifs. Lorsque j'ai écrit ``A Plan for Spam'', je n'en avais eu aucun, et je ne savais pas à quoi ils ressembleraient. Maintenant que j'en ai eu quelques-uns, je suis soulagé de constater qu'ils ne sont pas aussi mauvais que je le craignais. Les faux positifs générés par des filtres statistiques s'avèrent être des mails qui ressemblent beaucoup à des spams, et ceux-ci ont tendance à être ceux que vous seriez le moins dérangé de manquer [9].

Deux des faux positifs étaient des newsletters d'entreprises auprès desquelles j'ai acheté des choses. Je n'ai jamais demandé à les recevoir, donc on pourrait dire qu'ils étaient des spams, mais je les compte comme des faux positifs car je ne les avais pas supprimés comme spams auparavant. La raison pour laquelle les filtres les ont attrapés est que les deux entreprises ont changé en janvier pour des expéditeurs d'emails commerciaux au lieu d'envoyer les mails depuis leurs propres serveurs, et les en-têtes ainsi que les corps sont devenus beaucoup plus spammés.

Le troisième faux positif était un mauvais. C'était de quelqu'un en Égypte et écrit en toutes lettres majuscules. C'était un résultat direct de rendre les tokens sensibles à la casse ; le filtre Plan for Spam ne l'aurait pas attrapé.

Il est difficile de dire quel est le taux global de faux positifs, car nous sommes dans le bruit, statistiquement. Quiconque a travaillé sur des filtres (du moins, des filtres efficaces) sera conscient de ce problème. Avec certains emails, il est difficile de dire s'ils sont des spams ou non, et ce sont ceux que vous finissez par examiner lorsque vous rendez les filtres vraiment stricts. Par exemple, jusqu'à présent, le filtre a attrapé deux emails qui ont été envoyés à mon adresse à cause d'une faute de frappe, et un envoyé à moi dans la croyance que j'étais quelqu'un d'autre. On pourrait dire que ceux-ci ne sont ni mes spams ni mes mails non-spams.

Un autre faux positif provenait d'un vice-président de Virtumundo. Je leur ai écrit en prétendant être un client, et comme la réponse est revenue par les serveurs de mail de Virtumundo, elle avait les en-têtes les plus compromettants imaginables. On pourrait dire que ce n'est pas un vrai faux positif non plus, mais une sorte d'effet d'incertitude de Heisenberg : je ne l'ai reçu que parce que j'écrivais sur le filtrage des spams.

Sans compter ceux-ci, j'ai eu un total de cinq faux positifs jusqu'à présent, sur environ 7740 emails légitimes, un taux de 0,06 %. Les deux autres étaient un avis que quelque chose que j'avais acheté était en rupture de stock, et un rappel de fête d'Evite.

Je ne pense pas que ce chiffre puisse être fiable, en partie parce que l'échantillon est si petit, et en partie parce que je pense que je peux corriger le filtre pour ne pas attraper certains de ceux-ci.

Les faux positifs me semblent être un type d'erreur différent des faux négatifs. Le taux de filtrage est une mesure de performance. Les faux positifs, je les considère plus comme des bugs. J'aborde l'amélioration du taux de filtrage comme une optimisation, et la diminution des faux positifs comme un débogage.

Donc, ces cinq faux positifs sont ma liste de bugs. Par exemple, le mail d'Égypte a été attrapé parce que le texte en majuscules le faisait ressembler à un spam nigérian. C'est vraiment une sorte de bug. Comme avec le html, le fait que l'email soit entièrement en majuscules est vraiment conceptuellement une caractéristique, pas une pour chaque mot. Je dois gérer la casse de manière plus sophistiquée.

Alors que faire de ce 0,06 % ? Pas grand-chose, je pense. Vous pourriez le traiter comme une limite supérieure, en gardant à l'esprit la petite taille de l'échantillon. Mais à ce stade, c'est plus une mesure des bugs dans mon implémentation qu'un taux de faux positifs intrinsèque du filtrage bayésien.

Avenir

Que faire ensuite ? Le filtrage est un problème d'optimisation, et la clé de l'optimisation est le profilage. Ne tentez pas de deviner où votre code est lent, car vous devinerez mal. Regardez où votre code est lent, et corrigez cela. Dans le filtrage, cela se traduit par : regardez les spams que vous manquez, et déterminez ce que vous auriez pu faire pour les attraper.

Par exemple, les spammeurs travaillent maintenant agressivement pour échapper aux filtres, et l'une des choses qu'ils font est de décomposer et de mal orthographier des mots pour empêcher les filtres de les reconnaître. Mais travailler là-dessus n'est pas ma première priorité, car je n'ai toujours pas de problème à attraper ces spams [10].

Il y a deux types de spams avec lesquels j'ai actuellement des problèmes. L'un est le type qui prétend être un email d'une femme vous invitant à discuter avec elle ou à voir son profil sur un site de rencontre. Ceux-ci passent parce qu'ils sont le seul type de discours de vente que vous pouvez faire sans utiliser de jargon commercial. Ils utilisent le même vocabulaire que les emails ordinaires.

L'autre type de spams que j'ai du mal à filtrer est celui des entreprises en Bulgarie, par exemple, offrant des services de programmation contractuelle. Ceux-ci passent parce que je suis également programmeur, et les spams sont remplis des mêmes mots que mon vrai mail.

Je vais probablement me concentrer d'abord sur le type d'annonces personnelles. Je pense que si je regarde de plus près, je pourrai trouver des différences statistiques entre ceux-ci et mon vrai mail. Le style d'écriture est certainement différent, bien qu'il puisse falloir un filtrage multi-mots pour le capturer. De plus, je remarque qu'ils ont tendance à répéter l'url, et quelqu'un incluant une url dans un mail légitime ne ferait pas cela [11].

Le type d'externalisation sera difficile à attraper. Même si vous envoyez un crawler sur le site, vous ne trouverez pas de preuve statistique évidente. Peut-être que la seule réponse est une liste centrale de domaines annoncés dans les spams [12]. Mais il ne peut pas y avoir tant de ce type de mail. Si les seuls spams restants étaient des offres non sollicitées de services de programmation contractuelle en Bulgarie, nous pourrions probablement tous passer à autre chose.

Le filtrage statistique nous amènera-t-il réellement à ce point ? Je ne sais pas. En ce moment, pour moi personnellement, le spam n'est pas un problème. Mais les spammeurs n'ont pas encore fait d'effort sérieux pour tromper les filtres statistiques. Que se passera-t-il quand ils le feront ?

Je ne suis pas optimiste quant aux filtres qui fonctionnent au niveau du réseau [13]. Lorsqu'il y a un obstacle statique qu'il vaut la peine de franchir, les spammeurs sont assez efficaces pour le contourner. Il existe déjà une entreprise appelée Assurance Systems qui fera passer votre mail par Spamassassin et vous dira s'il sera filtré.

Les filtres au niveau du réseau ne seront pas complètement inutiles. Ils peuvent suffire à éliminer tout le spam "opt-in", c'est-à-dire le spam d'entreprises comme Virtumundo et Equalamail qui prétendent qu'elles gèrent vraiment des listes opt-in. Vous pouvez filtrer ceux-ci uniquement sur la base des en-têtes, peu importe ce qu'ils disent dans le corps. Mais quiconque est prêt à falsifier des en-têtes ou à utiliser des relais ouverts, présumément y compris la plupart des spammeurs pornographiques, devrait être capable de faire passer un message au-delà des filtres au niveau du réseau s'il le souhaite. (Ce n'est pas le message qu'ils aimeraient envoyer, cependant, ce qui est quelque chose.)

Le type de filtres sur lesquels je suis optimiste est celui qui calcule des probabilités basées sur le mail de chaque utilisateur individuel. Ceux-ci peuvent être beaucoup plus efficaces, non seulement pour éviter les faux positifs, mais aussi pour le filtrage : par exemple, trouver l'adresse email du destinataire encodée en base-64 n'importe où dans un message est un très bon indicateur de spam.

Mais le véritable avantage des filtres individuels est qu'ils seront tous différents. Si les filtres de tout le monde ont des probabilités différentes, cela ralentira horriblement la boucle d'optimisation des spammeurs, ce que les programmeurs appelleraient leur cycle d'édition-compilation-test. Au lieu de simplement ajuster un spam jusqu'à ce qu'il passe un filtre qu'ils ont sur leur bureau, ils devront faire un mailing test pour chaque ajustement. Ce serait comme programmer dans un langage sans un niveau supérieur interactif, et je ne souhaiterais cela à personne.

Notes

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

Les probabilités dans cet algorithme sont calculées en utilisant un cas dégénéré de la règle de Bayes. Il y a deux hypothèses simplificatrices : que les probabilités des caractéristiques (c'est-à-dire des mots) sont indépendantes, et que nous ne savons rien sur la probabilité a priori qu'un email soit un spam.

La première hypothèse est répandue dans la classification de texte. Les algorithmes qui l'utilisent sont appelés ``bayésiens naïfs.''

La deuxième hypothèse que j'ai faite parce que la proportion de spam dans mes mails entrants fluctuait tellement d'un jour à l'autre (en effet, d'une heure à l'autre) que le ratio global semblait inutile comme prédicteur. Si vous supposez que P(spam) et P(nonspam) sont tous deux 0,5, ils s'annulent et vous pouvez les retirer de la formule.

Si vous faisiez du filtrage bayésien dans une situation où le ratio de spam à non-spam était constamment très élevé ou (surtout) très bas, vous pourriez probablement améliorer les performances du filtre en incorporant des probabilités a priori. Pour bien faire cela, vous devriez suivre les ratios par heure de la journée, car le volume de spam et de mail légitime a tous deux des modèles quotidiens distincts.

[2] Patrick Pantel et 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 et Eric Horvitz. ``A Bayesian Approach to Filtering Junk E-Mail.'' Proceedings of AAAI-98 Workshop on Learning for Text Categorization.

[4] À l'époque, je n'avais aucun faux positif sur environ 4 000 emails légitimes. Si le prochain email légitime était un faux positif, cela nous donnerait 0,03 %. Ces taux de faux positifs ne sont pas fiables, comme je l'explique plus tard. Je cite un chiffre ici uniquement pour souligner que quel que soit le taux de faux positifs, il est inférieur à 1,16 %.

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

[6] Dans ``A Plan for Spam'', j'ai utilisé des seuils de 0,99 et 0,01. Il semble justifiable d'utiliser des seuils proportionnels à la taille des corpus. Puisque j'ai maintenant environ 10 000 de chaque type de mail, j'utilise 0,9999 et 0,0001.

[7] Il y a un défaut ici que je devrais probablement corriger. Actuellement, lorsque Subject*foo'' dégénère en juste foo'', cela signifie que vous obtenez les statistiques pour les occurrences de foo'' dans le corps ou les lignes d'en-tête autres que celles que je marque. Ce que je devrais faire, c'est garder une trace des statistiques pour foo'' dans l'ensemble ainsi que pour les versions spécifiques, et dégénérer de Subject*foo'' non pas en foo'' mais en ``Anywhere*foo''. Idem pour la casse : je devrais dégénérer de majuscule à n'importe quelle casse, pas en minuscule.

Il serait probablement avantageux de faire cela avec les prix aussi, par exemple, de dégénérer de $129.99'' à $--9.99'', $--.99'', et $--''.

Vous pourriez également dégénérer des mots à leurs racines, mais cela n'améliorerait probablement les taux de filtrage que tôt lorsque vous aviez de petits corpus.

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

[9] Les faux positifs ne sont pas tous égaux, et nous devrions nous en souvenir en comparant les techniques pour arrêter le spam. Alors que beaucoup des faux positifs causés par des filtres seront des quasi-spams que vous ne vous dérangeriez pas de manquer, les faux positifs causés par des listes noires, par exemple, seront juste des mails de personnes qui ont choisi le mauvais FAI. Dans les deux cas, vous attrapez des mails qui sont proches du spam, mais pour les listes noires, la proximité est physique, et pour les filtres, elle est textuelle.

[10] Si les spammeurs deviennent suffisamment bons pour obscurcir les tokens pour que cela devienne un problème, nous pouvons répondre en supprimant simplement les espaces, les points, les virgules, etc. et en utilisant un dictionnaire pour extraire les mots de la séquence résultante. Et bien sûr, trouver des mots de cette manière qui n'étaient pas visibles dans le texte original serait en soi une preuve de spam.

Extraire les mots ne sera pas trivial. Cela nécessitera plus que simplement reconstruire les frontières des mots ; les spammeurs ajoutent (xHot nPorn cSite'') et omettent (P#rn'') des lettres. La recherche en vision pourrait être utile ici, car la vision humaine est la limite que de telles astuces approcheront.

[11] En général, les spams sont plus répétitifs que les emails réguliers. Ils veulent marteler ce message. Je ne permets actuellement pas de doublons dans les 15 premiers tokens, car vous pourriez obtenir un faux positif si l'expéditeur utilise par hasard un mot inapproprié plusieurs fois. (Dans mon filtre actuel, ``dick'' a une probabilité de spam de 0,9999, mais c'est aussi un nom.) Il semble que nous devrions au moins remarquer la duplication, donc je pourrais essayer de permettre jusqu'à deux de chaque token, comme le fait Brian Burton dans SpamProbe.

[12] C'est ce vers quoi des approches comme Brightmail se dégénéreront une fois que les spammeurs seront poussés à utiliser des techniques de mad-lib pour générer tout le reste dans le message.

[13] On soutient parfois que nous devrions travailler sur le filtrage au niveau du réseau, car c'est plus efficace. Ce que les gens veulent généralement dire quand ils disent cela, c'est : nous filtrons actuellement au niveau du réseau, et nous ne voulons pas recommencer à zéro. Mais vous ne pouvez pas dicter le problème pour qu'il corresponde à votre solution.

Historiquement, les arguments de ressources rares ont été le côté perdant dans les débats sur la conception logicielle. Les gens ont tendance à les utiliser uniquement pour justifier des choix (l'inaction en particulier) faits pour d'autres raisons.

Remerciements à Sarah Harlin, Trevor Blackwell et Dan Giffin pour avoir lu des brouillons de cet article, et à Dan encore pour la plupart de l'infrastructure sur laquelle ce filtre fonctionne.

Liés :

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