La convergencia uniforme en la probabilidad es una forma de convergencia en la probabilidad en la teoría asintótica estadística y la teoría de la probabilidad . Significa que, bajo ciertas condiciones, las frecuencias empíricas de todos los eventos en una cierta familia de eventos convergen a sus probabilidades teóricas . La convergencia uniforme en la probabilidad tiene aplicaciones tanto para la estadística como para el aprendizaje automático como parte de la teoría del aprendizaje estadístico .
La ley de los grandes números dice que, para cada evento individual, su frecuencia empírica en una secuencia de ensayos independientes converge (con alta probabilidad) a su probabilidad teórica. Sin embargo, en muchas aplicaciones surge la necesidad de juzgar simultáneamente las probabilidades de eventos de toda una clase.de una misma muestra. Además, se requiere que la frecuencia relativa de los eventos converja a la probabilidad de manera uniforme en toda la clase de eventos. [1] El teorema de convergencia uniforme proporciona una condición suficiente para que se mantenga esta convergencia. Aproximadamente, si la familia de eventos es suficientemente simple (su dimensión VC es suficientemente pequeña), entonces se mantiene la convergencia uniforme.
Para una clase de predicados definido en un set y un conjunto de muestras , dónde , la frecuencia empírica de en es
La probabilidad teórica de Se define como
El teorema de convergencia uniforme establece, aproximadamente, que si es "simple" y extraemos muestras de forma independiente (con reemplazo) de según cualquier distribución , entonces, con alta probabilidad , la frecuencia empírica estará cerca de su valor esperado , que es la probabilidad teórica. [ cita requerida ]
Aquí "simple" significa que la dimensión Vapnik-Chervonenkis de la clasees pequeño en relación con el tamaño de la muestra. En otras palabras, una colección suficientemente simple de funciones se comporta aproximadamente de la misma manera en una pequeña muestra aleatoria que en la distribución como un todo.
El teorema de convergencia uniforme fue probado por primera vez por Vapnik y Chervonenkis [1] utilizando el concepto de función de crecimiento .
El enunciado del teorema de convergencia uniforme es el siguiente: [2]
Si es un conjunto de -funciones valoradas definidas en un conjunto y es una distribución de probabilidad en entonces para y un entero positivo, tenemos:
- donde, para cualquier ,
- y . indica que se toma el control de la probabilidad que consiste en iid se basa en la distribución .
- se define como: Para cualquier -funciones valoradas encima y ,
Y para cualquier número natural , el número demoledor Se define como:
Desde el punto de vista de la teoría del aprendizaje, uno puede considerar para ser la clase de concepto / hipótesis definida sobre el conjunto de instancias. Antes de entrar en los detalles de la demostración del teorema, enunciaremos el Lema de Sauer que necesitaremos en nuestra demostración.
[1] y [2] son las fuentes de la siguiente prueba. Antes de entrar en los detalles de la demostración del Teorema de convergencia uniforme , presentaremos una descripción general de alto nivel de la demostración.
- Simetrización: Transformamos el problema de analizar en el problema de analizar , dónde y son iid muestras de tamaño dibujado según la distribución . Uno puede ver como la muestra original de longitud extraída al azar , tiempo puede pensarse como la muestra de prueba que se utiliza para estimar .
- Permutación: desde y se seleccionan de forma idéntica e independiente, por lo que intercambiar elementos entre ellos no cambiará la distribución de probabilidad en y . Entonces, intentaremos acotar la probabilidad de para algunos considerando el efecto de una colección específica de permutaciones de la muestra conjunta . Específicamente, consideramos permutaciones cual intercambio y en algún subconjunto de . El símbolo significa la concatenación de y . [ cita requerida ]
- Reducción a una clase finita: ahora podemos restringir la clase de función a una muestra conjunta fija y, por tanto, si tiene una dimensión VC finita, se reduce al problema a uno que involucra una clase de función finita.
Presentamos los detalles técnicos de la prueba.
Simetrización
Lema: dejar y
Entonces para , .
Prueba: por la desigualdad del triángulo,
si y luego .
Por lo tanto,
desde y son independientes.
Ahora para arreglar un tal que . Para esto, mostraremos que
Por lo tanto, para cualquier , y por lo tanto . Y por eso realizamos el primer paso de nuestra idea de alto nivel.
Darse cuenta, es una variable aleatoria binomial con expectativa y varianza . Por la desigualdad de Chebyshev obtenemos
para el mencionado límite en . Aquí usamos el hecho de que por .
Permutaciones
Dejar ser el conjunto de todas las permutaciones de que intercambia y en algún subconjunto de .
Lema: dejar ser cualquier subconjunto de y cualquier distribución de probabilidad en . Luego,
donde la expectativa se acabó elegido de acuerdo a , y la probabilidad ha terminado elegido uniformemente de .
Prueba: para cualquier
(dado que las permutaciones de coordenadas conservan la distribución del producto .)
Se garantiza que existe el máximo ya que solo hay un conjunto finito de valores que la probabilidad bajo una permutación aleatoria puede tomar.
Reducción a una clase finita
Lema: Basándose en el lema anterior,
- .
Prueba: definamos y que es como mucho . Esto significa que hay funciones tal que para cualquier Entre y con por
Vemos eso si para algunos en satisface, . Por tanto, si definimos Si y de lo contrario.
Para y , tenemos eso si para algunos en satisface . Por unión obligada obtenemos
Dado que, la distribución sobre las permutaciones es uniforme para cada , entonces es igual a , con igual probabilidad.
Por lo tanto,
donde la probabilidad de la derecha ha terminado y ambas posibilidades son igualmente probables. Por la desigualdad de Hoeffding , esto es como mucho.
Finalmente, combinando las tres partes de la demostración obtenemos el Teorema de convergencia uniforme .