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.
Note furthermore that two networks that differ only in the neighborhood of one node will have @math KL distance. Therefore, even in cases where it is promised that the KL distance between the generating distribution and any other distribution defined by another graph is as large as possible, the lower bounds on the KL distance is @math . Plugging this into the bounds in @cite_3 yields a polynomial sampling complexity in the size of the network in order to find the generating network compared to our logarithmic sampling complexity. For other work based on minimizing the KL divergence see the references in @cite_3 .
@cite_3
1550211845
Let @math be a set of elements and d a distance function defined among them. Let NNk(u) be the k elements in @math having the smallest distance to u. The k-nearest neighbor graph (knng) is a weighted directed graph @math such that E= (u,v), v∈NNk(u) . Several knng construction algorithms are known, but they are not suitable to general metric spaces. We present a general methodology to construct knngs that exploits several features of metric spaces. Experiments suggest that it yields costs of the form c1n1.27 distance computations for low and medium dimensional spaces, and c2n1.90 for high dimensional ones.