Teoría de Vapnik-Chervonenkis

La teoría de Vapnik-Chervonenkis (también conocida como teoría VC ) fue desarrollada entre 1960 y 1990 por Vladimir Vapnik y Alexey Chervonenkis . La teoría es una forma de teoría del aprendizaje computacional que intenta explicar el proceso de aprendizaje desde un punto de vista estadístico.

La teoría de VC cubre al menos cuatro partes (como se explica en La naturaleza de la teoría del aprendizaje estadístico ^[1] ):

• Teoría de la consistencia de los procesos de aprendizaje
  • ¿Cuáles son las condiciones (necesarias y suficientes) para la consistencia de un proceso de aprendizaje basado en el principio empírico de minimización de riesgos ?
• Teoría no asintótica de la tasa de convergencia de los procesos de aprendizaje
  • ¿Qué tan rápida es la tasa de convergencia del proceso de aprendizaje?
• Teoría del control de la capacidad de generalización de los procesos de aprendizaje
  • ¿Cómo se puede controlar la tasa de convergencia (la capacidad de generalización ) del proceso de aprendizaje?
• Teoría de la construcción de máquinas de aprendizaje
  • ¿Cómo se pueden construir algoritmos que puedan controlar la capacidad de generalización?

La teoría VC es una rama importante de la teoría del aprendizaje estadístico . Una de sus principales aplicaciones en la teoría del aprendizaje estadístico es proporcionar condiciones de generalización para los algoritmos de aprendizaje. Desde este punto de vista, la teoría VC está relacionada con la estabilidad , que es un enfoque alternativo para caracterizar la generalización.

Además, la teoría VC y la dimensión VC son fundamentales en la teoría de procesos empíricos , en el caso de procesos indexados por clases VC. Podría decirse que estas son las aplicaciones más importantes de la teoría VC y se emplean para demostrar la generalización. Se presentarán varias técnicas que se utilizan ampliamente en el proceso empírico y la teoría VC. La discusión se basa principalmente en el libro Weak Convergence and Empirical Processes: With Applications to Statistics . ^[2]

