Coborâre a gradientului stocastic

Coborârea gradientului stocastic ( SGD ) este o metodă iterativă pentru optimizarea unei funcții obiective cu proprietăți de netezime adecvate (de exemplu, diferențiere sau subdiferențiabilitate ). Poate fi considerată ca o aproximare stocastică a optimizării coborârii gradientului , deoarece înlocuiește gradientul real calculat din setul de date complet cu o estimare calculată dintr-un subset de date selectat aleatoriu [1] . Acest lucru reduce resursele de calcul implicate și ajută la obținerea unor rate mai mari de iterație în schimbul unor rate de convergență mai mici [2] . Un efect deosebit de mare este obținut în aplicațiile legate de prelucrarea datelor mari .

Deși ideea de bază a aproximării stocastice se întoarce la algoritmul Robbins-Monroe din anii 1950 [3] , coborârea gradientului stocastic a devenit o tehnică importantă de optimizare în învățarea automată [1] .

Fundal

Atât estimarea statistică , cât și învățarea automată iau în considerare problema minimizării unei funcții obiective care are forma unei sume

Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w),

unde trebuie estimată minimizarea parametrilor . Fiecare termen sumă este de obicei asociat cu a- a observație din setul de date utilizat pentru antrenament. $w$ $Q(w)$ $Q_{i}$ $i$

În statistica clasică, problemele de minimizare a sumei apar în metoda celor mai mici pătrate și în metoda probabilității maxime (pentru observații independente). Clasa generală de estimatori care apar ca minimizarea sumelor se numește M-estimatori . Totuși, încă de la sfârșitul secolului al XX-lea, s-a observat că cerința minimizării chiar locale este prea restrictivă pentru unele probleme ale metodei de maximă probabilitate [4] . Prin urmare, teoreticienii statistici moderni iau în considerare adesea punctele staționare ale funcției de probabilitate (sau zerourile derivatei sale, funcția de scoring și alte metode de estimare a ecuațiilor ).

Problema minimizării sumei apare și la minimizarea riscului empiric . În acest caz, este valoarea funcției de pierdere din exemplul --lea și este riscul empiric. $Q_{i}(w)$ $i$ $Q(w)$

Când este utilizată pentru a minimiza funcția de mai sus, metoda de coborâre a gradientului standard (sau „loc”) efectuează următoarele iterații:

w:=w-\eta \nabla Q(w)=w-{\frac {\eta {n))\sum _{i=1}^{n}\nabla Q_{i}(w ),

unde este dimensiunea pasului, numită rata de învățare în învățarea automată. $\eta$

În multe cazuri, funcțiile sumabile au o formă simplă, care permite calcule cu costuri reduse pentru suma funcțiilor și gradientul sumei. De exemplu, în statistică, utilizarea familiilor exponențiale cu un parametru permite calculul economic al funcției și al gradientului.

Cu toate acestea, în alte cazuri, calcularea gradientului sumei poate necesita calcule scumpe de gradient pentru toate funcțiile sumabile. Pe un set mare de antrenament, în absența unor formule simple, calcularea sumelor gradienților devine foarte costisitoare, deoarece calcularea gradientului sumei necesită calcularea gradienților termenilor individuali ai sumei. Pentru a reduce cantitatea de calcul, coborârea gradientului stocastic selectează un subset de funcții sumabile la fiecare iterație a algoritmului. Această abordare este eficientă în special pentru problemele mari de învățare automată [5] .

Metoda iterativă

În coborârea gradientului stocastică ("online"), gradientul adevărat este aproximat de gradientul unui exemplu de antrenament $Q(w)$

w:=w-\eta \nabla Q_{i}(w).

Trecând prin setul de antrenament, algoritmul efectuează recalcularea de mai sus pentru fiecare exemplu de antrenament. Pot fi necesare mai multe treceri peste setul de date de antrenament pentru a obține convergența algoritmului. Înainte de fiecare nouă trecere, datele din set sunt amestecate pentru a elimina posibilitatea de a bucla algoritmul. Implementările tipice pot folosi rata de învățare adaptivă îmbunătăți convergența.

În pseudocod , coborârea gradientului stocastic poate fi reprezentată după cum urmează:

Alegeți un vector parametru inițial și o rată de învățare . $w$ $\eta$
Repetați până când se atinge un minim aproximativ:
- Amestecați aleatoriu exemplele din setul de antrenament.
- A împlini $i=1,2,...,n$
  - $\!w:=w-\eta \nabla Q_{i}(w).$

Un compromis între calcularea gradientului adevărat și a gradientului pentru un singur exemplu de antrenament poate fi calcularea gradientului pentru mai mult de un exemplu de antrenament, numit „mini-lot”, la fiecare pas. Acest lucru poate fi semnificativ mai bun decât coborârea gradientului stocastic „adevărat” descris, deoarece codul poate folosi biblioteci de forme vectoriale în loc de calcule separate la fiecare pas. De asemenea, poate duce la o convergență mai lină, deoarece gradientul calculat la fiecare pas este mediat pe mai multe exemple de antrenament.

Convergența coborârii gradientului stocastic a fost analizată folosind teoriile de minimizare convexă și aproximare stocastică . Într-o formă simplificată, rezultatul poate fi reprezentat după cum urmează: atunci când rata de învățare scade la o rată adecvată, având în vedere ipoteze relativ slabe, coborârea gradientului stocastic converge aproape sigur către minimul global dacă funcția obiectiv este convexă sau pseudoconvexă , în caz contrar metoda converge aproape sigur către minim local [6] [7] . De fapt, aceasta este o consecință a teoremei Robbins-Sigmund [8] . $\eta$

Exemplu

Să presupunem că vrem să aproximăm o linie printr-un set de antrenament cu multe observații și răspunsuri corespunzătoare folosind metoda celor mai mici pătrate . Funcția obiectivă pentru minimizare va fi ${\hat {y}}=\!w_{1}+w_{2}x$ $(x_{1},x_{2},\ldots,x_{n})$ $({\pălărie {y_{1}}}, {\pălărie {y_{2}}},\ldots ,{\pălărie {y_{n}}})$

Q(w)=\sum _{i=1}^{n}Q_{i}(w)=\sum _{i=1}^{n}\left({\hat {y_{i }}}-y_{i}\right)^{2}=\sum _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\ dreapta)^{2}.

Ultima linie din pseudocodul de mai sus pentru sarcină devine

{\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}:={\begin{bmatrix}w_{1}\\w_{2}\end{bmatrix}}- \eta {\begin{bmatrix}{\frac {\partial }{\partial w_{1}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\\ {\frac {\partial }{\partial w_{2}}}(w_{1}+w_{2}x_{i}-y_{i})^{2}\end{bmatrix}}={\begin {bmatrix}w_{1}\\w_{2}\end{bmatrix}}-\eta {\begin{bmatrix}2(w_{1}+w_{2}x_{i}-y_{i})\ \2x_{i}(w_{1}+w_{2}x_{i}-y_{i})\end{bmatrix}}.

Rețineți că în fiecare iterație (care se mai numește și reeșantionare), doar gradientul dintr-un punct este calculat în loc să se calculeze peste setul de toate eșantioanele. $x_i$

Diferența cheie față de coborârea gradientului standard (în lot) este că doar o parte a datelor din întregul set este utilizată la fiecare pas, iar această parte este aleasă aleatoriu la fiecare pas.

Aplicații notabile

Coborârea gradientului stocastic este un algoritm popular pentru antrenarea unei game largi de modele în învățarea automată , în special în mașinile vectoriale suport (liniare) , în regresia logistică (vezi de exemplu Vowpal Wabbit ) și în modelele probabilistice grafice [9] . Atunci când este combinat cu algoritmul de backpropagation , este algoritmul standard de facto pentru antrenarea rețelelor neuronale artificiale [10] . Aplicația sa a fost văzută și în comunitatea geofizică , în special pentru aplicațiile Full Waveform Inversion (FWI) [11] .

Coborârea gradientului stocastic concurează cu algoritmul L-BFGS , care este, de asemenea, utilizat pe scară largă. Coborârea gradientului stocastic a fost folosită cel puțin din 1960 pentru a antrena modele de regresie liniară sub denumirea de ADALINE [12] .

Un alt algoritm de coborâre a gradientului stocastic este filtrul adaptiv al celor mai mici pătrate medii [ ( LMS) .

Soiuri și modificări

Există multe modificări ale algoritmului de coborâre a gradientului stocastic. În special, în învățarea automată, problema este alegerea ratei de învățare (dimensiunea pasului): cu un pas mare, algoritmul poate diverge, iar cu un pas mic, convergența este prea lentă. Pentru a rezolva această problemă, puteți utiliza programul ratei de învățare , unde rata de învățare scade pe măsură ce crește numărul de iterații . În același timp, la primele iterații, valorile parametrilor se modifică semnificativ, iar la iterațiile ulterioare, acestea sunt doar rafinate. Asemenea programe sunt cunoscute încă de la lucrările lui McQueen asupra grupării k -means [ 13] . Câteva sfaturi practice privind selecția pașilor în unele variante SGD sunt oferite în secțiunile 4.4, 6.6 și 7.5 din Spall (2003) [14] . $\eta _{t}$ $t$

Modificări implicite (ISGD)

După cum am menționat mai devreme, coborârea clasică a gradientului stocastic este de obicei sensibilă la rata de învățare . Convergența rapidă necesită o rată mare de învățare rapidă, dar aceasta poate provoca instabilitate numerică . Problema poate fi rezolvată în principal [15] luând în considerare modificarea implicită în , când gradientul stocastic este recalculat la următoarea iterație, și nu la cea curentă. $\eta$

w^{nou}:=w^{vechi}-\eta \nabla Q_{i}(w^{nou}).

Această egalitate este implicită deoarece apare de ambele părți ale egalității. Aceasta este forma stocastică a metodei gradientului proximal , deoarece recalcularea poate fi exprimată ca $w^{nou}$

w^{nou}:=\arg \min _{w}\{Q_{i}(w)+{\frac {1}{2\eta }}||ww^{vechi}||^ {2}\}.

Ca exemplu, luați în considerare metoda celor mai mici pătrate cu proprietăți și observații . Vrem să decidem: $x_{1},\ldots,x_{n}\in \mathbb {R} ^{p)$ $y_{1},\ldots,y_{n}\in \mathbb {R}$

\min _{w}\sum _{j=1}^{n}(y_{j}-x_{j}'w)^{2},

unde înseamnă produsul scalar . ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p))$

Rețineți că poate avea „1” ca prim element. Coborârea clasică a gradientului stocastic funcționează astfel $X$

w^{nou}=w^{vechi}+\eta (y_{i}-x_{i}'w^{vechi})x_{i)

unde este distribuit uniform intre 1 si . În timp ce teoretic această procedură converge sub ipoteze relativ ușoare, în practică procedura poate fi extrem de instabilă. În special, dacă se setează incorect, atunci au valori proprii absolute mari cu probabilitate mare, iar procedura poate diverge în mai multe iterații. Prin contrast, coborârea gradientului stocastic implicit ( ISGD ) poate fi exprimată ca $i$ $n$ $\eta$ $I-\eta x_{i}x_{i}'$

w^{nou}=w^{vechi}+{\frac {\eta }{1+\eta ||x_{i}||^{2}}}(y_{i}-x_{i }'w^{vechi})x_{i}.

Procedura va rămâne stabilă numeric pentru aproape toate , deoarece rata de învățare este acum normalizată. O astfel de comparație între coborârea gradientului stocastic clasic și explicit în metoda celor mai mici pătrate este foarte asemănătoare cu comparația dintre filtrul celor mai mici pătrate medii ( engleză cele mai mici pătrate medii , LMS) și filtrul celor mai mici pătrate normalizate ( engleză normalizat filtrul celor mai mici pătrate medii , NLM-uri). $\eta$

Deși soluția analitică pentru ISGD este posibilă numai în metoda celor mai mici pătrate, procedura poate fi implementată eficient într-o gamă largă de modele. În special, să presupunem că depinde doar de o combinație liniară a proprietăților lui , astfel încât să putem scrie , unde o funcție cu valoare reală poate depinde de , dar nu direct, numai prin . Metoda celor mai mici pătrate satisface această condiție și, prin urmare, regresia logistică și cele mai multe modele liniare generalizate satisfac această condiție . De exemplu, în cele mai mici pătrate și în regresia logistică , unde este funcția logistică . În regresia Poisson , și așa mai departe. $Q_{i}(w)$ $w$ $x_{i}$ $\nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i)$ $q$ $x_{i}, y_{i}$ $w$ $x_{i}'w$ $q(x_{i}'w)=y_{i}-x_{i}'w$ $q(x_{i}'w)=y_{i}-S(x_{i}'w)$ $S(u)=e^{u}/(1+e^{u})$ $q(x_{i}'w)=y_{i}-e^{x_{i}'w)$

În astfel de condiții, ISGD este ușor de implementat după cum urmează. Fie , unde este un număr. Atunci ISGD este echivalent cu $f(\xi )=\eta q(x_{i}'w^{vechi}+\xi ||x_{i}||^{2})$ $\xi$

w^{nou}=w^{vechi}+\xi ^{\ast }x_{i},\;\xi ^{\ast }=f(\xi ^{\ast }).

Factorul de scară poate fi găsit prin bisectarea , deoarece în majoritatea modelelor, cum ar fi modelele liniare generalizate de mai sus, funcția scade, iar atunci limitele de căutare vor fi . $\xi ^{\ast }\in \mathbb {R}$ $q$ $\xi ^{\ast }$ $[\min(0,f(0)),\max(0,f(0))]$

Impuls

Evoluții mai recente includ metoda impulsului , care a apărut în lucrarea lui Rumelhart , Hinton și Williams despre învățarea propagării inverse [16] . Coborârea gradientului stocastic de impuls reține schimbarea la fiecare iterație și determină următoarea modificare ca o combinație liniară a gradientului și a modificării anterioare [17] [18] : $\Delta w$

\Delta w:=\alpha \Delta w-\eta \nabla Q_{i}(w)

w:=w+\Delta w

care duce la

w:=w-\eta \nabla Q_{i}(w)+\alpha \Delta w

unde parametrul , care minimizează , ar trebui estimat și este dimensiunea pasului (uneori numită rata de învățare în învățarea automată). $w$ $Q(w)$ $\eta$

Denumirea „momentum” provine de la impuls în fizică - vectorul greutate , înțeles ca traseul unei particule de-a lungul spațiului parametrilor [16] , experimentează o accelerație din gradientul funcției de pierdere (" forță "). Spre deosebire de coborârea clasică a gradientului stocastic, metoda încearcă să mențină progresul în aceeași direcție prin prevenirea fluctuațiilor. Momentum a fost folosit cu succes de informaticieni pentru a antrena rețele neuronale artificiale timp de câteva decenii [19] . $w$

Media

Average Stochastic Gradient Descent , dezvoltat independent de Ruppert și Polyak la sfârșitul anilor 1980, este o coborâre convențională a gradientului stocastic care înregistrează media unui vector de parametri. Adică, recalcularea este aceeași ca și în metoda obișnuită de coborâre a gradientului stocastic, dar algoritmul urmărește și [20]

{\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}

Când optimizarea este completă, vectorul parametrilor medii ia locul lui w .

AdaGrad

AdaGrad ( algoritm de gradient adaptiv ), publicat în 2011 [21] [22] , este o modificare a algoritmului de coborâre a gradientului stocastic cu o rată de învățare separată pentru fiecare parametru . În mod informal, aceasta crește rata de învățare pentru parametrii cu date rare și scade rata de învățare pentru parametrii cu date mai puțin rare. Această strategie crește rata de convergență în comparație cu metoda standard de coborâre a gradientului stocastic în condițiile în care datele sunt rare și parametrii corespunzători sunt mai informative. Exemple de astfel de aplicații sunt procesarea limbajului natural și recunoașterea modelelor [21] . Algoritmul are o rată de învățare de bază, dar este înmulțit cu elementele vectorului care este diagonala matricei exterioare a produsului $\eta$ $\{G_{j,j}}\}$

G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T)}

