VC-Dimension eines Rechtecks

9

Das Buch "Einführung in das maschinelle Lernen" von Ethem Alpaydın besagt, dass die VC-Dimension eines achsenausgerichteten Rechtecks ​​4 beträgt. Aber wie kann ein Rechteck einen Satz von vier kollinearen Punkten mit abwechselnden positiven und negativen Punkten zerbrechen?

Kann jemand die VC-Dimension eines Rechtecks ​​erklären und beweisen?

kaz
quelle

Antworten:

20

tl; dr: Sie haben die Definition der VC-Dimension falsch.

Die VC-Dimension von Rechtecken ist die Kardinalität der maximalen Menge von Punkten, die durch ein Rechteck zerbrochen werden können.

Die VC-Dimension von Rechtecken ist 4, da es einen Satz von 4 Punkten gibt, die durch ein Rechteck zerbrochen werden können, und jeder Satz von 5 Punkten kann nicht durch ein Rechteck zerbrochen werden. Während es wahr ist, dass ein Rechteck einen Satz von vier kollinearen Punkten mit abwechselnd positiv und negativ nicht zerbrechen kann, ist die VC-Dimension immer noch 4, da es eine Konfiguration von 4 Punkten gibt, die zerbrochen werden kann.

Neutralino
quelle
11

Die VC-Dimension eines Algorithmus ist die maximale Anzahl von Punkten, so dass

  • Es gibt ein Layout der Punkte, so dass

  • Für alle Beschriftungen dieser Punkte macht der Algorithmus keine Fehler

Tatsächlich gibt es eine Anordnung von vier Punkten (als Diamant), sodass ein Rechteck jeden Satz positiver Punkte von den anderen trennen kann. Dass es ein Layout mit vier Punkten gibt, an denen das Rechteck versagt, spielt keine Rolle.

Hier ist eine Beschreibung mit einem Diagramm .

Andy Jones
quelle
Das ist eine großartige Antwort und das Aufschreiben hilft sehr, aber ich bin immer noch neugierig, ob es unmöglich ist, dass 5 Punkte nicht zerstört werden können. Ich denke, es gibt auch ein Layout, in dem Sie Positives von Negativem trennen können, zum Beispiel als Sternform, bei der drei Punkte positiv und der Rest negativ sind oder umgekehrt. Vermisse ich etwas
Kirk Walla
0

Betrachten Sie es als ein Spiel zwischen Ihnen und einem Gegner. Sie wählen die Position der Punkte und der Gegner beschriftet sie nach Belieben. Wenn er gewinnt, indem er eine Beschriftung findet, die nicht zerstört werden kann, ist die VC-Dimension kleiner als die Anzahl der Punkte, aber wenn Sie gewinnen, ist die VC-Dimension gleich oder größer als die Anzahl der Punkte. In Ihrer Frage sind Sie nicht gezwungen, diese Anordnung auszuwählen. Sie können eine bessere Anordnung der Punkte finden, mit denen Sie gewinnen können.

Ahmad
quelle
1
Dies ist alles wahr, aber Sie haben die Frage, die mit der VC-Dimension eines achsenausgerichteten Rechtecks ​​zu tun hat, nicht wirklich beantwortet. Es wäre großartig, Ihre Antwort zu erweitern, um zu zeigen, wie sie auf die spezifische Frage zutrifft!
Jbowman