Discesa gradiente

Aggiornato su September 24, 2024 3 minuti a leggere

Introduzione

Immaginiamo di avere una funzione $f(x)$ e di volerne trovare il minimo. Cosa faresti ?

Semplice vero? Dobbiamo solo risolvere la seguente equazione:

$$f’(x) = 0$$

Il fatto è che trovare la formula di $f’$ non è sempre facile poiché tendono ad essere estremamente complicate soprattutto nel deep learning dove abbiamo a che fare con funzioni complesse. Dobbiamo quindi trovare un altro metodo che possa fornirci il minimo di una funzione senza la necessità di trovare la formula della derivata $f’$.

Costruiamo un po’ di intuizione

Supponiamo di avere una funzione f con il grafico corrispondente:

Graph 1

Iniziamo con un punto casuale $x_{0}$. L’obiettivo è spostare questo punto e renderlo sempre più vicino a $x*$ in modo tale che $f’($x*$) = 0$. Quindi il problema può essere diviso in due parti:

In quale direzione dovremmo spostare il punto $x$ ? Sinistra o destra?
Di quanto dovremmo spostarlo?

La direzione

Costruiamo un po’ di intuizione per rispondere alla prima domanda. Dai un’occhiata al seguente punto:

Graph 2

Graph 3

Notare che:

quando il punto $x_{0}$ è a destra del punto ottimo $x*$ la sua retta tangente va verso l’alto.
quando il punto $x_{0}$ è a destra del punto ottimo $x*$ la sua retta tangente va verso il basso.

La direzione di una linea è determinata dal segno della sua pendenza:

Una linea sale $\implica$ che la pendenza $a$ è positiva.
Una linea scende $\implica$ che la pendenza $a$ è negativa.

Nota che: \

La pendenza della retta tangente di una funzione in un certo punto $x_{0}$ non è maggiore della derivata in quel punto $f’(x_{0})$:

$$ tangent(x*{0}): g(x) = f’(x*{0}).(x-x*{0}) + f(x*{0}) $$

Quindi, come risposta alla domanda “Dove dovremmo spostare $x_{0}$?”:

$f’(x_{0}) < 0$ $\implies$ $x_{0}$ a destra di $x*$ $\implies$ Dobbiamo spostare $x_{0}$ a sinistra.
$f’(x_{0}) > 0$ $\implies$ $x_{0}$ a sinistra di $x*$ $\implies$ Dobbiamo spostare $x_{0}$ a destra.

I passaggi

Veniamo ora alla seconda domanda: Di quanto dovremmo spostare $x_{0}$?

Dai un’occhiata ai seguenti esempi:

Graph 4

Graph 5

Possiamo concludere che:

$x_{0}$ è vicino a $x*$ => La pendenza della tangente è piccola => $f’(x_{0})$ è piccola.
$x_{0}$ è distante da $x*$ => La pendenza della tangente è grande => $f’(x_{0})$ è grande.

Rispondendo ad entrambe le domande, abbiamo concluso che solo la conoscenza della derivata nel punto $x_{0}$ può darci molte informazioni sulla direzione e la distanza del punto ottimo $x_{0}$.

Discesa gradiente

La discesa del gradiente è la formulazione delle risposte delle due domande precedenti. È un algoritmo iterativo di ottimizzazione che approssima il minimo $x*$ di una funzione a partire da un punto iniziale casuale $x_{0}$. L’algoritmo è indicato come segue:

$$ x*{n+1} = x*{n} - lr \times \frac{\mathrm{d} f}{\mathrm{d} x_{n}} $$

Dove:

$ \frac{\mathrm{d} f}{\mathrm{d} x*{n}} $ non è altro che la derivata di $f$ nel punto $x*{n}$.
$lr$ è una costante positiva che determina la grandezza dei passi.

Si noti che:

$x_{n}$ è a destra di $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} > 0 $ => $ x_{n+ 1} = x_{n} - positivo $ => $x_{n}$ si sposta a sinistra.
$x_{n}$ è a sinistra di $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} < 0$ => $ x*{n +1} = x*{n} + positivo $ => $x_{n}$ si sposta a destra.
$x_{n}$ vicino a $x*$ => $\frac{\mathrm{d} f}{\mathrm{d} x_{n}}$ vicino a $0$ => Piccolo aggiornamento a $x_{ n}$.

##Quiz

Quando la discesa del gradiente interrompe l’iterazione:
Quando $x_{n}$ è abbastanza piccolo.
Quando $x_{n}$ è vicino a $x_{0}$ .
Quando $\frac{\mathrm{d} f}{\mathrm{d} x_{n}} = 0 $. XXX
Come scegliamo $x_{0}$:
Lo scegliamo a caso. XXX
Lo prendiamo nell’intorno di $x{n}$.
Dipende dal problema.
Perché abbiamo bisogno della discesa del gradiente:
Perché i computer non sono abbastanza potenti per calcolare le derivate.
Perché è estremamente difficile trovare le formule derivate dei modelli di deep learning. XXX
Perché le funzioni hanno più di un minimo locale.