Andrei Kolmogorov The theory of probability ... can and should be developed from axioms ... Vorlesung TU-München Wintersemester 2003/2004 Entities should not be multiplied unnecessarily William of Occam

Bereich
2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlvorlesung im Gebiet VII

Zeit und Ort
Wird unter http://www.idsia.ch/~marcus/ai/tumvorl.htm bekanntgegeben.
Abwechselnd Montag/Freitag Nachmittag an der TU-München, Boltzmannstr. 3, D-85748 Garching, Raum MI 00.08.038.

1.Stunde am Mo.27.Oct.03 von 14:15 bis 16:00.
2.Stunde am Fr.31.Oct.03 von 14:15 bis 16:00.
3.Stunde am Fr.14.Nov.03 von 14:15 bis 16:00.
4.Stunde am Mo.17.Nov.03 von 14:15 bis 16:00.
5.Stunde am Fr.05.Dez.03 von 14:15 bis 16:00.
6.Stunde am Mo.08.Dec.03 von 14:15 bis 16:00.
7.Stunde am Fr.19.Dez.03 von 15:15 bis 17:00.
8.Stunde am Mo.22.Dec.03 von 14:15 bis 16:00.
9.Stunde am Fr.16.Jan.04 von 15:15 bis 17:00.
10.Stunde am Mo.19.Jan.04 von 14:15 bis 16:00.
11.Stunde am Fr.30.Jan.04 von 15:15 bis 17:00.
12.Stunde am Mo.02.Feb.04 von 14:15 bis 16:00.

Schein
Einen Schein erhält, wer regelmässig an der Vorlesung teilnimmt, gelegentliche Übungsaufgaben löst, und eine mündliche Prüfung erfolgreich absolviert.

Hörerkreis
Studierende im Hauptstudium der Informatik, Mathematik, Physik oder verwandten Gebieten.

Voraussetzungen
Grundkenntnisse in Wahrscheinlichkeitstheorie, Algorithmen, und Berechenbarkeit.

Zusammenfassung
Die Vorlesung gibt eine Einführung in zwei fundamentale Theorien der Künstlichen Intelligenz. Die eine, genannt Eintscheidungstheorie, löst das Problem rationaler Agenten in ungewisser Umgebung, falls die wahre a priori Wahrscheinlichkeitsverteilung der Umgebung bekannt ist. Die andere ist Solomonoffs Theorie der universellen Induktion, basierend auf algorithmischer Informationstheorie, die formal das Problem der Sequenz-Vorhersage im Falle unbekannter a priori Wahrscheinlichkeit löst. Anwendungen in den Bereichen Genetik, Musik, und Linguistik werden vorgestellt. Gegen Ende ist geplant eine neuere vereinheitlichte Theorie universell-intelligenter Agenten vorzustellen und deren Potential zu diskutieren.

Geplanter Inhalt
1. Überblick / Motivation / Occam's Rasiermesser  [Hut03, Kap. 1.2 & 1.4]
2. Informations-Theorie und Kolmogorov-Komplexität  [Hut03, Kap. 2.1 & 2.2] (Beweise in [LV97, Kap.3])
3. Klassische Bayes Wahrscheinlichkeits-Theorie  [Hut03, Kap. 2.3]
4. Algorithmische Wahrscheinlichkeits-Theorie  [Hut03, Kap. 2.4.1 & 2.4.4] (Details in [LV97, Kap.4])
5. Induktive Inferenz und universelle Sequenz-Vorhersage  [Hut03, Kap. 2.4.2] (Beweise in [Hut03, Kap. 3.2] und [LV97, Kap.5])
6. MDL mit Anwendungen in der Genetik, Musik, Linguistik, etc.  [Li02] und [CVW03]
7. Sequentielle Entscheidungstheorie  [Hut03, Kap. 4] (weiterführend [SB98])
8. Rationale Agenten in unbekannter Umgebung  [Hut03, Kap. 5.4 & 5.7]
9. Diskussion  [Hut03, Kap. 8]

Verwandte Vorlesungen
Komplexitätstheorie, Berechenbarkeitstheorie, Entscheidungstheorie, Regelungstechnik, Wissenschaftstheorie.

Literatur
[Hut03] M. Hutter. Optimal Sequential Decisions based on Algorithmic Probability
  Habilitation preprint (2003)
[LV97] M. Li and P. M. B. Vitanyi. An Introduction to Kolmogorov Complexity and its Applications
  Springer, 2nd edition (1997)
[SB98] R. Sutton and A. Barto. Reinforcement Learning: An Introduction
   Cambridge, MA, MIT Press (1998)
[RN03] S. J. Russell and P. Norvig. Artificial Intelligence. A Modern Approach
  Prentice-Hall, Englewood Cliffs (2003)
[Hot97] G. Hotz. Algorithmische Informationstheorie
  Teubner, Stuttgart (1997)
[Li03] M. Li et. al. The Similarity Metric
  Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)
[CVW03] R. Cilibrasi et. al. Algorithmic Clustering of Music
  Technical Report, CWI, Amsterdam (2003)

Skript
Es gibt (noch?) kein Skript, welches genau zur Vorlesung passt. Die Vorlesung lehnt sich jedoch an das (fortgeschrittenere und wesentlich umfangreichere) Manuskript [Hut03] an. Für Details, siehe Literaturverweise unter Geplanter Inhalt .

Sprechzeiten
Im Anschluss an die Vorlesung

Ray Solomonoff ... Algorithmic Probability can serve as a kind of 'Gold Standard' for induction systems Only math nerds would call 2500 finite Leonid Levin