Filtrage Bayésien Amélioré | Essais de Paul Graham

Janvier 2003

(Cet article a été présenté lors d'une conférence sur le spam en 2003. Il décrit le travail que j'ai effectué pour améliorer les performances de l'algorithme décrit dans Un Plan contre le 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 articles de recherche. Il suffit d'écrire ce que l'on veut sans citer de travaux antérieurs, et des lecteurs indignés vous enverront des références à tous les articles que vous auriez dû citer. J'ai découvert cet algorithme après la publication de « Un Plan contre le Spam » [1] sur Slashdot.

Le filtrage du spam est un sous-ensemble de la classification de texte, un domaine bien établi, mais les premiers articles sur le filtrage bayésien du spam per se semblent avoir été deux présentés à 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'intéressaient 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 détectait que 92 % du spam, avec 1,16 % de faux positifs.

Lorsque j'ai essayé d'écrire un filtre anti-spam bayésien, il a détecté 99,5 % du spam avec moins de 0,03 % de faux positifs [4]. Il est toujours alarmant de voir deux personnes tentant la même expérience obtenir des résultats très divergents. C'est particulièrement alarmant ici car ces deux ensembles de chiffres pourraient mener à 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 qu'il l'est.

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 éléments qui expliquent probablement la différence.

L'une des raisons est simplement qu'ils ont entraîné leur filtre sur très peu de données : 160 spams et 466 courriels non-spams. Les performances du filtre devraient encore augmenter avec des ensembles de données aussi petits. Leurs chiffres pourraient donc ne même pas être une mesure précise des performances de leur algorithme, et encore moins du filtrage bayésien du spam 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 anti-spam, cela semblera une décision perverse. Et pourtant, dans les tout premiers filtres que j'ai essayé d'écrire, j'ai aussi ignoré les en-têtes. Pourquoi ? Parce que je voulais garder le problème propre. Je ne connaissais pas grand-chose aux en-têtes de courriel à l'époque, et ils me semblaient remplis de choses aléatoires. Il y a une leçon ici pour les développeurs de filtres : n'ignorez pas les données. On pourrait penser 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 « stemmé » les jetons, ce qui signifie qu'ils ont réduit par exemple « mailing » et « mailed » à la racine « mail ». Ils ont peut-être eu l'impression d'être contraints de le faire en raison de 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 jetons, alors que je n'utilise que les 15 plus significatifs. Si vous utilisez tous les jetons, vous aurez tendance à manquer les spams plus longs, du type où quelqu'un vous raconte sa vie jusqu'au moment où il est devenu riche grâce à un système de marketing 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 introduit de biais contre les faux positifs. Je pense que tout algorithme de filtrage du 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. Je le fais en comptant double les occurrences des jetons dans le corpus non-spam.

Je ne pense pas que ce soit une bonne idée de traiter le filtrage du 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 courriel, et du spam en particulier. Le courriel n'est pas seulement du texte ; il a une structure. Le filtrage du spam n'est pas seulement de la classification, car les faux positifs sont tellement pires que les faux négatifs qu'il faut les traiter comme un type d'erreur différent. Et la source de l'erreur n'est pas seulement une variation aléatoire, mais un spammeur humain actif qui travaille à déjouer votre filtre.

Jetons

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

Une fois que j'ai compris comment CRM114 fonctionnait, il m'a semblé inévitable que je doive un jour 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 des mots uniques. Et la réponse est : étonnamment loin.

J'ai surtout travaillé sur une tokenisation plus intelligente. Sur le spam actuel, j'ai pu atteindre des taux de filtrage qui se rapprochent de ceux de CRM114. Ces techniques sont pour la plupart orthogonales à celles de Bill ; une solution optimale pourrait intégrer les deux.

« Un Plan contre le 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'ignorais également la casse.

J'ai maintenant une définition plus complexe d'un jeton :

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 apparaissent entre deux chiffres. Cela me permet de conserver les adresses IP et les prix intacts.
Une fourchette de prix comme 20-25 $ donne deux jetons, 20 $ et 25 $.
Les jetons qui apparaissent dans les lignes To, From, Subject et Return-Path, ou dans les URL, sont marqués en conséquence. Par exemple, « foo » dans la ligne Subject devient « Subject*foo ». (L'astérisque peut ê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 jeton dans le corps du message n'a qu'une probabilité de spam de 65 %.

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

Subject*FREE      0.9999  
free!!            0.9999  
To*free           0.9998  
Subject*free      0.9782  
free!             0.9199  
Free              0.9198  
Url*free          0.9091  
FREE              0.8747  
From*free         0.7636  
free              0.6546

Dans le filtre « Un Plan contre le Spam », tous ces jetons auraient eu la même probabilité, 0,7602. Ce filtre reconnaissait environ 23 000 jetons. Le filtre actuel en reconnaît environ 187 000.

L'inconvénient d'avoir un univers de jetons plus grand est qu'il y a plus de chances de manquer des correspondances. 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 des constituants, par exemple, vous pourriez ne pas avoir de probabilité de spam pour « free » avec sept points d'exclamation, même si vous savez que « free » 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 les points d'exclamation terminaux, les lettres majuscules et l'occurrence dans l'un des cinq contextes marqués comme rendant un jeton plus spécifique. Par exemple, si je ne trouve pas de probabilité pour « Subjectfree! », je cherche les probabilités pour « Subjectfree », « free! » et « free », et je prends celle qui est la plus éloignée 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.

Subject*Free!!!  
Subject*free!!!  
Subject*FREE!  
Subject*Free!  
Subject*free!  
Subject*FREE  
Subject*Free  
Subject*free  
FREE!!!  
Free!!!  
free!!!  
FREE!  
Free!  
free!  
FREE  
Free  
free

Si vous faites cela, assurez-vous de considérer les versions avec majuscules initiales ainsi que toutes les versions en majuscules et en minuscules. Les spams ont tendance à contenir plus de phrases à l'impératif, et dans celles-ci, le premier mot est un verbe. Ainsi, les verbes avec 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 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, ce ne sont plus les mêmes jetons. Mais si cela vous dérange toujours, 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 examinez un courriel entrant, vous trouvez des jetons plus intéressants, c'est-à-dire ceux dont les probabilités sont éloignées de 0,5. J'utilise les 15 plus intéressants pour décider si un courriel est du spam. Mais vous pouvez rencontrer un problème lorsque vous utilisez un nombre fixe comme celui-ci. Si vous trouvez beaucoup de jetons maximalement intéressants, le résultat peut finir par être décidé par n'importe quel facteur aléatoire qui détermine l'ordre des jetons également intéressants. Une façon de gérer cela est de traiter 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, tel que je calculais les probabilités pour les jetons, les deux auraient la même probabilité de spam, le seuil de 0,99.

Cela ne semble pas juste. Il existe des arguments théoriques pour donner à ces deux jetons 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 jetons qui n'apparaissent que dans un seul corpus ou l'autre, nous devrions donner la priorité à ceux qui apparaissent beaucoup. Il y a donc maintenant deux valeurs seuils. Pour les jetons 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 jetons trouvés uniquement dans le corpus légitime.

Je pourrais plus tard ajuster substantiellement les probabilités des jetons, mais cette petite quantité d'ajustement garantit au moins que les jetons sont triés correctement.

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

Enfin, que faire du HTML ? J'ai essayé tout le spectre d'options, de l'ignorer à le parser entièrement. Ignorer le HTML est une mauvaise idée, car il est plein de signes de spam utiles. Mais si vous le parsez entièrement, votre filtre pourrait dégénérer en un simple reconnaisseur HTML. L'approche la plus efficace semble être la voie médiane, de 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 URL.

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 intelligents l'évitent déjà. Les performances futures ne devraient donc 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 sont passés. Cela représente un taux de filtrage d'environ 99,75 %.

Deux des quatre spams que j'ai manqués sont passés parce qu'ils utilisaient des mots qui apparaissent souvent dans mes courriels légitimes.

Le troisième était l'un de ceux qui exploitent un script CGI non sécurisé pour envoyer des courriels à des tiers. Ils sont difficiles à filtrer uniquement sur la base du 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 est passé de justesse avec une probabilité de 0,88, juste en dessous du seuil de 0,9.

Bien sûr, l'examen de séquences de jetons multiples le détecterait facilement. « Ci-dessous le résultat de votre formulaire de commentaires » est un indice instantané.

Le quatrième spam était ce que j'appelle un spam du futur, car c'est ce que j'attends du spam : un texte complètement neutre suivi d'une URL. Dans ce cas, il provenait 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 publicité 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 riposter en envoyant un crawler 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, cela ne sera pas rentable 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 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 les filtres statistiques s'avèrent être des courriels qui ressemblent beaucoup à du spam, et ce sont généralement ceux que vous regretteriez le moins de manquer [9].

Deux des faux positifs étaient des newsletters de sociétés auprès desquelles j'avais acheté des choses. Je n'avais jamais demandé à les recevoir, donc on pourrait dire que c'étaient des spams, mais je les compte comme des faux positifs car je ne les avais pas supprimés comme des spams auparavant. La raison pour laquelle les filtres les ont détectés est que les deux sociétés ont, en janvier, opté pour des expéditeurs de courriels commerciaux au lieu d'envoyer les courriels depuis leurs propres serveurs, et les en-têtes et les corps de message sont devenus beaucoup plus « spammy ».

Le troisième faux positif était cependant un mauvais. Il provenait 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 « Un Plan contre le Spam » ne l'aurait pas détecté.

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 courriels, il est difficile de dire s'ils sont du spam ou non, et ce sont ceux que vous finissez par examiner lorsque vos filtres deviennent vraiment stricts. Par exemple, jusqu'à présent, le filtre a détecté deux courriels 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 ce ne sont ni mes spams ni mes courriels non-spams.

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 via les serveurs de messagerie de Virtumundo, elle contenait les en-têtes les plus incriminants imaginables. On pourrait dire que ce n'est pas non plus un vrai faux positif, mais une sorte d'effet d'incertitude de Heisenberg : je ne l'ai reçu que parce que j'écrivais sur le filtrage du spam.

Sans compter ceux-ci, j'ai eu un total de cinq faux positifs jusqu'à présent, sur environ 7740 courriels légitimes, soit un taux de 0,06 %. Les deux autres étaient un avis de rupture de stock pour quelque chose que j'avais acheté, 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 corriger le filtre pour qu'il n'en détecte pas 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 performance. Les faux positifs, je les considère davantage 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.

Ces cinq faux positifs constituent donc ma liste de bugs. Par exemple, le courriel d'Égypte a été détecté parce que le texte en majuscules le faisait ressembler, pour le filtre, à un spam nigérian. C'est vraiment une sorte de bug. Comme pour le HTML, le fait que le courriel soit entièrement en majuscules est conceptuellement une seule caractéristique, pas une pour chaque mot. Je dois gérer la casse de manière plus sophistiquée.

Alors, que faire de ces 0,06 % ? Pas grand-chose, je pense. On pourrait le considérer comme une borne 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 intrinsèque de faux positifs du filtrage bayésien.

Avenir

Et ensuite ? Le filtrage est un problème d'optimisation, et la clé de l'optimisation est le profilage. N'essayez pas de deviner où votre code est lent, car vous vous tromperez. Regardez où votre code est lent, et corrigez cela. En matière de filtrage, cela se traduit par : examinez les spams que vous manquez, et déterminez ce que vous auriez pu faire pour les détecter.

Par exemple, les spammeurs travaillent maintenant agressivement pour échapper aux 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 cela n'est pas ma première priorité, car je n'ai toujours aucune difficulté à détecter ces spams [10].

Il y a deux types de spams avec lesquels j'ai actuellement des difficultés. 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 parce que c'est le seul type de discours commercial que l'on peut faire sans utiliser de langage commercial. Ils utilisent le même vocabulaire que les courriels ordinaires.

L'autre type de spams que j'ai du mal à filtrer sont ceux provenant d'entreprises, par exemple en Bulgarie, offrant des services de programmation sous contrat. Ceux-ci passent parce que je suis aussi un programmeur, et les spams sont remplis des mêmes mots que mes vrais courriels.

Je me concentrerai probablement 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 mes vrais courriels. Le style d'écriture est certainement différent, bien qu'il puisse falloir un filtrage multi-mots pour le détecter. De plus, je remarque qu'ils ont tendance à répéter l'URL, et quelqu'un incluant une URL dans un courriel légitime ne ferait pas cela [11].

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

Le filtrage statistique nous mènera-t-il réellement à ce point ? Je ne sais pas. Pour moi personnellement, le spam n'est pas un problème actuellement. 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 à franchir, les spammeurs sont assez efficaces pour le contourner. Il existe déjà une entreprise appelée Assurance Systems qui fera passer votre courriel par Spamassassin et vous dira s'il sera filtré.

Les filtres au niveau du réseau ne seront pas complètement inutiles. Ils pourraient suffire à éliminer tout le spam « opt-in », c'est-à-dire le spam provenant d'entreprises comme Virtumundo et Equalamail qui affirment gérer des listes d'opt-in. Vous pouvez les filtrer uniquement sur la base des en-têtes, peu importe ce qu'ils disent dans le corps du message. Mais quiconque est prêt à falsifier les en-têtes ou à utiliser des relais ouverts, y compris probablement la plupart des spammeurs pornographiques, devrait pouvoir faire passer un message par les filtres au niveau du réseau s'il le souhaite. (Cependant, pas du tout le message qu'ils aimeraient envoyer, ce qui est déjà ça.)

Le type de filtres pour lesquels je suis optimiste sont ceux qui calculent les probabilités en fonction du courriel 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 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 la boucle d'optimisation des spammeurs, ce que les programmeurs appelleraient leur cycle d'édition-compilation-test, effroyablement lente. Au lieu de simplement ajuster un spam jusqu'à ce qu'il passe à travers une copie d'un filtre qu'ils ont sur leur bureau, ils devront faire un envoi de test pour chaque ajustement. Ce serait comme programmer dans un langage sans toplevel interactif, et je ne souhaiterais cela à personne.

Notes

[1] Paul Graham. « Un Plan contre le Spam. » Août 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 les mots) sont indépendantes, et que nous ne savons rien de la probabilité a priori qu'un courriel soit du spam.

La première hypothèse est largement 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 est que la proportion de spam dans mes courriels entrants fluctuait tellement de jour en jour (voire d'heure en heure) que le rapport a priori global semblait sans valeur comme prédicteur. Si vous supposez que P(spam) et P(non-spam) sont tous deux de 0,5, ils s'annulent et vous pouvez les supprimer de la formule.

Si vous faisiez du filtrage bayésien dans une situation où le rapport spam/non-spam était constamment très élevé ou (surtout) très faible, vous pourriez probablement améliorer les performances du filtre en incorporant des probabilités a priori. Pour bien faire cela, il faudrait suivre les ratios par heure de la journée, car le volume de spam et de courriels légitimes ont tous deux des schémas quotidiens distincts.

[2] Patrick Pantel et Dekang Lin. « SpamCop – Un programme de classification et d'organisation du spam. » 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. « Une approche bayésienne du filtrage des courriels indésirables. » Actes de l'atelier AAAI-98 sur l'apprentissage pour la catégorisation de texte.

[4] À l'époque, j'avais zéro faux positif sur environ 4 000 courriels légitimes. Si le courriel légitime suivant é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. « Filtrage de messages par hachage polynomial binaire épars et le discriminateur CRM114. » Actes de la Conférence sur le Spam 2003.

[6] Dans « Un Plan contre le Spam », j'utilisais des seuils de 0,99 et 0,01. Il semble justifiable d'utiliser des seuils proportionnels à la taille des corpus. Puisque j'ai maintenant de l'ordre de 10 000 courriels de chaque type, j'utilise 0,9999 et 0,0001.

[7] Il y a un défaut ici que je devrais probablement corriger. Actuellement, lorsque « Subjectfoo » 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 suivre les statistiques pour « foo » dans l'ensemble ainsi que pour des versions spécifiques, et dégénérer de « Subjectfoo » non pas à « foo » mais à « Anywhere*foo ». Idem pour la casse : je devrais dégénérer des majuscules à n'importe quelle casse, pas aux minuscules.

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

Vous pourriez aussi dégénérer des mots à leurs racines (stems), mais cela n'améliorerait probablement les taux de filtrage qu'au début, lorsque vous aviez de petits corpus.

[8] Steven Hauser. « Le filtre anti-spam statistique fonctionne pour moi. » 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 quasi-spams que vous ne regretteriez pas de manquer, les faux positifs causés par les listes noires, par exemple, seront simplement des courriels de personnes qui ont choisi le mauvais FAI. Dans les deux cas, vous détectez des courriels 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 jetons au point 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 original serait en soi une preuve de spam.

Extraire les mots ne sera pas trivial. Cela nécessitera plus que la simple reconstruction des limites de mots ; les spammeurs ajoutent (par exemple, « xHot nPorn cSite ») et omettent (par exemple, « P#rn ») des lettres. La recherche en vision peut ê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 courriels normaux. Ils veulent marteler ce message. Actuellement, je n'autorise pas les doublons dans les 15 premiers jetons, car vous pourriez obtenir un faux positif si l'expéditeur utilise un mauvais mot 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 d'autoriser jusqu'à deux de chaque jeton, comme le fait Brian Burton dans SpamProbe.

[12] C'est ce en quoi les approches comme celle de Brightmail dégénéreront une fois que les spammeurs seront contraints d'utiliser des techniques de type « mad-lib » pour générer tout le reste du 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 par là, 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é du côté des perdants dans les débats sur la conception de logiciels. Les gens ont tendance à ne les utiliser que pour justifier des choix (l'inaction en particulier) faits pour d'autres raisons.

Remerciements à Sarah Harlin, Trevor Blackwell et Dan Giffin pour la lecture des ébauches de cet article, et à Dan encore pour la majeure partie de l'infrastructure sur laquelle ce filtre fonctionne.

Articles liés :