Publication
Multi-Evidence Lifted Message Passing, with Application to PageRank and the Kalman Filter
Babak Ahmadi; Kristian Kersting; Scott Sanner
In: Toby Walsh (Hrsg.). IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence. International Joint Conference on Artificial Intelligence (IJCAI-2011), July 16-22, Barcelona, Spain, Pages 1152-1158, IJCAI/AAAI, 2011.
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 multievidence lifted Gaussian belief propagation.