Wir wollen einen Spam Filter bauen.

Als Feature nehmen wir, welche Worte in der Email vorkommen (eingeschränkt auf die 10000 häufigsten Worte)

Beispiel: Wenn "Jahr" das 82. häufigste Wort ist, dann ist $x^{(82)} = 1$, wenn das Wort Jahr in der Email vorkommt.

Können wir GDA nutzen?

• Die $x$ sind binär und nicht normalverteilt
• $\Sigma \in \mathbb{R}^{n \times n}$ wird sehr groß

Nächstes generatives Modell: Naive Bayes

Naive Bayes war eines der ersten Modelle für erfolgreiche Spam Filter (1996).

Wir können nicht alle $p(x | y)$ auswendig lernen
($2^{10000}$ mögliche $x$).

Annahme: Alle $x^{(i)}$ sind unabhängig.

Unabhängigkeit ist eine starke Annahme (und trifft hier sicher nicht zu):

Wenn in einer Spam Email die Worte "Gratulation", "Sie" und "haben" vorkommen, ist das Auftreten von "gewonnen" deutlich wahrscheinlicher.

Funktioniert am Ende trotzdem ganz gut.

Unabhängigkeit der einzelnen Feature bedeutet: \[ P(x^{(1)}, x^{(2)}, \ldots, x^{(n)} | y)\\[3mm] = P(x^{(1)} | y) \cdot P(x^{(2)} | y) \cdot \ldots \cdot P(x^{(n)} | y)\\[3mm] = \prod_{i = 1}^n P(x^{(i)} | y) \]

Da $x$ binär ist, ist $P(x^{(1)} | y)$ Bernoulli verteilt.

Pro Klasse $y$ brauchen wir einen Parameter je Feature: \[ w_{i|y=0} = P(x^{(i)} = 1 | y = 0) \\ w_{i|y=1} = P(x^{(i)} = 1 | y = 1) \] (Wahrscheinlichkeit, dass das Wort vorkommt falls die Email kein Spam oder Spam ist)

Dann brauchen wir noch einen Parameter für die Wahrscheinlichkeit, dass eine beliebige Email Spam ist: \[ w_y = P(y = 1) \]

Damit hätten wir 20001 Parameter, die wir bestimmen müssen.

Maximum Likelihood Estimator:

\[ w_y = \frac{\sum_{(x,y) \in \mathcal{D}_\text{train}} 1[y = 1]}{m} \]

\[ w_{i, y=0} = \frac{\sum_{(x,y) \in \mathcal{D}_\text{train}} 1[x^{(i)} =1, y=0]}{\sum_{(x,y) \in \mathcal{D}_\text{train}} 1[y=0]} \]

\[ w_{i, y=1} = \frac{\sum_{(x,y) \in \mathcal{D}_\text{train}} 1[x^{(i)} =1, y=1]}{\sum_{(x,y) \in \mathcal{D}_\text{train}} 1[y=1]} \]

Wir merken uns also

• für jedes Feature, wie oft es in normalen und wie oft es in Spam Emails vorkommt
• wie viele Spam und nicht Spam Emails wir bekommen haben

Vorteile:

• Sehr effizient zu berechnen
• Einfach mit neuen Daten zu updaten
• Hohe Interpretierbarkeit der Ergebnisse

Nachteil:
Oft schlechter als zum Beispiel Logistische Regression

Vorhersagen funktionieren analog zu GDA: \[ \operatornamewithlimits{arg\,max}_y P(y | x) = \operatornamewithlimits{arg\,max}_y P(y) \cdot \prod_{i = 1}^n P(x^{(i)} | y) \]

Problem: Angenommen ich hatte noch keine Spam Email mit dem Wort "Bingen"

\[ P(x^{(\text{"Bingen"})} | y = 1) = \frac{0}{\text{Anzahl Spam Emails}} = 0 \]

Folge: Das Produkt $\prod_{i = 1}^n P(x^{(i)} | y)$ wird auch $0$.

Es ist immer eine schlechte Idee eine Wahrscheinlichkeit von 0 anzunehmen.

(nur weil man das Ereignis noch nicht gesehen hat)

Beispiel: 1. FSV Mainz 05

Mit Maximum Likelihood bekommen wir

\[ p(\text{Sieg}) = \frac{\text{Anzahl Siege}}{\text{Anzahl Siege} + \text{Anzahl Niederlagen}} \\[3mm] = \frac{0}{0 + 5} = 0 \]

Eine Wahrscheinlich von $0$ wäre doch etwas radikal.

Laplace Smoothing

Idee: Starte beim Zählen mit einer Anzahl 1 für alle Ereignisse

\[ p(\text{Sieg}) = \frac{1}{1 + 6} = 14.29\% \]

Durch Laplace Smoothing verhindern wir Wahrscheinlichkeiten von 0.

Wenn wir viele Beobachtungen haben, machen die fiktiven ersten Beobachtungen keinen Unterschied.

Naive Bayes mit Laplace Smoothing liefert bereits einen "brauchbaren" Spam Filter.

Naive Bayes ist einer der einfachsten Classifier überhaupt.
Guter Startpunkt für neue ML Projekte

Einfacher Classifier hilfreich beim Debuggen:
Beispiel: Email enthält das Wort "Grаtulation" statt "Gratulation"

Dieses Feature Problem hätte auch ein schlauerer Classifier gehabt.

Wenn unsere Feature $x$ nicht binär sind funktioniert das Konzept auch.

Je nach Daten nehmen wir eine andere Verteilung an:

In sklearn: Naive Bayes