TY - GEN

T1 - Fast exact inference for recursive cardinality models

AU - Tarlow, Daniel

AU - Swersky, Kevin

AU - Zemel, Richard S.

AU - Adams, Ryan P.

AU - Frey, Brendan J.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84886079293&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84886079293&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84886079293

SN - 9780974903989

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

SP - 825

EP - 834

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

T2 - 28th Conference on Uncertainty in Artificial Intelligence, UAI 2012

Y2 - 15 August 2012 through 17 August 2012

ER -