unde , gradient pe iterație . Diagonala este dată de $g_{\tau}=\nabla Q_{i}(w)$ $\tau$

G_{j,j}=\sum _{\tau =1}^{t}g_{\tau,j}^{2)

Acest vector este actualizat după fiecare iterație. Formula de conversie

w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2)}}\circ g

[A]

sau, scriind ca recalculare prin parametri,

w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j))))g_{j}.

Fiecare element oferă un multiplicator al ratei de învățare aplicat unui parametru . Deoarece numitorul din acest factor, , este norma ℓ2 a derivatei anterioare, modificările mari ale parametrilor sunt atenuate, în timp ce parametrii care primesc modificări mici primesc rate de învățare mai mari [19] . $\{G_{(i,i)}\}$ $w_{i}$ ${\sqrt {G_{i)}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2)))$

Deși algoritmul a fost dezvoltat pentru probleme convexe , AdaGrad a fost utilizat cu succes pentru optimizarea neconvexă [23] .

RMSProp

RMSProp (de la Root Mean Square Propagation ) este o metodă în care rata de învățare este ajustată pentru fiecare parametru. Ideea este de a împărți rata de învățare pentru greutăți la mediile mobile ale gradienților recenti pentru acea greutate [24] . Deci prima medie mobilă este calculată în termeni de rms

