Minimizing Human Intervention in Online Classification

1. Définition du problème

L'article aborde le défi de l'entraînement ou du fine-tuning de systèmes de classification basés sur des modèles de langage de grande taille (LLM) (par exemple, pour la réponse aux questions ou le support client) où le retour d'information d'experts humains est coûteux. L'objectif est de concevoir un agent d'apprentissage en ligne qui minimise le coût cumulatif des interactions avec un expert tout en maintenant une haute précision.

Cadre formel :

• Entrée : À chaque tour $t$, un agent reçoit un vecteur d'embedding de requête $q_t \in \mathbb{R}^d$ tiré i.i.d. d'une distribution inconnue $\mu$.
• Étiquettes : Il existe $N$ étiquettes latentes. La politique d'étiquetage de l'expert est définie par une partition de l'espace d'embedding en régions $C_1, \dots, C_N$ (souvent modélisées comme une tessellation de Voronoï basée sur des points « graines » inconnus).
• Actions : L'agent doit attribuer une étiquette à $q_t$. Il a deux choix :
  1. Deviner : Prédire une étiquette immédiatement. Si c'est correct, il gagne une récompense ; si c'est incorrect, il subit une pénalité. Crucialement, aucune vérité terrain n'est révélée si l'agent devine.
  2. Consulter l'expert : Demander la vraie étiquette. Cela engendre un coût (récompense négative) mais révèle la vérité terrain, qui est ajoutée à l'ensemble de données de l'agent.
• Objectif : Minimiser le Regret, défini comme la différence entre la récompense cumulative d'un Oracle (qui connaît la vraie partition et ne fait jamais d'erreur) et la récompense cumulative de l'agent. Le regret s'accumule à la fois à partir des appels à l'expert et des devinettes incorrectes.

2. Méthodologie

Les auteurs proposent trois algorithmes adaptés à différents régimes de l'horizon temporel $T$ (nombre total de requêtes) et de la dimension d'embedding $d$.

A. Classifieur Conservateur basé sur l'Enveloppe Convexe (CHC)

• Régime cible : Horizons longs ($T \geq e^d$).
• Mécanisme : L'agent maintient un ensemble de requêtes « étiquetées par l'expert » pour chaque classe. Il construit l'enveloppe convexe (ou l'enveloppe convexe sphérique pour les sphères unitaires) de ces points pour chaque classe.
• Règle de décision :
  • Si une nouvelle requête $q_t$ tombe à l'intérieur de l'enveloppe convexe de la classe $i$, l'agent prédit l'étiquette $i$.
  • Si $q_t$ tombe à l'extérieur de toutes les enveloppes connues, l'agent appelle l'expert.
• Propriété clé : Le CHC est « conservateur » ; il ne fait jamais de prédiction incorrecte car l'enveloppe convexe des points étiquetés $i$ est garantie d'être un sous-ensemble de la vraie région $C_i$ (en supposant des régions convexes).
• Complexité : Vérifier si un point est dans une enveloppe convexe est formulé comme un programme linéaire, soluble en temps polynomial.

B. Classifieur basé sur le Centre (CC)

• Régime cible : Horizons courts ($T \leq e^d$) avec des hypothèses distributionnelles spécifiques (mélanges sous-gaussiens avec des centres bien séparés).
• Mécanisme :
  • Phase 1 (Exploration) : Interroger l'expert jusqu'à ce que chaque étiquette ait été observée suffisamment pour estimer avec précision le « centre » (graine) de chaque classe.
  • Phase 2 (Engagement) : Arrêter d'interroger l'expert. Prédire l'étiquette du centre estimé le plus proche.
• Hypothèse : Nécessite que les vrais centres de classe soient suffisamment séparés par rapport à la variance du bruit et à la dimension.

C. Classifieur Généralisé basé sur l'Enveloppe Convexe (GHC)

• Régime cible : Paramètres pratiques à haute dimension (comblant l'écart entre CHC et CC).
• Mécanisme : Une extension du CHC qui introduit un paramètre de seuil ajustable $\tau \in [0, 1]$.
• Règle de décision : Au lieu d'attendre strictement qu'une requête soit à l'intérieur d'une enveloppe, l'agent devine l'étiquette $i$ si la distance de $q_t$ à l'enveloppe de la classe $i$ est significativement plus petite que la distance à toute autre enveloppe (spécifiquement, $d(q_t, \hat{C}_i) \leq \tau \cdot \min_{j \neq i} d(q_t, \hat{C}_j)$).
• Compromis :
  • $\tau = 0$ : Équivalent au CHC (conservateur, pas d'erreurs).
  • $\tau = 1$ : Devinettes agressives (ne consulte jamais l'expert une fois les enveloppes non vides).
  • Le réglage de $\tau$ permet d'équilibrer le coût des appels à l'expert contre le risque de devinettes incorrectes, particulièrement efficace lorsque la distribution des données est concentrée autour des graines de classe.

3. Contributions clés

Garanties théoriques

• Bornes de regret du CHC : Les auteurs prouvent que le CHC atteint un regret de $O(\log^d T)$ pour des partitions arbitraires de polytopes convexes. Cette borne est sans distribution et robuste.
  • Pour $d=1$, le CHC est prouvé minimax optimal, correspondant à la borne inférieure de $\Omega(\log T)$.
• Bornes de regret du CC : Pour des mélanges sous-gaussiens avec $T \leq e^d$, le CC atteint un regret proportionnel à $N \log N$ (où $N$ est le nombre d'étiquettes), à condition que les centres soient bien séparés.
• Bornes inférieures : L'article établit que dans des contextes adversariaux, un regret linéaire est inévitable, justifiant l'hypothèse i.i.d.

Innovations algorithmiques

• Approche géométrique : Le travail exploite la géométrie convexe (enveloppes convexes, drapeaux de polytopes, projections gnomoniques) pour dériver des bornes sans distribution, une approche novatrice dans la classification en ligne avec retour partiel.
• Extension pratique (GHC) : Le GHC comble l'écart théorique entre le CHC « sûr mais lent » et le CC « rapide mais risqué », offrant une solution pratique pour les embeddings de LLM à haute dimension où $T$ peut ne pas être exponentiellement grand par rapport à $d$.

Validation empirique

• Ensembles de données : Évalué sur des données synthétiques et des ensembles de données réels de réponse aux questions (Quora Question Groups, ComQA, CQADupStack).
• Embeddings : Utilisation de modèles d'embedding de texte de pointe (Nomic, E5, Mistral_E5) avec des dimensions allant de 784 à 4 096.
• Résultats :
  • Le GHC surpasse les bases de référence (Séquentiel k-Means, Perceptron Multiclasse Actif et CC standard) dans tous les contextes.
  • Bénéfice de la haute dimension : Contre-intuitivement, des embeddings de plus haute dimension (par exemple, Mistral_E5) ont conduit à un regret plus faible, probablement dû à une meilleure séparation des régions de classe dans les hautes dimensions.
  • Réglage du seuil : Les performances optimales ont été obtenues avec des seuils élevés ($\tau \approx 0.9$), indiquant que dans les espaces de haute dimension, la géométrie permet des devinettes agressives avec une erreur minimale.

4. Importance et impact

• Réduction des coûts : Le cadre fournit une méthode fondée pour réduire drastiquement la dépendance aux annotateurs humains coûteux lors du déploiement de systèmes basés sur des LLM.
• Rigueur théorique : Il va au-delà de l'apprentissage actif heuristique en fournissant des bornes de regret rigoureuses, sans distribution, qui tiennent compte de la structure géométrique des espaces d'embedding.
• Évolutivité : Les algorithmes proposés sont efficaces sur le plan computationnel (temps polynomial) et évolutifs vers les espaces de haute dimension typiques du NLP moderne, les rendant viables pour un déploiement réel.
• Voies futures : Ce travail ouvre des perspectives pour minimiser l'intervention humaine dans d'autres domaines de l'adaptation des modèles de base, tels que l'apprentissage par renforcement à partir de retours humains (RLHF) et le fine-tuning continu.

En résumé, l'article démontre avec succès qu'en exploitant les propriétés géométriques des espaces d'embedding, il est possible de concevoir des classificateurs en ligne qui apprennent efficacement à partir d'un retour d'expert limité, atteignant des garanties de regret quasi optimales tout en réduisant considérablement les coûts d'intervention humaine.