Online Conformal Prediction Beyond Feedback

Formulation du problème : Prédiction Conforme en Ligne au-delà du Feedback

La quantification de l'incertitude est cruciale pour le déploiement de l'apprentissage automatique dans des applications critiques pour la sécurité. La Prédiction Conforme en Ligne (OCP - Online Conformal Prediction) offre un cadre théoriquement fondé pour générer des ensembles de prédiction garantissant que la véritable étiquette est incluse avec une fréquence spécifiée par l'utilisateur, même pour des flux de données non-i.i.d. et des classifieurs boîtes noires. Cependant, les méthodes OCP standard reposent sur une boucle de rétroaction (feedback) : après avoir émis un ensemble de prédiction, l'algorithme reçoit un feedback (soit l'étiquette réelle, soit un signal de couverture) pour ajuster les ensembles futurs, compensant ainsi les erreurs de couverture passées.

Cet article traite d'un scénario où un tel feedback est indisponible ou prohibitif. Dans de nombreux scénarios critiques pour la sécurité, tels que les sondes latentes pour les Grands Modèles de Langage (LLM), un algorithme peut devoir classer des entrées dans des catégories de sécurité. Si la sonde s'abstient (interroge un humain ou un système plus puissant), l'étiquette peut éventuellement devenir disponible. Cependant, pour les entrées pour lesquelles la sonde prend une décision déployée, l'étiquette n'est jamais observée. Cela crée un scénario « au-delà du feedback » : l'apprenant doit choisir entre produire un ensemble de prédiction ou interroger l'étiquette correcte, mais ne peut pas faire les deux. Par conséquent, l'apprenant n'observe jamais si un ensemble de prédiction déployé était correct, empêissant les mécanismes de compensation standard utilisés dans les méthodes OCP existantes.

Méthodologie : OCP avec Requêtes (OCPQ)

Les auteurs proposent l'OCP avec Requêtes (OCPQ - Online Conformal Prediction with Queries), une méthode conçue pour ce protocole au-delà du feedback. L'approche se déroule en deux étapes principales :

1. Réduction à la surveillance partielle (Partial Monitoring) : Le problème est réduit à un jeu de surveillance partielle à horizon fini. Les « bras » du jeu consistent en un ensemble fini de seuils de prédiction $M \subset [0, 1]$ et une action de requête distincte.

   • Action de Prédiction : Sélectionner un seuil $m \in M$ génère un ensemble de prédiction $\Gamma_C(x_t, m)$ basé sur un classifieur boîte noire $C$. Cette action ne produit aucune observation (feedback nul $\perp$) et aucun reward direct.
   • Action de Requête : Sélectionner l'action de requête révèle la véritable étiquette $y_t$ mais ne produit aucun ensemble de prédiction et génère un reward de zéro.
   • Structure de Récompense (Reward) : L'algorithme définit une fonction de récompense auxiliaire $R(m, t)$. Si l'étiquette réelle est couverte par l'ensemble de prédiction ($y_t \in \Gamma_C(x_t, m)$), la récompense est $1 - m(1-\beta)$, où $\beta$ est un paramètre défini par l'utilisateur contrôlant le compromis entre couverture et efficacité. Si l'étiquette n'est pas couverte, la récompense est 0. L'action de requête génère toujours 0 de récompense. Cette structure incite l'apprenant à sélectionner des seuils serrés (petit $m$) tout en maintenant la couverture.

2. Conception de l'Algorithme : L'OCPQ adapte le prévoyeur exponentiellement pondéré à étiquettes efficaces de Cesa-Bianchi, Lugosi et Stoltz (2004).

   • À chaque tour $t$, l'algorithme effectue une requête avec une probabilité fixe $\epsilon$.
   • Si une requête est effectuée, la véritable étiquette $y_t$ est observée. L'algorithme met ensuite à jour les estimations de récompense cumulée $\hat{Z}_{m,t}$ pour tous les seuils $m \in M$ en utilisant un schéma de pondération par probabilité inverse, reconstruisant ainsi la récompense qui aurait été obtenue si une prédiction avait été faite.
   • Si aucune requête n'est faite, l'algorithme échantillonne un seuil $m_t$ à partir d'une distribution exponentiellement pondérée basée sur les estimations actuelles $\hat{Z}_{m,t}$ et produit l'ensemble de prédiction correspondant. Aucun feedback n'est reçu.

Résultats Théoriques

L'article établit des garanties à horizon fini pour l'OCPQ sous un flux de données adversaire de type « oblivious » de longueur $T$ :

• Regret : Le regret attendu par rapport au meilleur seuil fixe a posteriori est de $O(T^{2/3})$. Plus précisément, avec $\epsilon = T^{-1/3}$ et $\eta = T^{-2/3}\sqrt{\ln|M|}$, le regret est borné par $T^{2/3}(2\sqrt{\ln|M|} + 1)$. Les auteurs notent que ce taux est asymptotiquement optimal pour cette classe de jeux de surveillance partielle.
• Couverture : Le taux de couverture attendu $p_{cover}$ satisfait :
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  Cela garantit que la couverture approche la cible définie par l'utilisateur $\beta$ à mesure que $T$ augmente.
• Taux de Requête : L'algorithme requête l'étiquette sur seulement une fraction attendue de $T^{-1/3}$ des tours.
• Bornes de Haute Probabilité : L'article dérive également des bornes de haute probabilité pour le regret et la couverture, démontrant que la variance de la performance de l'algorithme est contrôlée et ne présente pas de comportement pathologique.

Résultats Empiriques

Des expériences ont été menées sur des jeux de données réels pour valider l'approche :

• Décalage de Distribution (Distribution Shift) : L'OCPQ a été testé sur des benchmarks standards (MNIST, CIFAR-10, CIFAR-100) où la distribution d'entraînement différait de la distribution de test (par exemple, MNIST vers USPS, ou MNIST vers MNIST-C). Les résultats ont montré que le compromis couverture-efficacité pouvait être contrôlé via le paramètre $\beta$. La couverture empirique a systématiquement dépassé la borne théorique inférieure.
• Surveillance de la Sécurité des LLM : La méthode a été appliquée à la surveillance de la sécurité des prompts de LLM en utilisant le dataset WildGuardMix, qui inclut des prompts tant originaux qu'adversairement réécrits. La précision du classifieur de base chutait significativement sur les prompts adversaires, pourtant l'OCPQ maintenait une couverture supérieure à la borne théorique tout en gardant des ensembles de prédiction informatifs.
• Comparaison : Comparé à l'Inférence Conforme Adaptative (ACI), qui suppose un feedback complet, l'OCPQ a atteint des frontières de couverture-efficacité comparables malgré l'utilisation de beaucoup moins d'informations (ne requêtant que ~5 % des tours).

Signification et Contributions

L'article revendique les contributions suivantes :

1. Nouveau Protocole : Il formule l'OCP dans un contexte « au-delà du feedback » où les prédictions déployées ne sont jamais évaluées, un scénario courant dans les applications critiques pour la sécurité où les étiquettes ne sont disponibles que pour les requêtes d'abstention.
2. Réduction Algorithmique : Il réduit ce problème à un jeu de surveillance partielle et adapte les techniques d'apprentissage adversaire à étiquettes efficaces pour le résoudre, en modifiant spécifiquement le prévoyeur pour traiter les requêtes comme des actions distinctes qui remplacent, plutôt que de suivre, les prédictions.
3. Garanties Théoriques : Il fournit des garanties de regret attendu et de couverture à horizon fini pour l'OCP dans ce contexte, montrant qu'une quantification de l'incertitude valide est possible avec seulement $O(T^{-1/3})$ requêtes d'étiquettes.
4. Efficacité Pratique : Les expériences démontrent qu'une supervision parcimonieuse (requêtes aléatoires) est suffisante pour maintenir des compromis de couverture et d'efficacité utiles, même sous des décalages de distribution adversaires, sans nécessiter de feedback provenant des prédictions déployées.

Les auteurs notent que bien que la méthode soit conservatrice (la couverture empirique dépassant souvent la borne), cela est une conséquence des hypothèses faibles requises pour la formulation du jeu de surveillance partielle. Les travaux futurs pourraient explorer des méthodes moins conservatrices ou des extensions aux adversaires adaptatifs.