Hispanopedia Wiki
Articulo de referencia

Descenso de gradiente

Descenso de gradiente en 2D El descenso de gradiente es un método de optimización matemática sin restricciones . Es un algoritmo iterativo de primer orden para minimizar una fun...

Hispanopedia WikiContenido en espanolLectura gratuita
Descenso de gradiente en 2D

El descenso de gradiente es un método de optimización matemática sin restricciones . Es un algoritmo iterativo de primer orden para minimizar una función multivariable diferenciable .

La idea consiste en dar pasos repetidos en la dirección opuesta al gradiente (o gradiente aproximado) de la función en el punto actual, ya que esta es la dirección de descenso más pronunciado. Por el contrario, dar pasos en la dirección del gradiente conducirá a una trayectoria que maximiza dicha función; este procedimiento se conoce como ascenso de gradiente . 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 es particularmente útil en el aprendizaje automático y la inteligencia artificial para minimizar la función de costo o pérdida. [ 1 ]

El descenso de gradiente se atribuye generalmente a Augustin-Louis Cauchy , quien lo sugirió por primera vez en 1847. [ 2 ] Jacques Hadamard propuso independientemente 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 se fue estudiando y utilizando cada vez más en las décadas siguientes. [ 6 ] [ 7 ]

Una extensión sencilla del descenso de gradiente, el descenso de gradiente estocástico , sirve como el algoritmo más básico utilizado para entrenar la mayoría de las redes neuronales profundas en la actualidad.

Descripción

Ilustración de un descenso gradual en una serie de conjuntos de niveles.

El descenso de gradiente se basa en la observación de que si la función multivariableF(incógnita){\displaystyle f(\mathbf {x} )}está definido y es diferenciable en un entorno de un puntoa{\displaystyle \mathbf {a} }, entoncesF(incógnita){\displaystyle f(\mathbf {x} )}disminuye más rápidamente si uno va desdea{\displaystyle \mathbf {a} }en la dirección del gradiente negativo deF{\displaystyle f}ena,i.mi.,−∇F(a){\displaystyle \mathbf {a} ,es decir,-\nabla f(\mathbf {a} )}. De ello se deduce que, si

anorte+1=anorte−η∇F(anorte){\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\eta \nabla f(\mathbf {a} _{n})}

para un tamaño de paso o tasa de aprendizaje suficientemente pequeñoη∈R+{\displaystyle \eta \in \mathbb {R} _{+}}, entonces F(anorte)≥F(anorte+1){\displaystyle f(\mathbf {a_ {n}} )\geq f(\mathbf {a_ {n+1}} )}En otras palabras, el términoη∇F(a){\displaystyle \eta \nabla f(\mathbf {a} )}se resta dea{\displaystyle \mathbf {a} }porque queremos movernos en contra del gradiente, hacia el mínimo local. Con esta observación en mente, uno comienza con una suposición.incógnita0{\displaystyle \mathbf {x} _{0}}para un mínimo local deF{\displaystyle f}y considera la secuenciaincógnita0,incógnita1,incógnita2,…{\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }de tal manera que

incógnitanorte+1=incógnitanorte−ηnorte∇F(incógnitanorte), norte≥0.{\displaystyle \mathbf {x} _ {n+1}=\mathbf {x} _ {n}-\eta _ {n}\nabla f(\mathbf {x} _ {n}),\ n\geq 0.}

Tenemos una secuencia monótona

F(incógnita0)≥F(incógnita1)≥F(incógnita2)≥⋯,{\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} _{1})\geq f(\mathbf {x} _{2})\geq \cdots ,}

así que la secuencia(incógnitanorte){\displaystyle (\mathbf {x} _ {n})}converge al mínimo local deseado. Tenga en cuenta que el valor del tamaño del pasoη{\displaystyle \eta }Se permite que cambie en cada iteración.

Es posible garantizar la convergencia a un mínimo local bajo ciertas suposiciones sobre la función.F{\displaystyle f}(Por ejemplo,F{\displaystyle f}convexo y∇F{\displaystyle \nabla f}Lipschitz ) y elecciones particulares deη{\displaystyle \eta }. Esos incluyen la secuencia

ηnorte=|(incógnitanorte−incógnitanorte−1)⊤[∇F(incógnitanorte)−∇F(incógnitanorte−1)]|‖∇F(incógnitanorte)−∇F(incógnitanorte−1)‖2{\displaystyle \eta _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{\top }\left[\nabla f(\mathbf {x} _{n})-\nabla f(\mathbf {x} _{n-1})\right]\right|}{\left\|\nabla f(\mathbf {x} _{n})-\nabla f(\mathbf {x} _{n-1})\right\|^{2}}}}

como en el método de Barzilai-Borwein , [ 8 ] [ 9 ] o una secuenciaηnorte{\displaystyle \eta _{n}}que satisface las condiciones de Wolfe (que se pueden encontrar mediante una búsqueda lineal ). Cuando la funciónF{\displaystyle f}es convexa , todos los mínimos locales son también mínimos globales, por lo que en este caso el descenso de gradiente puede converger a la solución global.

Este proceso se ilustra en la imagen adjunta. Aquí,F{\displaystyle f}Se supone que está definida 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 deF{\displaystyle f}es constante. Una flecha roja que parte de un punto muestra la dirección del gradiente negativo en ese punto. Nótese que el gradiente (negativo) en un punto es ortogonal a la línea de contorno que pasa por ese punto. Vemos que el descenso de gradiente nos lleva al fondo del cuenco, es decir, al punto donde el valor de la funciónF{\displaystyle f}es mínimo.

Una analogía para comprender el descenso de gradiente.

Niebla en las montañas

La intuición básica detrás del descenso de gradiente se puede ilustrar con un escenario hipotético. Un grupo de personas se encuentra atrapado en la montaña e intenta descender (es decir, busca el mínimo global). Hay una densa niebla que reduce drásticamente la visibilidad. Por lo tanto, el camino de descenso no es visible, así que deben usar información local para encontrar el mínimo. Pueden usar el método de descenso de gradiente, que consiste en observar la pendiente de la colina en su posición actual y luego avanzar en la dirección de mayor pendiente descendente. Si intentaran encontrar la cima de la montaña (es decir, el máximo), avanzarían en la dirección de mayor pendiente ascendente. Usando este método, eventualmente encontrarían el camino de descenso o posiblemente quedarían atrapados en algún hueco (es decir, un 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 a simple vista, sino que requiere un instrumento sofisticado para medirla, del cual disponen en ese momento. Medir la pendiente de la colina con dicho instrumento lleva bastante tiempo. Por lo tanto, deberían minimizar el uso del instrumento si quieren bajar de la montaña antes del atardecer. La dificultad reside entonces en elegir la frecuencia con la que deben medir la pendiente para no perderse.

En esta analogía, las personas representan el algoritmo, y el camino recorrido al descender la montaña representa la secuencia de configuraciones de parámetros que el algoritmo explorará. La pendiente de la colina representa la inclinación de la función en ese punto. El instrumento utilizado para medir la pendiente es la diferenciación . La dirección que eligen para desplazarse se alinea con el gradiente de la función en ese punto. El tiempo que transcurre antes de realizar otra medición es el tamaño del paso.

Elegir el tamaño del paso y la dirección de descenso.

Dado que se utiliza un tamaño de pasoη{\displaystyle \eta }que es demasiado pequeño ralentizaría la convergencia y unaη{\displaystyle \eta }demasiado grande provocaría sobrepaso y divergencia, encontrar un buen ajuste deη{\displaystyle \eta }es un problema práctico importante. Philip Wolfe también abogó por usar "elecciones inteligentes de la dirección [de descenso]" en la práctica. [ 10 ] Si bien usar una dirección que se desvíe de la dirección de descenso más pronunciada puede parecer contraintuitivo, la idea es que la pendiente menor se puede compensar manteniéndola durante una distancia mucho mayor.

Para razonar sobre esto matemáticamente, consideremos una dirección.pagnorte{\displaystyle \mathbf {p} _ {n}}y tamaño del pasoηnorte{\displaystyle \eta _{n}}y consideremos la actualización más general:

anorte+1=anorte−ηnortepagnorte{\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\eta _{n}\,\mathbf {p} _{n}}.

Encontrar buenos ajustes depagnorte{\displaystyle \mathbf {p} _ {n}}yηnorte{\displaystyle \eta _{n}}requiere algo de reflexión. En primer lugar, nos gustaría que la dirección de la actualización apuntara cuesta abajo. Matemáticamente, dejarθnorte{\displaystyle \theta _{n}}denotan el ángulo entre−∇F(anorte){\displaystyle -\nabla f(\mathbf {a_ {n}} )}ypagnorte{\displaystyle \mathbf {p} _ {n}}, esto requiere queporque⁡θnorte>0.{\displaystyle \cos \theta _{n}>0.}Para decir más, necesitamos más información sobre la función objetivo que estamos optimizando. Bajo el supuesto bastante débil de queF{\displaystyle f}es continuamente diferenciable, podemos demostrar que: [ 11 ]

Esta desigualdad implica que la cantidad por la cual podemos estar seguros de la funciónF{\displaystyle f}La disminución 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 la pendiente negativa. El segundo término mide la rapidez con la que cambia la pendiente a lo largo de la dirección de descenso.

En principio, la desigualdad ( 1 ) podría optimizarse sobrepagnorte{\displaystyle \mathbf {p} _{n}}yηnorte{\displaystyle \eta _{n}}para elegir un tamaño de paso y una dirección óptimos. El problema es que evaluar el segundo término entre corchetes requiere evaluar∇F(anorte−tηnortepagnorte){\displaystyle \nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})}y las evaluaciones de gradiente adicionales suelen ser costosas e indeseables. Algunas maneras de solucionar este problema son:

  • Renuncia a los beneficios de una dirección de descenso inteligente al establecerpagnorte=∇F(anorte){\displaystyle \mathbf {p} _{n}=\nabla f(\mathbf {a_{n}} )}y utilice la búsqueda lineal para encontrar un tamaño de paso adecuado.γnorte{\displaystyle \gamma _{n}}, como por ejemplo una que satisfaga las condiciones de Wolfe . Una forma más económica de elegir las tasas de aprendizaje es la búsqueda lineal con retroceso , un método que cuenta con buenas garantías teóricas y resultados experimentales. Nótese que no es necesario elegir pagnorte{\displaystyle \mathbf {p} _{n}}ser el gradiente; cualquier dirección que tenga un producto interno positivo con el gradiente dará como resultado una reducción del valor de la función (para un valor suficientemente pequeño deηnorte{\displaystyle \eta _{n}}).
  • Suponiendo queF{\displaystyle f}es dos veces diferenciable, use su matriz hessiana∇2F{\displaystyle \nabla ^{2}f}estimar‖∇F(anorte−tηnortepagnorte)−∇F(anorte)‖2≈‖tηnorte∇2F(anorte)pagnorte‖.{\displaystyle \|\nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})-\nabla f(\mathbf {a} _{n})\|_{2}\approx \|t\eta _{n}\nabla ^{2}f(\mathbf {a} _{n})\mathbf {p} _{n}\|.}Luego eligepagnorte{\displaystyle \mathbf {p} _{n}}yηnorte{\displaystyle \eta _{n}}optimizando la desigualdad ( 1 ).
  • Suponiendo que∇F{\displaystyle \nabla f}es Lipschitz , use su constante de LipschitzL{\displaystyle L}atar‖∇F(anorte−tηnortepagnorte)−∇F(anorte)‖2≤Ltηnorte‖pagnorte‖.{\displaystyle \|\nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})-\nabla f(\mathbf {a} _{n})\|_{2}\leq Lt\eta _{n}\|\mathbf {p} _{n}\|.}Luego eligepagnorte{\displaystyle \mathbf {p} _{n}}yηnorte{\displaystyle \eta _{n}}optimizando la desigualdad ( 1 ).
  • Construye un modelo personalizado demáximot∈[0,1]‖∇F(anorte−tηnortepagnorte)−∇F(anorte)‖2‖∇F(anorte)‖2{\displaystyle \max _{t\in [0,1]}{\frac {\|\nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})-\nabla f(\mathbf {a} _{n})\|_{2}}{\|\nabla f(\mathbf {a} _{n})\|_{2}}}}paraF{\displaystyle f}. Luego eligepagnorte{\displaystyle \mathbf {p} _{n}}yηnorte{\displaystyle \eta _{n}}optimizando la desigualdad ( 1 ).
  • Bajo supuestos más estrictos sobre la funciónF{\displaystyle f}Por ejemplo, en casos de convexidad , podrían ser posibles técnicas más avanzadas .

Por lo general, siguiendo una de las recetas anteriores, se puede garantizar la convergencia a un mínimo local. Cuando la funciónF{\displaystyle f}es convexa , todos los mínimos locales son también mínimos globales, por lo que en este caso el descenso de gradiente puede converger a la solución global.

Solución de un sistema lineal

El algoritmo de descenso más pronunciado aplicado al filtro de Wiener [ 12 ]

El descenso de gradiente se puede utilizar para resolver un sistema de ecuaciones lineales.

Aincógnita−b=0{\displaystyle \mathbf {A} \mathbf {x} -\mathbf {b} =0}

reformulado como un problema de minimización cuadrática. Si la matriz del sistemaA{\displaystyle \mathbf {A} }es real simétrica y definida positiva , una función objetivo se define como la función cuadrática, con minimización de

F(incógnita)=incógnita⊤Aincógnita−2incógnita⊤b,{\displaystyle f(\mathbf {x} )=\mathbf {x} ^{\top }\mathbf {A} \mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} ,}

de modo que

∇F(incógnita)=2(Aincógnita−b).{\displaystyle \nabla f(\mathbf {x} )=2(\mathbf {A} \mathbf {x} -\mathbf {b} ).}

Para una matriz real generalA{\displaystyle \mathbf {A} }, los mínimos cuadrados lineales definen

F(incógnita)=‖Aincógnita−b‖2.{\displaystyle f(\mathbf {x} )=\left\|\mathbf {A} \mathbf {x} -\mathbf {b} \right\|^{2}.}

En el método tradicional de mínimos cuadrados lineales para datos realesA{\displaystyle \mathbf {A} }yb{\displaystyle \mathbf {b} }se utiliza la norma euclidiana , en cuyo caso

∇F(incógnita)=2A⊤(Aincógnita−b).{\displaystyle \nabla f(\mathbf {x} )=2\mathbf {A} ^{\top }(\mathbf {A} \mathbf {x} -\mathbf {b} ).}

La minimización de la búsqueda lineal , encontrando el tamaño de paso óptimo local.η{\displaystyle \eta }En cada iteración, se puede realizar analíticamente para funciones cuadráticas y fórmulas explícitas para el óptimo local.η{\displaystyle \eta }son conocidos. [ 6 ] [ 13 ]

Por ejemplo, para una matriz real simétrica y definida positivaA{\displaystyle \mathbf {A} }, un algoritmo simple puede ser el siguiente, [ 6 ]

repetir en el bucle:r:=b−Aincógnitaη:=r⊤r/r⊤Arincógnita:=incógnita+ηrsi r⊤r Si es suficientemente pequeño, entonces salga del bucle.fin del bucle de repeticióndevolver incógnita como resultado{\displaystyle {\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&\qquad \eta  :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x}  :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{si }}\mathbf {r} ^{\top }\mathbf {r} {\text{es suficientemente pequeño, entonces salir del bucle}}\\&{\text{fin del bucle de repetición}}\\&{\text{devuelve }}\mathbf {x} {\text{como resultado}}\end{aligned}}}

Para evitar multiplicar porA{\displaystyle \mathbf {A} }dos veces por iteración, observamos queincógnita:=incógnita+ηr{\displaystyle \mathbf {x} :=\mathbf {x} +\eta \mathbf {r} } implicar:=r−ηAr{\displaystyle \mathbf {r} :=\mathbf {r} -\eta \mathbf {Ar} } , lo que da como resultado el algoritmo tradicional, [ 14 ]

r:=b−Aincógnitarepetir en el bucle:η:=r⊤r/r⊤Arincógnita:=incógnita+ηrsi r⊤r Si es suficientemente pequeño, entonces salga del bucle.r:=r−ηArfin del bucle de repeticióndevolver incógnita como resultado{\displaystyle {\begin{aligned}&\mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&{\text{repetir en el bucle:}}\\&\qquad \eta  :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x}  :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{si }}\mathbf {r} ^{\top }\mathbf {r} {\text{es suficientemente pequeño, entonces salir del bucle}}\\&\qquad \mathbf {r}  :=\mathbf {r} -\eta \mathbf {Ar} \\&{\text{fin del bucle de repetición}}\\&{\text{retornar }}\mathbf {x} {\text{ como resultado}}\end{aligned}}}
Trayectoria de convergencia del método de descenso más pronunciado para A = [[2, 2], [2, 3]]

Este 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 del descenso de gradiente suele ser proporcional al número de condición espectral.κ(A){\displaystyle \kappa (\mathbf {A} )}de la matriz del sistemaA{\displaystyle \mathbf {A} }(la relación entre los valores propios máximos y mínimos deA⊤A{\displaystyle \mathbf {A} ^{\top }\mathbf {A} }) , mientras que la convergencia del método del gradiente conjugado se determina típicamente mediante la raíz cuadrada del número de condición, es decir, es mucho más rápido. Ambos métodos pueden beneficiarse del precondicionamiento , donde el descenso de gradiente puede requerir menos suposiciones sobre el precondicionador. [ 14 ]

Comportamiento geométrico y ortogonalidad residual

En el descenso más pronunciado aplicado a la resoluciónAincógnita=b{\displaystyle \mathbf {Ax} =\mathbf {b} }, dóndeA{\displaystyle \mathbf {A} }es simétrica definida positiva, los vectores residualesrk=b−Aincógnitak{\displaystyle \mathbf {r} _{k}=\mathbf {b} -\mathbf {A} \mathbf {x} _{k}}son ortogonales entre iteraciones:

⟨rk+1,rk⟩=0.{\displaystyle \langle \mathbf {r} _{k+1},\mathbf {r} _{k}\rangle =0.}

Debido a que cada paso se da en la dirección más pronunciada, los pasos de descenso más pronunciado alternan entre direcciones alineadas con los ejes extremos de los conjuntos de nivel alargados. Cuandoκ(A){\displaystyle \kappa (\mathbf {A} )}es grande, esto produce una trayectoria característica en zigzag. El mal condicionamiento deA{\displaystyle \mathbf {A} }es la causa principal de la lenta convergencia, y la ortogonalidad de los residuos sucesivos refuerza esta alternancia.

Como se muestra en la imagen de la derecha, el descenso más pronunciado converge lentamente debido al alto número de condición deA{\displaystyle \mathbf {A} }y la ortogonalidad de los residuos obliga a cada nueva dirección a deshacer el sobreimpulso del paso anterior. El resultado es una trayectoria que zigzaguea hacia la solución. Esta ineficiencia es una de las razones por las que se prefieren los métodos de gradiente conjugado o de precondicionamiento. [ 15 ]

Solución de un sistema no lineal

