Esercizio - SVM a margine rigido e morbido a mano

Testo. Nel piano sono dati quattro punti: classe $-1$: $A=(1,1)$, $B=(2,3)$; classe $+1$: $C=(4,1)$, $D=(5,4)$.

1. Si trovi l'iperpiano a margine massimo $w\cdot x+b=0$ e si calcolino la larghezza del margine e i vettori di supporto.
2. Si ricavino i moltiplicatori $\alpha_i$ della forma duale e si verifichi $w=\sum\alpha_iy_ix_i$.
3. Si classifichi il punto $(2{,}5;\,2)$.
4. Si aggiunge il punto $E=(3,3)$ di classe $-1$. Con $(w,b)$ del punto 1 si calcolino la variabile di scarto $\xi_E$ e il valore dell'obiettivo soft margin $\frac12\|w\|^2+C\sum\xi_i$. Si confronti poi con il piano $w'=(1{,}2;\,-0{,}4)$, $b'=-3{,}4$: per quali $C$ conviene il primo?

Teoria usata: 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 →, 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 →.

1. Margine massimo

Idea. Tra due classi separabili, il piano a margine massimo ha due piani paralleli ($w\cdot x+b=\pm1$) che toccano i vettori di supporto. Conviene cercare quali punti stanno sui due piani.

Passo 1: i punti più estremi. Nella classe $+1$ i punti $C=(4,1)$ e $D=(5,4)$ sono i più vicini alla classe $-1$ in direzioni diverse; si fa l'ipotesi che entrambi stiano sul piano $w\cdot x+b=+1$ e che $B=(2,3)$ stia sul piano $w\cdot x+b=-1$ (si verificherà dopo).

Passo 2: direzione di $w$. Se $C$ e $D$ stanno sullo stesso piano parallelo al bordo, il vettore $D-C=(1,3)$ è parallelo al piano, quindi ortogonale a $w$: $w\cdot(1,3)=0$. I vettori ortogonali a $(1,3)$ sono multipli di $(3,-1)$: $w=t\,(3,-1)$.

Passo 3: valori di $t$ e $b$. Dalle due condizioni:

• $C$ su $+1$: $w\cdot C+b=t(12-1)+b=11t+b=1$;
• $B$ su $-1$: $w\cdot B+b=t(6-3)+b=3t+b=-1$.

Sottraendo la seconda dalla prima: $8t=2$, $t=0{,}25$. Allora $w=(0{,}75;\,-0{,}25)$ e $b=-1-3t=-1{,}75$.

Passo 4: verifica di tutti i punti con $m_i=y_i(w\cdot x_i+b)$:

Tutti $m_i\ge1$ e tre uguali a $1$: l'ipotesi è corretta. I vettori di supporto sono $B$, $C$ e $D$; $A$ è fuori dal margine.

Margine. $\|w\|=\sqrt{0{,}75^2+0{,}25^2}=\sqrt{0{,}625}=0{,}7906$. Larghezza totale $2/\|w\|=2{,}53$, cioè $1{,}26$ per lato. (Per essere sicuri che sia il minimo di $\|w\|$ si può controllare che nessun altro piano ammissibile abbia norma inferiore: lo conferma la ricerca esaustiva sulle coppie e terne di punti di supporto.)

2. Moltiplicatori $\alpha_i$

Solo i vettori di supporto hanno $\alpha_i>0$: $\alpha_A=0$. Le condizioni sono $w=\sum\alpha_iy_ix_i$ e $\sum\alpha_iy_i=0$:

• $\sum\alpha_iy_i=0$: $-\alpha_B+\alpha_C+\alpha_D=0$, quindi $\alpha_B=\alpha_C+\alpha_D$;
• componente $x$: $-2\alpha_B+4\alpha_C+5\alpha_D=0{,}75$;
• componente $y$: $-3\alpha_B+\alpha_C+4\alpha_D=-0{,}25$.

Sostituendo $\alpha_B=\alpha_C+\alpha_D$: la seconda diventa $2\alpha_C+3\alpha_D=0{,}75$ e la terza $-2\alpha_C+\alpha_D=-0{,}25$, da cui $\alpha_D=2\alpha_C-0{,}25$. Sostituendo nella prima: $2\alpha_C+6\alpha_C-0{,}75=0{,}75$, $\alpha_C=0{,}1875$, $\alpha_D=0{,}125$, $\alpha_B=0{,}3125$. Tutti positivi, come devono essere.

Verifica. $w=-0{,}3125\,(2,3)+0{,}1875\,(4,1)+0{,}125\,(5,4)=(-0{,}625+0{,}75+0{,}625;\ -0{,}9375+0{,}1875+0{,}5)=(0{,}75;\ -0{,}25)$ ✓. Valore del duale: $\sum\alpha_i=0{,}625$ e $\frac12\|w\|^2=0{,}3125$; il duale è $\sum\alpha_i-\frac12\|w\|^2$ calcolato in $w$, cioè $0{,}625-\frac12\cdot0{,}625=0{,}3125$, uguale al primale ✓.

3. Classificazione di $(2{,}5;\,2)$

$w\cdot x+b=0{,}75\cdot2{,}5-0{,}25\cdot2-1{,}75=1{,}875-0{,}5-1{,}75=-0{,}375$. Negativo: classe $-1$. Il punto è dentro il margine ($|{-0{,}375}|<1$), quindi la decisione è poco sicura. Con la forma duale si ottiene lo stesso valore: $\sum_i\alpha_iy_i\,(x_i\cdot x)+b=-0{,}3125\cdot(5+6)+0{,}1875\cdot(10+2)+0{,}125\cdot(12{,}5+8)-1{,}75=-3{,}4375+2{,}25+2{,}5625-1{,}75=-0{,}375$ ✓.

4. Un punto che viola il margine

$E=(3,3)$, $y_E=-1$: $w\cdot E+b=2{,}25-0{,}75-1{,}75=-0{,}25$, quindi $m_E=y_E(w\cdot E+b)=0{,}25$. Il punto è dal lato giusto ma dentro il margine: $\xi_E=\max(0,1-0{,}25)=0{,}75$. Gli altri punti hanno $m\ge1$, quindi $\xi=0$.

Obiettivo del piano $(w,b)$: $\frac12\|w\|^2+C\cdot0{,}75=0{,}3125+0{,}75\,C$.

Piano alternativo $w'=(1{,}2;-0{,}4)$, $b'=-3{,}4$: $\|w'\|^2=1{,}44+0{,}16=1{,}6$, $\frac12\|w'\|^2=0{,}8$. Margini: $A:-(1{,}2-0{,}4-3{,}4)=2{,}6$; $B:-(2{,}4-1{,}2-3{,}4)=2{,}2$; $C:4{,}8-0{,}4-3{,}4=1$; $D:6-1{,}6-3{,}4=1$; $E:-(3{,}6-1{,}2-3{,}4)=1$. Tutti $\ge1$: nessuno scarto, obiettivo $0{,}8$ (è il piano a margine rigido di tutti e cinque i punti).

Confronto. Il primo piano è migliore se $0{,}3125+0{,}75\,C<0{,}8$, cioè $C<0{,}65$. Con $C$ piccolo (errori poco costosi) conviene il margine largo con uno scarto; con $C>0{,}65$ conviene il piano più stretto che separa tutto. Ricordare che si confrontano solo i due candidati: il vero ottimo soft margin si trova risolvendo il problema di ottimizzazione.

Controllo con il codice

import numpy as np
from sklearn.svm import SVC
X = np.array([[1,1],[2,3],[4,1],[5,4]]); y = np.array([-1,-1,1,1])
clf = SVC(kernel="linear", C=1e6).fit(X, y)       # C enorme ~ margine rigido
print(clf.coef_, clf.intercept_, clf.support_)    # atteso: [[ 0.75 -0.25]] [-1.75], indici 1,2,3
print(clf.dual_coef_)                             # y_i * alpha_i: [[-0.3125  0.1875  0.125 ]]