étodos potenciales de prospección, FCAG, 2023.
Supongamos que buscamos el argumento que minimiza a la función $f: \mathbb{R}\to\mathbb{R}$ dada por $f(x) = \frac{1}{2}x^2 +1$. Utilizamos la notación $x^*$ para denotar la ubicación del mínimo, que en este caso es global y está en $x^*=0$.
Escribimos subrutinas para el cálculo de $f$ y de su derivada:
def f(x):
return x**2 / 2 + 1
def dfdx(x):
return x
Graficamos la función a minimizar, su derivada, el mínimo global $x^*$ y un punto inicial $x_0$.
Como podemos observar:
Sí $x_0<0 \rightarrow f^{\prime}(x_0)<0$. Podemos disminuir a $f(x_0)$ moviéndonos hacia la derecha de $x_0$.
Sí $x_0>0 \rightarrow f^{\prime}(x_0)>0$. Podemos disminuir a $f(x_0)$ moviéndonos hacia la izquierda de $x_0$.
En conclusión, siempre que $\epsilon>0$ sea lo suficientemente pequeño, podemos disminuir a $f(x)$ moviéndonos en sentido opuesto a su derivada.
Generalizando estas observaciones, podemos diseñar para $f : \mathbb{R}^n \to \mathbb{R}$ las bases de un algoritmo de minimización basado en la expresión
donde $\mathbf{\nabla}_{\mathbf{x}}\,f(\mathbf{x})$ es el gradiente de la función respecto de $\mathbf{x}$ y ${\color{green}\epsilon}>0$.
El parámetro $\epsilon$ se conoce como tamaño de paso (también conocido como "taza de aprendizaje"). Notamos que podemos decidir de movernos en cierta fracción de la derivada, es decir una cantidad $\epsilon\:f^{\prime}(x)$. De esta forma, si nos aproximamos a un mínimo, el cambio dado por $\epsilon\:f^{\prime}(x)$ es cada vez menor ya que la derivada debería aproximarse a $0$.
Una forma de implementar la idea de gradient descent puede ser delineada como sigue:
Una manera similar de proceder es la siguiente:
La sucesión $\mathbf{x}_{k}$ debería conducirnos hacia $\mathbf{x}^*$. El operador $||\cdot||$ es la norma Euclidea: $||\mathbf{x}||=\sqrt{\sum_j x_j^2}$.
El método de gradient descent es computacionalmente efectivo ya que no necesita guardar en memoria matrices para invertir. Sin embargo, es por lo general muy lento para converger hacia una solución aceptable.
El algoritmo puede generar overflow en especial si la codificación del algoritmo es naïve (es decir, sin line-search, sin preacondicionamiento y sin regularización). Por ejemplo, si el tamaño de paso es "grande" el método puede explorar una zona de la función objetivo donde las componentes del gradiente son también grandes y por lo tanto la actualización es grande también. Si esta tendencia de valores grandes se sostiene por un cierto número de iteraciones, se puede generar overflow. Un remedio para ello es elegir adecuadamente el tamaño de paso y utilizar regularización de forma que la norma de la solución no aumente sin límite.
Utilizamos ahora el método para estimar el mínimo global de $f(x) = \frac{1}{2}x^2+1$. Partimos del punto $x_0 = 2$ y empleamos el algoritmo para llegar a una estimación de $x^*$. La elección de $x_0$ y de los parámetros $\epsilon$ y $\delta$ influyen sobre el desarrollo del algoritmo.
x_n = 2
epsilon = 0.1
maxiter = 10
# Método naïve de gradient descent
for n in range(maxiter):
x_n = x_n - epsilon * dfdx(x_n)
Gradient descent Valor de x* : 0.0009135518149015478 Valor de f(x*) : 1.0000004172884593 Número de iteraciones: 74
Es importante observar la cantidad de iteraciones requeridas por el algoritmo para acercarse a $x^*$. La cantidad de iteraciones es según el consenso general, la mayor desventaja del método gradient descent. Por lo general, se persigue realizar la minimización "quickly, cheap, and in small memory".
Podemos representar la trayectoria de los puntos seguidos por el algoritmo hacia el mínimo. En este ejemplo podemos aproximarnos mucho más al mínimo aumentando el número de iteraciones. También podemos aumentar el tamaño de paso para aproximarnos al mínimo en un número menor de iteraciones.
Por último, realizamos la minimización por medio de subrutinas especializadas del paquete SciPy. En este caso utilizamos la subrutina fmin del paquete optimize. El interesado puede consultar la página de manual para descubrir que método está programado, en que referencias se basa y que bondades presenta el algoritmo encapsulado por detrás de scipy.optimize.fmin:
from scipy import optimize
x_sol = optimize.fmin(f,x0 = 2.)
Optimization terminated successfully.
Current function value: 1.000000
Iterations: 18
Function evaluations: 36
Valor de x* : -1.7763568394002505e-15
Valor de f(x*): 1.0
Número de iteraciones: 18
Observamos que la cantidad de iteraciones utilizadas por scipy.optimize.fmin es menor que la del método recién delineado. Para arribar a la misma exactitud que este método, podemos emplear unas 50 iteraciones con $\epsilon=0.5$ en nuestro algoritmo de gradient descent:
Gradient descent Valor de x* : 8.881784197001252e-16 Valor de f(x*) : 1.0 Número de iteraciones: 52
Consideramos ahora la minimización para una función $f: \mathbb{R}^2\to\mathbb{R}$, es decir de dos parámetros. Tomamos la conocida función de Rosenbrock:
$$f(\mathbf{x})=f(x,y) = 100 (y-x^2)^2 + (1-x)^{2}.$$La función $f(x,y)$ tiene un mínimo global en $\mathbf{x^*}=(1,1)^T$ y allí se cumple además $f(\mathbf{x}^*)=0$.
Programamos la función y su gradiente como subrutinas.
Graficamos para observar la "topografía" de la función. Observamos que hay un "valle" angosto con valores pequeños que rodean al mínimo global.
Partiendo de $\mathbf{x}_0=(0,0)^T$ buscamos una aproximación a $\mathbf{x^*}$ por medio de steepest descent. Tomamos un tamaño de paso fijo $\epsilon=0.001$ y una tolerancia $\delta=0.001$. Notamos que el número de iteraciones es elevado. (Necesitaríamos unas 50000 iteraciones para obtener un resultado con error despreciable para este ejemplo).
Valor de x* : [0.99888361 0.997764 ] Valor de f(x)* : 1.2483152708635157e-06 Número de iteraciones: 14020
Graficamos para observar la trayectoria seguida por los parámetros $\mathbf{x}_k$ y los valores de $f(\mathbf{x}_k)$ en cada iteración $k$ del algoritmo. Para la función considerada, deberíamos aproximarnos al valor $f(\mathbf{x^*})=0.$
Con estos conceptos y herramientas, en otra actividad práctica probaremos invertir datos de anomalía de gravedad para estimar parámetros físicos y geométricos de un modelo directo no lineal. Otras variantes al método de gradient descent son presentadas en la clase preliminar de regresión lineal.
Eso es todo por hoy.
Esta actividad práctica está basada en la siguiente notebook; en el siguiente curso; en el libro de deep learning; en el clásico libro de optimización; en esta gran referencia sobre métodos numéricos; y en este libro sobre algoritmos de inversión.