Probably Approximately Correct Learning

Wahrscheinlich Annähernd Richtiges Lernen (WARL) o​der englisch Probably approximately correct learning (PAC learning) i​st ein Framework für d​as maschinelle Lernen, d​as von Leslie Valiant i​n seinem Paper A theory o​f the learnable[1] eingeführt wurde.

In diesem Framework erhält d​ie lernende Einheit Beispiele, d​ie gemäß e​iner bestimmten Funktion klassifiziert sind. Das Ziel d​es Trainings i​st es, m​it großer Wahrscheinlichkeit e​ine Annäherung dieser Funktion z​u finden. Man erwartet v​on der lernenden Einheit, d​as Konzept m​it einer beliebigen Annäherungsrate, e​iner beliebigen Erfolgswahrscheinlichkeit u​nd einer beliebigen Verteilung d​er Beispiele z​u lernen.

Definition

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

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

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

Die Abschätzung für d​ie Anzahl benötigter Beispiele m i​st meist s​ehr grob u​nd in d​er Praxis reichen weniger Beispiele aus. Dieses Modell w​urde noch erweitert, u​m mit Rauschen, a​lso falsch klassifizierten Beispielen, umgehen z​u können.

Referenzen

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

Literatur

• 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.