Nonparametric undirected graphical model selection using diffusion models

Résumé Technique : Sélection de Modèles Graphiques Non Paramétriques Non Orientés à l'aide de Modèles de Diffusion

Énoncé du Problème
Les modèles graphiques non orientés fournissent un cadre pour représenter les structures d'indépendance conditionnelle entre des variables aléatoires de haute dimension. Bien que la sélection de modèles soit un problème central en statistique de haute dimension avec des applications en génomique, en neurosciences et en finance, la plupart des méthodes existantes reposent sur des hypothèses paramétriques (par exemple, les modèles graphiques gaussiens ou les modèles d'Ising). Ces méthodes échouent souvent lorsque la distribution réelle s'écarte de la forme paramétrique supposée. Des approches non paramétriques existent, mais elles sont statistiquement complexes en raison de la « malédiction de la dimensionnalité » dans l'estimation de densité, ainsi que de la complexité supplémentaire liée à l'estimation des dérivées du second ordre (le Hessien du logarithme de la densité), qui sont nécessaires pour identifier la structure du graphe via l'équivalence $(i, j) \notin E_0 \iff \frac{\partial^2 \log p_0}{\partial x_i \partial x_j} = 0$.

Méthodologie
Les auteurs proposent une nouvelle approche non paramétrique de sélection de modèles graphiques non orientés basée sur les modèles de diffusion. La méthode exploite le fait que les modèles de diffusion peuvent estimer les fonctions de score (gradients du logarithme de la densité) et s'adapter aux structures de faible dimension sans souffrir de la pleine malédiction de la dimensionnalité.

La procédure proposée, résumée dans l'Algorithme 1, consiste en les étapes suivantes :

1. Estimation de la Fonction de Score : En utilisant un cadre de modélisation de diffusion standard (spécifiquement le Modèle de Diffusion Probabiliste de Débruitage, DDPM), les auteurs estiment une famille de fonctions de score $f_0(x, t) = \nabla \log p_t(x)$, où $p_t$ est la densité marginale du processus de diffusion direct à un instant $t$. Ceci est réalisé par score matching sur les données observées.
2. Estimation du Hessien via la Formule de Tweedie : Au lieu de dériver directement la fonction de score estimée (ce qui est numériquement instable), la méthode utilise la formule de Tweedie du second ordre. Cette formule relie le Hessien du logarithme de la densité $\nabla^2 \log p_t(x)$ à la covariance conditionnelle des données originales $X_0$ étant donné l'observation bruitée $X_t = x$ :
   $$\nabla^2 \log p_t(x) = \sigma_t^{-4} \mu_t^2 \text{Cov}[X_0 | X_t = x] - \sigma_t^{-2} I_D$$
   où $\mu_t$ et $\sigma_t$ sont les paramètres du processus d'Ornstein-Uhlenbeck direct.
3. Récupération du Graphe : La méthode estime la covariance conditionnelle $\text{Cov}[X_0 | X_t = x]$ en utilisant l'échantillonnage de Monte Carlo à partir du processus de diffusion inverse. Plus précisément, pour un temps $t$ fixé et un vecteur aléatoire $U_t$, les auteurs calculent l'espérance empirique des valeurs absolues des entrées du Hessien estimé, $E_n[|\hat{H}_{ij}(U_t, t)|]$.
4. Seuillage et Clustering : Un arc $(i, j)$ est inclus dans le graphe estimé si la magnitude moyenne de l'entrée du Hessien dépasse un seuil $\tau$. Pour gérer le réglage pratique, les auteurs proposent d'agréger l'information à travers plusieurs petits pas de temps $t_1, \dots, t_M$ et d'appliquer le clustering K-means aux valeurs standardisées du Hessien pour séparer les arcs des non-arcs.

Principales Contributions Théoriques
L'article établit des garanties théoriques rigoureuses pour la méthode proposée sous des conditions de régularité modérées (spécifiquement, que $\log p_0$ appartienne à une classe de Hölder $\mathcal{H}_{\beta, K}$) :

• Taux de Décroissance : Les auteurs prouvent que la covariance conditionnelle $\text{Cov}[X_{0,i}, X_{0,j} | X_t = x]$ décroît à des taux différents selon la distance de graphe $d(i, j)$ entre les nœuds. Pour les arcs ($d(i, j)=1$), la covariance décroît en $O(t^2)$, tandis que pour les non-arcs ($d(i, j) \ge 2$), elle décroît plus rapidement, soit en $O(t^{(\beta+2)\wedge 5/2})$.
• Consistance de la Sélection : Sous l'hypothèse que l'estimateur de la fonction de score converge vers la véritable fonction de score à un taux $\epsilon_n$, les auteurs dérivent une borne supérieure non asymptotique de la probabilité d'une sélection de graphe incorrecte. Ils montrent qu'avec des choix appropriés du paramètre de temps $t$ et du seuil $\tau$, l'estimateur est consistant (c'est-à-dire $P(\hat{G}_{t, \tau} \neq G_0) = o(1)$) dans un régime de dimension fixe.
• Évitement de l'Estimation Directe du Hessien : En utilisant le processus de diffusion et la formule de Tweedie, la méthode contourne la nécessité de dériver directement le Hessien du logarithme de la densité de la distribution originale $p_0$, ce qui est statistiquement plus exigeant.

Résultats Empiriques
Les auteurs évaluent leur méthode à travers des simulations étendues et deux analyses de données réelles :

• Simulations : La méthode a été testée sur quatre distributions : deux gaussiennes et deux non gaussiennes (distribution Butterfly et Copule Gaussienne). La méthode basée sur la diffusion (DDPM) a performé de manière compétitive avec les modèles paramétriques correctement spécifiés (par exemple, le Graphical Lasso pour les données gaussiennes) et a nettement surpassé les bases non paramétriques existantes (SING et L-SING) sur toutes les distributions. Notamment, elle a obtenu une récupération parfaite des graphes dans les contextes non gaussiens où les méthodes paramétriques ont échoué.
• Analyse d'Images (MNIST) : Appliquée au jeu de données MNIST ($D=784$), la méthode a récupéré un graphe d'indépendance conditionnelle creux cohérent avec le principe de localité des images (les pixels étant connectés principalement à leurs voisins immédiats). Elle a également identifié une asymétrie spécifique dans les arcs diagonaux, reflétant l'inclinaison vers la droite des chiffres manuscrits dans ce jeu de données.
• Données Financières (Prix des Actions) : Appliquée aux rendements quotidiens de 28 entreprises industrielles, la méthode a récupéré un graphe creux de dépendances conditionnelles. Les arcs estimés ont montré des relations économiques significatives, incluant certaines non explicitement étiquetées comme concurrentes dans les bases de données externes, mais soutenues par des partenariats de chaîne d'approvisionnement ou technologiques.

Signification et Revendications
L'article affirme combler le fossé entre l'adaptabilité théorique des modèles de diffusion aux structures de graphes inconnues et leur application pratique pour l'estimation explicite de graphes. Les auteurs soulignent que leur méthode offre une alternative non paramétrique unifiée aux approches existantes, capable de gérer des distributions complexes et non gaussiennes sans nécessiter une spécification correcte du modèle. Ils notent que, bien que la consistance théorique soit établie pour des dimensions fixes, les résultats empiriques suggèrent que la méthode passe efficacement à des contextes de haute dimension ($D \gg n$), en exploitant la structure de faible dimension intrinsèque des données. Le travail conclut en identifiant l'extension aux asymptotiques de haute dimension et aux distributions discrètes comme des directions naturelles pour de futures recherches.