Descenso de gradiente estocástico

Algoritmo de optimización

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]

Fondo

Tanto la estimación estadística como el aprendizaje automático consideran el problema de minimizar una función objetivo que tiene la forma de una suma:

$${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w),}$$

estimar el parámetroobservaciónconjunto de datos ${\displaystyle w}$ ${\displaystyle Q(w)}$ ${\displaystyle Q_{i}}$ ${\displaystyle i}$

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. ${\displaystyle Q_{i}(w)}$ ${\displaystyle i}$ ${\displaystyle Q(w)}$

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:

$${\displaystyle w:=w-\eta \,\nabla Q(w)=w-{\frac {\eta }{n}}\sum _{i=1}^{n}\nabla Q_{i}(w).}$$

tasa de aprendizaje ${\displaystyle \eta }$ ${\displaystyle :=}$

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]

método iterativo

Las fluctuaciones en la función objetivo total se toman como pasos de gradiente con respecto a los minilotes.

En el descenso de gradiente estocástico (o "en línea"), el gradiente verdadero se aproxima mediante un gradiente en una sola muestra: ${\displaystyle Q(w)}$

$${\displaystyle w:=w-\eta \,\nabla Q_{i}(w).}$$

tasa de aprendizaje adaptativa^[5]

En pseudocódigo, el descenso de gradiente estocástico se puede presentar como:

• Elija un vector inicial de parámetros y tasa de aprendizaje . ${\displaystyle w}$ ${\displaystyle \eta }$
• Repetir hasta obtener un mínimo aproximado:
  • Mezcla aleatoriamente muestras en el conjunto de entrenamiento.
  • Para hacer: ${\displaystyle i=1,2,...,n}$
    • ${\displaystyle w:=w-\eta \,\nabla Q_{i}(w).}$

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 descenso de gradiente estocástico "verdadero" 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 propagación hacia atrás 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] ${\displaystyle \eta }$

Ejemplo

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 ${\displaystyle {\hat {y}}=w_{1}+w_{2}x}$ ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ ${\displaystyle ({\hat {y}}_{1},{\hat {y}}_{2},\ldots ,{\hat {y}}_{n})}$

$${\displaystyle Q(w)=\sum _{i=1}^{n}Q_{i}(w)=\sum _{i=1}^{n}\left({\hat {y}}_{i}-y_{i}\right)^{2}=\sum _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\right)^{2}.}$$

$${\displaystyle {\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}:={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}{\frac {\partial }{\partial w_{1}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\\{\frac {\partial }{\partial w_{2}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\end{bmatrix}}={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}2(w_{1}+w_{2}x_{i}-y_{i})\\2x_{i}(w_{1}+w_{2}x_{i}-y_{i})\end{bmatrix}}.}$$

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. ${\displaystyle x_{i}}$

Historia

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]}

Aplicaciones notables

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) .

Extensiones y variantes

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]

Un gráfico que visualiza el comportamiento de un conjunto seleccionado de optimizadores, utilizando una proyección en perspectiva 3D de una función de pérdida f(x, y).

Un gráfico que visualiza el comportamiento de un conjunto seleccionado de optimizadores.

Actualizaciones implícitas (ISGD)

Como se mencionó anteriormente, el descenso de gradiente estocástico clásico es generalmente 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:

$${\displaystyle w^{\text{new}}:=w^{\text{old}}-\eta \,\nabla Q_{i}(w^{\rm {new}}).}$$

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: ${\displaystyle w^{\rm {new}}}$

$${\displaystyle w^{\text{new}}:=\arg \min _{w}\left\{Q_{i}(w)+{\frac {1}{2\eta }}\left\|w-w^{\text{old}}\right\|^{2}\right\}.}$$

Como ejemplo, considere mínimos cuadrados con características y observaciones . Deseamos resolver: ${\displaystyle x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}}$ ${\displaystyle y_{1},\ldots ,y_{n}\in \mathbb {R} }$

