Estabilidad (teoría del aprendizaje)

Cambio en la precisión de un algoritmo de aprendizaje automático cuando se modifican los datos de entrenamiento

La estabilidad , también conocida como estabilidad algorítmica , es una noción en la teoría del aprendizaje computacional de cómo la salida de un algoritmo de aprendizaje automático cambia con pequeñas perturbaciones en sus entradas. Un algoritmo de aprendizaje estable es aquel cuya predicción no cambia mucho cuando los datos de entrenamiento se modifican ligeramente. Por ejemplo, considere un algoritmo de aprendizaje automático que se está entrenando para reconocer letras del alfabeto escritas a mano, utilizando 1000 ejemplos de letras escritas a mano y sus etiquetas ("A" a "Z") como conjunto de entrenamiento. Una forma de modificar este conjunto de capacitación es omitir un ejemplo, de modo que solo estén disponibles 999 ejemplos de cartas escritas a mano y sus etiquetas. Un algoritmo de aprendizaje estable produciría un clasificador similar con conjuntos de entrenamiento de 1000 elementos y 999 elementos.

La estabilidad se puede estudiar para muchos tipos de problemas de aprendizaje, desde el aprendizaje de idiomas hasta problemas inversos en física e ingeniería, ya que es una propiedad del proceso de aprendizaje más que del tipo de información que se aprende. El estudio de la estabilidad ganó importancia en la teoría del aprendizaje computacional en la década de 2000, cuando se demostró que tenía una conexión con la generalización . ^[1] Se demostró que para grandes clases de algoritmos de aprendizaje, en particular algoritmos empíricos de minimización de riesgos , ciertos tipos de estabilidad garantizan una buena generalización.

Historia

Un objetivo central en el diseño de un sistema de aprendizaje automático es garantizar que el algoritmo de aprendizaje se generalice o funcione con precisión en nuevos ejemplos después de haber sido entrenado en un número finito de ellos. En la década de 1990, se alcanzaron hitos en la obtención de límites de generalización para algoritmos de aprendizaje supervisado . La técnica históricamente utilizada para probar la generalización fue mostrar que un algoritmo era consistente , utilizando las propiedades de convergencia uniforme de las cantidades empíricas con sus medias. Esta técnica se utilizó para obtener límites de generalización para la gran clase de algoritmos empíricos de minimización de riesgos (ERM). Un algoritmo ERM es aquel que selecciona una solución de un espacio de hipótesis de tal manera que minimice el error empírico en un conjunto de entrenamiento . ${\displaystyle H}$ ${\displaystyle S}$

Un resultado general, demostrado por Vladimir Vapnik para algoritmos de clasificación binaria de ERM, es que para cualquier función objetivo y distribución de entrada, cualquier espacio de hipótesis con dimensión VC y ejemplos de entrenamiento, el algoritmo es consistente y producirá un error de entrenamiento que es de la mayoría (más factores logarítmicos) del error verdadero. Posteriormente, el resultado se amplió a algoritmos casi ERM con clases de funciones que no tienen minimizadores únicos. ${\displaystyle H}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle O\left({\sqrt {\frac {d}{n}}}\right)}$

El trabajo de Vapnik, utilizando lo que se conoció como teoría VC , estableció una relación entre la generalización de un algoritmo de aprendizaje y las propiedades del espacio de hipótesis de las funciones que se aprenden. Sin embargo, estos resultados no pudieron aplicarse a algoritmos con espacios de hipótesis de dimensión VC ilimitada. Dicho de otra manera, estos resultados no se podían aplicar cuando la información que se estaba aprendiendo tenía una complejidad demasiado grande para medirla. Algunos de los algoritmos de aprendizaje automático más simples (por ejemplo, para la regresión) tienen espacios de hipótesis con una dimensión VC ilimitada. Otro ejemplo son los algoritmos de aprendizaje de idiomas que pueden producir oraciones de longitud arbitraria. ${\displaystyle H}$

El análisis de estabilidad se desarrolló en la década de 2000 para la teoría del aprendizaje computacional y es un método alternativo para obtener límites de generalización. La estabilidad de un algoritmo es una propiedad del proceso de aprendizaje, más que una propiedad directa del espacio de hipótesis , y puede evaluarse en algoritmos que tienen espacios de hipótesis con una dimensión VC ilimitada o indefinida, como el vecino más cercano. Un algoritmo de aprendizaje estable es aquel en el que la función aprendida no cambia mucho cuando el conjunto de entrenamiento se modifica ligeramente, por ejemplo, omitiendo un ejemplo. Se utiliza una medida del error de dejar uno fuera en un algoritmo de validación cruzada dejar uno fuera (CVloo) para evaluar la estabilidad de un algoritmo de aprendizaje con respecto a la función de pérdida. Como tal, el análisis de estabilidad es la aplicación del análisis de sensibilidad al aprendizaje automático. ${\displaystyle H}$

Resumen de resultados clásicos.

• Principios de 1900 : La estabilidad en la teoría del aprendizaje se describió por primera vez en términos de continuidad del mapa de aprendizaje , atribuido a Andrey Nikolayevich Tikhonov ^{[ cita requerida ]} . ${\displaystyle L}$
• 1979 - Devroye y Wagner observaron que el comportamiento de dejar uno fuera de un algoritmo está relacionado con su sensibilidad a pequeños cambios en la muestra. ^[2]
• 1999 - Kearns y Ron descubrieron una conexión entre la dimensión finita de VC y la estabilidad. ^[3]
• 2002 - En un artículo histórico, Bousquet y Elisseeff propusieron la noción de estabilidad de hipótesis uniforme de un algoritmo de aprendizaje y demostraron que implica un bajo error de generalización. Sin embargo, la estabilidad uniforme de la hipótesis es una condición importante que no se aplica a grandes clases de algoritmos, incluidos los algoritmos ERM con un espacio de hipótesis de sólo dos funciones. ^[4]
• 2002 : Kutin y Niyogi ampliaron los resultados de Bousquet y Elisseeff proporcionando límites de generalización para varias formas más débiles de estabilidad a las que denominaron estabilidad casi en todas partes . Además, dieron un paso inicial para establecer la relación entre estabilidad y consistencia en los algoritmos ERM en el entorno Probablemente Aproximadamente Correcto (PAC). ^[5]
• 2004 - Poggio et al. demostró una relación general entre la estabilidad y la consistencia del ERM. Propusieron una forma estadística de estabilidad de dejar uno fuera a la que llamaron estabilidad CVEEEloo y demostraron que es a) suficiente para la generalización en clases de pérdidas acotadas, y b) necesaria y suficiente para la coherencia (y por tanto la generalización) de los algoritmos ERM. para ciertas funciones de pérdida como la pérdida cuadrada, el valor absoluto y la pérdida de clasificación binaria. ^[6]
• 2010 - Shalev Shwartz et al. Noté problemas con los resultados originales de Vapnik debido a las complejas relaciones entre el espacio de hipótesis y la clase de pérdida. Discuten nociones de estabilidad que capturan diferentes clases de pérdidas y diferentes tipos de aprendizaje, supervisado y no supervisado. ^[7]
• 2016 - Moritz Hardt et al. Estabilidad probada del descenso del gradiente dada cierta suposición sobre la hipótesis y el número de veces que se utiliza cada instancia para actualizar el modelo. ^[8]

Definiciones preliminares

Definimos varios términos relacionados con los conjuntos de entrenamiento de algoritmos de aprendizaje, para luego poder definir la estabilidad de múltiples maneras y presentar teoremas del campo.

Un algoritmo de aprendizaje automático, también conocido como mapa de aprendizaje , asigna un conjunto de datos de entrenamiento, que es un conjunto de ejemplos etiquetados , a una función desde hasta , donde y están en el mismo espacio de los ejemplos de entrenamiento. Las funciones se seleccionan de un espacio de hipótesis de funciones llamado . ${\displaystyle L}$ ${\displaystyle (x,y)}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f}$ ${\displaystyle H}$

El conjunto de entrenamiento del que aprende un algoritmo se define como

${\displaystyle S=\{z_{1}=(x_{1},\ y_{1})\ ,..,\ z_{m}=(x_{m},\ y_{m})\}}$

y es de tamaño en ${\displaystyle m}$ ${\displaystyle Z=X\times Y}$

extraído iid de una distribución desconocida D.

Por lo tanto, el mapa de aprendizaje se define como un mapeo desde adentro , mapeando un conjunto de entrenamiento en una función desde hasta . Aquí, consideramos sólo algoritmos deterministas donde es simétrico con respecto a , es decir, no depende del orden de los elementos en el conjunto de entrenamiento. Además, suponemos que todas las funciones son mensurables y todos los conjuntos son contables. ${\displaystyle L}$ ${\displaystyle Z_{m}}$ ${\displaystyle H}$ ${\displaystyle S}$ ${\displaystyle f_{S}}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle L}$ ${\displaystyle S}$

La pérdida de una hipótesis con respecto a un ejemplo se define entonces como . ${\displaystyle V}$ ${\displaystyle f}$ ${\displaystyle z=(x,y)}$ ${\displaystyle V(f,z)=V(f(x),y)}$

El error empírico de es . ${\displaystyle f}$ ${\displaystyle I_{S}[f]={\frac {1}{n}}\sum V(f,z_{i})}$

El verdadero error es ${\displaystyle f}$ ${\displaystyle I[f]=\mathbb {E} _{z}V(f,z)}$

Dado un conjunto de entrenamiento S de tamaño m, construiremos, para todo i = 1....,m, conjuntos de entrenamiento modificados de la siguiente manera:

• Eliminando el elemento i-ésimo

${\displaystyle S^{|i}=\{z_{1},...,\ z_{i-1},\ z_{i+1},...,\ z_{m}\}}$

• Reemplazando el elemento i-ésimo

${\displaystyle S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i}',\ z_{i+1},...,\ z_{m}\}}$

Definiciones de estabilidad

Estabilidad de hipótesis

Un algoritmo tiene estabilidad de hipótesis β con respecto a la función de pérdida V si se cumple lo siguiente: ${\displaystyle L}$

${\displaystyle \forall i\in \{1,...,m\},\mathbb {E} _{S,z}[|V(f_{S},z)-V(f_{S^{|i}},z)|]\leq \beta .}$

Estabilidad de hipótesis puntual

Un algoritmo tiene estabilidad de hipótesis puntual β con respecto a la función de pérdida V si se cumple lo siguiente: ${\displaystyle L}$

${\displaystyle \forall i\in \ \{1,...,m\},\mathbb {E} _{S}[|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|]\leq \beta .}$

Estabilidad de errores

Un algoritmo tiene estabilidad de error β con respecto a la función de pérdida V si se cumple lo siguiente: ${\displaystyle L}$

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},|\mathbb {E} _{z}[V(f_{S},z)]-\mathbb {E} _{z}[V(f_{S^{|i}},z)]|\leq \beta }$

Estabilidad uniforme

Un algoritmo tiene estabilidad uniforme β con respecto a la función de pérdida V si se cumple lo siguiente: ${\displaystyle L}$

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta }$

Una versión probabilística de estabilidad uniforme β es:

${\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},\mathbb {P} _{S}\{\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta \}\geq 1-\delta }$

Se dice que un algoritmo es estable cuando el valor de disminuye a medida que . ${\displaystyle \beta }$ ${\displaystyle O({\frac {1}{m}})}$

Estabilidad de validación cruzada de dejar uno fuera (CVloo)

Un algoritmo tiene estabilidad CVloo β con respecto a la función de pérdida V si se cumple lo siguiente: ${\displaystyle L}$

${\displaystyle \forall i\in \{1,...,m\},\mathbb {P} _{S}\{|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|\leq \beta _{CV}\}\geq 1-\delta _{CV}}$

La definición de estabilidad (CVloo) es equivalente a la estabilidad de hipótesis puntual vista anteriormente.

Error esperado de dejar uno fuera ( ) Estabilidad mi yo oh oh mi r r {\displaystyle Eloo_{err}}

Un algoritmo tiene estabilidad si para cada n existe a y a tal que: ${\displaystyle L}$ ${\displaystyle Eloo_{err}}$ ${\displaystyle \beta _{EL}^{m}}$ ${\displaystyle \delta _{EL}^{m}}$

${\displaystyle \forall i\in \{1,...,m\},\mathbb {P} _{S}\{|I[f_{S}]-{\frac {1}{m}}\sum _{i=1}^{m}V(f_{S^{|i}},z_{i})|\leq \beta _{EL}^{m}\}\geq 1-\delta _{EL}^{m}}$, con y yendo a cero para ${\displaystyle \beta _{EL}^{m}}$ ${\displaystyle \delta _{EL}^{m}}$ ${\displaystyle m,\rightarrow \infty }$

Teoremas clásicos

De Bousquet y Elisseeff (02) :

Para algoritmos de aprendizaje simétrico con pérdida limitada, si el algoritmo tiene estabilidad uniforme con la definición probabilística anterior, entonces el algoritmo se generaliza.

La estabilidad uniforme es una condición importante que no todos los algoritmos cumplen pero, sorprendentemente, sí la cumplen la gran e importante clase de algoritmos de regularización. El límite de generalización se da en el artículo.

De Mukherjee et al. (06) :

• Para algoritmos de aprendizaje simétrico con pérdida limitada, si el algoritmo tiene estabilidad de validación cruzada de dejar uno fuera (CVloo) y estabilidad de error esperado de dejar uno fuera ( ) como se definió anteriormente, entonces el algoritmo se generaliza. ${\displaystyle Eloo_{err}}$
• Ninguna condición por sí sola es suficiente para la generalización. Sin embargo, ambos juntos garantizan la generalización (aunque lo contrario no es cierto).
• Para los algoritmos ERM específicamente (por ejemplo, para la pérdida cuadrada), la estabilidad de validación cruzada de dejar uno fuera (CVloo) es necesaria y suficiente para lograr coherencia y generalización.

