Contenido principal
Cálculo multivariable
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 del, f, equals, 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, left parenthesis, x, right parenthesis, equals, x, squared, minus, 4, x, entonces podríamos calcular fácilmente del, f, equals, 0 para determinar que x, equals, 2 minimiza f, left parenthesis, x, right parenthesis. O podríamos usar el descenso de gradiente para obtener una aproximación numérica, algo así como x, approximately equals, 1, point, 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 del, f, equals, 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, left parenthesis, x, comma, y, right parenthesis 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, start subscript, 0, end subscript y nos movemos una distancia positiva alpha en la dirección del gradiente negativo, entonces nuestro nuevo y mejorado x, start subscript, 1, end subscript se verá así:
Más generalmente, podemos escribir una fórmula para convertir x, start subscript, n, end subscript en x, start subscript, n, plus, 1, end subscript:
A partir de una conjetura inicial x, start subscript, 0, end subscript, 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, left parenthesis, x, right parenthesis, equals, start fraction, x, squared, cosine, left parenthesis, x, right parenthesis, minus, x, divided by, 10, end fraction.
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, start subscript, 0, end subscript, equals, 6 y alpha, equals, 0, point, 2, el descenso de gradiente se mueve como se muestra en la siguiente gráfica. El primer punto es x, start subscript, 0, end subscript 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, equals, 4.
Si usamos el mismo x, start subscript, 0, end subscript pero alpha, equals, 1, point, 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, start subscript, 0, end subscript, equals, 7 con alpha, equals, 0, point, 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 sine, left parenthesis, x, right parenthesis con un polinomio de grado 5 dentro del rango minus, 3, is less than, x, is less than, 3?
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, start subscript, 0, end subscript, comma, dots, comma, a, start subscript, 5, end subscript que hacen que p, left parenthesis, x, right parenthesis sea lo más cercano posible a sine, left parenthesis, x, right parenthesis, mientras que x está entre minus, 3 y 3. Hay muchas maneras en las que podemos convertir esta idea en una función para minimizar. Una es llamada mínimos cuadrados:
En resumen, definimos nuestra f como la suma de qué tan incorrecto es p, left parenthesis, x, right parenthesis en cada punto. Por ejemplo, si p, left parenthesis, x, right parenthesis, equals, 2 cerca de x, equals, 0, entonces f aumentará mucho porque sine, left parenthesis, 0, right parenthesis, equals, 0. El descenso de gradiente intentará hacer que f sea lo más baja posible, que es lo mismo que hacer que p, left parenthesis, x, right parenthesis sea más cercano a sine, left parenthesis, x, right parenthesis. Elevamos al cuadrado esa diferencia por lo que la integral es siempre positiva.
Esto es lo que sucede si empezamos con a, start subscript, 0, end subscript, comma, dots, comma, a, start subscript, 5, end subscript 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 alpha, equals, 0, point, 001.
¡Obtenemos una aproximación bastante buena de sine, left parenthesis, x, right parenthesis!
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.
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 alpha. 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, start subscript, 0, end subscript y aplicar sucesivamente la fórmula x, start subscript, n, plus, 1, end subscript, equals, x, start subscript, n, end subscript, minus, alpha, del, f, left parenthesis, x, start subscript, n, end subscript, right parenthesis. 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 alpha 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?
- ¿Cómo saber cuando hay que parar la iteración?
¿Cómo se puede calcular ese error o tolerancia?(1 voto)