En la teoría de Vapnik-Chervonenkis , la dimensión de Vapnik-Chervonenkis (VC) es una medida de la capacidad (complejidad, poder expresivo, riqueza o flexibilidad) de un conjunto de funciones que se pueden aprender mediante un algoritmo de clasificación binaria estadística . Se define como la cardinalidad del mayor conjunto de puntos que el algoritmo puede romper . Originalmente fue definido por Vladimir Vapnik y Alexey Chervonenkis . [1]
De manera informal, la capacidad de un modelo de clasificación está relacionada con lo complicado que puede ser. Por ejemplo, considere el umbral de un polinomio de alto grado : si el polinomio se evalúa por encima de cero, ese punto se clasifica como positivo, de lo contrario como negativo. Un polinomio de alto grado puede ser ondulado, por lo que puede ajustarse bien a un conjunto determinado de puntos de entrenamiento. Pero se puede esperar que el clasificador cometa errores en otros puntos, porque es demasiado ondulado. Dicho polinomio tiene una gran capacidad. Una alternativa mucho más simple es establecer el umbral de una función lineal. Es posible que esta función no se ajuste bien al conjunto de entrenamiento porque tiene poca capacidad. Esta noción de capacidad se hace más rigurosa a continuación.
Definiciones
Dimensión VC de una familia de conjuntos
Dejar ser una familia de conjuntos (un conjunto de conjuntos) yun conjunto. Su intersección se define como la siguiente familia de conjuntos:
Decimos que un conjunto es destrozado por Si contiene todos los subconjuntos de , es decir:
La dimensión VC de es la mayor cardinalidad de conjuntos destrozada por. Si se pueden romper subconjuntos arbitrariamente grandes, la dimensión VC es.
Dimensión VC de un modelo de clasificación
Un modelo de clasificación binaria con algún vector de parámetro se dice que rompe un conjunto de puntos de datos si, para todas las asignaciones de etiquetas a esos puntos, existe un tal que el modelo no comete errores al evaluar ese conjunto de puntos de datos.
La dimensión VC de un modelo es el número máximo de puntos que se pueden organizar para que los destroza. Más formalmente, es el máximo cardenaltal que algún conjunto de puntos de datos de cardinalidad puede ser destrozado por .
Ejemplos de
1. es un clasificador constante (sin parámetros). Su dimensión VC es 0 ya que no puede romper ni un solo punto. En general, la dimensión VC de un modelo de clasificación finito, que puede devolver como máximo diferentes clasificadores, es como máximo (este es un límite superior en la dimensión VC; el lema Sauer-Shelah da un límite inferior en la dimensión).
2. es un clasificador de umbral paramétrico simple en números reales; es decir, para un cierto umbral, el clasificador devuelve 1 si el número de entrada es mayor que y 0 en caso contrario. La dimensión VC dees 1 porque: (a) Puede romper un solo punto. Por cada punto, un clasificador lo etiqueta como 0 si y lo etiqueta como 1 si . (b) No puede romper ningún conjunto de dos puntos. Para cada conjunto de dos números, si el más pequeño está etiquetado como 1, entonces el más grande también debe etiquetarse como 1, por lo que no todas las etiquetas son posibles.
3. es un clasificador de intervalo paramétrico simple en números reales; es decir, para un determinado parámetro, el clasificador devuelve 1 si el número de entrada está en el intervalo y 0 en caso contrario. La dimensión VC dees 2 porque: (a) Puede romper algunos conjuntos de dos puntos. Por ejemplo, para cada conjunto, un clasificador lo etiqueta como (0,0) si o si , como (1,0) si , como (1,1) si , y como (0,1) si . (b) No puede romper ningún conjunto de tres puntos. Para cada conjunto de tres números, si el más pequeño y el más grande están etiquetados como 1, entonces el del medio también debe etiquetarse como 1, por lo que no todas las etiquetas son posibles.
4. es una línea recta como modelo de clasificación de puntos en un plano bidimensional (este es el modelo utilizado por un perceptrón ). La línea debe separar los puntos de datos positivos de los puntos de datos negativos. Existen conjuntos de 3 puntos que de hecho pueden romperse usando este modelo (cualquier 3 puntos que no sean colineales pueden romperse). Sin embargo, ningún conjunto de 4 puntos puede romperse: según el teorema de Radon , cuatro puntos cualesquiera se pueden dividir en dos subconjuntos con cascos convexos que se cruzan , por lo que no es posible separar uno de estos dos subconjuntos del otro. Por lo tanto, la dimensión VC de este clasificador en particular es 3. Es importante recordar que si bien se puede elegir cualquier disposición de puntos, la disposición de esos puntos no puede cambiar cuando se intenta romper para alguna asignación de etiqueta. Tenga en cuenta que solo se muestran 3 de las 2 3 = 8 asignaciones de etiquetas posibles para los tres puntos.
![]() | ![]() | ![]() | ![]() |
3 puntos destrozados | 4 puntos imposible |
5. es un clasificador de seno paramétrico simple , es decir, para un determinado parámetro, el clasificador devuelve 1 si el número de entrada posee y 0 en caso contrario. La dimensión VC de es infinito, ya que puede romper cualquier subconjunto finito del conjunto . [2] : 57
Usos
En teoría del aprendizaje estadístico
La dimensión VC puede predecir un límite superior probabilístico en el error de prueba de un modelo de clasificación. Vapnik [3] demostró que la probabilidad de que el error de la prueba (es decir, el riesgo con la función 0-1 pérdida) distanciamiento de un límite superior (en los datos que se dibuja iid de la misma distribución como el conjunto de entrenamiento) está dada por:
dónde es la dimensión VC del modelo de clasificación, , y es el tamaño del conjunto de entrenamiento (restricción: esta fórmula es válida cuando . Cuándoes mayor, el error de prueba puede ser mucho mayor que el error de entrenamiento. Esto se debe al sobreajuste ).
La dimensión VC también aparece en los límites de complejidad de la muestra . Un espacio de funciones binarias con dimensión VC se puede aprender con:
muestras, donde es el error de aprendizaje y es la probabilidad de falla. Por tanto, la complejidad de la muestra es una función lineal de la dimensión VC del espacio de hipótesis.
En geometría computacional
La dimensión VC es uno de los parámetros críticos en el tamaño de las redes ε , lo que determina la complejidad de los algoritmos de aproximación basados en ellas; Los conjuntos de rango sin dimensión VC finita pueden no tener redes ε finitas en absoluto.
Límites
0. La dimensión VC de la familia de conjuntos dual de es estrictamente menor que , y esto es lo mejor posible.
1. La dimensión VC de una familia de conjuntos finita es como máximo . [2] : 56 Esto se debe a por definición.
2. Dado un conjunto-familia , definir como un conjunto-familia que contiene todas las intersecciones de elementos de . Entonces: [2] : 57
3. Dado un conjunto-familia y un elemento , definir dónde denota diferencia de conjunto simétrico . Entonces: [2] : 58
Dimensión VC de un plano proyectivo finito
Un plano proyectivo finito de orden n es una colección de n 2 + n + 1 conjuntos (llamados "líneas") sobre n 2 + n + 1 elementos (llamados "puntos"), para los cuales:
- Cada línea contiene exactamente n + 1 puntos.
- Cada línea se cruza con todas las demás en exactamente un punto.
- Cada punto está contenido exactamente en n + 1 líneas.
- Cada punto está exactamente en una línea en común con todos los demás puntos.
- Al menos cuatro puntos no se encuentran en una línea común.
La dimensión VC de un plano proyectivo finito es 2. [4]
Prueba : (a) Para cada par de puntos distintos, hay una línea que contiene ambos, líneas que contienen solo uno de ellos y líneas que no contienen ninguno de ellos, por lo que cada conjunto de tamaño 2 se rompe. (b) Para cualquier triples de tres puntos distintos, si hay una línea X que contiene los tres, entonces no hay una línea y que contiene exactamente dos (desde entonces x e y se cruzarían en dos puntos, lo cual es contrario a la definición de un plano proyectivo). Por lo tanto, ningún conjunto de tamaño 3 se rompe.
Dimensión VC de un clasificador impulsor
Supongamos que tenemos una clase base de clasificadores simples, cuya dimensión VC es .
Podemos construir un clasificador más poderoso combinando varios clasificadores diferentes de ; esta técnica se llama refuerzo . Formalmente, dado clasificadores y un vector de peso , podemos definir el siguiente clasificador:
La dimensión VC del conjunto de todos esos clasificadores (para todas las selecciones de clasificadores de y un vector de peso de ), asumiendo , es como máximo: [5] : 108–109
Dimensión VC de una red neuronal
Una red neuronal se describe mediante un gráfico acíclico dirigido G ( V , E ), donde:
- V es el conjunto de nodos. Cada nodo es una simple celda de cálculo.
- E es el conjunto de aristas, cada arista tiene un peso.
- La entrada a la red está representada por las fuentes del gráfico: los nodos sin bordes entrantes.
- La salida de la red está representada por los sumideros del gráfico: los nodos sin bordes salientes.
- Cada nodo intermedio obtiene como entrada una suma ponderada de las salidas de los nodos en sus bordes entrantes, donde los pesos son los pesos en los bordes.
- Cada nodo intermedio genera una determinada función creciente de su entrada, como la función de signo o la función sigmoidea . Esta función se denomina función de activación .
La dimensión VC de una red neuronal está limitada de la siguiente manera: [5] : 234-235
- Si la función de activación es la función de signo y los pesos son generales, entonces la dimensión VC es como máximo .
- Si la función de activación es la función sigmoidea y los pesos son generales, entonces la dimensión VC es al menos y como mucho .
- Si los pesos provienen de una familia finita (por ejemplo, los pesos son números reales que se pueden representar como máximo con 32 bits en una computadora), entonces, para ambas funciones de activación, la dimensión VC es como máximo .
Generalizaciones
La dimensión VC se define para espacios de funciones binarias (funciones hasta {0,1}). Se han sugerido varias generalizaciones para espacios de funciones no binarias.
- Para funciones de valores múltiples (funciones a {0, ..., n }), se puede usar la dimensión Natarajan [6] . Ben David et al [7] presentan una generalización de este concepto.
- Para funciones con valores reales (por ejemplo, funciones a un intervalo real, [0,1]), se puede utilizar la pseudo-dimensión [8] [9] [10] de Pollard .
- La complejidad de Rademacher proporciona límites similares a la VC y, a veces, puede proporcionar más información que los cálculos de dimensión de VC en métodos estadísticos tales como los que usan kernels [ cita requerida ] .
Ver también
- Función de crecimiento
- Lema de Sauer-Shelah , un límite en el número de conjuntos en un sistema de conjuntos en términos de la dimensión VC.
- Teorema de Karpinski-Macintyre , [11] un límite en la dimensión VC de las fórmulas generales de Pfaffian.
Notas al pie
- ^ Vapnik, VN; Chervonenkis, A. Ya. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades". Teoría de la probabilidad y sus aplicaciones . 16 (2): 264. doi : 10.1137 / 1116025 . Esta es una traducción al inglés, por B. Seckler, del periódico ruso: "Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades". Dokl. Akad. Nauk . 181 (4): 781. 1968. La traducción se reprodujo como: Vapnik, VN; Chervonenkis, A. Ya. (2015). "Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades". Medidas de complejidad . pag. 11. doi : 10.1007 / 978-3-319-21852-6_3 . ISBN 978-3-319-21851-9.
- ^ a b c d Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . Estados Unidos, Massachusetts: MIT Press. ISBN 9780262018258.
- ^ Vapnik 2000 .
- ^ Alon, N .; Haussler, D .; Welzl, E. (1987). "Partición e incrustación geométrica de espacios de rango de dimensión finita de Vapnik-Chervonenkis". Actas del tercer simposio anual sobre geometría computacional - SCG '87 . pag. 331. doi : 10.1145 / 41958.41994 . ISBN 978-0897912310. S2CID 7394360 .
- ^ a b Shalev-Shwartz, Shai; Ben-David, Shai (2014). Comprensión del aprendizaje automático: de la teoría a los algoritmos . Prensa de la Universidad de Cambridge. ISBN 9781107057135.
- ^ Natarajan 1989 .
- ^ Ben-David, Cesa-Bianchi y Long 1992 .
- ^ Pollard 1984 .
- ^ Anthony y Bartlett 2009 .
- ^ Morgenstern y Roughgarden, 2015 .
- ^ Karpinski y Macintyre 1997 .
Referencias
- Moore, Andrew. "Tutorial de dimensión VC" .
- Vapnik, Vladimir (2000). La naturaleza de la teoría del aprendizaje estadístico . Saltador.
- Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Warmuth, MK (1989). "Capacidad de aprendizaje y la dimensión de Vapnik-Chervonenkis" (PDF) . Revista de la ACM . 36 (4): 929–865. doi : 10.1145 / 76359.76371 . S2CID 1138467 .
- Burges, Christopher. "Tutorial sobre SVM para el reconocimiento de patrones" (PDF) . (contiene información también para la dimensión VC)
- Chazelle, Bernard . "El método de la discrepancia" .
- Natarajan, BK (1989). "Sobre el aprendizaje de conjuntos y funciones" . Aprendizaje automático . 4 : 67–97. doi : 10.1007 / BF00114804 .
- Ben-David, Shai; Cesa-Bianchi, Nicolò; Long, Philip M. (1992). "Caracterizaciones de la capacidad de aprendizaje para clases de funciones valoradas en {O, ..., n }". Actas del quinto taller anual sobre teoría del aprendizaje computacional - COLT '92 . pag. 333. doi : 10.1145 / 130385.130423 . ISBN 089791497X.
- Pollard, D. (1984). Convergencia de procesos estocásticos . Saltador. ISBN 9781461252542.
- Anthony, Martin; Bartlett, Peter L. (2009). Aprendizaje de redes neuronales: fundamentos teóricos . ISBN 9780521118620.
- Morgenstern, Jamie H .; Roughgarden, Tim (2015). Sobre la pseudo-dimensión de las subastas casi óptimas . NIPS. arXiv : 1506.03684 . Código bibliográfico : 2015arXiv150603684M .
- Karpinski, Marek; Macintyre, Angus (febrero de 1997). "Límites polinomiales para la dimensión VC de las redes neuronales sigmoidales y generales de Pfaffian" . Revista de Ciencias de la Computación y Sistemas . 54 (1): 169-176. doi : 10.1006 / jcss.1997.1477 .