Dimensión VC y Capacidad

La dimensión de Vapnik-Chervonenkis mide la capacidad de una clase de modelos por el conjunto más grande de puntos que puede etiquetar de todas las formas posibles, cuantificando la complejidad de un aprendiz.

Definition

La dimensión de Vapnik-Chervonenkis de una clase de clasificadores es el mayor número de puntos que la clase puede etiquetar de todas las formas posibles; es una medida de capacidad que limita cuánto puede sobreajustarse la clase y, por lo tanto, cuántos datos se necesitan para aprender de forma fiable.

Scope

Este tema cubre las medidas de la riqueza de una clase de hipótesis: la noción de "shattering" (separación) de un conjunto de puntos, la dimensión de Vapnik-Chervonenkis como el tamaño del conjunto "shattered" (separado) más grande, la función de crecimiento y cómo estas medidas de capacidad influyen en los límites de generalización. Explica por qué la capacidad, más que el número de parámetros por sí solo, rige la capacidad de generalizar.

Core questions

• ¿Qué significa que una clase de modelos "shatter" (separe) un conjunto de puntos?
• ¿Cómo se define y se calcula la dimensión de Vapnik-Chervonenkis?
• ¿Por qué la capacidad, en lugar del recuento de parámetros, rige la generalización?
• ¿Cómo influye la capacidad en los límites de la brecha entre el error de entrenamiento y el error verdadero?

Key theories

Shattering y capacidad

Una clase "shatters" (separa) un conjunto de puntos si puede realizar todas las posibles etiquetas de los mismos; el conjunto más grande de este tipo define la dimensión de Vapnik-Chervonenkis, una medida independiente de la distribución de la flexibilidad de la clase.

La capacidad controla la convergencia uniforme

La capacidad finita asegura que el error empírico converge al error verdadero uniformemente sobre la clase, por lo que un aprendiz con una dimensión de Vapnik-Chervonenkis acotada no puede sobreajustarse arbitrariamente a medida que aumentan los datos.

Capacidad versus recuento de parámetros

La capacidad, no el número bruto de parámetros, determina la generalización, por lo que dos modelos con el mismo recuento de parámetros pueden diferir enormemente en la cantidad de datos que requieren.

Clinical relevance

La dimensión de Vapnik-Chervonenkis proporciona la medida central de capacidad de la teoría clásica del aprendizaje y justifica la práctica de controlar la complejidad del modelo; subyace al análisis basado en el margen de las máquinas de vectores de soporte y enmarca los esfuerzos actuales para comprender por qué algunos modelos de muy alta capacidad, no obstante, generalizan.

History

Vapnik y Chervonenkis introdujeron la dimensión que lleva sus nombres en trabajos de finales de la década de 1960 y en el artículo de 1971 sobre convergencia uniforme, estableciendo una teoría de la capacidad independiente de la distribución. El concepto se convirtió en fundamental para las máquinas de vectores de soporte y para el análisis más amplio de la generalización.

Key figures

• Vladimir Vapnik
• Alexey Chervonenkis

Seminal works

• vapnik1971
• vapnik1995
• hastie2009

Frequently asked questions

¿Qué significa "shattering"?

Un conjunto de puntos es "shattered" (separado) por una clase de modelos si, para cada posible asignación de etiquetas a esos puntos, algún modelo de la clase produce exactamente esa etiqueta. El tamaño del conjunto "shatterable" (separable) más grande es la dimensión de Vapnik-Chervonenkis.

¿Un modelo con más parámetros siempre tiene mayor capacidad?

No necesariamente. La capacidad se mide por la dimensión de Vapnik-Chervonenkis o cantidades relacionadas, que pueden diferir del recuento de parámetros. La medida correcta de la complejidad para la generalización es la capacidad, no simplemente cuántos parámetros tiene un modelo.