24
G.Brewka Wissensbasierte Systeme 1 Probabilistisches Schließen Grundannahmen der klassischen Logik: Satz p wahr oder falsch; man weiß, was gilt, oder man weiß nichts. Bush ist Präsident der USA. Grundannahmen der subjektiven Wahrscheinlichkeitstheorie: Satz p wahr oder falsch; Grad der Überzeugung (degree of belief) eines Agenten, dass p gilt, wird durch Wert zwischen 0 und 1 beschrieben. Obama wird mit Wahrscheinlichkeit 0.6 nächster Präsident der USA. Grundannahmen der statistischen Wahrscheinlichkeitstheorie: Es gibt wiederholbares Experiment X mit Ergebnissen x1, ..., xn. Wert zwischen 0 und 1 gibt relative Häufigkeit der Ergebnisse bei oftmaligem Wiederholen des Experiments an.

G. BrewkaWissensbasierte Systeme 1 Probabilistisches Schließen Grundannahmen der klassischen Logik: Satz p wahr oder falsch; man weiß, was gilt, oder man

Embed Size (px)

Citation preview

G.Brewka Wissensbasierte Systeme1

Probabilistisches Schließen

Grundannahmen der klassischen Logik:

Satz p wahr oder falsch; man weiß, was gilt, oder man weiß nichts.

Bush ist Präsident der USA.

Grundannahmen der subjektiven Wahrscheinlichkeitstheorie:

Satz p wahr oder falsch; Grad der Überzeugung (degree of belief) eines Agenten, dass p gilt, wird durch Wert zwischen 0 und 1 beschrieben.

Obama wird mit Wahrscheinlichkeit 0.6 nächster Präsident der USA.

Grundannahmen der statistischen Wahrscheinlichkeitstheorie:

Es gibt wiederholbares Experiment X mit Ergebnissen x1, ..., xn. Wert zwischen 0 und 1 gibt relative Häufigkeit der Ergebnisse bei oftmaligem Wiederholen des Experiments an.

Die Wahrscheinlichkeit, eine 6 zu würfeln, ist 1/6.

G.Brewka Wissensbasierte Systeme2

Bedeutung von Wahrscheinlichkeiten für rationales Entscheiden

Basiert auf Wahrscheinlichkeiten der Effekte E der getroffenen Entscheidung A und deren Nutzen U(E)

Beispiel Flugzeug erreichen

90 min vorher losfahren? kann schiefgehen

120 min? schiefgehen unwahrscheinlicher, aber unangenehme Wartezeit

24 Std? schiefgehen fast ausgeschlossen, aber endloses Warten

Slogan: Entscheidungstheorie = Wahrscheinlichkeitstheorie + Nutzentheorie

Maximum Expected Utility:

Wähle Aktion A, so dass P(E) U(E) maximal wird!

EEffect(A)

G.Brewka Wissensbasierte Systeme3

Unsicheres Wissen

Beispiel Diagnose:

Zahnweh => Karies

falsch, weil es andere Gründe für Zahnweh geben kann

Zahnweh => Karies ... Kinnhaken

impraktikabel, Liste immer weiter verlängerbar, Medizin nicht abgeschlossen,

Unterscheidung plausible/unplausible Ursachen fehlt

deshalb Verwendung von Wahrscheinlichkeiten:

bedingte Wahrscheinlichkeit von Karies bei Zahnweh ist 0.8:

P(Karies | Zahnweh) = 0.8

Zahnweh hier die Evidenz, Zufügen neuer Evidenz kann Wahrscheinlichkeit (nichtmonoton) ändern, alle Evidenz ist grundsätzlich zu berücksichtigen

G.Brewka Wissensbasierte Systeme4

A Priori (Unbedingte) Wahrscheinlichkeit

Wahrscheinlichkeit einer Proposition ohne Vorliegen von Evidenz:

P(Karies) = 0.1

Aussagen, über deren W. man spricht, häufig in Form von Gleichungen

Wetter ist Zufallsvariable mit Wertebereich {Sonne,Regen,Wolken,Schnee}

Propositionale Konstanten auch als Zufallsvariable mit den Werten {true, false} aufzufassen. A Abkürzung für A = true, ¬A für A = false

Notation: P(Wetter) steht für Vektor der W. aller Werte: <0.7, 0.2, 0.08, 0.02>

heißt auch Wahrscheinlichkeitsverteilung für Wetter

P(Wetter, Karies, ...) ist W.-verteilung für alle Kombinationen von Werten aller Variablen

aussagenlogische Junktoren für Wahrscheinlichkeit komplexer Sätze: P(A B)

P(Wetter = Sonne) = 0.7P(Wetter = Regen) = 0.2P(Wetter = Wolken) = 0.08P(Wetter = Schnee) = 0.02

G.Brewka Wissensbasierte Systeme5

Bedingte Wahrscheinlichkeit

P(A | B): die Wahrscheinlichkeit von A, falls alles, was wir wissen, B ist

für Zufallsvariablen X, Y bezeichnet P(X | Y) die 2-dimensionale Tabelle mit Eintrag P(X = xi | Y= yj) an der Stelle i,j

bed. W. durch unbedingte definierbar, falls P(B) > 0:

P(A | B) = oder

P(A B) = P(A | B) P(B) (Produktregel) oder

P(A B) = P(B | A) P(A)

P(A B)P(B)

AA B B

¬A ¬B

mögliche Welten vor nach Bekanntwerden von B

A B B

G.Brewka Wissensbasierte Systeme6

P(B | A) P(A => B)

Beispiel:

P(A B) = 0.25P(A ¬B) = 0.25P(¬A B) = 0.25P(¬A ¬B) = 0.25

P(A => B) = P(¬A B) + P(¬A ¬B) + P(A B) =0.75

P(B | A) = P(A B)P(A)

= 0.250.5 = 0.5

A B

¬A B

A ¬B

¬A ¬B

P(A => B) P(B | A)mögliche Welten

G.Brewka Wissensbasierte Systeme7

Wahrscheinlichkeitsaxiome

1. 0 P(A) 1

2. P(true) = 1, P(false) = 0

3. P(A B) = P(A) + P(B) - P(A B)

A BA B

¬A ¬B

Alle Eigenschaften aus Axiomen ableitbar, etwa:

====

P(A ¬A)P(true)

1P(¬A)

P(A) + P(¬A) - P(A ¬A)P(A) + P(¬A) - P(false)P(A) + P(¬A) 1 - P(A)

G.Brewka Wissensbasierte Systeme8

Sind die Wahrscheinlichkeitsaxiome vernünftig?

Anhaltende philosophische Debatten über subjektive Wahrscheinlichkeit

Rückführung durch de Finetti auf Wettverhalten: wer bestimmte Wahr- scheinlichkeiten annimmt, sollte bereit sein, entsprechend darauf zu setzen.

de Finetti hat bewiesen:

Wenn Agent 1 "Wahrscheinlichkeiten" verwendet, die die Wahrscheinlich- keitsaxiome verletzen, so gibt es für Agent 2 eine Wettstrategie, bei der 1 mit Sicherheit verliert.

Agent1 Agent2 Ergebnis für Agent1Proposition Grad Wette Quote A B A ¬B ¬A B ¬A ¬B

-6-72

-11

-632

-1

4-72

-1

43-8

-1

AB

A B

0.40.30.8

AB

¬(A B)

4 zu 63 zu 72 zu 8

G.Brewka Wissensbasierte Systeme9

Wahrscheinlichkeitsverteilung (joint probability distribution, JPD)

probabilistisches Modell: Menge {X1, ..., Xn} von Zufallsvariablen mit möglichen Werten

atomares Ereignis: Belegung aller Variablen mit Werten

Wahrscheinlichkeitsverteilung P(X1, ..., Xn): n-dimensionale Tabelle, weist allen atomaren Ereignissen W. zu

