Support vector machines e metodi kernel

Questa nota riprende il problema della classificazione binaria già visto con il 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 con la 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 →: si vuole un classificatore lineare, cioè un iperpiano che divide lo spazio in due semispazi, uno per classe. La domanda è: tra gli infiniti iperpiani che separano i dati di addestramento, quale scegliere? La risposta delle SVM è «quello più lontano da tutti i punti», e da questa idea geometrica escono il modello, il problema di ottimizzazione, la tolleranza agli errori e, con il kernel trick, anche i bordi curvi.

Le etichette sono $y_i\in\{-1,+1\}$ (non $0/1$): serve per scrivere in una sola disuguaglianza la condizione «il punto sta dal lato giusto».

1. Perché il margine

Con due classi e un bordo di decisione (decision boundaryla soglia che separa le due classi), ogni nuova osservazione viene classificata dal lato in cui cade. Se i dati sono separabili esistono molti bordi con zero errori di addestramento: sono tutti uguali per il training set, ma non per i dati futuri. Il bordo che passa a metà tra le due classi è quello che «sbaglia meno» quando arriva un punto nuovo, perché lascia lo stesso spazio di errore da entrambe le parti.

Definizione (margine). Il margine è la distanza tra il bordo di decisione e le osservazioni di ciascuna classe più vicine ad esso. Il classificatore a margine massimo (maximal margin classifier) è il classificatore lineare che sceglie l'iperpiano per cui questa distanza è la più grande possibile.

I punti che toccano il margine si chiamano vettori di supporto (support vectors): sono gli unici che «sostengono» la soluzione. Se si sposta un punto lontano dal margine, o lo si toglie, l'iperpiano non cambia; se si sposta un vettore di supporto, cambia.

2. Geometria: iperpiano, distanza, margine

Servono il prodotto scalare $w\cdot x=\sum_jw_jx_j$ e la norma $\|w\|=\sqrt{w\cdot w}$ (Prodotto scalare, norma e angoliIl prodotto scalare aggiunge a uno spazio vettoriale lunghezze e angoli: norma, disuguaglianza di Cauchy-Schwarz, angolo tra vettori in R^n, ortogonalità, proiezione su una retta, aree e volumi con il determinante della matrice dei prodotti scalari.Prodotto scalare, norma e angoli →, Norma, distanza e prodotto scalare in RnIn Rⁿ la norma è |x| = √(x₁² + … + xₙ²) e la distanza tra x e y è |x − y|. Valgono la disuguaglianza triangolare |x + y| ≤ |x| + |y| e quella di Cauchy-Schwarz |x·y| ≤ |x||y|, con uguaglianza solo per vettori paralleli. Palle B(p,r] e cubi Q(p,r] si contengono a vicenda: B(p,r] ⊆ Q(p,r] ⊆ B(p,r√n]. Rette, piani, ellissi e cilindri si riconoscono dall'equazione (completando i quadrati).Norma, distanza e prodotto scalare in Rn →). Un iperpiano in $\mathbb R^p$ è l'insieme $\{x : w\cdot x+b=0\}$, con $w\in\mathbb R^p$ vettore dei pesi (normale all'iperpiano: ogni vettore $u-v$ tra due punti del piano soddisfa $w\cdot(u-v)=0$, cioè è ortogonale a $w$) e $b$ il bias (intercetta). La regola di classificazione è

$$\hat y(x)=\operatorname{sign}(w\cdot x+b).$$

Formula (distanza di un punto dall'iperpiano). $$d(x_0)=\frac{|w\cdot x_0+b|}{\|w\|}.$$

Perché. Sia $p$ la proiezione ortogonale di $x_0$ sull'iperpiano: allora $x_0=p+t\,\frac{w}{\|w\|}$ con $t$ la distanza con segno (il vettore $w/\|w\|$ è unitario e ortogonale al piano). Si calcola $w\cdot x_0+b=w\cdot p+b+t\,\frac{w\cdot w}{\|w\|}=0+t\|w\|$, perché $p$ sta sul piano. Da qui $t=(w\cdot x_0+b)/\|w\|$.

Esempio. Piano $x_1+x_2-4=0$, quindi $w=(1,1)$, $b=-4$, $\|w\|=\sqrt2$. Il punto $(3,3)$ dista $|3+3-4|/\sqrt2=2/\sqrt2=\sqrt2\approx1{,}41$.

Normalizzazione

La stessa retta si descrive con infinite coppie $(w,b)$: $(w,b)$ e $(10w,10b)$ sono lo stesso piano (l'equazione $w\cdot x+b=0$ non cambia moltiplicando tutto per $10$). Si sfrutta questa libertà per fissare la scala. Se il punto più vicino al piano ha $|w\cdot x+b|=m>0$, si dividono $w$ e $b$ per $m$: il piano è lo stesso, ma ora quel punto ha $|w\cdot x+b|=1$ e tutti gli altri hanno valore $\ge1$. Con le etichette $\pm1$ la condizione che tutti i punti stiano dal lato giusto e almeno a quella distanza diventa una sola riga:

$$y_i\,(w\cdot x_i+b)\ \ge\ 1\qquad\text{per ogni }i.$$

Il segno di $y_i$ fa sì che per la classe $+1$ si richieda $w\cdot x_i+b\ge1$ e per la classe $-1$ si richieda $w\cdot x_i+b\le-1$. I vettori di supporto sono i punti con l'uguaglianza. Il piano centrale è $w\cdot x+b=0$ e i due piani paralleli che toccano i vettori di supporto sono $w\cdot x+b=+1$ e $w\cdot x+b=-1$.

Formula (larghezza del margine). Con la normalizzazione precedente, la distanza dal piano centrale a ciascun piano parallelo è $1/\|w\|$ e il margine totale è $$\text{larghezza}=\frac{2}{\|w\|}.$$

Esempio. Con $w=(0{,}5;0{,}5)$ si ha $\|w\|=0{,}5\sqrt2\approx0{,}707$, quindi un margine di $1/0{,}707\approx1{,}41$ per lato e $2{,}83$ in totale.

Perché $1/\|w\|$. Un vettore di supporto $x_s$ ha $|w\cdot x_s+b|=1$; per la formula della distanza la sua distanza dal piano centrale è $|w\cdot x_s+b|/\|w\|=1/\|w\|$. I due lati (classe $+1$ e classe $-1$) contribuiscono ciascuno $1/\|w\|$, da cui $2/\|w\|$.

Conseguenza: massimizzare il margine equivale a minimizzare la norma di $w$. Una $w$ piccola vuol dire un piano poco «ripido», quindi i piani $\pm1$ sono lontani tra loro.

3. Il problema di ottimizzazione (margine rigido)

Passaggi di equivalenza: massimizzare $2/\|w\|$ è come massimizzare $1/\|w\|$ (la costante $2$ non sposta il massimo), e questo è come minimizzare $\|w\|$ (il reciproco è decrescente per valori positivi). Poiché $t\mapsto t^2$ è crescente per $t\ge0$, minimizzare $\|w\|$ è come minimizzare $\|w\|^2$, e moltiplicare per la costante positiva $\frac12$ non cambia dove sta il minimo. Si ottiene $\frac12\|w\|^2$, una funzione quadratica derivabile ovunque; il $\frac12$ si sceglie perché il suo gradiente è semplicemente $w$ (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 →).

Formula (SVM a margine rigido, hard margin). $$\min_{w,b}\ \frac12\|w\|^2\qquad\text{soggetto a}\quad y_i(w\cdot x_i+b)\ge1,\ \ i=1,\dots,n.$$

È un problema di programmazione quadratica convessa: funzione obiettivo convessa (una somma di quadrati, Funzioni convesse in più variabiliUn insieme C è convesso se contiene il segmento tra due suoi punti; f: C → R è convessa se f(tx + (1−t)y) ≤ t f(x) + (1−t) f(y) per t in [0,1], cioè il grafico sta sotto le corde. Se f è differenziabile, è convessa se e solo se f(y) ≥ f(x) + ∇f(x)·(y − x) (il grafico sta sopra ogni piano tangente). Se f è C² su un aperto convesso, è convessa se e solo se l'hessiana è semidefinita positiva in ogni punto; se è definita positiva ovunque f è strettamente convessa (non vale il viceversa: x⁴). Per una funzione convessa ogni punto critico è un minimo globale.Funzioni convesse in più variabili →) e vincoli lineari. Ha quindi un unico minimo globale (nessun minimo locale, a differenza delle reti neurali) e si risolve con algoritmi dedicati; il più usato per le SVM è la Sequential Minimal Optimization (SMO), che ottimizza due moltiplicatori alla volta. Una discesa del gradiente sul vincolo non è la scelta naturale; ha senso solo per la versione con hinge loss del paragrafo 5.

Esempio numerico completo

Dati in $\mathbb R^2$: classe $-1$: $(1,1),\ (2,-1),\ (0;0{,}5)$; classe $+1$: $(3,3),\ (5,2),\ (3{,}5;4)$.

I due punti più vicini tra classi diverse sono $(1,1)$ e $(3,3)$, distanti $2\sqrt2$. Il piano che li separa col massimo margine è l'asse del segmento che li unisce: passa per il punto medio $(2,2)$ ed è perpendicolare a $(2,2)$, quindi $x_1+x_2=4$. Per portare i due punti su $\pm1$ si cerca $w=t\,(1,1)$ con $w\cdot(3,3)+b=1$ e $w\cdot(1,1)+b=-1$: sottraendo, $4t=2$, cioè $t=\tfrac12$, e $b=-1-w\cdot(1,1)=-1-1=-2$. Risultato:

$$w=(0{,}5;\ 0{,}5),\qquad b=-2.$$

Verifica sui sei punti ($y_i(w\cdot x_i+b)$): $(1,1)\to1$; $(2,-1)\to1{,}5$; $(0;0{,}5)\to1{,}75$; $(3,3)\to1$; $(5,2)\to1{,}5$; $(3{,}5;4)\to1{,}75$. Tutti $\ge1$, e solo $(1,1)$ e $(3,3)$ valgono esattamente $1$: sono i vettori di supporto. Il margine totale è $2/\|w\|=2\sqrt2$, uguale alla distanza tra i due vettori di supporto, come deve essere. (Il risultato si controlla anche cercando, tra tutte le $(w,b)$ ammissibili, quella con $\|w\|$ minima.)

4. Forma duale: perché la SVM dipende dai prodotti scalari

Questo passaggio non cambia la soluzione, ma spiega i vettori di supporto e rende possibile il kernel. Si usa il metodo dei moltiplicatori di Lagrange (Massimi e minimi vincolati e moltiplicatori di LagrangeGli estremi di f sul vincolo g = c si cercano per sostituzione, per parametrizzazione o con i moltiplicatori di Lagrange: se f, g sono C¹, P0 è un estremo vincolato e ∇g(P0) ≠ 0, esiste λ con ∇f(P0) = λ∇g(P0) (curva di livello di f tangente al vincolo). Si risolve il sistema ∇f = λ∇g, g = c, si aggiungono i punti del vincolo con ∇g = 0 e si confrontano i valori; se il vincolo è compatto, Weierstrass garantisce massimo e minimo.Massimi e minimi vincolati e moltiplicatori di Lagrange →), qui con vincoli di disuguaglianza. Il problema è: minimizzare $f(w)=\frac12\|w\|^2$ con i vincoli $g_i(w,b)=y_i(w\cdot x_i+b)-1\ge0$. A ogni vincolo si associa un moltiplicatore $\alpha_i\ge0$ e si forma la lagrangiana (si sottrae $\alpha_ig_i$ perché violare il vincolo, $g_i<0$, deve aumentare $\mathcal L$ e quindi essere penalizzato):

$$\mathcal L(w,b,\alpha)=\tfrac12\|w\|^2-\sum_i\alpha_i\big[y_i(w\cdot x_i+b)-1\big].$$

Passo 1: annullare il gradiente rispetto alle variabili primali ($w$ e $b$), perché nel minimo la lagrangiana è stazionaria. Si ricordano $\nabla_w\frac12\|w\|^2=w$ e $\nabla_w(w\cdot x_i)=x_i$:

• $\nabla_w\mathcal L=w-\sum_i\alpha_iy_ix_i=0\ \Rightarrow\ w=\sum_i\alpha_iy_ix_i$;
• $\partial\mathcal L/\partial b=-\sum_i\alpha_iy_i=0\ \Rightarrow\ \sum_i\alpha_iy_i=0$ (il termine $\alpha_iy_ib$ è l'unico che contiene $b$).

Passo 2: sostituire in $\mathcal L$. Si espande $\mathcal L=\frac12\|w\|^2-\sum_i\alpha_iy_i\,(w\cdot x_i)-b\sum_i\alpha_iy_i+\sum_i\alpha_i$ e si calcolano i quattro pezzi con $w=\sum_i\alpha_iy_ix_i$. Sia $S=\sum_{i,j}\alpha_i\alpha_jy_iy_j\,(x_i\cdot x_j)$.

• $\frac12\|w\|^2=\frac12\,w\cdot w=\frac12\sum_i\sum_j\alpha_iy_i\alpha_jy_j\,(x_i\cdot x_j)=\frac12S$;
• $\sum_i\alpha_iy_i\,(w\cdot x_i)=\sum_i\alpha_iy_i\sum_j\alpha_jy_j\,(x_j\cdot x_i)=S$;
• $b\sum_i\alpha_iy_i=b\cdot0=0$ per il passo 1;
• $\sum_i\alpha_i$ resta.

Quindi $\mathcal L=\frac12S-S-0+\sum_i\alpha_i=\sum_i\alpha_i-\frac12S$: sono scomparsi $w$ e $b$. Massimizzando questa espressione rispetto agli $\alpha_i\ge0$ (con il vincolo $\sum\alpha_iy_i=0$ ricavato prima) si ottiene il problema duale:

Formula (forma duale). $$\max_{\alpha\ge0}\ \sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,(x_i\cdot x_j)\qquad\text{con}\quad\sum_i\alpha_iy_i=0.$$ Il classificatore è $\hat y(x)=\operatorname{sign}\!\Big(\sum_i\alpha_iy_i\,(x_i\cdot x)+b\Big)$, perché $w\cdot x=\sum_i\alpha_iy_i\,(x_i\cdot x)$.

Nel duale si massimizza perché il duale è il minimo della lagrangiana sulle variabili primali: per ogni $\alpha$ ammissibile dà un limite inferiore al valore del primale, e il miglior limite si trova massimizzando.

Tre fatti importanti:

1. Le condizioni KKT (le condizioni di ottimo per i problemi con vincoli di disuguaglianza) includono la complementarità $\alpha_i\big[y_i(w\cdot x_i+b)-1\big]=0$: il prodotto di due termini non negativi è zero, quindi o $\alpha_i=0$ o il vincolo è attivo (vale l'uguaglianza). Se un punto è strettamente oltre il margine ($y_i(w\cdot x_i+b)>1$) allora $\alpha_i=0$. Solo i vettori di supporto hanno $\alpha_i>0$, quindi $w=\sum\alpha_iy_ix_i$ è una combinazione di pochi punti.
2. I dati compaiono solo come prodotti scalari $x_i\cdot x_j$: è la porta d'ingresso del kernel (paragrafo 7).
3. Il duale è concavo: si risolve con SMO.

Esempio. Nell'esempio i vettori di supporto sono due, con $\alpha_1=\alpha_2=\alpha$ per $\sum\alpha_iy_i=0$. Da $w=\alpha\,(3,3)-\alpha\,(1,1)=\alpha\,(2,2)=(0{,}5;0{,}5)$ si ricava $\alpha=0{,}25$; gli altri quattro punti hanno $\alpha=0$. Si controlla che il valore del duale $\sum\alpha_i-\frac12\sum\alpha_i\alpha_jy_iy_jx_i\cdot x_j=0{,}5-\frac12\cdot0{,}25^2\cdot(2+18-2\cdot6)=0{,}5-0{,}25=0{,}25$ coincide con il valore del primale $\frac12\|w\|^2=0{,}25$.

5. Dati non separabili: margine morbido (soft margin)

Il margine rigido ha due difetti: (i) se le classi si sovrappongono il problema non ha soluzione; (ii) anche se esiste, basta un solo outlier a spostare il piano. Nell'esempio 1D delle slide, un punto di una classe che cade tra l'altra classe obbliga un margine rigido a un'unica soglia stretta, cioè overfitting e alta varianza.

Si accetta allora di sbagliare qualcosa sul training: si sceglie una soglia che consente qualche punto dentro il margine o dal lato sbagliato, per ridurre la varianza al prezzo di un po' di bias. Il margine ottenuto così si chiama margine morbido (soft margin) e il classificatore Support Vector Classifier (SVC).

Per ogni punto si introduce una variabile di scarto (slack) $\xi_i\ge0$ che misura di quanto viola il vincolo:

Formula (SVM a margine morbido). $$\min_{w,b,\xi}\ \frac12\|w\|^2+C\sum_{i=1}^n\xi_i\qquad\text{soggetto a}\quad y_i(w\cdot x_i+b)\ge1-\xi_i,\ \ \xi_i\ge0.$$

Interpretazione di $\xi_i$ per un punto con $m_i=y_i(w\cdot x_i+b)$:

• $\xi_i=0$: il punto è fuori dal margine, dal lato giusto ($m_i\ge1$);
• $0<\xi_i<1$: è dentro il margine ma ancora dal lato giusto;
• $\xi_i\ge1$: è dal lato sbagliato del piano, cioè mal classificato ($m_i\le0$).

Il valore minimo di $\xi_i$ che soddisfa il vincolo è $\xi_i=\max(0,\,1-m_i)$.

Perché $\xi_i=\max(0,1-m_i)$. Il vincolo dice $\xi_i\ge1-m_i$ e $\xi_i\ge0$; la funzione obiettivo cresce con $\xi_i$ (c'è $+C\xi_i$ con $C>0$), quindi il valore migliore è il più piccolo ammesso, cioè il maggiore tra i due limiti inferiori $1-m_i$ e $0$. Se $m_i\ge1$ il primo è negativo e vince $0$; se $m_i<1$ vince $1-m_i$.

Il parametro nel duale. Si procede come nel paragrafo 4, con un moltiplicatore $\alpha_i\ge0$ per il vincolo del margine e $\mu_i\ge0$ per $\xi_i\ge0$: $\mathcal L=\frac12\|w\|^2+C\sum\xi_i-\sum\alpha_i[y_i(w\cdot x_i+b)-1+\xi_i]-\sum\mu_i\xi_i$. La derivata rispetto a $\xi_i$ è $C-\alpha_i-\mu_i=0$, quindi $\alpha_i=C-\mu_i\le C$ (perché $\mu_i\ge0$). Il resto è identico: il duale è lo stesso, con un vincolo in più, $0\le\alpha_i\le C$. I punti con $\alpha_i=C$ sono quelli dentro il margine o mal classificati; $0<\alpha_i<C$ quelli esattamente sul margine; $\alpha_i=0$ quelli fuori. Tutti con $\alpha_i>0$ sono vettori di supporto.

Esempio. Con $w=(0{,}5;0{,}5)$, $b=-2$ e un punto di classe $+1$ in $(2{,}5;2)$: $m=0{,}5\cdot4{,}5-2=0{,}25$, quindi $\xi=0{,}75$ (dentro il margine, ma dal lato corretto). Un punto di classe $+1$ in $(3;0{,}5)$ ha $m=0{,}5\cdot3{,}5-2=-0{,}25$ e $\xi=1{,}25$: mal classificato.

Il parametro $C$

$C>0$ regola quanto costa uno scarto rispetto alla larghezza del margine.

Il compromesso bias-varianza (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 →) si regola scegliendo $C$ per cross-validation. Sull'Iris con due classi (Virginica contro Versicolour) e due soli attributi del petalo, le slide riportano l'accuratezza in cross-validation al crescere di $C$: $0{,}95$ per $C=0{,}01$, $0{,}94$ per $C=0{,}1$ e $C=1$, $0{,}93$ per $C=10$, $0{,}94$ per $C=100$. Il margine passa da larghissimo (molti errori ammessi) a quasi invisibile (si cerca di classificare tutto il training), ma qui le differenze sono piccole perché le due classi sono quasi separabili: l'effetto di $C$ si vede soprattutto sulla posizione dei vettori di supporto e sulla stabilità del piano.

Hinge loss: lo stesso problema come funzione di perdita

Sostituendo in $\frac12\|w\|^2+C\sum_i\xi_i$ il valore minimo $\xi_i=\max(0,1-m_i)$ trovato sopra, il soft margin diventa un problema senza vincoli nelle sole $(w,b)$:

$$\min_{w,b}\ \frac12\|w\|^2+C\sum_i\max\big(0,\,1-y_i(w\cdot x_i+b)\big).$$

La funzione $\max(0,1-m)$ è la hinge loss: zero se $m\ge1$, cresce linearmente se $m<1$. È una versione convessa dell'errore di classificazione. Il termine $\frac12\|w\|^2$ è una regolarizzazione $\ell_2$ come nella ridge regression (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 →); $C$ è l'inverso della forza di regolarizzazione: dividendo l'obiettivo per $C>0$ (stesso minimo) si ottiene $\sum_i\max(0,1-m_i)+\frac1{2C}\|w\|^2$, cioè una loss più una penalità $\lambda\|w\|^2$ con $\lambda=\frac1{2C}$.

Un confronto utile con la regressione logistica (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 →): entrambe penalizzano gli errori in modo approssimativamente lineare, ma la hinge è esattamente zero oltre il margine, quindi i punti già ben classificati non contribuiscono (è per questo che solo i vettori di supporto contano). La logistica ha una coda sempre positiva e dà anche probabilità; la SVM dà soltanto una distanza dal piano.

6. Bordi non lineari: espansione di base

Se i dati non sono separabili da un iperpiano nello spazio originale, si può comunque separarli in uno spazio più grande. Esempio 1D: punti di una classe in $x\in\{-1,0,1\}$ e dell'altra in $x=\pm3$: nessuna soglia sulla retta li divide. Si aggiunge la coordinata $x^2$ e si lavora nel piano $(x,x^2)$: ora la retta $x^2=4$ li separa (è una soglia sul quadrato).

In generale si sceglie una mappa di feature $\phi:\mathbb R^p\to\mathbb R^D$ con $D>p$ e si costruisce l'SVM sui vettori $\phi(x)$: il bordo è lineare in $\phi(x)$ e curvo in $x$. Per un punto $x=(x_1,x_2)$ la mappa polinomiale di grado 2 è

$$\phi(x)=\big[x_1^2,\ x_2^2,\ \sqrt2\,x_1x_2,\ \sqrt2\,x_1,\ \sqrt2\,x_2,\ 1\big]\in\mathbb R^6.$$

Il costo. Con $p$ attributi e grado $d$ le nuove dimensioni crescono come $\binom{p+d}{d}$: con $p=1000$ e $d=3$ sono oltre $1{,}6\cdot10^8$. Calcolare e memorizzare $\phi(x)$ diventa impossibile. Il kernel trick evita questo calcolo.

7. Il kernel trick

Nel duale i dati entrano solo attraverso $x_i\cdot x_j$. Dopo l'espansione di base compare $\phi(x_i)\cdot\phi(x_j)$. Se esiste una funzione $K$ che calcola direttamente quel numero senza costruire $\phi$, non serve mai lavorare nello spazio grande.

Definizione (kernel). Una funzione $K(x,x')$ è un kernel se vale $K(x,x')=\langle\phi(x),\phi(x')\rangle$ per una certa mappa $\phi$. Misura la «somiglianza» di $x$ e $x'$: grande per punti simili, piccola per punti dissimili. Una SVM (Support Vector Machine) è un SVC in cui $x_i\cdot x_j$ è sostituito dal kernel: $$\hat y(x)=\operatorname{sign}\Big(\sum_i\alpha_iy_i\,K(x_i,x)+b\Big).$$

Esempio (kernel polinomiale di grado 2). Con $\phi$ del paragrafo precedente si dimostra $\langle\phi(x),\phi(z)\rangle=(x\cdot z+1)^2$: si espande il quadrato, $(x_1z_1+x_2z_2+1)^2=x_1^2z_1^2+x_2^2z_2^2+2x_1x_2z_1z_2+2x_1z_1+2x_2z_2+1$, e si osserva che i sei addendi sono i prodotti delle sei componenti corrispondenti di $\phi(x)$ e $\phi(z)$ (per esempio $\sqrt2x_1x_2\cdot\sqrt2z_1z_2=2x_1x_2z_1z_2$); da qui il fattore $\sqrt2$ nella mappa. Numericamente, per $x=(1,2)$, $z=(3,1)$: $\phi(x)=[1,4,2\sqrt2,\sqrt2,2\sqrt2,1]$, $\phi(z)=[9,1,3\sqrt2,3\sqrt2,\sqrt2,1]$ e $\langle\phi(x),\phi(z)\rangle=9+4+12+6+4+1=36$. Con il kernel: $x\cdot z=3+2=5$ e $(5+1)^2=36$. Stesso risultato con un solo prodotto scalare in $\mathbb R^2$ invece di uno in $\mathbb R^6$.

Kernel principali

Perché la mappa dell'RBF ha dimensione infinita. Si sviluppa il quadrato della norma, $\|x-x'\|^2=\|x\|^2+\|x'\|^2-2\,x\cdot x'$, quindi $K=e^{-\gamma\|x\|^2}\,e^{-\gamma\|x'\|^2}\,e^{2\gamma\,x\cdot x'}$. L'ultimo fattore si scrive con la serie dell'esponenziale (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 →): $e^{2\gamma x\cdot x'}=\sum_{k=0}^{\infty}\frac{(2\gamma)^k}{k!}(x\cdot x')^k$, una somma di kernel polinomiali di ogni grado, ognuno con la sua mappa di feature: in tutto servono infinite componenti. Il kernel però si calcola con un solo esponenziale.

Il kernel RBF. Dipende solo dalla distanza: vale $1$ per $x=x'$ e tende a $0$ se i punti sono lontani. $\gamma>0$ regola la «finestra di influenza» di ogni vettore di supporto: $\gamma$ grande vuol dire influenza locale e bordi molto frastagliati (rischio di overfitting), $\gamma$ piccolo influenza larga e bordi lisci (rischio di underfitting). Come per $C$, i due parametri $(C,\gamma)$ si scelgono per cross-validation, tipicamente con una griglia.

Esempio. $x=(1,2)$, $z=(3,1)$: $\|x-z\|^2=4+1=5$. Con $\gamma=0{,}5$ si ottiene $K=e^{-2{,}5}\approx0{,}082$; con $\gamma=0{,}1$, $K=e^{-0{,}5}\approx0{,}607$.

Cosa mostrano le slide sui dataset Moons e Circles

Su due dataset non lineari (due lune intrecciate, due cerchi concentrici) le slide confrontano vari modelli, con l'accuratezza in cross-validation:

Sui cerchi il bordo lineare della logistica è inutile (accuratezza sotto il caso); basta un kernel (o delle feature) non lineare. Sulle lune l'AUC (vedi 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 →) della SVM RBF è $0{,}99$ contro $0{,}95$ della SVM lineare.

Regole pratiche

• Scalare sempre gli attributi (standardizzazione): la SVM dipende dalle distanze, un attributo con scala grande domina il margine e il kernel RBF.
• Provare prima il kernel lineare (veloce, interpretabile via $w$), poi RBF.
• Più di due classi: scikit-learn combina molti classificatori binari (uno contro uno).
• Costo: l'addestramento ha complessità tra $O(n^2)$ e $O(n^3)$ nel numero di campioni, quindi le SVM con kernel sono lente su dataset molto grandi.

from sklearn.svm import SVC
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import GridSearchCV

pipe = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
griglia = {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.01, 0.1, 1]}
cerca = GridSearchCV(pipe, griglia, cv=5).fit(X_train, y_train)   # C e gamma per cross-validation
print(cerca.best_params_, cerca.score(X_test, y_test))

La standardizzazione sta dentro la pipeline, così viene calcolata sul solo training di ogni fold (nessuna fuga di informazione dal test, 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 →).

8. Regressione a vettori di supporto (SVR)

Lo stesso schema vale per la regressione. Si cerca un modello lineare $f(x)=w\cdot x+b$ (o curvo, via kernel) il più piatto possibile (cioè con $\|w\|$ piccola) che stia entro una distanza $\varepsilon$ dai dati: lo scarto sotto $\varepsilon$ non costa nulla, formando un «tubo» di larghezza $2\varepsilon$ intorno alla funzione.

Formula (SVR). $$\min_{w,b,\xi,\xi^*}\ \frac12\|w\|^2+C\sum_i(\xi_i+\xi_i^*)\quad\text{con}\quad y_i-w\cdot x_i-b\le\varepsilon+\xi_i,\ \ w\cdot x_i+b-y_i\le\varepsilon+\xi_i^*,\ \ \xi_i,\xi_i^*\ge0.$$

$\xi_i$ misura le violazioni sopra il tubo e $\xi_i^*$ quelle sotto. Solo i punti fuori dal tubo (o sul bordo) sono vettori di supporto. La perdita è la $\varepsilon$-insensibile $\max(0,|y-f(x)|-\varepsilon)$, che per $\varepsilon=0$ diventa l'errore assoluto. $\varepsilon$ regola il numero di vettori di supporto e la liscezza; $C$ la penalità sugli scarti; il kernel (lineare, polinomiale, RBF) dà curve più o meno flessibili. Sulle slide con dati non lineari il kernel lineare fa una regressione troppo rigida, il polinomiale è instabile ai bordi, l'RBF segue bene l'onda.

9. Un cenno alla curva ROC

Le SVM producono una distanza dal piano, $f(x)=w\cdot x+b$, che si può confrontare con una soglia diversa da $0$: variando la soglia si ottengono diverse coppie (tasso di falsi positivi, tasso di veri positivi) e quindi la curva ROC. La curva e l'area sotto di essa (AUC) sono trattate 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 →. Esempio dalle slide: in un filtro anti-spam un falso positivo (messaggio utile perso) costa più di un falso negativo (spam letto a mano), quindi si sceglie una soglia che tiene basso il FPR.

10. Errori tipici

• Dimenticare di scalare gli attributi, soprattutto con RBF.
• Usare etichette $0/1$ nei calcoli a mano: le formule richiedono $\pm1$.
• Credere che un $C$ enorme dia «più accuratezza»: sul training sì, sul test spesso no (overfitting).
• Confondere $\gamma$ (kernel) con $C$ (penalità sugli scarti): i due parametri agiscono in modo diverso.
• Dimenticare che il margine è $2/\|w\|$ e non $1/\|w\|$ quando si chiede la larghezza totale.

Esercizi: Esercizio - SVM a margine rigido e morbido a mano, Esercizio - Kernel e confronto tra SVM.