Metodo di discesa del gradiente (caso scalare)

Come ottimizzare la funzione di costo?

Nell’articolo introduttivo alla matematica delle reti neurali, che trovi qui sotto, abbiamo visto che uno dei passaggi fondamentali per ottenere buona rete, in grado di risolvere il problema che ci interessa, è minimizzare una funzione di costo/loss.

Introduzione alla minimizzazione in una variabile

Prima di avventurarci a studiare problemi di ottimizzazione complicati, è importante partire da qualche esempio più semplice e trattabile. Questo è l’obiettivo di questo articolo.

Consideriamo una funzione scalare di una variabile f e assumiamo che ammetta abbastanza derivate continue così da giustificare i passaggi che seguono.

I punti critici di questa funzione sono tutti e soli quei punti della retta reale nei quali la derivata f ' si azzera, ovvero l’insieme qui sotto

\(\mathcal{C} = \{x\in\mathbb{R}:f'(x)=0\}.\)

Nel caso in cui la seconda derivata in un punto critico sia positiva, allora tale punto è un minimo. In altre parole,

\(x^*\in \arg\min f(x) \iff \left(f'(x^*)=0,\,f''(x^*)>0\right).\)

Per esempio, nel caso la funzione f sia convessa, allora si ha sempre che f ''(x)>0 e quindi tutti i punti critici sono minimi. Questo è uno dei motivi per cui le funzioni convesse sono tra le più studiate nel campo dell’ottimizzazione, insieme alle molte altre proprietà favorevoli che le caratterizzano.

Esempio

Supponiamo ora di voler risolvere il seguente problema di minimo

\(\min_{x\in\mathbb{R}}f(x),\,\,f(x):=(x^2-3)^2.\)

Notiamo che f è limitata dal basso, dato che è sempre non-negativa. Inoltre si ha che f(x)=0 quando |x| coincide con la radice di 3. Studiando la derivata prima e seconda notiamo che

\(\begin{split} f'(x)&=2(x^2-3)(2x) = 4x(x^2-3),\\ f''(x)&=4(x^2-3)+4x(2x)=12(x^2-1) \end{split}\)

Notiamo che la derivata seconda è positiva quando |x| è la radice di 3, e quindi f è minimizzata in entrambi i punti, come si può vedere dal grafico qui sotto.

In teoria il problema è risolto, però nella pratica la radice di 3 non è un numero razionale e quindi va approssimato. Questo è un semplice esempio per far capire come anche per problemi molto semplici di minimizzazione, è fondamentale avere a disposizione dei metodi numerici che ci permettono di approssimare la soluzione.

Metodo di discesa del gradiente

Il metodo del gradiente è il più semplice metodo numerico di questo tipo. L’idea è piuttosto intuitiva e voglio illustrarla prima con questo esempio e poi la vediamo nel caso vettoriale, che è molto più interessante. Vedremo l’estensione al caso vettoriale in un articolo separato, per non appesantire questo eccessivamente.

Il metodo del gradiente è un metodo iterativo. Ciò vuol dire che si parte da una soluzione iniziale che si ritiene sia ragionevole, oppure anche da un punto casuale, e poi la si va a migliorare fino a che non si è contenti abbastanza della qualità della soluzione prodotta.

L’algoritmo è definito come segue:

\(x_0\in\mathbb{R},\tau>0,\,\,x_{k+1}=x_k-\tau f'(x_k),\,k=0,1,... . \)

Tipicamente il metodo viene stoppato quando siamo vicini ad un punto stazionario oppure quando abbiamo fatto un numero troppo alto di iterate. Il primo criterio d’arresto si traduce nella seguente condizione

\(|f'(x_k)|\leq \text{tol},\)

dove tol è una tolleranza che fissiamo a priori. L’idea dietro questo metodo è relativamente intuitiva. Infatti ricordiamo che la derivata di una funzione in un punto è positiva se la funzione è localmente crescente, è negativa se decrescente, e si azzera nei punti stazionari. Questo metodo non fa altro che dire di spostarci a sinistra se la funzione è crescente, così da abbassarne il valore, e verso destra se la funzione è decrescente.

Per questo articolo introduttivo mi interessa comunicare l’intuizione geometrica, quindi rimandiamo l’analisi di alcune proprietà di convergenza ad un articolo futuro. Questo seguirà all’articolo dove estenderemo l’algoritmo a funzioni a più variabili, ma anche ad un successivo articolo dove vedremo le principali proprietà delle funzioni convesse.

Alcuni conti per capire l’algoritmo

Torniamo, per concludere, al nostro esempio di sopra. La cosa interessante sarà infatti vedere a quale dei due minimi convergiamo nel momento in cui andiamo a cambiare il valore iniziale x_0.

Per prendere la mano con il metodo, vediamo qualche iterazione esplicitamente. Poi, subito dopo questi brevi conti, puoi trovare degli esperimenti numerici che ho fatto (con Python) per mostrare le iterazioni e dove convergiamo.

Partiamo dal punto x_0 = 1. Ricordiamo che

\(f(x)=(x^2-3)^2,\,f'(x)=4x(x^2-3).\)

Consideriamo il passo tau = 1/16. Segue che le prime iterate sono della forma

\(\begin{split} x_1 &= x_0-\frac{1}{16}\,f'(x_0) = 1-\frac{1}{16}\,4\cdot 1\,(1^2-3) \\ &= 1-\frac{1}{16}(-8) = 1+\frac12 = \frac32,\\[6pt] x_2 &= x_1-\frac{1}{16}\,f'(x_1) = \frac32-\frac{1}{16}\,4\cdot\frac32\!\left(\frac{9}{4}-3\right) \\ &= \frac32-\frac{1}{16}\!\left(6\cdot\bigl(-\tfrac34\bigr)\right) = \frac32+\frac{9}{32} = \frac{57}{32},\\[6pt] x_3 &= x_2-\frac{1}{16}\,f'(x_2) \\ &= \frac{57}{32}-\frac{1}{16}\,4\cdot\frac{57}{32} \left(\left(\frac{57}{32}\right)^{2}-3\right) \;\approx\; 1.7043.\\ \end{split}\)

Da qui si può ovviamente andare avanti. Notiamo però che già alla terza iterazione siamo abbastanza vicini alla radice di 3, che vale circa 1.732050808.

Prima di passare ad un bel grafico, per anticipare la necessità di una teoria matematica di questo metodo, ti consiglio degli esercizi relativamente veloci ma illuminanti secondo me:

• Cosa succede se x_0 = 0?

• Cosa succede se x_0 = 1 e tau = 1/8?

• Cosa succede se x_0 = 1 e tau = 1/4?

Se hai voglia di risolverli, fammi sapere nei commenti i tuoi risultati e possiamo discutere dei risvolti più generali legati a questi risultati.

Nel grafico qui sotto vedi sull’asse x il numero da cui parte l’algoritmo, mentre sull’asse y il numero a cui arriviamo dopo 30 iterazioni del metodo del gradiente. Ho considerato 100 condizioni iniziali x_0 random nell’intervallo [-2,2]. Vedi che se parti abbastanza vicino a zero ma alla sua sinistra, allora convergi al minimo negativo, mentre convergi a quello positivo se parti con x_0 piccolo abbastanza ma positivo. Ci sarebbe molto di più da dire anche solo su questo esempio, ma direi che abbiamo già coperto molte cose interessanti!

Fammi sapere se hai domande o cosa ne pensi di questa serie di articoli. Ci vediamo al prossimo!