Fast Exact Inference for Recursive Cardinality Models

Abstract

Cardinality potentials are a generally useful class of high order potential that affect probabilities based on how many of D binary variables are active. Maximum a posteriori (MAP) inference for cardinality potential models is well-understood, with efficient computations taking O(DlogD) time. Yet efficient marginalization and sampling have not been addressed as thoroughly in the machine learning community. We show that there exists a simple algorithm for computing marginal probabilities and drawing exact joint samples that runs in O(Dlog2 D) time, and we show how to frame the algorithm as efficient belief propagation in a low order tree-structured model that includes additional auxiliary variables. We then develop a new, more general class of models, termed Recursive Cardinality models, which take advantage of this efficiency. Finally, we show how to do efficient exact inference in models composed of a tree structure and a cardinality potential. We explore the expressive power of Recursive Cardinality models and empirically demonstrate their utility.

Appears in Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence (UAI2012)

References in corpus (1)

• Efficient Minimization of Decomposable Submodular Functions

Cited by in corpus (7)

• Multi-Instance Dynamic Ordinal Random Fields for Weakly-supervised Facial Behavior Analysis
• Gradient Estimation with Stochastic Softmax Tricks
• Exchangeable Variable Models
• A fast numerical method for max-convolution and the application to efficient max-product inference in Bayesian networks
• Tighter Linear Program Relaxations for High Order Graphical Models
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies
• Combining exome and gene expression datasets in one graphical model of disease to empower the discovery of disease mechanisms