Shattering y dimensión VC

Cuando los Espacios de Hipótesis se Vuelven Infinitos

La cota m ≥ (1/ε)(ln|H| + ln(1/δ)) falla cuando |H| = ∞. La mayoría de las clases de hipótesis útiles (clasificadores lineales en ℝᵈ, árboles de decisión, redes neuronales) contienen infinitos candidatos. Vapnik y Chervonenkis resolvieron esto alrededor de 1971 con una medida de complejidad más rica: la dimensión VC.

Shattering

Una clase de hipótesis H shatter un conjunto de n puntos si H puede generar todas las posibles etiquetas de esos n puntos (todas las 2ⁿ dicotomías). Los clasificadores lineales en ℝ² shatter cualquier conjunto de 3 puntos en posición general: para cada una de las 8 posibles etiquetas +/− de esos 3 puntos, existe una recta que los separa correctamente.

Pero los clasificadores lineales en ℝ² no pueden shatter 4 puntos dispuestos en una configuración XOR. Ninguna línea recta separa el par diagonal del par antidiagonal.

Dimensión VC

VC(H) = el mayor n tal que H shatter algún conjunto de n puntos. Para clasificadores lineales en 2D: VC = 3. Para rectángulos alineados con los ejes en 2D: VC = 4. Para redes neuronales con W pesos: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Complejidad muestral con la dimensión VC

Reemplaza ln|H| en nuestra cota PAC por la dimensión VC d:

m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))

La dimensión VC actúa como nuestra 'complejidad efectiva' de una clase infinita. Una clase de hipótesis con baja dimensión VC generaliza a partir de pocas muestras; una clase con alta dimensión VC requiere más datos.

Dimensión VC como conteo efectivo de hipótesis

Una red neuronal tiene W = 10⁹ pesos. Según la cota de Bartlett-Anthony, VC ≤ O(W² log W). Aproximamos VC ≈ W² log₂ W.

Eliminando la Realizabilidad, Posteriores sobre Hipótesis

Dos Generalizaciones Importantes

El PAC clásico asume que nuestro concepto objetivo c vive dentro de nuestra clase de hipótesis H. Los datos reales contienen ruido, etiquetas incorrectas y conceptos que nuestra clase no puede representar. Dos extensiones manejan esto.

PAC Agnóstico

Eliminamos la suposición de que c ∈ H. Ahora competimos contra nuestra hipótesis mejor de su clase h* = argmin_{h ∈ H} risk(h). La forma del límite cambia: en lugar de acercarnos a la perfección, nos acercamos al mejor resultado posible dentro de H.

Cota agnóstica: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ con complejidad muestral m = O(1/ε² × (VC(H) + log(1/δ))). Nótese ε² en lugar de ε en el denominador: el aprendizaje agnóstico requiere más muestras para la misma precisión.

PAC-Bayes (McAllester 1999)

Pasamos de elegir una única hipótesis a elegir una distribución sobre hipótesis. Partimos de una distribución a priori P. Observamos los datos. Derivamos la distribución posterior Q. Las cotas PAC-Bayes acotan el riesgo esperado bajo Q:

𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]

KL(Q‖P) mide cuánto se alejó nuestro posterior de nuestro prior. Dos interpretaciones:

1. Vista de compresión. Un posterior cercano a su prior (KL pequeño) generaliza bien: un pequeño costo de información equivale a un pequeño gap de generalización.

2. Vista bayesiana. Un prior fuerte + una actualización débil de los datos = cota ajustada; un prior débil + una actualización fuerte de los datos = cota más laxa.

Por qué importa PAC-Bayes. Las cotas PAC-Bayes empíricas (Catoni 2007, Dziugaite & Roy 2017) proporcionan garantías de generalización numéricamente significativas para redes neuronales reales, donde las cotas PAC clásicas resultan vacías. Siguen siendo nuestro control teórico más ajustado sobre la generalización en modelos sobreparametrizados.

Lectura de una cota PAC-Bayes

Supongamos que entrenamos una red con n = 50.000 ejemplos etiquetados. Tras el entrenamiento, nuestra posterior Q sobre los pesos tiene KL(Q‖P) = 200 nats respecto a una prior gaussiana P. El riesgo empírico bajo Q es 0,10. Fijamos δ = 0,05.

Sobreparametrización y doble descenso

El desastre predicho por el PAC clásico

El PAC clásico predice: más parámetros que muestras = sobreajuste catastrófico. Aprende perfectamente los datos de entrenamiento y generaliza aleatoriamente en los datos de prueba. El límite VC predice memorización sin aprendizaje.

Las redes neuronales modernas suelen tener entre 10× y 1000× más parámetros que muestras de entrenamiento y aun así generalizan. Esto no debería ocurrir según la teoría clásica. Sin embargo, ocurre.

La curva en U que nos enseñaron

Sesgo-varianza clásico: a medida que crece la capacidad del modelo, el error de entrenamiento disminuye de forma monótona; el error de prueba primero disminuye (menos subajuste), alcanza un mínimo y luego aumenta (sobreajuste). Curva en U predicha por la teoría VC.

Lo que realmente ocurre — Doble descenso

Belkin et al (2019) demostraron que el error de prueba sigue nuestra curva en U clásica hasta el umbral de interpolación (capacidad = #muestras), y luego VUELVE A BAJAR después de ese umbral. Los modelos masivamente sobreparametrizados generalizan mejor que los modelos apenas suficientemente grandes.

Por qué el PAC clásico no captura esto

1. La suposición libre de distribución es demasiado pesimista. Los datos reales tienen estructura (baja dimensión intrínseca, geometría de variedad). Los límites PAC se cumplen sobre distribuciones del peor caso; las distribuciones reales explotan la estructura que también explota el SGD.

2. Regularización implícita. El SGD en redes sobreparametrizadas encuentra soluciones interpoladoras de mínima norma o mínima complejidad, no soluciones arbitrarias. La teoría clásica asume el minimizador de riesgo empírico en el peor caso; los algoritmos reales eligen soluciones benignas.

3. Definición incorrecta de la clase de hipótesis. La clase de hipótesis efectiva explorada por SGD es mucho más pequeña que el espacio nominal de pesos. Los posteriores PAC-Bayes capturan esto; la dimensión VC no.

El trabajo teórico moderno (Bartlett, Long, Lugosi, Tsigler 2020 sobre benign overfitting; Nakkiran et al 2020 sobre double descent) está construyendo una teoría de generalización post-PAC que explica nuestro régimen sobreparametrizado.

Diagnosticando un fallo del PAC clásico

Un equipo de investigación entrena una red de mil millones de parámetros con 100 000 ejemplos etiquetados. El PAC clásico predice cotas vacuas. Empíricamente, la precisión en test alcanza el 95 %.

Kaplan, Chinchilla y el dimensionamiento de la inteligencia general automatizada

De los límites a las leyes de escalado empíricas

El PAC clásico predice el tamaño del conjunto de datos teóricamente y resulta vacuo. Las leyes de escalado empíricas predicen el tamaño del conjunto de datos a partir de la observación y funcionan realmente. Han reemplazado al PAC como nuestra herramienta práctica de dimensionamiento para modelos grandes.

Kaplan et al (2020)

La pérdida sigue una ley de potencia en los parámetros N, los tokens del conjunto de datos D y el cómputo C:

L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC

Duplicar los parámetros reduce la pérdida por un factor multiplicativo fijo. Duplicar los datos reduce la pérdida por otro factor fijo. Estos exponentes (αN, αD, αC) miden y predicen el comportamiento de frontera a través de muchos órdenes de magnitud.

Hoffmann et al 2022 (Chinchilla)

Chinchilla demostró que los exponentes de Kaplan sobreestimaban los parámetros en relación con los datos. El entrenamiento óptimo en términos de cómputo requiere aproximadamente 20 tokens por parámetro:

D_opt ≈ 20 × N

GPT-3 (175B parámetros) se entrenó con ~300B tokens — muy subentrenado según la matemática de Chinchilla. Un modelo de 175B parámetros óptimo en cómputo requiere ~3.5 billones de tokens.

The Data Wall

Escalar nuestro recuento de parámetros requiere escalar proporcionalmente nuestro recuento de tokens. El rastreo público de la web produce ~10¹³ tokens útiles. Una hipotética inteligencia general automatizada de 10¹⁵ parámetros necesitaría ~2×10¹⁶ tokens — tres órdenes de magnitud por encima de los datos disponibles en la web.

Este es nuestro muro de datos. Las leyes de escalado predicen que alcanzaremos una escasez de corpus mucho antes de alcanzar una escasez de cómputo. Los datos sintéticos, los corpus multimodales (vídeo, audio, flujos de sensores) y el RL a partir del entorno buscan superarlo.

El PAC clásico nos decía (incorrectamente) que necesitábamos 10²¹ muestras. Las leyes de escalado nos indican (calibradas a la realidad) que necesitamos 2×10¹⁶. Ambos números superan el texto disponible. El trabajo de frontera actual se centra en cerrar esa brecha.

Estimación de un corpus para una Inteligencia General Automatizada

Supongamos que un laboratorio de frontera propone un modelo de 10¹⁴ parámetros y afirma que alcanzará la inteligencia general automatizada. Queremos dimensionar su corpus de entrenamiento según la regla de Chinchilla.

De los Límites Teóricos a las Mediciones en Producción

Dejar de Calcular Límites; Empezar a Medirlos

Los límites PAC clásicos resultan vacuos. Los límites PAC-Bayes resultan ajustados bajo suposiciones difíciles de verificar. Una alternativa práctica: medir ε empíricamente en tu distribución real y actualizarlo a medida que el sistema opera.

Idea 1 — Hacer la cobertura como PAC empírico

Un objetivo make coverage ejecuta N preguntas reservadas a través de tu sistema de consultas y mide dos tasas:

- cache_hit_rate — fracción de veces que tu sistema encontró una respuesta conocida

- i_dont_know_rate — fracción de veces que tu sistema se abstuvo honestamente

Cada medición = un ensayo de Bernoulli. A partir de los recuentos observados, se calcula un intervalo de confianza de Wilson sobre la tasa real. Ejemplo: N = 1000 consultas, observed i_dont_know_rate = 0.20 → IC 95% ≈ [0.177, 0.226]. El límite superior 0.226 funciona exactamente como una ε PAC con δ = 0.05, derivada de datos reales sobre la distribución real en lugar de un análisis teórico del peor caso.

El vocabulario clásico de PAC se aplica (ε, δ, confianza). Maquinaria diferente (concentración binomial vs. teoría VC). Resultado más ajustado porque las distribuciones reales contienen estructura explotable.

Idea 2 — Auditoría PAC-Bayes mediante eventos de falsificación

Tratar cada falsificación (respuesta del sistema demostrablemente incorrecta) como evidencia que actualiza la posterior sobre la tasa real de error ε:

1. Prior: ε ~ Beta(α₀, β₀). Elegir un prior débil, p. ej., Beta(1, 1) = uniforme.

2. Cada consulta produce un resultado de Bernoulli: falsificado (1) o mantenido (0).

3. Posterior tras k falsificaciones en n consultas: Beta(α₀ + k, β₀ + n − k).

4. Media posterior: (α₀ + k) / (α₀ + β₀ + n) → tasa empírica de falsificación cuando n → ∞.

5. Intervalo creíble del 95% sobre ε se estrecha como 1/√n.

Qué nos aporta esto

- Estimación real de ε₀ a partir del despliegue real, no de la teoría del peor caso

- Alarma anytime-valid: cuando el intervalo creíble posterior cruza el umbral del contrato, avisar a alguien

- Confianza monótona: más consultas observadas → IC más estrecho → garantía más fuerte

Técnicas emparentadas: predicción conforme con recalibración online (Vovk), pruebas de razón de verosimilitud secuenciales (Wald), PAC-Bayes online (Haddouche & Guedj 2022). Misma familia, distinta maquinaria matemática.

Cálculo de una posterior Beta sobre falsificaciones

Nuestro equipo ejecuta una auditoría de cobertura en un sistema de consultas en producción. Prior sobre la tasa real de error ε: Beta(1, 1) (uniforme). Tras 200 consultas de validación observamos 8 falsificaciones.