Esercizio - Gradient descent, batch GD, SGD e minibatch SGD (esempio d'esame 2)

Teoria: Apprendimento automatico nell'IA - supervisionato, SVM e valutazioneQuadro del machine learning nel corso di IA. Tre forme di apprendimento: supervisionato (coppie ingresso-uscita, classificazione se l'uscita è discreta e regressione se è un numero), non supervisionato (pattern senza feedback, per esempio clustering) e per rinforzo (ricompense). Un'ipotesi h approssima la funzione vera f e si valuta sul test set, non sul training set: un modello troppo semplice ha bias alto (underfitting), uno troppo complesso varianza alta (overfitting). Servono training, validation e test set; con pochi dati si usa la k-fold cross-validation. Alberi di decisione: si sceglie l'attributo con massimo guadagno d'informazione Gain = B(p/(p+n)) - somma (Nk/N) B(pk/Nk), si pota con il test del chi quadro (Delta > Delta*), si riduce la varianza con bagging e random forest. Perdita L1 e L2, regressione lineare e discesa del gradiente w <- w - alpha dL/dw. SVM: separatore a margine massimo, vettori di supporto, kernel trick con K(xj,xk). Pipeline scikit-learn del laboratorio 10: load_digits, train_test_split, SVC(C, kernel, gamma), fit, predict, classification_report, confusion_matrix, cross_val_score.Apprendimento automatico nell'IA - supervisionato, SVM e valutazione → (sezione 5), 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 → e 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 →. Domanda 2 del quiz da 9 CFU e domanda 1 di quello da 6 CFU: testo identico.

Testo (risposta aperta). Con riferimento ad algoritmi per machine learning, si spieghi brevemente cosa sono e quali sono le principali differenze tra Gradient Descent (GD), batch GD, Stochastic Gradient Descent (SGD) e minibatch SGD.

Risposta modello

Addestrare un modello vuol dire minimizzare una perdita $L(w)=\sum_{j=1}^{N}L_j(w)$, somma degli errori sugli $N$ esempi del training set, rispetto ai pesi $w$. Il gradient descent è il metodo iterativo che, partendo da pesi iniziali, li aggiorna a ogni passo nella direzione opposta al gradiente (la direzione di massima discesa): $$w\leftarrow w-\alpha\,\nabla_w L,$$ con $\alpha$ passo di apprendimento (learning rate). Con perdita convessa converge al minimo globale se $\alpha$ non è troppo grande; se lo è, il passo supera il minimo e la perdita cresce. Le varianti differiscono per quanti esempi si usano per stimare il gradiente a ogni aggiornamento.

• Batch GD (il GD "classico"): il gradiente è calcolato su tutti gli $N$ esempi, $\nabla L=\sum_j\nabla L_j$, e si fa un aggiornamento per epoca (un'epoca è un passaggio completo sui dati). Gradiente esatto, traiettoria regolare e deterministica; ma ogni passo costa $O(N)$ ed è lento o non entra in memoria con dataset grandi.
• SGD (stochastic): a ogni aggiornamento si usa un solo esempio scelto a caso. Si fanno $N$ aggiornamenti per epoca, ciascuno economico; il gradiente è una stima rumorosa ma non distorta di quello vero, quindi la perdita oscilla (il rumore aiuta a uscire da minimi locali e zone piatte) e, con $\alpha$ costante, si assesta intorno al minimo senza raggiungerlo; per convergere si fa decrescere $\alpha$.
• Minibatch SGD: si usano $m$ esempi (tipicamente 32, 64, 128 o 256) scelti a caso. Compromesso: rumore ridotto di un fattore circa $\sqrt m$ rispetto all'SGD puro, calcolo vettorizzato efficiente su GPU, memoria limitata. È la variante usata in pratica, e quando nelle librerie (Keras) si parla di SGD si intende di solito questa.

Il caso limite $m=N$ è il batch GD e $m=1$ è l'SGD puro: si distinguono solo per $m$.

Esempio numerico

Dati $(1,2)$, $(2,3)$, $(3,5)$, ipotesi $h(x)=w_1x+w_0$, perdita $L_j=(y_j-h_j)^2$, partenza $w_0=w_1=0$, $\alpha=0{,}02$. Con $w=0$ l'errore $y_j-h_j$ è $y_j$. Per ogni esempio $\partial L_j/\partial w_0=-2e_j$ e $\partial L_j/\partial w_1=-2x_je_j$.

Il minimo esatto è $w_1=1{,}5$, $w_0=\tfrac13$: il passo batch è il più grande e preciso, l'SGD fa passi piccoli e rumorosi ma ne fa tre per epoca. Con $N=1000$ esempi e $m=32$ si fanno $\lceil1000/32\rceil=32$ aggiornamenti per epoca (31 minibatch completi e uno da 8), contro $1$ del batch e $1000$ dell'SGD.

Errori tipici nella risposta: dire che SGD usa "un sottoinsieme" (è un solo esempio) o che il batch GD è stocastico; non spiegare che cosa cambia (quanti esempi per aggiornamento, rumore, costo); dimenticare il learning rate.