El método de descenso por gradiente, gradient descent de ahora en adelante, es uno de los algoritmos de optimización más populares en aprendizaje automático, particularmente por su uso extensivo en el campo de las redes neuronales. Gradient descent es un método general de minimización para cualquier función $f$. A la versión original se le considera lenta pero versátil, sobretodo para casos de que la funciones multi-dimensionales.

Al algoritmo gradient descent se le conoce por varios nombres, sobretodo en la literatura en inglés (vanilla gradient descent, batch gradient descent). A veces se les da el nombre de steepest descent, pero este término es más propio para aproximación analítica de integrales . El algoritmo también tiene una versión gemela bizarra que en lugar de buscar por un mínimo busca el punto máximo de una función.

La función a optimizar

Encontrar EL PUNTO mínimo de una función a veces puede ser fácil:

Tomado de wikipedia

O a veces puede ser difícil:

Tomado de wikiepdia

La opciones para encontrar el punto mínimo de las funciones son:

Analítica, que consiste en calcular la derivada cerrada de una función y encontrar los puntos donde la derivada es igual a cero.
Métodos numéricos, localizarse en un punto de la función y tratar de descender al punto mínimo usando información de la primera derivada (gradient descent). También podemos usar información de la segunda derivada (Newtown’s gradient descent).
Usar métodos aproximativos: BFGS , PSO , …

En el primer método requiere de que nuestra función tenga una forma cerrada para la cual se pueda calcular su derivada. El segundo y tercer método son iterativos, en el sentido de que comienza en una solución y trata de identificar una serie de mejores soluciones. En los métodos numéricos se usa información local a nuestra posición, mientras en los métodos aproximativos se puede hacer uso de información “global”. En este post nos enfocaremos al método numérico de gradient descent.

El método naïve

Imaginemos que nosotros mismos estamos en una montaña y nuestra visibilidad es nula, no podemos ver más allá de un 1cm de distancia, y queremos llegar a un punto seguro localizado en la parte más baja de la montaña. Un forma de lograrlo sería dar un paso en cada una las cuatro orientaciones (este, oeste, norte y sur) y escoger aquella en la que bajemos más para dar un paso en esa dirección, y continuar así hasta encontrar un punto en dónde al checar todas las direcciones las alturas sean más altos que nuestro punto actual o de plano ya no bajemos tanto. Este método naïve es una variante de <em>hill climbing</em> de los cursos de inteligencia artificial. Desafortunadamente este método tiene varias desventajas como avanzar en una sola orientación y que el paso que damos siempre es del mismo tamaño (1cm en este ejemplo).

La dirección de mayor descenso

Otra desventaja del método naïve es que tenemos que dar cuatro pasos (cuatro operaciones) para averiguar en que orientación se baja más. Si sólo tuviéramos una forma de saber la dirección hacia dónde crece/decrece una función….

¡Un minuto lo tenemos! La primera derivada (pendiente ) de una función mide la rapidez con que cambia una función, es decir cuando crece. Podemos calcular la pendiente para un punto específico, esto quiere decir que estando en un punto podemos saber en ese preciso punto cuando crece la función. Si partiendo de un punto buscamos un punto mínimo de la función podemos seguir la dirección contraria a la pendiente e iremos bajando esa pendiente hasta un punto mínimo.

En comparación con el método naïve donde damos cuatro pasos para averiguar la dirección, con la pendiente tenemos la información necesaria para calcular la dirección de mayor descenso.

Gradiente

El gradiente es la generalización vectorial de la derivada, es un vector de tantas dimensiones como la función y cada dimensión contiene la derivada parcial en dicha dimensión:

$$\nabla f=\left[\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \ldots \frac{\partial f}{\partial x_n} \right]$$

El gradiente $\nabla f_x$ es el vector que contiene la información de cuanto crece la función en un punto especifico $x$ por cada dimensión de nuestra furnción de forma independiente.

¿De que tamaño dar el paso?

Hasta ahora sabemos en que dirección avanzar para descender, pero no cuánto descender. Una estrategia sería si la función crece “mucho” descender mucho, y si crece “poco” descender poco. Es decir dar el paso en forma proporcional al gradiente. Para poder controlar la proporción del paso utilizaremos un parámetro $k$ de tal forma que el paso a dar se cuantifica:

$$-k\nabla$$

$k$ es un parámetro de tunning del método gradient descent al que llamamos: learning rate.

Calculando a dónde llegamos

Dada una posición $x$ podemos avanzar a una nueva posición $\hat{x}$ que dependerá del paso que demos, tamaño y dirección:

$\hat{x}=x-k \nabla f(x) $

Para cada nueva posición podemos medir la diferencia entre $\hat{x}$ y $x$ si esta es menor que cierto umbral o si alcanzamos un máximo de iteraciones, podemos decidir que hemos alcanzado un punto mínimo.

En la siguiente figura podemos observar el recorrido iterativo de las nuevas posiciones. En un principio cada paso es más agresivo porque el gradiente es mayor, y conforme nos acercamos al punto mínimo los pasos son más pequeños.

Tomado de wikipedia

¿EL PUNTO MÍNIMO?

Aunque avancemos en dirección contraria al gradiente esta estrategia no nos garantiza que lleguemos al punto más mínimo, y en algunas ocasiones nos conducirá a mínimos locales. Estos son regiones que parecen mínimos por la configuración alrededor a ellos, pero no son el mínimo global. Otra región de la función todavía podría estar en una zona más baja.

Gradient descent en Machine Learning supervisada

Un escenario común en aprendizaje automático es el supervisado, en donde se busca aprender una función que tome como entradas un conjunto de valores y que produzca cierta señal. Por ejemplo: predecir si una imagen es de una cara o no, o si un audio pertenece a cierto género, o si un tweet es irónico o no. Para lograr esto en un esquema supervisado tenemos varios ejemplos de como lucen casos en los que la imagen es una cara, el audio es cha-cha-cha y el tweet es irónico. También tenemos casos cuando no es el caso.

De forma formal tenemos:

Conjunto de entrada $$X={x_1,x_2,\ldots,x_N}$$
Y las salidas que debería producir $$Y={y_1,y_2,\ldots,y_N}$$

A este conjuntos conjuntos se les conoce como ejemplos de entrenamiento, y por cada $x$ de entrada se produce una $y$. En el caso más sencillo $x$ puede ser de varias dimensiones y $y$ de una sola. $y$ puede ser numérica (regresión) o categorica (clasificación), mientras que $x$ de cualquier tipo o una combinación de estas.

El modelo

En aprendizaje automático buscamos establecer una relación entre las variables de entradas y la de salida. La forma de establecer dicha relación es a través de un modelo. El modelo define como se relacionan las variables de entrada para producir la salida. Por ejemplo, en el caso las entradas y salidas fueran uni-dimesional (una dimensión), ambas podrían generar un espacio bi-dimensional que podríamos definir a través del modelo de una línea del tipo: $y=mx+b$ (regresión lineal).

Los modelos dependen de parámetros, en este ejemplo $m$ y $b$, que podemos modificar para hacer que el modelo se aproxime de la mejor forma a la salida. A estos dos parámetros los representamos usando la notación $\theta$, de tal forma que buscamos encontrar $f_{\theta} (X) \approx Y$. Es decir que la funcion $f$ con los parámetros $\theta$ de tal forma que para todos los valores $X$ de entrada aproxime a los valores de salida $Y$ correspondientes.

Función de costo J

A nuestro modelo le podemos asignar diferentes valores a sus parámetros, algunos de estos harán que $f_{\theta} (X) $ aproximen mejor a $Y$. Para medir que tan bien nuestros parámetros definen a nuestra salida podemos definir una función de costo $J(\theta)$ que mida la diferencia entre las salidas originales y las salidas producidas por el modelo. Existen varias opciones para $J$ dos de las más comunes:

Mean square error MSE $$ \frac{1}{N} \sum_{i=1}^N( f_{\theta} (x_i)- y_i)^2$$
Mean absolute error MAE $$ \frac{1}{N} \sum_{i=1}^N|f_{\theta} (x_i)- y_i |$$

Gradient descent para minimizar J

En aprendizaje automático usamos gradient descent para encontrar los parámetros de nuestro modelo que mejor definen nuestro conjunto de entrenamiento. La forma de lograr eso es minimizar la función de costo $J$ de la siguiente forma:

$$\min_{\theta} J(\theta)$$