v(w,t):=\gamma v(w,t-1)+(1-\gamma )(\nabla Q_{i}(w))^{2)

unde, este factorul uitarii. $\gamma$

Opțiunile sunt actualizate ca

w:=w-{\frac {\eta }{\sqrt {v(w,t)}}}\nabla Q_{i}(w)

RMSProp a demonstrat o bună adaptare a ratei de învățare în diferite aplicații. RMSProp poate fi gândit ca o generalizare a Rprop . Metoda este capabilă să lucreze cu minipachete, nu doar cu pachete complete [25] .

Adam

Adam [26] (prescurtarea de la Adaptive Moment Estimation ) este o actualizare a optimizatorului RMSProp . Acest algoritm de optimizare utilizează medii mobile atât ale gradienților, cât și ale secundelor momente ale gradienților. Dacă sunt dați parametrii , iar funcția de pierdere , unde reflectă indicele iterației curente (raportul începe cu ), recalcularea parametrului prin algoritmul Adam este dată de formulele $w^{(t)}$ $L^{(t)}$ $t$ $0$

m_{w}^{(t+1)}\leftarrow \beta _{1}m_{w}^{(t)}+(1-\beta _{1})\nabla _{w} L^{(t)}

v_{w}^{(t+1)}\leftarrow \beta _{2}v_{w}^{(t)}+(1-\beta _{2})(\nabla _{w }L^{(t)})^{2}

