Comprensione del gradiente medio stocastico

La discesa del gradiente è la tecnica di ottimizzazione più popolare nella modellazione dell'apprendimento automatico (ML). L'algoritmo riduce al minimo l'errore tra i valori previsti e la verità di base. Poiché la tecnica considera ogni punto dati per comprendere e ridurre al minimo l'errore, le sue prestazioni dipendono dalla dimensione dei dati di training. Tecniche come la discesa del gradiente stocastico (SGD) sono progettate per migliorare le prestazioni di calcolo, ma a scapito dell'accuratezza della convergenza.

Stochastic Average Gradient bilancia l'approccio classico, noto come Full Gradient Descent e SGD, e offre entrambi i vantaggi. Ma prima di poter utilizzare l'algoritmo, dobbiamo prima comprenderne l'importanza per l'ottimizzazione del modello.

Ottimizzazione degli obiettivi di apprendimento automatico con discesa del gradiente

Ogni algoritmo ML ha una funzione di perdita associata che mira a minimizzare o migliorare le prestazioni del modello. Matematicamente, la perdita può essere definita come:

Si tratta semplicemente della differenza tra il risultato effettivo e quello previsto, e minimizzare questa differenza significa che il nostro modello si avvicina di più ai valori di verità di base.

L'algoritmo di minimizzazione usa la discesa del gradiente per attraversare la funzione di perdita e trovare un minimo globale. Ogni passaggio di attraversamento comporta l'aggiornamento dei pesi dell'algoritmo per ottimizzare l'output.

Discesa con gradiente semplice

L'algoritmo di discesa del gradiente convenzionale utilizza la media di tutti i gradienti calcolati sull'intero set di dati. Il ciclo di vita di un singolo esempio di training è il seguente:

L'equazione di aggiornamento del peso si presenta come segue:

Dove W rappresenta i pesi del modello e dJ/dW è la derivata della funzione di perdita rispetto al peso del modello. Il metodo convenzionale ha un alto tasso di convergenza ma diventa computazionalmente costoso quando si ha a che fare con grandi set di dati che comprendono milioni di punti dati.

Discesa del gradiente stocastico (SGD)

La metodologia SGD rimane la stessa del GD semplice, ma invece di usare l'intero set di dati per calcolare i gradienti, usa un piccolo batch dagli input. Il metodo è molto più efficiente ma potrebbe saltare troppo attorno ai minimi globali poiché ogni iterazione usa solo una parte dei dati per l'apprendimento.

Gradiente medio stocastico

L'approccio Stochastic Average Gradient (SAG) è stato introdotto come via di mezzo tra GD e SGD. Seleziona un punto dati casuale e aggiorna il suo valore in base al gradiente in quel punto e a una media ponderata dei gradienti passati memorizzati per quel particolare punto dati.

Simile a SGD, SAG modella ogni problema come una somma finita di funzioni convesse e differenziabili. A ogni data iterazione, utilizza i gradienti attuali e la media dei gradienti precedenti per l'aggiornamento del peso. L'equazione assume la seguente forma:

Tasso di convergenza

Tra i due algoritmi più diffusi, il gradiente completo (FG) e la discesa del gradiente stocastico (SGD), l'algoritmo FG ha un tasso di convergenza migliore poiché utilizza l'intero set di dati durante ogni iterazione per il calcolo.

Sebbene SAG abbia una struttura simile a SGD, il suo tasso di convergenza è paragonabile e talvolta migliore dell'approccio full gradient. La Tabella 1 di seguito riassume i risultati degli esperimenti di Schmidt e altri .

Ulteriori modifiche

Nonostante le sue prestazioni sorprendenti, sono state proposte diverse modifiche all'algoritmo SGD originale per migliorarne le prestazioni.

• Riponderazione nelle prime iterazioni: la convergenza SAG rimane lenta durante le prime iterazioni poiché l'algoritmo normalizza la direzione con n (numero totale di punti dati). Ciò fornisce una stima imprecisa poiché l'algoritmo deve ancora vedere molti punti dati. La modifica suggerisce di normalizzare per m anziché per n, dove m è il numero di punti dati visti almeno una volta fino a quella particolare iterazione.
• Mini-batch: l'approccio Stochastic Gradient utilizza mini-batch per elaborare più punti dati contemporaneamente. Lo stesso approccio può essere applicato a SAG. Ciò consente la vettorializzazione e la parallelizzazione per una migliore efficienza del computer. Riduce inoltre il carico di memoria, una sfida importante per l'algoritmo SAG.
• Sperimentazione Step-Size: la dimensione del passo menzionata in precedenza (116L) fornisce risultati sorprendenti, ma gli autori hanno ulteriormente sperimentato utilizzando la dimensione del passo di 1L. Quest'ultima ha fornito una convergenza ancora migliore. Tuttavia, gli autori non sono stati in grado di presentare un'analisi formale dei risultati migliorati. Concludono che la dimensione del passo dovrebbe essere sperimentata per trovare quella ottimale per il problema specifico.

Considerazioni finali

La discesa del gradiente è un'ottimizzazione popolare utilizzata per localizzare i minimi globali delle funzioni obiettivo fornite. L'algoritmo utilizza il gradiente della funzione obiettivo per attraversare la pendenza della funzione fino a raggiungere il punto più basso.

Full Gradient Descent (FG) e Stochastic Gradient Descent (SGD) sono due varianti popolari dell'algoritmo. FG utilizza l'intero set di dati durante ogni iterazione e fornisce un'elevata velocità di convergenza a un elevato costo di elaborazione. A ogni iterazione, SGD utilizza un sottoinsieme di dati per eseguire l'algoritmo. È molto più efficiente ma con una convergenza incerta.

Stochastic Average Gradient (SAG) è un'altra variante che offre i vantaggi di entrambi gli algoritmi precedenti. Utilizza la media dei gradienti passati e un sottoinsieme del set di dati per fornire un elevato tasso di convergenza con un basso calcolo. L'algoritmo può essere ulteriormente modificato per migliorarne l'efficienza utilizzando la vettorizzazione e i mini-batch.