$${\displaystyle \min _{w}\sum _{j=1}^{n}\left(y_{j}-x_{j}'w\right)^{2},}$$

${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$ ${\displaystyle x}$

$${\displaystyle w^{\text{new}}=w^{\text{old}}+\eta \left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}}$$

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 tiene 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: ${\displaystyle i}$ ${\displaystyle n}$ ${\displaystyle \eta }$ ${\displaystyle I-\eta x_{i}x_{i}'}$

$${\displaystyle w^{\text{new}}=w^{\text{old}}+{\frac {\eta }{1+\eta \left\|x_{i}\right\|^{2}}}\left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}.}$$

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) . ${\displaystyle \eta }$

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. ${\displaystyle Q_{i}(w)}$ ${\displaystyle w}$ ${\displaystyle x_{i}}$ ${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}}$ ${\displaystyle q()\in \mathbb {R} }$ ${\displaystyle x_{i},y_{i}}$ ${\displaystyle w}$ ${\displaystyle x_{i}'w}$ ${\displaystyle q(x_{i}'w)=y_{i}-x_{i}'w}$ ${\displaystyle q(x_{i}'w)=y_{i}-S(x_{i}'w)}$ ${\displaystyle S(u)=e^{u}/(1+e^{u})}$ ${\displaystyle q(x_{i}'w)=y_{i}-e^{x_{i}'w}}$

En tales entornos, ISGD se implementa simplemente de la siguiente manera. Sea , donde es escalar. Entonces, ISGD es equivalente a: ${\displaystyle f(\xi )=\eta q(x_{i}'w^{old}+\xi \|x_{i}\|^{2})}$ ${\displaystyle \xi }$

$${\displaystyle w^{\text{new}}=w^{\text{old}}+\xi ^{\ast }x_{i},~{\text{where}}~\xi ^{\ast }=f(\xi ^{\ast }).}$$

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 . ${\displaystyle \xi ^{\ast }\in \mathbb {R} }$ ${\displaystyle q()}$ ${\displaystyle \xi ^{\ast }}$ ${\displaystyle [\min(0,f(0)),\max(0,f(0))]}$

Impulso

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 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: ^{[31] [32]}

$${\displaystyle \Delta w:=\alpha \Delta w-\eta \,\nabla Q_{i}(w)}$$

$${\displaystyle w:=w+\Delta w}$$

$${\displaystyle w:=w-\eta \,\nabla Q_{i}(w)+\alpha \Delta w}$$

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. . ${\displaystyle w}$ ${\displaystyle Q(w)}$ ${\displaystyle \eta }$ ${\displaystyle \alpha }$

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 una 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 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] ${\displaystyle w}$

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]

promediando

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]

$${\displaystyle {\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}.}$$

w

adagrad

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.

$${\displaystyle G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T}}}$$

donde , el gradiente, en la iteración τ . La diagonal está dada por ${\displaystyle g_{\tau }=\nabla Q_{i}(w)}$

$${\displaystyle G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}.}$$

^[a]

$${\displaystyle w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\odot g}$$

$${\displaystyle w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.}$$

{ G _{( i , i )} }w _inorma ℓ 2^[33] ${\textstyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$

Si bien está diseñado para problemas convexos , AdaGrad se ha aplicado con éxito a la optimización no convexa. ^[38]

RMSProp

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,

$${\displaystyle v(w,t):=\gamma v(w,t-1)+\left(1-\gamma \right)\left(\nabla Q_{i}(w)\right)^{2}}$$

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. ^[40] ${\displaystyle \gamma }$

Y los parámetros se actualizan como,

$${\displaystyle w:=w-{\frac {\eta }{\sqrt {v(w,t)}}}\nabla Q_{i}(w)}$$

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]

Adán

Adam ^[41] (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 . ^[42] 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: ${\displaystyle w^{(t)}}$ ${\displaystyle L^{(t)}}$ ${\displaystyle t}$ ${\displaystyle 0}$

$${\displaystyle m_{w}^{(t+1)}\leftarrow \beta _{1}m_{w}^{(t)}+\left(1-\beta _{1}\right)\nabla _{w}L^{(t)}}$$

$${\displaystyle v_{w}^{(t+1)}\leftarrow \beta _{2}v_{w}^{(t)}+\left(1-\beta _{2}\right)\left(\nabla _{w}L^{(t)}\right)^{2}}$$

$${\displaystyle {\hat {m}}_{w}={\frac {m_{w}^{(t+1)}}{1-\beta _{1}^{t}}}}$$

$${\displaystyle {\hat {v}}_{w}={\frac {v_{w}^{(t+1)}}{1-\beta _{2}^{t}}}}$$

$${\displaystyle w^{(t+1)}\leftarrow w^{(t)}-\eta {\frac {{\hat {m}}_{w}}{{\sqrt {{\hat {v}}_{w}}}+\epsilon }}}$$

${\displaystyle \epsilon }$ ${\displaystyle 10^{-8}}$ ${\displaystyle \beta _{1}}$ ${\displaystyle \beta _{2}}$

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. ^{[43] [44]} A pesar de esto, Adam continúa utilizándose en la práctica debido a su sólido desempeño en la práctica. ^[45] Además, la profunda influencia de este algoritmo inspiró múltiples esquemas de optimización basados ​​en el impulso más nuevos y menos conocidos que utilizan gradientes mejorados por Nesterov (por ejemplo: NAdam ^[46] y FASFA ^[47] ) y diversas interpretaciones de la información de segundo orden. (por ejemplo: Powerpropagation ^[48] y AdaSqrt ^[49] ). Sin embargo, las variantes más comúnmente utilizadas son AdaMax , ^[41] que generaliza a Adam usando la norma infinita, y AMSGrad , ^[50] que aborda los problemas de convergencia de Adam usando el máximo de gradientes cuadrados del pasado en lugar del promedio exponencial. ^[51] AdamW ^[52] es una actualización posterior que mitiga una elección no óptima del algoritmo de disminución de peso en Adam .

Descenso de gradiente estocástico basado en signos

Aunque la optimización basada en signos se remonta al Rprop antes mencionado, en 2018 los investigadores intentaron simplificar a Adam eliminando la magnitud del gradiente estocástico y considerando solo su signo. ^{[53] [54]}

Búsqueda de línea de retroceso

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. ${\displaystyle f(x_{n+1})\leq f(x_{n})}$

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 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.

Aproximaciones en tiempo continuo

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. ${\textstyle \eta }$ ${\textstyle (w_{n})_{n\in \mathbb {N} _{0}}}$

$${\displaystyle {\frac {d}{dt}}W_{t}=-\nabla Q(W_{t})}$$

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 ${\textstyle Q_{i}}$ ${\textstyle T>0}$ ${\textstyle g:\mathbb {R} ^{d}\to \mathbb {R} }$ ${\textstyle C>0}$ ${\textstyle \eta >0}$

$${\displaystyle \max _{k=0,\dots ,\lfloor T/\eta \rfloor }\left|\mathbb {E} [g(w_{k})]-g(W_{k\eta })\right|\leq C\eta ,}$$

donde denota la expectativa con respecto a la elección aleatoria de índices en el esquema de descenso de gradiente estocástico. ${\textstyle \mathbb {E} }$

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

$${\displaystyle dW_{t}=-\nabla \left(Q(W_{t})+{\tfrac {1}{4}}\eta |\nabla Q(W_{t})|^{2}\right)dt+{\sqrt {\eta }}\Sigma (W_{t})^{1/2}dB_{t},}$$

para

$${\displaystyle \Sigma (w)={\frac {1}{n^{2}}}\left(\sum _{i=1}^{n}Q_{i}(w)-Q(w)\right)\left(\sum _{i=1}^{n}Q_{i}(w)-Q(w)\right)^{T}}$$

integral Itomovimiento browniano ${\textstyle dB_{t}}$ ${\textstyle C>0}$

$${\displaystyle \max _{k=0,\dots ,\lfloor T/\eta \rfloor }\left|\mathbb {E} [g(w_{k})]-\mathbb {E} [g(W_{k\eta })]\right|\leq C\eta ^{2}.}$$

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]

Ver también

• Búsqueda de línea de retroceso
• Ley de escala neuronal rota
• Descenso de coordenadas : cambia una coordenada a la vez, en lugar de un ejemplo
• clasificador lineal
• Aprendizaje automático en línea
• Escalada de colinas estocástica
• Reducción de la varianza estocástica

