Stochastic Gradient Descent, Batch Gradient Descent Algorithm

Lo Stochastic Gradient Descent algorithm, il Batch Gradient Descent algorithm e il Mini-Batch Gradient Descent algorithm sono algoritmi di ottimizzazione.

Abbiamo definito cosa siano e compreso il principio della “discesa del gradiente“ e come si questo si collochi all’interno di una rete neurale.

Ora è giunto il momento di analizzare le differenti varianti del gradient descent!

Le differenze riguardano due aspetti:

• Numero di dati richiesti per il calcolo del gradiente a ogni iterazione.
• Accuracy-Time Complexity Trade-Off, ovvero il compromesso tra l’accuratezza del gradiente e il time complexity vale a dire il tempo richiesto dall’algoritmo per l’update dei parametri: è il learning rate.

Batch Gradient Descent

Il Batch Gradient Descent esegue una sommatoria di tutte le osservazioni a ogni iterazione e aggiorna di conseguenza i parametri.

Quando il numero di istanze del dataset aumenta a svariate milioni o miliardi, passare in rassegna l’intero dataset per ogni iterazione diviene un’attività computazionale sconsiderata.

Perché sceglierlo? Per diverse ragioni.

Innanzitutto evita la necessità di cambiare il learning rate, potendo scegliere di mantenerlo fisso. Niente learning rate decay, che approfondiremo nel post dedicato al learning rate.

In più ci assicura convergenza a un minimo globale, qualora la cost function fosse convessa, e a un minimo locale in caso contrario.

Inoltre all’aumentare delle dimensioni del dataset, l’errore standard diminuisce: il gradiente è stimato senza bias.

Non mancano certo gli svantaggi, che si concentrano principalmente sul sistema di funzionamento: l’iterazione sull’intero dataset a ogni epoca. Questo genera problemi di lentezza di convergenza.

Mini-batch gradient Descent

Contrariamente al suo fratello maggiore, questa variante del gradient descent considera un sottoinsieme del dataset per operare il calcolo del gradiente.

La dimensione del sottoinsieme è gestita dal batch size.

È fondamentale rimescolare (shuffle) il dataset, per massimizzare le prestazioni dell’algoritmo.

A livello di funzionamento, per completezza, è interessante sapere che qualora il batch size scelto non fosse un divisore della dimensione del dataset, la porzione rimanente costituirebbe un batch a sé stante.

Generalmente i valori scelti per il batch size sono potenze di 2: 32, 64, 128, 256, 512, etc. Questo perché le operazioni di calcolo sono quasi sempre svolte dalle GPU, che raggiungono risultati migliori proprio con potenze di 2.

I vantaggi più degni di nota sono:

• velocità di esecuzione maggiore del batch version
• selezione randomica dei samples

Gli svantaggi da considerare invece:

• Nessuna convergenza. A ogni epoca il learning step aumenterà o diminuirà a causa del rumore: saremo vicini al minimo ma non lo raggiungeremo mai.
• La presenza di rumore genera oscillazioni e richiede l’impostazione di un learning-decay in modo che il learning rate diminuisca all’avvicinamento del punto di minimo

È interessante notare come a settaggio di un batch size pari alla dimensione del dataset (b = m) il Mini-batch gradient descent diventa un batch gradient descent algorithm.

Stochastic Gradient Descent

Noto anche come SGD, lo Stochastic Gradient Descent calcola il gradiente aggiornandolo dopo ogni osservazione, a differenza delle varianti precedenti che calcolavano la sommatoria.

Anche lo Stochastic Gradient Descent necessita del rimescolamento del dataset affinché possa funzionare al meglio.

Inoltre, poiché viene considerata una sola osservazione alla volta, il rumore del percorso è superiore a quello del Batch Gradient Descent, quindi più randomico. Si tratta di un’informazione utile al solo scopo conoscitivo, tenuto presente il nostro unico interesse sia il raggiungimento del punto di minimo nel minor tempo possibile.

Un caldo abbraccio, Andrea