Dimensión Vapnik-Chervonenkis

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 .

Definición

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. $X$ ${\mathcal {F}}=\{f(x,\alpha )\}$ $x\en X$ $\alfa$ $f(x,\alfa )$ $X$ ${\ matemáticas {F}}$ $h$ $h$ $X$ ${\ matemáticas {F}}$ $h$

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] $\{g(x,\alfa)\}$ $\{I(g(x,\alpha )>\beta )\}$ $\beta$ $gramo$

Ejemplos

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. $2^{3}=8$


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 . $norte$ $n+1$

Véase también

Máquinas de vectores soporte

Enlaces

Información del sitio www.machinelearning.ru

Notas

↑ Hastie, T., Tibshirani R., Friedman J. Capítulo 7.9. Dimensión Vapnik-Chervonenkis // Los elementos del aprendizaje estadístico: minería de datos, inferencia y predicción . — 2ª ed. - Springer-Verlag, 2009. - 746 p. - ISBN 978-0-387-84857-0 . .

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ACI LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG