Reconstruction of Markov Random Fields from Samples: Some Easy Observations and Algorithms

Understand

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 non-degeneracy conditions it reconstructs the generating graph with high probability using $\Theta(d \epsilon^{-2}\delta^{-4} \log n)$ samples where $\epsilon,\delta$ depend on the local interactions.