3.4 Klassifikationsfehler & Bayesfehler

Auf den Folien steht dieser Teil schon unter der Überschrift „Signalentdeckungstheorie“. Er beantwortet die Frage, die in 3.1 offen geblieben ist: Warum minimiert die Bayessche Entscheidungsregel den Gesamtfehler, und wie groß ist dieser minimale Fehler?

Zwei Arten von Fehlern

Bei zwei Klassen und Entscheidungsregionen $\mathcal{R}_1$ (entscheide $\omega_1$) und $\mathcal{R}_2$ (entscheide $\omega_2$) gibt es genau zwei Möglichkeiten, falsch zu liegen 📄 06_bayes.pdf, Folie 22:

1. Die Beobachtung $\mathbf{x}$ fällt in $\mathcal{R}_2$, der wahre Naturzustand ist aber $\omega_1$.
2. Die Beobachtung $\mathbf{x}$ fällt in $\mathcal{R}_1$, der wahre Naturzustand ist aber $\omega_2$.

Die Abbildung auf Folie 22 zeigt die gewichteten Likelihoods $p(x\mid\omega_i)P(\omega_i)$ (also gemeinsame Dichten $p(x,\omega_i)$) für beide Klassen. Links einer Grenze $x^*$ liegt $\mathcal{R}_1$, rechts $\mathcal{R}_2$.

• Die rot schraffierte Fläche links ist $\int_{\mathcal{R}_1} p(x\mid\omega_2)P(\omega_2)\,dx$: Stücke der $\omega_2$-Kurve, die in $\mathcal{R}_1$ fallen (Fall 2).
• Die grau schraffierte Fläche rechts ist $\int_{\mathcal{R}_2} p(x\mid\omega_1)P(\omega_1)\,dx$: Stücke der $\omega_1$-Kurve, die in $\mathcal{R}_2$ fallen (Fall 1).

Die Gesamtfehlerwahrscheinlichkeit ist die Summe beider Flächen.

Fehlerwahrscheinlichkeit als Integral

Formal 📄 06_bayes.pdf, Folie 23:

$$\begin{aligned} p(\text{Fehler}) &= p(\mathbf{x}\in\mathcal{R}_2,\ \omega_1) + p(\mathbf{x}\in\mathcal{R}_1,\ \omega_2)\\ &= p(\mathbf{x}\in\mathcal{R}_2\mid\omega_1)\,p(\omega_1) + p(\mathbf{x}\in\mathcal{R}_1\mid\omega_2)\,p(\omega_2)\\ &= \int_{\mathcal{R}_2} p(\mathbf{x}\mid\omega_1)\,p(\omega_1)\,d\mathbf{x} + \int_{\mathcal{R}_1} p(\mathbf{x}\mid\omega_2)\,p(\omega_2)\,d\mathbf{x}. \end{aligned}$$

Schritt für Schritt:

1. Zeile 1: Die beiden Fehlerereignisse schließen sich gegenseitig aus, also addieren sich ihre Wahrscheinlichkeiten.
2. Zeile 2: Kettenregel $p(A,\omega)=p(A\mid\omega)p(\omega)$.
3. Zeile 3: Die Wahrscheinlichkeit, dass $\mathbf{x}$ in eine Region fällt, ist das Integral der Dichte über diese Region.

Warum die Bayes-Grenze optimal ist

Der minimale Fehler wird erreicht, wenn die Entscheidungsgrenze auf dem Punkt liegt, an dem beide A-posteriori-Wahrscheinlichkeiten gleich groß sind. Das ist genau die Bayessche Entscheidungsregel.

Begründung (ausführlicher als auf der Folie): Jeder Punkt $\mathbf{x}$ muss einer der beiden Regionen zugeordnet werden. Ordnet man ihn $\mathcal{R}_1$ zu, trägt er $p(\mathbf{x}\mid\omega_2)p(\omega_2)$ zum Fehlerintegral bei, ordnet man ihn $\mathcal{R}_2$ zu, trägt er $p(\mathbf{x}\mid\omega_1)p(\omega_1)$ bei. Um das Integral zu minimieren, wählt man an jeder Stelle den kleineren Beitrag:

$$\mathbf{x}\in\mathcal{R}_1 \iff p(\mathbf{x}\mid\omega_2)p(\omega_2) < p(\mathbf{x}\mid\omega_1)p(\omega_1) \iff p(\omega_1\mid\mathbf{x}) > p(\omega_2\mid\mathbf{x}).$$

Das ist die Bayessche Entscheidungsregel. Der dabei erreichte Fehler ist

