La teoría de Vapnik-Chervonenkis (también conocida como teoría de VC ) fue desarrollada durante 1960-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 CV está relacionada con la teoría del aprendizaje estadístico y con los procesos empíricos . Richard M. Dudley y Vladimir Vapnik , entre otros, han aplicado la teoría de CV a procesos empíricos .
Introducción
La teoría de VC cubre al menos cuatro partes (como se explica en The Nature of Statistical Learning Theory [1] ):
- Teoría de la consistencia de los procesos de aprendizaje
- ¿Cuáles son las condiciones (necesarias y suficientes) para la coherencia 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ápido 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 de 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 de CV se relaciona con la estabilidad , que es un enfoque alternativo para caracterizar la generalización.
Además, la teoría de VC y la dimensión de VC son instrumentales en la teoría de procesos empíricos , en el caso de procesos indexados por clases de VC. Podría decirse que estas son las aplicaciones más importantes de la teoría de VC y se emplean para demostrar la generalización. Se introducirán varias técnicas que se utilizan ampliamente en el proceso empírico y la teoría de CV. La discusión se basa principalmente en el libro Weak Convergence and Empirical Processes: With Applications to Statistics . [2]
Descripción general de la teoría de VC en procesos empíricos
Antecedentes de los procesos empíricos
Dejar Ser elementos aleatorios definidos en un espacio medible. . Para cualquier medida en , y cualquier función medible , definir
Los problemas de mensurabilidad se ignorarán aquí, para obtener más detalles técnicos, consulte [3] . Dejar ser una clase de funciones medibles y definir:
Definir la medida empírica
donde δ aquí representa la medida de Dirac . La medida empírica induce un mapa dada por:
Ahora suponga que P es la verdadera distribución subyacente de los datos, que se desconoce. La teoría de los procesos empíricos tiene como objetivo identificar clases para lo cual se cumplen afirmaciones como las siguientes:
- ley uniforme de grandes números :
- Es decir, como ,
- uniformemente para todos .
- teorema del límite central uniforme :
En el primer caso se llama clase Glivenko-Cantelli , y en el último caso (bajo el supuesto) la clase se llama Donsker o P -Donsker. Una clase de Donsker es Glivenko-Cantelli en probabilidad mediante una aplicación del teorema de Slutsky .
Estas afirmaciones son verdaderas para un solo , según los argumentos estándar LLN , CLT en condiciones de regularidad, y la dificultad en los procesos empíricos viene porque se están haciendo declaraciones conjuntas para todos. Entonces, intuitivamente, el conjunto no puede ser demasiado grande, y resulta que la geometría de juega un papel muy importante.
Una forma de medir el tamaño del conjunto de funciones es utilizar los llamados números de cobertura . El número de cobertura
es el número mínimo de bolas necesario para cubrir el conjunto (aquí se asume obviamente que existe una norma subyacente sobre ). La entropía es el logaritmo del número de cobertura.
A continuación se proporcionan dos condiciones suficientes, bajo las cuales se puede probar que el conjunto es Glivenko-Cantelli o Donsker.
Una clase es P -Glivenko-Cantelli si es P -medible con envolvente F tal que y satisface:
La siguiente condición es una versión del célebre teorema de Dudley . Si es una clase de funciones tales que
luego es P -Donsker para cada medida de probabilidad P tal que. En la última integral, la notación significa
- .
Simetrización
La mayoría de los argumentos sobre cómo unir 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 pruebas y, dado que se utiliza en muchas pruebas de aprendizaje automático sobre funciones de pérdida empírica delimitadas (incluida la prueba de la desigualdad de VC que se analiza en la siguiente sección), se presenta aquí.
Considere el proceso empírico:
Resulta que hay una conexión entre lo empírico y el siguiente proceso simétrizado:
El proceso simétrizado es un proceso de Rademacher , condicionalmente en los datos. Por tanto, es un proceso subgaussiano por la desigualdad de Hoeffding .
Lema (simetrización). Para cada no decreciente, convexo Φ: R → R y clase de funciones medibles,
La prueba del lema de simetrización se basa en la introducción de copias independientes de las variables originales. (a veces denominado muestra fantasma ) y reemplazando la expectativa 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 expectativa. La prueba se puede encontrar a continuación debido a su naturaleza instructiva.
Presentar la "muestra fantasma" ser copias independientes de . Para valores fijos de uno tiene:
Por tanto, por la desigualdad de Jensen :
Teniendo expectativa con respecto a da:
Tenga en cuenta que agregar un signo menos delante de un término no cambia el RHS, porque es una función simétrica de y . Por lo tanto, el RHS sigue siendo el mismo bajo "señal de perturbación":
para cualquier . Por lo tanto:
Finalmente, usando la desigualdad del primer triángulo y luego la convexidad de da:
Donde las dos últimas expresiones en el RHS son iguales, que concluye la demostración.
Una forma típica de probar CLT empíricos, primero utiliza la simetrización para pasar el proceso empírico a y luego argumentar condicionalmente sobre los datos, utilizando el hecho de que los procesos de Rademacher son procesos simples con buenas propiedades.
Conexión VC
Resulta que existe una conexión fascinante entre ciertas propiedades combinatorias del conjunto y los números de entropía. Los números de cobertura uniformes se pueden controlar mediante la noción de clases de conjuntos de Vapnik-Chervonenkis , o en breve, conjuntos de VC .
Considere una colección de subconjuntos del espacio muestral . se dice que elige un determinado subconjunto del conjunto finito Si para algunos . se dice que rompe S si selecciona cada uno de sus 2 n subconjuntos. El índice VC (similar a la dimensión VC + 1 para un conjunto de clasificadores elegido apropiadamente) de es el n más pequeño para el cual ningún conjunto de tamaño n se rompe por.
El lema de Sauer luego establece que el número de subconjuntos seleccionados por una clase VC satisface:
Que es un polinomio de subconjuntos en lugar de un número exponencial. Intuitivamente, esto significa que un índice VC finito implica que tiene una estructura aparentemente simplista.
Se puede mostrar un límite similar (con una constante diferente, la misma tasa) para las llamadas clases de subgrafo de VC . Para una funciónel subgrafo es un subconjunto de tal que: . Una coleccion de se llama una clase de subgrafo VC si todos los subgrafos forman una clase VC.
Considere un conjunto de funciones de indicador en para el tipo de medida empírica discreta Q (o equivalentemente para cualquier medida de probabilidad Q ). Entonces se puede demostrar que de manera bastante notable, para:
Considere además el casco convexo simétrico de un conjunto: siendo la colección de funciones de la forma con . Entonces sí
lo siguiente es válido para el casco convexo de :
La consecuencia importante de este hecho es que
que es suficiente para que la integral de entropía converja, y por lo tanto la clase va a ser P -Donsker.
Finalmente, se considera un ejemplo de una clase de subgrafo VC. Cualquier espacio vectorial de dimensión finita de funciones medibles es el subgrafo VC del índice menor o igual que .
Llevar puntos . Los vectores:
están en un subespacio dimensional n - 1 de R n . Tome un ≠ 0 , un vector que es ortogonal a este subespacio. Por lo tanto:
Considere el conjunto . Este conjunto no se puede seleccionar ya que si hay alguna tal que eso implicaría que el LHS es estrictamente positivo pero el RHS no es positivo.
Hay generalizaciones de la noción de clase de subgrafo VC, por ejemplo, existe la noción de pseudo-dimensión. El lector interesado puede consultar [4] .
Desigualdad de VC
Se considera una configuración similar, que es más común en el aprendizaje automático . Dejar es un espacio de características y . Una funciónse llama clasificador. Dejarser un conjunto de clasificadores. De manera similar a la sección anterior, defina el coeficiente de rotura (también conocido como función de crecimiento):
Tenga en cuenta aquí que hay un intervalo de 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 para ser la colección de subconjuntos obtenidos del mapeo anterior para cada . Por lo tanto, en términos de la sección anterior, el coeficiente de rotura es precisamente
- .
Esta equivalencia junto con el Lema de Sauer implica queva a ser polinomio en n , para n suficientemente grande siempre que la colección tiene un índice VC finito.
Dejar es un conjunto de datos observado. Suponga que los datos son generados por una distribución de probabilidad desconocida.. Definirpara ser la pérdida 0/1 esperada . Por supuesto desde es desconocido en general, no se tiene acceso a . Sin embargo, el riesgo empírico , dado por:
ciertamente puede ser evaluado. Entonces uno tiene el siguiente teorema:
Teorema (desigualdad de CV)
Para la clasificación binaria y la función de pérdida 0/1 tenemos los siguientes límites de generalización:
En palabras, la desigualdad de VC dice que a medida que aumenta la muestra, siempre que tiene una dimensión VC finita, el riesgo 0/1 empírico se convierte en un buen indicador del riesgo 0/1 esperado. Tenga en cuenta que ambos RHS de las dos desigualdades convergerán a 0, siempre quecrece polinomialmente en 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
pero no sorprende que las ideas sean las mismas. La prueba de la (primera parte de) la desigualdad de VC se basa en la simetrización y luego argumenta condicionalmente en 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.
Referencias
- ^ Vapnik, Vladimir N (2000). La naturaleza de la teoría del aprendizaje estadístico . Ciencias de la información y estadística. Springer-Verlag . ISBN 978-0-387-98780-4.
- Vapnik, Vladimir N (1989).Teoría del aprendizaje estadístico. Wiley-Interscience . ISBN 978-0-471-03003-4.
- ^van der Vaart, Aad W .; Wellner, Jon A. (2000). Convergencia débil y procesos empíricos: con aplicaciones a la estadística (2ª ed.). Saltador. ISBN 978-0-387-94640-5.
- ^Gyorfi, L .; Devroye, L .; Lugosi, G. (1996). Una teoría probabilística del reconocimiento de patrones (1ª ed.). Saltador. ISBN 978-0387946184.
- Véanse las referencias en los artículos: Richard M. Dudley , procesos empíricos , Conjunto destrozado .
- ^Pollard, David (1990). Procesos empíricos: teoría y aplicaciones. Serie de conferencias regionales NSF-CBMS sobre probabilidad y estadística Volumen 2. ISBN 978-0-940600-16-4.
- Bousquet, O .; Boucheron, S .; Lugosi, G. (2004). "Introducción a la teoría del aprendizaje estadístico". En O. Bousquet; U. von Luxburg; G. Ratsch (eds.). Conferencias avanzadas sobre aprendizaje automático . Apuntes de conferencias en Inteligencia Artificial. 3176 . Saltador. págs. 169–207.
- Vapnik, V .; Chervonenkis, A. (2004). "Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades". Teoría Probab. Apl . 16 (2): 264–280. doi : 10.1137 / 1116025 .