El descenso de gradiente también puede utilizarse para resolver sistemas de ecuaciones no lineales . A continuación , se muestra un ejemplo de cómo usar el descenso de gradiente para resolver tres variables desconocidas: x₁ , x₂ y x₃ . Este ejemplo muestra una iteración del descenso de gradiente.

Consideremos el sistema de ecuaciones no lineales

Una animación que muestra las primeras 83 iteraciones del descenso de gradiente aplicadas a este ejemplo. Las superficies son isosuperficies deF(incógnita(norte)){\displaystyle f(\mathbf {x} ^{(n)})}Según mis estimaciones actualesincógnita(norte){\displaystyle \mathbf {x} ^{(n)}}Las flechas indican la dirección del descenso. Debido a que el tamaño del paso es pequeño y constante, la convergencia es lenta.
{3incógnita1−porque⁡(incógnita2incógnita3)−32=04incógnita12−625incógnita22+2incógnita2−1=0exp⁡(−incógnita1incógnita2)+20incógnita3+10π−33=0{\displaystyle {\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}}

Introduzcamos la función asociada.

GRAMO(incógnita)=[3incógnita1−porque⁡(incógnita2incógnita3)−324incógnita12−625incógnita22+2incógnita2−1exp⁡(−incógnita1incógnita2)+20incógnita3+10π−33],{\displaystyle G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}},}

dónde

incógnita=[incógnita1incógnita2incógnita3].{\displaystyle \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}.}

Ahora se podría definir la función objetivo.

F(incógnita)=12GRAMO⊤(incógnita)GRAMO(incógnita)=12[(3incógnita1−porque⁡(incógnita2incógnita3)−32)2+(4incógnita12−625incógnita22+2incógnita2−1)2+(exp⁡(−incógnita1incógnita2)+20incógnita3+10π−33)2],{\displaystyle {\begin{aligned}f(\mathbf {x} )&={\frac {1}{2}}G^{\top }(\mathbf {x} )G(\mathbf {x} )\\&={\frac {1}{2}}\left[\left(3x_{1}-\cos(x_{2}x_{3})-{\frac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\right.\\&{}\qquad \left.\left(\exp(-x_{1}x_{2})+20x_{3}+{\frac {10\pi -3}{3}}\right)^{2}\right],\end{aligned}}}

que intentaremos minimizar. Como primera suposición, usemos

incógnita(0)=0=[000].{\displaystyle \mathbf {x} ^{(0)}=\mathbf {0} ={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}.}

Sabemos que

incógnita(1)=0−η0∇F(0)=0−η0JGRAMO(0)⊤GRAMO(0),{\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\eta _{0}\nabla f(\mathbf {0} )=\mathbf {0} -\eta _{0}J_{G}(\mathbf {0} )^{\top }G(\mathbf {0} ),}

donde la matriz jacobianaJGRAMO{\displaystyle J_{G}}es dado por

JGRAMO(incógnita)=[3pecado⁡(incógnita2incógnita3)incógnita3pecado⁡(incógnita2incógnita3)incógnita28incógnita1−1250incógnita2+20−incógnita2exp⁡(−incógnita1incógnita2)−incógnita1exp⁡(−incógnita1incógnita2)20].{\displaystyle J_{G}(\mathbf {x} )={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}.}

Calculamos:

JGRAMO(0)=[3000200020],GRAMO(0)=[−2.5−110.472].{\displaystyle J_{G}(\mathbf {0} )={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {0} )={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}.}

De este modo

incógnita(1)=0−η0[−7.5−2209,44],{\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\eta _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}},}

y

F(0)=0,5((−2.5)2+(−1)2+(10.472)2)=58.456.{\displaystyle f(\mathbf {0} )=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456.}

Ahora, un adecuadoη0{\displaystyle \eta _{0}}debe encontrarse de tal manera que

F(incógnita(1))≤F(incógnita(0))=F(0).{\displaystyle f\left(\mathbf {x} ^{(1)}\right)\leq f\left(\mathbf {x} ^{(0)}\right)=f(\mathbf {0} ).}

Esto se puede hacer con cualquiera de los diversos algoritmos de búsqueda lineal . También se podría simplemente adivinar.η0=0,001,{\displaystyle \eta _{0}=0.001,}lo cual da

incógnita(1)=[0,00750,002−0,20944].{\displaystyle \mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}.}

Al evaluar la función objetivo en este valor, se obtiene:

F(incógnita(1))=0,5((−2.48)2+(−1.00)2+(6.28)2)=23.306.{\displaystyle f\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306.}

La disminución deF(0)=58.456{\displaystyle f(\mathbf {0} )=58.456}al valor del siguiente paso de

F(incógnita(1))=23.306{\displaystyle f\left(\mathbf {x} ^{(1)}\right)=23.306}

Se trata de una disminución considerable de la función objetivo. Pasos posteriores reducirían aún más su valor hasta encontrar una solución aproximada al sistema.

Comentarios

