Lutning nedstigning

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 17 juli 2021; verifiering kräver 1 redigering .

Gradient descent, gradient descent-metoden är en numerisk metod för att hitta ett lokalt minimum eller maximum för en funktion genom att flytta längs en gradient , en av de viktigaste numeriska metoderna för modern optimering.

Det används aktivt i beräkningsmatematik, inte bara för direkt lösning av optimeringsproblem (minimering), utan också för problem som kan skrivas om i optimeringsspråket (lösning av olinjära ekvationer, sökning efter jämvikter, inversa problem, etc.). Gradient descent-metoden kan användas för optimeringsproblem i oändligt dimensionella rum, till exempel för numerisk lösning av optimala kontrollproblem.

Särskilt stort intresse för gradientmetoder de senaste åren beror på att gradientnedgångar och deras stokastiska/randomiserade varianter ligger till grund för nästan alla moderna inlärningsalgoritmer som utvecklats inom dataanalys.

Beskrivning

Låt objektivfunktionen se ut så här:

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

Och optimeringsproblemet ges som följer:

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

I fallet när det krävs för att hitta det maximala, istället för att använda $F({\vec {x)))$ $-F({\vec {x)))$

Huvudidén med metoden är att gå i riktning mot den brantaste nedstigningen, och denna riktning ges av antigradienten : $-\nabla F$

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

där anger gradientens nedstigningshastighet och kan väljas $\lambda ^{[j]}$

konstant (i detta fall kan metoden divergera);
minskar under gradientnedstigning;
garanterar den snabbaste nedstigningen:
1. För att hitta 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)\ höger)$
2. För att hitta det maximala 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)\ höger)$

Algoritm

Ställ in initial approximation och beräkningsnoggrannhet ${\vec {x}}^{0},\varepsilon$
Räkna var ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\höger)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left( {\vec {x}}^{[j]}\right)\right)$
Kontrollera stopptillståndet:
- Om , eller (välj ett av villkoren), gå sedan till steg 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öger|>\varepsilon$ $\left\|\nabla F\left({\vec {x}}^{[j+1]}\right)\right\|>\varepsilon$ $j=j+1$
- Annars sluta. ${\vec {x}}={\vec {x}}^{[j+1]}$

Kantorovich-relationen

För en kvadratisk funktion av formen konvergerar den brantaste gradientsökningsmetoden från vilken utgångspunkt som helst i takt med en geometrisk progression (linjärt) med en nämnare som inte överstiger . I det här fallet är följande uppskattningar giltiga: ${\frac {x^{T}\Gamma x}{2}}+c^{T}x,\Gamma ^{T}=\Gamma$ $x_{0}$ $q$

\exists 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^{*}\|

där och är de minsta och maximala egenvärdena för matrisen av andraderivator . $\lambda _{min}$ $\lambda _{max}$ $\nabla ^{2}f(x)=\Gamma$

Eftersom funktionen på ett litet sätt är nära sin kvadratiska approximation, beror konvergenshastigheten, i närheten av minimipunkten, på förhållandet mellan egenvärdena. Ju större detta förhållande, desto sämre konvergens av metoden.

Exempel

Låt oss tillämpa gradientmetoden på funktionen . Sedan kommer successiva approximationer att se ut så här: $F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos (2x+1-e^{y})$

Detta är ett typiskt exempel på en ravinfunktion. Gradientmetoden "hoppar" från en sluttning av ravinen till en annan och tillbaka, ibland nästan utan att röra sig i rätt riktning, vilket avsevärt saktar ner konvergensen. Ett annat exempel på en testbrunnsfunktion är Rosenbrock-funktionen .

Förbättringar, ändringar

För att minimera funktionen i gradientens riktning används endimensionella optimeringsmetoder , såsom gyllene snittmetoden . Du kan också söka inte efter den bästa punkten i gradientens riktning, utan efter något bättre än den nuvarande.

Gradient descent-metoden är den enklaste att implementera av alla lokala optimeringsmetoder. Den har ganska svaga konvergensförhållanden, men konvergenshastigheten är ganska liten (linjär). Gradientmetodsteget används ofta som en del av andra optimeringsmetoder, som Fletcher-Reeves-metoden .

Gradientnedstigningsmetoden visar sig vara mycket långsam när man rör sig längs en ravin, och när antalet objektiva funktionsvariabler ökar blir detta beteende hos metoden typiskt. För att bekämpa detta fenomen används ravinmetoden , vars kärna är mycket enkel. Efter att ha gjort två steg av gradientnedstigning och efter att ha fått tre poäng, bör det tredje steget tas i riktning mot vektorn som förbinder de första och tredje punkterna, längs botten av ravinen.

För funktioner nära kvadratisk är den konjugerade gradientmetoden effektiv .

Tillämpningar i artificiella neurala nätverk

Gradient descentmetoden med viss modifiering används i stor utsträckning för att träna perceptronen och är känd i teorin om artificiella neurala nätverk som backpropagation-metoden . När man tränar ett neuralt nätverk av perceptrontyp krävs det att nätverkets viktkoefficienter ändras på ett sådant sätt att medelfelet vid utgången av det neurala nätverket minimeras när en sekvens av träningsinmatningsdata matas till ingången. . Formellt, för att bara ta ett steg enligt metoden för gradientnedstigning (gör endast en ändring i nätverksparametrarna), är det nödvändigt att sekventiellt mata hela uppsättningen träningsdata till nätverksingången, beräkna felet för varje träningsdata objekt och beräkna den nödvändiga korrigeringen av nätverkskoefficienterna (men gör inte denna korrigering), och efter att ha skickat in all data, beräkna summan i korrigeringen av varje nätverkskoefficient (summan av gradienter) och korrigera koefficienterna "med ett steg" . Uppenbarligen, med en stor uppsättning träningsdata kommer algoritmen att arbeta extremt långsamt, därför justeras nätverkskoefficienterna i praktiken ofta efter varje träningselement, där gradientvärdet approximeras av gradienten för kostnadsfunktionen beräknad på endast en träningsmoment. Denna metod kallas stokastisk gradientnedstigning eller operationell gradientnedstigning . Stokastisk gradientnedstigning är en form av stokastisk approximation. Teorin om stokastiska approximationer ger förutsättningar för konvergensen av den stokastiska gradientdescentmetoden.

Länkar

J. Mathews. Modul för brantaste nedstigning eller gradientmetod.
Metaforisk interaktiv demonstration av den snabbaste Pyu- metoden

Litteratur

Polyak B. T. Introduktion till optimering. - M . : Vetenskap. Huvudupplaga av fysisk och matematisk litteratur, 1983. - 384 sid.
Nesterov Yu. E. Metoder för konvex optimering . - M. : MTSNMO Publishing House, 2010. - 281 sid.
Gasnikov AV Moderna numeriska metoder för optimering. The Universal Gradient Descent Method: A Study Guide . - M. : MIPT, 2018. - 291 sid. - ISBN 978-5-7417-0667-1 .
Akulich IL Matematisk programmering i exempel och problem. - M . : Högre skola, 1986. - S. 298-310.
Gill F., Murray W., Wright M. Praktisk optimering = praktisk optimering. — M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Matematiska grunder för cybernetik. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmer för att lösa olinjära programmeringsproblem. — M .: MEPhI, 1982.
Maksimov Yu. A. Linjära och diskreta programmeringsalgoritmer. — M .: MEPhI, 1980.
Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.
Gorodetsky S. Yu., Grishagin VA Icke-linjär programmering och multiextremal optimering. - Nizhny Novgorod: Nizhny Novgorod Universitys förlag, 2007. - S. 357-363.

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering