El perceptró des de zero: què calcula una neurona

Un perceptró pren les mesures, multiplica cadascuna per un número que controla, les suma, hi afegeix un número més, i mira el signe.

Escriu les mesures d'una peça com un vector $\mathbf{x} = (x_1, x_2)$ — amplada i pes. El perceptró manté un vector de pesos $\mathbf{w} = (w_1, w_2)$ i un biaix $b$. La seva puntuació és

i la seva resposta és el signe d'aquesta puntuació: accepta si $s(\mathbf{x}) \geq 0$, rebutja altrament.

Aquest és tot el model. Tot el que el perceptró arribarà a saber mai sobre la fàbrica viu en tres números.

Val la pena aturar-se en la geometria, perquè és la imatge que continua funcionant durant els vint-i-nou capítols següents fins i tot quan les equacions ja no caben en una línia. El conjunt de punts on $s(\mathbf{x}) = 0$ — on el perceptró està exactament indecís — és una línia recta al pla. En un costat la puntuació és positiva i tot s'accepta; a l'altre és negativa i tot es rebutja. Aprendre, per a un perceptró, vol dir moure aquesta línia.

Dos fets sobre aquesta línia surten directament de l'àlgebra, i tots dos importen més endavant:

• $\mathbf{w}$ hi és perpendicular. El vector de pesos no va al llarg de la frontera, sinó que la travessa, apuntant cap al costat acceptat.
• $b$ la desplaça sense girar-la. Sense un biaix, la línia estaria obligada a passar per l'origen, cosa que per a una fàbrica que mesura mil·límetres i grams seria una restricció absurda: voldria dir que una peça d'amplada zero i pes zero queda exactament sobre la tanca.

El perceptró comença sense saber res: $\mathbf{w} = (0, 0)$ i $b = 0$. Totes les puntuacions són zero, així que ho accepta tot.

Ara mostra-li un exemple cada vegada. Etiqueta les peces acceptades com a $y = +1$ i les rebutjades com a $y = -1$. Per a cada exemple, fes una pregunta: el signe ha sortit bé? La manera compacta d'escriure aquesta pregunta és comprovar si $y \cdot s(\mathbf{x})$ és positiu: si l'etiqueta i la puntuació coincideixen en signe, el seu producte és positiu, i si discrepen és negatiu.

Si la resposta és sí, no canviïs res. Si la resposta és no, empeny una mica:

Aquest és tot l'algorisme, i val la pena entendre per què és l'empenta correcta en lloc de memoritzar-la. Suposa que una peça hauria d'haver estat acceptada ($y = +1$) i la puntuació ha sortit negativa. Afegir $\mathbf{x}$ a $\mathbf{w}$ canvia la puntuació sobre aquesta mateixa peça en

que és un número positiu. La puntuació de la peça que acaba d'equivocar puja, que és la direcció en què havia d'anar. La regla no és una heurística que algú hagi endevinat; és el canvi més petit que millora demostrablement el cas que té davant. És clar que pot trencar un altre cas, i per això hi tornes a passar.

Fixa't què hi falta. No hi ha cap derivada enlloc. No és un descuit, i és la primera idea realment important del curs.

Allò que voldries diferenciar és l'error: el recompte de peces mal classificades. Però aquest recompte és una escala: es queda pla a 4 mentre empenys la línia, i després cau a 3 a l'instant que la línia travessa un punt. La seva derivada és zero gairebé a tot arreu i indefinida als esglaons. El càlcul no té on agafar-se. La regla del perceptró ho esquiva no demanant cap pendent: només pregunta "bé o malament?", i es mou en una direcció que pot justificar geomètricament.

Això és una solució de debò, i també és un carreró sense sortida. Al capítol 2 voldrem una pèrdua que vingui d'algun lloc en lloc de ser triada, al capítol 4 un model que informi de com de segur n'està, i al capítol 5 alguna cosa amb més d'una capa — i cap d'aquestes coses és accessible des d'una regla que només sap "malament". Recuperar un pendent usable és el que força els dos capítols següents. Però el perceptró pot fer una cosa que cap dels seus successors pot fer: aprendre sense càlcul en absolut.

Python pur, sense NumPy. Llistes i un bucle. NumPy arriba al capítol següent, quan l'aritmètica deixa de cabre en un bucle que voldries llegir; introduir-lo ara amagaria l'aritmètica darrere d'una biblioteca just en el moment que la vols veure.

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

Les quatre línies ressaltades són l'algorisme. Tota la resta és comptabilitat.

I la cinta, amb vuit peces mesurades en sortir-ne: quatre que es van enviar i quatre que van tornar:

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)

