Cenni a reinforcement learning e reti per sequenze

L'ultima lezione ("What's next") ripassa la pipeline di ML (dati, modello, loss, ottimizzatore, framework) e apre tre direzioni: i modelli generativi (VAE e GAN, in Autoencoderapprofondimento: non nel programma di Telecomunicazioni. Un autoencoder è una rete non supervisionata che impara a ricostruire il proprio ingresso passando per un collo di bottiglia: encoder $z=e(x)$ (dimensione bassa), decoder $\hat x=d(z)$, loss $|x-d(e(x))|^2$. Con attivazioni lineari equivale alla PCA; con non linearità impara rappresentazioni latenti più ricche (ipotesi del manifold). Varianti: sparse (penalità $\ell_1$ sulle attivazioni), denoising (ingresso corrotto, bersaglio pulito), convolutivi (inpainting). Anomaly detection: si addestra su dati normali e si segnala come anomalo ciò che ha errore di ricostruzione sopra una soglia. VAE: l'encoder produce media e deviazione standard di una gaussiana, il campione si ottiene con il trucco di riparametrizzazione $z=\mu+\sigma\odot\zeta$, $\zeta\sim\mathcal N(0,I)$, e la loss è errore di ricostruzione più KL verso $\mathcal N(0,I)$, con $KL=\frac12\sum(\mu^2+\sigma^2-1-\ln\sigma^2)$; il $\beta$-VAE pesa il KL con $\beta>1$ per rappresentazioni disaccoppiate. Cenno ai GAN.Autoencoder →), il reinforcement learning e l'apprendimento su sequenze. Sono cenni, senza esercizi.

1. Reinforcement learning

L'apprendimento supervisionato ha un «supervisore» che dà la risposta giusta per ogni esempio. In molti problemi non c'è: un'auto a guida autonoma sa percepire l'ambiente con il ML, ma deve anche pianificare e controllare le azioni, e il risultato di un'azione si vede solo dopo, a lungo termine. Negli scacchi la vera ricompensa è vincere la partita, e perdere un pezzo può essere la mossa giusta.

Definizione (reinforcement learning, RL). Area del ML e paradigma di apprendimento che si occupa di imparare a controllare un sistema (con molti elementi sconosciuti) interagendo con esso, per massimizzare una misura numerica di prestazione. I dati si raccolgono durante l'interazione con l'ambiente.

Elementi:

• agente: l'entità che deve risolvere il compito;
• stato $S_t$: descrizione completa del sistema (agente e ambiente) al tempo $t$;
• azioni: le scelte dell'agente (che possono dipendere dallo stato);
• ambiente: ciò con cui l'agente interagisce; a ogni istante dà una ricompensa (reward) $R_{t+1}$ per la coppia stato-azione;
• politica $\pi$: la regola con cui l'agente sceglie l'azione in ogni stato.

Esempio (dal film «Ricomincio da capo»). Phil, intrappolato in un ciclo temporale, è l'agente; le azioni sono comportarsi in vari modi (gentile, divertente...) a partire da stati diversi (al ristorante, al parco); l'ambiente è la città con i suoi abitanti; iterando raccoglie dati e impara come massimizzare la ricompensa (far innamorare Rita).

Esempi di ricompensa: per un veicolo, $+$ se segue la traiettoria, $-$ per ogni istante impiegato, $-\!-\!-$ forte per lo schianto; nei giochi, $\pm$ per vittoria/sconfitta o proporzionale al punteggio; per l'energia di un impianto HVAC (riscaldamento, ventilazione, condizionamento), $-$ per l'energia spesa e per il disagio degli utenti; nel trading, proporzionale al guadagno in euro; nella pubblicità e nei sistemi di raccomandazione, $\pm$ se la proposta è seguita o ignorata. Altre applicazioni: robot, droni, AlphaGo, videogiochi (Atari), sanità, chatbot (RLHF, reinforcement learning da feedback umano).

Il ritorno

