Gradient nedstigning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 17. juli 2021; verifikation kræver 1 redigering .

Gradient descent, gradient descent-metoden er en numerisk metode til at finde et lokalt minimum eller maksimum for en funktion ved at bevæge sig langs en gradient , en af de vigtigste numeriske metoder til moderne optimering.

Det bruges aktivt i beregningsmatematik ikke kun til den direkte løsning af optimerings- (minimerings-) problemer, men også til problemer, der kan omskrives i optimeringssproget (løsning af ikke-lineære ligninger, søgning efter ligevægte, inverse problemer osv.). Gradient descent-metoden kan bruges til optimeringsproblemer i uendelig-dimensionelle rum, for eksempel til den numeriske løsning af optimale kontrolproblemer.

Særlig stor interesse for gradientmetoder i de senere år skyldes, at gradientnedstigninger og deres stokastiske/randomiserede varianter ligger til grund for næsten alle moderne læringsalgoritmer udviklet inden for dataanalyse.

Beskrivelse

Lad den objektive funktion se ud som:

F({\vec {x}}):\;\mathbb {X} \to \mathbb {R}

Og optimeringsproblemet er givet som følger:

F({\vec {x}})\to \min _({\vec {x}}\in \mathbb {X}} }

I det tilfælde, hvor det er nødvendigt at finde det maksimale, i stedet for at bruge $F({\vec {x)))$ $-F({\vec {x)))$

Hovedideen med metoden er at gå i retning af den stejleste nedstigning, og denne retning er givet af anti -gradienten : $-\nabla F$

{\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)

hvor angiver gradientens nedstigningshastighed og kan vælges $\lambda ^{[j]}$

konstant (i dette tilfælde kan metoden divergere);
aftagende under gradientnedstigning;
garanterer den hurtigste nedstigning:
1. For at finde minimum, får vi $F\left({\vec {x}}\right)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left({\vec {x}}^{[j]}\right)\ ret)$
2. For at finde det maksimale, får vi $F\left({\vec {x}}\right)$ $\lambda ^{[j]}=\mathrm {argmax} _{\lambda }F\left({\vec {x}}^{[j+1]}\right)=\mathrm {argmax} _{\lambda }\,F\left({\vec {x}}^{[j]}+\lambda \nabla F\left({\vec {x}}^{[j]}\right)\ ret)$

Algoritme

Indstil den indledende tilnærmelse og beregningsnøjagtighed ${\vec {x}}^{0},\varepsilon$
Tæl hvor ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left( {\vec {x}}^{[j]}\right)\right)$
Tjek stoptilstanden:
- Hvis , eller (vælg en af betingelserne), så gå til trin 2. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\varepsilon$ $\left|F\left({\vec {x}}^{[j+1]}\right)-F\left({\vec {x}}^{[j]}\right)\ højre|>\varepsilon$ $\left\|\nabla F\left({\vec {x}}^{[j+1]}\right)\right\|>\varepsilon$ $j=j+1$
- Ellers stop. ${\vec {x}}={\vec {x}}^{[j+1]}$

Kantorovich-relationen

For en kvadratisk funktion af formen konvergerer den stejleste gradientsøgningsmetode fra et hvilket som helst udgangspunkt med hastigheden af en geometrisk progression (lineært) med en nævner, der ikke overstiger . I dette tilfælde er følgende estimater gyldige: ${\frac {x^{T}\Gamma x}{2}}+c^{T}x,\Gamma ^{T}=\Gamma$ $x_{0}$ $q$

\eksisterer a=a(x_{0}),T>0:0\leq a\leq q={\frac {\left(\lambda _{min}/\lambda _{max}-1\right)^ {2}}{\left(\lambda _{min}/\lambda _{max}+1\right)^{2}}}

f(x_{k})-f(x^{*})\leq a^{k}(f(x_{0})-f(x^{*}))

\|x_{k}-x^{*}\|\leq Ta^{k/2}\|x_{0}-x^{*}\|

hvor og er de minimale og maksimale egenværdier af matrixen af anden afledede . $\lambda _{min}$ $\lambda _{max}$ $\nabla ^{2}f(x)=\Gamma$

Da funktionen således på en lille måde er tæt på dens kvadratiske tilnærmelse, afhænger konvergenshastigheden i nærheden af minimumspunktet af forholdet mellem egenværdierne. Jo større dette forhold er, jo dårligere er konvergensen af metoden.

Eksempel

Lad os anvende gradientmetoden på funktionen . Derefter vil successive tilnærmelser se sådan ud: $F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos (2x+1-e^{y})$