{\hat {m}}_{w}={\frac {m_{w}^{(t+1))}{1-\beta _{1}^{t+1)))

{\hat {v}}_{w}={\frac {v_{w}^{(t+1))}{1-\beta _{2}^{t+1)))

w^{(t+1)}\leftarrow w^{(t)}-\eta {\frac ({\hat {m))_{w)}({\sqrt ({\hat {v) }}_{w}}}+\epsilon }}

unde este un mic aditiv folosit pentru a preveni împărțirea cu 0 și și sunt coeficienții de uitare pentru gradienți și, respectiv, al doilea moment al gradienților. Pătrarea și rădăcina pătrată sunt calculate element cu element. $\epsilon$ $\beta_{1}$ $\beta _{2}$

Coborâre în gradient natural și kSGD

Descent Stochastic Gradient ( kSGD ) [27] bazat pe Kalman este un algoritm online și offline pentru învățarea parametrilor pentru probleme statistice pentru modele de cvasi-probabilitate , care include modele liniare , modele neliniare , modele liniare generalizate și rețele neuronale cu pierderi rms ca caz special. Pentru problemele de învățare online, kSGD este un caz special al filtrului Kalman pentru probleme de regresie liniară, un caz special al filtrului Kalman extins pentru probleme de regresie neliniară și poate fi considerat ca o metodă incrementală Gauss-Newton . Mai mult, datorită relației dintre kSGD și filtrul Kalman și relației dintre coborârea gradientului natural [28] și filtrul Kalman [29] , kSGD este o îmbunătățire majoră a metodei populare de coborâre a gradientului natural.

Avantajele kSGD față de alte metode:

(1) insensibil la numărul de condiții ale problemei, [b] (2) are o alegere robustă de hiperparametri, (3) are o stare de oprire.

Dezavantajul kSGD este că algoritmul necesită stocarea unei matrice de covarianță densă între iterații, iar la fiecare iterație trebuie găsit produsul vectorului și matricei.

Pentru a descrie algoritmul, presupunem că funcția , unde , este definită folosind astfel încât $Q_{i}(w)$ $w\in \mathbb {R} ^{p}$ $(Y_{i},X_{i})\in \mathbb {R} \times \mathbb {R} ^{d)$

\nabla _{w}Q_{i}(w)={\frac {Y_{i}-\mu (X_{i},w)}{V(\mu (X_{i},w) )}}\nabla _{w}\mu (X_{i},w)

unde este funcția de mediere (adică valoarea așteptată a lui ) și este funcția de varianță (adică varianța pentru ). Apoi recalcularea parametrului și recalcularea matricei covariante sunt date de următoarele expresii $\mu (X_{i},w)$ $Y_{i}$ $X_{i}$ $V(\mu (X_{i},w))$ $Y_{i}$ $X_{i}$ $w(t+1)$ $M(t+1)$

p=\nabla _{w}\mu (X_{t+1},w(t))

m=\mu (X_{t+1},w(t))

v=M(t)p

s=\min \lbrace \gamma _{1},\max \lbrace \gamma _{2}, V(m)\rbrace \rbrace +v^{\mathsf {T}}p

w(t+1)=w(t)+{\frac {Y_{t+1}-m}{s}}v

M(t+1)=M(t)-{\frac {1}{s}}vv^{\mathsf {T}}

unde sunt hiperparametrii. Recalcularea poate face ca matricea covariantă să devină nedefinită, ceea ce poate fi evitat prin înmulțirea matricei cu matrice. poate fi orice matrice simetrică pozitiv-definită, dar matricea de identitate este de obicei luată. După cum a observat Patel [27] , pentru toate problemele, cu excepția regresiei liniare, sunt necesare executări repetate pentru a asigura convergența algoritmului, dar nu sunt date detalii teoretice sau de implementare. O metodă strâns legată offline multi-loturi pentru regresia neliniară, analizată de Bertsekas [30] , a folosit factorul de uitare în recalcularea matricei covariante pentru a dovedi convergența. $\gamma _{1},\gamma _{2)$ $M(t)$ $M(0)$

Metode de ordinul doi

