L’algoritmo di Discesa del Gradiente spiegato semplice

Immaginiamo di voler trovare il percorso più veloce per raggiungere una destinazione in auto. Si potrebbe utilizzare una mappa stradale per stimare la distanza e il tempo di percorrenza di diverse strade. Tuttavia, questo metodo non tiene conto del traffico, che può variare in modo significativo durante il giorno.

La Discesa del Gradiente (Gradient Descent) può essere utilizzata per trovare il percorso più veloce in tempo reale. In questo caso:

• La funzione di costo rappresenta il tempo di percorrenza del viaggio.
• Il parametro da ottimizzare è il percorso da seguire.
• Il gradiente indica la direzione in cui il tempo di percorrenza aumenta più rapidamente.

L’algoritmo di Discesa del Gradiente può quindi essere utilizzato per aggiornare il percorso in modo iterativo, avvicinandosi ad ogni iterazione al percorso più veloce.

Cerchiamo ora di dare mettere un po’ di ordine tra le definizioni.

La Discesa del Gradiente è un algoritmo che cerca di trovare il minimo di una funzione obiettivo, cioè il valore più basso possibile che la funzione può assumere. Per fare questo, l’algoritmo parte da un punto casuale e si sposta in direzione opposta al gradiente, cioè la direzione in cui la funzione cresce più rapidamente. Il gradiente è calcolato come la derivata della funzione, cioè la pendenza della curva in un punto. Più il gradiente è alto, più la funzione è ripida.

Cominciamo il nostro percorso…e cerchiamo di minimizzare la funzione di costo!

Il tasso di apprendimento

Il tasso di apprendimento è un parametro che determina quanto l’algoritmo si sposta ad ogni passo. Se il tasso di apprendimento è troppo alto, l’algoritmo potrebbe saltare il minimo e andare oltre.
Se il tasso di apprendimento è troppo basso, l’algoritmo potrebbe impiegare troppo tempo a raggiungere il minimo o fermarsi prima.
Il tasso di apprendimento deve essere scelto in modo da bilanciare velocità ed accuratezza. Si tratta di un punto estremamente importante e delicato da considerare.

Il criterio di arresto

Il criterio di arresto è una condizione che stabilisce quando l’algoritmo deve fermarsi. Può essere basato sul numero di passi, sulla differenza tra due valori consecutivi della funzione obiettivo, o su un valore soglia prefissato. Il criterio di arresto serve a evitare che l’algoritmo continui a girare inutilmente o si blocchi in un punto che non è il minimo.

Un’analogia per capire meglio la discesa del gradiente è quella di una persona che cerca di scendere da una montagna senza vedere dove va. La persona può usare una bussola per orientarsi e seguire la direzione in cui la pendenza è maggiore. La persona può anche decidere quanto camminare ad ogni passo e quando fermarsi, a seconda di quanto è stanco o sicuro di sé.

Un esempio di discesa del gradiente applicata al machine learning è quello della regressione lineare, cioè il metodo per trovare la retta che meglio approssima un insieme di punti. La funzione obiettivo in questo caso è l’errore quadratico medio tra i punti e la retta, cioè la somma dei quadrati delle distanze verticali tra i punti e la retta divisa per il numero dei punti.
L’obiettivo è trovare i parametri della retta (intercetta e coefficiente angolare) che minimizzano questo errore.
La discesa del gradiente parte da una retta casuale e aggiorna i parametri in base al gradiente dell’errore quadratico medio, fino a raggiungere una retta ottimale.

Un altro esempio di discesa del gradiente applicata al machine learning è quello delle reti neurali, cioè dei modelli matematici che imitano il funzionamento dei neuroni biologici.
Le reti neurali sono composte da diversi strati di nodi (neuroni) collegati tra loro da pesi (sinapsi). Ogni nodo riceve degli input dagli strati precedenti, li combina con i pesi e produce un output per gli strati successivi.
La funzione obiettivo in questo caso è la differenza tra l’output desiderato e quello effettivo della rete neurale, cioè l’errore di predizione. L’obiettivo è trovare i pesi che minimizzano questo errore.
La discesa del gradiente parte da dei pesi casuali e li aggiorna in base al gradiente dell’errore di predizione, fino a raggiungere una rete neurale ottimale.

La funzione obiettivo e la funzione di costo

La funzione obiettivo e la funzione di costo sono termini che si usano spesso in modo intercambiabile, ma hanno anche delle sfumature diverse a seconda del contesto.

In generale, la funzione obiettivo è una funzione che si vuole ottimizzare, cioè massimizzare o minimizzare, in base a un certo criterio. La funzione di costo è un tipo di funzione obiettivo che misura il “costo” o la “perdita” associati a una soluzione o a una previsione. In altre parole, la funzione di costo è una funzione obiettivo che si vuole minimizzare.

Ad esempio, se si vuole trovare la retta che meglio approssima un insieme di punti, si può usare la regressione lineare. In questo caso, la funzione obiettivo è l’errore quadratico medio tra i punti e la retta, cioè la somma dei quadrati delle distanze verticali tra i punti e la retta divisa per il numero dei punti. Questa funzione obiettivo è anche una funzione di costo, perché rappresenta il costo di avere una retta non perfetta. L’obiettivo è trovare i parametri della retta che minimizzano questo costo.

Tuttavia, non tutte le funzioni obiettivo sono funzioni di costo.

Alcune funzioni obiettivo possono essere funzioni di utilità, di guadagno, di verosimiglianza, ecc. Queste sono funzioni che si vogliono massimizzare, perché rappresentano il beneficio o la probabilità associati a una soluzione o a una previsione. In questo caso, non si parla di costo o di perdita, ma di ottimizzazione.

Ad esempio, se si vuole trovare il modello probabilistico che meglio descrive un insieme di dati, si può usare il metodo della massima verosimiglianza. In questo caso, la funzione obiettivo è la probabilità di generare l’insieme di dati dato il modello, cioè il prodotto delle probabilità di ogni dato dato il modello. Questa funzione obiettivo non è una funzione di costo, ma una funzione di verosimiglianza.
L’obiettivo è trovare i parametri del modello che massimizzano questa verosimiglianza.

Un esempio semplicissimo di codice

Per mantenere il massimo della semplicità nell’esposizione fornisco un esempio in R di implementazione di un algoritmo di Discesa del Gradiente, con mere finalità didattiche. Ecco il codice:

# Funzione di costo
f <- function(x) {
  return(x^2 + 2*x + 1)
}

# Derivata della funzione di costo
df <- function(x) {
  return(2*x + 2)
}

# Parametri iniziali
x <- 1
tasso_apprendimento <- 0.1

# Ciclo di iterazioni
for (i in 1:10) {
  # Calcolo del gradiente
  gradiente <- df(x)
  
  # Aggiornamento del parametro
  x <- x - tasso_apprendimento * gradiente
  
  # Stampa del valore corrente
  print(x)
}

il codice è volutamente molto semplice, e lo andiamo a esaminare riga per riga:

Passo 1: Funzione di costo

La funzione f <- function(x) { return(x^2 + 2*x + 1) } definisce la funzione di costo che vogliamo minimizzare. In questo caso, la funzione è una parabola semplice con un minimo in x = -1.

Passo 2: Derivata della funzione di costo

La funzione df <- function(x) { return(2*x + 2) } calcola la derivata della funzione di costo rispetto a x. La derivata ci indica la direzione in cui la funzione cresce più rapidamente.

Passo 3: Parametri iniziali

Le variabili x <- 1 e tasso_apprendimento <- 0.1 definiscono i parametri iniziali dell’algoritmo. La variabile x rappresenta il valore iniziale del parametro da ottimizzare, mentre tasso_apprendimento controlla la velocità di convergenza dell’algoritmo.

Passo 4: Ciclo di iterazioni

Il ciclo for (i in 1:10) esegue 10 iterazioni dell’algoritmo di Discesa del Gradiente. In ogni iterazione, le seguenti operazioni vengono eseguite:

• Calcolo del gradiente: La funzione df(x) viene utilizzata per calcolare il gradiente della funzione di costo nel punto corrente x.
• Aggiornamento del parametro: Il valore di x viene aggiornato sottraendo al gradiente un fattore proporzionale al tasso di apprendimento.
• Stampa del valore corrente: Il valore corrente di x viene stampato a schermo.

Discesa del Gradiente: Vantaggi e Svantaggi

In generale, la Discesa del Gradiente è un algoritmo di ottimizzazione versatile e potente che può essere utilizzato per risolvere una varietà di problemi. Tuttavia, è importante essere consapevoli dei suoi vantaggi e svantaggi per scegliere l’algoritmo più adatto al problema specifico.

Vantaggi:

• Semplicità: L’algoritmo di Discesa del Gradiente è relativamente semplice da comprendere e implementare.
• Efficienza: L’algoritmo è efficiente in termini di tempo e di memoria, soprattutto per problemi di dimensioni moderate.
• Flessibilità: La Discesa del Gradiente può essere applicata a una varietà di problemi di ottimizzazione con diverse funzioni di costo e vincoli.
• Robustezza: L’algoritmo è robusto e generalmente converge a una soluzione, anche se la funzione di costo non è convessa.

Svantaggi:

• Convergenza locale: L’algoritmo può convergere a un minimo locale anziché a un minimo globale, soprattutto se la funzione di costo è non convessa.
• Sensibilità al tasso di apprendimento: La scelta del tasso di apprendimento può influenzare significativamente la velocità di convergenza e la qualità della soluzione.
• Difficoltà di tuning: La regolazione dei parametri dell’algoritmo può essere difficile, soprattutto per problemi complessi.
• Lentezza per problemi di grandi dimensioni: L’algoritmo può diventare lento per problemi di grandi dimensioni con un elevato numero di parametri.