Esto quiere decir que queremos encontrar los parámetros $\theta$ que minimicen la diferencia entre las salidas $Y$ y las producidas por el modelo dependiente de $\theta$. Entre menor la diferencia quiere decir que el modelo $\theta$ aproxima mejor a la salida $Y$. Adaptando esto a gradient descent quiere decir que iteraremos sobre una secuencia de valores de $\theta$ de la siguiente forma:

$$ \hat\theta = \theta - k\nabla J(\theta)$$

En dónde $\hat\theta$ es una nueva posición para los parámetros que se acercan más al mínimo, es decir que hacen que $f_\theta(X)$ aproxime mejor a $Y$ . En esta formulación:

Nosotros escogemos $\theta$ y su $f$
Nosotros escogemos $J(\theta)$
Nosotros escogemos $k$
Lo único que queda por calcular es el gradiente $\nabla J(\theta) $

El algoritmo

Con todo lo anterior podemos definir el siguiente algoritmo:

	while True:
		if theta_-theta > threshold or iters > max_iters:
			break
		tetha_grad = evaluate_gradient(J, X,Y, tetha)
		tetha_ = tetha - learning_rate * theta_grad
		iters += 1

Ejemplo: regresión lineal para $y=mx+b$

Regresando al caso que $X$ y $Y$ son uni-dimensional y numéricas, y escogemos un modelo $y=mx+b$ con parámetros $\theta=(m,b)$. Lo que tenemos que hacer es calcular es el gradiente para estos parámetros. Primero escogemos nuestra función de costo, que para el ejemplo será MSE. Esto produce la siguiente expresión:

$$\hat{\theta} =\theta-k \nabla \frac{1}{N} \sum_{i=1}^N (y_i- {f}_{\theta} (x_i) )^2 $$

Para lo cual necesitamos calcular:

$$\nabla \theta = \nabla (m,b) =(m’, b’) = \left(\frac{\partial }{\partial m} J(\theta), \frac{\partial}{\partial b} J(\theta)\right)$$

Derivada $m$

Para el parámetro $m$ tenemos:

$$ m’ = \frac{\partial}{\partial m} \left( \frac{1}{N} \sum ({f}_{\theta} (x_i) - y_i)^2 \right) $$

Llegamos a la siguiente derivación:

$$ = \frac{2}{N} \sum\left((f_{\theta} (x_i) - y_i) \frac{\partial}{\partial m} (f_{\theta} (x_i) - y_i) \right) $$

Pero recordemos que:

$$ f_{\theta} = mx+b $$

Y sustituyendo llegamos:

$$ = \frac{2}{N} \sum\left((f_{\theta} (x_i) - y_i) \frac{\partial}{\partial m} (mx_i + b- y_i) \right) $$

Y por lo que:

$$= \frac{2}{N} \sum (f_{\theta} (x_i) - y_i) x_i $$

Derivada $b$

Para el parámetro $b$ tenemos:

$$ b’ = \frac{\partial}{\partial b} \left( \frac{1}{m} \sum ({f}_{\theta} (x_i) - y_i)^2 \right) $$

Llegamos a la siguiente derivación:

$$ = \frac{2}{N} \sum\left((f_{\theta} (x_i) - y_i) \frac{\partial}{\partial b} (mx_i + b- y_i) \right) $$

Y por lo que:

$$= \frac{2}{N} \sum (f_{\theta} (x_i) - y_i) $$

Parámetros a través de gradient descent

Con el gradiente $(m’,b’)$ podemos calcular los siguientes parámetros de $(\hat m, \hat b) de la siguiente forma:

$$ \hat m = m - \frac{k}{N} \sum(f_{\theta} (x_i) - y_i) \cdot x_i $$

$$ \hat b = b - \frac{k}{N} \sum(f_{\theta} (x_i) - y_i) $$

Resúmen

Gradient descent nos permite localizar un mínimo en una función de forma iterativa
Iteramos entre un valor actual y una posición
La nueva posición se calcula con la posición actual menos un “paso” hacia la dirección que mayor descenso en esa posición
En aprendizaje automático, la función a minimizar es la función de costo ($J$) que reduce la diferencia entre nuestro modelo y la salida a aprender
En este caso iteraremos entre nuevas posiciones para los parámetros $\theta$ de nuestro modelo

Descenso por gradiente (Gradient descent)