Richtiges PAC-Lernen VC-Dimensionsgrenzen

11

Es ist bekannt, dass für eine Konzeptklasse mit der VC-Dimension d ausreicht, um O ( d) zu erhaltenCdmarkierte Beispiele lernen PACC. Mir ist nicht klar, ob der PAC-Lernalgorithmus (der diese vielen Beispiele verwendet) richtig oder unpassend ist. In den Lehrbüchern von Kearns und Vazirani sowie Anthony und Biggs scheint der PAC-Lernalgorithmus nicht korrekt zu sein (dh die Ausgabehypothese liegt nicht inC).O(dεlog1ε)CC

  1. Könnte jemand klären, ob eine ähnliche Obergrenze auch für die richtige PAC-Lerneinstellung gilt? Wenn ja, können Sie mir eine Referenz geben, in der dies ausdrücklich erwähnt wird und die auch einen in sich geschlossenen Beweis enthält?

  2. Kürzlich hat Hanneke diese Grenze verbessert, indem er den -Faktor beseitigt hat. Könnte jemand klären, ob bekannt ist, dass das Protokoll ( 1 / ε ) für die richtige PAC-Lerneinstellung entfernbar ist? Oder ist es noch eine offene Frage?log(1/ε)log(1/ε)

Anonym
quelle
Auf welches Hanneke-Papier beziehen Sie sich?
Gradstudent
1
@gradstudent arxiv.org/abs/1507.00473
Clement C.

Antworten:

9

Ich danke Aryeh , dass er mich auf diese Frage aufmerksam gemacht hat.

Wie andere erwähnt haben, lautet die Antwort auf (1) Ja , und die einfache Methode der empirischen Risikominimierung in C erreicht die Komplexität der O((d/ε)log(1/ε)) -Stichprobe (siehe Vapnik und Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler und Warmuth, 1989).

Was (2) betrifft, so ist tatsächlich bekannt, dass es Räume C denen kein geeigneter Lernalgorithmus eine bessere als die Probenkomplexität von Ω((d/ε)log(1/ε)) erreicht und daher das richtige Lernen nicht das optimale O(d/ε) Probenkomplexität. Meines Wissens wurde diese Tatsache nie veröffentlicht, sondern basiert auf einem verwandten Argument von Daniely und Shalev-Shwartz (COLT 2014) (ursprünglich formuliert für eine andere, aber verwandte Frage beim Lernen in mehreren Klassen).

Betrachten Sie den einfachen Fall d=1 und setzen Sie den Raum X als {1,2,...,1/ε} und C sind Singletons fz(x):=I[x=z],zX : Das heißt, jeder Klassifikator in C klassifiziert genau einen Punkt von X als 1 und die anderen als 0. Für die untere Grenze, die Zielfunktion als Zufall Singletons nehmen fx , wobei xUniform(X) und P , die Randverteilung von X , ist einheitlich auf X{x} . Jetzt sieht der Lernende keine Beispiele mit der Bezeichnung 1 , sondern muss einen Punkt z auswählen, um zu erraten , dass er mit 1 (wichtig ist, dass die Funktion "Alle Nullen" nicht in C, So dass jeder richtigen Lerner muss etwas erraten , z ), und bis er jeden Punkt in gesehen hat X{x} es mindestens 1/2 Wahrscheinlichkeit des falschen erraten ( das heißt die posteriore Wahrscheinlichkeit seines fz mit zx mindestens 1/2 ). Das Coupon-Collector-Argument impliziert, dass Ω ( ( 1 / ε ) log ( 1 / ε ) ) erforderlich wäre.Ω((1/ε)log(1/ε))Beispiele, um jeden Punkt in X{x} . Dies beweist also eine Untergrenze von Ω((1/ε)log(1/ε)) für alle richtigen Lernenden.

Für allgemeines d>1 nehmen wir X als {1,2,...,d/(4ε)} , nimm C als Klassifikatoren IA für Mengen AX der Größe genau d , wähle die Zielfunktion zufällig aus C und nimm P erneut als einheitlich nur für die Punkte, die die Zielfunktion 0 klassifiziert ( Daher sieht der Lernende niemals einen Punkt mit der Bezeichnung 1). Dann impliziert eine Verallgemeinerung des Coupon-Collector-Arguments, dass wir Ω((d/ε)log(1/ε)) Samples benötigen , um mindestens |X|2d verschiedene Punkte von X , und ohne dass dies viele verschiedenen Punkten jeder richtiger Lernenden hat zumindest zu Sehen 1/3 Glück größer immer als d/4 seinen guess A von d Punkten falsch in der gewählten Hypothese hAwas bedeutet, dass seine Fehlerrate größer als ε . In diesem Fall gibt es also keinen richtigen Lernenden mit einer Probenkomplexität von weniger als Ω((d/ε)log(1/ε)) , was bedeutet, dass kein richtiger Lernender die optimale Probenkomplexität O(d/ε) .

Beachten Sie, dass das Ergebnis sehr spezifisch für den konstruierten Raum C . Es gibt Räume C denen richtige Lernende die O(d/ε) -optimale Stichprobenkomplexität erreichen können, und tatsächlich sogar den exakten vollständigen Ausdruck O((d/ε)+(1/ε)log(1/δ)) aus ( Hanneke, 2016a). In (Hanneke, 2016b) wurden einige Ober- und Untergrenzen für allgemeine ERM-Lernende entwickelt, die anhand der Eigenschaften des Raums C quantifiziert wurdenCsowie einige speziellere Fälle zu diskutieren, in denen bestimmte richtige Lernende manchmal die optimale Komplexität der Stichprobe erreichen können.

Verweise:

Vapnik und Chervonenkis (1974). Theorie der Mustererkennung. Nauka, Moskau, 1974.

Blumer, Ehrenfeucht, Haussler und Warmuth (1989). Lernfähigkeit und die Vapnik-Chervonenkis-Dimension. Zeitschrift der Association for Computing Machinery, 36 (4): 929–965.

Daniely und Shalev-Shwartz (2014). Optimale Lerner für Probleme mit mehreren Klassen. In Proceedings der 27. Konferenz über Lerntheorie.

Hanneke (2016a). Die optimale Stichprobenkomplexität des PAC-Lernens. Journal of Machine Learning Research. 17 (38), S. 1-15.

Hanneke (2016b). Verfeinerte Fehlergrenzen für mehrere Lernalgorithmen. Journal of Machine Learning Research. 17 (135), S. 1-55.

S. Hanneke
quelle
Interessant ... Gibt es eine kombinatorische Charakterisierung der Klassen für die das richtige PAC-Lernen stichprobenoptimal ist? Oder zumindest ausreichende Bedingungen (Schließung unter Kreuzung, Vereinigung?)C
Clement C.
2
@ClementC. Es ist keine vollständige Charakterisierung bekannt, welche Klassen optimale Raten aufweisen, die von geeigneten Lernenden im Allgemeinen erreicht werden können. Das referenzierte Papier "Verfeinerte Fehlergrenzen ..." gibt eine kombinatorische Charakterisierung, welche Klassen optimale Raten für alle ERM-Lernenden zulassen (Folgerung 14). Die relevante Menge ist die "Sternzahl": die größte Anzahl von Punkten, so dass man die Beschriftung eines einzelnen Punktes umdrehen kann, ohne die anderen zu ändern (Definition 9). Klassen mit geschlossenem Schnitt haben einen optimalen richtigen Lernenden: den "Abschluss" -Alg (Satz 5 in der Arbeit und auch von Darnstädt, 2015, bewiesen).
S. Hanneke
Vielen Dank!
Clement C.
6

Ω(dϵlog1ϵ)ϵ[a,b][0,1]O(1/ϵ)[0,0]1ϵlog1ϵ1/

P. Auer, R. Ortner. Ein neues PAC für Konzeptklassen mit geschlossenem Schnittpunkt. Maschinelles Lernen 66 (2-3): 151-163 (2007) http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf

Die Sache mit dem richtigen PAC ist, dass man für positive Ergebnisse im abstrakten Fall keinen Algorithmus jenseits des ERM spezifizieren kann, der besagt: "Finde ein Konzept, das mit der gekennzeichneten Stichprobe übereinstimmt". Wenn Sie über eine zusätzliche Struktur verfügen, z. B. Intervalle, können Sie zwei verschiedene ERM-Algorithmen wie oben untersuchen: ein minimales oder ein maximales konsistentes Segment. Und diese haben unterschiedliche Beispielkomplexitäten!

Die Macht eines unangemessenen PAC besteht darin, dass Sie verschiedene Abstimmungsschemata entwerfen können (Hanneke ist ein solches Ergebnis) - und diese zusätzliche Struktur ermöglicht es Ihnen, verbesserte Raten nachzuweisen. (Die Geschichte ist einfacher für agnostische PAC, bei denen ERM Ihnen die bestmögliche Worst-Case-Rate bis hin zu Konstanten bietet.)

O(d/ϵ)

Aryeh
quelle
Θ(d/ϵ)Θ(d/ϵlog(1/ϵ))
Ja, mit dem leichten Vorbehalt, dass Sie für eine fehlerhafte PAC einen bestimmten Algorithmus (Hanneke's) verwenden müssen - nicht irgendein altes ERM. Fühlen Sie sich frei, die Antwort zu akzeptieren :)
Aryeh
NPRP
1
Die übliche Definition der PAC-Lernbarkeit erfordert Poly-Time-Algorithmen. Meine Punkte sind, dass (i) das Entspannen, das Richtige und das Falsche die gleiche Komplexität der Stichprobe haben; (ii) Mit dieser Anforderung können wir keine bedingungslose Trennung zwischen richtig und unangemessen beweisen (da dies im Wesentlichen etwas wie NP beweisen würde, das nicht gleich RP ist). (Wir können jedoch Untergrenzen für die Stichprobenkomplexität spezifischer geeigneter Lernalgorithmen nachweisen, was meines Wissens die Referenz von Aryeh ist.)
Clement C.
1
@ClementC. In einem Ihrer früheren Kommentare, den Sie nach dem Ausführen eines falschen PAC-Algorithmus erwähnt haben, erhält ein Lernender eine möglicherweise falsche Hypothese, und der Lernende kann dann die nächstgelegene richtige Hypothese aus der Konzeptklasse finden (ohne weitere Beispiele). Aber wie könnte der Lernende dies tun, ohne die Verteilung zu kennen, unter der er Proben erhält? Wird der nächste Wert nicht nach einer unbekannten Verteilung gemessen?
Anonym
5

So fügen Sie der aktuell akzeptierten Antwort Folgendes hinzu:

  1. O(dεlog1ε)
    NP=RPLH=C
  2. log(1/ε)

    log(1/ε)(ε,δ)

    (Fußnote 1 im selben Papier ist ebenfalls relevant)


[1] A. Blumer, A. Ehrenfeucht, D. Haussler und MK Warmuth. Lernfähigkeit und die Vapnik-Chervonenkis-Dimension. Journal of the ACM, 36 (4): 929–965, 1989.

[2] S. Hanneke. Die optimale Stichprobenkomplexität des PAC-Lernens. J. Mach. Lernen. Res. 17, 1, 1319-1333, 2016.

[3] S. Arunachalam und R. de Wolf. Optimale Quantenprobenkomplexität von Lernalgorithmen. In Proceedings der 32. Computational Complexity Conference (CCC), 2017.

Clement C.
quelle
Wird vermutet, dass der 1-Einschluss-Graph von Haussler et al. ist so ein optimaler PAC-Lernender?
Aryeh
@ Aryeh Ich bin nicht sicher. Nach allem, was ich finden konnte, vermutete Warmuth dies im Jahr 2004. Mehr weiß ich nicht.
Clement C.