Optimal structure and parameter learning of Ising models

Andrey Y. Lokhov, Marc Vuffray, Sidhant Misra, Michael Chertkov

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

Reconstruction of the structure and parameters of an Ising model from binary samples is a problem of practical importance in a variety of disciplines, ranging from statistical physics and computational biology to image processing and machine learning. The focus of the research community shifted toward developing universal reconstruction algorithms that are both computationally efficient and require the minimal amount of expensive data. We introduce a new method, interaction screening, which accurately estimates model parameters using local optimization problems. The algorithm provably achieves perfect graph structure recovery with an informationtheoretically optimal number of samples, notably in the low-Temperature regime, which is known to be the hardest for learning. The efficacy of interaction screening is assessed through extensive numerical tests on synthetic Ising models of various topologies with different types of interactions, as well as on real data produced by a D-Wave quantum computer. This study shows that the interaction screening method is an exact, tractable, and optimal technique that universally solves the inverse Ising problem.

Original languageEnglish (US)
Article numbere1700791
JournalScience Advances
Volume4
Issue number3
DOIs
StatePublished - Mar 16 2018
Externally publishedYes

ASJC Scopus subject areas

  • General

Fingerprint

Dive into the research topics of 'Optimal structure and parameter learning of Ising models'. Together they form a unique fingerprint.

Cite this