Il perceptron da zero: che cosa calcola un neurone

Un perceptron prende le misure, moltiplica ciascuna per un numero che controlla, le somma, aggiunge un altro numero e guarda il segno.

Scrivi le misure di un pezzo come un vettore $\mathbf{x} = (x_1, x_2)$ — larghezza e peso. Il perceptron conserva un vettore di pesi $\mathbf{w} = (w_1, w_2)$ e un bias $b$. Il suo punteggio è

e la sua risposta è il segno di quel punteggio: accetta se $s(\mathbf{x}) \geq 0$, altrimenti rifiuta.

Questo è l’intero modello. Tutto ciò che il perceptron saprà mai della fabbrica vive in tre numeri.

Vale la pena fermarsi sulla geometria, perché è l’immagine che continua a funzionare per i prossimi ventinove capitoli anche quando le equazioni smettono di stare su una riga. L’insieme dei punti in cui $s(\mathbf{x}) = 0$ — dove il perceptron è esattamente indeciso — è una retta nel piano. Da un lato il punteggio è positivo e tutto viene accettato; dall’altro è negativo e tutto viene rifiutato. Per un perceptron, imparare significa spostare quella retta.

Due fatti su quella retta seguono direttamente dall’algebra, ed entrambi conteranno più avanti:

• $\mathbf{w}$ le è perpendicolare. Il vettore dei pesi non sta lungo il confine: lo attraversa, puntando verso il lato accettato.
• $b$ la fa scorrere senza ruotarla. Senza un bias, la retta sarebbe costretta a passare per l’origine, che per una fabbrica che misura millimetri e grammi sarebbe un vincolo assurdo: significherebbe che un pezzo di larghezza zero e peso zero sta esattamente sul confine.

Il perceptron parte senza sapere nulla: $\mathbf{w} = (0, 0)$ e $b = 0$. Ogni punteggio è zero, quindi accetta tutto.

Ora mostragli un esempio alla volta. Etichetta i pezzi accettati con $y = +1$ e quelli rifiutati con $y = -1$. Per ogni esempio, fai una sola domanda: il segno è uscito giusto? Il modo compatto per scrivere questa domanda è controllare se $y \cdot s(\mathbf{x})$ è positivo: se etichetta e punteggio concordano nel segno, il loro prodotto è positivo; se non concordano, è negativo.

Se la risposta è sì, non cambiare nulla. Se la risposta è no, dai una spinta:

Questo è tutto l’algoritmo, e vale la pena capire perché sia la spinta giusta invece di memorizzarla. Supponi che un pezzo dovesse essere accettato ($y = +1$) e che il punteggio sia uscito negativo. Aggiungere $\mathbf{x}$ a $\mathbf{w}$ cambia il punteggio su quello stesso pezzo di

che è un numero positivo. Il punteggio sul pezzo appena classificato male va su, cioè nella direzione in cui doveva andare. La regola non è un’euristica indovinata da qualcuno: è il cambiamento più piccolo che migliora in modo dimostrabile il caso davanti a sé. Naturalmente può rompere un altro caso, ed è per questo che si fa un altro giro.

Nota che cosa manca. Non c’è nessuna derivata. Non è una svista, ed è la prima idea davvero importante del corso.

La cosa che vorresti derivare è l’errore: il conteggio dei pezzi classificati male. Ma quel conteggio è una scala: resta piatto a 4 mentre sposti un po’ la retta, poi scende a 3 nell’istante in cui la retta attraversa un punto. La sua derivata è zero quasi ovunque e non definita sui gradini. Il calcolo non ha presa. La regola del perceptron ci gira intorno non chiedendo affatto una pendenza: chiede solo «giusto o sbagliato?», e si muove in una direzione che può giustificare geometricamente.

È una soluzione autentica, ed è anche un vicolo cieco. Nel Capitolo 2 vorremo una loss che venga da qualche parte invece di essere scelta, nel Capitolo 4 un modello che dica quanto è sicuro, e nel Capitolo 5 qualcosa con più di un layer — e nessuno dei due è raggiungibile da una regola che conosce solo «sbagliato». Recuperare una pendenza utilizzabile è ciò che costringe i prossimi due capitoli. Ma il perceptron può fare qualcosa che nessuno dei suoi successori può fare: imparare senza calcolo.

Python puro, niente NumPy. Liste e un ciclo. NumPy arriva nel capitolo successivo, dove l’aritmetica smette di stare in un ciclo che avresti voglia di leggere; introdurlo ora nasconderebbe l’aritmetica dietro una libreria proprio nel momento in cui vuoi vederla.

def score(w, b, x):
    return w[0] * x[0] + w[1] * x[1] + b


def predict(w, b, x):
    return 1 if score(w, b, x) >= 0 else -1


def train(data, epochs=200):
    """Returns (w, b, epoch_it_converged) — or None for the epoch if it never did."""
    w, b = [0.0, 0.0], 0.0
    for epoch in range(epochs):
        mistakes = 0
        for x, y in data:
            if y * score(w, b, x) <= 0:          
                w[0] += y * x[0]                 
                w[1] += y * x[1]                 
                b += y                           
                mistakes += 1
        if mistakes == 0:
            return w, b, epoch + 1
    return w, b, None

Le quattro righe evidenziate sono l’algoritmo. Tutto il resto è contabilità.

Ed ecco il nastro, con otto pezzi misurati — quattro spediti e quattro tornati indietro:

BELT = [
    ((18.0, 47.0), +1), ((19.5, 52.0), +1), ((20.2, 49.0), +1), ((21.0, 55.0), +1),
    ((24.0, 61.0), -1), ((25.5, 66.0), -1), ((23.0, 70.0), -1), ((26.0, 58.0), -1),
]

w, b, epoch = train(BELT, epochs=200)
print(epoch, w, b)

Questi otto pezzi sono separabili da una retta: ogni pezzo accettato è sotto i 22 mm e ogni pezzo rifiutato è da 23 mm in su. Una barriera verticale a 22 millimetri risolve il problema. Quindi il perceptron dovrebbe trovarla.

Eseguilo:

None [-142.1, -13.0] 54.0

Duecento epoche, 454 correzioni, e non è convergente. I pesi sono grandi e con il segno sbagliato. Qualcosa non va — solo che non c’è niente che non va, e il motivo è la cosa più utile di questo capitolo.

Il perceptron ha una garanzia, dimostrata da Novikoff nel 1962.¹ Se i dati possono essere separati da una retta, l’algoritmo farà al massimo

correzioni prima di smettere di farne — dove $R$ è il raggio dei dati, la lunghezza del vettore di esempio più lungo, e $\gamma$ è il margine: la distanza dall’iperpiano separatore al punto più vicino nello spazio aumentato in cui il bias è una terza coordinata. Ecco perché centrare i dati lo cambia mentre la distanza in millimetri no.

La garanzia è incondizionata e non menziona epoche, learning rate o fortuna. Non menziona nemmeno il tempo, e questa omissione è il punto.

Inseriamo i nostri numeri. Misurati direttamente sugli otto pezzi, con il bias incorporato come feature costante:

Il teorema non è mai stato violato. Esegui la versione grezza abbastanza a lungo e converge davvero: all’epoca 11.976, dopo 29.870 correzioni, comodamente dentro il suo limite di 2.633.550. E quello scarto è esso stesso il punto: il teorema limita il caso peggiore, non quello tipico. Servivano semplicemente sessanta volte più epoche di quante chiunque sarebbe disposto ad aspettare.

La seconda riga contiene gli stessi otto pezzi, le stesse venti righe di codice, con tre righe aggiunte per sottrarre la larghezza media e il peso medio da ogni misura. Tutto qui. Questo è l’intero cambiamento. Sposta la nuvola di punti in modo che attraversi l’origine invece di fluttuare intorno a (22, 57), e l’effetto sul limite è un fattore quindicimila, perché migliorano entrambi i termini: $R$ scende da 74 a 13 perché i punti non sono più misurati da un’origine lontana, e $\gamma$ sale da 0,045 a 0,989 perché il margine viene misurato rispetto a un vettore di pesi che non deve più portarsi dietro un bias enorme per raggiungere i dati.

mean_w = sum(x[0] for x, _ in BELT) / len(BELT)   # 22.15
mean_g = sum(x[1] for x, _ in BELT) / len(BELT)   # 57.25
CENTRED = [(((x[0] - mean_w), (x[1] - mean_g)), y) for x, y in BELT]

w, b, epoch = train(CENTRED, epochs=200)
print(epoch, w, b)

2 [-4.15, -10.25] 1.0

Convergente in due epoche, dopo essersi corretto esattamente una volta.

C’è una vera lezione qui e non è «ricordati di normalizzare gli input», anche se dovresti. È che una garanzia sul fatto che un algoritmo finisca non ti dice nulla sul fatto che tu sarai ancora lì quando lo farà, e che la distanza tra le due cose di solito è geometria. Questa è la prima apparizione di uno schema che incontrerai di nuovo nel Capitolo 6 con l’inizializzazione, nel Capitolo 10 con gli schedule del learning rate, e nel Capitolo 13 con la quantizzazione: la matematica dice che la cosa è possibile, l’ingegneria decide se è pratica. Un corso che ti insegna solo il teorema ti consegna un modello che si addestra per tre giorni e dà la colpa a te.

Ora il fallimento che chiuse la prima era delle reti neurali, e sta in quattro righe.

Dimentica la fabbrica. Prendi due input che possono essere ciascuno 0 o 1, e chiedi che la risposta sia $+1$ quando esattamente uno dei due è 1:

Questo è XOR — or esclusivo. Prima di continuare, disegna i quattro punti su carta: tre angoli di un quadrato unitario e il quarto. Segna i due angoli diagonali $(0,1)$ e $(1,0)$ come accetta, e $(0,0)$ e $(1,1)$ come rifiuta. Ora disegna una sola retta con i due punti accettati da un lato e i due punti rifiutati dall’altro.

Non puoi. Non è che sia difficile, o che serva un algoritmo più furbo; è che quella retta non esiste. Tre righe di algebra mostrano perché. Se un perceptron classificasse correttamente tutte e quattro le righe, allora leggendo le quattro righe in ordine avremmo

Somma le due disuguaglianze centrali: $w_1 + w_2 + 2b \geq 0$, quindi $w_1 + w_2 \geq -2b$. L’ultima dice $w_1 + w_2 < -b$. Insieme: $-2b \leq w_1 + w_2 < -b$, che richiede $-2b < -b$, che richiede $b > 0$. E la prima disuguaglianza dice $b < 0$. Non esiste un tale $b$, quindi non esistono tali pesi. Nessun perceptron, con qualunque numero possibile, classifica XOR.

Eseguilo comunque, perché vedere un algoritmo fallire vale più che sentirsi dire che fallirà:

     100 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
   1,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4
 100,000 epochs -> converged=None  w=[0.0, 0.0] b=0.0  correct=2/4

Non diverge, e non si agita vicino a una risposta decente. Cicla: percorre un breve anello nello spazio dei pesi e torna esattamente dov’era partito, per sempre, azzeccando due casi su quattro — quello che otterresti tirando a indovinare. Centomila epoche e cento sono indistinguibili, perché l’algoritmo non sta facendo un progresso che una corsa più lunga potrebbe completare. Confrontalo con il nastro, che a 200 epoche sembrava bloccato e in realtà avanzava faticosamente verso una risposta reale. Da fuori, nei primi secondi, le due situazioni si assomigliano. Distinguerle, senza il teorema, è impossibile — e questo è un altro argomento a favore del conoscere il teorema.

Nel 1969 Marvin Minsky e Seymour Papert pubblicarono Perceptrons, uno studio matematico di lunghezza pari a un libro su cosa questo modello può e non può rappresentare.² XOR è il suo risultato più citato, e la citazione viene di solito usata come accusa: che il libro abbia ucciso la ricerca sulle reti neurali per quindici anni per rivalità o rancore.

La matematica del libro è corretta, ed è più interessante dell’esempio XOR. Minsky e Papert non erano interessati soprattutto a sapere se un singolo perceptron potesse fare XOR; erano interessati a ciò che succede quando ai perceptron vengono dati campi recettivi limitati — ogni unità vede solo una parte dell’input — e dimostrarono che certe proprietà globali di un’immagine, per esempio se una figura è connessa, non possono essere calcolate in quel modo indipendentemente da quante unità usi. È un risultato davvero profondo sulla località, e non ha nulla a che vedere con la storia popolare.

Anche la storia popolare sbaglia la storia. Minsky e Papert discutono esplicitamente i perceptron multi-layer e dicono che la questione della loro potenza è aperta: sospettavano che estendere la teoria sarebbe stato «sterile», il che è una previsione, non una prova, ed era sbagliata. Quello che mancava nel 1969 non era l’idea di impilare layer; era un modo per addestrare uno stack. La regola del perceptron non può farlo: deve sapere quanto ogni unità è sbagliata, e per un’unità sepolta nel mezzo non c’è un’etichetta con cui confrontarsi. Quel vuoto rimase aperto finché backpropagation non fu resa popolare nel 1986,³ e colmarlo è ciò che fa il Capitolo 5.

Quindi il riassunto onesto è questo. Il libro dimostrò un limite reale di un modello reale. Il crollo dei finanziamenti del campo negli anni Settanta ebbe molte cause, una delle quali era che le promesse fatte per i perceptron nei primi anni Sessanta erano state esagerate. E l’ostacolo tecnico era risolvibile, ma nessuno aveva ancora lo strumento.

Il perceptron ha sessantotto anni e tu ne hai appena scritto uno. Vale la pena essere precisi su quali parti siano ancora nella macchina con cui finirai questo corso, perché la risposta è: più di quanto immagini.

Il perceptron si è bloccato su due cose insieme, e si scopre che sono la stessa cosa.

Non può rappresentare XOR, perché una retta non basta. Risolvere il problema significa impilare layer: un primo layer che piega lo spazio, un secondo che traccia la retta nello spazio piegato. Questo è il Capitolo 5.

Ma non puoi addestrare uno stack con la regola del perceptron, perché conosce solo «sbagliato», e un’unità nel mezzo di una rete non ha una propria etichetta su cui sbagliarsi. Per addestrare uno stack devi sapere quanto è sbagliato, e in quale direzione, per ogni peso: ti serve una pendenza. E la funzione di errore del perceptron, la scala, non ne ha una.

Quindi prima dello stack deve esserci una funzione di loss con una derivata utilizzabile. E nemmeno una scelta perché è comoda da derivare: una che venga da qualche parte, che dica qualcosa di vero sui dati, e il cui gradient emerga da quel significato invece di essere ingegnerizzato al contrario per sembrare ordinato.

Questo è il Capitolo 2, e inizia ponendo una domanda a cui il perceptron non ha mai dovuto rispondere: non «questo pezzo è buono?», ma «quanto sono probabili queste letture, se questa è la verità?»

Vale la pena leggere insieme a questo capitolo anche l’articolo originale di Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), più leggibile di quanto suggerisca la sua reputazione; McCulloch e Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), l’articolo che per primo modellò un neurone come una soglia su una somma pesata; la sezione sul perceptron di A Course in Machine Learning di Hal Daumé III, che deriva lo stesso aggiornamento con un’enfasi diversa; e i capitoli 2 e 3 di Mathematics for Machine Learning di Deisenroth, Faisal e Ong per l’algebra lineare, se il riquadro sopra ti ha lasciato con la voglia di più.