Notas

1. denota el producto de elementos . ${\displaystyle \odot }$

Referencias

1. Bottou, León ; Bousquet, Olivier (2012). "Las ventajas y desventajas del aprendizaje a gran escala". En Sra, Suvrit; Nowozin, Sebastián; Wright, Stephen J. (eds.). Optimización para el aprendizaje automático . Cambridge: Prensa del MIT. págs. 351–368. ISBN 978-0-262-01646-9.
2. Bottou, León (1998). "Algoritmos online y aproximaciones estocásticas". Aprendizaje en línea y redes neuronales . Prensa de la Universidad de Cambridge. ISBN 978-0-521-65263-6.
3. Ferguson, Thomas S. (1982). "Una estimación de máxima verosimilitud inconsistente". Revista de la Asociación Estadounidense de Estadística . 77 (380): 831–834. doi :10.1080/01621459.1982.10477894. JSTOR  2287314.
4. Bottou, León ; Bousquet, Olivier (2008). Las ventajas y desventajas del aprendizaje a gran escala. Avances en los sistemas de procesamiento de información neuronal . vol. 20. págs. 161-168.
5. Murphy, Kevin (2021). Aprendizaje automático probabilístico: una introducción. Prensa del MIT . Consultado el 10 de abril de 2021 .
6. Bilmes, Jeff; Asanovic, Krste; Chin, Chee-Whye; Demmel, James (abril de 1997). "Uso de PHiPAC para acelerar el aprendizaje de retropropagación de errores". 1997 Conferencia internacional IEEE sobre acústica, voz y procesamiento de señales . ICASP. Múnich, Alemania: IEEE. págs. 4153–4156 vol.5. doi :10.1109/ICASSP.1997.604861.
7. Kiwiel, Krzysztof C. (2001). "Convergencia y eficiencia de métodos subgradientes para minimización cuasiconvexa". Programación Matemática, Serie A. Berlín, Heidelberg: Springer. 90 (1): 1–25. doi :10.1007/PL00011414. ISSN  0025-5610. SEÑOR  1819784. S2CID  10043417.
8. Robbins, Herbert ; Siegmund, David O. (1971). "Un teorema de convergencia para casi supermartingalas no negativas y algunas aplicaciones". En Rustagi, Jagdish S. (ed.). Optimización de métodos en estadística . Prensa académica. ISBN 0-12-604550-X.
9. Robbins, H .; Monro, S. (1951). "Un método de aproximación estocástica". Los anales de la estadística matemática . 22 (3): 400. doi : 10.1214/aoms/1177729586 .
10. Kiefer, J.; Wolfowitz, J. (1952). "Estimación estocástica del máximo de una función de regresión". Los anales de la estadística matemática . 23 (3): 462–466. doi : 10.1214/aoms/1177729392 .
11. Rosenblatt, F. (1958). "El perceptrón: un modelo probabilístico para el almacenamiento y organización de información en el cerebro". Revisión psicológica . 65 (6): 386–408. doi :10.1037/h0042519. S2CID  12781225.
12. Bilmes, Jeff; Asanovic, Krste; Chin, Chee-Whye; Demmel, James (abril de 1997). "Uso de PHiPAC para acelerar el aprendizaje de retropropagación de errores". 1997 Conferencia internacional IEEE sobre acústica, voz y procesamiento de señales . ICASP. Múnich, Alemania: IEEE. págs. 4153–4156 vol.5. doi :10.1109/ICASSP.1997.604861.
13. Peng, Xinyu; Li, Li; Wang, Fei-Yue (2020). "Aceleración del descenso de gradiente estocástico de minibatch mediante muestreo de tipicidad". Transacciones IEEE sobre redes neuronales y sistemas de aprendizaje . 31 (11): 4649–4659. arXiv : 1903.04192 . doi :10.1109/TNNLS.2019.2957003. PMID  31899442. S2CID  73728964 . Consultado el 2 de octubre de 2023 .
14. Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (octubre de 1986). "Aprendizaje de representaciones mediante errores de retropropagación". Naturaleza . 323 (6088): 533–536. doi :10.1038/323533a0. ISSN  1476-4687. S2CID  205001834.
15. Duchi, John; Hazán, Elad; Cantante, Yoram (2011). "Métodos adaptativos de subgradiente para el aprendizaje en línea y la optimización estocástica" (PDF) . JMLR . 12 : 2121–2159.
16. Hinton, Geoffrey . "Conferencia 6e rmsprop: Divida el gradiente por un promedio móvil de su magnitud reciente" (PDF) . pag. 26 . Consultado el 19 de marzo de 2020 .
17. Kingma, Diederik; Ba, Jimmy (2014). "Adam: un método para la optimización estocástica". arXiv : 1412.6980 [cs.LG].
18. "torch.optim - documentación de PyTorch 2.0". pytorch.org . Consultado el 2 de octubre de 2023 .
19. Nguyen, Giang; Dlugolinsky, Stefan; Bobák, Martín; Tran, vietnamita; García, Álvaro; Heredia, Ignacio; Malik, Peter; Hluchý, Ladislav (19 de enero de 2019). "Marcos y bibliotecas de aprendizaje automático y aprendizaje profundo para la minería de datos a gran escala: una encuesta" (PDF) . Revisión de inteligencia artificial . 52 : 77-124. doi :10.1007/s10462-018-09679-z. S2CID  254236976.
20. "Módulo: tf.keras.optimizers | TensorFlow v2.14.0". TensorFlow . Consultado el 2 de octubre de 2023 .
21. Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning (2008). Análisis de campos aleatorio condicional, eficiente y basado en funciones. Proc. Reunión Anual de la ACL.
22. LeCun, Yann A. y col. "Retroceso eficiente". Redes neuronales: trucos del oficio. Springer Berlín Heidelberg, 2012. 9-48
23. Jerome R. Krebs, John E. Anderson, David Hinkley, Ramesh Neelamani, Sunwoong Lee, Anatoly Baumstein y Martin-Daniel Lacasse, (2009), "Inversión sísmica rápida de campo de onda completo utilizando fuentes codificadas", GEOFÍSICA 74: WCC177- CMI188.
24. Avi Pfeffer. "CS181 Conferencia 5: Perceptrones" (PDF) . Universidad Harvard.^{[ enlace muerto permanente ]}
25. Buen compañero, Ian ; Bengio, Yoshua; Courville, Aarón (2016). Aprendizaje profundo. Prensa del MIT. pag. 291.ISBN _ 978-0262035613.
26. Citado por Darken, Christian; Moody, John (1990). "Agrupación rápida y adaptativa de k-medias: algunos resultados empíricos ". Conferencia Conjunta Internacional. sobre redes neuronales (IJCNN). IEEE. doi :10.1109/IJCNN.1990.137720.
27. Spall, JC (2003). Introducción a la búsqueda y optimización estocástica: estimación, simulación y control . Hoboken, Nueva Jersey: Wiley. págs. Secciones 4.4, 6.6 y 7.5. ISBN 0-471-33052-3.
28. Toulis, Panos; Airoldi, Eduardo (2017). "Propiedades asintóticas y de muestras finitas de estimadores basados ​​en gradientes estocásticos". Anales de Estadística . 45 (4): 1694-1727. arXiv : 1408.2923 . doi :10.1214/16-AOS1506. S2CID  10279395.
29. Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (8 de octubre de 1986). "Aprendizaje de representaciones mediante errores de retropropagación". Naturaleza . 323 (6088): 533–536. Código Bib :1986Natur.323..533R. doi :10.1038/323533a0. S2CID  205001834.
30. "Descenso de gradiente e impulso: el método de la bola pesada". 13 de julio de 2020.
31. Sutskever, Ilya; Martens, James; Dahl, George; Hinton, Geoffrey E. (junio de 2013). Sanjoy Dasgupta y David Mccallester (ed.). Sobre la importancia de la inicialización y el impulso en el aprendizaje profundo (PDF) . En Actas de la 30ª conferencia internacional sobre aprendizaje automático (ICML-13). vol. 28. Atlanta, Georgia. págs. 1139-1147 . Consultado el 14 de enero de 2016 .
32. Sutskever, Ilya (2013). Entrenamiento de redes neuronales recurrentes (PDF) (Ph.D.). Universidad de Toronto. pag. 74.
33. Zeiler, Matthew D. (2012). "ADADELTA: Un método de tasa de aprendizaje adaptativo". arXiv : 1212.5701 [cs.LG].
34. Borysenko, Oleksandr; Byshkin, Maksym (2021). "CoolMomentum: un método para la optimización estocástica mediante Langevin Dynamics con recocido simulado". Informes científicos . 11 (1): 10705. arXiv : 2005.14605 . Código Bib : 2021NatSR..1110705B. doi :10.1038/s41598-021-90144-3. PMC 8139967 . PMID  34021212. 
35. "Documentos con código: explicación del gradiente acelerado de Nesterov".
36. Polyak, Boris T.; Juditsky, Anatoli B. (1992). "Aceleración de la aproximación estocástica mediante promediación" (PDF) . SIAM J. Control Optim . 30 (4): 838–855. doi :10.1137/0330046. S2CID  3548228. Archivado desde el original (PDF) el 12 de enero de 2016 . Consultado el 14 de febrero de 2018 .
37. Duchi, John; Hazán, Elad; Cantante, Yoram (2011). "Métodos adaptativos de subgradiente para el aprendizaje en línea y la optimización estocástica" (PDF) . JMLR . 12 : 2121–2159.
38. Gupta, Maya R.; Bengio, Samy; Weston, Jason (2014). "Formación de clasificadores altamente multiclase" (PDF) . JMLR . 15 (1): 1461-1492.
39. Hinton, Geoffrey . "Conferencia 6e rmsprop: Divida el gradiente por un promedio móvil de su magnitud reciente" (PDF) . pag. 26 . Consultado el 19 de marzo de 2020 .
40. "Comprensión de RMSprop: aprendizaje de redes neuronales más rápido". 2 de septiembre de 2018.
41. Kingma, Diederik; Ba, Jimmy (2014). "Adam: un método para la optimización estocástica". arXiv : 1412.6980 [cs.LG].
42. "4. Más allá del descenso del gradiente: fundamentos del aprendizaje profundo [libro]".
43. Reddi, Sashank J.; Kale, Satyen; Kumar, Sanjiv (2018). Sobre la convergencia de Adán y el más allá. 6ta Conferencia Internacional sobre Representaciones del Aprendizaje (ICLR 2018). arXiv : 1904.09237 .
44. Rubio, David Martínez (2017). Análisis de convergencia de un método adaptativo de descenso de gradientes (PDF) (tesis de maestría). Universidad de Oxford . Consultado el 5 de enero de 2024 .
45. Zhang, Yushun; Chen, Congliang; Shi, Naichen; Sol, Ruoyu; Luo, Zhi-Quan (2022). "Adam puede converger sin ninguna modificación en las reglas de actualización". Avances en los sistemas de procesamiento de información neuronal 35 . Avances en los sistemas de procesamiento de información neuronal 35 (NeurIPS 2022). arXiv : 2208.09632 .
46. Dozat, T. (2016). "Incorporando Nesterov Momentum en Adam". S2CID  70293087. {{cite journal}}: Citar diario requiere |journal=( ayuda )
47. Naveen, Philip (9 de agosto de 2022). "FASFA: un novedoso optimizador de retropropagación de próxima generación". doi :10.36227/techrxiv.20427852.v1 . Consultado el 19 de noviembre de 2022 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
48. Whye, Schwarz, Jonathan Jayakumar, Siddhant M. Pascanu, Razvan Latham, Peter E. Teh, Yee (1 de octubre de 2021). Propagación de energía: una escasez que induce la reparametrización del peso. OCLC  1333722169.{{cite book}}: CS1 maint: multiple names: authors list (link)
49. Hu, Yuzheng; Lin, Licong; Tang, Shange (20 de diciembre de 2019). "Información de segundo orden en métodos de optimización de primer orden". arXiv : 1912.09926 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
50. Reddi, Sashank J.; Kale, Satyen; Kumar, Sanjiv (2018). "Sobre la convergencia de Adán y más allá". arXiv : 1904.09237 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
51. "Una descripción general de los algoritmos de optimización del descenso de gradientes". 19 de enero de 2016.
52. Loshchilov, Ilya; Hutter, Frank (4 de enero de 2019). "Regularización de la caída de peso desacoplada". arXiv : 1711.05101 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
53. Balles, Lucas; Hennig, Philipp (15 de febrero de 2018). "Disección de Adán: el signo, la magnitud y la variación de los gradientes estocásticos".
54. "SignSGD: optimización comprimida para problemas no convexos". 3 de julio de 2018. págs. 560–569.
55. Byrd, derecha; Hansen, SL; Nocedal, J.; Cantante, Y. (2016). "Un método estocástico cuasi-Newton para la optimización a gran escala". Revista SIAM sobre Optimización . 26 (2): 1008–1031. arXiv : 1401.7020 . doi :10.1137/140954362. S2CID  12396034.
56. Spall, JC (2000). "Aproximación estocástica adaptativa por el método de perturbación simultánea". Transacciones IEEE sobre control automático . 45 (10): 1839-1853. doi :10.1109/TAC.2000.880982.
57. Spall, JC (2009). "Mecanismos de ponderación y retroalimentación para mejorar las estimaciones jacobianas en el algoritmo adaptativo de perturbación simultánea". Transacciones IEEE sobre control automático . 54 (6): 1216-1229. doi :10.1109/TAC.2009.2019793. S2CID  3564529.
58. Bhatnagar, S.; Prasad, HL; Prashanth, Luisiana (2013). Algoritmos estocásticos recursivos para la optimización: métodos de perturbación simultánea . Londres: Springer. ISBN 978-1-4471-4284-3.
59. Ruppert, D. (1985). "Una versión de Newton-Raphson del procedimiento multivariado de Robbins-Monro". Anales de Estadística . 13 (1): 236–245. doi : 10.1214/aos/1176346589 .
60. Amari, S. (1998). "El gradiente natural funciona de manera eficiente en el aprendizaje". Computación neuronal . 10 (2): 251–276. doi :10.1162/089976698300017746. S2CID  207585383.
61. Li, Qianxiao; Tai, Cheng; E, Weinan (2019). "Ecuaciones estocásticas modificadas y dinámica de algoritmos de gradiente estocástico I: fundamentos matemáticos". Revista de investigación sobre aprendizaje automático . 20 (40): 1–47. ISSN  1533-7928.
62. Gess, Benjamín; Kassing, Sebastián; Konarovskyi, Vitalii (14 de febrero de 2023). "Flujos estocásticos modificados, límites de campo medio y dinámica del descenso del gradiente estocástico". arXiv : 2302.07125 [matemáticas.PR].

Otras lecturas

• Bottou, Léon (2004), "Aprendizaje estocástico", Conferencias avanzadas sobre aprendizaje automático , LNAI, vol. 3176, Springer, págs. 146-168, ISBN 978-3-540-23122-6
• Buduma, Nikhil; Locascio, Nicholas (2017), "Más allá del descenso del gradiente", Fundamentos del aprendizaje profundo: diseño de algoritmos de inteligencia artificial de próxima generación , O'Reilly, ISBN 9781491925584
• LeCun, Yann A .; Bottou, León; Orr, Genevieve B.; Müller, Klaus-Robert (2012), "Efficient BackProp", Redes neuronales: trucos del oficio , Springer, págs. 9–48, ISBN 978-3-642-35288-1
• Spall, James C. (2003), Introducción a la búsqueda y optimización estocástica , Wiley , ISBN 978-0-471-33052-3

enlaces externos

• Uso de descenso de gradiente estocástico en C++, Boost, Ublas para regresión lineal
• Algoritmos de aprendizaje automático
• "Descenso de gradiente, cómo aprenden las redes neuronales". 3Azul1Marrón . 16 de octubre de 2017. Archivado desde el original el 22 de diciembre de 2021, a través de YouTube .
• Goh (4 de abril de 2017). "Por qué Momentum realmente funciona". Destilar . 2 (4). doi : 10.23915/distill.00006 .Documento interactivo que explica el impulso.