Stokastisk gradientnedstigning

Stokastisk gradientnedstigning ( SGD ) er en iterativ metode til at optimere en objektiv funktion med passende glathedsegenskaber (for eksempel differentiabilitet eller subdifferentierbarhed ) . Det kan opfattes som en stokastisk tilnærmelse af gradientnedstigningsoptimering , da den erstatter den faktiske gradient beregnet fra det fulde datasæt med et estimat beregnet ud fra en tilfældigt udvalgt delmængde af dataene [1] . Dette reducerer de involverede computerressourcer og hjælper med at opnå en højere iterationshastighed i bytte for en lavere konvergenshastighed [2] . En særlig stor effekt opnås i applikationer relateret til behandling af big data .

Selvom den grundlæggende idé om stokastisk tilnærmelse går tilbage til Robbins-Monroe-algoritmen fra 1950'erne [3] , er stokastisk gradientnedstigning blevet en vigtig optimeringsteknik i maskinlæring [1] .

Baggrund

Både statistisk estimering og maskinlæring overvejer problemet med at minimere en objektiv funktion , der har form af en sum

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

hvor parameterminimeringen skal estimeres . _ Hver sumterm er normalt forbundet med den th observation i datasættet , der bruges til træning. $w$ $Q(w)$ $Q_{i}$ $jeg$

I klassisk statistik opstår summinimeringsproblemer i mindste kvadraters metode og maksimum sandsynlighedsmetoden (til uafhængige observationer). Den generelle klasse af estimatorer, der opstår som minimering af summer, kaldes M-estimatorer . Men allerede i slutningen af det 20. århundrede blev det bemærket, at kravet om selv lokal minimering er for restriktivt til nogle problemer med maksimumsandsynlighedsmetoden [4] . Derfor overvejer moderne statistiske teoretikere ofte de stationære punkter i sandsynlighedsfunktionen (eller nuller af dens afledte, scoringsfunktionen og andre metoder til at estimere ligninger ).

Summinimeringsproblemet opstår også ved minimering af den empiriske risiko . I dette tilfælde er værdien af tabsfunktionen i det -th eksempel, og er den empiriske risiko. $Q_{i}(w)$ $jeg$ $Q(w)$

Når den bruges til at minimere ovenstående funktion, udfører standard (eller "batch") gradientnedstigningsmetode følgende iterationer:

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

hvor er trinstørrelsen, kaldet indlæringshastigheden i maskinlæring. $\eta$

I mange tilfælde har summerbare funktioner en simpel form, som tillader billige beregninger for summen af funktioner og gradienten af summen. For eksempel, i statistik, tillader brugen af en-parameter eksponentielle familier økonomisk beregning af funktionen og gradienten.

Men i andre tilfælde kan beregning af gradienten af summen kræve dyre gradientberegninger for alle summerbare funktioner. På et stort træningssæt, i mangel af simple formler, bliver det meget dyrt at beregne summen af gradienterne, da beregning af gradienten af summen kræver beregning af gradienterne af de individuelle termer af summen. For at reducere mængden af beregning vælger stokastisk gradientnedstigning et undersæt af summerbare funktioner ved hver iteration af algoritmen. Denne tilgang er især effektiv til store maskinlæringsproblemer [5] .

Iterativ metode

I stokastisk ("online") gradientnedstigning tilnærmes den sande gradient af gradienten i et træningseksempel $Q(w)$

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

Ved at køre gennem træningssættet udfører algoritmen ovenstående genberegning for hvert træningseksempel. Det kan tage flere gennemløb af træningsdatasættet for at opnå konvergens af algoritmen. Før hver ny gennemgang blandes dataene i sættet for at eliminere muligheden for at sløjfe algoritmen. Typiske implementeringer kan bruge adaptiv læringshastighed forbedre konvergens.

I pseudokode kan stokastisk gradientnedstigning repræsenteres som følger:

Vælg en initial parametervektor og en indlæringshastighed . $w$ $\eta$
Gentag indtil et omtrentligt minimum er nået:
- Bland tilfældigt eksemplerne i træningssættet.
- At opfylde $i=1,2,...,n$
  - $\!w:=w-\eta \nabla Q_{i}(w).$

En afvejning mellem at beregne den sande gradient og gradienten over et enkelt træningseksempel kan være at beregne gradienten over mere end ét træningseksempel, kaldet en "mini-batch", ved hvert trin. Dette kan være væsentligt bedre end den beskrevne "sande" stokastiske gradientnedstigning, da koden kan bruge vektorformbiblioteker i stedet for separate beregninger ved hvert trin. Det kan også resultere i jævnere konvergens, da gradienten beregnet ved hvert trin beregnes som gennemsnit over flere træningseksempler.

Konvergensen af stokastisk gradientnedstigning er blevet analyseret ved hjælp af de konvekse minimerings- og stokastiske tilnærmelsesteorier . I en forenklet form kan resultatet repræsenteres som følger: når indlæringshastigheden falder med en passende hastighed, givet relativt svage antagelser, konvergerer stokastisk gradientnedstigning næsten sikkert til det globale minimum, hvis den objektive funktion er konveks eller pseudokonveks , ellers konvergerer metoden næsten sikkert til lokalt minimum [6] [7] . Faktisk er dette en konsekvens af Robbins-Sigmund-sætningen [8] . $\eta$

Eksempel

Antag, at vi ønsker at tilnærme en linje ved hjælp af et træningssæt med mange observationer og tilsvarende svar ved hjælp af mindste kvadraters metode . Den objektive funktion for minimering vil være ${\hat {y}}=\!w_{1}+w_{2}x$ $(x_{1},x_{2},\ldots ,x_{n})$ $({\hat {y_{1}}},{\hat {y_{2}}},\ldots,{\hat {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}\ højre)^{2}.

Den sidste linje i ovenstående pseudokode for opgaven bliver

{\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}}.

Bemærk, at i hver iteration (som også kaldes en resampling), beregnes kun gradienten på et punkt i stedet for at beregne over sættet af alle prøver. $x_i$

Den vigtigste forskel i forhold til standard (batch) gradientnedstigning er, at kun én del af dataene fra hele sættet bruges på hvert trin, og denne del vælges tilfældigt ved hvert trin.

Bemærkelsesværdige applikationer

Stokastisk gradientnedstigning er en populær algoritme til træning af en lang række modeller i maskinlæring , især i (lineære) støttevektormaskiner , i logistisk regression (se for eksempel Vowpal Wabbit ) og i grafsandsynlighedsmodeller [9] . Når det kombineres med backpropagation- algoritmen , er det de facto- standardalgoritmen til træning af kunstige neurale netværk [10] . Dens anvendelse er også blevet set i det geofysiske samfund, især for Full Waveform Inversion (FWI) applikationer [11] .

Stokastisk gradientnedstigning konkurrerer med L-BFGS -algoritmen , som også er meget brugt. Stokastisk gradientnedstigning er blevet brugt siden mindst 1960 til at træne lineære regressionsmodeller under navnet ADALINE [12] .

En anden stokastisk gradientnedstigningsalgoritme er det adaptive filter for mindste middelkvadrater [ ( LMS) .

Sorter og modifikationer

Der er mange modifikationer til den stokastiske gradientnedstigningsalgoritme. Især i maskinlæring er problemet valget af indlæringshastighed (trinstørrelse): med et stort trin kan algoritmen divergere, og med et lille trin er konvergensen for langsom. For at løse dette problem kan du bruge indlæringshastighedsplanen , hvor indlæringshastigheden falder, når iterationstallet stiger . På samme tid, ved de første iterationer, ændres værdierne af parametrene betydeligt, og ved senere iterationer bliver de kun forfinet. Sådanne tidsplaner har været kendt siden McQueens arbejde med k -betyder clustering [ 13] . Nogle praktiske råd om valg af trin i nogle SGD-varianter er givet i afsnit 4.4, 6.6 og 7.5 i Spall (2003) [14] . $\eta _{t}$ $t$

Implicitte ændringer (ISGD)

Som tidligere nævnt er klassisk stokastisk gradientnedstigning normalt følsom over for indlæringshastighed . Hurtig konvergens kræver en hurtig høj indlæringshastighed, men dette kan forårsage numerisk ustabilitet . Problemet kan hovedsageligt løses [15] ved at overveje den implicitte ændring i , når den stokastiske gradient genberegnes ved næste iteration, og ikke ved den nuværende. $\eta$

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

Denne lighed er implicit, fordi den optræder på begge sider af ligheden. Dette er den stokastiske form af den proksimale gradientmetode , da genberegningen kan udtrykkes som $w^{ny}$

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

Som et eksempel kan du overveje mindste kvadraters metode med egenskaber og observationer . Vi ønsker at beslutte: ${\displaystyle 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},

hvor betyder det skalære produkt . ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p))$