Dette er et typisk eksempel på en kløftfunktion. Gradientmetoden "hopper" fra en skråning af kløften til en anden og tilbage, nogle gange næsten uden at bevæge sig i den rigtige retning, hvilket betydeligt bremser konvergensen. Et andet eksempel på en testbrøndfunktion er Rosenbrock-funktionen .

Forbedringer, ændringer

For at minimere funktionen i retning af gradienten, bruges endimensionelle optimeringsmetoder , såsom det gyldne snit metoden . Du kan også søge ikke efter det bedste punkt i retningen af gradienten, men efter noget bedre end det nuværende.

Gradient descent-metoden er den nemmeste at implementere af alle lokale optimeringsmetoder. Den har ret svage konvergensbetingelser, men konvergenshastigheden er ret lille (lineær). Gradientmetodetrinnet bruges ofte som en del af andre optimeringsmetoder, såsom Fletcher-Reeves-metoden .

Gradientnedstigningsmetoden viser sig at være meget langsom, når man bevæger sig langs en kløft, og efterhånden som antallet af objektive funktionsvariable stiger, bliver denne opførsel af metoden typisk. For at bekæmpe dette fænomen bruges ravinemetoden , hvis essens er meget enkel. Efter at have lavet to trin med gradientnedstigning og efter at have modtaget tre punkter, skal det tredje trin tages i retning af vektoren, der forbinder det første og tredje punkt langs bunden af kløften.

For funktioner tæt på kvadratisk er den konjugerede gradientmetode effektiv .

Applikationer i kunstige neurale netværk

Gradient-nedstigningsmetoden med en vis modifikation er meget brugt til at træne perceptronen og er kendt i teorien om kunstige neurale netværk som backpropagation-metoden . Når man træner et neuralt netværk af perceptrontypen, er det nødvendigt at ændre netværkets vægtkoefficienter på en sådan måde, at gennemsnitsfejlen ved udgangen af det neurale netværk minimeres, når en sekvens af træningsinputdata føres til inputtet. . Formelt, for kun at tage et trin i henhold til gradient descent-metoden (foretag kun én ændring i netværksparametrene), er det nødvendigt at sekventielt føre hele sættet af træningsdata til netværksinputtet, beregne fejlen for hver træningsdata objekt og beregne den nødvendige korrektion af netværkskoefficienterne (men gør ikke denne korrektion), og efter at have indsendt alle data, beregne summen i korrektionen af hver netværkskoefficient (summen af gradienter) og korrigere koefficienterne "med ét trin" . Det er klart, at med et stort sæt træningsdata vil algoritmen arbejde ekstremt langsomt, derfor justeres netværkskoefficienterne i praksis ofte efter hvert træningselement, hvor gradientværdien tilnærmes ved gradienten af omkostningsfunktionen beregnet på kun én træningselement. Denne metode kaldes stokastisk gradientnedstigning eller operationel gradientnedstigning . Stokastisk gradientnedstigning er en form for stokastisk tilnærmelse. Teorien om stokastiske tilnærmelser giver betingelser for konvergensen af den stokastiske gradientnedstigningsmetode.

Litteratur

Polyak B. T. Introduktion til optimering. - M . : Videnskab. Hovedudgave af fysisk og matematisk litteratur, 1983. - 384 s.
Nesterov Yu. E. Metoder til konveks optimering . - M. : MTSNMO Publishing House, 2010. - 281 s.
Gasnikov AV Moderne numeriske metoder til optimering. The Universal Gradient Descent Method: En studievejledning . - M. : MIPT, 2018. - 291 s. - ISBN 978-5-7417-0667-1 .
Akulich IL Matematisk programmering i eksempler og problemer. - M . : Højere skole, 1986. - S. 298-310.
Gill F., Murray W., Wright M. Praktisk optimering = praktisk optimering. — M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Matematiske grundlag for kybernetik. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmer til løsning af ikke-lineære programmeringsproblemer. - M .: MEPhI, 1982.
Maksimov Yu. A. Lineære og diskrete programmeringsalgoritmer. — M .: MEPhI, 1980.
Korn G., Korn T. Håndbog i matematik for videnskabsmænd og ingeniører. - M . : Nauka, 1970. - S. 575-576.
Gorodetsky S. Yu., Grishagin VA Ikke-lineær programmering og multi-ekstrem optimering. - Nizhny Novgorod: Forlag for Nizhny Novgorod Universitet, 2007. - S. 357-363.

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering