Ich studiere maschinelles Lernen aus Andrew Ng Stanford-Vorlesungen und bin gerade auf die Theorie der VC-Dimensionen gestoßen. Entsprechend den Vorlesungen und dem, was ich verstanden habe, der Definition der VC-Dimension kann wie folgt angegeben werden:
Wenn Sie eine Menge von $ n $ Punkten finden, so dass sie vom Klassifizierer zerstört werden kann (dh klassifizieren Sie alle möglichen $ 2 ^ n $ Beschriftungen korrekt) und Sie können keinen Satz von $ n + 1 $ Punkten finden, der zerbrochen werden kann (dh für jeden Satz von $ n + 1 $ Punkten gibt es mindestens eine Beschriftungsreihenfolge, so dass der Klassifizierer kann nicht alle Punkte richtig trennen), dann ist die VC-Dimension $ n $.
Auch Professor hat ein Beispiel genommen und dies gut erklärt. Das ist:
Lassen Sie
$ H = \ {{set \ of \ linear \ classifiers \ in \ 2 \ Dimensions \}} $
Dann können 3 beliebige Punkte durch $ H $ korrekt mit trennender Hyperebene klassifiziert werden, wie in der folgenden Abbildung gezeigt.
Und deshalb ist die VC-Dimension von $ H $ 3. Denn für 4 beliebige Punkte in der 2D-Ebene kann ein linearer Klassifikator nicht alle Kombinationen der Punkte zerbrechen. Beispiel:
Für Für diese Menge von Punkten, , kann keine trennende Hyperebene gezeichnet werden, um diese Menge zu klassifizieren. Die VC-Dimension ist also 3.
Ich habe die Idee bis hierher. Aber was ist, wenn wir folgenden Mustertyp haben?
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 gerade sehe. Hier um 16:24 , aber Professor erwähnt nicht den genauen Grund dafür.
Jedes intuitive Erklärungsbeispiel wird geschätzt. Vielen Dank
Kommentare
Antwort
Die Definition der VC-Dimension lautet: if Es gibt eine Menge von n Punkten, die vom Klassifikator zerstört werden können, und es gibt keine Satz von n + 1 Punkten, die vom Klassifizierer zerstört werden können, dann ist die VC-Dimension des Klassifizierers n.
Die Definition besagt nicht: Wenn eine beliebige Menge von n Punkten durch den Klassifizierer zerstört werden kann. ..
Wenn die VC-Dimension eines Klassifikators 3 ist, muss er nicht alle möglichen Anordnungen von 3 Punkten.
Wenn von allen Anordnungen von 3 Punkten mindestens eine gefunden wird Eine solche Anordnung, die vom Klassifizierer zerstört werden kann und keine 4 Punkte finden kann, die zerstört werden können, ist die VC-Dimension 3.
Kommentare
- Dann In diesem Fall können wir mindestens ein Muster einer beliebigen Anzahl von Punkten erhalten, die durch eine gerade Linie klassifiziert werden können. Denken Sie beispielsweise 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 VC-Dimension wäre 4. Warum also nicht berücksichtigt?
- Klassifiziert – ja. Zerschmettert – nein
- Also, was ist die Bedeutung von eine Anordnung von Punkten zerstören? Ich ' bin hier wirklich verwirrt. Dank
- 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 de.wikipedia.org/wiki/Shattered_set
- Abbildung mit 8 Nebenhandlungen 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 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.
Antwort
Die Punkte sollten Punkte im allgemeinen Zustand erfüllen, bevor sie für die VC-Dimension berücksichtigt werden. 