Gradiente Descendente

El método del Gradiente Descendente, también conocido como método de Augustin Louis Cauchy (1.847), trata de encontrar un mínimo de una función, sea local o no. El método se basa en el uso del gradiente negativo −∇f, pues en esa dirección obtendremos el descenso máximo en los valores de la función.

Cauchy

Para nuestros intereses será el algoritmo y la forma de optimizar las redes neuronales y/o el aprendizaje que nos proveerá del mínimo error que comete la red en función del conjunto de pesos.

 

 

Esta técnica, en sus primeros algoritmos, obtenía solo mínimos locales debido a que las direcciones de búsqueda consecutivas están a 90 grados, siendo lenta para  funciones o valores iniciales especiales, por lo que son necesarios métodos más robustos para resolver el problema.

 

 

Para explicar el gradiente debemos apoyarnos en las matemáticas y en concreto en el cálculo diferencial. Tomamos la función f(x), el gradiente de la función en un valor particular de x, es la tasa de cambio de f (x) cuando cambiamos x, que puede aproximarse a Δy / Δx para Δx pequeño. Se puede escribir como:

Direcciones de búsqueda
Direcciones de búsqueda

 

 

 

 

que se conoce como la derivada parcial de f (x) con respecto a Δx

 

Cuando queramos modificar el resultado de la función f (x), es evidente que deberemos cambiar el valor de x, como esto depende del gradiente de f (x) en el valor actual de x, nos  encontraremos tres casos. Para nuestros intereses sólo queremos el primero:

 

 

  1. Si ∂f / ∂x < 0 entonces f (x) disminuye a medida que x aumenta.

     función f(x)
    función f(x)

  2. Si ∂f / ∂x = 0 entonces f (x) está en un máximo o mínimo, no deberíamos cambiar x.
  3. Si ∂f / ∂x > 0 entonces f (x) aumenta a medida que aumenta x.

 

 

 

En resumen, podemos disminuir f (x) cambiando x por un valor, donde:

  • η es una constante positiva que especifica cuánto cambiamos x. Es importante considerar que η debe ser un valor adecuado para nuestra función, si tomamos un valor muy pequeño el cálculo del gradiente descendente podría ir muy lento, pero si se toma uno muy grande, podríamos pasarnos del mínimo.
  • derivada ∂f / ∂x nos indica cuál es la dirección en la que vamos.

 

El método del gradiente descendente ha sido, y es, uno de los métodos más utilizados en el entrenamiento de las RNA. Existen dos formas de aplicarlo, por Lotes y por SGD (Stochastic gradient descent):

 

Lotes. Es la más común y se calcula a partir de todo el conjunto de entrenamiento (lote). Un factor importante a tener en cuenta, si el lote tiene millones de datos, el cálculo será bastante costoso ya que tenemos que reevaluar todo el conjunto de datos de capacitación cada vez que damos un paso hacia el mínimo.

El método define una función E(w) que proporciona el error que comete la red en función del conjunto de pesos W. La forma de actuar es la siguiente:

  • Tomamos el conjunto de pesos W(0) para el instante de tiempo t=0, se calcula la dirección de máxima variación del error. Con E(W) en W(0) obtenemos el gradiente ∇E(W).
  • Se actualizan los pesos W(0) siguiendo el sentido contrario al indicado por el gradiente ∇E(W), que es el sentido de máximo decrecimiento y que produce un descenso por la superficie de error hasta alcanzar el mínimo actual  W (t +1) = W (t) −α∇E(W ).  α indica el tamaño del paso en cada ciclo, que puede ser diferente para cada peso. Sí el valor del paso es pequeño el entrenamiento es lento y al contrario, sí el paso es grande se producen oscilaciones en torno al punto mínimo.

Al aplicar de forma reiterada E(w), ha ido descendiendo al mínimo y en la k- enésima iteración es nula (cero), en este punto hemos alcanzado la solución a nuestro problema.

Problemas del gradiente descendente
Problemas del gradiente descendente

 

 

 

No es fácil obtener un buen resultado, ¿por qué?, porque puede que existan otros mínimos y en este caso nos encontramos con el denominado problema del gradiente descendente. También podemos encontrarnos en la cima entre dos valles (punto de silla) y ¿cúal es el más profundo?.

