Lo que una neurona no puede

Por qué XOR no es linealmente separable

Una neurona de dos entradas responde $f(x,y)=1$ si $w_1x+w_2y+b>0$ y $0$ en otro caso. Para XOR haría falta, a la vez:

Sumando las dos desigualdades del medio: $w_1+w_2+2b>0$, es decir, $w_1+w_2+b>-b\ge 0$, lo que contradice la última. No existen pesos que funcionen: es el mismo argumento geométrico de las diagonales, en álgebra. Es también el argumento con que Minsky y Papert demuestran en Perceptrons (§2.1) que la equivalencia $x\equiv y$, el complemento de XOR, no la calcula una sola neurona; el libro anota (§1.4) que, de las 16 funciones booleanas de dos variables, son las únicas dos con esa limitación. Lo comprobamos por fuerza bruta: con una rejilla fina de $(w_1,w_2,b)$ se alcanzan 14 de las 16 tablas de verdad, y las dos que faltan son XOR y su complemento.

La solución con una capa oculta

Con la función escalón $H$ (vale 1 si el argumento es positivo y 0 si no), estos pesos resuelven XOR:

$h_1$ es OR, $h_2$ es AND, y la salida es «OR y no AND», que es XOR. En el plano $(h_1,h_2)$ los cuatro puntos pasan a $(0,0)$, $(1,0)$, $(1,0)$ y $(1,1)$: los unos se funden en $(1,0)$ y una recta ya separa las clases.

Qué probaron Minsky y Papert, y qué no

En Perceptrons (1969), un perceptrón «de orden $k$» es una neurona de umbral cuyas entradas son predicados, cada uno de los cuales depende como máximo de $k$ entradas. Entre otros resultados, probaron que la paridad de $n$ bits tiene orden $n$ (teorema 3.1.1): hace falta al menos un predicado que mire todas las entradas. Con $n=2$ la paridad es XOR.

Sobre las redes de varias capas, el libro dice (§13.2) que consideraron las «máquinas de Gamba», «dos capas de perceptrón», y que no encontraron otra clase multicapa realmente interesante; y añade que «es un problema de investigación importante dilucidar (o rechazar) nuestro juicio intuitivo de que la extensión es estéril» (traducción nuestra). Lo presentan como una conjetura por comprobar, no como un teorema.

En código

import numpy as np

H = lambda z: (z > 0).astype(int)       # escalón

def xor_net(x, y):
    h1 = H(x + y - 0.5)                  # OR
    h2 = H(x + y - 1.5)                  # AND
    return H(h1 - h2 - 0.5)              # OR y no AND

for x in (0, 1):
    for y in (0, 1):
        print(x, y, "->", int(xor_net(np.array(x), np.array(y))))
# 0 0 -> 0 | 0 1 -> 1 | 1 0 -> 1 | 1 1 -> 0

Lo que viene

Los pesos de este ejemplo se eligieron a mano. En una red real se aprenden con el descenso del gradiente, que necesita el gradiente de cada peso, incluidos los de las capas ocultas: eso lo resuelve la retropropagación (lección 8), que Rumelhart, Hinton y Williams describieron en 1986 mostrando cómo las unidades ocultas llegan a representar características nuevas de la tarea. Antes, la lección 7 muestra por qué las capas necesitan una función de activación no lineal.