Thomas Bayes Theorie joint probability, DAG aus Markovian Parents conditional independence, explain...

Thomas Bayes Theorie

joint probability, DAG aus Markovian Parentsconditional independence, explain away, d-SeparationInference „brute force“Lernen einer binomialen VariableLernen einer multinomialen VariableBeispiel Lernen eines NetzwerksLernen der einzelnen CPT

Bayesche Netzwerke

Bayesche Denkweise

Thomas Bayes 1702-17611764 p.m. veröffentlichtRoyal Society of London

unbeeinsprucht bis George Bool 1854 „Laws of Thought“

Bayesche DenkweiseBayesche Denkweise

Thomas Bayes 1702-1761Subjektive WahrscheinlichkeitBackground ξa priori: p(e|ξ) a posteriori: p(e|D, ξ)

)|(

),|()|(),|(

Dp

eDpepDep

research by

David Heckerman Microsoft Research, Lernen in BN

Judea Pearl University of California, Theorie von Kausalität u.a.

Spiegelhalter University of Cambridge, Biostatistic, Klinische

Studien

Beispiel seasons (Pearl, Russel 2000)

implementiert in Netica 4.09www.norsys.com

Bayesian Networks are directed acyclic graphs (DAG). The causal connections are direct represent-ations of the real world.

Beispiel seasons

Sprinkler prob. wet (prediction)

slippery prob. wet (abduction)

wet prob. sprinkler or rain (abduction)

no link from Season to slippery

Beispiel seasons

Sprinkler Rain | Season

Kausalität

rauchen

Krebs

statistical knowlege is not causal knowlege

Judea Pearl: „correlation does not imply causation“

Kopfweh

Wetterumschwung

Conditional Independence

A

C

B A

C

B A

C

B

joint probability

X={X1,X2, ... , Xn}

2n verschiedene RealisierungenMöglicherweise 10.000nde Variablenjoint probability ist O(exp(n))!!conditional probability tables in BN sind nur O(nk)!!

),,,,()( 54321 xxxxxpxp

63 verschiedene Werte

Markovian Parents

),,,|(),,|(),|()|()(

),,,,(

432153214213121

54321

xxxxxpxxxxpxxxpxxpxp

xxxxxp

Use product rule to decompose joint probability into product of conditional probabilities. Order is important!!

Markovian Parents

)|(),|()|()|()()( 4532413121 xxpxxxpxxpxxpxpxp

)|(),,,|(

),|(),,|(

)|(),|(

)|(

)(

,,,, :Order

4543215

3243214

13213

12

1

54321

xxpxxxxxp

xxxpxxxxp

xxpxxxp

xxp

xp

xxxxx

Markovian Parents

)|(),|()|()|()()( 4532413121 xxpxxxpxxpxxpxpxp

3 + 4 + 4 + 4 + 2 = 17 verschiedene Werte

)|(),,,|(

),|(),,|(

)|(),|(

)|(

)(

,,,, :Order

4543215

3243214

13213

12

1

54321

xxpxxxxxp

xxxpxxxxp

xxpxxxp

xxp

xp

xxxxx

Markovian Parents

und PAi sind minimal

PAi sind markovian parents von Xi, wenn gilt:

ii

i

jji PAPAXX

\1

1

i

iin paxpxxp ,,1 daraus folgt:

d-separation (Pearl 1988)

AC

B A

CB A

C

B

Pfad blockiert, Information kann nicht passieren (AB)

A B

AC

B A

CB A

C

B

Pfad frei, Information propagiert (AB)

A B

}{}{}{ CBA

Beispiel explaining away

p(M|I) > p(M|S,I)

Sportlich Musikalisch |

Sportlich

Internat

Musikalisch

ASportlich Musikalisch | Internat)

Aufnahmekriterium des Internats: sportliche Leistung oder musikalische Begabung

explaning away

A

C

B

Diese Art des Schließens ist in regelbasierten Systemen oderneuronalen Netzen sehr schwer zu modellieren,in Bayeschen Netzen aber selbstverständlich.

Inference, evaluation

gegeben sind einige Faktengesucht ist die Wahrscheinlickeit von einer gewissen Konfiguration

? yesslipperyonsprinklerp

?53 yesXonXp

Inference, evaluation

Berechnung durch cond.prob.

4321

421

4321

421

,,, 4532413121

,, 4532413121

,,, 5321

,, 5321

5

5353

,

,

,,,

,,,

,

xxxx

xxx

xxxx

xxx

xtrueXpxxxpxxpxxpxp

xtrueXponXxxpxonXpxxpxp

trueXxxxp

trueXonXxxp

yesXp

yesXonXpyesXonXp

Inference, evaluation

im allgemeinen NP-hart (Cooper,1987)in realistischen Netzen ist exakte Lösung ebenfalls NP-hartlineare Lösung nur für polytrees „singly connected networks“

Applications

speech recognition Thiesson, Meek, Chickering, Heckerman 98

causal discoveryLernen von Strukturen, s. Heckerman 95

expert systemsMicrosoft Printer-Troubleshooter, Office Wizards

preference prediction Microsoft Commerce Server 4.0

Lernen, einfachstes Netz

nur ein Knoten in Graphz.B. Werfen eines Reißnagels

X X kann die Wertehead oder tail annehmen

nach n Versuchen soll der n+1ste vorhergesagt werden

Lernen als Bayesches Netz

mit jedem Wurf steigt mein Wissenleider steigen auch die Abhängigkeiten

A

X1

X2

X6

X5

X3 X4

hidden variable einführen

BN mit Hyperparameter

Bayesches Netz mit einer hidden variable

A priori Annahmen:Würfe sind unabhängig,Eigenschaften des Nagels bleiben unverändert mit der Zeit,All möglichen Werte für θ gelten als gleich wahrscheinlich.

X2 X3 X4 X5 X6X1

A

a priori Hypothese

Strukturwissen und ParameterschätzungenExpertenwissen fließt einKausale Zusammenhänge sind „logisch“Assessment liefert gute ErgebnisseStruktur von ExpertenCPT durch Lernen aus Datenbank

.

Lernen, Hypothese

Lernen mit conjugate prior

ththDp 1,,

Dp

DppDp

,,

th

th

thth

fc

pc

DppcDp

1

1

,, ,,

11

, 1Beta

th

th

th

thfp

th

th

th

thth th

th

th

thDp

,11

, Beta1,

a priori:

Lernen, Ergebnis

Marginalisierung über die Wahrscheinlichkeitsverteilungentspricht hier dem Erwartungswert

th

h

Dp

DpDheadXpDheadXp

th

h

th

th

ththth

th

,

,

,,,

BetaEE

d,

d,,,,