Stokastisk gradientnedstigning

Stokastisk gradientnedstigning ( SGD ) är en iterativ metod för att optimera en objektiv funktion med lämpliga jämnhetsegenskaper ( till exempel differentiabilitet eller subdifferentiering ). Det kan ses som en stokastisk approximation av gradientnedstigningsoptimering , eftersom den ersätter den faktiska gradienten beräknad från hela datasetet med en uppskattning beräknad från en slumpmässigt vald delmängd av data [1] . Detta minskar de involverade beräkningsresurserna och hjälper till att uppnå högre iterationshastigheter i utbyte mot lägre konvergenshastigheter [2] . En särskilt stor effekt uppnås i applikationer relaterade till bearbetning av big data .

Även om grundidén för stokastisk approximation går tillbaka till Robbins-Monroe-algoritmen på 1950-talet [3] har stokastisk gradientnedstigning blivit en viktig optimeringsteknik inom maskininlärning [1] .

Bakgrund

Både statistisk uppskattning och maskininlärning beaktar problemet med att minimera en objektiv funktion som har formen av en summa

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

där parameterminimeringen ska uppskattas . _ Varje summaterm är vanligtvis associerad med den e observationen i datasetet som används för träning. $w$ $Q(w)$ $Q_{i}$ $i$

I klassisk statistik uppstår summaminimeringsproblem i minsta kvadratmetoden och maximum likelihood-metoden (för oberoende observationer). Den allmänna klassen av estimatorer som uppstår som minimering av summor kallas M-estimatorer . Men redan i slutet av 1900-talet märktes att kravet på ens lokal minimering är för restriktivt för vissa problem med maximum likelihood-metoden [4] . Därför överväger moderna statistiska teoretiker ofta sannolikhetsfunktionens stationära punkter (eller nollor i dess derivata, poängfunktionen och andra metoder för att uppskatta ekvationer ).

Summinimeringsproblemet uppstår också vid minimering av den empiriska risken . I det här fallet är värdet av förlustfunktionen i det -th exemplet, och är den empiriska risken. $Q_{i}(w)$ $i$ $Q(w)$

När den används för att minimera ovanstående funktion, utför standardmetoden (eller "batch") gradientnedstigning följande iterationer:

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

var är stegstorleken, kallad inlärningshastigheten i maskininlärning. $\eta$

I många fall har summerbara funktioner en enkel form, vilket möjliggör lågkostnadsberäkningar för summan av funktioner och gradienten av summan. Till exempel, i statistik, tillåter användningen av enparameters exponentiella familjer ekonomisk beräkning av funktionen och gradienten.

Men i andra fall kan beräkning av gradienten för summan kräva dyra gradientberäkningar för alla summerbara funktioner. På en stor träningsuppsättning, i avsaknad av enkla formler, blir det mycket dyrt att beräkna summorna av gradienterna, eftersom beräkningen av gradienten för summan kräver att man beräknar gradienterna för de individuella termerna av summan. För att minska mängden beräkningar väljer stokastisk gradientnedstigning en delmängd av summerbara funktioner vid varje iteration av algoritmen. Detta tillvägagångssätt är särskilt effektivt för stora maskininlärningsproblem [5] .

Iterativ metod

I stokastisk ("online") gradientnedstigning approximeras den sanna gradienten av gradienten för ett träningsexempel $Q(w)$

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

Genom att köra igenom träningsuppsättningen utför algoritmen ovanstående omräkning för varje träningsexempel. Det kan ta flera pass över träningsdatauppsättningen för att uppnå konvergens av algoritmen. Före varje nytt pass blandas data i uppsättningen för att eliminera möjligheten att loopa algoritmen. Typiska implementeringar kan använda adaptiv inlärningshastighet för förbättra konvergensen.

I pseudokod kan stokastisk gradientnedstigning representeras enligt följande:

Välj en initial parametervektor och en inlärningshastighet . $w$ $\eta$
Upprepa tills ett ungefärligt minimum har uppnåtts:
- Blanda slumpmässigt exemplen i träningsuppsättningen.
- Att uppfylla $i=1,2,...,n$
  - $\!w:=w-\eta \nabla Q_{i}(w).$

En avvägning mellan att beräkna den sanna gradienten och gradienten över ett enskilt träningsexempel kan vara att beräkna gradienten över mer än ett träningsexempel, kallat en "minibatch", vid varje steg. Detta kan vara betydligt bättre än den beskrivna "sanna" stokastiska gradientnedstigningen, eftersom koden kan använda vektorformbibliotek istället för separata beräkningar vid varje steg. Det kan också resultera i jämnare konvergens eftersom gradienten som beräknas vid varje steg beräknas i medeltal över fler träningsexempel.

Konvergensen av stokastisk gradientnedstigning har analyserats med hjälp av teorierna för konvex minimering och stokastisk approximation . I en förenklad form kan resultatet representeras enligt följande: när inlärningshastigheten minskar i en lämplig takt, givet relativt svaga antaganden, konvergerar stokastisk gradientnedstigning nästan säkert till det globala minimumet om den objektiva funktionen är konvex eller pseudokonvex , annars konvergerar metoden nästan säkert till lokalt minimum [6] [7] . I själva verket är detta en följd av Robbins-Sigmund-satsen [8] . $\eta$

Exempel

Anta att vi vill approximera en linje genom en träningsuppsättning med många observationer och motsvarande svar med hjälp av minsta kvadratmetoden . Den objektiva funktionen för minimering kommer att vara ${\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)=\summa _{i=1}^{n}Q_{i}(w)=\summa _{i=1}^{n}\left({\hat {y_{i }}}-y_{i}\right)^{2}=\summa _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\ höger)^{2}.

Den sista raden i ovanstående pseudokod för uppgiften blir

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

Observera att i varje iteration (som också kallas omsampling) beräknas endast gradienten vid en punkt istället för att beräknas över uppsättningen av alla sampel. $x_i$

Den viktigaste skillnaden jämfört med standard (batch) gradientnedstigning är att endast en del av data från hela uppsättningen används vid varje steg, och denna del väljs slumpmässigt vid varje steg.

Anmärkningsvärda applikationer

Stokastisk gradientnedstigning är en populär algoritm för att träna ett brett spektrum av modeller inom maskininlärning , i synnerhet i (linjära) stödvektormaskiner , i logistisk regression (se till exempel Vowpal Wabbit ) och i grafiska probabilistiska modeller [9] . När den kombineras med backpropagation- algoritmen är den de facto standardalgoritmen för träning av artificiella neurala nätverk [10] . Dess tillämpning har också setts i det geofysiska samhället, särskilt för Full Waveform Inversion (FWI) applikationer [11] .

Stokastisk gradientnedstigning konkurrerar med L-BFGS -algoritmen , som också används flitigt. Stokastisk gradientnedstigning har använts sedan åtminstone 1960 för att träna linjära regressionsmodeller under namnet ADALINE [12] .

En annan stokastisk gradientnedstigningsalgoritm är det adaptiva filtret för minsta medelkvadrat [ ( LMS) .

Sorter och modifieringar

Det finns många modifieringar av den stokastiska gradientnedstigningsalgoritmen. I synnerhet inom maskininlärning är problemet valet av inlärningshastighet (stegstorlek): med ett stort steg kan algoritmen divergera, och med ett litet steg är konvergensen för långsam. För att lösa detta problem kan du använda inlärningshastighetsschemat , där inlärningshastigheten minskar när iterationstalet ökar . Samtidigt, vid de första iterationerna, ändras parametrarnas värden avsevärt, och vid senare iterationer förfinas de bara. Sådana scheman har varit kända sedan McQueens arbete med k -means clustering [ 13] . Några praktiska råd om stegval i vissa SGD-varianter ges i avsnitt 4.4, 6.6 och 7.5 i Spall (2003) [14] . $\eta _{t}$ $t$

Implicita ändringar (ISGD)

Som nämnts tidigare är klassisk stokastisk gradientnedstigning vanligtvis känslig för inlärningshastighet . Snabb konvergens kräver en snabb hög inlärningshastighet, men detta kan orsaka numerisk instabilitet . Problemet kan huvudsakligen lösas [15] genom att beakta den implicita förändringen i , när den stokastiska gradienten beräknas om vid nästa iteration, och inte vid den nuvarande. $\eta$

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

Denna jämlikhet är implicit eftersom den förekommer på båda sidor om jämlikheten. Detta är den stokastiska formen av den proximala gradientmetoden , eftersom omräkningen kan uttryckas som $w^{ny}$

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

Som ett exempel, betrakta minsta kvadratmetoden med egenskaper och observationer . Vi vill bestämma: ${\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},

där betyder den skalära produkten . ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p))$

Observera att den kan ha "1" som första element. Klassisk stokastisk gradientnedstigning fungerar så här $x$

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

där är jämnt fördelat mellan 1 och . Även om detta förfarande teoretiskt konvergerar under relativt milda antaganden, kan förfarandet i praktiken vara mycket instabilt. I synnerhet, om de ställs in felaktigt, har de stora absoluta egenvärden med hög sannolikhet, och proceduren kan skilja sig åt i flera iterationer. Däremot kan implicit stokastisk gradientnedstigning ( ISGD ) uttryckas som $i$ $n$ $\eta$ $I-\eta x_{i}x_{i}'$

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

Proceduren kommer att förbli numeriskt stabil för nästan alla , eftersom inlärningshastigheten nu är normaliserad. En sådan jämförelse mellan klassisk och explicit stokastisk gradientnedstigning i minsta kvadratmetoden är mycket lik jämförelsen mellan minsta medelkvadratfiltret ( engelska minsta medelkvadrat , LMS) och det normaliserade minsta kvadratfiltret ( engelska normalized minsta medelkvadratfilter , NLMs). $\eta$

Även om den analytiska lösningen för ISGD endast är möjlig i minsta kvadratmetoden, kan proceduren effektivt implementeras i ett brett spektrum av modeller. Antag i synnerhet att beror på endast som en linjär kombination av egenskaperna hos , så att vi kan skriva , där en verklig funktion kan bero på , men inte direkt, endast genom . Minsta kvadratmetoden uppfyller detta villkor, och därför uppfyller logistisk regression och de flesta generaliserade linjära modeller detta villkor . Till exempel, i minsta kvadrater , och i logistisk regression , var är den logistiska funktionen . I Poisson regression , och så vidare. $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ådana förhållanden är ISGD lätt att implementera enligt följande. Låt , var är en siffra. Då motsvarar ISGD $f(\xi )=\eta q(x_{i}'w^{old}+\xi ||x_{i}||^{2})$ $\xi$

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

Skalfaktorn kan hittas genom att halvera , för i de flesta modellerna, som de ovan generaliserade linjära modellerna, minskar funktionen , och då blir sökgränserna för . $\xi ^{\ast }\in \mathbb {R}$ $q$ ${\displaystyle \xi ^{\ast ))$ $[\min(0,f(0)),\max(0,f(0))]$

Impuls

Nyare utveckling inkluderar momentummetoden , som dök upp i Rumelhart , Hinton och Williams papper om backpropagation learning [16] . Momentum stokastisk gradientnedstigning kommer ihåg förändringen vid varje iteration och bestämmer nästa förändring som en linjär kombination av gradienten och den föregående förändringen [17] [18] : $\Delta w$

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

w:=w+\Delta w

som leder till

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

där parametern , som minimerar , ska uppskattas , och är stegstorleken (kallas ibland inlärningshastigheten vid maskininlärning). $w$ $Q(w)$ $\eta$

Namnet "momentum" härstammar från momentum i fysiken - viktvektorn , förstås som en partikels väg längs parameterrymden [16] , upplever acceleration från förlustfunktionens gradient (" kraft "). Till skillnad från klassisk stokastisk gradientnedstigning försöker metoden hålla framstegen i samma riktning genom att förhindra fluktuationer. Momentum har använts framgångsrikt av datavetare för att träna artificiella neurala nätverk i flera decennier [19] . $w$

Genomsnittlig

Average Stochastic Gradient Descent , utvecklad oberoende av Ruppert och Polyak i slutet av 1980-talet, är en konventionell stokastisk gradientnedstigning som registrerar medelvärdet av en vektor av parametrar. Det vill säga, omräkningen är densamma som i den vanliga stokastiska gradientnedstigningsmetoden, men algoritmen spårar också [20]

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

När optimeringen är klar tar vektorn av medelparametrar platsen för w .

AdaGrad

AdaGrad (adaptive gradient algorithm ), publicerad 2011 [21] [22] , är en modifiering av den stokastiska gradientnedstigningsalgoritmen med en separat inlärningshastighet för varje parameter . Informellt ökar detta inlärningshastigheten för parametrar med gles data och minskar inlärningshastigheten för parametrar med mindre gles data. Denna strategi ökar konvergenshastigheten jämfört med standardmetoden för stokastisk gradientnedstigning under förhållanden där data är sparsam och motsvarande parametrar är mer informativa. Exempel på sådana tillämpningar är naturlig språkbehandling och mönsterigenkänning [21] . Algoritmen har en basinlärningshastighet men den multipliceras med elementen i vektorn som är diagonalen för den yttre produktmatrisen $\eta$ $\{G_{j,j}}\}$

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

där , gradient per iteration . Diagonalen ges av $g_{\tau }=\nabla Q_{i}(w)$ $\tau$

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

Denna vektor uppdateras efter varje iteration. Konverteringsformel

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

[a]

eller skriva som omräkning med parametrar,

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

Varje element ger en multiplikator för inlärningshastighet som tillämpas på en parameter . Eftersom nämnaren i denna faktor, , är ℓ2- normen för den föregående derivatan, dämpas stora parameterändringar, medan parametrar som tar emot små förändringar får högre inlärningshastigheter [19] . $\{G_{(i,i)}\}$ $w_{i}$ ${\displaystyle {\sqrt {G_{i))}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2))))$

Även om algoritmen utvecklades för konvexa problem , har AdaGrad framgångsrikt använts för icke-konvex optimering [23] .

RMSProp

RMSProp (från Root Mean Square Propagation ) är en metod där inlärningshastigheten justeras för varje parameter. Tanken är att dela inlärningshastigheten för vikterna med de glidande medelvärdena för de senaste gradienterna för den vikten [24] . Så det första glidande medelvärdet beräknas i termer av rms

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

var, är den glömska faktorn. $\gamma$

Alternativen uppdateras som

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

RMSProp har visat bra anpassning av inlärningshastigheten över olika applikationer. RMSProp kan ses som en generalisering av Rprop . Metoden kan fungera med minipaket, inte bara fullpaket [25] .

Adam

Adam [26] (förkortning av Adaptive Moment Estimation ) är en uppdatering av RMSProp- optimeraren . Denna optimeringsalgoritm använder glidande medelvärden för både gradienterna och de andra momenten av gradienterna. Om parametrarna är givna och förlustfunktionen , där återspeglar indexet för den aktuella iterationen (rapporten börjar med ), ges omräkningen av parametern av Adam-algoritmen av formlerna $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)}\leftarrow w^{(t)}-\eta {\frac ({\hat {m))_{w))({\sqrt ({\hat {v) }}_{w}}}+\epsilon }}

där är en liten additiv som används för att förhindra division med 0, och och är glömskoefficienterna för gradienterna respektive de andra momenten av gradienterna. Kvadrat och kvadratrot beräknas element för element. $\epsilon$ $\beta_{1}$ $\beta _{2}$

Naturlig gradientnedstigning och kSGD

Kalmanbaserad Stokastisk Gradient Descent ( kSGD ) [27] är en online- och offlinealgoritm för inlärning av parametrar för statistiska problem för quasi-likelihood- modeller , som inkluderar linjära modeller , icke-linjära modeller , generaliserade linjära modeller och neurala nätverk med rms-förluster som specialfall. För onlineinlärningsproblem är kSGD ett specialfall av Kalman-filtret för linjära regressionsproblem, ett specialfall av det utökade Kalman-filtret för olinjära regressionsproblem, och kan betraktas som en inkrementell Gauss-Newton- metod . Dessutom, på grund av förhållandet mellan kSGD och Kalman-filtret och förhållandet mellan naturlig gradientnedstigning [28] och Kalman-filtret [29] är kSGD en stor förbättring av den populära metoden för naturlig gradientnedstigning.

Fördelar med kSGD framför andra metoder:

(1) okänslig för antalet tillstånd av problemet, [b] (2) har ett robust urval av hyperparametrar, (3) har ett stoppvillkor.

Nackdelen med kSGD är att algoritmen kräver lagring av en tät kovariansmatris mellan iterationer, och vid varje iteration måste produkten av vektorn och matrisen hittas.

För att beskriva algoritmen antar vi att funktionen , där , definieras genom att använda så att $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)

var är medelvärdesfunktionen (det vill säga det förväntade värdet av ), och är variansfunktionen (det vill säga variansen för ). Därefter ges omräkningen av parametern och omräkningen av den kovarianta matrisen av följande uttryck $\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}}

var finns hyperparametrar. Omräkning kan göra att den kovarianta matrisen blir odefinierad, vilket kan undvikas genom att multiplicera matris med matris. kan vara vilken positiv-definitiv symmetrisk matris som helst, men identitetsmatrisen tas vanligtvis. Som noterats av Patel [27] , för alla problem, förutom linjär regression, krävs upprepade körningar för att säkerställa konvergensen av algoritmen, men inga teoretiska eller implementeringsdetaljer ges. En närbesläktad offline multi-batch-metod för icke-linjär regression, analyserad av Bertsekas [30] , använde glömska faktorn vid omräkning av den kovarianta matrisen för att bevisa konvergens. ${\displaystyle \gamma _{1},\gamma _{2))$ $M(t)$ $M(0)$

Andra ordningens metoder

Det är känt att den stokastiska analogen av den standardiserade (deterministiska) Newton-Raphson-algoritmen (”andra ordningens”-metoden) ger en asymptotiskt optimal eller nästan optimal form av iterativ optimering under förhållanden av stokastisk approximation. En metod som använder den direkta beräkningen av de hessiska matriserna för summatermerna i den empiriska riskfunktionen utvecklades av Bird, Hansen, Nosedal och Singer [31] . En direkt bestämning av de nödvändiga hessiska matriserna för optimering kanske inte är möjlig i praktiken. Praktiska och teoretiska metoder för en andra ordningens version av SGD - algoritmen som inte kräver direkt hessisk information har getts av Spall et al . ). Dessa metoder, även om de inte direkt kräver information om hessian, är baserade antingen på värdena för summatermerna i den empiriska riskfunktionen som anges ovan, eller på värdena för gradienterna för summatermerna (dvs SGD-ingång) . I synnerhet är andra ordningens optimalitet asymptotiskt uppnåbar utan att direkt beräkna de hessiska matriserna för termerna för summan i den empiriska riskfunktionen.

Kommentarer

↑ är den elementära produkten av . $\cirkel$
↑ För ett linjärt regressionsproblem är kSGD:s objektiva funktionsvarians (d.v.s. totalt fel och varians) per iteration lika med sannolikhet som tenderar till 1 med en hastighet som beror på , där är variansen för residualerna. Dessutom, för ett visst val av , kan det visas att kSGD:s iterationsvarians av målfunktionen är lika med sannolikhet som tenderar till 1 med en hastighet som beror på , där är den optimala parametern. $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 även

Koordinatnedstigning - ändrar en koordinat i taget
Linjär klassificerare
Online maskininlärning

Anteckningar

