3.1 Entscheidungstheorie

Was ist Entscheidungstheorie?

Die Entscheidungstheorie (decision theory) bewertet die Kosten einer Klassifikationsentscheidung mit Hilfe von Wahrscheinlichkeitsaussagen 📄 06_bayes.pdf, Folie 4. Die zentrale, idealisierende Grundannahme lautet:

Alle Wahrscheinlichkeiten sind im Vornhinein bekannt.

Das ist natürlich unrealistisch, aber gerade deshalb nützlich: Man kann ausrechnen, wie man bestenfalls entscheiden könnte. Die Entscheidungstheorie bildet so die formale Grundlage der Mustererkennung und formalisiert, was man intuitiv als „gesunden Menschenverstand“ bezeichnen würde: Berücksichtige, was du vorher weißt, und was du gemessen hast.

Das Fischbeispiel

Das durchgehende Beispiel stammt aus Duda, Hart & Stork 📄 06_bayes.pdf, Folie 5: Auf einem Förderband einer Fischfabrik kommen Lachse (salmon) und Wolfsbarsche (sea bass) vorbei. Eine Kamera misst ein Merkmal, die Helligkeit (lightness) des Fisches, und ein System soll automatisch sortieren.

Das Histogramm zeigt: Lachse sind eher dunkel (Helligkeit um 3), Wolfsbarsche eher hell (um 7). Die Verteilungen überlappen aber im Bereich 4 bis 7. Eine Schwelle $x^*$ (im Bild bei etwa 5,5) trennt grob, aber egal wo man sie setzt, einige Fische werden falsch einsortiert.

Frage: Wo ist die beste Schwelle, und wie formalisiert man „beste“?

Naturzustände und A-priori-Wahrscheinlichkeiten

Annahme: Die Reihenfolge der Fische auf dem Band ist zufällig, also nicht vorhersagbar 📄 06_bayes.pdf, Folie 6. In der Sprache der Entscheidungstheorie ist die Natur in einem von zwei möglichen Zuständen $\omega$ (state of nature):

$$\text{Lachs: } \omega = \omega_1, \qquad \text{Wolfsbarsch: } \omega = \omega_2.$$

Weil $\omega$ unvorhersagbar ist, wird es als Zufallsvariable modelliert. Die Zustände $\omega_i$ sind genau das, was man im ML-Kontext Klassen nennt.

Weitere Annahme: Es gibt eine A-priori-Wahrscheinlichkeit (prior probability) $p(\omega_1)$ für Lachs und $p(\omega_2)$ für Wolfsbarsch. Bei zwei Zuständen gilt

$$p(\omega_1) + p(\omega_2) = 1.$$

Die A-priori-Wahrscheinlichkeit beschreibt das Vorwissen über das Entscheidungsproblem, z. B. „in dieser Jahreszeit werden doppelt so viele Lachse gefangen wie Wolfsbarsche“, also $p(\omega_1)=2/3$, $p(\omega_2)=1/3$.

Entscheiden ohne Messung

Angenommen, jeder Fehler kostet gleich viel, und das Band kann nicht beobachtet werden. Dann ist die beste Entscheidungsregel 📄 06_bayes.pdf, Folie 7:

$$\text{Entscheide für } \omega_1, \text{ falls } p(\omega_1) > p(\omega_2), \text{ sonst für } \omega_2.$$

Man entscheidet also immer gleich (im Beispiel immer „Lachs“). Die Fehlerwahrscheinlichkeit ist dann $\min(p(\omega_1), p(\omega_2))$, im Beispiel $1/3$. Das ist das Beste, was ohne Information über den einzelnen Fisch möglich ist.

Intuition

Das ist die „Mehrheitsklassen-Regel“ (majority class). Sie ist auch in der Praxis eine wichtige Baseline: Ein Klassifikator, der nicht besser ist als „immer die häufigste Klasse raten“, hat nichts gelernt. Bei unbalancierten Daten (z. B. 99 % gesund, 1 % krank) erreicht diese triviale Regel schon 99 % Genauigkeit.

Klassenbedingte Wahrscheinlichkeit

Jetzt messen wir. Für jeden Fisch gibt es eine (fehlerbehaftete) Messung eines Merkmalsvektors (feature vector) $\mathbf{x}$, im einfachsten Fall nur die Helligkeit $x$. Die Messung hängt über die klassenbedingte Wahrscheinlichkeit (class-conditional probability) $p(\mathbf{x}\mid\omega_i)$ von der Klasse ab 📄 06_bayes.pdf, Folie 7.

• $p(x\mid\omega_1)$ ist die Verteilung der Helligkeit unter allen Lachsen,
• $p(x\mid\omega_2)$ die Verteilung der Helligkeit unter allen Wolfsbarschen.

Beide sind normierte Dichten: $\int p(x\mid\omega_i)\,dx = 1$. Die Abbildung auf Folie 7 zeigt zwei solcher Kurven über $x\in[9,15]$, die sich stark überschneiden (die von $\omega_1$ ist sogar zweigipflig).

Als Funktion von $\omega_i$ bei festem $\mathbf{x}$ betrachtet heißt $p(\mathbf{x}\mid\omega_i)$ auch Likelihood (likelihood): „Wie gut erklärt die Klasse $\omega_i$ die beobachtete Messung?“

Fallstrick: $p(x\mid\omega)$ ist nicht $p(\omega\mid x)$

$p(x\mid\omega_1)$ beantwortet „Wenn es ein Lachs ist, wie wahrscheinlich ist diese Helligkeit?“. Für die Entscheidung brauchen wir aber die umgekehrte Frage: „Wenn ich diese Helligkeit messe, wie wahrscheinlich ist es ein Lachs?“, also $p(\omega_1\mid x)$. Die Umrechnung leistet der Satz von Bayes. Die beiden zu verwechseln ist der klassische Denkfehler (Prosecutor's Fallacy).

Exkurs: Paare von Zufallsvariablen

Um den Satz von Bayes herzuleiten, braucht man etwas Wahrscheinlichkeitsrechnung für zwei Zufallsvariablen (ZV) 📄 06_bayes.pdf, Folie 8.

Gemeinsame Verteilung und Randverteilung

Zwei diskrete Zufallsvariablen $x$ und $y$ werden durch eine gemeinsame Verteilung (joint distribution) $p(x,y)$ beschrieben, die jedem Wertepaar $(x_i,y_j)$ eine Wahrscheinlichkeit $p_{ij}$ zuordnet. Es gilt

$$p(x,y)\ge 0 \qquad\text{und}\qquad \sum_{x_i\in\mathcal{X}}\sum_{y_j\in\mathcal{Y}} p(x_i,y_j) = 1.$$

Die Randwahrscheinlichkeitsfunktionen (marginal distributions) erhält man, indem man über die jeweils andere Variable summiert („herausmarginalisiert“):

$$p(x) = \sum_{y_j\in\mathcal{Y}} p(x,y_j), \qquad p(y) = \sum_{x_i\in\mathcal{X}} p(x_i,y).$$

Die Folie zeigt als Beispiel (aus MacKay, 2003) die gemeinsame Verteilung aufeinanderfolgender Buchstabenpaare in englischem Text als Matrix: Die Größe jedes Quadrats ist proportional zu $p(x,y)$. Die Randverteilung $p(x)$ wäre dann die Zeilensumme, also die Häufigkeit des Buchstabens $x$ überhaupt.

Bedingte Wahrscheinlichkeit und Kettenregel

Wenn zwei ZV voneinander statistisch abhängig sind, erhöht die Kenntnis der einen das Wissen über die andere 📄 06_bayes.pdf, Folie 9. Die bedingte Wahrscheinlichkeit (conditional probability) „Wahrscheinlichkeit von $x$ gegeben $y$“ ist

$$p(x\mid y) = \frac{p(x,y)}{p(y)}.$$

Umgestellt ergibt sich die Kettenregel (product rule / chain rule):

$$p(x,y) = p(x\mid y)\,p(y) = p(y\mid x)\,p(x).$$

Die zweite Gleichheit gilt, weil man die Rollen von $x$ und $y$ tauschen kann.

Bei statistisch unabhängigen ZV gilt $p(x,y)=p(x)p(y)$ und damit

$$p(x\mid y) = \frac{p(x)\,p(y)}{p(y)} = p(x).$$

Die Kenntnis von $y$ ändert also nichts an der Verteilung von $x$.

Kleines Zahlenbeispiel

Ergänzung, nicht auf den Folien: Gemeinsame Verteilung von Fischart und „hell/dunkel“:

	dunkel	hell	Rand $p(\omega)$
Lachs $\omega_1$	0,50	0,10	0,60
Wolfsbarsch $\omega_2$	0,05	0,35	0,40
Rand $p(x)$	0,55	0,45	1,00

• Randverteilungen: Zeilen- bzw. Spaltensummen.
• Bedingt: $p(\text{hell}\mid\omega_1) = 0{,}10/0{,}60 \approx 0{,}167$, $p(\omega_1\mid\text{hell}) = 0{,}10/0{,}45 \approx 0{,}222$.
• Abhängig? $p(\omega_1)\,p(\text{hell}) = 0{,}6\cdot 0{,}45 = 0{,}27 \ne 0{,}10 = p(\omega_1,\text{hell})$, also ja.

Der Satz von Bayes

Frage: Wie beeinflusst die Messung $\mathbf{x}$ die Schätzung des Naturzustandes 📄 06_bayes.pdf, Folie 10?

Herleitung in drei Schritten:

1. Randwahrscheinlichkeit von $\mathbf{x}$ (Summe über alle Klassen): $$p(\mathbf{x}) = \sum_i p(\omega_i,\mathbf{x}).$$
2. Kettenregel, auf zwei Arten geschrieben: $$p(\omega_i,\mathbf{x}) = p(\mathbf{x}\mid\omega_i)\,p(\omega_i) \qquad\text{und}\qquad p(\omega_i,\mathbf{x}) = p(\omega_i\mid\mathbf{x})\,p(\mathbf{x}).$$
3. Beide rechten Seiten gleichsetzen, nach $p(\omega_i\mid\mathbf{x})$ auflösen und für $p(\mathbf{x})$ Schritt 1 (mit der Kettenregel) einsetzen:

Satz von Bayes (Folie 10)

$$p(\omega_i\mid\mathbf{x}) = \frac{p(\mathbf{x}\mid\omega_i)\,p(\omega_i)}{\sum_k p(\mathbf{x}\mid\omega_k)\,p(\omega_k)}$$

In Worten:

$$\text{A-posteriori} = \frac{\text{Likelihood}\times\text{A-priori}}{\text{Evidenz}}$$

Die Bausteine:

Begriff	Formel	Bedeutung
A-priori (prior)	$p(\omega_i)$	Vorwissen vor der Messung
Likelihood	$p(\mathbf{x}\mid\omega_i)$	wie gut Klasse $\omega_i$ die Messung erklärt
Evidenz (evidence)	$p(\mathbf{x})=\sum_k p(\mathbf{x}\mid\omega_k)p(\omega_k)$	Normierungskonstante, gleich für alle Klassen
A-posteriori (posterior)	$p(\omega_i\mid\mathbf{x})$	Wissen nach der Messung

Die Evidenz sorgt nur dafür, dass sich die Posteriors zu 1 summieren: $\sum_i p(\omega_i\mid\mathbf{x}) = 1$.

Durchgerechnetes Beispiel

Ergänzung, nicht auf den Folien: Priors $p(\omega_1)=2/3$ (Lachs), $p(\omega_2)=1/3$ (Wolfsbarsch). Wir messen eine Helligkeit $x$, für die gilt $p(x\mid\omega_1)=0{,}1$ und $p(x\mid\omega_2)=0{,}3$. Der Wert ist also für Wolfsbarsche dreimal typischer.

1. Zähler: $p(x\mid\omega_1)p(\omega_1) = 0{,}1\cdot\tfrac23 \approx 0{,}0667$ und $p(x\mid\omega_2)p(\omega_2) = 0{,}3\cdot\tfrac13 = 0{,}1$.
2. Evidenz: $p(x) = 0{,}0667 + 0{,}1 = 0{,}1667$.
3. Posteriors: $p(\omega_1\mid x) = 0{,}0667/0{,}1667 = 0{,}4$ und $p(\omega_2\mid x) = 0{,}1/0{,}1667 = 0{,}6$.

Obwohl Lachse a priori doppelt so häufig sind, spricht die Messung so stark für den Wolfsbarsch, dass er a posteriori wahrscheinlicher ist. Wäre die Likelihood-Relation nur 2:1 statt 3:1 gewesen, hätten sich Prior und Likelihood genau aufgehoben (Posteriors 0,5/0,5).

Prior und Likelihood ziehen gegeneinander

Der Posterior ist ein Kompromiss: Der Prior zieht zur häufigen Klasse, die Likelihood zur Klasse, die die Messung gut erklärt. Je aussagekräftiger die Messung (je unterschiedlicher die Likelihoods), desto weniger zählt der Prior.

Die Bayessche Entscheidungsregel

Nach einer Messung $\mathbf{x}$ ist die Fehlerwahrscheinlichkeit 📄 06_bayes.pdf, Folie 11

$$p(\text{Fehler}\mid\mathbf{x}) = \begin{cases} p(\omega_2\mid\mathbf{x}) & \text{bei Entscheidung für } \omega_1,\\ p(\omega_1\mid\mathbf{x}) & \text{bei Entscheidung für } \omega_2. \end{cases}$$

Warum? Entscheide ich mich für $\omega_1$, liege ich genau dann falsch, wenn in Wahrheit $\omega_2$ vorliegt, und das hat (gegeben $\mathbf{x}$) die Wahrscheinlichkeit $p(\omega_2\mid\mathbf{x})$.

Diese Fehlerwahrscheinlichkeit wird also minimiert, wenn man sich für die Klasse mit dem größeren Posterior entscheidet:

Bayessche Entscheidungsregel (Folie 11)

Entscheide für $\omega_1$, wenn $p(\omega_1\mid\mathbf{x}) > p(\omega_2\mid\mathbf{x})$, sonst für $\omega_2$.

Gleichwertig (Evidenz gekürzt): Entscheide für $\omega_1$, wenn

$$p(\mathbf{x}\mid\omega_1)\,p(\omega_1) > p(\mathbf{x}\mid\omega_2)\,p(\omega_2),$$

sonst für $\omega_2$.

Die zweite Form ist praktischer, weil man die Evidenz nicht berechnen muss. Der Fehler bei gegebenem $\mathbf{x}$ ist dann

$$p(\text{Fehler}\mid\mathbf{x}) = \min\bigl(p(\omega_1\mid\mathbf{x}),\, p(\omega_2\mid\mathbf{x})\bigr).$$

Weil die Regel für jedes einzelne $\mathbf{x}$ den kleinstmöglichen Fehler wählt, minimiert sie auch die gesamte Fehlerwahrscheinlichkeit (Mittel über alle $\mathbf{x}$). Das wird in 3.4 genauer gezeigt.

Grenzfälle zur Kontrolle:

• Gleiche Likelihoods $p(\mathbf{x}\mid\omega_1)=p(\mathbf{x}\mid\omega_2)$: Die Messung ist nutzlos, es entscheiden nur die Priors (wie ohne Messung).
• Gleiche Priors $p(\omega_1)=p(\omega_2)$: Es entscheiden nur die Likelihoods (Maximum-Likelihood-Entscheidung, maximum likelihood decision).

Entscheidung mit Kosten

Ergänzung, nicht auf den Folien: Folie 4 spricht von den „Kosten einer Klassifikationsentscheidung“. Die obige Regel setzt voraus, dass jeder Fehler gleich viel kostet (0-1-Verlust, zero-one loss). Kostet eine Verwechslung mehr als die andere (z. B. Krebs übersehen vs. Fehlalarm), gewichtet man mit Kosten $\lambda_{ij}$ (Kosten, wenn man $\omega_i$ wählt, obwohl $\omega_j$ vorliegt) und wählt die Klasse mit dem kleinsten erwarteten Risiko $R(\omega_i\mid\mathbf{x})=\sum_j \lambda_{ij}\,p(\omega_j\mid\mathbf{x})$. Bei zwei Klassen verschiebt das nur die Schwelle des Likelihood-Quotienten, siehe 3.2.

Folienformulierung „über einen Trainings- oder Testdatensatz“

Folie 11 sagt, die Regel minimiere „auch die Fehlerwahrscheinlichkeit über einen gegebenen Trainings- oder Testdatensatz“. Genau genommen minimiert sie die erwartete Fehlerrate unter der wahren Verteilung. Auf einem konkreten, endlichen Datensatz kann zufällig ein anderer Klassifikator weniger Fehler machen, im Mittel über viele Datensätze aber nicht.