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
CountryUnited 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

    Tarlow, D., Swersky, K., Zemel, R. S., Adams, R. P., & Frey, B. J. (2012). Fast exact inference for recursive cardinality models. In Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012 (pp. 825-834). (Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012).