Sea un espacio medible . Para cualquier medida en , y cualquier función medible , defina${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$${\displaystyle Q}$${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$

${\displaystyle Qf=\int fdQ}$

Aquí se ignorarán los problemas de mensurabilidad; para obtener más detalles técnicos, consulte ^[1] Sea una clase de funciones mensurables y defina:${\displaystyle {\mathcal {F}}}$${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$

${\displaystyle \|Q\|_{\mathcal {F}}=\sup\{\vert Qf\vert \ :\ f\in {\mathcal {F}}\}.}$

Sean elementos aleatorios independientes, distribuidos de forma idéntica de . Luego defina la medida empírica${\displaystyle X_{1},\ldots ,X_{n}}$${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$

${\displaystyle \mathbb {P} _{n}=n^{-1}\sum _{i=1}^{n}\delta _{X_{i}},}$

donde δ representa aquí la medida de Dirac . La medida empírica induce una función dada por:${\displaystyle {\mathcal {F}}\to \mathbf {R} }$

${\displaystyle f\mapsto \mathbb {P} _{n}f={\frac {1}{n}}(f(X_{1})+...+f(X_{n}))}$

Supongamos ahora que P es la distribución verdadera subyacente de los datos, que es desconocida. La teoría de procesos empíricos apunta a identificar clases para las que se cumplen afirmaciones como la siguiente:${\displaystyle {\mathcal {F}}}$

• Ley uniforme de grandes números :

  ${\displaystyle \|\mathbb {P} _{n}-P\|_{\mathcal {F}}{\underset {n}{\to }}0,}$

Es decir, como ,${\displaystyle n\to \infty }$

${\displaystyle \left|{\frac {1}{n}}(f(X_{1})+...+f(X_{n}))-\int fdP\right|\to 0}$

uniformemente para todos .${\displaystyle f\in {\mathcal {F}}}$

• teorema del límite central uniforme :

${\displaystyle \mathbb {G} _{n}={\sqrt {n}}(\mathbb {P} _{n}-P)\rightsquigarrow \mathbb {G} ,\quad {\text{in }}\ell ^{\infty }({\mathcal {F}})}$

En el primer caso se denomina clase Glivenko-Cantelli , y en el segundo caso (bajo el supuesto ) la clase se denomina Donsker o P -Donsker. Una clase Donsker es Glivenko-Cantelli en probabilidad mediante una aplicación del teorema de Slutsky .${\displaystyle {\mathcal {F}}}$${\displaystyle \forall x,\sup \nolimits _{f\in {\mathcal {F}}}\vert f(x)-Pf\vert <\infty }$${\displaystyle {\mathcal {F}}}$

Estas afirmaciones son verdaderas para un solo , según los argumentos LLN y CLT estándar en condiciones de regularidad, y la dificultad en los procesos empíricos surge porque se están haciendo afirmaciones conjuntas para todos los . Intuitivamente, entonces, el conjunto no puede ser demasiado grande y resulta que la geometría de juega un papel muy importante.${\displaystyle f}$${\displaystyle f\in {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$

Una forma de medir el tamaño del conjunto de funciones es utilizar los llamados números de cobertura . El número de cobertura${\displaystyle {\mathcal {F}}}$

${\displaystyle N(\varepsilon ,{\mathcal {F}},\|\cdot \|)}$

es el número mínimo de bolas necesarias para cubrir el conjunto (aquí se supone obviamente que hay una norma subyacente en ). La entropía es el logaritmo del número de cobertura.${\displaystyle \{g:\|g-f\|<\varepsilon \}}$${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}}$

A continuación se proporcionan dos condiciones suficientes bajo las cuales se puede demostrar que el conjunto es Glivenko-Cantelli o Donsker.${\displaystyle {\mathcal {F}}}$

Una clase es P -Glivenko–Cantelli si es P -medible con envolvente F tal que y satisface:${\displaystyle {\mathcal {F}}}$${\displaystyle P^{\ast }F<\infty }$

${\displaystyle \forall \varepsilon >0\quad \sup \nolimits _{Q}N(\varepsilon \|F\|_{Q},{\mathcal {F}},L_{1}(Q))<\infty .}$

La siguiente condición es una versión del célebre teorema de Dudley . Si es una clase de funciones tales que${\displaystyle {\mathcal {F}}}$

${\displaystyle \int _{0}^{\infty }\sup \nolimits _{Q}{\sqrt {\log N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)}}d\varepsilon <\infty }$

entonces es P -Donsker para cada medida de probabilidad P tal que . En la última integral, la notación significa${\displaystyle {\mathcal {F}}}$${\displaystyle P^{\ast }F^{2}<\infty }$

${\displaystyle \|f\|_{Q,2}=\left(\int |f|^{2}dQ\right)^{\frac {1}{2}}}$.

La mayoría de los argumentos sobre cómo limitar el proceso empírico se basan en la simetrización, las desigualdades máximas y de concentración y el encadenamiento. La simetrización suele ser el primer paso de las demostraciones y, dado que se utiliza en muchas demostraciones de aprendizaje automático sobre la limitación de funciones de pérdida empírica (incluida la demostración de la desigualdad VC que se analiza en la siguiente sección), se presenta aquí.

Consideremos el proceso empírico:

${\displaystyle f\mapsto (\mathbb {P} _{n}-P)f={\dfrac {1}{n}}\sum _{i=1}^{n}(f(X_{i})-Pf)}$

Resulta que existe una conexión entre el proceso empírico y el siguiente proceso simetrizado:

${\displaystyle f\mapsto \mathbb {P} _{n}^{0}f={\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})}$

El proceso simetrizado es un proceso de Rademacher , condicionalmente a los datos . Por lo tanto, es un proceso subgaussiano por la desigualdad de Hoeffding .${\displaystyle X_{i}}$

Lema (Simetrización). Para cada Φ no decreciente, convexo : R → R y clase de funciones mensurables ,${\displaystyle {\mathcal {F}}}$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} \Phi \left(2\left\|\mathbb {P} _{n}^{0}\right\|_{\mathcal {F}}\right)}$

La prueba del lema de simetrización se basa en la introducción de copias independientes de las variables originales (a veces denominadas muestras fantasma ) y en la sustitución de la esperanza interna del LHS por estas copias. Después de una aplicación de la desigualdad de Jensen , se podrían introducir diferentes signos (de ahí el nombre de simetrización) sin cambiar la esperanza. La prueba se puede encontrar a continuación debido a su naturaleza instructiva. El mismo método de prueba se puede utilizar para demostrar el teorema de Glivenko-Cantelli . ^[3]${\displaystyle X_{i}}$

Una forma típica de probar CLT empíricas, primero utiliza simetrización para pasar el proceso empírico a los datos y luego argumenta condicionalmente sobre ellos, utilizando el hecho de que los procesos de Rademacher son procesos simples con buenas propiedades.${\displaystyle \mathbb {P} _{n}^{0}}$

Resulta que existe una conexión fascinante entre ciertas propiedades combinatorias del conjunto y los números de entropía. Los números de recubrimiento uniforme pueden controlarse mediante el concepto de clases de conjuntos de Vapnik-Chervonenkis , o, para abreviar, conjuntos VC .${\displaystyle {\mathcal {F}}}$

Consideremos una colección de subconjuntos del espacio muestral . se dice que selecciona un cierto subconjunto del conjunto finito si para algún . se dice que desintegra S si selecciona cada uno de sus 2 ⁿ subconjuntos. El índice VC (similar a la dimensión VC + 1 para un conjunto clasificador elegido apropiadamente) de es el n más pequeño para el cual ningún conjunto de tamaño n se desintegra por .${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle W}$${\displaystyle S=\{x_{1},\ldots ,x_{n}\}\subset {\mathcal {X}}}$${\displaystyle W=S\cap C}$${\displaystyle C\in {\mathcal {C}}}$${\displaystyle {\mathcal {C}}}$ ${\displaystyle V({\mathcal {C}})}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {C}}}$

El lema de Sauer establece entonces que el número de subconjuntos seleccionados por una clase VC satisface:${\displaystyle \Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$${\displaystyle {\mathcal {C}}}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})\leq \sum _{j=0}^{V({\mathcal {C}})-1}{n \choose j}\leq \left({\frac {ne}{V({\mathcal {C}})-1}}\right)^{V({\mathcal {C}})-1}}$

Que es un número polinómico de subconjuntos en lugar de un número exponencial. Intuitivamente, esto significa que un índice VC finito implica que tiene una estructura aparentemente simplista.${\displaystyle O(n^{V({\mathcal {C}})-1})}$${\displaystyle {\mathcal {C}}}$

Se puede mostrar un límite similar (con una constante diferente, misma tasa) para las llamadas clases de subgrafos VC . Para una función, el subgrafo es un subconjunto de tal que: . Una colección de se denomina clase de subgrafos VC si todos los subgrafos forman una clase VC.${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$${\displaystyle {\mathcal {X}}\times \mathbf {R} }$${\displaystyle \{(x,t):t<f(x)\}}$${\displaystyle {\mathcal {F}}}$

Consideremos un conjunto de funciones indicadoras para un tipo empírico discreto de medida Q (o equivalentemente para cualquier medida de probabilidad Q ). Se puede demostrar entonces que, de manera bastante notable, para :${\displaystyle {\mathcal {I}}_{\mathcal {C}}=\{1_{C}:C\in {\mathcal {C}}\}}$${\displaystyle L_{1}(Q)}$${\displaystyle r\geq 1}$

${\displaystyle N(\varepsilon ,{\mathcal {I}}_{\mathcal {C}},L_{r}(Q))\leq KV({\mathcal {C}})(4e)^{V({\mathcal {C}})}\varepsilon ^{-r(V({\mathcal {C}})-1)}}$

Consideremos además la envoltura convexa simétrica de un conjunto : siendo la colección de funciones de la forma con . Entonces si${\displaystyle {\mathcal {F}}}$${\displaystyle \operatorname {sconv} {\mathcal {F}}}$${\displaystyle \sum _{i=1}^{m}\alpha _{i}f_{i}}$${\displaystyle \sum _{i=1}^{m}|\alpha _{i}|\leq 1}$

${\displaystyle N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)\leq C\varepsilon ^{-V}}$

Lo siguiente es válido para la envoltura convexa de :${\displaystyle {\mathcal {F}}}$

${\displaystyle \log N\left(\varepsilon \|F\|_{Q,2},\operatorname {sconv} {\mathcal {F}},L_{2}(Q)\right)\leq K\varepsilon ^{-{\frac {2V}{V+2}}}}$

La consecuencia importante de este hecho es que

${\displaystyle {\frac {2V}{V+2}}<2,}$

lo cual es suficiente para que la integral de entropía converja, y por lo tanto la clase sea P -Donsker.${\displaystyle \operatorname {sconv} {\mathcal {F}}}$

Finalmente, se considera un ejemplo de una clase de subgrafo VC. Cualquier espacio vectorial de dimensión finita de funciones mensurables es un subgrafo VC de índice menor o igual a .${\displaystyle {\mathcal {F}}}$${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$${\displaystyle \dim({\mathcal {F}})+2}$

Demostración: tomemos los puntos . Los vectores:${\displaystyle n=\dim({\mathcal {F}})+2}$${\displaystyle (x_{1},t_{1}),\ldots ,(x_{n},t_{n})}$

${\displaystyle (f(x_{1}),\ldots ,f(x_{n}))-(t_{1},\ldots ,t_{n})}$

están en un subespacio n − 1 dimensional de R ⁿ . Tome a ≠ 0 , un vector que es ortogonal a este subespacio. Por lo tanto:

${\displaystyle \sum _{a_{i}>0}a_{i}(f(x_{i})-t_{i})=\sum _{a_{i}<0}(-a_{i})(f(x_{i})-t_{i}),\quad \forall f\in {\mathcal {F}}}$

Consideremos el conjunto . Este conjunto no se puede seleccionar porque si existe alguno tal que eso implicaría que el lado izquierdo es estrictamente positivo pero el lado derecho no es positivo.${\displaystyle S=\{(x_{i},t_{i}):a_{i}>0\}}$${\displaystyle f}$${\displaystyle S=\{(x_{i},t_{i}):f(x_{i})>t_{i}\}}$

Existen generalizaciones del concepto de clase de subgrafo VC, por ejemplo, existe el concepto de pseudodimensión. ^[4]

Se considera una configuración similar, que es más común en el aprendizaje automático . Sea un espacio de características y . Una función se denomina clasificador. Sea un conjunto de clasificadores. De manera similar a la sección anterior, defina el coeficiente de fragmentación (también conocido como función de crecimiento):${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {Y}}=\{0,1\}}$${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$${\displaystyle {\mathcal {F}}}$

${\displaystyle S({\mathcal {F}},n)=\max _{x_{1},\ldots ,x_{n}}|\{(f(x_{1}),\ldots ,f(x_{n})),f\in {\mathcal {F}}\}|}$

Nótese aquí que hay una relación 1:1 entre cada una de las funciones en y el conjunto en el que la función es 1. Por lo tanto, podemos definir como la colección de subconjuntos obtenidos a partir de la aplicación anterior para cada . Por lo tanto, en términos de la sección anterior, el coeficiente de fragmentación es precisamente${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle f\in {\mathcal {F}}}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$.

Esta equivalencia junto con el Lema de Sauer implica que va a ser polinomial en n , para n suficientemente grande siempre que la colección tenga un índice VC finito.${\displaystyle S({\mathcal {F}},n)}$${\displaystyle {\mathcal {C}}}$

Sea un conjunto de datos observados. Supongamos que los datos son generados por una distribución de probabilidad desconocida . Definamos como la pérdida esperada 0/1 . Por supuesto, dado que es desconocida en general, no se tiene acceso a . Sin embargo, el riesgo empírico , dado por:${\displaystyle D_{n}=\{(X_{1},Y_{1}),\ldots ,(X_{n},Y_{m})\}}$${\displaystyle P_{XY}}$${\displaystyle R(f)=P(f(X)\neq Y)}$${\displaystyle P_{XY}}$${\displaystyle R(f)}$

${\displaystyle {\hat {R}}_{n}(f)={\dfrac {1}{n}}\sum _{i=1}^{n}\mathbb {I} (f(X_{i})\neq Y_{i})}$

Ciertamente se puede evaluar. Entonces se tiene el siguiente teorema:

Para la clasificación binaria y la función de pérdida 0/1 tenemos los siguientes límites de generalización:

${\displaystyle {\begin{aligned}P\left(\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|>\varepsilon \right)&\leq 8S({\mathcal {F}},n)e^{-n\varepsilon ^{2}/32}\\\mathbb {E} \left[\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|\right]&\leq 2{\sqrt {\dfrac {\log S({\mathcal {F}},n)+\log 2}{n}}}\end{aligned}}}$

En palabras, la desigualdad VC dice que a medida que aumenta la muestra, siempre que tenga una dimensión VC finita, el riesgo empírico 0/1 se convierte en un buen indicador del riesgo 0/1 esperado. Nótese que ambos lados derechos de las dos desigualdades convergerán a 0, siempre que crezca polinómicamente en n .${\displaystyle {\mathcal {F}}}$${\displaystyle S({\mathcal {F}},n)}$

La conexión entre este marco y el marco del proceso empírico es evidente. Aquí se trata de un proceso empírico modificado.

${\displaystyle \left|{\hat {R}}_{n}-R\right|_{\mathcal {F}}}$

Pero no es sorprendente que las ideas sean las mismas. La prueba de la (primera parte de) desigualdad VC se basa en la simetrización y luego se argumenta condicionalmente sobre los datos utilizando desigualdades de concentración (en particular la desigualdad de Hoeffding ). El lector interesado puede consultar el libro ^[5] Teoremas 12.4 y 12.5.

• Ver referencias en los artículos: Richard M. Dudley , Procesos empíricos , Conjunto fragmentado . ^{[ referencia circular ]}
• Bousquet, Olivier; Elisseeff, Andr´e (1 de marzo de 2002). "Estabilidad y generalización". The Journal of Machine Learning Research . 2 : 499–526. doi :10.1162/153244302760200704. S2CID  1157797 . Consultado el 10 de diciembre de 2022 .
• Vapnik, V.; Chervonenkis, A. (2004). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Theory Probab. Appl . 16 (2): 264–280. doi :10.1137/1116025.