teilweise von Koller, Daphne, and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT press, 2009.

Bayessche Netze - Repräsentation¶

Bayessche Netze sind gerichtete graphische Modelle (directed graphical models).
Diagramme von bedingten Unabhängigkeiten (Conditional independence diagrams).

Eine explizite Repräsentation von multivariaten Wahrscheinlichkeitsverteilungen vieler Zufallsvariablen ist nicht handhabbar:

in der Praxis nicht berechenbar:
- sehr aufwändig zu manipulieren
- im Allgemeinen zu groß, um im Computer-Speicher gehalten zu werden.
aus kognitiven Gründen:
- es ist unmöglich so viele Zahlen von (menschlichen) Experten zu erhalten.
- sehr kleine Zahlen sind schwierig für Menschen zu interpretieren.
aus statistischen Gründen:
- Lernen von Verteilungen aus Daten erfordert riesige Datenmengen (unmöglicher Größe), um alle Parameter zuverlässig zu berechnen.

Nutzen von bedingten Unabhängigkeiten¶

Bedingte Unabhängigkeiten zwischen Variablen können genutzt werden, um multivariate Wahrscheinlichkeitsverteilungen kompakter zu repräsentieren:

Mittels der Datenstruktur "gerichteter azyklischer Graph" (DAG)
DAG drückt die Faktorisierung der Wahrscheinlichkeitsverteilung aus.

Beispiel n-binäre Variaben¶

$n$-Variablen $X_i$ mit $\text{Val}(X_i)=\{0,1\}$

für die allgemeine Wahrscheinlichkeitsverteilung brauchen wir $2^n-1$ unabhängige Parameter, um die Verteilung zu spezifizieren.
wenn die Variablen (marginal) unabhängig sind, benötigen wir nur $n$ unabhängige Parameter.

conditional parametrization¶

Zwei Zufallsvariablen:

$I$: Intelligenz
$S$: SAT-Score (Studierfähigkeitstest)

$Val(I) = \{i^0, i^1\}$

hohe Intelligenz $i^1$
normale Intelligenz $i^0$

$Val(S)= \{s^0, s^1\}$

hoher Score $s^1$
niedriger Score $s^0$

mögliche multivariate Verteilung:

$I$	$S$	$P(I,S)$
$i^0$	$s^0$	0.665 $\hspace{0.15cm}$
$i^0$	$s^1$	0.035 $\hspace{0.15cm}$
$i^1$	$s^0$	0.06 $\hspace{0.15cm}$
$i^1$	$s^1$	0.24 $\hspace{0.15cm}$

Multinomial Verteilung (vier mögliche Ergebnisse) mit insgesamt drei unabhängigen Parametern.

Alternative Repräsentation¶

$$ P(I,S) = P(I)P(S \mid I) $$

Priori Verteilung über $I$: $P(I)$

$i^0$	$i^1$
0.7	0.3

Bedingte Wahrscheinlichkeitsverteilung $P(S \mid I)$:

$I$		$s^0$	$s^1$
$i^0$		0.95	0.05
$i^1$		0.2	0.8

Zusammen sind dies drei binomial Verteilungen:

$P(I)$
$P(S \mid I=i^0)$
$P(S \mid I=i^1)$ mit insgesamt drei unabhängigen Parametern

weitere Zufallsvariable¶

Note des Studierenden $G$ (grade)

$Val(G) = \{g^1, g^2, g^3\}$

keine (marginale) Unabhängigkeit zwischen $G,S,I$ sollte gelten, z.B.:

$$ P(g^1 \mid s^1) > P(g^1 \mid s^0) $$

aber bedingte Unabhängigkeit

$$ P(G \mid i^1, s^1) = P(G \mid i^1) $$

im Allgemeinen $$ P \models (S \perp G \mid I) $$

Dies Annahme gilt, wenn die Intelligenz der einzige Grund ist, weshalb der SAT-Score und die Note des Studierenden korreliert sind.

Diese bedinge Unabhängigkeit erlaubt es uns, eine kompakte Spezifikation der multivariaten Wahrscheinlichkeitsverteilung zu geben:

mit der Kettenregel

$$ P(I,S,G) = P(S,G\mid I)P(I) $$

und der bedingten Unabhängigkeit:

$$ P(S,G\mid I) = P(S\mid I) P(G\mid I) $$

gilt

$$ P(I,S,G) = P(S\mid I) P(G\mid I) P(I) $$

Die multivariate Wahrscheinlichkeitsverteilung faktorisiert als ein Produkt dreier bedingter Verteilungen (conditional probability distributions) (CPDs).

Priori Verteilung über $I$: $P(I)$

$i^0$	$i^1$
0.7	0.3

Bedingte Wahrscheinlichkeitsverteilung $P(S \mid I)$:

$I$		$s^0$	$s^1$
$i^0$		0.95	0.05
$i^1$		0.2	0.8

Bedingte Wahrscheinlichkeitsverteilung $P(G \mid I)$:

$I$		$g^1$	$g^2$	$g^3$
$i^0$		0.2	0.34	0.46
$i^1$		0.74	0.17	0.09

z.B.: $P(i^1, s^1, g^2) = P(i^1)P(s^1\mid i^1)P(g^2 \mid i^1) = 0.3 \cdot 0.8 \cdot 0.17 = 0.00408$

In [1]:

from matplotlib import rc
rc("font", family="serif", size=16)
rc("text", usetex=True)

In [2]:

%matplotlib inline

from IPython.core.pylabtools import figsize
from matplotlib import pyplot as plt

In [3]:

import daft
pgm = daft.PGM([4.3, 2.05], origin=[-1., -0.3], aspect=1.)
pgm.add_node(daft.Node("G", r"G", 0.5, 0.))
pgm.add_node(daft.Node("I", r"I", 1.5, 1.))
pgm.add_node(daft.Node("S", r"S", 2.5, 0.))
pgm.add_edge("I", "S")
pgm.add_edge("I", "G")
pgm.render()

Out[3]:

<matplotlib.axes._axes.Axes at 0x10f8a22b0>

Die alternative Formulierung ist kompakter:

Die binomiale Verteilungen $P(I)P(S\mid i^0)P(S \mid i^1)$ mit jeweils einem freien Parameter und
zwei dreiwertige Multinomialverteilungen $P(G \mid i^1)P(G\mid i^0)$ mit jeweils zwei freien Parameter. So ergeben sich für die kompakte Repräsentation insgesamt nur $3+4=7$ Parameter.

Im Gegensatz zur allg. multivariaten Wahrscheinlichkeitsverteilung $P(I,S,G)$ die $2 \cdot 2 \cdot 3 - 1 = 11$ Parameter enthält.

Ein weiterer Vorteil ist die Modularität der Repräsentation: Beim Hinzufügen der Zufallsvariablen $G$ ändern sich die vorhandenen CPDs bzw. conditional probability tables (CPT) nicht. Die CPTs von $I$ und $S$ können wiederverwendet werden (local property models).

Beispiel: Naive Bayes¶

In [6]:

def plot_native_bayes():
    pgm = daft.PGM([8.3, 2.05], origin=[-1., -0.3], aspect=1.)
    pgm.add_node(daft.Node("X_1", r"$X_1$", 0., 0., observed=True))
    pgm.add_node(daft.Node("X_2", r"$X_2$", 1., 0., observed=True))
    pgm.add_node(daft.Node("X_3", r"$X_3$", 2., 0., observed=True))
    pgm.add_node(daft.Node("X_4", r"$X_4$", 3., 0., observed=True))
    pgm.add_node(daft.Node("C", r"C", 2., 1.))
    pgm.add_node(daft.Node("X_n", r"$X_{n=5}$", 4., 0., observed=True))
    pgm.add_edge("C", "X_1")
    pgm.add_edge("C", "X_2")
    pgm.add_edge("C", "X_3")
    pgm.add_edge("C", "X_4")
    pgm.add_edge("C", "X_n")
    pgm.render()

$C$: gegenseitig exklusive Klassen
$X_i$: $n$ Merkmale (features)

Bedingte Unabhängigkeit $(X_i \perp X_j \mid C)$ mit $i\neq j$ für alle $i,j$

daraus folgt, dass das Modell folgendermaßen faktorisiert:

$$ P(C, X_1, \dots, X_n) = P(C) \prod_{i=1}^n P(X_i \mid C) $$

Beachte: Die Anzahl der freien Parameter des Modells wächst (nur) linear mit der Anzahl der Variablen $X_i$.

In [7]:

plot_native_bayes()

Bayessche Netze¶

Direkte azyklische Graphen (DAG) $\mathcal G$:

Knoten (nodes) sind Zufallsvariable
Kanten (edges) korrespondieren (intuitiv) zu direkten Einflussen zwischen Zufallsvariablen, d.h. $P(X_i \mid Par(X_i))$

Kettenregel für Bayessche Netze: $P$ faktorisiert über $\mathcal G$ ("P respektiert $\mathcal G$"), wenn $$ P(X_1, X_2, \dots X_n) = \prod_{i=1}^{n} P(X_i \mid Par(X_i)) $$

$\mathcal G$ kann auf zwei Weisen betrachtet werden:

als eine Datenstruktur, die das Gerüst (skeleton) für eine kompakte Repräsentation der multivariaten Wahrscheinlichkeitsverteilung bildet. Die Wahrscheinlichkeit faktorisiert gemäß $\mathcal G$.
als eine kompakte Repräsentation für ein Menge von bedingten Unäbhängigkeitsannahmen für eine Verteilung.

Beispiel: Ausführliches Studenten Netz¶

In [8]:

def plot_student_network():
    pgm = daft.PGM([5.1, 3.5], origin=[-1., .3], aspect=1.)
    pgm.add_node(daft.Node("I", r"I", 2.5, 3.))
    pgm.add_node(daft.Node("D", r"D", 0.5, 3.))
    pgm.add_node(daft.Node("G", r"G", 1.5, 2.))
    pgm.add_node(daft.Node("S", r"S", 3.5, 2.))
    pgm.add_node(daft.Node("L", r"L", 1.5, 0.8))
    pgm.add_edge("I", "S")
    pgm.add_edge("I", "G")
    pgm.add_edge("D", "G")
    pgm.add_edge("G", "L")        
    pgm.render()

In [9]:

plot_student_network()

Local Property Models: CPDs¶

Priori Verteilung über $I$: $P(I)$

$i^0$	$i^1$
0.7	0.3

Priori Verteilung über $D$: $P(D)$

$d^0$	$d^1$
0.6	0.4

Bedingte Wahrscheinlichkeitsverteilung $P(S \mid I)$:

$I$		$s^0$	$s^1$
$i^0$		0.95	0.05
$i^1$		0.2	0.8

Bedingte Wahrscheinlichkeitsverteilung $P(S \mid I)$:

$\hspace{1.4cm}$	$g^1$	$g^2$	$g^3$
$i^0, d^0$	0.3	0.4	0.3
$i^0, d^1$	0.05	0.25	0.7
$i^1, d^0$	0.9	0.08	0.02
$i^1, d^1$	0.5	0.3	0.2

Bedingte Wahrscheinlichkeitsverteilung $P(L \mid G)$:

$G$	$l^0$	$l^1$
$g^1$	0.1	0.9
$g^2$	0.4	0.6
$g^2$	0.99	0.01

Reasoning Pattern¶

Causal reasoning $\downarrow$: z.B. $P(l^1 \mid i^0) \approx 0.388$
Evidential reasoning, explaination $\uparrow$: z.B. $P(i^1 \mid g^3) \approx 0.079$
Intercausal reasoning $\rightarrow$ or $\leftarrow$: z.B. $P(i^1 \mid g^3, d^1)\approx 0.11$

Übung¶

Bauen Sie das Studentennetz (inkl. CPTs) in Samiam auf.
Probieren Sie verschiedene Wahrscheinlichkeitsfragen aus (für alle drei Reasoning Pattern).

Aktive Pfade (active trails)¶

Ohne Beobachtung¶

Ein Pfad $X_1 \rightarrow X_2 \rightarrow \dots \rightarrow X_k$ bzw. $X_1 \leftarrow X_2 \leftarrow \dots \leftarrow X_k$ zwischen unbeobachteten Zufallsvariablen ist aktiv, wenn er keine V-Struktur besitzt.
Man sagt: Eine V-Struktur $X_{i-1} \rightarrow X_i \leftarrow X_{x+1}$ blockiert den Pfad.

allgemeine Fall¶

Ein Pfad $X_1 - X_2 - \dots - X_k$ zwischen Zufallsvariablen ist aktiv, wenn

für jede V-Struktur $X_{i-1} \rightarrow X_i \leftarrow X_{x+1}$ die Variable $X_i$ oder eine ihrer Nachfahren beobachtet wird und
keine der anderen Variablen $X_i$ beobachtet wird.

Statistische Unabhängigkeiten in Bayesschen Netzen¶

Bayesian Network Graph $\mathcal G$¶

DAG bildet das Gerüst (skeleton data structure)
Lokale Wahrscheinlichkeitsmodelle (local probability models). Diese definieren zusammen die multivariate Wahrscheinlichkeitsverteilung.

Aus Bayesschen Netze können statistische Unabhängigkeiten abgelesen werden. Für statistische Abhängigkeiten gilt dies i.A. nicht. Bayesschen Netze sind sogenannte I-Maps (independency maps - Karten über (bedingte) statistische Unabhängigkeiten).

D-Separation und kodierte (bedingte) Unabhängigkeiten¶

Definition: Zwei Zufallsvariablen $X_i$ und $X_j$ sind d-separated gegeben die Evidenz $\mathcal E$ (als Vektor $\vec e$), wenn es keinen aktiven Pfad zwischen $X_i$ und $X_j$ unter $\mathcal E$ gibt. (Hinweis: das "d" in d-separated steht für "directed", da wir einen gerichteten Graphen betrachten). Die Unabhängigkeiten, die der Graph kodiert, werden mit $\mathcal I(G)$ notiert.

$$ \text{d-sep}(X,Y\mid \vec e) \Rightarrow \mathcal (X \perp Y \mid \vec e) \text{ ist in } \mathcal I(\mathcal G) $$

Bzw. für die Menge der (bedingten) Unabhängigkeiten, die der Graph kodiert:

$$ \mathcal I(\mathcal G) =\{ (X_i, X_j \mid \vec e): \text{d-sep}(X_i,X_j\mid \vec e)\} $$

Kausalität¶

Bayessche Netze spiegeln nicht notwendigerweise Kausalität wider.

Allerdings kann Kausalität mittels Bayesscher Netze solide mathematische untersucht werden. Literatur hierfür:

Pearl, Judea. Causality. Cambridge university press, 2009.

Literatur¶

Koller, Daphne, and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. MIT press, 2009.