Wiederholung Wahrscheinlichkeitstheorie

Ereignisse und Wahrscheinlichkeit

Hinweis: Die folgende Darstellung zur Einführung in die Wahrscheinlichkeitstheorie dient dem Verständnis des Naive Bayes Klassifikationsalgorithmus und ist teilweise eher oberflächlich gehalten. Sie kann und soll keine entsprechende mathematische Einführung ersetzen!

Ereignisse

• Ereignisse $\Omega = \lbrace \omega_1, \omega_2, \ldots, \omega_n \rbrace$: endliche Menge der Ausgänge eines Zufallsexperiments

• Elementarereignis: Die $\omega_i \in \Omega$

  • decken alle möglichen Versuchsergebnisse ab, und
  • schließen sich gegenseitig aus

Regeln

• Wenn $A$ und $B$ Ereignisse sind, dann auch $A \cup B$
• $\Omega$ wird als sicheres Ereignis bezeichnet: Enthält definitionsgemäß alle Versuchsausgänge, d.h. ein in der Menge enthaltenes Ereignis muss auftreten
• Die leere Menge $\emptyset$ wird als unmögliches Ereignis bezeichnet
• Die Variablen $A$ und $B$ heißen auch Zufallsvariablen

Im Rahmen dieser Veranstaltung betrachten wir nur diskrete Zufallsvariablen mit endlichem Wertebereich!

Wahrscheinlichkeit

• Wahrscheinlichkeit:

  Sei $\Omega = \lbrace \omega_1, \omega_2, \ldots, \omega_n \rbrace$ endlich. Die Wahrscheinlichkeit $P(A)$ für ein Ereignis $A$ ist dann definiert als

  $$ P(A) = \frac{|A|}{|\Omega|} = \frac{\text{Anzahl der für A günstigen Fälle}}{\text{Anzahl der möglichen Fälle}} $$

  Man könnte auch schreiben: $P(A) = \sum_{\omega \in A} P(\omega)$

  Hinweis: Diese Definition von Wahrscheinlichkeit geht von gleich wahrscheinlichen Elementarereignissen aus! Die allgemeine Definition geht über einen entsprechenden Grenzwert.

Verteilung

Den Vektor mit den Wahrscheinlichkeiten aller Elementarereignisse nennt man auch Verteilung.

Beispiel: $\mathbf{P}(A) = (P(A=1), P(A=2), \ldots, P(A=6)) = (1/6, 1/6, \ldots, 1/6)$

Hinweis: Wir betrachten hier nur diskrete Zufallsvariablen. Für kontinuierliche Variablen wird die Verteilung mit Hilfe einer Dichtefunktion dargestellt, beispielsweise der Gauss'schen Funktion.

Beispiel

• Einmaliges Würfeln mit einem Spielwürfel: $\Omega = \lbrace 1,2,3,4,5,6 \rbrace$
• Elementarereignisse: $\lbrace 1,2,3,4,5,6 \rbrace$
• Das Würfeln einer geraden Zahl ($A = \lbrace 2,4,6 \rbrace$) ist kein Elementarereignis, ebenso wie das Würfeln einer Zahl kleiner 5 ($B = \lbrace 1,2,3,4 \rbrace$), da $A \cap B = \lbrace 2,4 \rbrace \ne \emptyset$
• Wahrscheinlichkeit, eine 1 zu würfeln: $P(A \in \lbrace 1 \rbrace) = P(A=1) = \frac{1}{6}$. Anmerkung: Man schreibt statt $P(A \in \lbrace 1 \rbrace)$ oft einfach $P(1)$.
• Wahrscheinlichkeit, eine gerade Zahl zu würfeln: $P(A \in \lbrace 2,4,6 \rbrace) = P(A=2 \vee A=4 \vee A=6) = \frac{|\lbrace 2,4,6 \rbrace|}{|\lbrace 1,2,3,4,5,6 \rbrace|} = \frac{3}{6} = 0.5$

Rechenregeln: Kolmogorov Axiome

Sei $A$ ein Ereignis, also $A \subseteq \Omega$:

• $0 \le P(A) \le 1$

• $\Omega = \lbrace \omega_1, \omega_2, \ldots, \omega_n \rbrace$: $\sum_{i} P(\omega_i) = 1$ (Normierungsbedingung: Summe über die Wahrscheinlichkeiten aller Elementarereignisse ist immer 1)

• $P(A \cup B) = P(A) + P(B) - P(A \cap B)$

Daraus folgt (u.a.):

• $P(\Omega) = 1$
• $P(\emptyset) = 0$
• $P(A) = 1- P(\neg A)$

• $A$ und $B$ unabhängig: $P(A \cup B) = P(A) + P(B)$

• $P(A \cap B)$ ist leer, wenn $A$ und $B$ sich nicht überlappen

• $A \subseteq B$: $P(A) \le P(B)$

Verbundwahrscheinlichkeiten

• $P(S,H) = 0.04$

Die Tabelle kann man so lesen: In 4 von 100 Fällen tritt das Ereignis "Schnupfen" gleichzeitig mit dem Ereignis "Halsschmerzen" auf, in 6 von 100 Fällen tritt "Schupfen" ohne Halsschmerzen auf. ... In Summe kommt man wieder auf 100 Fälle (100 Prozent).

Nach diesen Zahlen liegt also die Verbundwahrscheinlichkeit für die Ereignisse "Schnupfen" und "Husten", d.h. $P(S,H)$, bei 4 Prozent.

Hinweis: Die gezeigten Zahlen und Zusammenhänge sind fiktiv und dienen lediglich zur Verdeutlichung der Wahrscheinlichkeitsbegriffe!

Bedingte Wahrscheinlichkeit

Definition: Bedingte Wahrscheinlichkeit für $A$ gegeben $B$:

• $P(\text{Schnupfen } | \text{ Halsschmerzen}) = \frac{P(S,H)}{P(H)} = \frac{0.04}{0.04+0.01} = 0.8$
• $P(\text{Halsschmerzen } | \text{ Schnupfen}) = \frac{P(H,S)}{P(S)} = \frac{0.04}{0.04+0.06} = 0.4$

Wegen $P(A|B) = \dfrac{P(A,B)}{P(B)}$ ist $P(A,B) = P(A|B)P(B) = P(B|A)P(A)$ (Produkt-Regel)!

Marginalisierung

Allgemein: Seien $B_1, \ldots, B_n$ Elementarereignisse mit $\bigcup_i B_i = \Omega$. Dann ist $$P(A) = \sum_i P(A,B_i) = \sum_i P(A|B_i)P(B_i)$$

Diesen Vorgang nennt man Marginalisierung. Die resultierende Verteilung $P(A)$ nennt man auch "Randverteilung", da sie mit einer Projektion eines Quaders auf eine Seitenfläche vergleichbar ist.

Kettenregel

• Produktregel: Wegen $P(A|B) = \dfrac{P(A,B)}{P(B)}$ gilt $P(A,B) = P(A|B)P(B)$

• Verallgemeinerung (Kettenregel): $$ \begin{array}{rcl} P(A_1,A_2,\ldots,A_n) &=& P(A_n,\ldots,A_2,A_1)\\ & = & P(A_n|A_{n-1},\ldots,A_1)P(A_{n-1},\ldots,A_1)\\ & = & P(A_n|A_{n-1},\ldots,A_1)P(A_{n-1}|A_{n-2},\ldots,A_1)P(A_{n-2},\ldots,A_1)\\ & = & \ldots\\ & = & P(A_n|A_{n-1},\ldots,A_1) \ldots P(A_2|A_1)P(A_1)\\ & = & \prod_i P(A_i|A_1,\ldots,A_{i-1}) \end{array} $$

Bayes-Regel

Bedingte Wahrscheinlichkeit: $P(A,B) = P(A|B)P(B) = P(B|A)P(A)$

• $P(A)$ nennt man "Prior" oder "A-priori-Wahrscheinlichkeit" (Das ist die Wahrscheinlichkeit für $A$ ohne weiteres Wissen)
• $P(B|A)$ nennt man "Likelihood" (Wie wahrscheinlich ist das Auftreten von $B$, gegeben $A$?)
• $P(A|B)$ nennt man "Posterior" oder "A-posteriori-Wahrscheinlichkeit" (Wie wahrscheinlich ist $A$, wenn $B$ eingetreten ist?)
• $P(B)$ ist ein Normierungsfaktor

Wenn man (siehe später: Naive Bayes Klassifikator) $A$ als Klasse und $B$ als Daten betrachtet:

• $P(A)$: Wie wahrscheinlich ist eine bestimmte Klasse an sich (A-priori-Wahrscheinlichkeit der Klassen)?
• $P(B|A)$: Wie wahrscheinlich sind bestimmte Daten, gegeben die Klasse $A$? (Likelihood der Daten)
• $P(A|B)$: Gegeben die Daten $B$, wie wahrscheinlich ist die Klasse $A$? (Posterior)

In der Medizin hat sucht man i.d.R. die Ursache für beobachtete Symptome: $$ P(\text{Ursache}|\text{Symptome}) = \frac{P(\text{Symptome}|\text{Ursache})P(\text{Ursache})}{P(\text{Symptome})} $$

Aus der A-priori-Wahrscheinlichkeit für bestimmte Krankheiten und der Likelihood der Symptome (wie wahrscheinlich sind Symptome, gegeben eine Krankheit) kann man die Wahrscheinlichkeit für das Vorliegen einer Erkrankung gegeben bestimmte Symptome berechnen.

Beispiel Bayes

• Bei Arthrose wird in 80 Prozent der Fälle ein steifes Gelenk beobachtet
• Eine von 10.000 Personen hat Arthrose
• Eine von 10 Personen hat ein steifes Gelenk

=> Ich habe ein steifes Gelenk. Habe ich Arthrose?

• Gegeben: $P(A) = 0.0001, P(S) = 0.1, P(S|A) = 0.8$
• Gesucht: $P(A|S)$

Wenn ein steifes Gelenk vorliegt, ist die Wahrscheinlichkeit, dann an Arthrose erkrankt zu sein, bei nur 0.08%. Kein Grund zur Sorge in diesem Fall :-)

=> Wie wahrscheinlich ist ein steifes Gelenk ohne Arthrose, also $P(S|\neg A$)?

Mit Marginalisierung: $P(S) = P(S|A)P(A) + P(S|\neg A)P(\neg A)$, d.h. $0.1 = 0.8 \times 0.0001 + P(S|\neg A) \times (1-0.0001)$, d.h. $P(S|\neg A) = 0.0999$

In knapp 10 Prozent der Fälle würde man im obigen Beispiel bei der Diagnose "keine Arthrose" ein steifes Gelenk beobachten.

Hinweis: Die genannten Zahlen und Zusammenhänge sind rein fiktional und sollen lediglich zur Veranschaulichung der Bayes-Regel dienen!

Schauen Sie sich auch das Beispiel 7.9 in [Ertel2017, Ex. 7.9, S. 135] an!

Unabhängige Ereignisse

• $P(\text{Halsschmerzen},\text{ Regen}) = P(\text{Regen }|\text{ Halsschmerzen})P(\text{Halsschmerzen})$

• $P(\text{Regen }|\text{ Halsschmerzen}) = \text{ ?? }$ $= P(\text{Regen})$

• Zwei Ereignisse $A$ und $B$ sind unabhängig, wenn $$ P(A|B) = P(A) $$

  => $P(A,B) = P(A|B)P(B) = P(A)P(B)$

Dies kann man verallgemeinern (bedingte Unabhängigkeit):

