Resumen Técnico: Aprendizaje con Múltiples Respuestas Correctas – Límites de Arrepentimiento bajo Diferentes Modelos de Retroalimentación

1. Definición del Problema y Motivación

Este trabajo aborda el problema del aprendizaje en línea con múltiples respuestas correctas, un escenario donde una única instancia de entrada $x$ admite un conjunto de etiquetas válidas $S \subseteq \mathcal{Y}$ en lugar de una única etiqueta objetivo. Esta formulación está motivada por tareas modernas como la generación de lenguaje (donde un prompt tiene muchas completaciones aceptables), la respuesta a preguntas abierta, la generación de diálogos y los sistemas de recomendación.

El estudio se centra en el paradigma de aprendizaje en línea (online learning), que procede en rondas $t \in [T]$. En cada ronda, un adversario presenta una instancia $x_t$ y un conjunto de etiquetas aceptables $S_t$. El aprendiz predice una etiqueta $\hat{y}_t$ e incurre en una pérdida de 1 si $\hat{y}_t \notin S_t$. El artículo analiza este problema bajo tres modelos de retroalimentación distintos:

1. Error-desconocido (Mistake-unknown): El aprendiz recibe únicamente una etiqueta válida $y_t \in S_t$ (elegida por el adversario), pero no sabe si su predicción fue correcta.
2. Error-conocido (Mistake-known): El aprendiz recibe una única etiqueta válida $y_t \in S_t$ y un indicador binario que revela si su predicción $\hat{y}_t$ fue un error.
3. Valor-conjunto (Set-valued): Al aprendiz se le revela el conjunto completo de etiquetas válidas $S_t$.

El análisis cubre tanto el escenario realizable (donde existe una hipótesis $h^* \in \mathcal{H}$ tal que $h^*(x_t) = S_t$ para todo $t$) como el escenario agnóstico (donde el aprendiz compite contra la mejor hipótesis en $\mathcal{H}$ que minimiza la pérdida acumulada).

2. Metodología y Caracterizaciones Combinatorias

Los autores introducen nuevas dimensiones combinatorias para caracterizar la capacidad de aprendizaje de clases de hipótesis multietiqueta $\mathcal{H}$ bajo cada modelo de retroalimentación. Estas dimensiones se definen mediante argumentos de fragmentación de árboles (tree-shattering) adaptados a la información específica disponible en cada modelo.

Dimensiones Combinatorias

• Dimensión de Littlestone de Valor-Conjunto ($LD_{set}$): Definida sobre un árbol de valores conjuntos donde los nodos están etiquetados con subconjuntos de $\mathcal{Y}$. Un árbol se considera fragmentado (shattered) si para cada trayectoria de predicciones, existe una hipótesis consistente con los conjuntos revelados $S_t$ pero que comete un error en la etiqueta predicha.
• Dimensión de Littlestone de Error-Conocido ($LD_{known}$): Definida sobre un árbol multietiqueta donde los nodos están etiquetados con etiquetas únicas. La fragmentación requiere consistencia con la etiqueta única revelada $y_t$ y un error en la predicción.
• Dimensión de Littlestone de Error-Desconocido ($LD_{unknown}$): Definida utilizando una función de "desplazamiento de error" (mistake offset). Un árbol está $d$-fragmentado si el número acumulado de errores a lo largo de cualquier trayectoria, más un desplazamiento para la hipótesis, excede $d$. Esto da cuenta de la falta de retroalimentación inmediata sobre la corrección.

Algoritmos

Para el escenario realizable, los autores proponen Algoritmos Óptimos Estándar (SOA) para cada modelo de retroalimentación. Estos algoritmos mantienen un espacio de versiones de hipótesis consistentes y seleccionan predicciones que minimizan la dimensión de peor caso del espacio de versiones restante.

• SOA para Error-Desconocido: Mantiene un espacio de versiones y una función de desplazamiento, prediciendo la etiqueta que minimiza la $LD_{unknown}$ máxima de las subclases resultantes.
• SOA para Error-Conocido: Predice para minimizar la $LD_{known}$ máxima de las subclases formadas por el bit de error potencial.
• SOA para Valor-Conjunto: Predice para minimizar la $LD_{set}$ máxima de las subclases formadas por el conjunto revelado $S_t$.

3. Resultados Clave

Aprendizaje en Línea Realizable

El artículo proporciona una caracterización completa del límite de errores óptimo para cualquier clase multietiqueta $\mathcal{H}$ en el escenario realizable:

• Error-desconocido: El límite de errores óptimo es $\min(LD_{unknown}(\mathcal{H}), T)$.
• Error-conocido: El límite de errores óptimo es $\min(LD_{known}(\mathcal{H}), T)$.
• Valor-conjunto: El límite de errores óptimo es $\min(LD_{set}(\mathcal{H}), T)$.

Estos resultados generalizan trabajos previos sobre clases finitas a clases de hipótesis arbitrarias (posiblemente infinitas). Los autores demuestran que $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$, lo cual ocurre si y solo si la intersección de los conjuntos de etiquetas de todas las hipótesis para cualquier instancia es no vacía.

Aprendizaje en Línea Agnóstico (Límites de Arrepentimiento/Regret)

Una contribución significativa es la demostración de que las tasas de arrepentimiento (regret) varían drásticamente entre los modelos de retroalimentación en el escenario agnóstico, contrastando con el aprendizaje de etiqueta única donde el arrepentimiento es típicamente $\tilde{\Theta}(\sqrt{T})$.

1. Error-Desconocido: Los autores muestran que el arrepentimiento puede crecer de forma lineal en $T$ ($\Omega(T)$), incluso para clases de hipótesis simples con $LD_{unknown}=1$. Esto implica que la capacidad de aprendizaje realizable (caracterizada por $LD_{unknown}$) no garantiza un arrepentimiento sublineal en el escenario agnóstico para este modelo de retroalimentación.
2. Error-Conocido: El artículo establece un límite superior de arrepentimiento sublineal de $O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$. Esto se logra reduciendo el problema a bandits no estocásticos con consejo de expertos, utilizando un conjunto de expertos basados en SOA.
3. Valor-Conjunto:
   • Para clases específicas (por ejemplo, la clase de ejemplo $H_3$), el arrepentimiento es constante ($O(1)$).
   • Para clases generales, el arrepentimiento está acotado por $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$. Notablemente, este límite es independiente del tamaño del espacio de etiquetas $|\mathcal{Y}|$, lo que permite que se aplique a espacios de etiquetas infinitos.

Implicaciones del Aprendizaje por Lotes (Batch Learning)

Las dimensiones combinatorias y los límites en línea derivados implican límites de complejidad de muestra para los problemas de aprendizaje por lotes correspondientes. Los autores proporcionan los primeros límites superiores conocidos para el aprendizaje por lotes bajo el modelo de retroalimentación de conjunto completo y mejoran los límites existentes para el caso de respuesta única de clases finitas a infinitas.

4. Significación y Reivindicaciones

El artículo afirma proporcionar la primera caracterización combinatoria completa del aprendizaje multietiqueta en línea realizable bajo tres modelos de retroalimentación distintos. Su principal significación teórica reside en la separación entre la capacidad de aprendizaje realizable y agnóstica en el escenario de error-desconocido, donde la dimensión de Littlestone estándar no logra capturar límites de arrepentimiento significativos.

Además, el trabajo destaca una estructura rica en el aprendizaje multietiqueta agnóstico:

• El modelo de retroalimentación altera fundamentalmente las tasas de arrepentimiento alcanzables (de lineal a constante).
• El modelo de retroalimentación de valor-conjunto permite un arrepentimiento constante en clases específicas y límites independientes de la dimensión para clases generales, un fenómeno no observado en el aprendizaje de etiqueta única.
• Los resultados sugieren que la caracterización del aprendizaje multietiqueta agnóstico requiere objetos combinatorios más allá de aquellos suficientes para el aprendizaje realizable.

Los autores señalan explícitamente que sus definiciones de arrepentimiento difieren de trabajos previos (por ejemplo, Joshi et al. [JLB+25] y Raman et al. [RST24]) para alinearse mejor con la tarea de predicción subyacente de minimizar el error contra el conjunto verdadero de etiquetas aceptables, en lugar de competir contra una hipótesis que simplemente contiene una etiqueta específica revelada.