Was bedeutet PAC-Lerntheorie?

Ich bin neu im maschinellen Lernen. Ich studiere einen Kurs in maschinellem Lernen (Stanford University) und habe nicht verstanden, was mit dieser Theorie gemeint ist und welchen Nutzen sie hat. Ich frage mich, ob jemand diese Theorie für mich detaillieren könnte.

Diese Theorie basiert auf dieser Gleichung.

Die wahrscheinlich ungefähr korrekte Lerntheorie (PAC) hilft zu analysieren, ob und unter welchen Bedingungen ein Lernender wahrscheinlich einen ungefähr korrekten Klassifikator ausgeben wird. (Einige Quellen verwenden anstelle von )A $L$$A$$L$

Definieren wir zunächst "ungefähr". Eine Hypothese ist annähernd richtig, wenn ihr Fehler über die Verteilung der Eingaben durch etwasDas heißt, , wobei die Verteilung über die Eingaben ist.ε , 0 ≤ ε ≤ $h \in H$errorD(h)<ϵ$\epsilon, 0 \le \epsilon \le \frac{1}{2}.$$error_D(h)\lt \epsilon$$D$

Als nächstes "wahrscheinlich". Wenn einen solchen Klassifikator mit der Wahrscheinlichkeit ausgibt , mit , nennen wir diesen Klassifikator wahrscheinlich ungefähr korrekt.1 - δ 0 ≤ δ ≤ $L$$1 - \delta$$0 \le \delta \le \frac{1}{2}$

Wenn Sie wissen, dass ein Zielkonzept PAC-lernbar ist, können Sie die Stichprobengröße einschränken, die erforderlich ist, um wahrscheinlich einen ungefähr korrekten Klassifikator zu lernen. Dies wird in der von Ihnen reproduzierten Formel gezeigt:

Beachten Sie die Auswirkungen auf wenn Sie die Variablen auf der rechten Seite ändern, um sich ein Bild davon zu machen. Wenn der zulässige Fehler abnimmt , nimmt die erforderliche Stichprobengröße zu. Ebenso wächst er mit der Wahrscheinlichkeit einer annähernd korrekten Lernenden, und mit der Größe des Raumes Hypothese . (Ein Hypothesenraum ist locker die Menge von Klassifikatoren, die Ihr Algorithmus berücksichtigt.) Wenn Sie mehr mögliche Klassifikatoren in Betracht ziehen oder einen geringeren Fehler oder eine höhere Wahrscheinlichkeit für die Richtigkeit wünschen, benötigen Sie mehr Daten, um zwischen ihnen zu unterscheiden.$m$$H$

Für mehr können dieses und andere verwandte Videos hilfreich sein, wie zum Beispiel diese lange Einführung oder einer von vielen Texten zum maschinellen Lernen , wie zum Beispiel Mitchell .

Die Definition von wahrscheinlich ungefähr korrekt ist Valiant zu verdanken. Es soll eine mathematisch strenge Definition dessen geben, was maschinelles Lernen ist.
Lass mich ein bisschen streifen. Während PAC den Begriff "Hypothese" verwendet, verwenden die meisten Menschen das Wortmodell anstelle der Hypothese. Mit einer Anspielung auf die Statistik-Community bevorzuge ich model, aber ich werde versuchen, beide zu verwenden. Maschinelles Lernen beginnt mit einigen Daten, und man will eine Hypothese oder das Modell finden , das wird angesichts der Eingänge zurückkehren oder etwas ganz in der Nähe. Noch wichtiger ist, dass das Modell bei neuen Daten die entsprechende berechnet oder vorhersagt .x i y i ˜ x ˜ $(x_i, y_i)$$x_i$$y_i$$\tilde{x}$$\tilde{y}$
Wirklich interessiert es nicht, wie genau die Hypothese auf den gegebenen (Trainings-) Daten ist, außer dass es kaum zu glauben ist, dass ein Modell, das unter Verwendung einiger Daten erstellt wurde, diesen Datensatz nicht genau widerspiegelt, sondern in Zukunft genau sein wird Datensätze. Die beiden wichtigen Vorbehalte sind, dass man neue Daten nicht mit 100% iger Genauigkeit vorhersagen kann und dass die Datenbeispiele, die man gesehen hat, möglicherweise etwas Wichtiges verpassen. Ein Spielzeugbeispiel wäre, wenn ich Ihnen die 'Daten' 1,2,3,4 geben würde, würde man 'vorhersagen', dass 5 die nächste Zahl sein würde. Wenn Sie dies testen, indem Sie Leute fragen, was die nächste Nummer in der Sequenz ist, würden die meisten Leute sagen 5. Jemand könnte esaber sagen 1.000.000. Wenn Sie die Sequenz 1, 2, 3, ..., 999, 999 hätten, wäre man sicherer, dass die nächste Zahl 1.000.000 ist. Die nächste Zahl könnte jedoch 999.999,5 oder sogar 5 sein. Der Punkt ist, je mehr Daten man sieht, desto sicherer kann man sein, dass man ein genaues Modell erstellt hat, aber man kann nie absolut sicher sein.

Die Definition von wahrscheinlich ungefähr richtig gibt eine mathematisch genaue Version dieser Idee. Bei gegebenen Daten mit der Ausgabe und einer Klasse von Modellen die die Hypothesen bilden, kann man 2 Fragen stellen. Können wir die Daten verwenden, um eine bestimmte Hypothese für zu finden, die bei der Vorhersage neuer Werte wahrscheinlich sehr genau ist? Wie wahrscheinlich ist es außerdem, dass das Modell so genau ist, wie wir es erwarten? Das heißt, wir können ein Modell trainieren, das höchstwahrscheinlich sehr genau ist. Wie in der Antwort von Sean Easter sagen wir, dass eine Klasse von Hypothesen (Klasse von Modellen) PAC ist, wenn wir ein Epsilon-Delta-Argument machen können. Das heißt, wir können mit der Wahrscheinlichkeit sagen, dass unser Modelly i f θ f Θ p > 1 - $x_i, 1 \leq i \leq m$$y_i$$f_{\theta}$$f_{\Theta}$$p >1-\delta$$f_{\Theta}$ ist innerhalb von genau . Wie viele Daten man sehen muss, um ein bestimmtes Paar zu erfüllen hängt vom tatsächlichen Wert und davon, wie komplex die angegebene Klasse von Hypothesen ist.$\epsilon$$(\delta,\epsilon)$$(\delta,\epsilon)$

Genauer gesagt ist eine Klasse von Hypothesen oder Modellen PAC, wenn es für ein Paar mit ein bestimmtes Modell alle neuen Daten , dieses Modell mit erfüllen Wahrscheinlichkeit wenn das Modell mit mindestens Trainingsbeispielen ausgewählt (trainiert) wurde . Hier ist Err die gewählte Verlustfunktion, die normalerweise .$\mathcal{H}$$f_{\theta}$$(\epsilon, \delta)$$0 < \epsilon,\delta , <.5$$f_{\Theta}$$\tilde{x}, \tilde{y}$$Err(f_{\Theta}(\tilde{x}) ,\tilde{y} ) < \epsilon$$p > 1-\delta$$m = m(\delta,\epsilon,\mathcal{H})$$(f_{\Theta}(\tilde{x}) -\tilde{y})^2$

Das Diagramm, das Sie haben, gibt eine Formel dafür an, wie viele Daten für eine bestimmte Klasse von Hypothesen trainiert werden müssen, um ein bestimmtes Paar zu erfüllen . Ich könnte mich irren, aber ich glaube, dass diese Definition von Valiant in einem Artikel mit dem Titel "A Theory of the Learnable" gegeben wurde und teilweise dafür verantwortlich war, dass Valiant den Turing-Preis gewann.$(\delta,\epsilon)$