Grundlagen der Künstlichen Intelligenz

Marc ToussaintMachine Learning & Robotics LabUniversität Stuttgart

marc.toussaint@informatik.uni-stuttgart.dehttp://ipvs.informatik.uni-stuttgart.de/mlr/marc/

KI – Wintersemester 2013/2014

Vorlesungen IS

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)

Vorlesungen der Abteilung MLR

3

Vorlesungen IS

Vorlesungen der Vertiefungslinie IS:– Computer Vision (Bruhn)

– SS: Correspondence Problems in Computer Vision (Bruhn)

Hauptseminare:– Recent Advances in Computer Vision (Bruhn)

Weitere Veranstaltungen von Andres Bruhn

4

Organisatorisches (1)

Mathematik für Informatiker und Softwaretechniker außerdem hilfreich:

Algorithmen und Datenstrukturen Theoretische Informatik

Welche Voraussetzung werden empfohlen?

7

Organisatorisches (4)

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)

Prüfungsmodalitäten

8

Inhalt (1)

Grundlagen der KI:– Lösungs-Suche, Spiele, Logik, Inferenz

Nicht

Mustererkennung (Computer Vision, Sprache)

Lernen (Maschinelles Lernen, Reinforcement Lernen)

Inhalt

13

Inhalt (2)

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

Kapitel-Nummerierung wie Russel-Norvig

16

Inhalt (3)

13. Unsicherheit

14. Probablistisches Schließen

15. Inferenz über die Zeit

16. Rationale Entscheidungen

17. Komplexe Entscheidungen

17

Kapitel-Nummerierung wie Russel-Norvig

Inhalt (4)

Intelligenz Definitionen der KI Rationalität

1. Einführung

18

Inhalt (5)

Agenten Umgebungen Agententypen

2. Intelligente Agenten

19

Schematischer Aufbau eines Agenten

Inhalt (6)

Problemtypen Problemformulierung Beispielprobleme Suchbäume Suchstrategien

3. Problemlösen durch Suchen

20Routenplanung als Suchproblem

Routenplanung

Inhalt (7)

Informierte Suche Lokale Suchalgorithmen Nichtdeterministische Suche

4. Heuristische Suche

21Routenplanung mit Luftlinien-Heuristik

Inhalt (8)

Constraint Satisfaction Problems (CSPs) Backtracking, Variablen und Werteauswahl,

Sackgassenvorhersage, Vorteilhafte Spezialfälle Lokale Suche

5. Probleme mit Rand- oder Nebenbedingungen

22Lösung des Einfärbeproblems mit drei Farben

Inhalt (9)

Spiele Minimax für zwei Spieler α-β Pruning Minimax für mehrere Spieler Nicht-deterministische Spiele Kartenspiele

6. Adversariale Suche

23

Suchbaum für Spiel mit Würfelkomponente

Schach bzw. Kartenspiel

Inhalt (10)

Wissens-basierte Agenten Wumpus Welt Aussagenlogik Inferenzregeln, Modus Ponens, Resolution Vorwärtsverkettung, Rückwärtsverkettung

7. Logik-basierte Agenten

24Wumpus Welt

Inferenz durch Vorwärtsverkettung

Inferenzregel für Bikonditional

)()(

Inhalt (11)

Prädikatenlogik vs. Aussagenlogik Quantoren Anwendung der Prädikatenlogik Wissensreprästentation in Prädikatenlogik Repräsentation von Veränderungen

8. Prädikatenlogik

25

Represäntation von VeränderungenPrädikatenlogik

Inhalt (12)

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)

9. Prädikatenlogische Inferenz

26

Prädikatenlogische Inferenz

Inhalt (13)

Wahrscheinlichkeit Bedingte Wahrscheinlichkeit Inferenz Unabhängigkeit Bedingte Unabhängigkeit Bayes’sche Regel

13. Unsicherheit

27

P(loch | zahnschmerzen) = P( loch zahnschmerzen) / P(zahnschmerzen)* = (0.016+0.064) / (0.108 + 0.012 + 0.016 + 0.064) = 0.4

Gemeinsame Wahrscheinlichkeiten

Berechnung bedingter Wahrscheinlichkeiten

Inhalt (14)

Bedingte Wahrscheinlichkeitstabellen Bayes-Netze

14. Probabilistisches Schließen

28

Bayes-Netz

Inhalt (15)

Markov-Prozesse Inferenz: Filterung, Vorhersage, Glättung, wahrsch. Erklärung Hidden Markov Modelle Kalman Filter Dynamische Bayes-Netze Spracherkennung

15. Inferenz über die Zeit

29

Hidden Markov Modell (HMM) Kalman-Filterung von Trajektorien

Inhalt (16)

Rationale Prioritäten Nutzenfunktion Geld Entscheidungsnetzwerke Wert von Information

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

16. Rationale Entscheidungen

30

Lotterie/Aktion mit rationalem Ergebnis

Berechnung des erwarteten Nutzens

Inhalt (17)

Sequentielle Entscheidungen Markov Entscheidungsprozesse Optimale Taktik Wert- und Taktikiteration

17. Komplexe Entscheidungen

31Optimale Taktik (Handlungsschema) für Markov Entscheidungsprozess

Konvergenz von Nutzen und Taktik

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

● Stuart Russell & Peter Norvig: Artificial Intelligence – A Modern Approach (Pearson)

Hauptliteratur

34