Manifold Dimension Estimation via Local Graph Structure

Résumé technique : Estimation de la dimension d'une variété via la structure graphique locale

Énoncé du problème
Estimer la dimension intrinsèque $d$ d'une variété plongée dans un espace ambiant de haute dimension $\mathbb{R}^p$ constitue un défi fondamental en réduction de dimension non linéaire. Alors que de nombreux estimateurs existants (par exemple, PCA locale, DanCo, TwoNN) reposent sur l'hypothèse de « platitude » — approximer les voisinages locaux comme des sous-espaces linéaires de dimension $d$ — cette approche montre ses limites lorsque les variétés présentent une courbure significative ou sont plongées de manière non linéaire. Des méthodes récentes comme la PCA ajustée à la courbure (CA-PCA) tentent de remédier à cela en corrigeant explicitement les structures propres pour la courbure, mais elles souffrent souvent d'une surestimation dans les espaces ambiants de haute dimension ou d'une instabilité computationnelle. Les auteurs identifient un manque de méthodes capables de modéliser de manière robuste la courbure locale sans recourir à une estimation directe instable de la courbure ou à la détection de sauts de valeurs propres.

Méthodologie
Les auteurs proposent un nouveau cadre qui reformule l'estimation de la dimension d'une variété comme un problème de régression sur les coordonnées de la PCA locale. Au lieu de supposer une platitude locale ou d'estimer explicitement des tenseurs de courbure, la méthode modélise le voisinage local d'un point $x_k$ comme le graphe d'une fonction lisse $g: \mathbb{R}^d \to \mathbb{R}^{p-d}$.

1. Représentation graphique locale : Pour un point $x_k$ et ses $K$ plus proches voisins, les auteurs effectuent une PCA pour établir un système de coordonnées local aligné avec l'espace tangent estimé. Les $d$ premières coordonnées représentent l'espace tangent, tandis que les $p-d$ coordonnées restantes représentent l'espace normal.
2. Formulation de la régression : Le cadre postule que les coordonnées normales peuvent s'exprimer comme une fonction des coordonnées tangentielles. Puisque le développement de Taylor du premier ordre de cette fonction est nul (par définition de l'espace tangent), les auteurs utilisent des termes du second ordre (quadratiques) pour capturer la courbure locale.
3. Sondage des dimensions candidates : L'algorithme itère sur les dimensions candidates $j$ (de 1 à $p-1$). Pour chaque $j$, il traite les $j$ premières coordonnées PCA comme entrées et la $(j+1)$-ième coordonnée comme sortie, ajustant un modèle de régression quadratique.
4. Deux estimateurs :
   • Intégration quadratique (QE) : Utilise les moindres carrés ordinaires (OLS) pour ajuster le modèle quadratique. Il évalue la qualité de l'ajustement à l'aide de la statistique $F$ et du $R^2$ ajusté. La dimension estimée est la plus petite $j$ pour laquelle l'ajustement du modèle devient statistiquement significatif (valeur p < 1 %) et reste significatif pour toutes les dimensions supérieures.
   • Moindres carrés totaux (TLS) : Utilise les moindres carrés totaux pour tenir compte des erreurs dans les variables d'entrée et de sortie. Au lieu des statistiques $F$, il évalue la baisse relative de l'erreur TLS totale ($\eta_j$) entre les dimensions consécutives. La dimension estimée correspond au pic de cette baisse relative.

Contributions clés

• Cadre basé sur la régression : L'article introduit une perspective novatrice qui présente l'estimation de la dimension comme un problème de régression récursive. Cela remplace l'estimation géométrique locale instable (comme le calcul direct de la courbure) par une procédure d'ajustement statistiquement agrégée, offrant une plus grande robustesse face à la sparsité de l'échantillonnage et au bruit.
• Modélisation consciente de la courbure : En employant des modèles quadratiques, la méthode capture explicitement la courbure de la variété sans nécessiter d'estimation explicite de la courbure ni de correction des valeurs propres, atténuant ainsi les problèmes de surestimation courants dans les méthodes basées sur la PCA.
• Robustesse au bruit et à la non-linéarité : Le cadre s'adapte naturellement au bruit et est conçu pour bien performer sur des variétés aux plongements complexes et non linéaires où les hypothèses de platitude échouent.
• Implémentation pratique : Les auteurs fournissent deux estimateurs concrets (QE et TLS) avec des algorithmes détaillés, incluant des heuristiques pour limiter l'espace de recherche ($p_{max}$) en fonction de la taille du voisinage afin d'assurer la faisabilité computationnelle.

Résultats expérimentaux
Les auteurs ont évalué QE et TLS sur 18 variétés synthétiques (incluant des sphères, des sphères déformées et des surfaces gaussiennes) et 6 jeux de données réels (ISOMAP, MNIST, ISOLET, Fashion MNIST, Frey Face, Gas Sensor Array Drift).

• Données synthétiques : QE et TLS ont démontré des performances compétitives ou supérieures par rapport aux méthodes de l'état de l'art (PCA locale, CA-PCA, DanCo, TwoNN, MADA, etc.), en particulier dans les régimes à faible échantillon et sur des variétés plongées de manière non linéaire (par exemple, des sphères déformées). Ils ont efficacement atténué la surestimation observée dans CA-PCA et PCA locale lorsque la dimension ambiante $p$ dépasse largement la dimension intrinsèque $d$.
• Robustesse au bruit : En présence de bruit gaussien, uniforme et de Laplace, les méthodes proposées ont maintenu des performances robustes, surpassant de nombreux estimateurs basés sur la platitude dont la précision se dégradait significativement.
• Données réelles : Sur les jeux de données réels, les estimateurs ont produit des résultats cohérents avec les plages de consensus (par exemple, estimant ISOMAP $\approx 3$, MNIST $\approx 8-11$). Notamment, ils ont évité la surestimation sévère observée dans PCA locale et CA-PCA sur des jeux de données à dimensions ambiantes élevées.
• Limitations observées : Les méthodes ont montré une performance réduite sur des variétés « triviales » à courbure nulle (par exemple, des hyperboules), où le modèle quadratique constitue une mauvaise spécification. De plus, TLS est borné inférieurement par 2 en raison de sa dépendance aux baisses d'erreur relative entre les dimensions.

Signification et affirmations
L'article affirme que, en déplaçant le paradigme de l'approximation géométrique vers la régression statistique, le cadre proposé atteint une robustesse et une précision améliorées, en particulier dans des régimes difficiles impliquant de petites tailles d'échantillons et une courbure complexe. Les auteurs affirment que leurs méthodes offrent une alternative convaincante aux estimateurs existants les plus performants, traitant efficacement les limites des approches basées sur la platitude et des corrections de courbure basées sur les valeurs propres. Ils concluent que, bien que la formulation quadratique actuelle soit efficace, des travaux futurs pourraient explorer des modèles plus expressifs si des outils de diagnostic fiables pour les statistiques d'échantillon sont développés. Le travail est présenté comme une étape significative vers la résolution des défis persistants en estimation de la dimension d'une variété, bien que les auteurs restent modestes concernant la nécessité d'un raffinement supplémentaire des critères d'évaluation (spécifiquement pour TLS) et de la gestion du bruit dans l'estimation de l'espace tangent.