Redes neuronales: Del perceptrón a la aproximación universal

En 1943 el neurofisiólogo Warren McCulloch y el joven lógico Walter Pitts publicaron «A Logical Calculus of the Ideas Immanent in Nervous Activity». Modelaron la neurona como un interruptor que se activa si la suma de sus entradas supera un umbral, y demostraron que las redes de estas neuronas pueden calcular cualquier función lógica. Era la primera vez que alguien conectaba el cerebro con la computación de Turing. Faltaba la pieza fundamental: cómo aprenden esas conexiones.

El perceptrón

En 1949 el psicólogo Donald Hebb propuso que las conexiones entre neuronas que se activan juntas se refuerzan. Frank Rosenblatt, psicólogo del Laboratorio Aeronáutico de Cornell, convirtió esa intuición en un algoritmo en 1957: el perceptrón. Calcula una suma ponderada de sus entradas y responde con su signo:

\hat{y} = sgn (𝐰 \cdot 𝐱 + b) \in {- 1, + 1} .

Geométricamente, la ecuación $𝐰 \cdot 𝐱 + b = 0$ es una recta (un hiperplano en dimensión alta) que parte el espacio en dos, una mitad para cada clase. Lo nuevo era la regla de aprendizaje: cada vez que el perceptrón se equivoca con un ejemplo $(𝐱, y)$ , corrige

𝐰 \leftarrow 𝐰 + η y 𝐱, b \leftarrow b + η y .

Si clasifica bien, no toca nada. Rosenblatt construyó una versión física, el Mark I Perceptron, con 400 fotocélulas y potenciómetros movidos por motores eléctricos como pesos ajustables. En julio de 1958, tras una demostración pública, el New York Times escribió que la Marina esperaba que fuera el embrión de un ordenador capaz de «andar, hablar, ver, escribir, reproducirse y ser consciente de su existencia».

Un laboratorio de clasificación. Haz clic para añadir puntos de la clase elegida. Con datos separables el perceptrón encuentra una recta en pocas pasadas, como garantiza el teorema de Novikoff. Con el XOR no lo consigue nunca: cambia a la red con capa oculta y observa cómo dobla la frontera. El fondo muestra la confianza del modelo en cada región.

Teorema (convergencia del perceptrón; Novikoff, 1962)

Supongamos que $‖ 𝐱_{i} ‖ \leq R$ para todos los ejemplos y que existe un vector unitario $𝐰^{*}$ que separa las clases con margen $γ > 0$ : $y_{i} (𝐰^{*} \cdot 𝐱_{i}) \geq γ$ . Entonces el perceptrón (con $b$ incorporado en $𝐰$ y empezando en $𝐰 = 𝟎$ ) comete como mucho

{(\frac{R}{γ})}^{2}

errores, sin importar el orden de los ejemplos ni cuántos haya.

Demostración

Sea $𝐰_{k}$ el vector tras el $k$ -ésimo error, cometido con $(𝐱, y)$ . Tomamos $η = 1$ porque su valor no afecta al resultado. Dos cotas:

Crece en la dirección buena: $𝐰_{k} \cdot 𝐰^{*} = 𝐰_{k - 1} \cdot 𝐰^{*} + y 𝐱 \cdot 𝐰^{*} \geq 𝐰_{k - 1} \cdot 𝐰^{*} + γ$ , luego $𝐰_{k} \cdot 𝐰^{*} \geq k γ$ .

No crece demasiado: $‖ 𝐰_{k} ‖^{2} = ‖ 𝐰_{k - 1} ‖^{2} + 2 y 𝐰_{k - 1} \cdot 𝐱 + ‖ 𝐱 ‖^{2} \leq ‖ 𝐰_{k - 1} ‖^{2} + R^{2}$ , porque hubo error ( $y 𝐰_{k - 1} \cdot 𝐱 \leq 0$ ). Luego $‖ 𝐰_{k} ‖^{2} \leq k R^{2}$ .

Por Cauchy-Schwarz, $k γ \leq 𝐰_{k} \cdot 𝐰^{*} \leq ‖ 𝐰_{k} ‖ \leq \sqrt{k} R$ , de donde $k \leq (R / γ)^{2}$ .

El problema del XOR y el primer invierno

En 1969 Marvin Minsky y Seymour Papert publicaron Perceptrons, un análisis matemático riguroso de lo que un perceptrón de una capa puede y no puede hacer. El ejemplo más famoso es el «o exclusivo» (XOR): devolver 1 si exactamente una de dos entradas binarias vale 1.

Proposición (XOR no es linealmente separable)

No existen $w_{1}, w_{2}, b$ tales que $sgn (w_{1} x_{1} + w_{2} x_{2} + b)$ valga $+ 1$ en $(0, 1)$ y $(1, 0)$ , y $- 1$ en $(0, 0)$ y $(1, 1)$ .

Demostración

Necesitaríamos $b < 0$ , $w_{2} + b > 0$ , $w_{1} + b > 0$ y $w_{1} + w_{2} + b < 0$ . Sumando la segunda y la tercera, $w_{1} + w_{2} + 2 b > 0$ , es decir, $w_{1} + w_{2} + b > - b > 0$ , lo que contradice la cuarta.

