Stokastisk gradient decent

SGD er en optimeringsmetode, som optimerer enkelte dataudtag af gangen til forskel fra gradient decent (GD). Dette gør optimeringen væsentlig hurtigere og kræver færre computerkrafter. En typisk GD algoritme kan beskrives ved formlen:$ latex \theta=\theta-\alpha \nabla_{\theta} E[L(\theta)] $
GD-algoritmen opdaterer parameteren $ latex \theta$ i forhold til en omkostningsfunktion $L(\theta)$, som approksimeres på baggrund af omkostningen og gradienten for det fulde træningsæt. Imens, benytter SGD kun et eller få dataudtræk af gangen til udregningen af gradienten for parametrene:
$ \theta=\theta-\alpha \nabla_{\theta} L\left(\theta ; x^{(i)}, y^{(i)}\right)
$
Hvor $ \left(x^{(i)}, y^{(i)}\right)$ er et eksempel på et par fra træningsættet og $\alpha$ er indlæringsraten.
Et mindre dataudtræk af $m$ observertioner ${x^1,\dots,x^m}$ med korresponderende mål $y^i$, udtrækkes fra træningssættet og vægtene opdateres ved en negativ gradient ved brug af (24).\
På den måde sker hver opdatering af parameteren $\theta$ ved brug af et mindre udtræk fra træningsdataen. Dette leder dog til øget varians i opdateringsprocessen, men i praksis sker udregningerne væsentlig hurtigere sammenlignet med (\ref{7}).
Indlæringsraten $\alpha$ bestemmes i praksis ikke som en konstant værdi, men falder over tid når træningen påbegyndes. Det betyder altså at indlæringsraten $\alpha$ påvirkes af antallet af gentagelser og derfor defineres som $\alpha_k$, hvor $k$ angiver antallet af gentagelser (epochs).

Figure 1: Trinstørrelse og aftagningsrate

For at sørge for, at SGD konvergere effektiv mod et globalt minima jf. figur 1, og ikke sidder fast, skal indlæringsraten overholde en række betingelser:
$ \sum^\infty_{k=1}\alpha_k=\infty, \quad \text{og} \quad \sum^\infty_{k=1}\alpha_k^2<\infty $
Hastigheden som indlæringsraten falder med er ofte lineært bestemt:
$ \alpha_k=(1-\beta) \alpha_0+\beta \alpha_\tau $
hvor $\beta=\frac{k}{\tau}$ og $\tau$ angiver den endelige gentagelse.
Når træningen begynder, vil en høj indlæringsrate hjælpe algoritmen med at konvergere hurtigere imod ekstremaet, men på et vist tidspunkt vil de store spring gøre, at algoritmen oscillerer rundt om ekstremaet og aldrig konvergere rigtigt mod den optimale værdi.