Wahrscheinlichkeiten

Zwei Zufallsvariablen: "Sonne scheint" $S \in \{0,1\}$, "Regen" $R \in \{0,1\}$

Probabilistische Inferenz

Ausgangspunkt: Joint distribution (probabilistische Datenbank): $P(S,R,H,V)$

• Bedingt auf unserer Beobachtung: $H=1, V=1$
• Interessiert an Frage: $R$

Aufgaben

• Modellierung:

  Wie spezifizieren wir die joint distribution $P(X_1, \ldots, X_n)$?

• Inferenz:

  Wie berechnen wir Query $P(X_i, X_j, \ldots | X_k = x_k, X_l = x_l, \ldots)$ effizient?

Erdbeben und Einbrüche sind unabhängige Ereignisse, die unsere Alarmanlage auslösen können.
Wir werden vom Alarm geweckt. Dann merken wir, dass auch die Erde bebt. Wie ändert das unsere Einschätzung, dass gerade ein Einbruch passiert?

1. Ein Einbruch ist wahrscheinlicher
2. Ein Einbruch ist unwahrscheinlicher
3. Ein Einbruch ist gleich wahrscheinlich

Bayesian network

$P(B=b, E=e, A=a) = {\color{blue} p(b)}{\color{green} p(e)}{\color{red} p(a | b,e)}$

$b$ $p(b)$ $0$ $0.98$ $1$ $0.02$ $e$ $p(e)$ $0$ $0.95$ $1$ $0.05$

$b$ $e$ $a$ $p(a | b,e)$ $0$ $0$ $0$ $1$ $0$ $0$ $1$ $0$ $0$ $1$ $0$ $0$ $0$ $1$ $1$ $1$ $1$ $0$ $0$ $0$ $1$ $0$ $1$ $1$ $1$ $1$ $0$ $0$ $1$ $1$ $1$ $1$

$P(B=b, E=e, A=a) = {\color{blue} p(b)}{\color{green} p(e)}{\color{red} p(a | b,e)}$

Darstellung als Factor Graph

Jeder Knoten hat einen eigenen Factor (der alle Eltern verbindet).

Queries

• $P(B=1)$ $= 0.019 + 0.001 = 0.02$
• $P(B=1 | A=1)$ $= \frac{0.019 + 0.001}{0.019 + 0.001 + 0.049} = 0.29$
• $P(B=1 | A=1, E=1)$ $= \frac{0.001}{0.001 + 0.049} = 0.02$

In kleinen Beispielen lassen sich die Queries noch explizit berechnen.

Anzahl Zeilen in joint distribution ist exponentiell mit Anzahl Variablen.

Bedingung: Lokal normalisiert

Teilgraph eines Bayesian network ist ein Bayesian network

Marginalisieren eines Blattes entspricht Netzwerk ohne Blatt.

$\Rightarrow$

Lokale conditional distribution ist wahre conditional distribution

$P(A=a | E=e, B=b) = p(a|e,b)$

(wir dürfen die lokalen conditional distributions verwenden, wenn die Query passt)

• Zufallsvariablen modellieren den Zustand der Welt
• Kanten sind Abhängigkeiten
• Spezifiziere lokale conditional distributions
• Probabilistische Inferenz: Frage nach dem Zustand der Welt bei bestimmten Beobachtungen

Andere Sichtweise: Probabilistic programs

Beispiel: Random walk

$\alpha = 0.5$

CS221 by Liang & Sadigh

$\alpha = 0.8$

CS221 by Liang & Sadigh

$\alpha = 0.1$

CS221 by Liang & Sadigh

$\alpha = 0.5$, $X_{10} = (8,2)$

CS221 by Liang & Sadigh

Anwendung: Natural Language Processing

Jedes Wort hängt von seinem Vorgänger ab:
$X_i \sim p(X_i | X_{i-1})$

(Markov model)

Object Tracking

Zu jedem Zeitpunkt $t = 1, \ldots, T$:

