O perceptrón desde cero: que calcula unha neurona

Un perceptrón toma as medicións, multiplica cada unha por un número que controla, súmaas, engade un número máis e mira o signo.

Escribe as medicións dunha peza como un vector $\mathbf{x} = (x_1, x_2)$ — anchura e peso. O perceptrón mantén un vector de pesos $\mathbf{w} = (w_1, w_2)$ e un sesgo $b$. A súa puntuación é

e a súa resposta é o signo desa puntuación: aceptar se $s(\mathbf{x}) \geq 0$, rexeitar en caso contrario.

Ese é todo o modelo. Todo o que o perceptrón chegará a saber sobre a fábrica vive en tres números.

Paga a pena deterse na xeometría, porque é a imaxe que segue funcionando durante os seguintes vinte e nove capítulos, mesmo cando as ecuacións deixen de caber nunha liña. O conxunto de puntos onde $s(\mathbf{x}) = 0$ — onde o perceptrón está exactamente indeciso — é unha liña recta no plano. Nun lado a puntuación é positiva e todo se acepta; no outro é negativa e todo se rexeita. Para un perceptrón, aprender significa mover esa liña.

Dous feitos sobre esa liña despréndense directamente da álxebra, e ambos importan máis adiante:

• $\mathbf{w}$ é perpendicular a ela. O vector de pesos non vai ao longo da fronteira; apunta a través dela, cara ao lado aceptado.
• $b$ desprázaa sen xirala. Sen un sesgo, a liña estaría obrigada a pasar pola orixe, o que nunha fábrica que mide milímetros e gramos sería unha restrición absurda: significaría que unha peza de anchura cero e peso cero está exactamente enriba da cerca.

O perceptrón comeza sen saber nada: $\mathbf{w} = (0, 0)$ e $b = 0$. Todas as puntuacións son cero, así que acepta todo.

Agora móstralle un exemplo de cada vez. Etiqueta as pezas aceptadas como $y = +1$ e as rexeitadas como $y = -1$. Para cada exemplo, fai unha pregunta: saíu ben o signo? A forma compacta de escribir esa pregunta é comprobar se $y \cdot s(\mathbf{x})$ é positivo: se a etiqueta e a puntuación concordan no signo, o seu produto é positivo; se non concordan, é negativo.

Se a resposta é si, non cambies nada. Se a resposta é non, empurra un pouco:

Ese é todo o algoritmo, e paga a pena entender por que é o empurrón correcto en vez de memorizalo. Supón que unha peza debería terse aceptado ($y = +1$) e a puntuación saíu negativa. Engadir $\mathbf{x}$ a $\mathbf{w}$ cambia a puntuación nesa mesma peza en

que é un número positivo. A puntuación da peza que acaba de clasificar mal sobe, que é a dirección na que tiña que ir. A regra non é unha heurística que alguén adiviñou; é o cambio máis pequeno que mellora de maneira demostrable o caso que ten diante. Por suposto, pode estragar outro caso, e por iso dás outra volta.

Fíxate no que falta. Non hai ningunha derivada. Non é un descoido, e é a primeira idea realmente importante do curso.

O que quererías diferenciar é o erro: o reconto de pezas mal clasificadas. Pero ese reconto é unha escaleira: queda plano en 4 mentres moves un pouco a liña, logo baixa a 3 no instante en que a liña cruza un punto. A súa derivada é cero case en todas partes e indefinida nos chanzos. O cálculo non ten de onde agarrarse. A regra do perceptrón traballa ao redor diso ao non pedir ningunha pendente: só pregunta "ben ou mal?" e móvese nunha dirección que pode xustificar xeometricamente.

Iso é unha solución real, e tamén é un camiño sen saída. No Capítulo 2 quereremos unha perda que veña dalgún sitio en vez de ser escollida, no Capítulo 4 un modelo que informe de como de seguro está, e no Capítulo 5 algo con máis dunha capa; e nada diso é alcanzable desde unha regra que só sabe "mal". Recuperar unha pendente útil é o que forza os dous capítulos seguintes. Pero o perceptrón pode facer algo que ningún dos seus sucesores pode: aprender sen cálculo ningún.

Python puro, sen NumPy. Listas e un bucle. NumPy chega no seguinte capítulo, onde a aritmética deixa de caber nun bucle que queiras ler; introducilo agora agocharía a aritmética detrás dunha biblioteca xusto no momento no que queres vela.

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

As catro liñas destacadas son o algoritmo. Todo o demais é contabilidade.

E a cinta, con oito pezas medidas nela: catro que se enviaron e catro que volveron:

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)

Estas oito pezas son separables por unha liña recta: todas as pezas aceptadas están por debaixo de 22 mm e todas as rexeitadas teñen 23 mm ou máis. Unha cerca vertical nos 22 milímetros fai o traballo. Así que o perceptrón debería atopala.

Execútao:

None [-142.1, -13.0] 54.0

Duascentas épocas, 454 correccións, e non converxeu. Os pesos son grandes e teñen o signo incorrecto. Algo vai mal; agás que non vai mal nada, e a razón é a cousa máis útil deste capítulo.

O perceptrón ten unha garantía, demostrada por Novikoff en 1962.¹ Se os datos poden separarse por unha liña dalgunha maneira, o algoritmo fai como moito

correccións antes de deixar de facer ningunha, onde $R$ é o radio dos datos, a lonxitude do vector de exemplo máis longo, e $\gamma$ é a marxe: a distancia desde o hiperplano separador ata o punto máis próximo no espazo aumentado onde o sesgo é unha terceira coordenada. Por iso centrar os datos o cambia aínda que a distancia en milímetros non cambie.

A garantía é incondicional e non menciona épocas, taxas de aprendizaxe nin sorte. Tampouco menciona o tempo, e esa omisión é a clave.

Metamos os nosos números. Medidos directamente a partir das oito pezas, co sesgo incorporado como unha característica constante:

O teorema nunca se violou. Executa a versión en bruto o tempo suficiente e converxe: na época 11.976, despois de 29.870 correccións, cómodamente dentro do seu límite de 2.633.550. E esa diferenza é precisamente a cuestión: o teorema acouta o peor caso, non o típico. Simplemente precisou sesenta veces máis épocas das que ninguén soportaría agardar.

A segunda fila son as mesmas oito pezas, as mesmas vinte liñas de código, con tres liñas engadidas para restar a anchura media e o peso medio a cada medición. Iso é todo. Ese é o cambio completo. Move a nube de puntos para que atravesen a orixe en vez de flotar arredor de (22, 57), e o efecto sobre o límite é un factor de quince mil, porque ambos termos melloran á vez: $R$ baixa de 74 a 13 porque os puntos xa non se miden desde unha orixe afastada, e $\gamma$ sobe de 0,045 a 0,989 porque a marxe se mide contra un vector de pesos que xa non ten que cargar cun sesgo enorme para chegar aos datos.

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

Converxeu en dúas épocas, tras corrixirse exactamente unha vez.

Hai aquí unha lección real, e non é "lembra normalizar as túas entradas", aínda que deberías facelo. É que unha garantía sobre se un algoritmo remata non che di nada sobre se estarás presente cando o faga, e que a distancia entre as dúas cousas adoita ser xeometría. Esta é a primeira aparición dun patrón que volverás atopar no Capítulo 6 coa inicialización, no Capítulo 10 cos calendarios de taxas de aprendizaxe e no Capítulo 13 coa cuantización: as matemáticas din que a cousa é posible, e a enxeñaría decide se é práctica. Un curso que che ensina só o teorema entrégache un modelo que adestra durante tres días e logo bótache a culpa.

Agora o fallo que puxo fin á primeira era das redes neuronais, e cabe en catro filas.

Esquece a fábrica. Toma dúas entradas que poden ser 0 ou 1, e pide que a resposta sexa $+1$ cando exactamente unha delas é 1:

Isto é XOR: ou exclusivo. Antes de seguir lendo, debuxa os catro puntos nun papel: tres cantos dun cadrado unidade e o cuarto. Marca os dous cantos diagonais $(0,1)$ e $(1,0)$ como aceptar, e $(0,0)$ e $(1,1)$ como rexeitar. Agora debuxa unha liña recta cos dous puntos aceptados nun lado e os dous rexeitados no outro.

Non podes. Non é que sexa difícil, nin que precises un algoritmo máis intelixente; é que esa liña non existe. Tres liñas de álxebra mostran por que. Se un perceptrón acertase os catro, entón ler as catro filas por orde dá

Suma as dúas desigualdades do medio: $w_1 + w_2 + 2b \geq 0$, polo tanto $w_1 + w_2 \geq -2b$. A última di $w_1 + w_2 < -b$. Xuntas: $-2b \leq w_1 + w_2 < -b$, o que require $-2b < -b$, que require $b > 0$. E a primeira desigualdade di $b < 0$. Non hai tal $b$, así que non hai tales pesos. Ningún perceptrón, con números calquera que sexan, clasifica XOR.

Execútao de todos modos, porque ver fallar un algoritmo vale máis que que che digan que vai 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

Non diverxe, e tampouco se axita arredor dunha resposta decente. Cicla: percorre un bucle curto polo espazo de pesos e volve exactamente ao punto de partida, para sempre, acertando dous de catro, que é o que obterías ao azar. Cen mil épocas e cen son indistinguibles, porque o algoritmo non está facendo un progreso que unha execución máis longa poida rematar. Compárao coa cinta, que parecía atascada ás 200 épocas e en realidade avanzaba a moenda cara a unha resposta real. Desde fóra, as dúas cousas semellan parecidas durante os primeiros segundos. Distinguilas, sen o teorema, é imposible, e iso é outro argumento para coñecer o teorema.

En 1969 Marvin Minsky e Seymour Papert publicaron Perceptrons, un estudo matemático con extensión de libro sobre exactamente que pode e que non pode representar este modelo.² XOR é o seu resultado máis citado, e a cita adoita usarse como acusación: que o libro matou a investigación en redes neuronais durante quince anos por rivalidade ou rancor.

As matemáticas do libro son correctas, e son máis interesantes ca o exemplo de XOR. Minsky e Papert non estaban interesados principalmente en se un só perceptrón podía facer XOR; interesáballes que ocorre cando aos perceptróns se lles dan campos receptivos limitados — cada unidade vendo só unha parte da entrada — e demostraron que certas propiedades globais dunha imaxe, como se unha figura está conectada, non se poden calcular dese xeito sen importar cantas unidades uses. É un resultado realmente profundo sobre a localidade, e non ten nada que ver coa historia popular.

A historia popular tamén se equivoca coa historia. Minsky e Papert falan explicitamente de perceptróns multicapa e din que a cuestión do seu poder está aberta: sospeitaban que estender a teoría sería "estéril", que é unha predición, non unha demostración, e era incorrecta. O que faltaba en 1969 non era a idea de apilar capas; era unha maneira de adestrar unha pila. A regra do perceptrón non pode facelo: precisa saber como de equivocada está cada unidade, e para unha unidade enterrada no medio non hai ningunha etiqueta coa que compararse. Esa fenda quedou aberta ata que backpropagation se popularizou en 1986,³ e pechala é o que fai o Capítulo 5.

Así que o resumo honesto é este. O libro demostrou unha limitación real dun modelo real. O colapso do financiamento do campo nos anos setenta tivo moitas causas, unha das cales foi que as promesas feitas para os perceptróns a comezos dos sesenta foran extravagantes. E o obstáculo técnico era resoluble, pero ninguén tiña aínda a ferramenta.

O perceptrón ten sesenta e oito anos e ti acabas de escribir un. Paga a pena ser preciso sobre que partes del seguen na máquina coa que rematarás este curso, porque a resposta é: máis das que imaxinarías.

O perceptrón quedou atascado en dúas cousas á vez, e resultan ser a mesma cousa.

Non pode representar XOR, porque unha liña non abonda. Arranxalo significa apilar capas: unha primeira capa que dobra o espazo, unha segunda que debuxa a liña no espazo dobrado. Iso é o Capítulo 5.

Pero non podes adestrar unha pila coa regra do perceptrón, porque só sabe "mal", e unha unidade no medio dunha rede non ten unha etiqueta propia sobre a que equivocarse. Para adestrar unha pila precisas saber como de mal, e en que dirección, para cada peso: precisas unha pendente. E a función de erro do perceptrón, a escaleira, non ten ningunha.

Así que antes da pila ten que haber unha función de perda cunha derivada útil. E tampouco unha escollida porque sexa cómoda de diferenciar: unha que veña dalgún sitio, que diga algo verdadeiro sobre os datos, e cuxo gradiente saia dese significado en vez de ser deseñado ao revés para parecer limpo.

Iso é o Capítulo 2, e comeza facendo unha pregunta que o perceptrón nunca tivo que responder: non "esta peza é boa?", senón "que probables son estas lecturas, se esta é a verdade?"

Tamén paga a pena ler xunto con este capítulo: o artigo orixinal de Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), que é máis lexible do que suxire a súa reputación; McCulloch e Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), o artigo que modelou por primeira vez unha neurona como un limiar sobre unha suma ponderada; a sección sobre o perceptrón de A Course in Machine Learning, de Hal Daumé III, que deriva a mesma actualización cun énfase distinto; e os capítulos 2 e 3 de Mathematics for Machine Learning, de Deisenroth, Faisal e Ong, para a álxebra lineal, se a caixa anterior che deixou con ganas de máis do que daba.