Descenso de gradiente estocástico

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))]}$.

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]

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

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]

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.

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.