Se știe că analogul stocastic al algoritmului Newton-Raphson standard (determinist) (metoda „de ordinul doi”) oferă o formă asimptotic optimă sau aproape optimă de optimizare iterativă în condiții de aproximare stocastică. O metodă care utilizează calculul direct al matricelor hessiene a termenilor sume în funcția de risc empiric a fost dezvoltată de Bird, Hansen, Nosedal și Singer [31] . Cu toate acestea, o determinare directă a matricelor hessiene necesare pentru optimizare ar putea să nu fie posibilă în practică. Metode practice și teoretice pentru o versiune de ordinul doi a algoritmului SGD care nu necesită informații hessiane directe au fost date de Spall și colab . ). Aceste metode, deși nu necesită în mod direct informații despre Hessian, se bazează fie pe valorile termenilor sume din funcția de risc empiric prezentată mai sus, fie pe valorile gradienților termenilor sumei (adică intrarea SGD) . În special, optimitatea de ordinul doi este realizabilă asimptotic fără a calcula direct matricele hessiene ale termenilor sumei în funcția de risc empiric.

Comentarii

↑ este produsul elementwise al lui . $\circ$
↑ Pentru o problemă de regresie liniară, varianța funcției obiective a lui kSGD (adică eroarea totală și varianța) per iterație este egală cu probabilitatea tinde spre 1 la o rată dependentă de , unde este varianța reziduurilor. Mai mult, pentru o anumită alegere a , se poate demonstra că varianța iterației lui kSGD a funcției obiectiv este egală cu probabilitatea care tinde la 1 la o rată dependentă de , unde este parametrul optim. $k$ ${\frac {1+\epsilon }{k}}p\sigma ^{2}$ $\epsilon \in(0,1)$ $\sigma ^{2}$ $\gamma _{1},\gamma _{2)$ $k$ ${\frac {(1+\epsilon )^{2}}{2k^{2}}}\Vert w(0)-w_{*}\Vert _{2}^{2}$ $\epsilon \in(0,1)$ $w_{*}$

Vezi și

Coborâre coordonată - modifică o coordonată la un moment dat
Clasificator liniar
Învățare automată online

Note

↑ 12 Taddy , 2019 , p. 303–307.
↑ Bottou, Bousquet, 2012 , p. 351–368.
↑ Mei, 2018 , p. E7665–E7671.
↑ Ferguson, 1982 , p. 831–834.
↑ Bottou, Bousquet, 2008 , p. 161–168.
↑ Bottou, 1998 .
↑ Kiwiel, 2001 , p. 1–25.
↑ Robbins, Siegmund, 1971 .
↑ Finkel, Kleeman, Manning, 2008 .
↑ LeCun și colab., 2012 , p. 9-48.
↑ Diaz, Guitton, 2011 , p. 2804-2808.
↑ Avi Pfeffer. CS181 Cursul 5 - Perceptroni (Universitatea Harvard) . (nedefinit) (link indisponibil)
↑ Darken, Moody, 1990 .
↑ Spall, 2003 .
↑ Toulis, Airoldi, 2017 , p. 1694–1727
↑ 1 2 Rumelhart, Hinton, Williams, 1986 , p. 533–536.
↑ Sutskever, Martens, Dahl, Hinton, 2013 , p. 1139–1147.
↑ Sutskever, Ilya (2013). Antrenarea rețelelor neuronale recurente (PDF) (Ph.D.). Universitatea din Toronto. Arhivat (PDF) din original pe 28.02.2020 . Extras 2020-03-01 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ 1 2 Matthew D. Zeiler (2012), ADADELTA: An adaptive learning rate method, arΧiv : 1212.5701 [cs.LG].
↑ Polyak, Juditsky, 1992 , p. 838–855.
↑ 1 2 Duchi, Hazan, Singer, 2011 , p. 2121–2159.
↑ Joseph Perla (2014). Note despre AdaGrad (link indisponibil) . Preluat la 1 martie 2020. Arhivat din original la 30 martie 2015. (nedefinit)
↑ Gupta, Bengio, Weston, 2014 , p. 1461–1492
↑ Tieleman, Tijmen și Hinton, Geoffrey (2012). Cursul 6.5-rmsprop: Împărțiți gradientul la o medie curentă a mărimii sale recente. COURSERA: Rețele neuronale pentru învățarea automată
↑ Hinton, Geoffrey Privire de ansamblu asupra coborârii gradientului mini-loturi (link indisponibil) 27–29. Consultat la 27 septembrie 2016. Arhivat din original la 23 noiembrie 2016. (nedefinit)
↑ Kingma Diederik, Jimmy Ba (2014), Adam: A method for stochastic optimization, arΧiv : 1412,6980 [cs.LG].
↑ 12 Patel , 2016 , p. 2620–2648.
↑ Cichocki, Chen, Amari, 1997 , p. 1345–1351.
↑ Ollivier Yann (2017), Online Natural Gradient as a Kalman Filter, arΧiv : 1703.00209 [stat.ML].
↑ Bertsekas, 1996 , p. 807–822.
↑ Byrd, Hansen, Nocedal, Singer, 2016 , p. 1008–1031.
↑ Spall, 2000 , p. 1839−1853.
↑ Spall, 2009 , p. 1216–1229.
↑ Bhatnagar, Prasad, Prashanth, 2013 .
↑ Ruppert, 1985 , p. 236–245.

Literatură

Leon Bottou, Olivier Bousquet. The Tradeoffs of Large Scale Learning // Optimization for Machine Learning / Suvrit Sra, Sebastian Nowozin, Stephen J. Wright (ed.). - Cambridge: MIT Press, 2012. - ISBN 978-0-262-01646-9 .
songmei. O vedere de câmp medie a peisajului rețelelor neuronale cu două straturi // Proceedings of the National Academy of Sciences . - Academia Națională de Științe , 2018. - Vol. 115 , iss. 33 . - doi : 10.1073/pnas.1806579115 . — PMID 30054315 .
Matt Taddy. Descent Stochastic Gradient // Știința datelor de afaceri: combinarea învățării automate și a economiei pentru a optimiza, automatiza și accelera deciziile de afaceri. — New York: McGraw-Hill, 2019. — ISBN 978-1-260-45277-8 .
Thomas S. Ferguson. O estimare a probabilității maxime inconsistente // Jurnalul Asociației Americane de Statistică. - 1982. - T. 77 , nr. 380 . - doi : 10.1080/01621459.1982.10477894 . — .
Leon Bottou, Olivier Bousquet. Compensațiile învățării la scară largă //Progrese în sistemele de procesare a informațiilor neuronale . - 2008. - Or. 20.

Leon Bottou. Algoritmi online și aproximări stocastice // Învățare online și rețele neuronale. - Cambridge University Press, 1998. - ISBN 978-0-521-65263-6 .

Krzysztof C. Kiwiel. Convergența și eficiența metodelor subgradiente pentru minimizarea cvasiconvexă // Programare matematică, Seria A. - Berlin, Heidelberg: Springer, 2001. - Vol. 90 , nr. 1 . — P. 1–25. — ISSN 0025-5610 . - doi : 10.1007/PL00011414 .
Herbert Robbins, David O. Siegmund. O teoremă de convergență pentru supermartingale aproape nenegative și unele aplicații // Optimizing Methods in Statistics / Jagdish S. Rustagi (ed.). — Academic Press, 1971.
Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning. Analizare eficientă, bazată pe caracteristici, pe câmp aleatoriu condiționat // Proc. Adunarea anuală a ACL . — 2008.
Yann A. LeCun, Leon Bottou, Genevieve B. Orr, Klaus-Robert Muller. Backprop eficient // Rețele neuronale: trucuri ale meseriei / Grégoire Montavon, Geneviève B. Orr, Klaus-Robert Müller (Eds.). - Berlin Heidelberg: Springer, 2012. - T. 7700. - (Lecture Notes in Computer Science). - ISBN 978-3-642-35288-1 .
Esteban Diaz, Antoine Guitton. Inversare rapidă completă a formei de undă cu decimare aleatorie a loviturilor // SEG Technical Program Expanded Abstracts . — 2011.
Christian Darken, John Moody. Int'l Joint Conf. on Neural Networks (IJCNN) // Fast adaptive k-means clustering: some empiric results . - IEEE, 1990.
Spall JC Introducere în căutarea stocastică și optimizare: estimare, simulare și control. - Hoboken, NJ: Wiley, 2003. - ISBN 0-471-33052-3 .
Panos Toulis, Edoardo Airoldi. Proprietăți asimptotice și eșantionare finite ale estimatorilor bazați pe gradienți stocastici // Annals of Statistics. - 2017. - T. 45 , nr. 4 . - doi : 10.1214/16-AOS1506 . - arXiv : 1408.2923 .
Spall JC Adaptive Stochastic Aproximation by the Simultaneous Perturbation Method // Tranzacții IEEE pe control automat. - 2000. - T. 45 , nr. 10 . - doi : 10.1109/TAC.2000.880982 .
Spall JC Feedback și mecanisme de ponderare pentru îmbunătățirea estimărilor jacobiene în algoritmul adaptiv de perturbare simultană // IEEE Transactions on Automatic Control. - 2009. - T. 54 , nr. 6 . - doi : 10.1109/TAC.2009.2019793 .
Bhatnagar S., Prasad HL, Prashanth LA Stochastic Recursive Algorithms for Optimization: Simultaneous Perturbation Methods. — Londra: Springer, 2013. — ISBN 978-1-4471-4284-3 .
Ruppert D. O versiune Newton-Raphson a procedurii multivariate Robbins-Monro // Analele statisticilor . - 1985. - T. 13 , nr. 1 . doi : 10.1214 / aos/1176346589 .
David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams. Învățarea reprezentărilor prin retropropagarea erorilor // Natura . - 1986. - Octombrie ( vol. 323 , iss. 6088 ). - doi : 10.1038/323533a0 . - .
Ilya Sutskever, James Martens, George Dahl, Geoffrey E. Hinton. Despre importanța inițializării și a impulsului în învățarea profundă // În lucrările celei de-a 30-a conferințe internaționale privind învățarea automată (ICML-13) / Sanjoy Dasgupta, David Mcallester (ed.). - Atlanta, GA, 2013. - T. 28.
Boris T. Polyak, Anatoli B. Juditsky. Accelerarea aproximării stocastice prin mediere // SIAM J. Control Optim.. - 1992. - Vol. 30 , nr. 4 . - doi : 10.1137/0330046 .
John Duchi, Elad Hazan, Yoram Singer. Metode adaptive subgradient pentru învățarea online și optimizarea stocastică // JMLR . - 2011. - T. 12 .
Maya R. Gupta, Samy Bengio, Jason Weston. Antrenarea clasificatorilor cu mai multe clase // JMLR. - 2014. - T. 15 , nr. 1 .
Metoda de gradient stochastic bazată pe Patel V. Kalman cu condiție de oprire și insensibilitate la condiționare // SIAM Journal on Optimization. - 2016. - T. 26 , nr. 4 . — ISSN 1052-6234 . - doi : 10.1137/15M1048239 . - arXiv : 1512.01139 .
Cichocki A., Chen T., Amari S. Stability Analysis of Learning Algorithms for Blind Source Separation // Neural Networks. - 1997. - Noiembrie ( vol. 10 , numărul 8 ). - doi : 10.1016/S0893-6080(97)00039-7 . — PMID 12662478 .
Byrd RH, Hansen SL, Nocedal J., Singer Y. A Stochastic Quasi-Newton method for Large-Scale Optimization // SIAM Journal on Optimization. - 2016. - T. 26 , nr. 2 . - doi : 10.1137/140954362 . - arXiv : 1401.7020 .
Bertsekas D. Metode incrementale ale celor mai mici pătrate și filtrul Kalman extins // SIAM Journal on Optimization. - 1996. - T. 6 , nr. 3 . - S. 807-822 . — ISSN 1052-6234 . - doi : 10.1137/S1052623494268522 .

Lectură pentru lecturi suplimentare

Dimitri P. Bertsekas. programare neliniară. — al 2-lea. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 978-1-886529-00-7 . .
Dimitri P. Bertsekas. Analiză și optimizare convexă. — Athena Scientific, 2003.
Leon Bottou. Învățare stocastică // Prelegeri avansate despre învățarea automată . - Springer, 2004. - T. 3176. - S. 146-168. — (LNAI). - ISBN 978-3-540-23122-6 .
Davidon WC [187–197 Noi algoritmi cu cel mai mic pătrat] // Journal of Optimization Theory and Applications. - 1976. - T. 18 , nr 2 . - doi : 10.1007/BF00935703 .
Richard O. Duda, Peter E. Hart, David G. Stork. clasificarea modelelor. — al 2-lea. - Wiley , 2000. - ISBN 978-0-471-05669-0 .
Krzysztof C. Kiwiel. Convergența metodelor de subgradient aproximativ și incremental pentru optimizarea convexă // SIAM Journal on Optimization. - 2004. - T. 14 , nr 3 . - S. 807-840 . - doi : 10.1137/S1052623400376366 .
Jan A. Snyman, Daniel N. Wilke. Optimizare matematică practică - Teoria de bază a optimizării și algoritmi bazați pe gradient . - 2. - Springer , 2018. - S. xxvi + 372. - (Springer Optimization and Its Applications Vol. 133). - ISBN 978-3-319-77585-2 .
James C. Spall. Introducere în căutarea stocastică și optimizare. - Wiley , 2003. - ISBN 978-0-471-33052-3 . .

Link -uri

Utilizarea coborârii gradientului stocastic în C++, Boost, Ublas pentru regresia liniară
Algoritmi de învățare automată
Coborâre în gradient, cum învață rețelele neuronale . 3Blue1Brown (16 octombrie 2017). (nedefinit)