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

Bedingten 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{1cm}$
$i^0$ $s^1$ 0.035
$i^1$ $s^0$ 0.06
$i^1$ $s^1$ 0.24

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 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 [4]:
from matplotlib import rc
rc("font", family="serif", size=16)
rc("text", usetex=True)
In [5]:
%matplotlib inline

from IPython.core.pylabtools import figsize
from matplotlib import pyplot as plt
In [6]:
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[6]:
<matplotlib.axes._axes.Axes at 0x111ee2a90>

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 [13]:
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.))
    pgm.add_node(daft.Node("X_2", r"$X_2$", 1., 0.))
    pgm.add_node(daft.Node("X_3", r"$X_3$", 2., 0.))
    pgm.add_node(daft.Node("X_4", r"$X_4$", 3., 0.))
    pgm.add_node(daft.Node("C", r"C", 2., 1.))
    pgm.add_node(daft.Node("X_n", r"$X_{n=5}$", 4., 0.))
    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) $$

Die Anzahl der freien Parameter des Modells wächst linear mit der Anzahl der Variablen $X_i$.

In [14]:
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 [37]:
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 [38]:
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 resoning $\downarrow$: z.B. $P(l^1 \mid i^0) \approx 0.388$
  • Evidential resoning, explaination $\uparrow$: z.B. $P(i^1 \mid g^3) \approx 0.079$
  • Intercausal resoning $\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 ist.
  • keine der anderen Variablen $X_i$ beobachtet ist.

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.

Statistische Unabhängigkeiten; Semantik Bayesscher Netze

Definition:

Eine Bayessche Netzstruktur $\mathcal G$ ist ein direkter azyklischer Graph $\mathcal G$, dessen Knoten $X_1,\dots,X_n$ Zufallsvariable repräsentieren.
$\text{Par}^{\mathcal G}_{X_i}$ steht für die Eltern von $X_i$ im Graph $\mathcal G$ und
$\text{NonDescendants}^{\mathcal G}_{X_i}$ für die Nicht-Nachfahren von $X_i$ im Graph $\mathcal G$.
Dann kodierte $\mathcal G$ folgenden Menge von bedingeten Unabhängigkeitsannahmen (local independencies), die mit $\mathcal I(G)$ notiert werden: $$ \forall X_i: (X_i \perp \text{NonDescendants}^{\mathcal G}_{X_i} \mid \text{Par}^{\mathcal G}_{X_i}) $$

D-Seperation

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.

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

Die Unabhängigkeiten, die der Graph codiert: $$ \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.

Kausalität (im Kontext Bayesscher Netze) ist ein eigenes Thema. Literatur: Pearl, Judea. Causality. Cambridge university press, 2009.

Literatur

  • Koller, Daphne, and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.