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 $f$ con algún vector de parámetros $\theta$ es llamado separador de un conjunto de puntos ($x_{1},x_{2},\ldots ,x_{n}$) si, para todas las asignaciones de las etiquetas de esos puntos, existe una $\theta$ tal que el modelo $f$ no tiene errores cuando evalúa ese conjunto de puntos.

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

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.

Separación de 3 puntos			Separación imposible con 4 puntos

Uso

La dimensión VC tiene utilidad en teoría de aprendizaje estadístico, porque puede predecir el límite superior probabilístico sobre el error en el conjunto de prueba.

El límite sobre el error en el conjunto de prueba del modelo (en los datos de entrenamiento es independiente y cumple una distribución aleatoria de la misma distribución) está dado por

Error de entrenamiento + ${\sqrt {h(\log(2N/h)+1)-\log(\eta /4) \over N}}$

con probabilidad $1-\eta$, donde $h$ es la dimensión VC del modelo de clasificación, y $N$ es el tamaño del conjunto de entrenamiento.

Referencias y fuentes

• Andrew Moore's VC dimension tutorial
• V. Vapnik and A. Chervonenkis. "On the uniform convergence of relative frequencies of events to their probabilities." Theory of Probability and its Applications, 16(2):264--280, 1971.
• A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. "Learnability and the Vapnik-Chervonenkis dimension." Journal of the ACM, 36(4):929--865, 1989.

• Datos: Q2662236
• Multimedia: Vapnik-Chervonenkis dimension / Q2662236