Transcript
Mitschriften zur Vorlesung Ku ¨ nstliche Intelligenz“ ” Sommersemester 2015 erstellt von:
Eric H¨ahner
9. Juli 2015
2
INHALTSVERZEICHNIS
Inhaltsverzeichnis 1 Pr¨ adikatenlogik 1.1 Rechenregeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 5
2 Prolog-Programmierung 2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Unterschied zwischen Prolog und imperativen Programmiersprachen 2.3 Behandlung von Existenzquantoren . . . . . . . . . . . . . . . . . . 2.4 Auswertestrategie von Prolog . . . . . . . . . . . . . . . . . . . . .
7 7 8 8 8
. . . .
. . . .
. . . .
3 Computeralgebra 11 3.1 Arithmetik in Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Sprachverarbeitung 13 4.1 Wertigkeit von Verben . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.2 Dialogsysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Probleml¨ osen durch Suche 5.1 Uninformierte Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Iterative Tiefensuche (IDDFS, iterative deepening depth-first search) 5.1.2 Planungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Informierte bzw. heuristische Suche . . . . . . . . . . . . . . . . . . . . . 5.2.1 Gierige Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 A∗ -Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.3 IDA∗ -Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Spiele mit Gegnern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Bewertungsfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 16 16 16 17 18 18 19 20 22
6 Schließen mit Unsicherheit 23 6.1 Bayes’sche Netze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.1.1 Semantik von Bayes-Netzen . . . . . . . . . . . . . . . . . . . . . 24 6.2 Algorithmus direktes Sampling . . . . . . . . . . . . . . . . . . . . . . . . 27
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
3
INHALTSVERZEICHNIS
1
Pr¨ adikatenlogik
Problem: Aussagenlogik ist wenig m¨achtig. Aussagen, die sich nicht formulieren lassen: Alle V¨ ogel k¨onnen fliegen. Wenn X eine Katze ist, dann ist X ein Haustier. F¨ ur jedes Land gibt es eine Hauptstadt.
In der Pr¨adikatenlogik betrachten wir zun¨achst eine (unwichtige) Menge U (Universum), die alle zu betrachtenden Objekte (V¨ogel, Katzen, L¨ander, ...) enth¨alt. Davon betrachten wir Teilmengen, z.B. die Menge aller V¨ogel (also eine einstellige Relation) oder die Menge aller Verheirateten (also eine mehrstellige Relation). Definition: Sei V eine Menge von Variablen, K eine Menge von Konstanten und F eine Menge von Funktionssymbolen. Dann sind alle Variablen in V und Konstanten in K Terme. Wenn t1 , ..., tn Terme und f ein n-stelliges Funktionssymbol sind, dann ist auch f (t1 , ..., tn ) ein Term.
Beispiel: V = {x, y, z}, K = {a, b, c}, F = {+, ∗} Terme sind x, y, a, x + a, (x + a) ∗ y, Definition: Sei eine Menge von Pr¨adikatensymbolen gegeben. Die Formeln der Pr¨adikatenlogik sind induktiv definiert: Wenn t1 , ..., tn Terme und P ein Pr¨ adikatensymbol der Stelligkeit n ist, dann ist P (t1 , ..., tn ) eine Formel. Wenn F, G Formeln sind, dann auch F ∧ G, F ∨ G, ¬F . Wenn x eine Variable und F eine Formel sind, dann auch ∀x F sowie ∃x F .
Wie in der Aussagenlogik sind die Operatoren →, ↔ definiert.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
Relation ist die Teilmenge aus dem Kreuzprodukt von Mengen. (R ⊆ Personen × Orte)
4
INHALTSVERZEICHNIS
Beispiel: katze(reni)
∀x ∀x katze(x) → haustier(x) Syntaxbaum dazu:
→
katze(x)
haustier(x) ∀x →
∀x land(x) → ∃y hauptstadt(x, y) Syntaxbaum dazu: ∃y
land(x)
hauptstadt(x, y) Semantik (informal): Den Pr¨adikatensymbolen m¨ ussen Relationen zugeordnet werden z.B. land = {deutschland, f rankreich, spanien, ...}. Wahrheitswert einer Formel: Die Formel P (t1 , ..., tn ) ist wahr, wenn (t1 , ..., tn ) ∈ P Die Wahrheit von F ∧ G, F ∨ G, ¬F ist wie in der Aussagenlogik definiert ∃x F ist wahr, wenn es ein x ∈ U gibt, so dass F f¨ ur dieses x wahr ist. ∀x F ist wahr, wenn f¨ ur alle x ∈ U F f¨ ur diese x wahr ist.
Beispiel: Symbole: vogel, f liegt Relationen: vogel = {amsel, drossel, f ink, star}, f liegt = vogel ∪ {maikaef er, A380} vogel(amsel) ist wahr ∃x vogel(x) ist wahr ∀x vogel(x) ist falsch. ∀x vogel(x) → f liegt(x) ist wahr
¬ h¨ochste Priorit¨at ∀, ∃ Vorrang der Operatoren: ∧, ∨ →, ↔ niedrigste Priorit¨at 9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
1.1
5
RECHENREGELN
Beispiel: land = {deutschland, england, f rankreich, spanien}, hauptstadt = {(deutschland, berlin), (england, london), (f rankreich, paris), (spanien, madrid)} ∀x (land(x) → ∃y hauptstadt(x, y))
1.1
Rechenregeln
¬∀x F ≡ ∃x ¬F ¬∃x F ≡ ∀x ¬F F¨ ur Q ∈ {∀, ∃} und ◦ ∈ {1, v} gilt (Q × F ) ◦ G ≡ Q × (F ◦ G), falls x in G nicht frei vorkommt. ∀x F ∧ ∀x G ≡ ∀x(F ∧ G) ∃x F ∨ ∃x G ≡ ∃x(F ∨ G) ∀x F ∨ ∀x G 6≡ ∀x(F ∨ G) ∃x F ∧ ∃x G 6≡ ∃x(F ∧ G)
Definition: Eine Aussage F ist in bereinigter Pr¨anexform, wenn F = Q1 y1 ...Qn yn G, wobei Qi ∈ {∀, ∃} und G keine Quantoren enth¨alt und y1 , ..., yn paarweise verschieden sind. F¨ ur jede Aussage gibt es eine ¨aquivalente Formel in bereinigter Pr¨anexform. Beispiel:
∀x land(x) → ∃y hauptstadt(x, y) ≡ ∀x ¬land(x) ∨ ∃y hauptstadt(x, y) ≡ ∀x ∃y hauptstadt(x, y) ∨ ¬land(x) ≡ ∀x∃y ¬land(x) ∨ hauptstadt(x, y) ≡ ∀x∃y land(x) → hauptstadt(x, y) ¬ ∀x vogel(x) → f liegt(x) ≡ ¬ ∀x ¬vogel(x) ∨ f liegt(x) ≡ ∃x¬ ¬vogel(x) ∨ f liegt(x) ≡ ∃x vogel(x) ∧ ¬f liegt(x)
9. Juli 2015
©
Eric H¨ ahner
Vorlesung K¨ unstliche Intelligenz SS15
1.1
6
RECHENREGELN
Definition: Ein Literal ist eine Atomformel oder eine negierte Atomformel. Eine Formel heißt Hornklausel, wenn sie eine ∨-Verkn¨ upfung von Literalen ist, von denen h¨ochstens eins positiv ist. Eine Hornformel ist eine ∧-Verkn¨ upfung von Hornklauseln.
Beispiel: Literale: P (x, y), ¬P (x, y), Q(2x) Hornklausel: ¬P (x, y) ∨ ¬Q(2x), ¬S(x) ∨ T (y) Wichtiger Spezialfall: Hornklauseln mit genau einem positiven Literal. Ein Literal: Fakt z.B. P (x, y) Mindestens zwei Literale: Dies l¨ asst sich als Implikation darstellen: ¬A1 ∨ ... ∨ ¬An−1 ∨ An ≡ ¬(A1 ∧ ... ∧ An−1 ) ∨ An ≡ A1 ∧ ... ∧ An−1 → An
Mit Hilfe von Hornklauseln lassen sich Regeln formulieren,z.B. ∀x katze(x) → haustier(x) , ∀x hund(x) → haustier(x) Wenn diese Hornklauseln mit ∧ verkn¨ upft werden, erhalten wir eine Hornformel. Diese Hornformel kann als Wissensbasis eines Expertensystems betrachtet werden. Anfrage Inferenzsystem Wissensbasis
9. Juli 2015
Antwort
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
2.1
7
SYNTAX
2
Prolog-Programmierung
Prolog: Programming in Logic. In den 70er und 80er Jahren als KI-Sprache entwickelt. Prolog-Programme sind im wesentlichen Hornformeln, bei denen alle Variablen allquantisiert sind und die in bereinigter Pr¨anexform vorliegen. Beispiel: 1 2
katze ( reni ) . haustier ( X ) : - katze ( X )
Dieses Prolog-Programm stellt die Hornformel katze(reni)∧∀x katze(x) → haustier(x) dar. Anfrage an Prolog: 1 2
2.1
? - haustier ( reni ) . true
Syntax
Pr¨adikat: Wort in Kleinbuchstaben (außerhalb einer Klammer) Konstante: Argument in Kleinbuchstaben Variablen: Wort, das mit Großbuchstaben beginnt ’←’: ’:-’ (wird impliziert von) ’∧’: ’,’ Jede Klausel wird mit ’.’ abgeschlossen. Das Programm ist eine Menge von Klauseln, die implizit mit ’∧’ verkn¨ upft sind (Hornformel). ∨-Verkn¨ upfung: Die Formel A ∨ B → C ist wegen A ∨ B → C ≡ ¬(A ∨ B) ∨ C ≡ (¬A ∧ ¬B) ∨ C keine Hornklausel. Da jedoch A∨B →C ≡ (¬A ∨ C) ∧ (¬B ∨ C) ≡ (A → C) ∧ (B → C) eine Hornformel ist, l¨asst sich A ∨ B → C in Prolog darstellen. ∨-Operator: ’;’ Beispiel: 1
haustier ( X ) : - katze ( X ) ; hund ( X )
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
2.2
UNTERSCHIED ZWISCHEN PROLOG UND IMPERATIVEN PROGRAMMIERSPRACHEN
2.2
8
Unterschied zwischen Prolog und imperativen Programmiersprachen
Eine Variable kann sowohl Eingabe als auch Ausgabe sein. Beispiel: 1 2
katze ( reni ) . katze ( mimi ) .
Anfrage: 1 2
1 2
1 2 3
2.3
? - katze ( reni ) true .
? - X = reni , katze ( X ) . true .
? - katze ( X ) . X = reni ; X = mimi .
Behandlung von Existenzquantoren
Da in Prolog alle Variablen allquantisiert sind, k¨onnen existenzquantifizierte Variablen nicht unmittelbar dargestellt werden. Existenzquantoren k¨onnen jedoch durch Skolemisierung eliminiert werden. Dazu wird die Formel zuerst in die bereinigte Pr¨anexform gebracht. Einfacher Spezialfall: Die Formel in bereinigter Pr¨anexform hat die Gestalt ∃x P (x). Diese kann erf¨ ullbarkeits¨aquivalent dargestellt werden durch P (a) wobei a eine noch nicht verwendete Konstante ist (Skolemkonstante). Weiterer Fall: Wenn die Formel die Gestalt P (x, y) besitzt, dann l¨asst sich diese ∀x∃y erf¨ ullbarkeits¨aquivalent darstellen durch P x, f (x) wobei f ein noch nicht verwendetes Funktionssymbol ist (Skolemfunktion).
2.4
Auswertestrategie von Prolog
Die Struktur eines Prolog-Programms l¨asst sich durch einen Und-Oder-Baum darstellen. Und-Verkn¨ upfung: 1
a(X) :- b(X), c(X), d(X).
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
2.4
9
AUSWERTESTRATEGIE VON PROLOG
a(X)
b(X)
c(X)
d(X)
F¨ ur die Anfrage a(X) werden die Teilziele b(X), c(X) und d(X) erzeugt, die alle wahr sein m¨ ussen. Oder-Verkn¨ upfung: 1
a(X) :- b(X); c(X); d(X).
a(X)
b(X)
c(X)
d(X)
Die Anfrage a(X) ist wahr genau dann, wenn eines der Teilziele b(X), c(X) oder d(X) wahr ist. Suche nach einer L¨osung (d.h. X ist nicht instantiiert): X wird nach unten weitergereicht, bis es auf einer Blattebene an eine Konstante gebunden wird, mit der das zugeh¨orige Teilziel wahr wird. Der so gefundene L¨osungskandidat wird dann nach oben propagiert und f¨ ur weitere Teilziele verwendet. a(X)
c(X) c(r)?
b(X)
b(r) X/r
...
Wenn mit dem gefundenen Kandidaten weitere, mit ∧ verkn¨ upfte Teilziele nicht erf¨ ullt werden, sucht Prolog nach weiteren L¨osungen. Dazu wird eine Tiefensuche mit Backtracking ausgef¨ uhrt.
...
¨ Beispiel: (Aufgabe 4, Ubung 1) Anfrage: nass(hochschulstraße) nass(hochschulstrasse)
strasse(hochschulstrasse, Y )
wahr
regnet(Y )
Y /dresden
strasse(hochschulstrasse, dresden)
regnet(dresden)
wahr
wahr
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
2.4
10
AUSWERTESTRATEGIE VON PROLOG
Definition: Zwei Atome P, Q heißen unifizierbar, wenn es eine Ersetzung der in P, Q vorkommenden Variablen gibt, so dass P ≡ Q. Beispiel: regnet(Y ), regnet(Dresden) sind unifizierbar durch Y /dresden. P (a, X, Y ), P (a, b, c) sind unifizierbar durch X/b, Y /c. P (X, X), P (a, b) sind nicht unifizierbar. Durchsuchen des Baumes: F¨ ur ein Ziel P wird das Prolog-Programm von oben nach unten durchsucht, bis eine linke Seite einer Klausel (Kopf) mit P unifiziert. Dadurch wird ein neues Ziel erzeugt. Wenn dieses neue Ziel false liefert, wird ein Backtracking ausgef¨ uhrt, indem eine weitere linke Seite gesucht wird, die mit dem Ziel unifiziert. Innerhalb jeder Klausel wird die rechte Seite von links nach rechts durchsucht. Problem bei der Tiefensuche: Beispiel: 1 2
zug (X , Y ) : - zug (Y , X ) . zug (1 ,2) .
Anfrage: 1
? - zug (2 ,1) .
Suchbaum: zug(2, 1) X/2, Y /1
zug(1, 2) X/1, Y /2
zug(2, 1) ... Die Auswertestrategie von oben nach unten l¨asst sich nutzen um ein if-else zu implementieren:
1 2
strasse ( regen , nass ) . strasse (X , trocken ) : - X \== regen .
3 4 5
? - strasse ( sonne , Y ) . Y = trocken .
9. Juli 2015
©
Eric H¨ ahner
Vorlesung K¨ unstliche Intelligenz SS15
3.1
11
ARITHMETIK IN PROLOG
3 3.1
Computeralgebra Arithmetik in Prolog
Arithmetische Ausdr¨ ucke werden mit dem Operator is“ ausgewertet. Dabei muss die ” rechte Seite instantiiert sein. Beispiel: 1 2 3 4 5 6
? - X is 3 + 4. X = 7. ? - 10 is 1 + 2. false . ? - 2 is 1 + X . Error .
Beispiel: Berechnung von n! 1 2
fac (0 ,1) . fac (N , M ) : - N1 is N -1 , fac ( N1 , F ) , M is N * F .
Vergleichsoperatoren == \== = \= =:= =\=
Bedeutung identisch nicht identisch unifizierbar nicht unifizierbar arithmetisch gleich arithmetisch ungleich
Beispiel p(X) == p(X) p(X) \== p(Y) p(X) = p(Y) p(X) \= q(X) 2 =:= 1 + 1 3 =\= 1 + 1
Prolog ist in der Lage mit Hilfe des Unifikationsoperators arithmetische Ausdr¨ ucke zu zerlegen, wobei die Priorit¨at der Operatoren beachtet wird. 1 2 3 4
? - x A ? - x A
+ = + =
3 * y = A + B. x, B = 3 * y. y + z = A + B. x + y, z = B.
Anwendung: Symbolisches Differenzieren 1 2 3 4 5 6
diff (X ,X ,1) . diff (C ,X ,0) : - atomic ( C ) , C \== X . diff ( -F ,X , - DF ) : - diff (F ,X , DF ) . diff ( C * F ,X , C * DF ) : - diff (C ,X ,0) , diff (F ,X , DF ) . diff ( F + G ,X , DF + DG ) : - diff (F ,X , DF ) , diff (G ,X , DG ) . diff ( F - G ,X , DF - DG ) : - diff (F ,X , DF ) , diff (G ,X , DG ) .
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
durch ¨ıs”werden Rechnungen ausgef¨ uhrt
3.2
12
LISTEN
Wie lassen sich Terme wie 1 ∗ x + 0 vereinfachen? Ansatz: Pr¨adikat s/2
s ist 2stellig
s (0 + A , A ) . s ( A + 0 , B ) : - s (A , B ) . s (1 * A , A ) . s(A * 1,A). s (0 * A , A ) . s(A * 0,A). s ( A + B , C ) : - number ( A ) , number ( B ) , C is A + B . % analog - ,* ,/ s ( A + B , C ) : - s (A , SA ) , s (B , SB ) , s ( SA + SB , C ) . % analog * s (A , A ) .
1 2 3 4 5 6 7 8 9 10 11
Idee: Mit dem Pr¨adikat s/2 werden die Terme rekursiv zerlegt, mit s0/2 werden elementare Vereinfachungen vorgenommen. Dadurch wird von oben nach unten ein Syntaxbaum aufgebaut und von unten nach oben vereinfacht.
3.2
Listen
Listen sind induktiv definiert.
H - Head, T - Tail
[ ] ist die leere Liste wenn H ein Element und T eine Liste sind, dann ist [H|T ] eine Liste, die aus H und den Elementen in T besteht.
Alternativ kann die Liste auch in der Form [x1 , ..., xn ] aufgeschrieben werden. Beispiele ur Listen: h f¨ i h i [a, b, c], a|[b, c] , a, b, c, 1, 2, [u, v] Beispiele f¨ ur ein Pr¨adikat auf einer Liste: member/2 member(X,[X|_]). member(X,[_|T]):- member(X,T). Suchbaum f¨ ur die Anfrage member(b,[a,b,c]).:
member(b, [a, b, c]) X/b, T /[b, c]
member(b, [b, c]) X/b
true Weiteres Listenpr¨adikat: append/3 append(L1,L2,L3) ist wahr genau dann, wenn die Verkettung der Listen L1, L2 gleich L3 ist.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
3.2
13
LISTEN
Beispiel: append([a,b,c],[d,e,f],L) liefert L=[a,b,c,d,e,f] append([1,2,3],L,[1,2,3,4,5]) liefert L=[4,5] append(L1,L2,[1,2,3]) liefert L1=[], L2=[1,2,3]; L1=[1],L2=[2,3];
4
usw.
Sprachverarbeitung
Beispielgrammatik: Satz
Nominalphrase
Verbalphrase
Artikel
Nomen
Verb
die
katze
jagt
Nominalphrase
Artikel
Nomen
die
maus
Zur Darstellung von Strings verwenden wir Listen, z.B. [die,katze,schlaeft]. Zur Darstellung der Grammatik verwenden wir einen Recursive-Decent-Parser. 1 2 3 4 5 6 7
satz ( In , Rest ) : - nominalphrase ( In , R ) , verbalphrase (R , Rest ) . nominalphrase ( In , Rest ) : - artikel ( In , R ) , nomen (R , Rest ) . verbalphrase ( In , Rest ) : - verb ( In , R ) , nominalphrase (R , Rest ) . artikel ( In , Rest ) : - match ( die , In , Rest ) . verb ( In , Rest ) : - match ( jagt , In , Rest ) . nomen ( In , Rest ) : - match ( katze , In , Rest ) , match ( maus , In , Rest ) . match (X ,[ X | Rest ] , Rest ) .
Beispiel: match(katze,[katze,schlaeft],R) liefert R = schlaeft. match(katze,[maus],R) liefert false.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
4.1
14
WERTIGKEIT VON VERBEN
Beispiel: Suchbaum f¨ ur die Anfrage nominalphrase([die,katze],[]). nominalphrase([die,katze],[]). In/[die, katze]
Rest/[ ]
artikel([die,katze],R)
nomen([katze],[])
match(die,[die,katze],R
match(katze,[katze],[]) true
R/[katze] match(die,[die,katze],[katze]) true
Genus-Kongruenz: Wenn das Nomen kater und der Artikel der in der obigen Grammatik eingef¨ ugt werden, k¨onnen auch grammatikalisch falsche S¨atze, wie [die,kater,jagt,der,maus] abgeleitet werden. L¨osung: nominalphrase ( In , Rest ) : - artikel ( In ,R , Genus ) , nomen (R , Rest , Genus ) artikel ( In , Rest , m ) : - match ( der , In , Rest ) . artikel ( In , Rest , f ) : - match ( die , In , Rest ) . nomen ( In , Rest , m ) : - match ( kater , In , Rest ) . nomen ( In , Rest , f ) : - match ( maus , In , Rest ) , match ( katze , In , Rest ) .
1 2 3 4 5
4.1
Wertigkeit von Verben
Zwei wichtige Klassen von Verben sind: intransitive Verben: Diese ziehen kein Objekt nach sich (z.B. laufen, schlafen). transitive Verben: Diese ben¨ otigen ein Objekt (z.B. sehen, fangen)
Das Verb bestimmt den Kasus des zugeh¨origen Objekts. Z.B. ben¨otigen die Verben jagen, fangen ein Akkusativobjekt (das Subjekt sieht wen oder was?).
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
4.2
15
DIALOGSYSTEME
4.2
Dialogsysteme
Drei wichtige Aufgaben eines Dialogsystems: Frage des Benutzers analysieren und den Sinn verstehen Antwort suchen Antwort konstruieren und dem Benutzer antworten.
Einfacher Ansatz, um die Frage des Benutzers zu verstehen: Grammatik f¨ ur m¨ogliche Fragen des Benutzers konstruieren, die Parameter f¨ ur die relevanten Bestandteile der Frage enth¨alt. Anwendbar f¨ ur einfach und gleichartig strukturierte Fragen, z.B. nach Zugverbindungen. Aus der analysierten Frage erzeugt das Dialogsystem eine interne Repr¨asentation und durchsucht damit eine Wissensbasis und erzeugt daraus die Antwort. place − question → (in|ε) (what|which) P lace1 is the P lace2 (on|in|locatedin|ε) P lace1 → street|town|city P lace2 → hotel|restaurant|shop
5
Probleml¨ osen durch Suche
Viele Probleme der K¨ unstlichen Intelligenz lassen sich auf eine systematische Suche in einem Wurzelbaum reduzieren. Problem: riesige Anzahl von Knoten in typischen Suchb¨aumen. Beispiel Schach: ca. 30 M¨oglichkeiten pro Halbzug. Bei 50 Halbz¨ ugen enth¨alt der Suchbaum 50 P d=0
30d =
3051 −1 30−1
≈ 7, 4 · 1073
Knoten. Bei 10000 Computer, die 109 Knoten/s erzeugen und durchsuchen k¨onnen, ergibt sich f¨ ur die Rechenzeit 2, 3 · 1053 Jahre.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
5.1
16
UNINFORMIERTE SUCHE
5.1
Uninformierte Suche
Bereits bekannt: Breiten- und Tiefensuche findall(X,P,L): sucht alle X, f¨ ur die P wahr ist, und erzeugt die Liste L. not(P): ist wahr genau dann, wenn P false liefert (Negation by Failure). Nachteil der Breitensuche: Exponentieller Speicherbedarf f¨ ur Suchb¨aume Nachteil der Tiefensuche, wenn bereits besuchte Knoten nicht gespeichert werden: Zyklen m¨oglich L¨osung: In der Tiefensuche werden nur die Knoten auf dem aktuellen Pfad gespeichert. Der Platzbedarf liegt dann in O(d), wobei d die L¨ange des aktuellen Pfades ist. Nachteile der Tiefensuche Der gefundene Weg ist nicht notwendig der k¨ urzeste Weg. Die Tiefensuche kann sich in unendlichen oder sehr langen Pfaden verlieren.
5.1.1
Iterative Tiefensuche (IDDFS, iterative deepening depth-first search)
Wir verwenden eine Tiefenschranke, die sukzessive erh¨oht wird, bis das Ziel gefunden wird. Da in einem Suchbaum mit Verzweigungsfaktor b > 1 fast alle Knoten Bl¨atter sind, f¨allt die meiste Rechenzeit zum Durchsuchen der Blattebene an. Durch eine genaue Rechnung l¨asst sich zeigen, dass die Laufzeit der iterativen Tiefensuche nur einen kleinen Faktor h¨oher ist, als die der Tiefensuche. 5.1.2
Planungsprobleme
Gegeben: Regeln, wie Zust¨ ande ver¨andert werden k¨onnen Startzustand, Zielzustand
Gesucht: Weg vom Start zum Ziel
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
5.2
17
INFORMIERTE BZW. HEURISTISCHE SUCHE
Beispiel: Affe-Banane-Problem
Ausganssituation: Affe an der T¨ ur, Banane in der Mitte an der Decke, Stuhl am Fenster Regeln: Affe kann herumlaufen Repr¨asentation eines Zustands (Knoten des Graphen): Position des Affens Position des Stuhls Position der Banane Affe auf Stuhl
Positionen: T¨ ur, Mitte, Fenster Die Kanten sind durch Regeln gegeben.
5.2
Informierte bzw. heuristische Suche
Ziel: Informationen u ¨ber das Suchproblem nutzen, um schneller zum Ziel zu kommen. Dazu wird eine Bewertungsfunktion f¨ ur die Knoten verwendet. Die heuristische Suche verwendet eine heuristische Bewertungsfunktion f : V → R+ 0. F¨ ur den Zielknoten v gilt: f (v) = 0. Die Knoten mit der niedrigsten Bewertung werden zuerst verfolgt.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
5.2.1
18
GIERIGE SUCHE
5.2.1
Gierige Suche
Die gierige Suche verwendet in jedem Schritt den Knoten, der dem Ziel am n¨achsten liegt bzw. der die g¨ unstigste Entfernungssch¨atzung bis zum Ziel hat. Beispiel: Suche nach Wegen zu einem Ort. Heuristische Bewertungsfunktion: f (s) = Luftlinienentfernung von s zum Ziel. A 90km 110km
B
C 10km
1km
Z Die k¨ urzeste Strecke von A nach Z ist A − B − Z (100km). Wenn f (C) < f (B), findet die gierige Suche jedoch die Strecke A − C − Z, die 11km l¨anger ist. Folgerung: Die gierige Suche ist nicht optimal. 5.2.2
A∗ -Suche
Die gierige Suche ber¨ ucksichtigt nicht die Kosten, die bis zum Knoten s bereits entstanden sind. Wir f¨ uhren daher eine Funktion g ein, die diese Kosten angibt und eine Funktion h, die die Kosten bis zum Ziel sch¨atzt. Damit definieren wir die heuristische Bewertungsfunktion f durch f (s) = g(s) + h(s). Obige gierige Suche ist der Spezialfall g(s) = 0, h(s) = Luftlinienentfernung bis zum Ziel. Definition: Eine heuristische Kostensch¨atzfunktion h heißt zul¨assig, wenn h die Kosten bis zum Ziel nie u ¨bersch¨atzt. D.h. es gilt stets h(s) ≤ tats¨achliche Entfernung von s bis zum Ziel. Die A∗ -Suche ist folgender Algorithmus: F¨ ur den aktuellen Knoten v werden die noch unbesuchten Nachbarn bestimmt und anhand ihrer heuristischen Bewertungsfunktion f , die wie oben konstruiert sein muss, in eine geeignete Datenstruktur eingef¨ ugt. In jedem Schritt wird die Suche mit einem Knoten mit minimaler Bewertung weiter gef¨ uhrt. Naive Implementierung: Wie bei der Breitensuche werden die noch zu besuchenden Knoten in einer Liste gespeichert. Diese wird anhand der f -Werte der Knoten sortiert, so dass am Kopf der Liste ein Knoten mit minimaler Bewertung steht. 9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
5.2.3
19
IDA∗ -SUCHE
Effiziente Implementierung der A∗ -Suche: Ein Min-Heap ist ein Bin¨arbaum mit der Eigenschaft: Jeder Knoten besitzt einen Wert, der ≤ der Werte seiner Nachfolger ist. Beispiel: 1 3
5
8
6
7
Die A∗ -Suche ist optimal, vorausgesetzt, die Kostensch¨atzfunktion h ist zul¨assig. Vorteil der A∗ -Suche: Bei guter Heuristik wird das Ziel oft deutlich schneller gefunden als mit einer uninformierten Suche. Nachteil: Wie bei der Breitensuche m¨ ussen im Worst-Case alle Knoten im Speicher gehalten werden. 5.2.3
IDA∗ -Suche
Ziel: Vorteile der A∗ -Suche mit denen der iterativen Tiefensuche kombinieren. Dazu f¨ uhren wir eine Schranke f¨ ur die heuristische Bewertungsfunktion f ein und erh¨ohen diese schrittweise.
Anwendung: 8-Puzzle 1 4 7
2 5 8
3 6
Darstellung als Graph: Knoten: Brettstellungen Kanten geben an, wie durch Verschieben eines Pl¨attchens eine neue Brettstellung erreicht werden kann. Darstellung einer Brettstellung in Prolog: Jede Zeile ist eine Liste aus drei Elementen, das Brett eine Liste aus drei Zeilen.
9. Juli 2015
R1 R2 X
1 4 9
A1 D1 G1
B1 E1 H1
2 5 7
3 6 8
C1 F1 I1
©
1 4 7
2 5 9
A1 B1 C1
3 6 8
D1 E1 F1
y H1 H1 I1
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
5.3
20
SPIELE MIT GEGNERN
Geeignete Heuristiken fu ¨ r die Suche im 8-Puzzle: 1. Hamming-Distanz: Anzahl der Pl¨attchen, die falsch stehen. Diese Heuristik ist zul¨assig, weil mindestens so viele Verschiebungen notwendig sind, wie Pl¨attchen falsch stehen. 2. Manhattan- oder Cityblock-Distanz: Anzahl an Verschiebungen, die n¨otig sind um ein Pl¨attchen auf direktem Weg zum Ziel zu schieben, summiert u ur ¨ber alle Pl¨attchen. Diese Heuristik ist zul¨assig, da f¨ jedes Pl¨attchen mindestens diese Anzahl an Verschiebungen n¨otig ist.
5.3
Spiele mit Gegnern
Wir bewerten Stellungen durch eine Nutzenfunktion. Es gibt zwei Spieler: Max: Max versucht die Nutzenfunktion zu maximieren. Min: Min versucht die Nutzenfunktion zu minimieren.
Einfachster Fall einer Nutzenfunktion: 1: Max hat gewonnen 0: Unentschieden -1: Min hat gewonnen.
Die Nutzenfunktion l¨asst sich im Allgemeinen nur f¨ ur Endzust¨ande des Spiels berechnen. Beispiel: Tic-Tac-Toe Max(x) hat am Anfang 9 M¨oglichkeiten das Kreuz zu setzen. Danach hat Min(o) 8 M¨oglichkeiten einen Kreis zu setzen, usw. x Endzust¨ande:
o x o x o -1
x o x
o o x 0
x x o
x
x o o 1
x
Da wir nicht wissen wie der Gegner zieht, betrachten wir alle m¨oglichen Z¨ uge des Gegners und nehmen an, dass dieser optimal spielt. Damit berechnen wir einen Nutzwert f¨ ur jeden Knoten (minimax-value). Dieser ergibt sich als: Maximum der Bewertungen der Nachfolgeknoten, wenn Max am Zug ist. Minimum der Bewertungen der Nachfolgeknoten, wenn Min am Zug ist.
Daraus erhalten wir eine rekursive Formel, um minimax zu berechnen: n ist ein Endzustand utility(n) minimax(n) := max{minimax(s)|s ∈ Succ(n)} n ist ein Maxknoten min{minimax(s)|s ∈ Succ(n)} n ist ein Minknoten Dabei sei Succ(n) die Menge der Nachfolger des Knotens n im Suchbaum. 9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
5.3
21
SPIELE MIT GEGNERN
Beispiel: M: Max O: Min 3 M
3 O
2 O
2 O
M
M
M
M
M
M
M
M
M
3
12
8
2
4
6
14
5
2
Die minimax-Werte lassen sich mit einer Tiefensuche berechnen. Laufzeit dazu: O(bd ), wenn der Suchbaum die Tiefe d und den Verzweigungsfaktor b besitzt. Nachteil dieser Art der Berechnung: Es m¨ ussen alle Knoten erzeugt und deren minimax-Werte berechnet werden. Wir k¨onnen Rechenzeit einsparen, wenn Knoten ausgelassen werden, deren minimax-Werte keine Auswirkungen auf den aktuellen Knoten haben. [3, 3], α = 3 M [3, 3], β = 3 O
[−∞, 2], β = 2 O
M
M
M
M
3
12
8
2
M
[2, 2], β = 2 O
M
M
M
M
14
5
2
Im Laufe der Berechnung werden folgende Werte aktualisiert: α-Wert: Untere Grenze des minimax-Wertes eines Max-Knotens. Der α-Wert bleibt gleich oder wird gr¨oßer. β-Wert: Obere Grenze des minimax-Wertes eines Min-Knotens. Der β-Wert bleibt gleich oder wird kleiner.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
5.4
22
BEWERTUNGSFUNKTIONEN
In 2 F¨allen kann der Suchbaum beschnitten werden: Ist der β-Wert eines Min-Knotens ≤ α-Wert des dar¨ uber liegenden Max-Knotens, dann muss der Min-Knoten nicht weiter untersucht werden.
β α≥β O
O M O
O
Ist der α-Wert≥ β-Wert, dann muss der Max-Knoten nicht weiter untersucht werden.
α M β≤α O M
M
M
Die Effizienz dieser α − β−K¨ urzung ist abh¨angig von der Reihenfolge, in der die Knoten besucht werden. Zuerst gute Knoten besuchen, z.B. Schach. Erst W¨ urfe pr¨ ufen, dann Bedrohungen, dann d Vorw¨artsz¨ uge, zuletzt R¨ uckw¨artsz¨ uge. Im besten Fall ist die Laufzeit O(b 2 ).
5.4
Bewertungsfunktionen
F¨ ur Spiele wie Schach ist auch die Laufzeit der α − β-Suche zu groß. Die Suche wird daher abgebrochen, bevor ein Endknoten erreicht wird. Innere Knoten werden dazu mit einer Funktion bewertet, z.B. #Bauer + 3 ∗ #Laeuf er + 5 ∗ #T uerme + 3 ∗ #Springer + 9 ∗ #Damen.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
6.1
23
BAYES’SCHE NETZE
6 6.1
Schließen mit Unsicherheit Bayes’sche Netze
Beispiel: Bob hat in seinem Haus eine Alarmanlage installiert. Seine Nachbarn John und Mary rufen ihn im B¨ uro an, wenn sie den Alarm h¨oren. Bob modelliert derern Zuverl¨assigkeit durch P (J|Al) = 0, 9 P (J|Al) = 0, 05
P (M |Al) = 0, 7 P (M |Al) = 0, 01
Aber auch durch ein Erdbeben kann der Alarm ausgel¨ost werden (Einbruch,Erdbeben): P (Al|Ein, Erd) = 0, 95 P (Al|Ein, Erd) = 0, 94 P (Al|Ein, Erd) = 0, 29 P (Al|Ein, Erd) = 0, 001 Ferner sei P (Ein) = 0, 001, P (Erd) = 0, 002. Ein, Erd seien unabh¨angig. Graphische Darstellung als Bayes-Netz P (Ein) 0,001
Einbruch
Alarm
Al w f
P (J) 0,9 0,05
Erdbeben
P (Erd) 0,002
Ein w w f f
P (Al) 0,95 0,94 0,29 0,001
Erd w f w f
Mary
John
Al w f
P (M ) 0,7 0,01
Wenn John und Mary unabh¨angig auf einen Alarm reagieren, gilt: P (J, M |Al) = P (J|Al) · P (M |Al) Wenn wir annehmen, dass John nicht auf einen Einbruch, sondern nur auf einen Alarm reagiert, gilt ferner P (J, Ein|Al) = P (J|Al) · P (Ein|Al)
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
6.1.1
24
SEMANTIK VON BAYES-NETZEN
6.1.1
Semantik von Bayes-Netzen
Kanten beschreiben (bedingte) Unabh¨angigkeit von Ereignissen: A und B sind unabh¨angig: A
B
C A, B sind unabh¨angig, gegeben C: C
A
B
Ein Bayes-Netz muss ein DAG sein. Dann k¨onnen die Knoten topologisch sortiert werden. Dann gilt: P (An |A1 , ..., An−1 ) = P (An |Eltern(An )) Es folgt: P (A1 , ..., An ) = P (An |A1 , ..., An−1 ) · P (A1 , ..., An−1 ) = P (An |A1 , ..., An−1 ) · P (An−1 |A1 , .., An−2 ) · P (A1 , .., An−2 ) = ... = n Y P (Ai |A1 , ..., Ai−1 ) = i=1
(wobei P (A1 |A1 , ..., A0 ) := P (A1 )) n Y P (Ai |Eltern(Ai )) i=1
¨ Berechne P (J, Al, Ein, Erd) U: P (J, Al, Ein, Erd) = P (J|Al) · P (Al|Ein, Erd) · P (Ein) · P (Erd) = 0, 9 · 0, 95 · 0, 001 · 0, 002 = 1, 7 · 10−6 ¨ Berechne P (J, Ein) U: F¨ ur disjunkte Ereignisse A1 , ..., An gilt: P
P n
P n Ai = P (Ai )
i=1
9. Juli 2015
©
Eric H¨ ahner
i=1
Vorlesung K¨ unstliche Intelligenz SS15
6.1.1
25
SEMANTIK VON BAYES-NETZEN
Disjunkte Zerlegung: P (A) = P (A ∩ B + A ∩ B) = P (A, B) + P (A, B) P (J, Ein) = P (J, Al, Ein, Erd)+ P (J, Al, Ein, Erd)+ P (J, Al, Ein, Erd)+ P (J, Al, Ein, Erd) = 0, 000849 Ebenso: P (J) = 0, 052 Damit ergibt sich P (Ein|J) = Ebenso: P (Ein|J, M ) =
P (Ein,J) P (J)
P (Ein|J,M ) P (J,M )
= 0, 016
= 0, 284
Definition: Eine Sprache L heißt NP-vollst¨andig, wenn L ∈ NP L NP-hart
ist. NP-hart bedeutet, dass jedes Problem in NP effizient u ¨bersetzt werden kann in ein Entscheidungsproblem f¨ ur L. Die exakte Inferenz in Bayes’schen Netzen ist NP-hart. Eines der klassischen NP-vollst¨andigen Probleme ist 3KN F − SAT ={F |F ist eine Formel in konjunktiver Normalform (KNF) mit 3 Literalen pro Klausel und F ist erf¨ ullbar}. Beispiel f¨ ur eine Formel in 3KNF-SAT: (A ∨ B ∨ ¬C) ∧ (¬A ∨ B ∨ ¬D) Ein Algorithmus f¨ ur die exakte Inferenz in Bayes’schen Netzen (Berechnung von Wahrscheinlichkeiten) l¨asst sich nutzen, um 3KNF-SAT zu entscheiden. Beispiel: F = (A ∨ B ∨ C) ∧ (C ∨ D ∨ ¬A) ∧ (B ∨ C ∨ ¬D) Aus dieser Formel l¨asst sich folgendes Bayes’sches Netz erzeugen:
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
6.1.1
26
SEMANTIK VON BAYES-NETZEN
1 2
1 2
1 2
1 2
A
B
C
D
¬ ¬ 1
2
3
∧ Der Knoten 2 besitzt folgende bedingte Wahrscheinlichkeiten: C f f f f w w w w
D f f w w f f w w
A f w f w f w f w
P (2) 1 0 1 1 1 1 1 1
Der Knoten 1 besitzt die bedingten Wahrscheinlichkeiten: 1 f f ... w
2 f f ... w
3 f w ... w
P (1) 0 0 0 1
Dann gilt: F ist erf¨ ullbar ⇔ P (1) > 0. Da die exakte Inferenz in Bayes’schen Netzen NP-hart ist, gibt es keinen effizienten (d.h. polynomiellen) Algorithmus zur Berechnung der Wahrscheinlichkeiten. Ausweg: Approximative Inferenz. Gegeben sei eine Verteilung, wie kann man Stichproben daraus ziehen? Beispiel: W¨ urfel 6 Ausf¨allt, Verteilung ist
1 1 1 1 1 1 , , , , , 6 6 6 6 6 6 1 6
0 1
9. Juli 2015
2 6
2
3 6
3
4 6
4
©
5 6
5
6 6
6
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
6.2
27
ALGORITHMUS DIREKTES SAMPLING
6.2
Algorithmus direktes Sampling
Voraussetzung: Netz ist topologisch sortiert 1 2 3 4
for i =1 to n Erzeuge einen Wert f¨ u r P ( Xi | Eltern ( Xi ) ) gem¨ a ß der bedingten Verteilung von Xi , gegeben die bereits erzeugten Werte f¨ u r Eltern ( Xi ) .
Auf diese Weise wird eine Stichprobe (x1 , ..., xn ) erzeugt. Korrektheit des Verfahrens: n Q P (x1 , ..., xn ) = P Xi |Eltern(Xi ) i=1
Dies ist die Wahrscheinlichkeit der Verteilung gem¨aß der Formel aus letzter Vorlesung. Beispiel: 0,5
0,5
A
B A B w w w f f w f f
C
P (C) 0,9 0,4 0,3 0,1
Berechnen von bedingten Wahrscheinlichkeiten: Ablehnungs-Sampling 1 2 3 4 5
for i =1 to k erzeuge eine Stichprobe x mit dem Algorithmus direktes Sampling Verwerfe x , wenn x nicht konsistent ist mit der Bedingung e , f¨ u r die P ( X | e ) berechnet werden soll
Berechne, wie oft das Ereignis X in den nicht verworfenen Samples vorkommt. Der Algorithmus Ablehnungs-Sampling ist ungeeignet, wenn P (e) klein ist. F¨ ur e = e1 , ..., en gilt insbesondere, dass P (e) exponentiell kleiner wird.
9. Juli 2015
©
Vorlesung K¨ unstliche Intelligenz SS15
Eric H¨ ahner
