PAC-Lernen

Ein Computerprogramm bekommt tausend Fotos gezeigt, jeweils mit der Angabe, ob eine Katze darauf ist. Danach soll es bei neuen, nie gesehenen Fotos selbst entscheiden. Die entscheidende Frage lautet: Wie viele Beispiele braucht es, damit man dem Ergebnis trauen kann? PAC-Lernen ist eine Theorie, die genau darauf eine mathematische Antwort gibt. Die Abkürzung steht für „probably approximately correct“, also „wahrscheinlich annähernd korrekt“. Beide Einschränkungen sind Absicht: Das Programm darf gelegentlich Fehler machen, und in seltenen Pechfällen darf sogar das ganze Ergebnis schlecht sein.

Warum zwei Prisen Unsicherheit erlaubt sind

Eine perfekte Garantie wäre schön, ist aber unmöglich. Die Beispiele sind zufällig ausgewählt. Mit sehr kleiner Wahrscheinlichkeit erwischt man tausend Fotos, auf denen zufällig jede Katze auf einem roten Sofa sitzt. Dann lernt das Programm die falsche Regel, ohne dass jemand einen Fehler gemacht hätte. Gegen solches Pech kann keine Methode etwas ausrichten.

Deshalb arbeitet PAC-Lernen mit zwei Stellschrauben. Die eine beschreibt, wie viele Fehler das fertige Programm im Betrieb machen darf, etwa höchstens fünf Prozent. Die andere beschreibt, wie oft das Lernen komplett danebengehen darf, etwa in einem von hundert Durchläufen. Beide Werte darf man frei wählen und beliebig klein machen. Der Preis dafür sind mehr Trainingsbeispiele.

Der praktische Wert liegt in der Umkehrung dieser Rechnung. Statt zu raten, wie viele Daten man sammeln muss, lässt sich eine Zahl ausrechnen. Das war in den 1980er-Jahren neu. Der Informatiker Leslie Valiant erhielt für diese Idee 2010 den Turing Award, die wichtigste Auszeichnung der Informatik.

Die Rechnung hinter der Beispielzahl

Vor dem Lernen legt man fest, welche Arten von Regeln überhaupt in Frage kommen. Diese Menge heißt Hypothesenraum. Bei einem einfachen Modell könnten das alle geraden Trennlinien zwischen zwei Punktwolken sein. Bei einem großen neuronalen Netz ist der Raum astronomisch viel größer. Das Lernverfahren sucht darin die Regel, die zu den gesehenen Beispielen am besten passt.

Die entscheidende Größe ist, wie flexibel dieser Raum ist. Fachleute messen das mit der VC-Dimension, benannt nach den Mathematikern Vapnik und Chervonenkis. Sie gibt grob an, wie viele Punkte das Modell noch in jeder beliebigen Aufteilung sauber trennen könnte. Je höher dieser Wert, desto mehr Beispiele sind nötig. Die Theorie liefert dafür eine Formel: Die Beispielzahl wächst ungefähr proportional zur VC-Dimension und umgekehrt proportional zur erlaubten Fehlerquote.

Dahinter steckt eine anschauliche Spannung. Ein sehr starres Modell braucht wenige Beispiele, kann aber viele Zusammenhänge gar nicht darstellen. Ein sehr flexibles Modell kann fast alles darstellen, merkt sich aber leicht nur die Trainingsdaten auswendig. Dieses Auswendiglernen nennt man Überanpassung. PAC-Lernen macht den Zusammenhang zwischen Flexibilität und Datenbedarf zum ersten Mal messbar.

Was davon in heutigen Modellen übrig ist

Direkt anwenden kann man die Formeln bei großen Sprachmodellen kaum. Die berechneten Beispielzahlen fallen dort absurd hoch aus, viel höher als das, was in der Praxis tatsächlich reicht. Ein häufiger Irrtum ist deshalb, PAC-Lernen sei widerlegt. Richtig ist: Die Theorie liefert eine Garantie für den schlechtestmöglichen Fall, und echte Daten sind fast nie so bösartig.

Die Denkweise prägt das Feld trotzdem bis heute. Der Grundsatz, Modelle nie auf denselben Daten zu bewerten, mit denen sie trainiert wurden, stammt aus dieser Ecke. Auch Sätze wie „mehr Trainingsdaten helfen, aber mit abnehmendem Ertrag“ sind eine Alltagsfassung der PAC-Formeln.

Begegnen wird man dem Begriff vor allem in Vorlesungen zu maschinellem Lernen und in Forschungsarbeiten. In Produktankündigungen taucht er selten auf. Wer aber Meldungen liest, in denen es um Datenmengen, Generalisierung oder Überanpassung geht, liest indirekt über PAC-Lernen mit.