El descenso de gradiente funciona en espacios de cualquier número de dimensiones, incluso en espacios de dimensión infinita. En este último caso, el espacio de búsqueda suele ser un espacio de funciones , y se calcula la derivada de Fréchet del funcional que se va a minimizar para determinar la dirección de descenso. [ 7 ]

Que el descenso de gradiente funcione en cualquier número de dimensiones (al menos un número finito) puede considerarse una consecuencia de la desigualdad de Cauchy-Schwarz , es decir, la magnitud del producto escalar de dos vectores de cualquier dimensión se maximiza cuando son colineales . En el caso del descenso de gradiente, esto ocurriría cuando el vector de ajustes de las variables independientes es proporcional al vector gradiente de las derivadas parciales.

El descenso de gradiente puede requerir muchas iteraciones para calcular un mínimo local con la precisión necesaria , si la curvatura en diferentes direcciones es muy distinta para la función dada. Para tales funciones, el precondicionamiento , que modifica la geometría del espacio para dar forma a los conjuntos de nivel de la función como círculos concéntricos , soluciona la lenta convergencia. Sin embargo, construir y aplicar el precondicionamiento puede resultar computacionalmente costoso.

El descenso de gradiente se puede modificar mediante momentos [ 16 ] ( Nesterov , Polyak, [ 17 ] y Frank-Wolfe [ 18 ] ) y parámetros de bola pesada (medias móviles exponenciales [ 19 ] y momento positivo-negativo [ 20 ] ). Los principales ejemplos de estos optimizadores son Adam, DiffGrad, Yogi, AdaBelief, etc.

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. [ 21 ] [ 22 ] 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 cual se multiplica el vector gradiente para ir en una dirección "mejor", combinado con un algoritmo de búsqueda lineal más sofisticado , para encontrar el "mejor" valor deη.{\displaystyle \eta .}Para problemas extremadamente grandes, donde predominan los problemas de memoria del ordenador, se debería utilizar un método de memoria limitada como L-BFGS en lugar de BFGS o el método del descenso más pronunciado.

Si bien a veces es posible sustituir el descenso de gradiente por un algoritmo de búsqueda local , el descenso de gradiente no pertenece a la misma familia: aunque es un método iterativo para la optimización local , se basa en el gradiente de una función objetivo en lugar de una exploración explícita de un espacio de soluciones .

El descenso de gradiente puede considerarse como la aplicación del método de Euler para resolver ecuaciones diferenciales ordinarias.incógnita′(t)=−∇F(incógnita(t)){\displaystyle x'(t)=-\nabla f(x(t))}a un flujo de gradiente . A su vez, esta ecuación puede derivarse como un controlador óptimo [ 23 ] para el sistema de control.incógnita′(t)=tú(t){\displaystyle x'(t)=u(t)}contú(t){\displaystyle u(t)}proporcionado en el formulario de comentariostú(t)=−∇F(incógnita(t)){\displaystyle u(t)=-\nabla f(x(t))}.

Modificaciones

El descenso de gradiente puede converger a un mínimo local y ralentizarse 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 zigzag en las iteraciones subsiguientes a medida que avanza, lo que resulta en una convergencia lenta. Se han propuesto diversas modificaciones del descenso de gradiente para abordar estas deficiencias.

métodos de gradiente rápido

Yurii Nesterov propuso [ 24 ] una modificación simple que permite una convergencia más rápida para problemas convexos y que desde entonces se ha generalizado aún más. Para problemas suaves 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 diferenciableF{\displaystyle f}es convexo y∇F{\displaystyle \nabla f}es Lipschitz , y no se asume queF{\displaystyle f}Si es fuertemente convexa , entonces el error en el valor objetivo generado en cada pasok{\displaystyle k}mediante el método de descenso de gradiente estará acotado porO(k−1){\textstyle {\mathcal {O}}\left({k^{-1}}\right)}. Utilizando la técnica de aceleración de Nesterov, el error disminuye enO(k−2){\textstyle {\mathcal {O}}\left({k^{-2}}\right)}. [ 25 ] [ 26 ] Se sabe que la tasaO(k−2){\displaystyle {\mathcal {O}}\left({k^{-2}}\right)}La disminución de la función de costo 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) [ 27 ] reduce esa constante a la mitad y es un método óptimo de primer orden para problemas a gran escala. [ 28 ]

Para problemas restringidos o no suaves, el método FGM de Nesterov se denomina método de gradiente proximal rápido (FPGM), una aceleración del método de gradiente proximal .

Método de impulso o de bola pesada

Para romper el patrón en zigzag del descenso de gradiente, el método de momento o de bola pesada utiliza un término de momento en analogía con una bola pesada que se desliza sobre la superficie de valores de la función que se minimiza, [ 6 ] o con el movimiento de masa en la dinámica newtoniana a través de un medio viscoso en un campo de fuerza conservativo . [ 29 ] El descenso de gradiente con momento 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 teórico de la tasa de convergencia del método de 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 extensión de los algoritmos de retropropagación empleados para entrenar redes neuronales artificiales . [ 30 ] [ 31 ] En la dirección de actualización, el descenso de gradiente estocástico añade una propiedad estocástica. Los pesos pueden utilizarse para calcular las derivadas.

