Fast Exact Inference for Recursive Cardinality Models

Understand

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.