Filtres Bayésiens - Livre blanc

Tous les grands outils anti-spam côté client (vous, l'internaute, par opposition aux outils anti-spam côté serveur) sont dotés d'un filtre bayésiens [9]. De très nombreuses solutions sont open-source dont les clients de messagerie de la fondation Mozilla (Mozilla Suite et Thunderbird) qui intègre un filtre bayésien directement au niveau du client. Des outils anti-spam parmi les plus efficaces, gratuits, s'implantent entre Internet et votre client de messagerie et certains, comme SpamPal, combinent des filtres à règles et un filtre bayésien (SpamPal, le meilleur anti-spam gratuit, combine également des listes noires de blocages tenues en temps réel - RBL et de nombreuses autres technologies).

Les serveurs de messagerie peuvent également trouver des outils disposant de filtres bayésiens comme Bogofilter [3] ou Spambayes [4] [9].

Le théorème de Thomas Bayes, un mathématicien et pasteur presbytérien anglais du 18ème siècle (1702 - 17 avril 1761), fut publié après sa mort, dans le Philosophical Transactions of the Royal Society of London en 1764 sous l'impulsion de l'un de ses amis, Richard Price, qui l'introduisait ainsi :

...find out a method by which we might judge concerning the probability that an event has to happen, in given circumstances, upon supposition that we know nothing concerning it but that, under the same circumstances, it has happened a certain number of times, and failed a certain other number of times.

...rechercher une méthode par laquelle nous pourrions juger de la probabilité qu'un événement se produise, dans des circonstances données, sur la supposition que nous ne savons rien au sujet de lui mais que, dans les mêmes circonstances, il s'est déjà produit un certain nombre de fois, et a échoué un certain nombre d'autres fois.

Les conclusions de ce théorème furent acceptées par Laplace en 1781, redécouvertes par Condorcet en 1785 (théorie des probabilités), discutées par Boole (a qui l'on doit l'algèbre booléenne et la théorie des ensembles) en 1854 (Lois de la pensée)...

Alors qu'aucun papier de Thomas Bayes ne fut publié de son vivant, ce théorème est aujourd'hui largement utilisé dans des domaines aussi divers que la génétique, les prévisions boursières, les prévisions météorologiques, les systèmes prédictifs de détection d'intrusion, les causalités de crimes, les investigations et détections de crimes, les prédictions de lieu de prochains crimes par des polices, l'attente des taxis...

C'est tout récemment que le théorème de Bayes s'applique au Spam. En Août 2002, Paul Graham publie "A plan for Spam". [1] C'est un spécialiste de Lisp, pas un statisticien. Pour les anti-spam, son article à une portée considérable et tout le monde s'engouffre dans ses algorithmes. Son algorithme est faux mais fonctionnel. Des mathématiciens apportent des critiques constructives. Dès Janvier 2003 Paul Graham publie une amélioration de son algorithme. [2] et mentionne des travaux antérieurs, de 1998 [5] et [6]. Il y a aussi l'article de William Baldwin - 21.09.1998 [7]. En remontant dans le temps, on note que des travaux précédents portaient sur la classification des documents par un ordinateur (gestion documentaire), mais dès 1996 ils portent aussi sur le classement des e-mail et dès 1998 ils portent sur le classement des Spam, terme employé très librement dans les textes sans qu'il soit besoin de l'expliquer, donc il est déjà dans les usages, alors que c'est à peine 4 ans auparavant qu'il vient d'être utilisé dans ce sens pour la première fois et que le spam et à peine en émergence.

Il va s'agir de reconnaître la fréquence (le nombre d'occurrences et leur distribution statistique) des mots dans un texte, chaque mot étant converti en un "poids" faisant basculer le texte entier en "Spam" ou "Non Spam". Le "poids" des mots repose sur un système d'apprentissage du filtre bayésien, particulier à chaque internaute. Ainsi le même filtre bayésien donnera des réponses différentes et personnalisées dans la discrimination en deux classes d'objets : "Spam" ou "Non Spam" selon la phase d'apprentissage, sans arrêt mise à jour et de plus en plus précise, que lui aura donné son utilisateur. Chaque fois que le filtre se trompe, il faut le lui dire. Un seul clic suffit sur une zone prévue à cet effet pour corriger le filtre.

Il est admis qu'il faut un corpus d'environ 1.000 Spam et 1.000 correspondances légitimes pour éduquer un filtre bayésien.

