🧮 Computational Mathematics

Inicio · Parte 17 — Frontera matemática para IA e investigación

357 — VC dimension

frontera-investigacion clase 17 de 20 4 horas demostración vc_dimension

Una clase con infinitas hipótesis puede tener dimensión VC igual a 1.

Fórmulas

VC = tamaño del mayor conjunto que la clase fragmenta
umbrales en 1D: VC = 1
hiperplanos en ℝᵈ: VC = d + 1

Desarrollo

La dimensión de Vapnik-Chervonenkis mide la capacidad de una clase de hipótesis por lo que puede hacer, no por cuántas hipótesis contiene. Una clase fragmenta un conjunto de puntos si puede realizar todas las 2ⁿ etiquetaciones posibles, y la dimensión VC es el tamaño del mayor conjunto que consigue fragmentar.

La distinción con el número de hipótesis es la aportación conceptual. La clase de los umbrales en una dimensión es infinita —hay un umbral por cada número real— y su dimensión VC es 1: puede etiquetar un punto de las dos formas, pero con dos puntos no puede producir la etiquetación «derecha positiva, izquierda negativa». Contar hipótesis no mide capacidad; fragmentar sí.

Los valores conocidos son informativos. Los intervalos en una dimensión tienen VC 2, porque no pueden etiquetar + − +. Los hiperplanos en ℝᵈ tienen VC d+1, así que en el plano son 3: con cuatro puntos en las esquinas de un cuadrado, la configuración XOR no es separable, exactamente el problema del perceptrón de la clase 301.

Su papel es dar cotas de generalización que dependen de la capacidad y no del número de hipótesis. Su límite práctico es severo: para redes neuronales la dimensión VC crece con el número de parámetros, lo que predice que las redes modernas no deberían generalizar en absoluto. La teoría es correcta y la cota es tan holgada que no informa; medidas alternativas como la complejidad de Rademacher o las basadas en normas se comportan algo mejor, sin resolver del todo la cuestión.

Ejemplo trabajado

Dimensión VC de tres clases de hipótesis.

Umbrales en 1D:
  fragmenta 1 punto:  sí
  fragmenta 2 puntos: no
  VC = 1
  (la clase es infinita y su VC vale 1)

Intervalos en 1D:
  VC = 2
  razón: no puede etiquetar + − + con un solo intervalo

Hiperplanos en ℝᵈ:
  VC = d + 1
  en ℝ²: VC = 3

Por qué no 4 puntos en ℝ²:
  XOR en las esquinas de un cuadrado no es separable,
  el mismo obstáculo del perceptrón.

Qué calcula el laboratorio

Dimensión VC: cuántos puntos puede fragmentar una clase de hipótesis.

python classes/part-17-frontera-matematica-para-ia-e-investigacion/357-vc-dimension/lab.py
compmath run 357

Salidas del laboratorio (9)

Muestra de la ejecución real

{
  "clase_umbral_1D": {
    "fragmenta_1_punto": true,
    "fragmenta_2_puntos": false,
    "VC": 1
  },
  "intervalos_1D": {
    "VC": 2,
    "razon": "no puede etiquetar + - + con un único intervalo"
  },
  "hiperplanos_en_R^d": {
    "VC": "d + 1"
  },
  "hiperplanos_en_R^2": 3,
  "por_que_no_4_puntos_en_R2": "XOR en las esquinas de un cuadrado no es separable",
  "clase_infinita_con_VC_finita": "los umbrales son infinitos pero su VC es 1"
}

Errores comunes

Dónde se usa

Cotas de generalización, comparación de familias de modelos, teoría del aprendizaje y análisis de complejidad de clases de hipótesis.

Idea rectora de la parte

HMC usa gradientes para proponer estados lejanos con alta aceptación.

Error a evitar

Invertir una matriz de covarianza sin jitter numérico.

Conexión con IA

Score matching fundamenta los modelos de difusión; el transporte óptimo aparece en flow matching; la teoría estadística del aprendizaje explica el scaling.

Bibliografía de la clase

Archivos de la clase

← 356 Statistical learning theory 358 PAC learning →