Skip to content
Torna ai risultati

Discesa del Gradiente Stocastico (SGD)

Introdotto da
Robbins, H. & Monro, S.
Anno
1951
Tipo
First-order iterative optimization algorithm

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

La Discesa del Gradiente Stocastico (SGD) è un algoritmo iterativo di ottimizzazione del primo ordine, radicato nel quadro dell'approssimazione stocastica introdotto da Robbins e Monro nel 1951, che minimizza una funzione obiettivo aggiornando i parametri del modello utilizzando il gradiente calcolato su un singolo esempio di addestramento selezionato casualmente (o un piccolo mini-batch) ad ogni passo.

È il motore di ottimizzazione centrale dietro il machine learning moderno e il deep learning, consentendo l'addestramento di modelli su dataset troppo grandi per essere contenuti nella memoria.

L’intuizione alla base del metodo

La discesa del gradiente ordinaria calcola il gradiente esatto della perdita su tutti gli esempi di addestramento prima di effettuare un singolo aggiornamento dei parametri — corretto ma proibitivamente lento su dataset di grandi dimensioni. La SGD scambia l'esattezza con la velocità: sceglie un esempio (o un piccolo batch) a caso, calcola una stima rumorosa del gradiente e aggiorna immediatamente i parametri. Il rumore non è semplicemente un fastidio; agisce come regolarizzazione implicita, aiutando l'ottimizzatore a sfuggire a minimi locali poco profondi e punti di sella. Nel corso di molte iterazioni, i passi rumorosi si compensano e i parametri convergono verso un minimo della perdita, molto simile a una passeggiata da ubriaco che arriva comunque a destinazione.

Storia

Il fondamento teorico della SGD è stato posto da Herbert Robbins e Sutton Monro nel loro articolo del 1951 'A Stochastic Approximation Method', che dimostrò che aggiornamenti iterativi rumorosi con una dimensione del passo decrescente convergono alla radice di una funzione di regressione. La connessione all'ottimizzazione basata sul gradiente fu resa esplicita da Kiefer e Wolfowitz (1952) e successivamente dalla regola LMS di Widrow e Hoff (1960) per il filtraggio adattivo. La SGD ha guadagnato prominenza nel machine learning attraverso il lavoro di LeCun e collaboratori alla fine degli anni '80 e '90 per l'addestramento di reti neurali tramite backpropagation. La pubblicazione di esperimenti su larga scala da parte di Bottou e collaboratori negli anni 2000 ha dimostrato la superiorità della SGD rispetto ai metodi batch su dataset industriali. La moderna formulazione della SGD con mini-batch è diventata universale con il rinascimento del deep learning intorno al 2012 (AlexNet), e l'algoritmo rimane l'ottimizzatore dominante nel campo, con varianti come Adam (Kingma & Ba, 2014) costruite direttamente sulla sua regola di aggiornamento.

Quando usarlo

La SGD è il metodo di scelta ogni volta che il set di addestramento è sufficientemente grande da rendere troppo costoso il calcolo del gradiente completo per ogni aggiornamento, il che comprende virtualmente tutto l'addestramento moderno di reti neurali e l'adattamento di modelli lineari su larga scala. Si applica a qualsiasi funzione di perdita differenziabile. Assunzioni chiave: la perdita è differenziabile (o sub-differenziabile) rispetto ai parametri, i punti dati sono campionati indipendentemente e lo stimatore del gradiente è non distorto. Per obiettivi fortemente convessi la SGD raggiunge una convergenza O(1/T); per obiettivi generali non convessi (es. reti profonde) trova punti stazionari in pratica, sebbene non esista una garanzia di ottimalità globale. La SGD con mini-batch (dimensione del batch 32–512) è tipicamente preferita rispetto alla SGD pura con singolo esempio perché fornisce stime del gradiente a varianza inferiore e sfrutta il parallelismo sull'hardware moderno. Quando il dataset è abbastanza piccolo per la discesa del gradiente con batch completo e l'obiettivo è ben condizionato, metodi del secondo ordine come L-BFGS possono convergere più velocemente.

Limiti e considerazioni

  • Le stime del gradiente sono rumorose, il che fa fluttuare la perdita anziché diminuirla monotonicamente, rendendo la convergenza più difficile da diagnosticare.
  • Altamente sensibile al tasso di apprendimento: troppo grande causa divergenza; troppo piccolo rende l'addestramento proibitivamente lento.
  • La convergenza a un minimo globale non è garantita per obiettivi non convessi come le reti neurali profonde.
  • Aggiornamenti isotropici trattano tutte le dimensioni dei parametri allo stesso modo, rendendola inadatta a superfici di perdita con curvature molto diverse lungo assi diversi — motivando varianti a tasso adattivo.
  • Richiede un'attenta messa a punto della pianificazione del tasso di apprendimento; pianificazioni scadenti degradano sostanzialmente le prestazioni finali.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Scala a dataset arbitrariamente grandi perché ogni aggiornamento richiede solo un esempio o un mini-batch, mantenendo costanti memoria e calcolo per passo.
  • Il rumore intrinseco fornisce regolarizzazione implicita e aiuta a sfuggire a minimi locali poco profondi e punti di sella in paesaggi non convessi.
  • Estremamente generale: applicabile a qualsiasi perdita differenziabile, inclusa cross-entropia, errore quadratico medio, hinge loss e obiettivi personalizzati.
  • Costituisce la base di quasi tutti gli ottimizzatori moderni (Adam, RMSProp, AdaGrad, Nesterov momentum) — comprendere la SGD è prerequisito per comprenderli.
  • Semplice da implementare e parallelizzare su GPU utilizzando mini-batch.

Applicazioni

  • Addestramento di reti neurali profonde per classificazione di immagini, riconoscimento vocale ed elaborazione del linguaggio naturale.
  • Adattamento di modelli di regressione logistica e SVM lineari su larga scala nella classificazione di testo e nei sistemi di raccomandazione.
  • Contesti di apprendimento online in cui gli esempi arrivano sequenzialmente e il modello deve essere aggiornato in tempo reale.
  • Metodi di gradiente di policy nell'apprendimento per rinforzo, dove il ritorno atteso viene ottimizzato utilizzando traiettorie campionate.
  • Fattorizzazione di matrici per il filtraggio collaborativo nei sistemi di raccomandazione.

Come funziona

Come funziona

1

L'obiettivo di addestramento è la perdita media su tutti gli n esempi. Per compiti come la classificazione con cross-entropia o la regressione con errore quadratico, questa somma può avere miliardi di termini, rendendo impraticabile la valutazione completa ad ogni iterazione.

Formula
L(\theta) = \frac{1}{n} \sum_{i=1}^{n} \ell(f(x_i; \theta),\, y_i)
2

Al passo t, viene campionato uniformemente a caso un singolo esempio di addestramento (o mini-batch). Il gradiente della perdita su quel campione è uno stimatore non distorto del gradiente vero, quindi in media l'aggiornamento punta nella giusta direzione sebbene sia rumoroso per ogni singolo passo.

Formula
\hat{g}_t = \nabla_\theta \ell(f(x_{i_t}; \theta_t),\, y_{i_t})
3

Il vettore dei parametri viene spostato nella direzione opposta alla stima del gradiente, scalato dal tasso di apprendimento eta_t. Un tasso di apprendimento più piccolo rende gli aggiornamenti cauti ma lenti; un tasso più grande accelera la convergenza ma rischia di superare il minimo. Questa singola riga — l'aggiornamento di Robbins–Monro — è il cuore di quasi tutti gli ottimizzatori moderni.

Formula
\theta_{t+1} = \theta_t - \eta_t \, \hat{g}_t
4

Le condizioni di Robbins–Monro (la somma dei tassi diverge, la somma dei quadrati dei tassi converge) garantiscono la convergenza per obiettivi convessi. In pratica, le pianificazioni comuni includono il decadimento a passi (step decay), l'annichilimento del coseno (cosine annealing) e i riavvii a caldo (warm restarts); le condizioni forniscono il fondamento teorico del perché una pianificazione decrescente sia necessaria.

Formula
\sum_{t=1}^{\infty} \eta_t = \infty, \quad \sum_{t=1}^{\infty} \eta_t^2 < \infty

Errori comuni

  • Utilizzare un tasso di apprendimento costante durante tutto l'addestramento senza alcuna pianificazione di decadimento, causando oscillazioni dell'ottimizzatore attorno al minimo anziché stabilizzarsi in esso.
  • Scegliere la dimensione del batch senza considerare l'effetto di regolarizzazione implicita: batch molto grandi riducono il rumore e possono danneggiare la generalizzazione rispetto a batch più piccoli allo stesso numero di epoche.
  • Dimenticare di mescolare (shuffle) i dati di addestramento prima di ogni epoca, il che può introdurre un bias sistematico quando i dati sono ordinati per classe o tempo.
  • Regolare il tasso di apprendimento solo una volta sulla perdita di validazione anziché monitorare le curve di addestramento, perdendo segnali di divergenza o plateau prematuro.
  • Trattare la SGD come un ottimizzatore a scatola nera senza comprenderne le proprietà di convergenza, per poi passare ciecamente ad Adam quando la convergenza sembra lenta senza diagnosticare la causa principale.

Domande frequenti

Qual è la differenza tra SGD, SGD con mini-batch e discesa del gradiente con batch completo?

La discesa del gradiente con batch completo calcola il gradiente esatto su tutti gli n esempi di addestramento per aggiornamento — costo accurato ma O(n) per passo. La SGD pura utilizza esattamente un esempio scelto casualmente per aggiornamento — costo O(1) ma molto rumoroso. La SGD con mini-batch utilizza un piccolo sottoinsieme casuale (tipicamente 32-512 esempi) — un compromesso pratico che riduce il rumore mantenendo il costo gestibile e sfruttando il parallelismo della GPU. Nell'uso moderno, 'SGD' significa quasi sempre SGD con mini-batch.

Come dovrei impostare il tasso di apprendimento?

Non esiste una risposta universale, ma una pratica comune è iniziare con un valore moderato (es. 0.01 o 0.1), monitorare la curva della perdita di addestramento e applicare una pianificazione di decadimento come step decay, cosine annealing o warm restarts. I cercatori di tasso di apprendimento (che provano diversi tassi su alcuni batch e osservano la perdita) possono identificare un buon valore iniziale. La teoria di Robbins-Monro richiede che il tasso decada a zero, ma in pratica il decadimento viene spesso applicato dolcemente per evitare un rallentamento prematuro.

Perché la SGD a volte generalizza meglio di Adam?

Ottimizzatori a tasso adattivo come Adam spesso convergono più velocemente ma possono sovra-adattarsi (overfit) di più, in particolare nei compiti di classificazione di immagini. Il rumore più elevato nella SGD — specialmente con batch di piccole dimensioni — agisce come regolarizzazione implicita, aiutando il modello a trovare minimi più piatti che generalizzano meglio. Diversi studi empirici (es. Wilson et al., 2017) hanno documentato questo fenomeno, motivo per cui la SGD con momentum è ancora preferita per addestrare modelli di computer vision come ResNet.

La SGD garantisce di trovare il minimo globale?

Solo per obiettivi strettamente convessi, sotto le condizioni di dimensione del passo di Robbins-Monro. Per obiettivi non convessi (virtualmente tutte le reti profonde), la SGD fornisce convergenza a un punto stazionario (dove il gradiente è zero), che in pratica tende ad essere un buon minimo locale piuttosto che un punto di sella o il minimo globale. Empiricamente, le soluzioni trovate sono spesso sufficienti per prestazioni allo stato dell'arte.

Metodi correlati

Fonti

  1. Robbins, H. & Monro, S. (1951). A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3), 400–407.

    Apri il riferimento DOI
    Copiato.
  2. Goodfellow, I., Bengio, Y. & Courville, A. (2016). Deep Learning (Ch. 8). MIT Press.

    ISBN: 978-0-262-03561-3
    Copiato.