Stochastický gradientní sestup

Stochastický gradient sestup ( SGD ) je iterativní metoda pro optimalizaci objektivní funkce s vhodnými vlastnostmi hladkosti (například diferencovatelnost nebo subdiferencovatelnost ). Lze si to představit jako stochastickou aproximaci optimalizace sestupu gradientu , protože nahrazuje skutečný gradient vypočítaný z úplného souboru dat odhadem vypočítaným z náhodně vybrané podmnožiny dat [1] . Sníží se tak potřebné výpočetní zdroje a pomáhá dosáhnout vyšší iterační rychlosti výměnou za nižší rychlost konvergence [2] . Zvláště velkého efektu je dosaženo v aplikacích souvisejících se zpracováním velkých dat .

Ačkoli základní myšlenka stochastické aproximace sahá až do Robbins-Monroeova algoritmu z 50. let [3] , stochastický gradient sestup se stal důležitou optimalizační technikou ve strojovém učení [1] .

Pozadí

Statistický odhad i strojové učení zvažují problém minimalizace objektivní funkce , která má tvar součtu

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

kde by měla být odhadnuta minimalizace parametru . Každý součtový člen je obvykle spojen s pozorováním v datovém souboru používaném pro trénování. $w$ $Q(w)$ $Qi}$ $i$

V klasické statistice vznikají problémy s minimalizací součtů v metodě nejmenších čtverců a v metodě maximální věrohodnosti (pro nezávislá pozorování). Obecná třída odhadů vznikajících jako minimalizace součtů se nazývá M-estimátory . Již na konci 20. století však bylo zaznamenáno, že požadavek i lokální minimalizace je pro některé problémy metody maximální věrohodnosti příliš restriktivní [4] . Moderní statistici teoretici proto často zvažují stacionární body věrohodnostní funkce (nebo nuly její derivace, skórovací funkce a další metody odhadu rovnic ).

Problém minimalizace součtu také vzniká při minimalizaci empirického rizika . V tomto případě je hodnota ztrátové funkce v -tém příkladu a je to empirické riziko. $Q_{i}(w)$ $i$ $Q(w)$

Při použití k minimalizaci výše uvedené funkce provádí standardní (nebo „dávková“) metoda sestupu gradientu následující iterace:

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

kde je velikost kroku, nazývaná rychlost učení ve strojovém učení. $\eta$

V mnoha případech mají sčítací funkce jednoduchý tvar, který umožňuje nízkonákladové výpočty součtu funkcí a gradientu součtu. Například ve statistice umožňuje použití jednoparametrových exponenciálních rodin ekonomický výpočet funkce a gradientu.

V jiných případech však může výpočet gradientu součtu vyžadovat nákladné výpočty gradientu pro všechny sčítatelné funkce. Na velké trénovací množině se při absenci jednoduchých vzorců stává výpočet součtů gradientů velmi nákladným, protože výpočet gradientu součtu vyžaduje výpočet gradientů jednotlivých členů součtu. Aby se snížilo množství výpočtů, stochastický gradientní sestup vybírá podmnožinu sčítatelných funkcí při každé iteraci algoritmu. Tento přístup je zvláště účinný u velkých problémů strojového učení [5] .

Iterační metoda

Při stochastickém („online“) gradientovém sestupu je skutečný gradient aproximován gradientem jednoho tréninkového příkladu $Q(w)$

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

Algoritmus prochází trénovací sadou a provádí výše uvedený přepočet pro každý příklad trénování. K dosažení konvergence algoritmu může trvat několik průchodů trénovací datovou sadou. Před každým novým průchodem jsou data v sadě zamíchána, aby se eliminovala možnost zacyklení algoritmu. Typické implementace mohou využívat adaptivní rychlost učení zlepšení konvergence.

V pseudokódu lze stochastický sestup gradientu reprezentovat následovně:

Vyberte vektor počátečního parametru a rychlost učení . $w$ $\eta$
Opakujte, dokud nedosáhnete přibližného minima:
- Náhodně zamíchejte příklady v tréninkové sadě.
- Naplnit _ $i=1,2,...,n$
  - $\!w:=w-\eta \nabla Q_{i}(w).$

Kompromisem mezi výpočtem skutečného gradientu a gradientu v rámci jednoho tréninkového příkladu může být výpočet gradientu z více než jednoho tréninkového příkladu, nazývaného "mini-dávka", v každém kroku. To může být výrazně lepší než popsaný "skutečný" stochastický gradientní sestup, protože kód může v každém kroku používat knihovny vektorových tvarů namísto samostatných výpočtů. Může také vést k hladší konvergenci, protože gradient vypočítaný v každém kroku je zprůměrován z více příkladů školení.

Konvergence sestupu stochastického gradientu byla analyzována pomocí teorií konvexní minimalizace a stochastické aproximace . Ve zjednodušené formě lze výsledek znázornit takto: když se míra učení snižuje vhodnou rychlostí, za předpokladu relativně slabých předpokladů, stochastický gradient sestupu konverguje téměř jistě ke globálnímu minimu, pokud je cílová funkce konvexní nebo pseudokonvexní . jinak metoda téměř jistě konverguje k lokálnímu minimu [6] [7] . Ve skutečnosti je to důsledek Robbins-Sigmundovy věty [8] . $\eta$

Příklad

Předpokládejme, že chceme aproximovat přímku pomocí trénovací množiny s mnoha pozorováními a odpovídajícími odpověďmi pomocí metody nejmenších čtverců . Cílová funkce pro minimalizaci bude ${\hat {y}}=\!w_{1}+w_{2}x$ $(x_{1},x_{2},\ldots ,x_{n})$ $({\klobouk {y_{1}}},{\klobouk {y_{2}}},\ldots ,{\klobouk {y_{n}}})$

Q(w)=\sum _{i=1}^{n}Q_{i}(w)=\sum _{i=1}^{n}\left({\hat {y_{i }}}-y_{i}\right)^{2}=\součet _{i=1}^{n}\left(w_{1}+w_{2}x_{i}-y_{i}\ správně)^{2}.

Poslední řádek ve výše uvedeném pseudokódu pro úlohu se stane

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

Všimněte si, že v každé iteraci (která se také nazývá převzorkování) se počítá pouze gradient v jednom bodě namísto výpočtu přes sadu všech vzorků. $x_i$

Klíčový rozdíl oproti standardnímu (dávkovému) sestupu gradientu spočívá v tom, že v každém kroku je použita pouze jedna část dat z celé sady a tato část je v každém kroku vybrána náhodně.

Pozoruhodné aplikace

Stochastický gradient sestup je oblíbeným algoritmem pro trénování široké škály modelů ve strojovém učení , zejména v (lineárních) podpůrných vektorových strojích , v logistické regresi (viz například Vowpal Wabbit ) a v grafových pravděpodobnostních modelech [9] . V kombinaci s algoritmem backpropagation je to de facto standardní algoritmus pro trénování umělých neuronových sítí [10] . Jeho aplikace byla také viděna v geofyzikální komunitě, zejména pro aplikace Full Waveform Inversion (FWI) [11] .

Stochastický gradientový sestup konkuruje algoritmu L-BFGS , který je také široce používán. Stochastický gradient sestup se používá minimálně od roku 1960 k trénování lineárních regresních modelů pod názvem ADALINE [12] .

Dalším stochastickým algoritmem sestupu gradientu je adaptivní filtr nejmenších čtverců [ ( LMS) .

Odrůdy a modifikace

Existuje mnoho modifikací algoritmu sestupu stochastického gradientu. Zejména ve strojovém učení je problémem volba rychlosti učení (velikost kroku): při velkém kroku se může algoritmus rozcházet a při malém kroku je konvergence příliš pomalá. K vyřešení tohoto problému můžete použít plán rychlosti učení , kde rychlost učení klesá s rostoucím číslem iterace . Zároveň se při prvních iteracích hodnoty parametrů výrazně mění a při pozdějších iteracích se pouze zpřesňují. Takové rozvrhy jsou známy již od McQueenovy práce na shlukování k -means [ 13] . Některé praktické rady ohledně výběru kroku v některých variantách SGD jsou uvedeny v oddílech 4.4, 6.6 a 7.5 Spall (2003) [14] . $\eta _{t}$ $t$

Implicitní změny (ISGD)

Jak již bylo zmíněno dříve, klasický stochastický gradientový sestup je obvykle citlivý na rychlost učení . Rychlá konvergence vyžaduje vysokou rychlost učení, ale to může způsobit numerickou nestabilitu . Problém lze vyřešit především [15] zohledněním implicitní změny v , kdy se stochastický gradient přepočítává při další iteraci, a ne při aktuální. $\eta$

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

Tato rovnost je implicitní, protože se objevuje na obou stranách rovnosti. Toto je stochastická forma metody proximálního gradientu , protože přepočet lze vyjádřit jako $w^{new}$

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

Jako příklad zvažte metodu nejmenších čtverců s vlastnostmi a pozorováními . Chceme se rozhodnout: ${\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},

kde znamená skalární součin . ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p))$

Všimněte si, že může mít jako první prvek "1". Klasický stochastický gradient sestup funguje takto $X$

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

kde je rovnoměrně rozloženo mezi 1 a . Zatímco teoreticky tento postup konverguje za relativně mírných předpokladů, v praxi může být postup značně nestabilní. Zejména pokud jsou nastaveny nesprávně, pak mají s vysokou pravděpodobností velké absolutní vlastní hodnoty a postup se může lišit v několika iteracích. Naproti tomu implicitní stochastický gradient sestup ( ISGD ) může být vyjádřen jako $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}.

Procedura zůstane numericky stabilní pro téměř všechny , protože rychlost učení je nyní normalizována. Takové srovnání mezi klasickým a explicitním stochastickým gradientem sestupu v metodě nejmenších čtverců je velmi podobné srovnání mezi filtrem nejmenších čtverců ( anglicky nejmenší průměr čtverců , LMS) a normalizovaným filtrem nejmenších čtverců ( anglicky normalized filtr nejmenších středních čtverců , NLM). $\eta$

Ačkoli analytické řešení pro ISGD je možné pouze metodou nejmenších čtverců, postup lze efektivně implementovat v široké škále modelů. Konkrétně předpokládejme, že to závisí na pouze jako lineární kombinace vlastností , takže můžeme psát , kde funkce s reálnou hodnotou může záviset na , ale ne přímo, pouze přes . Metoda nejmenších čtverců tuto podmínku splňuje, a proto logistická regrese a většina zobecněných lineárních modelů tuto podmínku splňují . Například v nejmenších čtvercích a v logistické regresi , kde je logistická funkce . V Poissonově regresi a tak dále. $Q_{i}(w)$ $w$ $x_{i}$ ${\displaystyle \nabla _{w}Q_{i}(š)=-q(x_{i}'š)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))$

Za takových podmínek lze ISGD snadno implementovat následovně. Nechť , kde je číslo. Pak je ISGD ekvivalentní $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 }).

Faktor měřítka lze nalézt pomocí půlení , protože ve většině modelů, jako jsou výše uvedené zobecněné lineární modely, se funkce snižuje a pak hranice hledání bude . $\xi ^{\ast }\in \mathbb {R}$ $q$ ${\displaystyle \xi ^{\ast ))$ $[\min(0,f(0)),\max(0,f(0))]$

Impuls

Novější vývoj zahrnuje metodu hybnosti , která se objevila v práci Rumelharta , Hintona a Williamse o učení zpětného šíření [16] . Stochastický gradient hybnosti sestup si pamatuje změnu při každé iteraci a určuje další změnu jako lineární kombinaci gradientu a předchozí změny [17] [18] : $\Delta w$

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

w:=w+\Delta w

to vede k

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

kde parametr , který minimalizuje , by měl být odhadnut a je velikost kroku (někdy nazývaná rychlost učení ve strojovém učení). $w$ $Q(w)$ $\eta$

Název "hybnost" pochází z hybnosti ve fyzice - vektor hmotnosti , chápaný jako dráha částice podél prostoru parametrů [16] , zažívá zrychlení z gradientu ztrátové funkce (" síla "). Na rozdíl od klasického sestupu stochastického gradientu se metoda snaží udržet pokrok ve stejném směru tím, že zamezí kolísání. Momentum bylo úspěšně používáno počítačovými vědci k trénování umělých neuronových sítí po několik desetiletí [19] . $w$

Průměrování

Průměrný stochastický gradientový sestup , vyvinutý nezávisle Ruppertem a Polyakem na konci 80. let, je konvenční stochastický gradientní sestup, který zaznamenává střední hodnotu vektoru parametrů. To znamená, že přepočet je stejný jako u obvyklé metody stochastického gradientu, ale algoritmus také sleduje [20]

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

Když je optimalizace dokončena, vektor středních parametrů zaujme místo w .

AdaGrad

AdaGrad (adaptive gradient algorithm ), publikovaný v roce 2011 [21] [22] , je modifikací stochastického gradientového sestupového algoritmu se samostatnou rychlostí učení pro každý parametr . Neformálně to zvyšuje rychlost učení pro parametry s řídkými daty a snižuje rychlost učení pro parametry s méně řídkými daty. Tato strategie zvyšuje rychlost konvergence ve srovnání se standardní metodou stochastického gradientu v podmínkách, kdy jsou data řídká a odpovídající parametry jsou informativnější. Příklady takových aplikací jsou zpracování přirozeného jazyka a rozpoznávání vzorů [21] . Algoritmus má základní rychlost učení , ale je vynásoben prvky vektoru , který je úhlopříčkou matice vnějšího produktu . $\eta$ $\{G_{j,j}}\}$

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

kde , gradient na iteraci . Úhlopříčka je dána $g_{\tau }=\nabla Q_{i}(w)$ $\tau$

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

Tento vektor je aktualizován po každé iteraci. Konverzní vzorec

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

[A]

nebo zápis jako přepočet podle parametrů,

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

Každý prvek poskytuje multiplikátor rychlosti učení aplikovaný na jeden parametr . Protože jmenovatel v tomto faktoru, , je ℓ2 norma předchozí derivace, velké změny parametrů jsou zeslabeny, zatímco parametry, které přijímají malé změny, mají vyšší rychlost učení [19] . $\{G_{(i,i)}\}$ $w_{i}$ ${\displaystyle {\sqrt {G_{i))}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2))))$

Přestože byl algoritmus vyvinut pro konvexní problémy , AdaGrad byl úspěšně použit pro nekonvexní optimalizaci [23] .

RMSProp

RMSProp (z Root Mean Square Propagation ) je metoda, ve které je rychlost učení upravena pro každý parametr. Cílem je vydělit rychlost učení pro váhy klouzavými průměry nedávných gradientů pro tuto váhu [24] . První klouzavý průměr se tedy vypočítá z hlediska efektivní hodnoty

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

kde je faktor zapomínání. $\gamma$

Možnosti jsou aktualizovány jako

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

RMSProp prokázal dobrou adaptaci rychlosti učení napříč různými aplikacemi. RMSProp lze považovat za zobecnění Rprop . Metoda je schopna pracovat s minibalíčky, nejen s plnými balíčky [25] .

Adam

Adam [26] (zkratka pro Adaptive Moment Estimation ) je aktualizací optimalizátoru RMSProp . Tento optimalizační algoritmus používá klouzavé průměry jak gradientů, tak druhých momentů gradientů. Pokud jsou zadány parametry , a ztrátová funkce , kde odráží index aktuální iterace (sestava začíná ), je přepočet parametru algoritmem Adam dán vzorci $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 }}

kde je malá přísada použitá k zabránění dělení 0 a a jsou koeficienty zapomínání pro gradienty a druhé momenty gradientů. Druhá mocnina a druhá odmocnina se počítají prvek po prvku. $\epsilon$ $\beta_{1}$ $\beta _{2}$

Přirozený gradient sestup a kSGD

Kalman- based Stochastic Gradient Descent ( kSGD ) [27] je online a offline algoritmus pro učení parametrů pro statistické problémy pro modely kvazi věrohodnosti , který zahrnuje lineární modely , nelineární modely , zobecněné lineární modely a neuronové sítě se ztrátami rms jako zvláštní případ. Pro online výukové problémy je kSGD speciální případ Kalmanova filtru pro lineární regresní problémy, speciální případ rozšířeného Kalmanova filtru pro nelineární regresní problémy a lze jej považovat za inkrementální Gauss-Newtonovu metodu . Navíc díky vztahu kSGD ke Kalmanovu filtru a vztahu přirozeného gradientu sestupu [28] ke Kalmanovu filtru [29] je kSGD hlavním vylepšením populární metody přirozeného gradientu sestupu.

Výhody kSGD oproti jiným metodám:

(1) necitlivé na počet podmínek problému, [b] (2) má velký výběr hyperparametrů, (3) má podmínku zastavení.

Nevýhodou kSGD je, že algoritmus vyžaduje ukládání husté kovarianční matice mezi iteracemi a při každé iteraci musí být nalezen součin vektoru a matice.

Pro popis algoritmu předpokládáme, že funkce , kde , je definována pomocí tak, že $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)

kde je funkce průměrování (tj. očekávaná hodnota ) a je rozptylová funkce (tj. rozptyl pro ). Potom přepočet parametru a přepočet kovariantní matice jsou dány následujícími výrazy $\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}}

kde jsou hyperparametry. Přepočet může způsobit, že se kovariantní matice stane nedefinovanou, čemuž se lze vyhnout vynásobením matice maticí. může být jakákoli pozitivně definitní symetrická matice, ale obvykle se bere matice identity. Jak poznamenává Patel [27] , pro všechny problémy, kromě lineární regrese, jsou vyžadovány opakované běhy, aby se zajistila konvergence algoritmu, ale nejsou uvedeny žádné teoretické nebo implementační podrobnosti. Úzce související offline vícedávková metoda pro nelineární regresi, kterou analyzoval Bertsekas [30] , používala faktor zapomínání při přepočítávání kovariantní matice k prokázání konvergence. ${\displaystyle \gamma _{1},\gamma _{2))$ $M(t)$ $M(0)$

Metody druhého řádu

Je známo, že stochastická analogie standardního (deterministického) Newton-Raphsonova algoritmu (metoda „druhého řádu“) poskytuje asymptoticky optimální nebo téměř optimální formu iterativní optimalizace za podmínek stochastické aproximace. Bird, Hansen, Nosedal a Singer [31] vyvinuli metodu, která využívá přímého výpočtu Hessových matic součtových členů v empirické rizikové funkci . Přímé stanovení požadovaných Hessových matic pro optimalizaci však nemusí být v praxi možné. Praktické a teoreticky vyhlížející metody pro verzi SGD algoritmu druhého řádu, která nevyžaduje přímou Hessovu informaci, uvedl Spall et al . ). Tyto metody, i když přímo nevyžadují informace o Hessianu, jsou založeny buď na hodnotách součtových členů ve výše uvedené empirické rizikové funkci, nebo na hodnotách gradientů součtových členů (tj. vstup SGD) . Zejména optimalita druhého řádu je asymptoticky dosažitelná bez přímého výpočtu Hessových matic členů součtu v empirické rizikové funkci.

Komentáře

↑ je elementární součin . $\circ$
↑ Pro problém lineární regrese je rozptyl objektivní funkce kSGD (tj. celková chyba a rozptyl) na iteraci roven pravděpodobnosti klesající k 1 při rychlosti závislé na , kde je rozptyl reziduí. Navíc, pro konkrétní volbu , lze ukázat, že iterační rozptyl kSGD účelové funkce je roven pravděpodobnosti inklinující k 1 při rychlosti závislé na , kde je optimální parametr. $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_{*}$

Viz také

Sestup souřadnic – mění vždy jednu souřadnici
Lineární klasifikátor
Online strojové učení

Poznámky

↑ 12 Taddy , 2019 , str. 303–307.
↑ Bottou, Bousquet, 2012 , str. 351–368.
↑ Mei, 2018 , str. E7665–E7671.
↑ Ferguson, 1982 , s. 831–834.
↑ Bottou, Bousquet, 2008 , str. 161–168.
↑ Bottou, 1998 .
↑ Kiwiel, 2001 , str. 1–25.
↑ Robbins, Siegmund, 1971 .
↑ Finkel, Kleeman, Manning, 2008 .
↑ LeCun a kol., 2012 , str. 9-48.
↑ Diaz, Guitton, 2011 , str. 2804-2808.
↑ Avi Pfeffer. CS181 Přednáška 5 - Perceptrony (Harvard University) . (neurčitý) (nedostupný odkaz)
↑ Darken, Moody, 1990 .
↑ Spall, 2003 .
↑ Toulis, Airoldi, 2017 , str. 1694–1727
↑ 1 2 Rumelhart, Hinton, Williams, 1986 , str. 533–536.
↑ Sutskever, Martens, Dahl, Hinton, 2013 , str. 1139–1147.
↑ Sutskever, Ilya (2013). Školení rekurentních neuronových sítí (PDF) (Ph.D.). University of Toronto. Archivováno (PDF) z originálu dne 28.02.2020 . Staženo 2020-03-01 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ 1 2 Matthew D. Zeiler (2012), ADADELTA: Metoda adaptivní rychlosti učení, arΧiv : 1212.5701 [cs.LG].
↑ Polyak, Juditsky, 1992 , s. 838–855.
↑ 1 2 Duchi, Hazan, Singer, 2011 , str. 2121–2159.
↑ Joseph Perla (2014). Poznámky k AdaGrad (nedostupný odkaz) . Získáno 1. března 2020. Archivováno z originálu dne 30. března 2015. (neurčitý)
↑ Gupta, Bengio, Weston, 2014 , str. 1461–1492
↑ Tieleman, Tijmen a Hinton, Geoffrey (2012). Přednáška 6,5-rmsprop: Vydělte gradient klouzavým průměrem jeho aktuální velikosti. KURZ: Neuronové sítě pro strojové učení
↑ Hinton, Geoffrey Přehled minidávkového gradientového sestupu (odkaz není k dispozici) 27.–29. Získáno 27. září 2016. Archivováno z originálu 23. listopadu 2016. (neurčitý)
↑ Kingma Diederik, Jimmy Ba (2014), Adam: Metoda pro stochastickou optimalizaci, arΧiv : 1412.6980 [cs.LG].
↑ 12 Patel , 2016 , str. 2620–2648.
↑ Cichocki, Chen, Amari, 1997 , str. 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 , str. 1008–1031.
↑ Spall, 2000 , str. 1839–1853.
↑ Spall, 2009 , str. 1216–1229.
↑ Bhatnagar, Prasad, Prashanth, 2013 .
↑ Ruppert, 1985 , str. 236–245.

Literatura

Leon Bottou, Olivier Bousquet. The Tradeoffs of Large Scale Learning // Optimalizace pro strojové učení / Suvrit Sra, Sebastian Nowozin, Stephen J. Wright (ed.). - Cambridge: MIT Press, 2012. - ISBN 978-0-262-01646-9 .
songmei. Střední pohled na krajinu dvouvrstvých neuronových sítí // Proceedings of the National Academy of Sciences . - Národní akademie věd , 2018. - Sv. 115 , iss. 33 . - doi : 10.1073/pnas.1806579115 . — PMID 30054315 .
Matt Taddy. Stochastic Gradient Descent // Věda o obchodních datech: Kombinace strojového učení a ekonomiky k optimalizaci, automatizaci a urychlení obchodních rozhodnutí. — New York: McGraw-Hill, 2019. — ISBN 978-1-260-45277-8 .
Thomas S. Ferguson. Nekonzistentní odhad maximální pravděpodobnosti // Journal of the American Statistical Association. - 1982. - T. 77 , čís. 380 . - doi : 10.1080/01621459.1982.10477894 . — .
Leon Bottou, Olivier Bousquet. Kompromisy učení ve velkém měřítku //Pokroky v systémech zpracování neuronových informací . - 2008. - T. 20.

Leon Bottou. Online algoritmy a stochastické aproximace // Online učení a neuronové sítě. - Cambridge University Press, 1998. - ISBN 978-0-521-65263-6 .

Krzysztof C. Kiwiel. Konvergence a účinnost subgradientových metod pro kvazikonvexní minimalizaci // Mathematical Programming, Series A. - Berlin, Heidelberg: Springer, 2001. - Vol.90 , no . 1 . — S. 1–25. — ISSN 0025-5610 . - doi : 10.1007/PL00011414 .
Herbert Robbins, David O. Siegmund. Konvergenční teorém pro nezáporné téměř supermartingaly a některé aplikace // Optimalizační metody ve statistice / Jagdish S. Rustagi (ed.). — Academic Press, 1971.
Jenny Rose Finkelová, Alex Kleeman, Christopher D. Manning. Efektivní podmíněná analýza náhodného pole založená na funkcích // Proc. Výroční zasedání ACL . — 2008.
Yann A. LeCun, Leon Bottou, Genevieve B. Orr, Klaus-Robert Muller. Efektivní backprop // Neuronové sítě: Obchodní triky / Grégoire Montavon, Geneviève B. Orr, Klaus-Robert Müller (Eds.). - Berlin Heidelberg: Springer, 2012. - T. 7700. - (Poznámky k přednáškám z informatiky). - ISBN 978-3-642-35288-1 .
Esteban Diaz, Antoine Guitton. Rychlá plná inverze tvaru vlny s náhodnou decimací // SEG Technical Program Expanded Abstracts . — 2011.
Christian Darken, John Moody. Mezinárodní společná konference o neuronových sítích (IJCNN) // Rychlé adaptivní shlukování k-means: některé empirické výsledky . — IEEE, 1990.
Spall JC Úvod do Stochastického vyhledávání a optimalizace: Odhad, simulace a řízení. - Hoboken, NJ: Wiley, 2003. - ISBN 0-471-33052-3 .
Panos Toulis, Edoardo Airoldi. Asymptotické a konečné-výběrové vlastnosti odhadů založených na stochastických gradientech // Annals of Statistics. - 2017. - T. 45 , no. 4 . - doi : 10.1214/16-AOS1506 . - arXiv : 1408.2923 .
Adaptivní stochastická aproximace Spall JC metodou simultánní poruchy // Transakce IEEE na automatickém řízení. - 2000. - T. 45 , no. 10 . - doi : 10.1109/TAC.2000.880982 .
Zpětná vazba a váhové mechanismy Spall JC pro zlepšení jakobiánských odhadů v algoritmu adaptivních simultánních poruch // Transakce IEEE na automatickém řízení. - 2009. - T. 54 , č. 6 . - doi : 10.1109/TAC.2009.2019793 .
Bhatnagar S., Prasad HL, Prashanth LA Stochastické rekurzivní algoritmy pro optimalizaci: metody simultánní poruchy. — London: Springer, 2013. — ISBN 978-1-4471-4284-3 .
Ruppert D. Newton-Raphsonova verze mnohorozměrné Robbins-Monro procedury // Annals of Statistics . - 1985. - T. 13 , no. 1 . doi : 10.1214 / aos/1176346589 .
David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams. Učení reprezentací zpětným šířením chyb // Nature . - 1986. - říjen ( sv. 323 , vyd. 6088 ). - doi : 10.1038/323533a0 . - .
Ilya Sutskever, James Martens, George Dahl, Geoffrey E. Hinton. O důležitosti inicializace a hybnosti v hlubokém učení // In Proceedings of the 30th international conference on machine learning (ICML-13) / Sanjoy Dasgupta, David Mcallester (ed.). - Atlanta, GA, 2013. - T. 28.
Boris T. Polyak, Anatoli B. Juditsky. Akcelerace stochastické aproximace průměrováním // SIAM J. Control Optim.. - 1992. - Vol.30 , no. 4 . - doi : 10.1137/0330046 .
John Duchi, Elad Hazan, Yoram Singer. Adaptivní subgradientní metody pro online učení a stochastickou optimalizaci // JMLR . - 2011. - T. 12 .
Maya R. Gupta, Samy Bengio, Jason Weston. Školení vysoce multiclass klasifikátorů // JMLR. - 2014. - T. 15 , no. 1 .
Patel V. Kalmanova metoda stochastického gradientu se stop podmínkou a necitlivostí na kondici // SIAM Journal on Optimization. - 2016. - T. 26 , no. 4 . — ISSN 1052-6234 . - doi : 10.1137/15M1048239 . - arXiv : 1512.01139 .
Cichocki A., Chen T., Amari S. Analýza stability algoritmů učení pro oddělení slepých zdrojů // Neuronové sítě. - 1997. - Listopad ( díl 10 , číslo 8 ). - doi : 10.1016/S0893-6080(97)00039-7 . — PMID 12662478 .
Byrd RH, Hansen SL, Nocedal J., Singer Y. 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. Přírůstkové metody nejmenších čtverců a rozšířený Kalmanův filtr // SIAM Journal on Optimization. - 1996. - T. 6 , no. 3 . - S. 807-822 . — ISSN 1052-6234 . - doi : 10.1137/S1052623494268522 .

Čtení pro další čtení

Dimitri P. Bertsekas. nelineární programování. — 2. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 978-1-886529-00-7 . .
Dimitri P. Bertsekas. Konvexní analýza a optimalizace. — Athena Scientific, 2003.
Leon Bottou. Stochastické učení // Pokročilé přednášky o strojovém učení . - Springer, 2004. - T. 3176. - S. 146-168. — (LNAI). - ISBN 978-3-540-23122-6 .
Davidon WC [187–197 Nové algoritmy nejmenších čtverců] // Journal of Optimization Theory and Applications. - 1976. - T. 18 , č. 2 . - doi : 10.1007/BF00935703 .
Richard O. Duda, Peter E. Hart, David G. Stork. klasifikace vzorů. — 2. - Wiley , 2000. - ISBN 978-0-471-05669-0 .
Krzysztof C. Kiwiel. Konvergence přibližných a přírůstkových metod subgradientu pro konvexní optimalizaci // SIAM Journal on Optimization. - 2004. - T. 14 , č. 3 . - S. 807-840 . - doi : 10.1137/S1052623400376366 .
Jan A. Snyman, Daniel N. Wilke. Praktická matematická optimalizace – základní teorie optimalizace a gradientově založené algoritmy . - 2. - Springer , 2018. - S. xxvi + 372. - (Springerova optimalizace a její aplikace sv. 133). - ISBN 978-3-319-77585-2 .
James C. Spall. Úvod do Stochastického vyhledávání a optimalizace. - Wiley , 2003. - ISBN 978-0-471-33052-3 . .

Odkazy

Použití stochastického sestupu gradientu v C++, Boost, Ublas pro lineární regresi
Algoritmy strojového učení
Gradient Descent, Jak se učí neuronové sítě . 3Blue1Brown (16. října 2017). (neurčitý)