VC-Dimension und Kapazität

Die Vapnik-Chervonenkis-Dimension misst die Kapazität einer Modellklasse anhand der größten Menge von Punkten, die sie auf alle möglichen Arten kennzeichnen kann, und quantifiziert so die Komplexität eines Lerners.

Definition

Die Vapnik-Chervonenkis-Dimension einer Klasse von Klassifikatoren ist die größte Anzahl von Punkten, die die Klasse auf jede mögliche Weise kennzeichnen kann; sie ist ein Kapazitätsmaß, das begrenzt, wie stark die Klasse überanpassen kann und somit, wie viele Daten benötigt werden, um zuverlässig zu lernen.

Scope

Dieses Thema behandelt Maße für die Reichhaltigkeit einer Hypothesenklasse: den Begriff des 'Shattering' einer Punktmenge, die Vapnik-Chervonenkis-Dimension als Größe der größten 'geshatterten' Menge, die Wachstumsfunktion und wie diese Kapazitätsmaße in Generalisierungs-Schranken eingehen. Es wird erklärt, warum die Kapazität und nicht die Anzahl der Parameter allein die Generalisierungsfähigkeit bestimmt.

Core questions

• Was bedeutet es für eine Modellklasse, eine Menge von Punkten zu 'shattern'?
• Wie wird die Vapnik-Chervonenkis-Dimension definiert und berechnet?
• Warum bestimmt die Kapazität und nicht die Parameteranzahl die Generalisierung?
• Wie geht die Kapazität in die Schranken für die Lücke zwischen Trainings- und wahrem Fehler ein?

Key theories

Shattering und Kapazität

Eine Klasse 'shattert' eine Menge von Punkten, wenn sie jede mögliche Kennzeichnung dieser Punkte realisieren kann; die größte solche Menge definiert die Vapnik-Chervonenkis-Dimension, ein verteilungsfreies Maß dafür, wie flexibel die Klasse ist.

Kapazität steuert gleichmäßige Konvergenz

Eine endliche Kapazität stellt sicher, dass der empirische Fehler gleichmäßig über die Klasse zum wahren Fehler konvergiert, sodass ein Lerner mit begrenzter Vapnik-Chervonenkis-Dimension nicht beliebig überanpassen kann, wenn die Datenmenge wächst.

Kapazität versus Parameteranzahl

Die Kapazität, nicht die reine Anzahl der Parameter, bestimmt die Generalisierung, sodass zwei Modelle mit der gleichen Parameteranzahl sich stark darin unterscheiden können, wie viele Daten sie benötigen.

Clinical relevance

Die Vapnik-Chervonenkis-Dimension liefert das zentrale Kapazitätsmaß der klassischen Lerntheorie und rechtfertigt die Praxis der Kontrolle der Modellkomplexität; sie liegt der margin-basierten Analyse von Support Vector Machines zugrunde und bildet den Rahmen für aktuelle Bemühungen zu verstehen, warum einige Modelle mit sehr hoher Kapazität dennoch generalisieren.

History

Vapnik und Chervonenkis führten die Dimension, die ihren Namen trägt, in Arbeiten aus den späten 1960er Jahren und dem Artikel von 1971 über die gleichmäßige Konvergenz ein und etablierten damit eine verteilungsfreie Theorie der Kapazität. Das Konzept wurde grundlegend für Support Vector Machines und für die breitere Analyse der Generalisierung.

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

Was bedeutet 'Shattering'?

Eine Menge von Punkten wird von einer Modellklasse 'geshattert', wenn für jede mögliche Zuweisung von Labels zu diesen Punkten ein Modell in der Klasse genau diese Kennzeichnung erzeugt. Die Größe der größten 'shatterbaren' Menge ist die Vapnik-Chervonenkis-Dimension.

Hat ein Modell mit mehr Parametern immer eine höhere Kapazität?

Nicht unbedingt. Die Kapazität wird durch die Vapnik-Chervonenkis-Dimension oder verwandte Größen gemessen, die sich von der Parameteranzahl unterscheiden können. Das richtige Komplexitätsmaß für die Generalisierung ist die Kapazität, nicht einfach die Anzahl der Parameter eines Modells.