Warum ist die VC-Dimension wichtig?

Wikipedia sagt das:

Die VC-Dimension ist die Kardinalität der größten Menge von Punkten, die ein Algorithmus zerstören kann.

Zum Beispiel hat ein linearer Klassifikator eine Kardinalität n + 1. Meine Frage ist, warum es uns interessiert? Die meisten Datensätze, für die Sie eine lineare Klassifizierung durchführen, sind in der Regel sehr groß und enthalten viele Punkte.

Was ist die VC-Dimension?

Wie von @CPerkins erwähnt, ist die VC-Dimension ein Maß für die Komplexität eines Modells. Es kann auch in Bezug auf die Fähigkeit definiert werden, Datenpunkte zu zerbrechen, wie es Wikipedia erwähnt hat.

Das Grundproblem

• Wir wollen ein Modell (z. B. einen Klassifikator), das sich gut auf unsichtbare Daten verallgemeinern lässt .
• Wir sind auf eine bestimmte Menge von Beispieldaten beschränkt.

Das folgende Bild (von hier aus aufgenommen ) zeigt einige Modelle ( bis S k ) unterschiedlicher Komplexität (VC-Dimension), die hier auf der x-Achse dargestellt sind und h heißen .$\mathcal{S_1}$$\mathcal{S_k}$$h$

Die Bilder zeigen, dass eine höhere VC-Dimension ein geringeres empirisches Risiko ermöglicht (der Fehler, den ein Modell bei den Probendaten macht), aber auch ein höheres Konfidenzintervall einführt. Dieses Intervall kann als Vertrauen in die Verallgemeinerungsfähigkeit des Modells angesehen werden.

Niedrige VC-Dimension (hohe Vorspannung)

Wenn wir ein Modell mit geringer Komplexität verwenden, führen wir eine Art Annahme (Bias) in Bezug auf den Datensatz ein, z. B. wenn wir einen linearen Klassifikator verwenden, gehen wir davon aus, dass die Daten mit einem linearen Modell beschrieben werden können. Ist dies nicht der Fall, kann unser gegebenes Problem nicht durch ein lineares Modell gelöst werden, beispielsweise weil das Problem nichtlinearer Natur ist. Wir werden ein Modell mit schlechter Leistung erhalten, das die Datenstruktur nicht lernen kann. Wir sollten daher versuchen, eine starke Voreingenommenheit zu vermeiden.

Hohe VC-Dimension (größeres Konfidenzintervall)

Auf der anderen Seite der x-Achse sehen wir Modelle mit höherer Komplexität, die möglicherweise eine so große Kapazität haben, dass sie sich die Daten lieber merken, anstatt ihre allgemeine zugrunde liegende Struktur zu lernen, dh die Modellüberanpassungen. Nachdem wir dieses Problem erkannt haben, sollten wir komplexe Modelle vermeiden.

Dies mag kontrovers erscheinen, da wir keine Verzerrung einführen werden, dh eine niedrige VC-Dimension haben, aber auch keine hohe VC-Dimension haben sollten. Dieses Problem hat tiefe Wurzeln in der statistischen Lerntheorie und ist als Bias-Varianz-Kompromiss bekannt . Was wir in dieser Situation tun sollten, ist, so komplex wie nötig und so simpel wie möglich zu sein. Wenn wir also zwei Modelle vergleichen, die denselben empirischen Fehler aufweisen, sollten wir das weniger komplexe verwenden.

Ich hoffe, ich konnte Ihnen zeigen, dass hinter der Idee der VC-Dimension mehr steckt.

$N$

$VC$

$N$$N$$log_2(N)$Informationsbits - ähnlich wie beim binären Suchproblem mit dem sortierten Array.

$N$$x$$N$$D=\{(x_1,y_1), (x_2, y_2), ..., (x_l, y_l)\}$$x_i$$x_i$$N$$x_i$$\epsilon$$\epsilon$$1-\delta$$(\epsilon, \delta)$$\frac{log_2N/\delta}{\epsilon}$

$N$$\epsilon$$1-\delta$$\frac{log_2N/\delta}{\epsilon^2}$

$log_2N$

$\epsilon$$1-\delta$$\epsilon$

^{___________________ Beide Linien (Funktion) klassifizieren die Punkte mit dem gleichen Erfolg___________________}

$VC$$log_2N$$VC$$\frac{VC -log(\delta)}{\epsilon}$$\frac{VC - log(\delta)}{\epsilon^2}$

$VC$$\epsilon$$1-\delta$

Die VC-Dimension ist ein Maß für die Komplexität des Modells. Angesichts der VC-Dimension Dvc gilt als Faustregel, dass Sie angesichts der Komplexität Ihres Modells n = 10xDvc-Datenpunkte haben sollten.

Sie können es auch verwenden, um eine Obergrenze für den Testfehler zu erstellen.