En el aprendizaje automático , la parada temprana es una forma de regularización que se utiliza para evitar el sobreajuste cuando se entrena a un alumno con un método iterativo, como el descenso de gradientes . 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. Pasado ese punto, sin embargo, 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 anticipada brindan orientación sobre cuántas iteraciones se pueden ejecutar antes de que el alumno comience a adaptarse en exceso. Las reglas de detención anticipada se han empleado en muchos métodos diferentes de aprendizaje automático, con diferentes cantidades de fundamento teórico.
Fondo
Esta sección presenta algunos de los conceptos básicos de aprendizaje automático necesarios para una descripción de los métodos de detención anticipada.
Sobreajuste
Los algoritmos de aprendizaje automático entrenan un modelo basado en un conjunto finito de datos de entrenamiento. Durante este entrenamiento, el modelo se evalúa en función de qué tan bien 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 nunca antes vistas. El sobreajuste se produce cuando un modelo se ajusta bien a los datos del conjunto de entrenamiento, al tiempo que se produce 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 al modelo aprendido. [1] Esta suavidad puede hacerse cumplir 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, caen bajo el paraguas de la regularización espectral, regularización caracterizada por la aplicación de un filtro. La parada anticipada también pertenece a esta clase de métodos.
Métodos de descenso de gradientes
Los métodos de descenso de gradientes 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 de paso de manera apropiada, se puede hacer que dicho método 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
Detención temprana en la teoría del aprendizaje estadístico
La detención anticipada 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,, espacio de salida, , y muestras extraídas de una medida de probabilidad desconocida, , en , el objetivo de tales problemas es aproximar una función de regresión ,, dada por
- ,
dónde es la distribución condicional en Inducido por . [2] Una opción común para aproximar la función de regresión es usar funciones de un espacio de Hilbert del núcleo en reproducción . [2] Estos espacios pueden ser de dimensión infinita, en los que pueden proporcionar soluciones que se adapten a conjuntos de entrenamiento de tamaño arbitrario. Por tanto, la regularización es especialmente importante para estos métodos. Una forma de regularizar los problemas de regresión no paramétrica es aplicar una regla de detención anticipada a un procedimiento iterativo como el descenso de gradiente.
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 iteración. Proporcionan prescripciones para el número de iteraciones a ejecutar 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] )
Dejar y . Dado un conjunto de muestras
- ,
elaborado independientemente de , minimizar el funcional
dónde, es un miembro del espacio de Hilbert del núcleo de reproducción . Es decir, minimizar el riesgo esperado de una función de pérdida por mínimos cuadrados. Desde depende de la medida de probabilidad desconocida , no se puede utilizar para cálculos. En su lugar, considere el siguiente riesgo empírico
Dejar y ser la t -ésima iteración del descenso de gradiente aplicada a los riesgos esperados y empíricos, respectivamente, donde ambas iteraciones se inicializan en el origen, y ambas usan el tamaño de paso. Laforman la iteración de la población , que converge a, pero no se puede utilizar en el cálculo, mientras que el forman la iteración de muestra que generalmente converge en una solución de sobreajuste.
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:
Esta diferencia puede reescribirse como la suma de dos términos: la diferencia en el riesgo esperado entre la muestra y las iteraciones de la población y entre la iteración de la población y la función de regresión:
Esta ecuación presenta una compensación de sesgo-varianza , que luego se resuelve para dar una regla de parada óptima que puede depender de la distribución de probabilidad desconocida. Esa regla tiene límites probabilísticos asociados al error de generalización. Para el análisis que conduce a la regla y los límites de detención anticipada, se remite al lector al artículo original. [3] En la práctica, los métodos basados en datos, por ejemplo, la validación cruzada, se pueden utilizar para obtener una regla de detención adaptativa.
Detenerse temprano en el impulso
El impulso se refiere a una familia de algoritmos en los que un conjunto de alumnos débiles (alumnos que están solo ligeramente correlacionados con el proceso real) se combinan para producir un alumno fuerte . Se ha demostrado, para varios algoritmos de impulso (incluido AdaBoost ), que la regularización mediante la detención anticipada puede proporcionar garantías de coherencia , es decir, que el resultado del algoritmo se acerca a la verdadera solución a medida que el número de muestras llega al infinito. [5] [6] [7]
L 2 -impulso
Los métodos de impulso tienen vínculos estrechos con los métodos de descenso de gradiente descritos anteriormente que se pueden considerar como un método de impulso basado en elpérdida: L 2 Boost . [3]
Detención anticipada basada en validación
Estas reglas de detención anticipada 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 proxy del error de generalización para determinar cuándo ha comenzado el sobreajuste. Estos métodos se emplean con mayor frecuencia en el entrenamiento de redes neuronales . Prechelt ofrece el siguiente resumen de una implementación ingenua de la detención anticipada basada en la retención de la siguiente manera: [8]
- Divida 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.
- 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 cinco épocas.
- Detenga el entrenamiento tan pronto como el error en el conjunto de validación sea mayor que la última vez que se verificó.
- Utilice los pesos que tenía la red en ese paso anterior como resultado de la ejecución de entrenamiento.
- Lutz Prechelt, parada anticipada, pero ¿cuándo?
Los formularios más sofisticados utilizan la validación cruzada (múltiples particiones de los datos en un conjunto de entrenamiento y un conjunto de validación) en lugar de una sola partición en un conjunto de entrenamiento y un conjunto de validación. Incluso este sencillo procedimiento se complica en la práctica por el hecho de que el error de validación puede fluctuar durante el entrenamiento, produciendo múltiples mínimos locales. Esta complicación ha llevado a la creación de muchas reglas ad hoc para decidir cuándo realmente ha comenzado el sobreajuste. [8]
Ver también
- El sobreajuste , la parada anticipada es 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 mediante un "conjunto de validación"
- Redes neuronales
Referencias
- ^ Girosi, Federico; Michael Jones; Tomaso Poggio (1 de marzo de 1995). "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 .
- ^ a b Smale, Steve; Ding-Xuan Zhou (1 de agosto de 2007). "Estimaciones de la teoría del aprendizaje a través de 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 .
- ^ a b c d Yao, Yuan; Lorenzo Rosasco; Andrea Caponnetto (1 de agosto de 2007). "Sobre la parada temprana en el aprendizaje por descenso de gradientes". 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 .
- ^ Raskutti, G .; MJ Wainwright; Bin Yu (2011). "Parada temprana para regresión no paramétrica: una regla de parada dependiente de datos óptima". 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 .
- ^ Wenxin Jiang (febrero de 2004). "Consistencia del proceso para AdaBoost" . The Annals of Statistics . 32 (1): 13-29. doi : 10.1214 / aos / 1079120128 . ISSN 0090-5364 .
- ^ Bühlmann, Peter; Bin Yu (1 de junio de 2003). "Impulso con la pérdida 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 .
- ^ Tong Zhang; Bin Yu (1 de agosto de 2005). "Impulso con parada anticipada: convergencia y coherencia". The Annals of Statistics . 33 (4): 1538-1579. arXiv : matemáticas / 0508276 . Bibcode : 2005math ...... 8276Z . doi : 10.1214 / 009053605000000255 . ISSN 0090-5364 . JSTOR 3448617 . S2CID 13158356 .
- ^ a b Prechelt, Lutz; Geneviève B. Orr (1 de enero de 2012). "Parada anticipada, pero ¿cuándo?". En Grégoire Montavon; Klaus-Robert Müller (eds.). Redes neuronales: trucos del oficio . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. págs. 53 –67. doi : 10.1007 / 978-3-642-35289-8_5 . ISBN 978-3-642-35289-8.