AdaGrad (abreviatura de Adaptive Gradient) es un algoritmo de optimización utilizado en aprendizaje automático y aprendizaje profundo que adapta la tasa de aprendizaje para cada parámetro individualmente. A diferencia del descenso de gradiente estocástico estándar, que aplica una única tasa de aprendizaje a todos los parámetros, AdaGrad escala la actualización de cada parámetro en función de los gradientes cuadrados históricos de ese parámetro. Esta adaptación por parámetro permite que el algoritmo realice actualizaciones más grandes para parámetros poco frecuentes y actualizaciones más pequeñas para los frecuentes, lo que resulta particularmente útil en entornos de datos dispersos. AdaGrad fue introducido por John Duchi, Elad Hazan y Yoram Singer en 2011 y se ha convertido en un método fundamental en el desarrollo de optimizadores adaptativos posteriores como RMSProp y Adam.
La idea central de AdaGrad es mantener una suma acumulada de los cuadrados de los gradientes pasados para cada parámetro. En cada iteración, la tasa de aprendizaje para un parámetro se divide por la raíz cuadrada de esta suma acumulada. Esto significa que los parámetros con gradientes históricos grandes reciben tasas de aprendizaje efectivas más pequeñas, mientras que los parámetros con gradientes pequeños o poco frecuentes reciben tasas de aprendizaje efectivas más grandes. La acumulación de gradientes cuadrados aumenta de manera monótona, lo que provoca que la tasa de aprendizaje efectiva decaiga con el tiempo. Esta propiedad puede ser beneficiosa para la convergencia en entornos convexos, pero también puede conducir a una disminución excesivamente agresiva en problemas no convexos, una limitación que motivó algoritmos posteriores.
Antecedentes
La optimización en el aprendizaje automático a menudo implica minimizar una función objetivo que es una suma de funciones de pérdida por ejemplo. Para un conjunto de entrenamiento de n ejemplos, el riesgo empírico se expresa como Q(w) = (1/n) Σ Q_i(w), donde w es el vector de parámetros y Q_i es la pérdida para el i-ésimo ejemplo. El descenso de gradiente estándar calcula el gradiente de la suma completa en cada paso, lo que puede ser computacionalmente costoso cuando n es grande. El descenso de gradiente estocástico (SGD) en su lugar aproxima el gradiente utilizando una sola muestra o un mini-lote, reduciendo el costo computacional por iteración pero introduciendo ruido. El algoritmo de Robbins-Monro de la década de 1950 sentó las bases para la aproximación estocástica, y el SGD se convirtió en un pilar del aprendizaje automático debido a su eficiencia en conjuntos de datos grandes.
En SGD, la regla de actualización es w := w - η ∇Q_i(w), donde η es la tasa de aprendizaje. Elegir una tasa de aprendizaje fija suele ser subóptimo: una tasa demasiado grande puede causar divergencia, mientras que una demasiado pequeña ralentiza la convergencia. Métodos adaptativos como AdaGrad buscan abordar esto ajustando la tasa de aprendizaje según la geometría del paisaje de optimización. La motivación para AdaGrad provino de la observación de que diferentes parámetros pueden requerir tamaños de paso distintos, especialmente en problemas con características dispersas donde algunos parámetros se actualizan raramente.
Algoritmo
AdaGrad modifica la actualización de SGD manteniendo una matriz diagonal G_t, donde cada elemento diagonal es la suma de los cuadrados de los gradientes pasados para el parámetro correspondiente. En el paso de tiempo t, la actualización para el parámetro w_i es:
w_i := w_i - (η / sqrt(G_{t,ii} + ε)) ∇Q_i(w_i),
donde ε es una constante pequeña (por ejemplo, 1e-8) para evitar la división por cero. Los gradientes cuadrados acumulados G_{t,ii} = Σ_{τ=1}^{t} (∇Q_i(w_τ))^2. Esto se puede escribir en forma vectorial como:
w := w - η * diag(G_t + εI)^{-1/2} ∇Q(w).
En la práctica, el algoritmo se aplica a menudo a mini-lotes, donde el gradiente se calcula sobre un subconjunto de ejemplos de entrenamiento. La tasa de aprendizaje por parámetro es entonces η_t,i = η / sqrt(G_{t,ii} + ε). Debido a que G_t crece con el tiempo, la tasa de aprendizaje efectiva disminuye, asegurando que el algoritmo tome pasos más pequeños a medida que avanza. Esto contrasta con SGD con momento, que acumula gradientes para acelerar en direcciones consistentes.
Propiedades Matemáticas
AdaGrad fue analizado originalmente en el contexto de la optimización convexa. Los autores demostraron que para funciones convexas, AdaGrad alcanza un límite de arrepentimiento que es asintóticamente óptimo para el aprendizaje en línea. Específicamente, el arrepentimiento, que mide la diferencia acumulada entre la pérdida del algoritmo y el mejor parámetro fijo en retrospectiva, crece como O(√T) para AdaGrad, igualando el límite inferior para la optimización convexa en línea. Esto es una mejora sobre el SGD estándar con una tasa de aprendizaje fija, que puede requerir un ajuste cuidadoso del programa de tasa de aprendizaje.
La idea clave es que AdaGrad se adapta automáticamente a la geometría del espacio de características. En entornos dispersos, donde muchas características son cero para la mayoría de los ejemplos, los gradientes acumulados para esas características permanecen pequeños, permitiendo actualizaciones más grandes cuando aparecen. Esto hace que AdaGrad sea particularmente efectivo para el procesamiento del lenguaje natural y otros dominios con entradas dispersas de alta dimensión.
Sin embargo, la acumulación de gradientes cuadrados aumenta de manera monótona, lo que significa que la tasa de aprendizaje decae a cero con el tiempo. En problemas no convexos, como el entrenamiento de redes neuronales profundas, esto puede causar que el algoritmo deje de aprender prematuramente. Esta limitación condujo al desarrollo de variantes como RMSProp, que utiliza un promedio móvil de gradientes cuadrados en lugar de una suma, y Adam, que combina tasas de aprendizaje adaptativas con momento.
Aplicaciones
AdaGrad se ha aplicado en diversas tareas de aprendizaje automático, particularmente aquellas que involucran datos dispersos. En el procesamiento del lenguaje natural, se ha utilizado para entrenar modelos con características de bolsa de palabras, donde cada documento se representa mediante un vector disperso de recuentos de palabras. La adaptación por parámetro permite que las palabras raras reciban actualizaciones más grandes, mejorando la capacidad del modelo para aprender de características poco frecuentes pero informativas.
En sistemas de recomendación, AdaGrad se ha utilizado para optimizar modelos de factorización de matrices, donde los embeddings de usuarios y elementos se actualizan según datos de interacción dispersos. La capacidad del algoritmo para manejar frecuencias variables de pares usuario-elemento lo hace adecuado para tales entornos. Además, AdaGrad se ha empleado en escenarios de aprendizaje en línea, donde los datos llegan secuencialmente y el modelo debe adaptarse rápidamente.
A pesar de haber sido superado por optimizadores más avanzados en muchas aplicaciones de aprendizaje profundo, AdaGrad sigue siendo un punto de referencia para comparaciones y todavía se utiliza en algunos dominios donde sus propiedades son ventajosas. Su influencia es evidente en el diseño de métodos adaptativos posteriores, que se basan en la idea de tasas de aprendizaje por parámetro.
Limitaciones y Extensiones
La limitación principal de AdaGrad es la tasa de aprendizaje que disminuye de manera monótona. En el aprendizaje profundo, donde el paisaje de pérdida es no convexo, esto puede conducir a una convergencia lenta o a quedarse atascado en mínimos locales pobres. Para abordar esto, los investigadores han propuesto varias extensiones:
- RMSProp: Introducido por Geoffrey Hinton en sus notas de clase, RMSProp utiliza un promedio móvil con decaimiento exponencial de los gradientes cuadrados, permitiendo que la tasa de aprendizaje se adapte de manera más flexible.
- Adam: Propuesto por Diederik Kingma y Jimmy Ba en 2014, Adam combina el promedio móvil de RMSProp con momento, proporcionando tanto tasas de aprendizaje adaptativas como momento.
- AdaDelta: Desarrollado por Matthew Zeiler, AdaDelta elimina la necesidad de un hiperparámetro de tasa de aprendizaje al utilizar una ventana de gradientes pasados.
Estos algoritmos se han convertido en las opciones predeterminadas para entrenar redes neuronales profundas, pero todos tienen sus raíces en el concepto de gradiente adaptativo introducido por AdaGrad.
Impacto y Legado
AdaGrad ha tenido un impacto duradero en el campo de la optimización en el aprendizaje automático. Fue uno de los primeros algoritmos ampliamente adoptados en utilizar tasas de aprendizaje por parámetro, allanando el camino para una familia de optimizadores adaptativos. Sus garantías teóricas en entornos convexos proporcionaron una base sólida para comprender los métodos adaptativos. El algoritmo se cita a menudo en libros de texto y artículos de investigación como un desarrollo clave en la historia de la optimización.
En la práctica, AdaGrad se utiliza menos hoy en día para entrenar modelos de aprendizaje profundo a gran escala, ya que Adam y sus variantes tienden a funcionar mejor. Sin embargo, sigue siendo una herramienta útil para problemas específicos, como aquellos con características dispersas, y todavía se enseña en cursos de aprendizaje automático como un paso conceptual importante.
Véase También
- descenso-de-gradiente-estocástico
- optimizador-adam
- RMSProp
- aprendizaje-profundo