3.2 Bayes-Klassifikator

Definition

Für einen gegebenen Messwert $\mathbf{x}$ schätzt der Bayes-Klassifikator (Bayes classifier) die Klassenzugehörigkeit nach der Bayesschen Entscheidungsregel, verallgemeinert auf beliebig viele Klassen 📄 06_bayes.pdf, Folie 13:

Bayessche Entscheidungsregel (allgemein)

Entscheide dich immer für die Klasse $\omega_i$, deren A-posteriori-Wahrscheinlichkeit $p(\omega_i\mid\mathbf{x})$ am höchsten ist:

$$\hat\omega(\mathbf{x}) = \arg\max_i\, p(\omega_i\mid\mathbf{x}) = \arg\max_i\, p(\mathbf{x}\mid\omega_i)\,p(\omega_i).$$

Diese Regel heißt auch Maximum-a-posteriori-Entscheidung (MAP decision). Die zweite Gleichheit gilt wieder, weil die Evidenz $p(\mathbf{x})$ nicht von $i$ abhängt.

Der Bayes-Klassifikator ist (theoretisch) der bestmögliche Klassifikator, da er die Wahrscheinlichkeit einer Fehlklassifikation minimiert. Jeder andere Klassifikator macht mehr oder mindestens gleich viele Fehler.

„Bestmöglich“ heißt nicht „fehlerfrei“

Überlappen sich die Klassen im Merkmalsraum, macht auch der Bayes-Klassifikator Fehler (den Bayesfehler, siehe 3.4). Außerdem gilt die Optimalität nur, wenn die wahren Verteilungen bekannt sind. Jedes reale Verfahren (Naive Bayes, logistische Regression, SVM, neuronale Netze …) kann man als Versuch sehen, den Bayes-Klassifikator aus Daten möglichst gut anzunähern.

Ergänzung: Für $c$ Klassen ist der Fehler bei gegebenem $\mathbf{x}$ dann $p(\text{Fehler}\mid\mathbf{x}) = 1-\max_i p(\omega_i\mid\mathbf{x})$.

Entscheidungsregionen und Entscheidungsgrenzen

Je nachdem, welche A-posteriori-Wahrscheinlichkeit am größten ist, wird der Inputraum in Entscheidungsregionen (decision regions) $\mathcal{R}_1, \mathcal{R}_2, \dots$ aufgeteilt 📄 06_bayes.pdf, Folie 13:

$$\mathcal{R}_i = \bigl\lbrace \mathbf{x} : p(\omega_i\mid\mathbf{x}) \ge p(\omega_k\mid\mathbf{x}) \text{ für alle } k \bigr\rbrace.$$

Die Entscheidungsregionen sind durch Entscheidungsgrenzen (decision boundaries) voneinander getrennt. Auf einer Grenze zwischen $\omega_1$ und $\omega_2$ gilt $p(\omega_1\mid\mathbf{x}) = p(\omega_2\mid\mathbf{x})$, dort ist der Klassifikator „unentschieden“.

Wichtig: Eine Entscheidungsregion muss nicht zusammenhängend sein. Sie kann aus mehreren getrennten Stücken bestehen, wie das folgende Beispiel zeigt.

Beispiel: ein kontinuierlicher Messwert

Folie 14 zeigt die beiden Posteriors $P(\omega_1\mid x)$ und $P(\omega_2\mid x)$ für ein Zweiklassenproblem über $x\in[9,15]$ 📄 06_bayes.pdf, Folie 14. (Es sind die Posteriors zu den Likelihoods von Folie 7 mit Priors $2/3$ und $1/3$.) Zu beobachten:

• An jeder Stelle gilt $P(\omega_1\mid x)+P(\omega_2\mid x)=1$, die Kurven sind spiegelbildlich zur Linie 0,5.
• Die Kurven schneiden sich mehrfach (bei etwa $x\approx 10$, $11{,}2$ und $12$). Jeder Schnittpunkt ist eine Entscheidungsgrenze.
• Ganz links ist $\omega_2$ fast sicher, ganz rechts $\omega_1$. Dazwischen wechselt die Entscheidung mehrfach.

Likelihood-Quotient und Schwelle

Für zwei Klassen kann man die Entscheidungsregel umformen, indem man beide Seiten durch $p(\mathbf{x}\mid\omega_2)\,p(\omega_1)$ teilt (beide positiv):

$$p(\mathbf{x}\mid\omega_1)\,p(\omega_1) > p(\mathbf{x}\mid\omega_2)\,p(\omega_2) \quad\Longleftrightarrow\quad \underbrace{\frac{p(\mathbf{x}\mid\omega_1)}{p(\mathbf{x}\mid\omega_2)}}_{\text{Likelihood-Quotient}} > \underbrace{\frac{p(\omega_2)}{p(\omega_1)}}_{=:\ \theta}.$$

