Incorporating Nesterov Momentum into Adam/paper/es

Research Paper
Authors	Dozat, T.
Year	2016
Venue	ICLR Workshop
Topic area	Machine Learning
Difficulty	Research
Source	View paper

Other languages:

English
Español
中文

SummarySource

Workshop track — ICLR 2016

Resumen

Este trabajo aspira a mejorar el algoritmo de optimización Adam (Kingma y Ba, 2014), recientemente propuesto y rápidamente popularizado. Adam tiene dos componentes principales — un componente de momentum y un componente de tasa de aprendizaje adaptativa. Sin embargo, el momentum regular puede mostrarse, conceptual y empíricamente, inferior a un algoritmo similar conocido como gradiente acelerado de Nesterov (NAG). Mostramos cómo modificar el componente de momentum de Adam para aprovechar las ideas de NAG, y a continuación presentamos evidencia preliminar que sugiere que esta sustitución mejora la velocidad de convergencia y la calidad de los modelos aprendidos.

Introducción

Cuando se intenta mejorar el rendimiento de un sistema de deep learning, hay un puñado de enfoques que se pueden tomar — mejorando la estructura del modelo, quizás haciéndolo más profundo; mejorando la inicialización del modelo, de modo que la señal de error se distribuya uniformemente entre los parámetros; recopilando más datos o probando una técnica de regularización diferente para evitar el sobreajuste; y empleando un algoritmo de optimización más potente, de manera que se puedan alcanzar mejores soluciones en un tiempo razonable. Este trabajo aspira a mejorar la calidad de los modelos aprendidos proporcionando un algoritmo de aprendizaje más potente.

Muchos algoritmos de aprendizaje populares para optimizar objetivos no convexos utilizan alguna variante del descenso de gradiente estocástico (SGD); este trabajo considerará un subconjunto de tales algoritmos en su análisis. El Algoritmo 1 presenta SGD con la notación utilizada en este artículo — todos los algoritmos siguientes añadirán o modificarán esta plantilla básica:

Algoritmo 1: descenso de gradiente estocástico

Require: $\alpha_0, \dots, \alpha_T$ : las tasas de aprendizaje para cada timestep (presumiblemente atenuadas).
Require: $f_i(\theta)$ : función objetivo estocástica parametrizada por $\theta$ e indexada por el timestep $$ i $$ .
Require: $\theta_0$ : los parámetros iniciales.

Mientras $\theta_t$ no haya convergido, hacer:

t \leftarrow t + 1

g_t \leftarrow \nabla_{\theta_{t-1}} f_t(\theta_{t-1})

\theta_t \leftarrow \theta_{t-1} - \alpha_t g_t

Fin del bucle; devolver $\theta_t$ .

Trabajo relacionado

El momentum clásico (Polyak, 1964) acumula una suma decreciente (con factor de decaimiento $\mu$ ) de las actualizaciones previas en un vector de momentum $$ m $$ y reemplaza el paso de gradiente original del Algoritmo 1 por ese vector. Es decir, modificamos el algoritmo para incluir lo siguiente en cada timestep:

m_t \leftarrow \mu m_{t-1} + \alpha_t g_t \qquad (1)

\theta_t \leftarrow \theta_{t-1} - m_t \qquad (2)

Intuitivamente, esto permite al algoritmo moverse más rápido a lo largo de dimensiones de baja curvatura, donde la actualización es consistentemente pequeña pero en la misma dirección, y más lento a lo largo de dimensiones turbulentas, donde la dirección de la actualización oscila significativamente (Sutskever et al., 2013).

Sutskever et al. (2013) muestran que el gradiente acelerado de Nesterov (NAG) (Nesterov, 1983) — que tiene una cota demostrablemente mejor que el descenso de gradiente para objetivos convexos no estocásticos — puede reescribirse como una especie de momentum mejorado. Si expandimos el término $$ m_t $$ en la formulación original del momentum en la línea 2, vemos que la actualización equivale a dar un paso en la dirección del vector de momentum previo y un paso en la dirección del gradiente actual:

\theta_t = \theta_{t-1} - (\mu m_{t-1} + \alpha_t g_t) \qquad (3)

Sin embargo, el paso de momentum $\mu m_{t-1}$ no depende del gradiente actual $$ g_t $$ , por lo que podemos obtener una dirección de paso de gradiente de mayor calidad si actualizamos los parámetros con el paso de momentum antes de calcular el gradiente. Sutskever et al. (2013) proponen modificar la línea de cálculo del gradiente en el bucle del Algoritmo 1 como en la línea 4 a continuación para lograrlo:

g_t \leftarrow \nabla_{\theta_{t-1}} f_t(\theta_{t-1} - \mu m_{t-1}) \qquad (4)

m_t \leftarrow \mu m_{t-1} + \alpha_t g_t \qquad (5)

\theta_t \leftarrow \theta_{t-1} - m_t \qquad (6)

Los autores también aportan evidencia empírica de que este algoritmo es superior a SGD, momentum clásico y Hessian-Free (Martens, 2010) en objetivos de optimización convencionalmente difíciles.

Tanto el momentum clásico como NAG definen $$ m $$ como una suma decreciente sobre las actualizaciones previas; sin embargo, Adaptive moment estimation (Adam) (Kingma y Ba, 2014) lo define en cambio como una media decreciente sobre los gradientes previos (este algoritmo también incluye un componente de tasa de aprendizaje adaptativa que no se discute aquí; cf. Duchi et al. (2011) y Tieleman y Hinton (2012)).

m_t \leftarrow \mu m_{t-1} + (1 - \mu) g_t \qquad (7)

\theta_t \leftarrow \theta_{t-1} - \alpha_t \frac{m_t}{1 - \mu^t} \qquad (8)

El uso de los gradientes previos en lugar de las actualizaciones previas permite al algoritmo seguir cambiando de dirección incluso cuando la tasa de aprendizaje se ha atenuado significativamente hacia el final del entrenamiento, lo que da lugar a una convergencia de grano fino más precisa. También permite al algoritmo corregir de forma directa el "sesgo de inicialización" que surge al inicializar el vector de momentum a cero (que es para lo que sirve el término $(1 - \mu^t)$ en el denominador de la línea 8). Kingma y Ba (2014) muestran que su algoritmo supera a varios otros, incluido NAG, en un pequeño conjunto de benchmarks.

Modificando el momentum de Adam

En lo que sigue permitiremos diferentes valores de $\mu$ indexados por timestep $\mu_1, \dots, \mu_T$ para mayor claridad. Antes de modificar la regla de actualización de Adam, mostramos cómo reescribir NAG para que sea más sencillo de implementar (a costa de algo de intuitividad). En lugar de actualizar los parámetros únicamente con el paso de momentum para calcular el gradiente, deshacer ese paso para volver al estado original de los parámetros, y luego volver a tomar el paso de momentum durante la actualización real, podemos aplicar el paso de momentum del timestep $$ t+1 $$ una sola vez, durante la actualización del timestep anterior $$ t $$ en lugar de en $$ t+1 $$ :

g_t \leftarrow \nabla_{\theta_{t-1}} f_t(\theta_{t-1}) \qquad (9)

m_t \leftarrow \mu_t m_{t-1} + \alpha_t g_t \qquad (10)

\theta_t \leftarrow \theta_{t-1} - (\mu_{t+1} m_t + \alpha_t g_t) \qquad (11)

Obsérvese que la línea 11 es casi idéntica a la línea 3 — la única diferencia es que la actualización utiliza $\mu_{t+1} m_t$ en lugar de $\mu_t m_{t-1}$ . También es fácil ver que tanto el paso de momentum como el paso de gradiente dependen aquí del gradiente actual, a diferencia de lo que ocurre con el momentum clásico.

Ahora podemos usar el mismo truco con el momentum de Adam: primero reescribimos el paso de actualización de Adam en términos de $m_{t-1}$ y $$ g_t $$ , como en la línea 12, y luego sustituimos el paso de momentum siguiente por el actual, como en la línea 13 (cuidando convenientemente el sesgo de inicialización).

\theta_t \leftarrow \theta_{t-1} - \alpha_t \left( \frac{\mu_t m_{t-1}}{1 - \prod_{i=1}^{t} \mu_i} + \frac{(1 - \mu_t) g_t}{1 - \prod_{i=1}^{t} \mu_i} \right) \qquad (12)

\theta_t \leftarrow \theta_{t-1} - \alpha_t \left( \frac{\mu_{t+1} m_t}{1 - \prod_{i=1}^{t+1} \mu_i} + \frac{(1 - \mu_t) g_t}{1 - \prod_{i=1}^{t} \mu_i} \right) \qquad (13)

Cuando modificamos Adam de esta manera, obtenemos el Algoritmo 2. Sin embargo, esta forma de momentum puede combinarse en principio con otros algoritmos que utilicen tasas de aprendizaje adaptativas, como Adamax (Kingma y Ba, 2014) o Equilibrated gradient descent (EGD) (Dauphin et al., 2015).

Algoritmo 2: Nesterov-accelerated Adaptive Moment Estimation (Nadam)

Require: $\alpha_0, \dots, \alpha_T$ ; $\mu_0, \dots, \mu_T$ ; $\nu$ ; $\epsilon$ : hiperparámetros.
$m_0, n_0 \leftarrow 0$ (vectores de primer / segundo momento).

Mientras $\theta_t$ no haya convergido, hacer:

g_t \leftarrow \nabla_{\theta_{t-1}} f_t(\theta_{t-1})

m_t \leftarrow \mu_t m_{t-1} + (1 - \mu_t) g_t

n_t \leftarrow \nu n_{t-1} + (1 - \nu) g_t^2

\hat{m} \leftarrow \frac{\mu_{t+1} m_t}{1 - \prod_{i=1}^{t+1} \mu_i} + \frac{(1 - \mu_t) g_t}{1 - \prod_{i=1}^{t} \mu_i}

\hat{n} \leftarrow \frac{\nu n_t}{1 - \nu^t}

\theta_t \leftarrow \theta_{t-1} - \frac{\alpha_t \hat{m}_t}{\sqrt{\hat{n}_t} + \epsilon}

Fin del bucle; devolver $\theta_t$ .

Experimento

Para probar el rendimiento de este Adam acelerado por Nesterov (Nadam), entrenamos un autoencoder convolucional (adaptado de Jones (2015)) con tres capas convolucionales y dos capas densas en cada uno del encoder y el decoder, para comprimir imágenes del dataset MNIST (LeCun et al., 1998) a un espacio vectorial de 16 dimensiones y luego reconstruir la imagen original (una tarea conocida por su dificultad). Probamos seis algoritmos de optimización: SGD, momentum, NAG, RMSProp, Adam y Nadam, todos los cuales utilizaron corrección del sesgo de inicialización y medias decrecientes (en lugar de sumas decrecientes) cuando correspondía. La mejor tasa de aprendizaje encontrada para SGD fue $$ 0.2 $$ , para momentum / NAG fue $$ 0.5 $$ , para RMSProp fue $$ 0.001 $$ y para Adam / Nadam fue $$ 0.002 $$ . $\mu$ , $\nu$ y $\epsilon$ se fijaron en $$ 0.975 $$ , $$ 0.999 $$ y $10^{-8}$ respectivamente (con grados variables de arbitrariedad) y se dejaron sin ajustar. Los resultados de la Figura 1 muestran que aunque Nadam y Adam tienen el mayor número de hiperparámetros, alcanzan los mejores resultados incluso sin ajuste más allá de la tasa de aprendizaje (que generalmente es inevitable). De forma crucial, Nadam supera claramente a los demás algoritmos — incluido su algoritmo padre Adam — en la reducción de la pérdida de entrenamiento y de validación.

Figura 1: pérdida de entrenamiento y validación de los distintos optimizadores en el dataset MNIST.

Conclusión

Kingma y Ba (2014) muestran esencialmente cómo combinar el momentum clásico con tasas de aprendizaje adaptativas, como RMSProp o EGD, de manera limpia y elegante. Este trabajo se construye sobre esa investigación llevando su enfoque un paso más allá y mejorando uno de los componentes principales de su algoritmo sin aumentar de forma apreciable la complejidad.

Referencias

Yann Dauphin, Harm de Vries, y Yoshua Bengio. Equilibrated adaptive learning rates for non-convex optimization. En Advances in Neural Information Processing Systems, pp. 1504–1512, 2015.
John Duchi, Elad Hazan, y Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121–2159, 2011.
Mike Swarbrick Jones. Convolutional autoencoders in python/theano/lasagne. Entrada de blog (consultada el 17 de febrero de 2016), abril de 2015. URL https://swarbrickjones.wordpress.com/2015/04/29/convolutional-autoencoders-in-pythontheanolasagne/.
Diederik Kingma y Jimmy Ba. Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Yann LeCun, Corinna Cortes, y Christopher J. C. Burges. The MNIST database of handwritten digits, 1998.
James Martens. Deep learning via Hessian-free optimization. En Proceedings of the 27th International Conference on Machine Learning (ICML-10), pp. 735–742, 2010.
Yurii Nesterov. A method of solving a convex programming problem with convergence rate $$ O(1/k^2) $$ . En Soviet Mathematics Doklady, volumen 27, pp. 372–376, 1983.
Boris Teodorovich Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964.
Ilya Sutskever, James Martens, George Dahl, y Geoffrey Hinton. On the importance of initialization and momentum in deep learning. En Proceedings of the 30th International Conference on Machine Learning (ICML-13), pp. 1139–1147, 2013.
Tijmen Tieleman y Geoffrey Hinton. Lecture 6.5 — RMSprop: divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 4, 2012.