Discrete distributions are learnable from metastable samples

Résumé technique : Les distributions discrètes sont apprenables à partir d'échantillons métastables

Énoncé du problème
Les méthodes de Monte Carlo par chaînes de Markov (MCMC) sont l'outil standard pour l'échantillonnage de distributions discrètes de haute dimension, telles que les distributions de Gibbs ou les modèles d'Ising. Cependant, dans les systèmes présentant un mélange lent — souvent dû à de fortes interactions ou à des températures basses — ces chaînes se retrouvent fréquemment piégées dans des états métastables. Dans de tels états, la chaîne échantillonne une région restreinte de l'espace d'états pendant de longues périodes, ce qui produit une distribution qui diffère significativement de la véritable distribution stationnaire selon des métriques globales comme la divergence de Kullback-Leibler (KL) ou la distance de variation totale (TV).

Les algorithmes d'apprentissage conventionnels, tels que l'estimation du maximum de vraisemblance (MLE), reposent sur la minimisation de métriques globales entre la distribution des données et une hypothèse. Comme la divergence KL entre une distribution métastable et la véritable distribution stationnaire peut être grande (par exemple, proportionnelle au logarithme de l'inverse de la probabilité de la région métastable), la MLE échoue à récupérer les véritables paramètres du modèle même avec une quantité infinie de données issues de l'état métastable. Cela soulève une question critique : est-il possible d'apprendre le véritable modèle stationnaire d'une chaîne de Markov en utilisant uniquement des échantillons tirés de ses états métastables ?

Méthodologie et définitions
Les auteurs proposent un cadre basé sur l'observation selon laquelle, bien que les distributions métastables puissent être globalement distinctes de la distribution stationnaire, leurs probabilités conditionnelles mono-variables restent, en moyenne, extrêmement proches de celles de la véritable distribution stationnaire.

Pour formaliser cela, l'article introduit deux définitions de la métastabilité pour une distribution $\nu$ par rapport à une chaîne de Markov réversible $P$ ayant pour distribution stationnaire $\mu$ :

1. Métastabilité ($\eta$-métastable) : Une distribution est $\eta$-métastable si sa distance TV par rapport à la distribution après une étape de la chaîne est petite ($|\nu - \nu P|_{TV} \le \eta$). Cela capture la notion intuitive d'une distribution qui évolue lentement dans le temps.
2. Métastabilité forte ($\eta$-fortement métastable) : Une distribution est $\eta$-fortement métastable si elle viole la condition de l'équilibre détaillé de la chaîne d'au plus $\eta$ en distance TV ($\frac{1}{2} \sum_{i,j} |P(i|j)\nu(j) - P(j|i)\nu(i)| \le \eta$).

L'article établit que les distributions supportées sur des régions de l'espace d'états présentant une faible conductance (goulots d'étranglement) sont des exemples d'états fortement métastables. Plus précisément, pour les chaînes à mélange lent, il existe des états fortement métastables où $\eta$ est exponentiellement petit par rapport au nombre de variables.

Résultats théoriques clés
La contribution théorique centrale est le Théorème 1, qui prouve que pour une chaîne de Markov réversible satisfaisant une condition de probabilité de basculement de spin bornée, les conditionnelles mono-variables d'une distribution $\nu$ $\eta$-fortement métastable diffèrent de celles de la véritable distribution stationnaire $\mu$ d'une distance TV moyenne de $O(\eta/\omega_P)$, où $\omega_P$ est une borne inférieure sur les probabilités de transition.

Ce résultat implique que si les distributions globales peuvent être très éloignées de la distribution stationnaire, les structures conditionnelles locales sont presque identiques. Puisque les méthodes d'apprentissage pour les modèles graphiques discrets, telles que la pseudo-vraisemblance (PL) et le criblage d'interactions (Interaction Screening), reposent sur la minimisation de la divergence KL moyenne entre les conditionnelles mono-variables plutôt que sur des métriques globales, ces méthodes peuvent effectivement récupérer le véritable modèle à partir de données métastables.

Garanties d'apprentissage
Les auteurs dérivent des garanties d'apprentissage rigoureuses pour l'estimateur de pseudo-vraisemblance (PL) :

• Bornes d'erreur de test (Théorème 2) : La perte PL calculée à partir d'échantillons fortement métastables est proche de la perte optimale, avec un terme de biais évoluant comme $O(\eta/\omega_P)$. Pour les systèmes à mélange lent où $\eta$ décroît exponentiellement avec la taille du système, ce biais est dominé par les erreurs statistiques ($O(M^{-1/2})$) pour des tailles d'échantillons suffisamment grandes.
• Récupération de paramètres (Théorème 3) : Pour les modèles d'Ising binaires, les paramètres de couplage peuvent être appris avec une borne d'erreur incluant un terme de biais proportionnel à $\sqrt{\eta}$. La complexité d'échantillonnage est de l'ordre de $\tilde{O}(\beta^d \log n)$, similaire au cas i.i.d., mais avec un biais inévitable dépendant du degré de métastabilité.
• Récupération de la structure et du champ (Théorèmes 4 & 5) : L'article étend ces garanties à l'apprentissage de la structure (récupération des arêtes du graphe) et à la récupération du champ magnétique. Il montre que les arêtes peuvent être récupérées avec une haute probabilité, à condition que les véritables forces de couplage dépassent un seuil déterminé par le terme de biais.

Expériences numériques
Les résultats théoriques sont validés par des expériences numériques sur deux modèles :

1. Modèle de Curie-Weiss : Les auteurs construisent des états explicitement fortement métastables centrés autour des minima locaux du paysage d'énergie libre. Ils démontrent que la dynamique de Glauber initialisée dans un état de magnétisation positive (où la véritable distribution a une magnétisation négative) produit des échantillons globalement éloignés de la vérité. Cependant, la méthode PL réussit à récupérer le couplage ($J$) et le paramètre de champ magnétique ($h$) corrects, alors que la MLE échoue complètement, prédisant le mauvais signe pour le champ magnétique.
2. Modèles de verres de spins d'ordre supérieur : Les auteurs testent l'apprentissage sur un modèle avec un alphabet $q=3$ et des interactions de troisième ordre (hypergraphe). Malgré le fait que la chaîne reste bloquée dans des états métastables de plus haute énergie par rapport à l'état fondamental, la méthode PL réussit à récupérer à la fois la structure du modèle (hyperarêtes) et les paramètres de couplage.

Signification et revendications
L'article affirme démontrer rigoureusement que les "mauvaises" données produites par des chaînes de Markov à mélange lent ne sont pas inutiles pour l'apprentissage. En déplaçant l'attention de l'appariement de distribution globale vers l'appariement conditionnel local, les auteurs montrent que le véritable modèle stationnaire peut être récupéré à partir d'échantillons métastables.

Les principales revendications incluent :

• Robustesse de l'apprentissage conditionnel : Les méthodes basées sur les conditionnelles mono-variables (comme la PL) sont robustes aux écarts globaux causés par la métastabilité, à condition que la métastabilité soit "forte" (c'est-à-dire que la violation de l'équilibre détaillé soit faible).
• Existence d'états métastables apprenables : L'article fournit des constructions explicites montrant que les états métastables issus d'ensembles à faible conductance dans l'espace d'états satisfont la condition de métastabilité forte requise pour l'apprentissage.
• Généralisation : Les résultats suggèrent qu'il est possible d'apprendre des distributions discrètes même lorsque les données sont contraintes à des régions spécifiques de l'espace d'états, à condition que l'algorithme d'apprentissage exploite la structure conditionnelle de la distribution.

Les auteurs notent que bien que le biais dans les estimations de paramètres dépende du paramètre de métastabilité $\eta$, pour les systèmes présentant un mélange lent, ce biais est souvent exponentiellement petit, rendant les garanties d'apprentissage quasi optimales dans la limite de grandes tailles de système. Ce travail jette un pont entre les concepts de la physique statistique (métastabilité, minima d'énergie libre) et la théorie de l'apprentissage statistique, offrant une justification théorique au succès empirique de l'apprentissage à partir de données dynamiques hors équilibre ou piégées.