Fast exact inference for recursive cardinality models

Daniel Tarlow, Kevin Swersky, Richard S. Zemel, Ryan P. Adams, Brendan J. Frey

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationUncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012
Pages825-834
Number of pages10
StatePublished - Dec 1 2012
Externally publishedYes
Event28th Conference on Uncertainty in Artificial Intelligence, UAI 2012 - Catalina Island, CA, United States
Duration: Aug 15 2012Aug 17 2012

Publication series

NameUncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012

Other

Other28th Conference on Uncertainty in Artificial Intelligence, UAI 2012
Country/TerritoryUnited States
CityCatalina Island, CA
Period8/15/128/17/12

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Fast exact inference for recursive cardinality models'. Together they form a unique fingerprint.

Cite this