Approximation by Quantization
This work addresses the problem of approximate inference in graphical models for researchers and practitioners, offering a novel method that improves performance over existing techniques.
The paper tackles the intractability of inference in graphical models by proposing quantization of potential values to introduce context-specific independencies, which are then exploited using algebraic decision diagrams for compact representation. Experimental results show that the new schemes significantly outperform state-of-the-art approaches on many benchmark instances.
Inference in graphical models consists of repeatedly multiplying and summing out potentials. It is generally intractable because the derived potentials obtained in this way can be exponentially large. Approximate inference techniques such as belief propagation and variational methods combat this by simplifying the derived potentials, typically by dropping variables from them. We propose an alternate method for simplifying potentials: quantizing their values. Quantization 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 reduction to variable elimination and junction tree propagation, yielding a family of bounded approximate inference schemes. Our experimental tests show that our new schemes significantly outperform state-of-the-art approaches on many benchmark instances.