Deferral Multi-Expert avec Budget

Informations Fondamentales

• ID de l'article: 2510.26706
• Titre: Budgeted Multiple-Expert Deferral
• Auteurs: Giulia DeSalvo (Google DeepMind), Clara Mohri (Harvard University), Mehryar Mohri (Google Research & Courant Institute), Yutao Zhong (Google Research)
• Classification: cs.LG, stat.ML
• Date de publication: 30 octobre 2025 (prépublication arXiv)
• Lien de l'article: https://arxiv.org/abs/2510.26706

Résumé

Apprendre à reporter les prédictions incertaines à des experts coûteux est une stratégie puissante pour améliorer la précision et l'efficacité des systèmes d'apprentissage automatique. Cependant, les procédures d'entraînement des algorithmes de report standard nécessitent généralement d'interroger tous les experts pour chaque instance d'entraînement, ce qui devient extrêmement coûteux lorsque les requêtes d'experts génèrent des coûts computationnels ou de ressources significatifs, contredisant l'objectif fondamental du report : limiter l'utilisation inutile d'experts. Pour surmonter ce défi, cet article introduit le cadre de report avec budget, conçu pour entraîner des algorithmes de report efficaces tout en minimisant le coût des requêtes d'experts pendant l'entraînement.

Contexte et Motivation de la Recherche

Définition du Problème

L'apprentissage traditionnel du report multi-expert (Learning to Defer) fait face à une contradiction fondamentale :

1. Objectif fondamental : réduire les coûts en reportant sélectivement les tâches de prédiction à des experts
2. Réalité de l'entraînement : la procédure d'entraînement standard nécessite d'interroger tous les experts pour chaque échantillon d'entraînement, avec un coût total de neT (nombre d'experts × nombre d'échantillons d'entraînement)
3. Paradoxe des coûts : le processus d'entraînement lui-même contredit l'intention de contrôle des coûts

Importance de la Recherche

• Besoins d'applications pratiques : dans les scénarios impliquant des ressources coûteuses telles que les grands modèles de langage ou les experts humains, les coûts d'entraînement peuvent être extrêmement élevés
• Problèmes d'évolutivité : à mesure que le nombre d'experts augmente, le coût d'entraînement croît linéairement, limitant l'utilité pratique de la méthode
• Environnements avec ressources limitées : dans les environnements où les ressources informatiques sont limitées, les méthodes existantes sont difficiles à déployer

Limitations des Méthodes Existantes

1. Hypothèse de requête complète : les méthodes existantes supposent que les prédictions et les informations de coût de tous les experts peuvent être obtenues sans frais
2. Déconnexion entre théorie et pratique : l'analyse théorique ignore les coûts de requête pendant la phase d'entraînement
3. Mauvaise extensibilité : incapacité à traiter efficacement les grands ensembles d'experts

Contributions Principales

1. Proposition du cadre de report avec budget : première étude systématique du contrôle des coûts de requête d'experts pendant l'entraînement
2. Conception d'algorithmes en deux étapes :
   • Algorithme de report avec budget en deux étapes (Sections 3-5)
   • Algorithme de report avec budget en une étape (Appendice E)
3. Garanties théoriques :
   • Bornes de généralisation : garanties de performance comparables aux méthodes standard
   • Complexité d'étiquetage : réduction de O(T) à Õ(√T) dans le cas réalisable, pouvant atteindre O(log T)
4. Validation expérimentale : réalisation d'un taux de requête d'expert inférieur à 40% sur plusieurs ensembles de données, tout en maintenant la précision des prédictions

Détails de la Méthode

Définition de la Tâche

Configuration en deux étapes :

• Espace d'entrée : X, Espace d'étiquettes : Y = n
• Ensemble d'experts : {g₁, ..., gₙₑ}, chaque expert gⱼ: X × Y → ℝ
• Fonction de routage : r ∈ R, sélectionnant l'expert r(x) = argmax_k r(x,k)
• Fonction de coût : cₖ(x,y), généralement une perte 0-1

Objectif : minimiser la perte de report en deux étapes

L_def(r,x,y,c) = Σₖ cₖ(x,y)𝟙_{r(x)=k}

Architecture Algorithmique Principale

Algorithme 1 : Algorithme de Report avec Budget en Deux Étapes

Innovation clé : décomposition de la décision en deux parties

1. Sélection d'expert : sélection de l'expert k avec probabilité qₜ,ₖ
2. Décision de requête : interrogation du coût de l'expert sélectionné avec probabilité pₜ,ₖ

Flux de l'algorithme :

pour t = 1 à T:
    recevoir (xₜ, yₜ)
    calculer le vecteur de probabilité de requête pₜ ← SAMPLING-PROBS(...)
    sélectionner l'expert kₜ ~ q_t
    interroger le coût cₜ,ₖₜ avec probabilité pₜ,ₖₜ
    mettre à jour l'ensemble d'entraînement Sₜ (avec poids d'importance 1/(qₜ,ₖₜpₜ,ₖₜ))
    mettre à jour la fonction de routage rₜ

Algorithme 2 : Sous-programme SAMPLING-PROBS

Maintenance de l'espace des versions :

Rₜ₊₁ = {r ∈ Rₜ : Eₜ(r) ≤ E*ₜ + Δₜ}

Calcul de la probabilité de requête :

pₜ,ₖ = max_{r,r'∈Rₜ} {ℓ(r,xₜ,k) - ℓ(r',xₜ,k)}

Philosophie de conception : prioriser l'interrogation des paires expert-instance présentant le plus grand désaccord dans l'espace des versions actuel

Points d'Innovation Technique

1. Stratégie de requête adaptative : ajustement dynamique des probabilités de requête en fonction du désaccord des hypothèses
2. Estimation par pondération d'importance : garantie d'estimation sans biais via le poids 1/(qₜ,ₖpₜ,ₖ)
3. Élagage de l'espace des versions : élimination progressive des hypothèses sous-optimales, concentration sur les régions de haute incertitude
4. Extension des outils théoriques :
   • Asymétrie de pente (Slope Asymmetry)
   • Mesure de distance d'hypothèse
   • Coefficient de désaccord généralisé

Analyse Théorique

Garanties de Généralisation

Théorème 1 (Borne de généralisation en deux étapes) : Avec une probabilité d'au moins 1-δ, l'hypothèse apprise rₜ satisfait :

E(rₜ) - E(r*) ≤ 2Δₜ₋₁

où Δₜ = √(q²·8/t·log(2t(t+1)|R|²/δ)), q = 1/q_min + 1

Complexité d'Étiquetage

Théorème 6 (Borne de complexité d'étiquetage) : La borne supérieure du nombre de requêtes attendues est :

4θ·Kℓ·(E*ₜ + O((1/q_min + 1)√T log(|R|T/δ)))

Améliorations clés :

• Cas réalisable : réduction de O(neT) à Õ(√T)
• Utilisation de l'inégalité de Freedman peut atteindre O(log T)

Configuration Expérimentale

Ensembles de Données

Utilisation de 10 ensembles de données de référence :

• Classification binaire : cod-rna, covtype, HIGGS, phishing, shuttle, skin
• Classification multi-classe : connect, dna, letter, pendigits

Configuration des Experts

• Nombre d'experts : égal au nombre de classes n
• Définition d'expert : l'expert gₖ est parfaitement correct sur la classe k, prédisant aléatoirement sur les autres classes
• Fonction de coût : perte 0-1 cₖ(x,y) = 𝟙_{gₖ(x)≠y}

Métriques d'Évaluation

• Précision du système : valeur moyenne de 1 - L_def(h,x,y) sur l'ensemble de test
• Efficacité des requêtes : nombre cumulé de requêtes d'experts vs. nombre de requêtes disponibles

Détails d'Implémentation

• Classe d'hypothèse : modèle de régression logistique (régularisation L2)
• Fonction de perte : perte logistique multinomiale
• Répétitions expérimentales : 5 divisions aléatoires pour chaque ensemble de données

Résultats Expérimentaux

Résultats Principaux

Efficacité des requêtes :

• Ensembles de données de classification binaire : taux de requête réduit à 35-40%
• Ensembles de données de classification multi-classe : taux de requête réduit à moins de 30%
• Effet du nombre d'experts : plus le nombre d'experts est élevé, plus l'amélioration d'efficacité est significative (meilleur résultat sur l'ensemble de données letter avec 26 experts)

Maintien de la précision :

• Précision du système comparable à la méthode standard sur tous les ensembles de données
• Barres d'erreur extrêmement petites sur les ensembles de données de classification binaire, indiquant une stabilité des résultats
• Certaines fluctuations sur les ensembles de données multi-classe, mais tendance générale cohérente

Découvertes Clés

1. Vérification de l'évolutivité : l'avantage de la méthode avec budget devient plus apparent à mesure que le nombre d'experts augmente
2. Analyse de stabilité : les « oscillations » dans le processus d'apprentissage en ligne sont une manifestation normale du caractère aléatoire de l'algorithme
3. Vérification théorique : les résultats expérimentaux soutiennent que les composants clés de l'analyse théorique (θ, Kℓ, E*) ont un impact limité

Travaux Connexes

Domaine du Report d'Apprentissage

• Méthodes en une étape : Mozannar & Sontag (2020), Verma & Nalisnick (2022)
• Méthodes multi-étapes : Mao et al. (2023a), études de garanties de cohérence
• Développement théorique : bornes de cohérence H, cohérence de Bayes

Apprentissage Actif

• Algorithme IWAL : apprentissage actif pondéré par importance de Beygelzimer et al. (2009)
• Apprentissage actif régional : Cortes et al. (2019a,b, 2020)

Apprentissage avec Contraintes de Budget

• Reid et al. (2024) : approche par machine à bras contextuels pour le cas d'un seul expert
• Limitations : difficile à étendre à plusieurs experts, hypothèses trop strictes

Conclusion et Discussion

Conclusions Principales

1. Preuve de faisabilité : il est possible de réduire considérablement les coûts d'entraînement tout en maintenant les performances des algorithmes de report
2. Percée théorique : première fourniture de garanties théoriques rigoureuses pour le problème du report avec budget
3. Valeur pratique : rend les stratégies de report plus viables dans les environnements aux ressources limitées

Limitations

1. Configuration des experts : la configuration des experts dans les expériences est relativement simplifiée ; dans les applications réelles, les experts peuvent être plus complexes
2. Fonction de coût : considération principale de la perte 0-1 ; d'autres structures de coûts nécessitent une vérification supplémentaire
3. Limitation de la classe d'hypothèse : l'analyse théorique est basée sur une classe d'hypothèse finie ; les classes d'hypothèse infinies nécessitent une analyse par nombre de couverture

Directions Futures

1. Stratégies de requête adaptatives : utilisation des informations structurelles entre les échantillons d'entraînement
2. Disponibilité dynamique des experts : traitement des scénarios où les experts changent dynamiquement
3. Intégration de l'apprentissage par renforcement : application aux scénarios de décision séquentielle ou interactive

Évaluation Approfondie

Points Forts

1. Importance du problème : résout un problème pratique fondamental dans l'apprentissage du report
2. Rigueur théorique : fournit un cadre d'analyse théorique complet, incluant les bornes de généralisation et la complexité d'étiquetage
3. Innovation algorithmique : adaptation ingénieuse des idées d'apprentissage actif au scénario du report
4. Suffisance expérimentale : validation de l'efficacité de la méthode sur plusieurs ensembles de données

Insuffisances

1. Limitations de la configuration expérimentale : la configuration des experts est relativement artificielle et peut différer des scénarios d'application réels
2. Baselines de comparaison uniques : comparaison principalement avec les méthodes de report standard, manque de comparaison avec d'autres méthodes avec contraintes de budget
3. Analyse insuffisante de la complexité computationnelle : analyse insuffisante des frais de calcul de l'algorithme

Impact

1. Contribution académique : ouvre une nouvelle direction de recherche dans le domaine du report d'apprentissage
2. Valeur pratique : importance significative pour les applications pratiques impliquant des experts coûteux
3. Valeur théorique : extension de la théorie de l'apprentissage actif à de nouveaux scénarios d'application

Scénarios d'Application

1. Report de grands modèles de langage : prise de décisions de report sensibles aux coûts entre modèles de différentes tailles
2. Systèmes de diagnostic médical : allocation des tâches de diagnostic entre différents spécialistes
3. Réseaux de capteurs : prise de décisions de collecte de données entre capteurs de capacités différentes

Références

Cet article cite des travaux importants dans les domaines du report d'apprentissage, de l'apprentissage actif et des machines à bras multi-armés, notamment :

• Mao et al. (2023a, 2024a) : fondements théoriques du report multi-expert
• Beygelzimer et al. (2009) : idée de pondération par importance de l'algorithme IWAL
• Reid et al. (2024) : travaux pionniers sur le report avec contraintes de budget

Évaluation Générale : Ceci est un article de haute qualité en théorie de l'apprentissage automatique qui résout un problème pratique important dans le report d'apprentissage, fournissant une analyse théorique rigoureuse et une validation expérimentale convaincante. La principale contribution de l'article réside dans l'étude systématique pour la première fois du contrôle des coûts de requête d'experts pendant la phase d'entraînement, jetant les bases importantes pour les applications pratiques dans ce domaine.