Ver el código de «Descenso de gradiente estocástico»

El '''descenso de gradiente estocástico''' (''en [[Inglés estadounidense|inglés]]: '''Stochastic gradient descent''''', a menudo abreviado como '''SGD''') es un [[método iterativo]] para optimizar una [[Función de pérdida|función objetivo]] con propiedades de [[Función infinitamente diferenciable|suavidad]] adecuadas (por ejemplo, [[Función diferenciable|diferenciable]] o [[Función subdiferenciable|subdiferenciable]]). Puede considerarse una [[aproximación estocástica]] de la optimización por [[Descenso del gradiente|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 [[Dimensión|alta dimensión,]] esto reduce la elevadísima [[carga computacional]], consiguiendo iteraciones más rápidas a cambio de una menor tasa de convergencia.<ref>{{Cita libro|apellidos=Bottou|nombre=Léon|título=Optimization for Machine Learning|año=2012|editorial=MIT Press|isbn=978-0-262-01646-9|ubicación=Cambridge|páginas=351–368|capítulo=The Tradeoffs of Large Scale Learning|apellidos2=Bousquet|nombre2=Olivier|apellido-editor=Sra|nombre-editor=Suvrit|apellido-editor2=Nowozin, Sebastian|nombre-editor2=Wright, Stephen J.|url-capítulo=https://books.google.com/books?id=JPQx7s2L1A8C&pg=PA351}}</ref>

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]].<ref name="dup-0-13">{{Cita libro|apellidos=Bottou|nombre=Léon|título=Online Learning and Neural Networks|url=https://archive.org/details/onlinelearningin0000unse|año=1998|editorial=Cambridge University Press|isbn=978-0-521-65263-6|capítulo=Online Algorithms and Stochastic Approximations}}</ref>

== Antecedentes ==
Tanto la [[M-estimador|estimación]] [[estadística]] como el [[aprendizaje automático]] consideran el problema de [[Optimización (matemática)|minimizar]] una [[Función de pérdida|función objetivo]] que tiene la forma de una suma:

<math>Q(w) = \frac{1}{n}\sum_{i=1}^n Q_i(w),</math>

en la que el [[Estadística paramétrica|parámetro]] <math>w</math> que minimiza <math>Q(w)</math> será [[Estimador|estimado]]. Cada una de las funciones sumando <math>Q_i</math>  suele estar asociada a la [[Unidad de observación|observación]] <math>i</math>-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.<ref>{{Cita publicación|título=An inconsistent maximum likelihood estimate|url=https://archive.org/details/sim_journal-of-the-american-statistical-association_1982-12_77_380/page/831|apellidos=Ferguson|nombre=Thomas S.|fecha=1982|publicación=Journal of the American Statistical Association|volumen=77|número=380|páginas=831–834|serie=JSTOR 2287314|doi=10.1080/01621459.1982.10477894}}</ref> Por lo tanto, los teóricos estadísticos contemporáneos suelen considerar [[Punto estacionario|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 <math>Q_i(w)</math>  es el valor de la [[función de pérdida]] en el ejemplo de <math>i</math>-n, y <math>Q(w)</math> es el riesgo empírico.

Cuando se utiliza para minimizar la función anterior, un método de [[Descenso del gradiente|descenso de gradiente]] estándar (o "por lotes") realizaría las siguientes iteraciones:

<math>w := w - \eta \nabla Q(w) = w - \frac{\eta}{n} \sum_{i=1}^n \nabla Q_i(w),</math>

donde <math>\eta</math> 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 [[Familia exponencial|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 [[Muestreo (estadística)|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.<ref>{{Cita publicación|url=http://leon.bottou.org/papers/bottou-bousquet-2008|título=The Tradeoffs of Large Scale Learning|apellidos=Bottou|nombre=Léon|apellidos2=Bousquet|nombre2=Olivier|fecha=2008|publicación=Advances in Neural Information Processing Systems|volumen=20|páginas=161–168}}</ref>

== Método iterativo ==
[[Archivo:Stogra.png|miniaturadeimagen|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 "[[Aprendizaje automático online|en línea]]"), el verdadero gradiente de <math>Q(w)</math> se aproxima por un gradiente en una sola muestra:

<math>w := w - \eta \nabla Q_i(w).</math>

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|tasa de aprendizaje adaptativa]] para que el algoritmo converja.<ref>{{Cita libro|apellidos=Murphy|nombre=Kevin|título=Probabilistic Machine Learning: An Introduction|url=https://probml.github.io/pml-book/book1.html|fechaacceso=10 de abril de 2021|año=2021|editorial=MIT Press|en=Probabilistic Machine Learning: An Introduction}}</ref>

En [[pseudocódigo]], el descenso de gradiente estocástico puede presentarse como:{{framebox|blue}}
* Elegir un vector inicial de parámetros  <math>w</math> y tasa de aprendizaje <math>\eta</math>.
*Repita la operación hasta obtener un mínimo aproximado:
** Barajar aleatoriamente las muestras del conjunto de entrenamiento.
** Para <math> i=1, 2, ..., n</math>, realizar:
*** <math> w := w - \eta \nabla Q_i(w).</math>
{{frame-footer}}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 matemática|vectorización]] en lugar de calcular cada fase por separada, como se mostró por primera vez<ref>{{Cita publicación|url=https://ieeexplore.ieee.org/document/604861|título=Using PHiPAC to speed error back-propagation learning|apellidos=Bilmes|nombre=Jeff|apellidos2=Asanovic|nombre2=Krste|fecha=Abril de 1997|publicación=ICASSP|volumen=5|páginas=4153-4156|lugar-publicación=Munich, Alemania|edición=|en=|doi=10.1109/ICASSP.1997.604861|cita=1997 IEEE International Conference on Acoustics, Speech, and Signal Processing|apellidos3=Chin|nombre3=Chee-Whye|apellidos4=Demmel|nombre4=James}}</ref> 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]] <math>
\eta</math> 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 [[Función convexa|convexa]] o [[pseudoconvexa]], y en caso contrario converge casi con seguridad a un mínimo local.<ref name="dup-0-13" /><ref>{{Cita publicación|título=Convergence and efficiency of subgradient methods for quasiconvex minimization|apellidos=Kiwiel|nombre=Krzysztof C.|fecha=2001|publicación=Mathematical Programming, Series A|editorial=Springer|volumen=90|número=1|páginas=1–25|lugar-publicación=Berlin, Heidelberg|issn=0025-5610|doi=10.1007/PL00011414|ref=10043417}}</ref> Esto es, de hecho, una consecuencia del [[teorema de Robbins-Siegmund]].<ref>{{Cita libro|apellidos=Robbins|nombre=Herbert|título=Optimizing Methods in Statistics|url=https://archive.org/details/optimizingmethod0000symp|año=1971|editorial=Academic Press|isbn=0-12-604550-X|capítulo=A convergence theorem for non negative almost supermartingales and some applications|apellidos2=Siegmund|nombre2=David O.|apellido-editor=Rustagi|nombre-editor=Jagdish S.}}</ref>

== Ejemplo ==
Supongamos que queremos ajustar una recta <math>\hat{y} = \! w_1 + w_2 x</math> a un conjunto de entrenamiento con observaciones <math>(x_1, x_2, \ldots, x_n)</math> y las correspondientes respuestas estimadas <math>(\hat{y_1}, \hat{y_2}, \ldots, \hat{y_n})</math> utilizando mínimos cuadrados. La función objetivo a minimizar es: 

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

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

<math>\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) \\ 2 x_i(w_1 + w_2 x_i - y_i) \end{bmatrix}.</math> 

Nótese que en cada iteración (también llamada actualización), el gradiente sólo se evalúa en un único punto <math> x_i</math> 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 [[Modelo en grafo|modelos en grafo]].<ref>{{Cita publicación|url=http://www.aclweb.org/anthology/P08-1109|título=Efficient, Feature-based, Conditional Random Field Parsing|apellidos=Finkel|nombre=Jenny Rose|apellidos2=Kleeman|nombre2=Alex|fecha=2008|publicación=Proc. Annual Meeting of the ACL.|apellidos3=Manning|nombre3=Christopher D.}}</ref> Combinado con el algoritmo de [[Propagación hacia atrás|retropropagación]], es el algoritmo estándar ''de facto'' para el entrenamiento de [[Red neuronal artificial|redes neuronales artificiales]].<ref>{{Cita publicación|url=http://yann.lecun.com/exdb/publis/pdf/lecun-98b.pdf|título=Efficient backprop." Neural networks: Tricks of the trade.|apellidos=Lecun|nombre=Yann A. et al.|fecha=2012|publicación=Springer Berlin Heidelberg}}</ref> 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).<ref>{{Cita publicación|url=https://library.seg.org/doi/abs/10.1190/1.3230502|título=Fast full-wavefield seismic inversion using encoded sources|apellidos=Krebs|nombre=Jerome R.|apellidos2=Anderson|nombre2=John E.|publicación=Geophysics|volumen=74|apellidos3=Neelamani|nombre3=Ramesh|apellidos4=Lee|nombre4=Sunwoong|apellidos5=Baumstein|nombre5=Anatoly|apellidos6=Lacasse|nombre6=Martin-Daniel}}</ref>

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|ADALINE]].<ref>{{Cita web|url=http://www.seas.harvard.edu/courses/cs181/files/lecture05-notes.pdf|título=CS181 Lecture 5 — Perceptrons|apellido=Pfeffer|nombre=Avi|editorial=Harvard University}}</ref>

Otro algoritmo de descenso de gradiente estocástico es el filtro adaptativo de [[Algoritmo LMS|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.<ref>{{Cita libro|apellidos=Goodfellow|nombre=Ian|título=Deep Learning|url=https://www.deeplearningbook.org|año=2016|editorial=MIT Press|isbn=978-0262035613|página=291|apellidos2=Bengio|nombre2=Yoshua|apellidos3=Courville|nombre3=Aaron}}</ref> Una extensión conceptualmente simple del descenso de gradiente estocástico hace que la tasa de aprendizaje sea una función decreciente <math>n_t</math> del número de iteraciones <math>t</math>, 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 [[K-medias|agrupación <math>k</math>-medias]].<ref>{{Cita publicación|título=Fast adaptive k-means clustering: some empirical results|apellidos=Darken|nombre=Christian|apellidos2=Moody|nombre2=John|fecha=1990|publicación=Int'l Joint Conf. on Neural Networks (IJCNN)|doi=10.1109/IJCNN.1990.137720}}</ref> Spall ofrece orientación práctica sobre la elección del ''step size'' en diversas variantes de SGD.<ref>{{Cita libro|apellidos=Spall|nombre=J. C.|título=Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control|url=https://archive.org/details/introductiontost0000spal|año=2003|editorial=Wiley|isbn=0-471-33052-3|ubicación=Hoboken, NJ|en=Sections 4.4, 6.6, and 7.5}}</ref>

=== 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]] <math>n</math>. Una convergencia rápida requiere grandes tasas de aprendizaje, pero esto puede inducir inestabilidad numérica. El problema puede resolverse en gran medida<ref>{{Cita publicación|url=https://arxiv.org/abs/1408.2923|título=Asymptotic and finite-sample properties of estimators based on stochastic gradients|apellidos=Toulis|nombre=Panos|apellidos2=Airoldi|nombre2=Edoardo|fecha=2017|publicación=Annals of Statistics|volumen=45|número=4|páginas=1694–1727|doi=10.1214/16-AOS1506}}</ref> considerando ''actualizaciones implícitas'' en las que el gradiente estocástico se evalúa en la siguiente iterada en lugar de en la actual:

<math>w^{\rm new} := w^{\rm old} - \eta \nabla Q_i(w^{\rm  new}).</math>

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

<math>w^{\rm new} := \arg\min_w \{ Q_i(w) + \frac{1}{2\eta} ||w - w^{\rm old}||^2 \}.</math>

A modo de ejemplo, consideremos los mínimos cuadrados con características <math>x_1, \ldots, x_n \in\mathbb{R}^p</math>  y observaciones <math>y_1, \ldots, y_n\in\mathbb{R}</math>. Queremos resolver:

<math>\min_w \sum_{j=1}^n (y_j - x_j'w)^2,</math>

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

<math>w^{\rm new} = w^{\rm old} + \eta (y_i - x_i'w^{\rm old}) x_i</math>

donde <math>i</math> se muestrea uniformemente entre 1 y <math>n</math>. 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 <math>n</math> está mal especificado de modo que <math>I - \eta x_i x_i'</math> 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:

<math>w^{\rm new} = w^{\rm old} + \frac{\eta}{1 + \eta ||x_i||^2} (y_i - x_i'w^{\rm old}) x_i.</math>

Este procedimiento se mantendrá numéricamente estable prácticamente para todas las <math>n</math> 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 [[Algoritmo LMS|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 <math>Q_i(w)</math> depende de <math>w</math> sólo a través de una combinación lineal con las características <math>x_i</math>, de modo que podemos escribir <math>\nabla_w Q_i(w) = -q(x_i'w) x_i</math>, donde <math>q() \in\mathbb{R}</math> puede depender de <math>x_i, y_i</math> pero no en <math>w</math> excepto a través de <math>x_i'w</math>. Los mínimos cuadrados obedecen esta regla, al igual que la [[regresión logística]] y la mayoría de los [[Modelo lineal generalizado|modelos lineales generalizados]]. Por ejemplo, en mínimos cuadrados, <math>q(x_i'w) = y_i - x_i'w</math> y en regresión logística <math>q(x_i'w) = y_i - S(x_i'w)</math>, donde <math>S(u) = e^u/(1+e^u)</math> es la [[función logística]]. En la [[regresión de Poisson]] <math>q(x_i'w) = y_i - e^{x_i'w}</math> y así sucesivamente.

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

<math>w^{\rm new} = w^{\rm old} + \xi^\ast x_i,~\text{where}~\xi^\ast = f(\xi^\ast).</math>

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

=== 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 [[David Rumelhart|Rumelhart]], [[Geoffrey Hinton|Hinton]] y [[Ronald j. Williams|Williams]] sobre el aprendizaje por retropropagación<ref name=":0">{{Cita publicación|url=https://ui.adsabs.harvard.edu/abs/1986Natur.323..533R|título=Learning representations by back-propagating errors|apellidos=Rumelhart|nombre=David E.|apellidos2=Hinton|nombre2=Geoffrey E.|fecha=8 de octubre de 1986|publicación=Nature|volumen=323|número=6088|páginas=533–536|doi=10.1038/323533a0|apellidos3=Williams|nombre3=Ronald J.}}</ref> y tomó prestada la idea del artículo del matemático soviético Boris Polyak de 1964 sobre la [[resolución de ecuaciones]] funcionales.<ref>{{Cita web|url=https://boostedml.com/2020/07/gradient-descent-and-momentum-the-heavy-ball-method.html|título=Gradient Descent and Momentum: The Heavy Ball Method|fecha=13 de julio de 2020}}</ref> El descenso de gradiente estocástico con impulso recuerda la actualización {{math|Δ''w''}} en cada iteración, y determina la siguiente actualización como una [[combinación lineal]] del gradiente y la actualización anterior:<ref>{{Cita publicación|url=http://www.cs.utoronto.ca/~ilya/pubs/2013/1051_2.pdf|título=On the importance of initialization and momentum in deep learning|apellidos=Sutskever|nombre=Ilya|apellidos2=Martens|nombre2=James|fecha=Junio de 2013|publicación=In Proceedings of the 30th international conference on machine learning (ICML-13)|volumen=28|número=1139–1147|fechaacceso=14 de enero de 2016|apellidos-editor=Dasgupta, Sanjoy|nombre-editor=Mcallester, David|ubicación=Atlanta, GA|apellidos3=Dahl|nombre3=George|apellidos4=Hinton|nombre4=Geoffrey E.}}</ref><ref>{{Cita publicación|url=http://www.cs.utoronto.ca/~ilya/pubs/ilya_sutskever_phd_thesis.pdf|título=Training recurrent neural networks (Ph. D.)|apellidos=Sutskever|nombre=Ilya|fecha=2013|publicación=University of Toronto|páginas=74}}</ref>

<math>\Delta w := \alpha \Delta w - \eta \nabla Q_i(w)</math>

<math>w := w + \Delta w</math>

lo cual conduce a:

<math>w := w - \eta \nabla Q_i(w) + \alpha \Delta w</math>

donde el parámetro <math>w</math> que minimiza a <math>Q(w)</math> será estimado, <math>\eta</math> es un ''step size'' (a veces llamado tasa de aprendizaje en el aprendizaje automático) y <math>\alpha</math> 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 ''[[Cantidad de movimiento|momentum]]'' en física: el vector peso <math>w</math>, pensado como una partícula que viaja a través del espacio de parámetros,<ref name=":0" /> 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 [[Red neuronal artificial|redes neuronales artificiales]].<ref name=":1">{{Cita arXiv|arxiv=1212.5701|class=cs.LG|last=Zeiler|surname=Matthew D.|title=ADADELTA: An adaptive learning rate method|date=2012}}</ref> El método del ''momentum'' está estrechamente relacionado con la [[dinámica de Langevin sin amortiguación]] y puede combinarse con el algoritmo de [[Algoritmo de recocido simulado|recocido simulado]].<ref>{{Cita publicación|url=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8139967|título=CoolMomentum: A Method for Stochastic Optimization by Langevin Dynamics with Simulated Annealing|apellidos=Borysenko|nombre=Oleksandr|apellidos2=Byshkin|nombre2=Maksym|fecha=2021|publicación=Scientific Reports|volumen=11|número=1|páginas=10705|doi=10.1038/s41598-021-90144-3|pmid=34021212}}</ref>

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.<ref>{{Cita web|url=https://paperswithcode.com/method/nesterov-accelerated-gradient|título=Papers with Code - Nesterov Accelerated Gradient Explained}}</ref>

=== 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<ref>{{Cita publicación|url=http://www.meyn.ece.ufl.edu/archive/spm_files/Courses/ECE555-2011/555media/poljud92.pdf|título=Acceleration of stochastic approximation by averaging|apellidos=Polyak|nombre=Boris T.|apellidos2=Juditsky|nombre2=Anatoli B.|fecha=1992|publicación=SIAM J. Control Optim.|volumen=30|número=4|páginas=838–855|doi=10.1137/0330046|fechaacceso=12 de julio de 2023|fechaarchivo=12 de enero de 2016|urlarchivo=https://web.archive.org/web/20160112091615/http://www.meyn.ece.ufl.edu/archive/spm_files/Courses/ECE555-2011/555media/poljud92.pdf|deadurl=yes}}</ref>

<math>\bar{w} = \frac{1}{t} \sum_{i=0}^{t-1} w_i</math>

Cuando se realiza la optimización, este vector de parámetros promediado ocupa el lugar de <math>w</math>.

=== AdaGrad ===
''AdaGrad'' (algoritmo de [[Descenso del gradiente|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.<ref name=":2">{{Cita publicación|url=http://jmlr.org/papers/volume12/duchi11a/duchi11a.pdf|título=Adaptive subgradient methods for online learning and stochastic optimization|apellidos=Duchi|nombre=John|apellidos2=Hazan|nombre2=Elad|fecha=2011|publicación=Journal of Machine Learning Research|volumen=12|páginas=2121–2159|apellidos3=Singer|nombre3=Yoram}}</ref> 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.<ref name=":2" />

Sigue teniendo una tasa de aprendizaje base <math>\eta</math>, pero ésta se multiplica por los elementos de un vector {{Math|{''G''<sub>''j'',''j''</sub>}}} que es la diagonal de la matriz [[producto exterior]]

<math>G = \sum_{\tau=1}^t g_\tau g_\tau^\mathsf{T} </math>

donde <math>g_\tau = \nabla Q_i(w) </math>, la gradiente, en la iteración <math>t </math>. La diagonal viene dada por:

<math>G_{j,j} = \sum_{\tau=1}^t g_{\tau,j}^2 </math>

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

<math>w := w - \eta\, \mathrm{diag}(G)^{-\frac{1}{2}} \odot g </math>{{Efn|<math>\odot</math> es el producto de Hadamard.}}

o, escritas como actualizaciones por parámetro,

<math>w_j := w_j - \frac{\eta}{\sqrt{G_{j,j}}} g_j. </math>

Cada {{Math|{''G''<sub>(''i'',''i'')</sub>}}} da lugar a un factor de escala para la tasa de aprendizaje que se aplica a un único parámetro <math>w_i </math>. Dado que el denominador de este factor, <math>\sqrt{G_i} = \sqrt{\sum_{\tau=1}^t g_\tau^2} </math> es la [[Norma vectorial|norma ''ℓ''<sub>2</sub>]] 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.<ref name=":1" />

Aunque está diseñado para [[Optimización convexa|problemas convexos]], AdaGrad se ha aplicado con éxito a la optimización no convexa.<ref>{{Cita publicación|url=http://jmlr.org/papers/volume15/gupta14a/gupta14a.pdf|título=Training highly multiclass classifiers|apellidos=Gupta|nombre=Maya R.|apellidos2=Bengio|nombre2=Samy|fecha=2014|publicación=JMLR|volumen=15|número=1|páginas=1461–1492|apellidos3=Weston|nombre3=Jason}}</ref>

=== RMSProp ===
''RMSProp'' o propagación de raíz cuadrática media (''en [[Inglés estadounidense|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.<ref name=":3">{{Cita web|url=http://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf|título=Lecture 6e rmsprop: Divide the gradient by a running average of its recent magnitude|fechaacceso=19 de marzo de 2020|apellido=Hinton|nombre=Geoffrey|página=26}}</ref> 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]],

<math>v(w,t):=\gamma v(w,t-1)+(1-\gamma)(\nabla Q_i(w))^2 </math>

en el que <math>\gamma </math> 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.<ref>{{Cita web|url=https://towardsdatascience.com/understanding-rmsprop-faster-neural-network-learning-62e116fcf29a|título=Understanding RMSprop — faster neural network learning|fechaacceso=2 de setiembre de 2018}}</ref>

Y los parámetros se actualizan como,

<math>w:=w-\frac{\eta}{\sqrt{v(w,t)}}\nabla Q_i(w) </math>

RMSProp ha demostrado una buena adaptación de la tasa de aprendizaje en diferentes aplicaciones. RMSProp puede considerarse como una generalización de [[Rprop aprendizaje automático|Rprop]] y es capaz de trabajar también con minilotes en lugar de sólo con lotes completos.<ref name=":3" />

=== Adam ===
''Adam''<ref name=":4">{{Cita arXiv|arxiv=1412.6980|class=cs.LG|last=Diederik|surname=Kingma|last1=Jimmy|surname1=Ba|title=Adam: A Method for Stochastic Optimization|date=2014}}</ref> o estimación de momento adaptativo (''en [[Inglés estadounidense|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''.<ref>{{Cita web|url=https://www.oreilly.com/library/view/fundamentals-of-deep/9781491925607/ch04.html|título=4. Beyond Gradient Descent - Fundamentals of Deep Learning &#91;Book&#93;}}</ref> 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 <math> w^ {(t)}</math>y una función de pérdida <math> L ^ {(t)} </math>, en el que <math>t</math>  indexa la iteración de entrenamiento actual (indexada en <math>0</math>), la actualización de los parámetros de Adam viene dada por: 

<math>m_w ^ {(t+1)} \leftarrow \beta_1 m_w ^ {(t)} + (1 - \beta_1) \nabla _w L ^ {(t)}</math> 

<math>v_w ^ {(t+1)} \leftarrow \beta_2 v_w ^ {(t)} + (1 - \beta_2) (\nabla _w L ^ {(t)} )^2</math>  

<math>\hat{m}_w = \frac{m_w ^ {(t+1)}}{1 - \beta_1^t}</math> 

<math>\hat{v}_w = \frac{ v_w ^ {(t+1)}}{1 - \beta_2^t}</math>  

<math>w ^ {(t+1)} \leftarrow w ^ {(t)} - \eta \frac{\hat{m}_w}{\sqrt{\hat{v}_w} + \epsilon}</math> 

donde <math>\epsilon</math> es un escalar pequeño (por ejemplo <math>10^{-8}</math>) utilizado para evitar la división por 0, y <math>\beta_1</math> (por ejemplo, 0,9) y <math>\beta_2</math> (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''<ref>{{Cita publicación|url=https://www.semanticscholar.org/paper/Incorporating-Nesterov-Momentum-into-Adam-Dozat/d44efdc542f2cc5e196f04bc76bc783bfd7084af|título=Incorporating Nesterov Momentum into Adam|apellidos=Dozat|nombre=T.|fecha=2016|publicación=S2CID 70293087}}</ref> y ''FASFA''<ref>{{Cita publicación|url=http://dx.doi.org/10.36227/techrxiv.20427852.v1|título=FASFA: A Novel Next-Generation Backpropagation Optimizer|apellidos=Naveen|nombre=Philip|fecha=2022-08-09|publicación=|fechaacceso=2022-11-19|doi=10.36227/techrxiv.20427852.v1}}</ref>) y diversas interpretaciones de la información de segundo orden (por ejemplo: ''Powerpropagation''<ref>{{Cita libro|apellidos=Whye|nombre=Schwarz, Jonathan Jayakumar, Siddhant M. Pascanu, Razvan Latham, Peter E. Teh, Yee|título=Powerpropagation: A sparsity inducing weight reparameterisation|url=http://worldcat.org/oclc/1333722169|año=2021}}</ref> y ''AdaSqrt''<ref>{{Cita publicación|url=https://arxiv.org/abs/1912.09926|título=Second-order Information in First-order Optimization Methods|apellidos=Hu|nombre=Yuzheng|apellidos2=Lin|nombre2=Licong|fecha=2019-12-20|publicación=|apellidos3=Tang|nombre3=Shange}}</ref>). Sin embargo, las variantes más utilizadas son ''AdaMax'',<ref name=":4" /> que generaliza ''Adam'' utilizando la norma del infinito, y ''AMSGrad'',<ref>{{Cita arXiv|last=Reddi|surname=Sashank J.|last1=Kale|surname1=Satyen|last2=Kumar|surname2=Sanjiv|date=2018|title=On the Convergence of Adam and Beyond|arxiv=1904.09237}}</ref> que aborda los problemas de convergencia de Adam utilizando el máximo de los gradientes pasados al cuadrado en lugar de la media exponencial.<ref>{{Cita web|url=https://www.ruder.io/optimizing-gradient-descent/#amsgrad|título=An overview of gradient descent optimization algorithms|fecha=19 de enero de 2016}}</ref> 

''AdamW'' <ref>{{Cita publicación|url=https://arxiv.org/abs/1711.05101|título=Decoupled Weight Decay Regularization|apellidos=Loshchilov|nombre=Ilya|apellidos2=Hutter|nombre2=Frank|fecha=4 de enero de 2019|publicación=}}</ref> 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.<ref>{{Cita web|url=https://openreview.net/forum?id=S1EwLkW0W|título=Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients|apellido=Balles, Lukas|nombre=Hennig, Philipp|fecha=15 de febrero de 2018}}</ref><ref>{{Cita web|url=https://proceedings.mlr.press/v80/bernstein18a.html|título=SignSGD: Compressed Optimisation for Non-Convex Problems|fecha=3 de julio de 2018|páginas=560–569}}</ref>

=== 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 <math>f(x_{n+1})\leq f(x_n)</math> 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) [[Algoritmo e Newton-Raphson|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<ref>{{Cita publicación|url=https://arxiv.org/abs/1401.7020|título=A Stochastic Quasi-Newton method for Large-Scale Optimization|apellidos=Byrd|nombre=R. H.|apellidos2=Hansen|nombre2=S. L.|fecha=2016|publicación=SIAM Journal on Optimization|volumen=26|número=2|páginas=1008–1031|doi=10.1137/140954362|apellidos3=Nocedal|nombre3=J.|apellidos4=Singer|nombre4=Y.}}</ref> desarrollaron un método que utiliza medidas directas de las [[Matriz hessiana|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<ref>{{Cita publicación|título=Adaptive Stochastic Approximation by the Simultaneous Perturbation Method|apellidos=Spall|nombre=J. C.|fecha=2000|publicación=IEEE Transactions on Automatic Control|volumen=45|número=10|páginas=1839−1853|doi=10.1109/TAC.2000.880982}}</ref><ref>{{Cita publicación|título=Feedback and Weighting Mechanisms for Improving Jacobian Estimates in the Adaptive Simultaneous Perturbation Algorithm|apellidos=Spall|nombre=J. C.|fecha=2009|publicación=IEEE Transactions on Automatic Control|volumen=54|número=6|páginas=1216–1229|doi=10.1109/TAC.2009.2019793}}</ref><ref>{{Cita libro|apellidos=Bhatnagar|nombre=S.|título=Stochastic Recursive Algorithms for Optimization: Simultaneous Perturbation Methods|url=https://archive.org/details/stochasticrecurs0000bhat|año=2013|editorial=Springer|isbn=978-1-4471-4284-3|ubicación=London|apellidos2=Prasad|nombre2=H. L.|apellidos3=Prashanth|nombre3=L. A.}}</ref> 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<ref>{{Cita publicación|título=A Newton-Raphson Version of the Multivariate Robbins-Monro Procedure|url=https://archive.org/details/sim_annals-of-statistics_1985-03_13_1/page/236|apellidos=Ruppert|nombre=D.|fecha=1985|publicación=Annals of Statistics|volumen=13|número=1|páginas=236–245|doi=10.1214/aos/1176346589}}</ref>). 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.<ref>{{Cita publicación|título=Natural gradient works efficiently in learning|apellidos=Amari|nombre=S.|fecha=1998|publicación=Neural Computation|volumen=10|número=2|páginas=251-276|doi=10.1162/089976698300017746}}</ref> 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 ==

* {{Cita publicación|url=http://leon.bottou.org/papers/bottou-mlss-2004|título=Advanced Lectures on Machine Learning|apellidos=Bottou|nombre=Léon|fecha=2004|publicación=Stochastic Learning|editorial=Springer|volumen=3176|páginas=146–168|serie=LNAI|idioma=EN|isbn=978-3-540-23122-6}}
* {{Cita libro|apellidos=Buduma|nombre=Nikhil|título=Fundamentals of Deep Learning : Designing Next-Generation Machine Intelligence Algorithms|año=2017|editorial=O'Reilly|isbn=9781491925584|capítulo=Beyond Gradient Descent|url-capítulo=https://books.google.com/books?id=80glDwAAQBAJ&pg=PA63|apellidos2=Locascio|nombre2=Nicholas}}
* {{Cita libro|apellidos=LeCun|nombre=Yann A.|título=Neural Networks: Tricks of the Trade|año=2012|editorial=Springer|isbn=978-3-642-35288-1|páginas=9–48|capítulo=Efficient BackProp|url-capítulo=https://books.google.com/books?id=VCKqCAAAQBAJ&pg=PA9|apellidos2=Bottou|nombre2=Léon|apellidos3=Orr|nombre3=Genevieve B.|apellidos4=Müller|nombre4=Klaus-Robert}}
* {{Cita libro|apellidos=Spall|nombre=James C.|título=Introduction to Stochastic Search and Optimization|url=https://archive.org/details/introductiontost0000spal|año=2003|editorial=John Wiley & Sons|isbn=978-0-471-33052-3}}

== Véase también ==

* [[Aprendizaje supervisado]]
* [[Aprendizaje automático online]]
* [[Descenso de gradiente estocástico|Descenso de gradiente estocástica]]

== Enlaces externos ==

* [http://codingplayground.blogspot.it/2013/05/stocastic-gradient-descent.html Uso del descenso de gradiente estocástico en C++, Boost, Ublas para regresión lineal (en inglés)]
* [https://studyofai.com/2018/03/16/machine-learning-algorithms-explained-clearly/ Algoritmos de aprendizaje automático (en inglés)]
* {{Cita web|url=https://www.youtube.com/watch?v=IHZwWFHWa-w&list=PLZHQObOWTQDNU6R1_67000Dx_ZCJB-3pi&index=2|título=(Video) Gradient Descent, How Neural Networks Learn|fecha=16 de octubre de 2017|editorial=3Blue1Brown|idioma=EN|urlarchivo=https://web.archive.org/web/20230108054344/https://www.youtube.com/watch?v=IHZwWFHWa-w&list=PLZHQObOWTQDNU6R1_67000Dx_ZCJB-3pi&index=2|fechaarchivo=8 de enero de 2023|fechaacceso=12 de julio de 2023|deadurl=}}
* {{Cita publicación|url=https://distill.pub/2017/momentum/|título=Why Momentum Really Works|apellidos=Goh|fecha=4 de abril de 2017|publicación=Distill|volumen=2|número=4|doi=10.23915/distill.00006}} Documento interactivo que explica el ''momentum''. 

== Referencias ==
{{listaref|2}}

{{Control de autoridades}}
[[Categoría:Redes neuronales artificiales]]
[[Categoría:Aprendizaje automático]]