Probably Approximately Correct Learning

Probably Approximately Correct Learning

Wahrscheinlich Annähernd Richtiges Lernen (WARL) oder englisch Probably approximately correct learning (PAC learning) ist ein Framework für das maschinelle Lernen, das von Leslie Valiant in seinem Paper A theory of the learnable[1] eingeführt wurde.

In diesem Framework erhält die lernende Einheit Beispiele, die gemäß einer bestimmten Funktion klassifiziert sind. Das Ziel des Trainings ist es, mit großer Wahrscheinlichkeit eine Annäherung dieser Funktion zu finden. Man erwartet von der lernenden Einheit, das Konzept mit einer beliebigen Annäherungsrate, einer beliebigen Erfolgswahrscheinlichkeit und einer beliebigen Verteilung der Beispiele zu lernen.

Inhaltsverzeichnis

Definition

Das PAC-Framework erlaubt eine genaue mathematische Analyse von Lernverfahren. H sei der endliche Hypothesenraum. \epsilon sei die gewünschte Genauigkeit des vom Lernverfahren erzeugten Klassifikators bei ungesehenen Daten. δ sei die Wahrscheinlichkeit, dass das Lernverfahren so einen Klassifikator nicht erzeugen kann. Es gelte 0 < \epsilon < 0.5 und 0 < δ < 0.5. Einem konsistenten Lernverfahren reichen dann m Trainingsbeispiele aus, um einen Klassifikator mit den Anforderungen von \epsilon und δ zu lernen. Mit anderen Worten, m Trainingsbeispiele reichen aus, um mit der Wahrscheinlichkeit von 1 − δ ein PAC-lernbares Problem so zu lernen, dass auf neuen Daten eine Fehlerrate von maximal 1-\epsilon zu erhalten. Dabei muss die Laufzeit bis zur Ausgabe des Klassifikators polynomiell in \frac{1}{\epsilon}, \frac{1}{\delta} und m sein. Für m gilt dabei

m\geq\frac{1}{\epsilon}\left(\ln(|H|)+\ln\left(\frac{1}{\delta}\right)\right)

Herleitung

Die Abschätzung für m ist eng mit dem Versionsraum verbunden. Ein konsistentes Lernverfahren gibt definitionsgemäß eine Hypothese aus dem Versionsraum aus. Jede Hypothese im Versionsraum ist konsistent mit den Trainingsdaten, kann jedoch auf ungesehenen Daten Fehler machen. Seien h_1,\ldots,h_\ell die Hypothesen, die einen echten Fehler mit Wahrscheinlichkeit größer \epsilon machen. So eine Hypothese ist mit Wahrscheinlichkeit 1-\epsilon mit einem zufälligen Beispiel und mit Wahrscheinlichkeit (1-\epsilon)^m mit m Beispielen konsistent. Existiert mindestens eine solche Hypothese, dann ist sie Teil des Versionsraums und könnte von einem konsistenten Lernverfahren als Hypothese ausgegeben werden. Die Wahrscheinlichkeit, dass im Versionsraum eine solche Hypothese enthalten ist, ist nach oben beschränkt durch \ell (1-\epsilon)^m. Man benötigt eine Abschätzung in Abhängigkeit von der Anzahl an Trainingsbeispielen. Es gilt \ell (1 - \epsilon)^m \leq |H|(1-\epsilon)^m \leq |H| e^{- \epsilon m}. In mindestens 1 − δ aller Fälle soll nach obiger Forderung keine Hypothese mit echtem Fehler größer als \epsilon im Versionsraum enthalten sein, d.h. 1-|H| e^{-\epsilon m} > 1-\delta. Damit folgt |H| e^{-\epsilon m} \leq \delta und Auflösung nach m ergibt

m \geq \frac{1}{\epsilon}\left(\ln(|H|)+\ln\left(\frac{1}{\delta}\right)\right).

Die Abschätzung für die Anzahl benötigter Beispiele m ist meist sehr grob und in der Praxis reichen weniger Beispiele aus. Dieses Modell wurde noch erweitert, um mit Rauschen, also falsch klassifizierten Beispielen, umgehen zu können.

Referenzen

  1. L. G. Valiant: A Theory of the Learnable. In: Communications of the ACM. 27(11), 1984, S. 1134-1142.[1]

Literatur

  • M. Kearns, U. Vazirani: An Introduction to Computational Learning Theory. MIT Press, 1994, ISBN 0262111934.
  • Tom M. Mitchell: Machine Learning. McGraw-Hill Education, 1997, ISBN 0071154671.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Probably approximately correct learning — In computational learning theory, probably approximately correct learning (PAC learning) is a framework for mathematical analysis of machine learning. It was proposed in 1984 by Leslie Valiant.[1] In this framework, the learner receives samples… …   Wikipedia

  • Computational learning theory — In theoretical computer science, computational learning theory is a mathematical field related to the analysis of machine learning algorithms. Contents 1 Overview 2 See also 3 References 3.1 Surveys …   Wikipedia

  • Algorithmic learning theory — (or algorithmic inductive inference) is a framework for machine learning.The framework was introduced in E. Mark Gold s seminal paper Language identification in the limit . The objective of language identification is for a machine running one… …   Wikipedia

  • Supervised learning — is a machine learning technique for learning a function from training data. The training data consist of pairs of input objects (typically vectors), and desired outputs. The output of the functioncan be a continuous value (called regression), or… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • WARL — Wahrscheinlich Annähernd Richtiges Lernen (WARL) oder englisch Probably approximately correct learning (PAC learning) ist ein Framework für das maschinelle Lernen, das von Leslie Valiant in seinem Paper A theory of the learnable[1] eingeführt… …   Deutsch Wikipedia

  • Warl — Wahrscheinlich Annähernd Richtiges Lernen (WARL) oder englisch Probably approximately correct learning (PAC learning) ist ein Framework für das maschinelle Lernen, das von Leslie Valiant in seinem Paper A theory of the learnable[1] eingeführt… …   Deutsch Wikipedia

  • History of virtual learning environments — A virtual learning environment (VLE) is a system that creates an environment designed to facilitate teachers in the management of educational courses for their students, especially a system using computer hardware and software, which involves… …   Wikipedia

  • Вэлиант, Лесли — Лесли Вэлиант Leslie Valiant Дата рождения …   Википедия

  • Hypothesis Theory — is a psychological theory of learning developed during the 1960s and 1970 s. Experimental Framework In the basic experimental framework, the subject is presented with a series of multidimensional stimuli, and provided feedback about the class of… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”