Articoli

Spiegazione grafica del metodo di discesa del Gradiente (Momentum, AdaGrad, RMSProp, Adam)

Autore:  Lili Jiang

Cattura 2 1

Grazie alle molteplici ricerche riguardanti la discesa del Gradiente, in questo post, vorrei graficamente spiegarvi come funzionano questi metodi. Con l’utilizzo di uno strumento di visualizzazione di discesa del Gradiente che ho costruito, spero di potervi trasmettere informazioni utili, o perlomeno alcune immagini.

Suppongo che già si abbiano delle conoscenze basi, riguardo il come e il perché, la discesa gradiente è utilizzato nel machine learning (se così non fosse, consiglio di vedermi il video di 3Blue1Brown).

Il mio obbiettivo è quello di mettere a confronto e in contrasto questi metodi, se non avete ancora una certa familiarità con i seguenti metodi, potete scorrere verso il basso e guardare alcuni divertenti video “d’ippica”.

Vanilla Gradient Descent

Diamoci una rinfrescata. Nell’apprendimento meccanico, l’obiettivo della discesa del Gradiente normalmente è quello di minimizzare la funzione di perdita per un problema di machine learning. Un buon algoritmo cerca il minimo in modo veloce ed affidabile (cioè: non si arresta in un minimo locale, o in punto di sella, o livelli fissi, ma punta al minimo globale). L’algoritmo base di discesa del gradiente segue l’idea che la direzione opposta dei punti di pendenza è dove si trova l’area inferiore. Quindi iterativamente prosegue nelle direzioni opposte dei gradienti. Per ogni parametro theta, bisogna eseguire la seguente operazione:

delta = – tasso_di_apprendimento* gradiente theta += delta

Theta è lo stesso parametro che voi volete ottimizzare (il peso di una connessione neurone-neurone nella rete neurale, il coefficiente di una caratteristica per la funzione nella regressione lineare etc.) ci possono essere migliaia di Theta in un’impostazione di ottimizzazione di ML. Delta è la quantità della variazione di Theta dopo ogni iterazione nell’algoritmo, l’aspettativa è che con ogni cambiamento, Theta si avvicini progressivamente all’ottimale.

Cattura 3

(illustrazione passo dopo passo dell’algoritmo della discesa del Gradiente)

La percezione umana è limitata alla terza dimensione, in tutti i miei esempi, supponiamo di avere solo due parametri (Theta) da ottimizzare, e nel grafico sono rappresentati dalle dimensioni X e Y. La superficie è la funzione di perdita. Noi dobbiamo trovare (X e Y) la combinazione che è al punto più basso della superficie. Il problema è irrilevante perché noi possiamo vedere tutta la superficie, ma la sfera (il discendente algoritmico) neanche può; può solo fare un passo alla volta ed esplorare il suo ambiente circostante, come camminare nel buio con solo una torcia.

La discesa del Gradiente vanilla, è vanilla perché è presente solo nei gradienti. Il seguente metodo rende alcune ulteriori elaborazioni migliori e più veloci.

 

Momentum

cattura 4

La discesa del Gradiente con l’algoritmo momentum (o Momentum) prende in prestito le idee dalla fisica. Immagina di far rotolare una palla dentro una cavità senza attrito. Invece di fermarsi sul fondo, il mometum che ha accumulato lo spinge in avanti, e la palla continua a rotolare avanti e dietro.

Possiamo applicare l’idea di momentum al nostro algoritmo di discesa del Gradiente Vanilla. In ogni passo, in aggiunta al solito Gradiente, si aggiunge anche al movimento del passo precedente. Matematicamente viene espresso cosi:

delta = – tasso_di apprendimento * gradiente + delta_precedente * tasso_decadimento (eq. 1)

theta += delta (eq. 2)

 

Io l’ho trovo molto comprensibile, se invece il contenuto di questa equazione contenesse un po’ della somma cumulativa del Gradiente (decomposto). Ciò renderebbe le cose più facili quando successivamente andremo ad introdurre l’algoritmo di Adam:

somma_del_gradiente = gradiente + precedente_somma_del_gradiente * tasso_di_decadimento (eq. 3)

delta = -tasso_di apprendimento * somma_del_gradiente (eq. 4)

theta += delta (eq. 5)

(Quello che ho fatto è stato factoring out -learning_rate. Per vedere l’equazione matematica, puoi sostituire delta con -learning_rate*sum_of_gradient in eq. 1 per ottenere l’eq. 3.)

 

Cattura6

 

Didascalia: Illustrazione dettagliata del momentum descent. Guarda l’animazione dal vivo nell’app. Per il resto di questo post, uso gradiente x e gradiente y nella visualizzazione; in realtà, poiché è la *discesa* gradiente, effettivamente è il negativo del gradiente.

Consideriamo due casi estremi per capire meglio questo parametro del tasso di decadimento. Se il tasso di decadimento è 0, allora è esattamente lo stesso della discesa del Gradiente (vanilla). Se il tasso di decadimento è 1 (e purché il tasso di apprendimento sia abbastanza piccolo), allora oscilla avanti e indietro all’infinito come l’analogia della ciotola senza attrito che abbiamo menzionato all’inizio. Voi non volete questo. Solitamente il tasso di decadimento viene scelto intorno a 0.8-0.9 è simile alla superficie con un può d’attrito così alla fine rallenta e si ferma.

 

immage 6

 

Didascalia: Momentum (magenta) vs la discesa del Gradiente (cyan) su una superficie con un minimum globale (sinistra) e un minimo locale (destra).

Quindi, in quale modo il Momento è migliore della discesa del Gradiente Vanilla? nel paragone di sinistra, potete notare 2 vantaggi:

  1. Momentum si muove più velocemente (a causa di tutto l’accumulo sul Momentum)
  2. Momentum ha la possibilità di sfuggire ai minimi locali (perché il Momentum potrebbe spingere fuori al minimum locale). Allo stesso modo, come vedremo più tardi, avrà anche la capacità di attraversare meglio  le regioni dell’altopiano.

 

AdaGrad

Invece di tenere traccia della somma del Gradiente come Momentum, l’algoritmo del Gradiente Adattivo, o AdaGrad, tiene traccia della somma del Gradiente al quadrato e lo utilizza per adattare il Gradiente in diverse direzioni. Spesso l’espressione viene espressa in tensori. Eviterò i tensori per semplificare il linguaggio. Per ogni dimensione:

somma_del_gradiente_al quadtrato = somma_del gradiente_precedente_al quadrato + gradiente² 

delta = -tasso_di apprendimento * gradiente / sqrt (somma_del_gradiente_al quadrato) theta += delta 

 

 

Cattura 7

Didascali: Illustrazione dell’AdaGrad passo dopo passo. Guarda l’animazione dal vivo con nell’ app.

Nell’ottimizzazione in ML, alcune caratteristiche sono sparse. Il gradiente standard per le caratteristiche sparse è solitamente piccolo, quindi tali caratteristiche vengono addestrate ad un ritmo molto più lento. Un modo per risolvere questo problema è quello di impostare l’apprendimento dei tassi per ogni caratteristica, ma ciò risulterebbe difficile.

AdaGrad affronta questo problema utilizzando quest’idea: più hai aggiornato una caratteristica, meno la aggiornerai in futuro, dando così la possibilità alle altre caratteristiche di recuperare (ad esempio le caratteristiche sparse). Visivamente, quanto avete aggiornato queste caratteristiche è come dire quanto vi siete mossi in questa dimensione e questo concetto viene acquisita dalla somma cumulativa di gradiente quadrato. Notare nella griglia d’illustrazione sopra come, passo dopo passo, senza la regolazione di ridimensionamento (1b) la palla si sarebbe spostata principalmente in modo verticale verso il basso; con il ridimensionamento (1b), si muove diagonalmente.

 

cattura 8

Didascalia: AdaGrad (bianco) vs la discesa del Gradiente (cyan) su un terreno con punta a sella. Lo studio del tasso di AdaGrad è situato nella parte più alta rispetto alla discesa del Gradiente, ma il punto del percorso di AdaGrad è più dritto e rimane principalmente vero a prescindere dal tasso di apprendimento.

Questa proprietà permette ad AdaGrad (o altri simili metodi di gradiente al quadrato come like RMSProp and Adam) di fuggire in un punto di sella migliore. AdaGrad prenderà un percorso rettilineo, mentre la discese del Gradiente (Momemtum) segue l’approccio “lasciatemi prima scivolare giù per il ripido pendio e forse più tardi mi preoccuperò della direzione più lenta”. Spesso la discesa del Gradiente vanilla potrebbe semplicemente fermarsi al punto di sella dove i gradienti in entrambe le direzioni equivalgono a 0 ed essere perfettamente a loro agio lì.

 

RMSProp

Il problema di AdaGrad, tuttavia, è quello di essere incredibilmente lento, perché la somma del gradiente al quadrato cresce solo e non si ristringe. RMSProp (Root Mean Square Propagation) corregge questo problema aggiungendo un fattore di decadimento.

somma_del_gradiente_quadrato = somma_precedente_del _gradiente_quadrato * tasso_di_decadimento+ gradiente² * (1-tasso_di_decadimento)

delta = -tasso_di_apprendimento* gradiente / sqrt(somma_del_gradiente_quadrato)

theta += delta

Precisamente, la somma del gradiente al quadrato è in realtà la somma decomposta del gradiente al quadrato. Il tasso di decadimento sta indicando solo le sfumature recenti del gradiente ², e quelli affrontati tanto tempo fa sono praticamente dimenticate. Come nota a margine, il termine “tasso di decadimento” è un po’ improprio. A differenza del tasso di decadimento che abbiamo visto nel Momentum, oltre al decadimento, il tasso di decadimento in questo caso ha anche un effetto di ridimensionamento: riduce l’intero termine per un fattore di (1 – tasso_di_decadimento). In altre parole, se il tasso_di_decadimento è di 0.99, oltre al decadimento, la somma del gradiente al quadrato sarà sqrt (1-0.99) = 0.1 del AdaGrad quindi il passo è sull’ordine di 10 volete per lo stesso tasso di apprendimento.