• Befindet sich das Objekt an Position $H_t \sim p(H_t | H_{t-1})$
• Erhalten wir Sensordaten $E_t \sim p(E_t | H_t)$

Inferenz: Wir kennen die Sensordaten und wollen die Objekt Position wissen.

(Hidden Markov Model - HMM)

Multiple Object Tracking

Zu jedem Zeitpunkt $t = 1, \ldots, T$:

• Befindet sich das Objekt $a$ an Position $H_t^a \sim p(H_t^a | H^a_{t-1})$
• Befindet sich das Objekt $b$ an Position $H_t^b \sim p(H_t^b | H^b_{t-1})$
• Erhalten wir Sensordaten $E_t \sim p(E_t | H_t^a, H_t^b)$

(factorial HMM)

Dokument Klassifikation

• Jedes Dokument erhält ein Label $Y \sim p(Y)$
• Für jedes Position im Dokument $i = 1, \ldots, L$:
  • Generiere Wort $W_i \sim p(W_i | Y)$

(naive Bayes)

Topic Modeling

• Wähle je Thema eine Wahrscheinlichkeit $\alpha \in \mathbb{R}^K$
• Für jedes Position im Dokument $i = 1, \ldots, L$:
  • Wähle ein Thema $Z_i \sim p(Z_i | \alpha)$
  • Wähle ein Wort $W_i \sim p(W_i | Z_i)$

Inferenz: welche Themen kommen in einem Dokument vor.

(latent Dirichlet allocation)

Medizinische Diagnose

• Für jede Krankheit $i=1,\ldots, m$:
  • Entscheide ob Krankheit vorliegt $D_i \sim p(D_i)$
• Für jedes Symptom $j=1,\ldots, n$:
  • Entscheide ob sich Symptom äußert
    $S_j \sim p(S_j | D_1,\ldots,D_m)$

Inferenz: Gegeben die beobachteten Symptome, welche Krankheiten sind wie wahrscheinlich?

Es ist oft einfacher ein Modell anfangend bei den versteckten Ursachen, hin zu den Beobachtungen zu erstellen.

Bayes Net ist eine Art probabilistische Datenbank mit unserem Wissen über die Welt, die wir querien.

Wie machen wir probabilistic inference?

1. Schritt: Graph vereinfachen.

Query: $P(Q | E=e)$

• Entferne (marginalize) alle Variablen, die keine Vorfahren von $Q$ oder $E$ sind.
• Konvertiere in einen Factor Graphen
• Fixiere $E=e$
• Entferne alle Knoten die nicht mehr mit $Q$ verbunden sind.

Marginalizing out

Marginalizing out

Marginalizing out

Factor Graph

$\Rightarrow$

Ein factor je Knoten

Variablen fixieren

Query: $P(H | E=1)$

	$\Rightarrow$
$H$ $E$ $p$ $0$ $0$ $p_{0,0}$ $0$ $1$ $p_{0,1}$ $1$ $0$ $p_{1,0}$ $1$ $1$ $p_{1,1}$		$H$ $p$ $0$ $p_{0,1}$ $1$ $p_{1,1}$

Query: $P(H | E)$

Query: $P(C,H | E)$

Wie berechnen wir nun die Wahrscheinlichkeiten auf dem reduzierten Graph?

• Spezialfall: Hidden Markov Model
  • Forward-backward Algorithmus
  • Particle filtering
• Allgemein: Gibbs sampling

Hidden Markov Model

Beispiel: Object Tracking

• $H_i \in \{1, \ldots, K \}$ : Ort zum Zeitpunkt $i$
• $E_i \in \{1, \ldots, K \}$ : gemessener Ort zum Zeitpunkt $i$
• Start $p(H_1)$ : z.B. Uniform über alle Orte
• Transition $p(h_i | h_{i-1})$ : z.B. Uniform über benachbarte Orte
• Emission $p(e_i | h_i)$ : z.B. Normalverteilt über benachbarte Orte

$P(H=h, E=e) = p(h_1) \prod_{i=2}^n p(h_i | h_{i-1}) \prod_{i=1}^n p(e_i | h_i)$

Typische Queries

Filtering:
$P(H_3 | E_1 = e_1, E_2 = e_2, E_3 = e_3)$

Smoothing:
$P(H_3 | E_1 = e_1, E_2 = e_2, E_3 = e_3, E_4 = e_4)$

Gitter Modell

• Kante "$\text{start} \Rightarrow H_1=h_1$" hat Gewicht $p(h_1)p(e_1 | h_1)$
• Kante "$H_{i-1} = h_{i-1} \Rightarrow H_i = h_i$" hat Gewicht $p(h_i | h_{i-1}) p(e_i | h_i)$
• Jeder Pfad von "start" nach "ende" ist ein mögliches Assignment mit Wahrscheinlichkeit (Gewicht) gleich dem Produkt der Kantengewichte

• Vorwärts: $F_i(h_i) = \sum_{h_{i-1} = 1}^K F_{i-1}(h_{i-1}) w_i(h_{i-1}, h_i)$
  Alle Gewichte von "start" bis "$H_i=h_i$"
• Rückwärts: $B_i(h_i) = \sum_{h_{i+1} = 1}^K B_{i+1}(h_{i+1}) w_{i+1}(h_i, h_{i+1})$
  Alle Gewichte von "$H_i=h_i$" bis "ende"
• $S_i(h_i) = F_i(h_i) B_i(h_i)$
  Alle Gewichte von "start" bis "ende" durch "$H_i=h_i$"

\[ P(H_i = h_i | E=e) = \frac{S_i(h_i)}{\sum_{h' = 1}^K S_i(h')} \]

($S$ sind die noch nicht normalisierten Wahrscheinlichkeiten)

Rechenzeit: $O(nK^2)$

Mit vielen möglichen Werten (großes $K$) wird Forward-Backward ineffizient.

Idee: Versuche korrektes Ergebnis zu approximieren

Particle Filter

Erweiterung von Beam-Search

Geeignet für Filter Queries:
$P(H_i | E_1=e_1, \ldots, E_i = e_i)$

Beam Search

Particle Filter

3 Schritte:

• Propose
• Weight
• Resample

Propose

Zum Zeitpunkt $i$ haben wir $K$ Partikel, aus der Verteilung $P(H_1, \ldots, H_i | E_1 = e_1, \ldots, E_i = e_i)$

Beispiel (Object Tracking):
Beobachtung $e_1 = 0, e_2 = 1$.

Partikel: $[0, 1], [1, 0]$

Für jeden Partikel samplen wir ein
$H_{i+1} \sim p(h_{i+1} | h_i)$.

Verteilung von neuen Partikeln ist
$P(H_1, \ldots, H_i, {\color{red} H_{i+1}} | E_1 = e_1, \ldots, E_i = e_i)$

Beispiel:
$[0,1] \to [0,1,{\color{red} 1}]$
$[1,0] \to [1,0,{\color{red} 0}]$

$K=8$

Weight

Jeder Partikel erhält Gewicht
$w(h_1, h_2, h_3) = p(e_3 | h_3)$

Idee: Wie Wahrscheinlich ist es, dass der Partikel an $h_3$ ist, wenn wir $e_3$ beobachten.

Beispiel (Object Tracking):
Beobachtung $e_1 = 0, e_2 = 1, e_3 = 1$.

$w([0,1,1]) = 0.8$
$w([1,0,0]) = 0.4$

Resample

Wir wählen $K$ Partikel aus.
Wahrscheinlichkeit für Partikel $q$ ist $\frac{w_q}{\sum_{q'} w_{q'}}$

Ziehen mit Zurücklegen: Ein Partikel kann $0,1,2,\ldots$ mal gezogen werden.

$K=10000$

CS221 by Liang & Sadigh

Vorteil gegenüber Beam Search: Potentiell diversere Menge an Lösungen.

Gibbs sampling

Wie machen wir probabilistic inference auf beliebigen Bayes Netzen?

Beobachtung: Gibbs sampling hält sich länger dort auf, wo die Wahrscheinlichkeit höher ist.

Zähle, wie oft jedes Assignment vorkommt $\Rightarrow$ gesuchte Wahrscheinlichkeitsverteilung

Theorem: Gibbs sampling konvergiert zur richtigen Verteilung (unter bestimmten Voraussetzungen). Aber: Das kann sehr lange dauern.

Beispiel: Object Tracking

Jupyter

Anwendung: Image denoising

• $X_i$: Pixel Wert an Position $i$
• Benachbarte Pixel sind eher gleich als unterschiedlich

CS221 by Liang & Sadigh

Probabilistic inference

Woher wissen wir die Wahrscheinlichkeiten?

$P(B=b, E=e, A=a) = {\color{blue} p(b)}{\color{green} p(e)}{\color{red} p(a | b,e)}$

$b$ $p(b)$ $0$ ? $1$ ? $e$ $p(e)$ $0$ ? $1$ ?

$b$ $e$ $a$ $p(a | b,e)$ $0$ $0$ $0$ ? $0$ $0$ $1$ ? $0$ $1$ $0$ ? $0$ $1$ $1$ ? $1$ $0$ $0$ ? $1$ $0$ $1$ ? $1$ $1$ $0$ ? $1$ $1$ $1$ ?

Trainingsdaten $\mathcal{D}_\text{train}$: Jedes Beispiel ist ein Assignment aller Variablen $X$

Parameter $\theta$: Lokale bedingte Wahrscheinlichkeiten

Was ist aufwendiger von der Rechenzeit?

• Probabilistic inference
• Parameter lernen (mit vollständigen Daten)

Einfachstes aller Bayesian networks
R ist ein Rating $\{1,2,3,4,5\}$ $P(R=r) = p(r)$

• Parameter: $\theta = (p(1), p(2), p(3), p(4), p(5))$
• Daten: $\mathcal{D}_\text{train} = \{1,3,4,4,4,4,4,5,5,5\}$

Intuition:
$p(r)$ proportional zu "Wie oft kommt $r$ in $\mathcal{D}_\text{train}$ vor."

Beispiel: $\mathcal{D}_\text{train} = \{1,3,4,4,4,4,4,5,5,5\}$

Zählen + normalisieren

$p(r) = \frac{\operatorname{anzahl}(r)}{|\mathcal{D}_\text{train}|}$

Zwei Variablen

• Genre $G \in \{\text{drama}, \text{comedy}\}$
• Rating $R \in \{1,2,3,4,5\}$

$P(G=g, R=r) = p_G(g) p_R(r|g)$

• $\mathcal{D}_\text{train} = \{(d,4), (d,4), (d,5), (c,1), (c,5)\}$
• $\theta = (p_G, p_R)$

	$P(G=g, R=r) = p_G(g) p_R(r|g)$
$\mathcal{D}_\text{train} = \{(d,4), (d,4), (d,5), (c,1), (c,5)\}$

Strategie: Schätze jede lokale Verteilung separat ab

Drei Variablen

• Genre $G \in \{\text{drama}, \text{comedy}\}$
• Award $A \in \{0, 1\}$
• Rating $R \in \{1,2,3,4,5\}$

$P(G=g, A=a, R=r) = p_G(g) p_A(a) p_R(r|g, a)$

$\mathcal{D}_\text{train} = \{(d,0,3), (d,1,5), (d,0,1), (c,0,5), (c,1,4)\}$

Drei Variablen - Variante 2

• Genre $G \in \{\text{drama}, \text{comedy}\}$
• Rating von Jim $R_1 \in \{1,2,3,4,5\}$
• Rating von Martha $R_2 \in \{1,2,3,4,5\}$

$P(G=g, R_1=r_1, R_2=r_2)= p_G(g) p_{R_1}(r_1 | g) p_{R_2}(r_2 | g)$

$\mathcal{D}_\text{train} = \{(d,4,5), (d,4,4), (d,5,3), (c,1,2), (c,5,4)\}$

Parameter $\theta = (p_G, p_{R_1}, p_{R_2})$

$\mathcal{D}_\text{train} = \{(d,4,5), (d,4,4), (d,5,3), (c,1,2), (c,5,4)\}$

Parameter $\theta = (p_G, p_R)$

Geteilte Parameter

Idee: Die lokalen Verteilungen von verschiedenen Variablen verwenden die gleichen Parameter

• Parameter lassen sich schneller lernen mit weniger Daten
• Modell kann weniger Unterschiede abbilden

Beispiel: Naive Bayes

• Kategorie $Y \in \{\text{kein Spam}, \text{Spam}\}$
• Worte $W_i, \ldots, W_L$

\[P(Y=y, W_1=w_1, \ldots, W_L=w_l) = p_Y(y) \prod_{i=1}^L p_W(w_i | y)\]

Parameter: $\theta=(p_Y, p_W)$

Beispiel: HMMs

• $H_1, \ldots, H_n$: Objekt Positionen
• $E_1, \ldots, E_n$: Sensor Messdaten

\[ P(H=h, E=e) = p_\text{start}(h_1) \prod_{i=2}^n p_\text{trans}(h_i | h_{i-1}) p_\text{emit}(e_i | h_i) \]

Parameter: $\theta=(p_\text{start}, p_\text{trans}, p_\text{emit})$

Ganz allgemein

• Bayesian network: Variablen $X_1, \ldots, X_n$
• Parameter: Verteilungen $\theta = \{p_d : d \in D\}$
• Jede Variable $X_i$ hat eine Verteilung $p_{d_i}$: \[ P(X_1 = x_1, \ldots, X_n = x_n) = \prod_{i=1}^n p_{\color{red} d_i} (x_i | x_{\text{Parents}(i)}) \]
• Geteilte Parameter: $d_i$ kann für mehre $i$ gleich sein.

Maximum Likelihood

\[ \max_\theta \prod_{x \in \mathcal{D}_\text{train}} P(X = x; \theta) \]

Suche Parameter, so dass die Beobachtung der Trainingsbeispiele am wahrscheinlichsten ist.

Ich werfe eine Münze 1000 mal und beobachte 700 mal Kopf und 300 mal Zahl.

Unter welche Annahme ist dieses Ergebnis wahrscheinlicher?

• Kopf kommt mit $50\%$ Wahrscheinlichkeit
• Kopf kommt mit $70\%$ Wahrscheinlichkeit

Zählen und normalisieren berechnet genau die Maximum Likelihood Lösung.

Ich werfe eine Münze einmal und bekomme "Kopf".
Was schätzen wir für die Wahrscheinlichkeit $p(K)$?

Maximum Likelihood: \[ p(K) = 1 \quad p(Z) = 0 \]

Solange wir wenige Daten haben, führt Maximum Likelihood zu Overfitting

Laplace Smoothing

Idee: Tue so, als hätten wir jedes mögliche Ereignis schon einmal beobachtet.

Beispiel: Münzwurf, 1x Kopf geworfen

Maximum Likelihood

Maximum Likelihood mit Laplace Smoothing

Allgemeiner: Wir addieren ${\color{red} \lambda} \geq 0$ zu jedem $\text{count}_d(x_{\text{Parents}(i)}, x_i)$ hinzu.

Größeres $\lambda$: Verteilung bleibt länger nahe bei Gleichverteilung

Genug Daten überwiegen am Ende immer

Ein Experiment: \[ p(K) = \frac{1{\color{red}+1}}{1{\color{red}+2}} = \frac{2}{3} \quad p(Z) = \frac{\color{red}1}{1{\color{red}+2}} = \frac{1}{3} \]

998 Experimente: \[ p(K) = \frac{998{\color{red}+1}}{998{\color{red}+2}} = 0.999 \quad p(Z) = \frac{\color{red}1}{998{\color{red}+2}} = 0.001 \]

Was machen wir, wenn wir manche Variablen nicht beobachten (können)?

$\mathcal{D}_\text{train} = \{ ({\color{red}?}, 4,5), ({\color{red}?}, 4,4), ({\color{red}?}, 5, 3), ({\color{red}?}, 1,2)\}$

Wir haben 2 Typen von Variablen: $H$ ist hidden und $E=e$ ist beobachtet (Evidenz)

Beispiel

\[ H = G, \quad E= (R_1, R_2), \quad e = (1,2),\\ \theta = (p_G, p_R) \]

Expectation Maximization konvergiert zu einem lokalen Optimum

Andere Start Verteilung $\theta$ kann zu anderem Ergebnis führen.

Beispiel

Genres $\{c, d\}$ und Ratings $\{1,2\}$

$\mathcal{D}_\text{train} = \{ (?, 2,2), (?, 1,2) \}$

Start Parameter

Sinnvoller Start: Nah an, aber ungleich Gleichverteilung.

E-Step

$\mathcal{D}_\text{train} = \{ (?, 2,2), (?, 1,2) \}$

M-Step

Ergebnis 1. Iteration:

$\mathcal{D}_\text{train} = \{ (?, 2,2), (?, 1,2) \}$

Zielfunktion (Start)

$\mathcal{D}_\text{train} = \{ (?, 2,2), (?, 1,2) \}$

\[ \begin{align*} P(\mathcal{D}_\text{train}) = &(0.55 \cdot 0.6 \cdot 0.6 + 0.45 \cdot 0.35 \cdot 0.35) \\ &\cdot (0.55 \cdot 0.4 \cdot 0.6 + 0.45 \cdot 0.65 \cdot 0.35) \\ =& (0.198 + 0.055) \cdot (0.132 + 0.102) \\ =& 0.059 \end{align*} \]

Zielfunktion (1. Iteration)

$\mathcal{D}_\text{train} = \{ (?, 2,2), (?, 1,2) \}$

\[ \begin{align*} P(\mathcal{D}_\text{train}) = &(0.674 \cdot 0.791 \cdot 0.791 + 0.326 \cdot 0.666 \cdot 0.666) \\ &\cdot (0.674 \cdot 0.209 \cdot 0.791 + 0.326 \cdot 0.334 \cdot 0.666) \\ =& (0.422 + 0.145) \cdot (0.111 + 0.073) \\ =& 0.104 \end{align*} \]

Wichtig: Wenn wir zu wenig Variablen beobachten, können wir nichts sinnvolles lernen.

Anwendung: Entschlüsselung

Copiale cipher: 75000 Zeichen; 2011 mit EM entschlüsselt

https://commons.wikimedia.org/wiki/File:Copiale-cipher09s.png

Monoalphabetische Substitution

Jedes Zeichen wird durch ein neues ersetzt

"hallo welt" $\Rightarrow$ "AUCCQ ZWCE"

Entschlüsselung als HMM

• $H_1, \ldots, H_n$: Zeichen des Klartext
• $E_1, \ldots, E_n$: Zeichen des Geheimtexts

Parameter: $\theta = (p_\text{start}, p_\text{trans}, p_\text{emit})$

\[ P(H=h, E=e) = p_\text{start}(h_1) \prod_{i =2}^n p_\text{trans} (h_i | h_{i-1}) \prod_{i=1}^n p_\text{emit}(e_i | h_i) \]

Wir hoffen, dass $p_\text{emit}$ am Ende unsere Substitutionstabelle ist.

Um eine Chance auf sinnvolle Ergebnisse zu haben brauchen wir gute Startverteilungen

• $p_\text{emit}$: Uniform (wollen wir durch EM schätzen)
• $p_\text{start}$: Uniform
• $p_\text{trans}$: Geschätzt aus beliebigen anderen Texten

Zusammenfassung

• Maximum Likelihood lernt Parameter aus vollständigen Daten
• Laplace Smoothing verhindert Overfitting
• Expectation Maximization lernt Parameter aus unvollständigen Daten
  • Wiederhole: Inference für fehlende Parameter + Maximum Likelihood