Grundlagen der Künstlichen Intelligenz

KI – Wintersemester 2013/2014
Grundlagen der Künstlichen Intelligenz
Marc Toussaint
Machine Learning & Robotics Lab
Universität Stuttgart
[email protected]
http://ipvs.informatik.uni-stuttgart.de/mlr/marc/
Vorlesungen IS
Vorlesungen der Abteilung MLR
 Bachelor:
– Grundlagen der Künstlichen Intelligenz (3+1 SWS)
 Master: Vertiefungslinie Intelligente Systeme
– gemeinsam angeboten mit Andres Bruhn (Computer Vision)
 Vorlesungen der Vertiefungslinie IS:
– Mathematics for Intelligent Systems (Nathan Ratliff)
–
Introduction to Robotics (Toussaint)
–
SS: Machine Learning (Toussaint)
–
SS: Optimization (Toussaint)
–
Reinforcement Learning (Ngo)
 Hauptseminare:
– Advanced Machine Learning (Toussaint)
–
SS: Advanced Robotics (Toussaint)
3
Vorlesungen IS
Weitere Veranstaltungen von Andres Bruhn
 Vorlesungen der Vertiefungslinie IS:
– Computer Vision (Bruhn)
–
SS: Correspondence Problems in Computer Vision (Bruhn)
 Hauptseminare:
– Recent Advances in Computer Vision (Bruhn)
4
Organisatorisches (1)
Welche Voraussetzung werden empfohlen?
 Mathematik für Informatiker und Softwaretechniker
 außerdem hilfreich:
 Algorithmen und Datenstrukturen
 Theoretische Informatik
7
Organisatorisches (4)
Prüfungsmodalitäten
 Schriftliche Prüfung, 90 Minuten
 keine Hilfsmittel erlaubt
 Anmeldung: Im LSF / beim Prüfungsamt
 Prüfungszulassung: 50% der Punkte der Übungsaufgaben
 Vorrechnen:
 bis zu zwei mal im Semester möglich
 gibt die Hälfte der Aufgabenpunkte zusätzlich
Registrierung und Skript
 Webseite zur Vorlesung:
https://ipvs.informatik.uni-stuttgart.de/mlr/marc/teaching/
 das Skript wird dort zu jeder Vorlesung online gestellt
(passwortgeschützt)
8
Inhalt (1)
Inhalt
 Grundlagen der KI:
– Lösungs-Suche, Spiele, Logik, Inferenz
Nicht
 Mustererkennung (Computer Vision, Sprache)
 Lernen (Maschinelles Lernen, Reinforcement Lernen)
13
Inhalt (2)
Kapitel-Nummerierung wie Russel-Norvig
1. Einführung
2. Intelligente Agenten
3. Problemlösen durch Suchen
4. Heuristische Suche
5. Probleme mit Rand- oder Nebenbedingungen
6. Adversariale Suche
7. Logik-basierte Agenten
8. Prädikatenlogik
9. Prädikatenlogische Inferenz
16
Inhalt (3)
Kapitel-Nummerierung wie Russel-Norvig
13. Unsicherheit
14. Probablistisches Schließen
15. Inferenz über die Zeit
16. Rationale Entscheidungen
17. Komplexe Entscheidungen
17
Inhalt (4)
1. Einführung
 Intelligenz
 Definitionen der KI
 Rationalität
18
Inhalt (5)
2. Intelligente Agenten
 Agenten
 Umgebungen
 Agententypen
Schematischer Aufbau eines Agenten
19
Inhalt (6)
3. Problemlösen durch Suchen





Problemtypen
Problemformulierung
Beispielprobleme
Suchbäume
Suchstrategien
Routenplanung
Routenplanung als Suchproblem
20
Inhalt (7)
4. Heuristische Suche
 Informierte Suche
 Lokale Suchalgorithmen
 Nichtdeterministische Suche
Routenplanung mit Luftlinien-Heuristik
21
Inhalt (8)
5. Probleme mit Rand- oder Nebenbedingungen
 Constraint Satisfaction Problems (CSPs)
 Backtracking, Variablen und Werteauswahl,
Sackgassenvorhersage, Vorteilhafte Spezialfälle
 Lokale Suche
Lösung des Einfärbeproblems mit drei Farben
22
Inhalt (9)
6. Adversariale Suche






