3.3 Naiver Bayes-Klassifikator

Die vereinfachende Annahme

Das Problem des Bayes-Klassifikators ist die Schätzung der $d$-dimensionalen Likelihood $p(\mathbf{x}\mid\omega_i)$. Der naive Bayes-Klassifikator (Naive Bayes) macht eine radikale Vereinfachung 📄 06_bayes.pdf, Folie 17:

Die klassenbedingte Wahrscheinlichkeit (Likelihood) faktorisiert für die einzelnen Merkmale $x_j$ im Merkmalsvektor $\mathbf{x}$. Das heißt: Bei gegebener Klasse $\omega_i$ sind die $x_j$ voneinander statistisch unabhängig.

$$p(\mathbf{x}\mid\omega_i) = p(x_1\mid\omega_i)\cdot p(x_2\mid\omega_i)\cdots = \prod_{j=1}^{d} p(x_j\mid\omega_i).$$

Damit wird aus einer $d$-dimensionalen Dichteschätzung eine Sammlung von $d$ eindimensionalen Dichteschätzungen pro Klasse. Die Bayessche Entscheidungsregel wird zu:

Entscheidungsregel Naive Bayes (Folie 17)

Entscheide für $\omega_1$, wenn

$$\prod_j p(x_j\mid\omega_1)\,p(\omega_1) > \prod_j p(x_j\mid\omega_2)\,p(\omega_2),$$

sonst für $\omega_2$. (Bei mehr Klassen: $\arg\max_i \prod_j p(x_j\mid\omega_i)\,p(\omega_i)$.)

Fallstrick: „bedingt unabhängig“ ist nicht „unabhängig“

Naive Bayes nimmt bedingte Unabhängigkeit (conditional independence) an, also Unabhängigkeit innerhalb jeder Klasse. Die Merkmale dürfen über alle Daten hinweg durchaus korreliert sein. Beispiel: Größe und Gewicht von Fischen sind insgesamt korreliert, schon weil Wolfsbarsche größer und schwerer sind als Lachse. Naive Bayes nimmt nur an, dass unter den Lachsen Größe und Gewicht nichts miteinander zu tun haben, was in Wirklichkeit natürlich auch nicht stimmt. Daher „naiv“.

Warum „naiv“, und warum trotzdem? Die Annahme ist fast nie exakt erfüllt. Für die Klassifikation kommt es aber nur darauf an, welche Klasse den größten Wert bekommt, nicht darauf, dass die geschätzten Wahrscheinlichkeiten stimmen. Die Rangfolge bleibt oft richtig, auch wenn die Zahlen verzerrt sind (siehe Eigenschaften).

Rechenbeispiel: diskreter Spamfilter

Ergänzung, nicht auf den Folien: Ein Spamfilter mit zwei binären Merkmalen: $x_1$ = „Mail enthält ‚Gewinn‘“, $x_2$ = „Mail enthält ‚Meeting‘“. Trainingsdaten: 10 Mails, davon 4 Spam ($S$) und 6 Ham ($H$, erwünscht).

	Anzahl	„Gewinn“ kommt vor	„Meeting“ kommt vor
Spam	4	3	1
Ham	6	1	4

Training (relative Häufigkeiten):

• Priors: $p(S)=4/10=0{,}4$, $p(H)=6/10=0{,}6$.
• Likelihoods: $p(x_1{=}1\mid S)=3/4$, $p(x_2{=}1\mid S)=1/4$, $p(x_1{=}1\mid H)=1/6$, $p(x_2{=}1\mid H)=4/6$.

Neue Mail: enthält „Gewinn“, aber nicht „Meeting“, also $\mathbf{x}=(1,0)$. Für $x_2=0$ braucht man die Gegenwahrscheinlichkeit $1-p(x_2{=}1\mid\cdot)$.

$$\begin{aligned} S:&\quad p(S)\,p(x_1{=}1\mid S)\,p(x_2{=}0\mid S) = 0{,}4\cdot\tfrac34\cdot\tfrac34 = 0{,}225\\ H:&\quad p(H)\,p(x_1{=}1\mid H)\,p(x_2{=}0\mid H) = 0{,}6\cdot\tfrac16\cdot\tfrac26 \approx 0{,}0333 \end{aligned}$$

$0{,}225 > 0{,}0333$, also Spam. Wenn man die Posterior-Wahrscheinlichkeit wissen will, normiert man: $p(S\mid\mathbf{x}) = 0{,}225/(0{,}225+0{,}0333)\approx 0{,}87$.

