MEILLEUR FILTRAGE BAYÉSIEN

Janvier 2003

(Cet article a été présenté sous forme de conférence à la Spam Conference de 2003. Il décrit le travail que j'ai effectué 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 je voudrais présenter ici est un algorithme pour l'évaluation paresseuse des documents de recherche. Il suffit d'écrire ce que l'on veut et de ne citer aucun travail antérieur, et les lecteurs indignés vous enverront des références à tous les documents que vous auriez dû citer. J'ai découvert cet algorithme après que "A Plan for Spam" [1] a été publié sur Slashdot.

Le filtrage anti-spam est un sous-ensemble du classement de texte, qui est un domaine bien établi, mais les premiers articles sur le filtrage anti-spam bayésien en tant que tel 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 ces travaux, j'ai été un peu surpris. Si les gens s'étaient penchés sur le filtrage bayésien il y a quatre ans, pourquoi tout le monde ne l'utilisait-il pas ? Quand j'ai lu les articles, j'ai compris pourquoi. Le filtre de Pantel et Lin était le plus efficace des deux, mais il ne captait que 92% du spam, avec 1,16% de faux positifs.

Quand j'ai essayé d'écrire un filtre anti-spam bayésien, il captait 99,5% du spam avec moins de 0,03% de faux positifs [4]. C'est toujours alarmant quand deux personnes essayant la même expérience obtiennent des résultats très divergents. C'est particulièrement alarmant ici car ces deux séries de chiffres pourraient conduire à des conclusions opposées. Les différents utilisateurs ont des exigences différentes, mais je pense que pour de nombreuses personnes, un taux de filtrage de 92% avec 1,16% de faux positifs signifie que le filtrage n'est pas une solution acceptable, alors que 99,5% avec moins de 0,03% de faux positifs signifie que c'en est une.

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 à la lecture de l'article, je vois cinq choses qui expliquent probablement la différence.

La première est simplement qu'ils ont entraîné leur filtre sur très peu de données : 160 spams et 466 non-spams. Les performances du filtre devraient encore s'améliorer avec des jeux de données aussi petits. Donc leurs chiffres ne sont peut-être même pas une mesure précise des performances de leur algorithme, encore moins du filtrage anti-spam bayésien en général.

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

Troisièmement, Pantel et Lin ont réduit les jetons, c'est-à-dire qu'ils ont ramené par exemple à la racine "mail" à la fois "mailing" et "mailed". Ils ont peut-être senti qu'ils y étaient forcés par la petite taille de leur corpus, mais dans ce 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 jetons, alors que moi je n'utilise que les 15 plus significatifs. Si vous utilisez tous les jetons, vous aurez tendance à manquer les spams plus longs, le type où quelqu'un vous raconte son histoire de vie jusqu'au moment où il s'est enrichi grâce à un système de vente multiniveau. Et un tel algorithme serait facile à tromper pour les spammeurs : il suffirait d'ajouter un gros bloc 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 anti-spam devrait avoir un bouton pratique que l'on peut tourner pour diminuer le taux de faux positifs au détriment du taux de filtrage. C'est ce que je fais en comptant les occurrences des jetons dans le corpus de non-spam le double.

Je ne pense pas que ce soit une bonne idée de traiter le filtrage anti-spam comme un simple problème de classification de texte. On peut utiliser des techniques de classification de texte, mais les solutions peuvent et doivent refléter le fait que le texte est un e-mail, et en particulier du spam. L'e-mail n'est pas seulement du texte ; il a une structure. Le filtrage anti-spam n'est pas seulement de la classification, car les faux positifs sont tellement pires que les faux négatifs qu'on devrait les traiter comme un type d'erreur différent. Et la source d'erreur n'est pas seulement une variation aléatoire, mais un spammeur humain vivant qui travaille activement pour contourner votre filtre.

Jetons

Un autre projet dont j'ai entendu parler après l'article de Slashdot était le CRM114 de Bill Yerazunis [5]. C'est le contre-exemple du principe de conception que je viens de mentionner. C'est un simple classificateur de texte, 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 fonctionnait le CRM114, il m'a semblé inévitable que je devrais finir par passer du filtrage basé sur des mots uniques à une approche comme celle-ci. Mais d'abord, me suis-je dit, je vais voir jusqu'où je peux aller avec les mots uniques. Et la réponse est, de manière surprenante, assez loin.

J'ai surtout travaillé sur un découpage de jetons plus intelligent. Sur le spam actuel, j'ai pu atteindre des taux de filtrage qui s'approchent de ceux du CRM114. Ces techniques sont en grande partie orthogonales à celles de Bill ; une solution optimale pourrait les incorporer toutes les deux.

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

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

La casse est préservée.

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

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

Une fourchette de prix comme 20-25 $ donne deux jetons, 20 $ et 25 $.

Les jetons 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 Objet devient "Subject*foo". (L'astérisque pourrait être n'importe quel caractère que vous n'autorisez pas comme constitutif.)

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

Voici quelques-unes des probabilités actuelles [6] :

SujetGRATUIT 0.9999 gratuit!! 0.9999 Àgratuit 0.9998 Sujetgratuit 0.9782 gratuit! 0.9199 Gratuit 0.9198 Urlgratuit 0.9091 GRATUIT 0.8747 De*gratuit 0.7636 gratuit 0.6546

Dans le Plan pour le filtre anti-spam, tous ces jetons auraient eu la même probabilité, .7602. Ce filtre a reconnu environ 23 000 jetons. Celui actuel en reconnaît environ 187 000.

L'inconvénient d'avoir un plus grand univers de jetons est qu'il y a plus de risque de ratés. Répartir votre corpus sur plus de jetons a le même effet que de le rendre plus petit. Si vous considérez les points d'exclamation comme constituants, par exemple, vous pourriez finir par ne pas avoir de probabilité de spam pour gratuit avec sept points d'exclamation, même si vous savez que gratuit avec seulement deux points d'exclamation a une probabilité de 99,99%.

Une solution à cela est ce que j'appelle la dégénérescence. Si vous ne trouvez pas de correspondance exacte pour un jeton, 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 d'apparaître dans l'un des cinq contextes marqués rendent un jeton plus spécifique. Par exemple, si je ne trouve pas de probabilité pour Sujet*gratuit!'', je cherche des probabilités pour Sujet*gratuit'', gratuit!'', et gratuit'', et je prends celle qui est la plus éloignée de .5.

Voici les alternatives [7] envisagées si le filtre voit ``GRATUIT!!!'' dans le Sujet et n'a pas de probabilité pour celui-ci.

SujetGratuit!!! Sujetgratuit!!! SujetGRATUIT! SujetGratuit! Sujetgratuit! SujetGRATUIT SujetGratuit Sujetgratuit GRATUIT!!! Gratuit!!! gratuit!!! GRATUIT! Gratuit! gratuit! GRATUIT Gratuit gratuit

Si vous faites cela, assurez-vous également de prendre en compte les versions avec majuscules initiales ainsi que tout en majuscules et tout en 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 une majuscule initiale ont des probabilités de spam plus élevées que s'ils étaient tout en minuscules. Dans mon filtre, la probabilité de spam de Agir'' est de 98% et pour agir'' seulement de 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, ils ne sont plus le même jeton. Mais si cela vous dérange encore, laissez-moi ajouter d'expérience que les mots que vous semblez compter plusieurs fois sont exactement ceux que vous voudriez.

Un autre effet d'un vocabulaire plus important est que lorsque vous examinez un courrier entrant, vous trouvez plus de jetons intéressants, c'est-à-dire ceux avec des probabilités très éloignées de .5. J'utilise les 15 plus intéressants pour décider si un courrier est un spam. Mais vous pouvez rencontrer un problème lorsque vous utilisez un nombre fixe comme celui-ci. Si vous trouvez beaucoup de jetons extrêmement 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 jetons également intéressants. Une façon de gérer cela est de considérer certains comme plus intéressants que d'autres.

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

Cela ne semble pas juste. Il y a des arguments théoriques pour donner à ces deux jetons des probabilités sensiblement 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 jetons qui n'apparaissent que dans un seul corpus, nous devrions donner la priorité à ceux qui apparaissent le plus souvent. Donc maintenant il y a deux valeurs de seuil. Pour les jetons qui n'apparaissent que dans le corpus de spam, la probabilité est de .9999 s'ils apparaissent plus de 10 fois et .9998 sinon. Pareil à l'autre extrémité de l'échelle pour les jetons trouvés uniquement dans le corpus légitime.

Je pourrai plus tard mettre à l'échelle de manière substantielle les probabilités des jetons, mais cette légère mise à l'échelle assure au moins que les jetons sont triés dans le bon ordre.

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

Enfin, que doit-on faire à propos du html ? J'ai essayé tout le spectre des options, de l'ignorer à le parser complètement. Ignorer le html est une mauvaise idée, car il est rempli de signes de spam utiles. Mais si vous le parsez tout, votre filtre pourrait se dégrader en un simple reconnaisseur de html. L'approche la plus efficace semble être le juste milieu, pour remarquer certains jetons 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 regarder, car ils contiennent des urls.

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

Performances

Entre le 10 décembre 2002 et le 10 janvier 2003, j'ai reçu environ 1750 spams. Parmi ceux-ci, 4 ont passé. C'est un taux de filtrage d'environ 99,75%.

Deux des quatre spams que j'ai manqués ont passé parce qu'ils se trouvaient utiliser des mots qui apparaissent souvent dans mon courrier légitime.

Le troisième était l'un de ceux qui exploitent un script cgi non sécurisé pour envoyer du courrier à des tiers. Ils sont difficiles à filtrer sur la seule base du contenu car les en-têtes sont innocents et ils font attention aux mots qu'ils utilisent. Même ainsi, je peux généralement les attraper. Celui-ci s'est faufilé avec une probabilité de .88, juste en dessous du seuil de .9.

Bien sûr, en examinant plusieurs séquences de jetons, on le repérerait facilement. ``Voici le résultat de votre formulaire de commentaires'' est un indice immédiat.

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, il s'agissait de quelqu'un disant qu'il avait enfin terminé sa page d'accueil et me demandant d'aller la voir. (La page était bien sûr une publicité pour un site pornographique.)

Si les spammeurs font attention aux en-têtes et utilisent une URL fraîche, il n'y a rien dans le spam du futur que les filtres puissent remarquer. Nous pouvons bien sûr contrer en envoyant un robot d'exploration pour examiner 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 faible, ça ne paiera pas pour les spammeurs de l'envoyer, et nous n'aurons pas à travailler trop dur pour le filtrer.

Maintenant, 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. Quand j'ai écrit "Un plan contre le spam", je n'en avais pas eu, 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 produits par les filtres statistiques s'avèrent être des courriels qui ressemblent beaucoup à du spam, et ce sont généralement ceux que vous ne seriez pas trop déçu de manquer [[9]].

Deux des faux positifs étaient des bulletins d'information d'entreprises auprès desquelles j'ai acheté des choses. Je ne les ai jamais demandés, donc on pourrait les considérer comme du spam, mais je les compte comme des faux positifs car je ne les supprimais pas comme du spam auparavant. La raison pour laquelle les filtres les ont captés est que les deux entreprises sont passées en janvier à des expéditeurs de courriels commerciaux au lieu d'envoyer les courriels à partir de leurs propres serveurs, et à la fois les en-têtes et les corps sont devenus beaucoup plus spammeux.

Le troisième faux positif était mauvais, cependant. Il venait de quelqu'un en Égypte et était écrit entièrement en majuscules. C'était une conséquence directe du fait de rendre les jetons sensibles à la casse ; le filtre du plan contre le 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, sur le plan statistique. Quiconque a travaillé sur des filtres (du moins, des filtres efficaces) connaît ce problème. Avec certains courriels, il est difficile de dire s'il s'agit de spam ou non, et ce sont ceux-là que vous finissez par examiner lorsque vous rendez vos filtres vraiment serrés. Par exemple, jusqu'à présent, le filtre a intercepté deux courriels qui m'ont été envoyés à cause d'une faute de frappe, et un qui m'a été envoyé dans la croyance que j'étais quelqu'un d'autre. On pourrait dire que ce ne sont ni mon spam ni mon courrier non spam.

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

Sans compter ceux-ci, j'ai eu un total de cinq faux positifs jusqu'à présent, sur environ 7 740 courriels légitimes, soit 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 pouvoir ajuster le filtre pour ne pas en attraper certains.

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

Donc ces cinq faux positifs sont ma liste de bugs. Par exemple, le courriel d'Égypte s'est fait prendre parce que le texte en majuscules le faisait ressembler à un spam nigérian aux yeux du filtre. C'est vraiment une sorte de bug. Comme avec le HTML, le fait que le courriel soit tout en majuscules est en réalité conceptuellement une seule caractéristique, et non une par mot. Je dois gérer la casse de manière plus sophistiquée.

Alors que penser 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 davantage une mesure des bugs de ma mise en œuvre qu'un taux intrinsèque de faux positifs 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 cherchez pas à deviner où votre code est lent, car vous vous tromperez. Regardez où votre code est lent, et corrigez cela. Dans le filtrage, cela se traduit par : regardez les spams que vous manquez, et découvrez ce que vous auriez pu faire pour les attraper.

Par exemple, les spammeurs travaillent maintenant avec acharnement pour éviter les filtres, et l'une des choses qu'ils font est de fragmenter et de mal orthographier les mots pour empêcher les filtres de les reconnaître. Mais travailler sur ce sujet n'est pas ma priorité, car je n'ai toujours aucun mal à attraper ces spams [[10]].

Il y a deux types de spams avec lesquels j'ai actuellement du mal. L'un est le type qui prétend être un courriel d'une femme vous invitant à discuter avec elle ou à voir son profil sur un site de rencontres. Ceux-ci passent à travers parce que c'est le seul type de démarchage que l'on peut faire sans utiliser un langage de vente. Ils utilisent le même vocabulaire que les courriels ordinaires.

L'autre type de spams avec lesquels j'ai du mal à filtrer sont ceux provenant d'entreprises en Bulgarie par exemple, offrant des services de programmation sous contrat. Ceux-ci passent à travers parce que je suis moi-même programmeur, et les spams sont remplis des mêmes mots que mon vrai courrier.

Je me concentrerai probablement d'abord sur le type d'annonce personnelle. Je pense que si j'examine de plus près, je pourrai trouver des différences statistiques entre ceux-ci et mon vrai courrier. Le style d'écriture est certainement différent, bien qu'il faille peut-être un filtrage sur plusieurs mots pour le saisir. De plus, je remarque qu'ils ont tendance à répéter l'URL, alors que quelqu'un qui inclut une URL dans un courriel légitime ne le ferait pas [[11]].

Les offres d'externalisation vont être difficiles à attraper. Même si vous envoyiez un robot d'exploration sur le site, vous ne trouveriez pas de preuve statistique flagrante. Peut-être que la seule réponse est une liste centrale des domaines annoncés dans les spams [[12]]. Mais il ne peut pas y avoir tant de ce type de courrier. Si les seuls spams restants étaient des offres non sollicitées de services de programmation sous contrat en provenance de Bulgarie, nous pourrions probablement passer à autre chose.

Cela va-t-il vraiment nous mener à ce point ? Je ne sais pas. En ce moment, personnellement, le spam n'est pas un problème pour moi. Mais les spammeurs n'ont pas encore fait d'efforts 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 qui vaut la peine d'être franchi, les spammeurs sont assez efficaces pour y arriver. Il existe déjà une entreprise appelée Assurance Systems qui fera passer votre courrier 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 provenant d'entreprises comme Virtumundo et Equalamail qui prétendent exploiter des listes d'abonnés volontaires. Vous pouvez les filtrer en vous basant uniquement sur les en-têtes, quoi qu'ils disent dans le corps du message. Mais toute personne prête à falsifier les en-têtes ou à utiliser des relais ouverts, y compris la plupart des spammeurs de contenu pornographique, devrait pouvoir faire passer un certain message à travers les filtres au niveau du réseau s'ils le veulent. (Pas le message qu'ils voudraient envoyer, cependant, qui est quelque chose.)

Le type de filtres pour lesquels je suis optimiste sont ceux qui calculent les probabilités en fonction du courrier de chaque utilisateur individuel. Ceux-ci peuvent être beaucoup plus efficaces, non seulement pour éviter les faux positifs, mais aussi pour filtrer : par exemple, trouver l'adresse e-mail 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 chacun ont des probabilités différentes, cela rendra le cycle d'optimisation des spammeurs, ce que les programmeurs appelleraient leur cycle de modification-compilation-test, affreusement lent. Au lieu de simplement retoucher un spam jusqu'à ce qu'il passe à travers une copie du filtre qu'ils ont sur leur bureau, ils devront faire un envoi de test pour chaque retouche. Ce serait comme programmer dans un langage sans boucle interactive, et je ne le souhaiterais à personne.

Notes

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

Les probabilités de 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 de la probabilité a priori qu'un e-mail soit du 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 seconde hypothèse, je l'ai faite parce que la proportion de spam dans mon courrier entrant fluctuait tellement d'un jour à l'autre (en fait, d'une heure à l'autre) que le ratio global a priori semblait inutile comme prédicteur. Si vous supposez que P(spam) et P(non-spam) sont tous deux de .5, ils s'annulent et vous pouvez les supprimer de la formule.

Si vous faites un filtrage bayésien dans une situation où le ratio de spam à non-spam est systématiquement très élevé ou (surtout) très faible, vous pourriez probablement améliorer les performances du filtre en intégrant les probabilités a priori. Pour bien faire, vous devriez suivre les ratios par heure de la journée, car le volume de spam et de courrier légitime ont tous deux des schémas quotidiens distincts.

[2] Patrick Pantel et Dekang Lin. ``SpamCop-- A Spam Classification & Organization Program.'' Actes de l'atelier AAAI-98 sur l'apprentissage pour la catégorisation de texte.

[3] Mehran Sahami, Susan Dumais, David Heckerman et Eric Horvitz. ``A Bayesian Approach to Filtering Junk E-Mail.'' Actes de l'atelier AAAI-98 sur l'apprentissage pour la catégorisation de texte.

[4] À l'époque, j'avais zéro faux positifs sur environ 4 000 e-mails légitimes. Si le prochain e-mail légitime était un faux positif, cela nous donnerait 0,03 %. Ces taux de faux positifs sont peu 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.'' Actes de la conférence Spam de 2003.

[6] Dans "A Plan for Spam", j'ai utilisé des seuils de 0,99 et 0,01. Il semble justifié d'utiliser des seuils proportionnels à la taille des corpus. Comme j'ai maintenant de l'ordre de 10 000 de chaque type de courrier, j'utilise 0,9999 et 0,0001.

[7] Il y a ici un défaut que je devrais probablement corriger. Actuellement, lorsque "Subjectfoo" se dégrade en simple "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 j'ai marquées. Ce que je devrais faire, c'est garder la trace des statistiques pour "foo" dans l'ensemble, ainsi que des versions spécifiques, et dégrader de "Subjectfoo" non pas vers "foo" mais vers "Anywhere*foo". Idem pour la casse : je devrais dégrader de majuscules vers tout-en-un-cas, pas vers minuscules.

Ce serait probablement un gain de faire la même chose avec les prix, par exemple de dégrader de "$129.99" vers "$--9.99", "$--.99", et "$--".

Vous pourriez également dégrader des mots vers leurs radicaux, mais cela n'améliorerait probablement les taux de filtrage que dans les premiers temps 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 lorsque nous comparons les techniques pour arrêter le spam. Alors que de nombreux faux positifs causés par les filtres seront des presque-spams que vous ne regretteriez pas de manquer, les faux positifs causés par les listes noires, par exemple, seront juste du courrier de personnes qui ont choisi le mauvais FAI. Dans les deux cas, vous interceptez du courrier qui est proche du spam, mais pour les listes noires, la proximité est physique, et pour les filtres, elle est textuelle.

[10] Si les spammeurs deviennent assez bons pour obscurcir les jetons pour que cela devienne un problème, nous pouvons réagir 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 d'origine serait en soi une preuve de spam.

Extraire les mots ne sera pas trivial. Cela nécessitera plus que la simple reconstruction des limites 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 tels stratagèmes viseront à atteindre.

[11] En général, les spams sont plus répétitifs que les e-mails ordinaires. Ils veulent marteler ce message. Actuellement, je n'autorise pas les doublons dans les 15 principaux jetons, car vous pourriez obtenir un faux positif si l'expéditeur utilise par hasard un mauvais mot plusieurs fois. (Dans mon filtre actuel, ``dick'' a une probabilité de spam de .9999, mais c'est aussi un nom.) Il semble que nous devrions au moins remarquer la duplication, donc je peux essayer d'autoriser jusqu'à deux de chaque jeton, comme le fait Brian Burton dans SpamProbe.

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

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

Historiquement, les arguments de ressources rares ont été du côté perdant dans les débats sur la conception des logiciels. Les gens ne les utilisent que pour justifier des choix (l'inaction en particulier) faits pour d'autres raisons.

Merci à Sarah Harlin, Trevor Blackwell et Dan Giffin pour avoir lu les brouillons de cet article, et à Dan à nouveau pour la majeure partie de l'infrastructure sur laquelle ce filtre fonctionne.

Lié :

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