Vapnik-Chervonenkis-Dimension: Warum können nicht vier Punkte auf einer Linie durch Rechtecke zerschmettert werden?

8

Ich lese also die 2. Ausgabe von "Introduction to Machine Learning" von Bishop et al. alle. Auf Seite 27 diskutieren sie die Vapnik-Chervonenkis-Dimension, die

"Die maximale Anzahl von Punkten, die durch H [die Hypothesenklasse] zerstört werden können, wird als Vapnik-Chervonenkis (VC) -Dimension von H bezeichnet, als VC (H) bezeichnet und misst die Kapazität von H."

Während "Splitter" eine Hypothese für einen Satz von N Datenpunkten anzeigt, so dass sie die positiven Beispiele von den negativen trennt. In einem solchen Beispiel wird gesagt, dass "H N Punkte zerbricht".h∈H.

Bisher glaube ich das zu verstehen. Die Autoren verlieren mich jedoch mit folgendem:

"Zum Beispiel können vier Punkte auf einer Linie nicht durch Rechtecke zerschmettert werden."

Hier muss es ein Konzept geben, das ich nicht vollständig verstehe, weil ich nicht verstehen kann, warum dies der Fall ist. Kann mir das jemand erklären?

machine-learning vc-dimension BrotherJack
quelle
2
Nennen Sie die vier Punkte in der Reihenfolge entlang der Linie. Es gibt kein Rechteck, das und enthält, aber und . p,q,r,sprqs
JeffE
Ja, aber es gibt Rechtecke, die und enthalten können , ausgenommen und . oder enthalten und und schließen und . Wollen Sie damit sagen, dass jede Kombination möglich sein muss, damit die Punkte zerstört werden, und wenn ja, WARUM IST DAS KEINE ANTWORT: P? pqrsqrps
BrotherJack

Antworten:

10

P.P.P.H.

p,q,r,sprqs

JeffE
quelle
Na, bitte. Viel besser, dies als Antwort zu haben, nein?
BrotherJack