Learning Ising and Potts Models with Latent Variables

Surbhi GoelAISTATS 2020 · OpenReview

Abstract

We study the problem of learning graphical models with latent variables. We give the first efficient algorithms for learning: 1) ferromagnetic Ising models with latent variables under arbitrary external fields and 2) Restricted Potts Models (RPMs). By proving that observed variables sharing a latent neighbor exhibit a minimum level of statistical "influence," we demonstrate that a simple greedy algorithm can accurately reconstruct the underlying network with optimal scaling relative to the number of variables.

Introduction

Graphical models, such as Ising and Potts models, are fundamental for representing high-dimensional dependencies in fields ranging from physics to machine learning. However, real-world data often involves latent (hidden) variables—unmeasured factors that influence observed data. These hidden variables induce complex dependencies, making structure recovery (or "reverse-engineering" the graph) a significant challenge. While previous research focused on fully observed models, learning models with latent variables remained difficult, particularly when dealing with arbitrary external fields.

The "Two-Hop" Influence

In restricted bipartite models like Restricted Boltzmann Machines (RBMs), observed nodes do not interact directly; they communicate solely through latent nodes. The core innovation of this work is proving that this "two-hop" interaction leaves a statistically detectable footprint that cannot be masked by conflicting external fields.

For RBMs, the author proves that the conditional covariance between two observed nodes sharing a latent neighbor remains bounded away from zero. This is achieved using Percus’s transformation, a technique that isolates correlations by analyzing symmetry across graph copies. For Potts models (multi-state systems), the Random Cluster Expansion is used to define an "influence function" that remains significant for nodes sharing a latent neighbor.

Algorithmic Framework

The proposed LearnRBMNbhd algorithm uses a Greedy Maximization strategy. It iteratively identifies the "two-hop" neighborhood of each node by maximizing the influence functions. This is followed by a pruning step to eliminate false positives, ensuring a clean reconstruction of the Markov blanket for each observed variable in $\tilde{O}(n^2)$ time.

Results and Sample Complexity

A major theoretical win is that the sample complexity scales with $O(\log n)$, where $n$ is the number of variables. This dimension independence makes the algorithm highly efficient for high-dimensional data, provided the underlying graph is relatively sparse.

Sample complexity scaling for different graph sizes (n=5, 10, 15), showing the fraction of successful runs vs. number of samples.

As shown in the figure above, the fraction of successful runs reaches 1.0 as the number of samples increases, with the required samples scaling optimally with the system size.

Empirical Validation: MNIST

Beyond synthetic tests, the algorithm was applied to binarized MNIST data. Although the ground truth graph is unknown, the algorithm identifies structural dependencies that correspond to the geometric features of handwritten digits.

Heatmaps of learned structural dependencies in MNIST digits, capturing the "shape" of the data through latent dependencies.

The heatmaps demonstrate that the algorithm captures meaningful clusters, effectively identifying which pixels are statistically linked through hidden features.

Conclusion and Future Directions

This work provides the first efficient algorithms for learning ferromagnetic RBMs with arbitrary fields and RPMs. While the $O(\log n)$ sample complexity is optimal, the algorithm's performance scales poorly with the weight parameter $\lambda$. Future work will focus on improving this dependency and extending the framework to non-ferromagnetic (frustrated) systems, which contain a mix of positive and negative interactions.

Summary updated

Abstract

We study the problem of learning graphical models with latent variables. We give the {\em first} efficient algorithms for learning: 1) ferromagnetic Ising models with latent variables under {\em ar...
BibTeX
@inproceedings{goel2020learning,
  author = {Surbhi Goel},
  title = {{Learning Ising and Potts Models with Latent Variables}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=JxSIkwW5R-5},
}
Figure