Prédiction Conforme Multi-modèle En Ligne avec Rétroaction Structurée par Graphe

Informations Fondamentales

• ID de l'article: 2506.20898
• Titre: Multi-model Online Conformal Prediction with Graph-Structured Feedback
• Auteurs: Erfan Hajihashemi, Yanning Shen (University of California, Irvine)
• Classification: cs.LG
• Date de publication/Conférence: Transactions on Machine Learning Research (10/2025)
• Lien de l'article: https://arxiv.org/abs/2506.20898

Résumé

La prédiction conforme en ligne a démontré sa capacité à construire un ensemble de prédiction pour chaque point de données entrant qui couvre l'étiquette véritable avec une probabilité prédéterminée. Pour faire face aux changements potentiels de distribution, la prédiction conforme multi-modèle en ligne a été introduite pour sélectionner et exploiter différents modèles à partir d'un ensemble de candidats présélectionnés. Parallèlement à la flexibilité accrue, le choix de l'ensemble présélectionné pose également des défis. Un ensemble de candidats incluant un grand nombre de modèles peut augmenter la complexité computationnelle. De plus, l'inclusion de modèles non pertinents avec de mauvaises performances peut affecter négativement les performances et conduire à des ensembles de prédiction inutilement volumineux. Pour résoudre ces défis, nous proposons un nouvel algorithme de prédiction conforme multi-modèle en ligne qui identifie un sous-ensemble de modèles efficaces à chaque étape temporelle en collectant des rétroactions à partir d'un graphe bipartite, qui est affiné lors de la réception de nouvelles données. Un modèle est ensuite sélectionné à partir de ce sous-ensemble pour construire l'ensemble de prédiction, ce qui réduit la complexité computationnelle et les ensembles de prédiction plus petits. De plus, nous démontrons que l'utilisation de la taille de l'ensemble de prédiction comme rétroaction, aux côtés de la perte du modèle, peut améliorer significativement l'efficacité en construisant des ensembles de prédiction plus petits tout en satisfaisant la garantie de couverture requise. Les algorithmes proposés sont prouvés pour assurer une couverture valide et atteindre un regret sous-linéaire. Les expériences sur des ensembles de données réels et synthétiques valident que les méthodes proposées construisent des ensembles de prédiction plus petits et surpassent les approches existantes de prédiction conforme multi-modèle en ligne.

Contexte et Motivation de la Recherche

1. Problème à résoudre: Les méthodes existantes de prédiction conforme multi-modèle en ligne font face à des problèmes de complexité computationnelle élevée et d'ensembles de prédiction trop volumineux lors du traitement des changements de distribution. Les méthodes traditionnelles nécessitent la mise à jour et l'évaluation de tous les modèles candidats, ce qui entraîne une inefficacité lorsque l'ensemble de candidats contient un grand nombre de modèles ou des modèles de faible performance.
2. Importance du problème: Dans les applications critiques pour la sécurité (comme la conduite autonome, le diagnostic médical), une quantification fiable de l'incertitude est nécessaire pour assurer la crédibilité des décisions. La prédiction conforme peut fournir des ensembles de prédiction valides sans dépendre d'hypothèses de distribution, mais elle doit faire face aux changements dynamiques de la distribution des données dans un environnement en ligne.
3. Limitations des méthodes existantes:
   • La complexité computationnelle augmente linéairement avec le nombre de modèles candidats
   • L'inclusion de modèles de faible performance affecte négativement les performances globales
   • Absence de mécanisme efficace de sélection de modèles pour s'adapter dynamiquement aux changements de distribution
4. Motivation de la recherche: Développer un algorithme de prédiction conforme multi-modèle en ligne capable de sélectionner adaptativement un sous-ensemble de modèles efficaces, réduisant la complexité computationnelle et la taille de l'ensemble de prédiction tout en garantissant la couverture.

Contributions Principales

1. Proposition de l'algorithme GMOCP: Conception d'un algorithme de prédiction conforme multi-modèle en ligne basé sur une rétroaction structurée par graphe, identifiant dynamiquement les sous-ensembles de modèles efficaces via un graphe bipartite
2. Construction d'un cadre de génération de graphe adaptatif: Construction et mise à jour dynamique du graphe bipartite basées sur les performances historiques des modèles, réalisant la sélection de modèles en ligne
3. Développement de l'algorithme d'extension EGMOCP: Utilisation de la taille de l'ensemble de prédiction comme signal de rétroaction supplémentaire, améliorant davantage l'efficacité de prédiction
4. Fourniture de garanties théoriques: Preuve de la couverture valide de l'algorithme et des bornes de regret sous-linéaire
5. Validation de l'efficacité sur plusieurs ensembles de données: Réalisation d'ensembles de prédiction plus petits et d'une complexité computationnelle inférieure sur les ensembles de données CIFAR-10C, CIFAR-100C, etc.

Explication Détaillée de la Méthode

Définition de la Tâche

Étant donné les données historiques $\{(X_τ, Y^{true}_τ)\}^{t-1}_{τ=1}$ et la nouvelle entrée $X_t$, construire un ensemble de prédiction $C^m_α(X_t) ⊆ Y$ tel que l'étiquette véritable $Y^{true}_t$ soit contenue dans l'ensemble de prédiction avec une probabilité $1-α$, où $α$ est la probabilité de non-couverture.

Architecture du Modèle

1. Conception de la Structure Bipartite

• Nœuds de modèle: $\{v^{(l)}_1, ..., v^{(l)}_M\}$ représentant M modèles candidats
• Nœuds de sélection: $\{v^{(s)}_1, ..., v^{(s)}_J\}$ représentant J nœuds de sélection
• Contraintes de connexion: Chaque nœud de sélection se connecte à au maximum N nœuds de modèle

2. Algorithme de Génération de Graphe

Probabilité de connexion du nœud de modèle: $p^m_t = (1 - η_e) \frac{w^m_t}{\sum^M_{\bar{m}=1} w^{\bar{m}}_t} + \frac{η_e}{M}$

où $η_e$ est le coefficient d'exploration et $w^m_t$ est le poids du modèle.

3. Mise à Jour du Poids du Modèle

Utilisation de l'estimation de perte par échantillonnage d'importance: $w^m_{t+1} = w^m_t \exp(-ε l^m_t / 2^b)$

où la fonction de perte est: $l^m_t = \frac{L(\bar{α}^m_t, α^m_t)}{q^m_t} I\{m ∈ S_t\}$

4. Mise à Jour Adaptative de la Probabilité de Non-couverture

Utilisation de la descente de gradient en ligne sans échelle: $α^m_{t+1} = α^m_t - η \frac{∇_{α^m_t} L(\bar{α}^m_t, α^m_t)}{\sqrt{\sum^t_{τ=1} \|∇_{α^m_τ} L(\bar{α}^m_τ, α^m_τ)\|^2_2}}$

Points d'Innovation Technique

1. Mécanisme de rétroaction structuré par graphe: Sélection dynamique des sous-ensembles de modèles via un graphe bipartite, évitant la mise à jour de tous les modèles
2. Conception de rétroaction double: EGMOCP considère simultanément la perte de prédiction et la taille de l'ensemble de prédiction comme signaux de rétroaction
3. Équilibre adaptatif exploration-exploitation: Réalisation d'une stratégie d'exploration multi-niveaux via différents coefficients d'exploration

Configuration Expérimentale

Ensembles de Données

1. CIFAR-10C/CIFAR-100C: Contenant 15 types de corruption, 5 niveaux de sévérité
2. TinyImageNet-C: Version corrompue de 200 classes d'ensemble de données
3. Ensemble de données synthétique: 3000 échantillons, 20 classes, simulant les changements de distribution

Métriques d'Évaluation

• Coverage: Pourcentage d'ensembles de prédiction contenant l'étiquette véritable
• Avg Width: Taille moyenne de l'ensemble de prédiction
• Run Time: Temps d'exécution de l'algorithme
• Single Width: Pourcentage d'ensembles de prédiction de taille 1 couvrant correctement

Méthodes de Comparaison

• MOCP: Méthode de base de prédiction conforme multi-modèle en ligne
• COMA: Méthode d'agrégation de modèles conformes en ligne
• Méthodes mono-modèle: ACI, FACI, DECAY, SAOCP

Détails d'Implémentation

• Taux de couverture cible: 90% (α = 0.1)
• Hyperparamètres: ε = 0.5, η = 0.05, β = 0.05
• Nombre d'étapes temporelles: T = 6000
• Taille de lot: 500 échantillons

Résultats Expérimentaux

Résultats Principaux

Dans l'expérience de changement de distribution soudain sur l'ensemble de données CIFAR-100C:

• GMOCP réalise un temps d'exécution plus rapide (amélioration d'environ 50%) et une taille d'ensemble de prédiction similaire par rapport à MOCP
• EGMOCP réduit significativement la taille de l'ensemble de prédiction, passant de 12.63 pour MOCP à 6.18, tout en maintenant le taux de couverture cible de 90%
• Le ratio de largeur unique passe de 22.43% à 29.91%

Expériences d'Ablation

1. Impact des paramètres du graphe: Test de différentes combinaisons de N (nombre de nœuds de modèle) et J (nombre de nœuds de sélection)
2. Stratégies d'exploration: Comparaison de l'effet de différents paramètres de coefficient d'exploration
3. Mécanisme de rétroaction: Vérification de l'efficacité de la rétroaction de taille d'ensemble de prédiction

Étude de Cas

Démonstration via trois configurations d'entraînement de DenseNet121 (120D, 10R, 1R):

• Le modèle haute performance (120D) obtient le poids le plus élevé et la probabilité de sélection
• EGMOCP peut identifier efficacement et favoriser la sélection de modèles de meilleure performance
• La taille de l'ensemble de prédiction est négativement corrélée aux performances du modèle

Découvertes Expérimentales

1. Amélioration de l'efficacité computationnelle: La complexité par étape de GMOCP est O(Nt + JMN), significativement réduite par rapport à O(Mt) de MOCP lorsque N << M
2. Amélioration de la qualité de prédiction: EGMOCP réalise des ensembles de prédiction plus petits via le mécanisme de rétroaction double
3. Vérification de la robustesse: Maintien de performances stables dans divers scénarios de changement de distribution

Travaux Connexes

1. Fondements de la prédiction conforme: Basé sur le cadre classique de Vovk et al., étendu à l'environnement en ligne
2. Prédiction conforme adaptative: Méthode de probabilité de non-couverture variant dans le temps de Gibbs & Candès
3. Approches multi-modèles: Comparaison avec les travaux de Hajihashemi & Shen et Gasparin & Ramdas
4. Théorie de l'apprentissage en ligne: Empruntant les idées de l'apprentissage d'experts et des bandits multi-bras

Conclusion et Discussion

Conclusions Principales

1. Le mécanisme de rétroaction structuré par graphe peut réduire efficacement la complexité computationnelle et améliorer l'efficacité de prédiction
2. La taille de l'ensemble de prédiction comme signal de rétroaction améliore significativement les performances de l'algorithme
3. Les garanties théoriques sont cohérentes avec les résultats expérimentaux, validant l'efficacité de la méthode

Limitations

1. La construction du graphe nécessite un ajustement supplémentaire des hyperparamètres
2. L'amélioration est limitée lorsque la qualité des modèles candidats est similaire
3. L'analyse théorique est basée sur des hypothèses spécifiques de fonction de perte

Directions Futures

1. Explorer des structures de graphe plus complexes et des stratégies de mise à jour
2. Étendre aux tâches de régression et autres méthodes de quantification d'incertitude
3. Étudier l'adaptabilité sous changements de distribution importants

Évaluation Approfondie

Avantages

1. Forte innovativité de la méthode: Le mécanisme de rétroaction structuré par graphe offre une nouvelle perspective pour la sélection multi-modèles
2. Fondations théoriques solides: Preuve rigoureuse de la couverture et des bornes de regret
3. Conception expérimentale complète: Couvrant plusieurs ensembles de données et scénarios de changement de distribution
4. Valeur pratique élevée: Réduction significative de la complexité computationnelle tout en améliorant la qualité de prédiction

Insuffisances

1. Sensibilité aux hyperparamètres: Nécessité d'ajuster plusieurs paramètres liés au graphe
2. Limitation des scénarios applicables: L'avantage n'est pas évident lorsque les différences de qualité des modèles sont faibles
3. Complexité de l'analyse théorique: Le processus de preuve est plutôt complexe, l'applicabilité pratique reste à vérifier

Impact

1. Contribution académique: Fournit une nouvelle voie technique pour le domaine de la quantification d'incertitude en ligne
2. Perspectives d'application: Valeur importante dans les systèmes critiques pour la sécurité nécessitant une prise de décision en temps réel
3. Reproductibilité: Description d'algorithme détaillée et configuration expérimentale claire

Scénarios Applicables

1. Systèmes d'apprentissage en ligne nécessitant une quantification d'incertitude en temps réel
2. Environnements dynamiques confrontés à des changements de distribution
3. Scénarios de fusion multi-modèles avec ressources computationnelles limitées
4. Besoins de prédiction fiable dans les applications critiques pour la sécurité

Références

1. Vovk, V., Gammerman, A., & Shafer, G. (2005). Algorithmic learning in a random world
2. Gibbs, I., & Candès, E. J. (2021). Adaptive conformal inference under distribution shift
3. Hajihashemi, E., & Shen, Y. (2024). Multi-model ensemble conformal prediction in dynamic environments
4. Gasparin, M., & Ramdas, A. (2024). Conformal online model aggregation