|
|
|
|
Fast Exact Inference for Recursive Cardinality Models
Daniel Tarlow, Kevin Swersky, Richard Zemel, Ryan Adams, Brendan Frey
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.
Keywords:
Pages: 825-834
PS Link:
PDF Link: /papers/12/p825-tarlow.pdf
BibTex:
@INPROCEEDINGS{Tarlow12,
AUTHOR = "Daniel Tarlow
and Kevin Swersky and Richard Zemel and Ryan Adams and Brendan Frey",
TITLE = "Fast Exact Inference for Recursive Cardinality Models",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "825--834"
}
|
|
