Gradienttilasku

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17. heinäkuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Gradienttilasku, gradienttilaskumenetelmä on numeerinen menetelmä funktion paikallisen minimin tai maksimin löytämiseksi liikkumalla gradienttia pitkin , joka on yksi nykyaikaisen optimoinnin tärkeimmistä numeerisista menetelmistä.

Sitä käytetään aktiivisesti laskennallisessa matematiikassa paitsi optimointi- (minimointi)-ongelmien suorassa ratkaisussa, myös ongelmissa, jotka voidaan kirjoittaa uudelleen optimointikielellä (epälineaaristen yhtälöiden ratkaisu, tasapainojen etsiminen, käänteisongelmat jne.). Gradienttilaskumenetelmää voidaan käyttää äärettömän ulottuvuuden avaruuden optimointiongelmiin, esimerkiksi optimaalisten säätöongelmien numeeriseen ratkaisuun.

Erityisen suuri kiinnostus gradienttimenetelmiä kohtaan viime vuosina johtuu siitä, että gradienttilaskeutumiset ja niiden stokastiset/satunnaistetut variantit ovat lähes kaikkien nykyaikaisten data-analyysissä kehitettyjen oppimisalgoritmien taustalla.

Kuvaus

Olkoon tavoitefunktio näyttää tältä:

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

Ja optimointiongelma esitetään seuraavasti:

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

Siinä tapauksessa, että on löydettävä maksimi, käytön sijaan $F({\vec {x)))$ $-F({\vec {x)))$

Menetelmän pääideana on mennä jyrkimmän laskun suuntaan, ja tämän suunnan antaa antigradientti : $-\nabla F$

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

jossa määrittää gradientin laskeutumisnopeuden ja voidaan valita $\lambda ^{[j]}$

vakio (tässä tapauksessa menetelmä voi poiketa);
vähenee kaltevuuden laskun aikana;
takaa nopeimman laskeutumisen:
1. Löytääksemme minimin saamme $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]}\oikea)\ oikein)$
2. Löytääksemme maksimi, saamme $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]}\oikea)\ oikein)$

Algoritmi

Aseta alkuperäinen approksimaatio ja laskennan tarkkuus ${\vec {x}}^{0},\varepsilon$
Laske missä ${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\oikea)$ $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda \nabla F\left( {\vec {x}}^{[j]}\oikea)\oikea)$
Tarkista pysäytystila:
- Jos , tai (valitse jokin ehdoista), siirry sitten vaiheeseen 2. $\left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\varepsilon$ $\left|F\left({\vec {x}}^{[j+1]}\right)-F\left({\vec {x}}^{[j]}\oikea)\ oikea|>\varepsilon$ $\left\|\nabla F\left({\vec {x}}^{[j+1]}\right)\right\|>\varepsilon$ $j=j+1$
- Muuten lopeta. ${\vec {x}}={\vec {x}}^{[j+1]}$

Kantorovich-suhde

Muodon neliöfunktiolle jyrkin gradientin hakumenetelmä konvergoi mistä tahansa aloituspisteestä geometrisen etenemisen nopeudella (lineaarisesti), jonka nimittäjä ei ole suurempi kuin . Tässä tapauksessa seuraavat arviot ovat voimassa: ${\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^{*}\|

missä ja ovat toisten derivaattojen matriisin vähimmäis- ja enimmäisominaisarvot . $\lambda _{min}$ $\lambda _{max}$ $\nabla ^{2}f(x)=\Gamma$

Näin ollen, koska funktio on vähän lähellä sen neliöllistä approksimaatiota, konvergenssin nopeus minimipisteen läheisyydessä riippuu ominaisarvojen suhteesta. Mitä suurempi tämä suhde, sitä huonompi menetelmän konvergenssi.

Esimerkki

Sovelletaan gradienttimenetelmää funktioon . Sitten peräkkäiset approksimaatiot näyttävät tältä: $F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos (2x+1-e^{y})$

Tämä on tyypillinen esimerkki rotkofunktiosta. Gradienttimenetelmä "hyppää" rotkon rinteestä toiseen ja takaisin, joskus melkein liikkumatta oikeaan suuntaan, mikä hidastaa merkittävästi lähentymistä. Toinen esimerkki testikaivon funktiosta on Rosenbrock-funktio .

Parannuksia, muutoksia

Gradientin suunnan funktion minimoimiseksi käytetään yksiulotteisia optimointimenetelmiä , kuten kultaleikkausmenetelmää . Voit myös etsiä parasta pistettä gradientin suunnasta, vaan jotain nykyistä parempaa.

Gradienttilaskumenetelmä on kaikista paikallisista optimointimenetelmistä helpoin toteuttaa. Sillä on melko heikot konvergenssiolosuhteet, mutta konvergenssinopeus on melko pieni (lineaarinen). Gradienttimenetelmävaihetta käytetään usein osana muita optimointimenetelmiä, kuten Fletcher-Reeves-menetelmää .

Gradienttilaskeutumismenetelmä osoittautuu erittäin hitaksi rotkoa pitkin liikuttaessa, ja tavoitefunktiomuuttujien määrän kasvaessa menetelmän käyttäytyminen muuttuu tyypilliseksi. Tämän ilmiön torjumiseksi käytetään rotkomenetelmää , jonka olemus on hyvin yksinkertainen. Kun on tehty kaksi kaltevuuslaskuaskelta ja saatu kolme pistettä, kolmas askel tulee ottaa ensimmäisen ja kolmannen pisteen yhdistävän vektorin suuntaan rotkon pohjaa pitkin.

Lähes neliötason funktioille konjugaattigradienttimenetelmä on tehokas .

Sovellukset keinotekoisissa neuroverkoissa

Gradienttilaskeutumismenetelmää, jossa on joitain muutoksia, käytetään laajalti perceptronin kouluttamiseen ja se tunnetaan keinotekoisten hermoverkkojen teoriassa backpropagation -menetelmänä . Perceptron-tyyppistä hermoverkkoa opetettaessa on tarpeen muuttaa verkon painokertoimia siten, että keskimääräinen virhe hermoverkon lähdössä minimoidaan, kun sisäänmenoon syötetään opetussyötedatan sarja. . Muodollisesti, jotta voidaan ottaa vain yksi askel gradienttilaskeutumismenetelmän mukaan (tehdä vain yksi muutos verkkoparametreihin), on tarpeen syöttää peräkkäin koko harjoitustietojoukko verkkosyötteeseen, laskea virhe jokaiselle harjoitusdatalle vastustaa ja laskea tarvittava verkkokertoimien korjaus (mutta älä tee tätä korjausta), ja kun olet toimittanut kaikki tiedot, laske kunkin verkkokertoimen korjauksen summa (gradienttien summa) ja korjaa kertoimet "yhdellä askeleella" . On selvää, että suurella opetusdatajoukolla algoritmi toimii erittäin hitaasti, joten käytännössä verkkokertoimia säädetään usein jokaisen harjoituselementin jälkeen, jolloin gradientin arvo on likimääräinen vain yhdelle lasketun kustannusfunktion gradientilla. koulutuselementti. Tätä menetelmää kutsutaan stokastiseksi gradienttilaskuksi tai operatiiviseksi gradienttilaskuksi . Stokastinen gradientin laskeutuminen on stokastisen approksimoinnin muoto. Stokastisten approksimaatioiden teoria antaa edellytykset stokastisen gradientin laskeutumismenetelmän konvergenssille.

Linkit

J. Mathews. Jyrkimmän laskeutumisen tai gradienttimenetelmän moduuli.
Nopeimman Pyu -menetelmän metaforinen interaktiivinen esitys

Kirjallisuus

Polyak B. T. Johdatus optimointiin. - M . : Tiede. Fysikaalisen ja matemaattisen kirjallisuuden pääpainos, 1983. - 384 s.
Nesterov Yu. E. Konveksin optimoinnin menetelmät . - M. : MTSNMO Publishing House, 2010. - 281 s.
Gasnikov AV Nykyaikaiset numeeriset optimointimenetelmät. Universal Gradient Descent Method: A Study Guide . - M. : MIPT, 2018. - 291 s. - ISBN 978-5-7417-0667-1 .
Akulich IL Matemaattinen ohjelmointi esimerkeissä ja tehtävissä. - M . : Higher School, 1986. - S. 298-310.
Gill F., Murray W., Wright M. Käytännön optimointi = Practical Optimization. - M .: Mir, 1985.
Korshunov Yu. M., Korshunov Yu. M. Kybernetiikan matemaattiset perusteet. - M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmit epälineaaristen ohjelmointiongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Maksimov Yu. A. Lineaariset ja diskreetit ohjelmointialgoritmit. - M .: MEPhI, 1980.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.
Gorodetsky S. Yu., Grishagin VA Epälineaarinen ohjelmointi ja multi-extremal optimointi. - Nižni Novgorod: Nižni Novgorodin yliopiston kustantamo, 2007. - S. 357-363.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi