Efficiently Learning Ising Models on Arbitrary Graphs
Thursday, May 21, 2015 - 10:20am - 11:10am
We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Without restrictive assumptions on the model, it is unclear whether it is possible to avoid a computationally prohibitive exhaustive search over all possible neighborhoods for each node. In this talk we show how a simple greedy algorithm learns the structure of an Ising model on an arbitrary bounded-degree graph in time quadratic in the number of nodes. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information.