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 gradiente es que se usa un tamaño de paso único (tasa de aprendizaje) para todas las variables de entrada. Las extensiones al descenso de gradiente como AdaGrad y RMSProp actualizan el algoritmo para usar un tamaño de paso separado para cada variable de entrada, pero pueden dar como resultado un tamaño de paso que disminuye rápidamente a valores muy pequeños.
los Estimación de movimiento adaptativo algoritmo, o Adán para abreviar, es una extensión del descenso de gradiente y un sucesor natural de técnicas como AdaGrad y RMSProp que adapta automáticamente una tasa de aprendizaje para cada variable de entrada para la función objetivo y suaviza aún más el proceso de búsqueda mediante el uso de una media móvil exponencialmente decreciente del gradiente para realizar actualizaciones a las variables.
En este tutorial, descubrirá cómo desarrollar el descenso de gradientes con el algoritmo de optimización de Adam 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.
- El descenso de gradiente se puede actualizar para usar un tamaño de paso adaptativo automáticamente para cada variable de entrada usando un promedio decreciente de derivadas parciales, llamado Adam.
- Cómo implementar el algoritmo de optimización de Adam desde cero y aplicarlo a una función objetivo y evaluar los resultados.
Empecemos.
Optimización del descenso de gradientes con Adam From Scratch
Foto de Don Graham, algunos derechos reservados.
Descripción general del tutorial
Este tutorial se divide en tres partes; son:
- Descenso de gradiente
- Algoritmo de optimización de Adam
- Descenso degradado con Adam
- Problema de prueba bidimensional
- Optimización del descenso de gradientes con Adam
- Visualización de Adán
Descenso de gradiente
El descenso de gradientes es un algoritmo de optimización.
Técnicamente se le 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 «derivado, ”Es la tasa de cambio o pendiente de la función objetivo en un punto específico, p. para una entrada específica.
Si la función de destino toma múltiples variables de entrada, se la 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 puede tomarse 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 objetivo 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 cuánto moverse en el espacio de entrada, calculado como el tamaño del paso (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
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 algoritmo de Adam.
Algoritmo de optimización de Adam
El algoritmo de estimación de movimiento adaptativo, o Adam para abreviar, es una extensión del algoritmo de optimización del descenso de gradientes.
El algoritmo fue descrito en el artículo de 2014 de Diederik Kingma y Jimmy Lei Ba titulado «Adam: un método para la optimización estocástica».
Adam está diseñado para acelerar el proceso de optimización, p. Ej. disminuir el número de evaluaciones de funciones requeridas para alcanzar los óptimos, o para mejorar la capacidad del algoritmo de optimización, p. resultar en un mejor resultado final.
Esto se logra calculando un tamaño de paso para cada parámetro de entrada que se optimiza. Es importante destacar que cada tamaño de paso se adapta automáticamente al rendimiento del proceso de búsqueda en función de los gradientes (derivadas parciales) encontrados para cada variable.
Proponemos Adam, un método para la optimización estocástica eficiente que solo requiere gradientes de primer orden con poca memoria. El método calcula las tasas de aprendizaje adaptativo individuales para diferentes parámetros a partir de estimaciones del primer y segundo momento de los gradientes; el nombre Adam se deriva de la estimación del momento adaptativo
– Adam: un método de optimización estocástica
Esto implica mantener un primer y segundo momento del gradiente, p. Ej. un gradiente medio que decae exponencialmente (primer momento) y varianza (segundo momento) para cada variable de entrada.
Los promedios móviles en sí mismos son estimaciones del primer momento (la media) y el segundo momento bruto (la varianza no centrada) del gradiente.
– Adam: un método de optimización estocástica
Repasemos cada elemento del algoritmo.
Primero, debemos mantener un vector de momento y una norma infinita ponderada exponencialmente para cada parámetro que se optimiza como parte de la búsqueda, denominados myv (en realidad, la letra griega nu) respectivamente. Se inicializan a 0.0 al comienzo de la búsqueda.
El algoritmo se ejecuta iterativamente en el tiempo t comenzando en t = 1, y cada iteración implica calcular un nuevo conjunto de valores de parámetros X, p.ej. ir desde x (t-1) a x
Quizás sea fácil entender el algoritmo si nos enfocamos en actualizar un parámetro, que se generaliza para actualizar todos los parámetros a través de operaciones vectoriales.
Primero, se calcula el gradiente (derivadas parciales) para el intervalo de tiempo actual.
A continuación, el primer momento se actualiza utilizando el degradado y un hiperparámetro. beta1.
- m
Luego, el segundo momento se actualiza usando el gradiente cuadrado y un hiperparámetro beta2.
- v
El primer y segundo momento están sesgados porque se inicializan con valores cero.
… estos promedios móviles se inicializan como (vectores de) 0, lo que conduce a estimaciones de momento que están sesgadas hacia cero, especialmente durante los pasos de tiempo iniciales, y especialmente cuando las tasas de caída son pequeñas (es decir, las betas están cerca de 1). La buena noticia es que este sesgo de inicialización se puede contrarrestar fácilmente, lo que da como resultado estimaciones con corrección de sesgo …
– Adam: un método de optimización estocástica
A continuación, se corrige el sesgo del primer y segundo momento, protagonizado por el primer momento:
- mhat
Y luego el segundo momento:
- vhat
Nota, beta1
- beta1
- beta2
Finalmente, podemos calcular el valor del parámetro para esta iteración.
- x
Dónde alfa es el hiperparámetro del tamaño del paso, eps es un valor pequeñoépsilon) como 1e-8 que asegura que no encontremos una división por error cero, y sqrt () es la función raíz cuadrada.
Tenga en cuenta que se puede utilizar una reordenación más eficiente de la regla de actualización que se enumera en el documento:
- alpha
- x
Para revisar, hay tres hiperparámetros para el algoritmo, que son:
- alfa: Tamaño del paso inicial (tasa de aprendizaje), un valor típico es 0,001.
- beta1: Factor de caída para el primer impulso, un valor típico es 0,9.
- beta2: Factor de decaimiento para la norma infinita, un valor típico es 0,999.
Y eso es.
Para obtener una derivación completa del algoritmo de Adam en el contexto del algoritmo de Adam, recomiendo leer el artículo.
A continuación, veamos cómo podríamos implementar el algoritmo desde cero en Python.
Descenso degradado con Adam
En esta sección, exploraremos cómo implementar el algoritmo de optimización del descenso de gradientes con Adam.
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 trazar 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 desde el 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 desde el 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 una gráfica 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 objetivo de prueba, veamos cómo podemos implementar el algoritmo de optimización de Adam.
Optimización del descenso de gradientes con Adam
Podemos aplicar el descenso de gradiente con Adam 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. La función derivada () 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 X = límites[[:, 0] + rand(len(límites)) * (límites[[:, 1] – límites[[:, 0]) Puntuación = objetivo(X[[0], X[[1]) |
A continuación, necesitamos inicializar el primer y segundo momento a cero.
|
... # inicializar el primer y segundo momento metro = [[0.0 para _ en rango(límites.forma[[0])] v = [[0.0 para _ en rango(límites.forma[[0])] |
Luego ejecutamos un número fijo de iteraciones del algoritmo definido por el «nitro”Hiperparámetro.
|
... # ejecutar iteraciones de descenso de gradiente para t en rango(nitro): ... |
El primer paso es calcular el gradiente para la solución actual usando el derivado() función.
|
... # calcular gradiente degradado = derivado(solución[[0], solución[[1]) |
El primer paso es calcular la derivada del conjunto de parámetros actual.
|
... # calcular gradiente g |
A continuación, debemos realizar los cálculos de actualización de Adam. Realizaremos estos cálculos una variable a la vez utilizando un estilo de programación imperativo para facilitar la lectura.
En la práctica, recomiendo usar operaciones vectoriales NumPy para mayor eficiencia.
|
... # construya una solución una variable a la vez para yo en rango(X.forma[[0]): ... |
Primero, necesitamos calcular el momento.
|
... # m |
Luego, el segundo momento.
|
... # v |
Luego, la corrección de sesgo para el primer y segundo momento.
|
... # mhat |
Luego, finalmente, el valor de la variable actualizada.
|
... # x |
Luego, esto se repite para cada parámetro que se está optimizando.
Al final de la iteración, podemos evaluar los nuevos valores de los parámetros e informar el rendimiento de la búsqueda.
|
... # evaluar el punto candidato Puntuación = objetivo(X[[0], X[[1]) # informe de progreso impresión(‘>% d f (% s) =% .5f’ % (t, X, Puntuación)) |
Podemos unir todo esto en una función llamada Adán() que toma los nombres de las funciones objetivo y derivada, así como los hiperparámetros del algoritmo, y devuelve la mejor solución encontrada al final de la búsqueda 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 28 29 |
# algoritmo de descenso de gradiente con adam def Adán(objetivo, derivado, límites, nitro, alfa, beta1, beta2, eps=1e–8): # generar un punto inicial X = límites[[:, 0] + rand(len(límites)) * (límites[[:, 1] – límites[[:, 0]) Puntuación = objetivo(X[[0], X[[1]) # inicializar el primer y segundo momento metro = [[0.0 para _ en rango(límites.forma[[0])] v = [[0.0 para _ en rango(límites.forma[[0])] # ejecutar las actualizaciones de descenso de gradiente para t en rango(nitro): # calcular gradiente g |
Nota: hemos utilizado intencionalmente listas y estilo de codificación imperativa en lugar de operaciones vectorizadas para facilitar la lectura. Siéntase libre de adaptar la implementación a una implementación vectorizada con matrices NumPy para un mejor rendimiento.
Luego podemos definir nuestros hiperparámetros y llamar al Adán() función para optimizar nuestra función objetivo de prueba.
En este caso, usaremos 60 iteraciones del algoritmo con un tamaño de pasos iniciales de 0.02 y valores beta1 y beta2 de 0.8 y 0.999 respectivamente. Estos valores de hiperparámetros se encontraron después de un pequeño ensayo y error.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 dieciséis 17 |
... # 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 = 60 # tamaño de pasos alfa = 0,02 # factor de gradiente promedio beta1 = 0.8 # factor for average squared gradient beta2 = 0.999 # perform the gradient descent search with adam best, score = adam(objective, derivative, bounds, n_iter, alpha, beta1, beta2) print(‘Done!’) print(‘f(%s) = %f’ % (best, score)) |
Tying all of this together, the complete example of gradient descent optimization with Adam is listed below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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 |
# gradient descent optimization with adam for a two-dimensional test function from math import sqrt from numpy import asarray from numpy.random import rand from numpy.random import seed # objective function def objective(x, y): return x**2.0 + y**2.0 # derivative of objective function def derivative(x, y): return asarray([[x * 2.0, y * 2.0]) # gradient descent algorithm with adam def adam(objective, derivative, bounds, n_iter, alpha, beta1, beta2, eps=1e–8): # generate an initial point x = bounds[[:, 0] + rand(len(bounds)) * (bounds[[:, 1] – bounds[[:, 0]) score = objective(x[[0], x[[1]) # initialize first and second moments m = [[0.0 para _ en range(bounds.shape[[0])] v = [[0.0 para _ en range(bounds.shape[[0])] # run the gradient descent updates para t en range(n_iter): # calculate gradient g |
Running the example applies the Adam optimization algorithm to our test problem and reports the performance of the search for each iteration of the algorithm.
Note: 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 53 iterations of the search, with input values near 0.0 and 0.0, evaluating to 0.0.
|
… >50 f([-0.00056912 -0.00321961]) = 0.00001 >51 f([-0.00052452 -0.00286514]) = 0.00001 >52 f([-0.00043908 -0.00251304]) = 0.00001 >53 f([-0.0003283 -0.00217044]) = 0.00000 >54 f([-0.00020731 -0.00184302]) = 0.00000 >55 f([-8.95352320e-05 -1.53514076e-03]) = 0.00000 >56 f([ 1.43050285e-05 -1.25002847e-03]) = 0.00000 >57 f([ 9.67123406e-05 -9.89850279e-04]) = 0.00000 >58 f([ 0.00015359 -0.00075587]) = 0.00000 >59 f([ 0.00018407 -0.00054858]) = 0.00000 Done! f([ 0.00018407 -0.00054858]) = 0.000000 |
Visualization of Adam
We can plot the progress of the Adam 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 adam() 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 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
# gradient descent algorithm with adam def adam(objective, derivative, bounds, n_iter, alpha, beta1, beta2, eps=1e–8): solutions = list() # generate an initial point x = bounds[[:, 0] + rand(len(bounds)) * (bounds[[:, 1] – bounds[[:, 0]) score = objective(x[[0], x[[1]) # initialize first and second moments m = [[0.0 para _ en range(bounds.shape[[0])] v = [[0.0 para _ en range(bounds.shape[[0])] # run the gradient descent updates para t en range(n_iter): # calculate gradient g |
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 seed(1) # define range for input bounds = asarray([[[[–1.0, 1.0], [[–1.0, 1.0]]) # define the total iterations n_iter = 60 # steps size alpha = 0.02 # factor for average gradient beta1 = 0.8 # factor for average squared gradient beta2 = 0.999 # perform the gradient descent search with adam solutions = adam(objective, derivative, bounds, n_iter, alpha, beta1, beta2) |
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 results = objective(x, y) # create a filled contour plot with 50 levels and jet color scheme pyplot.contourf(x, y, results, levels=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.plot(solutions[[:, 0], solutions[[:, 1], ‘.-‘, color=‘w’) |
Tying this all together, the complete example of performing the Adam 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 16 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 77 78 79 |
# example of plotting the adam search on a contour plot of the test function from math import sqrt from numpy import asarray from numpy import arange from numpy.random import rand from numpy.random import seed from numpy import meshgrid from matplotlib import pyplot from mpl_toolkits.mplot3d import Axes3D # objective function def objective(x, y): return x**2.0 + y**2.0 # derivative of objective function def derivative(x, y): return asarray([[x * 2.0, y * 2.0]) # gradient descent algorithm with adam def adam(objective, derivative, bounds, n_iter, alpha, beta1, beta2, eps=1e–8): solutions = list() # generate an initial point x = bounds[[:, 0] + rand(len(bounds)) * (bounds[[:, 1] – bounds[[:, 0]) score = objective(x[[0], x[[1]) # initialize first and second moments m = [[0.0 para _ en range(bounds.shape[[0])] v = [[0.0 para _ en range(bounds.shape[[0])] # run the gradient descent updates para t en range(n_iter): # calculate gradient g |
Running the example performs the search as before, except in this case, a 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 Adam Search Results Shown
Further Reading
This section provides more resources on the topic if you are looking to go deeper.
Papers
Books
APIs
Articles
Summary
In this tutorial, you discovered how to develop gradient descent with Adam optimization algorithm from scratch.
Specifically, you learned:
- Gradient descent is an optimization algorithm that uses the gradient of the objective function to navigate the search space.
- Gradient descent can be updated to use an automatically adaptive step size for each input variable using a decaying average of partial derivatives, called Adam.
- How to implement the Adam 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.