出版社：Institute for Operations Research and the Management Sciences (INFORMS), Applied Probability Society
摘要：We consider the structure learning problem for graphical mod-els that we call loosely connected Markov random fields, in which thenumber of short paths between any pair of nodes is small, and presenta new conditional independence test based algorithm for learning theunderlying graph structure. The novel maximization step in our al-gorithm ensures that the true edges are detected correctly even whenthere are short cycles in the graph. The number of samples requiredby our algorithm is C log p, where p is the size of the graph and theconstant C depends on the parameters of the model. We show thatseveral previously studied models are examples of loosely connectedMarkov random fields, and our algorithm achieves the same or lowercomputational complexity than the previously designed algorithmsfor individual cases. We also get new results for more general graph-ical models, in particular, our algorithm learns general Ising modelson the Erd.os-R′enyi random graph G (p,cp) correctly with runningtime O(np5)
