Descenso de gradiente estocástico

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

Antecedentes

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),}$

en la que el parámetro ${\displaystyle w}$ que minimiza ${\displaystyle Q(w)}$ será estimado. Cada una de las funciones sumando ${\displaystyle Q_{i}}$ suele estar asociada a la observación ${\displaystyle i}$-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 ${\displaystyle Q_{i}(w)}$ es el valor de la función de pérdida en el ejemplo de ${\displaystyle i}$-n, y ${\displaystyle Q(w)}$ 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:

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

donde ${\displaystyle \eta }$ 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 ${\displaystyle Q(w)}$ se aproxima por un gradiente en una sola muestra:

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

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 ${\displaystyle w}$ y tasa de aprendizaje ${\displaystyle \eta }$.
• Repita la operación hasta obtener un mínimo aproximado:
  • Barajar aleatoriamente las muestras del conjunto de entrenamiento.
  • Para ${\displaystyle i=1,2,...,n}$, realizar:
    • ${\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 (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 ${\displaystyle \eta }$ 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 ${\displaystyle {\hat {y}}=\!w_{1}+w_{2}x}$ a un conjunto de entrenamiento con observaciones ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$ y las correspondientes respuestas estimadas ${\displaystyle ({\hat {y_{1}}},{\hat {y_{2}}},\ldots ,{\hat {y_{n}}})}$ utilizando mínimos cuadrados. La función objetivo a minimizar es:

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

La última línea del pseudocódigo anterior para este problema específico se convertirá en:

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

Nótese que en cada iteración (también llamada actualización), el gradiente sólo se evalúa en un único punto ${\displaystyle x_{i}}$ 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.

Aplicaciones destacadas

El descenso de gradiente estocástico es un algoritmo popular para entrenar una amplia gama de modelos de aprendizaje automático, incluyendo las máquinas de vectores de soporte (lineales), la regresión logística (véase, por ejemplo, Vowpal Wabbit) y los modelos en grafo.[10]​ Combinado con el algoritmo de retropropagación, es el algoritmo estándar de facto para el entrenamiento de redes neuronales artificiales.[11]​ También se ha informado de su uso en la comunidad geofísica, concretamente en aplicaciones de inversión de forma de onda completa (en inglés: Full Waveform Inversion, FWI).[12]​

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 ${\displaystyle n_{t}}$ del número de iteraciones ${\displaystyle t}$, 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 ${\displaystyle k}$-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 ${\displaystyle n}$. 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:

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

Esta ecuación está implícita ya que ${\displaystyle w^{\rm {new}}}$ 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:

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

A modo de ejemplo, consideremos los mínimos cuadrados con características ${\displaystyle x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}}$ y observaciones ${\displaystyle y_{1},\ldots ,y_{n}\in \mathbb {R} }$. Queremos resolver:

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

en el que ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$ indica el producto interior. Obsérvese que ${\displaystyle x}$ podría tener "1" como primer elemento para incluir un intercepto. El descenso de gradiente estocástico clásico procede de la siguiente manera:

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

donde ${\displaystyle i}$ se muestrea uniformemente entre 1 y ${\displaystyle n}$. 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 ${\displaystyle n}$ está mal especificado de modo que ${\displaystyle I-\eta x_{i}x_{i}'}$ 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:

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

Este procedimiento se mantendrá numéricamente estable prácticamente para todas las ${\displaystyle n}$ 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 ${\displaystyle Q_{i}(w)}$ depende de ${\displaystyle w}$ sólo a través de una combinación lineal con las características ${\displaystyle x_{i}}$, de modo que podemos escribir ${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}}$, donde ${\displaystyle q()\in \mathbb {R} }$ puede depender de ${\displaystyle x_{i},y_{i}}$ pero no en ${\displaystyle w}$ excepto a través de ${\displaystyle x_{i}'w}$. 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, ${\displaystyle q(x_{i}'w)=y_{i}-x_{i}'w}$ y en regresión logística ${\displaystyle q(x_{i}'w)=y_{i}-S(x_{i}'w)}$, donde ${\displaystyle S(u)=e^{u}/(1+e^{u})}$ es la función logística. En la regresión de Poisson ${\displaystyle q(x_{i}'w)=y_{i}-e^{x_{i}'w}}$ y así sucesivamente.

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

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

El factor de escala ${\displaystyle \xi ^{\ast }\in \mathbb {R} }$ 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 ${\displaystyle q()}$ es decreciente, y por lo tanto los límites de búsqueda para ${\displaystyle \xi ^{\ast }}$ son ${\displaystyle [\min(0,f(0)),\max(0,f(0))]}$.

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

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

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

lo cual conduce a:

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

donde el parámetro ${\displaystyle w}$ que minimiza a ${\displaystyle Q(w)}$ será estimado, ${\displaystyle \eta }$ es un step size (a veces llamado tasa de aprendizaje en el aprendizaje automático) y ${\displaystyle \alpha }$ 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 ${\displaystyle w}$, 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]​

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

