Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Projektseminar zur Berechenbarkeits- und Lerntheorie

MSc Seminar - Winter 2019/20

Personen: Dr. Timo Kötzing, Vanja Doskoč
Link: Lehrveranstaltungen IT Systems Engineering

Beschreibung

In diesem Kurs geht es darum, ein Thema stark zu vertiefen und wissenschaftlich kennen zu lernen. Dazu fangen wir an mit einigen Wochen im Stile einer interaktiven Vorlesung mit wöchentlichen Übungen. Danach präsentiert jede Teilnehmerin und jeder Teilnehmer ein einzelnes Paper wie bei einem Seminar, aber etwas kürzer und ohne detaillierter Ausarbeitung, aber mit einem Handout. Danach werden wir gemeinsam an einer offenen Frage des Bereichs forschen, mit dem Ziel einer Publikation.

Themen

Wir werden die Gold-Style Lerntheorie kennen lernen, welche formale Grenzen des maschinellen Lernens mit Mittlen der Berechenbarkeitstheorie analysiert. Konkret stellen wir uns Fragen wie:

  • Kann jeder Lerner konsistent sein, d.h. bekannte Daten korrekt reflektieren?
  • Ist es wichtig, korrekte Hypothesen verwerfen zu dürfen, oder ist solch ein Verhalten ineffizient?
  • In welcher Form werden Daten präsentiert? Erhält der Lerner nur einseitige Informationen ("positive Examples") oder beidseitige ("positive and negative examples")?
  • In welcher Form werden Hypothesen formalisiert? Welchen Unterschied macht es, wenn ich aussagekräftige Hypothesen (für welche bestimmte Probleme entscheidbar sind) statt weniger aussagekräftigen verlange?

Wir werden dazu zunächst das sehr mächtige Werkzeug "ORT" kennen lernen, das Operator Recursion Theorem von John Case. Dieses ist eine weitreichende Verstärkung von KRT und erlaubt das finden von unendlich vielen spezifizierten Indizes mit Selbstreferenz (KRT erlaubt das finden von einem einzelnen spezifizierten Index mit Selbstreferenz).

Danach dringen wir tief in die Techniken des Gold-Style Lernens ein, zum Beispiel lernen wir Locking Sequenzen kennen und sogenannte Vergiftungsargumente. Mit diesen Werkzeugen können wir die oben genannten Fragen angehen, wobei einige dieser Fragen noch weitgehend ungeklärt sind - das wird dann der forschende Teil dieses Projektseminars sein.

Voraussetzungen

Die Teilnehmer sollten keine Probleme bei der Anwendung vom Smn-Theorem und von KRT haben und allgemein stark im Bereich formale Beweise sein. Die Teilnahme an einer vertiefenden Vorlesung zum Thema Berechenbarkeit könnte hilfreich sein, ist aber nicht notwendig.

Leistungserfassung

Die Leistungserfassung erfolgt kursbegleitend über die Übungsaufgaben (10%), den Vortrag (40%) und die Mitarbeit beim abschließenden wissenschaftlichen Projekt (50%).

Literatur

  • Systems that learn. Osherson, Stob und Weinstein.
  • Systems that learn, second edition. Jain, Osherson, Royer, Sharma.

Lern- und Lehrformen

Es werden Elemente aus klassisichen Vorlesungen mit Übungen vermischt mit Elementen aus einem Seminar, sowie schließlich, im Hauptteil, mit dem forschenden Lernen.

Termine

Wir treffen uns montags um 11:00 in A-2.2 und dienstags um 9:15 in H-2.57. Der erste Termin ist am 14.10.2019.