Sztochasztikus gradiens süllyedés

A sztochasztikus gradiens süllyedés ( SGD ) egy iteratív módszer egy célfüggvény optimalizálására megfelelő simasági tulajdonságokkal (például differenciálhatóság vagy szubdifferenciálhatóság ). Felfogható a gradiens süllyedésének optimalizálásának sztochasztikus közelítésének , mivel a teljes adatkészletből számított tényleges gradienst az adatok véletlenszerűen kiválasztott részhalmazából számított becsléssel helyettesíti [1] . Ez csökkenti a felhasznált számítási erőforrásokat , és elősegíti a magasabb iterációs ráta elérését alacsonyabb konvergencia rátákért cserébe [2] . Különösen nagy hatás érhető el a big data feldolgozásával kapcsolatos alkalmazásokban .

Bár a sztochasztikus közelítés alapötlete az 1950-es évek Robbins-Monroe algoritmusára nyúlik vissza [3] , a sztochasztikus gradiens süllyedés a gépi tanulás fontos optimalizálási technikájává vált [1] .

Háttér

Mind a statisztikai becslés , mind a gépi tanulás figyelembe veszi az összeg formájú célfüggvény minimalizálásának problémáját

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

ahol a paraméterminimalizálást meg kell becsülni . Minden összegtag általában a betanításhoz használt található [ en] megfigyeléshez kapcsolódik . $w$ $Q(w)$ $Q_{i}$ $én$

A klasszikus statisztikában összegminimalizálási problémák merülnek fel a legkisebb négyzetek módszerénél és a maximum likelihood módszernél (független megfigyeléseknél). Az összegek minimalizálásaként létrejövő becslések általános osztályát M-becslésnek nevezzük . Azonban már a 20. század végén észrevették, hogy az egyenletes lokális minimalizálás követelménye túlságosan korlátozó a maximum likelihood módszer egyes problémáinál [4] . Ezért a modern statisztikai teoretikusok gyakran figyelembe veszik a likelihood-függvény stacionárius pontjait (vagy deriváltjának nulláit, a pontozási függvényt és az egyenletek egyéb becslési módszereit ).

Az empirikus kockázat minimalizálása során is felmerül az összegminimalizálási probléma . Ebben az esetben a veszteségfüggvény értéke a -edik példában, és az empirikus kockázat. $Q_{i}(w)$ $én$ $Q(w)$

Ha a fenti függvény minimalizálására használják, a szabványos (vagy "kötegelt") gradiens süllyedési módszer a következő iterációkat hajtja végre:

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

hol van a lépésméret, amelyet tanulási sebességnek neveznek a gépi tanulásban. $\eta$

Az összegezhető függvények sok esetben egyszerű formájúak, ami lehetővé teszi a függvények összegének és az összeg gradiensének olcsó számítását. Például a statisztikákban az egyparaméteres exponenciális családok használata lehetővé teszi a függvény és a gradiens gazdaságos kiszámítását.

Más esetekben azonban az összeg gradiensének kiszámítása költséges gradiens-számításokat igényelhet minden összeadható függvény esetében. Egy nagy képzési halmaznál egyszerű képletek híján a gradiensek összegének kiszámítása nagyon költségessé válik, mivel az összeg gradiensének kiszámításához az összeg egyes tagjainak gradienseit kell kiszámítani. A számítás mennyiségének csökkentése érdekében a sztochasztikus gradiens süllyedés az algoritmus minden iterációjában kiválasztja az összegezhető függvények egy részhalmazát. Ez a megközelítés különösen hatékony nagy gépi tanulási problémák esetén [5] .

Iteratív módszer

Sztochasztikus („online”) gradiens süllyedés esetén a valódi gradienst egy képzési példa gradiensével közelítjük $Q(w)$

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

A betanítási halmazt végigfutva az algoritmus minden egyes betanítási példánál elvégzi a fenti újraszámítást. Az algoritmus konvergenciájának eléréséhez több lépésre is szükség lehet a betanítási adatkészleten. Minden új lépés előtt a készletben lévő adatok megkeverednek, hogy kizárják az algoritmus hurkolásának lehetőségét. A tipikus megvalósítások alkalmazkodó tanulási sebességet használhatnak konvergencia javítására.

A pszeudokódban a sztochasztikus gradiens süllyedés a következőképpen ábrázolható:

Válasszon ki egy kezdeti paramétervektort és egy tanulási sebességet . $w$ $\eta$
Ismételje addig, amíg el nem éri a hozzávetőleges minimumot:
- Véletlenszerűen keverje össze a példákat a képzési készletben.
- teljesíteni _ $i=1,2,...,n$
  - $\!w:=w-\eta \nabla Q_{i}(w).$

A valódi gradiens és a gradiens egyetlen betanítási példán keresztüli kiszámítása közötti kompromisszum lehet, ha a gradienst egynél több betanítási példában, úgynevezett "mini kötegben" számítjuk ki. Ez lényegesen jobb lehet, mint a leírt "igazi" sztochasztikus gradiens süllyedés, mivel a kód használhat vektor alakzat könyvtárakat ahelyett, hogy minden lépésben külön számításokat végezne. Ez simább konvergenciát is eredményezhet, mivel az egyes lépéseknél kiszámított gradienst több tanítási példa alapján átlagolják.

A sztochasztikus gradiens süllyedés konvergenciáját a konvex minimalizálás és a sztochasztikus közelítés elméletek segítségével elemeztük . Egyszerűsített formában az eredmény a következőképpen ábrázolható: ha a tanulási sebesség megfelelő ütemben csökken, viszonylag gyenge feltételezések mellett a sztochasztikus gradiens süllyedés szinte biztosan konvergál a globális minimumhoz, ha a célfüggvény konvex vagy pszeudokonvex , egyébként a módszer szinte biztosan konvergál a lokális minimumhoz [6] [7] . Valójában ez a Robbins-Sigmund tétel [8] következménye . $\eta$

Példa

Tegyük fel, hogy a legkisebb négyzetek módszerével szeretnénk közelíteni egy egyenest egy sok megfigyelést és megfelelő választ tartalmazó tanító halmaz segítségével . A minimalizálás célfüggvénye az lesz ${\hat {y}}=\!w_{1}+w_{2}x$ $(x_{1},x_{2},\ldots ,x_{n})$ $({\kalap {y_{1}}},{\kalap {y_{2}}},\ldots ,{\kalap {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}\ jobbra)^{2}.

A feladat fenti pszeudokódjának utolsó sora ez lesz

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

Vegye figyelembe, hogy minden iterációban (amelyet újramintavételezésnek is neveznek) csak az egyik pont gradiense kerül kiszámításra, ahelyett, hogy az összes minta halmazán keresztül számolnánk. $x_i$

A legfontosabb különbség a szabványos (kötegelt) gradiens süllyedéshez képest az, hogy a teljes halmaz adatainak csak egy része kerül felhasználásra minden lépésben, és ezt a részt véletlenszerűen választják ki minden lépésben.

Nevezetes alkalmazások

A sztochasztikus gradiens süllyedés egy népszerű algoritmus modellek széles skálájának betanítására a gépi tanulásban , különösen a (lineáris) támogató vektorgépekben , a logisztikus regresszióban (lásd például a Vowpal Wabbit ) és a gráf valószínűségi modellekben [9] . A backpropagation algoritmussal kombinálva ez a de facto szabványos algoritmus a mesterséges neurális hálózatok betanításához [10] . Alkalmazása a geofizikai közösségben is megjelent, különösen a Full Waveform Inversion (FWI) alkalmazásokban [11] .

A sztochasztikus gradiens süllyedés versenyez a szintén széles körben használt L-BFGS A sztochasztikus gradiens süllyedés legalább 1960 óta használatos lineáris regressziós modellek képzésére ADALINE [12] néven .

Egy másik sztochasztikus gradiens süllyedési algoritmus a legkisebb négyzetek adaptív szűrője [ ( LMS) .

Fajták és módosítások

A sztochasztikus gradiens süllyedés algoritmusának számos módosítása van. A gépi tanulásban különösen a tanulási sebesség (lépésméret) megválasztása okoz problémát: nagy lépésnél az algoritmus eltérhet, kis lépésnél pedig túl lassú a konvergencia. A probléma megoldásához használhatja a tanulási ütem ütemezését , ahol a tanulási sebesség az iterációszám növekedésével csökken . Ugyanakkor az első iterációknál a paraméterek értékei jelentősen megváltoznak, a későbbi iterációknál pedig csak finomodnak. Az ilyen ütemezések McQueen k - means klaszterezéssel foglalkozó munkája óta ismertek [ 13] . Néhány gyakorlati tanácsot ad néhány SGD-változat lépéseinek kiválasztásához Spall (2003) 4.4, 6.6 és 7.5 szakasza [14] . $\eta _{t}$ $t$

Implicit változások (ISGD)

Ahogy korábban említettük, a klasszikus sztochasztikus gradiens süllyedés általában érzékeny a tanulási sebességre . A gyors konvergencia gyors, nagy tanulási sebességet igényel, de ez számszerű instabilitást okozhat . A probléma elsősorban úgy oldható meg [15] , hogy figyelembe vesszük az implicit változást , amikor a sztochasztikus gradienst a következő iterációnál számítjuk újra, és nem az aktuálisnál. $\eta$

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

Ez az egyenlőség implicit, mert az egyenlőség mindkét oldalán megjelenik. Ez a proximális gradiens módszer sztochasztikus formája , mivel az újraszámítás így fejezhető ki. $w^{új}$

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

Példaként vegyük a legkisebb négyzetek módszerét tulajdonságokkal és megfigyelésekkel . Szeretnénk dönteni: ${\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},

ahol a skalárszorzatot jelenti . ${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p))$

Ne feledje, hogy az "1" lehet az első elem. A klasszikus sztochasztikus gradiens süllyedés így működik $x$

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

ahol egyenletesen oszlik el 1 és között . Míg elméletileg ez az eljárás viszonylag enyhe feltételezések mellett konvergál, a gyakorlatban az eljárás nagyon instabil lehet. Különösen, ha helytelenül vannak beállítva, akkor nagy valószínűséggel nagy abszolút sajátértékekkel rendelkeznek, és az eljárás több iterációban eltérhet. Ezzel szemben az implicit sztochasztikus gradiens süllyedés ( ISGD ) úgy fejezhető ki $én$ $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}.

Az eljárás numerikusan stabil marad szinte mindegyiknél , mivel a tanulási sebesség most normalizálódott. Egy ilyen összehasonlítás a klasszikus és az explicit sztochasztikus gradiens süllyedés között a legkisebb négyzetek módszerében nagyon hasonló a legkisebb négyzetek szűrője ( angol legkisebb átlag négyzetek , LMS) és a normalizált legkisebb négyzetek szűrő összehasonlításához ( angol normalized legkisebb négyzetek szűrője , NLM-ek). $\eta$

Bár az ISGD analitikai megoldása csak a legkisebb négyzetek módszerével lehetséges, az eljárás a modellek széles körében hatékonyan megvalósítható. Konkrétan tegyük fel, hogy csak a tulajdonságok lineáris kombinációjaként függ attól , hogy felírhassuk , ahol egy valós értékű függvény függhet -től , de nem közvetlenül, csak a -n keresztül . A legkisebb négyzetek módszere teljesíti ezt a feltételt, ezért a logisztikus regresszió és a legtöbb általánosított lineáris modell kielégíti ezt a feltételt . Például a legkisebb négyzetekben és a logisztikai regresszióban , ahol a logisztikai függvény . Poisson - regresszióban és így tovább. $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))$

Ilyen körülmények között az ISGD könnyen megvalósítható az alábbiak szerint. Legyen , hol van egy szám. Ekkor az ISGD egyenértékű $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 }).

A léptéktényezőt felezéssel találhatjuk meg , mivel a legtöbb modellben, mint például a fenti általánosított lineáris modelleknél, a függvény csökken, és ekkor a keresési határ a következő lesz . $\xi ^{\ast }\in \mathbb {R}$ $q$ ${\displaystyle \xi ^{\ast ))$ $[\min(0,f(0)),\max(0,f(0))]$

Impulzus

Az újabb fejlesztések közé tartozik a momentum módszer , amely megjelent Rumelhart , Hinton és Williams tanulmányában a backpropagation learningről [16] . A lendületi sztochasztikus gradiens süllyedés minden iterációnál megjegyzi a változást, és a következő változást a gradiens és az előző változás lineáris kombinációjaként határozza meg [17] [18] : $\Delta w$

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

w:=w+\Delta w

ami ahhoz vezet

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

ahol a paramétert , amely minimalizálja , meg kell becsülni , és ez a lépésméret (ezt néha tanulási sebességnek nevezik a gépi tanulásban). $w$ $Q(w)$ $\eta$

A "lendület" elnevezés a fizikában a lendületből származik - a súlyvektor , amelyet úgy értünk, mint egy részecske útvonalát a paramétertér mentén [16] , és a veszteségfüggvény gradienséből (" erő ") gyorsulást tapasztal. A klasszikus sztochasztikus gradiens süllyedéstől eltérően a módszer a fluktuációk megelőzésével igyekszik ugyanabban az irányban tartani a haladást. A Momentumot több évtizede sikeresen alkalmazzák az informatikusok mesterséges neurális hálózatok képzésére [19] . $w$

Átlagolás

Az Average Stochastic Gradient Descent , amelyet Ruppert és Polyak egymástól függetlenül fejlesztett ki az 1980-as évek végén, egy hagyományos sztochasztikus gradiens süllyedés, amely a paraméterek vektorának átlagát rögzíti. Azaz az újraszámítás ugyanaz, mint a szokásos sztochasztikus gradiens süllyedési módszernél, de az algoritmus követi is [20]

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

Amikor az optimalizálás befejeződött, az átlagparaméterek vektora veszi át w helyét .

AdaGrad

A 2011-ben megjelent AdaGrad (adaptív gradiens algoritmus ) [21] [22] a sztochasztikus gradiens süllyedés algoritmusának egy olyan módosítása, amely minden paraméterhez külön tanulási sebességgel rendelkezik . Informálisan ez növeli a ritka adatot tartalmazó paraméterek tanulási sebességét, és csökkenti a kevésbé ritka adatot tartalmazó paraméterek tanulási sebességét. Ez a stratégia növeli a konvergencia sebességét a standard sztochasztikus gradiens süllyedési módszerhez képest olyan körülmények között, ahol az adatok ritkák és a megfelelő paraméterek informatívabbak. Ilyen alkalmazások például a természetes nyelvi feldolgozás és a mintafelismerés [21] . Az algoritmusnak van egy alap tanulási sebessége , de azt megszorozzák annak a vektornak az elemeivel, amely a külső szorzatmátrix átlója $\eta$ $\{G_{j,j}}\}$

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

ahol , gradiens iterációnként . Az átlót a $g_{\tau }=\nabla Q_{i}(w)$ $\tau$

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

Ez a vektor minden iteráció után frissül. Konverziós képlet

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

[a]

vagy paraméterekkel történő újraszámításként írva,

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

Minden elem egy paraméterre alkalmazott tanulási sebesség szorzót ad . Mivel ebben a faktorban a nevező az előző derivált ℓ2 -es normája , a nagy paraméterváltozások gyengülnek, míg a kis változást mutató paraméterek magasabb tanulási arányt kapnak [19] . $\{G_{(i,i)}\}$ $w_{i}$ ${\displaystyle {\sqrt {G_{i))}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2))))$

Bár az algoritmust konvex problémákra fejlesztették ki , az AdaGrad-ot sikeresen alkalmazták nem konvex optimalizálásra [23] .

RMSProp

Az RMSProp (a Root Mean Square Propagation szóból) egy olyan módszer, amelyben a tanulási sebesség minden paraméterhez igazodik. Az ötlet az, hogy a súlyok tanulási sebességét elosztjuk az adott súly legutóbbi gradienseinek mozgóátlagaival [24] . Tehát az első mozgóátlagot az effektív értékkel számítjuk ki

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

hol van a felejtési tényező. $\gamma$

Az opciók frissülnek:

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

