Vwi.tu-dresden.de

Hier zeige ich eine der wichtigsten aktuellen Anwendungen des Satzes von Bayes: denBayes-Filter zur Selektion von Spam aus der Email-Box. Im Gegensatz zu klassischen,auf ”Schwarze” und ”Weiße Listen” beruhenden Spamfiltern geht der Bayes Filter alleinvon der statistischen Wahrscheinlichkeit aus, mit der die in einer Email vorkommendenWorte bisher in Spam-Mails bzw. in erw¨unschten Mails (”Ham”) vorkamen. Die einkom-mende Email wird also in Worte zerlegt und diese Wort f¨ur Wort analysiert. Ein ”Wort”wird dabei sehr weit ausgelegt. Neben Worten im Text, dem Absender, Betreffzeilen etcwerden auch Bildverweise, Links sowie Teile des ¨ analysiert.
Wer dazu n¨aheres wissen will, dem sein auf den sehr guten Artikel in der c’t 2003, Heft17, S. 150 verwiesen.
Unser ”Zufallsexperiment” ist das Eintreffen einer neuen Email mit den beiden m¨oglichenEreignissen S : ”Email ist Ham”, d.h. die E-Mail ist erw¨unscht.
Im Prinzip zerlegt der Bayes-Filter die Email in einzelne Worte W1 . . . Wn, z.B.
W1 = ”Viagra”,W2 = ”Statistik”,W3 = ”Republic”, und bestimmt die Spamwahrscheinlichkeit als bedingte Wahrscheinlichkeit Falls diese oberhalb eine Grenzwertes von z.B. 0.9 liegt, wird die Email als Spam klassi-fiziert, ansonsten nicht.
Frage: Warum wird die Grenz-Wahrscheinlichkeit so hoch gew¨ahlt? In einer neu eintreffenden Email kommt das Wort W1 =”Viagra” vor. Zur Bestimmungder statistischen Wahrscheinlichkeiten liegen unserem Spamfilter 300 Emails, darunter 200Spams zur Analyse vor. In 25% aller Spams kam bisher ”Viagra” vor, aber auch in einerHam-Mail von einem Freund (”Du, bekommst Du in letzter Zeit auch so viele Viagra-Angebote ¨ubers Netz?”). Wie groß ist die Spam-Wahrscheinlichkeit der neuen Email, wennnur dieses eine Wort analysiert wird? Die ”a-Priori” Wahrscheinlichkeiten P (S) und P (W1) sowie die bedingte Wahrscheinlich-keit P (W1|S) bestimmen wir mit der statistischen Definition der Wahrscheinlichkeit ausden relativen H¨aufigkeiten der dem Filter zug¨anglichen E-Mails der Vergangenheit: Obwohl ”Viagra” nur in einem Viertel aller Spams vorkommt, betr¨agt dennoch im vor-liegender Mailbox die Bayes-Spamwahrscheinlichkeit einer konkreten Email, die diesesWort enth¨alt, 98%! Entscheidend ist hier, dass in Ham-Mails dieses Wort eben nur sehrselten vorkommt! Im Gegensatz zu den klassischen Filtern ”lernt” der Bayes-Filter seineWahrscheinlichkeiten aus den vergangenen Emails. Jeder Spamfilter ist damit individuellauf seinen ”Meister” dressiert! Bei einem Urologen w¨urde z.B. die obige Email sicher als”Ham” durchgehen.
Was ist aber nun mit erw¨unschten Emails, die ”Viagra” o. ¨ irrt¨umlicherweise unter ”Spam” abgelegt? Irrt¨umlich als ”schlecht” klassifizierte ”gute”Mails, sog. ” false positives”, stellen immerhin den schlimmsten Fehler dar, den Filterbegehen k¨onnen! Schauen wir uns folgende Email n¨aher an: From: Arne Kesting <[email protected]>To: treiber <[email protected]>Subject: UebungsaufgabenHi Martin, das neue Statistik-¨ so mit Spams bombardiert, die z.B. Viagra oder ein einschl¨ anbieten oder - typischerweise von Nigeria aus - eine Million Dollar Gewinnversprechen? Gr¨une Worte sind starke Indizien f¨ur Ham, rote f¨ur Spam. Wie im echten Leben gibt esalso ”mehrere Meinungen”. Wie bestimmt man nun die Gesamt-Spamwahrscheinlichkeit?Zun¨achst mal enth¨alt diese Email einige ”100%ter”: Noch nie kamen in einer Spam sospezifische Worte wie ” [email protected]”, ”Kesting” oder auch” ¨ Ubungsblatt” vor. Damit ist diese Mail nach Bayes zu 100% ”Ham” (warum?) Ahnlichkeiten mit tats¨achlichen Begebenheiten, aktuellen oder vergangenen Emails sowie mit lebenden oder toten Personen sind rein zuf¨allig;-) Lassen wir nun aus ”Sportlichkeit” diese Worte weg und untersuchen nur folgende Wortemit den jeweiligen relativen H¨aufigkeiten in den bisherigen Spam- und Ham-Mails: Hier ist P (W1 ∩ W2|S) die bedingte Wahrscheinlichkeit daf¨ur, dass in einer Spam-Mail dieWorte ”Viagra” und ”Statistik” vokommen. Macht man die ”naive” Annahme, dass dieAntreffwahrscheinlichkeit P (Wi) f¨ur ein Wort Wi nicht von anderen W¨ortern Wj abh¨angt,gilt f¨ur bedingte Wahrscheinlichkeiten dasselbe Kriterium f¨ur Unabh¨angigkeit wie bei”einfachen” Wahrscheinlichkeiten: Analog gilt f¨ur die ”Ham”-Wahrscheinlichkeiten Bildet man den Quotienten, k¨urzt sich jeweils der Nenner weg und man erh¨alt N¯s = 100 die Zahl der ”guten” E-Mails,Ns = 200 die Zahl der Spams,Ns,1 = 50 die Zahl der Spams, die ”Viagra” enthalten,N¯s,1 = 1 die Zahl der Nicht-Spams, die ”Viagra” enthalten,usw.
Damit ist Pspam/Pham = 1 und wegen Pspam + Pham = 1 die Spamwahrscheinlichkeit=50%,also kleiner als die Grenz-Wahrscheinlichkeit, so dass die Email als ”Ham” angenommenwird.
Mit n W¨ortern ist die Verallgemeinerung offensichtlich: • Wegen der zus¨atzlichen ”naiven” Annahme der Wort-Unabh¨angigkeit heißen die ublichen Bayes-Spamfilter auch ”naive Bayes-Filter”.
• Hauptvorteil gegen¨uber den klassischen Filtern ist die individuell erlernte ”White- list”, auf die ein Spammer, im Gegensatz zu ”Schwarzen Listen”, i.A. keine Reakti-onsm¨oglichkeiten z.B. durch Wortverst¨ummelungen (”Vi@gra!”) hat.

Source: http://www.vwi.tu-dresden.de/~treiber/statistik2/statistik_download/folien13_spamfilter.pdf