Local Regularization Does Not Characterize Multiclass PAC Learnability

Resumen Técnico: La Regularización Local No Caracteriza la Aprendibilidad PAC Multiclase

Planteamiento del Problema
Una cuestión central en la teoría del aprendizaje estadístico es identificar principios algorítmicos simples que caractericen la aprendibilidad de clases de hipótesis. En la clasificación binaria, la Minimización del Riesgo Empírico (ERM) caracteriza la aprendibilidad PAC. Sin embargo, el entorno multiclase es más complejo; el aprendizaje apropiado puede fallar para clases aprendibles, y los aprendices óptimos suelen depender de estructuras dependientes de la muestra en lugar de ordenamientos de hipótesis fijos.

Asilis et al. propusieron la regularización local como una posible generalización de ERM para el entorno multiclase. Un regularizador local asigna una puntuación fija $\psi(h, x)$ a cada hipótesis $h$ en cada punto de prueba $x$, independientemente de la muestra de entrenamiento. Un aprendiz inducido por tal regularizador predice la etiqueta de la hipótesis con la puntuación mínima entre aquellas que son consistentes con la muestra observada. Si bien Jafar, Asilis y Dughmi demostraron previamente que la regularización local falla para caracterizar la aprendibilidad en el modelo transductivo (donde se evalúa un punto específico retenido), seguía siendo una cuestión abierta si este principio caracteriza la aprendibilidad PAC, donde el punto retenido puede tener una masa poblacional insignificante y el muestreo repetido podría teóricamente revelarlo.

Metodología y Construcción
El artículo construye un contraejemplo utilizando una clase de hipótesis contable basada en torneos (grafos dirigidos completos).

• Clase de Hipótesis ($H$): Para un entero $q \ge 3$, las hipótesis corresponden a las aristas de un grafo completo $K_q$. Una hipótesis $h_{q,e}$ predice la "cabeza" (vértice objetivo) de la arista $e$ dentro de una instancia de torneo $\tau$.
• Espacio de Instancias: Las instancias son pares $(q, \tau)$, donde $\tau$ es un torneo sobre $q$ vértices.
• Distribuciones Difíciles: Los autores definen una familia de distribuciones "difíciles" $D_{e,v}$ para una arista objetivo $e=\{u,v\}$ y un extremo $v$. Estas distribuciones son uniformes sobre torneos donde la arista $e$ está orientada hacia $v$. En consecuencia, todas las etiquetas observadas en la muestra de entrenamiento son idénticas: $(q, v)$.
• El Mecanismo de Fallo:
  1. Filtrado: La muestra de entrenamiento (todas las etiquetas iguales a $v$) filtra el espacio de versiones, reteniendo solo las hipótesis correspondientes a las aristas incidentes a $v$ que están orientadas hacia $v$ en los torneos muestreados.
  2. Ranking Fijo: El regularizador local $\psi$ impone un ordenamiento total estricto sobre las aristas incidentes a $v$ en el punto de prueba antes de observar la muestra.
  3. Inversiones Cíclicas: La dificultad central surge de los triángulos cíclicos en el torneo. Incluso si la muestra de entrenamiento elimina muchos competidores, el ordenamiento fijo de las aristas restantes puede ser "invertido" respecto al objetivo real debido a la estructura cíclica. Específicamente, si una arista saliente (que no debería ser el objetivo) sobrevive al proceso de filtrado y aparece antes en el ranking fijo del regularizador que la verdadera arista entrante objetivo, el aprendiz comete un error.

Contribuciones Clave y Resultados

1. Existencia de un Contraejemplo: El artículo demuestra la existencia de una clase de hipótesis multiclase contable $H$ que es aprendible en el modelo PAC pero no es aprendible por ningún regularizador local.

   • Aprendibilidad: La clase es aprendible en el modelo PAC con una complejidad de muestra de $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$. Un aprendiz explícito tiene éxito al identificar la arista objetivo una vez que aparecen ambos extremos de las etiquetas en la muestra.
   • Límite de Dimensión: La clase tiene una dimensión de Daniely–Shalev-Shwartz (DS) de como máximo 2. Esto se establece mostrando que la imagen de cada hipótesis contiene como máximo dos etiquetas, lo que evita la formación de un pseudo-cubo de 3 dimensiones.

2. Teorema de Imposibilidad: Para cualquier regularizador local $\psi$, existe un aprendiz inducido $A_\psi$ que falla en aprender $H$ en el modelo PAC.

   • Modo de Fallo: Para cualquier regularizador fijo, los autores muestran que para tamaños de muestra $n$ arbitrariamente grandes, existen distribuciones realizables donde la probabilidad de error supera una constante $\delta_0 = \frac{1}{192e}$.
   • Límites Cuantitativos: La probabilidad de error está acotada lejos de cero ($\varepsilon_0 = \frac{1}{96e}$) porque el número esperado de "inversiones" (aristas salientes clasificadas antes que aristas entrantes) en la estructura del torneo sigue siendo significativo. La prueba aprovecha el hecho de que un torneo aleatorio contiene $\Theta(q^3)$ triángulos cíclicos, asegurando que para cualquier ordenamiento estricto de las aristas, una fracción constante de las incidencias del objetivo resultará en un error de predicción.

Significado y Reivindicaciones
El artículo concluye que la regularización local no caracteriza la aprendibilidad PAC multiclase realizable.

• Distinción de los Resultados Transductivos: A diferencia del límite inferior transductivo de Jafar et al., que depende de un único punto retenido con potencialmente masa insignificante, esta construcción distribuye el error a través de una población de torneos. El fallo persiste incluso cuando los tamaños de muestra crecen arbitrariamente, impidiendo que el aprendiz "aprenda" la estructura oculta mediante el muestreo repetido.
• Limitación de las Puntuaciones Fijas: El resultado resalta una rigidez fundamental en la regularización local: debido a que el ranking de las hipótesis en un punto de prueba es fijo antes de observar la muestra, el aprendiz no puede adaptar el orden relativo de los competidores supervivientes basándose en la estructura específica de los datos de entrenamiento. En el entorno de los torneos, esta incapacidad de reordenar conduce a un error poblacional constante a pesar de que la clase tiene una baja dimensión DS y es eficientemente aprendible por otros medios.
• Alcance: El resultado se aplica específicamente a regularizadores donde las puntuaciones son fijas independientemente de la muestra. No aborda marcos no supervisados donde la regla de regularización podría depender de la muestra no etiquetada.

En resumen, el artículo proporciona una respuesta negativa definitiva a la pregunta de si la regularización local caracteriza la aprendibilidad PAC multiclase realizable, demostrando que incluso para clases con baja dimensión combinatoria (dim-DS $\le 2$) y complejidad de muestra óptima, los regularizadores de puntuación fija pueden fallar en el aprendizaje.