Bemærk, at det kan have "1" som det første element. Klassisk stokastisk gradientnedstigning fungerer sådan her $x$

{\displaystyle w^{ny}=w^{gammel}+\eta (y_{i}-x_{i}'w^{gammel})x_{i))

hvor er jævnt fordelt mellem 1 og . Selvom denne procedure teoretisk konvergerer under relativt milde antagelser, kan proceduren i praksis være meget ustabil. Især, hvis de er indstillet forkert, har de store absolutte egenværdier med høj sandsynlighed, og proceduren kan afvige i flere iterationer. I modsætning hertil kan implicit stokastisk gradientnedstigning ( ISGD ) udtrykkes som $jeg$ $n$ $\eta$ $I-\eta x_{i}x_{i}'$

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

Proceduren vil forblive numerisk stabil for næsten alle , da indlæringshastigheden nu er normaliseret. En sådan sammenligning mellem klassisk og eksplicit stokastisk gradientnedstigning i mindste kvadraters metode er meget lig sammenligningen mellem filteret med mindste kvadraters ( engelsk mindste kvadraters , LMS) og det normaliserede mindste kvadraters filter ( engelsk normaliseret mindste gennemsnitlige kvadraters filter , NLM'er). $\eta$

Selvom den analytiske løsning til ISGD kun er mulig i mindste kvadraters metode, kan proceduren implementeres effektivt i en lang række modeller. Antag især, at afhænger af kun som en lineær kombination af egenskaberne af , så vi kan skrive , hvor en reel værdi funktion kan afhænge af , men ikke direkte, kun gennem . Mindste kvadraters metode opfylder denne betingelse, og derfor opfylder logistisk regression og de fleste generaliserede lineære modeller denne betingelse . For eksempel i mindste kvadrater , og i logistisk regression , hvor er den logistiske funktion . I Poisson regression , og så videre. $Q_{i}(w)$ $w$ $x_{i}$ ${\displaystyle \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})$ ${\displaystyle q(x_{i}'w)=y_{i}-e^{x_{i}'w))$

Under sådanne forhold er ISGD let at implementere som følger. Lad , hvor er et tal. Så svarer ISGD til $f(\xi )=\eta q(x_{i}'w^{gammel}+\xi ||x_{i}||^{2})$ $\xi$

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

Skalafaktoren kan findes ved at halvere , for i de fleste modeller, såsom de ovenstående generaliserede lineære modeller, falder funktionen, og så vil søgegrænserne for være . $\xi ^{\ast }\in \mathbb {R}$ $q$ ${\displaystyle \xi ^{\ast ))$ $[\min(0,f(0)),\max(0,f(0))]$

Impuls

Nyere udvikling omfatter momentum-metoden , som dukkede op i Rumelhart , Hinton og Williams' papir om backpropagation learning [16] . Momentum stokastisk gradientnedstigning husker ændringen ved hver iteration og bestemmer den næste ændring som en lineær kombination af gradienten og den forrige ændring [17] [18] : $\Delta w$

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

w:=w+\Delta w

der fører til

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

hvor parameteren , som minimerer , skal estimeres , og er trinstørrelsen (nogle gange kaldet indlæringshastigheden i maskinlæring). $w$ $Q(w)$ $\eta$

Navnet "momentum" stammer fra momentum i fysik - vægtvektoren , forstået som en partikels vej langs parameterrummet [16] , oplever acceleration fra gradienten af tabsfunktionen (" kraft "). I modsætning til klassisk stokastisk gradientnedstigning forsøger metoden at holde fremskridtet i samme retning ved at forhindre udsving. Momentum er blevet brugt med succes af computerforskere til at træne kunstige neurale netværk i flere årtier [19] . $w$

Gennemsnitlig

Gennemsnitlig stokastisk gradientnedstigning , udviklet uafhængigt af Ruppert og Polyak i slutningen af 1980'erne, er en konventionel stokastisk gradientnedstigning, der registrerer middelværdien af en vektor af parametre. Det vil sige, at genberegningen er den samme som i den sædvanlige stokastiske gradientnedstigningsmetode, men algoritmen sporer også [20]

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

Når optimeringen er fuldført, træder vektoren af middelparametre i stedet for w .

AdaGrad

AdaGrad (adaptive gradient algorithm ), udgivet i 2011 [21] [22] , er en modifikation af den stokastiske gradient descent-algoritme med en separat indlæringshastighed for hver parameter . Uformelt øger dette indlæringshastigheden for parametre med sparsomme data og reducerer indlæringshastigheden for parametre med mindre sparsomme data. Denne strategi øger konvergenshastigheden sammenlignet med standard stokastisk gradientnedstigningsmetode under forhold, hvor dataene er sparsomme, og de tilsvarende parametre er mere informative. Eksempler på sådanne applikationer er naturlig sprogbehandling og mønstergenkendelse [21] . Algoritmen har en basisindlæringshastighed, men den multipliceres med elementerne i vektoren , som er diagonalen af den ydre produktmatrix $\eta$ $\{G_{j,j}}\}$

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

hvor , gradient pr. iteration . Diagonalen er givet ved $g_{\tau }=\nabla Q_{i}(w)$ $\tau$

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

Denne vektor opdateres efter hver iteration. Konverteringsformel

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

[en]

eller skrive som genberegning af parametre,

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

Hvert element giver en multiplikator for indlæringshastigheden anvendt på én parameter . Fordi nævneren i denne faktor, , er ℓ2- normen for den tidligere afledede, dæmpes store parameterændringer, mens parametre, der modtager små ændringer, får højere indlæringsrater [19] . $\{G_{(i,i)}\}$ $w_{i}$ ${\displaystyle {\sqrt {G_{i))}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2))))$

Selvom algoritmen blev udviklet til konvekse problemer , er AdaGrad med succes blevet brugt til ikke-konveks optimering [23] .

RMSProp

RMSProp (fra Root Mean Square Propagation ) er en metode, hvor indlæringshastigheden justeres for hver parameter. Ideen er at dividere indlæringshastigheden for vægtene med de glidende gennemsnit af de seneste gradienter for den vægt [24] . Så det første glidende gennemsnit beregnes i forhold til rms

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

hvor, er den glemmende faktor. $\gamma$

Valgmuligheder opdateres som

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

RMSProp har vist god tilpasning af indlæringshastigheden på tværs af forskellige applikationer. RMSProp kan opfattes som en generalisering af Rprop . Metoden er i stand til at arbejde med minipakker, ikke kun fulde pakker [25] .

Adam

Adam [26] (forkortelse for Adaptive Moment Estimation ) er en opdatering til RMSProp optimizer . Denne optimeringsalgoritme bruger glidende gennemsnit af både gradienterne og de andet momenter af gradienterne. Hvis parametrene er givet , og tabsfunktionen , hvor afspejler indekset for den aktuelle iteration (rapporten starter med ), er genberegningen af parameteren ved Adam-algoritmen givet af formlerne $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}

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

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

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

hvor er et lille additiv, der bruges til at forhindre division med 0, og og er glemmekoefficienterne for henholdsvis gradienterne og de andet momenter af gradienterne. Kvadrat og kvadratrod beregnes element for element. $\epsilon$ $\beta_{1}$ $\beta _{2}$

Naturlig gradientnedstigning og kSGD

Kalman- baseret Stokastisk Gradient Descent ( kSGD ) [27] er en online og offline algoritme til indlæring af parametre for statistiske problemer for quasi-likelihood- modeller , som inkluderer lineære modeller , ikke-lineære modeller , generaliserede lineære modeller og neurale netværk med rms tab som et særligt tilfælde. For online læringsproblemer er kSGD et specialtilfælde af Kalman-filteret for lineære regressionsproblemer, et særligt tilfælde af det udvidede Kalman-filter for ikke-lineære regressionsproblemer, og kan betragtes som en inkrementel Gauss-Newton- metode . På grund af forholdet mellem kSGD og Kalman-filteret og forholdet mellem naturlig gradientnedstigning [28] til Kalman-filteret [29] er kSGD desuden en væsentlig forbedring af den populære metode til naturlig gradientnedstigning.

Fordele ved kSGD frem for andre metoder:

(1) ufølsom over for antallet af betingelser for problemet, [b] (2) har et robust udvalg af hyperparametre, (3) har en stopbetingelse.

Ulempen ved kSGD er, at algoritmen kræver lagring af en tæt kovariansmatrix mellem iterationer, og ved hver iteration skal produktet af vektoren og matricen findes.

For at beskrive algoritmen antager vi, at funktionen , hvor , er defineret ved at bruge så $Q_{i}(w)$ $w\in \mathbb {R} ^{p}$ ${\displaystyle (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)

hvor er gennemsnitsfunktionen (det vil sige den forventede værdi af ), og er variansfunktionen (det vil sige variansen for ). Derefter er genberegningen af parameteren og genberegningen af den kovariante matrix givet ved følgende udtryk $\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}}

hvor er hyperparametre. Genberegning kan få den kovariante matrix til at blive udefineret, hvilket kan undgås ved at gange matrix med matrix. kan være en hvilken som helst positiv-definitiv symmetrisk matrix, men identitetsmatrixen tages normalt. Som bemærket af Patel [27] kræves der for alle problemer, undtagen lineær regression, gentagne kørsler for at sikre konvergensen af algoritmen, men der gives ingen teoretiske eller implementeringsdetaljer. En nært beslægtet offline multi-batch metode til ikke-lineær regression, analyseret af Bertsekas [30] , brugte glemmefaktoren ved genberegning af den kovariante matrix for at bevise konvergens. ${\displaystyle \gamma _{1},\gamma _{2))$ $M(t)$ $M(0)$

Anden orden metoder

Det er kendt, at den stokastiske analog af den standard (deterministiske) Newton-Raphson algoritme (“anden ordens” metoden) giver en asymptotisk optimal eller næsten optimal form for iterativ optimering under forhold med stokastisk tilnærmelse. En metode, der anvender den direkte beregning af de hessiske matricer af sumleddene i den empiriske risikofunktion, er udviklet af Bird, Hansen, Nosedal og Singer [31] . Imidlertid er en direkte bestemmelse af de nødvendige hessiske matricer til optimering muligvis ikke mulig i praksis. Praktiske og teoretiske metoder til en andenordens version af SGD - algoritmen, der ikke kræver direkte hessisk information, er blevet givet af Spall et al . ). Disse metoder, selv om de ikke direkte kræver information om hessian, er baseret enten på værdierne af sumtermerne i den empiriske risikofunktion givet ovenfor eller på værdierne af gradienterne af sumtermerne (dvs. SGD-input) . Især andenordens optimalitet er asymptotisk opnåelig uden direkte at beregne de hessiske matricer af summens vilkår i den empiriske risikofunktion.

Kommentarer

↑ er det elementvise produkt af . $\cirk$
↑ For et lineært regressionsproblem er kSGDs objektive funktionsvarians (dvs. total fejl og varians) per iteration lig med sandsynlighed, der tenderer til 1 med en hastighed, der afhænger af , hvor er variansen af residualerne. Desuden kan det for et bestemt valg af , vises, at kSGD's iterationsvarians af den objektive funktion er lig med sandsynlighed, der har tendens til 1 med en hastighed afhængig af , hvor er den optimale parameter. $k$ ${\frac {1+\epsilon }{k}}p\sigma ^{2}$ $\epsilon \in(0,1)$ $\sigma ^{2}$ ${\displaystyle \gamma _{1},\gamma _{2))$ $k$ ${\frac {(1+\epsilon )^{2}}{2k^{2}}}\Vert w(0)-w_{*}\Vert _{2}^{2}$ $\epsilon \in(0,1)$ $w_{*}$

Se også

Koordinatnedstigning - ændrer en koordinat ad gangen
Lineær klassifikator
Online maskinlæring

Noter

↑ 12 Taddy , 2019 , s. 303-307.
↑ Bottou, Bousquet, 2012 , s. 351-368.
↑ Mei, 2018 , s. E7665–E7671.
↑ Ferguson, 1982 , s. 831-834.
↑ Bottou, Bousquet, 2008 , s. 161-168.
↑ Bottou, 1998 .
↑ Kiwiel, 2001 , s. 1-25.
↑ Robbins, Siegmund, 1971 .
↑ Finkel, Kleeman, Manning, 2008 .
↑ LeCun et al., 2012 , s. 9-48.
↑ Diaz, Guitton, 2011 , s. 2804-2808.
↑ Avi Pfeffer. CS181 Forelæsning 5 - Perceptroner (Harvard University) . (ubestemt) (utilgængeligt link)
↑ Darken, Moody, 1990 .
↑ Spall, 2003 .
↑ Toulis, Airoldi, 2017 , s. 1694–1727
↑ 1 2 Rumelhart, Hinton, Williams, 1986 , s. 533-536.
↑ Sutskever, Martens, Dahl, Hinton, 2013 , s. 1139-1147.
↑ Sutskever, Ilya (2013). Træning af tilbagevendende neurale netværk (PDF) (Ph.D.). University of Toronto. Arkiveret (PDF) fra originalen 2020-02-28 . Hentet 2020-03-01 . Forældet parameter brugt |deadlink=( hjælp )
↑ 1 2 Matthew D. Zeiler (2012), ADADELTA: An adaptive learning rate method, arΧiv : 1212.5701 [cs.LG].
↑ Polyak, Juditsky, 1992 , s. 838-855.
↑ 1 2 Duchi, Hazan, Singer, 2011 , s. 2121-2159.
↑ Joseph Perla (2014). Noter om AdaGrad (utilgængeligt link) . Hentet 1. marts 2020. Arkiveret fra originalen 30. marts 2015. (ubestemt)
↑ Gupta, Bengio, Weston, 2014 , s. 1461-1492
↑ Tieleman, Tijmen og Hinton, Geoffrey (2012). Forelæsning 6.5-rmsprop: Divider gradienten med et løbende gennemsnit af dens seneste størrelse. KURSUS: Neurale netværk til maskinlæring
↑ Hinton, Geoffrey Oversigt over mini-batch gradient nedstigning (link utilgængeligt) 27-29. Hentet 27. september 2016. Arkiveret fra originalen 23. november 2016. (ubestemt)
↑ Kingma Diederik, Jimmy Ba (2014), Adam: A method for stochastic optimization, arΧiv : 1412.6980 [cs.LG].
↑ 12 Patel , 2016 , s. 2620-2648.
↑ Cichocki, Chen, Amari, 1997 , s. 1345-1351.
↑ Ollivier Yann (2017), Online Natural Gradient as a Kalman Filter, arΧiv : 1703.00209 [stat.ML].
↑ Bertsekas, 1996 , s. 807-822.
↑ Byrd, Hansen, Nocedal, Singer, 2016 , s. 1008-1031.
↑ Spall, 2000 , s. 1839−1853.
↑ Spall, 2009 , s. 1216-1229.
↑ Bhatnagar, Prasad, Prashanth, 2013 .
↑ Ruppert, 1985 , s. 236-245.

Litteratur

Leon Bottou, Olivier Bousquet. The Tradeoffs of Large Scale Learning // Optimization for Machine Learning / Suvrit Sra, Sebastian Nowozin, Stephen J. Wright (red.). - Cambridge: MIT Press, 2012. - ISBN 978-0-262-01646-9 .
sangmei. Et gennemsnitligt feltbillede af landskabet af to-lags neurale netværk // Proceedings of the National Academy of Sciences . - National Academy of Sciences , 2018. - Vol. 115 , udg. 33 . - doi : 10.1073/pnas.1806579115 . — PMID 30054315 .
Matt Taddy. Stokastisk gradientnedstigning // Business Data Science: Kombination af maskinlæring og økonomi for at optimere, automatisere og fremskynde forretningsbeslutninger. — New York: McGraw-Hill, 2019. — ISBN 978-1-260-45277-8 .
Thomas S. Ferguson. Et inkonsistent estimat for maksimal sandsynlighed // Journal of the American Statistical Association. - 1982. - T. 77 , no. 380 . - doi : 10.1080/01621459.1982.10477894 . — .
Leon Bottou, Olivier Bousquet. Afvejningen af læring i stor skala //Fremskridt inden for neurale informationsbehandlingssystemer . - 2008. - T. 20.

Leon Bottou. Online algoritmer og stokastiske approksimationer // Online læring og neurale netværk. - Cambridge University Press, 1998. - ISBN 978-0-521-65263-6 .

Krzysztof C. Kiwiel. Konvergens og effektivitet af subgradientmetoder til kvasikonveks minimering // Mathematical Programming, Series A. - Berlin, Heidelberg: Springer, 2001. - Vol. 90 , nr. 1 . — S. 1–25. — ISSN 0025-5610 . - doi : 10.1007/PL00011414 .
Herbert Robbins, David O. Siegmund. En konvergenssætning for ikke-negative næsten supermartingales og nogle applikationer // Optimizing Methods in Statistics / Jagdish S. Rustagi (red.). — Academic Press, 1971.
Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning. Effektiv, funktionsbaseret, betinget tilfældig feltparsing // Proc. Årsmøde i ACL . – 2008.
Yann A. LeCun, Leon Bottou, Genevieve B. Orr, Klaus-Robert Muller. Effektiv backprop // Neurale netværk: Tricks of the trade / Grégoire Montavon, Geneviève B. Orr, Klaus-Robert Müller (red.). - Berlin Heidelberg: Springer, 2012. - T. 7700. - (Lecture Notes in Computer Science). - ISBN 978-3-642-35288-1 .
Esteban Diaz, Antoine Guitton. Hurtig fuld bølgeforminversion med tilfældig skuddecimering // SEG Technical Program Expanded Abstracts . – 2011.
Christian Darken, John Moody. Int'l Joint Conf. på neurale netværk (IJCNN) // Hurtig adaptiv k-betyder klyngedannelse: nogle empiriske resultater . — IEEE, 1990.
Spall JC Introduktion til stokastisk søgning og optimering: estimering, simulering og kontrol. - Hoboken, NJ: Wiley, 2003. - ISBN 0-471-33052-3 .
Panos Toulis, Edoardo Airoldi. Asymptotiske og finite-sample egenskaber af estimatorer baseret på stokastiske gradienter // Annals of Statistics. - 2017. - T. 45 , no. 4 . - doi : 10.1214/16-AOS1506 . - arXiv : 1408.2923 .
Spall JC Adaptiv Stokastisk Approximation ved den simultane forstyrrelsesmetode // IEEE-transaktioner på automatisk kontrol. - 2000. - T. 45 , no. 10 . - doi : 10.1109/TAC.2000.880982 .
Spall JC- feedback og vægtningsmekanismer til forbedring af Jacobian-estimater i den adaptive simultane forstyrrelsesalgoritme // IEEE-transaktioner på automatisk kontrol. - 2009. - T. 54 , no. 6 . - doi : 10.1109/TAC.2009.2019793 .
Bhatnagar S., Prasad HL, Prashanth LA Stokastiske rekursive algoritmer til optimering: simultane forstyrrelsesmetoder. — London: Springer, 2013. — ISBN 978-1-4471-4284-3 .
Ruppert D. En Newton-Raphson-version af den multivariate Robbins-Monro-procedure // Annals of Statistics . - 1985. - T. 13 , no. 1 . doi : 10.1214 / aos/1176346589 .
David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams. Læring af repræsentationer ved tilbage-propagerende fejl // Nature . - 1986. - Oktober ( vol. 323 , iss. 6088 ). - doi : 10.1038/323533a0 . - .
Ilya Sutskever, James Martens, George Dahl, Geoffrey E. Hinton. Om vigtigheden af initialisering og fremdrift i deep learning // In Proceedings of the 30th international conference on machine learning (ICML-13) / Sanjoy Dasgupta, David Mcallester (red.). - Atlanta, GA, 2013. - T. 28.
Boris T. Polyak, Anatoli B. Juditsky. Acceleration af stokastisk tilnærmelse ved middelværdi // SIAM J. Control Optim.. - 1992. - Vol. 30 , no. 4 . - doi : 10.1137/0330046 .
John Duchi, Elad Hazan, Yoram Singer. Adaptive subgradient metoder til online læring og stokastisk optimering // JMLR . - 2011. - T. 12 .
Maya R. Gupta, Samy Bengio, Jason Weston. Træning af højklassificerende klassifikatorer // JMLR. - 2014. - T. 15 , no. 1 .
Patel V. Kalman-baseret stokastisk gradientmetode med stoptilstand og ufølsomhed over for konditionering // SIAM Journal om optimering. - 2016. - T. 26 , no. 4 . — ISSN 1052-6234 . - doi : 10.1137/15M1048239 . - arXiv : 1512.01139 .
Cichocki A., Chen T., Amari S. Stabilitetsanalyse af læringsalgoritmer til blindkildeadskillelse // Neurale netværk. - 1997. - November ( bind 10 , hæfte 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 , no. 2 . - doi : 10.1137/140954362 . - arXiv : 1401.7020 .
Bertsekas D. Incremental Least Squares Methods and the Extended Kalman Filter // SIAM Journal on Optimization. - 1996. - T. 6 , no. 3 . - S. 807-822 . — ISSN 1052-6234 . - doi : 10.1137/S1052623494268522 .