Zahnweh ¬ Zahnweh

Karies¬ Karies

0.04

0.01

0.06

0.89

Beispiel n = 2, Summe aller Einträge = 1

Wahrscheinlichkeiten können abgelesen und aufaddiert werden: P(Karies) = 0.04 + 0.06, P(Karies Zahnweh) = 0.04 + 0.06 + 0.01

P(Karies | Zahnweh) = = = 0.8P(Karies Zahnweh)P(Zahnweh)

0.040.04 + 0.01

G.Brewka Wissensbasierte Systeme10

Bayes´ Theorem

JPD ermöglicht Berechnung aller Wahrscheinlichkeiten.

Aber 2 Einträge schon im booleschen Fall (Variablen haben Werte ja/nein)

gesucht: Möglichkeit, direkt mit bed. W. zu rechnen

Produktregel:

n

P(A B) = P(A | B) P(B)P(A B) = P(B | A) P(A)

Gleichsetzen der rechten Seiten und Division durch P(A):

P(B | A) = P(A | B) P(B)P(A) (Bayes´ Regel)

Verallgemeinerung:

P(B | A, E) = P(A | B, E) P(B, E)P(A, E)

G.Brewka Wissensbasierte Systeme11

Anwendungsbeispiel

Medizinische Diagnose:

Meningitis verursacht zu 50% Nackensteife

A priori Wahrscheinlichkeit von Meningitis ist 1/50 000

A priori Wahrscheinlichkeit von Nackensteife 1/20

Hat Patient mit Nackensteife Meningitis?

P(M | S) = P(S | M) P(M)

P(S)0.51 / 50000

1 / 20= = 0.0002

G.Brewka Wissensbasierte Systeme12

Vermeiden von a priori W. für Symptome

Angenommen, es gibt eine weitere Krankheit W, die S verursacht.

Wenn es nur darauf ankommt, die relative Wahrscheinlichkeit von W und M, gegeben S, zu berechnen, ist P(S) nicht nötig: wenn P(S | W) = 0.8 und P(W) = 1/1000, dann ist

P(M | S) P(W | S)

= P(S | M) P(M) P(S | W) P(W)

= 0.51/50 000

0.81/100= 1/80

Auch wenn exakte Werte für die bedingten W. nötig sind, sind manchmal a priori W. für Symptome nicht nötig:

da P(S) = P(S | M) P(M) + P(S | ¬M) P (¬M) wird Bayes´ Rule zu

P(M|S) = P(S|M) P(M)P(S|M)P(M) + P(S |¬M)P(¬M)

also: statt P(S) wird P(S | ¬M) verwendet, häufig einfacher zu ermitteln

G.Brewka Wissensbasierte Systeme13

Normalisierung

Es gilt P(M | S) + P(¬M | S) = 1; es muss Faktor = 1/P(S) geben, so dass

P(S | M) P(M) + P(S | ¬M) P(¬M) = 1

Im mehrwertigen Fall: P(Y | X) = P(X | Y) P(Y)

wobei die Normalisierungskonstante ist, d.h. die Konstante, die die Summe der Tabelleneinträge von P(Y|X) zu 1 macht.

In der Praxis wird oft zunächst mit unnormalisierten Werten gerechnet, diese werden zuletzt normalisiert

Beispiel: wir wissen P(M) = 0.00002, damit P(¬M) = 0.99998, P(S | M) = 0.5

Annahme: P(S | ¬M) = 4999 / 99998, gesucht so dass

0.50.00002 + 4999 / 99998 0.99998 = 1

Lösung: = 20

G.Brewka Wissensbasierte Systeme14

Seien X, Y, Z Zufallsvariablen.

X ist bedingt unabhängig von Y gegeben Z genau dann wenn eine der folgenden

äquivalenten Bedingungen erfüllt ist:

P(X | Z) = P(X | Z,Y)

P(Y | Z) = P(Y | Z,X)

P(X,Y | Z) = P(X | Z) P(Y | Z)

Intuitiv: falls Z bekannt ist, ändert sich die Wahrscheinlichkeit von X nicht,

wenn Y bekannt wird (und umgekehrt, da bed. Unabhängigkeit symmetrisch).

Bedingte Unabhängigkeit

G.Brewka Wissensbasierte Systeme15

Überzeugungsnetze(Bayes Netze, Belief Networks, BNs)

Ein Überzeugungsnetz ist ein gerichteter Graph mit folgenden Eigenschaften

1. die Knoten des Graphen sind Zufallsvariablen

2. gerichtete Kanten von X nach Y bedeuten: X beeinflusst Y direkt

3. für jeden Knoten Y gibt es eine bedingte W. -Tabelle, die die Effekte der Elternknoten Xi auf Y beschreiben

4. der Graph ist zyklenfrei

Grundidee:

sparsame Repräsentation von bedingten Wahrscheinlichkeiten,

alle übrigen bed. W. ergeben sich aus dieser Information zusammen mit Unabhängigkeitsannahmen, ausgedrückt durch Topologie des Graphen

G.Brewka Wissensbasierte Systeme16

Ein Überzeugungsnetz

EinBruch Erdbeben

Alarm

AnrufJohn AnrufMary

P(B).001

P(E).002

BTTFF

ETFTF

P(A|BE) .95 .94 .29 .001

ATF

P(J|A) .90 .05

ATF

P(M|A).70.01

Tabellen spezifizieren bedingte Wahrscheinlichkeiten für jede möglicheWahrheitsbelegung der Elternknoten (Wert für die Negation in jeder Zeile implizit).

G.Brewka Wissensbasierte Systeme17

Überzeugungsnetze als Repräsentation der JPD

Eintrag in der JPD gibt die Wahrscheinlichkeit eines atomaren Ereignisses an, d.h. einer Belegung aller Zufallsvariablen mit Werten (im booleschen Fall wahr oder falsch).

ein BN ist die Repräsentation der JPD, die folgendermaßen definiert ist:

P(X1 = x1, ..., Xn = xn) = P(Xi = xi | Eltern(Xi))n

i = 1

terminiert, weil Graph azyklisch!

macht implizit Unabhängigkeitsannahmen: bei gegebenem Zustand der Elternknoten haben weitere Variablen keinen Einfluss. Etwa:

P(M | J, A, E, B) = P(M | A)

Beispiel:

P(J M A ¬B ¬E) =

P(J | A) P(M | A) P(A | ¬B ¬E) P (¬B) P(¬E) =0.9 0.7 0.001 0.999 0.998 = 0.00062

G.Brewka Wissensbasierte Systeme18

Ersparnis durch BN-Repräsentation

im schlechtesten Fall hängt eine Variable direkt von jeder anderen ab

=> keine Ersparnis

aber: normalerweise gibt es nicht zu großes k, so dass jede Variable höchstens von k anderen direkt abhängt

dann braucht boolesches BN maximal n 2 Zahlen, dagegen JPD 2

konkretes Beispiel: n = 20, k = 5, BN braucht 640 Angaben, JPD > 1000000

Hinweis zur Erstellung von BNs

es hat sich gezeigt, dass es am günstigsten ist, die kausale Struktur von Ereignissen als Grundlage für die Topologie der BNs zu verwenden

andere Strategien, z. B. von Symptom zu Ursache, führen oft zu komplexeren Netzen mit schwerer zu spezifizierenden Wahrscheinlichkeiten

k n

G.Brewka Wissensbasierte Systeme19

Bedingte Unabhängigkeit und d-Separation

kann man aus dem Netz ablesen, ob Knotenmenge X bei gegebener Evidenz E bedingt unabhängig ist von Knotenmenge Y?

==> Begriff der d-Separation. Sinn des Ganzen: wenn X und Y durch E d-separiert wird, so sind X und Y bedingt unabhängig bei Evidenz E.

