XOR: Onde um Neurônio Só Bate a Cabeça na Parede

Aula 3d, e é a última que existe no repositório até hoje. Antes de fechar essa leva de posts, o professor deixa um gancho que é quase poético: o mesmo perceptron que resolveu tudo até aqui, sem esforço, trava duro num problema de 4 pontos.

O dataset: portas lógicas, geometricamente

def createLogicalDataset(n=40, func=lambda a, b: bool(a) or bool(b)):
  X, y = make_blobs(n_samples=n,
                    centers=[[0.2,0.2], [0.8, 0.2], [0.2, 0.8], [0.8, 0.8]],
                    n_features=2,
                    cluster_std=0.05,
                    center_box=(0,1))
  y = np.array([func(a>0.5, b>0.5) for a, b in X], dtype=int)
  return X, y

O mesmo dataset de 4 blobs do post anterior, só que agora o rótulo vem de aplicar uma função lógica (or, and, !=) em cima de "esse ponto está à direita de 0.5?" e "esse ponto está acima de 0.5?". Cada blob vira, na prática, um valor de porta lógica: canto inferior-esquerdo é (falso, falso), inferior-direito é (verdadeiro, falso), e assim por diante.

OR e AND: sem drama

X, y = createLogicalDataset(func=lambda a, b: bool(a) or bool(b))
model = NeuralNetwork()
model.fit(X, y)

Saída (OR): acurácia 1.0, pesos [-1.14, 1.72, 1.57].

X, y = createLogicalDataset(func=lambda a, b: bool(a) and bool(b))
model = NeuralNetwork()
model.fit(X, y)

Saída (AND): acurácia 1.0, pesos [-2.16, 1.55, 1.79].

As duas portas são linearmente separáveis: em OR, uma única reta separa o blob inferior-esquerdo (o único falso) dos outros três. Em AND, a mesma coisa, só que isolando o blob superior-direito (o único verdadeiro). Nada que esse perceptron não tenha feito o post inteiro até aqui.

XOR: a mesma receita, o mesmo código, e trava

X, y = createLogicalDataset(func=lambda a, b: bool(a) != bool(b))
model = NeuralNetwork()
model.fit(X, y)

Saída (XOR): acurácia 0.5, pesos [0.006, -0.011, -0.002].

Acurácia de 0.5 com 2 classes é exatamente o nível de jogar uma moeda. E repara nos pesos: praticamente zero nos três, o modelo essencialmente desistiu, encolhendo o vetor de peso até quase nada em vez de convergir pra qualquer coisa útil. Reproduzi isso eu mesmo, com dataset seedado, e bati na mesma parede: OR e AND em 1.0, XOR travado em 0.5, pesos igualmente murchos ([-0.025, -0.066, 0.118]).

O motivo é geométrico, e dá pra ver sem fórmula nenhuma: XOR marca como verdadeiro os dois cantos opostos na diagonal (inferior-direito e superior-esquerdo) e como falso os outros dois cantos, também opostos entre si (inferior-esquerdo e superior-direito). Não existe reta nenhuma que separe "os dois cantos de uma diagonal" dos "dois cantos da outra diagonal": qualquer reta que eu desenhar corta uma das diagonais ao meio, misturando as duas classes dos dois lados. XOR não é linearmente separável, ponto final, e nenhuma quantidade de treino vai mudar isso, porque o problema não está no algoritmo de aprendizado, está no que um único neurônio, com uma única fronteira reta, consegue representar.

Interativo: assiste o perceptron nunca convergir

Mesmo dataset seedado de cima, agora no XOR. Clica em "Processar próximo ponto" várias vezes: repara que, diferente de todo componente anterior nessa playlist, esse aqui nunca mostra a mensagem de convergência. Sempre vai sobrar pelo menos um ponto do lado errado, não importa quanto eu clique.

Fica à vontade pra clicar bastante. A fronteira vai girar e deslizar sem parar, tentando achar um lugar que não existe.

O que isso significa (e o que vem depois)

Esse resultado não é uma curiosidade isolada, é historicamente o limite que definiu os primeiros anos de rede neural: um único neurônio, com uma fronteira de decisão linear, tem um teto de expressividade, e XOR fica acima desse teto. A saída, e é aqui que essa playlist ainda não chegou, é empilhar neurônios: um MLP (rede de múltiplas camadas) consegue resolver XOR combinando duas fronteiras lineares numa camada escondida antes de decidir a saída final. Guardei dois papers exatamente pra esse momento, na pasta de referência dessa playlist: a tese de doutorado de Paul Werbos (1974), a derivação mais antiga que se conhece do algoritmo de retropropagação (backpropagation), e o paper de Rumelhart, Hinton e Williams (Nature, 1986), o que de fato popularizou esse algoritmo e destravou o treino prático de MLPs.

O repositório do professor ainda não tem esse notebook. As 3 aulas que cobri até aqui (perceptron, Adaline, funções de custo, multiclasse) são tudo que existe publicado até o momento, e o gancho do XOR é exatamente onde a matéria dele também está agora. Como já falei lá no primeiro post dessa playlist, essa é uma playlist viva: assim que o professor publicar a aula de MLP e retropropagação, volto aqui pra continuar de onde parei, com Werbos e Rumelhart-Hinton-Williams já esperando pra entrar em cena.

Fechando

Aplicação Prática

Não tem um dataset real clássico de "XOR" pra buscar (é uma função lógica, não um fenômeno do mundo), então a aplicação prática aqui é mostrar que a mesma barreira de separabilidade linear aparece em dado real, não só em portas lógicas de brinquedo. Uso o dataset de duas luas que já apareceu no Reconhecimento de Padrões, sabidamente não-linearmente-separável.

from sklearn.datasets import make_moons
X, y = make_moons(n_samples=300, noise=0.05, random_state=42)

O perceptron não trava tão feio quanto no XOR (0.867 não é 0.5, porque as duas luas têm uma separação aproximadamente linear na maior parte do espaço, só a curvatura nas pontas engana uma reta), mas fica bem atrás do KNN, que não tem esse teto porque não depende de uma fronteira reta única. É o mesmo limite estrutural do XOR, só que numa versão mais suave: qualquer problema onde a fronteira verdadeira não é uma reta vai expor essa limitação, cedo ou tarde.