Parada temprana

Método en el aprendizaje automático

En el aprendizaje automático , la detención temprana es una forma de regularización que se utiliza para evitar el sobreajuste al entrenar a un alumno con un método iterativo, como el descenso de gradiente . Dichos métodos actualizan al alumno para que se ajuste mejor a los datos de entrenamiento con cada iteración. Hasta cierto punto, esto mejora el rendimiento del alumno en datos fuera del conjunto de entrenamiento. Sin embargo, más allá de ese punto, mejorar el ajuste del alumno a los datos de entrenamiento se produce a expensas de un mayor error de generalización . Las reglas de detención temprana proporcionan una guía sobre cuántas iteraciones se pueden ejecutar antes de que el alumno comience a sobreajustarse. Las reglas de detención temprana se han empleado en muchos métodos de aprendizaje automático diferentes, con diferentes cantidades de fundamento teórico.

Fondo

En esta sección se presentan algunos de los conceptos básicos de aprendizaje automático necesarios para describir los métodos de detención temprana.

Sobreajuste

Figura 1. La línea verde representa un modelo sobreajustado y la línea negra representa un modelo regularizado. Si bien la línea verde sigue mejor los datos de entrenamiento, depende demasiado de ellos y es probable que tenga una tasa de error más alta en los datos nuevos no vistos, ilustrados por puntos delineados en negro, en comparación con la línea negra.

Los algoritmos de aprendizaje automático entrenan un modelo basándose en un conjunto finito de datos de entrenamiento. Durante este entrenamiento, el modelo se evalúa en función de lo bien que predice las observaciones contenidas en el conjunto de entrenamiento. Sin embargo, en general, el objetivo de un esquema de aprendizaje automático es producir un modelo que generalice, es decir, que prediga observaciones no vistas previamente. El sobreajuste se produce cuando un modelo se ajusta bien a los datos del conjunto de entrenamiento, pero incurre en un error de generalización mayor .

Regularización

La regularización, en el contexto del aprendizaje automático, se refiere al proceso de modificación de un algoritmo de aprendizaje para evitar el sobreajuste. Esto generalmente implica imponer algún tipo de restricción de suavidad en el modelo aprendido. ^[1] Esta suavidad se puede aplicar explícitamente, fijando el número de parámetros en el modelo o aumentando la función de costo como en la regularización de Tikhonov . La regularización de Tikhonov, junto con la regresión de componentes principales y muchos otros esquemas de regularización, se incluyen en el ámbito de la regularización espectral, regularización caracterizada por la aplicación de un filtro. La detención temprana también pertenece a esta clase de métodos.

Métodos de descenso de gradiente

Los métodos de descenso de gradiente son métodos de optimización iterativos de primer orden. Cada iteración actualiza una solución aproximada al problema de optimización dando un paso en la dirección del negativo del gradiente de la función objetivo. Al elegir el tamaño del paso de manera adecuada, se puede lograr que un método de este tipo converja a un mínimo local de la función objetivo. El descenso de gradiente se utiliza en el aprendizaje automático al definir una función de pérdida que refleja el error del alumno en el conjunto de entrenamiento y luego minimizar esa función.

Parada anticipada basada en resultados analíticos

Parada temprana enteoría del aprendizaje estadístico

La detención temprana se puede utilizar para regularizar los problemas de regresión no paramétrica que se encuentran en el aprendizaje automático . Para un espacio de entrada dado, , un espacio de salida, , y muestras extraídas de una medida de probabilidad desconocida, , en , el objetivo de dichos problemas es aproximar una función de regresión , , dada por ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle \rho }$ ${\displaystyle Z=X\times Y}$ ${\displaystyle f_{\rho }}$

${\displaystyle f_{\rho }(x)=\int _{Y}y\,d\rho (y\mid x),\,x\in X,}$

donde es la distribución condicional en inducida por . ^[2] Una opción común para aproximar la función de regresión es usar funciones de un espacio de Hilbert de kernel de reproducción . ^[2] Estos espacios pueden ser de dimensión infinita, en los que pueden proporcionar soluciones que sobreajustan conjuntos de entrenamiento de tamaño arbitrario. Por lo tanto, la regularización es especialmente importante para estos métodos. Una forma de regularizar problemas de regresión no paramétrica es aplicar una regla de detención temprana a un procedimiento iterativo como el descenso de gradiente. ${\displaystyle \rho (y\mid x)}$ ${\displaystyle x}$ ${\displaystyle \rho }$

Las reglas de detención temprana propuestas para estos problemas se basan en el análisis de los límites superiores del error de generalización en función del número de iteraciones. Producen prescripciones para el número de iteraciones que se deben ejecutar y que se pueden calcular antes de iniciar el proceso de solución. ^{[3] [4]}

