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.Jenny Rose Finkel, Alex Kleeman, Christopher D. Manning (2008). Efficient, Feature-based, Conditional Random Field Parsing. Proc. Annual Meeting of the ACL. 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 nei parametriIn questo contesto, i parametri del modello statistico sono le variabili libere da ottimizzare, mentre i parametri del metodo di ottimizzazione sono chiamati iperparametri. che ha la forma di una somma

dove ogni addendo rappresenta il costo calcolato sull'-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

dove è 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

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 è approssimato ad ogni iterazione con il gradiente calcolato su un singolo addendo della funzione costo (corrispondente ad un elemento del dataset)

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 può essere variato dinamicamente, tipicamente riducendolo con il procedere delle iterazioni (annealing).

1 2 3 until convergenza do: 4 dataset:= permutazione(dataset) 5 for do: 6 7

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.Cited by

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

che risulta in

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

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 che tiene conto del movimento.Nesterov, Yuri (1983). A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). ANSSSR vol. 269, pp. 543– 547.

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 è moltiplicato per un vettore i cui elementi rappresentano i fattori di scala per ogni parametro. Tale vettore è la diagonale della matrice ottenuta come prodotto esterno

dove è il gradiente all'iterazione . Gli elementi diagonali di hanno la forma

.

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

dove è il prodotto di Hadamard e è un termine di smoothing, solitamente con un valore dell'ordine di , aggiunto per migliorare la stabilità numerica.

Ogni elemento è un fattore di scala del learning rate per un singolo parametro da ottimizzare, e è la norma ℓ2 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

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 ). 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,Tieleman, Tijmen and Hinton, Geoffrey (2012). Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning che vengono comunemente citate come fonte originale per tale metodo. Data la media mobile della norma del gradiente ad ogni iterazione, calcolata in una finestra di iterazioni precedenti