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.