Cuando se realiza la optimización, este vector de parámetros promediado ocupa el lugar de ${\displaystyle w}$.

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 ${\displaystyle \eta }$, pero ésta se multiplica por los elementos de un vector {G_j,j} que es la diagonal de la matriz producto exterior

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

donde ${\displaystyle g_{\tau }=\nabla Q_{i}(w)}$, la gradiente, en la iteración ${\displaystyle t}$. La diagonal viene dada por:

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

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

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

o, escritas como actualizaciones por parámetro,

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

Cada {G_(i,i)} da lugar a un factor de escala para la tasa de aprendizaje que se aplica a un único parámetro ${\displaystyle w_{i}}$. Dado que el denominador de este factor, ${\displaystyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$ es la norma ℓ₂ 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,

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

en el que ${\displaystyle \gamma }$ 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,

${\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 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 ${\displaystyle w^{(t)}}$y una función de pérdida ${\displaystyle L^{(t)}}$, en el que ${\displaystyle t}$ indexa la iteración de entrenamiento actual (indexada en ${\displaystyle 0}$), la actualización de los parámetros de Adam viene dada por:

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

${\displaystyle v_{w}^{(t+1)}\leftarrow \beta _{2}v_{w}^{(t)}+(1-\beta _{2})(\nabla _{w}L^{(t)})^{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 }}}$

donde ${\displaystyle \epsilon }$ es un escalar pequeño (por ejemplo ${\displaystyle 10^{-8}}$) utilizado para evitar la división por 0, y ${\displaystyle \beta _{1}}$ (por ejemplo, 0,9) y ${\displaystyle \beta _{2}}$ (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 ${\displaystyle f(x_{n+1})\leq f(x_{n})}$ 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.

Lectura adicional

• Bottou, Léon (2004). «Advanced Lectures on Machine Learning». Stochastic Learning. LNAI (en inglés) (Springer) 3176: 146-168. ISBN 978-3-540-23122-6. 
• Buduma, Nikhil; Locascio, Nicholas (2017). «Beyond Gradient Descent». Fundamentals of Deep Learning : Designing Next-Generation Machine Intelligence Algorithms. O'Reilly. ISBN 9781491925584. 
• LeCun, Yann A.; Bottou, Léon; Orr, Genevieve B.; Müller, Klaus-Robert (2012). «Efficient BackProp». Neural Networks: Tricks of the Trade. Springer. pp. 9-48. ISBN 978-3-642-35288-1. 
• Spall, James C. (2003). Introduction to Stochastic Search and Optimization. John Wiley & Sons. ISBN 978-0-471-33052-3. 

Véase también

• Aprendizaje supervisado
• Aprendizaje automático online
• Descenso de gradiente estocástica

Enlaces externos

• Uso del descenso de gradiente estocástico en C++, Boost, Ublas para regresión lineal (en inglés)
• Algoritmos de aprendizaje automático (en inglés)
• «(Video) Gradient Descent, How Neural Networks Learn» (en inglés). 3Blue1Brown. 16 de octubre de 2017. Archivado desde el original el 8 de enero de 2023. Consultado el 12 de julio de 2023. 
• Goh (4 de abril de 2017). «Why Momentum Really Works». Distill 2 (4). doi:10.23915/distill.00006.  Documento interactivo que explica el momentum.

Referencias

1. Bottou, Léon; Bousquet, Olivier (2012). «The Tradeoffs of Large Scale Learning». En Sra, Suvrit; Nowozin, Sebastian, Wright, Stephen J., eds. Optimization for Machine Learning. Cambridge: MIT Press. pp. 351-368. ISBN 978-0-262-01646-9. 
2. Bottou, Léon (1998). «Online Algorithms and Stochastic Approximations». Online Learning and Neural Networks. Cambridge University Press. ISBN 978-0-521-65263-6. 
3. Ferguson, Thomas S. (1982). «An inconsistent maximum likelihood estimate». Journal of the American Statistical Association. JSTOR 2287314 77 (380): 831-834. doi:10.1080/01621459.1982.10477894. 
4. Bottou, Léon; Bousquet, Olivier (2008). «The Tradeoffs of Large Scale Learning». Advances in Neural Information Processing Systems 20: 161-168. 
5. Murphy, Kevin (2021). Probabilistic Machine Learning: An Introduction. MIT Press. Probabilistic Machine Learning: An Introduction. Consultado el 10 de abril de 2021. 
6. Bilmes, Jeff; Asanovic, Krste; Chin, Chee-Whye; Demmel, James (Abril de 1997). «Using PHiPAC to speed error back-propagation learning». ICASSP (Munich, Alemania) 5: 4153-4156. doi:10.1109/ICASSP.1997.604861. «1997 IEEE International Conference on Acoustics, Speech, and Signal Processing». 
7. Bottou, Léon (1998). «Online Algorithms and Stochastic Approximations». Online Learning and Neural Networks. Cambridge University Press. ISBN 978-0-521-65263-6. 
8. Kiwiel, Krzysztof C. (2001). «Convergence and efficiency of subgradient methods for quasiconvex minimization». Mathematical Programming, Series A (Berlin, Heidelberg: Springer) 90 (1): 1-25. ISSN 0025-5610. doi:10.1007/PL00011414. 
9. Robbins, Herbert; Siegmund, David O. (1971). «A convergence theorem for non negative almost supermartingales and some applications». En Rustagi, Jagdish S., ed. Optimizing Methods in Statistics. Academic Press. ISBN 0-12-604550-X. 
10. Finkel, Jenny Rose; Kleeman, Alex; Manning, Christopher D. (2008). «Efficient, Feature-based, Conditional Random Field Parsing». Proc. Annual Meeting of the ACL. 
11. Lecun, Yann A. et al. (2012). «Efficient backprop." Neural networks: Tricks of the trade.». Springer Berlin Heidelberg. 
12. Krebs, Jerome R.; Anderson, John E.; Neelamani, Ramesh; Lee, Sunwoong; Baumstein, Anatoly; Lacasse, Martin-Daniel. «Fast full-wavefield seismic inversion using encoded sources». Geophysics 74. 
13. Pfeffer, Avi. «CS181 Lecture 5 — Perceptrons». Harvard University. 
14. Goodfellow, Ian; Bengio, Yoshua; Courville, Aaron (2016). Deep Learning. MIT Press. p. 291. ISBN 978-0262035613. 
15. Darken, Christian; Moody, John (1990). «Fast adaptive k-means clustering: some empirical results». Int'l Joint Conf. on Neural Networks (IJCNN). doi:10.1109/IJCNN.1990.137720. 
16. Spall, J. C. (2003). Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. Hoboken, NJ: Wiley. Sections 4.4, 6.6, and 7.5. ISBN 0-471-33052-3. 
17. Toulis, Panos; Airoldi, Edoardo (2017). «Asymptotic and finite-sample properties of estimators based on stochastic gradients». Annals of Statistics 45 (4): 1694-1727. doi:10.1214/16-AOS1506. 
18. Rumelhart, David E.; Hinton, Geoffrey E.; Williams, Ronald J. (8 de octubre de 1986). «Learning representations by back-propagating errors». Nature 323 (6088): 533-536. doi:10.1038/323533a0. 
19. «Gradient Descent and Momentum: The Heavy Ball Method». 13 de julio de 2020. 
20. 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. 
21. Sutskever, Ilya (2013). «Training recurrent neural networks (Ph. D.)». University of Toronto: 74. 
22. Zeiler (2012). «ADADELTA: An adaptive learning rate method». arXiv:1212.5701  [cs.LG]. 
23. Borysenko, Oleksandr; Byshkin, Maksym (2021). «CoolMomentum: A Method for Stochastic Optimization by Langevin Dynamics with Simulated Annealing». Scientific Reports 11 (1): 10705. PMID 34021212. doi:10.1038/s41598-021-90144-3. 
24. «Papers with Code - Nesterov Accelerated Gradient Explained». 
25. Polyak, Boris T.; Juditsky, Anatoli B. (1992). «Acceleration of stochastic approximation by averaging». SIAM J. Control Optim. 30 (4): 838-855. doi:10.1137/0330046. Archivado desde el original el 12 de enero de 2016. Consultado el 12 de julio de 2023. 
26. Duchi, John; Hazan, Elad; Singer, Yoram (2011). «Adaptive subgradient methods for online learning and stochastic optimization». Journal of Machine Learning Research 12: 2121-2159. 
27. ${\displaystyle \odot }$ es el producto de Hadamard.
28. Gupta, Maya R.; Bengio, Samy; Weston, Jason (2014). «Training highly multiclass classifiers». JMLR 15 (1): 1461-1492. 
29. Hinton, Geoffrey. «Lecture 6e rmsprop: Divide the gradient by a running average of its recent magnitude». p. 26. Consultado el 19 de marzo de 2020. 
30. «Understanding RMSprop — faster neural network learning». Consultado el 2 de setiembre de 2018. 
31. Diederik (2014). «Adam: A Method for Stochastic Optimization». arXiv:1412.6980  [cs.LG]. 
32. «4. Beyond Gradient Descent - Fundamentals of Deep Learning [Book]». 
33. Dozat, T. (2016). «Incorporating Nesterov Momentum into Adam». S2CID 70293087. 
34. Naveen, Philip (9 de agosto de 2022). FASFA: A Novel Next-Generation Backpropagation Optimizer. doi:10.36227/techrxiv.20427852.v1. Consultado el 19 de noviembre de 2022. 
35. Whye, Schwarz, Jonathan Jayakumar, Siddhant M. Pascanu, Razvan Latham, Peter E. Teh, Yee (2021). Powerpropagation: A sparsity inducing weight reparameterisation. 
36. Hu, Yuzheng; Lin, Licong; Tang, Shange (20 de diciembre de 2019). Second-order Information in First-order Optimization Methods. 
37. Reddi; Kumar (2018). «On the Convergence of Adam and Beyond». arXiv:1904.09237. 
38. «An overview of gradient descent optimization algorithms». 19 de enero de 2016. 
39. Loshchilov, Ilya; Hutter, Frank (4 de enero de 2019). Decoupled Weight Decay Regularization. 
40. Balles, Lukas, Hennig, Philipp (15 de febrero de 2018). «Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients». 
41. «SignSGD: Compressed Optimisation for Non-Convex Problems». 3 de julio de 2018. pp. 560-569. 
42. Byrd, R. H.; Hansen, S. L.; Nocedal, J.; Singer, Y. (2016). «A Stochastic Quasi-Newton method for Large-Scale Optimization». SIAM Journal on Optimization 26 (2): 1008-1031. doi:10.1137/140954362. 
43. Spall, J. C. (2000). «Adaptive Stochastic Approximation by the Simultaneous Perturbation Method». IEEE Transactions on Automatic Control 45 (10): 1839−1853. doi:10.1109/TAC.2000.880982. 
44. Spall, J. C. (2009). «Feedback and Weighting Mechanisms for Improving Jacobian Estimates in the Adaptive Simultaneous Perturbation Algorithm». IEEE Transactions on Automatic Control 54 (6): 1216-1229. doi:10.1109/TAC.2009.2019793. 
45. Bhatnagar, S.; Prasad, H. L.; Prashanth, L. A. (2013). Stochastic Recursive Algorithms for Optimization: Simultaneous Perturbation Methods. London: Springer. ISBN 978-1-4471-4284-3. 
46. Ruppert, D. (1985). «A Newton-Raphson Version of the Multivariate Robbins-Monro Procedure». Annals of Statistics 13 (1): 236-245. doi:10.1214/aos/1176346589. 
47. Amari, S. (1998). «Natural gradient works efficiently in learning». Neural Computation 10 (2): 251-276. doi:10.1162/089976698300017746.