Extensiones

El descenso de gradiente puede extenderse para manejar restricciones mediante la inclusión de una proyección sobre el conjunto de restricciones. Este método solo es factible cuando la proyección se puede calcular eficientemente en una computadora. Bajo supuestos adecuados, este método converge. Este método es un caso específico del algoritmo de avance-retroceso para inclusiones monótonas (que incluye programación convexa y desigualdades variacionales ). [ 32 ]

El descenso de gradiente es un caso especial del descenso de espejo que utiliza la distancia euclidiana al cuadrado como la divergencia de Bregman dada . [ 33 ]

Propiedades teóricas

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 lineal ). Las suposiciones realizadas afectan la tasa de convergencia y otras propiedades que pueden demostrarse para el descenso de gradiente. [ 34 ] Por ejemplo, si se supone que la función objetivo es fuertemente convexa y Lipschitz suave , entonces el descenso de gradiente converge linealmente con un tamaño de paso fijo. [ 1 ] Suposiciones menos estrictas conllevan garantías de convergencia más débiles o requieren una selección de tamaño de paso más sofisticada. [ 34 ]

Ejemplos

Véase también

Referencias

  1. 1 2 Boyd, Stephen; Vandenberghe, Lieven (2004-03-08). Optimización convexa . Cambridge University Press. doi : 10.1017/cbo9780511804441 . ISBN 978-0-521-83378-3.
  2. ↑ Lemaréchal, C. (1 de enero de 2012). «Cauchy y el método del gradiente» (PDF) . En Grötschel, M. (ed.). Optimization Stories . Documenta Mathematica Series. Vol. 6 (1.ª ed.). EMS Press. pp. 251–254 . doi : 10.4171/dms/6/27 . ISBN    978-3-936609-58-5Archivado del original (PDF) el 29-12-2018 . Consultado el 26-01-2020 .
  3. ^ 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 .
  4. ↑ Courant, R. (1943). "Métodos variacionales para la solución de problemas de equilibrio y vibraciones" . Boletín de la Sociedad Matemática Americana . 49 (1): 1– 23. doi : 10.1090/S0002-9904-1943-07818-4 .
  5. ↑ Curry, Haskell B. (1944). "El método del descenso más pronunciado para problemas de minimización no lineal" . Quart. Appl. Math . 2 (3): 258– 261. doi : 10.1090/qam/10667 .
  6. 1 2 3 4 5 Polyak, Boris (1987). Introducción a la optimización .
  7. ^ Akilov , médico de cabecera; Kantorovich, LV (1982). Análisis funcional (2ª ed.). Prensa de Pérgamo. ISBN  0-08-023036-9.
  8. ↑ Barzilai, Jonathan; Borwein, Jonathan M. (1988). "Métodos de gradiente de tamaño de paso de dos puntos". IMA Journal of Numerical Analysis . 8 (1): 141– 148. doi : 10.1093/imanum/8.1.141 .
  9. ↑ Fletcher, R. (2005). "Sobre el método de Barzilai-Borwein". En Qi, L.; Teo, K.; Yang, X. (eds.). Optimización y control con aplicaciones . Optimización aplicada. Vol. 96. Boston: Springer. pp. 235–256 . ISBN   0-387-24254-6.
  10. ↑ Wolfe, Philip (abril de 1969). "Condiciones de convergencia para métodos de ascenso". SIAM Review . 11 (2): 226– 235. doi : 10.1137/1011036 .
  11. ↑ Bernstein, Jeremy; Vahdat, Arash; Yue, Yisong; Liu, Ming-Yu (2020-06-12). "Sobre la distancia entre dos redes neuronales y la estabilidad del aprendizaje". arXiv : 2002.03432 [ cs.LG ].
  12. ↑ Haykin, Simon S. Teoría de filtros adaptativos. Pearson Education India, 2008. - págs. 108-142, 217-242
  13. ↑ Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos (2.ª ed.). Filadelfia, Pensilvania: Society for Industrial and Applied Mathematics. 195 págs . ISBN   978-0-89871-534-7.
  14. 1 2 Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). "Preacondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado" . Procedia Computer Science . 51 : 276–285 . arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 .
  15. ↑ Holmes, M. (2023). Introducción a la computación científica y al análisis de datos, 2.ª ed . Springer. ISBN 978-3-031-22429-4.
  16. ↑ Abdulkadirov, Ruslan; Lyakhov, Pavel; Nagornov, Nikolay (enero de 2023). "Revisión de algoritmos de optimización en redes neuronales modernas" . Matemáticas . 11 (11): 2466. doi : 10.3390/math11112466 . ISSN 2227-7390 . 
  17. ↑ Diakonikolas, Jelena; Jordan, Michael I. (enero de 2021). "Métodos generalizados basados ​​en el momento: una perspectiva hamiltoniana" . SIAM Journal on Optimization . 31 (1): 915– 944. arXiv : 1906.00436 . doi : 10.1137/20M1322716 . ISSN 1052-6234 . 
  18. ↑ Meyer, Gerard GL (noviembre de 1974). "Algoritmos acelerados de Frank-Wolfe" . SIAM Journal on Control . 12 (4): 655– 663. doi : 10.1137/0312050 . ISSN 0036-1402 . 
  19. ↑ Kingma, Diederik P.; Ba, Jimmy (29-01-2017), Adam: Un método para la optimización estocástica , arXiv : 1412.6980
  20. ↑ Xie, Zeke; Yuan, Li; Zhu, Zhanxing; Sugiyama, Masashi (2021-07-01). "Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalization" . Actas de la 38.ª Conferencia Internacional sobre Aprendizaje Automático . PMLR: 11448–11458 . arXiv : 2103.17182 .
  21. ↑ Press, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (1992). Numerical Recipes in C: The Art of Scientific Computing (2.ª ed.). Nueva York: Cambridge University Press . ISBN  0-521-43108-5.
  22. ↑ Strutz, T. (2016). Ajuste de datos e incertidumbre: una introducción práctica a los mínimos cuadrados ponderados y más allá (2.ª ed.). Springer Vieweg. ISBN  978-3-658-11455-8.
  23. ↑ Ross, IM (julio de 2019). "Una teoría de control óptimo para la optimización no lineal" . Journal of Computational and Applied Mathematics . 354 : 39–51 . doi : 10.1016/j.cam.2018.12.044 . S2CID 127649426 . 
  24. ↑ Nesterov, Yurii (2004). Lecciones introductorias sobre optimización convexa: un curso básico . Springer. ISBN 1-4020-7553-7.
  25. ↑ Vandenberghe, Lieven (2019). "Métodos de gradiente rápido" (PDF) . Apuntes de conferencias para EE236C en UCLA .
  26. ↑ Walkington, Noel J. (2023). "Método de Nesterov para la optimización convexa" . SIAM Review . 65 (2): 539– 562. doi : 10.1137/21M1390037 . ISSN 0036-1445 . 
  27. ↑ Kim, D.; Fessler, JA (2016). " Métodos optimizados de primer orden para la minimización convexa suave" . Mathematical Programming . 151 ( 1–2 ): 81–107 . arXiv : 1406.5468 . doi : 10.1007/ s10107-015-0949-3 . PMC 5067109. PMID 27765996. S2CID 207055414 .   
  28. ↑ Drori, Yoel (2017). "La complejidad basada en información exacta de la minimización convexa suave". Journal of Complexity . 39 : 1–16 . arXiv : 1606.01424 . doi : 10.1016/j.jco.2016.11.001 . S2CID 205861966 . 
  29. ↑ Qian, Ning (enero de 1999). "Sobre el término de momento en los 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 .   
  30. ↑ "Momento y adaptación de la tasa de aprendizaje" . Universidad de Willamette . Consultado el 17 de octubre de 2014 .
  31. ↑ Geoffrey Hinton ; Nitish Srivastava; Kevin Swersky. "El método del momento" . 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/12/2016 en Wayback Machine .
  32. ↑ 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.; Luke, DR; Wolkowicz, H. (eds.). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . Nueva York: Springer. pp. 185–212 . arXiv : 0912.3522 . ISBN  978-1-4419-9568-1.
  33. ↑ "Algoritmo de descenso en espejo" .
  34. 1 2 Bubeck, Sébastien (2015). "Optimización convexa: algoritmos y complejidad". arXiv : 1405.4980 [ math.OC ].

Lecturas adicionales

  • Boyd, Stephen ; Vandenberghe, Lieven (2004). «Minimización sin restricciones» (PDF) . Optimización 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. pp. 131–160 . ISBN  978-1-118-27901-4.
  • Himmelblau, David M. (1972). «Procedimientos de minimización sin restricciones mediante derivadas». Programación no lineal aplicada . Nueva York: McGraw-Hill. págs. 63-132 . ISBN  0-07-028921-2.
  • Uso del descenso de gradiente en C++, Boost, Ublas para regresión lineal
  • Una serie de videos de la Khan Academy analiza el ascenso gradual.
  • Enseñanza en línea del descenso de gradiente en el contexto de las redes neuronales profundas
  • Archivado en Ghostarchivey la Wayback Machine: "Descenso de gradiente: cómo aprenden las redes neuronales" . 3Blue1Brown . 16 de octubre de 2017 – vía YouTube .
  • Garrigos, Guillaume; Gower, Robert M. (2023). "Manual de teoremas de convergencia para métodos de gradiente (estocásticos)". arXiv : 2301.11235 [ math.OC ].