Intelligente Systeme · Folien basieren auf Russell und Norvig: Künstliche Intelligenz: Ein...

Intelligente Systeme��

Suche ���

Michael Schroeder�www.biotec.tu-dredsen.de/schroeder�

Lehrbuch

Folien basieren auf��Russell und Norvig: �Künstliche Intelligenz: �Ein Moderner Ansatz. �

Dank an Prof. Fürnkranz �für die Folienvorlagen

By Michael Schroeder, Biotec 2

Graphen und Netzwerke§  Facebook: Bekanntschaften§  Dbpedia: Wissensnetz (Subjekt-Prädikat-Objekt Tripel)§  Google: Wissensnetz (aus Webseiten)§  GoPubMed: Hierarchie von Konzepten§  IBM deep blue: Schachspiel als Baum§  Navigationssysteme: Straßennetz§  NASA Deep Space One: Netzwerk aus Komponenten

§  Software Engineering: Zustandsdiagramme§  Automatentheorie: Transitionssysteme§  Bioinformatik: Proteininteraktionsnetze§  Ökologie: Räuber-Beute Netze§  Elektrotechnik: Schaltkreise

By Michael Schroeder, Biotec 3

Graph G=(V,E)

§  Graph: §  Ist V eine Menge von Knoten (Vertices, Einzahl Vertex) und §  E VxV eine Menge von Kanten (Edges),

dann ist G=(V,E) ein Graph

§  Baum (Graph ohne Kreise)§  Gerichteter Graph

§  Gewichteter Graph

By Michael Schroeder, Biotec 4

Zustandsraum

§  Zustand, Startzustand, Endzustand§  Aktionen, Zustandsübergang

By Michael Schroeder, Biotec 5

Problemmodellierung

§  Navigation§  Roboter§  Schiebepuzzle

§  Damenproblem

§  Entitätenerkennung (HMM)

§  Relationsextraktion (Multiples Sequenzalignment)

By Michael Schroeder, Biotec 6

Problemmodellierung: Navigation§  Startzustand: Arad§  Zielzustand: Bukarest§  Aktionen: Fahrt in nächste Stadt§  Lösung: Folge von Städten§  Kosten = Distanz, Zahl der Städte, Zeit,...

By Michael Schroeder, Biotec 7

Problemmodellierung: Roboter§  Startzustand: Links und rechts Staub§  Zielzustand: Links und rechts kein Staub§  Aktionen: Links, Rechts, Sauge§  Lösung: Folge von Aktionen§  Kosten = Distanz, Zahl der Aktionen, Dauer,...

By Michael Schroeder, Biotec 8

Problemmodellierung: Schiebepuzzle§  Startzustand: s.u. links§  Zielzustand: s.u. rechts§  Aktionen: verschiebe Zahl§  Lösung: Folge von Verschiebungen§  Kosten = Zahl der Verschiebungen,...

By Michael Schroeder, Biotec 9

Problemmodellierung: Damenproblem§  Startzustand: s.u. links§  Zielzustand: Damen können sich nicht schlagen§  Aktionen: Bewege Dame

By Michael Schroeder, Biotec 10

Problemmodellierung: Entitätenerkennung (HMM)

§  Startzustand: S§  Zielzustand: E

§  Zustände: Wort ist Person (P), Ort (L), Anderes (O) §  Kosten = Wahrscheinlichkeit für Wortfolge gegeben Zustandsfolge

By Michael Schroeder, Biotec 11

Problemmodellierung: �Relationsextraktion (Multiples Sequenzalignment)

§  Problem: Alignment von Zeichenketten peter, petra, pitr§  Startzustand: Alignment von drei leeren Zeichenketten§  Zielzustand: Alignment der drei Zeichenketten§  Aktion: „Konsumieren“ von Zeichen in den Zeichenketten§  Kosten = Größte Übereinstimmung der Zeichenketten

By Michael Schroeder, Biotec 12

peter-pet-rapit-r-

Suchverfahren

§  Einfache Suche§  Breitensuche§  Tiefensuche

§  Tiefenbegrenzte Suche§  Iteratives Vertiefen

§  Bestensuche§  Gierige (greedy) Suche§  A*

By Michael Schroeder, Biotec 13

Suchverfahren

§  Expandiere Knoten im Suchbaum bis Ziel gefunden§  Strategie: In welcher Reihenfolge?

By Michael Schroeder, Biotec 14

Suchbaum

By Michael Schroeder, Biotec 15

Suchbaum

By Michael Schroeder, Biotec 16

Suchbaum

Blätter

Tiefe

By Michael Schroeder, Biotec 17

Baumsuche

§  Blätter = [Startknoten]§  While Blätter nicht leer:

§  Nächster = pop(Blätter)§  If Nächster = Zielknoten then return Nächster§  For all Folgeknoten von Nächster

§  Füge Folgeknoten der Liste Blätter hinzu

§  Return failure

§  pop gibt erstes Element aus Liste �zurück und entfernt dieses aus Liste

§  Pfad? Pfadkosten? Tiefe?

By Michael Schroeder, Biotec 18

Suchstrategie

§  Welche Reihenfolge bei Expansion?

§  Bewertung: §  Vollständigkeit: Wird Lösung gefunden?

§  Zeitkomplexität: Zahl expandierter Knoten

§  Speicherkomplexität: Max. Zahl von Knoten im Speicher§  Optimalität: Lösung mit bester Bewertung?

§  b: maximaler Verzeigungsgrad (branching factor)§  d: Tiefe der besten Lösung (depth)

§  m: Maximale Tiefe des Zustandsraumes (kann unendlich sein)

By Michael Schroeder, Biotec 19

Breitensuche

§  Blätter = Schlange FIFO (first in, first out)

By Michael Schroeder, Biotec 20

Breitensuche

§  Blätter = Schlange FIFO (first in, first out)

By Michael Schroeder, Biotec 21

Breitensuche

§  Blätter = Schlange FIFO (first in, first out)

By Michael Schroeder, Biotec 22

Breitensuche

§  Blätter = Schlange FIFO (first in, first out)

By Michael Schroeder, Biotec 23

Breitensuche

§  Vollständig (wenn b endlich)§  Zeitaufwand:

§  Jede Ebene hat b mal mehr Knoten als vorherige

§  Jeder Knoten wird expandiert§  Ziel in Ebene d bedeutet:

§  Speicheraufwand:§  Jeder Knoten bleibt im Speicher O(bd+1)

§  Optimal

By Michael Schroeder, Biotec 24

⇒1+b+b2+b3+...+bd + b d+1( ) − b( )=O bd+1( )

Breitensucheb = 10, 10,000 nodes/sec, 1000 bytes/node

Tiefe Knoten Zeit Speicher2 1100 .11 secs 1 MB4 111 100 11 secs 106 MB6 107 19 mins 10 GB8 109 31 hours 1 TB10 1011 129 days 101 TB12 1013 35 years 10 PetaBytes14 1015 3523 years 1 ExaByte

By Michael Schroeder, Biotec 25

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 26

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 27

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 28

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 29

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 30

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 31

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 32

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 33

Tiefensuche

§  Blätter = Schlange LIFO (last in, first out)

By Michael Schroeder, Biotec 34

Tiefensuche

§  Blätter = Schlange LIFO (last in, first out)

By Michael Schroeder, Biotec 35

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 36

Tiefensuche

§  Blätter = Stapel LIFO (last in, first out)

By Michael Schroeder, Biotec 37

Tiefensuche

§  Nicht Vollständig, wenn unendliche Tiefe oder Schleifen§  Vollständig, wenn endlich und Scheifenprüfung

§  Zeitaufwand:§  Jeder Zweig, also max. Tiefe m: §  Schlecht, wenn m>>d

§  Speicheraufwand:§  Linear in Pfadlänge: O(m b)

§  Nicht optimal

By Michael Schroeder, Biotec 38

O bm( )

Tiefenbeschränkte Suche

§  Knoten mit Tiefe >t werden nicht expandiert

§  Unvollständig, wenn d>t

§  Nicht optimal §  Zeitaufwand O(bt)§  Speicheraufwand O(b t)

§  Wie kann Vollständigkeit erreicht werden?§  Erhöhe t sukzeszive

By Michael Schroeder, Biotec 39

Iteratives Vertiefen

Iteratives Vertiefen

Iteratives Vertiefen

§  Vollständig �(wenn es keine unendlichen Pfade gibt)

§  Zeitaufwand

§  Speicheraufwand O(b d)

§  Optimal

By Michael Schroeder, Biotec 42

(d +1) ⋅1+ d ⋅b+ d −1( )b2+...+2 ⋅bd−1+1⋅bd = d − i+1( )i=0

d

∑ ⋅bi=O(bd )

Zusammenfassung

By Michael Schroeder, Biotec 43

BS TS TBS IV

Vollständig Ja Nein Ja, für t≥d Ja

Zeit bd+1 bm

bt

bd

Speicher bd+1 bm bt bd

Optimal Ja Nein Nein Ja

b Verzeigungsfaktor, d Tiefe der Lösung, m Tiefe des Baumes, t Tiefenbeschränkung

Baum vs. Graph

By Michael Schroeder, Biotec 44

Graphsuche§  Blätter = [Startknoten]§  For all Knoten

§  visited(Knoten) = false§  While Blätter nicht leer:

§  Nächster = pop(Blätter)§  If Nächster = Zielknoten then return Nächster§  visited(Nächster)=true§  For all Folgeknoten von Nächster

§  If not visited(Folgeknoten) then§  Füge Folgeknoten der Liste Blätter hinzu

§  Return failure

§  pop gibt erstes Element aus Liste �zurück und entfernt dieses aus Liste

§  Pfad? Pfadkosten? Tiefe? Vorgänger?

By Michael Schroeder, Biotec 45

Suchverfahren

§  Einfache Suche§  Breitensuche§  Tiefensuche

§  Tiefenbegrenzte Suche§  Iteratives Vertiefen

§  Bestensuche§  Gierige (greedy) Suche§  A*

By Michael Schroeder, Biotec 46

Motivation§  Von Dresden nach Brüssel?

§  Dresden bietet Flüge nach Moskau, Frankfurt, Düsseldorf,...§  Breitensuche: Dresden-Moskau-Brüssel: 3876km§  Beste Lösung: Dresden-Frankfurt-Brüssel: 692km

By Michael Schroeder, Biotec 47

Moskau

BrüsselFrankfurt

Dresden

§  Breitensuche nutzt keinerlei Bewertung

§  Wie lassen sich Knoten, Pfade, Lösungen bewerten?§  Wie lassen sich diese Bewertungen optimieren?

Motivation

§  Durchschnittliche Lösungstiefe für Schiebepuzzle ist 22§  Breitensuche expandiert ca. 3x1010 Knoten

By Michael Schroeder, Biotec 48

§  Breitensuche nutzt keinerlei Bewertung

§  Wie lassen sich Knoten, Pfade, Lösungen bewerten?§  Wie lassen sich diese Bewertungen optimieren?

Bewertung

§  Navigation: Distanzen

§  Schiebepuzzle: §  Anzahl falschliegender Zahlen§  Summe Manhattandistanz jeder Zahl zur korrekten Position

§  Dame:§  Anzahl Bedrohungen

§  Multiples Sequenzalignment§  Anzahl Übereinstimmungen in Zeichenketten

By Michael Schroeder, Biotec 49

Idee

Sortiere zu expandierende Knoten gemäß Bewertung

Nutze Heuristik. Eureka = „Ich finde“

Heuristikfunktion h schätzt Kosten von Knoten zum Ziel

By Michael Schroeder, Biotec 50

Navigationsheuristik

§  Heuristik ist Luftliniendistanz zum Ziel

§  Euklidische Distanz

By Michael Schroeder, Biotec 51

d

ij

=

vuuutnX

k=1(x

ik

� x

jk

)2

1

Navigationsheuristik

§  Heuristik ist Luftliniendistanz zum Ziel

§  Erde ist keine Scheibe?

§  Distanz

By Michael Schroeder, Biotec 52

Rumänien

176

By Michael Schroeder, Biotec 53

Gierige Suche

Expandiere Knoten mit geringster Distanz zum Ziel zuerst

By Michael Schroeder, Biotec 54

Gierige Suche

By Michael Schroeder, Biotec 55

Gierige Suche

Gierige Suche

By Michael Schroeder, Biotec 57

Gierige Suche

By Michael Schroeder, Biotec 58

Gierige Suche

§  Vollständigkeit: Schleifen!§  Von Iasi nach Fagaras§  Iasi-Neamt-Iasi-Neamt-...

By Michael Schroeder, Biotec 59

Gierige Suche

§  Vollständig, wenn auf Schleifen getestet wird§  Zeitaufwand:

§  O(bm) wie Tiefensuche

§  Aber: Perfekte Heuristik = Lösung in d Schritten

§  Speicheraufwand:§  Wie Zeit

§  Optimalität:§  Nein!

By Michael Schroeder, Biotec 60

Gierige Suche

Gierige Suche findet lokales Optimum

(A* findet globales Optimum)

By Michael Schroeder, Biotec 61

Motivation§  Von Dresden nach Brüssel?

§  Dresden bietet Flüge nach Moskau, Frankfurt, Düsseldorf,...§  Breitensuche: Dresden-Moskau-Brüssel: 3876km§  Gierige Suche: Dresden-Düsseldorf-Amsterdam-Brüssel: 824km§  Beste Lösung: Dresden-Frankfurt-Brüssel: 692km

By Michael Schroeder, Biotec 62

Düsseldorf

BrüsselFrankfurt Dresden

§  Gierige Suche bewertet bisherige Kosten nicht§  A* tut dieses...

Amsterdam

A* Suche

§  Evaluiere vollständige Pfadkosten

§  Bisherige Kosten: g(n) §  Abschätzung der Kosten bis zum Ziel: h(n)

§  Gesamtbewertung: f (n) = g(n)+h(n)

By Michael Schroeder, Biotec 63

A*

A*

A*

A*

A*

Pitesti wird expandiert, obwohl Bukarest bereits

gefunden wurde

A*

A* Suche

§  Vollständigkeit �(es sei denn, es gibt unendlich viele Knoten mit f(n)<f(G))

§  Zeitaufwand§  Abhängig von Abweichung der Heuristik von den wahren

Kosten

§  Speicheraufwand:§  Alle Knoten bleiben im Speicher. Verbesserung?

§  Optimalität?

Zulässige Heuristik

§  Eine zulässige Heuristik unterschätzt Kosten, �d.h. h(n) ≤h*(n), wobei h* die echten Kosten sind

§  h(Zielknoten)=0§  h(n)≥0

§  Luftliniendistanz ist zulässig

§  Schiebepuzzle §  Anzahl der falschpositionierten �

Zahlen zulässig?§  Manhattandistanz zulässig?§  K*=26, hMan =18, hfpz=8

By Michael Schroeder, Biotec 71

A* ist optimal

■ Wenn die Heuristik h* zulässig ist, �so ist A* Baumsuche optimal

■  Beweis:■ Sei O eine optimale Lösung mit Kosten K* �

und N eine nichtoptimale Lösung mit Kosten K■ K* < K

■ Für jeden Knoten n im Pfad O gilt: �f(n) = g(n)+h(n) ≤ K*

■ Somit gilt, f(n) ≤K* < K

■ Damit würde nicht optimale Lösung N erst gewählt, �nachdem jeder Knoten n auf dem optimalen Pfad expandiert wird

By Michael Schroeder, Biotec 72

A* Graphsuche

■ Graphsuche prüft auf Schleifen, somit keine Wiederholungen

■ Bisheriger Pfad möglicherweise schlechter als neuer Pfad

■ Expandiere optimalen Pfad zu gleichen Knoten zuerst

■  Sichergestellt, wenn Kosten monoton steigen = Konsistenz

By Michael Schroeder, Biotec 73

Konsistenz

Eine Heuristik ist konsistent, gdw. �für jeden Knoten n und �jeden Folgeknoten n‘ gilt, daß ��h(n) ≤ c(n,n‘) + h(n‘), ��wobei c(n,n‘) die Kosten �für den Übergang �von n nach n‘ sind.

(Dreiecksungleichung)

By Michael Schroeder, Biotec 74

Jede konsistente Heuristik ist zulässig