Læsning for yderligere læsning

Dimitri P. Bertsekas. ikke-lineær programmering. — 2. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 978-1-886529-00-7 . .
Dimitri P. Bertsekas. Konveks analyse og optimering. — Athena Scientific, 2003.
Leon Bottou. Stokastisk læring // Avancerede forelæsninger om maskinlæring . - Springer, 2004. - T. 3176. - S. 146-168. — (LNAI). - ISBN 978-3-540-23122-6 .
Davidon WC [187-197 Nye mindste kvadraters algoritmer] // Journal of Optimization Theory and Applications. - 1976. - T. 18 , nr. 2 . - doi : 10.1007/BF00935703 .
Richard O. Duda, Peter E. Hart, David G. Stork. mønster klassificering. — 2. - Wiley , 2000. - ISBN 978-0-471-05669-0 .
Krzysztof C. Kiwiel. Konvergens af omtrentlige og inkrementelle subgradientmetoder til konveks optimering // SIAM Journal on Optimization. - 2004. - T. 14 , nr. 3 . - S. 807-840 . - doi : 10.1137/S1052623400376366 .
Jan A. Snyman, Daniel N. Wilke. Praktisk matematisk optimering - Grundlæggende optimeringsteori og gradientbaserede algoritmer . - 2. - Springer , 2018. - S. xxvi + 372. - (Springer Optimization and Its Applications Vol. 133). - ISBN 978-3-319-77585-2 .
James C. Spall. Introduktion til Stokastisk søgning og optimering. - Wiley , 2003. - ISBN 978-0-471-33052-3 . .