Halfspace e Perceptron

I classificatori più semplici sono quelli lineari: separano le classi con un iperpiano. Il modello geometrico è l'halfspace; l'algoritmo storico che lo impara è il Perceptron, che è anche il «mattone» delle reti neurali (Reti neurali - neuroni e funzioni di attivazioneUn neurone calcola $\hat y=g(w_0+w^\top x)$: somma pesata degli ingressi più bias, poi una funzione di attivazione $g$ non lineare (Perceptron a soglia, sigmoide, tanh, ReLU e varianti). Senza non linearità ogni rete è equivalente a un solo modello lineare. Una rete feed-forward impila strati di neuroni: $a^{(k)}=g(W^{(k)}a^{(k-1)}+b^{(k)})$; con uno strato nascosto è già un approssimatore universale, ma più strati rappresentano funzioni complesse con molti meno neuroni e imparano feature gerarchiche (bordi, parti, oggetti). Lo strato di uscita e la loss si scelgono dal compito: lineare+MSE (regressione), sigmoide+cross-entropy binaria, softmax+cross-entropy (multiclasse). Il numero di parametri di uno strato denso è $n_{in}n_{out}+n_{out}$. Nel lab (Keras, MNIST) una rete 784-512-10 ha 407 050 parametri e supera il 98% di accuratezza.Reti neurali - neuroni e funzioni di attivazione →). La nota si appoggia sulla geometria dell'iperpiano e sul prodotto scalare (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 →, 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 →, 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 →). Gli esercizi sono Esercizio - Perceptron a mano su quattro punti e Esercizio - Halfspace, distanza dal piano e problema XOR. Il Perceptron non ha una lezione dedicata nel corso di Automazione (compare solo come neurone nella lezione 23 sul deep learning): la nota è scritta dal programma ufficiale e dalle conoscenze standard (vedi _fonti).

Il modello halfspace

Si lavora con una classificazione binaria con etichette $y\in\{-1,+1\}$ (invece di $\{0,1\}$: rende più comode le formule) e ingressi $x\in\mathbb R^p$.

Definizione (halfspace). La classe di funzioni $$h_{w,b}(x)=\operatorname{sign}\big(w^Tx+b\big),\qquad w\in\mathbb R^p,\ b\in\mathbb R,$$ con $\operatorname{sign}(z)=+1$ per $z>0$ e $-1$ per $z<0$ (per $z=0$ si sceglie una convenzione, per esempio $+1$). Il vettore dei pesi $w$ e il bias $b$ sono i parametri.

Esempio. In $\mathbb R^2$ con $w=(1,1)$ e $b=-3$: $h(x)=\operatorname{sign}(x_1+x_2-3)$. Il punto $(2,3)$ dà $2+3-3=2>0\Rightarrow+1$; il punto $(0,1)$ dà $-2<0\Rightarrow-1$.

Geometria. L'insieme $\{x:w^Tx+b=0\}$ è un iperpiano (una retta se $p=2$, un piano se $p=3$): divide lo spazio in due semispazi (halfspace) in cui il segno è $+1$ e $-1$. Il vettore $w$ è perpendicolare al piano: se $x_1,x_2$ stanno sul piano, $w^T(x_1-x_2)=-b+b=0$. Un punto $x$ è dalla parte di $w$ se $w^Tx+b>0$. La distanza di $x$ dal piano è $$\operatorname{dist}(x)=\frac{|w^Tx+b|}{\lVert w\rVert}.$$ (Dimostrazione: se $x_0$ è la proiezione ortogonale di $x$ sul piano, $x=x_0+t\,w/\lVert w\rVert$ con $t$ la distanza con segno; allora $w^Tx+b=w^Tx_0+b+t\,\lVert w\rVert=t\,\lVert w\rVert$.) Nell'esempio, il punto $(2,3)$ dista $2/\sqrt2=1{,}414$ dalla retta $x_1+x_2=3$.

La dimostrazione, passaggio per passaggio.

