Online Learning-to-Defer with Varying Experts

Formulation du problème
L'apprentissage de la mise en deferre (Learning-to-Defer, L2D) est un cadre conçu pour intégrer des modèles prédictifs avec des experts externes (humains ou automatisés) afin d'améliorer la fiabilité du système en acheminant les entrées incertaines ou à haut risque vers des agents plus compétents. Alors que les recherches existantes en L2D opèrent principalement dans des contextes par lots avec des pools d'experts fixes et une supervision complète (observation de toutes les prédictions d'experts durant l'entraînement), les déploiements réels font face à des défis significatifs : les données arrivent de manière séquentielle, la disponibilité des experts fluctue (par exemple, en raison de changements d'équipe ou de contraintes de ressources), et la fiabilité des experts peut dériver au fil du temps. De plus, les systèmes pratiques fonctionnent souvent sous un feedback de type bandit, où l'apprenant n'observe que le résultat de l'action choisie (prédiction ou requête spécifique à un expert) plutôt que la vérité terrain ou la performance de tous les experts disponibles. Cet article comble le fossé entre les hypothèses classiques du L2D et ces réalités dynamiques et en ligne en introduisant le premier cadre L2D en ligne pour la classification multiclasse avec feedback de type bandit et un pool d'experts variant dynamiquement.

Méthodologie
Les auteurs proposent un cadre général où, à chaque round $t$, une entrée augmentée $(x_t, A_t)$ est révélée, composée d'un vecteur de caractéristiques $x_t$ et d'un ensemble d'experts disponibles $A_t$. L'apprenant doit décider soit de prédire une étiquette de classe, soit de mettre en deferre l'un des experts disponibles dans $A_t$. L'interaction suit un contexte semi-adversarial : les entrées peuvent être choisies de manière adversariale, mais les étiquettes sont tirées d'une distribution fixe (bien que inconnue) conditionnelle à l'entrée.

Les contributions méthodologiques principales incluent :

1. Perte de mise en deferre réelle et surrogate : Les auteurs définissent une perte de mise en deferre réelle $\ell_{def}$ qui prend en compte les coûts de mauvaise classification et les coûts de requête d'expert. Puisque cette perte est non différentiable, ils introduisent une perte surrogate convexe $\Phi_{def}$ qui étend les surrogates basés sur les scores standards (comme la perte charnière contrainte) au contexte en ligne avec experts variables. Ce surrogate est conçu pour ne pas être affecté par les scores des experts indisponibles.
2. Bornes de cohérence-H pour l'apprentissage en ligne : Une étape théorique significative est l'extension des bornes de cohérence-H de l'apprentissage par lots au contexte en ligne. Les auteurs prouvent que la minimisation du regret de mise en deferre surrogate dans le cadre en ligne garantit un regret de mise en deferre réel borné, à condition que le surrogate sous-jacent admette une borne de cohérence-H par rapport à la perte zéro-un.
3. Conception de l'algorithme : L'algorithme proposé (Algorithme 1) utilise la Descente de Gradient en Ligne (OGD) avec des gradients projetés. Pour gérer la contrainte selon laquelle la somme des scores pour les étiquettes disponibles doit être nulle (requise pour la perte charnière contrainte), l'algorithme projette la matrice de poids sur un sous-espace réalisable $K_{A_t}$ spécifique à l'ensemble actuel d'experts disponibles. Cette projection préserve les prédictions de l'hypothèse sur l'ensemble d'étiquettes disponibles. L'algorithme intègre un taux d'exploration $\gamma_t$ pour gérer le feedback de type bandit, estimant la fonction de perte basée sur le résultat observé de l'action échantillonnée.

Contributions clés
L'article revendique quatre contributions principales :

1. Premier cadre L2D en ligne : Il introduit le premier cadre pour l'apprentissage de la mise en deferre en ligne sous feedback de type bandit où à la fois la distribution des données et le pool d'experts peuvent varier au fil du temps.
2. Extension théorique : Il étend la notion de bornes de cohérence-H au contexte en ligne, une propriété précédemment limitée aux analyses d'apprentissage par lots.
3. Garanties de regret : L'algorithme proposé atteint une borne de regret de $O((n + n_e)T^{2/3})$ dans le cas général, où $n$ est le nombre de classes et $n_e$ le nombre d'experts distincts observés. Sous une hypothèse de faible bruit (presque réalisable), cela s'améliore en $O((n + n_e)\sqrt{T})$.
4. Validation empirique : L'approche est validée sur des ensembles de données synthétiques et réels (Reuters4 et CIFAR10H), démontrant sa capacité à s'adapter à une disponibilité variable des experts et à une expertise dérivante.

Résultats
Des expériences ont été menées dans trois régimes de complexité croissante : (1) disponibilité et expertise fixes, (2) disponibilité dérivante avec expertise fixe, et (3) contextes entièrement dynamiques avec à la fois disponibilité et expertise dérivantes.

• Données synthétiques : L'algorithme a appris avec succès la frontière optimale entre la prédiction et la mise en deferre, acheminant systématiquement les entrées vers les experts disponibles les plus compétents. Il a maintenu une faible perte de mise en deferre et une haute précision même lorsque les zones de compétence des experts ont changé au fil du temps.
• Données réelles (Reuters4) : Dans le contexte le plus difficile (disponibilité et expertise dérivantes), la méthode a suivi efficacement les zones de compétence des experts en mouvement. Elle a mis en deferre avec une fréquence élevée vers les experts actuellement compétents, préservant une calibration stable et atteignant une précision de tâche comparable aux références à expertise fixe.
• CIFAR10H : En utilisant un prédicteur WideResNet et des experts annotés par des humains, la méthode a surpassé une référence basée sur la confiance qui met en deferre de manière uniforme au hasard. La politique apprise a atteint une perte de mise en deferre plus faible et une précision plus élevée, indiquant qu'elle a appris à acheminer les exemples vers les experts les plus adaptés plutôt que de mettre en deferre de manière indiscriminée.

Signification
L'article se positionne comme une étape fondamentale vers la viabilité des systèmes d'apprentissage de la mise en deferre pour des environnements réels non stationnaires. En allant au-delà de l'hypothèse de pools d'experts fixes et de supervision complète, les auteurs démontrent que des méthodes basées sur des surrogates cohérents peuvent être rendues robustes face aux environnements adversariaux et à la fiabilité variable des experts. L'établissement théorique de la cohérence-H dans le contexte en ligne fournit une garantie rigoureuse selon laquelle la minimisation de la perte surrogate conduit à la minimisation du regret de mise en deferre réel, comblant un fossé critique entre les garanties théoriques du L2D et les exigences pratiques des données en flux continu et des systèmes d'experts dynamiques.