La estabilidad , también conocida como estabilidad algorítmica , es una noción en la teoría del aprendizaje computacional de cómo un algoritmo de aprendizaje automático se ve perturbado por pequeños cambios en sus entradas. Un algoritmo de aprendizaje estable es aquel en el que la predicción no cambia mucho cuando los datos de entrenamiento se modifican ligeramente. Por ejemplo, considere un algoritmo de aprendizaje automático que está siendo entrenado para reconocer letras del alfabeto escritas a mano , usando 1000 ejemplos de letras escritas a mano y sus etiquetas ("A" a "Z") como un 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 unclasificador con los 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 [ cita requerida ] . Se demostró que para grandes clases de algoritmos de aprendizaje, en particular los 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 utilizada históricamente para probar la generalización fue mostrar que un algoritmo era consistente , usando las propiedades de convergencia uniforme de las cantidades empíricas en sus medias. Esta técnica se utilizó para obtener límites de generalización para la gran clase de algoritmos de minimización de riesgos empíricos (ERM). Un algoritmo ERM es aquel que selecciona una solución de un espacio de hipótesis. de tal manera que se minimice el error empírico en un conjunto de entrenamiento .
Un resultado general, probado por Vladimir Vapnik para un algoritmo de clasificación binaria ERM, es que para cualquier función objetivo y distribución de entrada, cualquier espacio de hipótesiscon dimensión VC , y ejemplos de entrenamiento, el algoritmo es consistente y producirá un error de entrenamiento que es como máximo (más factores logarítmicos) del error verdadero. El resultado se extendió posteriormente a casi algoritmos ERM con clases de función que no tienen minimizadores únicos.
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 funciones que se aprenden. Sin embargo, estos resultados no se pudieron aplicar a algoritmos con espacios de hipótesis de dimensión VC ilimitada. Dicho de otra manera, estos resultados no se pueden aplicar cuando la información que se está aprendiendo tiene una complejidad demasiado grande para medir. Algunos de los algoritmos de aprendizaje automático más simples, por ejemplo, para la regresión, tienen espacios de hipótesis con dimensión de VC ilimitada. Otro ejemplo son los algoritmos de aprendizaje de idiomas que pueden producir oraciones de longitud arbitraria.
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 se puede evaluar en algoritmos que tienen espacios de hipótesis con dimensión de VC ilimitada o indefinida, como el vecino más cercano. Un algoritmo de aprendizaje estable es aquel para el que la función aprendida no cambia mucho cuando el conjunto de entrenamiento se modifica ligeramente, por ejemplo, al omitir un ejemplo. Se utiliza una medida del error 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.
Resumen de resultados clásicos
- Principios del siglo XX : la estabilidad en la teoría del aprendizaje se describió por primera vez en términos de continuidad del mapa de aprendizaje., rastreada hasta Andrey Nikolayevich Tikhonov [ cita requerida ] .
- 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. [1]
- 1999 - Kearns y Ron descubrieron una conexión entre la dimensión VC finita y la estabilidad. [2]
- 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 error de generalización bajo. La estabilidad de hipótesis uniforme, sin embargo, es una condición fuerte que no se aplica a grandes clases de algoritmos, incluidos los algoritmos ERM con un espacio de hipótesis de solo dos funciones. [3]
- 2002 - Kutin y Niyogi ampliaron los resultados de Bousquet y Elisseeff al proporcionar límites de generalización para varias formas más débiles de estabilidad a las que llamaron estabilidad casi en todas partes . Además, dieron un paso inicial para establecer la relación entre estabilidad y consistencia en los algoritmos de ERM en la configuración Probablemente Aproximadamente Correcta (PAC). [4]
- 2004 - Poggio et al. demostró una relación general entre estabilidad y consistencia 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 limitadas, yb) necesaria y suficiente para la coherencia (y, por lo tanto, la generalización) de los algoritmos ERM. para determinadas funciones de pérdida, como la pérdida cuadrada, el valor absoluto y la pérdida de clasificación binaria. [5]
- 2010 - Shalev Shwartz 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 las nociones de estabilidad que capturan diferentes clases de pérdidas y diferentes tipos de aprendizaje, supervisado y no supervisado. [6]
Definiciones preliminares
Definimos varios términos relacionados con los conjuntos de entrenamiento de algoritmos de aprendizaje, de modo que luego podamos definir la estabilidad de múltiples formas y presentar teoremas del campo.
Un algoritmo de aprendizaje automático, también conocido como mapa de aprendizaje. , mapea un conjunto de datos de entrenamiento, que es un conjunto de ejemplos etiquetados , en una función de a , dónde y están en el mismo espacio de los ejemplos de formación. Las funciones se seleccionan de un espacio de hipótesis de funciones llamado .
El conjunto de entrenamiento del que aprende un algoritmo se define como
y es de tamaño en
extraído de una distribución desconocida D.
Por tanto, el mapa de aprendizaje se define como un mapeo de dentro , mapeando un conjunto de entrenamiento en una función de a . Aquí, consideramos solo algoritmos deterministas donde es simétrico con respecto a , es decir, no depende del orden de los elementos del conjunto de entrenamiento. Además, asumimos que todas las funciones son medibles y todos los conjuntos son contables.
La pérdida de una hipótesis con respecto a un ejemplo entonces se define como .
El error empírico de es .
El verdadero error de es
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 i-ésimo elemento
- Reemplazando el i-ésimo elemento
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:
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:
Estabilidad de error
Un algoritmo tiene estabilidad de error β con respecto a la función de pérdida V si se cumple lo siguiente:
Estabilidad uniforme
Un algoritmo tiene una estabilidad uniforme β con respecto a la función de pérdida V si se cumple lo siguiente:
Una versión probabilística de estabilidad uniforme β es:
Se dice que un algoritmo es estable , cuando el valor de disminuye a medida que .
Estabilidad de validación cruzada de dejar uno fuera (CVloo)
Un algoritmo tiene CVloo estabilidad β con respecto a la función de pérdida V si se cumple lo siguiente:
La definición de estabilidad (CVloo) es equivalente a la estabilidad de la hipótesis puntual vista anteriormente.
Error esperado de dejar uno fuera () Estabilidad
Un algoritmo posee estabilidad si para cada n existe una y un tal que:
, con y yendo a cero para
Teoremas clásicos
Desde 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, el algoritmo se generaliza.
La estabilidad uniforme es una condición importante que no todos los algoritmos cumplen, pero que, 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 los algoritmos de aprendizaje simétricas con pérdida acotada, si el algoritmo tiene tanto Dejar fuera de una validación cruzada (CVloo) Estabilidad y licencia-un-out-esperada de error () Estabilidad como se define arriba, luego el algoritmo se generaliza.
- Ninguna condición por sí sola es suficiente para la generalización. Sin embargo, ambos juntos garantizan la generalización (mientras que lo contrario no es cierto).
- Para los algoritmos ERM específicamente (por ejemplo, para la pérdida de cuadrado), la estabilidad de validación cruzada de dejar uno fuera (CVloo) es necesaria y suficiente para la coherencia y la generalización.
Este es un resultado importante para los fundamentos de la teoría del aprendizaje, porque muestra que dos propiedades previamente no relacionadas de un algoritmo, 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 [7]
- Clasificador k-NN con función de pérdida {0-1}. [8]
- Admite la clasificación de máquina vectorial (SVM) con un kernel acotado y donde el regularizador es una norma en un espacio de Hilbert del kernel de reproducción. Una gran constante de regularizaciónconduce a una buena estabilidad. [9]
- Clasificación SVM de margen suave. [10]
- Regresión de mínimos cuadrados regularizados . [11]
- El algoritmo de entropía relativa mínima para la clasificación. [12]
- Una versión de los regularizadores de ensacado con el número de regresores aumentando con . [13]
- Clasificación SVM de clases múltiples. [14]
- Todos los algoritmos de aprendizaje con regularización de Tikhonov satisfacen los criterios de estabilidad uniforme y, por lo tanto, son generalizables. [15]
Referencias
- ^ L. Devroye y Wagner, Límites de rendimiento sin distribución para reglas de función potencial, IEEE Trans. Inf. Teoría 25 (5) (1979) 601-604.
- ^ M. Kearns y D. Ron , Estabilidad algorítmica y límites de comprobación de cordura para la validación cruzada de dejar uno fuera, Neural Comput. 11 (6) (1999) 1427–1453.
- ^ O. Bousquet y A. Elisseeff. Estabilidad y generalización. J. Mach. Aprender. Res., 2: 499–526, 2002.
- ^ 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).
- ^ 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 del riesgo empírico. Adv. Computación. Math., 25 (1-3): 161-193, 2006.
- ^ Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Aprendizaje, estabilidad y convergencia uniforme, Journal of Machine Learning Research, 11 (octubre): 2635-2670, 2010.
- ^ Elisseeff, A. Un estudio sobre la estabilidad algorítmica y su relación con los rendimientos de generalización. Reporte técnico. (2000)
- ^ L. Devroye y Wagner, Límites de rendimiento sin distribución para reglas de función potencial, IEEE Trans. Inf. Teoría 25 (5) (1979) 601-604.
- ^ O. Bousquet y A. Elisseeff. Estabilidad y generalización. J. Mach. Aprender. Res., 2: 499–526, 2002.
- ^ O. Bousquet y A. Elisseeff. Estabilidad y generalización. J. Mach. Aprender. Res., 2: 499–526, 2002.
- ^ O. Bousquet y A. Elisseeff. Estabilidad y generalización. J. Mach. Aprender. Res., 2: 499–526, 2002.
- ^ O. Bousquet y A. Elisseeff. Estabilidad y generalización. J. Mach. Aprender. Res., 2: 499–526, 2002.
- ^ Rifkin, R. Everything Old is New Again: Una nueva mirada a los enfoques históricos en el aprendizaje automático. Doctor. Tesis, MIT, 2002
- ^ Rifkin, R. Everything Old is New Again: Una nueva mirada a los enfoques históricos en el aprendizaje automático. Doctor. Tesis, MIT, 2002
- ^ http://www.mit.edu/~9.520/spring09/Classes/class10_stability.pdf
Otras lecturas
- S. Kutin y P.Niyogi: error de generalización y estabilidad algorítmica en casi todas partes. En Proc. de la AUI 18, 2002
- S. Rakhlin, S. Mukherjee y T. Poggio. La estabilidad da como resultado 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. Springer, 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, Stability of Randomized Learning Algorithms, 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, NATO SCIENCE SERIES SUB SERIES III COMPUTER AND SYSTEMS SCIENCES, 2003, VOL 190, páginas 111-130
- Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Aprendizaje, estabilidad y convergencia uniforme, Journal of Machine Learning Research, 11 (octubre): 2635-2670, 2010