$$p_{\text{Bayes}}(\text{Fehler}) = \int \min\bigl(p(\mathbf{x}\mid\omega_1)p(\omega_1),\ p(\mathbf{x}\mid\omega_2)p(\omega_2)\bigr)\,d\mathbf{x},$$

also die Fläche unter dem Minimum der beiden gewichteten Kurven (Ergänzung: diese kompakte Form steht so nicht auf den Folien).

Bayesfehler

Der mit der Bayesschen Entscheidungsregel erreichbare minimale Fehler heißt Bayesfehler (Bayes error, auch Bayes rate). Kein Klassifikator kann bei derselben Merkmalswahl im Mittel weniger Fehler machen.

Der reduzierbare Fehler

Auf Folie 22 sind zwei Grenzen eingezeichnet 📄 06_bayes.pdf, Folie 22:

• $x_B$: die Bayes-Grenze, an der sich die beiden gewichteten Kurven schneiden.
• $x^*$: eine (suboptimale) Grenze etwas weiter rechts.

Mit $x^*$ statt $x_B$ wird das Stück zwischen $x_B$ und $x^*$ der Region $\mathcal{R}_1$ zugeschlagen, obwohl dort die $\omega_2$-Kurve höher liegt. Dadurch kommt das dreieckige Gebiet (reducible error, dick umrandet) zum Fehler hinzu. Dieser Anteil ist reduzierbar: Schiebt man $x^*$ auf $x_B$, verschwindet er. Der Rest, die Überlappung der beiden Kurven, ist nicht reduzierbar, das ist der Bayesfehler.

Was „nicht reduzierbar“ bedeutet

Der Bayesfehler ist nur bezüglich der gewählten Merkmale unvermeidbar. Mit zusätzlichen oder besseren Merkmalen (z. B. Länge und Helligkeit statt nur Helligkeit) können sich die Klassen weniger überlappen, und der Bayesfehler sinkt. Mehr Trainingsdaten oder ein besseres Lernverfahren helfen dagegen nur gegen den reduzierbaren Anteil.

Rechenbeispiel: Bayesfehler zweier Gaußverteilungen

Ergänzung, nicht auf den Folien: $p(x\mid\omega_1)=\mathcal{N}(0,1)$, $p(x\mid\omega_2)=\mathcal{N}(2,1)$, gleiche Priors $0{,}5$. Mit $\Phi$ bezeichnen wir die Verteilungsfunktion der Standardnormalverteilung.

1. Grenze: Gleiche Varianzen und Priors, also Schnittpunkt genau in der Mitte: $x_B = 1$. $\mathcal{R}_1 = (-\infty, 1)$, $\mathcal{R}_2 = (1, \infty)$.
2. Fall 1 ($\omega_1$ landet rechts von 1): $p(x\ge 1\mid\omega_1) = 1-\Phi(1) \approx 0{,}159$.
3. Fall 2 ($\omega_2$ landet links von 1): $p(x\le 1\mid\omega_2) = \Phi(-1) \approx 0{,}159$.
4. Bayesfehler: $0{,}5\cdot 0{,}159 + 0{,}5\cdot 0{,}159 \approx 0{,}159$, also knapp 16 %.

Setzt man die Grenze stattdessen auf $x^*=1{,}5$: Fall 1: $1-\Phi(1{,}5)\approx 0{,}067$, Fall 2: $\Phi(-0{,}5)\approx 0{,}309$, Gesamt $0{,}5\cdot(0{,}067+0{,}309)\approx 0{,}188$. Der reduzierbare Anteil beträgt also etwa 2,9 Prozentpunkte.

Fallstrick: Schnittpunkt der Likelihoods vs. der gewichteten Likelihoods

Die Bayes-Grenze liegt dort, wo sich $p(x\mid\omega_1)\,p(\omega_1)$ und $p(x\mid\omega_2)\,p(\omega_2)$ schneiden, nicht dort, wo sich die reinen Likelihoods $p(x\mid\omega_i)$ schneiden. Nur bei gleichen Priors fallen beide Punkte zusammen. Sind Lachse häufiger, wandert die Grenze in Richtung der Wolfsbarsche, $\mathcal{R}_1$ wird größer.

Ausblick

Im Rest des Kapitels werden die beiden Fehlerarten mit eigenen Namen versehen (Fehlalarm und Miss) und man betrachtet, wie sie sich gegeneinander verschieben, wenn man die Grenze $x^*$ bewegt. Das führt zur ROC-Kurve in 3.5.