Cattura8

 

Didascali: RMSProp (verde) vs AdaGrad (bianco). Il primo run mostra solo le sfere, il secondo run mostra anche la somma del gradiente al quadrato rappresentato attraverso quadrati.

Per osservare l’effetto del decadimento, in questo confronto testa a testa, AdaGrad (bianco) sta al passo con RMSProp (verde) inizialmente, come previsto con il tasso di apprendimento e il tasso di decadimento. La somma del Gradiente al quadrato si accumulano così velocemente che presto diventeranno enormi (dimostrato dalle dimensioni dei quadrati nell’animazione). Questi hanno un pesante costo, e prima o poi AdaGrad smette di muoversi. RMSProp, invece, ha mantenuto i quadrati sotto una dimensione gestibile per tutto il tempo, grazie al decadimento del tasso. Ciò rende RMSProp più veloce di AdaGrad.

 

Adam

L’ultimo ma non per importanza, Adam (abbreviazione per Adaptive Moment Estimation), prende il meglio di entrambi i metodi, Momentum e RMSProp. Adam empiricamente funziona bene, per tanto negli ultimi anni viene comunemente scelto per i problemi di apprendimento profondo.

Guardiamo come esso lavora:

somma_del_gradiente = somma_del_gradiente_precedente * beta1 + gradiente * (1 – beta1) [Momentum]

somma_del_gradiente_quadrato = somma_del_gradiente_precedente_quadrato * beta2 + gradiente² * (1- beta2) [RMSProp]

delta = – tasso_di_appredimento * somma_del_gradiente / sqrt(somma_del_gradiente_quadrato)

theta += delta 

Beta1 è il tasso decadente per il primo momento, la somma del gradiente (aka momentum), comunemente fissato a 0.9. Beta2 è il tasso decadente del secondo momento, la somma del gradiente quadrato, è comunemente fissato a 0.999.

 

Cattura89

Didascalia: Passo dopo passo viene illustrato Adam descent. Guarda l’animazione dal vivo tramite l’app.

Adam ottiene la velocità dal Momentum e dal RMSProp la capacità di adattare i gradienti in direzioni diverse. La combinazione fra queste due lo rende potente.

 

In conclusione

Ora che abbiamo parlato di tutti i metodi, andiamo a guardare alcune competizioni fra questi metodi di discesa di cui abbiamo parlato fin ora! (ci sono alcune inevitabili scelte selettive di parametri. Il miglior modo per testarlo è mettersi in gioco).

In questo terreno, ci sono due piccole colline che bloccano la strada al minimo globale. Adam è l’unico in grado di cercare una strada al minimum globale. In qualsiasi modo i parametri siano sintetizzati, almeno da questa posizione di partenza, nessuno di questi metodi può andare bene. Ciò significa che né il Momentum né il solo Gradiente adattato può indurci in inganno. È in realtà la combinazione fra questi due: il primo, Momentum prende Adam oltre il minimo locale dove tutte le altre sfere si fermano; quindi, l’aggiustamento dalla somma del Gradiente quadrato lo spinge di lato, perché questa è la direzione meno esplorata, dirigendolo alla vittoria.

 

Qui c’è un’altra gara. In questo terreno, c’è una regione piana (plateau) la zona del minimo globale. Con alcune parametrizzazioni, Momentum e Adam (grazie alla sua componete momentum) possono arrivare al centro. Mentre gli altri metodi non possono.

 

In Sintesi, la discesa del Gradiente è un tipo di algoritmo che mira a cercare il punto minimum nella funzione seguendo il Gradiente. La discesa del Gradiente Vanilla solo segue il Gradiente (scalando il tasso di appredimento). Due strumenti comuni per migliorare la discesa del Gradiente sono la somma dei gradienti (nel primo momentum) e la somma del gradiente quadrato (nel secondo momentum). Il metodo del Momentum viene usato nella prima situazione con il tasso di decadimento per guadagnare velocità. AdaGrad usato nel secondo momentum senza decadimento per affrontare le caratteristiche sparse. RMSProp viene usato nel secondo momentum con il tasso di decadimento accelerato da AdaGrad. Adam usa entrambi primo e secondo momentum, ed è effettivamente la migliore scelta. Ci sono poche altre varianti degli algoritmi della discesa del gradiente, ad esempio l’acceleratore del Gradiente Nesterov, AdaDelta etc… che non sono compresi nell’articolo.

 

Infine vi lascerò con questa discesa del Momentum senza decadimento. Il suo percorso costituisce un modello divertente. Non ho visto un uso pratico (ancora) ma lo metto qui solo perché è divertente. [Edit: mi rimangio la parola, riguardo l’uso prativo. Per maggiori informazioni riguardo questa curva https://en.wikipedia.org/wiki/Lissajous_curve.]

 

 

Gioca con lo strumento di visualizzazione che è utilizzato per generare tutta la visualizzazione di quest’articolo, e vedi cosa trovi!

 

References e Link: