Dimensión Vapnik-Chervonenkis

Noción en aprendizaje automático supervisado.

En la teoría de Vapnik-Chervonenkis , la dimensión de Vapnik-Chervonenkis (VC) es una medida del tamaño (capacidad, complejidad, poder expresivo, riqueza o flexibilidad) de una clase de conjuntos. La noción puede extenderse a clases de funciones binarias. Se define como la cardinalidad del conjunto más grande de puntos que el algoritmo puede destruir , lo que significa que el algoritmo siempre puede aprender un clasificador perfecto para cualquier etiquetado de al menos una configuración de esos puntos de datos. Fue definido originalmente por Vladimir Vapnik y Alexey Chervonenkis . ^[1]

Informalmente, 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 moverse, 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 inestable. Un polinomio de este tipo tiene una gran capacidad. Una alternativa mucho más sencilla es establecer un umbral para 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 rigurosa a continuación.

Definiciones

Dimensión VC de una familia de conjuntos

Sean una familia de conjuntos (un conjunto de conjuntos) y un conjunto. Su intersección se define como la siguiente familia de conjuntos: ${\displaystyle H}$ ${\displaystyle C}$

${\displaystyle H\cap C:=\{h\cap C\mid h\in H\}.}$

Decimos que un conjunto se rompe si contiene todos los subconjuntos de , es decir: ${\displaystyle C}$ ${\displaystyle H}$ ${\displaystyle H\cap C}$ ${\displaystyle C}$

${\displaystyle |H\cap C|=2^{|C|}.}$

La dimensión VC de es la cardinalidad del conjunto más grande que es destrozado por . Si se pueden romper conjuntos arbitrariamente grandes, la dimensión VC es . ${\displaystyle D}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle \infty }$

Dimensión VC de un modelo de clasificación.

Se dice que un modelo de clasificación binaria con algún vector de parámetros destruye un conjunto de puntos de datos generalmente posicionados si, para cada asignación de etiquetas a esos puntos, existe tal que el modelo no cometa errores al evaluar ese conjunto de puntos de datos ^{[ cita necesaria ]} . ${\displaystyle f}$ ${\displaystyle \theta }$ ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle \theta }$ ${\displaystyle f}$

La dimensión VC de un modelo es el número máximo de puntos que se pueden disponer de manera que los rompa. Más formalmente, es el cardinal máximo tal que existe un conjunto de puntos de datos de cardinalidad generalmente posicionados que pueden ser destruidos por . ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle f}$

Ejemplos

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 clasificadores diferentes, es como máximo (este es un límite superior de la dimensión VC; el lema de Sauer-Shelah proporciona un límite inferior de la dimensión). ${\displaystyle f}$ ${\displaystyle 2^{d}}$ ${\displaystyle d}$

2. es un clasificador de umbral uniparamétrico para 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 de es 1 porque: (a) Puede romper un solo punto. Para cada punto , un clasificador lo etiqueta como 0 si y lo etiqueta como 1 si . (b) No puede destrozar todos los conjuntos con dos puntos. Para cada conjunto de dos números, si el más pequeño está etiquetado con 1, entonces el mayor también debe estar etiquetado con 1, por lo que no todos los etiquetados son posibles. ${\displaystyle f}$ ${\displaystyle \theta }$ ${\displaystyle f_{\theta }}$ ${\displaystyle \theta }$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f_{\theta }}$ ${\displaystyle \theta >x}$ ${\displaystyle \theta <x}$

3. es un clasificador de intervalos uniparamétrico para 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 de es 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 destrozar 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 con 1, entonces el del medio también debe estar etiquetado con 1, por lo que no todos los etiquetados son posibles. ${\displaystyle f}$ ${\displaystyle \theta }$ ${\displaystyle f_{\theta }}$ ${\displaystyle [\theta ,\theta +4]}$ ${\displaystyle f}$ ${\displaystyle \{x,x+2\}}$ ${\displaystyle f_{\theta }}$ ${\displaystyle \theta <x-4}$ ${\displaystyle \theta >x+2}$ ${\displaystyle \theta \in [x-4,x-2)}$ ${\displaystyle \theta \in [x-2,x]}$ ${\displaystyle \theta \in (x,x+2]}$

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 (cualesquiera 3 puntos que no sean colineales pueden romperse). Sin embargo, ningún conjunto de 4 puntos puede romperse: según el teorema de radón , cuatro puntos cualesquiera pueden dividirse 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 uno 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 posibles asignaciones de etiquetas para los tres puntos.} ${\displaystyle f}$

5. es un clasificador sinusoidal de un solo parámetro , es decir, para un determinado parámetro , el clasificador devuelve 1 si el número de entrada lo tiene y 0 en caso contrario. La dimensión VC de es infinita, ya que puede destruir cualquier subconjunto finito del conjunto . ^{[2] : 57} ${\displaystyle f}$ ${\displaystyle \theta }$ ${\displaystyle f_{\theta }}$ ${\displaystyle x}$ ${\displaystyle \sin(\theta x)>0}$ ${\displaystyle f}$ ${\displaystyle \{2^{-m}\mid m\in \mathbb {N} \}}$

Usos

En la 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 prueba (es decir, el riesgo con función de pérdida 0-1) se aleje de un límite superior (en datos extraídos de la misma distribución que el conjunto de entrenamiento) viene dada por:

${\displaystyle \Pr \left({\text{test error}}\leqslant {\text{training error}}+{\sqrt {{\frac {1}{N}}\left[D\left(\log \left({\tfrac {2N}{D}}\right)+1\right)-\log \left({\tfrac {\eta }{4}}\right)\right]}}\,\right)=1-\eta ,}$

donde 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 . Cuando es mayor, el error de prueba puede ser mucho mayor que el error de entrenamiento. Esto se debe a sobreajuste ). ${\displaystyle D}$ ${\displaystyle 0<\eta \leqslant 1}$ ${\displaystyle N}$ ${\displaystyle D\ll N}$ ${\displaystyle D}$

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: ^{[4] : ​​73} ${\displaystyle D}$

${\displaystyle N=\Theta \left({\frac {D+\ln {1 \over \delta }}{\varepsilon }}^{2}\right)}$

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. ${\displaystyle \varepsilon }$ ${\displaystyle \delta }$

En geometría computacional

La dimensión VC es uno de los parámetros críticos en el tamaño de las ε-nets , que determina la complejidad de los algoritmos de aproximación basados ​​en ellas; los conjuntos de rangos sin dimensión VC finita pueden no tener redes ε finitas en absoluto.

Límites

0. La dimensión VC de la familia de conjuntos duales de es estrictamente menor que , y esto es lo mejor posible. ${\displaystyle {\mathcal {F}}}$ ${\displaystyle 2^{\operatorname {vc} ({\mathcal {F}})+1}}$

1. La dimensión VC de una familia de conjuntos finita es como máximo . ^{[2] : 56} Esto se debe a que, por definición. ${\displaystyle H}$ ${\displaystyle \log _{2}|H|}$ ${\displaystyle |H\cap C|\leq |H|}$

2. Dada una familia de conjuntos , defina como una familia de conjuntos que contiene todas las intersecciones de elementos de . Entonces: ^{[2] : 57} ${\displaystyle H}$ ${\displaystyle H_{s}}$ ${\displaystyle s}$ ${\displaystyle H}$

${\displaystyle \operatorname {VCDim} (H_{s})\leq \operatorname {VCDim} (H)\cdot (2s\log _{2}(3s))}$

3. Dada una familia de conjuntos y un elemento , defina dónde denota diferencia de conjuntos simétrica . Entonces: ^{[2] : 58} ${\displaystyle H}$ ${\displaystyle h_{0}\in H}$ ${\displaystyle H\,\Delta h_{0}:=\{h\,\Delta h_{0}\mid h\in H\}}$ ${\displaystyle \Delta }$

${\displaystyle \operatorname {VCDim} (H\,\Delta h_{0})=\operatorname {VCDim} (H)}$

Ejemplos de clases de VC

Dimensión VC de un plano proyectivo finito

Un plano proyectivo finito de orden n es una colección de n ² + n + 1 conjuntos (llamados "líneas") sobre n ² + 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 líneas exactamente en 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. ^[5]

Prueba : (a) Para cada par de puntos distintos, hay una línea que contiene a ambos, líneas que contienen solo uno de ellos y líneas que contienen ninguno de ellos, por lo que cada conjunto de tamaño 2 se rompe. (b) Para cualquier tripleta de tres puntos distintos, si hay una recta x que contiene los tres, entonces no hay una recta y que contenga exactamente dos (ya que entonces x e y se cortarían en dos puntos, lo cual es contrario a la definición de un plano proyectivo). Por tanto, ningún conjunto de tamaño 3 se rompe.

Dimensión VC de un clasificador potenciador.

Supongamos que tenemos una clase base de clasificadores simples, cuya dimensión VC es . ${\displaystyle B}$ ${\displaystyle D}$

Podemos construir un clasificador más potente combinando varios clasificadores diferentes de ; Esta técnica se llama impulso . Formalmente, dados los clasificadores y un vector de peso , podemos definir el siguiente clasificador: ${\displaystyle B}$ ${\displaystyle T}$ ${\displaystyle h_{1},\ldots ,h_{T}\in B}$ ${\displaystyle w\in \mathbb {R} ^{T}}$

${\displaystyle f(x)=\operatorname {sign} \left(\sum _{t=1}^{T}w_{t}\cdot h_{t}(x)\right)}$

La dimensión VC del conjunto de todos esos clasificadores (para todas las selecciones de clasificadores de y un vector de peso de ), suponiendo que , es como máximo: ^{[4] : ​​108–109} ${\displaystyle T}$ ${\displaystyle B}$ ${\displaystyle \mathbb {R} ^{T}}$ ${\displaystyle T,D\geq 3}$

${\displaystyle T\cdot (D+1)\cdot (3\log(T\cdot (D+1))+2)}$

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 celda de cálculo simple.
• 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 aristas entrantes.
• La salida de la red está representada por los sumideros del gráfico: los nodos sin bordes de salida.
• Cada nodo intermedio recibe 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 llama función de activación .

La dimensión VC de una red neuronal está delimitada de la siguiente manera: ^{[4] : ​​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 . ${\displaystyle O(|E|\cdot \log(|E|))}$
• 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 máximo . ${\displaystyle \Omega (|E|^{2})}$ ${\displaystyle O(|E|^{2}\cdot |V|^{2})}$
• Si los pesos provienen de una familia finita (por ejemplo, los pesos son números reales que pueden representarse como máximo con 32 bits en una computadora), entonces, para ambas funciones de activación, la dimensión VC es como máximo . ${\displaystyle O(|E|)}$

Generalizaciones

La dimensión VC se define para espacios de funciones binarias (funciones para {0,1}). Se han sugerido varias generalizaciones para espacios de funciones no binarias.

• Para funciones de clases múltiples (por ejemplo, funciones para {0,..., n-1 }), se puede utilizar la dimensión de Natarajan ^[6] . Ben David y cols. ^[7] presentan una generalización de este concepto.
• Para funciones con valores reales (p. ej., funciones en un intervalo real, [0,1]), se puede utilizar la pseudodimensión de Pollard ^{[8] [9] [10] .}
• La complejidad de Rademacher proporciona límites similares a los de VC y, a veces, puede proporcionar más información que los cálculos de dimensiones de VC en métodos estadísticos como los que utilizan núcleos ^{[ cita requerida ]} .
• La capacidad de memoria (a veces capacidad equivalente a la memoria) proporciona un límite inferior de capacidad, en lugar de un límite superior (consulte, por ejemplo: Red neuronal artificial#Capacidad ) y, por lo tanto, indica el punto de posible sobreajuste.

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 Pfaff.

Notas a pie de página

1. Vapnik, VN; Chervonenkis, A. Ya. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos con respecto 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, realizada por B. Seckler, del artículo ruso: "Sobre la convergencia uniforme de frecuencias relativas de eventos con respecto a sus probabilidades". Dokl. Akád. 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 con respecto a sus probabilidades". Medidas de Complejidad . pag. 11. doi :10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
2. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . Estados Unidos, Massachusetts: MIT Press. ISBN 9780262018258.
3. Vápnik 2000.
4. Shalev-Shwartz, Shai; Ben-David, Shai (2014). Comprender el aprendizaje automático: de la teoría a los algoritmos . Prensa de la Universidad de Cambridge. ISBN 9781107057135.
5. 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.
6. Natarajan 1989.
7. Ben-David, Cesa-Bianchi y Long 1992.
8. Pollard 1984.
9. Antonio y Bartlett 2009.
10. Morgenstern y Roughgarden 2015.
11. Karpinski y Macintyre 1997.

Referencias

• Moore, Andrés. "Tutorial de dimensiones de VC" (PDF) .
• Vápnik, Vladimir (2000). La naturaleza de la teoría del aprendizaje estadístico . Saltador.
• Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, MK (1989). "La capacidad de aprendizaje y la dimensión Vapnik-Chervonenkis" (PDF) . Revista de la ACM . 36 (4): 929–865. doi : 10.1145/76359.76371. S2CID  1138467.
• Burges, Cristóbal. "Tutorial sobre SVM para reconocimiento de patrones" (PDF) . Microsoft .(que 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ò; Largo, Philip M. (1992). "Caracterizaciones de capacidad de aprendizaje para clases de funciones valoradas {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.
• Antonio, Martín; Bartlett, Peter L. (2009). Aprendizaje de redes neuronales: fundamentos teóricos . ISBN 9780521118620.
• Morgenstern, Jamie H.; Jardín áspero, Tim (2015). Sobre la pseudodimensión de las subastas casi óptimas. NIPS. arXiv : 1506.03684 . Código Bib : 2015arXiv150603684M.
• Karpinski, Marek; Macintyre, Angus (febrero de 1997). "Límites polinomiales para la dimensión VC de redes neuronales sigmoidales y de Pfaffian generales". Revista de Ciencias de la Computación y de Sistemas . 54 (1): 169-176. doi : 10.1006/jcss.1997.1477 .