Discesa stocastica del gradiente

La discesa stocastica del gradiente (in lingua inglese stochastic gradient descent, SGD) è un metodo iterativo per l'ottimizzazione di funzioni differenziabili, approssimazione stocastica del metodo di discesa del gradiente (GD) quando la funzione costo ha la forma di una somma. SGD opera similmente a GD ma, ad ogni iterazione, sostituisce il valore esatto del gradiente della funzione costo con una stima ottenuta valutando il gradiente solo su un sottinsieme degli addendi. È ampiamente usato per l'allenamento di una varietà di modelli probabilistici e modelli di apprendimento automatico, come macchine a vettori di supporto, regressione logistica e modelli grafici. In combinazione con il metodo di retropropagazione dell'errore, è lo standard de facto per l'allenamento delle reti neurali artificiali.

Contesto

In molti problemi di statistica e di apprendimento automatico si ha la necessità di ottimizzare una funzione $Q(w)$ nei parametri $w$ che ha la forma di una somma

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

dove ogni addendo $Q_{i}$ rappresenta il costo calcolato sull'$i$-esima osservazione in un dataset. Nel contesto della statistica classica, tale problema appare tipicamente in applicazioni del metodo dei minimi quadrati o del metodo della massima verosimiglianza, e gli stimatori ottenuti come soluzione di tali problemi sono chiamati stimatori M. Il metodo di discesa del gradiente esegue iterazioni nella forma

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

dove $\eta$ è un iperparametro che controlla l'ampiezza di ogni passo, e nel contesto dell'apprendimento automatico è chiamato tasso di apprendimento (learning rate). In molti casi, gli addendi hanno un'espressione sufficientemente semplice, che consente una valutazione rapida del gradiente ad ogni iterazione (ad esempio, in statistica, le funzioni della famiglia esponenziale). Tuttavia, in altri contesti, la valutazione dell'intera somma può essere particolarmente costosa, ad esempio quando il dataset è particolarmente ampio e non esiste un'espressione elementare per il costo, richiedendo la valutazione di tutti i singoli addendi, fatto che si verifica comunemente, ad esempio, nei problemi di apprendimento profondo. La discesa stocastica del gradiente affronta tale problema approssimando il gradiente dell'intera somma, valutandolo solo in un sottoinsieme casuale degli addendi ad ogni iterazione.

Formulazione

Esempio di andamento della funzione costo nel corso delle iterazioni in un problema di ottimizzazione risolto tramite SGD

La discesa del gradiente classica viene anche chiamata batch GD, in quanto l'intero dataset viene valutato ad ogni iterazione. Quando il gradiente viene invece approssimato stocasticamente, è possibile costruire diversi metodi a seconda del numero di addendi usati ad ogni iterazione. Un possibile approccio è la discesa stocastica del gradiente in linea (on-line), che usa un solo elemento del dataset alla volta, ed è così chiamato perché può essere usato quando il dataset non è prefissato e nuovi dati vengono generati sul momento (on-line, o on-the-fly). Il gradiente di $Q(w)$ è approssimato ad ogni iterazione con il gradiente calcolato su un singolo addendo della funzione costo (corrispondente ad un elemento del dataset)

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

e i parametri vengono aggiornati dopo ogni valutazione. Il dataset può essere attraversato diverse volte, fino a quando il metodo converge. Tipicamente, l'ordine degli elementi è randomizzato ad ogni attraversamento del dataset, e il tasso di apprendimento $\eta$ può essere variato dinamicamente, tipicamente riducendolo con il procedere delle iterazioni (annealing).

 1  $w:=w_{0}$
 2  $\eta :=\eta _{0}$
 3  until convergenza do:
 4      dataset:= permutazione(dataset)
 5      for $i:=1,...n$ do:
 6          $\!w:=w-\eta \nabla Q_{i}(w).$
 7          $\eta :={\text{annealing}}(\eta )$

