El descenso de gradiente es un algoritmo de optimización que sigue el gradiente negativo de una función objetivo para localizar el mínimo de la función.
Una limitación del descenso de gradientes es que puede atascarse en áreas planas o rebotar si la función objetivo devuelve gradientes ruidosos. Momentum es un enfoque que acelera el progreso de la búsqueda para recorrer áreas planas y suavizar los gradientes hinchables.
En algunos casos, la aceleración del impulso puede hacer que la búsqueda pierda o supere los mínimos en el fondo de cuencas o valles. El impulso de Nesterov es una extensión del impulso que implica calcular el promedio móvil decreciente de los gradientes de las posiciones proyectadas en el espacio de búsqueda en lugar de las posiciones reales en sí mismas.
Esto tiene el efecto de aprovechar los beneficios de la aceleración del impulso al tiempo que permite que la búsqueda disminuya al acercarse al óptimo y reduce la probabilidad de perderlo o sobrepasarlo.
En este tutorial, descubrirá cómo desarrollar el algoritmo de optimización Gradient Descent con Nesterov Momentum desde cero.
Después de completar este tutorial, sabrá:
- El descenso de gradiente es un algoritmo de optimización que utiliza el gradiente de la función objetivo para navegar por el espacio de búsqueda.
- La convergencia del algoritmo de optimización del descenso de gradientes se puede acelerar extendiendo el algoritmo y agregando Nesterov Momentum.
- Cómo implementar el algoritmo de optimización Nesterov Momentum desde cero y aplicarlo a una función objetivo y evaluar los resultados.
Empecemos.
Descenso de gradiente con impulso de Nesterov desde cero
Foto de Bonnie Moreland, algunos derechos reservados.
Descripción general del tutorial
Este tutorial se divide en tres partes; son:
- Descenso de gradiente
- Momento de Nesterov
- Descenso de gradiente con impulso de Nesterov
- Problema de prueba bidimensional
- Optimización del descenso de gradientes con Nesterov Momentum
- Visualización del impulso de Nesterov
Descenso de gradiente
El descenso de gradientes es un algoritmo de optimización.
Técnicamente se lo conoce como un algoritmo de optimización de primer orden, ya que hace uso explícito de la derivada de primer orden de la función objetivo objetivo.
Los métodos de primer orden se basan en la información del gradiente para ayudar a dirigir la búsqueda de un mínimo …
– Página 69, Algoritmos de optimización, 2019.
La derivada de primer orden, o simplemente la «derivada», es la tasa de cambio o pendiente de la función objetivo en un punto específico, p. Ej. para una entrada específica.
Si la función de destino toma múltiples variables de entrada, se denomina función multivariante y las variables de entrada se pueden considerar como un vector. A su vez, la derivada de una función objetivo multivariante también se puede tomar como un vector y se denomina generalmente «gradiente».
- Degradado: Derivada de primer orden para una función objetivo multivariante.
La derivada o el gradiente apunta en la dirección del ascenso más pronunciado de la función de destino para una entrada específica.
El descenso de gradiente se refiere a un algoritmo de optimización de minimización que sigue el negativo del gradiente cuesta abajo de la función objetivo para localizar el mínimo de la función.
El algoritmo de descenso de gradiente requiere una función objetivo que se está optimizando y la función derivada para la función objetivo. La función objetivo f () devuelve una puntuación para un conjunto dado de entradas, y la función derivada f ‘() da la derivada de la función objetivo para un conjunto dado de entradas.
El algoritmo de descenso de gradiente requiere un punto de partida (x) en el problema, como un punto seleccionado al azar en el espacio de entrada.
Luego se calcula la derivada y se da un paso en el espacio de entrada que se espera que resulte en un movimiento cuesta abajo en la función objetivo, asumiendo que estamos minimizando la función objetivo.
Un movimiento cuesta abajo se realiza calculando primero qué tan lejos moverse en el espacio de entrada, calculado como el tamaño de los pasos (llamado alfa o tasa de aprendizaje) multiplicado por el gradiente. Esto luego se resta del punto actual, asegurando que nos movemos contra el gradiente o hacia abajo de la función de destino.
- x (t + 1) = x
Cuanto más pronunciada sea la función objetivo en un punto dado, mayor será la magnitud del gradiente y, a su vez, mayor será el paso dado en el espacio de búsqueda. El tamaño del paso realizado se escala mediante un hiperparámetro de tamaño de paso.
- Numero de pie (alfa): Hiperparámetro que controla qué tan lejos moverse en el espacio de búsqueda contra el gradiente en cada iteración del algoritmo.
Si el tamaño del paso es demasiado pequeño, el movimiento en el espacio de búsqueda será pequeño y la búsqueda llevará mucho tiempo. Si el tamaño del paso es demasiado grande, la búsqueda puede rebotar en el espacio de búsqueda y omitir los óptimos.
Ahora que estamos familiarizados con el algoritmo de optimización del descenso de gradientes, echemos un vistazo al impulso de Nesterov.
Momento de Nesterov
Nesterov Momentum es una extensión del algoritmo de optimización del descenso de gradientes.
El enfoque fue descrito por (y nombrado por) Yurii Nesterov en su artículo de 1983 titulado «Un método para resolver el problema de programación convexa con tasa de convergencia O (1 / k ^ 2)».
Ilya Sutskever y col. son responsables de popularizar la aplicación de Nesterov Momentum en el entrenamiento de redes neuronales con descenso de gradiente estocástico descrito en su artículo de 2013 «Sobre la importancia de la inicialización y el impulso en el aprendizaje profundo». Se refirieron al enfoque como «Gradiente acelerado de Nesterov, ”O NAG para abreviar.
El impulso de Nesterov es como el impulso más tradicional, excepto que la actualización se realiza utilizando la derivada parcial de la actualización proyectada en lugar del valor de la variable actual derivada.
Si bien NAG no se suele considerar como un tipo de impulso, de hecho resulta estar estrechamente relacionado con el impulso clásico, difiriendo solo en la actualización precisa del vector de velocidad …
– Sobre la importancia de la inicialización y el impulso en el aprendizaje profundo, 2013.
El impulso tradicional implica mantener una variable adicional que representa la última actualización realizada a la variable, un promedio móvil de gradientes pasados que decae exponencialmente.
El algoritmo de impulso acumula un promedio móvil de gradientes pasados que decae exponencialmente y continúa moviéndose en su dirección.
– Página 296, Deep Learning, 2016.
Esta última actualización o último cambio de la variable se agrega a la variable escalada por un «impulso«Hiperparámetro que controla la cantidad del último cambio que se debe agregar, p. Ej. 0,9 para el 90%.
Es más fácil pensar en esta actualización en términos de dos pasos, por ejemplo, calcular el cambio en la variable usando la derivada parcial y luego calcular el nuevo valor para la variable.
- cambio (t + 1) = (impulso * cambio
- x (t + 1) = x
Podemos pensar en el impulso en términos de una bola rodando cuesta abajo que se acelerará y seguirá yendo en la misma dirección incluso en presencia de pequeñas colinas.
El impulso se puede interpretar como una bola que rueda por una pendiente casi horizontal. La bola adquiere impulso de forma natural a medida que la gravedad hace que se acelere, al igual que el gradiente hace que se acumule impulso en este método de descenso.
– Página 75, Algoritmos de optimización, 2019.
Un problema con el impulso es que la aceleración a veces puede hacer que la búsqueda sobrepase los mínimos en el fondo de una cuenca o valle.
Nesterov Momentum se puede considerar como una modificación del momentum para superar este problema de sobrepasar los mínimos.
Implica calcular primero la posición proyectada de la variable usando el cambio de la última iteración y usando la derivada de la posición proyectada en el cálculo de la nueva posición para la variable.
El cálculo de la pendiente de la posición proyectada actúa como factor de corrección de la aceleración acumulada.
Con el impulso de Nesterov, el gradiente se evalúa después de aplicar la velocidad actual. Por lo tanto, se puede interpretar el impulso de Nesterov como un intento de agregar un factor de corrección al método estándar de impulso.
– Página 300, Deep Learning, 2016.
Nesterov Momentum es fácil de pensar en esto en términos de los cuatro pasos:
- 1. Proyecte la posición de la solución.
- 2. Calcule el gradiente de la proyección.
- 3. Calcule el cambio en la variable usando la derivada parcial.
- 4. Actualice la variable.
Repasemos estos pasos con más detalle.
Primero, la posición proyectada de toda la solución se calcula utilizando el cambio calculado en la última iteración del algoritmo.
- proyección (t + 1) = x
Luego podemos calcular el gradiente para esta nueva posición.
- gradiente (t + 1) = f ‘(proyección (t + 1))
Ahora podemos calcular la nueva posición de cada variable usando el gradiente de la proyección, primero calculando el cambio en cada variable.
- cambio (t + 1) = (impulso * cambio
Y finalmente, calcular el nuevo valor para cada variable utilizando el cambio calculado.
- x (t + 1) = x
En el campo de la optimización convexa de manera más general, se sabe que Nesterov Momentum mejora la tasa de convergencia del algoritmo de optimización (por ejemplo, reduce el número de iteraciones necesarias para encontrar la solución).
Al igual que el impulso, NAG es un método de optimización de primer orden con una mejor tasa de convergencia garantizada que el descenso de gradientes en determinadas situaciones.
– Sobre la importancia de la inicialización y el impulso en el aprendizaje profundo, 2013.
Aunque la técnica es eficaz para entrenar redes neuronales, es posible que no tenga el mismo efecto general de acelerar la convergencia.
Desafortunadamente, en el caso del gradiente estocástico, el impulso de Nesterov no mejora la tasa de convergencia.
– Página 300, Deep Learning, 2016.
Ahora que estamos familiarizados con el algoritmo Nesterov Momentum, exploremos cómo podríamos implementarlo y evaluar su desempeño.
Descenso de gradiente con impulso de Nesterov
En esta sección, exploraremos cómo implementar el algoritmo de optimización del descenso de gradientes con Nesterov Momentum.
Problema de prueba bidimensional
Primero, definamos una función de optimización.
Usaremos una función bidimensional simple que eleva al cuadrado la entrada de cada dimensión y define el rango de entradas válidas de -1.0 a 1.0.
La función objetivo () a continuación implementa esta función.
|
# función objetiva def objetivo(X, y): regreso X**2.0 + y **2.0 |
Podemos crear una gráfica tridimensional del conjunto de datos para tener una idea de la curvatura de la superficie de respuesta.
El ejemplo completo de trazado de la función objetivo se enumera a continuación.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23 24 |
# Gráfico 3d de la función de prueba desde numpy importar arange desde numpy importar rejilla desde matplotlib importar pyplot # función objetiva def objetivo(X, y): regreso X**2.0 + y **2.0 # definir rango para entrada r_min, r_max = –1.0, 1.0 # rango de entrada de muestra uniformemente en incrementos de 0.1 xaxis = arange(r_min, r_max, 0,1) yaxis = arange(r_min, r_max, 0,1) # crea una malla a partir del eje X, y = rejilla(xaxis, yaxis) # calcular objetivos resultados = objetivo(X, y) # crea un gráfico de superficie con el esquema de color jet figura = pyplot.figura() eje = figura.gca(proyección=‘3d’) eje.plot_surface(X, y, resultados, cmap=‘chorro’) # mostrar la trama pyplot.show() |
La ejecución del ejemplo crea un gráfico de superficie tridimensional de la función objetivo.
Podemos ver la forma familiar de cuenco con los mínimos globales en f (0, 0) = 0.
Gráfico tridimensional de la función objetivo de prueba
También podemos crear una gráfica bidimensional de la función. Esto será útil más adelante cuando queramos trazar el progreso de la búsqueda.
El siguiente ejemplo crea un gráfico de contorno de la función objetivo.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23 |
# gráfica de contorno de la función de prueba desde numpy importar asarray desde numpy importar arange desde numpy importar rejilla desde matplotlib importar pyplot # función objetiva def objetivo(X, y): regreso X**2.0 + y **2.0 # definir rango para entrada límites = asarray([[[[–1.0, 1.0], [[–1.0, 1.0]]) # rango de entrada de muestra uniformemente en incrementos de 0.1 xaxis = arange(límites[[0,0], límites[[0,1], 0,1) yaxis = arange(límites[[1,0], límites[[1,1], 0,1) # crea una malla a partir del eje X, y = rejilla(xaxis, yaxis) # calcular objetivos resultados = objetivo(X, y) # crear un gráfico de contorno relleno con 50 niveles y esquema de color jet pyplot.contourf(X, y, resultados, niveles=50, cmap=‘chorro’) # mostrar la trama pyplot.show() |
La ejecución del ejemplo crea un gráfico de contorno bidimensional de la función objetivo.
Podemos ver la forma del cuenco comprimida a los contornos mostrados con un degradado de color. Usaremos este gráfico para trazar los puntos específicos explorados durante el progreso de la búsqueda.
Gráfico de contorno bidimensional de la función objetivo de prueba
Ahora que tenemos una función de objetivo de prueba, veamos cómo podríamos implementar el algoritmo de optimización Nesterov Momentum.
Optimización del descenso de gradientes con Nesterov Momentum
Podemos aplicar el descenso de gradiente con Nesterov Momentum al problema de prueba.
Primero, necesitamos una función que calcule la derivada de esta función.
La derivada de x ^ 2 es x * 2 en cada dimensión y la derivado() La función implementa esto a continuación.
|
# derivada de la función objetivo def derivado(X, y): regreso asarray([[X * 2.0, y * 2.0]) |
A continuación, podemos implementar la optimización del descenso de gradientes.
Primero, podemos seleccionar un punto aleatorio en los límites del problema como punto de partida para la búsqueda.
Esto supone que tenemos una matriz que define los límites de la búsqueda con una fila para cada dimensión y la primera columna define el mínimo y la segunda columna define el máximo de la dimensión.
|
... # generar un punto inicial solución = límites[[:, 0] + rand(len(límites)) * (límites[[:, 1] – límites[[:, 0]) |
A continuación, necesitamos calcular el punto proyectado desde la posición actual y calcular su derivada.
|
... # calcular la solución proyectada proyectado = [[solución[[I] + impulso * cambio[[I] por I en abarcar(solución.forma[[0])] # calcular el gradiente para la proyección degradado = derivado(proyectado[[0], proyectado[[1]) |
Luego podemos crear la nueva solución, una variable a la vez.
Primero, el cambio en la variable se calcula usando la derivada parcial y la tasa de aprendizaje con el impulso del último cambio en la variable. Este cambio se almacena para la próxima iteración del algoritmo. Luego, el cambio se usa para calcular el nuevo valor de la variable.
|
... # construye una solución una variable a la vez nueva_solución = lista() por I en abarcar(solución.forma[[0]): # calcula el cambio cambio[[I] = (impulso * cambio[[I]) – Numero de pie * degradado[[I] # calcular la nueva posición en esta variable valor = solución[[I] + cambio[[I] # almacenar esta variable nueva_solución.adjuntar(valor) |
Esto se repite para cada variable de la función objetivo, luego se repite para cada iteración del algoritmo.
Luego, esta nueva solución puede evaluarse utilizando el objetivo() función y el rendimiento de la búsqueda se pueden informar.
|
... # evaluar el punto candidato solución = asarray(nueva_solución) solution_eval = objetivo(solución[[0], solución[[1]) # informe de progreso imprimir(‘>% d f (% s) =% .5f’ % (eso, solución, solution_eval)) |
Y eso es.
Podemos unir todo esto en una función llamada nesterov () que toma los nombres de la función objetivo y la función derivada, una matriz con los límites del dominio y los valores del hiperparámetro para el número total de iteraciones del algoritmo, la tasa de aprendizaje y el impulso, y devuelve la solución final y su evaluación.
Esta función completa se enumera a continuación.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23 24 25 26 27 |
# algoritmo de descenso de gradiente con impulso nesterov def nesterov(objetivo, derivado, límites, nitro, Numero de pie, impulso): # generar un punto inicial solución = límites[[:, 0] + rand(len(límites)) * (límites[[:, 1] – límites[[:, 0]) # lista de cambios realizados en cada variable cambio = [[0.0 por _ en abarcar(límites.forma[[0])] # ejecutar el descenso de gradiente por eso en abarcar(nitro): # calcular la solución proyectada proyectado = [[solución[[I] + impulso * cambio[[I] por I en abarcar(solución.forma[[0])] # calcular el gradiente para la proyección degradado = derivado(proyectado[[0], proyectado[[1]) # construye una solución una variable a la vez nueva_solución = lista() por I en abarcar(solución.forma[[0]): # calcula el cambio cambio[[I] = (impulso * cambio[[I]) – Numero de pie * degradado[[I] # calcular la nueva posición en esta variable valor = solución[[I] + cambio[[I] # almacenar esta variable nueva_solución.adjuntar(valor) # evaluar el punto candidato solución = asarray(nueva_solución) solution_eval = objetivo(solución[[0], solución[[1]) # informe de progreso imprimir(‘>% d f (% s) =% .5f’ % (eso, solución, solution_eval)) regreso [[solución, solution_eval] |
Nota, hemos utilizado intencionalmente listas y estilo de codificación imperativa en lugar de operaciones vectorizadas para facilitar la lectura. No dude en adaptar la implementación a una implementación de vectorización con matrices NumPy para un mejor rendimiento.
Luego podemos definir nuestros hiperparámetros y llamar al nesterov () función para optimizar nuestra función objetivo de prueba.
En este caso, usaremos 30 iteraciones del algoritmo con una tasa de aprendizaje de 0.1 y un impulso de 0.3. Estos valores de hiperparámetros se encontraron después de un pequeño ensayo y error.
|
... # siembra el generador de números pseudoaleatorios semilla(1) # definir rango para entrada límites = asarray([[[[–1.0, 1.0], [[–1.0, 1.0]]) # definir las iteraciones totales nitro = 30 # definir el tamaño del paso Numero de pie = 0,1 # definir impulso impulso = 0,3 # realizar la búsqueda de descenso de gradiente con impulso nesterov mejor, puntaje = nesterov(objetivo, derivado, límites, nitro, Numero de pie, impulso) imprimir(‘¡Hecho!’) imprimir(‘f (% s) =% f’ % (mejor, puntaje)) |
Uniendo todo esto, el ejemplo completo de optimización del descenso de gradientes con Nesterov Momentum se enumera a continuación.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# optimización del descenso de gradiente con impulso nesterov para una función de prueba bidimensional desde Matemáticas importar sqrt desde numpy importar asarray desde numpy.aleatorio importar rand desde numpy.aleatorio importar semilla # función objetiva def objetivo(X, y): regreso X**2.0 + y **2.0 # derivada de la función objetivo def derivado(X, y): regreso asarray([[X * 2.0, y * 2.0]) # algoritmo de descenso de gradiente con impulso nesterov def nesterov(objetivo, derivado, límites, nitro, Numero de pie, impulso): # generar un punto inicial solución = límites[[:, 0] + rand(len(límites)) * (límites[[:, 1] – límites[[:, 0]) # lista de cambios realizados en cada variable cambio = [[0.0 por _ en abarcar(límites.forma[[0])] # ejecutar el descenso de gradiente por eso en abarcar(nitro): # calcular la solución proyectada proyectado = [[solución[[I] + impulso * cambio[[I] por I en abarcar(solución.forma[[0])] # calcular el gradiente para la proyección degradado = derivado(proyectado[[0], proyectado[[1]) # construye una solución una variable a la vez nueva_solución = lista() por I en abarcar(solución.forma[[0]): # calculate the change cambio[[I] = (momentum * cambio[[I]) – step_size * gradient[[I] # calculate the new position in this variable valor = solución[[I] + cambio[[I] # store this variable new_solution.append(valor) # evaluate candidate point solución = asarray(new_solution) solution_eval = objective(solución[[0], solución[[1]) # report progress print(‘>%d f(%s) = %.5f’ % (eso, solución, solution_eval)) regreso [[solución, solution_eval] # seed the pseudo random number generator semilla(1) # define range for input bounds = asarray([[[[–1.0, 1.0], [[–1.0, 1.0]]) # define the total iterations n_iter = 30 # define the step size step_size = 0.1 # define momentum momentum = 0,3 # perform the gradient descent search with nesterov momentum mejor, puntaje = nesterov(objective, derivative, bounds, n_iter, step_size, momentum) print(‘Done!’) print(‘f(%s) = %f’ % (mejor, puntaje)) |
Running the example applies the optimization algorithm with Nesterov Momentum to our test problem and reports performance of the search for each iteration of the algorithm.
Nota: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.
In this case, we can see that a near optimal solution was found after perhaps 15 iterations of the search, with input values near 0.0 and 0.0, evaluating to 0.0.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
>0 f([-0.13276479 0.35251919]) = 0.14190 >1 f([-0.09824595 0.2608642 ]) = 0.07770 >2 f([-0.07031223 0.18669416]) = 0.03980 >3 f([-0.0495457 0.13155452]) = 0.01976 >4 f([-0.03465259 0.0920101 ]) = 0.00967 >5 f([-0.02414772 0.06411742]) = 0.00469 >6 f([-0.01679701 0.04459969]) = 0.00227 >7 f([-0.01167344 0.0309955 ]) = 0.00110 >8 f([-0.00810909 0.02153139]) = 0.00053 >9 f([-0.00563183 0.01495373]) = 0.00026 >10 f([-0.00391092 0.01038434]) = 0.00012 >11 f([-0.00271572 0.00721082]) = 0.00006 >12 f([-0.00188573 0.00500701]) = 0.00003 >13 f([-0.00130938 0.0034767 ]) = 0.00001 >14 f([-0.00090918 0.00241408]) = 0.00001 >15 f([-0.0006313 0.00167624]) = 0.00000 >16 f([-0.00043835 0.00116391]) = 0.00000 >17 f([-0.00030437 0.00080817]) = 0.00000 >18 f([-0.00021134 0.00056116]) = 0.00000 >19 f([-0.00014675 0.00038964]) = 0.00000 >20 f([-0.00010189 0.00027055]) = 0.00000 >21 f([-7.07505806e-05 1.87858067e-04]) = 0.00000 >22 f([-4.91260884e-05 1.30440372e-04]) = 0.00000 >23 f([-3.41109926e-05 9.05720503e-05]) = 0.00000 >24 f([-2.36851711e-05 6.28892431e-05]) = 0.00000 >25 f([-1.64459397e-05 4.36675208e-05]) = 0.00000 >26 f([-1.14193362e-05 3.03208033e-05]) = 0.00000 >27 f([-7.92908415e-06 2.10534304e-05]) = 0.00000 >28 f([-5.50560682e-06 1.46185748e-05]) = 0.00000 >29 f([-3.82285090e-06 1.01504945e-05]) = 0.00000 ¡Hecho! f([-3.82285090e-06 1.01504945e-05]) = 0.000000 |
Visualization of Nesterov Momentum
We can plot the progress of the Nesterov Momentum search on a contour plot of the domain.
This can provide an intuition for the progress of the search over the iterations of the algorithm.
We must update the nesterov() function to maintain a list of all solutions found during the search, then return this list at the end of the search.
The updated version of the function with these changes is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
# gradient descent algorithm with nesterov momentum def nesterov(objective, derivative, bounds, n_iter, step_size, momentum): # track all solutions solutions = lista() # generate an initial point solución = bounds[[:, 0] + rand(len(bounds)) * (bounds[[:, 1] – bounds[[:, 0]) # list of changes made to each variable cambio = [[0.0 por _ en abarcar(bounds.forma[[0])] # run the gradient descent por eso en abarcar(n_iter): # calculate the projected solution projected = [[solución[[I] + momentum * cambio[[I] por I en abarcar(solución.forma[[0])] # calculate the gradient for the projection gradient = derivative(projected[[0], projected[[1]) # build a solution one variable at a time new_solution = lista() por I en abarcar(solución.forma[[0]): # calculate the change cambio[[I] = (momentum * cambio[[I]) – step_size * gradient[[I] # calculate the new position in this variable valor = solución[[I] + cambio[[I] # store this variable new_solution.append(valor) # store the new solution solución = asarray(new_solution) solutions.append(solución) # evaluate candidate point solution_eval = objective(solución[[0], solución[[1]) # report progress print(‘>%d f(%s) = %.5f’ % (eso, solución, solution_eval)) regreso solutions |
We can then execute the search as before, and this time retrieve the list of solutions instead of the best final solution.
|
... # seed the pseudo random number generator semilla(1) # define range for input bounds = asarray([[[[–1.0, 1.0], [[–1.0, 1.0]]) # define the total iterations n_iter = 50 # define the step size step_size = 0.01 # define momentum momentum = 0.8 # perform the gradient descent search with nesterov momentum solutions = nesterov(objective, derivative, bounds, n_iter, step_size, momentum) |
We can then create a contour plot of the objective function, as before.
|
... # sample input range uniformly at 0.1 increments xaxis = arange(bounds[[0,0], bounds[[0,1], 0.1) yaxis = arange(bounds[[1,0], bounds[[1,1], 0.1) # create a mesh from the axis X, y = meshgrid(xaxis, yaxis) # compute targets resultados = objective(X, y) # create a filled contour plot with 50 levels and jet color scheme pyplot.contourf(X, y, resultados, niveles=50, cmap=‘jet’) |
Finally, we can plot each solution found during the search as a white dot connected by a line.
|
... # plot the sample as black circles solutions = asarray(solutions) pyplot.trama(solutions[[:, 0], solutions[[:, 1], ‘.-‘, color=‘w’) |
Tying this all together, the complete example of performing the Nesterov Momentum optimization on the test problem and plotting the results on a contour plot is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 sesenta y cinco 66 67 68 69 70 71 72 73 74 75 76 |
# example of plotting the nesterov momentum search on a contour plot of the test function desde Matemáticas import sqrt desde numpy import asarray desde numpy import arange desde numpy.aleatorio import rand desde numpy.aleatorio import semilla desde numpy import meshgrid desde matplotlib import pyplot desde mpl_toolkits.mplot3d import Axes3D # objective function def objective(X, y): regreso x**2.0 + y**2.0 # derivative of objective function def derivative(X, y): regreso asarray([[x * 2.0, y * 2.0]) # gradient descent algorithm with nesterov momentum def nesterov(objective, derivative, bounds, n_iter, step_size, momentum): # track all solutions solutions = lista() # generate an initial point solución = bounds[[:, 0] + rand(len(bounds)) * (bounds[[:, 1] – bounds[[:, 0]) # list of changes made to each variable cambio = [[0.0 por _ en abarcar(bounds.forma[[0])] # run the gradient descent por eso en abarcar(n_iter): # calculate the projected solution projected = [[solución[[I] + momentum * cambio[[I] por I en abarcar(solución.forma[[0])] # calculate the gradient for the projection gradient = derivative(projected[[0], projected[[1]) # build a solution one variable at a time new_solution = lista() por I en abarcar(solución.forma[[0]): # calculate the change cambio[[I] = (momentum * cambio[[I]) – step_size * gradient[[I] # calculate the new position in this variable valor = solución[[I] + cambio[[I] # store this variable new_solution.append(valor) # store the new solution solución = asarray(new_solution) solutions.append(solución) # evaluate candidate point solution_eval = objective(solución[[0], solución[[1]) # report progress print(‘>%d f(%s) = %.5f’ % (eso, solución, solution_eval)) regreso solutions # seed the pseudo random number generator semilla(1) # define range for input bounds = asarray([[[[–1.0, 1.0], [[–1.0, 1.0]]) # define the total iterations n_iter = 50 # define the step size step_size = 0.01 # define momentum momentum = 0.8 # perform the gradient descent search with nesterov momentum solutions = nesterov(objective, derivative, bounds, n_iter, step_size, momentum) # sample input range uniformly at 0.1 increments xaxis = arange(bounds[[0,0], bounds[[0,1], 0.1) yaxis = arange(bounds[[1,0], bounds[[1,1], 0.1) # create a mesh from the axis X, y = meshgrid(xaxis, yaxis) # compute targets resultados = objective(X, y) # create a filled contour plot with 50 levels and jet color scheme pyplot.contourf(X, y, resultados, niveles=50, cmap=‘jet’) # plot the sample as black circles solutions = asarray(solutions) pyplot.trama(solutions[[:, 0], solutions[[:, 1], ‘.-‘, color=‘w’) # show the plot pyplot.show() |
Running the example performs the search as before, except in this case, the contour plot of the objective function is created.
In this case, we can see that a white dot is shown for each solution found during the search, starting above the optima and progressively getting closer to the optima at the center of the plot.
Contour Plot of the Test Objective Function With Nesterov Momentum Search Results Shown
Further Reading
This section provides more resources on the topic if you are looking to go deeper.
Papers
Books
APIs
Articles
Resumen
In this tutorial, you discovered how to develop the gradient descent optimization with Nesterov Momentum from scratch.
Specifically, you learned:
- Gradient descent is an optimization algorithm that uses the gradient of the objective function to navigate the search space.
- The convergence of gradient descent optimization algorithm can be accelerated by extending the algorithm and adding Nesterov Momentum.
- How to implement the Nesterov Momentum optimization algorithm from scratch and apply it to an objective function and evaluate the results.
Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.