Garantías matemáticas del aprendizaje estadístico

Suponemos observaciones z₁,…,zₙ independientes y con la misma distribución D: IID. Fijamos de antemano una clase H finita, no vacía, y pérdidas medibles 0≤ℓ(h,z)≤1. En clasificación, la pérdida cero–uno vale uno al fallar y cero al acertar.

El riesgo poblacional promedia sobre un dato nuevo de D. El empírico promedia la muestra. Entrenar suele reducir el segundo; el primero es la cantidad que queremos controlar.

Antes de observar datos, R̂ es aleatorio porque depende de la muestra. Para h fijo, su esperanza es R(h), pero una muestra concreta puede quedar por encima o debajo. Una ley asintótica no da sola un margen a tamaño finito.

Una garantía de confianza 1−δ significa que el evento indicado ocurre con al menos esa probabilidad sobre las muestras. No significa que cada predicción nueva tenga error menor que el margen ni transforma el evento en certeza después de entrenar.

Para un h fijo y las hipótesis anteriores, . El factor dos controla ambas direcciones. Para un margen fijo, aumentar n reduce esta cota.

Elegir después el modelo más favorable entre muchos requiere algo más: la garantía de un h prefijado no se aplica automáticamente a una selección que usó esos mismos datos. Primero construiremos un evento simultáneo.

El evento uniforme falla si falla para alguno de los M=|H| modelos. La probabilidad de una unión no supera la suma: .

Para 0<δ<1 elegimos , con log natural. Con probabilidad al menos 1−δ, todos los modelos de H cumplen el margen a la vez. No se exige que sus eventos de error sean independientes.

Sea ĥ un minimizador exacto del riesgo empírico en H. En el evento uniforme, para cualquier h∈H, . Cada desigualdad tiene una razón: garantía, mínimo empírico y garantía otra vez.

La comparación es con el mejor modelo de esa clase, no con cualquier predictor imaginable. Si el algoritmo aproxima el mínimo empírico con error η≥0, se añade η a 2ε. Error de optimización, elección de clase y generalización son cuestiones distintas.

Para M y δ fijos, ε escala como n⁻¹ᐟ². Cuadruplicar n lo divide por dos. Para un margen deseado ε basta , redondeando al entero superior.

Aumentar M sube la cota; puede mejorar la aproximación de la clase y aumentar su complejidad a la vez. Reducir δ pide más confianza y también sube el margen a n fijo. Estas son condiciones suficientes de peor caso, no un número exacto de datos que necesite toda tarea.

Con infinitos modelos no se introduce M=∞ en la misma cota esperando un número finito. En clasificación binaria, herramientas como dimensión VC y funciones de crecimiento controlan cuántos patrones de etiquetas puede producir una clase.

La dimensión VC es el máximo número de puntos que puede etiquetarse de todas las formas mediante la clase. Otros problemas requieren otras complejidades y condiciones de medibilidad. Contar parámetros no reemplaza automáticamente ese análisis.

IID pide independencia y la misma distribución que se usará al definir el riesgo nuevo. Datos repetidos, dependencia temporal o cambios de población necesitan otro análisis. No se arreglan poniendo un n mayor en la fórmula original.

La evaluación práctica complementa la garantía con separación de datos y controles de selección. Probar modelos indefinidamente sobre la misma prueba introduce adaptación. Se comunica el evento, las hipótesis y su alcance junto al número calculado.