Estabilidad (teoría del aprendizaje)

La estabilidad , también conocida como estabilidad algorítmica , es una noción en la teoría del aprendizaje computacional que se refiere a cómo se modifica la salida de un algoritmo de aprendizaje automático con pequeñas perturbaciones en sus entradas. Un algoritmo de aprendizaje estable es aquel en el que la predicción no cambia mucho cuando se modifican ligeramente los datos de entrenamiento. 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 entrenamiento es omitir un ejemplo, de modo que solo estén disponibles 999 ejemplos de letras escritas a mano y sus etiquetas. Un algoritmo de aprendizaje estable produciría un clasificador similar 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 en lugar 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 de minimización de riesgos empíricos , ciertos tipos de estabilidad garantizan una buena generalización.

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 ser 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 era mostrar que un algoritmo era consistente , utilizando las propiedades de convergencia uniforme de las cantidades empíricas para sus medias. Esta técnica se utilizó para obtener límites de generalización para la gran clase de algoritmos de minimización de riesgo empírico (ERM). Un algoritmo ERM es uno que selecciona una solución de un espacio de hipótesis de tal manera que minimiza el error empírico en un conjunto de entrenamiento . ${\estilo de visualización H}$${\estilo de visualización S}$

Un resultado general, demostrado por Vladimir Vapnik para algoritmos de clasificación binaria ERM, es que para cualquier función de destino 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 se aleja como máximo (más factores logarítmicos) del error verdadero. El resultado se extendió posteriormente a algoritmos casi ERM con clases de funciones que no tienen minimizadores únicos. ${\estilo de visualización H}$ ${\estilo de visualización d}$${\estilo de visualización n}$${\displaystyle O\left({\sqrt {\frac {d}{n}}}\right)}$

El trabajo de Vapnik, que utilizó 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 están aprendiendo. Sin embargo, estos resultados no se podían aplicar a algoritmos con espacios de hipótesis de dimensión VC ilimitada. Dicho de otro modo, 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 regresión) tienen espacios de hipótesis con dimensión VC ilimitada. Otro ejemplo son los algoritmos de aprendizaje de idiomas que pueden producir oraciones de longitud arbitraria. ${\estilo de visualización 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, en lugar de una propiedad directa del espacio de hipótesis , y se puede evaluar en algoritmos que tienen espacios de hipótesis con dimensión VC ilimitada o indefinida, como el vecino más cercano. Un algoritmo de aprendizaje estable es uno para el cual la función aprendida no cambia mucho cuando el conjunto de entrenamiento se modifica ligeramente, por ejemplo, al omitir un ejemplo. Una medida del error de dejar uno fuera se utiliza en un algoritmo de validación cruzada de 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. ${\estilo de visualización H}$

• 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 , cuyo origen se remonta a Andrey Nikolayevich Tikhonov ^{[ cita requerida ]} .${\estilo de visualización 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 VC finita y la estabilidad. ^[3]
• 2002 - En un artículo de referencia, Bousquet y Elisseeff propusieron la noción de estabilidad uniforme de hipótesis de un algoritmo de aprendizaje y demostraron que implica un error de generalización bajo. Sin embargo, la estabilidad uniforme de hipótesis es una condición sólida que no se aplica a grandes clases de algoritmos, incluidos los algoritmos ERM con un espacio de hipótesis de solo 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 algoritmos ERM en el contexto Probablemente Aproximadamente Correcto (PAC). ^[5]
• 2004 - Poggio et al. demostraron una relación general entre la estabilidad y la consistencia de ERM. Propusieron una forma estadística de estabilidad de tipo leave-one-out que llamaron estabilidad CVEEEloo y demostraron que es a) suficiente para la generalización en clases de pérdida acotadas y b) necesaria y suficiente para la consistencia (y por lo tanto la generalización) de los algoritmos ERM para ciertas funciones de pérdida como la pérdida al cuadrado, el valor absoluto y la pérdida de clasificación binaria. ^[6]
• 2010 - Shalev Shwartz et al. notaron problemas con los resultados originales de Vapnik debido a las relaciones complejas entre el espacio de hipótesis y la clase de pérdida. Analizan nociones de estabilidad que capturan diferentes clases de pérdida y diferentes tipos de aprendizaje, supervisado y no supervisado. ^[7]
• 2016 - Moritz Hardt et al. demostraron la estabilidad del descenso del gradiente dadas ciertas suposiciones sobre la hipótesis y el número de veces que se utiliza cada instancia para actualizar el modelo. ^[8]

