Dimensión Vapnik-Chervonenkis

Noción en el 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 se puede extender a clases de funciones binarias. Se define como la cardinalidad del conjunto más grande de puntos que el algoritmo puede fragmentar , 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 definida originalmente 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 la umbralización de un polinomio de alto grado : si el polinomio evalúa por encima de cero, ese punto se clasifica como positivo, de lo contrario, como negativo. Un polinomio de alto grado puede ser irregular, por lo que puede ajustarse bien a un conjunto dado de puntos de entrenamiento. Pero se puede esperar que el clasificador cometa errores en otros puntos, porque es demasiado irregular. Un polinomio de este tipo tiene una alta capacidad. Una alternativa mucho más simple es establecer un umbral para una función lineal. Esta función puede no ajustarse bien al conjunto de entrenamiento, porque tiene una baja 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 descompone 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 se fragmenta por . Si se pueden fragmentar 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 destroza un conjunto de puntos de datos generalmente posicionados si, para cada asignación de etiquetas a esos puntos, existe un tal que el modelo no comete errores al evaluar ese conjunto de puntos de datos ^{[ cita requerida ]} . ${\displaystyle f}$ ${\displaystyle \theta }$ ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle \theta }$ ${\displaystyle f}$

La dimensión VC de un modelo es la cantidad máxima de puntos que se pueden organizar de modo que se rompan. Más formalmente, es el cardinal máximo de modo que exista un conjunto de puntos de datos de cardinalidad generalmente posicionados que se puedan romper por . ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle f}$

Ejemplos

1. ${\displaystyle f}$es un clasificador constante (sin parámetros); su dimensión VC es 0 ya que no puede fragmentar 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 2^{d}}$ ${\displaystyle d}$
2. ${\displaystyle f}$es un clasificador de umbral uniparamétrico 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 de es 1 porque: (a) Puede destrozar un único 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 como 1, entonces el más grande también debe estar etiquetado como 1, por lo que no todos los etiquetados son posibles. ${\displaystyle \theta }$ ${\displaystyle f_{\theta }}$ ${\displaystyle \theta }$ ${\displaystyle f}$ ${\displaystyle x}$ ${\displaystyle f_{\theta }}$ ${\displaystyle \theta >x}$ ${\displaystyle \theta <x}$
3. ${\displaystyle f}$es un clasificador de intervalos uniparamétrico sobre 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 fragmentar 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 fragmentar 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 estar etiquetado como 1, por lo que no todos los etiquetados son posibles. ${\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. ${\displaystyle f}$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 negativos. Existen conjuntos de 3 puntos que pueden de hecho fragmentarse utilizando este modelo (cualquiera de los 3 puntos que no sean colineales puede fragmentarse). Sin embargo, ningún conjunto de 4 puntos puede fragmentarse: por el teorema de Radon , cualesquiera cuatro puntos pueden dividirse en dos subconjuntos con envolturas convexas que se intersecan , 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 al intentar fragmentar para alguna asignación de etiqueta. Tenga en cuenta que solo se muestran 3 de las 2 ³  = 8 asignaciones de etiquetas posibles para los tres puntos.
5. ${\displaystyle f}$es un clasificador de seno uniparamétrico , es decir, para un determinado parámetro , el clasificador devuelve 1 si el número de entrada tiene y 0 en caso contrario. La dimensión VC de es infinita, ya que puede fragmentar cualquier subconjunto finito del conjunto . ^{[2] : 57} ${\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 del 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 una función de pérdida de 0-1) se aleje de un límite superior (en datos extraídos iid de la misma distribución que el conjunto de entrenamiento) está 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 al 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 lo 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 }$

Engeometría computacional

La dimensión VC es uno de los parámetros críticos en el tamaño de las ε-redes , 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 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 finitos 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 donde denota la diferencia de conjuntos simétricos . 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 intersecta todas las demás líneas exactamente en un punto.
• Cada punto está contenido en exactamente n + 1 líneas.
• Cada punto está en exactamente 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]

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

Dimensión VC de un clasificador de refuerzo

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 boosting . 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 , 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 bordes entrantes.
• La salida de la red está representada por los sumideros del gráfico: los nodos sin bordes salientes.
• 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 denomina función de activación .

La dimensión VC de una red neuronal está limitada 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 como mínimo 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 con un máximo de 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 hasta {0,1}). Se han sugerido varias generalizaciones para espacios de funciones no binarias.

• Para funciones multiclase (por ejemplo, funciones hasta {0,..., n-1 }), se puede utilizar la dimensión de Natarajan ^[6] y su generalización, la dimensión DS ^{[7] .}
• Para funciones de valores reales (por ejemplo, funciones en un intervalo real, [0,1]), se puede utilizar la dimensión gráfica ^[6] o la pseudodimensión de Pollard ^{[8] [9] [10] .}
• La complejidad de Rademacher proporciona límites similares a la VC y, a veces, puede brindar más información que los cálculos de dimensión de VC sobre métodos estadísticos como los que utilizan núcleos ^{[ cita requerida ]} .
• La capacidad de memoria (a veces, capacidad equivalente de memoria) proporciona un límite inferior de capacidad, en lugar de un límite superior (ver, por ejemplo: Red neuronal artificial#Capacidad ) y, por lo tanto, indica el punto de sobreajuste potencial.

Véase 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 al pie

1. Vapnik, VN; Chervonenkis, A. Ya. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Teoría de la probabilidad y sus aplicaciones . 16 (2): 264. doi :10.1137/1116025.Se trata de una traducción al inglés, realizada por B. Seckler, del artículo ruso: "Sobre la convergencia uniforme de las frecuencias relativas de los acontecimientos con sus probabilidades". Dokl. Akad. Nauk . 181 (4): 781. 1968.La traducción fue reproducida como: Vapnik, VN; Chervonenkis, A. Ya. (2015). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Medidas de complejidad . p. 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 . EE. UU., Massachusetts: MIT Press. ISBN 9780262018258.
3. Vapnik 2000.
4. Shalev-Shwartz, Shai; Ben-David, Shai (2014). Entender el aprendizaje automático: de la teoría a los algoritmos . Cambridge University Press. ISBN 9781107057135.
5. Alon, N.; Haussler, D.; Welzl, E. (1987). "Particionado 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 . p. 331. doi :10.1145/41958.41994. ISBN 978-0897912310.S2CID 7394360  .
6. Natarajan 1989.
7. Brujim 2022. sfn error: no target: CITEREFBrukhim2022 (help)
8. Pollard 1984.
9. Anthony y Bartlett 2009.
10. Morgenstern y Roughgarden 2015.
11. Karpinski y Macintyre 1997.

Referencias

• Moore, Andrew. "Tutorial de dimensión VC" (PDF) .
• Vapnik, Vladimir (2000). La naturaleza de la teoría del aprendizaje estadístico . Springer.
• Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, MK (1989). "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, Christopher. "Tutorial sobre SVM para reconocimiento de patrones" (PDF) . Microsoft .(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). "Caracterización de la capacidad de aprendizaje para clases de funciones con valores {O, …, n }". Actas del quinto taller anual sobre teoría del aprendizaje computacional – COLT '92 . p. 333. doi :10.1145/130385.130423. ISBN 089791497X.
• Brukhim, Nataly; Carmon, Daniel; Dinur, Irit; Moran, Shay; Yehudayoff, Amir (2022). "Una caracterización de la capacidad de aprendizaje multiclase". 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) . arXiv : 2203.01550 .
• Pollard, D. (1984). Convergencia de procesos estocásticos . Springer. 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 pseudodimensión de subastas casi óptimas. NIPS. arXiv : 1506.03684 . Código Bibliográfico :2015arXiv150603684M.
• Karpinski, Marek; Macintyre, Angus (febrero de 1997). "Límites polinómicos para la dimensión VC de redes neuronales sigmoideas y pfaffianas generales". Journal of Computer and System Sciences . 54 (1): 169–176. doi : 10.1006/jcss.1997.1477 .