$p$-adic Principal Component Analysis

Cet article formule un problème d'optimisation $p$-adique sur la factorisation de matrices et explore une méthode heuristique analogue à l'analyse en composantes principales (PCA).

L'essentiel

Voici une explication de ce papier de recherche, imagée et simplifiée, comme si nous discutions autour d'un café.

Le Problème : Quand les règles du jeu changent

Imaginez que vous êtes un détective chargé de trier des milliers de documents. Habituellement, pour trouver des patterns ou des anomalies (des documents bizarres), vous utilisez une méthode classique appelée PCA (Analyse en Composantes Principales). C'est comme si vous regardiez une foule de personnes et que vous disiez : « Tiens, la plupart des gens sont debout, donc je vais ignorer la hauteur et me concentrer sur la largeur pour mieux les voir. »

Mais ce papier pose une question bizarre : Que se passe-t-il si les règles de la géométrie ne sont plus celles de notre monde réel ?

Dans notre monde (les nombres réels), la distance entre deux points est fluide. Si vous vous éloignez d'un peu, la distance augmente un peu.
Dans le monde p-adique (un univers mathématique étrange basé sur les nombres premiers, comme le 7 ou le 2), la géométrie est discrète et fractale. C'est comme si l'univers était fait de poupées russes ou d'arbres généalogiques infinis. Ici, la distance ne fonctionne pas comme chez nous : deux points peuvent être très proches même s'ils semblent très différents, et la notion de "ligne droite" ou de "cercle" est toute différente.

L'auteur, Tomoki Mihara, se demande : Comment faire de l'analyse de données (comme la PCA) dans cet univers étrange où les règles habituelles (comme la dérivée ou la moyenne) ne fonctionnent plus ?

La Solution : Une nouvelle boussole

En mathématiques classiques, la PCA fonctionne en trouvant les axes principaux d'un nuage de points (comme les axes X et Y sur une carte). Pour cela, on utilise des concepts comme l'orthogonalité (des lignes perpendiculaires).

Mais dans le monde p-adique, le concept de "perpendiculaire" tel que nous le connaissons n'existe pas vraiment. C'est comme essayer de mesurer un angle avec une règle en caoutchouc qui change de forme selon où vous la posez.

L'idée géniale de l'auteur :
Au lieu de chercher des lignes perpendiculaires, il définit l'orthogonalité par la proximité.

• Analogie : Imaginez que vous essayez de projeter une ombre d'un objet sur un mur. Dans notre monde, vous cherchez l'angle droit. Dans le monde p-adique, l'auteur dit : « L'ombre la plus proche de l'objet, c'est celle qui minimise la distance. »
• Il crée un algorithme qui cherche systématiquement le point le plus proche, comme un chercheur d'or qui creuse là où la terre semble la plus riche, jusqu'à ne plus trouver de pépites.

Les Deux Méthodes : Le "Sauvage" et le "Préparé"

L'auteur propose deux façons d'appliquer cette nouvelle méthode :

1. La méthode "Non-réduite" (NRPCA) : Le Chasseur Sauvage

   • C'est une approche directe. On prend le premier point disponible, on l'utilise comme base, et on ajuste tout le reste autour de lui.
   • Analogie : C'est comme si vous arriviez dans une forêt et que vous choisissiez le premier arbre que vous voyez pour construire votre cabane, sans regarder autour. C'est rapide, mais parfois vous vous trompez de direction.

2. La méthode "Réduite" (RPCA) : L'Architecte Préparé

   • Avant de commencer, l'algorithme prend le temps de "nettoyer" et d'organiser tous les points pour s'assurer qu'ils sont bien alignés (orthogonaux) les uns par rapport aux autres.
   • Analogie : C'est comme si, avant de construire la cabane, vous preniez le temps de couper les branches, de tasser la terre et de vous assurer que tous les poteaux sont parfaitement droits. Cela prend plus de temps au début, mais la maison est beaucoup plus solide.

L'Expérience : Chasser les anomalies

Pour tester ces méthodes, l'auteur a créé un jeu de données où la plupart des points sont "normaux" (ils vivent dans des petites bulles ou sur des lignes droites) et quelques points sont "anormaux" (des intrus).

• Le défi : Dans le monde p-adique, les "intrus" ne sont pas toujours ceux qui sont les plus loin. Parfois, un intrus a une distance très petite selon les règles p-adiques, mais il est quand même bizarre.
• Le résultat :
  • La méthode RPCA (l'architecte préparé) a été excellente. Elle a réussi à repérer les intrus avec une précision incroyable, même quand les règles semblaient impossibles. Elle a compris que certains groupes de points (les "bulles paires") étaient plus importants que d'autres, et a ignoré le bruit.
  • La méthode NRPCA (le chasseur sauvage) a été moins précise pour trouver les intrus, mais elle a fait moins d'erreurs en accusant à tort des gens normaux (moins de "fausses alarmes").

Pourquoi est-ce important ?

Ce papier est important car il ouvre la porte à l'analyse de données dans des mondes où la logique classique échoue.

• En informatique : Cela pourrait aider à mieux comprendre les réseaux de neurones ou les structures de données complexes qui ressemblent à des arbres (comme les dendrogrammes).
• En cryptographie et sécurité : Cela permet de détecter des anomalies dans des systèmes où les données ne sont pas continues (comme des codes binaires ou des nombres modulo un nombre premier).

En résumé

Imaginez que vous essayez de ranger une bibliothèque.

• La PCA classique dit : "Rangez les livres par taille, du plus petit au plus grand."
• La PCA p-adique de Tomoki Mihara dit : "Oubliez la taille. Regardez la 'parenté' des livres. Si deux livres partagent le même nombre de pages dans leur histoire (leur structure mathématique), mettez-les ensemble, même s'ils ont des tailles différentes."

L'auteur a inventé une nouvelle façon de trier le chaos dans un univers où les règles de la distance sont inversées, et il a prouvé que sa méthode fonctionne mieux que les anciennes techniques pour trouver les "mauvais élèves" dans la classe. C'est une belle démonstration de comment les mathématiques pures peuvent résoudre des problèmes très pratiques dans des contextes très exotiques.

Résumé technique

Voici un résumé technique détaillé de l'article « p-adic Principal Component Analysis » de Tomoki Mihara, rédigé en français.

1. Problématique et Contexte

L'analyse en composantes principales (PCA) est un outil fondamental de réduction de dimensionnalité basé sur l'algèbre linéaire sur les réels ($\mathbb{R}$). Cependant, son application directe aux variables catégorielles (données discrètes) pose problème : l'encodage usuel dans un espace euclidien peut créer des composantes « virtuelles » qui ne respectent pas la structure algébrique originale des données (par exemple, les opérations booléennes sur $\{0, 1\}$ ou l'arithmétique modulaire sur $\mathbb{Z}/n\mathbb{Z}$).

L'auteur propose de formuler une version p-adique de la PCA pour des données à valeurs dans $\mathbb{Q}_p^D$ ou $\mathbb{Z}_p^D$ (où $p$ est un nombre premier). L'objectif est de préserver la structure algébrique intrinsèque des données catégorielles en les plongeant dans un espace p-adique, qui possède une topologie totalement discontinue, contrairement à la connectivité de $\mathbb{R}$.

Défis majeurs identifiés :

• Absence de gradient : Les méthodes d'optimisation classiques basées sur le gradient (comme la descente de gradient) ne sont pas applicables car la différentiation des fonctions de perte (souvent basées sur des normes) n'est pas bien définie ou triviale dans le contexte p-adique (fonctions localement constantes).
• Non-diagonalisabilité : Contrairement aux matrices symétriques réelles, les matrices symétriques p-adiques ne sont pas nécessairement diagonalisables. La méthode standard de PCA (décomposition spectrale de la matrice de covariance) échoue donc.
• Défaut de l'orthogonalité standard : Le produit scalaire p-adique standard ne satisfait pas la condition de non-dégénérescence ($\langle v, v \rangle = 0 \iff v = 0$) de manière générale, rendant l'approche par produit scalaire inadaptée.
• Limites de la norme $\ell_\infty$ : Bien que la théorie des diviseurs élémentaires (forme normale de Smith) permette une factorisation matricielle exacte avec la norme $\ell_\infty$, cette approche est trop rigide pour des tâches comme la détection d'anomalies, où les normes $\ell_\infty$ des données anormales peuvent coïncider avec celles des données normales.

2. Méthodologie

L'article propose une approche heuristique basée sur une nouvelle définition de l'orthogonalité et des algorithmes d'optimisation discrets.

A. Orthogonalité p-adique et Projection

Au lieu d'utiliser un produit scalaire, l'auteur définit l'orthogonalité par la relation entre la perpendicularité et le point le plus proche.

• Définition : Un vecteur $w$ est un composant de $v_0$ selon $v_1$ si $w$ est le plus proche voisin de $v_0$ dans l'espace engendré par $v_1$ (sous l'effet de la norme $\ell_q$).
• Orthogonalisation : Un vecteur $v_0$ est dit orthogonal à $v_1$ si son composant selon $v_1$ est nul.
• Algorithme de recherche : Pour trouver le coefficient optimal $c$ minimisant $\|v_0 - c v_1\|$, l'auteur utilise un algorithme de recherche sur un arbre de trie (trie tree) basé sur les expansions p-adiques des rapports d'entrées. Cela permet de résoudre le problème d'optimisation de manière exacte modulo $p^E$ sans utiliser de calculs flottants.

B. Algorithmes de PCA p-adique

Deux variantes de la PCA sont proposées pour la factorisation matricielle de rang faible ($Y \approx C X$) :

1. NRPCA (Non-reduced p-adic PCA) :

   • Stratégie : Sélectionne itérativement le premier vecteur non nul de la matrice résiduelle $Y$ comme nouveau vecteur de base.
   • Avantage : Faible coût de pré-calcul.
   • Inconvénient : Le système de coordonnées résultant n'est pas nécessairement orthogonal, ce qui peut entraîner une redondance et une sous-optimalité.

2. RPCA (Reduced p-adic PCA) :

   • Stratégie : Effectue d'abord une orthogonalisation itérée de l'ensemble des données $Y$ pour obtenir un système de coordonnées approximativement orthogonal ($Z$). Ensuite, les vecteurs de base sont sélectionnés parmi $Z$ (triés par norme décroissante).
   • Avantage : Produit un système de coordonnées plus stable et une meilleure approximation globale grâce à la réduction de la redondance.
   • Coût : Pré-calcul plus lourd (itérations d'orthogonalisation).

C. Optimisation Locale (Line Search)

Pour vérifier la qualité des solutions heuristiques, l'article introduit une « recherche linéaire p-adique » et une « descente de coordonnées p-adique ». Ces méthodes itèrent sur des sous-ensembles de vecteurs pour ajuster les coefficients et minimiser la perte, bien que les résultats expérimentaux montrent que les solutions initiales (NRPCA/RPCA) sont souvent déjà localement optimales.

3. Résultats Expérimentaux

Les expériences ont été menées sur des tâches de détection d'anomalies avec $p=7$, dimension $D=100$, et une précision $E=5$. Les données normales sont générées dans des sous-espaces spécifiques (boules fermées ou sous-espaces affines) avec du bruit, tandis que les données anormales sont dispersées.

Comparaison NRPCA vs RPCA :

• RPCA (Reduced) : Surpasse systématiquement NRPCA en termes de taux de vrais positifs (détection correcte des anomalies). L'orthogonalisation préalable permet de mieux capturer la structure sous-jacente des données normales, rendant les anomalies plus visibles par leur faible taux de compression.
  • Dans le cas des sous-espaces affines, RPCA détecte correctement les anomalies même lorsque la dimension du sous-espace normal ($D'$) est supérieure à la dimension de réduction ($D^-$), une situation où les méthodes linéaires classiques (comme la forme normale de Smith) échouent.
• NRPCA (Non-reduced) : Montre des taux de faux positifs plus faibles (moins d'erreurs de classification des données normales comme anormales). Elle est donc préférable si la priorité est de ne pas alerter à tort, au détriment de la détection complète des anomalies.

Cas particuliers :

• Lorsque le nombre de composantes normales est supérieur à la dimension de réduction ($B > D^-$), aucune méthode ne fonctionne parfaitement, ce qui est attendu théoriquement.
• RPCA parvient à distinguer des structures complexes (comme des boules p-adiques de rayons différents) que la factorisation basée sur la norme $\ell_\infty$ ne pourrait pas séparer.

4. Contributions Clés

1. Formulation théorique : Définition d'une notion d'orthogonalité p-adique basée sur la distance minimale (plus proche voisin) plutôt que sur le produit scalaire, contournant ainsi les problèmes de dégénérescence du produit scalaire p-adique.
2. Algorithmes d'optimisation : Développement d'algorithmes efficaces (arbres de trie) pour résoudre des problèmes d'optimisation de normes $\ell_q$ dans $\mathbb{Q}_p$ sans recours aux gradients.
3. Deux variantes de PCA : Introduction de NRPCA et RPCA, offrant un compromis entre la complexité de calcul et la qualité de l'orthogonalité du système de coordonnées.
4. Validation pratique : Démonstration que la PCA p-adique est supérieure aux méthodes classiques de réduction de dimension (comme la forme normale de Smith) pour la détection d'anomalies dans des données catégorielles structurées, en particulier lorsque les anomalies ne se distinguent pas simplement par une grande norme $\ell_\infty$.

5. Signification et Impact

Cet article ouvre une nouvelle voie pour l'analyse de données catégorielles et discrètes en exploitant la structure algébrique des nombres p-adiques.

• Au-delà de l'analyse réelle : Il démontre que l'embedding des données dans des espaces p-adiques permet de préserver des structures algébriques (comme les opérations booléennes ou modulaires) que l'embedding euclidien détruit.
• Applications potentielles : La méthode est particulièrement pertinente pour la détection d'anomalies dans des systèmes discrets (réseaux de capteurs, données de sécurité, bio-informatique) où les relations de voisinage sont mieux modélisées par la métrique ultramétrique p-adique que par la métrique euclidienne.
• Limites et perspectives : L'approche reste heuristique et dépend de la précision $E$ et du choix de la norme $\ell_q$. Néanmoins, elle offre une alternative robuste aux méthodes linéaires classiques dans des contextes où la diagonalisation est impossible.

En résumé, Tomoki Mihara propose un cadre mathématique et algorithmique solide pour adapter l'analyse en composantes principales aux données p-adiques, comblant un vide entre l'analyse de données catégorielles et la théorie des nombres, avec des résultats prometteurs pour l'apprentissage automatique non supervisé.