Apprendimento automatico nell'IA - supervisionato, SVM e valutazione

Il corso di IA dedica due lezioni e un laboratorio al machine learning (ML): il quadro delle idee e la pipeline pratica in scikit-learn. Le derivazioni, i metodi in dettaglio e gli esercizi sono nella materia Machine Learning: qui si dice cosa serve per l'esame di IA e si rimanda lì. Panoramica generale: Introduzione al machine learningIl machine learning (ML) è la parte dell'intelligenza artificiale che costruisce soluzioni a partire dai dati e non da regole scritte a mano: un modello matematico con parametri liberi viene addestrato su esempi storici e poi usato su dati nuovi. Si distingue tra apprendimento supervisionato (dati $(x,y)$, si impara la mappa $x\mapsto y$: regressione se $y$ è un numero, classificazione se è una categoria), non supervisionato (solo $x$, si cercano struttura e gruppi) e per rinforzo (stato, azione, ricompensa). Un progetto ML non è «plug and play»: segue le fasi problema, raccolta, pulizia, modellazione, rilascio, e va valutato su dati mai visti; senza dati non c'è modello, alcuni fenomeni sono imprevedibili, la generalizzazione fuori dal dominio di addestramento non è garantita.Introduzione al machine learning →. Gli esercizi di questa materia sono Esercizio - Ricerca del miglior C per una SVM lineare sul dataset digits (laboratorio 10), Esercizio - SVM con tre kernel sul dataset iris (laboratorio 10) e Esercizio - Albero di decisione sul ristorante - guadagno d'informazione e potatura (slide del corso).

1. Forme di apprendimento

Un agente impara quando migliora le prestazioni dopo aver osservato dati. A seconda del feedback che accompagna gli ingressi:

• supervisionato: l'agente vede coppie ingresso-uscita e impara la funzione che le lega;
• non supervisionato: impara pattern negli ingressi senza feedback esplicito (per esempio il clustering, Clustering e k-meansIl clustering raggruppa osservazioni simili senza etichette, come preprocessing (un modello per ogni cluster) o come obiettivo (segmentazione clienti, organizzazione di documenti). K-means: si sceglie $K$, si inizializzano $K$ centroidi, si alterna assegnazione di ogni punto al centroide più vicino e aggiornamento di ogni centroide alla media dei suoi punti, fino a convergenza; minimizza $\mathrm{MSE}{\text{within}}=\frac1N\sum_k\sum{x_i\in C_k}|x_i-\mu_k|^2$ ma solo fino a un minimo locale, quindi dipende dall'inizializzazione. Il numero di cluster si sceglie col metodo del gomito (la dispersione cala sempre, si cerca dove rallenta) o con la gap statistic $\mathrm{Gap}(K)=E[\log W_K^{ref}]-\log W_K$ (si prende il più piccolo $K$ con $\mathrm{Gap}(K)\ge\mathrm{Gap}(K+1)-s_{K+1}$). Il clustering gerarchico agglomerativo parte da un cluster per punto e fonde i due più vicini (linkage single, complete, average, Ward) costruendo un dendrogramma; quello divisivo parte da un solo cluster. Programma di Telecomunicazioni: clustering.Clustering e k-means →);
• per rinforzo: impara da una serie di ricompense e punizioni (Cenni a reinforcement learning e reti per sequenzeapprofondimento: non nel programma di Telecomunicazioni, solo cenni (ultima lezione del corso). Reinforcement learning: un agente in uno stato $S_t$ sceglie azioni, l'ambiente restituisce ricompense; l'obiettivo non è minimizzare una loss ma massimizzare il ritorno $G_t=\sum_{k\ge0}\gamma^kR_{t+k+1}$ (fattore di sconto $\gamma\in[0,1)$) trovando la politica ottima $\pi^*=\arg\max G$. Apprendimento di sequenze: servono lunghezze variabili, dipendenze a lungo termine, ordine, parametri condivisi nel tempo; una rete ricorrente aggiorna uno stato $h_t=f_W(h_{t-1},x_t)$; le reti convolutive temporali (TCN) usano convoluzioni causali e dilatate con campo recettivo $1+(k-1)\sum d_\ell$. Chiude con i modelli generativi (VAE, GAN) già visti in Autoencoder.Cenni a reinforcement learning e reti per sequenze →, e il Q-learning del laboratorio 9 in Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iterationUn MDP (processo decisionale di Markov) modella un problema decisionale sequenziale in ambiente stocastico e completamente osservabile con stati S, azioni A(s), modello di transizione P(s'|s,a) e ricompensa R(s,a,s'). La soluzione è una politica pi(s). L'utilità U(s) è il ritorno scontato atteso e soddisfa l'equazione di Bellman U(s)=max_a sum_s' P(s'|s,a)[R(s,a,s')+gamma U(s')]; la quantità tra parentesi quadre sommata su s' è la funzione azione-utilità Q(s,a). Value iteration parte da U=0, applica Bellman a tutti gli stati insieme e si ferma quando delta <= eps(1-gamma)/gamma; la politica è argmax_a Q(s,a). Policy iteration alterna valutazione (sistema lineare, senza max) e miglioramento greedy, e termina quando la politica non cambia. Nei POMDP lo stato è nascosto: si lavora sullo stato di credenza b aggiornato come nel filtraggio, b'(s')=alpha P(e|s') sum_s P(s'|s,a)b(s).Processi decisionali di Markov - utilità, equazione di Bellman, value e policy iteration →).

Due problemi tipici dell'apprendimento supervisionato: classificazione (l'uscita è uno tra un insieme finito di valori, per esempio {nuvoloso, soleggiato, piovoso}) e regressione (l'uscita è un numero, per esempio la pressione). Il corso si concentra sul supervisionato.

2. Apprendimento supervisionato, bias e varianza

Definizione. Dato un training set di $N$ esempi $(x_1,y_1),\dots,(x_N,y_N)$ generati da una funzione sconosciuta $y=f(x)$, si cerca un'ipotesi $h$ (un modello dei dati) che approssimi $f$. Gli $y_i$ si chiamano ground truth. Un'ipotesi generalizza bene se predice con accuratezza le uscite di esempi non ancora visti: la sua qualità si misura sul test set, non sul training set.

• Bias: tendenza di un'ipotesi a deviare dal valore atteso quando si media su diversi training set. Una retta ha bias alto sui dati non lineari: underfitting (non trova il pattern).
• Varianza: quanto cambia l'ipotesi al variare del training set. Due polinomi di grado 12 addestrati su campioni diversi della stessa $f$ sono molto diversi: varianza alta, overfitting (si presta troppa attenzione al training set particolare e si va male sui dati nuovi).

Il compromesso è tra ipotesi complesse a basso bias, che si adattano bene ai dati, e ipotesi semplici a bassa varianza, che generalizzano meglio (rasoio di Ockham). Dettagli e formule in Overfitting, ridge regression e cross-validationUna buona prestazione sul training non basta: serve stimare quella su dati nuovi. La cross-validation (K-fold: $k$ parti, ciascuna a turno come test, errore medio; Monte Carlo: $k$ divisioni casuali con quota di test $q$; leave-one-out se $k=n$) evita di dipendere da una sola divisione casuale. L'errore atteso si scompone in $\text{bias}^2+\text{varianza}+\sigma^2$: i modelli semplici fanno underfitting (bias alto), quelli complessi overfitting (varianza alta). La regolarizzazione aggiunge alla perdita una penalità: la ridge regression minimizza $|y-X\beta|^2+\lambda\sum_{j\ge1}\beta_j^2$ e ha soluzione $\beta=(X^TX+\lambda\tilde I)^{-1}X^Ty$ (l'intercetta non si penalizza, le feature si standardizzano): riduce i coefficienti, rende l'inversa stabile con feature collineari, e $\lambda$ è un iperparametro scelto con la validazione (cross-validation annidata per non contaminare il test).Overfitting, ridge regression e cross-validation →.

3. Selezione del modello, ottimizzazione e valutazione

Trovare una buona ipotesi ha tre sotto-compiti:

1. selezione del modello: scegliere lo spazio delle ipotesi (lineare o polinomiale, quanti nodi, quanti pesi: gli iperparametri);
2. ottimizzazione (addestramento): trovare la migliore ipotesi dentro quello spazio (i parametri);
3. valutazione: per esempio il tasso d'errore, cioè la frazione di volte in cui $h(x)\neq y$.

Servono tre insiemi: un training set per creare i modelli candidati, un validation set per valutare e scegliere il migliore, un test set per la valutazione finale non distorta. Se i dati non bastano per tre insiemi si usa la cross-validation a $k$ fold: si divide il training in $k$ parti uguali; in $k$ giri una parte fa da validation e le altre da training; si riporta la media dei $k$ punteggi. Valori comuni: $k=5$ o $10$; con $k$ uguale alla dimensione del dataset è la leave-one-out. Serve comunque un test set separato.

Esempio. Con 1 797 immagini e $k=5$, ogni giro usa circa 1 437 immagini per l'addestramento e 360 per la validazione; i cinque punteggi, per l'SVM del laboratorio, sono $0{,}975;\ 0{,}950;\ 0{,}983;\ 0{,}992;\ 0{,}961$, con media $0{,}972$ e deviazione standard $0{,}015$.

Si sceglie il valore dell'iperparametro con il minimo errore di validazione (per esempio la dimensione ottima di un albero), e solo poi si ricalcola il modello su tutti i dati di addestramento e si misura sul test set.

4. Alberi di decisione

Definizione. Un albero di decisione mappa un vettore di valori di attributi in un'uscita con una sequenza di test, dalla radice a una foglia: ogni nodo interno testa un attributo, i rami sono i suoi valori, le foglie danno la decisione. Dettagli, Gini e CART in Alberi di decisioneUn albero di decisione partiziona i dati con una sequenza di regole su una sola variabile alla volta (nodi interni = regole, foglie = predizioni: classe più frequente, oppure media del target in regressione). Si costruisce in modo ricorsivo scegliendo a ogni nodo la divisione che rende i figli più «puri»: con l'entropia $H=-\sum p_i\log_2p_i$ e il guadagno d'informazione $IG=H(S)-\sum\frac{|S_v|}{|S|}H(S_v)$ (ID3), oppure con l'indice di Gini $1-\sum p_i^2$ e soglie $x\le t$ su variabili numeriche (CART); in regressione con MSE o riduzione di varianza. Un albero pienamente sviluppato fa overfitting (varianza alta): si limita con la profondità massima (pre-potatura) o con la potatura a costo-complessità $R_\alpha(T)=R(T)+\alpha|T|$ (post-potatura). Pro: interpretabile, niente normalizzazione, predizione immediata; contro: varianza alta, da cui le foreste. Programma di Telecomunicazioni: Decision Trees e Random Forests.Alberi di decisione →.

Esempio del corso: il ristorante. Il problema è decidere se aspettare un tavolo (WillWait, booleano) a partire da 10 attributi (Alternate, Bar, Fri, Hungry, Patrons con valori None/Some/Full, Price, Rain, Reservation, Type, Estimated waiting); il dataset ha 12 esempi precedenti, 6 positivi e 6 negativi.

Algoritmo. Si sceglie ricorsivamente l'attributo più importante come radice; se gli esempi in una foglia hanno tutti lo stesso valore, ci si ferma; altrimenti si prende il valore più frequente (plurality value): tra gli esempi correnti se non ci sono più attributi, tra quelli del genitore se non ci sono più esempi.

Importanza = guadagno d'informazione. L'entropia di una variabile booleana vera con probabilità $q$ è $$B(q)=-\big(q\log_2q+(1-q)\log_2(1-q)\big)$$ (per una moneta equa $B(\tfrac12)=1$ bit). Con $p$ esempi positivi e $n$ negativi, $q=p/(p+n)$. Un test su un attributo $A$ con $d$ valori divide gli esempi in $d$ sottoinsiemi con $p_k$ positivi e $n_k$ negativi ($N_k=p_k+n_k$); l'entropia attesa dopo il test e il guadagno sono $$\text{Remainder}(A)=\sum_{k=1}^{d}\frac{N_k}{N}\,B\!\Big(\frac{p_k}{N_k}\Big),\qquad \text{Gain}(A)=B\!\Big(\frac{p}{p+n}\Big)-\text{Remainder}(A).$$ Si sceglie l'attributo con guadagno massimo.

Calcolo per Patrons (None: 0 positivi e 2 negativi; Some: 4 e 0; Full: 2 e 4):

• $B(\tfrac6{12})=1$;
• $B(0)=0$, $B(1)=0$, $B(\tfrac26)=-\big(\tfrac13\log_2\tfrac13+\tfrac23\log_2\tfrac23\big)=0{,}5283+0{,}3900=0{,}9183$;
• $\text{Remainder}=\tfrac2{12}\cdot0+\tfrac4{12}\cdot0+\tfrac6{12}\cdot0{,}9183=0{,}4591$;
• $\text{Gain}(\text{Patrons})=1-0{,}4591=\mathbf{0{,}541}$ bit.

Per Type (French 1 e 1, Italian 1 e 1, Thai 2 e 2, Burger 2 e 2) ogni sottoinsieme ha entropia 1: $\text{Gain}(\text{Type})=0$. Patrons è molto migliore. L'esercizio Esercizio - Albero di decisione sul ristorante - guadagno d'informazione e potatura (slide del corso) calcola tutti i dieci guadagni.

Overfitting e potatura. Più test ci sono, più sale il rischio di overfitting. La potatura (pruning) elimina i nodi poco rilevanti, quelli con poco guadagno. Quanto poco lo decide un test di significatività: ipotesi nulla "l'attributo è irrilevante" (il guadagno tende a 0 con infiniti esempi). Si misura la deviazione totale dei campioni rispetto a quella attesa sotto l'ipotesi nulla: $$\Delta=\sum_{k=1}^{d}\left[\frac{(p_k-\hat p_k)^2}{\hat p_k}+\frac{(n_k-\hat n_k)^2}{\hat n_k}\right],\qquad \hat p_k=p\,\frac{N_k}{N},\quad \hat n_k=n\,\frac{N_k}{N}.$$ Se $\Delta>\Delta^*$, dove $\Delta^*$ si legge nella tavola del $\chi^2$ con $d-1$ gradi di libertà per la probabilità di ipotesi nulla desiderata (tipicamente $5\%$), l'ipotesi nulla è rifiutata e l'attributo è utile (si tiene); altrimenti si pota.

Esempio (Hungry nel ramo Patrons = Full, con 2 positivi e 4 negativi). Hungry = No: 0 positivi e 2 negativi; Hungry = Yes: 2 positivi e 2 negativi. Attesi: $\hat p_{No}=2\cdot\tfrac26=0{,}667$, $\hat p_{Yes}=2\cdot\tfrac46=1{,}333$, $\hat n_{No}=4\cdot\tfrac26=1{,}333$, $\hat n_{Yes}=4\cdot\tfrac46=2{,}667$. $$\Delta=\tfrac{(0-0{,}667)^2}{0{,}667}+\tfrac{(2-1{,}333)^2}{1{,}333}+\tfrac{(2-1{,}333)^2}{1{,}333}+\tfrac{(2-2{,}667)^2}{2{,}667}=0{,}667+0{,}333+0{,}333+0{,}167=1{,}5.$$ Con $d=2$ c'è 1 grado di libertà e $\Delta^*=3{,}841$: $1{,}5<3{,}841$, quindi Hungry non è significativo e si pota.

Bagging e random forest. Il bagging estrae $K$ training set di $N$ esempi con ripetizione, addestra $K$ alberi e aggrega: voto di maggioranza (classificazione) o media (regressione). Riduce la varianza. Il problema è che gli alberi sono molto correlati (un attributo con guadagno altissimo è la radice quasi ovunque): la random forest a ogni nodo sceglie il miglior attributo solo tra un sottoinsieme casuale, rendendo gli alberi più diversi; non serve potare, perché l'insieme dei $K$ alberi riduce già l'overfitting, e si può costruire in parallelo. Dettagli in Metodi ensemble - bagging, random forest e boostingUn albero da solo ha varianza alta; un ensemble combina molti modelli deboli. Bagging: ogni albero è addestrato su un campione bootstrap (n estrazioni con rimpiazzo, circa il 63% di campioni distinti) e si vota o si fa la media: riduce la varianza, perché la media di $T$ stimatori con varianza $\sigma^2$ e correlazione $\rho$ ha varianza $\rho\sigma^2+(1-\rho)\sigma^2/T$. Random forest = bagging + a ogni split solo $\sqrt p$ feature casuali (alberi meno correlati); l'importanza di una feature è la somma delle riduzioni di Gini pesate sui nodi in cui è usata. Boosting: alberi in sequenza, ciascuno corregge gli errori dei precedenti, e si riduce il bias. Gradient boosting: $F\leftarrow F+\eta h$ con $h$ albero sui residui (gradiente negativo della perdita), $\eta$ piccolo; AdaBoost: stump e pesi sui campioni sbagliati; XGBoost: similarity score $\frac{(\sum r)^2}{N+\lambda}$, gain, potatura con $\gamma$, output $\frac{\sum r}{N+\lambda}$. Programma di Telecomunicazioni: Random Forests; boosting come approfondimento.Metodi ensemble - bagging, random forest e boosting →.

5. Perdita, regressione lineare e discesa del gradiente

In ML di solito si minimizza una perdita invece di massimizzare un'utilità: $L(y,\hat y)$ è l'utilità persa predicendo $\hat y=h(x)$ al posto di $y=f(x)$. Due perdite comuni: valore assoluto $L_1=|y-\hat y|$ e errore quadratico $L_2=(y-\hat y)^2$.

Regressione lineare univariata. Ipotesi $h_w(x)=w_1x+w_0$; si cercano i pesi che minimizzano la perdita quadratica sui $N$ esempi, $\sum_j\big(y_j-(w_1x_j+w_0)\big)^2$. È una funzione convessa dei pesi con un minimo globale, che si trova azzerando le derivate parziali (soluzione analitica). Teoria completa in Regressione lineareNell'apprendimento supervisionato si impara una funzione $F(x)$ dagli esempi $(x,y)$: regressione se $y$ è continua, classificazione se è categorica. Il modello lineare è $F_\beta(x)=\beta_0+\beta_1x_1+\dots+\beta_px_p=X\beta$ (con una colonna di uni per $\beta_0$) e i parametri si scelgono minimizzando l'errore quadratico medio $\mathrm{MSE}=\frac1n\sum_i(y_i-F_\beta(x_i))^2$, funzione convessa dei parametri. Annullando il gradiente di $J(\beta)=|y-X\beta|^2$ si ottengono le equazioni normali $X^TX\beta=X^Ty$ e la soluzione dei minimi quadrati ordinari $\beta=(X^TX)^{-1}X^Ty$. Il coefficiente di determinazione $R^2=1-SS_{res}/SS_{tot}$ misura la qualità del fit (0 = come la media, negativo = peggio della media). Un modello va valutato su un test set mai usato per addestrare: l'errore sul training è ottimistico e un polinomio di grado alto lo azzera senza generalizzare.Regressione lineare →.

Discesa del gradiente. Quando non c'è la soluzione in forma chiusa, si cerca il minimo modificando i parametri passo dopo passo (come l'hill climbing ma minimizzando): $$w_i\leftarrow w_i-\alpha\,\frac{\partial L}{\partial w_i},$$ con $\alpha$ passo (learning rate). Su $N$ esempi, batch: $w_i\leftarrow w_i-\alpha\sum_j\partial L_j/\partial w_i$; un passaggio su tutti i dati è un'epoca. Con perdita convessa converge al minimo globale se $\alpha$ non è troppo grande (altrimenti il passo supera il minimo). SGD: un solo esempio $j$ scelto a caso a ogni passo (più veloce); minibatch SGD: $m$ esempi su $N$. Dettagli: 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 →.