E d-separiert X und Y wenn jeder ungerichtete Pfad von einem Knoten in X zu einem in Y durch E blockiert wird. Ein Pfad wird durch E blockiert wenn es auf ihm einen Knoten Z gibt, so dass

1. Z aus E und Z hat eine eingehende und eine ausgehende Pfadkante, oder

2. Z aus E und beide Pfadkanten sind ausgehend, oder

3. weder Z noch ein Nachfahre von Z sind in E, und beide Pfadkanten führen zu Z.

Z

Z

Z

X Y

E

1.2.3.

G.Brewka Wissensbasierte Systeme20

d-Separation: Beispiel

Batterie

Radio Zündung Benzin

Startet

Fährt

Radio und Benzin unabhängig gegeben ZündungRadio und Benzin unabhängig gegeben BatterieRadio und Benzin unabhängig ohne jede EvidenzRadio und Benzin abhängig gegeben Startet(wenn z.B Auto nicht startet, dann erhöht Radio die Wahrscheinlichkeit von ¬ Benzin)

G.Brewka Wissensbasierte Systeme21

Typen probabilistischer Inferenz

Diagnostische Inferenz (von Effekt zu Ursache)

geg.: AnrufJohn, gesucht: P(Einbruch | AnrufJohn) = 0.016

Kausale Inferenz (von Ursache zu Effekt)

geg.: Einbruch, gesucht: P(AnrufJohn | Einbruch ) = 0.67

Interkausale Inferenz (zwischen Ursachen und einem gemeinsamen Effekt)

geg.: Alarm, Erdbeben, gesucht: P(Einbruch | Alarm, Erdbeben) = 0.003 (explaining away)

Mischformen

geg.: AnrufJohn, ¬Erdbeben, gesucht: P(Alarm | AnrufJohn, ¬Erdbeben) = 0.03 (diagnostisch und kausal)

G.Brewka Wissensbasierte Systeme22

Inferenzverfahren für BNs

Es existieren diverse effiziente Inferenzmethoden

• Variablen-Eliminationsverfahren

• Cliquenbaum-Propagation (HUGIN Expert – siehe Demo)

• Rekursives Konditionieren

Effizient genug für vielfältigen praktischen Einsatz

Detaillierte Behandlung im Rahmen der Vorlesung nicht möglich

Hier nur kurz: rekursives Verfahren (Details dazu – nicht prüfungsrelevant - in Russell/Norvig)

G.Brewka Wissensbasierte Systeme23

Ein rekursiver BN-Algorithmus für P(X |E)

Annahme: BN ist Polytree: zwischen 2 Knoten höchstens 1 ungerichteter Pfad

X hat Eltern U = U1, ..., Um, Söhne Y = Y1, ..., Yn

E ist der Teil der Evidenz, der mit X durch Eltern verbunden ist

E ist der Teil der Evidenz, der mit X durch Söhne verbunden ist

Grundidee:

1. beschreibe P(X | E) auf der Basis von und

2. berechne den Effekt von auf die Eltern Ui, und propagiere ihn zu X

3. berechne den Effekt von auf die Söhne Yj, und propagiere ihn zu X

Berechnung für Eltern und Söhne rekursive Instanz des Problems für X

Falls Polytree-Bedingung nicht erfüllt ist, müssen Knoten geclustert werden

-X

+X

E+X

E -X

E+X

E -X

G.Brewka Wissensbasierte Systeme24

Clustering:

Cloudy

Sprinkler Rain

WetGrass

CTF

P(S|C)0.10.5

CTF

P(R|C)0.80.2

P(C) = 0.5

S RTT FF TF F

P(W|SR) 0.990.90 0.90 0.00

Cloudy

S+R

WetGrass

P(C) = 0.5

S+RTTFFTFF

P(W|S+R) 0.990.90 0.90 0.00

CTF

P(S+R|C)TT TF FT FF

.08 .02 .72 .18 .40 .10 .40 .10

aus

wird