Entscheide also für $\omega_1$, wenn der Likelihood-Quotient (likelihood ratio) die Schwelle $\theta$ überschreitet. Das Schöne daran: Die linke Seite hängt nur von der Messung ab, die rechte Seite nur vom Vorwissen (und, s. u., von den Kosten).

Genau das zeigt Folie 15 📄 06_bayes.pdf, Folie 15: Aufgetragen ist der Quotient $p(x\mid\omega_1)/p(x\mid\omega_2)$ über $x$, dazu eine waagrechte Schwelle $\theta_a$ (rot gestrichelt).

• Wo die Kurve über $\theta_a$ liegt, entscheidet man $\omega_1$ (Region $\mathcal{R}_1$, schwarz).
• Wo sie darunter liegt, entscheidet man $\omega_2$ (Region $\mathcal{R}_2$, rot).
• Die Kurve schneidet $\theta_a$ dreimal, deshalb gibt es vier Intervalle: $\mathcal{R}_2, \mathcal{R}_1, \mathcal{R}_2, \mathcal{R}_1$. Die Region $\mathcal{R}_2$ besteht also aus zwei getrennten Stücken.

Im Bild ist außerdem eine zweite, höhere Schwelle $\theta_b$ markiert (nur auf der Achse, ohne eingezeichnete Regionen). Bei der höheren Schwelle liegt ein größerer Teil der Kurve unterhalb, die $\mathcal{R}_2$-Stücke werden breiter und die $\mathcal{R}_1$-Stücke schmaler.

Ergänzung, nicht auf den Folien (aus Duda et al.): $\theta_a$ ist die Schwelle bei 0-1-Verlust, also $\theta_a = p(\omega_2)/p(\omega_1)$. $\theta_b$ ergibt sich, wenn es teurer ist, ein $\omega_2$ fälschlich als $\omega_1$ zu klassifizieren als umgekehrt. Mit Kosten $\lambda_{ij}$ (Wahl $\omega_i$, wahr $\omega_j$) lautet die allgemeine Schwelle

$$\theta = \frac{(\lambda_{12}-\lambda_{22})\,p(\omega_2)}{(\lambda_{21}-\lambda_{11})\,p(\omega_1)}.$$

Höhere Kosten für „fälschlich $\omega_1$“ ($\lambda_{12}$ groß) erhöhen die Schwelle, man wird vorsichtiger mit der Entscheidung für $\omega_1$, und $\mathcal{R}_1$ schrumpft.

Eine Schwelle verschieben = einen Arbeitspunkt wählen

Diese Idee kehrt bei der ROC-Kurve wieder: Ein Klassifikator liefert einen Wert (hier den Likelihood-Quotienten), und erst die Wahl der Schwelle legt fest, wie oft er „$\omega_1$“ sagt. Verschiebt man die Schwelle, tauscht man eine Fehlerart gegen die andere, siehe 3.5.

Beispiel: zwei kontinuierliche Messwerte

Folie 16 zeigt dasselbe für einen zweidimensionalen Merkmalsraum 📄 06_bayes.pdf, Folie 16. Über der Ebene sind die beiden Funktionen $p(\mathbf{x}\mid\omega_1)P(\omega_1)$ (grau) und $p(\mathbf{x}\mid\omega_2)P(\omega_2)$ (rot) als Gebirge aufgetragen. An jedem Punkt der Ebene gewinnt das höhere Gebirge.

In der Projektion darunter sieht man:

• Die Entscheidungsgrenzen (decision boundary) sind gekrümmte Kurven, keine Geraden.
• $\mathcal{R}_2$ besteht wieder aus mehreren Teilen: ein Gebiet um den roten Gipfel und ein Gebiet ganz außen (links unten), denn weit weg von beiden Gipfeln fällt die schmalere graue Verteilung schneller ab als die breitere rote, sodass dort wieder $\omega_2$ gewinnt.
• $\mathcal{R}_1$ ist ein Gebiet um den grauen Gipfel.

Ergänzung: Bei Gaußverteilungen mit unterschiedlichen Kovarianzmatrizen sind die Grenzen allgemein Quadriken (Ellipsen, Parabeln, Hyperbeln). Bei gleichen Kovarianzmatrizen kürzen sich die quadratischen Terme heraus, und die Grenze wird linear. Das ist genau der Fall von Folie 19, siehe 3.3.

Von der Theorie zur Praxis

Für den Bayes-Klassifikator braucht man $p(\mathbf{x}\mid\omega_i)$ und $p(\omega_i)$. Die Priors sind leicht zu schätzen (relative Klassenhäufigkeiten). Die klassenbedingten Dichten $p(\mathbf{x}\mid\omega_i)$ im $d$-dimensionalen Raum zu schätzen, ist dagegen schwer: Mit wachsendem $d$ braucht man exponentiell viele Daten, um den Raum abzudecken (Fluch der Dimensionalität, curse of dimensionality, Ergänzung).

Der naive Bayes-Klassifikator im nächsten Abschnitt umgeht das mit einer vereinfachenden Annahme.