L'aggiornamento dei parametri in linea, con iterazione sui singoli elementi del dataset, implica generalmente un andamento molto irregolare della funzione costo (figura a lato). Una variante ampiamente utilizzata, che rappresenta un approccio intermedio tra SGD in linea e batch GD, è nota come mini-batch e prevede di calcolare il gradiente su un sottinsieme di elementi del dataset ad ogni iterazione, invece che su in singolo elemento. La dimensione di ogni mini-batch è generalmente dipendente dal contesto. Ciò rende l'evoluzione della funzione costo nel corso delle iterazioni meno rumorosa, in quanto il gradiente ad ogni iterazione diventa la media di ogni mini-batch, risultando in un effetto di smoothing, e riduce il costo computazionale, consentendo una migliore vettorizzazione del codice.

La convergenza del metodo è stata studiata nel contesto dell'ottimizzazione convessa e dell'approssimazione stocastica. In sintesi, se il tasso di apprendimento decresce nel corso delle iterazioni secondo una funzione opportuna del tempo, e la funzione obiettivo è convessa o pseudoconvessa e soddisfa alcune ipotesi deboli, la discesa del gradiente stocastica converge quasi certamente ad un punto di ottimo locale.

Estensioni e varianti

Molte estensioni del metodo sono state proposte, soprattutto nel contesto dell'apprendimento automatico, dove la discesa stocastica del gradiente è un metodo indispensabile per l'addestramento delle reti neurali artificiali profonde. In tale contesto la funzione obiettivo ha tipicamente decine di milioni di parametri da ottimizzare, il che rende difficile sfuggire dai punti di sella.

Uno degli aspetti importanti nella formulazione dei metodi è la presenza di iperparametri che necessitano di essere a loro volta ottimizzati, e la capacità di un algoritmo di non dipendere da iperparametri espliciti è generalmente un aspetto positivo. Un iperparametro fondamentale in molti metodi è il tasso di apprendimento, che riveste un ruolo cruciale in quanto un valore troppo elevato comporta scarsa capacità di convergenza, mentre un valore troppo basso implica una convergenza molto lenta. Un'estensione elementare prevede di usare un tasso di apprendimento dinamico con una funzione decrescente nel numero di iterazioni, concetto già studiato in precedenza in altri algoritmi come simulated annealing o nell'estensione adattiva dell'algoritmo k-means.

Diversi metodi con tasso di apprendimento adattivo, regolato automaticamente nel corso delle iterazioni, sono stati sviluppati e hanno raggiunto grande diffusione nelle applicazioni pratiche. Tuttavia in alcuni problemi di apprendimento automatico, come riconoscimento di oggetti o traduzione automatica, tali metodi mostrano scarsa capacità di generalizzazione e sono meno robusti rispetto a una semplice SGD con momento. Questo è legato al fatto che tali metodi usano una media mobile con memoria a breve termine, soggetta a decadimento esponenziale, e poiché alcune mini-batch sono più ricche di contenuto informativo ma allo stesso tempo più rare, la loro influenza risulta limitata, indebolendo la robustezza del metodo.

Momento

Il momento è un termine dipendente dalle iterazioni precedenti, che viene sommato al gradiente nel tentativo di regolarizzare il movimento nello spazio dei parametri. È stato descritto da Rumelhart, Hinton e Williams nel loro articolo seminale del 1986 sulla retropropagazione dell'errore. L'aggiornamento dei parametri usa una combinazione lineare del gradiente nell'iterazione corrente e dell'aggiornamento nell'iterazione precedente

$\Delta w_{t+1}=\alpha \Delta w_{t}-\eta \nabla Q_{i}(w_{t})$

$w_{t+1}=w_{t}+\Delta w_{t+1}$

che risulta in

$w_{t+1}=w_{t}-\eta \nabla Q_{i}(w_{t})+\alpha \Delta w_{t}$

Questo metodo introduce un secondo iperparametro $\alpha$ per controllare l'effetto del momento, ovvero l'importanza dell'iterazione passata. Un valore empirico per tale parametro è solitamente fissato intorno a $\alpha =0.9$.

Il metodo è stato usato a lungo nell'addestramento delle reti neurali e il nome deriva da un'analogia non del tutto accurata con il momento lineare in fisica, in quanto il vettore dei parametri può essere visto come una particella che si muove nello spazio dei parametri, soggetta ad accelerazione da parte di una forza il cui potenziale è espresso dalla funzione costo.

NAG

NAG (Nesterov accelerated gradient), introdotto da Jurij Nesterov nel 1983, è un'estensione del metodo del momento che approssima la posizione futura dei parametri, introducendo una espressione corretta $w+\alpha \Delta w$ che tiene conto del movimento.

$\Delta w_{t+1}=\alpha \Delta w_{t}-\eta \nabla Q_{i}(w_{t}+\alpha \Delta w_{t})$

$w_{t+1}=w_{t}+\Delta w_{t+1}$

Questa correzione previene movimenti eccessivi nello spazio dei parametri, e la sua introduzione ha portato significativi miglioramenti nella performance delle reti neurali ricorsive.

AdaGrad

AdaGrad (adaptive gradient) è un metodo pubblicato nel 2011 che usa un tasso di apprendimento indipendente per ogni parametro. Intuitivamente, questo metodo usa tassi di apprendimento più elevati per parametri con una distribuzione più sparsa, e più lenti per i parametri con distribuzione più densa. AdaGrad spesso converge più rapidamente rispetto a SGD ordinaria, soprattutto quando la distribuzione dei dati è sparsa e i parametri sparsi hanno maggior contenuto informativo, che si verifica ad esempio in problemi di elaborazione del linguaggio naturale o riconoscimento automatico del contenuto di immagini.

Il tasso di apprendimento $\eta$ è moltiplicato per un vettore $G$ i cui elementi rappresentano i fattori di scala per ogni parametro. Tale vettore è la diagonale della matrice ottenuta come prodotto esterno

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

dove $g_{\tau }=\nabla Q_{i}(w)$ è il gradiente all'iterazione $\tau$. Gli elementi diagonali di $G$ hanno la forma

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

Tale vettore è aggiornato ad ogni iterazione, e l'espressione di aggiornamento dei parametri diventa

$w:=w-\eta \,\left(\mathrm {diag} (G+\epsilon I)\right)^{-{\frac {1}{2}}}\circ g$

dove $\circ$ è il prodotto di Hadamard e $\epsilon$ è un termine di smoothing, solitamente con un valore dell'ordine di $10^{-8}$, aggiunto per migliorare la stabilità numerica.

Ogni elemento $G_{i,i}$ è un fattore di scala del learning rate per un singolo parametro $w_{i}$ da ottimizzare, e ${\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}$ è la norma ℓ₂ di una quantità che incorpora le derivate alle iterazioni precedenti, per cui tale fattore attenua il learning rate di parametri soggetti ad aggiornamenti bruschi, e fornisce maggiore importanza al learning rate di parametri con aggiornamenti piccoli o infrequenti. Esprimendo l'aggiornamento per ogni singolo parametro, la formula diventa

$w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}+\epsilon }}}g_{j}.$

Benché ideato per problemi di ottimizzazione convessa, AdaGrad è usato anche per problemi di ottimizzazione nonconvessa. Uno dei vantaggi principali di AdaGrad è la sua capacità di adattare automaticamente il tasso di apprendimento, che ne fa in pratica un metodo senza iperparametri, in quanto molte implementazioni usano un valore iniziale predefinito (intorno a $\eta =0.01$). Il principale svantaggio è la tendenza del metodo a cancellare il learning rate nel corso delle iterazioni, portando ad un arresto dell'apprendimento, poiché i termini della somma sono positivi e il valore del denominatore è strettamente crescente in funzione delle iterazioni.

RMSProp

RMSProp (Root Mean Square Propagation) è un metodo con tasso di apprendimento adattivo che affronta il problema della cancellazione del tasso di apprendimento in AdaGrad. L'algoritmo non è stato pubblicato su una rivista peer-reviewed dall'autore Geoffrey Hinton, ma è stato proposto originariamente nelle sue slide per il corso Neural Networks for Machine Learning, tenutosi su Coursera, che vengono comunemente citate come fonte originale per tale metodo. Data la media mobile $E$ della norma del gradiente ad ogni iterazione, calcolata in una finestra di iterazioni precedenti

$E[g^{2}]_{t}=\gamma E[g^{2}]_{t-1}+(1-\gamma )g^{2}$

dove $\gamma \in [0,1]$ è un fattore di decadimento esponenziale, solitamente con valore empiricamente fissato intorno a $\gamma =0.9$ (suggerito anche da Hinton), il parametro $\gamma$ determina l'importanza della memoria delle passate iterazioni nel calcolo della media mobile: un valore pari a zero significa che le iterazioni passate sono ignorate e solo il gradiente all'iterazione corrente è usato, e all'aumentare di $\gamma$ la memoria delle passate iterazioni assume importanza sempre maggiore, a discapito del valore corrente del gradiente.

Definendo la media quadratica $\mathrm {RMS}$ (root mean square) come

$\mathrm {RMS} [X]_{t}={\sqrt {E[X]_{t}+\epsilon }}$

l'aggiornamento dei parametri è definito come

$\Delta w_{t}=-{\frac {\eta }{\mathrm {RMS} [g^{2}]_{t}}}g_{t}.$

In questo modo, il tasso di apprendimento $\eta$ è controllato dinamicamente della media quadratica della norma del gradiente.

AdaDelta

AdaDelta, come RMSProp, è una variante di AdaGrad che contrasta la cancellazione del tasso di apprendimento. È stato sviluppato indipendentemente da RMSProp, di cui può essere considerato una estensione. Ad ogni iterazione viene calcolata una media mobile $E$ del quadrato della norma del gradiente nel corso delle iterazioni

$E[g^{2}]_{t}=\gamma E[g^{2}]_{t-1}+(1-\gamma )g^{2}$

e una media mobile del vettore di cambiamento dei parametri

$E[\Delta w^{2}]_{t}=\gamma E[\Delta w^{2}]_{t-1}+(1-\gamma )\Delta w_{t}^{2}.$

Il vettore di aggiornamento dei parametri è definito come

$\Delta w_{t}=-{\frac {\mathrm {RMS} [\Delta w^{2}]_{t-1}}{\mathrm {RMS} [g^{2}]_{t}}}g_{t}.$

Il tasso di apprendimento è completamente automatico, e l'unico iperparametro di AdaDelta è il decadimento $\gamma$.

Adam

Adam (Adaptive moment estimation) è un'estensione di RMSProp che tiene conto della media mobile dei momenti primo ($m$) e secondo ($v$) del gradiente, usando degli stimatori corretti ${\hat {m}}$ e ${\hat {v}}$, in quanto $m$ e $v$ sono distorti verso valori prossimi allo zero, fenomeno evidente soprattutto nelle prime iterazioni. Indicando con $w_{t}$ i parametri all'iterazione $t$, e con $Q$ la funzione costo da ottimizzare, si ha

$m_{t+1}=\beta _{1}m_{t}+(1-\beta _{1})\nabla Q(w_{t})$

$v_{t+1}=\beta _{2}v_{t}+(1-\beta _{2})(\nabla Q(w_{t}))^{2}$

${\hat {m}}={\frac {m_{t+1}}{1-\beta _{1}^{t+1}}}$

${\hat {v}}={\frac {v_{t+1}}{1-\beta _{2}^{t+1}}}$

$w_{t+1}=w_{t}-\eta {\frac {\hat {m}}{{\sqrt {\hat {v}}}+\epsilon }}$

dove $\epsilon$ è un termine di smoothing aggiunto ai fini della stabilità numerica, mentre $\beta _{1}$ e $\beta _{2}$ sono iperparametri che controllano il decadimento esponenziale. Gli autori suggeriscono $\epsilon =10^{-8}$, $\beta _{1}=0.9$ e $\beta _{2}=0.999$.

AdaMax

AdaMax è una variante di Adam che usa la norma del massimo del gradiente invece della norma ℓ₂ nella stima del momento secondo

$u_{t+1}=\beta _{2}u_{t}+(1-\beta _{2})|g_{t+1}|_{\infty }=\max \left\{\beta _{2}u_{t},|g_{t+1}|\right\}$

ottenendo la formula di aggiornamento

$w_{t+1}=w_{t}-\eta {\frac {\hat {m}}{u_{t}}}$

dove $u_{t}$ non richiede correzione né smoothing. Gli autori suggeriscono $\eta =0.002$, $\beta _{1}=0.9$ e $\beta _{2}=0.999$.

Nadam

Nadam (Nesterov-accelerated Adaptive Moment Estimation) è un metodo che incorpora NAG in Adam. Espandendo la formula di aggiornamento dei parametri di Adam, sostituendo ${\hat {m_{t}}}$ con la sua definizione, si ha

$w_{t+1}=w_{t}-\eta {\frac {\hat {m}}{{\sqrt {\hat {v}}}+\epsilon }}=w_{t}-{\frac {\eta }{{\sqrt {\hat {v}}}+\epsilon }}\left(\beta _{1}{\hat {m}}_{t-1}+{\frac {(1-\beta _{1})g_{t}}{1-\beta _{1}^{t}}}\right)$

Si può quindi applicare la correzione di Nesterov sostituendo lo stimatore corretto del momento all'iterazione precedente ${\hat {m}}_{t-1}$ con la stima all'iterazione corrente ${\hat {m}}_{t}$, ottenendo la formula di aggiornamento dei parametri di Nadam

$w_{t+1}=w_{t}-{\frac {\eta }{{\sqrt {\hat {v}}}+\epsilon }}\left(\beta _{1}{\hat {m}}_{t}+{\frac {(1-\beta _{1})g_{t}}{1-\beta _{1}^{t}}}\right).$

AMSGrad

AMSGrad è una variante di Adam che sostituisce la media mobile del quadrato della norma del gradiente nelle passate iterazioni con il massimo, nel tentativo di ridurre l'effetto di memoria a breve termine che, in alcuni problemi, limità la robustezza di molti metodi con tasso di apprendimento adattivo

$m_{t+1}=\beta _{1}m_{t}+(1-\beta _{1})\nabla Q(w_{t})$

$v_{t+1}=\beta _{2}v_{t}+(1-\beta _{2})(\nabla Q(w_{t}))^{2}$

${\hat {v}}_{t+1}=\max \left\{{\hat {v}}_{t},v_{t+1}\right\}$

$w_{t+1}=w_{t}-\eta {\frac {m_{t+1}}{{\sqrt {{\hat {v}}_{t+1}}}+\epsilon }}$

kSGD

kSGD (Kalman-based Stochastic Gradient Descent) è un metodo per l'apprendimento di parametri in modelli di quasi-verosimiglianza, includendo come casi particolari modelli di regressione lineare e non lineare, modelli lineari generalizzati e reti neurali con errore quadratico medio come funzione costo. Per l'apprendimento in linea, kSGD è un caso particolare di filtro di Kalman nel caso di problemi di regressione lineare, o un caso particolare di filtro di Kalman esteso per problemi di regressione non lineare, e costituisce un'estensione formalmente rigorosa della discesa del gradiente.

kSGD non è sensibile al numero di condizionamento del problema, ha una condizione di arresto e una scelta robusta degli iperparametri. Tra gli svantaggi, vi sono il fatto che kSGD richiede di memorizzare una matrice densa di covarianza, e richiede il calcolo di un prodotto matrice-vettore ad ogni iterazione.

Sia data la funzione costo $Q_{i}(w)$, dove i parametri $w\in \mathbb {R} ^{p}$ sono definiti da un'osservazione $(Y_{i},X_{i})\in \mathbb {R} \times \mathbb {R} ^{d}$ in maniera tale che

$\nabla _{w}Q_{i}(w)={\frac {Y_{i}-\mu (X_{i},w)}{V(\mu (X_{i},w))}}\nabla _{w}\mu (X_{i},w)$

dove $\mu (X_{i},w)$ è il valore atteso di $Y_{i}$ dato $X_{i}$ e $V(\mu (X_{i},w))$ è la varianza di $Y_{i}$ dato $X_{i}$). Gli aggiornamenti dei parametri $w(t+1)$ e della matrice di covarianza $M(t+1)$ sono dati da

$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}}$

dove $\gamma _{1},\gamma _{2}$ sono iperparametri del metodo. L'aggiornamento di $M(t)$ può risultare in una matrice di covarianza non definita, e questo può essere evitato al costo di calcolare un prodotto di matrici aggiuntivo. $M(0)$ può essere una qualsiasi matrice simmetrica definita positiva, ed è tipicamente inizializzata con l'identità. In un metodo correlato di regressione non-lineare, un fattore di decadimento è usato nell'aggiornamento della matrice di covarianza allo scopo di dimostrare la convergenza.

Implementazione parallela

Benché l'algoritmo di discesa stocastica del gradiente sia inerentemente sequenziale, è possibile parallelizzarlo per l'esecuzione su sistemi distribuiti, generalmente operando su diversi mini-batch in parallelo e usando un array di parametri condiviso che viene aggiornato combinando i risultati. Se i dati sono sufficientemente sparsi, ovvero ogni elemento del dataset influenza solo un numero limitato di parametri, è possibile implementare SGD in parallelo condividendo i parametri senza sincronizzazione, evitando il costo aggiuntivo di quest'ultima, in quanto la probabilità di incorrere in corse critiche è molto bassa e le stesse, pur introducendo rumore nel processo, risultano avere un effetto trascurabile sulla convergenza dell'algoritmo.

Alcuni framework fanno uso di un processo server che memorizza i parametri, e una collezione di processi worker che calcolano i gradienti e manipolano i parametri tramite primitive di sincronizzazione. TensorFlow dalla versione 0.8 fornisce nativamente l'allenamento dei modelli con ottimizzazione distribuita su più GPU.

Ottimizzazioni

In problemi complessi, ad esempio nell'ottimizzazione dei parametri di reti neurali molto profonde, può essere utile introdurre del rumore ad ogni iterazione, sommando al gradiente una componente di rumore gaussiano con media nulla e varianza $\sigma ^{2}={\frac {\eta }{(1+t)^{\gamma }}}$, soggetta ad annealing in funzione del numero di iterazioni $t$. Questo approccio rende il processo meno dipendente dal valore iniziale dei parametri da ottimizzare, e aumenta la capacità dell'algoritmo di sfuggire da minimi locali sub-ottimali.

In generale, è utile randomizzare l'ordine del dataset ad ogni attraversamento, per evitare di introdurre un bias. Tuttavia in alcuni casi, ad esempio in problemi di apprendimento automatico, può essere invece utile attraversare il dataset in ordine di difficoltà crescente dei record, dove la difficoltà dipende dalla natura del problema (ad esempio, difficoltà di classificazione di un record in un problema di classificazione). Tale approccio è chiamato curriculum learning, e diverse strategie di ordinamento sono state studiate.

Bibliografia

• Dimitri P. Bertsekas, Nonlinear Programming, 2nd, Cambridge, MA., Athena Scientific, 1999, ISBN 1-886529-00-0.
• Dimitri Bertsekas, Convex Analysis and Optimization, Athena Scientific, 2003.
• Léon Bottou, Stochastic Learning, in Advanced Lectures on Machine Learning, LNAI, vol. 3176, Springer, 2004, pp. 146–168, ISBN 978-3-540-23122-6.
• W.C. Davidon, New least-square algorithms, in Journal of Optimization Theory and Applications, vol. 18, n. 2, 1976, pp. 187–197, DOI:10.1007/BF00935703.
• Richard O. Duda, Peter E. Hart e David G. Stork, Pattern Classification, 2nd, Wiley, 2000, ISBN 978-0-471-05669-0.
• Krzysztof C. Kiwiel, Convergence of approximate and incremental subgradient methods for convex optimization, in SIAM Journal of Optimization, vol. 14, n. 3, 2004, pp. 807–840, DOI:10.1137/S1052623400376366. (Extensive list of references)
• Sebastian Ruder, An overview of gradient descent optimization algorithms, 2017, arXiv:1609.04747.
• James C. Spall, Introduction to Stochastic Search and Optimization, Wiley, 2003, ISBN 978-0-471-33052-3.