- Dimensión VC
-
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 θ 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 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 cuál 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 2 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 de test del modelo de clasificación.
El límite sobre el error de test del modelo de clasificación (en datos de entrenamiento son independientes y cumplen una distribución aleatoria de la misma distribución) está dado por
- Error de entrenamiento +
con probabilidad 1 − η, 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.
Categorías: Aprendizaje automático | Algoritmos | Dimensión - Error de entrenamiento +
Wikimedia foundation. 2010.
