Resumen Técnico: ¡Haciendo mucho con poco! Sobre técnicas de muestreo para la estimación/minimización de la pérdida empírica por pares

Planteamiento del problema

Muchas tareas fundamentales de aprendizaje automático, incluyendo el aprendizaje de similitud, de clasificación (ranking), de agrupamiento (clustering) y el aprendizaje de representaciones contrastivas, dependen de la minimización de funciones de pérdida empírica por pares. Estos objetivos se formulan como U-estadísticos de orden 2, lo que requiere la evaluación de $O(N^2)$ pares de observaciones. Al tratar con datos de alta dimensión (por ejemplo, embeddings de imágenes o texto), computar la pérdida sobre todos los pares posibles se convierte en el cuello de botella computacional dominante, haciendo que la evaluación de todos los pares sea prohibitiva a escala.

Un heurístico común para mitigar este costo es submuestrear observaciones individuales y formar pares a partir del subconjunto resultante. Sin embargo, este artículo argumenta que tal estrategia es subóptima. El desafío central consiste en diseñar un esquema de muestreo que seleccione una fracción pequeña e informativa de pares para estimar o minimizar el riesgo empírico, manteniendo la eficiencia estadística y corrigiendo el sesgo de selección.

Metodología

Los autores proponen aplicar la teoría del muestreo de encuestas directamente a la población de pares en lugar de a las observaciones individuales. La metodología se fundamenta en el estimador de Horvitz-Thompson (HT), el cual proporciona una estimación insesgada del total (o media) de la población mediante la ponderación de los valores observados por el inverso de sus probabilidades de inclusión.

Marco central

1. Definición de la población: En lugar de muestrear desde el conjunto de observaciones $I = \{1, \dots, N\}$, el método define una población de pares $J = \{(i, j) : 1 \le i < j \le N\}$.
2. Información auxiliar: El diseño de muestreo aprovecha la información auxiliar $\rho(W_i, W_j)$, un proxy correlacionado con la pérdida por pares $\ell(Z_i, Z_j)$. Esta información puede derivarse de características a nivel de observación (por ejemplo, metadatos, proyecciones de baja dimensión) o de características a nivel de par (por ejemplo, pesos de aristas en un grafo).
3. Probabilidades de inclusión: Los pares se seleccionan con probabilidades proporcionales al proxy auxiliar: $\bar{\pi}_{i,j} \propto \rho(W_i, W_j)$. Esto asegura que los pares "informativos" (aquellos que probablemente contribuyan significativamente a la pérdida) sean muestreados con mayor frecuencia.
4. Estimadores:
   • Muestreo directo de pares: Los pares se muestrean directamente de $J$ utilizando un diseño $\bar{D}_{\bar{N}}$ (por ejemplo, muestreo de Poisson o de rechazo/rejective). El estimador es $\bar{U}_{\bar{D}_{\bar{N}}} = \frac{2}{N(N-1)} \sum_{(i,j) \in \bar{S}} \frac{\ell(Z_i, Z_j)}{\bar{\pi}_{i,j}}$.
   • Muestreo de observaciones (Línea base): Se muestrean observaciones de $I$, y se forman pares a partir del subconjunto. El estimador es $\tilde{U}_{D_N} = \frac{2}{N(N-1)} \sum_{i<j \in S} \frac{\ell(Z_i, Z_j)}{\pi_{i,j}}$.

Análisis teórico

El artículo establece límites no asintóticos para el exceso de riesgo de los predictores entrenados con pares muestreados mediante encuestas.

• Minimización de la varianza: Los autores demuestran que, para un presupuesto fijo de pares evaluados, el muestreo directo de pares domina estrictamente al muestreo de observaciones en términos de la varianza del estimador. Esto se debe a que las probabilidades de inclusión a nivel de observación están restringidas a factorizarse ($\pi_{i,j} = \pi_i \pi_j$), lo que impide que se adapten a la geometría completa de la pérdida por pares.
• Límites de generalización: Utilizando la desigualdad de Bernstein para variables independientes (Poisson) y negativamente asociadas (Rejective), el artículo deriva límites de desviación uniforme. Demuestra que el exceso de riesgo converge a la tasa estándar de $O(1/\sqrt{N})$ siempre que el número de pares muestreados $\bar{n}$ escale linealmente con $N$ (es decir, $\bar{n} = cN$). Esto implica que la razón entre los pares evaluados y los pares totales disponibles desaparece cuando $N \to \infty$, y aun así, la tasa de aprendizaje sigue siendo óptima.

Principales contribuciones

1. Superioridad teórica del muestreo directo de pares: El artículo establece que el muestreo directo de pares es teóricamente óptimo para la estimación de la pérdida por pares. La Proposición 1 demuestra que ningún plan de muestreo basado en observaciones puede alcanzar la misma reducción de varianza que un plan de muestreo directo óptimo, incluso con información auxiliar perfecta.
2. Probabilidades de inclusión óptimas: El Teorema 1 identifica la función de enlace óptima para las probabilidades de inclusión en un esquema de Poisson por pares. La probabilidad óptima es proporcional a $\rho^*(W_i, W_j) = \sqrt{E[\ell^2(Z, Z') | W_i, W_j]}$. El artículo muestra además que el uso de un proxy $\rho$ correlacionado con la pérdida produce reducciones de varianza proporcionales a la calidad de dicha correlación.
3. Garantías de generalización no asintóticas: La Sección 4 proporciona los primeros límites de exceso de riesgo no asintóticos para el aprendizaje por pares basados en pares muestreados mediante encuestas. Confirma que la tasa de convergencia $O(1/\sqrt{N})$ del aprendizaje de pares completo se preserva incluso cuando solo se evalúa una fracción lineal de pares.
4. Validación empírica: El enfoque se valida con datos sintéticos y tres conjuntos de datos del mundo real (MovieLens, Cora, LFW). Los resultados muestran que el muestreo de pares informado reduce la varianza por factores que van desde $2\times$ hasta más de $100\times$ en comparación con el muestreo uniforme de pares y el muestreo de observaciones, dependiendo de la heterogeneidad de la pérdida y la calidad del proxy auxiliar.

Resultados

• Reducción de la varianza: En una tarea de señal dispersa, el muestreo de pares informado logró una reducción de varianza de $121\times$ respecto al muestreo uniforme de pares. En conjuntos de datos reales, la reducción osciló entre $1.2\times$ y $76.8\times$ en comparación con el muestreo basado en observaciones, con una ganancia que escala con el coeficiente de variación al cuadrado de la pérdida ($CV^2(\ell)$).
• Desempeño de aprendizaje: Los experimentos en clasificación de nodos (Cora) y reconocimiento facial (LFW) demostraron que los modelos entrenados con pares muestreados mediante encuestas convergen al desempeño del entrenamiento de pares completo (el oráculo).
  • Corrección de sesgo: A diferencia del "hard negative mining" u otros métodos de selección heurística que introducen sesgo de selección, el enfoque de muestreo de encuestas ponderado por HT permanece insesgado. El artículo muestra que el muestreo de tipo "hard" se estanca debido al sesgo no corregido, mientras que el muestreo de Poisson y de rechazo continúan convergiendo hacia la pérdida de pares completa.
  • Robustez: Incluso con información auxiliar débil (por ejemplo, LFW con una correlación $\approx 0.16$), el muestreo informado nunca tuvo un desempeño inferior al muestreo uniforme, aunque las ganancias fueron modestas. Cuando se utilizó un proxy fuerte (por ejemplo, una pérdida contrastiva precomputada), el desempeño igualó de cerca al del oráculo.

Significado y afirmaciones

El artículo afirma proporcionar un intercambio (trade-off) con principios y base teórica entre el costo computacional y la precisión de la estimación para problemas de aprendizaje por pares.

• Cambio de paradigma: Desafía la práctica estándar de submuestrear observaciones para tareas por pares, argumentando que el dominio natural para el muestreo en estos problemas es el conjunto de pares en sí mismo.
• Frugalidad: La metodología permite "hacer mucho con poco" al permitir que los profesionales evalúen una fracción evanescente de pares ($O(N)$ en lugar de $O(N^2)$) manteniendo las garantías estadísticas del aprendizaje de pares completo.
• Aplicabilidad general: El marco es aplicable a cualquier tarea formulada como un U-estadístico de orden 2, incluyendo ranking, aprendizaje métrico y aprendizaje contrastivo, siempre que haya información auxiliar adecuada para guiar el muestreo.

Los autores concluyen que, si bien existen direcciones abiertas para obtener límites de tasa de aprendizaje más agudos que consideren la reducción de la varianza, este trabajo allana el camino para métodos de aprendizaje por pares más frugales mediante esquemas de selección de datos apropiados basados en la teoría de muestreo de encuestas.