### 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 language | English (US) |
---|---|

Title of host publication | Uncertainty in Artificial Intelligence - Proceedings of the 28th Conference, UAI 2012 |

Pages | 825-834 |

Number of pages | 10 |

State | Published - Dec 1 2012 |

Externally published | Yes |

Event | 28th Conference on Uncertainty in Artificial Intelligence, UAI 2012 - Catalina Island, CA, United States Duration: Aug 15 2012 → Aug 17 2012 |

### Publication series

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

### Other

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

Country | United States |

City | Catalina Island, CA |

Period | 8/15/12 → 8/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

*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).