Discrete distributions are learnable from metastable samples

Resumo Técnico: Distribuições discretas são aprendíveis a partir de amostras metaestáveis

Enunciado do Problema
Métodos de Monte Carlo via Cadeias de Markov (MCMC) são a ferramenta padrão para amostragem de distribuições discretas de alta dimensão, como distribuições de Gibbs ou modelos de Ising. No entanto, em sistemas que exibem mistura lenta — frequentemente devido a interações fortes ou baixas temperaturas — essas cadeias tornam-se frequentemente presas em estados metaestáveis. Nesses estados, a cadeia amostra de uma região restrita do espaço de estados por longos períodos, resultando em uma distribuição que difere significamente da verdadeira distribuição estacionária sob métricas globais como a divergência de Kullback-Leibler (KL) ou a distância de Variação Total (TV).

Algoritmos de aprendizagem convencionais, como a Estimativa de Máxima Verossimilhança (MLE), baseiam-se na minimização de métricas globais entre a distribuição dos dados e uma hipótese. Como a divergência KL entre uma distribuição metaestável e a verdadeira distribuição estacionária pode ser grande (por exemplo, proporcional ao logaritmo da probabilidade inversa da região metaestável), a MLE falha em recuperar os parâmetros reais do modelo mesmo com dados infinitos do estado metaestável. Isso levanta uma questão crítica: É possível aprender o modelo estacionário verdadeiro de uma cadeia de Markov dados apenas amostras extraídas de seus estados metaestáveis?

Metodologia e Definições
Os autores propõem um framework baseado na observação de que, embora as distribuições metaestáveis possam ser globalmente distintas da distribuição estacionária, suas probabilidades condicionais de variável única permanecem, em média, extremamente próximas das da verdadeira distribuição estacionária.

Para formalizar isso, o artigo introduz duas definições de metaestabilidade para uma distribuição $\nu$ em relação a uma cadeia de Markov reversível $P$ com distribuição estacionária $\mu$:

1. Metaestabilidade ($\eta$-metaestável): Uma distribuição é $\eta$-metaestável se sua distância TV de sua distribuição após um passo da cadeia for pequena ($|\nu - \nu P|_{TV} \le \eta$). Isso captura a noção intuitiva de uma distribuição que muda lentamente ao longo do tempo.
2. Metaestabilidade Forte ($\eta$-fortemente metaestável): Uma distribuição é $\eta$-fortemente metaestável se ela viola a condição de detalhe equilibrado da cadeia por no máximo $\eta$ em distância TV ($\frac{1}{2} \sum_{i,j} |P(i|j)\nu(j) - P(j|i)\nu(i)| \le \eta$).

O artigo estabelece que distribuições suportadas em regiões do espaço de estados com baixa condutância (gargalos) são exemplos de estados fortemente metaestáveis. Especificamente, para cadeias de mistura lenta, existem estados fortemente metaestáveis onde $\eta$ é exponencialmente pequeno em relação ao número de variáveis.

Resultados Teóricos Principais
A principal contribuição teórica é o Teorema 1, que prova que, para uma cadeia de Markov reversível satisfazendo uma condição de probabilidade de inversão de spin limitada, as condicionais de variável única de uma distribuição $\eta$-fortemente metaestável $\nu$ diferem das da verdadeira distribuição estacionária $\mu$ por uma distância TV média de $O(\eta/\omega_P)$, onde $\omega_P$ é um limite inferior nas probabilidades de transição.

Este resultado implica que, embora as distribuições globais possam estar distantes, as estruturas condicionais locais são quase idênticas. Uma vez que métodos de aprendizagem para modelos gráficos discretos, como a Pseudo-Verossimilhança (PL) e a Triagem de Interação (Interaction Screening), baseiam-se na minimização da divergência KL média entre condicionais de variável única em vez de métricas globais, esses métodos podem efetivamente recuperar o modelo verdadeiro a partir de dados metaestáveis.

Garantias de Aprendizagem
Os autores derivam garantias rigorosas de aprendizagem para o estimador de Pseudo-Verossimilhança (PL):

• Limites de Erro de Teste (Teorema 2): A perda PL computada a partir de amostras fortemente metaestáveis é próxima da perda ótima, com um termo de viés escalando como $O(\eta/\omega_P)$. Para sistemas de mistura lenta onde $\eta$ decai exponencialmente com o tamanho do sistema, este viés é dominado por erros estatísticos ($O(M^{-1/2})$) para tamanhos de amostra suficientemente grandes.
• Recuperação de Parâmetros (Teorema 3): Para modelos de Ising binários, os parâmetros de acoplamento podem ser aprendidos com um limite de erro que inclui um termo de viés proporcional a $\sqrt{\eta}$. A complexidade de amostragem escala como $\tilde{O}(\beta^d \log n)$, similar ao caso i.i.d., mas com um viés inevitável dependente do grau de metaestabilidade.
• Recuperação de Estrutura e Campo (Teoremas 4 & 5): O artigo estende essas garantias para a aprendizagem de estrutura (recuperação das arestas do grafo) e recuperação de campo magnético. Ele mostra que as arestas podem ser recuperadas com alta probabilidade, desde que as forças de acoplamento verdadeiras excedam um limiar determinado pelo termo de viés.

Experimentos Numéricos
As descobertas teóricas são validadas através de experimentos numéricos em dois modelos:

1. Modelo de Curie-Weiss: Os autores constroem estados fortemente metaestáveis explícitos centrados em torno dos mínimos locais do cenário de energia livre. Eles demonstram que a dinâmica de Glauber inicializada em um estado de magnetização positiva (onde a distribuição verdadeira possui magnetização negativa) produz amostras que são globalmente distantes da verdade. No entanto, o método PL recupera com sucesso o acoplamento ($J$) e o parâmetro de campo magnético ($h$) corretos, enquanto a MLE falha completamente, prevendo o sinal errado para o campo magnético.
2. Modelos de Spin Glass de Ordem Superior: Os autores testam a aprendizagem em um modelo com alfabeto $q=3$ e interações de terceira ordem (hipergrafo). Apesar de a cadeia ficar presa em estados metaestáveis de maior energia comparados ao estado fundamental, o método PL recupera com sucesso tanto a estrutura do modelo (hiperarestas) quanto os parâmetros de acoplamento.

Significância e Alegações
O artigo afirma demonstrar rigorosamente que os dados "ruins" produzidos por cadeias de Markov de mistura lenta não são inúteis para a aprendizagem. Ao mudar o foco do ajuste de distribuição global para o ajuste condicional local, os autores mostram que o modelo estacionário verdadeiro pode ser recuperado a partir de amostras metaestáveis.

As principais alegações incluem:

• Robustez da Aprendizagem Condicional: Métodos baseados em condicionais de variável única (como PL) são robustos às discrepâncias globais causadas pela metaestabilidade, desde que a metaestabilidade seja "forte" (ou seja, a violação do detalhe equilibrado seja pequena).
• Existência de Estados Metaestáveis Aprendíveis: O artigo fornece construções explícitas mostrando que estados metaestáveis decorrentes de conjuntos de baixa condutância no espaço de estados satisfazem a condição de metaestabilidade forte necessária para a aprendizagem.
• Generalização: Os resultados sugerem que a aprendizagem de distribuições discretas é possível mesmo quando os dados estão restritos a regiões específicas do espaço de estados, desde que o algoritmo de aprendizagem explore a estrutura condicional da distribuição.

Os autores observam que, embora o viés nos estimadores de parâmetros dependa do parâmetro de metaestabilidade $\eta$, para sistemas que exibem mistura lenta, esse viés é frequentemente exponencialmente pequeno, tornando as garantias de aprendizagem quase ótimas no limite de grandes tamanhos de sistema. O trabalho une conceitos de física estatística (metaestabilidade, mínimos de energia livre) com a teoria de aprendizagem estatística, oferecendo uma justificação teórica para o sucesso empírico da aprendizagem a partir de dados dinâmicos não-equilibrados ou presos.