Contenido principal

Curso: Cálculo multivariable > Unidad 3

Lección 4: Optimizar funciones multivariables (artículos)

Descenso de gradiente

El descenso de gradiente es un algoritmo de uso general que numéricamente encuentra un mínimo de funciones multivariables.

Antecedentes

¿Entonces, qué es esto?

El descenso de gradiente es un algoritmo que estima numéricamente dónde una función genera sus valores más bajos. Eso significa que encuentra mínimos locales, pero no al establecer

\nabla f = 0

como hemos visto antes. En lugar de encontrar mínimos manipulando símbolos, el descenso de gradiente aproxima la solución con números. Además, todo lo que necesita para ejecutarse es la salida numérica de una función, no requiere ninguna fórmula.

Vale la pena enfatizar esta distinción porque es lo que hace que este método resulte útil. Si tuviéramos una fórmula simple como

f (x) = x^{2} - 4 x

, entonces podríamos calcular fácilmente

\nabla f = 0

para determinar que

x = 2

minimiza

f (x)

. O podríamos usar el descenso de gradiente para obtener una aproximación numérica, algo así como

x \approx 1.99999967

. Ambas estrategias llegan a la misma respuesta.

Pero si no tenemos una fórmula simple para nuestra función, entonces se vuelve difícil o imposible resolver

\nabla f = 0

. Si nuestra función tiene cien o un millón de variables, entonces manipular los símbolos no es factible. Ahí es cuando una solución aproximada es valiosa y el descenso de gradiente puede darnos estas estimaciones sin importar cuán elaborada sea nuestra función.

Cómo funciona el descenso de gradiente

La forma en la que el descenso de gradiente logra encontrar el mínimo de funciones es más fácil de imaginar en tres dimensiones.

Piensa en una función

f (x, y)

que define algún terreno montañoso cuando se grafica como un mapa de altura. Aprendimos que el gradiente evaluado en cualquier punto representa la dirección del ascenso más pronunciado por este terreno montañoso. Eso podría darte una idea de cómo maximizar la función: comenzar con una entrada aleatoria, y tantas veces como podamos, dar un pequeño paso en la dirección del gradiente para movernos cuesta arriba. En otras palabras, subir la colina.

Por el contrario, para minimizar la función, podemos seguir el negativo del gradiente, y así ir en la dirección del descenso más pronunciado. Este es el descenso de gradiente. Formalmente, si comenzamos en un punto

x_{0}

y nos movemos una distancia positiva

α

en la dirección del gradiente negativo, entonces nuestro nuevo y mejorado

x_{1}

se verá así:

x_{1} = x_{0} - α \nabla f (x_{0})

Más generalmente, podemos escribir una fórmula para convertir

x_{n}

x_{n + 1}

x_{n + 1} = x_{n} - α \nabla f (x_{n})

A partir de una conjetura inicial

x_{0}

, la seguimos mejorando poco a poco hasta encontrar un mínimo local. Este proceso puede tomar miles de iteraciones, por lo que normalmente implementamos un gradiente de descenso con una computadora.

Ejemplo 1

Considera la función

f (x) = \frac{x^{2} \cos (x) - x}{10}

Como podemos ver en la gráfica, esta función tiene muchos mínimos locales. El descenso de gradiente encontrará diferentes mínimos dependiendo de nuestra conjetura inicial y de nuestro tamaño de paso.

Si por ejemplo elegimos

x_{0} = 6

α = 0.2

, el descenso de gradiente se mueve como se muestra en la siguiente gráfica. El primer punto es

x_{0}

y las líneas conectan cada punto con el siguiente de la secuencia. Después de solo

10

pasos, converge al mínimo cerca de

x = 4

Si usamos el mismo

x_{0}

pero

α = 1.5

parece como si el tamaño de paso es demasiado grande para que el descenso de gradiente converja al mínimo. Volveremos a esto cuando discutamos las limitaciones del algoritmo.

Si empezamos en

x_{0} = 7

con

α = 0.2

, descendemos en un mínimo local completamente diferente.

Ejemplo 2

Utilicemos el descenso de gradiente para resolver el siguiente problema: ¿Cómo podemos aproximar mejor $\sin (x)$ ‍ con un polinomio de grado $5$ ‍ dentro del rango $- 3 < x < 3$ ‍?

p (x) = a_{0} + a_{1} x + \dots + a_{5} x^{5}

Para poder utilizar el descenso de gradiente, necesitamos pensar el problema en términos de minimizar una función

f

. Intuitivamente, nuestro objetivo es encontrar los coeficientes

a_{0}, \dots, a_{5}

que hacen que

p (x)

sea lo más cercano posible a

\sin (x)

, mientras que

x

está entre

- 3

3

. Hay muchas maneras en las que podemos convertir esta idea en una función para minimizar. Una es llamada mínimos cuadrados:

f (a_{0}, \dots, a_{5}) = \int_{- 3}^{3} (p (x) - \sin (x))^{2} d x

En resumen, definimos nuestra

f

como la suma de qué tan incorrecto es

p (x)

en cada punto. Por ejemplo, si

p (x) = 2

cerca de

x = 0

, entonces

f

aumentará mucho porque

\sin (0) = 0

. El descenso de gradiente intentará hacer que

f

