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 @math nodes and maximum degree @math given observations. We show that under mild non-degeneracy conditions it reconstructs the generating graph with high probability using @math samples where @math depend on the local interactions. For most local interaction @math are of order @math . Our results are optimal as a function of @math up to a multiplicative constant depending on @math 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 @math running time bound. In cases where the measure on the graph has correlation decay, the running time is @math for all fixed @math . 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 non-identifiability even for generic noise and interactions. Finally, we briefly show that in some simple cases, models with hidden nodes can also be recovered.
@cite_8: We focus on the problem of estimating the graph structure associated with a discrete Markov random field. We describe a method based on l1-regularized logistic regression, in which the neighborhood of any given node is estimated by performing logistic regression subject to an l-constraint. Our framework applies to the high-dimensional setting, in which both the number of nodes p and maximum neighborhood sizes d are allowed to grow as a function of the number of observations n. Our main result is to establish sufficient conditions on the triple (n, p, d) for the method to succeed in consistently estimating the neighborhood of every node in the graph simultaneously. Under certain mutual incoherence conditions analogous to those imposed in previous work on linear regression, we prove that consistent neighborhood selection can be obtained as long as the number of observations n grows more quickly than 6d6 log d + 2d5 log p, thereby establishing that logarithmic growth in the number of samples n relative to graph size p is sufficient to achieve neighborhood consistency.
The same problem as in the present work (but restricted to the Ising model) was studied by Wainwright, @cite_8 , where an algorithm based on @math -regularization was introduced. The algorithm presented is efficient also for dense graphs with running time @math but is applicable only in very restricted settings. The work only applies to the Ising model and more importantly only models with edge interactions (no larger cliques are allowed). The most important restrictions are the two conditions in the paper (A1 and A2). Condition A1 requires (among other things) that the covariates [spins] do not become overly dependent''. Verifying when the conditions holds seems hard. However, it is easy to see that this condition fails for standard models such as the Ising model on the lattice or on random @math -regular graphs when the model is at low temperatures, i.e. for @math in the case of the two dimensional Ising model and @math for random @math -regular graphs.