On Learning Discrete Graphical Models Using Greedy Methods

Details On Learning Discrete Graphical Models Using Greedy Methods On Learning Discrete Graphical Models Using Greedy Methods

2011-07-16

arxiv.org/abs/1107.3258v1

Computer Science

Learning

Scientific paper

In this paper, we address the problem of learning the structure of a pairwise graphical model from samples in a high-dimensional setting. Our first main result studies the sparsistency, or consistency in sparsity pattern recovery, properties of a forward-backward greedy algorithm as applied to general statistical models. As a special case, we then apply this algorithm to learn the structure of a discrete graphical model via neighborhood estimation. As a corollary of our general result, we derive sufficient conditions on the number of samples n, the maximum node-degree d and the problem size p, as well as other conditions on the model parameters, so that the algorithm recovers all the edges with high probability. Our result guarantees graph selection for samples scaling as n = Omega(d^2 log(p)), in contrast to existing convex-optimization based algorithms that require a sample complexity of \Omega(d^3 log(p)). Further, the greedy algorithm only requires a restricted strong convexity condition which is typically milder than irrepresentability assumptions. We corroborate these results using numerical simulations at the end.

Affiliated with

Also associated with

No associations

Rating

On Learning Discrete Graphical Models Using Greedy Methods 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 On Learning Discrete Graphical Models Using Greedy Methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Learning Discrete Graphical Models Using Greedy Methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-478511