Spam-Erkennung galt lange Zeit (bis in die frühen 2000er) als eine große Herausforderung in der Künstlichen Intelligenz (KI), da man vermutete, ein Spam-Filter müsse Texte sinnvoll "interpretieren", um Spam effektiv erkennen zu können. Glücklicherweise stellte sich heraus, dass es auch einfacher funktioniert, nämlich durch den Einsatz von ein klein wenig Statistik auf Basis des Bayes-Theorems [1].
Bevor Sie, geneigter Leser, nun ob der Androhung von Mathematik bzw. Statistik gleich wieder von dannen ziehen, seien Sie versichert, dass das Bayes-Theorem nicht so kompliziert ist, wie es auf den ersten Blick vielleicht erscheinen mag. Um Sie davon zu überzeugen, werde ich diesen Blog-Eintrag zunächst ausführlich mit Beispielen unterfüttern, bevor ich abschließend auf die mathematischen Hintergründe eingehe.
Zu Beginn noch ein klein wenig Hintergrundwissen, wie die Anwendung des Bayes-Theorems zur Spam-Filterung bzw. zur Text-Klassifizierung allgemein eingeordnet werden kann. Es fällt, wie bereits angedeutet, in den Bereich der Künstlichen Intelligenz, wo man von einem sogenannten überwachten Lernverfahren (engl.: supervised machine learning) aus dem Bereich des Maschinellen Lernens (engl.: machine learning) spricht. Wie so oft in der KI geht es auch hierbei um die Auswertung statistischer Werte zur Ermittlung einer Wahrscheinlichkeit. Nämlich der, ob eine unbekannte Nachricht Spam enthält, oder eben nicht.
Ein Bayes-Classifier muss daher zunächst mit einer Menge von Nachrichten trainiert werden (dem sog. Training-Set), zu denen bekannt ist, ob sie als Spam klassifiziert worden sind oder nicht. Wie das funktioniert, beschreibe ich im nächsten Abschnitt.
Trainingsphase
Der Einstieg in die Trainingsphase des Bayes-Classifier ist sehr einfach: Wir müssen nichts weiter tun, als auf unserem Training-Set die Anzahl der enthaltenen Spam-Mails sowie die Anzahl der Mails, die keinen Spam enthalten, zu zählen und beide jeweils durch die Gesamtanzahl an vorliegenden Nachrichten zu teilen:
pspam = Anzahl der Spam-Mails / Anzahl aller Mails
pno-spam = Anzahl der Nicht-Spam-Mails / Anzahl aller Mails
Angenommen,
unser Training-Set besteht aus den folgenden
einfachen E-Mails (bzw. auf Grund der Kürze besser E-Mail-Betreffs), von
denen die letzten beiden als Spam annotiert sind, ...
M1: Hallo Welt!
M2: Hallo Java!
M3: Dringende Nachricht!
M4: Günstige Viagra kaufen!
M5: Hallo Nachricht: wolle Viagra kaufen?
... so ergeben sich folgende Werte:
pspam = 2/5
pno-spam = 3/5
In der Praxis empfiehlt es sich übrigens, das Verhältnis von Spam zu Nicht-Spam in den Trainingsdaten ungefähr dem Gesamtaufkommen an Spam-Mails anzupassen, das weltweit geschätzt bei etwa 80% liegt.
Als nächstes berechnen wir schlicht, wie hoch der Anteil jedes gefundenen Worts am Anteil aller Worte in der jeweiligen Klasse (also Spam bzw. Nicht-Spam) ist:
pspam-wort-x = Anz. d. Vorkommen in Spam-Mails / Anz. d. Vorkommen aller Wörter in allen Spam-Mails
pno-spam-wort-x = Anz. d. Vorkommen in Nicht-Spam-Mails / Anz. d. Vorkommen aller Wörter in allen Nicht-Spam-Mails
Das Ergebnis dieser einfachen Rechenübung ist die Spam- bzw. Nicht-Spam-Wahrscheinlichkeit (im Englischen auch "spamliness" genannt) jedes Worts, die sich recht übersichtlich in einer Tabelle darstellen lässt:
| Wort | pspam | pno-spam |
| Hallo | 1/8 | 2/6 |
| Welt | 0/8 | 1/6 |
| Java | 0/8 | 1/6 |
| Dringende | 0/8 | 1/6 |
| Nachricht | 1/8 | 1/6 |
| Günstige | 1/8 | 0/6 |
| Viagra | 2/8 | 0/6 |
| wolle | 1/8 | 0/6 |
| kaufen | 2/8 | 0/6 |
Am Beispiel "Hallo" sei die Berechnung nochmals verdeutlicht: unsere als Spam markierten Betreffs enthalten insgesamt 8 Worte unter denen "Hallo" einmal vorkommt (-> 1/8). Bei den nicht als Spam klassifizierten Betreffs (im Englischen manchmal auch als "ham" bezeichnet) sind insgesamt 6 Worte enthalten, "Hallo" taucht dort zweimal auf (-> 2/6). Damit ist die Lernphase auch bereits abgeschlossen.
Im KI-Kontext werden die einzelnen Worte übrigens oft als Features bezeichnet, womit angedeutet ist, dass dieser Algorithmus auch mit anderen Features, die nicht unbedingt Worte sein müssen, funktionieren wird, vgl. z.B. [3].
Klassifizierung
Auch die nun folgende sogenannte Klassifizierung eines unbekannten Textes in Spam oder Ham ist alles andere als kompliziert: prinzipiell müssen wir nur auf Basis der eben gelernten Daten abschätzen, wie hoch die Spam-Wahrscheinlichkeit der in einer neuen Nachricht enthaltenen Worte ist.
Wir benötigen also zunächst einen oder mehrere neue Mail-Betreffs, die z.B. wie folgt schnell ausgedacht sind:
M6: Hallo! Wichtige Nachricht!
M7: Billige Viagra kaufen!
Nun schauen wir die Spam-Wahrscheinlichkeiten aller enthaltenen Worte in obiger Tabelle nach, wobei wir bis dato unbekannte Worte der Einfachheit halber schlicht ignorieren:
Hallo: p
spam-hallo = 1/8
Nachricht: p
spam-Nachricht = 1/8
Viagra: p
spam-Viagra = 2/8
kaufen: p
spam-kaufen = 2/8
Wichtige: unbekannt -> ignorieren
Billige: unbekannt -> ignorieren
Es hat sich in der Praxis gezeigt, dass es völlig ausreichend ist, einen sogenannten naiven Bayes-Classifier zu verwenden, weswegen wir nun die gefundenen Wort-Wahrscheinlichkeiten einfach aufmultiplizieren und abschließend noch mit p
spam (= 2/5) multiplizieren können (Erklärung folgt unten). Also rechnen wir zunächst:
p
spam-M6 = 1/8 * 1/8 * 2/5 =
0,00625
p
spam-M7 = 2/8 * 2/8 * 2/5 =
0,025
Analog dazu können wir im Kein-Spam-Fall vorgehen und danach schlicht vergleichen, welcher der beiden Werte größer ist:
p
no-spam-M6 = 2/6 * 1/6 * p
no-spam =
0,0333...
p
no-spam-M7 = 0/8 * 0/8 * p
no-spam =
0
Offenbar haben wir also eine deutliche Tendenz, dass
M6 kein Spam zu sein scheint, während der Spam-Verdacht für
M7 nicht so einfach von der Hand zu weisen ist.
Normalisierung
Wenn wir möchten, können wir die gerade berechneten Werte noch normalisieren und erhalten nach Bayes für den dazu notwendigen Nenner:
p
spam * p
spam-Wort-1 * ... * p
spam-Wort-n + p
no-spam * p
no-spam-Wort-1 * ... * p
no-spam-Wort-n
Unsere Beispieldaten offenbaren nun leider ein Problem, nämlich sobald in einer Kategorie jeweils ein Wort vorkommt, das in der anderen Kategorie nicht auftaucht, wird der Nenner zu null, womit die Normalisierung nicht funktioniert.
Eine einfache Möglichkeit, dies zu verhindern ist es, pauschal bei der Berechnung der (Kein-)Spam-Wahrscheinlichkeit in jedem Zähler eine eins aufzuaddieren (das sog. Laplace Smoothing). Um dies wieder auszugleichen addieren wir zusätzlich in jedem Nenner die Gesamtanzahl der Worte (also die Größe des Vokabulars), so dass sich folgende Formel ergibt:
Anzahl der Vorkommen in Spam-Mails + 1
p'
spam-wort-x = -----------------------------------------------------------------------------------------------------
Anzahl der Vorkommen aller Wörter in allen Spam-Mails + Anzahl aller Worte
Das funktioniert natürlich für die Kein-Spam-Wahrscheinlichkeit analog, so dass sich obige Tabelle wie folgt neu berechnen lässt:
| Wort | p'spam | p'no-spam |
| Hallo | (1+1)/(8+9) = 2/17 | (2+1)/(6+9) = 3/15 |
| Welt | 0/8 -> 1/17 | 1/6 -> 2/15 |
| Java | 0/8 -> 1/17 | 1/6 -> 2/15 |
| Dringende | 0/8 -> 1/17 | 1/6 -> 2/15 |
| Nachricht | 1/8 -> 2/17 | 1/6 -> 2/15 |
| Günstige | 1/8 -> 2/17 | 0/6 -> 1/15 |
| Viagra | 2/8 -> 3/17 | 0/6 -> 1/15 |
| wolle | 1/8 -> 2/17 | 0/6 -> 1/15 |
| kaufen | 2/8 -> 3/17 | 0/6 -> 1/15 |
Wir berechnen daraufhin die unnormalisierten Spam-Wahrscheinlichkeiten ebenfalls neu ...
p'
spam-M6 = 2/17 * 2/17 * 0,4 =
0,00554
p
'spam-M7 = 3/17 * 3/17 * 0,4 =
0,01246
p'no-spam-M6 = 3/15 * 2/15 * 0,6 = 0,016
p'no-spam-M7 = 1/15 * 1/15 * 0,6 = 0,00267
... und können anschließend auch den Nenner problemlos berechnen; natürlich jeweils nur mit den Worten, die in M6 (Hallo und Nachricht) bzw. M7 (Viagra und kaufen) auch tatsächlich auftauchen:
NennerM6 = 0,4 * (2/17)^2 + 0,6 *(3/15) * (2/15) = 0,02153633217
NennerM7 = 0,4 * (3/17)^2 + 0,6 *(1/15)^2 = 0,01512341407
Somit ergeben sich folgende normalisierte Wahrscheinlichkeiten:
pspam-M6 = 25,7% pno-spam-M6 = 74,3%
pspam-M7 = 82,3% pno-spam-M7 = 17,7%
Diese addieren sich erwartungsgemäß zu 100% auf, so dass es in der Praxis ausreichend wäre, nur eine der beiden Wahrscheinlichkeiten zu berechnen. Da bei einem Spam-Filter eine fälschlicherweise als Spam klassifizierte Nachricht (ein sogenanntes False Positive) deutlich schlimmer ist, als eine Spam-Nachricht, die nicht erkannt wird (False Negative), kann es in der Praxis sinnvoll sein, den Schwellwert für Spam deutlich höher als auf 50%, also z.B. auf 80% zu setzen. Somit lässt sich auf Nummer sicher gehen, dass keine erwünschten Nachrichten aussortiert werden.
Damit haben wir mit etwas Zählen und Bruchrechnung ein maschinelles Lernverfahren angewendet, das vielfach unnötig komplex und mathematisch erklärt wird. Leser, die sich nichtsdestotrotz auch für die mathematischen Hintergründe interessieren, finden diese nun im nächsten Abschnitt.
Mathematische Hintergründe
Wie bereits mehrfach erwähnt, verwendet das vorgestellte Verfahren einen sogenannten Naive Bayes Classifier, der auf dem Bayes'schen Theorem der bedingten Wahrscheinlichkeiten beruht. Das klingt schon wieder unheimlich kompliziert, ein einfaches Beispiel bringt aber hoffentlich etwas Licht ins Dunkel.
Möchten wir die Wahrscheinlichkeit abschätzen, dass M7 Spam enthält, können wir dies auf Basis der "Spamliness" der enthaltenen Worte berechnen, wie wir es oben getan haben. Mit Hilfe von Bayes lässt sich das folgendermaßen ausdrücken:
p
spam * p(Viagra, kaufen | Spam)
p
spam-M6(Spam | Billige, Viagra, kaufen) = ---------------------------------------------------
p(Viagra, kaufen)
In Worten ausgedrückt, schätzen wir auf Basis der Worte (Billige, Viagra, kaufen), die M7 enthält, die Wahrscheinlichkeit ab, dass es sich um eine Spam-Mail handelt. Dazu multiplizieren wir zunächst die Wahrscheinlichkeit unter allen Mails auf eine Spam-Mail zu stoßen mit der Wahrscheinlichkeit, dass die genannten Worte zuvor (also in der Trainingsphase) in einer Spam-Mail aufgetaucht sind (und ignorieren das unbekannte "Billige"). Zum Zwecke der Normalisierung können wir die errechnete Zahl abschließend durch die Wahrscheinlichkeit die jeweiligen Worte in den Mails des Training-Sets gesehen zu haben, dividieren.
Der verwendete Classifier heißt übrigens "Naive Bayes", weil die Annahme getroffen wird, dass die Worte unabhängig voneinander in Texten vorkommen. Das wird zwar in der Praxis nie vollständig eintreffen, da z.B. die Phrase "Sehr geehrte Damen und Herren" sehr häufig in dieser Konstellation vorkommen wird, erlaubt uns aber das einfache Ausmultiplizieren der Wahrscheinlichkeiten. Wir können daher folgendes schreiben:
p(Viagra, kaufen | Spam) = pspam-Viagra * pspam-kaufen
Diese Annahme ist zwar nicht zu einhundert Prozent korrekt, für die Praxis aber vollkommen ausreichend und erleichtert uns die Rechenarbeit erheblich. Nicht nur wie eben gezeigt im Zähler, sondern auch im Nenner, wo wir diese kleine Vereinfachung ebenfalls angewenden können.
Dort müssen wir die Wahrscheinlichkeiten der einzelnen Worte noch für den Spam- und den Kein-Spam-Fall ermitteln und sie entsprechend gewichten, so dass sich p(Viagra, kaufen) zu
pspam * pspam-Viagra * pspam-kaufen + pno-spam * pno-spam-Viagra * ... * pno-spam-kaufen
umschreiben lässt. Damit ergibt sich insgesamt die folgende, bereits oben verwendete Klassifizierungsformel, die sich durch Einsetzen der in der Trainingsphase ermittelten Werte problemlos ausrechnen lässt:
p
spam * p
spam-Viagra * p
spam-kaufen
p
spam-M6 = --------------------------------------------------------------------------------------------------------
pspam * pspam-Viagra * pspam-kaufen + pno-spam * pno-spam-Viagra * ... * pno-spam-kaufen
Bzw. abschließend noch allgemein geschrieben die Formel:
pspam * ∏ pspam-Worte
pspam(Spam | Worte) = ------------------------------------------------------------------------
pspam * ∏ pspam-Worte + pno-spam * ∏ pno-spam-Worte
Da die Klassifizierung in einer einzigen Schleife über alle in einem Dokument enthaltenen Worte implementiert werden kann, ist sie nach der Lernphase effizient auf großen Datenmengen einsetzbar und nötigenfalls sogar parallelisierbar.
Underflows vermeiden
In der Praxis taucht gerade bei größeren Dokumenten leider oft ein weiteres Problem auf. Multiplizieren wir dort die per se bereits kleinen Spam-Wahrscheinlichkeiten von vielen Worten auf, erreichen wir unter Umständen die Grenzen der Fließkomma-Arithmetik. Der kleinste Wert, den z.B. ein Java-Double darstellen kann liegt im Bereich 10-324. Alles was noch kleiner wird, produziert einen sogenannten Underflow.
Eine einfache Lösung wäre, z.B. nur die z.B. 12 Worte mit den höchsten Spam-Wahrscheinlichkeiten zu multiplizieren, um auf der sicheren Seite zu bleiben. Wer es etwas mathematischer und vollständiger mag, könnte aber auch auf die Idee kommen, die Wahrscheinlichkeiten zu logarithmieren (was beim Umgang mit vielen bedingten Wahrscheinlichkeiten ein gängiger Ansatz ist).
Das erfordert für den unnormalisierten Teil der Berechnung nur die Anwendung der bekannten Logarithmen-Gesetze, sprich unser Zähler
pspam * ∏ pspam-Worte wird logarithmiert zu ln(pspam * ∏ pspam-Worte)
und damit ergibt sich:
ln(Zähler) = ln(pspam) + ∑ ln(pspam-Worte)
Über ein e^(ln(pspam) + ∑ ln(pspam-Worte)) lässt sich das Ergebnis ggf. am Ende wieder zurückrechnen, was aber eigentlich überflüssig ist, da uns an dieser Stelle nur interessiert, ob der Wert für Spam größer ist als der für Ham (= Kein-Spam).
Die Anwendung dieses Tricks auf die gesamte (normalisierte) Formel ist durch die Summe im Nenner etwas komplizierter, vgl. [5]. Der erste Schritt dazu ist das Logarithmieren obiger Formel auf beiden Seiten, so dass sich ergibt:
ln(pspam(Spam | Worte)) = ln(Zähler) - ln(Nenner)
Für den Zähler können wir die gerade abgeleitete Formel verwenden, im Nenner müssen wir wie folgt vorgehen:
ln(pspam * ∏ pspam-Worte + pno-spam * ∏ pno-spam-Worte)
= ln( e^ln(pspam * ∏ pspam-Worte) + e^ln(pno-spam * ∏ pno-spam-Worte) )
Das bringt uns zwar zunächst einmal noch nichts, ermöglicht uns aber eine weitere Umformung wie folgt, wobei ai für den natürlichen Logarithmus des jeweiligen Summenelements aus dem Nenner (also z.B. pspam * ∏ pspam-Worte) steht:
ln ∑ e^ai = ln ∑ e^ai e^(m-m) (mit i als Laufvariable für die Summe)
Da (m-m) offensichtlich gleich 0 und e^0 = 1 ist, tut das zunächst einmal nicht weh, erlaubt uns aber an dieser Stelle den entscheidenden Trick:
ln ∑ e^ai e^(m-m) = m + ln ∑ e^(ai-m)
Nun müssen wir nur noch m als das Maximum aller logarithmierten Summenelemente ermitteln und können damit den Underflow im Nenner vermeiden.
Da unser Nenner aus zwei Elementen besteht, ergibt sich abschließend folgende Formel:
ln(Nenner) = m + ln( e^(ln(pspam * ∏ pspam-Worte) - ln(m) + ln(pno-spam * ∏ pno-spam-Worte) - ln(m) ) )
Interessante Links
- Paul Grahams "Plan for Spam": http://www.paulgraham.com/spam.html (engl.)
- Eine Analyse wo Graham vom Bayes'schen Vorgehen abweicht: http://cs.wellesley.edu/~anderson/writing/naive-bayes.pdf (engl.)
- Bayes als Entscheidungshilfe für Golf-Spieler: https://www.youtube.com/watch?v=CPqOCI0ahss (engl.)
- Bayes zum Verbessern der Glücksspielchancen: https://www.youtube.com/watch?v=ugbWqWCcxrg (engl.)
- Vermeidung von Underflows: https://stats.stackexchange.com/questions/105602/example-of-how-the-log-sum-exp-trick-works-in-naive-bayes (engl.)
