Descenso de gradiente estocástico

El descenso de gradiente estocástico ( SGD ) es un método iterativo para optimizar una función objetivo con propiedades de suavidad adecuadas (por ejemplo, diferenciabilidad o subdiferenciabilidad ). Se puede considerar como una aproximación estocástica de la optimización del descenso del gradiente , ya que reemplaza el gradiente real calculado a partir del conjunto de datos completo con una estimación calculada a partir de un subconjunto de datos seleccionado al azar [1] . Esto reduce los recursos informáticos involucrados. y ayuda a lograr una mayor tasa de iteración a cambio de una menor tasa de convergencia [2] . Se logra un efecto particularmente grande en aplicaciones relacionadas con el procesamiento de big data .

Aunque la idea básica de la aproximación estocástica se remonta al algoritmo de Robbins-Monroe de la década de 1950 [3] , el descenso de gradiente estocástico se ha convertido en una importante técnica de optimización en el aprendizaje automático [1] .

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

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

donde se debe estimar la minimización del parámetro . Cada término de suma generalmente se asocia con la observación enésima en el conjunto de datos utilizado para el entrenamiento. $w$ ${\ estilo de visualización Q (w)}$ $Q_{yo}$ $i$

En estadística clásica, los problemas de minimización de sumas surgen en el método de mínimos cuadrados y en el método de máxima verosimilitud (para observaciones independientes). La clase general de estimadores que surgen como minimización de sumas se denomina estimadores M . Sin embargo, ya a fines del siglo XX, se notó que el requisito de incluso la minimización local es demasiado restrictivo para algunos problemas del método de máxima verosimilitud [4] . Por lo tanto, los teóricos estadísticos modernos a menudo consideran los puntos estacionarios de la función de probabilidad (o los ceros de su derivada, la función de puntuación y otros métodos de estimación de ecuaciones ).

El problema de la minimización de la suma también surge cuando se minimiza el riesgo empírico . En este caso, es el valor de la función de pérdida en el -ésimo ejemplo, y es el riesgo empírico. ${\ Displaystyle Q_ {i} (w)}$ $i$ ${\ estilo de visualización Q (w)}$

Cuando se utiliza para minimizar la función anterior, el método de descenso de gradiente estándar (o "por lotes") realiza las siguientes iteraciones:

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

donde es el tamaño del paso, llamado tasa de aprendizaje en el aprendizaje automático. $\eta$

En muchos casos, las funciones sumables tienen una forma simple, lo que permite cálculos de bajo costo para la suma de funciones y el gradiente de la suma. Por ejemplo, en estadística, el uso de familias exponenciales de un parámetro permite el cálculo económico de la función y el gradiente.

Sin embargo, en otros casos, calcular el gradiente de la suma puede requerir costosos cálculos de gradiente para todas las funciones sumables. En un conjunto de entrenamiento grande, en ausencia de fórmulas simples, calcular las sumas de los gradientes se vuelve muy costoso, ya que calcular el gradiente de la suma requiere calcular los gradientes de los términos individuales de la suma. Para reducir la cantidad de cómputo, el descenso de gradiente estocástico selecciona un subconjunto de funciones sumables en cada iteración del algoritmo. Este enfoque es especialmente efectivo para grandes problemas de aprendizaje automático [5] .

Método iterativo

En el descenso de gradiente estocástico ("en línea"), el gradiente real se aproxima mediante el gradiente de un ejemplo de entrenamiento ${\ estilo de visualización Q (w)}$

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

Al ejecutar el conjunto de entrenamiento, el algoritmo realiza el recálculo anterior para cada ejemplo de entrenamiento. Puede tomar varias pasadas sobre el conjunto de datos de entrenamiento para lograr la convergencia del algoritmo. Antes de cada nueva pasada, los datos del conjunto se barajan para eliminar la posibilidad de hacer un bucle en el algoritmo. Las implementaciones típicas pueden usar una tasa de aprendizaje adaptable mejorar la convergencia.

En pseudocódigo , el descenso de gradiente estocástico se puede representar de la siguiente manera:

Elija un vector de parámetros inicial y una tasa de aprendizaje . $w$ $\eta$
Repetir hasta alcanzar un mínimo aproximado:
- Mezcla aleatoriamente los ejemplos en el conjunto de entrenamiento.
- cumplir _ ${\ estilo de visualización i = 1,2,...,n}$
  - $\!w:=w-\eta \nabla Q_{i}(w).$

Una compensación entre calcular el gradiente real y el gradiente sobre un solo ejemplo de entrenamiento puede ser calcular el gradiente sobre más de un ejemplo de entrenamiento, llamado "mini-lote", en cada paso. Esto puede ser significativamente mejor que el descenso de gradiente estocástico "verdadero" descrito, ya que el código puede usar bibliotecas de formas vectoriales lugar de cálculos separados en cada paso. También puede dar como resultado una convergencia más suave, ya que el gradiente calculado en cada paso se promedia en más ejemplos de entrenamiento.

La convergencia del descenso del gradiente estocástico se ha analizado utilizando las teorías de minimización convexa y aproximación estocástica . De forma simplificada, el resultado se puede representar de la siguiente manera: cuando la tasa de aprendizaje disminuye a una tasa adecuada, dados supuestos relativamente débiles, el descenso del gradiente estocástico converge casi con seguridad al mínimo global si la función objetivo es convexa o pseudoconvexa , de lo contrario, el método converge casi con certeza al mínimo local [6] [7] . De hecho, esto es una consecuencia del teorema de Robbins-Sigmund [8] . $\eta$

Ejemplo

Supongamos que queremos aproximar una recta mediante un conjunto de entrenamiento con muchas observaciones y respuestas correspondientes usando el método de mínimos cuadrados . La función objetivo de minimización será ${\sombrero {y}}=\!w_{1}+w_{2}x$ $(x_{1},x_{2},\ldots,x_{n})$ $({\sombrero {y_{1}}},{\sombrero {y_{2}}},\ldots,{\sombrero {y_{n}}})$

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}\ derecha)^{2}.

La última línea del pseudocódigo anterior para la tarea se convierte en

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

Tenga en cuenta que en cada iteración (que también se denomina remuestreo), solo se calcula el gradiente en un punto en lugar de calcular sobre el conjunto de todas las muestras. $x_i$

La diferencia clave en comparación con el descenso de gradiente estándar (por lotes) es que solo se usa una parte de los datos del conjunto completo en cada paso, y esta parte se elige aleatoriamente en cada paso.

Aplicaciones notables

El descenso de gradiente estocástico es un algoritmo popular para entrenar una amplia gama de modelos en aprendizaje automático , en particular en máquinas de vectores de soporte (lineales) , en regresión logística (ver por ejemplo Vowpal Wabbit ) y en modelos probabilísticos gráficos [9] . Cuando se combina con el algoritmo de retropropagación , es el algoritmo estándar de facto para entrenar redes neuronales artificiales [10] . Su aplicación también se ha visto en la comunidad geofísica , especialmente para aplicaciones de inversión de forma de onda completa (FWI) [11] .

El descenso de gradiente estocástico compite con el algoritmo L-BFGS , que también es muy utilizado. El descenso de gradiente estocástico se ha utilizado desde al menos 1960 para entrenar modelos de regresión lineal bajo el nombre ADALINE [12] .

Otro algoritmo de descenso de gradiente estocástico es el filtro adaptativo de mínimos cuadrados medios [ ( LMS) .

Variedades y modificaciones

Hay muchas modificaciones al algoritmo de descenso de gradiente estocástico. En particular, en el aprendizaje automático, el problema es la elección de la tasa de aprendizaje (tamaño de paso): con un paso grande, el algoritmo puede divergir, y con un paso pequeño, la convergencia es demasiado lenta. Para resolver este problema, puede usar el programa de tasa de aprendizaje , donde la tasa de aprendizaje disminuye a medida que aumenta el número de iteraciones . Al mismo tiempo, en las primeras iteraciones, los valores de los parámetros cambian significativamente y, en iteraciones posteriores, solo se refinan. Dichos horarios se conocen desde el trabajo de McQueen sobre k -means clustering [ 13] . En las secciones 4.4, 6.6 y 7.5 de Spall (2003) [14] se dan algunos consejos prácticos sobre la selección de pasos en algunas variantes de SGD . $\eta _{t}$ $t$

Cambios Implícitos (ISGD)

Como se mencionó anteriormente, el descenso de gradiente estocástico clásico suele ser sensible a la tasa de aprendizaje . La convergencia rápida requiere una tasa de aprendizaje grande y rápida, pero esto puede causar inestabilidad numérica . El problema se puede resolver principalmente [15] considerando el cambio implícito en , cuando el gradiente estocástico se vuelve a calcular en la siguiente iteración, y no en la actual. $\eta$

w^{nuevo}:=w^{antiguo}-\eta \nabla Q_{i}(w^{nuevo}).

Esta igualdad es implícita porque aparece en ambos lados de la igualdad. Esta es la forma estocástica del método del gradiente proximal , ya que el recálculo se puede expresar como $w^{nuevo}$

w^{nuevo}:=\arg \min _{w}\{Q_{i}(w)+{\frac {1}{2\eta }}||ww^{antiguo}||^ {2}\}.

Como ejemplo, considere el método de mínimos cuadrados con propiedades y observaciones . Queremos decidir: ${\displaystyle x_{1},\ldots,x_{n}\in \mathbb {R} ^{p))$ $y_{1},\ldots,y_{n}\en \mathbb {R}$

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

donde significa el producto escalar . ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p))$

Tenga en cuenta que puede tener "1" como primer elemento. El descenso de gradiente estocástico clásico funciona así $X$

{\displaystyle w^{nuevo}=w^{antiguo}+\eta (y_{i}-x_{i}'w^{antiguo})x_{i))

donde se distribuye uniformemente entre 1 y . Mientras que en teoría este procedimiento converge bajo supuestos relativamente moderados, en la práctica el procedimiento puede ser muy inestable. En particular, si se configuran incorrectamente, tienen valores propios absolutos grandes con alta probabilidad y el procedimiento puede divergir en varias iteraciones. Por el contrario, el descenso de gradiente estocástico implícito ( ISGD ) se puede expresar como $i$ $norte$ $\eta$ $yo-\eta x_{i}x_{i}'$

w^{nuevo}=w^{antiguo}+{\frac {\eta }{1+\eta ||x_{i}||^{2}}}(y_{i}-x_{i }'w^{antiguo})x_{i}.

El procedimiento se mantendrá numéricamente estable para casi todos , ya que la tasa de aprendizaje ahora está normalizada. Tal comparación entre el descenso de gradiente estocástico clásico y explícito en el método de mínimos cuadrados es muy similar a la comparación entre el filtro de mínimos cuadrados medios ( inglés mínimos cuadrados medios , LMS) y el filtro de mínimos cuadrados normalizados ( inglés normalizado filtro de mínimos cuadrados medios , NLM). $\eta$

Aunque la solución analítica para ISGD solo es posible en el método de mínimos cuadrados, el procedimiento se puede implementar de manera efectiva en una amplia gama de modelos. En particular, suponga que depende de solo como una combinación lineal de las propiedades de , de modo que podamos escribir , donde una función de valor real puede depender de , pero no directamente, solo a través de . El método de mínimos cuadrados satisface esta condición y, por lo tanto, la regresión logística y la mayoría de los modelos lineales generalizados satisfacen esta condición . Por ejemplo, en mínimos cuadrados y en regresión logística , donde es la función logística . En la regresión de Poisson , y así sucesivamente. ${\ Displaystyle Q_ {i} (w)}$ $w$ $x_{yo}$ ${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i))$ $q$ ${\ estilo de visualización x_ {i}, y_ {i}}$ $w$ $x_{i}'w$ $q(x_{i}'w)=y_{i}-x_{i}'w$ $q(x_{i}'w)=y_{i}-S(x_{i}'w)$ $S(u)=e^{u}/(1+e^{u})$ ${\displaystyle q(x_{i}'w)=y_{i}-e^{x_{i}'w))$

Bajo tales condiciones, ISGD es fácil de implementar de la siguiente manera. Sea , donde es un número. Entonces ISGD es equivalente a $f(\xi )=\eta q(x_{i}'w^{antiguo}+\xi ||x_{i}||^{2})$ $\xi$

w^{nuevo}=w^{antiguo}+\xi ^{\ast }x_{i},\;\xi ^{\ast }=f(\xi ^{\ast }).

El factor de escala se puede encontrar dividiendo en dos , porque en la mayoría de los modelos, como los modelos lineales generalizados anteriores, la función disminuye, y luego los límites de búsqueda serán . ${\ estilo de visualización \ xi ^ {\ ast} \ in \ mathbb {R}}$ $q$ ${\ estilo de visualización \ xi ^ {\ ast}}$ ${\ estilo de visualización [\ min (0, f (0)), \ max (0, f (0))]}$

Impulso

Desarrollos más recientes incluyen el método de impulso , que apareció en el artículo de Rumelhart , Hinton y Williams sobre el aprendizaje de retropropagación [16] . El descenso de gradiente estocástico de impulso recuerda el cambio en cada iteración y determina el siguiente cambio como una combinación lineal del gradiente y el cambio anterior [17] [18] : ${\ estilo de visualización \ Delta w}$

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

{\ estilo de visualización w: = w + \ Delta w}

eso lleva a

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

donde se debe estimar el parámetro , que minimiza , y es el tamaño del paso (a veces llamado tasa de aprendizaje en aprendizaje automático). $w$ ${\ estilo de visualización Q (w)}$ $\eta$

El nombre "momentum" se origina en el momento en la física: el vector de peso , entendido como el camino de una partícula a lo largo del espacio de parámetros [16] , experimenta aceleración del gradiente de la función de pérdida (" fuerza "). A diferencia del descenso de gradiente estocástico clásico, el método intenta mantener el progreso en la misma dirección evitando fluctuaciones. Momentum ha sido utilizado con éxito por científicos informáticos para entrenar redes neuronales artificiales durante varias décadas [19] . $w$

Promedio

El descenso de gradiente estocástico promedio , desarrollado de forma independiente por Ruppert y Polyak a fines de la década de 1980, es un descenso de gradiente estocástico convencional que registra la media de un vector de parámetros. Es decir, el recálculo es el mismo que en el método de descenso de gradiente estocástico habitual, pero el algoritmo también rastrea [20]

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

Cuando se completa la optimización, el vector de parámetros medios toma el lugar de w .

AdaGrado

AdaGrad ( algoritmo de gradiente adaptativo ), publicado en 2011 [21] [22] , es una modificación del algoritmo de descenso de gradiente estocástico con una tasa de aprendizaje separada para cada parámetro . Informalmente, esto aumenta la tasa de aprendizaje para parámetros con datos dispersos y disminuye la tasa de aprendizaje para parámetros con datos menos dispersos. Esta estrategia aumenta la tasa de convergencia en comparación con el método de descenso de gradiente estocástico estándar en condiciones donde los datos son escasos y los parámetros correspondientes son más informativos. Ejemplos de tales aplicaciones son el procesamiento del lenguaje natural y el reconocimiento de patrones [21] . El algoritmo tiene una tasa de aprendizaje base pero se multiplica por los elementos del vector que es la diagonal de la matriz del producto exterior $\eta$ ${\ estilo de visualización \ {G_ {j, j}}\}}$

G=\sum_{\tau =1}^{t}g_{\tau}g_{\tau}^{\mathsf {T))

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

{\displaystyle G_{j,j}=\sum_{\tau =1}^{t}g_{\tau,j}^{2))

Este vector se actualiza después de cada iteración. Fórmula de conversión

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

[a]

o, escribiendo como recálculo por parámetros,

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

Cada elemento proporciona un multiplicador de tasa de aprendizaje aplicado a un parámetro . Debido a que el denominador de este factor, , es la norma ℓ2 de la derivada anterior, los cambios grandes de parámetros se atenúan, mientras que los parámetros que reciben cambios pequeños reciben tasas de aprendizaje más altas [19] . $\{G_{(i,i)}\}$ $Wisconsin}$ ${\displaystyle {\sqrt {G_{i))}={\sqrt {\sum_{\tau =1}^{t}g_{\tau}^{2))))$

