Approximate full conformal prediction in an RKHS

Résumé Technique : Prédiction Conforme Complète Approchée dans un RKHS

Énoncé du Problème
La prédiction conforme complète est un cadre de distribution-free qui construit des régions de prédiction de confiance avec une couverture garantie pour un large éventail d'estimateurs. Cependant, son application pratique est sévèrement limitée par l'intraitabilité computationnelle. Pour calculer la région de prédiction conforme complète pour une nouvelle entrée $X_{n+1}$, il faut évaluer un score de non-conformité pour chaque candidat de sortie $y \in \mathcal{Y}$ possible. Puisque le prédicteur sous-jacent $\hat{f}_{D_y}$ doit être réentraîné pour chaque candidat $y$ (où $D_y$ inclut le nouveau point $(X_{n+1}, y)$), cela nécessite l'entraînement d'un nombre infini d'estimateurs lorsque $\mathcal{Y} = \mathbb{R}$.

Les alternatives existantes, telles que la prédiction conforme scindée (split-conformal) ou croisée (cross-conformal), réduisent les coûts de calcul en entraînant un nombre fixe de prédicteurs. Cependant, ces méthodes entraînent une perte d'information en écartant des données lors de l'entraînement ou de la division, ce qui résulte souvent en des régions de prédiction plus larges et moins informatives. D'autres approches reposant sur des solutions en forme close (par exemple, pour la régression ridge) ou des formes spécifiques de p-valeurs sont limitées à des contextes étroits et ne se généralisent pas à des fonctions de perte arbitraires ou à des espaces de Hilbert à noyau reproduisant (RKHS).

Méthodologie
Les auteurs proposent une stratégie générique pour approximer efficacement la région de prédiction conforme complète dans un RKHS sans diviser les données. Le cœur de la méthodologie implique :

1. Prédicteurs Approchés : Au lieu de réentraîner le prédicteur pour chaque candidat $y$, la méthode approxime le prédicteur $\hat{f}_{D_y}$ en utilisant un prédicteur fixe $\hat{f}_{D_z}$ (entraîné sur un point fixe $z$) ou une correction de premier ordre basée sur des fonctions d'influence.
2. Scores de Non-Conformité Approchés : En utilisant le prédicteur approché, les auteurs définissent des scores de non-conformité approximés $\tilde{S}_{D_y}$.
3. Borner l'Erreur d'Approximation : Crucialement, la méthode dérive des bornes supérieures explicites ($\tau$) sur la divergence entre les scores réels et les scores approximés. Ces bornes dépendent de la régularité de la fonction de perte et des propriétés du noyau.
4. Encadrement de la Région : En incorporant ces bornes d'erreur dans le calcul de la p-valeur conforme, les auteurs construisent une région approximée "supérieure" ($\hat{C}^{up}$) et une région approximée "inférieure" ($\hat{C}^{lo}$). La véritable région conforme complète est garantie de se trouver à l'intérieur de cet encadrement ($\hat{C}^{lo} \subseteq \hat{C}^{full} \subseteq \hat{C}^{up}$).
5. Quantification de l'Épaisseur : Une nouvelle métrique appelée "épaisseur" (thickness) est introduite pour quantifier le volume de la différence symétrique entre les régions conformes approximées et complètes, fournissant une mesure de la précision de l'approximation au-delà de la simple probabilité de couverture.

Le papier développe trois niveaux d'approximation basés sur les hypothèses de régularité de la fonction de perte :

