Teoría del aprendizaje: ¿Por qué funciona con datos que nunca ha visto?

Un estudiante que se aprende de memoria las respuestas del examen del año pasado saca un diez en ese examen y suspende el de este año. Con las máquinas ocurre lo mismo: lo que importa no es el error en los datos de entrenamiento, sino en los datos nuevos. A esa capacidad se le llama generalización, y es la propiedad que distingue aprender de memorizar.

Riesgo empírico y riesgo verdadero

Supongamos que los ejemplos $(x, y)$ salen de una distribución desconocida $𝒟$ . Para un modelo (o hipótesis) $h$ elegido de una clase $ℋ$ y una función de pérdida $ℓ$ , hay dos errores:

R (h) = 𝔼_{(x, y) \sim 𝒟} [ℓ (h (x), y)] y {\hat{R}}_{n} (h) = \frac{1}{n} \sum_{i = 1}^{n} ℓ (h (x_{i}), y_{i}) .

El riesgo verdadero $R$ es lo que nos importa, pero no lo podemos calcular. El riesgo empírico ${\hat{R}}_{n}$ es lo que medimos con los datos. Entrenar es, casi siempre, minimizar el riesgo empírico, un principio que Vladimir Vapnik puso en el centro de la teoría. La pregunta es cuándo un ${\hat{R}}_{n}$ pequeño garantiza un $R$ pequeño.

Ajuste de un polinomio de grado

d

n

puntos con ruido (la curva discontinua es la función real). Derecha: el error en los datos de entrenamiento siempre baja al subir el grado, pero el error en datos nuevos dibuja una U. Con grado bajo el modelo es demasiado rígido (subajuste); con grado alto persigue el ruido (sobreajuste). Pulsa «Nuevos datos» para ver cuánto cambia el ajuste de grado alto con otra muestra: eso es la varianza.

La figura ilustra la descomposición sesgo-varianza (Geman, Bienenstock y Doursat, 1992). Para la pérdida cuadrática, el error esperado en un punto nuevo se separa en tres términos:

𝔼 [(y - \hat{h} (x))^{2}] = \underset{{sesgo}^{2}}{\underset{⏟}{(𝔼 [\hat{h} (x)] - f (x))^{2}}} + \underset{varianza}{\underset{⏟}{Var (\hat{h} (x))}} + \underset{ruido}{\underset{⏟}{σ^{2}}} .

Los modelos simples tienen sesgo alto y varianza baja; los complejos, al revés. La sabiduría clásica dice que hay que buscar el punto intermedio.

Aprendizaje PAC

En 1984 Leslie Valiant dio una definición formal de «aprender» con una expresión deliberadamente modesta: probablemente aproximadamente correcto (PAC). No exigimos acertar siempre; basta con que, con probabilidad alta sobre la muestra, el modelo tenga error pequeño.

Definición (aprendizaje PAC, Valiant 1984)

Una clase $ℋ$ es aprendible si existe un algoritmo y una función $n (ε, δ)$ tales que, para toda distribución $𝒟$ y todos $ε, δ \in (0, 1)$ , con $n \geq n (ε, δ)$ ejemplos el algoritmo devuelve $h$ con

P (R (h) \leq min_{h^{'} \in ℋ} R (h^{'}) + ε) \geq 1 - δ .

Para una clase finita, la respuesta sale de combinar dos herramientas clásicas.

Teorema (cota de generalización para clases finitas)

Si $ℋ$ es finita y la pérdida toma valores en $[0, 1]$ , entonces con probabilidad al menos $1 - δ$ sobre la muestra, para toda $h \in ℋ$ a la vez,

R (h) \leq {\hat{R}}_{n} (h) + \sqrt{\frac{\ln | ℋ | + \ln (2 / δ)}{2 n}} .

Demostración

Para una $h$ fija, ${\hat{R}}_{n} (h)$ es una media de $n$ variables independientes en $[0, 1]$ con esperanza $R (h)$ . La desigualdad de Hoeffding (1963) dice que $P (| {\hat{R}}_{n} (h) - R (h) | > ε) \leq 2 e^{- 2 n ε^{2}}$ : la ley de los grandes números con velocidad exponencial. Con la cota de la unión, la probabilidad de que alguna de las $| ℋ |$ hipótesis se desvíe es como mucho $2 | ℋ | e^{- 2 n ε^{2}}$ . Igualando a $δ$ y despejando $ε$ sale la cota.

La cota recoge la intuición de la navaja de Occam: el precio por elegir entre muchas hipótesis crece con $\ln | ℋ |$ , que es aproximadamente el número de bits necesarios para describir la hipótesis elegida. Más datos lo compensan como $1 / \sqrt{n}$ .

La dimensión VC

Las clases interesantes son infinitas: hay infinitas rectas en el plano. Vladimir Vapnik y Alexey Chervonenkis encontraron en 1971 la medida adecuada de su capacidad. Se dice que una clase pulveriza un conjunto de puntos si consigue todas las formas posibles de etiquetarlos.

Definición (dimensión de Vapnik-Chervonenkis)

La dimensión VC de $ℋ$ es el mayor $d$ tal que algún conjunto de $d$ puntos es pulverizado por $ℋ$ . Si existen conjuntos pulverizados de cualquier tamaño, es infinita.

¿Pueden las rectas pulverizar estos puntos? Cada miniatura es uno de los

2^{n}

etiquetados posibles, con la recta que lo separa (si existe). Arrastra los puntos. Con 3 puntos en posición general salen los 8, pero con 4 nunca salen los 16: hay siempre un etiquetado tipo XOR imposible. La dimensión VC de las rectas del plano es 3 (y la de los hiperplanos de

ℝ^{k}

k + 1

Teorema (teorema fundamental del aprendizaje PAC)

Para clasificación binaria, $ℋ$ es PAC-aprendible si y solo si su dimensión VC $d$ es finita. En ese caso el número de ejemplos necesario es

n (ε, δ) = Θ (\frac{d + \ln (1 / δ)}{ε^{2}}),

y minimizar el riesgo empírico es un algoritmo que lo consigue.

Este resultado, construido por Vapnik y Chervonenkis (1971) y Blumer, Ehrenfeucht, Haussler y Warmuth (1989), es una de las cumbres de la teoría: reduce la pregunta «¿se puede aprender?» a un número combinatorio. En los años noventa inspiró las máquinas de vectores soporte (Boser, Guyon y Vapnik, 1992; Cortes y Vapnik, 1995), que maximizan el margen para controlar la capacidad y fueron el método estrella antes del aprendizaje profundo.

No hay almuerzo gratis

Teorema (no free lunch; Wolpert, 1996)

Promediando sobre todas las funciones objetivo posibles, todos los algoritmos de aprendizaje tienen el mismo error medio fuera de la muestra de entrenamiento. Ningún método es mejor que otro en todos los problemas.

Generalizar exige suponer algo sobre el mundo, un sesgo inductivo. Las convoluciones suponen que lo que importa en una imagen no depende de su posición. La atención supone que cualquier palabra puede depender de cualquier otra, con un peso que se calcula según el contenido. Elegir la arquitectura es, en buena parte, elegir las suposiciones correctas.

El misterio de las redes profundas

En 2017, Chiyuan Zhang y sus colaboradores hicieron un experimento demoledor: entrenaron redes de visión estándar con las etiquetas de las imágenes barajadas al azar. Las redes las memorizaron a la perfección. Su capacidad, por tanto, da para ajustar cualquier cosa, así que las cotas basadas en VC son inútiles para ellas: predicen errores mayores que el 100 %. Y sin embargo, con las etiquetas verdaderas, esas mismas redes generalizan de maravilla.

Belkin y sus colaboradores (2019) documentaron además el doble descenso: si se aumenta el tamaño del modelo más allá del punto en que ajusta perfectamente los datos, el error de prueba, que había empeorado según la curva en U clásica, vuelve a bajar. Los LLM viven muy a la derecha de esa curva.

Pregunta abierta

No hay todavía una teoría completa de por qué generalizan las redes sobreparametrizadas. Las explicaciones candidatas son la regularización implícita del descenso de gradiente estocástico (que tiende a soluciones «simples» o de norma pequeña), la preferencia por mínimos planos, las cotas PAC-Bayes (que sí dan garantías no triviales en algunos casos) y la estructura de los propios datos del mundo real.

Con los datos, la arquitectura y el algoritmo de optimización adecuados, la generalización llega. Para el lenguaje, la arquitectura que lo cambió todo apareció en 2017.

Referencias

V. N. Vapnik y A. Y. Chervonenkis (1971). «On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities». Theory of Probability and Its Applications, 16(2).
W. Hoeffding (1963). «Probability Inequalities for Sums of Bounded Random Variables». JASA, 58(301).
L. G. Valiant (1984). «A Theory of the Learnable». Communications of the ACM, 27(11).
A. Blumer, A. Ehrenfeucht, D. Haussler y M. K. Warmuth (1989). «Learnability and the Vapnik-Chervonenkis Dimension». Journal of the ACM, 36(4).
S. Geman, E. Bienenstock y R. Doursat (1992). «Neural Networks and the Bias/Variance Dilemma». Neural Computation, 4(1).
D. H. Wolpert (1996). «The Lack of A Priori Distinctions Between Learning Algorithms». Neural Computation, 8(7).
C. Zhang, S. Bengio, M. Hardt, B. Recht y O. Vinyals (2017). «Understanding Deep Learning Requires Rethinking Generalization». ICLR.
M. Belkin, D. Hsu, S. Ma y S. Mandal (2019). «Reconciling modern machine-learning practice and the classical bias-variance trade-off». PNAS, 116(32).
S. Shalev-Shwartz y S. Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.

§Riesgo empírico y riesgo verdadero

§Aprendizaje PAC

§La dimensión VC

§No hay almuerzo gratis

§El misterio de las redes profundas