Fallstrick: Nullwahrscheinlichkeiten

Käme in den Ham-Mails „Gewinn“ nie vor, wäre $p(x_1{=}1\mid H)=0$, und das ganze Produkt für Ham wäre 0, egal wie stark alle anderen Merkmale für Ham sprechen. Ein einziges ungesehenes Wort entscheidet dann alles.

Ergänzung: Abhilfe ist die Laplace-Glättung (Laplace / additive smoothing): Man addiert zu jeder Zählung eine Pseudo-Zählung, z. B. $p(x_1{=}1\mid H) = (1+1)/(6+2)$ bei binären Merkmalen.

In der Praxis: Logarithmen

Ergänzung: Bei vielen Merkmalen (Tausende Wörter) wird das Produkt vieler kleiner Zahlen numerisch 0 (Underflow). Man vergleicht deshalb die Log-Posteriors: $\log p(\omega_i) + \sum_j \log p(x_j\mid\omega_i)$. Da der Logarithmus monoton ist, ändert sich die Entscheidung nicht, und aus dem Produkt wird eine Summe.

Gaussian Naive Bayes

Für kontinuierliche Merkmale nimmt man für die einzelnen Likelihoods $p(x_j\mid\omega_i)$ oft eine Gaußverteilung an. Das heißt dann Gaussian Naive Bayes (GNB) 📄 06_bayes.pdf, Folie 17.

Modell und Training

Beim GNB nimmt man für jedes Merkmal $x_i$ und jede Klasse $\omega_j$ eine Gaußverteilung an 📄 06_bayes.pdf, Folie 18. (Achtung: Auf Folie 18 ist der Index vertauscht, $i$ läuft über die Merkmale, $j$ über die Klassen.)

$$p(x_i\mid\omega_j) = \frac{1}{\sqrt{2\pi\sigma_{ij}^2}}\; e^{-\frac12\frac{(x_i-\mu_{ij})^2}{\sigma_{ij}^2}}.$$

Training heißt hier nur: Mittelwert $\mu_{ij}$ und Standardabweichung $\sigma_{ij}$ für jede Kombination aus Merkmal und Klasse aus den Trainingsdaten $x_{i,k}$ schätzen (Merkmal $i$ des Trainingsbeispiels $k$):

$$\mu_{ij} = \frac{1}{|\omega_j|}\sum_{k\in\omega_j} x_{i,k} \qquad\text{und}\qquad \sigma_{ij}^2 = \frac{1}{|\omega_j|-1}\sum_{k\in\omega_j} (x_{i,k}-\mu_{ij})^2.$$

Dabei ist $|\omega_j|$ die Anzahl der Trainingsbeispiele in Klasse $\omega_j$, und die Summen laufen nur über die Beispiele dieser Klasse. Der Faktor $1/(|\omega_j|-1)$ macht die Varianzschätzung erwartungstreu (siehe Stichprobenvarianz in Kapitel 1).

Die A-priori-Wahrscheinlichkeiten ergeben sich aus den relativen Häufigkeiten der Klassen im Trainingsdatensatz ($\ell$ = Gesamtzahl der Trainingsbeispiele):

$$p(\omega_j) = \frac{|\omega_j|}{\ell}.$$

Fallstrick: Priors aus den Trainingsdaten

Diese Schätzung ist nur sinnvoll, wenn die Klassenverteilung im Trainingsset der im Einsatz entspricht. Wurde der Datensatz künstlich balanciert (z. B. 50 % Betrugsfälle, obwohl in Wirklichkeit 0,1 %), sind die so geschätzten Priors falsch und der Klassifikator schlägt viel zu oft „Betrug“ vor.

Rechenbeispiel: GNB von Hand

Ergänzung, nicht auf den Folien: Zwei Merkmale, je drei Trainingspunkte pro Klasse:

Klasse	Trainingspunkte $(x_1, x_2)$	$\mu_{1j}$	$\mu_{2j}$	$\sigma_{1j}^2$	$\sigma_{2j}^2$
$\omega_1$	$(1,5),\ (2,6),\ (3,7)$	2	6	1	1
$\omega_2$	$(6,2),\ (7,3),\ (8,4)$	7	3	1	1

Varianz z. B. für $x_1$ in $\omega_1$: Abweichungen $-1, 0, 1$, Quadratsumme 2, geteilt durch $3-1=2$ ergibt 1. Priors: $p(\omega_1)=p(\omega_2)=3/6=0{,}5$.

Neuer Punkt $\mathbf{x}=(4,4)$. Mit $\sigma=1$ ist jeder Faktor $\frac{1}{\sqrt{2\pi}}e^{-z^2/2}$ mit $z = x_i-\mu_{ij}$:

	$z$ für $x_1$	$z$ für $x_2$	$p(x_1\mid\omega_j)$	$p(x_2\mid\omega_j)$	Produkt
$\omega_1$	$4-2=2$	$4-6=-2$	0,0540	0,0540	0,00292
$\omega_2$	$4-7=-3$	$4-3=1$	0,00443	0,2420	0,00107

Die Priors sind gleich, also gewinnt $\omega_1$. Posterior: $p(\omega_1\mid\mathbf{x}) = 0{,}00292/(0{,}00292+0{,}00107)\approx 0{,}73$.

Mit Logarithmen geht es eleganter: Die Konstanten sind für beide Klassen gleich, es bleibt der Vergleich von $-\tfrac12\sum_i z_i^2$, also $-\tfrac12(4+4)=-4$ gegen $-\tfrac12(9+1)=-5$. Differenz 1, also Quotient $e^1\approx 2{,}72$ und Posterior $e/(1+e)\approx 0{,}73$.

Dasselbe in NumPy:

import numpy as np

X = np.array([[1, 5], [2, 6], [3, 7], [6, 2], [7, 3], [8, 4]], float)
y = np.array([0, 0, 0, 1, 1, 1])
x = np.array([4.0, 4.0])

mu    = np.array([X[y == k].mean(axis=0)        for k in (0, 1)])
var   = np.array([X[y == k].var(axis=0, ddof=1) for k in (0, 1)])
prior = np.array([np.mean(y == k)               for k in (0, 1)])

# Log-Likelihood (Summe über Merkmale) + Log-Prior
log_post = -0.5 * np.sum(np.log(2*np.pi*var) + (x - mu)**2 / var, axis=1) + np.log(prior)
post = np.exp(log_post - log_post.max()); post /= post.sum()
print(post)   # [0.731 0.269]

Hinweis: sklearn.naive_bayes.GaussianNB schätzt die Varianz mit $1/n$ statt $1/(n-1)$ (plus eine kleine Glättung), liefert hier also etwas andere Wahrscheinlichkeiten (etwa 0,82 statt 0,73), aber dieselbe Entscheidung.

Beispiel: gleiche Varianzen in allen Merkmalen

Folie 19 zeigt links den 1D-Fall, rechts den 2D-Fall mit zwei Gaußverteilungen gleicher (kugelförmiger) Varianz und gleichen Priors $P(\omega_1)=P(\omega_2)=0{,}5$ 📄 06_bayes.pdf, Folie 19. Die Entscheidungsgrenze liegt in 1D genau in der Mitte zwischen den Mittelwerten, in 2D ist sie eine Gerade.

Gleiche A-priori-Wahrscheinlichkeit in allen Klassen führt auf einen linearen Klassifikator (Trennfläche bestimmt sich aus dem kleinsten Abstand zum Klassenmittelwert).

Herleitung (Ergänzung): Alle $\sigma_{ij}=\sigma$ gleich. Dann ist der Log-Posterior bis auf Konstanten, die für alle Klassen gleich sind,

$$\log p(\omega_j\mid\mathbf{x}) = -\frac{1}{2\sigma^2}\sum_i (x_i-\mu_{ij})^2 + \log p(\omega_j) + \text{const} = -\frac{\lVert\mathbf{x}-\boldsymbol\mu_j\rVert^2}{2\sigma^2} + \log p(\omega_j) + \text{const}.$$

Bei gleichen Priors fällt $\log p(\omega_j)$ weg, und man wählt die Klasse mit dem kleinsten euklidischen Abstand $\lVert\mathbf{x}-\boldsymbol\mu_j\rVert$ zum Klassenmittelwert (nearest mean classifier). Warum ist die Grenze linear? Ausmultipliziert ist

$$\lVert\mathbf{x}-\boldsymbol\mu_j\rVert^2 = \lVert\mathbf{x}\rVert^2 - 2\boldsymbol\mu_j^\top\mathbf{x} + \lVert\boldsymbol\mu_j\rVert^2.$$

