Faster Algorithms for Max-Product Message-Passing

Details Faster Algorithms for Max-Product Message-Passing Faster Algorithms for Max-Product Message-Passing

2009-10-17

arxiv.org/abs/0910.3301v4

Computer Science

Artificial Intelligence

34 pages, 22 figures

Scientific paper

Maximum A Posteriori inference in graphical models is often solved via message-passing algorithms, such as the junction-tree algorithm, or loopy belief-propagation. The exact solution to this problem is well known to be exponential in the size of the model's maximal cliques after it is triangulated, while approximate inference is typically exponential in the size of the model's factors. In this paper, we take advantage of the fact that many models have maximal cliques that are larger than their constituent factors, and also of the fact that many factors consist entirely of latent variables (i.e., they do not depend on an observation). This is a common case in a wide variety of applications, including grids, trees, and ring-structured models. In such cases, we are able to decrease the exponent of complexity for message-passing by 0.5 for both exact and approximate inference.

Affiliated with

Also associated with

No associations

Rating

Faster Algorithms for Max-Product Message-Passing 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 Faster Algorithms for Max-Product Message-Passing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Algorithms for Max-Product Message-Passing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-89624