La dimensión Vapnik-Chervonenkis o dimensión VC es una característica de una familia de algoritmos para resolver un problema de clasificación con dos clases, caracterizando la complejidad o capacidad de esta familia. Es uno de los conceptos clave en la teoría de aprendizaje automático estadístico de Vapnik-Chervonenkis y lleva el nombre de Vladimir Vapnik y Alexey Chervonenkis .
Los propios Vapnik y Chervonenkis prefieren llamar a esta cantidad dimensión combinatoria , ya que resultó que los algebristas la conocían incluso antes del descubrimiento de su teoría del aprendizaje automático .
Sean dados un conjunto y alguna familia de funciones indicadoras (algoritmos de clasificación, reglas de decisión) , donde es el argumento de las funciones, es el vector de parámetros que definen la función. Cada una de estas funciones asigna a cada elemento del conjunto una de las dos clases dadas. La dimensión VC de una familia es el número más grande , tal que hay un subconjunto de los elementos del conjunto , cuyas funciones se pueden dividir en dos clases de todas las formas posibles. Si tales subconjuntos existen para arbitrariamente grande , entonces se supone que la dimensión VC es igual a infinito.
La dimensión VC también se puede generalizar al caso de una familia de funciones que toman valores reales. Su dimensión VC se define como la dimensión VC de la familia de funciones indicadoras , donde el rango de funciones . [una]
Como ejemplo, considere el problema de dividir puntos en un plano en dos clases por una línea recta: este es el llamado clasificador lineal . Un conjunto de tres puntos que no se encuentran en una línea recta se puede dividir por una línea recta en dos clases de todas las formas posibles ( las formas que se muestran en la figura a continuación muestran tres de ellos), pero ya no hay un conjunto de cuatro o más puntos. Por lo tanto, la dimensión VC del clasificador lineal en el plano es igual a tres.
Ejemplos de dividir tres puntos en dos clases |
La separación es imposible para estos cuatro puntos. |
En el caso general, la dimensión VC de los clasificadores lineales en un espacio dimensional es .
Aprendizaje automático y minería de datos | |
---|---|
Tareas | |
Aprendiendo con un maestro | |
análisis de conglomerados | |
Reducción de dimensionalidad | |
Pronóstico estructural | |
Detección de anomalías | |
Graficar modelos probabilísticos | |
Redes neuronales | |
Aprendizaje reforzado |
|
Teoría | |
revistas y congresos |
|