Résumé technique : Rayons des plus proches voisins sous échantillonnage dépendant

Énoncé du problème

Les méthodes des plus proches voisins (PPV) sont fondamentales pour l'apprentissage automatique classique et moderne, sous-tendant des tâches allant de la classification et de la régression par $k$-PPV à l'apprentissage de variétés et à la recherche d'information. La performance de ces méthodes repose fortement sur les propriétés géométriques des voisinages locaux qu'elles construisent. Plus précisément, la distance entre un point de requête $x$ et son $k$-ième plus proche voisin, notée rayon $R_{n,k}(x)$, détermine l'échelle du voisinage local et régit le compromis biais-variance.

Bien que le comportement de $R_{n,k}(x)$ soit bien compris sous un échantillonnage indépendant et identiquement distribué (i.i.d.) — où l'échelle canonique est $(k/n)^{1/s}$ avec $s$ étant la dimension intrinsèque locale —, de nombreux problèmes d'apprentissage réels impliquent des données dépendantes (par exemple, séries temporelles, trajectoires d'apprentissage par renforcement, capteurs spatio-temporels). Dans de tels contextes, les observations sont souvent fortement dépendantes même si leur distribution marginale est stable. La question centrale abordée dans cet article est : Comment la dépendance affecte-t-elle la géométrie des voisinages des plus proches voisins ? Plus précisément, la dépendance modifie-t-elle fondamentalement l'échelle du rayon des plus proches voisins, ou l'échelle géométrique canonique reste-t-elle robuste ?

Méthodologie et configuration

Les auteurs analysent un tableau triangulaire de variables aléatoires à valeurs dans $\mathbb{R}^d$, noté $[X_{n,i} : 1 \le i \le n, n \ge 1]$, défini sur un espace de probabilité commun.

• Distribution marginale : Toutes les observations partagent une loi marginale commune $\mu$.
• Structure de dépendance : L'article suppose une dépendance de mélange fort ($\alpha$-mélange) le long de chaque ligne du tableau. Les coefficients de mélange $\alpha_m$ quantifient la décroissance de la dépendance entre des segments de la séquence séparés par $m$ indices.
• Objet d'étude : Le rayon $R_{n,k}(x) = \|X_{n}^{(k)}(x) - x\|$, où $X_{n}^{(k)}(x)$ est le $k$-ième plus proche voisin d'un point de requête fixe $x$ parmi $n$ observations.

L'analyse distingue deux régimes de mélange :

1. Mélange polynomial : $\alpha_m \lesssim m^{-\gamma}$ pour un certain $\gamma > 1$.
2. Mélange géométrique (exponentiel) : $\alpha_m \le e^{-\gamma m}$ pour un certain $\gamma > 0$.

Les résultats théoriques sont formulés en utilisant un exposant local $s > 0$ plutôt que la dimension ambiante $d$. Cet exposant caractérise l'accumulation de masse locale près de $x$ (c'est-à-dire $\mu(B(x,r)) \asymp r^s$), permettant à la théorie de s'appliquer à des données concentrées près de variétés de dimension inférieure.

Contributions et résultats clés

1. Convergence presque sûre sans hypothèse de distribution

Sous un $\alpha$-mélange polynomial, les auteurs établissent un théorème de convergence presque sûre sans hypothèse de distribution.

• Résultat : Si $k/n \to 0$, alors $R_{n,k}(x) \xrightarrow{p.s.} r_x$, où $r_x$ est la distance entre $x$ et le support de $\mu$.
• Implication : Si $x$ appartient au support de $\mu$, le rayon converge vers 0 presque sûrement. Ce résultat étend la consistance classique i.i.d. aux tableaux triangulaires dépendants sans exiger d'hypothèses de densité ou de régularité, démontrant qu'une faible dépendance n'altère pas le comportement géométrique limite.

2. Bornes de moments non asymptotiques sous mélange géométrique

Sous l'hypothèse plus forte d'un $\alpha$-mélange géométrique et de conditions de masse locale (Hypothèses 2 et 3), l'article dérive des bornes non asymptotiques précises.

• Bornes de queue : Les auteurs prouvent une borne de queue montrant que $R_{n,k}(x)$ se concentre autour de l'échelle canonique $(k/n)^{1/s}$. L'exposant de concentration inclut un facteur supplémentaire $\log n$, qui est le « prix » payé pour découpler les observations dépendantes en blocs indépendants (une technique standard dans l'analyse des séquences de mélange).
• Majoration de moment : Pour le régime $k \gtrsim \log n$, l'article établit la majoration de moment précise :
  $$\mathbb{E}[R_{n,k}(x)^p] \lesssim \left(\frac{k}{n}\right)^{p/s}$$
• Minoration de moment : Sous une condition de masse supérieure locale correspondante, une minoration correspondante est dérivée :
  $$\mathbb{E}[R_{n,k}(x)^p] \gtrsim \left(\frac{k}{n}\right)^{p/s}$$
• Caractérisation de l'ordre exact : En combinant ces éléments, l'article prouve que sous mélange géométrique, l'ordre exact des moments est :
  $$\mathbb{E}[R_{n,k}(x)^p] \asymp \left(\frac{k}{n}\right)^{p/s}$$

3. Interprétation de l'exposant local

Une caractéristique critique de la théorie est sa dépendance à l'exposant local $s$ plutôt qu'à la dimension ambiante $d$. Cela s'aligne avec les scénarios modernes d'apprentissage en haute dimension où les données résident souvent près de variétés de dimension inférieure. Les résultats confirment que l'échelle du rayon des PPV est déterminée par la dimension intrinsèque de la distribution près du point de requête, et non par l'espace ambiant, même en présence de dépendance.

Validation expérimentale

L'article étaye ses résultats théoriques par des expériences synthétiques et réelles :

1. Taux de convergence des moments : Des expériences sur des modèles d'espace d'état gaussiens linéaires, des modèles de Markov cachés (HMM) et des processus gaussiens stationnaires (noyau RBF) confirment que la pente estimée de la relation entre le moment logarithmique et $\log(k/n)$ s'aligne sur le taux théorique $p/s$. Une faible dépendance reste proche de la référence i.i.d., tandis qu'une dépendance moyenne/forte introduit des écarts cohérents avec la pénalité de concentration théorique.
2. Estimation de l'entropie : En utilisant les estimateurs d'entropie de Kozachenko–Leonenko, l'étude montre que lorsque les données ont une dimension intrinsèque $s$ mais sont observées dans une dimension supérieure $d$, l'estimateur converge vers l'entropie du processus intrinsèque. Cela vaut même sous dépendance temporelle, à condition que la géométrie locale soit préservée (par exemple, via l'ACP).
3. Benchmarks réels : Les auteurs évaluent Raw-kNN et PCA-kNN sur des tâches de prévision et de classification de séries temporelles issues du Time Series Pile (incluant les ensembles de données Informer, Monash et UCR). Les résultats indiquent que les méthodes des plus proches voisins restent informatives sur des données dépendantes réelles. PCA-kNN se comporte de manière comparable à Raw-kNN, suggérant que la réduction de dimension peut préserver la structure locale nécessaire à la prédiction basée sur les voisinages, même sous dépendance.

Signification et affirmations

L'article avance un message simple mais significatif : Sous faible dépendance, la géométrie des plus proches voisins reste essentiellement la même que dans le cas indépendant au niveau de son échelle canonique.

• Impact théorique : Ce travail fournit un principe de contrôle géométrique pour les méthodes d'apprentissage sous échantillonnage dépendant. Il isole l'effet de la dépendance, montrant que si la dépendance modifie les constantes de concentration et introduit une pénalité logarithmique, elle ne change pas l'exposant fondamental $(k/n)^{1/s}$.
• Implication pratique : Cette découverte justifie le transfert de l'intuition géométrique et des principes de conception des méthodes locales (par exemple, sélection de la fenêtre, ajustement de la taille du voisinage) du régime i.i.d. vers des contextes dépendants beaucoup plus larges. Cela suggère que de nombreuses heuristiques développées pour les données i.i.d. restent applicables aux séries temporelles et autres données dépendantes, à condition que la dépendance ne soit pas trop forte pour invalider les hypothèses de mélange.

Les auteurs soulignent que leurs résultats sont modestes en termes de portée concernant la convergence uniforme (se concentrant sur l'analyse ponctuelle) mais robustes dans leur interprétation géométrique, offrant une pierre angulaire pour les futures analyses des algorithmes d'apprentissage non paramétrique et par graphes sous dépendance.