Discesa gradiente

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:

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:

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:

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.