Un nouvel internaute procèdera avec le temps et, selon la quantité de correspondances reçue, mettra 2 ou 3 mois à éduquer son filtre.
Un internaute ayant des archives de messages qu'il a déjà classées dans ses répertoires de correspondances légitimes pourra s'en renvoyer un millier (sur une boîte à détruire après l'opération) et éduquer son filtre : aucun message de cet envoi ne doit être détecté en Spam. Puis, s'il n'a pas vidé sa poubelle et qu'elle ne contient que des correspondances de type spam (pas des correspondances légitimes qu'il a lues puis mis à la poubelle), il pourra s'en renvoyer un millier (également sur une boîte à détruire après l'opération) et éduquer son filtre : tous les messages de cet envoi doivent être détectés en Spam.
Lorsqu'un filtre bayésien est mutualisé, son éducation risque d'être difficile et ses résultats antagonistes pour les uns et les autres. Dans une même entreprise un filtre bayésien mutualisé peut classer en Spam une correspondance publicitaire dont le service marketing aurait besoin pour étudier la concurence dans sa forme et son fond. A contrario, la secrétaire ne comprendrait pas pourquoi le service informatique laisse passer de telles inepties. Quant au service informatique de cette même société, il requiert la réception de quantité de correspondances en langue anglaise, parlant de virus, hoax, spam, failles de sécurité, en provenance de sources trop nombreuses pour être identifiées en liste blanche, tandis que le reste du personnel risque de s'énerver lors de telles réceptions.

On obtient des taux record de réussite tournant entre 95 à 98% (seulement !) de détection sans erreur. Il y a donc, dans les correspondances déclarées Spam, 2 à 5% de correspondances légitimes (ce qui peut être catastrophique si le courrier légitime classé en spam est important) et il y a, dans les correspondances classées "légitimes" par les filtres bayésiens les meilleurs, quelques spams qui passent au travers (ce qui peut également être catastrophique s'il s'agit d'une arnaque, de phishing etc. ...). Le but ultime de 100% de discrimination sans erreur dans les 2 classes d'objets n'est probablement pas atteignable par les calculs probabilistes des filtres bayésiens. Il y a donc toujours ce reliquat inexpugnable d'erreurs ("faux positifs" et "faux négatifs") qui fait que l'on ne peut jamais détruire automatiquement le courrier classé Spam par un outil anti-spam, au risque de détruire des correspondances légitimes.

La situation idyllique suivante n'existe pas.

La situation réaliste est plutôt la suivante.
Pourquoi ? Pour nous, les êtres humains, la discrimination entre Spam et Non Spam est instantanée et sans ambiguïté. Il n'est souvent même pas nécessaire de lire le corps de la correspondance pour décider. Son enveloppe suffit (expéditeur, sujet). Nous utilisons un mécanisme cognitif qui se base sur l'expérience acquise et d'autres critères, comme l'intuition, totalement impossibles à reproduire dans un système d'intelligence artificielle et sa sous-classe, la reconnaissance de forme (discrimination) à laquelle appartiennent des filtres bayésiens. Au mieux, nous obtiendrons les résultats suivants :

Ressources

[1] Paul Graham - "A plan for Spam". Août 2002
http://www.paulgraham.com/paulgraham/spam.html

[2] Paul Graham - "Better Bayesian Filtering"
http://www.paulgraham.com/paulgraham/better.html

[3] BogoFilter
http://bogofilter.sourceforge.net/

[4] SpamBayes
http://spambayes.sourceforge.net

[5] A Bayesian Approach to Filtering Junk E-mail
Mehran Sahami, Susan Dumais, David Heckerman, and Eric Horvitz
http://research.microsoft.com/~horvitz/junkfilter.htm

[6] Patrick Pantel and Dekang Lin. 11 mars 1998. SpamCop
A Spam Classification & Organization Program
http://www.isi.edu/~pantel/Download/Papers/aaai98.pdf

[7] Forbes magazine - Spam killers - William Baldwin - 21.09.1998
http://www.forbes.com/free_forbes/1998/0921/6206254a.html

[8] William W. Cohen - Learning rules that classify e-mails
In AAAI Spring Symposium on Machines Learning for Information Access - 1996
Pas disponible en ligne.

[9] Inventaire des 70 filtres bayésiens en mai 2004.
Cette liste est maintenue par Paul Graham mais est reproduite ici car toutes ses pages contiennent des Web Bug (280 Web Bug rien que sur la page d'inventaire des filtres bayésiens ce qui la rend totalement illisible selon les outils anti-web-bug dont on dispose). Pour être complet, ces Web Bug sont, en sus, sur une machine bloquée par toutes les listes hosts.

Filtres Bayésiens - Livre blanc - Anti-spam

Filtres Bayésiens - Livre blanc - Anti-spam

Nouvelle adresse du site Assiste.com depuis le 22 octobre 2012 : http://assiste.com