Bayesscher Spamfilter

Der Bayes-Spamfilter ist ein statistischer Filter zur Klassifizierung unerwünschter E-Mail-Nachrichten (Spam) mithilfe des naiven Bayes-Klassifikators. Bei dieser Methode werden dem Filter vom Benutzer Beispiel-E-Mails für Spam vorgelegt. Anschließend versucht der Filter, aus diesen E-Mails Wörter zu extrahieren, die charakteristisch für Spam sind. Nach der Trainingsphase soll der Filter in der Lage sein, eingehende E-Mails anhand des Vorkommens dieser Wörter als Spam zu klassifizieren.

Funktionsweise

E-Mails werden mithilfe des bayesschen Filters folgendermaßen untersucht: Von charakteristischen Wörtern in einer E-Mail (Ereignis) wird auf die Eigenschaft geschlossen, gänzlich unerwünscht zu sein (Spam). Dieses statistische Filtern, zuerst 1998 von Sahami et al. vorgeschlagen und ab 2002 durch einen einflussreichen Artikel von Paul Graham popularisiert, soll vorhersagen, ob es sich bei einer Nachricht um Spam handelt.

Das System wird von vielen Programmen zur Spamerkennung genutzt und ist beispielsweise in den E-Mail-Programmen Pegasus Mail, Opera Mail und Mozilla Thunderbird implementiert.

Statistische Gegenmaßnahmen basieren auf Wahrscheinlichkeitsmethoden, die aus dem Satz von Bayes abgeleitet sind. Bayessche Filter sind oft „lernend“ (auch „selbstlernend“) organisiert und setzen auf Worthäufigkeiten in bereits vom Benutzer erhaltenen und klassifizierten E-Mails.

Ein bayesscher Filter wird durch seinen Benutzer trainiert, indem dieser seine E-Mails in erwünschte und unerwünschte Nachrichten einteilt. Der bayessche Filter erstellt daraufhin eine Liste mit Wörtern, die in unerwünschten E-Mails vorkommen. Hat der Benutzer beispielsweise E-Mails mit den Begriffen „Sex“ und „Viagra“ als Spam gekennzeichnet, haben alle E-Mails mit diesen Begriffen eine hohe Spamwahrscheinlichkeit. Begriffe aus erwünschten E-Mails wie „Verabredung“ oder „Bericht“ führen dann im Gegenzug zu einer Herabstufung der negativen Bewertung. Allerdings reichen einzelne Schlüsselwörter nicht aus; relevant ist die Summe der Bewertungen der einzelnen Wörter.

Der Filter erreicht bereits nach kurzem Training mit wenigen E-Mails hohe Trefferquoten – auch wenn für den produktiven Einsatz ein Training mit mehreren hundert E-Mails beider Kategorien empfohlen wird. Ein Risiko für den Benutzer sind falsch-positive Treffer – also E-Mails, die fälschlicherweise als Spam erkannt werden. Dieses Risiko lässt sich durch das Markieren von erwünschten E-Mails verringern, ist aber insbesondere für Unternehmen problematisch.

Die Versender von Spam ergreifen Gegenmaßnahmen gegen Bayes-Filter. Werbebotschaften werden in Bildern gezeigt, die der Filter nicht untersuchen kann. Auch werden verdächtige Begriffe bewusst falsch geschrieben (beispielsweise „V|agra“ oder „Va1ium“) oder mit eingestreuten Leerzeichen versehen. Allerdings bewertet der Filter auch HTML-Tags wie „img“ und „src“ negativ, sodass Bilder in E-Mails ebenfalls mit einer höheren Spamwahrscheinlichkeit bewertet werden. Auch werden vermehrt zufällige Zitate aus der Weltliteratur (auch in weißer Schrift oder als Meta-Tag unlesbar) eingefügt, um die statistischen Maßnahmen in die Irre zu führen. Dies ist aber keine erfolgreiche Strategie, weil zufällig ausgewählte „harmlose“ Begriffe oder Sätze weder eine besonders hohe noch eine besonders niedrige Spamwahrscheinlichkeit erzielen, so dass sie letztendlich keine Rolle spielen.

Eine Besonderheit in nicht englischsprachigen Ländern ergibt sich durch den Umstand, dass Spam überwiegend in englischer Sprache verfasst wird. Die Trefferwahrscheinlichkeit eines bayesschen Filters dürfte daher in diesen Ländern höher sein, aber auch die Gefahr, dass eine erwünschte englischsprachige Mail fälschlicherweise als Spam markiert wird, steigt.

Das Filtern auf statistischen Grundlagen ist eine Form der Textklassifikation. Eine Anzahl von Forschern der angewandten Linguistik, die sich mit maschinellem Lernen befassen, haben sich bereits diesem Problem gewidmet. Eine Weiterentwicklung im Bereich der E-Mail-Verarbeitung ist der Markow-Spamfilter, bei der nicht nur einzelne Wörter, sondern ganze Wortketten und Kombinationsmöglichkeiten bewertet werden.

Mathematische Grundlage

Der Satz von Bayes lautet:

$P(A|B)\;=\;{\frac {P(B|A)\cdot P(A)}{P(B)}}$

wobei $P(A|B)$ die bedingte Wahrscheinlichkeit des Ereignisses A unter der Voraussetzung ist, dass (vorher) Ereignis B eingetreten ist.

$P({\text{Suchwort kommt vor}}|{\text{Spam}})\,$

wäre demnach die Wahrscheinlichkeit dafür, dass das betreffende Suchwort in einer E-Mail vorkommt, wenn es sich bei ihr um eine Spam-Mail handelt. Umgekehrt ist

$P({\text{Spam}}|{\text{Suchwort kommt vor}})\,$

die in diesem Zusammenhang interessierende Wahrscheinlichkeit, dass eine E-Mail Spam ist, wenn sie das betreffende Suchwort enthält. Gemäß der obigen Bayes-Formel lässt sich diese Wahrscheinlichkeit nun wie folgt berechnen:

$P({\text{Spam}}|{\text{Suchwort kommt vor}})\;=\;{\frac {P({\text{Suchwort kommt vor}}|{\text{Spam}})\cdot P({\text{Spam}})}{P({\text{Suchwort kommt vor}})}}$.

Beispiel Naive-Bayes-Klassifikator

In E-Mail-Programmen mit (lernenden) Naive-Bayes-Klassifikatoren werden Spam-Mails sehr effizient ausgefiltert. Dabei gibt es zwei Klassen von E-Mails: Spam- und Nicht-Spam-E-Mails ($C=\{Spam,{\overline {Spam}}\}$). Eine E-Mail besteht aus einzelnen Wörtern $W_{i}$. Aus alten, bereits klassifizierten E-Mails kann man für jedes Wort $W_{i}$ die Wahrscheinlichkeit schätzen, dass es in einer Spam- oder Nicht-Spam-E-Mail vorkommt, also:

$P(W_{i}|Spam)={\frac {{\text{Anzahl der Spam-E-Mails mit dem Wort }}W_{i}}{\text{Anzahl der Spam-E-Mails}}}$

$P(W_{i}|{\overline {Spam}})={\frac {{\text{Anzahl der Nicht-Spam-E-Mails mit dem Wort }}W_{i}}{\text{Anzahl der Nicht-Spam-E-Mails}}}$

Für eine neue E-Mail $W$ stellt sich die Frage: Ist die Wahrscheinlichkeit $P(Spam|W)$ größer oder kleiner als die Wahrscheinlichkeit $P({\overline {Spam}}|W)$? Wenn $P(Spam|W)<P({\overline {Spam}}|W)$, wird die neue E-Mail als Nicht-Spam klassifiziert, anderenfalls als Spam.

Für die Wahrscheinlichkeit $P(Spam|W)$ gilt nach dem Satz von Bayes:

$P(Spam|W)={\frac {P(Spam\cap W)}{P(W)}}={\frac {P(W|Spam)\cdot P(Spam)}{P(W)}}$.

$P(W)$ ist die Wahrscheinlichkeit, dass die E-Mail $W$ auftritt. Da diese unabhängig von $P({\overline {Spam}}|W)$ und $P(Spam|W)$ ist, nimmt sie immer denselben Wert an und kann vernachlässigt werden. Daher betrachten die E-Mail-Programme den Ausdruck

$Q={\frac {P(Spam|W)}{P({\overline {Spam}}|W)}}={\frac {P(W|Spam)\cdot P(Spam)}{P(W)}}{\frac {P(W)}{P(W|{\overline {Spam}})P({\overline {Spam}})}}={\frac {P(W|Spam)\cdot P(Spam)}{P(W|{\overline {Spam}})\cdot P({\overline {Spam}})}}$.

Ist $Q>1$, wird die E-Mail als Spam klassifiziert, andernfalls als Nicht-Spam. Die Wahrscheinlichkeit, dass überhaupt eine E-Mail Spam bzw. Nicht-Spam ist, kann wieder aus den alten E-Mails geschätzt werden:

$P(Spam)={\frac {\text{Anzahl der Spam-E-Mails}}{\text{Anzahl aller E-Mails}}}$, $P({\overline {Spam}})={\frac {\text{Anzahl der Nicht-Spam-E-Mails}}{\text{Anzahl aller E-Mails}}}$.

Besteht die E-Mail $W$ aus den Wörtern $W_{1},\dotsc ,W_{n}$ und treten diese Wörter unabhängig voneinander auf, so gilt

$P(W|Spam)=P(W_{1}\cap \dotsb \cap W_{n}|Spam)=P(W_{1}|Spam)\dotsm P(W_{n}|Spam)$.

Die Wahrscheinlichkeit $P(W_{i}|Spam)$ ist oben bereits angegeben und damit kann der Gesamtquotient berechnet werden:

$Q={\frac {P(Spam|W)}{P({\overline {Spam}}|W)}}={\frac {P(W_{1}|Spam)\dotsm P(W_{n}|Spam)\cdot P(Spam)}{P(W_{1}|{\overline {Spam}})\dotsm P(W_{n}|{\overline {Spam}})\cdot P({\overline {Spam}})}}$.

Am Schluss noch drei Bemerkungen:

1. In der Praxis wird eine E-Mail als Spam klassifiziert, wenn beispielsweise $Q>10$ gilt, also wenn die Wahrscheinlichkeit, eine Spam-E-Mail zu sein, wesentlich größer ist als die Wahrscheinlichkeit, eine Nicht-Spam-E-Mail zu sein. Der Grund liegt darin, dass eine als Spam klassifizierte E-Mail meist automatisch in einen Junk-Ordner verschoben wird, ohne dass der Empfänger sie nochmals zu Gesicht bekommt. Dies kann problematisch sein, wenn die E-Mail fälschlicherweise als Spam klassifiziert wird. In diesem Fall ist es oft wünschenswerter, gelegentlich eine Spam-Mail im Posteingang zu finden, als wichtige E-Mails zu verlieren.
2. Der Filter wird als lernender Filter bezeichnet, da sich mit der Kennzeichnung neuer E-Mails als Junk in der Inbox die Wahrscheinlichkeiten $P(W_{i}|Spam)$, $P(Spam)$ usw. dynamisch anpassen.
3. Obwohl die mathematisch-statistische Theorie die Unabhängigkeit der Wörter $W_{i}$ fordert, ist dies in der Praxis nicht erfüllt. Beispielsweise treten die Wörter Viagra und Sex häufig im gleichen Zusammenhang auf. Trotz dieser Verletzung der Unabhängigkeitsannahme funktionieren die Naive-Bayes-Filter in der Praxis sehr gut. Der Grund liegt darin, dass die exakten Wahrscheinlichkeiten $P(Spam|W)$ und $P({\overline {Spam}}|W)$ gar nicht benötigt werden. Es genügt, korrekt zu bestimmen, welche der beiden Wahrscheinlichkeiten größer ist. Daher werden zur Klassifizierung meist nur etwa zehn Wörter aus der E-Mail herangezogen: jeweils die fünf mit der höchsten Wahrscheinlichkeit, in einer Spam- bzw. Nicht-Spam-E-Mail vorzukommen.

Weblinks

• Die Mathematik im Bayes Spamfilter, die benötigten Hilfsmittel und ein Rechenbeispiel (Memento vom 31. Januar 2020 im Internet Archive)