El descenso de gradiente estocástico (a menudo abreviado SGD ) es un método iterativo para optimizar una función objetivo con propiedades de suavidad adecuadas (por ejemplo, diferenciable o subdiferenciable ). Puede considerarse como una aproximación estocástica de la optimización del descenso de gradiente , ya que reemplaza el gradiente real (calculado a partir de todo el conjunto de datos ) por una estimación del mismo (calculado a partir de un subconjunto de datos seleccionado al azar). Especialmente en problemas de optimización de alta dimensión, esto reduce la altísima carga computacional , logrando iteraciones más rápidas a cambio de una tasa de convergencia más baja . [1]
La idea básica detrás de la aproximación estocástica se remonta al algoritmo de Robbins-Monro de la década de 1950. Hoy en día, el descenso de gradiente estocástico se ha convertido en un método de optimización importante en el aprendizaje automático . [2]
Tanto la estimación estadística como el aprendizaje automático consideran el problema de minimizar una función objetivo que tiene forma de suma: donde se quiere estimar el parámetro que minimiza . Cada función sumando normalmente se asocia con la -ésima observación en el conjunto de datos (utilizado para el entrenamiento).
En estadística clásica, los problemas de minimización de suma surgen en mínimos cuadrados y en estimación de máxima verosimilitud (para observaciones independientes). La clase general de estimadores que surgen como minimizadores de sumas se denominan estimadores M. 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 a menudo consideran 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 la minimización de la suma también surge para la minimización empírica del riesgo . Ahí está el valor de la función de pérdida en el ejemplo -ésimo y es el riesgo empírico.
Cuando se usa para minimizar la función anterior, un método de descenso de gradiente estándar (o "por lotes") realizaría las siguientes iteraciones: El tamaño del paso se denota por (a veces llamado tasa de aprendizaje en el aprendizaje automático) y aquí " " denota la actualización de un variable en el algoritmo.
En muchos casos, las funciones sumando tienen una forma simple que permite evaluaciones económicas de la función suma y el gradiente suma. Por ejemplo, en estadística, las familias exponenciales de un parámetro permiten evaluaciones de funciones económicas y evaluaciones de gradientes.
Sin embargo, en otros casos, evaluar el gradiente de suma puede requerir evaluaciones costosas de los gradientes de todas las funciones de sumando. Cuando el conjunto de entrenamiento es enorme y no existen fórmulas simples, evaluar las sumas de gradientes se vuelve muy costoso, porque evaluar el gradiente requiere evaluar todos los gradientes de las funciones de sumando. Para economizar el costo computacional en cada iteración, el descenso de gradiente estocástico toma muestras de un subconjunto de funciones de sumando en cada paso. Esto es muy eficaz en el caso de problemas de aprendizaje automático a gran escala. [4]
En el descenso de gradiente estocástico (o "en línea"), el gradiente verdadero se aproxima mediante 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 sobre el conjunto de entrenamiento hasta que el algoritmo converja. Si se hace esto, los datos se pueden mezclar 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 se puede presentar como:
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 (llamada "mini lote") en cada paso. Esto puede funcionar significativamente mejor que el "verdadero" descenso de gradiente estocástico descrito, porque el código puede hacer uso de bibliotecas de vectorización en lugar de calcular cada paso por separado, como se mostró por primera vez en [6], donde se denominó "el algoritmo de retropropagación en modo agrupado". ". También puede dar como resultado 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 minimización convexa y de aproximación estocástica . En resumen, cuando las tasas de aprendizaje disminuyen a una tasa adecuada y sujetas a supuestos relativamente suaves, el descenso del gradiente estocástico converge casi con seguridad 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. [2] [7] Esto es de hecho una consecuencia del teorema de Robbins-Siegmund. [8]
Supongamos que queremos ajustar una línea recta a un conjunto de entrenamiento con observaciones y las correspondientes respuestas estimadas usando mínimos cuadrados . La función objetivo a minimizar es. La última línea del pseudocódigo anterior para este problema específico será:
Tenga en cuenta que en cada iteración o paso de actualización, el gradiente solo se evalúa en un único . Ésta es la diferencia clave entre el descenso de gradiente estocástico y el descenso de gradiente por lotes.
En 1951, Herbert Robbins y Sutton Monro introdujeron los primeros métodos de aproximación estocástica, anteriores al descenso de gradiente estocástico. [9] Sobre la base de este trabajo, un año después, Jack Kiefer y Jacob Wolfowitz publicaron un algoritmo de optimización muy cercano al descenso de gradiente estocástico, utilizando diferencias centrales como una aproximación del gradiente. [10] Más tarde, en la década de 1950, Frank Rosenblatt utilizó SGD para optimizar su modelo de perceptrón , demostrando la primera aplicabilidad del descenso de gradiente estocástico a redes neuronales. [11]
La retropropagación se describió por primera vez en 1986, y se utilizó el descenso de gradiente estocástico para optimizar de manera eficiente los parámetros en redes neuronales con múltiples capas ocultas . Poco después, se desarrolló otra mejora: el descenso de gradiente de mini lotes, donde se sustituyen muestras individuales por pequeños lotes de datos. En 1997, se exploraron por primera vez los beneficios prácticos de rendimiento de la vectorización que se pueden lograr con lotes tan pequeños, [12] allanando el camino para una optimización eficiente en el aprendizaje automático. A partir de 2023, este enfoque de mini lotes seguirá siendo la norma para entrenar redes neuronales, equilibrando los beneficios del descenso de gradiente estocástico con el descenso de gradiente . [13]
En la década de 1980, el impulso ya se había introducido y se añadió a las técnicas de optimización SGD en 1986. [14] Sin embargo, estas técnicas de optimización asumían hiperparámetros constantes , es decir, una tasa de aprendizaje fija y un parámetro de impulso. En la década de 2010, se introdujeron enfoques adaptativos para aplicar SGD con una tasa de aprendizaje por parámetro con AdaGrad (para "Gradiente adaptativo") en 2011 [15] y RMSprop (para "Propagación cuadrática media") en 2012. [16] En 2014, se publicó Adam (para "Adaptive Moment Estimation"), aplicando los enfoques adaptativos de RMSprop al impulso; Luego se desarrollaron muchas mejoras y ramas de Adam, como Adadelta, Adagrad, AdamW y Adamax. [17] [18]
Dentro del aprendizaje automático, los enfoques de optimización en 2023 estarán dominados por los optimizadores derivados de Adam. TensorFlow y PyTorch, con diferencia las bibliotecas de aprendizaje automático más populares, [19] a partir de 2023 solo incluyen en gran medida optimizadores derivados de Adam, así como predecesores de Adam, como RMSprop y el SGD clásico. PyTorch también admite parcialmente BFGS de memoria limitada , un método de búsqueda de líneas, pero solo para configuraciones de un solo dispositivo sin grupos de parámetros. [18] [20]
El descenso de gradiente estocástico es un algoritmo popular para entrenar una amplia gama de modelos en aprendizaje automático , incluidas máquinas de vectores de soporte (lineales) , regresión logística (ver, por ejemplo, Vowpal Wabbit ) y modelos gráficos . [21] Cuando se combina con el algoritmo de retropropagación , es el algoritmo estándar de facto para entrenar redes neuronales artificiales . [22] Su uso también ha sido reportado en la comunidad de Geofísica , específicamente para aplicaciones de Inversión de Forma de Onda Completa (FWI). [23]
El descenso de gradiente estocástico compite con el algoritmo L-BFGS , [ cita necesaria ] que también se usa ampliamente. El descenso de gradiente estocástico se ha utilizado al menos desde 1960 para entrenar modelos de regresión lineal , originalmente con el nombre de ADALINE . [24]
Otro algoritmo de descenso de gradiente estocástico es el filtro adaptativo de mínimos cuadrados medios (LMS) .
Se han propuesto y utilizado muchas mejoras en el algoritmo básico de descenso de gradiente estocástico. En particular, en el aprendizaje automático, se ha reconocido que es problemática la necesidad de establecer una tasa de aprendizaje (tamaño del paso). Establecer este parámetro demasiado alto puede hacer que el algoritmo diverja; establecerlo demasiado bajo hace que su convergencia sea lenta. [25] Una extensión conceptualmente simple del descenso de gradiente estocástico hace que la tasa de aprendizaje sea una función decreciente η t del número de iteración t , dando un programa de tasa de aprendizaje , de modo que las primeras iteraciones causan grandes cambios en los parámetros, mientras que las últimas solo lo hacen. sintonia FINA. Estos programas se conocen desde el trabajo de MacQueen sobre la agrupación de k -medias . [26] Spall ofrece orientación práctica sobre cómo elegir el tamaño del paso en varias variantes de SGD. [27]
Como se mencionó anteriormente, el descenso de gradiente estocástico clásico generalmente es sensible a la tasa de aprendizaje η . La convergencia rápida requiere altas tasas de aprendizaje, pero esto puede inducir inestabilidad numérica. El problema se puede resolver en gran medida [28] considerando actualizaciones implícitas mediante las cuales el gradiente estocástico se evalúa en la siguiente iteración en lugar de en la actual:
Esta ecuación está implícita ya que aparece en ambos lados de la ecuación. Es una forma estocástica del método del gradiente proximal ya que la actualización también se puede escribir como:
Como ejemplo, considere mínimos cuadrados con características y observaciones . Deseamos resolver: donde indica el producto interno. Tenga en cuenta que podría tener "1" como primer elemento para incluir una intersección. 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 se especifica mal de modo que tenga valores propios absolutos grandes 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) se puede resolver en forma cerrada como:
Este procedimiento permanecerá numéricamente estable prácticamente para todos, ya que la tasa de aprendizaje ahora está 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 mínimos cuadrados medios (LMS) y el filtro de mínimos cuadrados medio normalizado (NLMS) .
Aunque una solución de forma cerrada para ISGD sólo es posible en mínimos cuadrados, el procedimiento se puede implementar de manera eficiente en una amplia gama de modelos. Específicamente, supongamos que depende de solo a través de una combinación lineal con características , de modo que podemos escribir , donde también puede depender pero no de 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 está la función logística . En la regresión de Poisson , etc.
En tales entornos, ISGD se implementa simplemente de la siguiente manera. Sea , donde es escalar. Entonces, ISGD es equivalente a:
El factor de escala se puede encontrar mediante el método de bisección , ya que en la mayoría de los modelos regulares, como los modelos lineales generalizados antes mencionados, la función es decreciente y, por lo tanto, los límites de búsqueda son .
Otras propuestas incluyen el método del impulso o el método de la bola pesada , que en el contexto del aprendizaje automático apareció en el artículo de Rumelhart , Hinton y Williams sobre el aprendizaje por retropropagación [29] y tomó prestada la idea del artículo de 1964 del matemático soviético Boris Polyak sobre la resolución de ecuaciones funcionales. [30] El descenso del 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: [31] [32] que conduce a:
donde se estima el parámetro que minimiza , es un tamaño de paso (a veces llamado tasa de aprendizaje en el aprendizaje automático) y es un factor de caída exponencial entre 0 y 1 que determina la contribución relativa del gradiente actual y los gradientes anteriores al cambio de peso. .
El nombre impulso surge de una analogía con el impulso en física: el vector de peso , considerado como una partícula que viaja a través del espacio de parámetros, [29] sufre aceleración a partir del gradiente de pérdida (" fuerza "). A diferencia del descenso de gradiente estocástico clásico, tiende a seguir viajando en la misma dirección, evitando oscilaciones. Los científicos informáticos han utilizado con éxito Momentum en el entrenamiento de redes neuronales artificiales durante varias décadas. [33] El método del impulso está estrechamente relacionado con la dinámica de Langevin subamortiguada y puede combinarse con el recocido simulado . [34]
A mediados de la década de 1980, Yurii Nesterov modificó el método para usar el gradiente predicho en el siguiente punto, y el resultante, llamado gradiente acelerado de Nesterov, se usó a veces en ML en la década de 2010. [35]
El descenso de gradiente estocástico promediado , inventado de forma independiente por Ruppert y Polyak a finales de los años 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 de gradiente estocástico ordinario, pero el algoritmo también realiza un seguimiento de [36]
Cuando se realiza la optimización, este vector de parámetros promediado toma el lugar de w .
AdaGrad (para algoritmo de gradiente adaptativo) es un algoritmo de descenso de gradiente estocástico modificado con tasa de aprendizaje por parámetro , publicado por primera vez en 2011. [37] De manera informal, esto aumenta la tasa de aprendizaje para parámetros más dispersos [ se necesita aclaración ] y disminuye la tasa de aprendizaje para los que son menos escasos. Esta estrategia a menudo mejora el rendimiento de la convergencia con respecto al descenso de gradiente estocástico estándar en entornos donde los datos son escasos y los parámetros escasos son más informativos. Ejemplos de tales aplicaciones incluyen el procesamiento del lenguaje natural y el reconocimiento de imágenes. [37]
Todavía tiene una tasa de aprendizaje base η , pero esta se multiplica por los elementos de un vector { G j , j } que es la diagonal de la matriz del producto exterior.
donde , el gradiente, en la iteración τ . La diagonal está dada por
Básicamente, este vector almacena 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 ahora es [a] o, escrita como actualizaciones por parámetro, cada { G ( i , i ) } da lugar a un factor de escala para la tasa de aprendizaje que se aplica a un único parámetro wi . Dado que el denominador de este factor es la norma ℓ 2 de las derivadas anteriores, las actualizaciones extremas de parámetros se amortiguan, mientras que los parámetros que reciben pocas o pequeñas actualizaciones reciben tasas de aprendizaje más altas. [33]
Si bien está diseñado para problemas convexos , AdaGrad se ha aplicado con éxito a la optimización no convexa. [38]
RMSProp (por Root Mean Square Propagation) es un método inventado en 2012 por James Martens e Ilya Sutskever , entonces ambos estudiantes de doctorado en el grupo de Geoffrey Hinton, en el que la tasa de aprendizaje , como en Adagrad, se adapta a cada uno de los parámetros. La idea es dividir la tasa de aprendizaje de un peso por un promedio móvil de las magnitudes de los gradientes recientes para ese peso. [39] Inusualmente, no se publicó en un artículo, sino que simplemente se describió en una conferencia de Coursera . [ cita necesaria ]
Entonces, primero se calcula el promedio móvil en términos de medias cuadráticas,
donde, es el factor de olvido. El concepto de almacenar el gradiente histórico como suma de cuadrados se toma prestado de Adagrad, pero se introduce el "olvido" para resolver las tasas de aprendizaje decrecientes de Adagrad en problemas no convexos al disminuir gradualmente la influencia de los datos antiguos. [ cita necesaria ]
Y los parámetros se actualizan como,
RMSProp ha demostrado una buena adaptación de la tasa de aprendizaje en diferentes aplicaciones. RMSProp puede verse como una generalización de Rprop y es capaz de trabajar también con minilotes, en lugar de solo con lotes completos. [39]
Adam [40] (abreviatura de Adaptive Moment Estimation) es una actualización de 2014 del optimizador RMSProp que lo combina con la característica principal del método Momentum . [41] En este algoritmo de optimización, se utilizan promedios móviles 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 , donde indexa la iteración de entrenamiento actual (indexada en ), la actualización de parámetros de Adam viene dada por:
donde es un escalar pequeño (p. ej. ) utilizado para evitar la división por 0, y (p. ej. 0,9) y (p. ej. 0,999) son los factores de olvido para gradientes y segundos momentos de gradientes, respectivamente. La aplicación de raíces cuadradas y cuadradas se realiza por elementos.
La prueba inicial que establecía la convergencia de Adán era incompleta y el análisis posterior ha revelado que Adán no converge para todos los objetivos convexos. [42] [43] A pesar de esto, Adam continúa utilizándose en la práctica debido a su sólido desempeño en la práctica. [44]
La popularidad de Adam inspiró muchas variantes y mejoras. Algunos ejemplos incluyen:
Aunque la optimización basada en signos se remonta al mencionado Rprop , en 2018 los investigadores intentaron simplificar a Adam eliminando la magnitud del gradiente estocástico de ser tenido en cuenta y considerando solo su signo. [53] [54]
La búsqueda de líneas de retroceso es otra variante del descenso de gradiente. Todo lo que aparece a continuación proviene del enlace mencionado. Se basa en una condición conocida como 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 de líneas de retroceso utiliza evaluaciones de funciones para verificar la condición de Armijo y, en principio, el bucle en el algoritmo para determinar las tasas de aprendizaje puede ser largo y desconocido de antemano. El SGD adaptativo no necesita un bucle para determinar las tasas de aprendizaje. Por otro lado, el SGD adaptativo no garantiza la "propiedad de descenso", de la que disfruta la búsqueda de línea de retroceso, que es para todos n. Si el gradiente de la función de costos es globalmente continuo de Lipschitz, con la constante de Lipschitz L, 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 de líneas de retroceso.
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 contexto de la aproximación estocástica [ cita necesaria ] . Byrd, Hansen, Nocedal y Singer desarrollaron un método que utiliza mediciones directas de las matrices de Hesse de los sumandos en la función de riesgo empírico. [55] Sin embargo, en la práctica puede no ser posible determinar directamente las matrices de Hesse necesarias para la optimización. Spall y otros proporcionan métodos prácticos y teóricamente sólidos para versiones de segundo orden de SGD que no requieren información directa de Hesse. [56] [57] [58] (Ruppert ofrece un método menos eficiente basado en diferencias finitas, en lugar de perturbaciones simultáneas. [59] ) Otro enfoque para la aproximación de la matriz de Hesse es reemplazarla con la matriz de información de Fisher, que transforma el degradado habitual en natural. [60] Estos métodos que no requieren información directa de Hesse se basan en valores de los sumandos en la función de riesgo empírica anterior o en valores de los gradientes de los sumandos (es decir, las entradas del SGD). En particular, la optimización de segundo orden se puede lograr asintóticamente sin el cálculo directo de las matrices hessianas de los sumandos en la función de riesgo empírica.
Para una tasa de aprendizaje pequeña, el descenso de gradiente estocástico puede verse como una discretización de la ODE de flujo de gradiente .
sujeto a ruido estocástico adicional. Esta aproximación sólo es válida en un horizonte de tiempo finito en el siguiente sentido: supongamos que todos los coeficientes son suficientemente suaves. Sea y sea una función de prueba suficientemente fluida. Entonces existe una constante tal que para todo
donde denota la expectativa con respecto a la elección aleatoria de índices en el esquema de descenso de gradiente estocástico.
Dado que esta aproximación no captura las fluctuaciones aleatorias alrededor del comportamiento medio del descenso de gradiente estocástico, se han propuesto soluciones a ecuaciones diferenciales estocásticas (SDE) como objetos limitantes. [61] Más precisamente, la solución al SDE
porque donde denota la integral Ito con respecto a un movimiento browniano es una aproximación más precisa en el sentido de que existe una constante tal que
Sin embargo, este SDE sólo se aproxima al movimiento de un punto del descenso de gradiente estocástico. Para una aproximación del flujo estocástico hay que considerar SDE con ruido de dimensión infinita. [62]
{{cite journal}}
: Citar diario requiere |journal=
( ayuda ){{cite journal}}
: Citar diario requiere |journal=
( ayuda ){{cite book}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: Citar diario requiere |journal=
( ayuda ){{cite journal}}
: Citar diario requiere |journal=
( ayuda ){{cite journal}}
: Citar diario requiere |journal=
( ayuda )