La formule de Bayes

La formule de Bayes (de Thomas Bayes, qui l’a trouvée) se base sur la notion de probabilité conditionnelle, c’est à dire, la probabilité qu’un évènement se produise sachant qu’un autre s’est produit. Nous allons nous intéresser à un cas particulier de cette formule, vous pouvez vous intéresser aux détails sur l’article Théorème de Bayes de Wikipedia. Par ailleurs, je me suis inspiré de l’article Bayesian spam filtering sur de wikipedia également.

Considérons l’ensemble des messages que l’on peut les répartir en deux catégories : les spams et les hams (non-spams). L’un est le complément de l’autre, c’est à dire que tout message est dans l’une et une seule des deux catégories.

Considérons ensuite l’évènement “le message contient le mot foo”.

Nous cherchons à déterminer la probabilité que le message soit un spam, sachant qu’il contient le mot foo (on notera cette probabilité Ps). Pour pouvoir écrire la formule facilement on notera ainsi :

  • p(foo/spam), la probabilité que dans un message on trouve le mot “foo” sachant que c’est un spam,
  • p(spam), la probabilité qu’un message soit un spam,
  • p(foo/ham), la probabilité que l’on trouve le mot “foo” dans un ham,
  • p(ham), la probabilité qu’un message ne soit pas un spam.

On a alors :

Nous obtenons donc une sorte de “valeur potentielle d’un mot comme spam”, mais notre filtre ne peut pas se baser sur l’analyse d’un seul mot. Il faut donc effectuer ce calcul sur chaque mot d’un message et évaluer le “potentiel de spam” de ce message.

En réalité, on va exclure les mots “neutres” dont la probabilité calculée avoisine les 0.5, c’est à dire qu’il y a presque autant de chance que ce mot soit contenu dans un spam que dans un ham. On s’intéressera en fait à une liste restreinte de mots, ceux dont la probabilité est proche de 0 (n’est presque jamais dans un spam) ou de 1(presque toujours dans un spam).

Pour calculer le potentiel de spam, nous allons considérer (naïvement) que les mots sont indépendants dans un message, ce qui est naturellement faux, puisque les mots constituent des phrases et sont liés les uns aux autres. On utilisera la formule suivante

On a au numérateur le produit des probabilités qu’un mot du message soit dans un spam (d’après les calculs précédents).

Au dénominateur on a ce même produit additionné au produit des probabilités contraires (la probabilité que le mot ne soit pas dans un spam).

Si un mot est présent plusieurs fois dans le message analysé, on peut inclure sa valeur plusieurs fois dans la formule, pour la rendre plus juste.

Cette méthode est naïve !

Cette méthode est assez naïve puisqu’elle se base sur un certain nombre de suggestions fausses. Il est alors possible de tromper le filtre en insérant de nombreux mots dont la valeur de spam est très faible afin de fausser le calcul. Afin d’améliorer encore un peu plus notre algorithme, nous pourrions considérer des chaînes de mots plutôt que des mots, permettant de mieux considérer le contexte.

Par exemple, si le mot “viagra” est très souvent contenu dans un spam, le mot “amour” sera (idéalement !) dans un ham. Pourtant “amour avec viagra” ne fait pas de doute sur sa qualité de “mot à spam”.

Feed the filter

Il est impossible de connaître par avance les valeurs potentielles de spam de tous les mots que l’on trouvera dans une boîte mail, il va donc falloir éduquer le filtre.

Le principe est donc de constituer une base de données contenant les mots considérés et leur fréquence dans des messages que l’utilisateur aura enregistré comme spams et non spams.

On doit donc enregistrer :

  • le mot,
  • le nombre de fois ou le mot a été trouvé dans un spam,
  • le nombre de fois ou le mot a été trouvé dans un ham,
  • le nombre total de spams analysés,
  • le nombre total de hams analysés.

On obtient p(foo/spam) (la probabilité que le mot foo soit dans un spam) en divisant le nombre de fois où le mot a été trouvé dans un spam par le nombre de spams analysés. p(foo/ham) s’obtient de la même manière.

Le problème des mots inconnus

Bien souvent, un e-mail contiendra un mot inconnu : soit parce que la base de données n’est pas encore suffisamment complète, soit parce que le mot est mal orthographié. Nous ne connaissons alors pas la probabilité qu’un tel mot soit contenu dans un spam, et pire, notre potentiel de spam Ps devient incalculable et n’a pas de sens (la probabilité que le mot soit dans un spam est nulle… tout comme la probabilité qu’il soit dans un ham !).

La seule solution qui s’offre à nous et d’exclure ce mot de nos calculs et de le compter une fois que le statut du message qui le contient est connu.

Passer à l’implémentation

Nous avons maintenant une bonne base théorique, et c’est suffisant pour proposer un filtre naïf capable de nous donner des valeurs qualifiant le potentiel de spam d’un message. Il nous reste maintenant à choisir des valeurs initiales, et à regarder les limites de ce filtre.

Nous devons réfléchir aux valeurs p(spam) et p(ham), respectivement probabilités qu’un message soit un spam ou non. On peut utiliser les valeurs enregistrées dans notre base : p(spam) correspond aux nombre de messages collectés comme spam sur le nombre total de messages analysés. Cependant, ces valeurs seront très certainement incohérentes dans un premier temps (le filtre n’a pas suffisamment appris). Je suggère de considérer qu’en dessous d’un certain nombre de messages analysés, le filtre sera neutre et considérera que “globalement”, la proportions de spams et de ham est identique : p(spam)=p(ham)=0,5.

Nous devrons également choisir la valeur P (entre 0 et 1) à partir de laquelle on considérera que le message analysé est un spam. Plus la valeur sera proche de 0, plus le filtre sera sévère. Un environnement peu spammé peut se contenter d’un seuil à 0,5, sur un formulaire en ligne ou une adresse e-mail de contact, prendre un seuil plus bas (0,3 ou 0,4) sera plus efficace.

Il faut bien comprendre que notre filtre sera parfaitement inutile sans une phase d’apprentissage consistante : nous devons déterminer une base conséquente de mots dont la probabilité de présence dans un spam sera vraiment élevée. Il est toujours possible de commencer avec une liste noire de mots dont la probabilité p(mot/spam) sera fixée à une valeur élevée (0,8-0,9).

Conclusion

De nombreux systèmes anti-spam reposent sur cette technique, même si les formules sont souvent adaptées et pondérées pour être ajustés à la réalité. On pourra, je pense, utiliser la version présentée dans cette article dans un environnement moyennement spammé comme un blog.

Soyons tout de même attentif, lors de l’implémentation, aux performances : notre base de données risque de gonfler très rapidement !