We propose a multiplicative approximation scheme (MAS) for inference problems

in graphical models, which can be applied to various inference algorithms. The

method uses \epsilon-decompositions which decompose functions used throughout the

inference procedure into functions over smaller sets of variables with a known

error \epsilon. MAS translates these local approximations into bounds on the accuracy

of the results. We show how to optimize \epsilon-decompositions and provide a fast

closed-form solution for an L2 approximation. Applying MAS to the Variable

Elimination inference algorithm, we introduce an algorithm we call DynaDecomp

which is extremely fast in practice and provides guaranteed error bounds on the

result. The superior accuracy and efficiency of DynaDecomp is demonstrated.

PDF file

In  NIPS

Details