Mitschriften zur Vorlesung
Künstliche Intelligenz“
”
Sommersemester 2015
erstellt von:
Eric Hähner
9. Juli 2015
2
INHALTSVERZEICHNIS
Inhaltsverzeichnis
1 Prädikatenlogik
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ösen 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ünstliche Intelligenz SS15
Eric Hähner
3
INHALTSVERZEICHNIS
1
Prädikatenlogik
Problem: Aussagenlogik ist wenig mächtig. Aussagen, die sich nicht formulieren lassen:
Alle Vögel können fliegen.
Wenn X eine Katze ist, dann ist X ein Haustier.
Für jedes Land gibt es eine Hauptstadt.
In der Prädikatenlogik betrachten wir zunächst eine (unwichtige) Menge U (Universum),
die alle zu betrachtenden Objekte (Vögel, Katzen, Länder, ...) enthält. Davon betrachten wir Teilmengen, z.B. die Menge aller Vögel (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ädikatensymbolen gegeben. Die Formeln der Prädikatenlogik sind
induktiv definiert:
Wenn t1 , ..., tn Terme und P ein Prädikatensymbol 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ünstliche Intelligenz SS15
Eric Hähner
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ädikatensymbolen müssen 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ür dieses x wahr ist.
∀x F ist wahr, wenn für alle x ∈ U F für 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öchste Priorität
∀, ∃
Vorrang der Operatoren:
∧, ∨
→, ↔ niedrigste Priorität
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
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ür 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änexform, wenn F = Q1 y1 ...Qn yn G, wobei
Qi ∈ {∀, ∃} und G keine Quantoren enthält und y1 , ..., yn paarweise verschieden sind.
Für jede Aussage gibt es eine äquivalente Formel in bereinigter Pränexform.
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ähner
Vorlesung Künstliche 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üpfung von Literalen ist, von
denen höchstens eins positiv ist.
Eine Hornformel ist eine ∧-Verknüpfung 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ässt 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üpft werden, erhalten wir eine Hornformel. Diese
Hornformel kann als Wissensbasis eines Expertensystems betrachtet werden.
Anfrage
Inferenzsystem
Wissensbasis
9. Juli 2015
Antwort
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
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änexform 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ädikat: 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üpft sind (Hornformel).
∨-Verknüpfung: 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ässt sich A ∨ B → C in Prolog darstellen.
∨-Operator: ’;’
Beispiel:
1
haustier ( X ) : - katze ( X ) ; hund ( X )
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
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önnen existenzquantifizierte Variablen
nicht unmittelbar dargestellt werden. Existenzquantoren können jedoch durch Skolemisierung eliminiert werden. Dazu wird die Formel zuerst in die bereinigte Pränexform
gebracht.
Einfacher Spezialfall: Die Formel in bereinigter Pränexform hat die Gestalt ∃x P (x).
Diese kann erfüllbarkeitsäquivalent 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ässt sich diese
∀x∃y erfüllbarkeitsäquivalent 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ässt sich durch einen Und-Oder-Baum darstellen.
Und-Verknüpfung:
1
a(X) :- b(X), c(X), d(X).
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
2.4
9
AUSWERTESTRATEGIE VON PROLOG
a(X)
b(X)
c(X)
d(X)
Für die Anfrage a(X) werden die Teilziele b(X), c(X) und d(X) erzeugt, die alle wahr
sein müssen.
Oder-Verknüpfung:
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ösung (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örige Teilziel wahr wird. Der so gefundene Lösungskandidat
wird dann nach oben propagiert und für weitere Teilziele verwendet.
a(X)
c(X) c(r)?
b(X)
b(r) X/r
...
Wenn mit dem gefundenen Kandidaten
weitere, mit ∧ verknüpfte Teilziele nicht
erfüllt werden, sucht Prolog nach weiteren
Lösungen. Dazu wird eine Tiefensuche mit
Backtracking ausgeführt.
...
Beispiel: (Aufgabe 4, Übung 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ünstliche Intelligenz SS15
Eric Hähner
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ür 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ührt, 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ässt 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ähner
Vorlesung Künstliche Intelligenz SS15
3.1
11
ARITHMETIK IN PROLOG
3
3.1
Computeralgebra
Arithmetik in Prolog
Arithmetische Ausdrücke 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ücke zu
zerlegen, wobei die Priorität 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ünstliche Intelligenz SS15
Eric Hähner
durch
ı̈s”werden
Rechnungen
ausgeführt
3.2
12
LISTEN
Wie lassen sich Terme wie 1 ∗ x + 0 vereinfachen?
Ansatz: Prädikat 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ädikat 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
h für Listen:
i h
i
[a, b, c], a|[b, c] , a, b, c, 1, 2, [u, v]
Beispiele für ein Prädikat auf einer Liste: member/2
member(X,[X|_]).
member(X,[_|T]):- member(X,T).
Suchbaum für 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ädikat: 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ünstliche Intelligenz SS15
Eric Hähner
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ünstliche Intelligenz SS15
Eric Hähner
4.1
14
WERTIGKEIT VON VERBEN
Beispiel:
Suchbaum für 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ügt werden, können auch grammatikalisch falsche Sätze, wie [die,kater,jagt,der,maus] abgeleitet werden.
Lösung:
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ötigen ein Objekt (z.B. sehen, fangen)
Das Verb bestimmt den Kasus des zugehörigen Objekts. Z.B. benötigen die Verben jagen,
fangen ein Akkusativobjekt (das Subjekt sieht wen oder was?).
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
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ür mögliche Fragen des Benutzers konstruieren, die Parameter für die relevanten Bestandteile der Frage enthält. Anwendbar für einfach und gleichartig strukturierte Fragen, z.B. nach Zugverbindungen. Aus der analysierten Frage erzeugt das
Dialogsystem eine interne Repräsentation 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ösen durch Suche
Viele Probleme der Künstlichen Intelligenz lassen sich auf eine systematische Suche in
einem Wurzelbaum reduzieren.
Problem: riesige Anzahl von Knoten in typischen Suchbäumen.
Beispiel Schach: ca. 30 Möglichkeiten pro Halbzug. Bei 50 Halbzügen enthält 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önnen, ergibt sich
für die Rechenzeit 2, 3 · 1053 Jahre.
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
5.1
16
UNINFORMIERTE SUCHE
5.1
Uninformierte Suche
Bereits bekannt: Breiten- und Tiefensuche
findall(X,P,L): sucht alle X, für 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ür Suchbäume
Nachteil der Tiefensuche, wenn bereits besuchte Knoten nicht gespeichert werden: Zyklen möglich
Lösung:
In der Tiefensuche werden nur die Knoten auf dem aktuellen Pfad gespeichert. Der
Platzbedarf liegt dann in O(d), wobei d die Länge des aktuellen Pfades ist.
Nachteile der Tiefensuche
Der gefundene Weg ist nicht notwendig der kürzeste 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öht wird, bis das Ziel gefunden
wird. Da in einem Suchbaum mit Verzweigungsfaktor b > 1 fast alle Knoten Blätter
sind, fällt die meiste Rechenzeit zum Durchsuchen der Blattebene an. Durch eine genaue
Rechnung lässt sich zeigen, dass die Laufzeit der iterativen Tiefensuche nur einen kleinen
Faktor höher ist, als die der Tiefensuche.
5.1.2
Planungsprobleme
Gegeben:
Regeln, wie Zustände verändert werden können
Startzustand, Zielzustand
Gesucht: Weg vom Start zum Ziel
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
5.2
17
INFORMIERTE BZW. HEURISTISCHE SUCHE
Beispiel: Affe-Banane-Problem
Ausganssituation: Affe an der Tür, Banane in der Mitte an der Decke, Stuhl am Fenster
Regeln: Affe kann herumlaufen
Repräsentation eines Zustands (Knoten des Graphen):
Position des Affens
Position des Stuhls
Position der Banane
Affe auf Stuhl
Positionen: Tür, Mitte, Fenster
Die Kanten sind durch Regeln gegeben.
5.2
Informierte bzw. heuristische Suche
Ziel: Informationen über das Suchproblem nutzen, um schneller zum Ziel zu kommen.
Dazu wird eine Bewertungsfunktion für die Knoten verwendet. Die heuristische Suche
verwendet eine heuristische Bewertungsfunktion f : V → R+
0.
Für den Zielknoten v gilt: f (v) = 0. Die Knoten mit der niedrigsten Bewertung werden
zuerst verfolgt.
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
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ächsten
liegt bzw. der die günstigste Entfernungsschätzung 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ürzeste 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änger ist.
Folgerung: Die gierige Suche ist nicht optimal.
5.2.2
A∗ -Suche
Die gierige Suche berücksichtigt nicht die Kosten, die bis zum Knoten s bereits entstanden sind. Wir führen daher eine Funktion g ein, die diese Kosten angibt und eine
Funktion h, die die Kosten bis zum Ziel schätzt. 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ätzfunktion h heißt zulässig, wenn h die Kosten bis zum Ziel
nie überschätzt. D.h. es gilt stets h(s) ≤ tatsächliche Entfernung von s bis zum Ziel.
Die A∗ -Suche ist folgender Algorithmus:
Für 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ügt. In jedem Schritt wird die Suche mit einem Knoten mit minimaler Bewertung weiter geführt.
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ünstliche Intelligenz SS15
Eric Hähner
5.2.3
19
IDA∗ -SUCHE
Effiziente Implementierung der A∗ -Suche:
Ein Min-Heap ist ein Binärbaum 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ätzfunktion h ist zulässig.
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üssen 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ühren wir eine Schranke für die heuristische Bewertungsfunktion f ein und erhöhen
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ättchens 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ünstliche Intelligenz SS15
Eric Hähner
5.3
20
SPIELE MIT GEGNERN
Geeignete Heuristiken für die Suche im 8-Puzzle:
1. Hamming-Distanz:
Anzahl der Plättchen, die falsch stehen.
Diese Heuristik ist zulässig, weil mindestens so viele Verschiebungen notwendig
sind, wie Plättchen falsch stehen.
2. Manhattan- oder Cityblock-Distanz:
Anzahl an Verschiebungen, die nötig sind um ein Plättchen auf direktem Weg zum
Ziel zu schieben, summiert über alle Plättchen. Diese Heuristik ist zulässig, da für
jedes Plättchen mindestens diese Anzahl an Verschiebungen nötig 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ässt sich im Allgemeinen nur für Endzustände des Spiels berechnen.
Beispiel: Tic-Tac-Toe
Max(x) hat am Anfang 9 Möglichkeiten das Kreuz zu setzen. Danach hat Min(o) 8
Möglichkeiten einen Kreis zu setzen, usw.
x
Endzustände:
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öglichen Züge des Gegners und nehmen an, dass dieser optimal spielt. Damit berechnen wir einen Nutzwert
für 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ünstliche Intelligenz SS15
Eric Hähner
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üssen alle Knoten erzeugt und deren
minimax-Werte berechnet werden. Wir können 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ößer.
β-Wert: Obere Grenze des minimax-Wertes eines Min-Knotens. Der β-Wert bleibt
gleich oder wird kleiner.
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
5.4
22
BEWERTUNGSFUNKTIONEN
In 2 Fällen kann der Suchbaum beschnitten werden:
Ist der β-Wert eines Min-Knotens ≤ α-Wert des darüber 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ürzung ist abhängig von der Reihenfolge, in der die Knoten
besucht werden.
Zuerst gute Knoten besuchen, z.B. Schach. Erst Würfe prüfen, dann Bedrohungen, dann
d
Vorwärtszüge, zuletzt Rückwärtszüge. Im besten Fall ist die Laufzeit O(b 2 ).
5.4
Bewertungsfunktionen
Für 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ünstliche Intelligenz SS15
Eric Hähner
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üro an, wenn sie den Alarm hören. Bob modelliert derern Zuverlässigkeit
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öst 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ängig.
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ängig 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ünstliche Intelligenz SS15
Eric Hähner
6.1.1
24
SEMANTIK VON BAYES-NETZEN
6.1.1
Semantik von Bayes-Netzen
Kanten beschreiben (bedingte) Unabhängigkeit von Ereignissen:
A und B sind unabhängig:
A
B
C
A, B sind unabhängig, gegeben C:
C
A
B
Ein Bayes-Netz muss ein DAG sein. Dann können 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)
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)
Für disjunkte Ereignisse A1 , ..., An gilt: P
P
n
P
n
Ai =
P (Ai )
i=1
9. Juli 2015
©
Eric Hähner
i=1
Vorlesung Künstliche 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ändig, wenn
L ∈ NP
L NP-hart
ist.
NP-hart bedeutet, dass jedes Problem in NP effizient übersetzt werden kann in ein
Entscheidungsproblem für L.
Die exakte Inferenz in Bayes’schen Netzen ist NP-hart.
Eines der klassischen NP-vollständigen Probleme ist
3KN F − SAT ={F |F ist eine Formel in konjunktiver Normalform (KNF)
mit 3 Literalen pro Klausel und F ist erfüllbar}.
Beispiel für eine Formel in 3KNF-SAT:
(A ∨ B ∨ ¬C) ∧ (¬A ∨ B ∨ ¬D)
Ein Algorithmus für die exakte Inferenz in Bayes’schen Netzen (Berechnung von Wahrscheinlichkeiten) lässt sich nutzen, um 3KNF-SAT zu entscheiden.
Beispiel:
F = (A ∨ B ∨ C) ∧ (C ∨ D ∨ ¬A) ∧ (B ∨ C ∨ ¬D)
Aus dieser Formel lässt sich folgendes Bayes’sches Netz erzeugen:
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
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üllbar ⇔ 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ürfel
6 Ausfällt, 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ünstliche Intelligenz SS15
Eric Hähner
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ür P ( Xi | Eltern ( Xi ) )
gemäß der bedingten Verteilung von Xi , gegeben
die bereits erzeugten Werte fü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äß 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ü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ür e = e1 , ..., en gilt insbesondere, dass P (e) exponentiell kleiner wird.
9. Juli 2015
©
Vorlesung Künstliche Intelligenz SS15
Eric Hähner
© Copyright 2024 ExpyDoc
