Computationally sufficient statistics for Ising models

원문 초록

Learning Gibbs distributions using only sufficient statistics has long been recognized as a computationally hard problem. On the other hand, computationally efficient algorithms for learning Gibbs distributions rely on access to full sample configurations generated from the model. For many systems of interest that arise in physical contexts, expecting a full sample to be observed is not practical, and hence it is important to look for computationally efficient methods that solve the learning problem with access to only a limited set of statistics. We examine the trade-offs between the power of computation and observation within this scenario, employing the Ising model as a paradigmatic example. We show that the couplings of the model can be learned to a desired accuracy from statistics whose order grows linearly with the $\ell_1$ width of the model and only logarithmically with the inverse of the accuracy. In particular, for a fixed accuracy, the required order is proportional to the width. This allows us to infer the model's structure, using statistics whose order grows logarithmically with the inverse of the weakest coupling, and also to learn its magnetic fields. When the width and the accuracy are fixed, the running time is polynomial in the number of variables. We also discuss a setting where prior information about structure of the model is available and show that the learning problem can be solved efficiently with even more limited observational power.