O perceptron do zero: o que um neurônio calcula

Um perceptron pega as medições, multiplica cada uma por um número que ele controla, soma tudo, adiciona 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 viés $b$. Sua pontuação é

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

Esse é o modelo inteiro. Tudo que o perceptron saberá sobre a fábrica mora em três números.

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

Dois fatos sobre essa linha vêm diretamente da álgebra, e ambos importam mais tarde:

• $\mathbf{w}$ é perpendicular a ela. O vetor de pesos não fica ao longo da fronteira; ele aponta através dela, em direção ao lado aceito.
• $b$ a desliza sem girá-la. Sem um viés, a linha seria forçada a passar pela origem, o que, para uma fábrica medindo milímetros e gramas, seria uma restrição absurda — significaria que uma peça de largura zero e peso zero está exatamente em cima do muro.

O perceptron começa sem saber nada: $\mathbf{w} = (0, 0)$ e $b = 0$. Toda pontuação é zero, então ele aceita tudo.

Agora mostre a ele um exemplo por vez. Rotule as peças aceitas 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, 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:

Esse é o algoritmo inteiro, e vale a pena entender por que esse é o empurrão certo, em vez de memorizá-lo. Suponha que uma peça deveria ter sido aceita ($y = +1$) e a pontuação saiu negativa. Adicionar $\mathbf{x}$ a $\mathbf{w}$ muda a pontuação nessa mesma peça em

que é um número positivo. A pontuação da peça que ele acabou de errar sobe, que é a direção em que precisava ir. A regra não é uma heurística que alguém chutou; é a menor mudança que comprovadamente melhora o caso à sua frente. É claro que ela pode quebrar outro caso, e por isso você dá outra volta.

Observe o que está ausente. Não há derivada em lugar nenhum. Isso não é descuido, e é a primeira ideia realmente importante do curso.

O que você gostaria de diferenciar é o erro — a contagem de peças classificadas incorretamente. Mas essa contagem é uma escada: fica plana em 4 enquanto você empurra a linha, depois cai para 3 no instante em que a linha cruza um ponto. Sua derivada é zero em quase todos os lugares e indefinida nos degraus. O cálculo não tem onde se agarrar. A regra do perceptron contorna isso ao não pedir inclinação nenhuma: ela pergunta apenas "certo ou errado?" e se move em uma direção que consegue justificar geometricamente.

Isso é uma solução genuína, e também é um beco sem saída. No Capítulo 2, vamos querer uma função de perda que venha de algum lugar em vez de ser escolhida; no Capítulo 4, um modelo que informe quão certo ele está; e, no Capítulo 5, algo com mais de uma camada — e nada disso é alcançável a partir de uma regra que só conhece "errado". Recuperar uma inclinação utilizável é o que força os próximos dois capítulos. Mas o perceptron consegue fazer algo que nenhum de seus sucessores consegue: aprender sem cálculo algum.

Python puro, sem NumPy. Listas e um loop. NumPy chega no próximo capítulo, quando a aritmética deixa de caber em um loop que você gostaria de ler; introduzi-lo agora esconderia a aritmética atrás de uma biblioteca exatamente no momento em que você quer vê-la.

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. Todo o resto é contabilidade.

E a esteira, com oito peças medidas nela — quatro que foram enviadas 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)

Essas oito peças são separáveis por uma linha reta — toda peça aceita tem menos de 22 mm e toda peça rejeitada tem 23 mm ou mais. Uma cerca vertical em 22 milímetros resolve. Então o perceptron deveria encontrá-la.

Execute:

None [-142.1, -13.0] 54.0

Duzentas épocas, 454 correções, e ele não convergiu. Os pesos são grandes e têm o sinal errado. Algo está errado — exceto que nada está errado, e o motivo é 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 linha, o algoritmo faz no máximo

correções antes de parar 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 em que o viés é uma terceira coordenada. É por isso que centralizar os dados muda essa distância, enquanto a distância em milímetros não muda.

A garantia é incondicional e não menciona épocas, taxas de aprendizado nem sorte. Ela também não menciona tempo, e essa omissão é o ponto.

Coloque nossos números. Medidos diretamente a partir das oito peças, com o viés incorporado como uma feature constante:

O teorema nunca foi violado. Execute a versão bruta por tempo suficiente e ela converge — na época 11.976, depois de 29.870 correções — confortavelmente dentro de seu limite de 2.633.550, e essa lacuna em si é o ponto: o teorema limita o pior caso, não o caso típico. Ele simplesmente precisou de sessenta vezes mais épocas do que qualquer pessoa aceitaria esperar.

A segunda linha são as mesmas oito peças, as mesmas vinte linhas de código, com três linhas adicionadas para subtrair a largura média e o peso médio de cada medição. Só isso. Essa é a mudança inteira. Ela move a nuvem de pontos para que ela 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 já não são 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 precisa carregar um viés enorme para alcançar os 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 épocas, tendo se corrigido exatamente uma vez.

Há uma lição real aqui, e ela não é "lembre-se de normalizar suas entradas", embora você deva. É que uma garantia de que um algoritmo termina não diz nada sobre você estar presente quando isso acontecer, e a diferença entre as duas coisas geralmente é geometria. Esta é a primeira aparição de um padrão que você encontrará de novo no Capítulo 6 com inicialização, no Capítulo 10 com cronogramas de taxa de aprendizado, e no Capítulo 13 com quantização: a matemática diz que a coisa é possível, e a engenharia decide se ela é prática. Um curso que ensina apenas o teorema entrega a você um modelo que treina por três dias e coloca a culpa em você.

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

Esqueça a fábrica. Pegue duas entradas que podem ser 0 ou 1, e peça que a resposta seja $+1$ quando exatamente uma delas for 1:

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

Você não consegue. Não é que seja difícil, ou que você precise de um algoritmo mais esperto; é que a linha não existe. Três linhas de álgebra mostram por quê. Se um perceptron acertasse os quatro, então, lendo as quatro linhas na ordem, teríamos

Some as duas desigualdades do meio: $w_1 + w_2 + 2b \geq 0$, então $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$, o que exige $b > 0$. E a primeira desigualdade diz $b < 0$. Não existe tal $b$, então não existem tais pesos. Nenhum perceptron, com quaisquer números que sejam, classifica XOR.

Execute mesmo assim, porque ver um algoritmo falhar vale mais do que ouvir que ele 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

Ele não diverge, e não fica se debatendo perto de uma resposta razoável. Ele entra em ciclo: percorre um pequeno loop pelo espaço de pesos e volta exatamente para onde começou, para sempre, acertando dois de quatro — o que você conseguiria chutando. Cem mil épocas e cem são indistinguíveis, porque o algoritmo não está fazendo um progresso que uma execução mais longa poderia concluir. Compare isso à esteira, que parecia travada em 200 épocas e, na verdade, estava avançando lentamente rumo a uma resposta real. Por fora, as duas situações parecem semelhantes nos primeiros segundos. Distingui-las, 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 esse modelo pode e não pode representar.² XOR é seu resultado mais citado, e a citação costuma ser usada como acusação: que o livro matou a pesquisa em redes neurais por quinze anos por rivalidade ou despeito.

A matemática do livro está correta, e é mais interessante do que o exemplo do XOR. Minsky e Papert não estavam interessados principalmente em saber se um único perceptron podia fazer XOR; eles estavam interessados no que acontece quando perceptrons recebem campos receptivos limitados — cada unidade vendo apenas parte da entrada — e provaram que certas propriedades globais de uma imagem, como uma figura estar conectada, não podem ser computadas dessa forma, independentemente de quantas unidades você use. Esse é um resultado genuinamente profundo sobre localidade, e não tem nada a ver com a história popular.

A história popular também erra na história. Minsky e Papert discutem explicitamente perceptrons de múltiplas camadas e dizem que a questão de seu poder está em aberto — eles suspeitavam que estender a teoria seria "estéril", o que é uma previsão, não uma prova, e estava errado. 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 fazer isso: ela precisa saber quão errada cada unidade está, e, para uma unidade enterrada no meio, não há rótulo para comparar. Essa lacuna ficou aberta até backpropagation ser popularizada em 1986,³ e fechá-la é o que o Capítulo 5 faz.

Então 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 delas sendo que as promessas feitas para perceptrons no começo dos anos sessenta tinham sido extravagantes. E o obstáculo técnico era solucionável, mas ninguém ainda tinha a ferramenta.

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

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

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

Mas você 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 estar errada. Para treinar uma pilha, você precisa saber quão errado, e em que direção, para cada peso — você precisa de uma inclinação. E a função de erro do perceptron, a escada, não tem uma.

Então, antes da pilha, precisa existir uma função de perda com uma derivada utilizável. E não uma escolhida porque é conveniente de diferenciar: uma que venha de algum lugar, que diga algo verdadeiro sobre os dados, e cujo gradiente saia desse significado em vez de ser engenharia reversa para parecer arrumado.

Esse é o Capítulo 2, e ele começa fazendo uma pergunta que o perceptron nunca precisou responder: não "esta peça é boa?", mas "qual é a probabilidade destas leituras, se esta é a verdade?"

Também vale ler junto 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 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 seção sobre perceptron 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 deixou você querendo mais do que ela ofereceu.