$X$ und $Y$ sind bedingt unabhängig (gegeben $Z$), wenn $P(X|Y,Z) = P(X|Z)$ bzw. $P(Y|X,Z) = P(Y|Z)$

Daraus folgt:

Wrap-Up

• Grundlagen der Wahrscheinlichkeitstheorie
  • Elementarereignisse und Wahrscheinlichkeit
  • Rechenregeln
  • Bedingte Wahrscheinlichkeit und Verbundwahrscheinlichkeit
  • Marginalisierung
  • (Bedingte) Unabhängigkeit
  • Bayes'sche Regel

Klassifikation mit Naive Bayes

Medizinische Diagnostik mit NB

• Bei Arthrose wird in 80 Prozent der Fälle ein steifes Gelenk beobachtet: $P(S|A) = 0.8$
• Eine von 10.000 Personen hat Arthrose: $P(A) = 0.0001$
• Eine von 10 Personen hat ein steifes Gelenk: $P(S) = 0.1$

=> Ich habe ein steifes Gelenk. Habe ich Arthrose?

Textklassifikation mit NB

• Mails, manuell markiert:

  • D1: ("Sieben Zwerge fraßen sieben Ziegen", OK)
  • D2: ("Sieben Ziegen traten sieben Wölfe", SPAM)
  • D3: ("Sieben Wölfe fraßen sieben Böcke", OK)
  • D4: ("Sieben Böcke traten sieben Zwerge", SPAM)

• Neue Mails:

  • T1: ("Sieben Zwerge fraßen sieben Wölfe")
  • T2: ("Sieben Zwerge traten sieben Ziegen")

Lernen Sie mit Hilfe der Trainingsmenge einen Naive-Bayes-Klassifikator und wenden Sie diesen auf die beiden Test-Dokumente an.

Naive Bayes

• Verallgemeinerte Bayes Regel $$ P(H|D_1, \ldots, D_n) = \frac{P(D_1, \ldots, D_n | H)P(H)}{P(D_1, \ldots, D_n)} $$

• Annahme: $D_i$ sind bedingt unabhängig $$ P(D_1, \ldots, D_n | H) = P(D_1 | H) \cdot \ldots \cdot P(D_n | H) = \prod_i P(D_i | H) $$

• Beobachtung: $P(D_1, \ldots, D_n)$ für alle Hypothesen $h \in H$ gleich

• Naive Bayes Klassifikator bzw. MAP ("Maximum a Posteriori") $$ h_{MAP} = \operatorname{argmax}_{h \in H} P(h | D_1, \ldots, D_n) = \operatorname{argmax}_{h \in H} P(h) \prod_i P(D_i | h) $$

  Naive Bayes: Wähle die plausibelste Hypothese, die von den Daten unterstützt wird.

Bayes'sches Lernen

Training: Bestimme die Wahrscheinlichkeiten aus Trainingsdaten $\mathbf{S}$

• Für jede Klasse $h$:
  • Schätze $P(h) = \dfrac{|S(h)|}{|S|}$
  • Für jedes Attribut $D_i$ und jede Ausprägung $x \in D_i$: Schätze $P(D_i=x | h) = \dfrac{|S_{D_i}(x) \cap S(h)|}{|S(h)|}$

Klassifikation: Wähle wahrscheinlichste Klasse $h_{MAP}$ für Vektor $\mathbf{x}$

• $h_{MAP} = \operatorname{argmax}_{h \in H} P(h) \prod_{x \in \mathbf{x}} P(x | h)$

Beispiel Klassifikation mit NB

• Eingabe: Person mit Husten und Fieber

Gesucht: $P(\text{krank})$, $P(\text{gesund})$, $P(\text{Nase=0}|\text{krank})$, $P(\text{Nase=0}|\text{gesund})$, ...

Wähle Klasse $$ \begin{array}{rl} h_{MAP} = \operatorname{argmax}_{h \in \lbrace \text{gesund, krank} \rbrace} & P(h) \cdot P(\text{Nase=0}|h) \cdot P(\text{Husten=1}|h) \\ & \cdot P(\text{Haut=0}|h) \cdot P(\text{Fieber=1}|h) \end{array} $$

Ergebnis: (nur die für den zu klassifizierenden Beispiel-Vektor nötigen Werte, die restlichen müssten aber auch beim "Training" berechnet werden!)

P(gesund) = 2/5 = 0.4
P(krank)  = 3/5 = 0.6

P(Nase=0 | gesund) = 1/2 = 0.5
P(Nase=0 | krank)  = 1/3 = 0.333

P(Husten=1 | gesund) = 0/2 = 0
P(Husten=1 | krank)  = 2/3 = 0.667

P(Haut=0 | gesund) = 2/2 = 1
P(Haut=0 | krank)  = 1/3 = 0.333

P(Fieber=1 | gesund) = 0/2 = 0
P(Fieber=1 | krank)  = 1/3 = 0.333

h = gesund: P(gesund) * P(Nase=0 | gesund) * P(Husten=1 | gesund) * P(Haut=0 | gesund) * P(Fieber=1 | gesund) = 0.4*0.5*0*1*0              = 0
h = krank:  P(krank)  * P(Nase=0 | krank)  * P(Husten=1 | krank)  * P(Haut=0 | krank)  * P(Fieber=1 | krank)  = 0.6*0.333*0.667*0.33*0.333 = 0.015

=> Klasse "krank" gewinnt ...

Textklassifikation mit NB

• Texte als Trainingsmenge:

  • Text zerlegen in Terme (Wörter, sonstige relevante Token)
  • ggf. Entfernen von Stoppwörtern (beispielsweise Artikel u.ä.)
  • ggf. Stemming und Lemmatisierung für restliche Terme
  • ggf. weitere Vorverarbeitungsschritte (Groß-Klein-Schreibung, ...)
  • Terme zusammenfassen als Menge: "Bag of Words" (mit Häufigkeit)

• Naive Bayes "trainieren":

  • A-priori-Wahrscheinlichkeit der Klassen: $P(c) = \dfrac{N_c}{N} = \dfrac{\text{Anzahl Dokumente in Klasse c}}{\text{Anzahl Dokumente}}$

  • Likelihood der Daten (Terme):

    • $P(t|c) = \dfrac{\operatorname{count}(t,c)}{\sum_{v \in V} \operatorname{count}(v,c)}$ mit $\operatorname{count}(t,c)$ Anzahl der Vorkommen von Term $t$ in allen Dokumenten der Klasse $c$ und $V$ die Vereinigung aller Terme aller Dokumente (als Menge)

    • Variante mit Laplace-Glättung (s.u.): $P(t|c) = \dfrac{\operatorname{count}(t,c) + 1}{\sum_{v \in V} \operatorname{count}(v,c) + |V|}$

Naivität im Naive Bayes

• Unabhängigkeit der Attribute oft nicht gegeben

  => $P(D_1, \ldots, D_n | H) \ne \prod_i P(D_i | H)$

• A-posteriori-Wahrscheinlichkeiten oft unrealistisch nah an 1 oder 0

• Praxis: Dennoch häufig sehr gute Ergebnisse

  Wichtig: Solange die Maximierung über alle Hypothesen die selben Ergebnisse liefert, müssen die konkreten Schätzungen/Werte nicht exakt stimmen ...

Wenn Attribute nicht (bedingt) unabhängig sind, kann sich der NB verschätzen, d.h. es kommt dann u.U. zu einer höheren Fehlerrate, da bestimmte Eigenschaften in der Trainingsmenge zu hoch gewichtet werden.

Laplace-Schätzer

• Problem: Attribut-Ausprägung für bestimmte Klasse nicht in Trainingsmenge:

  • => Bedingte Wahrscheinlichkeit ist 0
  • => Produkt gleich 0

• Lösung: "Laplace-Schätzer" (auch "Laplace-Glättung")

  Statt $P(D_i=x | h) = \dfrac{|S_{D_i}(x) \cap S(h)|}{|S(h)|}$

  nutze $P(D_i=x|h) = \dfrac{|S_{D_i}(x) \cap S(h)| + m \cdot p_i}{|S(h)| + m}$

  • mit $m$: frei wählbarer Faktor, und

  • $p_i$: A-priori-Wahrscheinlichkeit für $P(D_i=x|h)$

    Hintergrundwissen oder einfach uniforme Verteilung der Attributwerte: $p_i = 1/|D_i|$ (Wahrscheinlichkeit für eine Attributausprägung ist 1/(Anzahl der Ausprägungen des Attributs))

  => "virtuelle" Trainingsbeispiele ($m$ ist die Zahl der virtuellen Trainingsbeispiele)

Probleme mit Floating Point Underflow

• MAP berechnet Produkt mit vielen Termen

• Problem: Bei kleinen Zahlen kann Floating Point Underflow auftreten!

• Lösung: Logarithmus maximieren (Produkt geht in Summe über)

  Erinnerung: $\log(x \cdot y) = \log(x) + \log(y)$ und Logarithmus streng monoton

  $$ \begin{array}{rcl} h_{MAP} &=& \operatorname{argmax}_{h \in H} P(h|D_1, \ldots, D_n) \\[5pt] &=& \operatorname{argmax}_{h \in H} P(h) \prod_i P(D_i | h) \\[5pt] &=& \operatorname{argmax}_{h \in H} [\log(P(h)) + \sum_i \log(P(D_i | h))] \end{array} $$

Maximum Likelihood

• Maximum a Posteriori $$ h_{MAP} = \operatorname{argmax}_{h \in H} P(h | D_1, \ldots, D_n) = \operatorname{argmax}_{h \in H} P(h) \prod_i P(D_i | h) $$

• Annahme: Klassen uniform verteilt => $P(h_i) = P(h_j)$

  Maximum Likelihood $$ h_{ML} = \operatorname{argmax}_{h \in H} \prod_i P(D_i | h) $$

  => Maximiere die Likelihood der Daten

Ausblick: Kontinuierliche Attribute

Bisher sind wir von diskreten Attributen ausgegangen. Bei kontinuierlichen Attributen hat man zwei Möglichkeiten:

• Diskretisierung der Attribute: Aufteilung in Intervalle und Bezeichnung der Intervalle mit einem Namen
• Einsatz einer Verteilungsannahme und deren Dichtefunktion, beispielsweise Annahme von normalverteilten Daten mit der Dichtefunktion $$ f(x) = \frac{1}{\sqrt{2 \pi \sigma}} e^{- \frac{(x - \mu)^2}{2 \sigma^2}} $$ wobei $\mu$ der Mittelwert und $\sigma^2$ die Varianz der Daten sind.

Hinweis zum Sprachgebrauch

In Abhängigkeit von der Verteilung der $P(D_i | h)$ spricht man von

• "multinominalem" NB: Attribute umfassen mehrere Kategorien (verschiedene Ausprägungen, wie im "Wahlkampf"-Beispiel: Attribut "Bildung" hat die Ausprägungen "Abitur", "Bachelor" und "Master")
• Bernoulli NB: Attribute sind binär (Ausprägung 0 oder 1), typischerweise bei der Textklassifikation
• Gauss'sches NB: Annahme einer Normalverteilung der Attribut-Ausprägungen

Wrap-Up

• Klassifikation mit Naive Bayes
  • Annahme von Unabhängigkeit => "Naive" Bayes Klassifikation
  • Schätzen der bedingten Wahrscheinlichkeiten aus den Trainingsdaten
  • Klassifikation durch Nutzung der geschätzten Wahrscheinlichkeiten
  • Hinweis auf Naivität der Annahme, dennoch sehr gute Erfolge in Praxis
  • Hinweis auf Probleme mit niedrigen Wahrscheinlichkeiten