↑ 12 Taddy , 2019 , sid. 303–307.
↑ Bottou, Bousquet, 2012 , sid. 351–368.
↑ Mei, 2018 , sid. E7665–E7671.
↑ Ferguson, 1982 , sid. 831–834.
↑ Bottou, Bousquet, 2008 , sid. 161–168.
↑ Bottou, 1998 .
↑ Kiwiel, 2001 , sid. 1–25.
↑ Robbins, Siegmund, 1971 .
↑ Finkel, Kleeman, Manning, 2008 .
↑ LeCun et al., 2012 , sid. 9-48.
↑ Diaz, Guitton, 2011 , sid. 2804-2808.
↑ Avi Pfeffer. CS181 Föreläsning 5 - Perceptroner (Harvard University) . (obestämd) (inte tillgänglig länk)
↑ Darken, Moody, 1990 .
↑ Spall, 2003 .
↑ Toulis, Airoldi, 2017 , sid. 1694–1727
↑ 1 2 Rumelhart, Hinton, Williams, 1986 , sid. 533–536.
↑ Sutskever, Martens, Dahl, Hinton, 2013 , sid. 1139–1147.
↑ Sutskever, Ilya (2013). Träning av återkommande neurala nätverk (PDF) (Ph.D.). University of Toronto. Arkiverad (PDF) från originalet 2020-02-28 . Hämtad 2020-03-01 . Utfasad parameter används |deadlink=( hjälp )
↑ 1 2 Matthew D. Zeiler (2012), ADADELTA: An adaptive learning rate method, arΧiv : 1212.5701 [cs.LG].
↑ Polyak, Juditsky, 1992 , sid. 838–855.
↑ 1 2 Duchi, Hazan, Singer, 2011 , sid. 2121–2159.
↑ Joseph Perla (2014). Anteckningar om AdaGrad (inte tillgänglig länk) . Hämtad 1 mars 2020. Arkiverad från originalet 30 mars 2015. (obestämd)
↑ Gupta, Bengio, Weston, 2014 , sid. 1461–1492
↑ Tieleman, Tijmen och Hinton, Geoffrey (2012). Föreläsning 6.5-rmsprop: Dela gradienten med ett löpande medelvärde av dess senaste magnitud. KURS: Neurala nätverk för maskininlärning
↑ Hinton, Geoffrey Översikt över mini-batch-gradientnedstigning (länk ej tillgänglig) 27–29. Hämtad 27 september 2016. Arkiverad från originalet 23 november 2016. (obestämd)
↑ Kingma Diederik, Jimmy Ba (2014), Adam: A method for stochastic optimization, arΧiv : 1412.6980 [cs.LG].
↑ 12 Patel , 2016 , sid. 2620–2648.
↑ Cichocki, Chen, Amari, 1997 , sid. 1345–1351.
↑ Ollivier Yann (2017), Online Natural Gradient as a Kalman Filter, arΧiv : 1703.00209 [stat.ML].
↑ Bertsekas, 1996 , sid. 807–822.
↑ Byrd, Hansen, Nocedal, Singer, 2016 , sid. 1008–1031.
↑ Spall, 2000 , sid. 1839−1853.
↑ Spall, 2009 , sid. 1216–1229.
↑ Bhatnagar, Prasad, Prashanth, 2013 .
↑ Ruppert, 1985 , sid. 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 .
songmei. En genomsnittlig fältvy av landskapet av tvålagers neurala nätverk // Proceedings of the National Academy of Sciences . - National Academy of Sciences , 2018. - Vol. 115 , iss. 33 . - doi : 10.1073/pnas.1806579115 . — PMID 30054315 .
Matt Taddy. Stokastisk gradientnedstigning // Business Data Science: Kombinera maskininlärning och ekonomi för att optimera, automatisera och påskynda affärsbeslut. — New York: McGraw-Hill, 2019. — ISBN 978-1-260-45277-8 .
Thomas S. Ferguson. En inkonsekvent uppskattning av maximal sannolikhet // Journal of the American Statistical Association. - 1982. - T. 77 , nr. 380 . - doi : 10.1080/01621459.1982.10477894 . — .
Leon Bottou, Olivier Bousquet. Avvägningarna med storskaligt lärande //Framsteg inom neurala informationsbehandlingssystem . - 2008. - T. 20.

Leon Bottou. Onlinealgoritmer och stokastiska approximationer // Onlineinlärning och neurala nätverk. - Cambridge University Press, 1998. - ISBN 978-0-521-65263-6 .

