Résumé technique : Caractéristiques aléatoires pour l'approximation de noyaux Grassmanniens avec projections de rang un bornées

Énoncé du problème

Dans de nombreuses tâches d'apprentissage supervisé et non supervisé, les classes ou grappes de données sont naturellement représentées par des sous-espaces de faible dimension dans des espaces de haute dimension, plutôt que par des points euclidiens individuels. Cela nécessite d'opérer sur la variété Grassmannienne $\mathcal{G}(k, n)$, l'ensemble de tous les sous-espaces de dimension $k$ dans $\mathbb{R}^n$. Bien que les machines à noyaux (par exemple, les SVM) puissent apprendre efficacement sur de telles données en utilisant des noyaux définis positifs (comme les noyaux de projection ou de Binet–Cauchy), elles souffrent d'une faible extensibilité. Les méthodes à noyaux standard nécessitent la construction et le stockage d'une matrice de Gram $N \times N$, ce qui entraîne des coûts de mémoire et de calcul de $O(N^2)$, ce qui est prohibitif pour les grands ensembles de données.

Les tentatives existantes pour approximer les noyaux Grassmanniens via des caractéristiques aléatoires font face à deux limitations principales :

1. Projections aléatoires denses : L'incorporation de sous-espaces en projetant leurs projecteurs orthogonaux sur des matrices gaussiennes aléatoires denses nécessite $O(n^2)$ de stockage et de calcul par caractéristique, ce qui est impraticable pour les hautes dimensions.
2. Projections de rang un (ROP) non bornées : Bien que moins coûteuses en calcul ($O(kn)$ par caractéristique), les ROP basées sur des mesures quadratiques $a^\top P b$ présentent des distributions à queue lourde (sub-Weibull). Cela entraîne des taux de concentration lents, empêchant des garanties d'approximation uniforme sur l'ensemble de la variété Grassmannienne avec un nombre de caractéristiques croissant linéairement avec la dimension intrinsèque.

Méthodologie

Les auteurs proposent une famille de fonctions de caractéristiques aléatoires qui combinent des projections de rang un (ROP) avec des transformations non linéaires bornées pour parvenir à une approximation de noyau uniforme et évolutive.

1. Projections de rang un (ROP)

Pour un sous-espace $P \in \mathcal{G}(k, n)$ représenté par une base orthonormée $U$ (où $P = UU^\top$), la méthode sonde le sous-espace en utilisant $m$ mesures quadratiques de rang un indépendantes :
$$\psi_{\text{rop}}(U) = \left( a_i^\top P b_i \right)_{i=1}^m$$
où $a_i, b_i \sim \text{i.i.d. } \mathcal{N}(0, I_n)$. Cela réduit le coût de calcul par caractéristique à $O(kn)$ et le stockage à $O(kn)$ (après factorisation de $U^\top a_i$ et $U^\top b_i$).

2. Transformations non linéaires bornées

Pour dompter la distribution à queue lourde des ROP non bornées et assurer la convergence uniforme, les auteurs composent $\psi_{\text{rop}}$ avec des fonctions non linéaires bornées $g(\cdot)$ :
$$\psi_g(U) = g(\psi_{\text{rop}}(U))$$
Deux transformations spécifiques sont analysées :

• Caractéristiques binaires : En utilisant la fonction signe, $g(\lambda) = \text{sign}(\lambda)$. Cela produit des caractéristiques aléatoires binaires $\psi_\pm \in \{\pm 1\}^m$, permettant un stockage compact de 1 bit et des opérations bit à bit rapides.
• Caractéristiques périodiques : En utilisant l'exponentielle complexe, $g(\lambda) = \exp(i\omega \lambda)$. Cela produit des caractéristiques aléatoires périodiques $\psi_\circ$, analogues aux caractéristiques de Fourier aléatoires (Random Fourier Features).

3. Projections structurées

Pour réduire davantage la complexité de calcul, les auteurs remplacent les vecteurs de sondage gausiens denses par des matrices aléatoires structurées basées sur des compositions de transformées rapides de Walsh-Hadamard et de matrices diagonales de signes aléatoires (inspirées par Choromanski et al., 2016). Cela réduit la complexité de calcul de $O(kmn)$à$O(km \log n)$ tout en maintenant les propriétés statistiques.

Contributions clés

Garanties théoriques

L'article établit que les produits scalaires empiriques de ces caractéristiques aléatoires bornées sont des estimateurs non biaisés de noyaux Grassmanniens spécifiques, bien définis et invariants par rotation. Crucialement, les auteurs prouvent des bornes d'approximation uniforme sur tous les sous-espaces de dimension fixe $k$ dans $\mathbb{R}^n$.

• Complexité d'échantillonnage : Ils montrent que $m = O(kn)$ caractéristiques aléatoires (à un facteur logarithmique près) suffisent pour contrôler l'erreur d'approximation uniformément. Cela passe linéairement de la dimension ambiante $n$ et de la dimension du sous-espace $k$, une amélioration significative par rapport aux exigences de $O((kn)^2)$ des ROP non bornées.
• Noyau binaire ($\kappa_\pm$) : Il est démontré que le noyau attendu pour les caractéristiques binaires est défini positif et invariant par rotation. Bien qu'il n'existe pas d'expression de forme fermée pour un $k$ général, il est caractérisé de manière semi-explicite comme :
  $$\kappa_\pm(U, V) = 1 - \frac{2}{\pi} \mathbb{E}[\angle(P g, Q g)]$$
  où $g \sim \mathcal{N}(0, I_n)$ et $\angle(\cdot, \cdot)$ est l'angle entre les vecteurs. Pour $k=1$, une forme fermée $(1 - 2\theta/\pi)^2$ est dérivée.
• Noyau périodique ($\kappa_\circ$) : Le noyau attendu pour les caractéristiques périodiques admet une expression de forme fermée dépendant des angles principaux $\{\theta_j\}_{j=1}^k$ :
  $$\kappa_\circ(U, V) = \prod_{j=1}^k (1 + \omega^2 \sin^2 \theta_j)^{-1}$$
  Les auteurs analysent le comportement de $\kappa_\circ$ par rapport au paramètre de fréquence $\omega$ :
  • $\omega$ grand : $\kappa_\circ$ se comporte comme un noyau de Binet–Cauchy inverse (sensible aux petits angles principaux).
  • $\omega$ petit : $\kappa_\circ$ approxime un noyau RBF de projection, $\exp(-\frac{1}{2}\omega^2 \|P-Q\|_F^2)$.

Complexité de calcul

Les méthodes proposées offrent des gains d'efficacité substantiels :

• Mémoire : Le stockage pour les ROP bornées non structurées est de $O(mn)$ pour les vecteurs de sondage. En substituant $m = O(kn)$ pour assurer une approximation uniforme, la complexité globale de mémoire devient $O(kn^2)$ (spécifiquement dérivée comme $O(\delta^{-2}(kn^2))$ dans l'article). Ceci est distinct des projections denses qui nécessitent $O(mn^2)$ de stockage (passant à $O(k^3 n^3)$ pour une approximation uniforme).
• Calcul : La complexité de calcul pour les ROP bornées non structurées est de $O(kmn)$. Avec $m = O(kn)$, cela passe à $O(k^2 n^2)$. C'est nettement inférieur à la complexité de $O(k^2 n^3)$ associée aux méthodes de projection denses (qui nécessitent $O(\delta^{-2} k^3 n^3)$).
• Stockage : Les caractéristiques binaires ne nécessitent que $O(m)$ bits par sous-espace.

Résultats expérimentaux

Les auteurs valident leur approche en utilisant des expériences synthétiques et le jeu de données ETH-80 (images d'objets visuels sous différents angles de vue).

1. Approximation de noyau : Les expériences confirment que les ROP bornées convergent vers leurs noyaux cibles avec des coûts de calcul et de mémoire nettement inférieurs à ceux des projections denses.
2. Plongements structurés : L'analyse empirique des esquisses de Hadamard-diagonale structurées montre que l'utilisation de $S=3$ blocs est suffisante pour approximer une distribution gaussienne, validant l'utilisation de transformées rapides.
3. Performance de classification :
   • Sur les tâches de classification de superclasse (8 voies) et de classification d'objets (80 voies), les caractéristiques aléatoires proposées (tant structurées qu'non structurées) atteignent des précisions de classification comparables aux méthodes à noyaux exactes, bien qu'avec certains compromis selon la tâche et le noyau.
   • Plus précisément, les plongements structurés avec un ratio de suréchantillonnage $\rho = m/(nk)$ aussi bas que 0,05 (5 % de la taille de la base originale) produisent une grande précision tout en réduisant le temps de calcul de plusieurs ordres de grandeur par rapport à l'évaluation exacte du noyau. Par exemple, pour la tâche de classification à 80 voies, les méthodes structurées ont réduit le temps d'exécution total d'environ 52,9 secondes (noyau de projection exacte) à environ 1,9 seconde. Cependant, ce gain de vitesse s'est accompagné d'une baisse notable de la précision, passant de 98,75 % (exact) à 83,00 % (structuré), soulignant le compromis entre efficacité de calcul et performance de classification dans ce contexte spécifique.

Signification et revendications

L'article prétend fournir une alternative pratique et évolutive aux noyaux Grassmanniens classiques. En combinant les projections de rang un avec des non-linéarités bornées, les auteurs démontrent qu'il est possible de :

1. Recouvrer la géométrie Grassmannienne avec une grande précision.
2. Obtenir des garanties d'approximation uniforme sur la variété avec un nombre de caractéristiques croissant linéairement avec la dimension intrinsèque.
3. Réduire considérablement les exigences de mémoire et de calcul, rendant l'apprentissage par noyau sur des données de sous-espaces réalisable pour des applications à grande échelle et de haute dimension.

Ce travail comble le fossé entre les méthodes à noyaux théoriques et l'extensibilité pratique, offrant un cadre où le compromis entre l'erreur d'approximation et le coût de calcul peut être explicitement contrôlé via le nombre de caractéristiques aléatoires et le choix de la transformation non linéaire.