Este es un resultado importante para los fundamentos de la teoría del aprendizaje, porque muestra que dos propiedades de un algoritmo que antes no estaban relacionadas, la estabilidad y la consistencia, son equivalentes para ERM (y ciertas funciones de pérdida). El límite de generalización se da en el artículo.

Algoritmos que son estables

Esta es una lista de algoritmos que han demostrado ser estables y el artículo donde se proporcionan los límites de generalización asociados.

• Regresión lineal ^[9]
• Clasificador k-NN con función de pérdida {0-1}. ^[2]
• Clasificación de máquina vectorial de soporte (SVM) con un kernel acotado y donde el regularizador es una norma en un espacio de Hilbert del kernel de reproducción. Una constante de regularización grande conduce a una buena estabilidad. ^[4] ${\displaystyle C}$
• Clasificación SVM de margen suave. ^[4]
• Regresión de mínimos cuadrados regularizada . ^[4]
• El algoritmo de entropía relativa mínima para la clasificación. ^[4]
• Una versión de regularizadores de embolsado con un número de regresores que aumenta con . ^[10] ${\displaystyle k}$ ${\displaystyle n}$
• Clasificación SVM multiclase. ^[10]
• Todos los algoritmos de aprendizaje con regularización de Tikhonov satisfacen los criterios de Estabilidad Uniforme y, por tanto, son generalizables. ^[11]

Referencias

1. Bousquet, Olivier; Elisseeff, André (2002). "Estabilidad y Generalización". Revista de investigación sobre aprendizaje automático . 2 (marzo): 499–526. ISSN  1533-7928.
2. L. Devroye y Wagner, Límites de rendimiento sin distribución para reglas de funciones potenciales, IEEE Trans. inf. Teoría 25(5) (1979) 601–604.
3. M. Kearns y D. Ron , Estabilidad algorítmica y límites de verificación de cordura para validación cruzada de dejar uno fuera, Neural Comput. 11(6) (1999) 1427–1453.
4. O. Bousquet y A. Elisseeff. Estabilidad y generalización. J. Mach. Aprender. Res., 2:499–526, 2002.
5. S. Kutin y P. Niyogi, Error de generalización y estabilidad algorítmica en casi todas partes, Informe técnico TR-2002-03, Universidad de Chicago (2002).
6. S. Mukherjee, P. Niyogi, T. Poggio y RM Rifkin. Teoría del aprendizaje: la estabilidad es suficiente para la generalización y necesaria y suficiente para la coherencia de la minimización empírica del riesgo. Adv. Computadora. Matemáticas, 25(1-3):161–193, 2006.
7. Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Capacidad de aprendizaje, estabilidad y convergencia uniforme, Journal of Machine Learning Research, 11 (octubre): 2635-2670, 2010.
8. Moritz Hardt, Benjamin Recht, Yoram Singer, Entrene más rápido, generalice mejor: estabilidad del descenso de gradiente estocástico, ICML 2016.
9. Elisseeff, A. Un estudio sobre la estabilidad algorítmica y su relación con las actuaciones de generalización. Reporte técnico. (2000)
10. Rifkin, R. Todo lo viejo es nuevo otra vez: una nueva mirada a los enfoques históricos del aprendizaje automático. Doctor. Tesis, MIT, 2002
11. Rosasco, L. y Poggio, T. Estabilidad de la regularización de Tikhonov, 2009

Otras lecturas

• S.Kutin y P.Niyogi. Estabilidad algorítmica en casi todas partes y error de generalización. En Proc. de la AUI 18 de 2002
• S. Rakhlin, S. Mukherjee y T. Poggio. La estabilidad resulta en la teoría del aprendizaje. Análisis y aplicaciones, 3(4):397–419, 2005
• VN Vapnik. La naturaleza de la teoría del aprendizaje estadístico. Saltador, 1995
• Vapnik, V., Teoría del aprendizaje estadístico. Wiley, Nueva York, 1998
• Poggio, T., Rifkin, R., Mukherjee, S. y Niyogi, P., "Teoría del aprendizaje: condiciones generales para la predictividad", Nature, vol. 428, 419-422, 2004
• Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, Estabilidad de los algoritmos de aprendizaje aleatorio, Journal of Machine Learning Research 6, 55–79, 2010
• Elisseeff, A. Pontil, M., Error de exclusión y estabilidad de los algoritmos de aprendizaje con aplicaciones, SERIE DE CIENCIA DE LA OTAN SUB SERIE III CIENCIAS DE SISTEMAS Y COMPUTADORAS, 2003, VOL 190, páginas 111-130
• Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Capacidad de aprendizaje, estabilidad y convergencia uniforme, Journal of Machine Learning Research, 11 (octubre): 2635-2670, 2010