Aunque el algoritmo se desarrolló para problemas convexos , AdaGrad se ha utilizado con éxito para la optimización no convexa [23] .

RMSProp

RMSProp (de Root Mean Square Propagation ) es un método en el que la tasa de aprendizaje se ajusta para cada parámetro. La idea es dividir la tasa de aprendizaje de los pesos por las medias móviles de los gradientes recientes de ese peso [24] . Entonces, el primer promedio móvil se calcula en términos de rms

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

donde, es el factor de olvido. $\gama$

Las opciones se actualizan como

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

RMSProp ha mostrado una buena adaptación de la tasa de aprendizaje en diferentes aplicaciones. RMSProp puede considerarse como una generalización de Rprop . El método puede trabajar con minipaquetes, no solo con paquetes completos [25] .

Adán

Adam [26] (abreviatura de Adaptive Moment Estimation ) es una actualización del optimizador RMSProp . Este algoritmo de optimización utiliza medias móviles tanto de los gradientes como de los segundos momentos de los gradientes. Si se dan los parámetros , y la función de pérdida , donde refleja el índice de la iteración actual (el informe comienza con ), el recálculo del parámetro por el algoritmo de Adam viene dado por las fórmulas ${\ estilo de visualización w^{(t)}}$ ${\ estilo de visualización L ^ {(t)}}$ $t$ ${\ estilo de visualización 0}$

m_{w}^{(t+1)}\leftarrow \beta_{1}m_{w}^{(t)}+(1-\beta_{1})\nabla_{w} L^{(t)}

v_{w}^{(t+1)}\leftarrow \beta_{2}v_{w}^{(t)}+(1-\beta_{2})(\nabla_{w }L^{(t)})^{2}

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

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