Az RMSProp jól alkalmazkodott a tanulási sebességhez a különböző alkalmazásokban. Az RMSProp az Rprop általánosításaként fogható fel . A módszer nem csak teljes csomagokkal, hanem minicsomagokkal is képes dolgozni [25] .

Ádám

Adam [26] (az Adaptive Moment Estimation rövidítése ) az RMSProp optimalizáló frissítése . Ez az optimalizáló algoritmus mind a gradiensek, mind a második pillanatok mozgóátlagait használja. Ha a paraméterek adottak , és a veszteségfüggvény , ahol az aktuális iteráció indexét tükrözi (a jelentés karakterrel kezdődik ), akkor a paraméter Adam algoritmus általi újraszámítását a képletek adják meg. $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 }}

ahol egy kis adalékot használnak a 0-val való osztás megakadályozására, és a és a gradiensek felejtési együtthatói, illetve a gradiensek második momentumai. A négyzetre emelést és a négyzetgyököt elemről elemre kell kiszámítani. $\epsilon$ $\beta_{1}$ $\beta _{2}$

Természetes gradiens süllyedés és kSGD

A Kalman- alapú sztochasztikus gradiens süllyedés ( kSGD ) [27] egy online és offline algoritmus a kvázi-likelihood modellek statisztikai problémáinak tanulási paramétereihez , amely lineáris modelleket , nem-lineáris modelleket , általánosított lineáris modelleket és neurális hálózatokat foglal magában. effektív veszteségekkel speciális esetként. Online tanulási problémák esetén a kSGD a Kalman-szűrő speciális esete a lineáris regressziós problémákhoz, a kiterjesztett Kalman-szűrő speciális esete a nemlineáris regressziós problémákhoz, és inkrementális Gauss-Newton módszernek tekinthető . Ezenkívül a kSGD és a Kálmán-szűrő kapcsolata, valamint a természetes gradiens süllyedés [28] és a Kálmán-szűrő [29] kapcsolata miatt a kSGD jelentős előrelépést jelent a népszerű természetes gradiens süllyedés módszeréhez képest.

A kSGD előnyei más módszerekkel szemben:

(1) érzéketlen a probléma számos körülményére, [b] (2) a hiperparaméterek széles választékával rendelkezik, (3) leállási feltétellel rendelkezik.

A kSGD hátránya, hogy az algoritmus sűrű kovarianciamátrix tárolását igényli az iterációk között, és minden iterációnál meg kell találni a vektor és a mátrix szorzatát.

Az algoritmus leírásához feltételezzük, hogy a függvény , ahol , úgy van definiálva, hogy a so that $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)

ahol az átlagoló függvény (vagyis a várható értéke ) , és a varianciafüggvény (vagyis a variancia ) . Ekkor a paraméter újraszámítását és a kovariáns mátrix újraszámítását a következő kifejezések adják $\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}}

hol vannak a hiperparaméterek. Az újraszámítás hatására a kovariáns mátrix definiálatlanná válhat, ami elkerülhető a mátrix mátrixonkénti szorzásával. lehet bármilyen pozitív-definit szimmetrikus mátrix, de általában az azonosságmátrixot veszik. Amint Patel [27] megjegyezte , a lineáris regresszió kivételével minden probléma esetén ismételt futtatások szükségesek az algoritmus konvergenciájának biztosításához, de elméleti vagy megvalósítási részleteket nem adunk meg. A nemlineáris regresszióhoz szorosan kapcsolódó offline többtételes módszer, amelyet Bertsekas [30] elemzett , a felejtési tényezőt használta a kovariáns mátrix újraszámításánál a konvergencia bizonyítására. ${\displaystyle \gamma _{1},\gamma _{2))$ $M(t)$ $M(0)$

Másodrendű módszerek

Ismeretes, hogy a standard (determinisztikus) Newton-Raphson algoritmus sztochasztikus analógja (a „másodrendű” módszer) aszimptotikusan optimális vagy majdnem optimális formáját adja az iteratív optimalizálásnak sztochasztikus közelítés körülményei között. Bird, Hansen, Nosedal és Singer [31] dolgozott ki egy módszert, amely az empirikus kockázati függvényben az összegtagok Hess-mátrixának közvetlen kiszámítását használja . Előfordulhat azonban, hogy az optimalizáláshoz szükséges Hess-mátrixok közvetlen meghatározása a gyakorlatban nem lehetséges. Az SGD algoritmus olyan másodrendű változatához, amely nem igényel közvetlen Hess-információt, gyakorlati és elméleti keresési módszereket adtak meg Spall et al . ). Ezek a módszerek, bár közvetlenül nem igényelnek információt a Hessian-ról, de vagy a fent megadott empirikus kockázati függvényben szereplő összegtagok értékein, vagy az összegtagok gradienseinek értékein (azaz SGD bemeneten) alapulnak. . Konkrétabban, a másodrendű optimalitás aszimptotikusan elérhető anélkül, hogy az empirikus kockázati függvényben szereplő összegek Hess-mátrixait közvetlenül ki kellene számítani.

Megjegyzések

↑ elemenkénti szorzata . $\circ$
↑ Lineáris regressziós probléma esetén a kSGD célfüggvény varianciája (azaz a teljes hiba és variancia) iterációnként egyenlő 1-re hajló valószínűséggel, attól függő sebességgel , ahol a maradékok varianciája. Ezen túlmenően egy adott választásnál kimutatható, hogy a célfüggvény kSGD iterációs varianciája egyenlő 1-re hajló valószínűséggel, attól függő sebességgel , ahol az optimális paraméter. $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_{*}$

Lásd még

Koordináta süllyedés – egyszerre egy koordinátát változtat
Lineáris osztályozó
Online gépi tanulás

Jegyzetek

↑ Taddy 12. , 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 et al., 2012 , p. 9-48.
↑ Diaz, Guitton, 2011 , p. 2804-2808.
↑ Avi Pfeffer. CS181 5. előadás – Perceptronok (Harvard Egyetem) . (határozatlan) (nem elérhető link)
↑ 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, Ilja (2013). Ismétlődő neurális hálózatok képzése (PDF) (Ph.D.). Torontói Egyetem. Archivált (PDF) az eredetiből ekkor: 2020-02-28 . Letöltve: 2020-03-01 . Elavult használt paraméter |deadlink=( súgó )
↑ 1 2 Matthew D. Zeiler (2012), ADADELTA: Egy adaptív tanulási sebesség módszer, arΧiv : 1212.5701 [cs.LG].
↑ Polyak, Juditsky, 1992 , p. 838–855.
↑ 1 2 Duchi, Hazan, Singer, 2011 , p. 2121–2159.
↑ Joseph Perla (2014). Megjegyzések az AdaGrad-ról (nem elérhető link) . Letöltve: 2020. március 1. Az eredetiből archiválva : 2015. március 30. (határozatlan)
↑ Gupta, Bengio, Weston, 2014 , p. 1461–1492
↑ Tieleman, Tijmen és Hinton, Geoffrey (2012). 6.5-rmsprop előadás: Ossza el a gradienst a legutóbbi nagyságrendjének futó átlagával. COURSERA: Neurális hálózatok a gépi tanuláshoz
↑ Hinton, Geoffrey A mini-batch gradiens süllyedés áttekintése (hivatkozás nem érhető el) 27–29. Letöltve: 2016. szeptember 27. Az eredetiből archiválva : 2016. november 23. (határozatlan)
↑ Kingma Diederik, Jimmy Ba (2014), Adam: A method for stochastic optimization, arΧiv : 1412.6980 [cs.LG].
↑ Patel 12. , 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.

Irodalom

Leon Bottou, Olivier Bousquet. The Tradeoffs of Large Scale Learning // Optimalizálás gépi tanuláshoz / Suvrit Sra, Sebastian Nowozin, Stephen J. Wright (szerk.). - Cambridge: MIT Press, 2012. - ISBN 978-0-262-01646-9 .
songmei. A kétrétegű neurális hálózatok tájának átlagos terepi képe // Proceedings of the National Academy of Sciences . - Nemzeti Tudományos Akadémia , 2018. - 1. évf. 115 , iss. 33 . - doi : 10.1073/pnas.1806579115 . — PMID 30054315 .
Matt Taddy. Sztochasztikus gradiens süllyedés // Business Data Science: A gépi tanulás és a közgazdaságtan összekapcsolása az üzleti döntések optimalizálása, automatizálása és felgyorsítása érdekében. — New York: McGraw-Hill, 2019. — ISBN 978-1-260-45277-8 .
Thomas S. Ferguson. Inkonzisztens maximális valószínűségi becslés // Journal of the American Statistical Association. - 1982. - T. 77 , sz. 380 . - doi : 10.1080/01621459.1982.10477894 . — .
Leon Bottou, Olivier Bousquet. A nagyléptékű tanulás kompromisszumai //A neurális információfeldolgozó rendszerek fejlődése . - 2008. - T. 20.

Leon Bottou. Online algoritmusok és sztochasztikus közelítések // Online tanulás és neurális hálózatok. - Cambridge University Press, 1998. - ISBN 978-0-521-65263-6 .

Krzysztof C. Kiwiel. Szubgradiens módszerek konvergenciája és hatékonysága kvázikonvex minimalizáláshoz // Mathematical Programming, Series A. - Berlin, Heidelberg: Springer, 2001. - Vol. 90 , no. 1 . — P. 1–25. — ISSN 0025-5610 . - doi : 10.1007/PL00011414 .
Herbert Robbins, David O. Siegmund. Konvergenciatétel a nem negatív szinte szupermartingálokhoz és néhány alkalmazáshoz // Optimizing Methods in Statistics / Jagdish S. Rustagi (szerk.). – Akadémiai Kiadó, 1971.
Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning. Hatékony, jellemző alapú, feltételes véletlenszerű mezőelemzés // Proc. Az ACL éves közgyűlése . – 2008.
Yann A. LeCun, Leon Bottou, Genevieve B. Orr, Klaus-Robert Muller. Hatékony backprop // Neurális hálózatok: Tricks of the trade / Grégoire Montavon, Geneviève B. Orr, Klaus-Robert Müller (szerk.). - Berlin Heidelberg: Springer, 2012. - T. 7700. - (Lecture Notes in Computer Science). - ISBN 978-3-642-35288-1 .
Esteban Diaz, Antoine Guitton. Gyors teljes hullámforma inverzió véletlenszerű tizedeléssel // SEG Technical Program Expanded Abstracts . – 2011.
Christian Darken, John Moody. Közös Nemzetközi Konf. on Neural Networks (IJCNN) // Gyors adaptív k-közép klaszterezés: néhány empirikus eredmény . – IEEE, 1990.
Spall JC Bevezetés a sztochasztikus keresésbe és optimalizálásba: becslés, szimuláció és vezérlés. - Hoboken, NJ: Wiley, 2003. - ISBN 0-471-33052-3 .
Panos Toulis, Edoardo Airoldi. Sztochasztikus gradienseken alapuló becslések aszimptotikus és véges mintájú tulajdonságai // Annals of Statistics. - 2017. - T. 45 , sz. 4 . - doi : 10.1214/16-AOS1506 . - arXiv : 1408.2923 .
Spall JC adaptív sztochasztikus közelítés szimultán perturbációs módszerrel // IEEE-tranzakciók az automatikus vezérlésen. - 2000. - T. 45 , sz. 10 . - doi : 10.1109/TAC.2000.880982 .
Spall JC visszacsatolási és súlyozási mechanizmusai a Jacobi-becslések javítására az adaptív szimultán perturbációs algoritmusban // IEEE Transactions on Automatic Control. - 2009. - T. 54 , sz. 6 . - doi : 10.1109/TAC.2009.2019793 .
Bhatnagar S., Prasad HL, Prashanth LA Sztochasztikus rekurzív algoritmusok optimalizáláshoz: szimultán perturbációs módszerek. — London: Springer, 2013. — ISBN 978-1-4471-4284-3 .
Ruppert D. A többváltozós Robbins-Monro eljárás Newton-Raphson változata // Annals of Statistics . - 1985. - T. 13 , sz. 1 . doi : 10.1214 / aos/1176346589 .
David E. Rumelhart, Geoffrey E. Hinton, Ronald J. Williams. Reprezentációk tanulása visszaterjedési hibákkal // Természet . - 1986. - október ( 323. kötet , 6088. szám ). - doi : 10.1038/323533a0 . - .
Ilya Sutskever, James Martens, George Dahl, Geoffrey E. Hinton. Az inicializálás és a lendület fontosságáról a mély tanulásban // In Proceedings of the 30th international Conference on Machine learning (ICML-13) / Sanjoy Dasgupta, David Mcallester (szerk.). - Atlanta, GA, 2013. - T. 28.
Boris T. Polyak, Anatoli B. Juditsky. Sztochasztikus közelítés gyorsítása átlagolással // SIAM J. Control Optim.. - 1992. - Vol. 30 , no. 4 . - doi : 10.1137/0330046 .
John Duchi, Elad Hazan, Yoram Singer. Adaptív szubgradiens módszerek online tanuláshoz és sztochasztikus optimalizáláshoz // JMLR . - 2011. - T. 12 .
Maya R. Gupta, Samy Bengio, Jason Weston. Erősen több osztályú osztályozók képzése // JMLR. - 2014. - T. 15 , sz. 1 .
Patel V. Kálmán-alapú sztochasztikus gradiens módszer leállási feltétellel és a kondicionálásra való érzéketlenséggel // SIAM Journal on Optimization. - 2016. - T. 26 , sz. 4 . — ISSN 1052-6234 . - doi : 10.1137/15M1048239 . - arXiv : 1512.01139 .
Cichocki A., Chen T., Amari S. A vakforrás-leválasztás tanulási algoritmusainak stabilitási elemzése // Neurális hálózatok. - 1997. - november ( 10. évf. , 8. szám ). - 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 , sz. 2 . - doi : 10.1137/140954362 . - arXiv : 1401.7020 .
Bertsekas D. Növekményes legkisebb négyzetek módszerei és a kiterjesztett Kálmán-szűrő // SIAM Journal on Optimization. - 1996. - T. 6 , sz. 3 . - S. 807-822 . — ISSN 1052-6234 . - doi : 10.1137/S1052623494268522 .

Olvasás további olvasáshoz

Dimitri P. Bertsekas. nemlineáris programozás. — 2. - Cambridge, MA.: Athena Scientific, 1999. - ISBN 978-1-886529-00-7 . .
Dimitri P. Bertsekas. Konvex elemzés és optimalizálás. – Athena Scientific, 2003.
Leon Bottou. Sztochasztikus tanulás // Advanced Lectures on Machine Learning . - Springer, 2004. - T. 3176. - S. 146-168. — (LNAI). - ISBN 978-3-540-23122-6 .
Davidon WC [187–197 Új legkisebb négyzetes algoritmusok] // Journal of Optimization Theory and Applications. - 1976. - T. 18 , 2. sz . - doi : 10.1007/BF00935703 .
Richard O. Duda, Peter E. Hart, David G. Stork. minta besorolása. — 2. - Wiley , 2000. - ISBN 978-0-471-05669-0 .
Krzysztof C. Kiwiel. Közelítő és növekményes szubgradiens módszerek konvergenciája konvex optimalizáláshoz // SIAM Journal on Optimization. - 2004. - T. 14 , 3. sz . - S. 807-840 . - doi : 10.1137/S1052623400376366 .
Jan A. Snyman, Daniel N. Wilke. Gyakorlati matematikai optimalizálás - Optimalizálási elmélet és gradiens alapú algoritmusok . - 2. - Springer , 2018. - S. xxvi + 372. - (Springer Optimization és alkalmazásai, 133. kötet). - ISBN 978-3-319-77585-2 .
James C. Spall. Bevezetés a sztochasztikus keresésbe és optimalizálásba. - Wiley , 2003. - ISBN 978-0-471-33052-3 . .

Linkek

Sztochasztikus gradiens süllyedés használata C++, Boost, Ublas nyelven a lineáris regresszióhoz
Gépi tanulási algoritmusok
Gradient Descent, Hogyan tanulnak a neurális hálózatok . 3Blue1 Brown (2017. október 16.). (határozatlan)