Proceedings

Multi-Evidence Lifted Message Passing, with Application to PageRank and the Kalman Filter

Babak Ahmadi, Kristian Kersting, Scott Sanner

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1152-1157.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-197

Abstract

Lifted message passing algorithms exploit repeated structure within a given graphical model to answer queries efficiently. Given evidence, they construct a lifted network of supernodes and superpotentials corresponding to sets of nodes and potentials that are indistinguishable given the evidence. Recently, efficient algorithms were presented for updating the structure of an existing lifted network with incremental changes to the evidence. In the inference stage, however, current algorithms need to construct a separate lifted network for each evidence case and run a modified message passing algorithm on each lifted network separately. Consequently, symmetries across the inference tasks are not exploited. In this paper, we present a novel lifted message passing technique that exploits symmetries across multiple evidence cases. The benefits of this multi-evidence lifted inference are shown for several important AI tasks such as computing personalized PageRanks and Kalman filters via multi-evidence lifted Gaussian belief propagation.

Babak Ahmadi, Kristian Kersting, and Scott Sanner. 2011. Multi-Evidence Lifted Message Passing, with Application to PageRank and the Kalman Filter. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1152–1157. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-197
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards