Fast Exact Inference for Recursive Cardinality Models

DSpace/Manakin Repository

Fast Exact Inference for Recursive Cardinality Models

Citable link to this page


Title: Fast Exact Inference for Recursive Cardinality Models
Author: Tarlow, Daniel; Swersky, Kevin; Zemel, Richard S.; Adams, Ryan Prescott

Note: Order does not necessarily reflect citation order of authors.

Citation: Tarlow, Daniel, Kevin Swersky, Richard S. Zemel, Ryan Prescott Adams, and Brendan Frey. 2012. "Fast Exact Inference for Recursive Cardinality Models." In Proceedings of the Twenty-Eighth Conference Conference on Uncertainty in Artificial Intelligence (UAI), ed. Nando de Freitas, Kevin Murphy, Aug 14-18 2012, Catalina Island, CA. 825-834. Corvallis, Oregon: AUAI Press.
Full Text & Related Files:
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(D log D) 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(D log2 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.
Published Version:
Other Sources:
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search