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


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


Zustandsraum

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


Problemmodellierung

§  Navigation§  Roboter§  Schiebepuzzle

§  Damenproblem

§  Entitätenerkennung (HMM)

§  Relationsextraktion (Multiples Sequenzalignment)


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,...


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,...


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


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


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


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


peter-pet-rapit-r-

Suchverfahren

§  Einfache Suche§  Breitensuche§  Tiefensuche

§  Tiefenbegrenzte Suche§  Iteratives Vertiefen

§  Bestensuche§  Gierige (greedy) Suche§  A*


Suchverfahren

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


Suchbaum


Suchbaum


Suchbaum

Blätter

Tiefe


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?


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)


Breitensuche

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


Breitensuche



Breitensuche



Breitensuche



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


⇒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


Tiefensuche

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


Tiefensuche



Tiefensuche



Tiefensuche



Tiefensuche



Tiefensuche



Tiefensuche



Tiefensuche



Tiefensuche

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


Tiefensuche

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


Tiefensuche



Tiefensuche



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


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


Iteratives Vertiefen



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

§  Zeitaufwand

§  Speicheraufwand O(b d)

§  Optimal


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

d

∑ ⋅bi=O(bd )

Zusammenfassung


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


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?


Suchverfahren

§  Einfache Suche§  Breitensuche§  Tiefensuche

§  Tiefenbegrenzte Suche§  Iteratives Vertiefen

§  Bestensuche§  Gierige (greedy) Suche§  A*


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


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


§  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


Idee

Sortiere zu expandierende Knoten gemäß Bewertung

Nutze Heuristik. Eureka = „Ich finde“

Heuristikfunktion h schätzt Kosten von Knoten zum Ziel


Navigationsheuristik

§  Heuristik ist Luftliniendistanz zum Ziel

§  Euklidische Distanz


d

ij

=

vuuutnX

k=1(x

ik

� x

jk

)2

1

Navigationsheuristik

§  Heuristik ist Luftliniendistanz zum Ziel

§  Erde ist keine Scheibe?

§  Distanz


Rumänien

176


Gierige Suche

Expandiere Knoten mit geringster Distanz zum Ziel zuerst


Gierige Suche


Gierige Suche

Gierige Suche


Gierige Suche


Gierige Suche

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


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!


Gierige Suche

Gierige Suche findet lokales Optimum

(A* findet globales Optimum)


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


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)


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


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


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


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)


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)


Konsistenz = �Monoton steigende Bewertung

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


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


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


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


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


§  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


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


Innsbruck

Frankfurt Dresden

LinzSalzburg

Venedig

Zürich

München

Date post:	27-Jun-2020
Category:	Documents
Upload:	others
View:	4 times
Download:	0 times

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

Documents