WikiDer > Computergestützte Lerntheorie

Computationele leertheorie

Das Computergestützte Lerntheorie ist Teil von Theoretische Informatik in welchen Algorithmen in der maschinelles Lernen werden analysiert.

Überblick

In der Theorie des computergestützten Lernens wird hauptsächlich an einer Methode des induktiven Lernens geforscht, die: überwachtes Lernen wird genannt. Beim überwachten Lernen wird ein Algorithmus mit Beispielen (Proben), die vom Betreuer auf sinnvolle Weise beschriftet werden. Die Proben können zum Beispiel Beschreibungen von Pilzen sein und die Etiketten können anzeigen, ob die Pilze essbar sind oder nicht. Der Algorithmus leitet eine Klassifizierungsfunktion aus den zuvor gekennzeichneten Abtastwerten ab. Diese Klassifizierungsfunktion weist Samples Labels zu, einschließlich Samples, die der Algorithmus noch nie zuvor gefunden hat. Das Ziel eines überwachten Lernalgorithmus besteht darin, die Leistung in einem bestimmten Bereich zu optimieren, beispielsweise um die Anzahl der Fehler bei neuen Abtastwerten zu minimieren.

Neben den Grenzen von Algorithmen des maschinellen Lernens untersuchen Theoretiker des Computational Learning auch die Zeitkomplexität und Machbarkeit des Lernens. In der computergestützten Lerntheorie gilt eine Berechnung als machbar, wenn Polynomzeit durchgeführt werden kann. Es gibt zwei Arten von Zeitkomplexitätsergebnissen:

  • positive Resultate Zeigen Sie, dass eine Klasse von Funktionen in polynomieller Zeit gelernt werden kann;
  • negative Ergebnisse Zeigen Sie, dass eine Klasse von Funktionen nicht in polynomieller Zeit gelernt werden kann.

Negative Ergebnisse hängen normalerweise von Annahmen ab. Häufige Annahmen bei negativen Ergebnissen sind:

  • Rechenkomplexität: P ≠ NP
  • Kryptographie - Einwegfunktionen vorhanden.

Es gibt mehrere Methoden in der computergestützten Lerntheorie. Sie unterscheiden sich in den Annahmen über die Prinzipien von Inferenz verwendet, um auf der Grundlage einer begrenzten Datenmenge allgemeine Schlussfolgerungen zu ziehen. Dazu gehört die verwendete Form von Wahrscheinlichkeit (zum Beispiel frequentistische Wahrscheinlichkeitstheorie und Bayessche Wahrscheinlichkeit) und die unterschiedlichen Annahmen zur Musterherstellung. Beispiele für die verschiedenen Ansätze sind:

  • wahrscheinlich ungefähr richtiges Lernen (PAC-Lernen), entwickelt von Leslie Valiant;
  • VC-Theorie, entwickelt von Vladimir Vapnik;
  • Bayessche Statistik, entstand aus einer Forschung, die gestartet wurde von Thomas Bayes.
  • algorithmische Lerntheorie, entwickelt von E. M. Gold;
  • Online-Maschinelles Lernen, entwickelt von Nick Littlestone.

Die computergestützte Lerntheorie hat eine Reihe praktischer Algorithmen hervorgebracht. Boosting beispielsweise entstand auf Basis der PAC-Theorie, während die VC-Theorie vorsah Support-Vektor-Maschinen auf und verwenden Bayessche Statistik entwickelt Judäa PerleWahrscheinlichkeitsnetzwerke.

Siehe auch

Literaturverzeichnis

Zu untersuchen

  • Angluin, D. 1992. „Computergestützte Lerntheorie: Übersicht und ausgewählte Bibliographie.“ In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Mai 1992), S. 351-369. http://portal.acm.org/citation.cfm?id=129712.129746
  • Haussler, D. 1990. „Wahrscheinlich ungefähr richtiges Lernen.“ In: AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA. S. 1101-1108. Amerikanische Vereinigung für Künstliche Intelligenz. http://citeseer.ist.psu.edu/haussler90probably.html

VC-Theorie

  • Vapnik, V. und A. Chervonenkis. 1971. Über die gleichmäßige Konvergenz relativer Häufigkeiten von Ereignissen zu ihren Wahrscheinlichkeiten. Wahrscheinlichkeitstheorie und ihre Anwendungen, 16(2). S. 264-280.

Merkmalsauswahl

Induktive Inferenz

  • Gold, E. M., Spracherkennung im Limit. Information und Kontrolle. 10. S. 447-474.

Erlernen der optimalen O-Notation

Negative Ergebnisse

  • Kearns, M. und Leslie Valiant. 1989. „Kryptographische Beschränkungen beim Lernen boolescher Formeln und endlicher Automaten.“ In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, S. 433-444. http://citeseer.ist.psu.edu/kearns89cryptographic.html

erhöhen

Ockhams Rasiermesser

  • Blumer, A., A. Ehrenfeucht, D. Haussler und M.K. Wärme. 1987. "Occams Rasiermesser." Im: Inf.Proc.Lett. 24. Seite 377-380.
  • Blumer, A., A. Ehrenfeucht, D. Haussler und M. K. Warmuth. 1989. „Erlernbarkeit und die Vapnik-Chervonenkis-Dimension.“ In: Zeitschrift der ACM 36(4). S. 929-865.

Wahrscheinlich ungefähr richtiges Lernen

  • Valiant, L., „Eine Theorie des Erlernbaren.“ In: Mitteilungen des ACM 27(11). S. 1134-1142.

Fehlertoleranz

Gleichwertigkeit

  • Haussler, D., M. Kearns, N. Littlestone und M. Warmuth. 1988. „Äquivalenz von Modellen für polynomielle Erlernbarkeit.“ In: proz. 1. ACM Workshop zu Computational Learning Theory S. 42-55.
  • Pitt, L. und M.K. Warmuth. 1990. „Vorhersage bewahrende Reduktion“ In: Zeitschrift für Computersystem und Wissenschaft 41 S. 430-467.

Externe Links