Approximating Max‐Sum‐Product Problems using Multiplicative Error Bounds

Christopher Meek and Ydo Wexler

in Bayesian Statistics 9

Published in print October 2011 | ISBN: 9780199694587
Published online January 2012 | e-ISBN: 9780191731921 | DOI:
Approximating Max‐Sum‐Product Problems using Multiplicative Error Bounds

More Like This

Show all results sharing this subject:

  • Probability and Statistics


Show Summary Details


We describe the Multiplicative Approximation Scheme (MAS) for approximate inference in multiplicative models. We apply this scheme to develop the DynaDecomp approximation algorithm. This algorithm can be used to obtain bounded approximations for various types of max‐sum‐product problems including the computation of the log probability of evidence, the log‐partition function, Most Probable Explanation (MPE) and maximum a posteriori probability (MAP) inference problems. We demonstrate that this algorithm yields bounded approximations superior to existing methods using a variety of large graphical models.

Keywords: Approximate inference; graphical models; max‐sum‐product; sum‐product

Chapter.  18262 words.  Illustrated.

Subjects: Probability and Statistics

Full text: subscription required

How to subscribe Recommend to my Librarian

Buy this work at Oxford University Press »

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.