El descenso de gradiente estocástico (en inglés: Stochastic gradient descent, a menudo abreviado como SGD) es un método iterativo para optimizar una función objetivo con propiedades de suavidad adecuadas (por ejemplo, diferenciable o subdiferenciable). Puede considerarse una aproximación estocástica de la optimización por descenso de gradiente, ya que sustituye el gradiente real (calculado a partir de todo el conjunto de datos) por una estimación del mismo (calculada a partir de un subconjunto de datos seleccionados aleatoriamente). Especialmente en problemas de optimización de alta dimensión, esto reduce la elevadísima carga computacional, consiguiendo iteraciones más rápidas a cambio de una menor tasa de convergencia.[1]
Aunque la idea básica de la aproximación estocástica se remonta al algoritmo Robbins-Monro de la década de 1950, el descenso de gradiente estocástico se ha convertido en un importante método de optimización en el aprendizaje automático.[2]
en la que el parámetro que minimiza será estimado. Cada una de las funciones sumando suele estar asociada a la observación-n del conjunto de datos (utilizado para el entrenamiento).
En la estadística clásica, los problemas de minimización de sumas surgen en los mínimos cuadrados y en la estimación de máxima verosimilitud (para observaciones independientes). La clase general de estimadores que surgen como minimizadores de sumas se denominan estimadores M (o M-estimador). Sin embargo, en estadística se reconoce desde hace tiempo que exigir incluso una minimización local es demasiado restrictivo para algunos problemas de estimación de máxima verosimilitud.[3] Por lo tanto, los teóricos estadísticos contemporáneos suelen considerar puntos estacionarios de la función de verosimilitud (o ceros de su derivada, la función de puntuación y otras ecuaciones de estimación).
El problema de minimización de la suma también se plantea en la minimización del riesgo empírico. En este es el valor de la función de pérdida en el ejemplo de -n, y es el riesgo empírico.
Cuando se utiliza para minimizar la función anterior, un método de descenso de gradiente estándar (o "por lotes") realizaría las siguientes iteraciones:
donde es un step size (a veces llamado tasa de aprendizaje en el aprendizaje automático).
En muchos casos, las funciones sumando tienen una forma simple que permite evaluaciones económicas de la función suma y del gradiente de la suma. Por ejemplo, en estadística, las familias exponenciales de un parámetro permiten evaluaciones económicas de la función y del gradiente.
Sin embargo, en otros casos, la evaluación del gradiente de la suma puede requerir costosas evaluaciones de los gradientes de todas las funciones sumando. Cuando el conjunto de entrenamiento es enorme y no existen fórmulas sencillas, la evaluación de las sumas de gradientes resulta muy costosa, porque evaluar el gradiente requiere evaluar todos los gradientes de las funciones sumando. Para economizar el coste computacional en cada iteración, el descenso de gradiente estocástico muestrea un subconjunto de funciones sumando en cada paso (en inglés: step). Esto resulta muy eficaz en el caso de problemas de aprendizaje automático a gran escala.[4]
Método iterativo
Fluctuaciones en la función objetivo total a medida que se dan pasos de gradiente con respecto a minilotes.
En el descenso de gradiente estocástico (o "en línea"), el verdadero gradiente de se aproxima por un gradiente en una sola muestra:
A medida que el algoritmo recorre el conjunto de entrenamiento, realiza la actualización anterior para cada muestra de entrenamiento. Se pueden realizar varias pasadas por el conjunto de entrenamiento hasta que el algoritmo converja. Si se hace esto, los datos pueden barajarse en cada pasada para evitar ciclos. Las implementaciones típicas pueden utilizar una tasa de aprendizaje adaptativa para que el algoritmo converja.[5]
En pseudocódigo, el descenso de gradiente estocástico puede presentarse como:
Elegir un vector inicial de parámetros y tasa de aprendizaje .
Repita la operación hasta obtener un mínimo aproximado:
Barajar aleatoriamente las muestras del conjunto de entrenamiento.
Para , realizar:
Un compromiso entre calcular el gradiente verdadero y el gradiente en una sola muestra es calcular el gradiente contra más de una muestra de entrenamiento (llamado "mini-lote") en cada paso. Esto puede funcionar significativamente mejor que el descenso de gradiente estocástico "verdadero" descrito, porque el código puede hacer uso de bibliotecas de vectorización en lugar de calcular cada fase por separada, como se mostró por primera vez[6] en el llamado "algoritmo de retropropagación en modo de lote". También puede dar lugar a una convergencia más suave, ya que el gradiente calculado en cada paso se promedia sobre más muestras de entrenamiento.
La convergencia del descenso de gradiente estocástico se ha analizado utilizando las teorías de la minimización convexa y de la aproximación estocástica. Brevemente, cuando las tasas de aprendizaje disminuyen con una tasa apropiada, y sujeto a supuestos relativamente suaves, el descenso de gradiente estocástico converge casi seguro a un mínimo global cuando la función objetivo es convexa o pseudoconvexa, y en caso contrario converge casi con seguridad a un mínimo local.[7][8] Esto es, de hecho, una consecuencia del teorema de Robbins-Siegmund.[9]
Ejemplo
Supongamos que queremos ajustar una recta a un conjunto de entrenamiento con observaciones y las correspondientes respuestas estimadas utilizando mínimos cuadrados. La función objetivo a minimizar es:
La última línea del pseudocódigo anterior para este problema específico se convertirá en:
Nótese que en cada iteración (también llamada actualización), el gradiente sólo se evalúa en un único punto en lugar de en el conjunto de todas las muestras.
La diferencia clave en comparación con el descenso gradiente estándar (por lotes) es que sólo se utiliza un dato del conjunto de datos para calcular el paso, y el dato se elige aleatoriamente en cada paso.
El descenso de gradiente estocástico compite con el algoritmo L-BFGS, que también es ampliamente utilizado. El descenso de gradiente estocástico se ha utilizado al menos desde 1960 para el entrenamiento de modelos de regresión lineal, originalmente bajo el nombre de ADALINE.[13]
Otro algoritmo de descenso de gradiente estocástico es el filtro adaptativo de mínimos cuadrados medios (en inglés: Least-Mean-Square algorithm, LMS).
Extensiones y variantes
Se han propuesto y utilizado muchas mejoras del algoritmo básico de descenso de gradiente estocástico. En particular, en el aprendizaje automático, se ha reconocido que la necesidad de establecer una tasa de aprendizaje (step size) es problemática. Si se fija un parámetro demasiado alto, el algoritmo puede divergir; si se fija demasiado bajo, la convergencia es lenta.[14] Una extensión conceptualmente simple del descenso de gradiente estocástico hace que la tasa de aprendizaje sea una función decreciente del número de iteraciones , dando un programa de tasa de aprendizaje, de modo que las primeras iteraciones causen grandes cambios en los parámetros, mientras que las posteriores sólo hacen un ajuste fino. Tales programas se conocen desde el trabajo de MacQueen sobre la agrupación -medias.[15] Spall ofrece orientación práctica sobre la elección del step size en diversas variantes de SGD.[16]
Actualizaciones implícitas (ISGD)
Como ya se ha mencionado, el descenso de gradiente estocástico clásico suele ser sensible a la tasa de aprendizaje. Una convergencia rápida requiere grandes tasas de aprendizaje, pero esto puede inducir inestabilidad numérica. El problema puede resolverse en gran medida[17] considerando actualizaciones implícitas en las que el gradiente estocástico se evalúa en la siguiente iterada en lugar de en la actual:
Esta ecuación está implícita ya que aparece en ambos lados de la ecuación. Se trata de una forma estocástica del método del gradiente proximal, ya que la actualización también puede escribirse como:
A modo de ejemplo, consideremos los mínimos cuadrados con características y observaciones . Queremos resolver:
en el que indica el producto interior. Obsérvese que podría tener "1" como primer elemento para incluir un intercepto. El descenso de gradiente estocástico clásico procede de la siguiente manera:
donde se muestrea uniformemente entre 1 y . Aunque la convergencia teórica de este procedimiento se produce bajo supuestos relativamente suaves, en la práctica el procedimiento puede ser bastante inestable. En particular, cuando está mal especificado de modo que tiene grandes valores propios absolutos con alta probabilidad, el procedimiento puede divergir numéricamente en unas pocas iteraciones. Por el contrario, el descenso de gradiente estocástico implícito (abreviado como ISGD) puede resolverse de forma cerrada como:
Este procedimiento se mantendrá numéricamente estable prácticamente para todas las ya que la tasa de aprendizaje está ahora normalizada. Esta comparación entre el descenso de gradiente estocástico clásico e implícito en el problema de mínimos cuadrados es muy similar a la comparación entre el filtro de mínimos cuadrados medios (LMS) y el filtro de mínimos cuadrados medios normalizados (NLMS).
Aunque una solución de forma cerrada para el ISGD sólo es posible en mínimos cuadrados, el procedimiento puede aplicarse eficazmente en una amplia gama de modelos. En concreto, supongamos que depende de sólo a través de una combinación lineal con las características , de modo que podemos escribir , donde puede depender de pero no en excepto a través de . Los mínimos cuadrados obedecen esta regla, al igual que la regresión logística y la mayoría de los modelos lineales generalizados. Por ejemplo, en mínimos cuadrados, y en regresión logística , donde es la función logística. En la regresión de Poisson y así sucesivamente.
En estos casos, la ISGD se aplica de la siguiente manera. Sea , donde es escalar. Entonces, ISGD es equivalente a:
El factor de escala puede hallarse mediante el método de bisección, ya que en la mayoría de los modelos regulares, como los modelos lineales generalizados mencionados, la función es decreciente, y por lo tanto los límites de búsqueda para son .
Momentum
Otras propuestas incluyen el método del momentum o método de la bola pesada, que en el contexto del ML apareció en el artículo de Rumelhart, Hinton y Williams sobre el aprendizaje por retropropagación[18] y tomó prestada la idea del artículo del matemático soviético Boris Polyak de 1964 sobre la resolución de ecuaciones funcionales.[19] El descenso de gradiente estocástico con impulso recuerda la actualización Δw en cada iteración, y determina la siguiente actualización como una combinación lineal del gradiente y la actualización anterior:[20][21]
lo cual conduce a:
donde el parámetro que minimiza a será estimado, es un step size (a veces llamado tasa de aprendizaje en el aprendizaje automático) y es un factor de decaimiento exponencial entre 0 y 1 que determina la contribución relativa del gradiente actual y los gradientes anteriores al cambio de peso.
El nombre momentum proviene de una analogía con el momentum en física: el vector peso , pensado como una partícula que viaja a través del espacio de parámetros,[18] incurre en aceleración por el gradiente de la pérdida ("fuerza"). A diferencia del descenso por gradiente estocástico clásico, tiende a seguir viajando en la misma dirección, evitando oscilaciones. Los científicos informáticos llevan varias décadas utilizando con éxito el método del momentum en el entrenamiento de redes neuronales artificiales.[22] El método del momentum está estrechamente relacionado con la dinámica de Langevin sin amortiguación y puede combinarse con el algoritmo de recocido simulado.[23]
A mediados de la década de 1980, el método fue modificado por Yurii Nesterov para utilizar el gradiente previsto en el siguiente punto, y el llamado Gradiente Acelerado de Nesterov resultante se utilizó a veces en ML en la década de 2010.[24]
Promedio
El descenso de gradiente estocástico promediado, inventado independientemente por Ruppert y Polyak a finales de la década de 1980, es un descenso de gradiente estocástico ordinario que registra un promedio de su vector de parámetros a lo largo del tiempo. Es decir, la actualización es la misma que para el descenso estocástico ordinario, pero el algoritmo también lleva la cuenta de[25]
Cuando se realiza la optimización, este vector de parámetros promediado ocupa el lugar de .
AdaGrad
AdaGrad (algoritmo de gradiente adaptativo) es un algoritmo de descenso de gradiente estocástico modificado con una tasa de aprendizaje por parámetro, publicado por primera vez en 2011.[26] Informalmente, esto aumenta la tasa de aprendizaje para los parámetros más dispersos y disminuye la tasa de aprendizaje para los que son menos dispersos. Esta estrategia suele mejorar el rendimiento de la convergencia con respecto al descenso por gradiente estocástico estándar en entornos en los que los datos son dispersos y los parámetros dispersos son más informativos. Ejemplos de estas aplicaciones son el procesamiento del lenguaje natural y el reconocimiento de imágenes.[26]
Sigue teniendo una tasa de aprendizaje base , pero ésta se multiplica por los elementos de un vector {Gj,j} que es la diagonal de la matriz producto exterior
donde , la gradiente, en la iteración . La diagonal viene dada por:
Este vector almacena esencialmente una suma histórica de cuadrados de gradiente por dimensión y se actualiza después de cada iteración. La fórmula para una actualización es ahora
Cada {G(i,i)} da lugar a un factor de escala para la tasa de aprendizaje que se aplica a un único parámetro . Dado que el denominador de este factor, es la norma ℓ2 de las derivadas anteriores, las actualizaciones extremas de los parámetros se amortiguan, mientras que los parámetros que reciben pocas o pequeñas actualizaciones reciben mayores tasas de aprendizaje.[22]
Aunque está diseñado para problemas convexos, AdaGrad se ha aplicado con éxito a la optimización no convexa.[28]
RMSProp
RMSProp o propagación de raíz cuadrática media (en inglés: Root Mean Square Propagation) es un método inventado por Geoffrey Hinton en 2012 en el que la tasa de aprendizaje es, como en Adagrad, adaptada para cada uno de los parámetros. La idea es dividir la tasa de aprendizaje para un peso por una media de las magnitudes de los gradientes recientes para ese peso.[29] Inusualmente, no se publicó en un artículo, sino que simplemente se describió en una conferencia de Coursera.
Así pues, primero se calcula la media móvil en términos de media cuadrática,
en el que es el factor de olvido. El concepto de almacenar el gradiente histórico como suma de cuadrados se toma prestado de Adagrad, pero el "olvido" se introduce para resolver la disminución de las tasas de aprendizaje de Adagrad en problemas no convexos, disminuyendo gradualmente la influencia de los datos antiguos.[30]
Y los parámetros se actualizan como,
RMSProp ha demostrado una buena adaptación de la tasa de aprendizaje en diferentes aplicaciones. RMSProp puede considerarse como una generalización de Rprop y es capaz de trabajar también con minilotes en lugar de sólo con lotes completos.[29]
Adam
Adam[31] o estimación de momento adaptativo (en inglés: Adaptive Moment Estimation) es una actualización de 2014 del optimizador RMSProp que lo combina con la característica principal del método Momentum.[32] En este algoritmo de optimización, se utilizan promedios en ejecución con olvido exponencial tanto de los gradientes como de los segundos momentos de los gradientes. Dados los parámetros y una función de pérdida , en el que indexa la iteración de entrenamiento actual (indexada en ), la actualización de los parámetros de Adam viene dada por:
donde es un escalar pequeño (por ejemplo ) utilizado para evitar la división por 0, y (por ejemplo, 0,9) y (por ejemplo, 0,999) son los factores de olvido para los gradientes y los segundos momentos de los gradientes, respectivamente. La cuadratura y la raíz cuadrada se realizan elemento a elemento. La profunda influencia de este algoritmo ha inspirado múltiples esquemas de optimización basados en el impulso más recientes y menos conocidos que utilizan gradientes mejorados por Nesterov (p. ej.: NAdam[33] y FASFA[34]) y diversas interpretaciones de la información de segundo orden (por ejemplo: Powerpropagation[35] y AdaSqrt[36]). Sin embargo, las variantes más utilizadas son AdaMax,[31] que generaliza Adam utilizando la norma del infinito, y AMSGrad,[37] que aborda los problemas de convergencia de Adam utilizando el máximo de los gradientes pasados al cuadrado en lugar de la media exponencial.[38]
AdamW[39] es una actualización posterior que mitiga una elección no óptima del algoritmo de regresión contraída (en inglés: ridge regression) en Adam.
Descenso de gradiente estocástico basado en signos
Aunque la optimización basada en signos se remonta al ya mencionado Rprop, solo en 2018 los investigadores intentaron simplificar Adam eliminando la magnitud del gradiente estocástico de ser tenido en cuenta y solo considerando su signo.[40][41]
Búsqueda lineal con retroceso
La búsqueda lineal con retroceso (en inglés: Backtracking line search) es otra variante del descenso de gradiente. Todos los datos que figuran a continuación proceden del enlace mencionado. Se basa en una condición conocida como la condición de Armijo-Goldstein. Ambos métodos permiten que las tasas de aprendizaje cambien en cada iteración; sin embargo, la forma del cambio es diferente. La búsqueda lineal con retroceso utiliza evaluaciones de funciones para comprobar la condición de Armijo y, en principio, el bucle del algoritmo para determinar las tasas de aprendizaje puede ser largo y desconocido de antemano. La SGD adaptativa no necesita un bucle para determinar las tasas de aprendizaje. Por otro lado, la SGD adaptativa no garantiza la "propiedad de descenso" –de la que goza la búsqueda lineal con retroceso–, que consiste en que para todo n. Si el gradiente de la función de coste es globalmente continuo de Lipschitz, con constante L de Lipschitz, y la tasa de aprendizaje se elige del orden 1/L, entonces la versión estándar de SGD es un caso especial de búsqueda lineal con retroceso.
Métodos de segundo orden
Un análogo estocástico del algoritmo estándar (determinista) de Newton-Raphson (un método de "segundo orden") proporciona una forma asintóticamente óptima o casi óptima de optimización iterativa en el entorno de la aproximación estocástica. Byrd, Hansen, Nocedal y Singer[42] desarrollaron un método que utiliza medidas directas de las matrices hessianas de los sumandos de la función de riesgo empírica. Sin embargo, determinar directamente las matrices hessianas necesarias para la optimización puede no ser posible en la práctica. Spall y otros[43][44][45] presentan métodos prácticos y teóricamente sólidos para versiones de segundo orden de SGD que no requieren información directa sobre el hessiano. (Un método menos eficiente basado en diferencias finitas, en lugar de perturbaciones simultáneas, es dado por Ruppert[46]). Otra aproximación a la matriz hessiana de aproximación consiste en sustituirla por la matriz de información de Fisher, que transforma el gradiente habitual en natural.[47] Estos métodos que no requieren información hessiana directa se basan en los valores de los sumandos de la función de riesgo empírica anterior o en los valores de los gradientes de los sumandos (es decir, las entradas SGD). En particular, la optimización de segundo orden es asintóticamente alcanzable sin cálculo directo de las matrices hessianas de los sumandos en la función de riesgo empírica.
Historia
El SGD fue desarrollado gradualmente por varios colectivos durante la década de 1950.
↑Kiwiel, Krzysztof C. (2001). «Convergence and efficiency of subgradient methods for quasiconvex minimization». Mathematical Programming, Series A (Berlin, Heidelberg: Springer) 90 (1): 1-25. ISSN0025-5610. doi:10.1007/PL00011414.
↑Sutskever, Ilya; Martens, James; Dahl, George; Hinton, Geoffrey E. (Junio de 2013). «On the importance of initialization and momentum in deep learning». En Dasgupta, Sanjoy, Mcallester, David, ed. In Proceedings of the 30th international conference on machine learning (ICML-13) (Atlanta, GA) 28 (1139–1147). Consultado el 14 de enero de 2016.
↑Spall, J. C. (2000). «Adaptive Stochastic Approximation by the Simultaneous Perturbation Method». IEEE Transactions on Automatic Control45 (10): 1839−1853. doi:10.1109/TAC.2000.880982.
↑Spall, J. C. (2009). «Feedback and Weighting Mechanisms for Improving Jacobian Estimates in the Adaptive Simultaneous Perturbation Algorithm». IEEE Transactions on Automatic Control54 (6): 1216-1229. doi:10.1109/TAC.2009.2019793.