Computergestützte Lerntheorie

Die computergestützte Lerntheorie untersucht, welche Konzepte effizient aus Beispielen gelernt werden können, wobei Lernen als ein Problem der Berechnung und Stichprobenkomplexität behandelt wird.

Definition

Die computergestützte Lerntheorie ist die Untersuchung der Ressourcen, in Bezug auf Daten und Berechnung, die erforderlich sind, um Konzepte aus Beispielen zu lernen; im wahrscheinlich annähernd korrekten Modell ist eine Konzeptklasse lernbar, wenn ein Algorithmus aus einer polynomialen Anzahl von Stichproben und in polynomialer Zeit eine Hypothese ausgeben kann, die mit hoher Wahrscheinlichkeit genau ist.

Scope

Dieses Thema behandelt formale Modelle der Lernbarkeit: das wahrscheinlich annähernd korrekte Modell, das fragt, wann ein Konzept mit hoher Genauigkeit und hoher Wahrscheinlichkeit aus polynomisch vielen Beispielen und Berechnungen gelernt werden kann, die Modelle der Fehlergrenze und des Online-Lernens, schwache versus starke Lernbarkeit und Boosting sowie Verbindungen zur Berechnungskomplexität. Es befasst sich sowohl mit der statistischen als auch mit der algorithmischen Machbarkeit des Lernens.

Core questions

• Welche Konzeptklassen können effizient aus Beispielen gelernt werden?
• Wie viele Daten und Berechnungen erfordert das Lernen eines Konzepts?
• Welche Beziehung besteht zwischen schwacher und starker Lernbarkeit?
• Wie hängt Lernbarkeit mit der Berechnungskomplexität zusammen?

Key theories

Wahrscheinlich annähernd korrektes Lernen

Valiants Modell definiert eine Konzeptklasse als lernbar, wenn ein effizienter Algorithmus mit hoher Wahrscheinlichkeit eine Hypothese mit geringem Fehler aus polynomisch vielen Beispielen erzeugen kann, wodurch Lernbarkeit zu einer präzisen rechnerischen Frage wird.

Schwache Lernbarkeit und Boosting

Ein zentrales Ergebnis zeigt, dass jede Klasse, die etwas besser als der Zufall lernbar ist, auch stark lernbar ist, was direkt zu Boosting-Algorithmen führte, die schwache Lerner zu präzisen machen.

Statistische und rechnerische Grenzen

Die Lernbarkeit wird sowohl durch die Stichprobenkomplexität, die mit Kapazitätsmaßen verbunden ist, als auch durch die rechnerische Härte begrenzt, sodass einige Klassen statistisch lernbar, aber rechnerisch unlösbar sind.

Clinical relevance

Die computergestützte Lerntheorie liefert die formale Grundlage dafür, was Lernalgorithmen erreichen können und was nicht, und inspirierte direkt praktische Methoden, insbesondere das Boosting, das aus der Frage entstand, ob schwache Lerner zu starken kombiniert werden könnten; sie rahmt das Lernen als eine rigorose rechnerische Disziplin ein.

History

Valiant führte 1984 das wahrscheinlich annähernd korrekte Modell ein, das dem Lernen eine präzise rechnerische Definition gab und das Feld begründete. Nachfolgende Arbeiten etablierten Charakterisierungen der Stichprobenkomplexität, die Äquivalenz von schwacher und starker Lernbarkeit, die das Boosting motivierte, und Härteergebnisse, die die rechnerischen Grenzen des Lernens aufzeigten.

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

Was bedeutet „wahrscheinlich annähernd korrekt“?

Es bedeutet, dass der Lerner mit hoher Wahrscheinlichkeit über die Zufallsstichprobe eine Hypothese ausgibt, die annähernd korrekt ist, d. h. einen geringen Fehler bei zukünftigen Daten aufweist. Lernbarkeit erfordert, dies aus einer Anzahl von Beispielen und einem Rechenaufwand zu erreichen, die nur polynomial wachsen.

Wie führte die Lerntheorie zum Boosting?

Forscher fragten, ob ein Lerner, der nur geringfügig besser als zufälliges Raten ist, in einen hochpräzisen umgewandelt werden könnte. Der Beweis, dass schwache und starke Lernbarkeit äquivalent sind, war konstruktiv, und diese Konstruktion wurde zu den Boosting-Algorithmen, die in der Praxis weit verbreitet sind.