Esempio a mano. Dati $(1,2)$, $(2,3)$, $(3,5)$; si parte da $w_0=w_1=0$, con $L=\sum_j(y_j-h_j)^2$, per cui $\partial L/\partial w_0=-2\sum_j(y_j-h_j)$ e $\partial L/\partial w_1=-2\sum_jx_j(y_j-h_j)$. Il minimo esatto è $w_1=1{,}5$, $w_0=\tfrac13$ (con $\bar x=2$, $\bar y=\tfrac{10}3$, pendenza $\tfrac{(-1)(-4/3)+0+1\cdot(5/3)}{2}=1{,}5$, $w_0=\tfrac{10}3-1{,}5\cdot2$).

• Passo 0: errori $y-h=(2,3,5)$, $L=4+9+25=38$; $\partial L/\partial w_0=-2\cdot10=-20$, $\partial L/\partial w_1=-2(2+6+15)=-46$. Con $\alpha=0{,}02$: $w_0=0+0{,}4=0{,}4$, $w_1=0+0{,}92=0{,}92$.
• Passo 1: $h=(1{,}32;\ 2{,}24;\ 3{,}16)$, errori $(0{,}68;\ 0{,}76;\ 1{,}84)$, $L=4{,}4256$; gradienti $-6{,}56$ e $-15{,}44$; $w_0=0{,}5312$, $w_1=1{,}2288$.
• Passo 2: con $w=(0{,}5312;\ 1{,}2288)$ si ha $L=0{,}6699$ e i nuovi pesi sono $w_0=0{,}5725$, $w_1=1{,}3332$. Poi $L=0{,}2491$ e, dopo un altro passo, $w=(0{,}5839;\ 1{,}3692)$ con $L=0{,}2013$ (il minimo esatto ha $L=\tfrac16=0{,}1667$).

La perdita scende a ogni passo e $w_1$ si avvicina a $1{,}5$. Con $\alpha=0{,}05$ i pesi oscillano attorno al minimo prima di assestarsi, e con $\alpha=0{,}2$ la perdita cresce a ogni passo ($38\to1\,209\to38\,679$): il passo è troppo grande.

Regressione multivariata. $x_j$ è un vettore di $n$ elementi e $h_w(x_j)=w\cdot x_j$; la perdita ha un minimo unico, raggiunto dalla discesa del gradiente.

Dalla regressione alla classificazione. Una funzione lineare serve anche per classificare: $h_w(x)=\text{Threshold}(w\cdot x)$, con soglia $1$ se $z\ge0$ e $0$ altrimenti. Il confine di decisione è una retta (in dimensioni maggiori un piano o una superficie) che separa le due classi; con dati linearmente separabili è un separatore lineare. Vedi Halfspace e PerceptronUn halfspace (semispazio) classifica con un iperpiano: $h(x)=\operatorname{sign}(w^Tx+b)$, con $w$ normale al piano e $|w^Tx+b|/|w|$ distanza dal piano; aggiungendo una componente costante $1$ a $x$ si scrive $\operatorname{sign}(\tilde w^T\tilde x)$. Il Perceptron (Rosenblatt, 1958) è il neurone con attivazione a gradino e impara con una regola semplice: per ogni errore $y_i,w^Tx_i\le0$ si aggiorna $w\leftarrow w+y_ix_i$. Teorema di convergenza (Novikoff): se i dati sono linearmente separabili con margine $\gamma$ ($y_iw^{T}x_i\ge\gamma$, $|w^|=1$) e $|x_i|\le R$, il Perceptron fa al più $(R/\gamma)^2$ errori e si ferma. Non risolve problemi non separabili (XOR), non ha un criterio di margine ottimale (le SVM sì) e il suo analogo morbido è la regressione logistica. Programma di Telecomunicazioni: halfspace model, Perceptron.Halfspace e Perceptron → e Regressione logistica e softmaxLa regressione lineare non è adatta alla classificazione (valori fuori da [0,1], retta tirata dai punti lontani). La regressione logistica passa il predittore lineare dalla sigmoide $\sigma(z)=1/(1+e^{-z})$ e interpreta $\hat y=\sigma(x^T\beta)$ come $P(y=1\mid x)$: si predice la classe 1 se $\hat y\ge0{,}5$, cioè $x^T\beta\ge0$ (bordo lineare). L'errore quadratico dà una funzione non convessa; si usa la log-verosimiglianza negativa $-\sum[y\log\hat y+(1-y)\log(1-\hat y)]$, convessa, con gradiente $X^T(\hat y-y)$ e nessuna formula chiusa (discesa del gradiente). Per più classi: one-vs-one ($C(C-1)/2$ classificatori, voto), one-vs-all ($C$ classificatori, massima probabilità), o la softmax $p_c=e^{z_c}/\sum_ke^{z_k}$ con cross-entropia. Si può regolarizzare (ridge, LASSO, Elastic Net) e la cross-validation si fa stratificata. Approfondimento: non nel programma di Telecomunicazioni.Regressione logistica e softmax →.

6. Support vector machines

Le SVM hanno tre proprietà: costruiscono un separatore a margine massimo (la distanza massima dagli esempi più vicini); creano un iperpiano separatore lineare; sono non parametriche (l'iperpiano è definito da un insieme di esempi). Gli esempi più vicini al separatore sono i vettori di supporto.

La soluzione ottima si trova risolvendo il problema duale, convesso e con un unico massimo globale: i pesi $\alpha_j$ sono nulli per tutti gli esempi tranne i vettori di supporto, e la classificazione è con soglia 0. Derivazione completa in Support vector machines e metodi kernelUna SVM cerca l'iperpiano $w\cdot x+b=0$ che separa due classi con il margine più largo possibile: normalizzando $y_i(w\cdot x_i+b)\ge1$ il margine totale vale $2/|w|$, quindi si risolve $\min\frac12|w|^2$ (problema convesso, nessun minimo locale). Con classi sovrapposte si ammettono errori con le variabili di scarto $\xi_i$ e il parametro $C$ (soft margin, equivalente alla hinge loss più una penalità su $|w|^2$); $C$ piccolo = margine largo e più bias, $C$ grande = margine stretto e più varianza, si sceglie per cross-validation. La soluzione dipende solo dai vettori di supporto ($w=\sum\alpha_iy_ix_i$) e solo tramite prodotti scalari, per questo si può sostituire $x_i\cdot x_j$ con un kernel $K(x_i,x_j)=\langle\phi(x_i),\phi(x_j)\rangle$ (polinomiale, RBF) senza calcolare $\phi$: così si ottengono bordi non lineari. La SVR usa lo stesso schema con un tubo di tolleranza $\varepsilon$. Nell'esame le SVM sono solo nella parte teorica.Support vector machines e metodi kernel →.

Trucco del kernel. Nel duale compare solo il prodotto scalare $x_j\cdot x_k$: lo si sostituisce con una funzione kernel $K(x_j,x_k)=F(x_j)\cdot F(x_k)$ per una qualche trasformazione $F$ in uno spazio di dimensione maggiore, senza calcolare $F$. Un confine circolare in due dimensioni diventa un piano in tre dimensioni. Kernel comuni: polinomiale $(c+x_j\cdot x_k)^d$ e gaussiano $\exp(-\gamma\|x_j-x_k\|^2)$.

Esempio numerico. Con $x_j=(1,2)$, $x_k=(3,1)$: $x_j\cdot x_k=5$. Il kernel polinomiale con $c=0$, $d=2$ dà $5^2=25$, e coincide con il prodotto scalare delle immagini $F(x)=(x_1^2,\sqrt2\,x_1x_2,x_2^2)$: $F(x_j)=(1,\ 2\sqrt2,\ 4)$, $F(x_k)=(9,\ 3\sqrt2,\ 1)$, prodotto $9+12+4=25$. Con $c=1$, $d=2$: $(1+5)^2=36$. Il kernel gaussiano con $\gamma=0{,}5$: $\|x_j-x_k\|^2=4+1=5$, $\exp(-2{,}5)=0{,}0821$. Per questo il kernel è molto più economico della mappa esplicita (nel gaussiano lo spazio ha dimensione infinita). Esercizio: Esercizio - Kernel e confronto tra SVM.

7. Pipeline in scikit-learn (laboratorio 10)

Il dataset digits ha 1 797 immagini $8\times8$ in scala di grigi di cifre da 0 a 9. Prima di passarle a un classificatore: appiattire ogni immagine da $(8,8)$ a $(64,)$ e dividere in training e test.

from sklearn import datasets, svm, metrics
from sklearn.model_selection import train_test_split, cross_val_score

digits = datasets.load_digits()
n = len(digits.images)
data = digits.images.reshape((n, -1))                      # (1797, 64)
X_train, X_test, y_train, y_test = train_test_split(
    data, digits.target, test_size=0.25, shuffle=False)    # 75% training, 25% test

clf = svm.SVC(gamma=0.001)        # kernel rbf, C=1 di default
clf.fit(X_train, y_train)         # addestramento
predicted = clf.predict(X_test)   # predizione sul test set
print(metrics.classification_report(y_test, predicted))
print(metrics.confusion_matrix(y_test, predicted))
print(cross_val_score(svm.SVC(gamma=0.001), data, digits.target, cv=5))   # 5-fold

Risultato verificato: accuratezza $0{,}967$ sui 450 esempi del test; 5-fold: $[0{,}975,\ 0{,}950,\ 0{,}983,\ 0{,}992,\ 0{,}961]$.

Gli iperparametri di SVC: $C$ controlla il compromesso tra massimizzare il margine e minimizzare gli errori sul training (grande: pochi errori ma margine stretto); kernel (linear, poly, rbf, ...) permette di trattare dati non linearmente separabili; $\gamma$ determina l'influenza di un singolo esempio sul confine. LinearSVC usa il kernel lineare ed è più veloce.

Metriche (classification_report), con TP, TN, FP, FN: $$\text{accuracy}=\tfrac{TP+TN}{TP+TN+FP+FN},\quad\text{precision}=\tfrac{TP}{TP+FP},\quad\text{recall}=\tfrac{TP}{TP+FN},\quad F_1=\tfrac{2\cdot\text{precision}\cdot\text{recall}}{\text{precision}+\text{recall}}.$$ La matrice di confusione confronta etichette vere (righe) e predette (colonne). Esempio: per la SVM lineare del laboratorio (cifra 3) $TP=36$ su 47 esempi della classe, $FN=11$, $FP=2$: $\text{precision}=\tfrac{36}{38}=0{,}947$, $\text{recall}=\tfrac{36}{47}=0{,}766$, $F_1=\tfrac{2\cdot36}{2\cdot36+2+11}=0{,}847$ (nel report del corso: $0{,}95$, $0{,}77$, $0{,}85$). Dettagli e ROC in Metriche di classificazioneIn classificazione binaria ogni previsione è vero positivo (TP), vero negativo (TN), falso positivo (FP, errore di tipo I) o falso negativo (FN, errore di tipo II). Da queste quattro quantità: accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, specificità $=\frac{TN}{TN+FP}$, precision $=\frac{TP}{TP+FP}$, recall $=\frac{TP}{TP+FN}$, e la loro media armonica $F_1=\frac{2PR}{P+R}$. Con dati sbilanciati l'accuracy inganna (un modello che predice sempre la classe maggioritaria ha 99%): si usano precision, recall, F1, ROC-AUC, la cross-validation stratificata e il riequilibrio con undersampling o oversampling (non SMOTE). Cambiando la soglia sulla probabilità si ottiene la curva ROC (TPR contro FPR) e l'area AUC. Approfondimento: non nel programma di Telecomunicazioni.Metriche di classificazione →; esercizio Esercizio - Metriche di classificazione da una matrice di confusione.

Cross-validation per scegliere gli iperparametri (laboratorio): scegliere $C$ e kernel sul test set li "fa trapelare" nel modello (leakage). Si tiene fuori un test set e si usa la CV sul resto. Applicazione: Esercizio - Ricerca del miglior C per una SVM lineare sul dataset digits (laboratorio 10).

Errori tipici

• Valutare il modello sul training set o scegliere gli iperparametri guardando il test set.
• Dimenticare di appiattire le immagini prima di una SVM o di fare lo shuffle: con shuffle=False su iris il test set contiene una sola classe.
• Dimenticare di pesare per $N_k/N$ nell'entropia attesa.
• Prendere $\Delta^*$ con i gradi di libertà sbagliati: sono $d-1$.
• Scegliere un passo $\alpha$ troppo grande nella discesa del gradiente: la perdita cresce.
• Confondere precision (tra i predetti positivi) e recall (tra i veri positivi).

Domande d'esame

1. Un attributo divide 12 esempi (6 positivi e 6 negativi) in tre insiemi: (0 pos, 2 neg), (4 pos, 0 neg), (2 pos, 4 neg). Quanto vale il guadagno d'informazione? $B(\tfrac12)=1$; $\text{Remainder}=\tfrac6{12}B(\tfrac13)=0{,}5\cdot0{,}9183=0{,}4591$; $\text{Gain}=1-0{,}4591=0{,}541$ bit.
2. Perché non si valuta un modello sul training set? Perché un modello che memorizza il training ha errore nullo ma generalizza male (overfitting). La qualità si misura su dati non visti (test set); gli iperparametri si scelgono su un validation set o con la cross-validation.
3. Cosa sono i vettori di supporto e cosa fa il kernel? Sono gli esempi più vicini al separatore a margine massimo, gli unici con peso $\alpha_j\neq0$. Il kernel $K(x_j,x_k)=F(x_j)\cdot F(x_k)$ sostituisce il prodotto scalare e permette confini non lineari senza calcolare $F$.
4. Un test $\chi^2$ dà $\Delta=1{,}5$ con $d=2$ valori dell'attributo e soglia al $5\%$. Si tiene o si pota? $\Delta^*=3{,}841$ (1 grado di libertà): $1{,}5<3{,}841$, l'attributo non è significativo, si pota.