Para resolverlo debemos verificar todas las direcciones posibles en el espacio, en este ejemplo xyz, siendo la dirección en la que se produce la disminución más pronunciada del valor de la función el que verdaderamente nos interesa, el mínimo global. Para ello debemos comenzar de alguna manera o por algún sitio y ¿cuál es?, sencillamente de forma aleatoria que es la aplicada en la forma estocástica.

 

 

 

 

SGD – Gradiente Descendente Estocástico.

Los primeros prototipos de los algoritmos SGD (Stochastic Gradient Descent) son los publicados por Herbert Robbins y Sutton Monro en 1.951 con el título de “A Stochastic Approximation Method”  y el posterior de Jacob Wolfowitz y Jack Kiefer publicado en 1.952 como “Stochastic Estimation of a Regression Function”.

 

Jacob Wolfowitz
Wolfowitz
Jack Kiefer
Kiefer
Herbert Robbins
Robbins

El algoritmo RM (Robbins-Monro) describe cómo encontrar la raíz de una función creciente f: R → R cuando solo se dispone de estimaciones ruidosas del valor de la función en un punto determinado. Tomando esta idea y con aplicación en lo que nos ocupa, si tratamos f como el gradiente de alguna función F, el algoritmo Robbins-Monro es un método de aproximación estocástica que puede verse como un procedimiento de obtención de mínimos locales. La estructura del algoritmo es generar iteraciones de la forma:

 

 

 

Kiefer y Wolfowitz siguiendo la estela del algoritmo RM, desarrollan el primer algoritmo de aproximación estocástica para la optimización, el KW. Su  propuesta fue la búsqueda del gradiente tratando de encontrar el máximo de una función de regresión que incorporaba estimaciones de gradiente de diferencias finitas, de aquí que a su algoritmo también se le conozca por FDSA (Finite Differences Stochastic Approximation). Este algoritmo tiene el inconveniente de perder la eficiencia que tiene con datos escalares cuando trata con parámetros vectoriales, en este escenario se produce una sobrecarga computacional.

 

Robbins - Monro Gráfica
Robbins-Monro Gráfica

SGD tiene problemas para transitar por los valles donde la superficie se curva mucho más en una dimensión que en otra, es un problema muy común cerca de los mínimos locales. Una imagen de esta situación está en el gráfico de arriba en gradiente descendente, para mejorar esta problemática están apareciendo nuevos algoritmos optimizados que veremos más adelante.

 

En 1.972 Vladimir Katkovnik y Y. U. Kulchitsky publican “Convergence of a class of random search algorithm” donde proponen un esquema de búsqueda aleatoria, SF (Smoothed Functional) que solo requiere una evaluación de la función objetivo independientemente de la dimensión de los parámetros.

 

En 1.992 James C. Spall propone SPSA (Simultaneous Perturbation Stochastic Approximation) aproximación estocástica de perturbaciones simultáneas. Es un algoritmo de optimización multivariable que cambia todos los parámetros a la vez en lugar de uno solo, como resultado puede obtener una aproximación del gradiente con muchas menos muestras del sistema. Lo hace con una búsqueda aleatoria en el espacio de parámetros y solo requiere dos evaluaciones de la función objetivo en cada iteración, independientemente de la dimensión del problema. Este algoritmo es muy popular debido a su eficiencia, simplicidad computacional y facilidad de implementación.

 

 

Pongamos un ejemplo en Java para obtener el mínimo local de una función: Tomemos la función  f(x) = x3 -2x2 + 6 y su derivada f'(x) = 3x2 – 4x. Con ello calculamos un mínimo local.

 

Gradiente Descendente Mínimo local (java)
Gradiente Descendente Mínimo local (java)

 

Acciones a tener en cuenta.

  • Sí el descenso del gradiente funciona correctamente, la función de costo debería disminuir después de cada iteración.
  • Cuando el gradiente ya no puede disminuir la función de costo y permanece más o menos en el mismo nivel, decimos que ha convergido.
  • El número de iteraciones que se necesitan para converger puede variar mucho y por tanto, el número de ciclos es difícil de estimar.
  • La Tasa/Gamma tiene el potencial de cambiar el tiempo de computación.

 

Cuanto más grandes son los saltos en la tasa de aprendizaje, más rápido nos moveremos hacia el mínimo local, pero si los pasos son demasiado grandes, es posible que no se alcance el mínimo, nos pasamos y obtendremos errores, en lenguaje coloquial, “nos hemos pasado tres pueblos”. Si el valor es muy pequeño, el descenso de gradiente finalmente alcanzará el mínimo local, pero tal vez le tome demasiado tiempo. Y para redondear los problemas, no hay un solo valor que sea un buen valor, dado que la tasa de aprendizaje cambia de una función a otra.

 

En estas tablas se puede observar el cambio de gamma y en función de la misma comprobar que el número de ciclos varía enormemente, de los más de 800 hasta los 31. El mínimo local también varía, aunque este en menor medida.

 

Tasa Precisión Mínimo Ciclo
0,010 0,0000000000000002 1,3333333333333401 791
0,0000000000000002 1,3333333333333400 792
0,0000000000000002 1,3333333333333397 793
0,0000000000000002 1,3333333333333395 794
0,0000000000000002 1,3333333333333393 795
0,0000000000000002 1,3333333333333390 796
0,0000000000000002 1,3333333333333388 797
0,0000000000000002 1,3333333333333386 798
0,0000000000000002 1,3333333333333384 799
0,0000000000000002 1,3333333333333381 800
0,0000000000000002 1,3333333333333380 801
0,0000000000000002 1,3333333333333377 802
0,0000000000000002 1,3333333333333375 803
0,0000000000000002 1,3333333333333373 804
0,0000000000000002 1,3333333333333370 805
0,0000000000000002 1,3333333333333368 806
0,0000000000000002 1,3333333333333366 807
0,0000000000000002 1,3333333333333364 808
0,0000000000000002 1,3333333333333361 809
-0,0000000000000000 1,3333333333333361 810
Mínimo local: 1,3333333333333361
Tasa Precisión Mínimo Ciclo
0,10 0,0000000000012275 1,3333333333351745 49
0,0000000000007365 1,3333333333344380 50
0,0000000000004419 1,3333333333339960 51
0,0000000000002651 1,3333333333337310 52
0,0000000000001590 1,3333333333335720 53
0,0000000000000955 1,3333333333334765 54
0,0000000000000573 1,3333333333334192 55
0,0000000000000344 1,3333333333333848 56
0,0000000000000204 1,3333333333333643 57
0,0000000000000124 1,3333333333333520 58
0,0000000000000075 1,3333333333333444 59
0,0000000000000044 1,3333333333333400 60
0,0000000000000027 1,3333333333333373 61
0,0000000000000016 1,3333333333333357 62
0,0000000000000009 1,3333333333333348 63
0,0000000000000004 1,3333333333333344 64
0,0000000000000004 1,3333333333333340 65
0,0000000000000002 1,3333333333333337 66
0,0000000000000002 1,3333333333333335 67
-0,0000000000000000 1,3333333333333335 68
Mínimo local: 1,3333333333333335

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Tasa Precisión Mínimo Ciclo
0,191 0,0000797958177079 1,3333086761806480 12
0,0000188377162817 1,3333275138969298 13
0,0000044460300070 1,3333319599269369 14
0,0000010492814060 1,3333330092083429 15
0,0000002476314325 1,3333332568397753 16
0,0000000584410749 1,3333333152808502 17
0,0000000137920968 1,3333333290729470 18
0,0000000032549352 1,3333333323278822 19
0,0000000007681646 1,3333333330960468 20
0,0000000001812868 1,3333333332773336 21
0,0000000000427840 1,3333333333201176 22
0,0000000000100968 1,3333333333302144 23
0,0000000000023828 1,3333333333325972 24
0,0000000000005624 1,3333333333331596 25
0,0000000000001328 1,3333333333332924 26
0,0000000000000313 1,3333333333333237 27
0,0000000000000073 1,3333333333333310 28
0,0000000000000018 1,3333333333333328 29
0,0000000000000004 1,3333333333333333 30
-0,0000000000000000 1,3333333333333333 31
Mínimo local: 1,3333333333333333

 

 

 

2 thoughts on “Gradiente Descendente

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *