Greedy Learning of Markov Network Structure

Details Greedy Learning of Markov Network Structure Greedy Learning of Markov Network Structure

2012-02-08

arxiv.org/abs/1202.1787v1

Statistics

Machine Learning

Preliminary version appeared in 48th Annual Allerton Conference on Communication, Control, and Computing, 2010. Full version s

Scientific paper

We propose a new yet natural algorithm for learning the graph structure of general discrete graphical models (a.k.a. Markov random fields) from samples. Our algorithm finds the neighborhood of a node by sequentially adding nodes that produce the largest reduction in empirical conditional entropy; it is greedy in the sense that the choice of addition is based only on the reduction achieved at that iteration. Its sequential nature gives it a lower computational complexity as compared to other existing comparison-based techniques, all of which involve exhaustive searches over every node set of a certain size. Our main result characterizes the sample complexity of this procedure, as a function of node degrees, graph size and girth in factor-graph representation. We subsequently specialize this result to the case of Ising models, where we provide a simple transparent characterization of sample complexity as a function of model and graph parameters. For tree graphs, our algorithm is the same as the classical Chow-Liu algorithm, and in that sense can be considered the extension of the same to graphs with cycles.

Affiliated with

Also associated with

No associations

Rating

Greedy Learning of Markov Network Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Greedy Learning of Markov Network Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Greedy Learning of Markov Network Structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-65253