Computational learning theory

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)

Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Bitte entferne erst danach diese Warnmarkierung.

In der theoretischen Informatik ist die Computer-Lerntheorie ein mathematisches Feld, welches sich auf die Analyse von Maschinen-Lern-Algorithmen bezieht.

Überblick

Theoretische Ergebnisse beim maschinellen Lernen behandeln hauptsächlich den Typ des Induktiven Lernens - das überwachte Lernen. Beim überwachten Lernen werden einem Algorithmus Beispiele mit nützliche Kommentaren gegeben. Zum Beispiel könnten die Beispiele Beschreibungen von Pilzen sein und der Kommentar ein Hinweis darauf, ob sie essbar sind. Der Algorithmus nimmt nun die vorherigen kommentierten Beispiele und benutzt sie um eine Klassifizierung durchzuführen. Diese Klassifizierung ist eine Funktion des Algorithmus, die Kommentare Beispielen zuordnet - inklusive Beispielen, die er noch nie zuvor gesehen hat. Das Ziel des Algorithmus vom überwachten Lernen ist die Erkennung zu optimieren - z.B. die Nummer von Fehlern, die bei neuen Beispielen gemacht wird, zu verringern.

Zusätzlich zu Performance Begrenzungen studieren die Personen hinter der Computer-Lerntheorie die Zeit Komplexität und Machbarkeit des Lernens. Zurzeit gilt eine Berechnung als machbar, wenn sie in Polynomialzeit durchgeführt werden kann. Es gibt zwei Arten von Komplexitäts-Ergebnissen:

• Positive Ergebnisse - Zeigen, dass eine bestimmte Klasse von Funktionen in Polynomialzeit lernbar ist.
• Negative Ergebnisse - Zeigen, dass eine bestimmte Klasse nicht in Polynomialzeit lernbar ist.

Negative Ergebnisse werden nur durch Annahmen bewiesen. Annahmen, die in negativen Ergebnissen Standard sind, sind:

• Komplexitätstheorie - P ≠ NP
• Kryptographie - Einwegfunktionen existieren

Es gibt viele verschiedene Ansätze zur zur Computer-Lerntheorie. Diese Unterschiede basieren auf Annahmen über die Schlussfolgerungs Prinzipien, welche verwendet werden um die limitierten Daten zu generalisieren. Dies umschließt verschiedene Definitionen von Wahrscheinlichkeit (Frequentistischer Wahrscheinlichkeitsbegriff, Bayessche Statistik) und verschiedene Annahmen über die Generierung von Beispielen. Die verschiedenen Ansätze sind unter anderem:

• Wahrscheinlich annähernd richtiges Lernen (WARL), von Leslie Valiant
• VC Theorie, von Wladimir Wapnik
• Bayessche Statistik, aus der Arbeit von Thomas Bayes
• Algoriethmische Lern Theorie, aus der Arbeit von E.M. Gold
• Online Maschinen Lernen, aus der Arbeit von Nick Littlestone

Die Computer-Lerntheorie hat zu vielen praktischen Algorithmen geführt. Zum Beispiel hat die WARL Theorie Boosting inspiriert, die VC Theorie führte zum Support Vector Machine und die Bayessche Statistik zum Bayessches Netz Algorithmus.