Humboldt-Universität zu Berlin, Institut für Informatik
Lehrstuhl für Komplexität und Kryptografie

Vorlesung: Algorithmisches Lernen

Dozent: Prof. Johannes Köbler und Dr. Wolfgang Lindner


Termine: VL Di 11-13 (RUD 25, 4.1.10) Prof. J. Köbler und Dr. W. Lindner
VL Do 13-15 (RUD 25, 4.1.11) Prof. J. Köbler und Dr. W. Lindner
UE Di 13-15 (RUD 25, 4.1.10) Prof. J. Köbler
Zuordnung: Hauptstudium, Halbkurs

Inhalte und Lernziele

Die Theorie des algorithmischen Lernens beschäftigt sich mit Lernprozessen, die von Algorithmen ausgeführt werden. Hierzu wurde eine Vielfalt an Lernmodellen entworfen, die die unterschiedlichen Rahmenbedingungen widerspiegeln, unter denen solche Lernprozesse stattfinden. Das Spiel "Mastermind" etwa stellt ein sehr anschauliches Beispiel für ein Lernmodell dar, bei dem das Lernziel durch aktives Stellen von Fragen an einen "Lehrer" erreicht werden kann.

In der Vorlesung wird ein überblick über die bekanntesten Lernmodelle gegeben. Im Vordergrund steht dabei die Frage, welcher (Zeit-)Aufwand zum Erreichen eines vorgegebenen Lernziels benötigt wird (obere und untere Schranken). Interessanterweise bestehen hier enge Querbezüge zur Sicherheit von Public-Key-Verfahren, wie sich in neueren Arbeiten herausgestellt hat.

  1. Einleitung
  2. Lernen im Mistake-Bound Modell
  3. Optimale Fehlerschranken
  4. Effizientes Lernen im Mistake-Bound Modell ([3], [4])
  5. Exaktes Lernen durch Fragen ([1] Kapitel 8)
  6. Erlernbarkeit endlicher Automaten ([1] Kapitel 8)
  7. PAC-Lernen ([1] Kapitel 1 und 2)
  8. VC-Dimension und PAC-Erlernbarkeit ([1] Kapitel 3, [2] Kapitel 8)
  9. Kryptographische Grenzen der Erlernbarkeit
  10. Die Fourier-Transformation

Literatur

[1]M. Kearns, U. Vazirani. An Introduction to Computational Learning Theory. MIT Press 1997 (2nd Ed.)]
[2] M. Anthony, N. Biggs. Computational Learning Theory. Cambridge University Press 1992
[3]N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning 2. 1988
[4] R. Rivest. Machine Learning (Lectures Notes 1994)
[5] Andreas Abel. Division nach Beame, Cook und Hoover. (Iteriertes Produkt mit einem Schaltkreis logarithmischer Tiefe)

Übungen



wl
Erstellt am 31.07.2000
Zuletzt geändert am 18.05.2001