Approximating Max-Sum-Product Problems using Multiplicative Error Bounds

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.