Esercizio - Perceptron a mano su quattro punti

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

Testo. Il Perceptron con bias deve imparare la porta logica AND: ingressi $x\in\{(0,0),(0,1),(1,0),(1,1)\}$, uscita $+1$ solo per $(1,1)$ e $-1$ altrimenti.

1. Eseguire l'algoritmo del Perceptron ($w=0$; per ogni errore $y_i\,w^T\tilde x_i\le0$: $w\leftarrow w+y_i\tilde x_i$, con $\tilde x=(x_1,x_2,1)$), ordine degli esempi $(0,0),(0,1),(1,0),(1,1)$, e dire a che cosa converge.
2. Verificare la soluzione e calcolarne distanza dei punti e margine.
3. Confrontare il numero di errori con il limite del teorema di convergenza.
4. Cosa cambia con un ordine diverso degli esempi?

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 → (regola di aggiornamento, teorema di convergenza); prodotto scalare e distanza punto-piano 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 → 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 →.

1. Esecuzione

Vettori aumentati: $\tilde x_1=(0,0,1)$, $\tilde x_2=(0,1,1)$, $\tilde x_3=(1,0,1)$, $\tilde x_4=(1,1,1)$ con $y=(-1,-1,-1,+1)$. All'inizio $w=(0,0,0)$: tutti i prodotti $y_iw^T\tilde x_i$ sono $0$, cioè «errori» (la condizione è $\le0$).

Passata 1.

• $\tilde x_1$: $y\,w^T\tilde x=0\le0$: errore. $w\leftarrow w-\tilde x_1=(0,0,-1)$.
• $\tilde x_2$: $w^T\tilde x_2=-1$, $y=-1$, prodotto $+1>0$: corretto.
• $\tilde x_3$: analogamente prodotto $+1$: corretto.
• $\tilde x_4$: $w^T\tilde x_4=-1$ e $y=+1$: prodotto $-1\le0$: errore. $w\leftarrow w+\tilde x_4=(0,0,-1)+(1,1,1)=(1,1,0)$.

Passata 2 (parte da $w=(1,1,0)$).

• $\tilde x_1$: $w^T\tilde x_1=0$, prodotto $0$: errore. $w\leftarrow(1,1,0)-(0,0,1)=(1,1,-1)$.
• $\tilde x_2$: $w^T\tilde x_2=1+(-1)=0$, prodotto $0$: errore. $w\leftarrow(1,1,-1)-(0,1,1)=(1,0,-2)$.
• $\tilde x_3$: $w^T\tilde x_3=1-2=-1$, $y=-1$: prodotto $+1$: corretto.
• $\tilde x_4$: $w^T\tilde x_4=1+0-2=-1$, $y=+1$: prodotto $-1$: errore. $w\leftarrow(1,0,-2)+(1,1,1)=(2,1,-1)$.

L'algoritmo continua: passata 3 (3 errori, $w$ passa da $(2,1,-1)$ a $(2,0,-2)$, $(1,0,-3)$, $(2,1,-2)$), passata 4 (2 errori, $w=(2,2,-2)$), passata 5 ($w=(3,2,-2)$), passata 6 ($w=(3,2,-3)$), passata 7 ($w=(3,3,-3)$), passata 8 ($w=(3,2,-4)$), passata 9: nessun errore. Totale 18 aggiornamenti e $$w=(3,\,2,\,-4),\qquad h(x)=\operatorname{sign}(3x_1+2x_2-4).$$

2. Verifica, distanze e margine

$y_iw^T\tilde x_i$: $(0,0)$: $-(-4)=4$; $(0,1)$: $-(2-4)=2$; $(1,0)$: $-(3-4)=1$; $(1,1)$: $3+2-4=1$: tutti positivi: classificazione corretta. L'iperpiano è la retta $3x_1+2x_2=4$. Distanze dai punti $\frac{|w^Tx+b|}{\lVert w_{1:2}\rVert}$ con $\lVert(3,2)\rVert=\sqrt{13}=3{,}606$: $\frac4{3{,}606}=1{,}11$; $0{,}555$; $0{,}277$; $0{,}277$. Il margine (distanza minima) è $0{,}277$: i punti $(1,0)$ e $(1,1)$ sono quasi sulla retta; esistono rette separatrici con margine più grande (per esempio $x_1+x_2=1{,}5$, che dista $0{,}354$ da $(1,0)$, $(0,1)$ e $(1,1)$: margine $\frac{0{,}5}{\sqrt2}=0{,}354$), che il Perceptron non cerca: è il compito delle SVM (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 →).

3. Limite del teorema

Per i vettori aumentati $R=\max\lVert\tilde x_i\rVert=\sqrt3$ e per $w^\ast=w/\lVert w\rVert$ (norma del vettore aumentato $\sqrt{9+4+16}=\sqrt{29}=5{,}385$) i valori $y_iw^{\ast T}\tilde x_i$ sono $\frac{4,2,1,1}{5{,}385}$, quindi $\gamma=\frac1{5{,}385}=0{,}1857$. Il limite $\left(\frac R\gamma\right)^2=\frac{3}{0{,}0345}=87$: l'algoritmo ne ha fatti $18\le87$. Il limite è largo ma vale per qualunque ordine; e il margine migliore possibile (rette come $x_1+x_2=1{,}5$) darebbe un limite più piccolo.

4. Ordine degli esempi

La soluzione e il numero di errori dipendono dall'ordine: scorrendo gli esempi nell'ordine inverso $(1,1),(1,0),(0,1),(0,0)$ si ottiene $w=(2,3,-4)$ dopo $22$ aggiornamenti (la retta $2x_1+3x_2=4$). Tutte le soluzioni separano i dati, ma sono diverse: il Perceptron trova un iperpiano separatore, non il migliore.

Verifica

import numpy as np
X = np.array([[0,0],[0,1],[1,0],[1,1.]]); y = np.array([-1,-1,-1,1]); Xa = np.c_[X, np.ones(4)]
w = np.zeros(3); n_err = 0
while True:
    err = 0
    for xi, yi in zip(Xa, y):
        if yi * (w @ xi) <= 0: w += yi * xi; err += 1; n_err += 1
    if err == 0: break
print(w, n_err)                  # [ 3.  2. -4.]  18