w^{(t+1)}\leftarrow w^{(t)}-\eta {\frac ({\hat {m))_{w))({\sqrt ({\hat {v }}_{w}}}+\épsilon }}

donde se usa un pequeño aditivo para evitar la división por 0, y y son los coeficientes de olvido para los gradientes y los segundos momentos de los gradientes, respectivamente. El cuadrado y la raíz cuadrada se calculan elemento por elemento. $\epsilon$ $\beta_{1}$ $\beta _{2}$

Descenso de gradiente natural y kSGD

El descenso de gradiente estocástico basado en Kalman ( kSGD ) [27] es un algoritmo en línea y fuera de línea para aprender parámetros para problemas estadísticos para modelos de cuasi-verosimilitud , que incluye modelos lineales , modelos no lineales , modelos lineales generalizados y redes neuronales con pérdidas rms como caso especial. Para problemas de aprendizaje en línea, kSGD es un caso especial del filtro de Kalman para problemas de regresión lineal, un caso especial del filtro de Kalman extendido para problemas de regresión no lineal, y puede considerarse como un método incremental de Gauss-Newton . Además, debido a la relación de kSGD con el filtro de Kalman y la relación del descenso de gradiente natural [28] con el filtro de Kalman [29] , kSGD es una mejora importante en el popular método de descenso de gradiente natural.

Ventajas de kSGD sobre otros métodos:

(1) insensible al número de condiciones del problema, [b] (2) tiene una opción robusta de hiperparámetros, (3) tiene una condición de parada.

La desventaja de kSGD es que el algoritmo requiere almacenar una matriz de covarianza densa entre iteraciones y, en cada iteración, se debe encontrar el producto del vector y la matriz.

Para describir el algoritmo, asumimos que la función , donde , se define usando para que ${\ Displaystyle Q_ {i} (w)}$ $w\en \mathbb {R} ^{p}$ ${\displaystyle (Y_{i},X_{i})\en \mathbb {R} \times \mathbb {R} ^{d))$

\nabla_{w}Q_{i}(w)={\frac {Y_{i}-\mu (X_{i},w)}{V(\mu (X_{i},w) )}}\nabla _{w}\mu (X_{i},w)

donde es la función de promedio (es decir, el valor esperado de ) y es la función de varianza (es decir, la varianza de ). Entonces el recálculo del parámetro y el recálculo de la matriz covariante vienen dados por las siguientes expresiones ${\ estilo de visualización \ mu (X_{i}, w)}$ $Y_{yo}$ $X_{yo}$ $V(\mu (X_{i},w))$ $Y_{yo}$ $X_{yo}$ ${\ estilo de visualización w (t + 1)}$ ${\ estilo de visualización M (t + 1)}$

p=\nabla _{w}\mu (X_{t+1},w(t))

m=\mu (X_{t+1},w(t))

{\ estilo de visualización v = M (t) p}

s=\min \lbrace \gamma _{1},\max \lbrace \gamma _{2},V(m)\rbrace \rbrace +v^{\mathsf {T}}p

w(t+1)=w(t)+{\frac {Y_{t+1}-m}{s}}v

M(t+1)=M(t)-{\frac {1}{s}}vv^{\mathsf {T}}

donde están los hiperparámetros. El recálculo puede hacer que la matriz covariante se vuelva indefinida, lo que se puede evitar multiplicando matriz por matriz. puede ser cualquier matriz simétrica definida positiva, pero generalmente se toma la matriz identidad. Como señaló Patel [27] , para todos los problemas, excepto para la regresión lineal, se requieren corridas repetidas para asegurar la convergencia del algoritmo, pero no se dan detalles teóricos o de implementación. Un método de lotes múltiples fuera de línea estrechamente relacionado para la regresión no lineal, analizado por Bertsekas [30] , usó el factor de olvido al volver a calcular la matriz covariante para probar la convergencia. ${\ estilo de visualización \ gamma _ {1}, \ gamma _ {2}}$ $Monte)$ ${\ estilo de visualización M (0)}$

Métodos de segundo orden

Se sabe que el análogo estocástico del algoritmo estándar (determinista) de Newton-Raphson (el método de "segundo orden") proporciona una forma asintóticamente óptima o casi óptima de optimización iterativa en condiciones de aproximación estocástica. Bird, Hansen, Nosedal y Singer [31] desarrollaron un método que utiliza el cálculo directo de las matrices hessianas de los términos de la suma en la función de riesgo empírica . Sin embargo, una determinación directa de las matrices hessianas requeridas para la optimización puede no ser posible en la práctica. Spall et al . han proporcionado métodos prácticos y teóricos para una versión de segundo orden del algoritmo SGD que no requiere información hessiana directa . Estos métodos, aunque no requieren información directamente sobre la arpillera, se basan en los valores de los términos de la suma en la función de riesgo empírica dada anteriormente, o en los valores de los gradientes de los términos de la suma (es decir, entrada SGD) . En particular, la optimización de segundo orden se puede lograr asintóticamente sin calcular directamente las matrices hessianas de los términos de la suma en la función de riesgo empírica.

Comentarios

↑ es el producto elemental de . $\circ$
↑ Para un problema de regresión lineal, la varianza de la función objetivo de kSGD (es decir, el error total y la varianza) por iteración es igual con una probabilidad que tiende a 1 a una tasa que depende de , donde es la varianza de los residuos. Además, para una elección particular de , se puede demostrar que la varianza de iteración de la función objetivo de kSGD es igual con una probabilidad que tiende a 1 a una tasa que depende de , donde es el parámetro óptimo. $k$ ${\frac{1+\epsilon}{k}}p\sigma^{2}$ ${\ estilo de visualización \ épsilon \ en (0,1)}$ ${\ estilo de visualización \ sigma ^ {2}}$ ${\ estilo de visualización \ gamma _ {1}, \ gamma _ {2}}$ $k$ ${\frac {(1+\epsilon)^{2}}{2k^{2}}}\Vert w(0)-w_{*}\Vert_{2}^{2}$ ${\ estilo de visualización \ épsilon \ en (0,1)}$ ${\ estilo de visualización w_ {*}}$

Véase también

Descenso de coordenadas : cambia una coordenada a la vez
clasificador lineal
Aprendizaje automático en línea

Notas

↑ 12 Taddy , 2019 , pág. 303–307.
↑ Bottou, Bousquet, 2012 , pág. 351–368.
↑ Mei, 2018 , pág. E7665–E7671.
↑ Ferguson, 1982 , pág. 831–834.
↑ Bottou, Bousquet, 2008 , pág. 161–168.
↑ Botto, 1998 .
↑ Kiwiel, 2001 , pág. 1–25.
↑ Robbins, Siegmund, 1971 .
↑ Finkel, Kleeman, Manning, 2008 .
↑ LeCun et al., 2012 , pág. 9-48.
↑ Díaz, Guitton, 2011 , pág. 2804-2808.
↑ Avi Pfeffer. CS181 Clase 5 - Perceptrones (Universidad de Harvard) . (indefinido) (enlace no disponible)
↑ Oscurecer, Moody, 1990 .
↑ Spall, 2003 .
↑ Toulis, Airoldi, 2017 , pág. 1694-1727
↑ 1 2 Rumelhart, Hinton, Williams, 1986 , pág. 533–536.
↑ Sutskever, Martens, Dahl, Hinton, 2013 , pág. 1139-1147.
↑ Sutskever, Ilya (2013). Entrenamiento de redes neuronales recurrentes (PDF) (Ph.D.). Universidad de Toronto. Archivado (PDF) desde el original el 28 de febrero de 2020 . Consultado el 01-03-2020 . Parámetro obsoleto utilizado |deadlink=( ayuda )
↑ 1 2 Matthew D. Zeiler (2012), ADADELTA: Un método de tasa de aprendizaje adaptativo, arΧiv : 1212.5701 [cs.LG].
↑ Polyak, Juditsky, 1992 , pág. 838–855.
↑ 1 2 Duchi, Hazan, Singer, 2011 , p. 2121-2159.
↑ José Perla (2014). Notas sobre AdaGrad (enlace no disponible) . Consultado el 1 de marzo de 2020. Archivado desde el original el 30 de marzo de 2015. (indefinido)
↑ Gupta, Bengio, Weston, 2014 , pág. 1461-1492
↑ Tieleman, Tijmen y Hinton, Geoffrey (2012). Clase 6.5-rmsprop: Divida el gradiente por un promedio móvil de su magnitud reciente. CURSO: Redes Neuronales para Aprendizaje Automático
↑ Hinton, Geoffrey Descripción general del descenso de gradiente de minilotes (enlace no disponible) 27–29. Consultado el 27 de septiembre de 2016. Archivado desde el original el 23 de noviembre de 2016. (indefinido)
↑ Kingma Diederik, Jimmy Ba (2014), Adam: Un método para la optimización estocástica, arΧiv : 1412.6980 [cs.LG].
↑ 12 Patel , 2016 , pág. 2620–2648.
↑ Cichocki, Chen, Amari, 1997 , pág. 1345-1351.
↑ Ollivier Yann (2017), Gradiente natural en línea como filtro de Kalman, arΧiv : 1703.00209 [stat.ML].
↑ Bertsekas, 1996 , pág. 807–822.
↑ Byrd, Hansen, Nocedal, Singer, 2016 , pág. 1008–1031.
↑ Spall, 2000 , pág. 1839-1853.
↑ Spall, 2009 , pág. 1216–1229.
↑ Bhatnagar, Prasad, Prashanth, 2013 .
↑ Ruppert, 1985 , pág. 236–245.

Literatura

León Bottou, Olivier Bousquet. Las compensaciones del aprendizaje a gran escala // Optimización para el aprendizaje automático / Suvrit Sra, Sebastian Nowozin, Stephen J. Wright (ed.). - Cambridge: MIT Press, 2012. - ISBN 978-0-262-01646-9 .
songmei. Una vista de campo medio del paisaje de las redes neuronales de dos capas // Actas de la Academia Nacional de Ciencias . - Academia Nacional de Ciencias , 2018. - Vol. 115 , edición. 33 . -doi : 10.1073/ pnas.1806579115 . —PMID 30054315 .
Matt Taddy. Descenso de gradiente estocástico // Ciencia de datos comerciales: combinación de aprendizaje automático y economía para optimizar, automatizar y acelerar las decisiones comerciales. — Nueva York: McGraw-Hill, 2019. — ISBN 978-1-260-45277-8 .
Thomas S. Ferguson. Una estimación de máxima verosimilitud inconsistente // Revista de la Asociación Estadounidense de Estadística. - 1982. - T. 77 , núm. 380 . -doi : 10.1080/ 01621459.1982.10477894 . — .
León Bottou, Olivier Bousquet. Las ventajas y desventajas del aprendizaje a gran escala //Avances en Sistemas de Procesamiento de Información Neural . - 2008. - T. 20.

León Bottou. Algoritmos en línea y aproximaciones estocásticas // Aprendizaje en línea y redes neuronales. - Prensa de la Universidad de Cambridge, 1998. - ISBN 978-0-521-65263-6 .

Krzysztof C. Kiwiel. Convergencia y eficiencia de los métodos de subgradiente para la minimización cuasiconvexa // Programación matemática, Serie A. - Berlín, Heidelberg: Springer, 2001. - Vol. 90 , no. 1 . — pág. 1–25. — ISSN 0025-5610 . -doi : 10.1007/ PL00011414 .
Herbert Robbins, David O. Siegmund. Un teorema de convergencia para casi supermartingalas no negativas y algunas aplicaciones // Métodos de optimización en estadística / Jagdish S. Rustagi (ed.). — Prensa académica, 1971.
Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning. Análisis de campo aleatorio condicional, eficiente y basado en características // Proc. Reunión Anual de la ACL . — 2008.
Yann A. LeCun, Leon Bottou, Genevieve B. Orr, Klaus-Robert Muller. Backprop eficiente // Redes neuronales: Trucos del oficio / Grégoire Montavon, Geneviève B. Orr, Klaus-Robert Müller (Eds.). - Berlin Heidelberg: Springer, 2012. - T. 7700. - (Lecture Notes in Computer Science). - ISBN 978-3-642-35288-1 .
Esteban Díaz, Antoine Guitton. Inversión rápida de forma de onda completa con diezmado de disparos aleatorios // Resúmenes ampliados del programa técnico de SEG . — 2011.
Christian Oscurecer, John Moody. Conf. Conjunta Internacional on Neural Networks (IJCNN) // Agrupación rápida adaptativa de k-medias: algunos resultados empíricos . —IEEE, 1990.
Spall JC Introducción a la búsqueda y optimización estocástica: estimación, simulación y control. - Hoboken, Nueva Jersey: Wiley, 2003. - ISBN 0-471-33052-3 .
Panos Toulis, Edoardo Airoldi. Propiedades asintóticas y de muestras finitas de estimadores basados en gradientes estocásticos // Annals of Statistics. - 2017. - T. 45 , núm. 4 . -doi : 10.1214 / 16-AOS1506 . -arXiv : 1408.2923 . _
Spall JC Aproximación estocástica adaptativa por el método de perturbación simultánea // Transacciones IEEE en control automático. - 2000. - T. 45 , núm. 10 _ -doi : 10.1109/ TAC.2000.880982 .
Spall JC Mecanismos de retroalimentación y ponderación para mejorar las estimaciones jacobianas en el algoritmo de perturbación simultánea adaptativa // Transacciones IEEE en control automático. - 2009. - T. 54 , núm. 6 _ -doi : 10.1109/ TAC.2009.2019793 .
Bhatnagar S., Prasad HL, Prashanth LA Algoritmos recursivos estocásticos para la optimización: Métodos de perturbación simultánea. — Londres: Springer, 2013. — ISBN 978-1-4471-4284-3 .
Ruppert D. Una versión de Newton-Raphson del procedimiento multivariado de Robbins-Monro // Annals of Statistics . - 1985. - T. 13 , núm. 1 . doi : 10.1214 / años/1176346589 .
David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams. Aprendizaje de representaciones por errores de retropropagación // Naturaleza . - 1986. - Octubre ( vol. 323 , ed. 6088 ). -doi : 10.1038/ 323533a0 . - .
Ilya Sutskever, James Martens, George Dahl, Geoffrey E. Hinton. Sobre la importancia de la inicialización y el impulso en el aprendizaje profundo // En Actas de la 30.ª conferencia internacional sobre aprendizaje automático (ICML-13) / Sanjoy Dasgupta, David Mcallester (ed.). - Atlanta, GA, 2013. - T. 28.
Boris T. Polyak, Anatoli B. Juditsky. Aceleración de la aproximación estocástica por promedio // SIAM J. Control Optim.. - 1992. - Vol. 30 , no. 4 . -doi : 10.1137/ 0330046 .
John Duchi, Elad Hazan, Yoram Singer. Métodos de subgradiente adaptables para aprendizaje en línea y optimización estocástica // JMLR . - 2011. - T. 12 .
Maya R. Gupta, Samy Bengio, Jason Weston. Entrenamiento de clasificadores altamente multiclase // JMLR. - 2014. - T. 15 , núm. 1 .
Método de gradiente estocástico basado en Patel V. Kalman con condición de parada e insensibilidad al condicionamiento // SIAM Journal on Optimization. - 2016. - T. 26 , núm. 4 . — ISSN 1052-6234 . -doi : 10.1137/ 15M1048239 . -arXiv : 1512.01139 . _
Cichocki A., Chen T., Amari S. Análisis de estabilidad de algoritmos de aprendizaje para separación ciega de fuentes // Redes neuronales. - 1997. - noviembre ( vol. 10 , número 8 ). - doi : 10.1016/S0893-6080(97)00039-7 . —PMID 12662478 .
Byrd RH, Hansen SL, Nocedal J., Singer Y. Un método estocástico cuasi-newton para la optimización a gran escala // SIAM Journal on Optimization. - 2016. - T. 26 , núm. 2 . -doi : 10.1137/ 140954362 . -arXiv : 1401.7020 . _
Bertsekas D. Métodos de mínimos cuadrados incrementales y el filtro de Kalman extendido // SIAM Journal on Optimization. - 1996. - T. 6 , núm. 3 . - S. 807-822 . — ISSN 1052-6234 . -doi : 10.1137/ S1052623494268522 .

Lectura para leer más

Dimitri P. Bertsekas. programación no lineal. — 2do. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 978-1-886529-00-7 . .
Dimitri P. Bertsekas. Análisis y Optimización Convexa. — Atenea científica, 2003.
León Bottou. Aprendizaje estocástico // Conferencias avanzadas sobre aprendizaje automático . - Springer, 2004. - T. 3176. - S. 146-168. — (LNIA). - ISBN 978-3-540-23122-6 .
Davidon WC [187–197 Nuevos algoritmos de mínimos cuadrados] // Journal of Optimization Theory and Applications. - 1976. - T. 18 , N º 2 . -doi : 10.1007/ BF00935703 .
Richard O. Duda, Peter E. Hart, David G. Stork. clasificación de patrones. — 2do. -Wiley , 2000. -ISBN 978-0-471-05669-0 .
Krzysztof C. Kiwiel. Convergencia de métodos de subgradiente aproximados e incrementales para optimización convexa // SIAM Journal on Optimization. - 2004. - T. 14 , N º 3 . - S. 807-840 . -doi : 10.1137/ S1052623400376366 .
Jan A. Snyman, Daniel N. Wilke. Optimización Matemática Práctica - Teoría Básica de Optimización y Algoritmos Basados en Gradientes . - 2. - Springer , 2018. - S. xxvi + 372. - (Optimización de Springer y sus aplicaciones Vol. 133). - ISBN 978-3-319-77585-2 .
James C. Spall. Introducción a la búsqueda y optimización estocástica. -Wiley , 2003. -ISBN 978-0-471-33052-3 . .

Enlaces

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 . 3Blue1Brown (16 de octubre de 2017). (indefinido)