Esercizio - Halfspace, distanza dal piano e problema XOR

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

Testo.

1. Nello spazio $\mathbb R^3$ si consideri l'halfspace $h(x)=\operatorname{sign}(w^Tx+b)$ con $w=(2,-1,2)$ e $b=-4$. Classificare i punti $P_1=(1,1,3)$, $P_2=(0,0,0)$, $P_3=(2,0,0)$, calcolarne la distanza dal piano e la proiezione di $P_1$ sul piano.
2. Mostrare che nessun halfspace in $\mathbb R^2$ classifica correttamente lo XOR: $(0,0)\to-1$, $(1,1)\to-1$, $(0,1)\to+1$, $(1,0)\to+1$.
3. Mostrare che aggiungendo la feature $x_1x_2$ lo XOR diventa linearmente separabile.

Teoria usata: 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 → (halfspace, distanza dal piano, separabilità); piani e distanze in Spazi affini, rette e pianiNello spazio affine Aⁿ si distinguono punti e vettori (Q − P è il vettore da P a Q). Un sottospazio affine è L = P + W, un punto più un sottospazio vettoriale (lo spazio direttore): si descrive con equazioni parametriche X = P + t₁w₁ + … oppure cartesiane AX = B. Rette e piani di A³, passaggio tra i due tipi di equazioni, posizione reciproca: incidenti, paralleli, sghembi.Spazi affini, rette e piani → e Distanze e angoli nello spazio affineLa distanza tra due punti è la norma del vettore che li unisce. La distanza di un punto Q da un sottospazio affine L si misura dal piede della perpendicolare H, l'unico punto di L con Q − H ortogonale allo spazio direttore. Per un iperpiano a·x = b vale la formula |a·Q − b|/‖a‖. Rette sghembe: perpendicolare comune. Angoli tra rette e piani dai vettori direttori e normali.Distanze e angoli nello spazio affine →; prodotto scalare e norma in 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 →; proiezioni in Complemento ortogonale e proiezioni ortogonaliL'ortogonale U⊥ di un sottospazio è un sottospazio di dimensione n − dim U, e R^n = U ⊕ U⊥; ogni vettore si scompone in proiezione su U più componente ortogonale; la proiezione è il punto di U più vicino e si calcola con un sistema o con la matrice di proiezione A(AᵀA)⁻¹Aᵀ.Complemento ortogonale e proiezioni ortogonali →.

1. Classificazione e distanza

$\lVert w\rVert=\sqrt{4+1+4}=3$. Per ciascun punto si calcola $z=w^TP+b$:

• $P_1=(1,1,3)$: $z=2\cdot1-1\cdot1+2\cdot3-4=2-1+6-4=3>0\Rightarrow h=+1$; distanza $\frac{|z|}{\lVert w\rVert}=\frac33=1$;
• $P_2=(0,0,0)$: $z=-4<0\Rightarrow h=-1$; distanza $\frac43=1{,}33$ (dal lato negativo);
• $P_3=(2,0,0)$: $z=4-4=0$: il punto è sul piano (distanza $0$; il segno è una convenzione, per esempio $+1$).

Proiezione di $P_1$. Il piano ha normale $w$, quindi la proiezione ortogonale è $x_0=P_1-\dfrac{w^TP_1+b}{\lVert w\rVert^2}\,w=(1,1,3)-\frac39(2,-1,2)=\big(1-\tfrac23,\ 1+\tfrac13,\ 3-\tfrac23\big)=\big(\tfrac13,\tfrac43,\tfrac73\big)$. Verifica: $w^Tx_0+b=\frac23-\frac43+\frac{14}3-4=\frac{12}3-4=0$ ✓, e $\lVert P_1-x_0\rVert=\lVert\frac13(2,-1,2)\rVert=\frac13\cdot3=1$ ✓ (la distanza).

2. Lo XOR non è separabile

Si cercano $w=(w_1,w_2)$ e $b$ con $\operatorname{sign}(w_1x_1+w_2x_2+b)=y$ per i quattro punti, cioè (con disuguaglianze strette):

Sommando le ultime due: $w_1+w_2+2b>0$. Ma dalle prime due: $w_1+w_2+2b=(w_1+w_2+b)+b<0+0=0$ (somma di due quantità negative). Contraddizione: nessun $w,b$ funziona. Geometricamente: un semispazio è convesso, quindi se contiene i due estremi di un segmento contiene tutto il segmento. I punti positivi $(0,1)$ e $(1,0)$ sono agli estremi di un segmento e i negativi $(0,0)$ e $(1,1)$ agli estremi di un altro; i due segmenti si incrociano in $(0{,}5;\,0{,}5)$, che dovrebbe quindi stare sia nel semispazio positivo sia in quello negativo: impossibile. Il Perceptron su questi dati non converge mai (a ogni passata ci sono errori). Serve una rete con più strati.

3. Con la feature $x_1x_2$

Si aggiunge $x_3=x_1x_2$ ($\phi(x)=(x_1,x_2,x_1x_2)$). Si prendano $w=(1,1,-2)$ e $b=-0{,}5$:

• $(0,0)$: $0+0-0-0{,}5=-0{,}5<0\Rightarrow-1$ ✓;
• $(1,1)$: $1+1-2\cdot1-0{,}5=-0{,}5<0\Rightarrow-1$ ✓;
• $(0,1)$: $0+1-0-0{,}5=+0{,}5>0\Rightarrow+1$ ✓;
• $(1,0)$: $+0{,}5>0\Rightarrow+1$ ✓.

Nello spazio aumentato i dati sono separabili con margine $\frac{0{,}5}{\lVert(1,1,-2)\rVert}=\frac{0{,}5}{\sqrt6}=0{,}204$. È l'idea alla base dei metodi kernel e delle reti: portare i dati in uno spazio di feature in cui un halfspace funziona (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 →, 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 → per l'espansione di base polinomiale). Nel piano originale la regione positiva è $x_1+x_2-2x_1x_2>0{,}5$, una regione non lineare.

Verifica

import numpy as np
w, b = np.array([2., -1., 2.]), -4.0
for P in ([1,1,3], [0,0,0], [2,0,0]):
    P = np.array(P, float); z = w @ P + b; print(P, z, abs(z) / np.linalg.norm(w))   # z = 3, -4, 0
x0 = np.array([1,1,3.]) - (3 / 9) * w; print(x0, w @ x0 + b)                         # [0.333 1.333 2.333]  0.0
phi = lambda x: np.array([x[0], x[1], x[0] * x[1]]); wv = np.array([1., 1., -2.])
print([np.sign(wv @ phi(x) - 0.5) for x in ([0,0], [1,1], [0,1], [1,0])])            # [-1, -1, 1, 1]