sea lo más baja posible, que es lo mismo que hacer que

p (x)

sea más cercano a

\sin (x)

. Elevamos al cuadrado esa diferencia por lo que la integral es siempre positiva.

Esto es lo que sucede si empezamos con

a_{0}, \dots, a_{5}

como números aleatorios y luego nos movemos a lo largo del gradiente negativo. El número en la parte superior izquierda muestra cuántos pasos hemos tomado hasta ahora, donde utilizamos un tamaño de paso de

α = 0.001

¡Obtenemos una aproximación bastante buena de

\sin (x)

\begin{aligned} p (x) = & - 0.00177 + 0.88974 x + 0.00287 x^{2} \\ - 0.11613 x^{3} - 0.00048 x^{4} + 0.00224 x^{5} \end{aligned}

Técnicamente, la animación de arriba utiliza algo llamado descenso de gradiente con momento, que es una variante que ayuda a evitar quedarse atorado en un mínimo local.

La idea es imaginar que estamos rodando una pelota por una colina, mientras nos movemos, vamos cada vez más rápido. Si encontramos un mínimo local suficientemente pequeño, lo pasaremos de largo porque tenemos el momento necesario para pasar por encima.

Sin momento, nos quedamos atorados en un mínimo local:

Con momento, encontramos el mínimo global:

Formalmente, empezamos con una posición

x_{0}

y una velocidad

v_{0} = 0

. Cada paso, le sumamos una fracción

λ

(normalmente alrededor de

0.9

) de la antigua velocidad al nuevo gradiente. De esa manera mantenemos parte de nuestro viejo momento durante cada paso.

\begin{aligned} v_{n + 1} & = λ v_{n} - α \nabla f (x_{n}) \\ x_{n + 1} & = x_{n} + v_{n + 1} \end{aligned}

Limitaciones

El descenso de gradiente tiene aplicaciones cada vez que tenemos una función que queremos minimizar, lo que es común en el aprendizaje automático, por ejemplo. Pero es importante conocer sus deficiencias para que podamos planificar su uso.

Una de sus limitaciones es que solo encuentra minimos locales (en lugar del mínimo global). Tan pronto como el algoritmo encuentra algún punto que sea un mínimo local, nunca escapará mientras el tamaño de paso no exceda el tamaño del foso.

En la gráfica anterior, cada mínimo local tiene su propio valle que atraparía un algoritmo de descenso de gradiente. Después de todo, el algoritmo siempre intenta ir hacia abajo, así que una vez que encuentra un punto en el que cada dirección sea hacia arriba, se detendrá. Mirando la gráfica desde una perspectiva diferente, también vemos que ese mínimo local es más bajo que el otro.

Cuando minimizamos una función, queremos encontrar el mínimo global, pero no hay manera de que el descenso de gradiente pueda distinguir los mínimos globales y locales.

Otra limitación del descenso de gradiente tiene que ver con el tamaño de paso

α

. Un buen tamaño de paso se mueve hacia el mínimo rápidamente y con cada paso realiza un progreso sustancial.

Un buen tamaño del paso converge rápidamente.

Sin embargo, si el tamaño de paso es demasiado grande, es posible que nunca converjamos al mínimo local porque lo excedemos en cada ocasión.

Un tamaño de paso grande diverge.

Si tenemos suerte y el algoritmo converge de todos modos, aún así podría dar más pasos de los necesarios.

Un tamaño de paso grande converge lentamente.

Si el tamaño de paso es demasiado pequeño, entonces tendremos una mayor probabilidad de que converja, pero tomaremos muchos más pasos de los necesarios. Esto es un problema cuando la función que estamos minimizando tiene miles o millones de variables, y evaluarla es engorroso.

Un tamaño de paso muy pequeño converge lentamente.

Una última limitación es que el descenso de gradiente solo funciona cuando nuestra función es diferenciable en todas partes. De lo contrario, podríamos llegar a un punto en el que el gradiente no esté definido, y entonces no podremos utilizar nuestra fórmula de actualización.

El descenso de gradiente falla para funciones no diferenciables.

Resumen

El descenso de gradiente minimiza las funciones diferenciables que dan como resultado un número y tienen cualquier cantidad de variables de entrada.
Hace esto al hacer una conjetura para $x_{0}$ ‍ y aplicar sucesivamente la fórmula $x_{n + 1} = x_{n} - α \nabla f (x_{n})$ ‍. En otras palabras, la fórmula indica dar un pequeño paso en la dirección del gradiente negativo.
El descenso de gradiente no puede determinar si un mínimo encontrado es local o global.
El tamaño de paso $α$ ‍ controla si el algoritmo converge a un mínimo rápida o lentamente, o si diverge.
Muchos problemas del mundo real se reducen a minimizar una función.

¿Quieres unirte a la conversación?

Inicia sesión

Ordenar por:

cperaltap
Publicado hace hace 3 años. Enlace directo a la publicación “¿Cómo saber cuando hay qu...” de cperaltap
¿Cómo saber cuando hay que parar la iteración?
¿Cómo se puede calcular ese error o tolerancia?
Botón que navega a la página de registroBotón que navega a la página de registro
(1 voto)
Respuesta

¿Sabes inglés? Haz clic aquí para ver más discusiones en el sitio en inglés de Khan Academy.