Résumé technique : Sous-échantillonnage pour l'apprentissage supervisé dans les espaces de Hilbert à noyau reproduisant (RKHS)

Énoncé du problème

À l'ère du Big Data, le coût computationnel et la consommation d'énergie associés à l'entraînement de modèles d'apprentissage statistique sur des ensembles de données massifs sont devenus des goulots d'étrangleurs critiques. Bien qu'il existe diverses techniques de réduction de données (ex: sketching, coreset, optimisation stochastique), beaucoup sont soit agnostiques à la tâche, soit reposent sur des probabilités intraitables pour une sélection optimale. Plus précisément, dans l'apprentissage supervisé non paramétrique où les hypothèses résident dans un espace de Hilbert à noyau reproduisant (RKHS), les méthodes existantes échouent souvent à fournir un schéma de sous-échantillonnage dépendant des données qui soit optimal pour minimiser la variance asymptotique de l'estimateur. Les méthodes à noyau passent généralement mal à l'échelle ($O(n^2)$ ou $O(nm)$) avec la taille originale du jeu de données $n$, et bien que le sous-échantillonnage réduise cela à $O(s^2)$ (où $s \ll n$), le sous-échantillonnage uniforme standard ignore la valeur informationnelle de chaque point de donnée, conduisant à une précision d'estimation sous-optimale.

Méthodologie

Les auteurs proposent un cadre pour la Minimisation du Risque Sous-échantillonné (SRM) dans les RKHS, utilisant un schéma de repondération de Horvitz-Thompson pour garantir une estimation sans biais du risque empirique. La méthodologie centrale comprend :

1. Cadre théorique :

   • Contexte : Apprentissage supervisé non paramétrique (classification et régression) avec une fonction de perte $\ell$ convexe et deux fois dérivable et une pénalité de ridge. L'estimateur minimise un risque empirique régularisé.
   • Stratégies de sous-échantillonnage : Le papier analyse deux stratégies :
     • Sous-échantillonnage multinomial (avec remplacement) : Les points sont tirés indépendamment avec des probabilités d'inclusion $\pi_{n,i}$.
     • Sous-échantillonnage de Poisson (sans remplacement) : Les points sont inclus indépendamment avec une probabilité $s_n \pi_{n,i}$.
   • Analyse asymptotique : En utilisant des outils issus des espaces de probabilité fonctionnels et de la théorie des martingales, les auteurs établissent la normalité asymptotique de l'estimateur SRM. Ils dérivent l'opérateur de covariance asymptotique $\Sigma^*$ qui dépend des probabilités d'inclusion $\pi_{n,i}$.

2. Schéma de sous-échantillonnage optimal :

   • Les auteurs définissent l'L-optimalité comme la minimisation de la trace de l'opérateur de covariance asymptotique (préconditionné par l'inverse de la hessienne du risque réel).
   • Ils dérivent une expression en forme close pour la fonction d'intérêt absolue L-optimale $\psi^*$, qui dicte les probabilités d'inclusion optimales :
     $$\psi^*(z) = |\ell'(h_0(x), y)| \sqrt{k(x, x)}$$
     où $h_0$ est le véritable minimiseur du risque régularisé, $\ell'$ est la dérivée de la perte, et $k$ est le noyau.
   • Cela implique que les points de données ayant une erreur de prédiction élevée (grand $|\ell'|$) ou une forte auto-similarité de noyau (high kernel self-similarity) doivent être échantillonnés avec une probabilité plus élevée.

3. Implémentation pratique (Estimateur pilote) :

   • Puisque $h_0$ est inconnu, les auteurs proposent une approche par plug-in :
     1. Calculer un estimateur pilote $\hat{h}_{k_n}$ sur un petit sous-ensemble des données ($k_n \ll s_n$).
     2. Estimer les probabilités optimales en utilisant $\hat{h}_{k_n}$.
     3. Lisser les probabilités estimées pour s'assurer qu'elles satisfont les hypothèses techniques (spécifiquement, qu'elles ne convergent pas vers zéro trop rapidement) en utilisant un hyperparamètre $\alpha \in (0, 1]$ :
        $$\tilde{\pi}_{n,i}^\alpha = (1-\alpha)\tilde{\pi}_{n,i} + \frac{\alpha}{n}$$
     4. Pour le sous-échantillonnage de Poisson, appliquer une troncature post-hoc pour garantir que les probabilités restent valides ($\leq 1/s_n$).
   • Des garanties théoriques (consistance et normalité asymptotique) sont fournies pour cet estimateur $\alpha$-piloté.

Contributions clés

• Normalité asymptotique dans les RKHS : Le papier établit la normalité asymptotique des estimateurs sous-échantillonnés dans les RKHS de dimension infinie, se distinguant des résultats paramétriques en employant des techniques d'espaces de probabilité aléatoires fonctionnels et la théorie des martingales.
• Dérivation du schéma optimal : Il fournit la première dérivation d'un schéma de sous-échantillonnage optimal spécifiquement pour les méthodes à noyau non paramétriques, montrant que la probabilité d'inclusion optimale est proportionnelle à l'amplitude du gradient de la perte pondérée par la diagonale du noyau.
• Comparaison des stratégies : Les auteurs analysent les compromis entre le sous-échantillonnage multinomial et de Poisson, démontrant que le choix optimal dépend du ratio limite $c = \lim s_n/n$. Notamment, en raison de la présence de la régularisation de ridge, les deux stratégies ont des efficacités asymptotiques différentes lorsque $c=0$, contrairement aux observations dans les contextes paramétriques.
• Algorithme pratique robuste : La proposition d'un algorithme "pilote" en deux étapes combinant un estimateur pilote avec lissage et troncature rend le schéma théoriquement optimal implémentable en pratique tout en maintenant les garanties statistiques.

Résultats

Des expériences numériques ont été menées sur des jeux de données synthétiques (classification et régression) et un jeu de données réel (UCI Covertype), comparant le SRM $\alpha$-piloté proposé à :

• Le sous-échantillonnage uniforme (référence).
• La méthode de Nyström.
• Les caractéristiques de Fourier aléatoires (RFF).
• Le sketching de noyau.

Résultats :

• Paramètre de lissage : Un paramètre de lissage $\alpha$ compris entre 0,1 et 0,4 donne la meilleure erreur de généralisation, équilibrant les bénéfices du sous-échantillonnage optimal avec la stabilité de l'échantillonnage uniforme.
• Régime de grandes données : Pour les grands ensembles de données, le SRM proposé surpasse significativement le sous-échantillonnage uniforme en termes de compromis entre l'erreur de généralisation et le temps de calcul (CPU).
• Comparaison avec les approximations : Sur le jeu de données réel Covertype, la méthode SRM est plus efficace que Nyström, RFF et le sketching. Sur des tâches synthétiques de faible dimension, les approximations de noyau (Nyström, RFF) sont plus rapides, suggérant que le sous-échantillonnage et l'approximation de noyau sont des techniques complémentaires.
• Approche hybride : Combiner le sous-échantillonnage avec la méthode de Nyström améliore encore les performances, indiquant la compatibilité de la méthode avec les techniques existantes d'approximation de noyau.

Signification et affirmations

Le papier affirme fournir une méthode théoriquement fondée et pratiquement viable pour réduire la charge de calcul de l'apprentissage basé sur les noyaux sans sacrifier l'efficacité statistique. En dérivant un schéma de sous-échantillonnage optimal basé sur la trace de la covariance asymptotique, les auteurs offrent un moyen d'extraire des individus "informatifs" à partir de grands ensembles de données.

Les auteurs présentent leur travail avec modestie comme une étape vers un apprentissage plus économe en énergie, notant que bien que la méthode réduise la taille du problème d'optimisation de $O(n^2)$ à $O(s^2)$, elle repose sur un estimateur pilote. Ils reconnaissent que la théorie est actuellement basée sur des risques régularisés et que l'extension à des contextes non régularisés ou le développement de procédures en ligne multi-étapes sont des directions potentielles pour la recherche future. Le travail se distingue en abordant les défis spécifiques du cadre non paramétrique RKHS, que les théories de sous-échantillonnage paramétriques existantes ne couvrent pas entièrement.