Parallele Rechtecke der PAC-Lernachse

Ich versuche den Beweis zu verstehen, dass die achsparallelen Rechtecke im realisierbaren Fall PAC-lernbar sind. Dies bedeutet, dass gegeben$\epsilon, \delta$ Mit genügend Daten können wir eine Funktion finden $h$ so dass

Für achsparallele Rechtecke (in binärer Klassifikation) lautet das übliche Argument wie folgt: $R$ sei das wahre Rechteck und lass $R'$ sei eindeutig das kleinste Rechteck mit den positiven Beispielen $R' \subseteq R$betrachten wir die vier rechteckigen Streifen dazwischen $R'$ und $R$. Klar, wenn alle eine Wahrscheinlichkeit haben$\leq \epsilon/4$ dann ist die Wahrscheinlichkeit, einen Fehler zu machen, geringer als $\epsilon$Wir können also davon ausgehen, dass mindestens einer die Wahrscheinlichkeit hat, einen Fehler zu machen $\geq \epsilon/4$.

Für einen solchen Streifen die Wahrscheinlichkeit, alle korrekt zu klassifizieren $m$ Trainingsbeispiele gibt es höchstens $(1 - \epsilon/4)^m$Wenn wir also eine über alle Streifen gebundene Vereinigung nehmen, erhalten wir, dass die Wahrscheinlichkeit, alles richtig zu klassifizieren, geringer ist als $4(1-\epsilon/4)^m \leq 4e^{-m/4}$und mit ein bisschen Algebra ergibt sich, dass die Komplexität der Stichprobe gleich ist $m \geq (4/\epsilon)\ln(4/\delta)$.

Hier ist ein PDF , das etwas ausführlicher erklärt. Mit einigen Bildern musste ich das Argument nur so weit wie möglich zusammenfassen, um es hier einzufügen.

Meine Frage ist, warum müssen wir die vier rechteckigen Streifen getrennt betrachten, warum können wir nicht einfach sagen, dass die Wahrscheinlichkeit der Region dazwischen liegt $R'$ und $R$ muss größer sein als $\epsilon$ (weil wir sonst fertig sind) und somit mit demselben Argument zur besseren Grenze gelangen würden $m \geq (1/\epsilon)\ln(1/\delta)$?

Entschuldigung für die lange Frage und vielen Dank im Voraus.

Die Frage ist ein wenig vage, aber es scheint, als ob das, was Sie argumentieren möchten, in etwa so lautet: Lassen Sie $R$ sei das Konzept zu lernen und nimm jedes $R^*\subset R$ ein beliebiges Rechteck sein, das a $(1-\epsilon)$-ein Bruchteil von $R$. Dann mit einiger Wahrscheinlichkeit$R'$ wird beinhalten $R^*$.

Das Problem dabei ist, dass die besondere Wahrscheinlichkeit von der spezifischen Wahl von abhängt $R^*$. Ich denke, was Sie verwirrt ist, ist dieser Wunsch$R'$an unsichtbaren Beispielen gut abschneiden . Durch den Bau$R'$klassifiziert alle Trainingsdaten korrekt. Das schlechte Ereignis ist tatsächlich, dass alle Trainingsdaten in einem zu kleinen Rechteck konzentriert sind. Dies geschieht höchstens mit der Wahrscheinlichkeit, dass einer der Streifen von allen Trainingsbeispielen übersehen wird.

hmm ... nun, in dem Beweis, den Sie erwähnen, ziehen wir Punkte (x, y) aus einer Verteilung D und prüfen, ob sie wirklich in ein Quadrat fallen. Dh wir wählen das gleiche$\delta$für jede Grenze (max x, min x, max y, min y). Wenn Sie einen Kreis hatten, können Sie das nicht einfach tun - Sie müssen ein Delta für einen Radius auswählen, und der Radius ist eine Funktion der Koordinaten. Das macht den Beweis also komplizierter.

Wenn Sie sich für nicht konkave Polygone entscheiden, sollte dies viel schwieriger werden.