Lifted Probabilistic Inference with Counting Formulas
Lifted inference algorithms exploit repeated structure in probabilistic models to answer queries efficiently. Previous work such as de Salvo Braz et al.'s first-order variable elimination (FOVE) has focused on the sharing of potentials across interchangeable random variables. In this paper, we...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
AAAI Press
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72028 https://orcid.org/0000-0001-6054-7145 |
| _version_ | 1826208489673850880 |
|---|---|
| author | Haimes, Michael M. Kaelbling, Leslie P. Kersting, Kristian Milch, Brian Zettlemoyer, Luke S. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Haimes, Michael M. Kaelbling, Leslie P. Kersting, Kristian Milch, Brian Zettlemoyer, Luke S. |
| author_sort | Haimes, Michael M. |
| collection | MIT |
| description | Lifted inference algorithms exploit repeated structure in probabilistic models to answer queries efficiently. Previous work such as de Salvo Braz et al.'s first-order variable elimination (FOVE) has focused on the sharing of potentials across interchangeable random variables. In this paper, we also exploit interchangeability within individual potentials by introducing counting formulas, which indicate how many of the random variables in a set have each possible value. We present a new lifted inference algorithm, C-FOVE, that not only handles counting formulas in its input, but also creates counting formulas for use in intermediate potentials. C-FOVE can be described succinctly in terms of six operators, along with heuristics for when to apply them. Because counting formulas capture dependencies among large numbers of variables compactly, C-FOVE achieves asymptotic speed improvements compared to FOVE. |
| first_indexed | 2024-09-23T14:06:09Z |
| format | Article |
| id | mit-1721.1/72028 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:06:09Z |
| publishDate | 2012 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | mit-1721.1/720282022-09-28T18:27:24Z Lifted Probabilistic Inference with Counting Formulas Haimes, Michael M. Kaelbling, Leslie P. Kersting, Kristian Milch, Brian Zettlemoyer, Luke S. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kaelbling, Leslie P. Haimes, Michael M. Kaelbling, Leslie P. Kersting, Kristian Milch, Brian Zettlemoyer, Luke S. Lifted inference algorithms exploit repeated structure in probabilistic models to answer queries efficiently. Previous work such as de Salvo Braz et al.'s first-order variable elimination (FOVE) has focused on the sharing of potentials across interchangeable random variables. In this paper, we also exploit interchangeability within individual potentials by introducing counting formulas, which indicate how many of the random variables in a set have each possible value. We present a new lifted inference algorithm, C-FOVE, that not only handles counting formulas in its input, but also creates counting formulas for use in intermediate potentials. C-FOVE can be described succinctly in terms of six operators, along with heuristics for when to apply them. Because counting formulas capture dependencies among large numbers of variables compactly, C-FOVE achieves asymptotic speed improvements compared to FOVE. United States. Defense Advanced Research Projects Agency (contract NBCHD030010) 2012-08-08T15:18:44Z 2012-08-08T15:18:44Z 2008-01 Article http://purl.org/eprint/type/JournalArticle 978-1-57735-368-3 http://hdl.handle.net/1721.1/72028 Haimes, Michael M., et al. "Lifted probabilistic inference with counting formulas." Proceedings of the 23rd National Conference on Artificial Intelligence (2008): 1062-1068. © 2008 AAAI Press https://orcid.org/0000-0001-6054-7145 en_US http://dl.acm.org/citation.cfm?id=1620237 Proceedings of the 23rd National Conference on Artificial Intelligence, (AAAI '08) Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf AAAI Press AAAI |
| spellingShingle | Haimes, Michael M. Kaelbling, Leslie P. Kersting, Kristian Milch, Brian Zettlemoyer, Luke S. Lifted Probabilistic Inference with Counting Formulas |
| title | Lifted Probabilistic Inference with Counting Formulas |
| title_full | Lifted Probabilistic Inference with Counting Formulas |
| title_fullStr | Lifted Probabilistic Inference with Counting Formulas |
| title_full_unstemmed | Lifted Probabilistic Inference with Counting Formulas |
| title_short | Lifted Probabilistic Inference with Counting Formulas |
| title_sort | lifted probabilistic inference with counting formulas |
| url | http://hdl.handle.net/1721.1/72028 https://orcid.org/0000-0001-6054-7145 |
| work_keys_str_mv | AT haimesmichaelm liftedprobabilisticinferencewithcountingformulas AT kaelblinglesliep liftedprobabilisticinferencewithcountingformulas AT kerstingkristian liftedprobabilisticinferencewithcountingformulas AT milchbrian liftedprobabilisticinferencewithcountingformulas AT zettlemoyerlukes liftedprobabilisticinferencewithcountingformulas |