Esercizio - Discesa del gradiente, momento e Adam a mano

Testo. Si minimizza $J(w)=(w-3)^2$ partendo da $w_0=0$.

1. Discesa del gradiente con $\eta=0{,}1$: i primi quattro passi. Per quali $\eta$ converge?
2. SGD con momento ($\rho=0{,}9$, $\alpha=0{,}1$): i primi quattro passi.
3. Adam ($\alpha=0{,}1$, $\beta_1=0{,}9$, $\beta_2=0{,}999$, $\varepsilon\approx0$): i primi tre passi.
4. RMSProp (decadimento $0{,}9$, $\alpha=0{,}1$) e AdaGrad ($\alpha=0{,}1$): il primo e il secondo passo.
5. Quante iterazioni per epoca fa un mini-batch da $B=64$ su $n=60\,000$ campioni?

Teoria usata: Addestramento delle reti neurali - backpropagation e ottimizzatoriAddestrare una rete significa minimizzare la loss empirica $J(W)=\frac1n\sum_i\mathcal L(f(x^{(i)};W),y^{(i)})$ con la discesa del gradiente $W\leftarrow W-\eta,\partial J/\partial W$; in pratica a mini-batch (SGD). Il gradiente di tutti i pesi si ottiene con la backpropagation, cioè la regola della catena applicata all'indietro: $\delta^{(L)}=\partial J/\partial a^{(L)}\odot g'(z^{(L)})$, $\delta^{(l)}=(W^{(l+1)\top}\delta^{(l+1)})\odot g'(z^{(l)})$, $\partial J/\partial W^{(l)}=\delta^{(l)}a^{(l-1)\top}$ (con sigmoide e cross-entropy $\delta=\hat y-y$). Per far funzionare reti profonde: attivazioni ReLU, inizializzazione di Xavier o He (varianza $2/(n_{in}+n_{out})$ e $2/n_{in}$), batch normalization, ottimizzatori con momento o adattivi (Momentum, AdaGrad, RMSProp, Adam con $\beta_1=0{,}9$, $\beta_2=0{,}999$, lr $10^{-3}$) e un learning rate che varia nel tempo (a gradini, coseno). Si addestra tenendo d'occhio la loss di training e di validazione.Addestramento delle reti neurali - backpropagation e ottimizzatori →, Gradiente e direzione di massima crescitaIl gradiente è il vettore delle derivate parziali ∇f(p) = (∂₁f(p), …, ∂ₙf(p)). Se f è C¹ (derivate parziali continue) vale la formula del gradiente D_u f(p) = ∇f(p)·u: tutte le derivate direzionali si ottengono dalle parziali e u ↦ D_u f(p) è lineare. Tra i versori, la crescita è massima lungo ∇f/|∇f| (pendenza |∇f|), minima lungo −∇f/|∇f| (pendenza −|∇f|), nulla lungo le direzioni ortogonali al gradiente. Utili: ∇|x| = x/|x|, ∇φ(|x|) = φ'(|x|) x/|x|.Gradiente e direzione di massima crescita →, Derivata - definizione e significatoLa derivata è il limite del rapporto incrementale; geometricamente è la pendenza della retta tangente. f è derivabile in x0 se e solo se f(x) = f(x0) + f'(x0)(x − x0) + o(x − x0); derivabile implica continua, non viceversa. Derivata destra e sinistra, punti angolosi, flessi a tangente verticale, cuspidi.Derivata - definizione e significato →.

Il gradiente è $g(w)=J'(w)=2(w-3)$.

1. Discesa del gradiente

Regola: $w\leftarrow w-\eta\,g(w)=w-0{,}1\cdot2(w-3)=0{,}8\,w+0{,}6$.

La distanza dal minimo si moltiplica per $1-2\eta$ a ogni passo: $w-3\leftarrow(1-2\eta)(w-3)$. Converge se $|1-2\eta|<1$, cioè $0<\eta<1$; per $\eta=0{,}5$ arriva al minimo in un passo; per $\eta>1$ la distanza cresce in modulo e il segno alterna (divergenza).

2. Momento

Regole: $v\leftarrow\rho v+g(w)$, $w\leftarrow w-\alpha v$, con $v_0=0$.

Il primo passo coincide con la discesa semplice ($0{,}6$). Poi la velocità accumulata fa superare il minimo ($w_4=3{,}926>3$): il momento accelera ma può oltrepassare; successivamente il gradiente cambia segno e la velocità si smorza. Nella discesa semplice $w_4=1{,}771$: il momento è molto più avanti.

3. Adam

Regole: $m_t=\beta_1m_{t-1}+(1-\beta_1)g_t$, $v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2$, $\hat m_t=m_t/(1-\beta_1^t)$, $\hat v_t=v_t/(1-\beta_2^t)$, $w\leftarrow w-\alpha\,\hat m_t/\sqrt{\hat v_t}$.

• Passo 1. $g_1=-6$: $m_1=-0{,}6$, $v_1=0{,}001\cdot36=0{,}036$; $\hat m_1=-0{,}6/0{,}1=-6$, $\hat v_1=0{,}036/0{,}001=36$; $\hat m_1/\sqrt{\hat v_1}=-6/6=-1$, quindi $w_1=0+0{,}1=0{,}1$. Il primo passo ha ampiezza $\alpha$, qualunque sia la scala del gradiente.
• Passo 2. $g_2=2(0{,}1-3)=-5{,}8$: $m_2=0{,}9(-0{,}6)+0{,}1(-5{,}8)=-1{,}12$, $v_2=0{,}999\cdot0{,}036+0{,}001\cdot33{,}64=0{,}06960$; $\hat m_2=-1{,}12/(1-0{,}81)=-5{,}895$, $\hat v_2=0{,}0696/(1-0{,}998001)=34{,}82$, $\sqrt{\hat v_2}=5{,}901$; rapporto $-0{,}999$, $w_2=0{,}1+0{,}0999=0{,}1999$.
• Passo 3. $g_3=2(0{,}1999-3)=-5{,}600$: dopo le correzioni $\hat m_3=-5{,}786$, $\hat v_3=33{,}67$, rapporto $-0{,}997$, $w_3=0{,}2996$.

Adam avanza circa $\alpha=0{,}1$ per passo (il rapporto $\hat m/\sqrt{\hat v}\approx\pm1$ quando il gradiente ha segno costante), a prescindere dalla grandezza del gradiente. Con $\alpha=0{,}1$ servono circa $30$ passi per arrivare a $w\approx3$, più lento qui della discesa semplice (che lo fa in meno passi su questo problema comodo), ma robusto su problemi con scale di gradiente molto diverse tra i parametri.

4. RMSProp e AdaGrad

RMSProp. $s\leftarrow0{,}9\,s+0{,}1\,g^2$, $w\leftarrow w-\alpha\,g/\sqrt s$.

• Passo 1: $g=-6$, $s=0{,}1\cdot36=3{,}6$, $\sqrt s=1{,}897$; $w_1=0+0{,}1\cdot6/1{,}897=0{,}316$.
• Passo 2: $g=2(0{,}316-3)=-5{,}367$; $s=0{,}9\cdot3{,}6+0{,}1\cdot28{,}81=6{,}121$, $\sqrt s=2{,}474$; $w_2=0{,}316+0{,}1\cdot5{,}367/2{,}474=0{,}533$.

AdaGrad. $s\leftarrow s+g^2$, $w\leftarrow w-\alpha\,g/\sqrt s$.

• Passo 1: $s=36$, $w_1=0+0{,}1\cdot6/6=0{,}1$.
• Passo 2: $g=-5{,}8$, $s=36+33{,}64=69{,}64$, $\sqrt s=8{,}345$; $w_2=0{,}1+0{,}1\cdot5{,}8/8{,}345=0{,}1695$.

AdaGrad accumula $s$ senza dimenticare: il passo si rimpicciolisce a ogni iterazione ($0{,}1;\,0{,}0695;\,0{,}056$), che a lungo andare lo ferma. RMSProp, con la media mobile, tiene $s$ limitato e passi più grandi.

5. Iterazioni per epoca

$\lceil60\,000/64\rceil=\lceil937{,}5\rceil=938$ iterazioni (l'ultimo batch ha $32$ campioni). Con $B=32$ sarebbero $1\,875$.

Controllo con il codice

import numpy as np
g = lambda w: 2 * (w - 3)
w, m, v = 0., 0., 0.
for t in range(1, 4):                                  # Adam
    gr = g(w); m = .9*m + .1*gr; v = .999*v + .001*gr**2
    w -= .1 * (m/(1-.9**t)) / (np.sqrt(v/(1-.999**t)) + 1e-8)
    print(t, round(w, 4))                              # 0.1  0.1999  0.2996