1. $w$ è perpendicolare al piano. Due punti qualunque $x_1,x_2$ del piano soddisfano $w^Tx_1+b=0$ e $w^Tx_2+b=0$; sottraendo, $w^T(x_1-x_2)=0$. Il vettore $x_1-x_2$ è una direzione contenuta nel piano e il suo prodotto scalare con $w$ è nullo, quindi $w$ è ortogonale a ogni direzione del piano (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 →: $u\cdot v=0$ equivale a $u\perp v$).
2. La distanza è lungo la normale. Il punto del piano più vicino a $x$ è la sua proiezione ortogonale $x_0$ (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 →), e il segmento $x-x_0$ è perpendicolare al piano, cioè parallelo a $w$: $x=x_0+t\,\frac{w}{\lVert w\rVert}$, dove $\frac w{\lVert w\rVert}$ è il vettore unitario nella direzione di $w$ e $|t|$ la distanza cercata.
3. Si calcola il valore della funzione in $x$. $w^Tx+b=\underbrace{w^Tx_0+b}_{=0}+t\,\frac{w^Tw}{\lVert w\rVert}=t\,\lVert w\rVert$, perché $w^Tw=\lVert w\rVert^2$. Quindi $t=\frac{w^Tx+b}{\lVert w\rVert}$ e la distanza è $|t|$. Il segno di $t$ dice da che parte del piano sta il punto (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 →). Controllo sull'esempio: $w=(1,1)$, $\lVert w\rVert=\sqrt{1+1}=\sqrt2$. Punto $(2,3)$: $t=\frac{2+3-3}{\sqrt2}=1{,}414$ (lato positivo); punto $(0,1)$: $t=\frac{0+1-3}{\sqrt2}=-1{,}414$ (lato negativo, dista uguale); punto $(3,1)$: $t=\frac{1}{\sqrt2}=0{,}707$; punto $(1,-1)$: $t=\frac{-3}{\sqrt2}=-2{,}121$. Il margine di questo piano sui quattro punti dell'esempio del Perceptron è quindi $0{,}707$. Moltiplicare $(w,b)$ per una costante $c>0$ non cambia né il piano né le classificazioni né la distanza (il fattore si semplifica nel rapporto), per questo la distanza si divide sempre per $\lVert w\rVert$.

Bias incorporato. Si aggiunge ai dati una componente costante: $\tilde x=(x,1)$ e $\tilde w=(w,b)$. Allora $w^Tx+b=\tilde w^T\tilde x$: l'iperpiano passa per l'origine nello spazio aumentato e si può scrivere $h(x)=\operatorname{sign}(\tilde w^T\tilde x)$ (è la colonna di uni della 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 →). Nel seguito si scrive $w^Tx$ intendendo $\tilde w^T\tilde x$.

Definizione (separabilità lineare). Un insieme di esempi $(x_i,y_i)$ è linearmente separabile se esistono $w,b$ con $y_i(w^Tx_i+b)>0$ per ogni $i$, cioè se un halfspace li classifica tutti correttamente. Il margine di un tale piano è la distanza minima dei punti dal piano.

La condizione $y_i(w^Tx_i)>0$ è comoda: è positivo quando il segno di $w^Tx_i$ coincide con $y_i$ (previsione corretta), negativo o nullo se la previsione è sbagliata.

Il Perceptron

Il Perceptron (Rosenblatt, 1958) è il modello di un neurone: calcola la combinazione lineare $w^Tx+b$ degli ingressi e la passa a una funzione di attivazione a gradino: uscita $+1$ se la somma supera la soglia, $-1$ (o $0$) altrimenti. È quindi esattamente un halfspace. Sostituendo il gradino con la sigmoide si ha 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 →); con altre attivazioni e molti neuroni in strati, una rete neurale (Reti neurali - neuroni e funzioni di attivazioneUn neurone calcola $\hat y=g(w_0+w^\top x)$: somma pesata degli ingressi più bias, poi una funzione di attivazione $g$ non lineare (Perceptron a soglia, sigmoide, tanh, ReLU e varianti). Senza non linearità ogni rete è equivalente a un solo modello lineare. Una rete feed-forward impila strati di neuroni: $a^{(k)}=g(W^{(k)}a^{(k-1)}+b^{(k)})$; con uno strato nascosto è già un approssimatore universale, ma più strati rappresentano funzioni complesse con molti meno neuroni e imparano feature gerarchiche (bordi, parti, oggetti). Lo strato di uscita e la loss si scelgono dal compito: lineare+MSE (regressione), sigmoide+cross-entropy binaria, softmax+cross-entropy (multiclasse). Il numero di parametri di uno strato denso è $n_{in}n_{out}+n_{out}$. Nel lab (Keras, MNIST) una rete 784-512-10 ha 407 050 parametri e supera il 98% di accuratezza.Reti neurali - neuroni e funzioni di attivazione →).

L'algoritmo di apprendimento

Definizione (algoritmo del Perceptron). Dati $(x_i,y_i)$ con $y_i\in\{-1,+1\}$ e $x_i$ aumentati con la costante $1$:

1. si inizializza $w=0$;
2. si scorrono gli esempi; per un esempio sbagliato, cioè con $y_i\,w^Tx_i\le0$, si aggiorna $$w\leftarrow w+y_i\,x_i;$$
3. si ripete finché in un'intera passata non ci sono errori.

Perché l'aggiornamento ha senso. Dopo l'aggiornamento la quantità $y_i\,w^Tx_i$ per lo stesso esempio diventa $y_i(w+y_ix_i)^Tx_i=y_i\,w^Tx_i+y_i^2\lVert x_i\rVert^2=y_i\,w^Tx_i+\lVert x_i\rVert^2$ (perché $y_i^2=1$): aumenta di $\lVert x_i\rVert^2>0$, quindi l'esempio viene «avvicinato» alla classificazione corretta. Geometricamente, per un positivo $w$ si sposta verso $x_i$, per un negativo si allontana da $x_i$. L'aggiornamento può rendere sbagliati altri esempi: per questo si ripassa fino a che non ci sono errori.

Esempio completo (verificato). Dati $x_0=(2,3)$ con $y=+1$, $x_1=(3,1)$ con $+1$, $x_2=(0,1)$ con $-1$, $x_3=(1,-1)$ con $-1$; con la costante $\tilde x=(x_1,x_2,1)$ e $w=(0,0,0)$:

Totale: $5$ errori e un classificatore che separa tutti i punti: $h(x)=\operatorname{sign}(x_1+x_2-3)$.

Come si muove la retta. Ogni riga della tabella dà un vettore $w=(w_1,w_2,w_0)$ e quindi la retta $w_1x_1+w_2x_2+w_0=0$, cioè $w_1x_1+w_2x_2=-w_0$. I cinque aggiornamenti producono: (1) $w=(2,3,1)$: retta $2x_1+3x_2=-1$; (2) $w=(2,2,0)$: $x_1+x_2=0$; (3) $w=(1,3,-1)$: $x_1+3x_2=1$; (4) $w=(1,2,-2)$: $x_1+2x_2=2$; (5) $w=(1,1,-3)$: $x_1+x_2=3$. Il grafico le mostra in sequenza: dopo ogni errore la retta ruota e si sposta nella direzione che corregge quel punto, finché la quinta separa i quattro punti.

Il teorema di convergenza

Se i dati sono linearmente separabili il Perceptron si ferma sempre, dopo un numero finito di errori che dipende dal margine.

Teorema (convergenza del Perceptron, Novikoff). Siano $\lVert x_i\rVert\le R$ per ogni $i$, e sia $w^\ast$ con $\lVert w^\ast\rVert=1$ tale che $y_i\,w^{\ast T}x_i\ge\gamma>0$ per ogni $i$ (esiste un iperpiano con margine $\gamma$). Allora il Perceptron commette al più $(R/\gamma)^2$ errori (aggiornamenti) prima di classificare correttamente tutti gli esempi.

Dimostrazione. Sia $w_t$ il vettore dopo $t$ aggiornamenti ($w_0=0$).

L'idea: il vettore $w_t$ deve tenersi sempre più allineato a $w^\ast$ (passo 1) senza però crescere troppo in lunghezza (passo 2); poiché un allineamento non può superare il 100%, il numero di aggiornamenti è limitato.

1. Il prodotto scalare con $w^\ast$ cresce linearmente. Un aggiornamento con l'esempio $(x,y)$ dà $w_{t+1}\cdot w^\ast=(w_t+yx)\cdot w^\ast=w_t\cdot w^\ast+y\,(x\cdot w^\ast)$ (linearità del prodotto scalare) $\ge w_t\cdot w^\ast+\gamma$, perché per ipotesi $y\,(x\cdot w^\ast)\ge\gamma$. Per induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →: base $w_0\cdot w^\ast=0\ge0\cdot\gamma$; passo, se $w_t\cdot w^\ast\ge t\gamma$ allora $w_{t+1}\cdot w^\ast\ge t\gamma+\gamma=(t+1)\gamma$. Quindi $w_t\cdot w^\ast\ge t\gamma$.
2. La norma cresce al più come $\sqrt t$. Si sviluppa il quadrato della norma (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 →: $\lVert a+b\rVert^2=\lVert a\rVert^2+2a\cdot b+\lVert b\rVert^2$): $\lVert w_{t+1}\rVert^2=\lVert w_t+yx\rVert^2=\lVert w_t\rVert^2+2y\,w_t\cdot x+y^2\lVert x\rVert^2$, con $y^2=1$. Poiché si aggiorna solo se c'è un errore, $y\,w_t\cdot x\le0$ (il termine centrale è non positivo e si può togliere), e $\lVert x\rVert\le R$, quindi $\lVert w_{t+1}\rVert^2\le\lVert w_t\rVert^2+R^2$. Per induzione, con $\lVert w_0\rVert^2=0$: $\lVert w_t\rVert^2\le tR^2$, cioè $\lVert w_t\rVert\le\sqrt t\,R$.
3. Si combinano con la disuguaglianza di Cauchy-Schwarz: $w_t\cdot w^\ast=\lVert w_t\rVert\,\lVert w^\ast\rVert\cos\theta\le\lVert w_t\rVert\,\lVert w^\ast\rVert=\lVert w_t\rVert$, perché $\cos\theta\le1$ e $\lVert w^\ast\rVert=1$. Allora $t\gamma\le w_t\cdot w^\ast\le\lVert w_t\rVert\le\sqrt t\,R$. Dividendo per $\sqrt t\,\gamma$ (positivo): $\sqrt t\le R/\gamma$, elevando al quadrato $t\le(R/\gamma)^2$. ∎

Il numero $t$ di aggiornamenti non può superare $(R/\gamma)^2$: dopo tanti aggiornamenti non possono esserci altri errori, e quindi l'algoritmo si ferma. Il ruolo di $\gamma$: un margine piccolo significa che i punti sono vicini al piano, quindi $w_t$ deve diventare molto più lungo e allineato per superare tutti.

Esempio. Nell'esempio precedente $w^\ast=(1,1,-3)/\sqrt{11}$ ha margini $y_iw^{\ast T}\tilde x_i=[2,1,2,3]/\sqrt{11}$, quindi $\gamma=1/\sqrt{11}=0{,}302$; il vettore aumentato più lungo è $(2,3,1)$ con $R=\sqrt{14}=3{,}74$. Il teorema garantisce $t\le R^2/\gamma^2=14\cdot11=154$ errori; ne sono occorsi $5$ (il limite è largo ma vale per ogni ordine degli esempi).

Il teorema dice anche che più è piccolo il margine, più errori servono; non dipende dalla dimensione $p$ né dal numero di esempi $n$.

Limiti

• Solo problemi separabili. Se i dati non sono linearmente separabili l'algoritmo non converge (continua ad aggiornare). Esempio classico, lo XOR: $(0,0)\to-1$, $(1,1)\to-1$, $(0,1)\to+1$, $(1,0)\to+1$. Se esistessero $w,b$: $b<0$ (primo punto); $w_1+w_2+b<0$ (secondo); $w_2+b>0$ e $w_1+b>0$ (gli altri due). Sommando le ultime due, $w_1+w_2+2b>0$; ma dalle prime due si ha $w_1+w_2+2b=(w_1+w_2+b)+b<0$: contraddizione. Nessun halfspace risolve lo XOR; serve una rete con più strati.

Geometricamente: un halfspace separa i punti con una retta, quindi le due classi dovrebbero avere involucri convessi disgiunti; qui i segmenti che uniscono le coppie della stessa classe (le due diagonali del quadrato) si incontrano nel centro $(\frac12,\frac12)$, e un semispazio, che è convesso, non può contenere i due estremi di una diagonale senza contenere anche il centro.

• La soluzione non è unica e dipende dall'ordine degli esempi: tra i tanti iperpiani separatori il Perceptron trova il primo, non il migliore.
• Nessun criterio di margine ottimale. Le SVM cercano il piano di margine massimo (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 →) e con i metodi kernel gestiscono anche il caso non separabile.
• Dati rumorosi. Con classi che si sovrappongono si preferisce la regressione logistica (minimizza una perdita continua) o varianti come il pocket Perceptron (tiene il miglior $w$ visto).

Codice

import numpy as np
def perceptron(X, y, max_epochs=100):
    Xa = np.hstack([X, np.ones((len(X), 1))])        # bias incorporato
    w = np.zeros(Xa.shape[1])
    for _ in range(max_epochs):
        errors = 0
        for xi, yi in zip(Xa, y):
            if yi * (w @ xi) <= 0:                    # esempio sbagliato (o sul piano)
                w += yi * xi; errors += 1
        if errors == 0: break                         # tutti corretti: stop
    return w                                          # w = (pesi, bias)

predict = lambda w, X: np.sign(np.hstack([X, np.ones((len(X), 1))]) @ w)

Con $y\in\{-1,+1\}$: il confronto <= 0 include il caso $w^Tx=0$ (all'inizio, con $w=0$, tutti gli esempi sono «sul piano» e il primo aggiornamento avviene subito).

Errori tipici

• Usare le etichette $\{0,1\}$ nella regola $w\leftarrow w+y_ix_i$: servono $\pm1$ (con $0/1$ un negativo non allontanerebbe $w$).
• Dimenticare il bias (o la colonna di uni): il piano è costretto a passare per l'origine.
• Confondere $w$ (normale al piano) con un punto del piano.
• Aspettarsi la convergenza con dati non separabili.
• Considerare il Perceptron e la regressione logistica equivalenti: cambiano l'uscita e la regola di apprendimento (errori contro gradiente di una perdita).