4.1 Wahrscheinlichkeiten und probabilistische Netzwerke 4.1.1

Darstellung, Verarbeitung und Erwerb von Wissen
4.1 Wahrscheinlichkeiten und probabilistische
Netzwerke
4.1.1 Grundlagen
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
1
Beispiel: Mord in Florida 1/2
Dieses Beispiel basiert auf einer realen statistischen Untersuchung, die
in Florida in den Jahren 1973-79 durchgeführt wurde. 5000 Mordfälle
wurden erfasst, und die folgende Wahrscheinlichkeitsverteilung P
spiegelt die Praxis der damaligen gerichtlichen Verurteilungen wider.
Betrachtete Aussagenvariablen:
V = Mordopfer (Victim) ist schwarz/weiß
M = Mörder ist schwarz/weiß
D = Todesstrafe (Death) verhängt
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
v̇ ∈ {vb, vw }
ṁ ∈ {mb, mw }
¯
d˙ ∈ {d, d}
2
Beispiel: Mord in Florida 2/2
ω
P (ω)
ω
P (ω)
vw mw d 0.0151 vw mw d 0.4353
vw mbd 0.0101 vw mbd 0.0502
vbmw d
0
vbmw d 0.0233
vbmbd 0.0023 vbmbd 0.4637
P (d|mw ) = 0.0319 und P (d|mb) = 0.0236
P (d|vw mw ) = 0.0335,
P (d|vbmw ) = 0,
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
P (d|vw mb) = 0.1675,
P (d|vbmb) = 0.0049
3
Simpson’s Paradoxon
P (E|C) > P (E|¬C),
aber: P (E|C, M ) < P (E|¬C, M ),
P (E|C, ¬M ) < P (E|¬C, ¬M )
Beispiel:
C = Medikamenteneinnahme, E = Gesundung
Gesamt
C
¬C
Männer
C
¬C
E ¬E
18 12
7
3
25 15
DVEW – WS 2004/05 –
E ¬E
20 20
16 24
36 44
Σ Gesundungsrate
40
50 %
40
40 %
80
Σ Gesund.
30
60 %
10
70 %
40
c Gabriele Kern-Isberner
Frauen
C
¬C
E ¬E
2
8
9 21
11 29
Σ Gesund.
10
20 %
30
30 %
40
4
Probabilistisches Schließen
• Probabilistisches Schließen ist schwierig und oft unergiebig
– P (A ∧ B) wird nicht eindeutig durch P (A) und P (B) bestimmt
z.B. P (A) = P (B) = 0.5 ⇒ P (A ∧ B) ∈ [0, 0.5]
– P (C|A) = x, P (C|B) = y ⇒ P (C|A ∧ B) ∈ [0, 1]!
⇒ Probabilistische Logik ist nicht wahrheitsfunktional!
• Zentrales Problem: Wie wirkt sich zusätzliche Information aus?
– d.h.: Wenn P (B|A) bekannt ist, was kann man dann über
P (B|A ∧ C) sagen?
• Hohe Komplexität (n Aussagen → 2n Vollkonjunktionen)
• Wahrscheinlichkeiten sind schwierig zu spezifizieren.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
5
Probabilistische Netzwerke 1/2
Grundlegende Ideen:
• Quantitatives probabilistisches Schließen wird mit qualitativer Information über Strukturen (i.e. Abhängigkeiten und Unabhängigkeiten
von Variablen) kombiniert
• Man benutzt graphische Mittel zur Darstellung: Zu jeder Aussage A1, . . . , An in Σ wird ein Knoten assoziiert, so dass
V = {A1, . . . , An} die Menge der Ecken eines Graphen G = GV
ist. Die Kanten von G sollen direkte Abhängigkeiten unter den Ai
repräsentieren.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
6
Probabilistische Netzwerke 2/2
Probabilistische Netzwerke können gerichtete oder ungerichtete Graphen sein:
Ungerichtete Graphen: (Markov-Netze)
• Eine ungerichtete Kante zwischen A und B drückt aus, dass A und
B direkt voneinander abhängig sind.
Gerichtete Graphen: (Bayes-Netze)
• Eine gerichtete Kante von A nach B drückt aus, dass B direkt
von A abhängig ist; A wird oft auch als kausale Ursache von B
betrachtet.
In beiden Graphentypen werden indirekte Abhängigkeiten mittels Pfaden im Graphen repräsentiert.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
7
Probabilistische Netzwerke – Beispiel
Ungerichteter Graph
Gerichteter Graph
A
x
A
x
B
x
B
?
x
C
x
C
?
x
A und B bzw. B und C
hängen direkt voneinander ab;
A und C hängen indirekt
voneinander ab.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
B hängt direkt von A ab,
C hängt direkt von B ab;
C hängt indirekt von A ab.
8
Darstellung, Verarbeitung und Erwerb von Wissen
4.1 Wahrscheinlichkeiten und probabilistische
Netzwerke
4.1.2 Ungerichtete Netzwerke
(Markov-Graphen)
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
9
Separation in ungerichteten Graphen 1/2
Idee:
Direkt abhängige Aussagen sollen Nachbarn in G sein, während indirekt abhängige Variablen durch Wege der Länge ≥ 2 verbunden
sind.
Separation:
• paarweise disjunkte Teilmengen A, B, C von V;
Schreibweise:
A
|=
• C separiert A und B,
G
B|C
gdw. jeder Weg zwischen einem Knoten in A und einem Knoten in
B mindestens einen Knoten von C enthält.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
10
Separation in ungerichteten Graphen 2/2
C
A
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
|=
A
G
B
B|C
11
Separation und bedingte Unabhängigkeit
0
B
|
(C
∪
C
);
G
P
B | C gilt, nicht aber
|=
• es ist jedoch möglich, dass A
A P B | (C ∪ C0).
|=
G B | C impliziert A
|= |=
• A
|=
|=
graphische Separation und probabilistische bedingte Unabhängigkeit
sind ähnliche Konzepte, aber . . .
A P B | C gdw. A G B | C ist nicht möglich, denn
abhängig:
gender
|=
Im Raucher-Beispiel sind Geschlecht und verheiratet statistisch unP
marriage | ∅,
nicht
DVEW – WS 2004/05 –
( gender
c Gabriele Kern-Isberner
|=
aber bedingt abhängig gegeben Schwangerschaft:
P
marriage | pregnancy)!
12
Markov-Netze 1/2
Graph G mit Knotenmenge V, Verteilung P über V
G
B | C impliziert A
|=
A
|=
G heißt Unabhängigkeitsgraph zu P , wenn gilt:
P
B|C
(globale Markov-Eigenschaft)
d.h. Unabhängigkeiten in G entsprechen Unabhängigkeiten in P .
Unabhängigkeitsgraphen stellen i.Allg. zu viele Abhängigkeiten dar,
d.h. einige (bedingte) Unabhängigkeiten werden nicht repräsentiert.
Unabhängigkeitsgraphen, die dieses Fehlverhalten auf ein Minimum
reduzieren, sind von besonderem Interesse.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
13
Markov-Netze 2/2
Ein Unabhängigkeitsgraph G heißt minimaler Unabhängigkeitsgraph
oder Markov-Graph zu P , wenn G keine überflüssigen Kanten enthält,
d.h., wenn G nach Entfernen einer beliebigen Kante kein Unabhängigkeitsgraph mehr zu P ist.
Es gelten die folgenden Resultate:
|=
• Zu jeder positiven Wahrscheinlichkeitsverteilung P gibt es einen
(eindeutig bestimmten) Markov-Graph G0 = hV, E0i, so dass
(A, B) ∈
/ E0 gdw. A P B | (V − {A, B}).
• Andererseits lässt sich zu jedem ungerichteten Graphen G eine
Verteilung P angeben, so dass G ein Unabhängigkeitsgraph von P
ist. P heißt dann Markov-Feld bezgl. G.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
14
Beispiel Infektion
Av
@
@
B
@
@
@
@
@v
v
@
@
@
@
@
C
@
@v
D
G
DVEW – WS 2004/05 –
D | {B, C}, also auch A
c Gabriele Kern-Isberner
|=
Es gilt A
|=
Personen A, B, C, D haben sich infiziert – die Kanten geben die
Kontakte innerhalb dieser Gruppe wieder.
P
D | {B, C}.
15
Verteilung → Markov-Graph:
Sei P eine (positive) Wahrscheinlichkeitsverteilung über V.
A
|=
Ausgehend von einem vollständigen Graphen auf V entfernt man alle
Kanten (A, B), für die gilt
P
B | (V − {A, B})
|=
(Umgekehrt kann man natürlich auch von einem leeren Graphen
starten und nur die Knoten verbinden, bei denen A P B | (V −
{A, B}) für die entsprechenden Variablen falsch ist.)
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
16
Potentialdarstellungen
Sei P eine gemeinsame Verteilung über den Variablen in V;
sei {Wi | 1 ≤ i ≤ p} eine Menge von Teilmengen von V mit
Sp
i=1 Wi = V; seien
ψi : {wi | wi ist Vollkonjunktion über Wi, 1 ≤ i ≤ p} → IR≥0
Funktionen, die jeder Vollkonjunktion von Variablen in Wi (1 ≤ i ≤
p) eine nicht-negative reelle Zahl zuordnen.
Gilt nun
P (V) = K ·
Qp
i=1 ψi(Wi)
so heißt {W1, . . . , Wp; ψi} eine Potentialdarstellung von P .
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
17
Kleine Graphentheorie
Sei G = hV, Ei ein ungerichteter Graph.
Eine Teilmenge C ⊆ V heißt Clique von G, wenn C eine maximale
vollständige Menge ist, d.h., wenn jedes Paar verschiedener Knoten
aus C durch eine Kante in E miteinander verbunden ist, und wenn C
bzgl. dieser Eigenschaft maximal unter den Teilmengen von V ist.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
18
Graph G → Verteilung P
• C1, . . . , Cm seien die Cliquen von G.
• Zu jeder Clique Ci, definiere (beliebig) eine nicht-negative PotenP Qm
tialfunktion ψi(Ci), so dass V i=1 ψi(Ci) 6= 0.
• Ein passendes P (so dass G ein Unabhängigkeitsgraph für P ist)
lässt sich dann definieren durch
P (V) := K
Qm
i=1 ψi(Ci)
(P faktorisiert über den Cliquen von G)
Potentialdarstellungen brechen die Komplexität von Wahrscheinlichkeitsverteilungen auf!
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
19
Beispiel Infektion (Forts.)
Av
@
@
@
@
B
@
@
@v
v
@
@
@
@
@
@
C
Personen
A, B, C, D
haben
sich
infiziert
@v
D
Mengensystem = Cliquen Ci:
C1 = {A, B}, C2 = {A, C}, C3 = {B, D}, C4 = {C, D}
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
20
Beispiel Infektion (Forts.)
Potentialfunktion(en) ψi:
ci
ab
ab
ab
ab
DVEW – WS 2004/05 –
ψi(ci)
1
0
0
0.5
ci
ac
ac
ac
ac
c Gabriele Kern-Isberner
ψi(ci)
1
0
0
0.5
ci
bd
bd
bd
bd
ψi(ci)
1
0
0
0.5
ci
cd
cd
cd
cd
ψi(ci)
1
0
0
0.5
21
Beispiel Infektion (Forts.)
Passende Wahrscheinlichkeitsfunktion:
P (A, B, C, D) = K · ψ1(A, B)ψ2(A, C)ψ3(B, D)ψ4(C, D)
d.h.
v
K −1P (v)
v
K −1P (v)
v
K −1P (v)
v
K −1P (v)
abcd
abcd
abcd
abcd
1
0
0
0
abcd
abcd
abcd
abcd
0
0
0
0
abcd
abcd
abcd
abcd
0
0
0
0
abcd
abcd
abcd
abcd
0
0
0
0.0625
mit K = (1 + 0.0625)−1
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
22
Grenzen ungerichteter Netzwerke
Ergebnisse der Würfe zweier gleicher, fairer Münzen;
Glocke, klingelt genau dann, wenn Ergebnisse der
Münzwürfe gleich.
A
P
B | ∅, aber nicht A
|=
A, B
C
“Münzen und Glocke”:
|=
Beispiel
P
B|C
Kein ungerichteter Graph kann beide Aussagen zugleich repräsentieren!
Ay
By
@
@
@
@
@
@
R
@
y
C
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
23
Darstellung, Verarbeitung und Erwerb von Wissen
4.1 Wahrscheinlichkeiten und probabilistische
Netzwerke
4.1.3 Gerichtete Netzwerke (Bayes-Netze)
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
24
Wir werden uns im Folgenden mit gerichteten probabilistischen Netzwerken beschäftigen . . .
Zentrales Problem:
Wie spiegeln sich bedingte Unabhängigkeiten in der Graphenstrukur wider?
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
25
Holmes und Watson in London
Ein Winterabend in London . . .
S
: glatte Straßen (Slippery roads)
Ha : Holmes hatte einen Unfall (Holmes – car accident)
Wa : Watson hatte einen Unfall (Watson – car accident)
' $
S
& %
@
@
@
'
$
R' $
@
Ha
& %
Wa
& %
• keine Information über S: Ha und Wa voneinander abhängig.
• konkrete Information über S: keine (direkte) Abhängigkeit mehr!
Ha und Wa sind also bedingt unabhängig bei gegebenem S.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
26
Holmes und Watson in Los Angeles
Ein sonniger Morgen in Los Angeles . . .
R
S
Hl
Wl
:
:
:
:
Regen in der letzten Nacht
der Sprinkler hat sich (irrtümlich) angeschaltet
Holmes’ Rasen (lawn) ist nass
Watson’s Rasen (lawn) ist nass
' $
' $
S
R
& %
& %
@
@
@
$
$
'
@
R' Wl
& %
Hl
& %
Auch hier sind Wl und Hl bedingt unabhängig bei gegebenem R.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
27
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
28
Gerichtete azyklische Graphen . . .
. . . (Directed acyclic graphs, DAG) G sind gerichtete Graphen ohne
Zyklen (i.e. zyklische Effekte werden im Folgenden von der Betrachtung ausgenommen).
• Wenn (v, w) eine (gerichtete) Kante in G ist, dann nennt man v
den Elternknoten von w, und w das Kind von v.
• w heißt Nachkomme (descendant) von v, und v heißt Vorfahr von
w, wenn es in G einen (gerichteten) Pfad von v nach w gibt.
• Die Nicht-Nachkommen (non-descendants, nd (v)) eines Knoten v
sind diejenigen Knoten in V, die verschieden sind von v und seinen
Elternknoten und nicht zu seinen Nachkommen gehören.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
29
Bayes-Netze
Ein Bayessches Netz
B = hV, E, P i
besteht aus
• einem DAG G = hV, Ei und
• einer Wahrscheinlichkeitsverteilung P über V = {A1, . . . , An},
Ai
|=
so dass jede Variable Ai bedingt unabhängig von ihren NichtNachkommen nd (Ai), gegeben ihre Elternknoten pa(Ai):
P
nd (Ai) | pa(Ai) für alle i = 1, . . . , n
lokale gerichtete Markov-Bedingung
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
30
Holmes und Watson in London
Ein Winterabend in London . . .
S
Ha
Wa
:
:
:
glatte Straßen (Slippery roads)
Holmes hatte einen Unfall (Holmes – car accident)
Watson hatte einen Unfall (Watson – car accident)
' $
S
& %
@
@
@
$
'
R' $
@
Ha
Ha
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
|=
& %
P
Wa
& %
Wa | S
31
Holmes und Watson in Los Angeles
Ein sonniger Morgen in Los Angeles . . .
R
S
Hl
Wl
:
:
:
:
Regen in der letzten Nacht
der Sprinkler hat sich (irrtümlich) angeschaltet
Holmes’ Rasen (lawn) ist nass
Watson’s Rasen (lawn) ist nass
' $
' $
S
R
& %
& %
@
@
@
$
$
'
@
R' Hl
Wl
& %
Hl
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
|=
& %
P
Wl | R
32
Exkurs: D-Separation 1/2
In einem Bayesschen Netzwerk besteht der folgenden wichtige Zusammenhang zwischen der graphischen und der probabilistischen Repräsentation von Wissen:
Ai
|=
Jede Variable Ai ist bedingt unabhängig von ihren Nicht-Nachkommen
nd (Ai), gegeben ihre Elternknoten pa(Ai):
P
nd (Ai) | pa(Ai) für alle i = 1, . . . , n
lokale gerichtete Markov-Bedingung
Wenn C A und B d-separiert, so gilt A
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
|=
Dazu passt der Begriff der d-Separation – in einem Bayesschen Netz
gilt nämlich die Globale gerichtete Markov-Bedingung
P
B|C
33
Exkurs: D-Separation 2/2
Sei G ein DAG über V.
• Eine Vorfahrenmenge ist eine Menge A ⊆ V, in der für jeden
Knoten v ∈ A auch alle seine Vorfahren an(v) enthalten sind.
• Für eine Knotenmenge W ⊆ V bezeichnet An(W) die kleinste
Vorfahrenmenge, die W enthält:
S
An(W) = W ∪ w∈W an(w)
Definition “d-Separation”
Sei G ein DAG, seien A, B, C disjunkte Teilmengen von V. C dsepariert A und B in G, wenn C die beiden Mengen A und B
in dem moralen Graphen, der durch die kleinste Vorfahrenmenge
An(A ∪ B ∪ C) aufgespannt wird, separiert.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
34
Kleine Graphentheorie
Sei G = hV, Ei ein ungerichteter Graph.
• Eine Sehne eines einfachen Weges oder Zyklus’ v0, v1, . . . , vn in G
ist eine Kante zwischen zwei nicht aufeinanderfolgenden Knoten
vi, vj , | i − j |> 1.
• G heißt trianguliert, wenn jeder einfache Zyklus der Länge > 3 eine
Sehne besitzt.
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
35
Graphen – Beispiele
'$
'$
A
@
&%
@
@
@
@
@
$
'
'$
C
B
A
@
&%
@
@
@
@
@
$
'$'$'
B
D
C
&%
&%
@
@
@
@
@ '$
@
&%&%&%
@
@
@
@
@ '$
@
&%
&%
D
trianguliert
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
E
nicht trianguliert!
36
Potentialdarstellungen für Bayes-Netze
Eltern-Kind-Beziehungen in Bayesschen Netzen symbolisieren direkte
Abhängigkeiten:
Elternknoten ist direkte Ursache für Kindknoten.
(Bayessche Netzwerke ≈ kausale Netzwerke, auch: belief networks)
Eine Potentialdarstellung eines Bayesschen Netzes wird gegeben durch
P (V) =
Q
P (V | pa(V ))
V ∈V
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
37
Bayessches Netz – Krebserkrankung
A
B
C
D
E
Krebserkrankung mit Metastasen liegt vor
Kalzium-Serum-Wert ist erhöht
Gehirntumor liegt vor
Koma liegt vor
starke Kopfschmerzen liegen vor
' $
A
& %
@
@
'
$
R' $
@
B
C
& %
& %
@
@
@
@
$
R' @
R' $
@
D
& %
E
& %
P (A, B, C, D, E) = P (A)P (B|A)P (C|A)P (D|BC)P (E|C)
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
38
Bayessches Netz – Krebserkrankung (Forts.)
Durch die folgenden (bedingten) Wahrscheinlichkeiten wird P
vollständig festgelegt:
P (a) = 0.20
P (b | a) = 0.80
P (b | ā) = 0.20
P (c | a) = 0.20
P (c | ā) = 0.05
P (d | bc) = 0.80
P (d | b̄c) = 0.70
P (d | bc̄) = 0.90
P (d | b̄c̄) = 0.05
P (e | c) = 0.80
P (e | c̄) = 0.60
P (abcde) = P (a)P (b|a)P (c|a)P (d|bc)P (e|c)
= 0.2 · 0.8 · 0.2 · 0.2 · 0.8 = 0.00512
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
39
Bayessches Netz – Krebserkrankung (Forts.)
Vorteil der Potentialdarstellung:
Man benötigt nur 11 (bedingte) Wahrscheinlichkeiten, um die 25 = 32
Werte der Verteilung P (A, B, C, D, E) zu bestimmen.
Beweis der Potentialdarstellung (in diesem Beispiel):
P (A, B, C, D, E) P (A, B, C, D)
P (A, B, C, D, E) =
·
P (A, B, C, D)
P (A, B, C)
P (A, B, C) P (A, B)
·
·
· P (A)
P (A, B)
P (A)
= P (E|A, B, C, D) · P (D|A, B, C)
·P (C|A, B) · P (B|A) · P (A)
= P (E|C)P (D|B, C)P (C|A)P (B|A)P (A)
DVEW – WS 2004/05 –
c Gabriele Kern-Isberner
40