Gradientnedstigning

Gradientnedstigning i 2D

Gradientnedstigning är en metod för obegränsad matematisk optimering. Det är en första ordningens iterativ algoritm för att minimera en differentierbar multivariatfunktion.

Idén är att ta upprepade steg i motsatt riktning av gradienten (eller en approximativ gradient) av funktionen vid den aktuella punkten, eftersom detta är riktningen för den brantaste nedstigningen. Omvänt, att ta steg i gradientens riktning leder till en bana som maximerar funktionen; proceduren är då känd som gradient ascent.

Det är särskilt användbart inom maskininlärning för att minimera kostnads- eller förlustfunktionen. Gradientnedstigning ska inte förväxlas med lokala sökalgoritmer, även om båda är iterativa metoder för optimering.

Gradientnedstigning tillskrivs vanligtvis Augustin-Louis Cauchy, som först föreslog den 1847. Jacques Hadamard föreslog oberoende en liknande metod 1907. Dess konvergens-egenskaper för icke-linjära optimeringsproblem studerades först av Haskell Curry 1944, och metoden blev alltmer studerad och använd under de följande årtiondena.

En enkel utvidgning av gradientnedstigning, stokastisk gradientnedstigning, fungerar som den mest grundläggande algoritmen för att träna de flesta djupa nätverk idag.

Beskrivning

Illustration av gradientnedstigning på en serie av nivåmängder

Gradientnedstigning baseras på observationen att om en flerdimensionell funktion $F(\mathbf {x} )$ är definierad och differentierbar i en omgivning av en punkt $\mathbf {a}$, så minskar $F(\mathbf {x} )$ snabbast om man går från $\mathbf {a}$ i riktning mot den negativa gradienten av $F$ vid $\mathbf {a} ,-\nabla F(\mathbf {a} )$. Det följer att, om

$\mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})$

för en tillräckligt liten steglängd eller inlärningshastighet $\gamma \in \mathbb {R} _{+}$, då gäller att $F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )$. Med andra ord subtraheras termen $\gamma \nabla F(\mathbf {a} )$ från $\mathbf {a}$ eftersom vi vill röra oss mot gradienten, mot det lokala minimumet. Med denna observation i åtanke börjar man med en gissning $\mathbf {x} _{0}$ för ett lokalt minimum av $F$, och betraktar följden $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots$ så att

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

Vi har en monoton följd

$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,$

så förhoppningsvis konvergerar följden $(\mathbf {x} _{n})$ till det önskade lokala minimumet. Notera att värdet på steglängden $\gamma$ får ändras vid varje iteration.

Det är möjligt att garantera konvergens till ett lokalt minimum under vissa antaganden om funktionen $F$ (till exempel, att $F$ är konvex och att $\nabla F$ har Lipschitz-kontinuitet) och med särskilda val av $\gamma$. Dessa inkluderar följden

$\gamma _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{T}\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}}}$

som i Barzilai-Borwein-metoden, eller en följd $\gamma _{n}$ som uppfyller Wolfe-villkoren (som kan hittas genom linjesökning). När funktionen $F$ är konvex, är alla lokala minimum också globala minimum, så i detta fall kan gradientnedstigning konvergera till den globala lösningen.

Denna process illustreras i den angränsande bilden. Här antas $F$ vara definierad på planet, och att dess graf har formen av en skål. De blå kurvorna är konturlinjerna, det vill säga de områden där värdet på $F$ är konstant. En röd pil som utgår från en punkt visar riktningen för den negativa gradienten vid den punkten. Notera att den (negativa) gradienten vid en punkt är ortogonal mot konturlinjen som passerar genom den punkten. Vi ser att gradientnedstigningen leder oss till botten av skålen, det vill säga till punkten där funktionen $F$ har sitt minimum.

En analogi för att förstå gradientnedstigning

Dimma i bergen

Den grundläggande intuitionen bakom gradientnedstigning kan illustreras med ett hypotetiskt scenario. Personer är fast i bergen och försöker ta sig ner (dvs. de försöker hitta det globala minimumet). Det är tät dimma, vilket gör att sikten är extremt begränsad. Därför är vägen ner från berget inte synlig, och de måste använda lokal information för att hitta minimumet. De kan använda gradientnedstigningsmetoden, som innebär att de tittar på brantheten av sluttningen vid deras nuvarande position och sedan fortsätter i riktningen med den brantaste nedgången (dvs. nedförsbacke). Om de istället försökte hitta toppen av berget (dvs. maximumet), skulle de fortsätta i riktningen med den brantaste uppgången (dvs. uppförsbacke). Genom att använda denna metod skulle de så småningom hitta vägen ner från berget eller eventuellt fastna i någon hålighet (dvs. lokalt minimum eller sadelpunkt), som en bergssjö. Antag dock också att sluttningens branthet inte är omedelbart uppenbar vid enkel observation, utan att det kräver ett sofistikerat instrument för att mäta, vilket personerna råkar ha tillgängligt just nu. Det tar en hel del tid att mäta sluttningens branthet med instrumentet, så de bör minimera användningen av instrumentet om de vill komma ner från berget före solnedgången. Svårigheten ligger då i att välja hur ofta de ska mäta sluttningens branthet för att inte hamna fel.

I denna analogi representerar personerna algoritmen, och vägen de tar ner från berget representerar följden av parameterinställningar som algoritmen kommer att utforska. Sluttningens branthet representerar lutningen av funktionen vid den punkten. Instrumentet som används för att mäta brantheten är differentiation. Riktningen de väljer att färdas i stämmer överens med gradienten av funktionen vid den punkten. Den tid de färdas innan de tar en ny mätning är steglängden. Om de skulle råka kliva över ett stup i dimman, skulle de ha optimerat sin nedstigningsväg.

Att välja steglängd och nedstigningsriktning

Eftersom en steglängd $\gamma$ som är för liten skulle sakta ner konvergensen, och en $\gamma$ som är för stor skulle leda till att man skjuter förbi och får divergens, är det en viktig praktisk fråga att hitta en bra inställning av $\gamma$. Philip Wolfe förespråkade också användningen av "smarta val av [nedstignings-]riktningen" i praktiken. Även om det kan verka kontraintuitivt att använda en riktning som avviker från den brantaste nedstigningsriktningen, är tanken att den mindre lutningen kan kompenseras genom att den upprätthålls över en mycket längre sträcka.

För att resonera om detta matematiskt, överväg en riktning $\mathbf {p} _{n}$ och steglängden $\gamma _{n}$, och överväg den mer allmänna uppdateringen:

$\mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma _{n}\,\mathbf {p} _{n}$.

Att hitta bra inställningar för $\mathbf {p} _{n}$ och $\gamma _{n}$ kräver eftertanke. För det första vill vi att uppdateringsriktningen ska peka nedåt. Matematiskt sett, om $\theta _{n}$ betecknar vinkeln mellan $-\nabla F(\mathbf {a_{n}} )$ och $\mathbf {p} _{n}$, krävs det att $\cos \theta _{n}>0.$ För att säga mer behöver vi mer information om den objektiva funktionen som vi optimerar. Under det ganska svaga antagandet att $F$ är kontinuerligt deriverbar, kan vi bevisa att: Mall:NumBlk

Denna olikhet implicerar att hur mycket vi säkert kan säga att funktionen $F$ minskar beror på en avvägning mellan de två termerna inom klamrarna. Den första termen mäter vinkeln mellan nedstigningsriktningen och den negativa gradienten. Den andra termen mäter hur snabbt gradienten ändras längs nedstigningsriktningen.

I princip skulle olikhet (Mall:EquationNote) kunna optimeras över $\mathbf {p} _{n}$ och $\gamma _{n}$ för att välja en optimal steglängd och riktning. Problemet är att utvärderingen av den andra termen inom klamrarna kräver att man utvärderar $\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})$, och extra gradientutvärderingar är generellt sett dyra och oönskade. Några sätt att kringgå detta problem är:

• Avstå från fördelarna med en smart nedstigningsriktning genom att sätta $\mathbf {p} _{n}=\nabla F(\mathbf {a_{n}} )$, och använda line search för att hitta en lämplig steglängd $\gamma _{n}$, såsom en som uppfyller Wolfe conditions. Ett mer ekonomiskt sätt att välja inlärningshastigheter är backtracking line search, en metod som har både goda teoretiska garantier och experimentella resultat. Notera att man inte behöver välja $\mathbf {p} _{n}$ som gradienten; vilken riktning som helst som har positiv skalärprodukt med gradienten kommer att leda till en minskning av funktionsvärdet (för ett tillräckligt litet värde av $\gamma _{n}$).

