A scalable version of MADD for big-data classification

Résumé Technique : Une version scalable de MADD pour la classification de Big-Data

Énoncé du Problème
Les classificateurs basés sur la distance, particulièrement ceux reposant sur la distance euclidienne, sont fondamentaux dans l'apprentissage automatique moderne. Cependant, dans les scénarios de haute dimensionnalité à faible nombre d'échantillons (HDLSS), la distance euclidienne souffre de « concentration de la distance », où les distances entre des points appartenant à la même classe deviennent plus grandes que les distances entre des points de classes différentes. Cela viole les structures de voisinage et conduit à l'émergence de « hubs », dégradant sévèrement les performances du classificateur.

Pour remédier à cela, Pal et al. (2016) ont introduit le MADD (Mean Absolute Difference of Distances), une semi-métrique pilotée par les données qui contourne avec succès ces problèmes de haute dimensionnalité en maintenant des structures de voisinage correctes basées sur les différences de localisation et d'échelle. Malgré ses avantages théoriques, le MADD fait face à un goulot d'étranglement critique : sa complexité computationnelle. Le calcul du MADD entre deux points nécessite $O(nd)$ opérations (où $n$ est la taille de l'échantillon d'entraînement et $d$ la dimensionnalité), et la classification d'un point de test via une approche de plus proche voisin (NN) nécessite $O(n^2d)$ opérations. Comme démontré dans l'article, cette mise à l'échelle quadratique rend le MADD computationnellement prohibitif pour les grands ensembles de données avec un $n$ élevé, même sur du matériel moderne.

Méthodologie
Les auteurs proposent une version scalable du MADD, nommée MADDsc, qui réduit considérablement la complexité computationnelle tout en conservant les avantages statistiques de la métrique originale. La méthodologie se compose de trois composantes clés :

1. Sélection d'un ensemble représentatif via les Processus de Points Déterminantaux (DPP) :
   Au lieu de calculer les distances par rapport à l'ensemble du jeu d'entraînement, MADDsc redéfinit la métrique en utilisant un petit sous-ensemble d'observations représentatives, $X^* \subset X$. Les auteurs soutiennent que les propriétés de séparation théoriques du MADD sont préservées si l'ensemble représentatif capture la diversité des données originales.

   • Pour sélectionner cet ensemble, les auteurs emploient des Processus de Points Déterminantaux (DPP). Contrairement à l'échantillonnage aléatoire simple, qui peut manquer les structures intrinsèques des données (particulièrement dans les distributions multimodales), les DPP introduisent un effet de « répulsion ». En construisant une matrice de similitude $L$ à l'aide d'un noyau radial gaussien, les DPP sélectionnent un sous-ensemble de points qui sont diversifiés et répartis de manière étendue à travers le nuage de données, garantissant que l'ensemble représentatif capture le paysage de l'échantillon d'entraînement complet.
   • Le coût computationnel est réduit de $O(n^2d)$ à $O(knd)$, où$k$ est la taille de l'ensemble représentatif ($k \ll n$).

2. Validation croisée incrémentale pour la sélection d'hyperparamètres :
   La taille de l'ensemble représentatif ($k$) est un hyperparamètre crucial. Une validation croisée standard nécessiterait de sélectionner de manière répétée des échantillons DPP et de re-calculer les distances pour chaque pli et chaque candidat $k$, ce qui annulerait les gains de vitesse.

   • Les auteurs proposent une technique de validation croisée incrémentale. En modifiant l'algorithme d'échantillonnage DPP pour garantir que les sous-ensembles sélectionnés sont imbriqués (c'est-à-dire $X^*(k_t) \subseteq X^*(k_{t+1})$), les valeurs MADDsc peuvent être calculées de manière incrémentielle. Cela permet à l'algorithme de mettre à jour la métrique à mesure que $k$ augmente sans recalculer l'intégralité de la matrice de distance, réduisant ainsi drastiquement la surcharge computationnelle de la sélection de modèle.

3. Caractéristiques de Fourier Aléatoires (RFF) pour les ensembles de données massifs :
   Pour les ensembles de données extrêmement larges où même la construction de la matrice de similitude $n \times n$ pour le DPP est irréalisable (en raison de la mémoire ou des coûts de décomposition en valeurs propres), les auteurs intègrent les Caractéristiques de Fourier Aléatoires (RFF).

   • Basé sur le théorème de Bochner, le noyau gaussien est approximé via une espérance de Monte Carlo. La matrice de similitude $L$ est approximée par $R R^T$, où $R$ est une matrice de mise en correspondance de caractéristiques de faible dimension ($n \times 2D$).
   • Cela permet à la décomposition en valeurs propres requise pour l'échantillonnage DPP d'être effectuée sur une matrice beaucoup plus petite de $2D \times 2D$ (ou via SVD de $R$), réduisant ainsi la complexité temporelle et de mémoire. Cette approche est formalisée sous le nom de NN-MADDsc avec RFF.

Le cadre est également étendu au gMADDsc, une version scalable du MADD généralisé (gMADD), qui traite les cas où les populations diffèrent au-delà des deux premiers moments (localisation et échelle).

Résultats Clés
Des études de simulation approfondies et des analyses de données réelles sur les ensembles de données de séries temporelles UCR démontrent l'efficacité des méthodes proposées :

• Performance vs MADD Original : Dans les simulations à travers diverses distributions (localisation, échelle, mélange et queue lourde), le NN-MADDsc atteint des taux de mauvaise classification presque identiques au NN-MADD original (différences typiquement $\le 1\%$).
• Efficacité Computationnelle :
  • Le NN-MADDsc est nettement plus rapide que le NN-MADD. Pour une taille d'entraînement de $n=16\,384$, le NN-MADD a pris plus de 6,5 heures, tandis que le NN-MADDsc s'est terminé en une fraction de ce temps.
  • La stratégie de validation croisée incrémentielle réduit davantage le temps d'exécution par rapport à la validation croisée standard, coupant le temps de calcul de près de la moitié pour $n=4096$.
  • L'approche basée sur les RFF offre l'accélération la plus spectaculaire. Pour $n=25\,000$, la méthode basée sur les RFF s'est terminée en moins de 25 minutes, alors que le NN-MADDsc standard a pris plus de 15 heures, et le NN-MADD original a échoué en raison de contraintes de mémoire.
• Comparaison avec d'autres classificateurs : Le NN-MADDsc surpasse ou égale systématiquement les classificateurs de pointe (incluant Random Forest, SVM et GLMNET) dans les contextes de haute dimensionnalité, particulièrement lorsque les distributions de données diffèrent en forme ou en échelle. Dans les benchmarks de séries temporelles réels, il a obtenu les taux d'erreur les plus bas sur plusieurs jeux de données (ex: Synthetic Control Chart, Two Patterns).
• Garanties Théoriques : L'article établit que sous les régimes de haute dimensionnalité et de grand échantillonnage (HDHSS), les décisions de classification du NN-MADDsc convergent vers celles du NN-MADD avec une probabilité tendant vers 1, à condition que la taille de l'ensemble représentatif croisse de manière appropriée par rapport au logarithme de la taille de l'échantillon.

Signification et Revendications
L'article affirme élargir le champ d'application du MADD, le rendant applicable aux scénarios de Big-Data caractérisés à la fois par une haute dimensionnalité et un grand nombre d'observations. La contribution primaire est le découplage de la robustesse statistique du MADD de sa complexité computationnelle quadratique. En exploitant les DPP pour un sous-échantillonnage préservant la diversité et les RFF pour l'approximation de noyau, les auteurs fournissent une solution pratique et scalable qui conserve les avantages théoriques du MADD dans les espaces de haute dimension. Ce travail ne prétend pas remplacer tous les classificateurs, mais positionne le MADDsc comme une alternative supérieure pour la classification basée sur la distance dans les régimes où la distance euclidienne échoue et où le MADD traditionnel est computationnellement intraitable.