• Niveau 0 (Stabilité Uniforme) : Utilise des constantes de Lipschitz uniformes pour les fonctions de perte et de score, ce qui permet de récupérer des bornes similaires aux approches de stabilité uniforme mais permet des fonctions de perte générales dans un RKHS.
• Nps 1 (Stabilité Locale) : Exploite la différentiabilité de la fonction de perte pour dériver des bornes de stabilité locale qui varient avec $y$, resserrant ainsi les constantes d'approximation.
• Niveau 2 (Fonctions d'Influence) : Tire parti d'une régularité d'ordre supérieur (fonctions de perte deux et trois fois dérivables) et des fonctions d'influence (fonction d'influence de Bouligand) pour créer une approximation de prédicteur qui dépend de $y$ via un développement de Taylor au premier ordre. Cela produit des taux de convergence plus rapides pour l'erreur d'approximation.

Contributions Clés

• Stratégie d'Approximation Générique : Le papier fournit un cadre de distribution-free et générique pour approximer les régions conformes complètes dans des contextes RKHS avec des fonctions de perte générales (non quadratiques), incluant des pertes robustes comme Logcosh, Pseudo-Huber et Pinball lissée.
• Garanties Non-Asymptotiques : Contrairement aux approches précédentes basées sur les fonctions d'influence qui n'offrent que des garanties asymptotiques, ce travail fournit des bornes non-asymptotiques sur la qualité de l'approximation et assure que la région résultante est une région de confiance valide (couverture $\geq 1-\alpha$).
• Métrique d'Épaisseur : L'introduction de l' "épaisseur" permet de quantifier la divergence entre les régions conformes approximées et complètes en termes de volume (mesure de Lebesgue), et non seulement en termes de probabilité de couverture.
• Amélioration des Taux de Convergence : En utilisant les fonctions d'influence et des hypothèses de régularité d'ordre supérieur, les auteurs démontrent que l'erreur d'approximation décroît à un taux plus rapide ($O(n^{-1+r+\min(-1+2r, 0)})$) par rapport aux bornes de stabilité uniforme ($O(n^{-1+r})$), particulièrement lorsque le paramètre de régularisation $\lambda$ décroît lentement.

Résultats

• Bornes Théoriques : L'analyse théorique montre que l'épaisseur de l'approximation est bornée par des termes dépendant des propriétés du noyau, du paramètre de régularisation et de la régularité de la perte. Pour les fonctions de perte lisses, les bornes se resserrent significativement à mesure que la taille de l'échantillon $n$ augmente.
• Performance Empirique : Des expériences sur des données synthétiques (Friedman1) comparent quatre stratégies : Split-conformal, Stabilité Uniforme (Niveau 0), Stabilité Locale (Niveau 1), et Fonction d'Influence (Niveau 2).
  • Couverture : Toutes les méthodes proposées atteignent une couverture empirique proche du niveau cible ($1-\alpha = 0.9$).
  • Taille de la Région : La méthode basée sur la Fonction d'Influence produit les régions de prédiction les plus étroites (les plus informatives) avec une faible variance, surpassant les méthodes de split-conformal et de stabilité.
  • Calcul : Bien que la méthode de la Fonction d'Influence nécessite plus de temps de calcul (en raison de l'inversion de la matrice Hessienne), elle reste traitable. La méthode de Stabilité Locale offre un compromis favorable entre précision et coût de calcul.
• Visualisation : Des graphiques log-log de l'écart d' "épaisseur" par rapport à la taille de l'échantillon confirment les taux de convergence théoriques, montrant que l'approche par Fonction d'Influence converge plus rapidement que l'approche de stabilité uniforme.

Signification et Revendications
Les auteurs affirment que leur travail comble le fossé entre l'optimalité théorique de la prédiction conforme complète et la faisabilité computationnelle des méthodes de prédiction conforme scindée. En évitant la division des données, la méthode proposée utilise l'ensemble des données pour l'entraînement, préservant ainsi l'information et produisant des régions de prédiction plus étroites. Le cadre est significatif car il étend l'approximation conforme complète à une large classe de fonctions de perte et de contextes RKHS, fournissant des garanties non-asymptotiques rigoureuses tant sur la couverture que sur la "compacité" (épaisseur) des régions résultantes. Le papier souligne que, bien que l'approximation soit efficacement calculable (nécessitant un ou quelques évaluations de prédicteur), elle maintient la validité distribution-free du cadre de la prédiction conforme complète.