Definimos varios términos relacionados con los conjuntos de entrenamiento de algoritmos de aprendizaje, para que luego podamos 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 de a , 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 . ${\estilo de visualización L}$${\estilo de visualización (x,y)}$${\estilo de visualización f}$${\estilo de visualización X}$${\estilo de visualización Y}$${\estilo de visualización X}$${\estilo de visualización Y}$${\estilo de visualización f}$${\estilo de visualización 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${\estilo de visualización m}$${\displaystyle Z=X\veces Y}$

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

Por lo tanto, el mapa de aprendizaje se define como una asignación de en , que asigna un conjunto de entrenamiento a una función de en . Aquí, solo consideramos 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, asumimos que todas las funciones son mensurables y todos los conjuntos son contables. ${\estilo de visualización L}$$Estilo de visualización Z_ {m}}$${\estilo de visualización H}$${\estilo de visualización S}$$estilo de visualización f_{S}}$${\estilo de visualización X}$${\estilo de visualización Y}$${\estilo de visualización L}$${\estilo de visualización S}$

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

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

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

Dado un conjunto de entrenamiento S de tamaño m, construiremos, para todos los 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_{ metro}\}}$

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

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

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

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

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

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

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

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

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

${\displaystyle \para todo S\en Z^{m},\para todo i\en \{1,...,m\},\mathbb {P} _{S}\{\sup _{z\en 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 . ${\estilo de visualización \beta}$${\displaystyle O({\frac {1}{m}})}$

Un algoritmo tiene estabilidad CVloo β con respecto a la función de pérdida V si se cumple lo siguiente: ${\estilo de visualización 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.

Un algoritmo tiene estabilidad si para cada n existen a y a tales que: ${\estilo de visualización 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 }$

De Bousquet y Elisseeff (02) :

Para los 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 se cumple en todos los algoritmos, pero que, sorprendentemente, se cumple en la amplia e importante clase de algoritmos de regularización. El límite de generalización se proporciona en el artículo.

De Mukherjee et al. (06) :

• Para los 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, ambas condiciones juntas garantizan la generalización (mientras que lo inverso no es cierto).
• Específicamente para los algoritmos ERM (por ejemplo, para la pérdida al cuadrado), la validación cruzada de dejar uno afuera (CVloo) La estabilidad es necesaria y suficiente para la consistencia y la generalización.

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

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 una función de pérdida {0-1}. ^[2]
• Clasificación por máquina de vectores de soporte (SVM) con un núcleo acotado y donde el regularizador es una norma en un espacio de Hilbert de núcleo reproductor. Una constante de regularización grande conduce a una buena estabilidad. ^[4]${\estilo de visualización C}$
• Clasificación SVM de margen blando. ^[4]
• Regresión de mínimos cuadrados regularizados . ^[4]
• El algoritmo de entropía relativa mínima para la clasificación. ^[4]
• Una versión de regularizadores de bagging con el número de regresores aumentando con . ^[10]${\estilo de visualización k}$${\estilo de visualización n}$
• Clasificación SVM multiclase. ^[10]
• Todos los algoritmos de aprendizaje con regularización de Tikhonov satisfacen los criterios de estabilidad uniforme y, por lo tanto, son generalizables. ^[11]