La idea es dar pasos repetidos en la dirección opuesta al gradiente (o gradiente aproximado) de la función en el punto actual, porque esta es la dirección del descenso más pronunciado. Por el contrario, avanzar en la dirección del gradiente conducirá a un máximo local de esa función; el procedimiento se conoce entonces como ascenso en gradiente . Es particularmente útil en el aprendizaje automático para minimizar la función de costo o pérdida. [1] El descenso de gradiente no debe confundirse con los algoritmos de búsqueda local , aunque ambos son métodos iterativos de optimización .
El descenso de gradiente se atribuye generalmente a Augustin-Louis Cauchy , quien lo sugirió por primera vez en 1847. [2] Jacques Hadamard propuso de forma independiente un método similar en 1907. [3] [4] Sus propiedades de convergencia para problemas de optimización no lineal fueron estudiadas por primera vez por Haskell Curry en 1944, [5] y el método fue cada vez más estudiado y utilizado en las décadas siguientes. [6] [7]
El descenso de gradiente se basa en la observación de que si la función multivariable está definida y diferenciable en una vecindad de un punto , entonces disminuye más rápido si uno va en la dirección del gradiente negativo de at . De ello se deduce que, si
entonces, para un tamaño de paso o tasa de aprendizaje lo suficientemente pequeño . En otras palabras, el término se resta porque queremos avanzar en contra del gradiente, hacia el mínimo local. Con esta observación en mente, se comienza con una estimación de un mínimo local de y se considera la secuencia tal que
entonces, con suerte, la secuencia converge al mínimo local deseado. Tenga en cuenta que el valor del tamaño del paso puede cambiar en cada iteración.
Es posible garantizar la convergencia a un mínimo local bajo ciertos supuestos sobre la función (por ejemplo, convexa y Lipschitz ) y elecciones particulares de . Estos incluyen la secuencia
como en el método de Barzilai-Borwein , [8] [9] o una secuencia que satisface las condiciones de Wolfe (que se puede encontrar mediante la búsqueda de líneas ). Cuando la función es convexa , todos los mínimos locales también son mínimos globales, por lo que en este caso el descenso del gradiente puede converger a la solución global.
Este proceso se ilustra en la imagen adyacente. Aquí, se supone que está definido en el plano y que su gráfica tiene forma de cuenco . Las curvas azules son las líneas de contorno , es decir, las regiones en las que el valor de es constante. Una flecha roja que se origina en un punto muestra la dirección del gradiente negativo en ese punto. Tenga en cuenta que el gradiente (negativo) en un punto es ortogonal a la línea de contorno que pasa por ese punto. Vemos que el descenso del gradiente nos lleva al fondo del cuenco, es decir, al punto donde el valor de la función es mínimo.
Una analogía para comprender el descenso de gradientes
La intuición básica detrás del descenso de gradientes se puede ilustrar mediante un escenario hipotético. Las personas están atrapadas en las montañas y están tratando de bajar (es decir, tratando de encontrar el mínimo global). Hay una densa niebla que hace que la visibilidad sea extremadamente baja. Por lo tanto, el camino que baja de la montaña no es visible, por lo que deben utilizar información local para encontrar el mínimo. Pueden utilizar el método de descenso en gradiente, que implica observar la pendiente de la colina en su posición actual y luego proceder en la dirección con el descenso más pronunciado (es decir, cuesta abajo). Si estuvieran tratando de encontrar la cima de la montaña (es decir, el máximo), entonces procederían en la dirección del ascenso más empinado (es decir, cuesta arriba). Usando este método, eventualmente encontrarían el camino montaña abajo o posiblemente quedarían atrapados en algún agujero (es decir, mínimo local o punto de silla ), como un lago de montaña. Sin embargo, supongamos también que la pendiente de la colina no es inmediatamente obvia con una simple observación, sino que requiere un instrumento sofisticado para medirlo, que las personas tienen en ese momento. Se necesita bastante tiempo para medir la pendiente de la colina con el instrumento, por lo que deberían minimizar el uso del instrumento si quisieran bajar de la montaña antes del atardecer. La dificultad entonces es elegir la frecuencia con la que deben medir la pendiente de la colina para no desviarse del camino.
En esta analogía, las personas representan el algoritmo y el camino tomado montaña abajo representa la secuencia de configuraciones de parámetros que explorará el algoritmo. La pendiente de la colina representa la pendiente de la función en ese punto. El instrumento utilizado para medir la pendiente es la diferenciación . La dirección que eligen viajar se alinea con el gradiente de la función en ese punto. La cantidad de tiempo que viajan antes de tomar otra medida es el tamaño del paso.
Elegir el tamaño del paso y la dirección de descenso
Dado que el uso de un tamaño de paso demasiado pequeño ralentizaría la convergencia y uno demasiado grande provocaría un exceso y divergencia, encontrar un buen ajuste de es un problema práctico importante. Philip Wolfe también abogó por utilizar en la práctica "elecciones inteligentes de la dirección [de descenso]". [10] Si bien usar una dirección que se desvía de la dirección de descenso más pronunciada puede parecer contrario a la intuición, la idea es que la pendiente más pequeña puede compensarse manteniéndose a lo largo de una distancia mucho más larga.
Para razonar matemáticamente sobre esto, considere una dirección y un tamaño de paso y considere la actualización más general:
.
Encontrar buenos ajustes de y requiere algo de reflexión. En primer lugar, nos gustaría que la dirección de actualización apunte cuesta abajo. Matemáticamente, dejar de denotar el ángulo entre y , esto requiere que Para decir más, necesitamos más información sobre la función objetivo que estamos optimizando. Bajo el supuesto bastante débil de que es continuamente diferenciable, podemos demostrar que: [11]
Esta desigualdad implica que la cantidad en la que podemos estar seguros de que la función disminuye depende de un equilibrio entre los dos términos entre corchetes. El primer término entre corchetes mide el ángulo entre la dirección de descenso y el gradiente negativo. El segundo término mide la rapidez con la que cambia el gradiente a lo largo de la dirección de descenso.
En principio, la desigualdad ( 1 ) podría optimizarse y elegir un tamaño y dirección de paso óptimos. El problema es que evaluar el segundo término entre corchetes requiere evaluar y las evaluaciones de gradiente adicionales son generalmente costosas e indeseables. Algunas formas de solucionar este problema son:
Renuncie a los beneficios de una dirección de descenso inteligente estableciendo y utilice la búsqueda de líneas para encontrar un tamaño de paso adecuado , como uno que satisfaga las condiciones de Wolfe . Una forma más económica de elegir las tasas de aprendizaje es la búsqueda de líneas retrospectivas , un método que tiene buenas garantías teóricas y resultados experimentales. Tenga en cuenta que no es necesario elegir ser el degradado; cualquier dirección que tenga un producto de intersección positivo con el gradiente dará como resultado una reducción del valor de la función (para un valor suficientemente pequeño de ).
Suponiendo que es dos veces diferenciable, use su hessiano para estimar. Luego elija y optimizando la desigualdad ( 1 ).
Suponiendo que sea Lipschitz , use su constante de Lipschitz para limitar Luego elija y optimizando la desigualdad ( 1 ).
Cree un modelo personalizado de . Luego elija y optimizando la desigualdad ( 1 ).
Bajo supuestos más sólidos sobre la función, como la convexidad , pueden ser posibles técnicas más avanzadas.
Generalmente, siguiendo una de las recetas anteriores, se puede garantizar la convergencia a un mínimo local. Cuando la función es convexa , todos los mínimos locales también son mínimos globales, por lo que en este caso el descenso del gradiente puede converger a la solución global.
reformulado como un problema de minimización cuadrática. Si la matriz del sistema es simétrica real y definida positiva , una función objetivo se define como la función cuadrática, con minimización de
La minimización de la búsqueda de líneas , encontrando el tamaño de paso localmente óptimo en cada iteración, se puede realizar analíticamente para funciones cuadráticas, y se conocen fórmulas explícitas para el óptimo local. [6] [13]
Por ejemplo, para una matriz real simétrica y definida positiva , un algoritmo simple puede ser el siguiente, [6]
Para evitar multiplicar por dos veces por iteración, observamos que implica , lo que da el algoritmo tradicional, [14]
El método rara vez se utiliza para resolver ecuaciones lineales, siendo el método del gradiente conjugado una de las alternativas más populares. El número de iteraciones de descenso de gradiente es comúnmente proporcional al número de condición espectral de la matriz del sistema (la relación entre los valores propios máximo y mínimo de ) , mientras que la convergencia del método de gradiente conjugado generalmente está determinada por una raíz cuadrada del número de condición, es decir , es mucho más rápido. Ambos métodos pueden beneficiarse del preacondicionamiento , donde el descenso del gradiente puede requerir menos suposiciones sobre el preacondicionador. [14]
Solución de un sistema no lineal.
El descenso de gradiente también se puede utilizar para resolver un sistema de ecuaciones no lineales . A continuación se muestra un ejemplo que muestra cómo utilizar el descenso de gradiente para resolver tres variables desconocidas, x 1 , x 2 y x 3 . Este ejemplo muestra una iteración del descenso del gradiente.
Considere el sistema no lineal de ecuaciones.
Introduzcamos la función asociada.
dónde
Ahora se podría definir la función objetivo.
que intentaremos minimizar. Como suposición inicial, usemos
Esto se puede hacer con cualquiera de una variedad de algoritmos de búsqueda de líneas . También se podría simplemente adivinar cuál da
Al evaluar la función objetivo a este valor, se obtiene
La disminución desde el valor del siguiente paso de
es una disminución considerable en la función objetivo. Otros pasos reducirían aún más su valor hasta que se encontrara una solución aproximada al sistema.
Comentarios
El descenso de gradiente funciona en espacios de cualquier número de dimensiones, incluso en espacios de dimensiones infinitas. En el último caso, el espacio de búsqueda suele ser un espacio funcional y se calcula la derivada de Fréchet del funcional que se va a minimizar para determinar la dirección de descenso. [7]
El hecho de que el descenso de gradiente funcione en cualquier número de dimensiones (al menos en un número finito) puede verse como una consecuencia de la desigualdad de Cauchy-Schwarz , es decir, la magnitud del producto interno (punto) de dos vectores de cualquier dimensión se maximiza cuando son colineales. . En el caso del descenso de gradiente, eso sería cuando el vector de ajustes de variables independientes es proporcional al vector de gradiente de derivadas parciales.
El descenso del gradiente puede requerir muchas iteraciones para calcular un mínimo local con la precisión requerida , si la curvatura en diferentes direcciones es muy diferente para la función dada. Para tales funciones, el precondicionamiento , que cambia la geometría del espacio para dar forma a los conjuntos de niveles de función como círculos concéntricos , cura la convergencia lenta. Sin embargo, construir y aplicar el precondicionamiento puede resultar costoso desde el punto de vista computacional.
El descenso de gradiente se puede combinar con una búsqueda de líneas , encontrando el tamaño de paso localmente óptimo en cada iteración. Realizar la búsqueda de líneas puede llevar mucho tiempo. Por el contrario, utilizar un valor fijo pequeño puede generar una mala convergencia y un valor grande puede conducir a una divergencia. Sin embargo, se pueden alternar tamaños de paso pequeños y grandes para mejorar la tasa de convergencia. [15] [16]
Los métodos basados en el método de Newton y la inversión del hessiano utilizando técnicas de gradiente conjugado pueden ser mejores alternativas. [17] [18] Generalmente, estos métodos convergen en menos iteraciones, pero el costo de cada iteración es mayor. Un ejemplo es el método BFGS que consiste en calcular en cada paso una matriz por la que se multiplica el vector gradiente para ir en una "mejor" dirección, combinada con un algoritmo de búsqueda lineal más sofisticado , para encontrar el "mejor" valor de Para extremadamente En problemas grandes, donde dominan los problemas de memoria de la computadora, se debe usar un método de memoria limitada como L-BFGS en lugar de BFGS o el descenso más pronunciado.
Se puede considerar que el descenso de gradiente aplica el método de Euler para resolver ecuaciones diferenciales ordinarias a un flujo de gradiente . A su vez, esta ecuación se puede derivar como un controlador óptimo [19] para el sistema de control dado en forma de retroalimentación .
Modificaciones
El descenso del gradiente puede converger a un mínimo local y desacelerarse en las proximidades de un punto de silla . Incluso para la minimización cuadrática sin restricciones, el descenso de gradiente desarrolla un patrón en zig-zag de iteraciones posteriores a medida que avanzan las iteraciones, lo que resulta en una convergencia lenta. Se han propuesto múltiples modificaciones del descenso de gradiente para abordar estas deficiencias.
Métodos de gradiente rápido
Yurii Nesterov ha propuesto [20] una modificación simple que permite una convergencia más rápida para problemas convexos y desde entonces se ha generalizado aún más. Para problemas suaves y sin restricciones, el método se denomina método de gradiente rápido (FGM) o método de gradiente acelerado (AGM). Específicamente, si la función diferenciable es convexa y es Lipschitz , y no se supone que sea fuertemente convexa , entonces el error en el valor objetivo generado en cada paso por el método de descenso de gradiente estará acotado por . Utilizando la técnica de aceleración de Nesterov, el error disminuye en . [21] [22] Se sabe que la tasa de disminución de la función de costos es óptima para los métodos de optimización de primer orden. Sin embargo, existe la oportunidad de mejorar el algoritmo reduciendo el factor constante. El método de gradiente optimizado (OGM) [23] reduce esa constante por un factor de dos y es un método óptimo de primer orden para problemas a gran escala. [24]
Para problemas restringidos o no suaves, la FGM de Nesterov se denomina método de gradiente proximal rápido (FPGM), una aceleración del método de gradiente proximal .
impulso obola pesadamétodo
Al intentar romper el patrón en zig-zag del descenso del gradiente, el método del impulso o de la bola pesada utiliza un término de impulso en analogía con una bola pesada que se desliza sobre la superficie de los valores de la función que se minimiza, [6] o con el movimiento de masas en la dinámica newtoniana. a través de un medio viscoso en un campo de fuerza conservador . [25] El descenso de gradiente con impulso recuerda la actualización de la solución en cada iteración y determina la siguiente actualización como una combinación lineal del gradiente y la actualización anterior. Para la minimización cuadrática sin restricciones, un límite de tasa de convergencia teórica del método de la bola pesada es asintóticamente el mismo que el del método de gradiente conjugado óptimo . [6]
Esta técnica se utiliza en el descenso de gradiente estocástico y como una extensión de los algoritmos de retropropagación utilizados para entrenar redes neuronales artificiales . [26] [27] En la dirección de la actualización, el descenso de gradiente estocástico agrega una propiedad estocástica. Los pesos se pueden utilizar para calcular las derivadas.
Extensiones
El descenso de gradiente se puede ampliar para manejar restricciones incluyendo una proyección sobre el conjunto de restricciones. Este método sólo es factible cuando la proyección se puede calcular de manera eficiente en una computadora. Bajo supuestos adecuados, este método converge. Este método es un caso específico del algoritmo hacia adelante-hacia atrás para inclusiones monótonas (que incluye programación convexa y desigualdades variacionales ). [28]
Las propiedades del descenso de gradiente dependen de las propiedades de la función objetivo y de la variante de descenso de gradiente utilizada (por ejemplo, si se utiliza un paso de búsqueda de línea ). Los supuestos realizados afectan la tasa de convergencia y otras propiedades que pueden demostrarse para el descenso de gradiente. [30] Por ejemplo, si se supone que el objetivo es fuertemente convexo y los labios suaves , entonces el descenso del gradiente converge linealmente con un tamaño de paso fijo. [1] Los supuestos más flexibles conducen a garantías de convergencia más débiles o requieren una selección del tamaño del paso más sofisticada. [30]
^ ab Boyd, Stephen; Vandenberghe, Lieven (8 de marzo de 2004). Optimizacion convexa. Prensa de la Universidad de Cambridge. ISBN 978-0-521-83378-3.
^ Lemaréchal, C. (2012). "Cauchy y el método del gradiente" (PDF) . Doc Matemáticas Extra : 251–254. Archivado desde el original (PDF) el 29 de diciembre de 2018 . Consultado el 26 de enero de 2020 .
^ Hadamard, Jacques (1908). "Mémoire sur le problème d'analyse relatif à l'équilibre des plaques élastiques encastrées". Mémoires présentés par divers savants éstrangers à l'Académie des Sciences de l'Institut de France . 33 .
^ Courant, R. (1943). "Métodos variacionales para la solución de problemas de equilibrio y vibraciones". Boletín de la Sociedad Matemática Estadounidense . 49 (1): 1–23. doi : 10.1090/S0002-9904-1943-07818-4 .
^ Curry, Haskell B. (1944). "El método de descenso más pronunciado para problemas de minimización no lineal". Cuarto de galón. Aplica. Matemáticas . 2 (3): 258–261. doi : 10.1090/qam/10667 .
^ ABCDE Polyak, Boris (1987). Introducción a la Optimización.
^ ab Akilov, médico de cabecera; Kantorovich, LV (1982). Análisis funcional (2ª ed.). Prensa de Pérgamo. ISBN0-08-023036-9.
^ Barzilai, Jonathan; Borwein, Jonathan M. (1988). "Métodos de gradiente de tamaño de paso de dos puntos". Revista IMA de Análisis Numérico . 8 (1): 141–148. doi :10.1093/imanum/8.1.141.
^ Fletcher, R. (2005). "Sobre el método Barzilai-Borwein". En Qi, L.; Teo, K.; Yang, X. (eds.). Optimización y Control con Aplicaciones . Optimización aplicada. vol. 96. Boston: Springer. págs. 235-256. ISBN0-387-24254-6.
^ Wolfe, Philip (abril de 1969). "Condiciones de convergencia para métodos de ascenso". Revisión SIAM . 11 (2): 226–235. doi :10.1137/1011036.
^ Bernstein, Jeremy; Vahdat, Arash; Yue, Yisong; Liu, Ming-Yu (12 de junio de 2020). "Sobre la distancia entre dos redes neuronales y la estabilidad del aprendizaje". arXiv : 2002.03432 [cs.LG].
^ Haykin, Simon S. Teoría del filtro adaptativo. Pearson Education India, 2008. - pág. 108-142, 217-242
^ Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos (2ª ed.). Filadelfia, Pensilvania: Sociedad de Matemáticas Industriales y Aplicadas. págs.195. ISBN978-0-89871-534-7.
^ ab Bouwmeester, Henricus; Dougherty, Andrés; Knyazev, Andrés V. (2015). "Precondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado". Procedia Ciencias de la Computación . 51 : 276–285. arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 .
^ Altschuler, Jason (Jason M.) (2018). Avaricia, cobertura y aceleración en la optimización convexa (Tesis de tesis). Instituto de Tecnología de Massachusetts.
^ Parshall, Allison (11 de agosto de 2023). "Pasos gigantes y arriesgados pueden resolver problemas de optimización más rápido". Revista Quanta . Consultado el 11 de agosto de 2023 .
^ Strutz, T. (2016). Ajuste de datos e incertidumbre: una introducción práctica a los mínimos cuadrados ponderados y más (2ª ed.). Springer Vieweg. ISBN978-3-658-11455-8.
^ Ross, IM (julio de 2019). "Una teoría de control óptimo para la optimización no lineal". Revista de Matemática Computacional y Aplicada . 354 : 39–51. doi : 10.1016/j.cam.2018.12.044 . S2CID 127649426.
^ Nesterov, Yurii (2004). Conferencias introductorias sobre optimización convexa: un curso básico . Saltador. ISBN1-4020-7553-7.
^ Vandenberghe, Lieven (2019). "Métodos de gradiente rápido" (PDF) . Apuntes de conferencias para EE236C en UCLA .
^ Walkington, Noel J. (2023). "Método de Nesterov para la optimización convexa". Revisión SIAM . 65 (2): 539–562. doi :10.1137/21M1390037. ISSN 0036-1445.
^ Kim, D.; Fessler, JA (2016). "Métodos optimizados de primer orden para una minimización convexa suave". Programación Matemática . 151 (1–2): 81–107. arXiv : 1406.5468 . doi :10.1007/s10107-015-0949-3. PMC 5067109 . PMID 27765996. S2CID 207055414.
^ Drori, Yoel (2017). "La complejidad exacta basada en información de la minimización convexa suave". Revista de Complejidad . 39 : 1–16. arXiv : 1606.01424 . doi :10.1016/j.jco.2016.11.001. S2CID 205861966.
^ Qian, Ning (enero de 1999). "Sobre el término de impulso en algoritmos de aprendizaje de descenso de gradiente". Redes neuronales . 12 (1): 145-151. CiteSeerX 10.1.1.57.5612 . doi :10.1016/S0893-6080(98)00116-6. PMID 12662723. S2CID 2783597.
^ "Adaptación del impulso y la tasa de aprendizaje". Universidad de Willamette . Consultado el 17 de octubre de 2014 .
^ Geoffrey Hinton ; Nitish Srivastava; Kevin Swersky. "El método del impulso". Coursera . Consultado el 2 de octubre de 2018 .Parte de una serie de conferencias para el curso en línea de Coursera Redes neuronales para el aprendizaje automático Archivado el 31 de diciembre de 2016 en Wayback Machine .
^ Combettes, PL; Pesquet, J.-C. (2011). "Métodos de división proximal en el procesamiento de señales". En Bauschke, HH; Burachik, RS ; Combettes, PL; Elser, V.; Lucas, DR; Wolkowicz, H. (eds.). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . Nueva York: Springer. págs. 185-212. arXiv : 0912.3522 . ISBN978-1-4419-9568-1.
^ "Algoritmo de descenso de espejos".
^ ab Bubeck, S. (2014). Teoría de la optimización convexa para el aprendizaje automático. ArXiv, abs/1405.4980.
Otras lecturas
Boyd, Esteban ; Vandenberghe, Lieven (2004). "Minimización sin restricciones" (PDF) . Optimizacion convexa . Nueva York: Cambridge University Press. págs. 457–520. ISBN 0-521-83378-7.
Chong, Edwin KP; Żak, Stanislaw H. (2013). "Métodos de gradiente". Introducción a la optimización (Cuarta ed.). Hoboken: Wiley. págs. 131-160. ISBN 978-1-118-27901-4.
Himmelblau, David M. (1972). "Procedimientos de minimización sin restricciones mediante derivados". Programación no lineal aplicada . Nueva York: McGraw-Hill. págs. 63-132. ISBN 0-07-028921-2.
enlaces externos
Wikimedia Commons tiene medios relacionados con el descenso de gradientes .
Uso del descenso de gradiente en C++, Boost, Ublas para regresión lineal
Una serie de vídeos de Khan Academy analiza el ascenso del gradiente
Libro en línea que enseña el descenso de gradientes en el contexto de redes neuronales profundas
Archivado en Ghostarchive y Wayback Machine: "Gradient Descent, cómo aprenden las redes neuronales". 3Azul1Marrón . 16 de octubre de 2017 - vía YouTube .
Manual de teoremas de convergencia para métodos de gradiente (estocásticos)