Résumé Technique : Apprentissage avec Multiples Réponses Correctes – Bornes de Regret sous Différents Modèles de Feedback

1. Définition du Problème et Motivation

Ce travail traite du problème de l'apprentissage en ligne avec multiples réponses correctes, un cadre où une instance d'entrée $x$ admet un ensemble de labels valides $S \subseteq \mathcal{Y}$ plutôt qu'un label cible unique. Cette formulation est motivée par des tâches modernes telles que la génération de langage (où un prompt possède de nombreuses complétions acceptables), la réponse aux questions ouverte, la génération de dialogues et les systèmes de recommandation.

L'étude se concentre sur le paradigme de l'apprentissage en ligne (online learning), se déroulant en cycles $t \in [T]$. À chaque cycle, un adversaire présente une instance $x_t$ et un ensemble de labels acceptables $S_t$. L'apprenant prédit un label $\hat{y}_t$ et subit une perte de 1 si $\hat{y}_t \notin S_t$. L'article analyse ce problème sous trois modèles de feedback distincts :

1. Erreur-inconnue (Mistake-unknown) : L'apprenant ne reçoit qu'un seul label valide $y_t \in S_t$ (choisi par l'adversaire) mais ne sait pas si sa prédiction était correcte.
2. Erreur-connue (Mistake-known) : L'apprenant reçoit un seul label valide $y_t \in S_t$ ainsi qu'un indicateur binaire révélant si sa prédiction $\hat{y}_t$ était une erreur.
3. Valeur-ensemble (Set-valued) : L'intégralité de l'ensemble des labels valides $S_t$ est révélée à l'apprenant.

L'analyse couvre les contextes réalisables (où il existe une hypothèse $h^* \in \mathcal{H}$ telle que $h^*(x_t) = S_t$ pour tout $t$) et agnostiques (où l'apprenant cherche à rivaliser avec la meilleure hypothèse de $\mathcal{H}$ minimisant la perte cumulée).

2. Méthodologie et Caractérisations Combinatoires

Les auteurs introduisent de nouvelles dimensions combinatoires pour caractériser la capacité d'apprentissage des classes d'hypothèses multi-labels $\mathcal{H}$ sous chaque modèle de feedback. Ces dimensions sont définies via des arguments d'éclatement d'arbres (tree-shattering) adaptés à l'information disponible dans chaque modèle.

Dimensions Combinatoires

• Dimension de Littlestone par Valeur-Ensemble ($LD_{set}$) : Définie sur un arbre à valeurs d'ensembles où les nœuds sont étiquetés avec des sous-ensembles de $\mathcal{Y}$. Un arbre est éclaté si, pour chaque chemin de prédictions, il existe une hypothèse cohérente avec les ensembles $S_t$ révélés mais commettant une erreur sur le label prédit.
• Dimension de Littlestone par Erreur-Connue ($LD_{known}$) : Définie sur un arbre multi-label où les nœuds sont étiquetés avec des labels uniques. L'éclatement nécessite la cohérence avec le label unique $y_t$ révélé et une erreur sur la prédiction.
• Dimension de Littlestone par Erreur-Inconnue ($LD_{unknown}$) : Définie en utilisant une fonction de "décalage d'erreur" (mistake offset). Un arbre est $d$-éclaté si le nombre cumulé d'erreurs le long de n'importe quel chemin, plus un décalage pour l'hypothèse, dépasse $d$. Cela rend compte de l'absence de feedback immédiat sur la correction.

Algorithmes

Pour le cas réalisable, les auteurs proposent des Algorithmes Optimaux Standards (SOA) pour chaque modèle de feedback. Ces algorithmes maintèlent un espace de versions (version space) d'hypothèses cohérentes et sélectionnent des prédictions qui minimisent la dimension la plus défavorable de l'espace de versions restant.

• SOA pour Erreur-Inconnue : Maintient un espace de versions et une fonction de décalage, prédisant le label qui minimise la $LD_{unknown}$ maximale des sous-classes résultantes.
• SOA pour Erreur-Connue : Prédit pour minimiser la $LD_{known}$ maximale des sous-classes formées par le bit d'erreur.
• SOA pour Valeur-Ensemble : Prédit pour minimiser la $LD_{set}$ maximale des sous-classes formées par l'ensemble $S_t$ révélé.

3. Résultats Clés

Apprentissage en Ligne Réalisable

L'article fournit une caractérisation complète de la borne d'erreur optimale pour toute classe multi-label $\mathcal{H}$ dans le cadre réalisable :

• Erreur-inconnue : La borne d'erreur optimale est $\min(LD_{unknown}(\mathcal{H}), T)$.
• Erreur-connue : La borne d'erreur optimale est $\min(LD_{known}(\mathcal{H}), T)$.
• Valeur-ensemble : La borne d'erreur optimale est $\min(LD_{set}(\mathcal{H}), T)$.

Ces résultats généralisent les travaux précédents sur les classes finies à des classes d'hypothèses arbitraires (potentiellement infinies). Les auteurs prouvent que $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$, ce qui se produit si et seulement si l'intersection de tous les ensembles de labels des hypothèses pour toute instance est non vide.

Apprentissage en Ligne Agnostique (Bornes de Regret)

Une contribution significative est la démonstration que les taux de regret varient radicalement selon les modèles de feedback dans le cadre agnostique, contrastant avec l'apprentissage à label unique où le regret est typiquement de l'ordre de $\tilde{\Theta}(\sqrt{T})$.

1. Erreur-inconnue : Les auteurs montrent que le regret peut croître de manière linéaire en $T$ ($\Omega(T)$), même pour des classes d'hypothèses simples avec $LD_{unknown}=1$. Cela implique que l'apprentissage réalisable (caractérisé par $LD_{unknown}$) ne garantit pas un regret sous-linéaire dans le cadre agnostique pour ce modèle de feedback.
2. Erreur-connue : L'article établit une borne supérieure de regret sous-linéaire de $O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$. Ceci est obtenu en réduant le problème aux bandits non stochastiques avec conseils d'experts, en utilisant un ensemble d'experts basés sur les SOA.
3. Valeur-ensemble :
   • Pour des classes spécifiques (ex: la classe d'exemple $H_3$), le regret est constant ($O(1)$).
   • Pour les classes générales, le regret est borné par $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$. Notamment, cette borne est indépendante de la taille de l'espace de labels $|\mathcal{Y}|$, ce qui lui permet de s'appliquer à des espaces de labels infinis.

Implications pour l'Apprentissage par Lots (Batch Learning)

Les dimensions combinatoires et les bornes en ligne dérivées impliquent des bornes de complexité d'échantillonnage pour les problèmes de lot correspondants. Les auteurs fournissent les premières bornes supérieures connues pour l'apprentissage par lots sous le modèle de feedback par ensemble complet et améliorent les bornes existantes pour le cas à un seul label correct, passant de classes finies à des classes infinies.

4. Signification et Revendications

L'article affirme fournir la première caractérisation combinatoire complète de l'apprentissage multi-label réalisable en ligne sous trois modèles de feedback distincts. Sa principale signification théorique réside dans la séparation entre l'apprentissage réalisable et agnostique dans le cadre de l'erreur-inconnue, où la dimension de Littlestone standard ne parvient pas à capturer des bornes de regret significatives.

De plus, ce travail met en lumière une structure riche dans l'apprentissage multi-label agnostique :

• Le modèle de feedback modifie fondamentalement les taux de regret réalisables (de linéaire à constant).
• Le modèle de feedback par valeur-ensemble permet un regret constant sur certaines classes et des bornes indépendantes de la dimension pour les classes générales, un phénomène non observé dans l'apprentissage à label unique.
• Les résultats suggèrent que la caractérisation de l'apprentissage multi-label agnostique nécessite des objets combinatoires au-delà de ceux suffisants pour l'apprentissage réalisable.

Les auteurs notent explicitement que leurs définitions de regret diffèrent des travaux antérieurs (ex: Joshi et al. [JLB+25] et Raman et al. [RST24]) afin de mieux s'aligner sur la tâche de prédiction sous-jacente consistant à minimiser l'erreur contre le véritable ensemble de labels acceptables, plutôt que de rivaliser contre une hypothèse qui contient simplement un label révélé spécifique.