Spiele
Minimax für zwei Spieler
α-β Pruning
Minimax für mehrere Spieler
Nicht-deterministische Spiele
Kartenspiele
Suchbaum für Spiel mit Würfelkomponente
Schach bzw. Kartenspiel
23
Inhalt (10)
7. Logik-basierte Agenten






(   )  (    )
Wissens-basierte Agenten
Wumpus Welt
Inferenzregel für Bikonditional
Aussagenlogik
Inferenzregeln, Modus Ponens, Resolution
Vorwärtsverkettung, Rückwärtsverkettung
Inferenz durch Vorwärtsverkettung
Wumpus Welt
24
Inhalt (11)
8. Prädikatenlogik





Prädikatenlogik vs. Aussagenlogik
Quantoren
Anwendung der Prädikatenlogik
Wissensreprästentation in Prädikatenlogik
Repräsentation von Veränderungen
Prädikatenlogik
Represäntation von
Veränderungen
25
Inhalt (12)
9. Prädikatenlogische Inferenz






Instantiierung
Reduktion auf aussagenlogische Inferenz
Generalisierter Modus Ponens
Unifikation
Vorwärtsverkettung, Rückwärtsverkettung
Resolution
 x König(x)  Gierig(x)  Böse(x)
König(John)
 y Gierig(y)
Bruder(Richard,John)
Prädikatenlogische Inferenz
26
Inhalt (13)
13. Unsicherheit






Wahrscheinlichkeit
Bedingte Wahrscheinlichkeit
Inferenz
Unabhängigkeit
Bedingte Unabhängigkeit
Bayes’sche Regel
Gemeinsame Wahrscheinlichkeiten
P(loch | zahnschmerzen) =
P(loch  zahnschmerzen) / P(zahnschmerzen)* =
(0.016+0.064) / (0.108 + 0.012 + 0.016 + 0.064) = 0.4
Berechnung bedingter Wahrscheinlichkeiten
27
Inhalt (14)
14. Probabilistisches Schließen
 Bedingte Wahrscheinlichkeitstabellen
 Bayes-Netze
Bayes-Netz
28
Inhalt (15)
15. Inferenz über die Zeit






Markov-Prozesse
Inferenz: Filterung, Vorhersage, Glättung, wahrsch. Erklärung
Hidden Markov Modelle
Kalman Filter
Dynamische Bayes-Netze
Spracherkennung
Hidden Markov Modell (HMM)
Kalman-Filterung von Trajektorien
29
Inhalt (16)
16. Rationale Entscheidungen





Rationale Prioritäten
Nutzenfunktion
Geld
Entscheidungsnetzwerke
Wert von Information
Lotterie/Aktion mit rationalem Ergebnis
MEN-Prinzip:
Wähle die Aktion A, die zur Maximierung des Erwarteten Nutzens führt.
EU(A | E) = i P(Resultati(A) | A, E) U(Resultati(A)).
Berechnung des erwarteten Nutzens
30
Inhalt (17)
17. Komplexe Entscheidungen




Sequentielle Entscheidungen
Markov Entscheidungsprozesse
Optimale Taktik
Wert- und Taktikiteration
Konvergenz von Nutzen und Taktik
Optimale Taktik (Handlungsschema) für Markov Entscheidungsprozess
31
Organisation der Übungen


Wir werden ca. 5 Probleme definieren:
–
Kürzester Weg in einer Karte [Suchmethoden]
–
CSP Probleme wie Sudoku und map coloring
–
Wumpus Welt (geplant)
–
Spam Filter mit Naive Bayes
–
Samplingmethoden
–
Schach/TicTacToe oder andere Spiele mit MCTS/UCT
Problem-orientierte Herangehensweise
32
Organisation der Übungen
 Eine gemeinsame Übung, 14-tägig, Donnerstag 11:30
 Die meisten Aufgaben werden Programmieraufgaben sein
– In den Übungsstunden besprechen wir den Lösungen und code
–
Einzelne Nicht-Programmier-Aufgaben werden hier in der
Präsenz-Übungen diskutiert
 Lösungen können in Gruppen
abgegeben werden
 Lösungen werden an einen gitlab server eingecheckt und automatisch
getestet
 Generische Programmiersprache: Python
33
Literatur
Hauptliteratur
●
Stuart Russell & Peter Norvig: Artificial Intelligence – A
Modern Approach (Pearson)
34