Aquestes vuit peces són separables per una línia recta: totes les peces acceptades fan menys de 22 mm i totes les rebutjades fan 23 mm o més. Una tanca vertical a 22 mil·límetres fa la feina. Així que el perceptró hauria de trobar-la.

Executa'l:

None [-142.1, -13.0] 54.0

Dues-centes èpoques, 454 correccions, i no ha convergit. Els pesos són grans i tenen el signe equivocat. Alguna cosa falla — tret que no falla res, i la raó és la cosa més útil d'aquest capítol.

El perceptró té una garantia, demostrada per Novikoff el 1962.¹ Si les dades es poden separar per una línia, l'algorisme fa com a màxim

correccions abans de deixar-ne de fer — on $R$ és el radi de les dades, la longitud del vector d'exemple més llarg, i $\gamma$ és el marge: la distància de l'hiperplà separador al punt més proper en l'espai augmentat on el biaix és una tercera coordenada. Per això centrar les dades ho canvia mentre que la distància en mil·límetres no.

La garantia és incondicional i no esmenta èpoques, taxes d'aprenentatge ni sort. Tampoc no esmenta el temps, i aquesta omissió és el punt.

Posem-hi els nostres números. Mesurats directament de les vuit peces, amb el biaix incorporat com una característica constant:

El teorema no s'ha violat mai. Executa la versió en brut prou temps i sí que convergeix: a l'època 11.976, després de 29.870 correccions, còmodament dins del límit de 2.633.550, i aquesta diferència és precisament el punt: el teorema limita el pitjor cas, no el cas típic. Simplement necessitava seixanta vegades més èpoques de les que ningú s'asseuria a esperar.

La segona fila són les mateixes vuit peces, les mateixes vint línies de codi, amb tres línies afegides per restar l'amplada mitjana i el pes mitjà de cada mesura. Això és tot. Aquest és tot el canvi. Mou el núvol de punts perquè travessi l'origen en lloc de surar a (22, 57), i l'efecte sobre el límit és d'un factor de quinze mil, perquè tots dos termes milloren alhora: $R$ baixa de 74 a 13 perquè els punts ja no es mesuren des d'un origen llunyà, i $\gamma$ puja de 0,045 a 0,989 perquè el marge es mesura contra un vector de pesos que ja no ha de carregar un biaix enorme per arribar a les dades.

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

Ha convergit en dues èpoques, després d'haver-se corregit exactament una vegada.

Aquí hi ha una lliçó real i no és "recorda normalitzar les entrades", tot i que ho hauries de fer. És que una garantia sobre si un algorisme acaba no et diu res sobre si hi seràs quan ho faci, i que l'escletxa entre totes dues coses sol ser geometria. Aquesta és la primera aparició d'un patró que tornaràs a trobar al capítol 6 amb la inicialització, al capítol 10 amb els calendaris de taxa d'aprenentatge, i al capítol 13 amb la quantització: les matemàtiques diuen que la cosa és possible, i l'enginyeria decideix si és pràctica. Un curs que només t'ensenya el teorema et dona un model que entrena durant tres dies i et culpa a tu.

Ara el fracàs que va posar fi a la primera era de les xarxes neuronals, i cap en quatre files.

Oblida la fàbrica. Pren dues entrades que cadascuna pot ser 0 o 1, i demana que la resposta sigui $+1$ quan exactament una d'elles és 1:

Això és XOR — o exclusiu. Abans de continuar llegint, dibuixa els quatre punts en un paper: tres cantonades d'un quadrat unitari i la quarta. Marca les dues cantonades diagonals $(0,1)$ i $(1,0)$ com a acceptades, i $(0,0)$ i $(1,1)$ com a rebutjades. Ara dibuixa una sola línia recta amb els dos punts acceptats a un costat i els dos rebutjats a l'altre.

No pots. No és que sigui difícil, ni que necessitis un algorisme més llest; és que la línia no existeix. Tres línies d'àlgebra mostren per què. Si un perceptró encertés les quatre, llegint les quatre files en ordre obtindríem

Suma les dues desigualtats del mig: $w_1 + w_2 + 2b \geq 0$, així que $w_1 + w_2 \geq -2b$. L'última diu $w_1 + w_2 < -b$. Juntes: $-2b \leq w_1 + w_2 < -b$, cosa que requereix $-2b < -b$, cosa que requereix $b > 0$. I la primera desigualtat diu $b < 0$. No hi ha cap $b$ així, de manera que no hi ha aquests pesos. Cap perceptró, amb cap número possible, classifica XOR.

Executa'l igualment, perquè veure un algorisme fallar val més que no pas que et diguin que fallarà:

     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

No divergeix, i no es sacseja prop d'una resposta decent. Cicla: recorre un bucle curt per l'espai de pesos i torna exactament on havia començat, per sempre, encertant-ne dos de quatre — el mateix que obtindries endevinant. Cent mil èpoques i cent són indistinguibles, perquè l'algorisme no fa cap progrés que una execució més llarga pogués acabar. Compara-ho amb la cinta, que semblava encallada a 200 èpoques i de fet avançava lentament cap a una resposta real. Des de fora, durant els primers segons les dues coses s'assemblen. Distingir-les, sense el teorema, és impossible — i això és un argument més per conèixer el teorema.

El 1969 Marvin Minsky i Seymour Papert van publicar Perceptrons, un estudi matemàtic en forma de llibre sobre exactament què pot representar aquest model i què no.² XOR n'és el resultat més citat, i la cita se sol desplegar com una acusació: que el llibre va matar la recerca en xarxes neuronals durant quinze anys per rivalitat o rancúnia.

Les matemàtiques del llibre són correctes, i són més interessants que l'exemple de XOR. Minsky i Papert no estaven interessats principalment en si un sol perceptró podia fer XOR; els interessava què passa quan als perceptrons se'ls donen camps receptius limitats — cada unitat veient només una part de l'entrada — i van demostrar que certes propietats globals d'una imatge, com ara si una figura és connexa, no es poden calcular així independentment de quantes unitats facis servir. És un resultat realment profund sobre la localitat, i no té res a veure amb la història popular.

La història popular també s'equivoca en la història. Minsky i Papert discuteixen explícitament els perceptrons multicapa i diuen que la qüestió del seu poder és oberta: sospitaven que estendre la teoria seria "estèril", que és una predicció, no una demostració, i era equivocada. El que faltava el 1969 no era la idea d'apilar capes; era una manera d'entrenar una pila. La regla del perceptró no ho pot fer: necessita saber com s'equivoca cada unitat, i per a una unitat enterrada al mig no hi ha cap etiqueta amb què comparar. Aquesta escletxa va romandre oberta fins que backpropagation es va popularitzar el 1986,³ i tancar-la és el que fa el capítol 5.

Així que el resum honest és aquest. El llibre va demostrar una limitació real d'un model real. L'enfonsament del finançament del camp als anys setanta va tenir moltes causes, una de les quals era que les promeses fetes per als perceptrons a principis dels seixanta havien estat extravagants. I l'obstacle tècnic era solucionable, però ningú no tenia encara l'eina.

El perceptró té seixanta-vuit anys i n'acabes d'escriure un. Val la pena ser precís sobre quines parts encara són a la màquina amb què acabaràs aquest curs, perquè la resposta és: més de les que t'imagines.

El perceptró es va encallar en dues coses alhora, i resulten ser la mateixa cosa.

No pot representar XOR, perquè una línia no n'hi ha prou. Arreglar-ho vol dir apilar capes: una primera capa que doblega l'espai, una segona que dibuixa la línia en l'espai doblegat. Això és el capítol 5.

Però no pots entrenar una pila amb la regla del perceptró, perquè només sap "malament", i una unitat al mig d'una xarxa no té cap etiqueta pròpia sobre la qual equivocar-se. Per entrenar una pila necessites saber com d'equivocat, i en quina direcció, per a cada pes: necessites un pendent. I la funció d'error del perceptró, l'escala, no en té cap.

Així que abans de la pila hi ha d'haver una funció de pèrdua amb una derivada usable. Tampoc una triada perquè és còmoda de diferenciar: una que vingui d'algun lloc, que digui alguna cosa certa sobre les dades, i el gradient de la qual surti d'aquest significat en lloc d'haver estat enginyat a l'inrevés perquè sembli polit.

Això és el capítol 2, i comença fent una pregunta que el perceptró mai no havia hagut de respondre: no "aquesta peça és bona?", sinó "com de probables són aquestes lectures, si aquesta és la veritat?"

També val la pena llegir, al costat d'aquest capítol: l'article original de Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), que és més llegible del que suggereix la seva reputació; McCulloch i Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), l'article que va modelar per primera vegada una neurona com un llindar sobre una suma ponderada; la secció sobre el perceptró d'A Course in Machine Learning de Hal Daumé III, que deriva la mateixa actualització amb un èmfasi diferent; i els capítols 2 i 3 de Mathematics for Machine Learning de Deisenroth, Faisal i Ong per a l'àlgebra lineal, si el quadre de més amunt t'ha deixat amb ganes de més del que donava.