Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Improved Approximate Sum-Product Inference Using Multiplicative Error Bounds

Christopher Meek and Ydo Wexler

Abstract

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.

Details

Publication typeInbook
PublisherOxford University Press
> Publications > Improved Approximate Sum-Product Inference Using Multiplicative Error Bounds