Gradient Descent è un algoritmo di ottimizzazione generico in grado di trovare soluzioni ottimali per una vasta gamma di problemi. L’idea generale della discesa del gradiente è modificare i parametri in modo iterativo per ridurre al minimo una funzione di costo.
In altre parole, ciò significa trovare i parametri del modello (ad es. coefficienti o pesi) che minimizzino l’errore del modello nel set di dati di addestramento.
In questo modo, il modello fa previsioni sui dati di addestramento e utilizza l’errore sulle previsioni per aggiornare il modello stesso al fine di ridurre l’errore, come abbiamo visto nel precedente articolo.
In questa sede ci concentriamo su un esempio dell’algoritmo Gradient Descent in linguaggio python. In primo luogo ci concentriamo nel risolvere un problema di regressione lineare utilizzando il Batch Gradient Descent, una tipologia di Gradient Descent e successivamente vediamo come questo risultato si modifica utilizzando il Stochastic Gradient Descent, altro tipo di discesa del gradiente.
L’esempio è tratto dal libro di Hands on Machine Learning di Aurelien Geron.
Regressione lineare
In termini matematici la regressione lineare multipla assume un modello come il seguente:
Dove:
- ŷ è la risposta ai valori, ossia rappresenta il risultato previsto dal modello;
- θ0 è l’intercetta, ossia il valore di ŷ quando gli xi sono tutti uguali a 0;
- θ1 è il coefficiente di X1 (la prima caratteristica);
- θn è il coefficiente di Xn (l’ennesima caratteristica);
- x1,x2, …, xn sono le variabili indipendenti del modello.
Questa equazione l’avevamo già vista anche in questo articolo (al posto di Theta si è utilizzato Beta).
Per trovare i vari valori di theta occorre minimizzare il valore dell’errore quadratico medio. Si ricorda che l’errore quadratico medio (MSE o Mean Squared Error) è quell’errore che mostra quanto bene o male il modello descrive il set di dati analizzato. La formula per calcolarlo è la seguente:
Più l’MSE è elevato e meno il modello rappresenta ciò che stiamo studiando e viceversa. Pertanto è bene cercare di ottenere un errore quadratico medio più piccolo possibile.
Per fare questo ovviamente ci può essere utile la discesa del gradiente.
Batch Gradient Descent
L’errore quadratico medio rappresenta la funzione costo che il gradiente andrà a minimizzare.
Il Batch Gradient Descent (o algoritmo discesa del gradiente a Batch) è una tipologia di discesa del gradiente.
La sua particolarità è che calcola l’errore per ciascun esempio nel set di dati di addestramento, ma aggiorna il modello solo dopo aver valutato tutti gli esempi di addestramento.
Un ciclo attraverso l’intero set di dati di allenamento è chiamato un’epoca di allenamento. Pertanto, si dice spesso che la discesa del gradiente batch esegua gli aggiornamenti del modello alla fine di ogni epoca di allenamento.
Di conseguenza è terribilmente lento su set di dati di allenamento molto grandi. Tuttavia, la discesa del gradiente si adatta bene al numero di funzioni: l’addestramento di un modello di regressione lineare quando ci sono centinaia di migliaia di funzioni è molto più veloce usando la Discesa del gradiente che usando l’equazione normale o la decomposizione SVD (Singular Value Decomposition).
Stochastic Gradient Descent
La discesa stocastica del gradiente, spesso abbreviata in SGD, è una variazione dell’algoritmo di discesa del gradiente che calcola l’errore e aggiorna il modello per ciascun esempio nel set di dati di addestramento.
L’aggiornamento del modello per ciascun esempio di addestramento significa che la discesa graduale stocastica è spesso chiamata algoritmo di apprendimento automatico online.
D’altra parte, a causa della sua natura stocastica (cioè casuale), questo algoritmo è molto meno regolare della variante vista poco fa: invece di diminuire delicatamente fino a raggiungere il minimo, la funzione di costo rimbalzerà su e giù, diminuendo solo in media.
Nel tempo finirà molto vicino al minimo, ma una volta arrivato continuerà a rimbalzare, senza mai stabilizzarsi. Quindi, una volta che l’algoritmo si ferma, i valori dei parametri finali sono buoni, ma non ottimali.
Quando la funzione di costo è molto irregolare, può effettivamente aiutare l’algoritmo a uscire dai minimi locali, quindi la Discesa del gradiente stocastica ha maggiori possibilità di trovare il minimo globale rispetto alla Discesa gradiente batch.
Pertanto la casualità è buona per sfuggire all’ottimo locale, ma è cattiva perché significa che l’algoritmo non può mai stabilizzarsi al minimo. Una soluzione a questo dilemma è ridurre gradualmente il tasso di apprendimento.
I passaggi iniziano in grande (il che aiuta a fare rapidi progressi e sfuggire ai minimi locali), quindi diventano sempre più piccoli, consentendo all’algoritmo di stabilizzarsi al minimo globale. Questo processo è simile all’algoritmo simulated annealing, un algoritmo ispirato al processo di ricottura in metallurgia in cui il metallo fuso viene lentamente raffreddato.
La funzione che determina il tasso di apprendimento ad ogni iterazione è chiamata programma di apprendimento. Se il tasso di apprendimento viene ridotto troppo rapidamente, potresti rimanere bloccato in un minimo locale o persino finire congelato a metà al minimo.
Regressione Lineare in Python
Vediamo dapprima di prendere un’equazione lineare da cui partire a prevedere dei valori. L’equazione utilizzata è:
y = 3 * x + 4 + errore statistico.
Definiamo il nostro dataset di 100 valori e poi avvalendosi di sklearn possiamo digitare le seguenti righe di codice:
Dopo aver importato le librerie (numpy, matplotlib) richiamato la funzione di LinearRegression, adattiamo il modello ai nostri dati e calcoliamo il valore dell’intercetta e del coefficiente. Avremo:
Dopodichè prevediamo i valori nella variabile y_pred e visualizziamo i dati su un grafico, grazie alla libreria matplotlib:
Batch Gradient Descent in Python
Per implementare il Batch Gradient Descend bisogna definire innanzitutto il Learning Rate (eta) e il numero di iterazioni che l’algoritmo dovrà eseguire (n_iterations).
Definiamo anche il valore di X_b richiamando la funzione np.ones di numpy per avere un array (100, 2), ossia 100 righe e 2 colonne, dove il primo valore di tutte le 100 righe è composto da 1.
Con un learning rate pari a 0,1 e il numero di iterazioni pari a 1000 l’algoritmo ottiene il seguente risultato:
La procedura è quella di determinare un valore casuale di theta che segua una distribuzione normale standard, avvalendosi della libreria numpy, della funzione random.randn.
Dopodichè si esegue un ciclo for, e per ogni iterazione viene calcolato il gradiente e aggiornato theta.
Il gradiente viene così calcolato attraverso il prodotto scalare tra la trasposta di X_b e tra il prodotto scalare di X_b e theta precedentemente diminuito del valore di y.
Come si può vedere il risultato è vicino a quanto ottenuto con il modello sopra.
Ora le iterazioni sono 1000, qualora ne avessimo milioni, il Batch Gradient Descent le valuterebbe prima tutte prima di fare una modifica al modello.
Stochastic Gradient Descent in Python
Vediamo ora come calcolare la Stochastic Gradiend Descent in Python. Vengono definite sempre le epoche e due iperparametri t0 e t1, che ci servono per calcolare il programma di apprendimento o learning schedule.
Dopo aver definito il programma di apprendimento, si inizializza theta come abbiamo visto per il batch gradient descent.
Per convenzione, ripetiamo cicli di ripetizioni; anche qua ogni round è chiamato un’epoca.
Mentre il codice di Discesa del gradiente batch è stato ripetuto 1.000 volte nell’intero set di addestramento, questo codice passa attraverso il set di training solo 50 volte e raggiunge una soluzione abbastanza buona:
Ad ogni iterazione, viene calcolato un indice random che segue una distribuzione uniforme tramite la funzione np.random.randint.
Ciò serve ad aggiornare i valori di xi e yi, necessari al calcolo del gradiente.
Anche qua il calcolo del gradiente è simile a quanto visto per il Batch Gradient Descent, quello che cambia è che esso dipende dal valore di xi e yi, che si modificano ad ogni iterazione.
Successivamente viene aggiornato il tasso di apprendimento eta e infine calcolato theta per ogni epoca.
Questo algoritmo è possibile implementarlo anche utilizzando Scikit-Learn, utilizzando meno righe di codice:
Ancora una volta, si trova una soluzione molto simile a quelle restituite sopra:
Conclusione
In questo articolo abbiamo visto un esempio di come implementare l’algoritmo discesa del gradiente per un problema di regressione lineare in linguaggio python.
Abbiamo visto due variazioni dell’algoritmo, il Batch Gradient Descent e il Stochastic Gradient Descent, per risolvere un problema di regressione lineare.
Il primo è più adatto nei casi in cui non si deve trattare con un elevato set di dati, mentre il secondo è più propenso ad errori, ma comunque in grado di trovare velocemente una soluzione buona (minimo locale).
Potrebbe valere la pena considerare di utilizzare una via di mezzo tra i due, il Mini-Batch Gradient Descent come capita per le reti neurali.
