Timezone: »

 
Oral
MAS: a multiplicative approximation scheme for probabilistic inference
Ydo Wexler · Christopher Meek

Tue Dec 09 03:00 PM -- 03:20 PM (PST) @
in Oral session 4: Combinatorial Approximation »
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 $L_2$ 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.

Author Information

Ydo Wexler (Microsoft Research)
Christopher Meek (Microsoft Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors