Was ist die genaue Definition der VC-Dimension?

8

Ich studiere maschinelles Lernen aus Andrew Ng Stanford-Vorlesungen und bin gerade auf die Theorie der VC-Dimensionen gestoßen. Gemäß den Vorlesungen und dem, was ich verstanden habe, kann die Definition der VC-Dimension wie folgt angegeben werden:

Wenn Sie eine Menge von Punkten finden können, so dass sie vom Klassifikator zerschmettert werden kann (dh alle möglichen 2 n Beschriftungen korrekt klassifizieren ) und Sie keine Menge von n + 1 Punkten finden können, die zerbrochen werden können (dh für jede Menge von n + 1 Punkte gibt es mindestens eine Beschriftungsreihenfolge, so dass der Klassifizierer nicht alle Punkte korrekt trennen kann), dann ist die VC-Dimension n .n2nn+1n+1n

Auch Professor nahm ein Beispiel und erklärte dies schön. Welches ist:

Lassen,

H={set of linear classifiers in 2 Dimensions}

Dann können 3 beliebige Punkte durch korrekt klassifiziert werden , wobei die Hyperebene getrennt wird, wie in der folgenden Abbildung gezeigt.H

Geben Sie hier die Bildbeschreibung ein

Und deshalb ist die VC-Dimension von 3. Da ein linearer Klassifikator für 4 Punkte in der 2D-Ebene nicht alle Kombinationen der Punkte zerstören kann. Zum Beispiel,H

Geben Sie hier die Bildbeschreibung ein

Für diesen Satz von Punkten kann keine trennende Hyperebene gezeichnet werden, um diesen Satz zu klassifizieren. Die VC-Dimension ist also 3.

Ich habe die Idee bis hierher. Aber was ist, wenn wir folgende Muster haben?

Geben Sie hier die Bildbeschreibung ein

Oder das Muster, bei dem drei Punkte aufeinander fallen. Auch hier können wir keine trennende Hyperebene zwischen drei Punkten zeichnen. Dennoch wird dieses Muster bei der Definition der VC-Dimension nicht berücksichtigt. Warum? Der gleiche Punkt wird auch in den Vorlesungen besprochen, die ich hier um 16:24 Uhr sehe, aber Professor erwähnt nicht den genauen Grund dafür.

Jedes intuitive Erklärungsbeispiel wird geschätzt. Vielen Dank

machine-learning classification vc-theory Kaushal28
quelle
entnommen aus datascience.stackexchange.com/a/16146/23305
oW_

Antworten:

9

Die Definition von VC Dimension ist: Wenn es gibt eine Menge von n Punkten , die durch den Klassifikator zertrümmert werden können , und es gibt keine Menge von n + 1 Punkten , die durch den Klassifikator zerschmettert werden können, dann ist die VC Dimension der Klassifikator n.

Die Definition sagt nicht: ob eine Menge von n Punkten durch den Klassifikator zerschmettert werden kann ...

Wenn die VC-Dimension eines Klassifikators 3 ist, muss er nicht alle möglichen Anordnungen von 3 Punkten zerstören .

Wenn Sie von allen Anordnungen mit 3 Punkten mindestens eine solche Anordnung finden, die vom Klassifizierer zerstört werden kann, und nicht 4 Punkte finden können, die zerstört werden können, beträgt die VC-Dimension 3.

Vladislav Gladkikh
quelle
1
Dann können wir in diesem Fall mindestens ein Muster einer beliebigen Anzahl von Punkten erhalten, die durch eine gerade Linie klassifiziert werden können. Denken Sie zum Beispiel an 4 Punkte. Zwei rote Punkte auf der linken Seite und zwei blaue Punkte auf der rechten Seite würden eine Klassifizierung ermöglichen, und die VC-Dimension wäre 4. Warum also nicht berücksichtigt?
Kaushal28
Klassifiziert - ja.
Erschüttert
Was bedeutet es also, eine Anordnung von Punkten zu zerstören? Ich bin hier wirklich verwirrt. Danke
Kaushal28
Eine Anordnung von Punkten kann zerstört werden, wenn eine Teilmenge dieser Anordnung isoliert und in eine Klasse eingeteilt werden kann. Angenommen, Sie möchten testen, ob eine bestimmte Anordnung (nicht alle möglichen Anordnungen, sondern nur eine bestimmte Anordnung) von n Punkten durch einen bestimmten Klassifizierertyp zerstört werden kann. Dann testen Sie zuerst, ob ein einzelner Punkt isoliert werden kann. Wenn dann 2 beliebige Punkte isoliert werden können, dann 3 beliebige Punkte usw., bis n-1 Punkte dieser bestimmten Anordnung vorliegen. Siehe hier en.wikipedia.org/wiki/Shattered_set
Vladislav Gladkikh
1
Die Abbildung mit 8 Teilplots ist eine sehr gute Illustration dessen, was erschüttert. Hier haben Sie 3 Punkte, 2 Klassen, also 2 ^ 3 = 8 mögliche Beschriftungen dieser 3 Punkte. Alle 8 Beschriftungen können mit einer Linie durchgeführt und isoliert werden, daher kann dieser Satz durch eine Linie zerbrochen werden. Die Abbildung mit 4 Punkten: Es gibt einige Beschriftungen, die mit einer Linie isoliert werden können (z. B. zwei links sind rot, zwei rechts sind blau), aber auch eine Beschriftung, die nicht mit einer Linie isoliert werden kann (wie in der Abbildung: oben und oben) unteres Blau; links und rechts sind links). Da es eine Beschriftung hat, die nicht mit einer Linie isoliert werden kann, ist dieses Set nicht zerbrochen.
Vladislav Gladkikh