Optimización de descenso de gradiente de Code Adam desde cero

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.


Recomendado: ¿Qué es el Big data?.


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

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:

  1. Descenso de gradiente
  2. Algoritmo de optimización de Adam
  3. Descenso degradado con Adam
    1. Problema de prueba bidimensional
    2. Optimización del descenso de gradientes con Adam
    3. 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

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.

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

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.

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

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.

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.

A continuación, necesitamos inicializar el primer y segundo momento a cero.

Luego ejecutamos un número fijo de iteraciones del algoritmo definido por el “nitro”Hiperparámetro.

El primer paso es calcular el gradiente para la solución actual usando el derivado() función.

El primer paso es calcular la derivada del conjunto de parámetros actual.

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.

Primero, necesitamos calcular el momento.

Luego, el segundo momento.

Luego, la corrección de sesgo para el primer y segundo momento.

Luego, finalmente, el valor de la variable actualizada.

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.

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.

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.

Tying all of this together, the complete example of gradient descent optimization with Adam is listed below.

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.

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.

We can then execute the search as before, and this time retrieve the list of solutions instead of the best final solution.

We can then create a contour plot of the objective function, as before.

Finally, we can plot each solution found during the search as a white dot connected by a line.

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.

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

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.