Reconstruction of 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 towards
developing universal reconstruction algorithms which are both computationally
efficient and require the minimal amount of expensive data. We introduce a new
method, Interaction Screening, which accurately estimates the model parameters
using local optimization problems. The algorithm provably achieves perfect
graph structure recovery with an information-theoretically 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 a real data produced by a D-Wave
quantum computer. This study shows that the Interaction Screening method is an
exact, tractable and optimal technique universally solving the inverse Ising
problem.

本文介绍一种名为 Interaction Screening 的新方法，使用本地优化问题准确估计模型参数，这个算法在信息论上优化样本数量的条件下可以实现完美的图形结构恢复，证明了 Interaction Screening 方法是一种准确、可行和最优的通用逆向 Ising 问题解决技术。