Philosophie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

Autor Begriff Zusammenfassung/Zitate Quellen

Peter Norvig über Lerntheorie – Lexikon der Argumente

Norvig I 713
Lerntheorie/Norvig/Russell: [Hauptproblem:] Wie können wir sicher sein, dass unser Lernalgorithmus eine Hypothese aufgestellt hat, die den richtigen Wert für bisher ungesehene Inputs vorhersagen kann? Wie können wir formal gesehen wissen, dass die Hypothese h nahe an der Zielfunktion f liegt, wenn wir nicht wissen, was f ist? Über diese Fragen wird seit mehreren Jahrhunderten nachgedacht.
In den letzten Jahrzehnten sind andere Fragen aufgetaucht: Wie viele Beispiele brauchen wir, um eine gute Hypothese h zu erhalten? Welchen Hypothesenraum sollten wir verwenden? Wenn der Hypothesenraum sehr komplex ist, können wir dann überhaupt das beste h finden, oder müssen wir uns mit einem lokalen Maximum im
Norvig I 714
Hypothesenraum begnügen? Wie komplex sollte h sein? Wie vermeiden wir eine Überanpassung (overfitting)? (>Entscheidungsbaum/Norvig, >Komplexität/Norvig, >Lernen/KI-Forschung).
Computational learning theory: (...) liegt an der Schnittstelle von KI, Statistik und theoretischer Informatik. Das zugrundeliegende Prinzip ist, dass jede Hypothese, die ernsthaft falsch ist, mit hoher Wahrscheinlichkeit nach einer kleinen Anzahl von Beispielen "entdeckt" wird, weil sie eine falsche Vorhersage macht. Daher ist es unwahrscheinlich, dass eine Hypothese, die mit einer ausreichend großen Anzahl von Trainingsbeispielen übereinstimmt, ernsthaft falsch ist: das heißt, sie muss wahrscheinlich annähernd richtig sein.
PAC: Jeder Lernalgorithmus, der Hypothesen hervorbringt, die wahrscheinlich annähernd richtig sind, wird als PAC-Lernalgorithmus bezeichnet; wir können diesen Ansatz verwenden, um Grenzen für die Leistung verschiedener Lernalgorithmen festzulegen.
Annahme der Stationarität: Zukünftige Beispiele werden aus der gleichen festgelegten Verteilung P(E)=P(X, Y ) wie frühere Beispiele gezogen.
Richtigkeit: Eine Hypothese h wird als annähernd richtig bezeichnet, wenn der Fehler (h) ≤ ϵ ist, wobei es sich bei ϵ um eine kleine Konstante handelt. Wir werden zeigen, dass wir ein N finden können, sodass, nachdem wir N Beispiele gesehen haben, mit hoher Wahrscheinlichkeit alle konsistenten Hypothesen annähernd richtig sein werden. >Lernen/KI-Forschung, >Künstliche Neuronale Netze.
Norvig I 757
Die computational learning theory analysiert die Komplexität der Stichprobe (sample complexity) und die Berechnungskomplexität (computational complexity) des induktiven Lernens. Es gibt einen Tradeoff zwischen der Expressivität der Sprache der Hypothese und der Leichtigkeit des Lernens.
Die lineare Regression ist ein weit verbreitetes Modell. Die optimalen Parameter eines Modells der linearen Regression können durch eine gradient descent search gefunden oder exakt berechnet werden.
Ein linearer Klassifikator mit einem hard threshold - auch als Perzeptron bekannt - kann durch eine einfache Regel zur Aktualisierung der Gewichte so trainiert werden, dass er zu Daten passt, welche linear trennbar sind. In anderen Fällen konvergiert die Regel nicht.
Norvig I 759
Geschichte: Die Theorie des PAC-Lernens wurde von Leslie Valiant (1984)(1) eingeführt. In seiner Arbeit betonte er die Wichtigkeit der Berechnungs- und Stichprobenkomplexität. Zusammen mit Michael Kearns (1990)(2) zeigte Valiant, dass sich mehrere Konzeptklassen nicht sinnvoll mittels PAC-Lernen erlernen lassen, obwohl in den Beispielen genügend Informationen vorhanden sind. Einige positive Ergebnisse wurden für Klassen wie z.B. Entscheidungslisten erzielt (Rivest, 1987)(3).
Eine unabhängige Tradition der Analyse von Stichprobenkomplexität hat in der Statistik existiert, beginnend mit den Arbeiten zur einheitlichen Konvergenztheorie (Vapnik und Chervonenkis, 1971)(4).
Die sogenannte VC-Dimension liefert ein Maß, das in etwa analog zum, aber allgemeiner als das aus der PAC-Analyse gewonnene ln |H| Maß ist. Die VC-Dimension kann auf kontinuierliche Funktionsklassen angewendet werden, auf die die herkömmliche PAC-Analyse nicht anwendbar ist. Die PAC-Lerntheorie und die C-Theorie wurden zunächst durch die "vier Deutschen" (von denen keiner tatsächlich deutsch ist) miteinander verbunden: Blumer, Ehrenfeucht, Haussler und Warmuth (1989)(5).
Die lineare Regression mit quadratischem Fehlerverlust geht auf Legendre (1805)(6) und Gauss (1809)(7) zurück, die beide an der Vorhersage von Umlaufbahnen um die Sonne arbeiteten. Die moderne Verwendung der multivariaten Regression für machine learning wird in Texten wie Bishop (2007)(8) behandelt. Ng (2004)(9) analysierte die Unterschiede zwischen der Regularisierung von L1- und L2.


1. Valiant, L. (1984). A theory of the learnable. CACM, 27, 1134-1142.
2. Kearns, M. (1990). The Computational Complexity of Machine Learning. MIT Press.
3. Rivest, R. (1987). Learning decision lists. Machine Learning, 2(3), 229-246.
4. Vapnik, V. N. and Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16, 264-280.
5. Blumer, A., Ehrenfeucht, A., Haussler, D., andWarmuth, M. (1989). Learnability and the Vapnik-
Chervonenkis dimension. JACM, 36(4), 929–965.
6. Legendre, A. M. (1805). Nouvelles méthodes pour la détermination des orbites des comètes.
7. Gauss, C. F. (1809). Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Ambientium.
Sumtibus F. Perthes et I. H. Besser, Hamburg.


_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link
> Gegenargumente gegen Norvig
> Gegenargumente zu Lerntheorie

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Y   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z