L'obiettivo è la somma delle ricompense accumulate, il ritorno (return). A orizzonte finito (episodio che termina al tempo $T$):

$$G_t=R_{t+1}+R_{t+2}+\dots+R_T.$$

A orizzonte infinito la somma potrebbe divergere: si sconta il futuro con un fattore $\gamma\in[0,1)$, perché una ricompensa lontana vale meno di una vicina:

$$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\dots=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}.$$

Se le ricompense sono limitate da $R_{max}$ la serie geometrica converge: $G_t\le R_{max}\sum_k\gamma^k=\frac{R_{max}}{1-\gamma}$ (Serie di potenze e serie di TaylorLe serie di potenze sono serie di funzioni della forma $\sum a_n(x-x_0)^n$. Esse convergono assolutamente all'interno del raggio di convergenza $\rho$ e uniformemente nei compatti interni, permettendo l'integrazione e la derivazione termine a termine.Serie di potenze e serie di Taylor →). $\gamma$ vicino a $0$ rende l'agente miope; vicino a $1$ lungimirante.

La convergenza, passo per passo. Le somme parziali della serie geometrica sono $S_N=\sum_{k=0}^N\gamma^k=\dfrac{1-\gamma^{N+1}}{1-\gamma}$ (moltiplicando $S_N$ per $\gamma$ e sottraendo si cancellano tutti i termini tranne il primo e l'ultimo). Per $0\le\gamma<1$ si ha $\gamma^{N+1}\to0$ (Limiti di successioniUna successione ha limite l se, da un certo indice in poi, i suoi termini stanno vicini a l quanto si vuole; definizioni con epsilon, limiti infiniti e unicità.Limiti di successioni →) e quindi $S_N\to\frac1{1-\gamma}$ (Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →). Per $\gamma\ge1$ le somme parziali non convergono e il ritorno può divergere: ecco perché si impone $\gamma<1$. Poiché ogni $R_{t+k+1}\le R_{max}$, $G_t\le R_{max}\cdot\frac1{1-\gamma}$ (confronto termine a termine). Con $\gamma=0{,}9$ il massimo ritorno è $10R_{max}$; con $\gamma=0{,}5$ è $2R_{max}$.

Orizzonte efficace. Dopo quanti passi il peso scende sotto l'$1\%$? Si risolve $\gamma^k<0{,}01$ prendendo il logaritmo (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →; poiché $\ln\gamma<0$ il verso della disuguaglianza si inverte): $k>\dfrac{\ln0{,}01}{\ln\gamma}$. Per $\gamma=0{,}9$ è $k>\frac{-4{,}605}{-0{,}1054}=43{,}7$, quindi circa $44$ passi; per $\gamma=0{,}5$ è $k>6{,}6$, cioè $7$ passi. Più $\gamma$ è vicino a $1$, più il futuro lontano conta (come nel grafico).

Esempio. Ricompense $R_{t+1}=1$, $R_{t+2}=0$, $R_{t+3}=2$ con $\gamma=0{,}9$: $G_t=1+0{,}9\cdot0+0{,}81\cdot2=2{,}62$. Lo stesso valore si ottiene all'indietro con la relazione ricorsiva $G_t=R_{t+1}+\gamma G_{t+1}$ (raccogliendo $\gamma$ dalla somma): all'ultimo passo $G=2$; prima $0+0{,}9\cdot2=1{,}8$; poi $1+0{,}9\cdot1{,}8=2{,}62$. Questa ricorsione è alla base degli algoritmi di RL.

Perché si parla di valore atteso e di argmax (esempio con due azioni). Il ritorno è casuale perché l'ambiente lo è (Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →): la politica ottima massimizza la media del ritorno, $E[G]$. Esempio minimo: due leve, A paga $1$ con probabilità $0{,}8$ (altrimenti $0$) e B paga $3$ con probabilità $0{,}3$ (altrimenti $0$). I valori attesi sono $E[R_A]=1\cdot0{,}8=0{,}8$ e $E[R_B]=3\cdot0{,}3=0{,}9$: la leva B ha il valore atteso più alto, anche se paga meno spesso; $\pi^*=\arg\max$ sceglie B. L'agente non conosce queste probabilità: le stima provando le leve e facendo la media dei premi osservati, ed è la legge dei grandi numeriSe X₁, X₂, ... sono i.i.d. con media μ, la media campionaria X̄ₙ = (X₁ + ... + Xₙ)/n converge a μ: in probabilità (legge debole, dimostrata con Chebyshev se la varianza è finita: P(|X̄ₙ − μ| > ε) ≤ σ²/(nε²)) e quasi certamente (legge forte). Metodo Monte Carlo: ∫ g = E[g(U)] si stima con la media di g(U₁), ..., g(Uₙ) per uniformi indipendenti.Legge dei grandi numeri e metodo Monte Carlo → a garantire che la media si avvicini al valore atteso (all'inizio la stima è rumorosa, per questo si alterna esplorazione e sfruttamento). Lo stato evolve in modo probabilistico, $P(S_{t+1}\mid S_t,A_t)$, una Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata → che dipende solo dallo stato e dall'azione correnti, non dalla storia precedente (proprietà di Markov).

Formula (obiettivo del RL). Si cerca la politica ottima $\pi^*=\arg\max_\pi\,E[G]$. A differenza del ML supervisionato, dove si minimizza una loss, qui si massimizza il ritorno.

2. Apprendimento di sequenze

Molti dati sono sequenze: riconoscimento vocale, musica, classificazione del sentimento di una recensione («There is nothing to like in this movie» $\to$ una stella), sequenze di DNA, traduzione automatica (francese $\to$ inglese), riconoscimento di attività nei video, Named Entity Recognition (NER: riconoscere nomi propri come «Harry Potter»).

Notazione. Per l'esempio $i$, $x^{(i)<t>}$ è l'elemento di ingresso al passo $t$ e $T_x^{(i)}$ la lunghezza dell'ingresso; $y^{(i)<t>}$ e $T_y^{(i)}$ per l'uscita. Per «The cat is on the table» nella NER si assegna $y^{<t>}=1$ a ogni parola che è un nome e $0$ altrimenti.

Requisiti di un modello di sequenze (con esempi):

• lunghezze variabili: «Do you like cats?» $\to$ «I love cats!» oppure una risposta di tre righe;
• dipendenze a lungo termine: «Lisboa is where I grew up, but now I live in Sweden. I speak fluent ___» (la risposta dipende da una parola molto indietro);
• ordine: «The food was good, not bad at all» e «The food was bad, not good at all» hanno le stesse parole;
• parametri condivisi nel tempo: una parola imparata va riconosciuta in qualunque posizione (come i pesi condivisi dei filtri convolutivi, Reti neurali convolutive (CNN)approfondimento: non nel programma di Telecomunicazioni. Una rete convolutiva (CNN) sostituisce gli strati densi con filtri piccoli che scorrono sull'immagine: ogni neurone vede solo una patch locale (campo recettivo) e i pesi del filtro sono condivisi in tutta l'immagine, quindi i parametri non dipendono dalla dimensione dell'immagine ($K^2C_{in}C_{out}+C_{out}$ per strato) e si conserva l'informazione spaziale. Dimensione dell'uscita: $\lfloor(W-K+2P)/S\rfloor+1$. Pooling (max 2x2, stride 2) sottocampiona e dà invarianza locale; i filtri 1x1 riducono i canali; struttura tipica CONV+ReLU, POOL, ..., FLATTEN, FC, SOFTMAX, addestrata con cross-entropy e backpropagation. Tre strati 3x3 hanno il campo recettivo di un 7x7 con meno parametri e più non linearità (VGG). Architetture: LeNet, AlexNet (ReLU, dropout, data augmentation), VGG, GoogLeNet (moduli Inception), ResNet (blocchi residui $H(x)=F(x)+x$), EfficientNet. Nel lab: CNN su Fashion-MNIST (241 546 parametri) e su CIFAR-10 (122 570).Reti neurali convolutive (CNN) →).

Una rete feed-forward non va bene: ingressi di dimensione fissa, nessuna condivisione dei parametri tra posizioni, nessuna memoria dell'ordine.

Reti ricorrenti (RNN)

Una rete ricorrente processa la sequenza un elemento alla volta mantenendo uno stato $h_t$ che riassume il passato:

$$h_t=f_W(h_{t-1},x_t),$$

con $f_W$ la stessa funzione (stessi pesi $W$) a ogni passo, $h_{t-1}$ lo stato precedente e $x_t$ l'ingresso. Lo stesso blocco gestisce quindi sequenze di qualsiasi lunghezza. Si addestra con la backpropagation «attraverso il tempo»; sulle sequenze lunghe i gradienti diventano evanescenti (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 →).

Quanti parametri e perché si condividono. Nella forma più semplice $h_t=\tanh(W_hh_{t-1}+W_xx_t+b)$ (Reti neurali - neuroni e funzioni di attivazioneUn neurone calcola $\hat y=g(w_0+w^\top x)$: somma pesata degli ingressi più bias, poi una funzione di attivazione $g$ non lineare (Perceptron a soglia, sigmoide, tanh, ReLU e varianti). Senza non linearità ogni rete è equivalente a un solo modello lineare. Una rete feed-forward impila strati di neuroni: $a^{(k)}=g(W^{(k)}a^{(k-1)}+b^{(k)})$; con uno strato nascosto è già un approssimatore universale, ma più strati rappresentano funzioni complesse con molti meno neuroni e imparano feature gerarchiche (bordi, parti, oggetti). Lo strato di uscita e la loss si scelgono dal compito: lineare+MSE (regressione), sigmoide+cross-entropy binaria, softmax+cross-entropy (multiclasse). Il numero di parametri di uno strato denso è $n_{in}n_{out}+n_{out}$. Nel lab (Keras, MNIST) una rete 784-512-10 ha 407 050 parametri e supera il 98% di accuratezza.Reti neurali - neuroni e funzioni di attivazione →). Con stato di dimensione $n=64$ e ingresso di dimensione $d=32$ i parametri sono $W_h$ ($64\cdot64=4096$), $W_x$ ($64\cdot32=2048$) e $b$ ($64$): $6208$ in tutto, qualunque sia la lunghezza $T$ della sequenza. Una rete completamente connessa su una sequenza di $T=100$ passi da $32$ valori ciascuno avrebbe $3200$ ingressi e già nel primo strato da $64$ neuroni $3200\cdot64=204\,800$ pesi, e solo per sequenze di lunghezza esattamente $100$.

Perché i gradienti evanescenti (passaggi). Per addestrare serve la derivata dello stato finale rispetto a uno stato lontano, $\dfrac{\partial h_T}{\partial h_t}$. Per la regola della catena (Regola della catena in più variabiliSe x(t) è una curva derivabile e f è differenziabile in x(t₀), allora (f∘x)'(t₀) = ∇f(x(t₀))·x'(t₀) = Σ ∂ᵢf(x(t₀)) xᵢ'(t₀): la variazione di f lungo il moto è il gradiente per la velocità. Serve per derivare composte come f(2t, t²), per ricavare il gradiente da informazioni lungo curve, per le derivate di f(g(s,t)) e per provare che il gradiente è ortogonale alle curve di livello.Regola della catena in più variabili →, Matrice jacobiana e derivata delle funzioni compostePer F: Rn → Rm, F = (f1, …, fm), la matrice jacobiana JF è la matrice m × n con (JF)ij = ∂fi/∂xj: la riga i è il gradiente di fi. Regola della catena: J(f∘g)(x) = Jf(g(x)) · Jg(x); casi frequenti d/dt f(γ(t)) = ∇f(γ(t))·γ'(t) e ∂f/∂x = f_u u_x + f_v v_x. Se det JF(x0) ≠ 0, F è invertibile vicino a x0 e J(F⁻¹) = (JF)⁻¹. Coordinate polari: det J = ρ.Matrice jacobiana e derivata delle funzioni composte →) è il prodotto delle matrici jacobiane di ogni passo: $\dfrac{\partial h_T}{\partial h_t}=\prod_{j=t+1}^{T}\dfrac{\partial h_j}{\partial h_{j-1}}$, e ogni fattore è $\operatorname{diag}(1-h_j^2)\,W_h$ (la derivata della tangente iperbolica è $1-\tanh^2\le1$: Funzioni iperbolicheSeno, coseno e tangente iperbolici costruiti con e^x ed e^(-x), la relazione cosh^2 - sinh^2 = 1 e le loro inverse con formula esplicita.Funzioni iperboliche →). Se in norma ogni fattore vale al più $\lambda<1$, il prodotto di $T-t$ fattori vale al più $\lambda^{T-t}$, una successione geometrica che tende a $0$ (Limiti di successioniUna successione ha limite l se, da un certo indice in poi, i suoi termini stanno vicini a l quanto si vuole; definizioni con epsilon, limiti infiniti e unicità.Limiti di successioni →): con $\lambda=0{,}5$ e $20$ passi $0{,}5^{20}\approx10^{-6}$, quindi l'influenza di un ingresso lontano sul gradiente è praticamente nulla e la rete non impara le dipendenze a lungo termine. Se invece $\lambda>1$ il prodotto cresce ($1{,}2^{20}\approx38$) e i gradienti esplodono.

Reti convolutive temporali (TCN)

Alternativa: convoluzioni 1D sul tempo. Due ingredienti:

• causalità: la previsione al passo $t$, $P(x_{t+1}\mid x_1,\dots,x_t)$, non può dipendere dai passi futuri;
• convoluzione dilatata: il filtro guarda campioni a distanza $d$ l'uno dall'altro, per ottenere un campo recettivo ampio con pochi strati.

Esempio. Filtro di dimensione $k=3$ e dilatazioni $d=1,2,4$ in tre strati: ogni strato $\ell$ allarga il campo recettivo di $(k-1)d_\ell$, per un totale $1+(3-1)(1+2+4)=15$ passi di passato con soli tre strati (senza dilatazione, con $k=3$ servirebbero sette strati per lo stesso campo, $1+2\cdot7=15$).

La formula del campo recettivo, passo per passo. Il campo recettivo è il numero di passi di ingresso da cui dipende un'uscita. Un filtro causale di dimensione $k$ e dilatazione $d$ guarda le posizioni $t,\,t-d,\,t-2d,\dots,t-(k-1)d$: copre $(k-1)d+1$ posizioni, cioè allarga di $(k-1)d$ il campo precedente. Partendo da un solo passo (campo $1$): dopo lo strato $1$ ($d=1$) il campo è $1+2\cdot1=3$; dopo lo strato $2$ ($d=2$) è $3+2\cdot2=7$; dopo lo strato $3$ ($d=4$) è $7+2\cdot4=15$. In generale $RF=1+(k-1)\sum_\ell d_\ell$. Con $d_\ell=2^{\ell-1}$ si ha $\sum_{\ell=1}^Ld_\ell=2^L-1$ (somma di una serie geometrica finita: SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →), quindi $RF=1+(k-1)(2^L-1)$ cresce in modo esponenziale col numero $L$ di strati, mentre senza dilatazione ($d_\ell=1$) è $1+(k-1)L$, lineare. Con $k=3$ e $L=8$ strati: $511$ passi contro $17$.

3. Conclusione del corso

Molte tecnologie quotidiane si basano sul ML; restano ancora molte cose da costruire, in particolare IA «su misura» che sfrutta dati disponibili a una sola azienda (finanziari, vendite, clienti, marketing, operazioni, fornitori, risorse umane).