Resumen Técnico: Submuestreo para el Aprendizaje Supervisado en Espacios de Hilbert con Núcleo Reproductor (RKHS)

Planteamiento del Problema

En la era del Big Data, el coste computacional y el consumo energético asociados al entrenamiento de modelos de aprendizaje estadístico en conjuntos de datos masivos se han convertido en cuellos de botella críticos. Aunque existen diversas técnicas de reducción de datos (por ejemplo, sketching, coresets, optimización estocástica), muchas son o bien agnósticas a la tarea o dependen de probabilidades intratables para una selección óptima. Específicamente, en el aprendizaje supervisado no paramétrico donde las hipótesis residen en un Espacio de Hilbert con Núcleo Reproductor (RKHS), los métodos existentes suelen fallar al no proporcionar un esquema de submuestreo dependiente de los datos que sea óptimo para minimizar la varianza asintótica del estimador. Los métodos de kernel suelen escalar de forma deficiente ($O(n^2)$ o $O(nm)$) con el tamaño del conjunto de datos original $n$, y aunque el submuestreo reduce esto a $O(s^2)$ (donde $s \ll n$), el submuestreo uniforme estándar ignora el valor informacional de los puntos de datos individuales, lo que conduce a una precisión de estimación subóptima.

Metodología

Los autores proponen un marco para la Minimización del Riesgo Submuestreado (SRM) en RKHS, utilizando un esquema de reponderación de Horvitz-Thompson para asegurar una estimación insesgada del riesgo empírico. La metodología central consiste en:

1. Marco Teórico:

   • Configuración: Aprendizaje supervisado no paramétrico (clasificación y regresión) con una función de pérdida $\ell$ convexa y dos veces diferenciable y una penalización de tipo ridge. El estimador minimiza un riesgo empírico regularizado.
   • Estrategias de Submuestreo: El artículo analiza dos estrategias:
     • Submuestreo Multinomial (con reemplazo): Los puntos se extraen independientemente con probabilidades de inclusión $\pi_{n,i}$.
     • Submuestreo de Poisson (sin reemplazo): Los puntos se incluyen independientemente con una probabilidad $s_n \pi_{n,i}$.
   • Análisis Asintótico: Utilizando herramientas de espacios de probabilidad funcionales y la teoría de martingalas, los autores establecen la normalidad asintótica del estimador SRM. Derivan el operador de covarianza asintótica $\Sigma^*$, el cual depende de las probabilidades de inclusión $\pi_{n,i}$.

2. Esquema de Submuestreo Óptimo:

   • Los autores definen la L-optimalidad como la minimización de la traza del operador de covarianza asintótica (precondicionado por la inversa de la Hessiana del riesgo real).
   • Derivan una expresión de forma cerrada para la función de interés absoluto L-óptima $\psi^*$, que dicta las probabilidades de inclusión óptimas:
     $$\psi^*(z) = |\ell'(h_0(x), y)| \sqrt{k(x, x)}$$
     donde $h_0$ es el verdadero minimizador del riesgo regularizado, $\ell'$ es la derivada de la pérdida y $k$ es el kernel.
   • Esto implica que los puntos de datos con un alto error de predicción (un $|\ell'|$ grande) o una alta similitud de auto-kernel deben ser muestreados con una mayor probabilidad.

3. Implementación Práctica (Estimador Piloto):

   • Dado que $h_0$ es desconocido, los autores proponen un enfoque de plug-in:
     1. Calcular un estimador piloto $\hat{h}_{k_n}$ sobre un subconjunto pequeño de los datos ($k_n \ll s_n$).
     2. Estimar las probabilidades óptimas utilizando $\hat{h}_{k_n}$.
     3. Suavizar las probabilidades estimadas para asegurar que cumplan con los supuestos técnicos (específicamente, que no converjan a cero demasiado rápido) utilizando un hiperparámetro $\alpha \in (0, 1]$:
        $$\tilde{\pi}_{n,i}^\alpha = (1-\alpha)\tilde{\pi}_{n,i} + \frac{\alpha}{n}$$
     4. Para el submuestreo de Poisson, aplicar una truncación post-hoc para asegurar que las probabilidades sigan siendo válidas ($\leq 1/s_n$).
   • Se proporcionan garantías teóricas (consistencia y normalidad asintótica) para este estimador piloto-$\alpha$.

Contribuciones Clave

• Normalidad Asintótica en RKHS: El artículo establece la normalidad asintótica de los estimadores submuestreados en RKHS de dimensión infinita, distinguiéndose de los resultados paramétricos mediante el empleo de técnicas de espacio de probabilidad aleatoria funcional y la teoría de martingalas.
• Derivación del Esquema Óptimo: Proporciona la primera derivación de un esquema de submuestreo óptimo específicamente para métodos de kernel no paramétricos, demostrando que la probabilidad de inclusión óptima es proporcional a la magnitud del gradiente de la pérdida ponderada por la diagonal del kernel.
• Comparación de Estrategias: Los autores analizan las compensaciones entre el submuestreo multinomial y el de Poisson, demostrando que la elección óptima depende de la razón límite $c = \lim s_n/n$. Notablemente, debido a la presencia de la regularización ridge, las dos estrategias no tienen eficiencias asintóticas idénticas cuando $c=0$, lo que difiere de los hallazgos en entornos paramétricos.
• Algoritmo Práctico Robusto: La propuesta de un algoritmo de dos pasos ("piloto") que combina un estimador piloto con suavizado y truncación hace que el esquema teóricamente óptimo sea implementable en la práctica manteniendo las garantías estadísticas.

Resultados

Se realizaron experimentos numéricos en conjuntos de datos sintéticos (clasificación y regresión) y un conjunto de datos del mundo real (UCI Covertype), comparando el SRM piloto-$\alpha$ propuesto contra:

• Submuestreo uniforme (línea base).
• Método Nyström.
• Características de Fourier Aleatorias (RFF).
• Sketching de kernel.

Hallazgos:

• Parámetro de Suavizado: Un parámetro de suavizado $\alpha$ entre 0.1 y 0.4 produce el mejor error de generalización, equilibrando los beneficios del submuestreo óptimo con la estabilidad del muestreo uniforme.
• Régimen de Datos Grandes: Para conjuntos de datos grandes, el SRM propuesto supera significativamente al submuestreo uniforme en términos de la relación entre el error de generalización y el tiempo de computación (CPU).
• Comparación con Aproximaciones: En el conjunto de datos real Covertype, el método SRM fue más eficiente que Nyström, RFF y sketching. En tareas sintéticas de baja dimensión, las aproximaciones de kernel (Nyström, RFF) fueron más rápidas, lo que sugiere que el submuestreo y la aproximación de kernel son técnicas complementarias.
• Enfoque Híbrido: Combinar el submuestreo con el método Nyström mejoró aún más el rendimiento, lo que indica la compatibilidad del método con las técnicas de aproximación de kernel existentes.

Significado y Reivindicaciones

El artículo afirma proporcionar un método teóricamente fundamentado y prácticamente viable para reducir la carga computacional del aprendizaje basado en kernels sin sacrificar la eficiencia estadística. Al derivar un esquema de submuestreo óptimo basado en la traza de la covarianza asintótica, los autores ofrecen una forma de extraer individuos "informativos" de grandes conjuntos de datos.

Los autores enmarcan su trabajo de forma modesta como un paso hacia un aprendizaje más eficiente energéticamente, señalando que, si bien el método reduce el tamaño del problema de optimización de $O(n^2)$ a $O(s^2)$, este depende de un estimador piloto. Reconocen que la teoría se basa actualmente en riesgos regularizados y que extenderla a entornos no regularizados o desarrollar procedimientos online de múltiples etapas son direcciones potenciales para futuras investigaciones. El trabajo se distingue al abordar los desafíos específicos del entorno no paramétrico de RKHS, que las teorías de submuestreo paramétrico existentes no cubren por completo.