• Om vi antar att $F$ är två gånger deriverbar, kan vi använda dess Hessian $\nabla ^{2}F$ för att uppskatta $|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})|_{2}\approx |t\gamma _{n}\nabla ^{2}F(\mathbf {a} _{n})\mathbf {p} _{n}|.$ Därefter kan vi välja $\mathbf {p} _{n}$ och $\gamma _{n}$ genom att optimera olikhet (Mall:EquationNote).

• Om vi antar att $\nabla F$ är Lipschitz-kontinuerlig, kan vi använda dess Lipschitz-konstant $L$ för att begränsa $|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})|_{2}\leq Lt\gamma _{n}|\mathbf {p} _{n}|.$ Därefter kan vi välja $\mathbf {p} _{n}$ och $\gamma _{n}$ genom att optimera olikhet (Mall:EquationNote).

• Bygg en egen modell av $\max _{t\in [0,1]}{\frac {|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})|_{2}}{|\nabla F(\mathbf {a} _{n})|_{2}}}$ för $F$. Därefter kan vi välja $\mathbf {p} _{n}$ och $\gamma _{n}$ genom att optimera olikhet (Mall:EquationNote).

• Under starkare antaganden om funktionen $F$, såsom konvexitet, kan mer avancerade tekniker vara möjliga.

Vanligtvis kan konvergens till ett lokalt minimum garanteras genom att följa ett av recepten ovan. När funktionen $F$ är konvex är alla lokala minima även globala minima, så i detta fall kan gradientnedstigning konvergera till den globala lösningen.

Lösning av ett linjärt system

Den brantaste nedstigningsalgoritmen tillämpad på Wienerfilter

Gradientnedstigning kan användas för att lösa ett system av linjära ekvationer:

$A\mathbf {x} -\mathbf {b} =0$

som omformuleras som ett kvadratiskt minimiseringsproblem. Om systemmatrisen $A$ är reellt symmetrisk och positivt definit, definieras en objektiv funktion som den kvadratiska funktionen, där målet är att minimera

$F(\mathbf {x} )=\mathbf {x} ^{T}A\mathbf {x} -2\mathbf {x} ^{T}\mathbf {b} ,$

så att

$\nabla F(\mathbf {x} )=2(A\mathbf {x} -\mathbf {b} ).$

För en allmän reell matris $A$ definieras linjär minsta kvadratmetoden som

$F(\mathbf {x} )=\left\|A\mathbf {x} -\mathbf {b} \right\|^{2}.$

I den traditionella linjära minsta kvadratmetoden för reella $A$ och $\mathbf {b}$ används euklidisk norm, och i detta fall gäller

$\nabla F(\mathbf {x} )=2A^{T}(A\mathbf {x} -\mathbf {b} ).$

Linjär sökning för att minimera, och hitta den lokalt optimala steglängden $\gamma$ vid varje iteration, kan utföras analytiskt för kvadratiska funktioner, och explicita formler för den lokalt optimala $\gamma$ är kända.

Till exempel, för en reell symmetrisk och positivt definit matris $A$, kan en enkel algoritm vara som följer:

${\begin{aligned}&{\text{upprepa i loopen:}}\\&\qquad \mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\text{om }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ är tillräckligt liten, avsluta loopen}}\\&{\text{slut på upprepa-loop}}\\&{\text{returnera }}\mathbf {x} {\text{ som resultat}}\end{aligned}}$

För att undvika multiplikation med $A$ två gånger per iteration, noterar vi att $\mathbf {x} :=\mathbf {x} +\gamma \mathbf {r}$ implicerar $\mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar}$, vilket ger den traditionella algoritmen:

${\begin{aligned}&\mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&{\text{upprepa i loopen:}}\\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\text{om }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ är tillräckligt liten, avsluta loopen}}\\&\qquad \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} \\&{\text{slut på upprepa-loop}}\\&{\text{returnera }}\mathbf {x} {\text{ som resultat}}\end{aligned}}$

Metoden används sällan för att lösa linjära ekvationer, med konjugatgradientmetoden som ett av de mest populära alternativen. Antalet gradientnedstigningsiterationer är vanligtvis proportionellt mot det spektrala konditionstalet $\kappa (A)$ för systemmatrisen $A$ (förhållandet mellan de största och minsta egenvärdena för $A^{T}A$), medan konvergensen för konjugatgradientmetoden typiskt bestäms av en kvadratrot av konditionstalet, vilket innebär att den är mycket snabbare. Båda metoderna kan dra nytta av förkonditionering, där gradientnedstigning kan kräva färre antaganden om förkonditioneringen.