O perceptron de raiz: o que calcula um neurónio

Um perceptron pega nas medições, multiplica cada uma por um número que controla, soma tudo, acrescenta mais um número e olha para o sinal.

Escreva as medições de uma peça como um vetor $\mathbf{x} = (x_1, x_2)$ — largura e peso. O perceptron mantém um vetor de pesos $\mathbf{w} = (w_1, w_2)$ e um bias $b$. A sua pontuação é

e a sua resposta é o sinal dessa pontuação: aceitar se $s(\mathbf{x}) \geq 0$, rejeitar caso contrário.

Este é o modelo inteiro. Tudo o que o perceptron alguma vez saberá sobre a fábrica vive em três números.

Vale a pena parar na geometria, porque é a imagem que continua a funcionar nos próximos vinte e nove capítulos, mesmo quando as equações deixam de caber numa linha. O conjunto de pontos onde $s(\mathbf{x}) = 0$ — onde o perceptron está exatamente indeciso — é uma reta no plano. De um lado, a pontuação é positiva e tudo é aceite; do outro, é negativa e tudo é rejeitado. Aprender, para um perceptron, significa mover essa reta.

Dois factos sobre essa reta seguem diretamente da álgebra, e ambos importam mais tarde:

• $\mathbf{w}$ é perpendicular a ela. O vetor de pesos não fica ao longo da fronteira; aponta através dela, em direção ao lado aceite.
• $b$ desloca-a sem a rodar. Sem bias, a reta seria obrigada a passar pela origem, o que, para uma fábrica que mede milímetros e gramas, seria uma restrição absurda — significaria que uma peça com largura zero e peso zero fica exatamente em cima da vedação.

O perceptron começa sem saber nada: $\mathbf{w} = (0, 0)$ e $b = 0$. Todas as pontuações são zero, por isso aceita tudo.

Agora mostre-lhe um exemplo de cada vez. Rotule as peças aceites como $y = +1$ e as rejeitadas como $y = -1$. Para cada exemplo, faça uma pergunta: o sinal saiu certo? A forma compacta de escrever essa pergunta é verificar se $y \cdot s(\mathbf{x})$ é positivo — se o rótulo e a pontuação concordam no sinal, o seu produto é positivo; se discordam, é negativo.

Se a resposta for sim, não mude nada. Se a resposta for não, dê um empurrão:

Este é o algoritmo inteiro, e vale a pena perceber por que é o empurrão certo em vez de o memorizar. Suponha que uma peça devia ter sido aceite ($y = +1$) e a pontuação saiu negativa. Somar $\mathbf{x}$ a $\mathbf{w}$ altera a pontuação nessa mesma peça em

que é um número positivo. A pontuação da peça em que acabou de errar sobe, que é a direção em que precisava de ir. A regra não é uma heurística que alguém adivinhou; é a menor alteração que melhora, de forma demonstrável, o caso à sua frente. Pode, claro, estragar outro caso, e é por isso que volta a percorrer tudo.

Repare no que está ausente. Não há nenhuma derivada. Isto não é um descuido, e é a primeira ideia verdadeiramente importante do curso.

Aquilo que gostaria de diferenciar é o erro — a contagem de peças mal classificadas. Mas essa contagem é uma escada: fica plana em 4 enquanto desloca a reta, depois cai para 3 no instante em que a reta cruza um ponto. A sua derivada é zero quase em todo o lado e indefinida nos degraus. O cálculo não tem por onde agarrar. A regra do perceptron contorna isso ao não pedir declive nenhum: pergunta apenas «certo ou errado?» e move-se numa direção que consegue justificar geometricamente.

Isto é uma solução real, e também é um beco sem saída. No Capítulo 2 vamos querer uma loss que venha de algum lado em vez de ser escolhida, no Capítulo 4 um modelo que indique quão certo está, e no Capítulo 5 algo com mais do que uma camada — e nada disso é alcançável a partir de uma regra que só conhece «errado». Recuperar um declive utilizável é o que obriga aos próximos dois capítulos. Mas o perceptron pode fazer algo que nenhum dos seus sucessores consegue: aprender sem cálculo nenhum.

Python puro, sem NumPy. Listas e um ciclo. O NumPy chega no próximo capítulo, quando a aritmética deixa de caber num ciclo que se queira ler; introduzi-lo agora esconderia a aritmética atrás de uma biblioteca exatamente no momento em que a queremos ver.

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 quatro linhas destacadas são o algoritmo. Tudo o resto é contabilidade.

E a passadeira, com oito peças medidas nela — quatro que seguiram e quatro que voltaram:

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 peças são separáveis por uma reta — todas as peças aceites têm menos de 22 mm e todas as rejeitadas têm 23 mm ou mais. Uma vedação vertical nos 22 milímetros resolve o problema. Portanto, o perceptron deve encontrá-la.

Execute:

None [-142.1, -13.0] 54.0

Duzentas epochs, 454 correções, e ainda não convergiu. Os pesos são grandes e têm o sinal errado. Algo está errado — exceto que nada está errado, e a razão é a coisa mais útil deste capítulo.

O perceptron tem uma garantia, provada por Novikoff em 1962.¹ Se os dados puderem ser separados por uma reta, o algoritmo faz no máximo

correções antes de deixar de fazer qualquer uma — onde $R$ é o raio dos dados, o comprimento do vetor de exemplo mais longo, e $\gamma$ é a margem: a distância do hiperplano separador ao ponto mais próximo no espaço aumentado onde o bias é uma terceira coordenada. É por isso que centrar os dados a altera, enquanto a distância em milímetros não.

A garantia é incondicional e não menciona epochs, taxas de aprendizagem nem sorte. Também não menciona tempo, e essa omissão é o ponto.

Ponhamos os nossos números. Medidos diretamente a partir das oito peças, com o bias incorporado como uma característica constante:

O teorema nunca foi violado. Execute a versão em bruto durante tempo suficiente e ela converge — na epoch 11.976, após 29.870 correções — confortavelmente dentro do seu limite de 2.633.550, e essa diferença é precisamente o ponto: o teorema limita o pior caso, não o caso típico. Simplesmente precisou de sessenta vezes mais epochs do que alguém estaria disposto a acompanhar.

A segunda linha são as mesmas oito peças, as mesmas vinte linhas de código, com três linhas acrescentadas para subtrair a largura média e o peso médio a cada medição. É só isso. Essa é a alteração inteira. Move a nuvem de pontos para que atravesse a origem em vez de flutuar em (22, 57), e o efeito no limite é um fator de quinze mil, porque os dois termos melhoram ao mesmo tempo: $R$ cai de 74 para 13 porque os pontos deixam de ser medidos a partir de uma origem distante, e $\gamma$ sobe de 0,045 para 0,989 porque a margem é medida contra um vetor de pesos que já não tem de carregar um bias enorme para chegar aos dados.

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

Convergiu em duas epochs, tendo-se corrigido exatamente uma vez.

Há aqui uma lição real, e não é «lembre-se de normalizar os inputs», embora deva fazê-lo. É que uma garantia sobre se um algoritmo termina não lhe diz nada sobre se ainda lá estará quando isso acontecer, e que a diferença entre as duas coisas costuma ser geometria. Esta é a primeira aparição de um padrão que voltará a encontrar no Capítulo 6 com a inicialização, no Capítulo 10 com escalonamentos da taxa de aprendizagem, e no Capítulo 13 com quantização: a matemática diz que a coisa é possível, e a engenharia decide se é prática. Um curso que lhe ensina apenas o teorema entrega-lhe um modelo que treina durante três dias e depois o culpa a si.

Agora a falha que encerrou a primeira era das redes neuronais, e cabe em quatro linhas.

Esqueça a fábrica. Pegue em dois inputs que são cada um 0 ou 1, e peça que a resposta seja $+1$ quando exatamente um deles é 1:

Isto é XOR — ou exclusivo. Antes de continuar, desenhe os quatro pontos em papel: três cantos de um quadrado unitário e o quarto. Marque os dois cantos diagonais $(0,1)$ e $(1,0)$ como aceitar, e $(0,0)$ e $(1,1)$ como rejeitar. Agora desenhe uma reta com os dois pontos aceites de um lado e os dois pontos rejeitados do outro.

Não consegue. Não é que seja difícil, nem que precise de um algoritmo mais esperto; é que a reta não existe. Três linhas de álgebra mostram porquê. Se um perceptron acertasse nos quatro casos, então, lendo as quatro linhas por ordem, obteríamos

Some as duas desigualdades do meio: $w_1 + w_2 + 2b \geq 0$, logo $w_1 + w_2 \geq -2b$. A última diz $w_1 + w_2 < -b$. Juntas: $-2b \leq w_1 + w_2 < -b$, o que exige $-2b < -b$, que exige $b > 0$. E a primeira desigualdade diz $b < 0$. Não existe tal $b$, portanto não existem tais pesos. Nenhum perceptron, com quaisquer números que sejam, classifica XOR.

Execute-o na mesma, porque ver um algoritmo falhar vale mais do que lhe dizerem que vai falhar:

     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

Não diverge, e não se debate perto de uma resposta razoável. Ele entra em ciclo: percorre um pequeno laço no espaço dos pesos e volta exatamente ao ponto de partida, para sempre, acertando dois em quatro — o que obteria por palpite. Cem mil epochs e cem são indistinguíveis, porque o algoritmo não está a fazer progresso que uma execução mais longa possa concluir. Compare isto com a passadeira, que parecia presa às 200 epochs e estava, na verdade, a avançar penosamente para uma resposta real. Vistos de fora, os dois casos parecem semelhantes nos primeiros segundos. Distingui-los, sem o teorema, é impossível — o que é mais um argumento a favor de conhecer o teorema.

Em 1969, Marvin Minsky e Seymour Papert publicaram Perceptrons, um estudo matemático em formato de livro sobre exatamente o que este modelo consegue e não consegue representar.² XOR é o seu resultado mais citado, e a citação costuma ser usada como acusação: a de que o livro matou a investigação em redes neuronais durante quinze anos por rivalidade ou despeito.

A matemática no livro está correta, e é mais interessante do que o exemplo XOR. Minsky e Papert não estavam principalmente interessados em saber se um único perceptron conseguia fazer XOR; interessava-lhes o que acontece quando os perceptrons recebem campos recetivos limitados — cada unidade vê apenas parte do input — e provaram que certas propriedades globais de uma imagem, como uma figura estar ligada, não podem ser calculadas dessa forma, independentemente de quantas unidades se usem. Isto é um resultado genuinamente profundo sobre localidade, e não tem nada que ver com a história popular.

A história popular também está errada na parte histórica. Minsky e Papert discutem explicitamente perceptrons multicamada e dizem que a questão do seu poder está em aberto — suspeitavam que estender a teoria seria «estéril», o que é uma previsão, não uma prova, e estava errada. O que faltava em 1969 não era a ideia de empilhar camadas; era uma forma de treinar uma pilha. A regra do perceptron não consegue fazê-lo: precisa de saber quão errada está cada unidade, e para uma unidade enterrada no meio não há rótulo contra o qual comparar. Essa lacuna ficou aberta até backpropagation ser popularizada em 1986,³ e fechá-la é o que o Capítulo 5 faz.

Portanto, o resumo honesto é este. O livro provou uma limitação real de um modelo real. O colapso do financiamento da área nos anos setenta teve muitas causas, uma das quais foi o facto de as promessas feitas para os perceptrons no início dos anos sessenta terem sido extravagantes. E o obstáculo técnico era resolúvel, mas ninguém tinha ainda a ferramenta.

O perceptron tem sessenta e oito anos e acabou de escrever um. Vale a pena ser preciso sobre que partes dele ainda estão na máquina com que terminará este curso, porque a resposta é: mais do que imagina.

O perceptron ficou preso em duas coisas ao mesmo tempo, e elas acabam por ser a mesma coisa.

Não consegue representar XOR, porque uma reta não chega. Corrigir isso significa empilhar camadas — uma primeira camada que dobra o espaço, uma segunda que desenha a reta no espaço dobrado. Isso é o Capítulo 5.

Mas não consegue treinar uma pilha com a regra do perceptron, porque ela só conhece «errado», e uma unidade no meio de uma rede não tem um rótulo próprio sobre o qual possa estar errada. Para treinar uma pilha, precisa de saber quão errado, e em que direção, para cada peso — precisa de um declive. E a função de erro do perceptron, a escada, não tem um.

Portanto, antes da pilha tem de haver uma função de loss com uma derivada utilizável. E não uma escolhida por ser conveniente de diferenciar: uma que venha de algum lado, que diga algo verdadeiro sobre os dados, e cujo gradient saia desse significado em vez de ser reconstruído ao contrário para parecer arrumado.

Esse é o Capítulo 2, e começa por fazer uma pergunta que o perceptron nunca teve de responder: não «esta peça é boa?», mas «quão prováveis são estas leituras, se isto for a verdade?»

Também vale a pena ler juntamente com este capítulo: o artigo original de Rosenblatt, The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain (Psychological Review 65(6), 1958), que é mais legível do que a sua reputação sugere; McCulloch e Pitts, A Logical Calculus of the Ideas Immanent in Nervous Activity (Bulletin of Mathematical Biophysics 5, 1943), o artigo que primeiro modelou um neurónio como um limiar sobre uma soma ponderada; a secção sobre perceptrons de A Course in Machine Learning, de Hal Daumé III, que deriva a mesma atualização com uma ênfase diferente; e os capítulos 2 e 3 de Mathematics for Machine Learning, de Deisenroth, Faisal e Ong, para a álgebra linear, se a caixa acima o deixou a querer mais do que ela deu.