Ejemplo: pérdida por mínimos cuadrados

(Adaptado de Yao, Rosasco y Caponnetto, 2007 ^[3] )

Sea y Dado un conjunto de muestras ${\displaystyle X\subseteq \mathbb {R} ^{n}}$ ${\displaystyle Y=\mathbb {R} .}$

${\displaystyle \mathbf {z} =\left\{(x_{i},y_{i})\in X\times Y:i=1,\dots ,m\right\}\in Z^{m},}$

extraído independientemente de , minimiza la funcionalidad ${\displaystyle \rho }$

${\displaystyle {\mathcal {E}}(f)=\int _{X\times Y}(f(x)-y)^{2}\,d\rho }$

donde, es un miembro del espacio de Hilbert del núcleo reproductor . Es decir, minimiza el riesgo esperado para una función de pérdida de mínimos cuadrados. Dado que depende de la medida de probabilidad desconocida , no se puede utilizar para el cálculo. En su lugar, considere el siguiente riesgo empírico ${\displaystyle f}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle {\mathcal {E}}}$ ${\displaystyle \rho }$

${\displaystyle {\mathcal {E}}_{\mathbf {z} }(f)={\frac {1}{m}}\sum _{i=1}^{m}\left(f(x_{i})-y_{i}\right)^{2}.}$

Sean y las iteraciones t -ésimas del descenso de gradiente aplicadas a los riesgos esperados y empíricos, respectivamente, donde ambas iteraciones se inicializan en el origen y ambas utilizan el tamaño de paso . Las forman la iteración de población , que converge a , pero no se puede utilizar en el cálculo, mientras que las forman la iteración de muestra que generalmente converge a una solución de sobreajuste. ${\displaystyle f_{t}}$ ${\displaystyle f_{t}^{\mathbf {z} }}$ ${\displaystyle \gamma _{t}}$ ${\displaystyle f_{t}}$ ${\displaystyle f_{\rho }}$ ${\displaystyle f_{t}^{\mathbf {z} }}$

Queremos controlar la diferencia entre el riesgo esperado de la iteración de la muestra y el riesgo mínimo esperado, es decir, el riesgo esperado de la función de regresión:

${\displaystyle {\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{\rho })}$

Esta diferencia se puede reescribir como la suma de dos términos: la diferencia en el riesgo esperado entre las iteraciones de la muestra y la población y entre la iteración de la población y la función de regresión:

${\displaystyle {\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{\rho })=\left[{\mathcal {E}}(f_{t}^{\mathbf {z} })-{\mathcal {E}}(f_{t})\right]+\left[{\mathcal {E}}(f_{t})-{\mathcal {E}}(f_{\rho })\right]}$

Esta ecuación presenta un equilibrio entre sesgo y varianza , que luego se resuelve para obtener una regla de detención óptima que puede depender de la distribución de probabilidad desconocida. Esa regla tiene límites probabilísticos asociados en el error de generalización. Para el análisis que conduce a la regla de detención temprana y los límites, se remite al lector al artículo original. ^[3] En la práctica, se pueden utilizar métodos basados ​​en datos, por ejemplo, la validación cruzada, para obtener una regla de detención adaptativa.

Parada temprana en el impulso

Boosting se refiere a una familia de algoritmos en los que un conjunto de aprendices débiles (aprendices que solo están ligeramente correlacionados con el proceso verdadero) se combinan para producir un aprendiz fuerte . Se ha demostrado, para varios algoritmos de boosting (incluido AdaBoost ), que la regularización mediante detención temprana puede proporcionar garantías de consistencia , es decir, que el resultado del algoritmo se acerca a la solución verdadera a medida que el número de muestras tiende al infinito. ^{[5] [6] [7] [8]}

yo₂-impulsando

Los métodos de refuerzo tienen vínculos estrechos con los métodos de descenso de gradiente descritos anteriormente y pueden considerarse como un método de refuerzo basado en la pérdida: L ₂ Boost . ^[3] ${\displaystyle L_{2}}$

Detención anticipada basada en validación

Estas reglas de detención temprana funcionan dividiendo el conjunto de entrenamiento original en un nuevo conjunto de entrenamiento y un conjunto de validación . El error en el conjunto de validación se utiliza como un proxy para el error de generalización para determinar cuándo ha comenzado el sobreajuste. Estos métodos se emplean en el entrenamiento de muchos algoritmos iterativos de aprendizaje automático, incluidas las redes neuronales . Prechelt ofrece el siguiente resumen de una implementación ingenua de detención temprana basada en holdout de la siguiente manera: ^[9]

1. Dividir los datos de entrenamiento en un conjunto de entrenamiento y un conjunto de validación, por ejemplo, en una proporción de 2 a 1.
2. Entrene solo en el conjunto de entrenamiento y evalúe el error por ejemplo en el conjunto de validación de vez en cuando, por ejemplo, después de cada quinta época.
3. Detenga el entrenamiento tan pronto como el error en el conjunto de validación sea mayor que el que tenía la última vez que se verificó.
4. Utilice los pesos que tenía la red en el paso anterior como resultado de la ejecución de entrenamiento.
   —  Lutz Prechelt, Detención temprana, ¿pero cuándo?

La validación cruzada  es una alternativa que se puede aplicar a escenarios que no son de series temporales. La validación cruzada implica dividir múltiples particiones de los datos en un conjunto de entrenamiento y un conjunto de validación, en lugar de una única partición en un conjunto de entrenamiento y un conjunto de validación. Incluso este procedimiento simple se complica en la práctica por el hecho de que el error de validación puede fluctuar durante el entrenamiento, lo que produce múltiples mínimos locales. Esta complicación ha llevado a la creación de muchas reglas ad hoc para decidir cuándo ha comenzado realmente el sobreajuste. ^[9]

Véase también

• El sobreajuste y la detención temprana son uno de los métodos utilizados para evitar el sobreajuste.
• Error de generalización
• Regularización (matemáticas)
• Teoría del aprendizaje estadístico
• Impulso (aprendizaje automático)
• Validación cruzada , en particular utilizando un "conjunto de validación"
• Redes neuronales

Referencias

1. Girosi, Federico; Michael Jones; Tomaso Poggio (1995-03-01). "Teoría de la regularización y arquitecturas de redes neuronales". Computación neuronal . 7 (2): 219–269. CiteSeerX  10.1.1.48.9258 . doi :10.1162/neco.1995.7.2.219. ISSN  0899-7667. S2CID  49743910.
2. Smale, Steve; Ding-Xuan Zhou (1 de agosto de 2007). "Estimaciones de la teoría del aprendizaje mediante operadores integrales y sus aproximaciones". Aproximación constructiva . 26 (2): 153–172. CiteSeerX 10.1.1.210.722 . doi :10.1007/s00365-006-0659-y. ISSN  0176-4276. S2CID  5977083. 
3. Yao, Yuan; Lorenzo Rosasco; Andrea Caponnetto (1 de agosto de 2007). "Sobre la detención temprana en el aprendizaje por descenso de gradiente". Aproximación constructiva . 26 (2): 289–315. CiteSeerX 10.1.1.329.2482 . doi :10.1007/s00365-006-0663-2. ISSN  0176-4276. S2CID  8323954. 
4. Raskutti, G.; MJ Wainwright; Bin Yu (2011). "Detención temprana para regresión no paramétrica: una regla de detención óptima dependiente de los datos". 2011 49.ª Conferencia Anual de Allerton sobre Comunicación, Control y Computación (Allerton) . 2011 49.ª Conferencia Anual de Allerton sobre Comunicación, Control y Computación (Allerton). págs. 1318–1325. doi :10.1109/Allerton.2011.6120320.
5. Wenxin Jiang (febrero de 2004). "Consistencia del proceso para AdaBoost". Anales de Estadística . 32 (1): 13–29. doi : 10.1214/aos/1079120128 . ISSN  0090-5364.
6. Bühlmann, Peter; Bin Yu (1 de junio de 2003). "Aumento con pérdida de L₂: regresión y clasificación". Revista de la Asociación Estadounidense de Estadística . 98 (462): 324–339. doi :10.1198/016214503000125. ISSN  0162-1459. JSTOR  30045243. S2CID  123059267.
7. Tong Zhang; Bin Yu (1 de agosto de 2005). "Impulso con detención temprana: convergencia y consistencia". Anales de estadística . 33 (4): 1538–1579. arXiv : math/0508276 . Bibcode :2005math......8276Z. doi :10.1214/009053605000000255. ISSN  0090-5364. JSTOR  3448617. S2CID  13158356.
8. Stankewitz, Bernhard (1 de abril de 2024). "Detención temprana del refuerzo L2 en modelos lineales de alta dimensión". Anales de estadística . 52 (2): 491–518. arXiv : 2210.07850 . doi :10.1214/24-AOS2356.
9. Prechelt, Lutz; Geneviève B. Orr (1 de enero de 2012). "Detención temprana, pero ¿cuándo?". En Grégoire Montavon; Klaus-Robert Müller (eds.). Redes neuronales: trucos del oficio . Apuntes de clase en informática. Springer Berlin Heidelberg. págs. 53–67. doi :10.1007/978-3-642-35289-8_5. ISBN 978-3-642-35289-8.