Der quadratische Term $\lVert\mathbf{x}\rVert^2$ ist für beide Klassen gleich und fällt beim Vergleich weg. Übrig bleibt eine in $\mathbf{x}$ lineare Gleichung:

$$(\boldsymbol\mu_1-\boldsymbol\mu_2)^\top\mathbf{x} = \tfrac12\bigl(\lVert\boldsymbol\mu_1\rVert^2-\lVert\boldsymbol\mu_2\rVert^2\bigr).$$

Das ist die Mittelsenkrechte der Verbindungsstrecke zwischen $\boldsymbol\mu_1$ und $\boldsymbol\mu_2$. Im Rechenbeispiel oben: Abstandsquadrat von $(4,4)$ zu $(2,6)$ ist $8$, zu $(7,3)$ ist $10$, also $\omega_1$, wie berechnet.

Sind die Priors ungleich, bleibt die Grenze eine Gerade, verschiebt sich aber parallel weg von der wahrscheinlicheren Klasse (deren Region wird größer).

Präzisierung zur Folienaussage

Folie 19 nennt als Bedingung „gleiche A-priori-Wahrscheinlichkeit“. Für die Linearität entscheidend sind aber die gleichen Varianzen (Überschrift der Folie): Haben die Klassen unterschiedliche Varianzen $\sigma_{ij}$, bleiben quadratische Terme stehen und die Grenze ist gekrümmt. Gleiche Priors sorgen zusätzlich dafür, dass die Grenze genau die Mittelsenkrechte ist (nächster Mittelwert).

Eigenschaften des naiven Bayes-Klassifikators

Folie 20 fasst zusammen 📄 06_bayes.pdf, Folie 20:

• Funktioniert erstaunlich gut: Trotz der stark vereinfachenden Annahmen ist Naive Bayes in einigen Anwendungen sehr erfolgreich, z. B. bei der Dokumentenklassifikation, bei Gehirnscans und als Spamfilter.
• Theoretische Begründung: Man kann zeigen, dass die Nachteile der Unabhängigkeitsannahme bei vielen real vorkommenden Verteilungen nicht sehr ins Gewicht fallen (H. Zhang, The Optimality of Naive Bayes, Proc. FLAIRS, 2004). Grob gesagt: Abhängigkeiten zwischen Merkmalen heben sich über die Klassen hinweg oft gegenseitig auf.
• Wenig Parameter, wenig Daten: Bei $d$-dimensionalen Daten und zwei Klassen sind nur $4\times d$ Parameter zu schätzen ($\mu_{ij}$ und $\sigma_{ij}$ für $d$ Merkmale und 2 Klassen). Das braucht relativ wenig Trainingsdaten.
• Schnelles Training: Ein Durchlauf über die Daten genügt (Mittelwerte und Varianzen summieren), also $O(\ell)$ in der Anzahl der Trainingsbeispiele $\ell$.
• Varianten je nach Art der Daten:

Variante	Daten	Modell für $p(x_j\mid\omega_i)$
Gaussian Naive Bayes	kontinuierlich	Gaußverteilung
Bernoulli Naive Bayes	binär (Wort kommt vor / nicht)	Bernoulli-Verteilung
Multinomial Naive Bayes	ganzzahlig (Wortanzahlen)	Multinomialverteilung

Das Spamfilter-Beispiel oben ist ein Bernoulli Naive Bayes.

Zum Vergleich: volle Kovarianz

Ergänzung: Ohne Unabhängigkeitsannahme bräuchte ein Gauß-Modell pro Klasse eine volle $d\times d$-Kovarianzmatrix, also etwa $d^2/2$ Parameter statt $d$. Bei $d=1000$ Merkmalen sind das rund 500 000 statt 1000 Varianzen pro Klasse, mit wenigen hundert Trainingsbeispielen nicht schätzbar.

Fallstrick: Naive-Bayes-Wahrscheinlichkeiten sind oft schlecht kalibriert

Ergänzung: Sind Merkmale stark korreliert (z. B. dasselbe Wort doppelt als Merkmal), wird ihre Evidenz mehrfach gezählt. Die Entscheidung bleibt oft richtig, aber die Posterior-Werte werden zu extrem (nahe 0 oder 1). Die Zahl $p(\omega\mid\mathbf{x})$ eines Naive-Bayes-Modells sollte man deshalb nicht wörtlich als Wahrscheinlichkeit nehmen.