Reconstruction of Markov random fields from samples: Some observations and algorithms

Guy Bresler, Elchanan Mossel, Allan Sly

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

Markov random fields are used to model high dimensional distributions in a number of applied areas. Much recent interest has been devoted to the reconstruction of the dependency structure from independent samples from the Markov random fields. We analyze a simple algorithm for reconstructing the underlying graph defining a Markov random field on n nodes and maximum degree d given observations. We show that under mild nondegeneracy conditions it reconstructs the generating graph with high probability using Θ(dε-2 δ-4 log n) samples, where e, δ depend on the local interactions. For most local interactions ε,δ are of order exp(- O(d)). Our results are optimal as a function of n up to a multiplicative constant depending on d and the strength of the local interactions. Our results seem to be the first results for general models that guarantee that the generating model is reconstructed. Furthermore, we provide explicit O(nd+2 ε-2 δ-4 log n) running-time bound. In cases where the measure on the graph has correlation decay, the running time is O(n2 log n) for all fixed d. We also discuss the effect of observing noisy samples and show that as long as the noise level is low, our algorithm is effective. On the other hand, we construct an example where large noise implies nonidentifiability even for generic noise and interactions. Finally, we briefly show that in some simple cases, models with hidden nodes can also be recovered.

Original languageEnglish (US)
Pages (from-to)563-578
Number of pages16
JournalSIAM Journal on Computing
Volume42
Issue number2
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

  • Algorithms
  • Correlation decay
  • Markov random fields

Fingerprint

Dive into the research topics of 'Reconstruction of Markov random fields from samples: Some observations and algorithms'. Together they form a unique fingerprint.

Cite this