Krzysztof C. Kiwiel. Konvergens och effektivitet av subgradientmetoder för kvasikonvex 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 konvergenssats för icke-negativa nästan supermartingales och vissa tillämpningar // Optimizing Methods in Statistics / Jagdish S. Rustagi (red.). — Academic Press, 1971.
Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning. Effektiv, funktionsbaserad, villkorlig slumpmässig fältanalys // Proc. Årsmöte för ACL . — 2008.
Yann A. LeCun, Leon Bottou, Genevieve B. Orr, Klaus-Robert Muller. Effektiv ryggstöd // Neurala nätverk: Tricks of the trade / 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. Snabb invertering av full vågform med slumpmässig decimering // SEG Technical Program Expanded Abstracts . — 2011.
Christian Darken, John Moody. Int'l Joint Conf. på neurala nätverk (IJCNN) // Snabb adaptiv k-betyder klustring: några empiriska resultat . — IEEE, 1990.
Spall JC Introduktion till stokastisk sökning och optimering: uppskattning, simulering och kontroll. - Hoboken, NJ: Wiley, 2003. - ISBN 0-471-33052-3 .
Panos Toulis, Edoardo Airoldi. Asymptotiska och finita urvalsegenskaper hos estimatorer baserade på stokastiska gradienter // Annals of Statistics. - 2017. - T. 45 , nr. 4 . - doi : 10.1214/16-AOS1506 . - arXiv : 1408.2923 .
Spall JC Adaptiv Stokastisk Approximation med simultan störningsmetoden // IEEE-transaktioner på automatisk kontroll. - 2000. - T. 45 , nr. 10 . - doi : 10.1109/TAC.2000.880982 .
Spall JC -återkoppling och viktningsmekanismer för att förbättra Jacobian-uppskattningar i den adaptiva simultanförändringsalgoritmen // IEEE-transaktioner på automatisk kontroll. - 2009. - T. 54 , nr. 6 . - doi : 10.1109/TAC.2009.2019793 .
Bhatnagar S., Prasad HL, Prashanth LA Stokastiska rekursiva algoritmer för optimering: Samtidiga störningsmetoder. — London: Springer, 2013. — ISBN 978-1-4471-4284-3 .
Ruppert D. En Newton-Raphson-version av den multivariata Robbins-Monro-proceduren // Annals of Statistics . - 1985. - T. 13 , nr. 1 . doi : 10.1214 / aos/1176346589 .
David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams. Lärande representationer genom bakåtpropagerande fel // Nature . - 1986. - Oktober ( vol. 323 , iss. 6088 ). - doi : 10.1038/323533a0 . - .
Ilya Sutskever, James Martens, George Dahl, Geoffrey E. Hinton. Om vikten av initialisering och momentum i djupinlärning // 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 av stokastisk approximation genom medelvärde // SIAM J. Control Optim.. - 1992. - Vol. 30 , nr. 4 . - doi : 10.1137/0330046 .
John Duchi, Elad Hazan, Yoram Singer. Adaptiva subgradientmetoder för onlineinlärning och stokastisk optimering // JMLR . - 2011. - T. 12 .
Maya R. Gupta, Samy Bengio, Jason Weston. Utbildning av högklassificerare // JMLR. - 2014. - T. 15 , nr. 1 .
Patel V. Kalman-baserad stokastisk gradientmetod med stopptillstånd och okänslighet för konditionering // 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. Stabilitetsanalys av inlärningsalgoritmer för Blind Source Separation // Neurala nätverk. - 1997. - November ( vol. 10 , nummer 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. Incremental Least Squares Methods and the Extended Kalman Filter // SIAM Journal on Optimization. - 1996. - T. 6 , nr. 3 . - S. 807-822 . — ISSN 1052-6234 . - doi : 10.1137/S1052623494268522 .

Läsning för vidare läsning

Dimitri P. Bertsekas. icke-linjär programmering. — 2:a. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 978-1-886529-00-7 . .
Dimitri P. Bertsekas. Konvex analys och optimering. — Athena Scientific, 2003.
Leon Bottou. Stokastiskt lärande // Avancerade föreläsningar om maskininlärning . - Springer, 2004. - T. 3176. - S. 146-168. — (LNAI). - ISBN 978-3-540-23122-6 .
Davidon WC [187–197 Nya minsta kvadratiska 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önsterklassificering. — 2:a. - Wiley , 2000. - ISBN 978-0-471-05669-0 .
Krzysztof C. Kiwiel. Konvergens av approximativa och inkrementella subgradientmetoder för konvex 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äggande optimeringsteori och gradientbaserade algoritmer . - 2. - Springer , 2018. - S. xxvi + 372. - (Springer Optimization and Its Applications Vol. 133). - ISBN 978-3-319-77585-2 .
James C. Spall. Introduktion till Stokastisk sökning och optimering. - Wiley , 2003. - ISBN 978-0-471-33052-3 . .

Länkar

Använder stokastisk gradientnedstigning i C++, Boost, Ublas för linjär regression
Machine Learning Algoritmer
Gradient Descent, hur neurala nätverk lär sig . 3Blue1Brown (16 oktober 2017). (obestämd)