Efficiently Learning Markov Random Fields from Dynamics

Jason Gaitonde, Ankur Moitra, Elchanan Mossel

Abstract

Learning the structure and parameters of high-order Markov Random Fields (MRFs) is a fundamental challenge in machine learning, traditionally hampered by the "noisy parity" barrier. When restricted to independent and identically distributed (i.i.d.) samples, learning an order-$k$ MRF typically requires $n^{\Theta(k)}$ time. This paper demonstrates that this computational barrier can be bypassed by shifting the learning paradigm from equilibrium snapshots to dynamical trajectories. By observing a system evolving under Glauber dynamics, we can recover the underlying graph structure and interaction strengths in polynomial time, specifically $O(n^2 \log n)$, regardless of the interaction order $k$.

1. Introduction

Markov Random Fields (MRFs) are essential for modeling complex dependencies in high-dimensional data, ranging from statistical physics to computer vision. However, the traditional reliance on i.i.d. samples presents two significant hurdles. First, generating independent samples from a known MRF is often NP-hard due to mixing time issues. Second, even if samples are available, learning the dependencies between variables is computationally prohibitive for higher-order interactions. This is known as the noisy parity barrier, where the time complexity scales exponentially with the interaction order $k$.

This research challenges the assumption that temporal correlation in data is a hindrance. Instead, it posits that the trajectory of a system—how it moves from one state to another—contains rich information about local dependencies that are lost in equilibrium snapshots. By analyzing the system's evolution under Glauber dynamics, we can treat the natural progression of the system as a series of local interventions.

2. Methodology

The proposed approach focuses on systems governed by Glauber dynamics, a stochastic process where variables are resampled one at a time based on the current state of their neighbors. The methodology is divided into two primary phases: structure learning and parameter learning.

2.1 Structure Learning via Local Statistics

To identify whether a dependency exists between variable $i$ and variable $j$, the authors introduce a novel local statistic based on specific update sequences. By monitoring a trajectory for an "$iijii$" pattern—where variable $i$ updates twice, followed by an update to $j$, and then two more updates to $i$—the algorithm can isolate the influence of $j$ on $i$.

This method is remarkably efficient because it only requires observing pairs of variables. Unlike i.i.d. methods that must search through all possible $k$-sized neighborhoods, this dynamical approach detects the change in the update bias of $i$ caused by the flip of $j$. This allows the algorithm to identify the graph structure in $O(n^2 \log n)$ time, effectively decoupling the complexity from the interaction order $k$.

2.2 Parameter Learning

Once the dependency graph is established, the interaction strengths (parameters) are estimated using node-wise logistic regression. While the samples in a trajectory are highly correlated, the authors prove that Glauber dynamics provide sufficient "unpredictability." By treating the dynamics as a Santha-Vazirani source, they demonstrate that the system generates enough entropy to satisfy the conditions required for convex optimization to converge to the true parameters.

3. Experimental Results

The algorithm was evaluated against Sparsitron, the state-of-the-art algorithm for learning MRFs from i.i.d. samples, using synthetic benchmarks designed to trigger the noisy parity barrier.

  • Sparse Parity with Noise (SPN): In cases where a variable's state depends on the XOR sum of $k-1$ other variables, the dynamical algorithm achieved 100% success in recovering the structure for $n=40$ and $k=7$ within seconds.
  • Performance Comparison: While the proposed algorithm scaled efficiently, the i.i.d. baseline failed to recover the neighborhood within a 1500-second limit as the problem size increased, illustrating the practical impact of bypassing the $n^{\Theta(k)}$ runtime.
  • Latent Variables: A significant theoretical and practical finding is the algorithm's ability to recover dependencies even when some variables are hidden (latent). In the i.i.d. setting, this is often information-theoretically impossible, but the dynamical trajectory provides enough resolution to infer these hidden influences.

4. Discussion and Limitations

The "blessing of dynamics" suggests that the way a system reaches equilibrium is as informative as the equilibrium itself. However, the current framework has specific requirements:

  1. Update Visibility: The algorithm assumes that all update attempts are observable, including those where a variable's value does not change.
  2. Binary Constraints: The current formal proofs are limited to binary variables ($\pm 1$), though extensions to larger alphabets are theoretically plausible.
  3. Theoretical Bounds: While the algorithm performs exceptionally well in practice, the current theoretical constants are conservative, suggesting that the actual efficiency may be even higher than currently proven.

5. Conclusion

By leveraging the temporal information in Glauber dynamics, this work provides a path around the noisy parity barrier that has long limited the study of high-order MRFs. The transition from $n^{\Theta(k)}$ to $O(n^2 \log n)$ complexity represents a significant shift in the feasibility of learning complex, high-dimensional models from real-world, non-equilibrium data.

Summary updated

BibTeX
@inproceedings{gaitonde2024efficiently,
  author = {Jason Gaitonde and Ankur Moitra and Elchanan Mossel},
  title = {{Efficiently Learning Markov Random Fields from Dynamics}},
  booktitle = {STOC},
  year = {2024},
}
Figure