Esercizio - Kernel e confronto tra SVM

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo.

1. Con la mappa di grado 2 $\phi(x)=[x_1^2,\,x_2^2,\,\sqrt2x_1x_2,\,\sqrt2x_1,\,\sqrt2x_2,\,1]$ si verifichi $\langle\phi(x),\phi(z)\rangle=(x\cdot z+1)^2$ per $x=(2,-1)$, $z=(0,3)$.
2. Quattro punti (problema XOR): classe $+1$ in $(1,1)$ e $(-1,-1)$, classe $-1$ in $(1,-1)$ e $(-1,1)$. Si mostri che nessun iperpiano li separa nel piano, si trovi una feature che li rende separabili e si calcoli il margine.
3. Per lo stesso problema si calcoli la matrice del kernel $K(x,z)=(x\cdot z+1)^2$ e si ricavi $\alpha$ e il classificatore in forma duale.
4. Kernel RBF: si calcoli $K(x,z)$ per $x=(0,0)$, $z=(1,1)$ con $\gamma=0{,}1;\,1;\,10$ e si commenti.
5. Quante componenti ha la mappa polinomiale completa di grado 3 per $p=100$ attributi? Perché si usa il kernel?

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. Verifica del kernel polinomiale

$x\cdot z=2\cdot0+(-1)\cdot3=-3$, quindi $(x\cdot z+1)^2=(-2)^2=4$.

Con la mappa: $\phi(x)=[4,\,1,\,\sqrt2\cdot2\cdot(-1),\,\sqrt2\cdot2,\,\sqrt2\cdot(-1),\,1]=[4,1,-2\sqrt2,2\sqrt2,-\sqrt2,1]$ e $\phi(z)=[0,\,9,\,0,\,0,\,3\sqrt2,\,1]$. Prodotto scalare componente per componente: $4\cdot0+1\cdot9+(-2\sqrt2)\cdot0+2\sqrt2\cdot0+(-\sqrt2)(3\sqrt2)+1\cdot1=0+9+0+0-6+1=4$ ✓. I due calcoli coincidono, ma il primo usa un solo prodotto scalare in $\mathbb R^2$.

2. Il problema XOR

Non separabile. Un iperpiano (retta) $w_1x_1+w_2x_2+b=0$ dovrebbe dare $w_1+w_2+b>0$ e $-w_1-w_2+b>0$ (i due punti $+1$), $w_1-w_2+b<0$ e $-w_1+w_2+b<0$ (i due $-1$). Sommando le prime due: $2b>0$. Sommando le ultime due: $2b<0$. Contraddizione: nessuna retta separa le classi.

Feature aggiuntiva. Si usa $\phi(x)=(x_1,x_2,x_1x_2)$. I due punti $+1$ hanno $x_1x_2=+1$, i due $-1$ hanno $x_1x_2=-1$: in $\mathbb R^3$ il piano $z=0$ (con $z=x_1x_2$) li separa. Con $w=(0,0,1)$, $b=0$: $y_i(w\cdot\phi(x_i)+b)=y_i\,x_{i1}x_{i2}=1$ per tutti e quattro. Il margine totale è $2/\|w\|=2$ e tutti e quattro i punti sono vettori di supporto.

3. Forma duale con il kernel

Prodotti scalari $x_i\cdot x_j$: $2$ tra un punto e sé stesso, $-2$ tra punti opposti, $0$ tra punti con una coordinata che cambia segno. Quindi $K=(x_i\cdot x_j+1)^2$ vale $(2+1)^2=9$ sulla diagonale, $(-2+1)^2=1$ tra punti opposti, $(0+1)^2=1$ negli altri casi: nell'ordine $(1,1),(-1,-1),(1,-1),(-1,1)$

$$K=\begin{bmatrix}9&1&1&1\\1&9&1&1\\1&1&9&1\\1&1&1&9\end{bmatrix}.$$

Per simmetria i quattro punti hanno lo stesso $\alpha$ e $b=0$ (la condizione $\sum\alpha_iy_i=0$ vale perché $y=(+,+,-,-)$). Per il punto $x_1$ la condizione sul margine $y_1f(x_1)=1$ con $f(x_1)=\sum_j\alpha y_jK_{j1}+b$ dà $\alpha\,(9\cdot1+1\cdot1+1\cdot(-1)+1\cdot(-1))=8\alpha=1$, quindi $\alpha=\tfrac18$.

Classificatore: $f(x)=\frac18\big[(x^{(1)}\!\cdot x+1)^2+(x^{(2)}\!\cdot x+1)^2-(x^{(3)}\!\cdot x+1)^2-(x^{(4)}\!\cdot x+1)^2\big]$. Con $x=(a,b)$ i quattro termini sono $(a+b+1)^2,\ (-a-b+1)^2,\ (a-b+1)^2,\ (-a+b+1)^2$. La somma dei primi due è $2(a+b)^2+2$, quella degli ultimi due $2(a-b)^2+2$, la differenza $2[(a+b)^2-(a-b)^2]=8ab$. Quindi $f(x)=\frac18\cdot8ab=ab=x_1x_2$: coincide con la feature trovata al punto 2. Il bordo di decisione è $x_1x_2=0$, cioè i due assi, e la classe è $\operatorname{sign}(x_1x_2)$.

4. Kernel RBF

$\|x-z\|^2=1+1=2$, $K=e^{-2\gamma}$:

Con $\gamma$ piccolo punti a distanza $\sqrt2$ sono ancora «molto simili» (influenza larga, bordo liscio, rischio di underfitting); con $\gamma=10$ sono già praticamente scorrelati (ogni vettore di supporto influenza solo il suo intorno, bordo frastagliato, rischio di overfitting). $\gamma$ si sceglie per cross-validation insieme a $C$.

5. Dimensione della mappa

I monomi di grado al più $3$ in $p=100$ variabili sono $\binom{p+3}{3}=\binom{103}{3}=\frac{103\cdot102\cdot101}{6}=176\,851$. Calcolare e memorizzare vettori di quella lunghezza per ogni campione è oneroso; con il kernel $K(x,z)=(\gamma\,x\cdot z+r)^3$ basta un prodotto scalare in $\mathbb R^{100}$ e una potenza. Il kernel RBF corrisponde invece a una mappa di dimensione infinita, che non si potrebbe nemmeno scrivere.

Verifica numerica

import numpy as np
phi = lambda v: np.array([v[0]**2, v[1]**2, np.sqrt(2)*v[0]*v[1], np.sqrt(2)*v[0], np.sqrt(2)*v[1], 1])
x, z = np.array([2, -1]), np.array([0, 3])
print(phi(x) @ phi(z), (x @ z + 1) ** 2)        # 4.0  4
from sklearn.svm import SVC
X = np.array([[1,1],[-1,-1],[1,-1],[-1,1]]); y = np.array([1,1,-1,-1])
SVC(kernel="poly", degree=2, gamma=1, coef0=1, C=1e6).fit(X, y).dual_coef_   # |alpha| = 0.125