Esercizio - Discesa del gradiente per il LASSO e scelta del passo

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo. Una sola feature centrata $x=[-1{,}5;\,-0{,}5;\,0{,}5;\,1{,}5]$ e uscita centrata $y_c=[-1{,}5;\,-0{,}5;\,1{,}5;\,0{,}5]$ (i dati $x=[1,2,3,4]$, $y=[2,3,5,4]$ senza media; l'intercetta vale $\bar y=3{,}5$ e non si penalizza). Il costo del LASSO è $$J(\beta)=\sum_i(y_{c,i}-\beta x_i)^2+\lambda|\beta|.$$

1. Scrivere il subgradiente di $J$ e il passo di aggiornamento.
2. Con $\lambda=2$ eseguire la discesa del gradiente con passo $\eta=0{,}05$ partendo da $\beta=0$, confrontare con la soluzione esatta e dire per quali $\eta$ l'algoritmo converge.
3. Ripetere con $\lambda=10$ e spiegare il comportamento; mostrare l'effetto del passo adattivo $\eta_t=\eta_0/(1+\gamma t)$.

Teoria usata: LASSO e discesa del gradienteIl LASSO è la regressione regolarizzata con penalità $L_1$: minimizza $\sum_i(y_i-x_i^T\beta)^2+\lambda\sum_{j\ge1}|\beta_j|$. A differenza della ridge, porta alcuni coefficienti esattamente a zero (soluzione sparsa, selezione delle feature): geometricamente le curve di livello dell'errore toccano il vincolo $\sum|\beta_j|\le s$ (un rombo) in uno spigolo. Non ha formula chiusa, quindi si minimizza con la discesa del gradiente $W\leftarrow W-\eta,\nabla J(W)$, usando il subgradiente $\operatorname{sign}(\beta_j)$ per il valore assoluto (nel punto 0 qualunque valore in $[-1,1]$). Il passo $\eta$ è critico: per l'errore quadratico converge se $\eta<1/\mu_{\max}(X^TX)$; si può usare $\eta_t=\eta_0/(1+\gamma t)$. L'Elastic Net combina le penalità $L_1$ e $L_2$ con $\lambda_1=\alpha\lambda$, $\lambda_2=(1-\alpha)\lambda$.LASSO e discesa del gradiente → (subgradiente, passo, soglia morbida); derivate in 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 → e in più variabili Differenziabilità e gradientef è differenziabile in x0 se f(x) = f(x0) + ∇f(x0)·(x − x0) + o(‖x − x0‖): vicino a x0 il grafico si confonde con il piano tangente z = f(x0) + ∇f(x0)·(x − x0). Differenziabile ⇒ continua, derivabile e D_v f = ∇f·v; derivate parziali continue ⇒ differenziabile. Il gradiente indica la direzione di massima crescita (pendenza ‖∇f‖) ed è ortogonale alle curve di livello.Differenziabilità e gradiente →; autovalori in Autovalori e autovettoriUn autovettore è un vettore non nullo che una funzione lineare manda in un suo multiplo; si trovano gli autovalori come radici del polinomio caratteristico det(A − λI) e gli autovettori come nucleo di A − λI. Matrici simili hanno gli stessi autovalori.Autovalori e autovettori →.

1. Subgradiente

Il termine quadratico: $\sum_i(y_{c,i}-\beta x_i)^2=\sum y_c^2-2\beta\sum x_iy_{c,i}+\beta^2\sum x_i^2$. Servono $\sum x_i^2=2{,}25+0{,}25+0{,}25+2{,}25=5$ e $\sum x_iy_{c,i}=2{,}25+0{,}25+0{,}75+0{,}75=4$, quindi il termine vale $\text{costante}-8\beta+5\beta^2$ e la sua derivata è $10\beta-8$. Il termine $\lambda|\beta|$ ha subgradiente $\lambda\operatorname{sign}(\beta)$ (con $\operatorname{sign}(0)=0$, e in $0$ qualunque valore in $[-\lambda,\lambda]$). Quindi $$g(\beta)=10\beta-8+\lambda\operatorname{sign}(\beta),\qquad\beta\leftarrow\beta-\eta\,g(\beta).$$

Soluzione esatta (soglia morbida): per $\beta>0$, $g=0\Rightarrow\beta=\dfrac{8-\lambda}{10}$ (accettabile se $\lambda<8$); per $\beta<0$, $\beta=\dfrac{-8+\lambda}{10}$ (se $\lambda<-8$, impossibile); se $\lambda\ge8$ il minimo è $\beta=0$ (in $0$ il subdifferenziale $[-8-\lambda,\,-8+\lambda]$ contiene $0$ se $\lambda\ge8$). Il coefficiente OLS è $4/5=0{,}8$.

2. $\lambda=2$, $\eta=0{,}05$

Soluzione esatta $\beta^\ast=(8-2)/10=0{,}6$. Iterazioni, $\beta_0=0$:

Si vede che l'errore $\beta_t-0{,}6$ si dimezza a ogni passo: $\beta_{t+1}-0{,}6=(1-10\eta)(\beta_t-0{,}6)=0{,}5\,(\beta_t-0{,}6)$ (infatti per $\beta>0$, $g=10(\beta-0{,}6)$). Dopo 8 passi $\beta=0{,}598$.

Condizione di convergenza. L'errore si moltiplica per $1-10\eta$ ad ogni passo, quindi serve $|1-10\eta|<1\iff0<\eta<0{,}2$. Si ritrova la regola $\eta<1/\mu_{\max}(X^TX)$, con $X^TX=\sum x_i^2=5$ ($\mu_{\max}=5$): $\eta<0{,}2$. Con $\eta=0{,}25$ (troppo grande) si ottiene $\beta=2;\ -1{,}5;\ 4{,}75;\ -5{,}625;\ 10{,}94;\dots$: oscilla e diverge. Con $\eta=0{,}1$ il fattore è $0$: dopo il primo passo ($\beta=0{,}8$) il secondo arriva esattamente a $0{,}6$ (un caso fortunato di questo problema a una variabile).

3. $\lambda=10$: la soluzione è zero

Poiché $\lambda=10\ge8$ la soluzione esatta è $\beta^\ast=0$ (il LASSO azzera la feature). Con $\eta=0{,}05$ il subgradiente non converge a zero: $\beta_t=0{,}4;\ 0{,}1;\ -0{,}05;\ 0{,}875;\ 0{,}3375;\ 0{,}069;\ -0{,}066;\ 0{,}867;\dots$. Il valore oscilla attorno a zero senza fermarsi, con ampiezza dell'ordine di $\eta\lambda=0{,}5$: subito sotto zero il termine $\lambda\operatorname{sign}(\beta)=-10$ spinge con forza verso valori positivi. Con $\eta=0{,}01$ l'oscillazione è più piccola ($0{,}08;\ 0{,}052;\ 0{,}027;\ 0{,}004;\ -0{,}016;\ 0{,}165;\dots$, cioè entro $\approx0{,}17$) ma resta.

Passo adattivo. Con $\eta_t=\dfrac{0{,}05}{1+0{,}2t}$ l'ampiezza decresce: dopo 60 iterazioni $\beta_t\approx0{,}011$. Quindi:

• il subgradiente dà soluzioni approssimate vicino a zero ma non zeri esatti; per ottenerli si tronca a zero quando $|\beta|$ è sotto una tolleranza, oppure si usa la soglia morbida (metodi per coordinate, LARS);
• il passo che decresce stabilizza l'iterazione.

Verifica

import numpy as np
x = np.array([-1.5, -.5, .5, 1.5]); yc = np.array([-1.5, -.5, 1.5, .5])
def gd(lam, eta, n, gamma=0.0):
    b = 0.0
    for t in range(n):
        g = 2 * x @ (b * x - yc) + lam * np.sign(b)       # = 10 b - 8 + lam sign(b)
        b -= eta / (1 + gamma * t) * g
    return b
print(gd(2, 0.05, 60))               # 0.6
print(gd(2, 0.25, 6))                # diverge
print(gd(10, 0.05, 60, gamma=0.2))   # ~0.01: vicino a 0