Probably Approximately Correct Learning

Wahrscheinlich Annähernd Richtiges Lernen

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.

DefinitionBearbeiten

Das PAC-Framework erlaubt eine genaue mathematische Analyse von Lernverfahren.   sei der endliche Hypothesenraum.   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   und  . Einem konsistenten Lernverfahren reichen dann   Trainingsbeispiele aus, um einen Klassifikator mit den Anforderungen von   und   zu lernen. Mit anderen Worten,   Trainingsbeispiele reichen aus, um mit der Wahrscheinlichkeit von   ein PAC-lernbares Problem so zu lernen, dass auf neuen Daten eine Fehlerrate von maximal   zu erhalten. Dabei muss die Laufzeit bis zur Ausgabe des Klassifikators polynomiell in   und   sein. Für   gilt dabei

 

HerleitungBearbeiten

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   die Hypothesen, die einen echten Fehler mit Wahrscheinlichkeit größer   machen. So eine Hypothese ist mit Wahrscheinlichkeit   mit einem zufälligen Beispiel und mit Wahrscheinlichkeit   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  . Man benötigt eine Abschätzung in Abhängigkeit von der Anzahl an Trainingsbeispielen. Es gilt  . In mindestens   aller Fälle soll nach obiger Forderung keine Hypothese mit echtem Fehler größer als   im Versionsraum enthalten sein, d. h.  . Damit folgt   und Auflösung nach m ergibt

 .

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.

ReferenzenBearbeiten

  1. L. G. Valiant: A Theory of the Learnable. In: Communications of the ACM. Band 27(11), 1984, S. 1134–1142.[1] (PDF; 806 kB)

LiteraturBearbeiten

  • M. Kearns, U. Vazirani: An Introduction to Computational Learning Theory. MIT Press, 1994, ISBN 0-262-11193-4.
  • Tom M. Mitchell: Machine Learning. McGraw-Hill Education, 1997, ISBN 0-07-115467-1.