Dimensión VC

La dimensión VC (del inglés Vapnik-Chervonenkis dimension) es una medida de la capacidad de los algoritmos de clasificación estadística, definida como la cardinalidad del mayor conjunto de puntos que el algoritmo puede separar. Es un concepto central en la teoría Vapnik-Chervonenkis, y fue originalmente definido por Vladimir Vapnik y Alexey Chervonenkis.

Separación

Un modelo de clasificación con algún vector de parámetros es llamado separador de un conjunto de puntos () si, para todas las asignaciones de las etiquetas de esos puntos, existe una tal que el modelo no tiene errores cuando evalúa ese conjunto de puntos.

La dimensión VC del modelo es el máximo para el cuál algún punto del conjunto de datos de cardinalidad puede ser separado por .

Por ejemplo, considerando una línea recta como modelo de clasificación: el modelo empleado por un perceptrón. La línea debería separar los puntos de clase "+" (positivos) de los de clase "-" (negativos). Cuando hay 3 puntos que no sean colineales, la línea puede separarlos. Sin embargo, la línea no puede separar 4 puntos. Es importante recordar que uno puede elegir una configuración de puntos que pueden ser separables por una recta, pero no podríamos separar todas las permutaciones. Sólo 3 de las 8 permutaciones posibles son mostradas para 3 puntos.

VC1.svg VC2.svg VC3.svg VC4.svg
Separación de 3 puntos Separación imposible con 4 puntos
Other Languages