§  Für alle Knoten n, die zum Ziel G führen, gilt��h(n) ≤ c(n,G) + h(G) (nach Def. Konsistenz) �und c(n,G) + h(G) = h*(n) (Def h*) �

§  Mittels Induktion über die Pfadlänge zum Ziel ergibt sich �h(n) ≤ h*(n) für alle n

§  Nicht jede zulässige Heuristik ist konsistent �(z.B. h = Luftlinie, doch für einige Knoten h(n)=0)

By Michael Schroeder, Biotec 75

Konsistenz = �Monoton steigende Bewertung

Ist h konsistent, so sind �die Werte f(n) monoton steigend �entlang eines Pfades

By Michael Schroeder, Biotec 76

A* ist optimal

§  Ist h konsistent, so ist A* optimal

§  Beweis: A* expandiert Knoten in Reihenfolge�steigender Bewertungen f

§  A* expandiert �alle Knoten mit f(n)<K*, �einige mit f(n)=K* und �keine Knoten mit f(n)>K* ��K* = Optimum

By Michael Schroeder, Biotec 77

Höhenlinie fi = Knoten mit f(n)<fi

Animation der Höhenlinien

Wikipedia.org

A* Suche

§  Knoten bleiben im Speicher = Problem

§  Schwellwert K: §  Überschätzung der wahren Kosten K*§  Knoten n mit f(n)>K können nicht Teil der optimalen

Lösung sein und müssen daher nicht gespeichert werden

§  Je kleiner K-K*, desto weniger Knoten werden besucht

§  Wie lässt sich K bestimmen?§  Z.B. Nicht optimale Lösung aus gieriger Suche

By Michael Schroeder, Biotec 79

Effektiver Verzweigungsfaktor

§  N Knoten besucht, bis zur Lösung in Tiefe d §  Verteile N Knoten gleichmäßig über Baum der Tiefe d, �

d.h. suche b*, so daß 1+N = 1+b*+b*2+b*3+...+b*d

§  Effektiver Verzweigungsfaktor b*=1 ist optimal

By Michael Schroeder, Biotec 80

Vergleich A* und iteratives Vertiefen�Schiebepuzzle

Suchkosten Effektiver Verzweigungsfaktor

d IV A* fpz A* Manh. IV A* fpz A* Manh.

2 10 6 6 2,45 1,79 1,79

6 680 20 18 2,73 1,34 1,30

10 47.127 93 39 2,79 1,38 1,22

12 3.644.035 227 73 2,78 1,42 1,24

14 - 539 113 - 1,44 1,23

20 - 7.276 676 - 1,47 1,27

24 - 39.139 1.641 - 1,48 1,26

d=Tiefe der Lösung, IV= iteratives Vertiefen, fpz=falsch plazierte Zahlen, Manh.=Manhattandistanz

Zusammenfassung

■ Heuristiken verbessern Suche

■ Gierige Suche = lokales Optimum, nicht vollständig

■ A* = optimal und vollständig■ Bewertung = Bisherige Kosten + Unterschätzung zum Ziel

■ Schwellwert K = Überschätzung der Kosten erlaubt Knoten zu entfernen, die nicht Teil des Optimums sein können

By Michael Schroeder, Biotec 82

§  Von Dresden nach Brüssel?§  Dresden bietet Flüge nach Moskau, Frankfurt, Düsseldorf,...§  Breitensuche: Dresden-Moskau-Brüssel: 3876km§  Gierige Suche: Dresden-Düsseldorf-Amsterdam-Brüssel: 824km§  A*: Dresden-Frankfurt-Brüssel: 692km

By Michael Schroeder, Biotec 83

BrüsselFrankfurt Dresden

§  Von Dresden nach Innsbruck?§  Breitensuche: Dresden-Frankfurt-Innsbruck: 759km§  Gierige Suche: �

Dresden�München�Venedig�Zürich�Salzburg�Linz�Frankfurt�Innsbruck: �2288km

§  A*: Dresden-Frankfurt-Innsbruck: 759km

By Michael Schroeder, Biotec 84

Innsbruck

Frankfurt Dresden

LinzSalzburg

Venedig

Zürich

München