alt=Un punto percorre unha superficie en pasos sucesivos, con frechas que indican o gradiente e a dirección oposta.|miniatura|351x351px|O descenso do gradiente reduce iterativamente unha función: en cada punto calcula o gradiente e dá un paso na dirección contraria. A traxectoria representada foi calculada co algoritmo, non debuxada á man. O descenso do gradiente é unha familia de métodos iterativos de optimización matemática de primeira orde. Serve para procurar valores das variables que reduzan unha función obxectivo diferenciable. Partindo dun punto inicial, calcula o gradiente (o vector das derivadas parciais) e desprázase na dirección oposta. O gradiente sinala o maior crecemento local coa xeometría euclidiana. O seu negativo proporciona, xa que logo, o descenso local máis pronunciado. A lonxitude de cada desprazamento está gobernada polo tamaño do paso, chamado habitualmente taxa de aprendizaxe en aprendizaxe automática.
Na súa forma básica, para minimizar unha función , a sucesión de aproximacións é onde é o punto actual, o gradiente e o tamaño do paso. Trátase dun procedemento local: a información usada en cada iteración describe a función arredor do punto actual, non toda a súa paisaxe. A converxencia e o seu destino dependen da regularidade e da convexidade da función, da elección dos pasos e do punto inicial. En problemas convexos suaves poden darse garantías globais; nos non convexos, como moitos dos que aparecen ao adestrar unha rede neuronal artificial, o método pode achegarse a un mínimo local, a un punto de sela ou a outro punto estacionario, e non garante en xeral o mínimo global.
O método pertence á optimización numérica moito antes do desenvolvemento da aprendizaxe automática moderna. A súa formulación histórica remóntase cando menos ao traballo de Augustin-Louis Cauchy de 1847. Na actualidade é tanto unha ferramenta por dereito propio como a base conceptual de métodos estocásticos, con momento e adaptativos. A súa importancia práctica débese a que só require valores da función e das súas primeiras derivadas, unha vantaxe cando hai millóns ou milleiros de millóns de parámetros.
Problema de minimización O problema sen restricións que motiva o método escríbese O vector contén as variables de decisión e é a función obxectivo; minimizar significa atopar un punto onde o seu valor sexa tan pequeno como permitan as condicións do problema. Un punto é un mínimo global se para todo do dominio. É un mínimo local se existe unha veciñanza na que a mesma desigualdade se cumpre. Todo mínimo global é local, mais non á inversa.
Se é diferenciable e un mínimo local está no interior do dominio, necesariamente . Un punto que satisfai esa igualdade chámase punto estacionario ou crítico. A condición é necesaria, non suficiente: tamén a cumpren máximos locais e puntos de sela. Por exemplo, ten derivada nula en cero, mais cero non é extremo; ten en un punto de sela.
Da derivada ao gradiente Nunha dimensión, a derivada describe a taxa de cambio local. Se , un pequeno aumento de tende a aumentar ; se , tende a diminuíla. Esta lectura é local e pode deixar de ser válida tras un desprazamento grande.
En varias dimensións hai unha taxa de cambio para cada coordenada. Se existen as derivadas parciais, o gradiente é o vector columna Cada compoñente mide a variación ao modificar unha coordenada e manter momentaneamente as demais fixas. Para unha dirección unitaria , a derivada direccional dunha función diferenciable é O produto escalar incorpora simultaneamente todas as variacións coordenadas. miniatura|350x350px|O gradiente é perpendicular á curva de nivel no punto e apunta cara ao incremento local máis rápido; o seu negativo apunta cara ao descenso local máis rápido.
Por que descende o gradiente negativo Para calquera de norma euclidiana unitaria, a desigualdade de Cauchy–Schwarz dá Se o gradiente non é nulo, o límite inferior acádase con Así, entre as direccións unitarias, o gradiente negativo minimiza a taxa instantánea de cambio. Isto xustifica chamalo dirección de máximo descenso na norma euclidiana. É unha afirmación infinitesimal: non asegura que unha recta prolongada nesa dirección pase polo mínimo global nin que un paso arbitrariamente longo reduza a función.
A expansión de Taylor de primeira orde expresa a mesma idea: Ao escoller , con pequeno, o termo lineal é , negativo agás nun punto estacionario. O termo de orde superior explica por que o cualificativo «pequeno» importa.
Steepest descent e elección da norma En textos en inglés úsanse gradient descent e steepest descent ás veces como sinónimos, sobre todo no espazo euclidiano. Conceptualmente, o descenso máis pronunciado depende da medida de lonxitude. Para unha norma , a dirección resolve a minimización da aproximación lineal baixo ; a resposta relaciónase coa norma dual. Só coa norma e o produto escalar habitual coincide directamente con . Esta observación conecta o método co precondicionamento, o gradiente natural e os métodos de espello.
Algoritmo básico Unha iteración consta de avaliar a derivada no punto actual e construír o seguinte punto: Aquí conta as iteracións, é a aproximación actual, a información local de primeira orde e un escalar positivo. O carácter iterativo permite volver calcular a dirección despois de cada paso, pois a xeometría pode cambiar ao longo da traxectoria.escoller un punto inicial x₀ para k = 0, 1, 2, ... ata cumprir un criterio de parada: calcular gₖ = ∇f(xₖ) escoller un tamaño do paso αₖ > 0 actualizar xₖ₊₁ = xₖ − αₖ gₖ devolver a última aproximaciónO pseudocódigo oculta decisións relevantes: como obter o gradiente, como elixir o paso, que precisión numérica empregar e cando deter o cálculo.
Interpretación xeométrica As curvas de nivel reúnen os puntos co mesmo valor de . Nun punto regular dunha curva de nivel, toda dirección tanxente satisfai ; por iso o gradiente é normal á curva. Avanzar no seu oposto cruza localmente as curvas cara a niveis menores. A lonxitude do gradiente tamén ten significado: é a máxima magnitude da derivada direccional unitaria, de xeito que unha norma pequena indica pouca variación de primeira orde en todas as direccións euclidianas.
Esta xeometría depende das coordenadas. Se unha variable se expresa en metros e outra en milímetros, o mesmo fenómeno físico pode producir compoñentes do gradiente con escalas moi distintas. O método básico non é invariante ante cambios lineais xerais de coordenadas. A estandarización de variables, un precondicionador ou unha métrica adaptada poden evitar que unha mera elección de unidades domine a traxectoria.
O paso tamén resolve un pequeno modelo regularizado: O primeiro termo variable predí o beneficio lineal e o termo cuadrático penaliza afastarse demasiado do punto onde esa predición é fiable. Esta lectura conecta o tamaño do paso coa confianza no modelo local.
Exemplo cuadrático Un modelo central na análise é onde é simétrica. O gradiente é e o Hessiano, a matriz de segundas derivadas, é . Se é definida positiva, a función é fortemente convexa, posúe un único mínimo e a iteración toma a forma Os autovalores de permiten ver exactamente a estabilidade: cun paso constante, a converxencia require . O paso óptimo dentro desta familia, para o peor caso, é .
Tamaño do paso O tamaño do paso determina canto se confía na aproximación local. Un paso moi pequeno adoita producir descenso estable pero progreso lento. Un paso excesivo pode cruzar repetidamente un val (overshooting), oscilar ou diverxer. Un valor intermedio pode reducir axiña o obxectivo sen abandonar a rexión onde o gradiente é informativo. alt=Tres puntos parten do mesmo lugar na mesma curva; un avanza lentamente, outro converge e o terceiro oscila afastándose.|miniatura|350x350px|Efecto do tamaño do paso na mesma función e desde o mesmo punto inicial: paso pequeno, adecuado e excesivo. As posicións son iteracións calculadas do algoritmo. En aprendizaxe automática, ou denomínase taxa de aprendizaxe (learning rate), non é un concepto matemático distinto. Pode ser constante, diminuír segundo un calendario (schedule ou decay), sufrir reinicios ou adaptarse por coordenadas. Unha taxa constante pode manter ruído útil nun método estocástico pero impedir converxencia exacta, taxas decrecentes poden permitir estabilización, a cambio de avances tardíos menores.
Busca lineal Dada unha dirección de descenso , a busca lineal considera . A busca exacta minimiza para ; mesmo cando existe, resolver ese subproblema con gran precisión pode custar máis que o beneficio obtido. As buscas inexactas procuran un paso aceptable cun número moderado de avaliacións.
A condición de decrecemento suficiente ou de Armijo é O lado dereito esixe unha fracción do descenso previsto polo modelo lineal. Un procedemento habitual, backtracking, comeza cun paso candidato e redúceo xeometricamente ata cumprir a desigualdade. Armijo formulou en 1966 unha regra deste tipo para funcións con primeiras derivadas Lipschitz.
As condicións de Wolfe engaden unha condición de curvatura, na forma débil que evita aceptar pasos tan curtos que a pendente apenas cambie. As condicións fortes substitúen esa desigualdade por unha cota do valor absoluto. Son especialmente útiles na teoría de métodos quasi-Newton; non implican que o paso sexa o minimizador exacto da recta.
Unha busca lineal supón que xa se escolleu unha dirección con . Armijo e Wolfe non reparan unha dirección que non sexa de descenso. Tampouco toda aplicación necesita busca lineal: en aprendizaxe a avaliación repetida dunha perda sobre grandes lotes pode ser prohibitiva, e o ruído fai menos informativa a comparación exacta entre candidatos. Nese contexto predominan taxas prefixadas ou adaptativas; en optimización determinista de precisión, as buscas proporcionan unha salvagarda valiosa.
Evolución continua O límite ideal de pasos cada vez máis pequenos leva ao fluxo de gradiente Ao longo dunha solución diferenciable, Polo tanto, o obxectivo non aumenta no tempo continuo. O descenso básico pode verse como a discretización de Euler explícita desta ecuación diferencial. Esta interpretación aclara tanto o signo da actualización como a inestabilidade dos pasos grandes: unha discretización explícita pode diverxer aínda cando o sistema continuo sexa estable. Non obstante, o algoritmo discreto ten propiedades propias e non é simplemente unha simulación física.
Interpretación mediante un modelo local Outra maneira de obter a actualización consiste en substituír temporalmente a función por un modelo local fácil de minimizar. A aproximación lineal soa, non ten normalmente un mínimo finito: se a dirección pode crecer sen límite, o termo lineal continúa diminuíndo. Engádese por iso unha penalización cuadrática que desaconsella afastarse demasiado do punto actual: O mínimo deste modelo satisfai e é precisamente . Así, o tamaño do paso tamén pode interpretarse como a confianza depositada no modelo lineal: un pequeno penaliza moito o afastamento, mentres un grande permite unha modificación máis ambiciosa.
Esta formulación separa dúas ideas. O termo lineal representa a información de primeira orde dispoñible; o termo cuadrático escolle a xeometría coa que se mide o desprazamento. Se se substitúe a norma euclidiana por , con definida positiva, o minimizador usa . O precondicionamento, algúns métodos adaptativos e os métodos quasi-Newton poden entenderse como eleccións diferentes desa xeometría local, aínda que a maneira de construír e as súas garantías son distintas.