Approximation by Quantization

摘要

Inference in graphical models consists of repeat edly multiplying and summing out potentials. It is generally intractable because the derived po tentials obtained in this way can be exponen tially large. Approximate inference techniques such as belief propagation and variational meth ods combat this by simplifying the derived poten tials, typically by dropping variables from them. We propose an alternate method for simplifying potentials: quantizing their values. Quantiza tion causes different states of a potential to have the same value, and therefore introduces context specific independencies that can be exploited to represent the potential more compactly. We use algebraic decision diagrams (ADDs) to do this efficiently. We apply quantization and ADD re duction to variable elimination and junction tree propagation, yielding a family of bounded ap proximate inference schemes. Our experimen tal tests show that our new schemes significantly outperform state-of-the-art approaches on many benchmark instances.