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_3: We study the computational and sample complexity of parameter and structure learning in graphical models. Our main result shows that the class of factor graphs with bounded degree can be learned in polynomial time and from a polynomial number of training examples, assuming that the data is generated by a network in this class. This result covers both parameter estimation for a known network structure and structure learning. It implies as a corollary that we can learn factor graphs for both Bayesian networks and Markov networks of bounded degree, in polynomial time and sample complexity. Importantly, unlike standard maximum likelihood estimation algorithms, our method does not require inference in the underlying network, and so applies to networks where inference is intractable. We also show that the error of our learned model degrades gracefully when the generating distribution is not a member of the target class of networks. In addition to our main result, we show that the sample complexity of parameter learning in graphical models has an O(1) dependence on the number of variables in the model when using the KL-divergence normalized by the number of variables as the performance criterion.
Abbeel, @cite_3 considered the problem of reconstructing graphical models based on factor graphs, and proposed a polynomial time and sample complexity algorithm. However, the goal of their algorithm was not to reconstruct the true structure, but rather to produce a model whose distribution is close in Kullback-Leibler divergence to the true distribution. In applications it is often of interest to reconstruct the true structure which give some insights into the underlying structure of the inferred model.