El libro reconocía que las redes con varias capas no tienen esa limitación, pero no se sabía cómo entrenarlas. Junto con el informe Lighthill (1973) en el Reino Unido, el escepticismo cortó la financiación y llevó al primer invierno de la IA. Rosenblatt murió en 1971 en un accidente de barco, sin ver la reivindicación de sus ideas.

La capa oculta

La solución es componer. Una red neuronal multicapa aplica una transformación lineal, una no linealidad, otra transformación lineal…

f (𝐱) = W_{2} σ (W_{1} 𝐱 + 𝐛_{1}) + 𝐛_{2} .

Las neuronas de la capa oculta calculan rasgos nuevos (para el XOR, por ejemplo, «al menos una entrada encendida» y «las dos encendidas»), y en ese nuevo espacio el problema sí es separable. Como vimos en el capítulo de álgebra lineal, sin la no linealidad $σ$ todo se colapsaría en una sola matriz. Desde 1986 sabemos entrenar estas redes con retropropagación y descenso de gradiente. ¿Hasta dónde llega su poder expresivo?

El teorema de aproximación universal

Teorema (aproximación universal; Cybenko 1989, Hornik 1991, Leshno et al. 1993)

Sea $σ$ una función continua sigmoidal (o, más en general, cualquier función continua que no sea un polinomio). Para toda función continua $f : [0, 1]^{d} \to ℝ$ y todo $ε > 0$ existen $N$ y parámetros $α_{i}, b_{i} \in ℝ$ , $𝐰_{i} \in ℝ^{d}$ tales que

| f (𝐱) - \sum_{i = 1}^{N} α_{i} σ (𝐰_{i} \cdot 𝐱 + b_{i}) | < ε para todo 𝐱 \in [0, 1]^{d} .

Con una sola capa oculta suficientemente ancha se puede aproximar cualquier función continua tanto como se quiera. En una dimensión la idea se ve con claridad: una sigmoide muy empinada es casi un escalón, y una suma de escalones puede imitar cualquier curva.

Una red con una capa oculta de

N

neuronas sigmoides aproxima la curva objetivo (gris). Cada neurona aporta un escalón suave en una posición; sus alturas se ajustan para seguir la función. Al subir

N

y la pendiente

k

, el error máximo baja tanto como quieras. Es una demostración constructiva del teorema en una dimensión.

Hay que leer el teorema con cuidado. Garantiza que la aproximación existe, pero no dice cuántas neuronas hacen falta (pueden ser exponencialmente muchas), ni que el descenso de gradiente vaya a encontrarla, ni que la red funcione bien con datos que no ha visto. La profundidad importa: hay funciones que una red profunda representa con pocas neuronas y que una red de una sola capa necesitaría exponencialmente más neuronas para aproximar (Telgarsky, 2016). Por eso el aprendizaje es profundo.

El regreso: aprendizaje profundo

En 1989 Yann LeCun entrenó con retropropagación una red convolucional que leía los códigos postales escritos a mano del servicio postal de EE. UU. Las convoluciones reutilizan los mismos pesos en todas las posiciones de la imagen, una forma de incorporar a la arquitectura el conocimiento de que un borde es un borde esté donde esté. Aun así, durante los años noventa y dos mil otras técnicas, como las máquinas de vectores soporte, dominaron el aprendizaje automático.

El cambio llegó con tres ingredientes que por fin coincidieron: datos masivos (ImageNet, 2009, con más de un millón de imágenes etiquetadas para la competición), cálculo masivo (GPU) y algunos trucos técnicos (ReLU, dropout, buena inicialización). En 2012, la red AlexNet de Alex Krizhevsky, Ilya Sutskever y Geoffrey Hinton ganó la competición de ImageNet con un error top-5 del 15,3 %, frente al 26,2 % del segundo clasificado. En pocos años las redes profundas pasaron a dominar la visión, el habla y, después, el lenguaje.

Queda un misterio. Las redes modernas tienen muchos más parámetros que ejemplos de entrenamiento: podrían memorizarlo todo, y aun así aciertan con datos nuevos. ¿Por qué? Esa es la pregunta de la teoría del aprendizaje.

Referencias

W. S. McCulloch y W. Pitts (1943). «A Logical Calculus of the Ideas Immanent in Nervous Activity». Bulletin of Mathematical Biophysics, 5.
F. Rosenblatt (1958). «The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain». Psychological Review, 65(6).
A. B. J. Novikoff (1962). «On Convergence Proofs on Perceptrons». Symposium on the Mathematical Theory of Automata, 12.
M. Minsky y S. Papert (1969). Perceptrons. MIT Press.
G. Cybenko (1989). «Approximation by Superpositions of a Sigmoidal Function». Mathematics of Control, Signals and Systems, 2(4).
K. Hornik (1991). «Approximation Capabilities of Multilayer Feedforward Networks». Neural Networks, 4(2).
Y. LeCun et al. (1989). «Backpropagation Applied to Handwritten Zip Code Recognition». Neural Computation, 1(4).
A. Krizhevsky, I. Sutskever y G. E. Hinton (2012). «ImageNet Classification with Deep Convolutional Neural Networks». NeurIPS.
M. Telgarsky (2016). «Benefits of depth in neural networks». COLT.

§El perceptrón

§El problema del XOR y el primer invierno

§La capa oculta

§El teorema de aproximación universal

§El regreso: aprendizaje profundo