Timezone: »
Statistical relational models provide compact encodings of probabilistic dependencies in relational domains, but result in highly intractable graphical models. The goal of lifted inference is to carry out probabilistic inference without needing to reason about each individual separately, by instead treating exchangeable, undistinguished objects as a whole. In this paper, we study the domain recursion inference rule, which, despite its central role in early theoretical results on domain-lifted inference, has later been believed redundant. We show that this rule is more powerful than expected, and in fact significantly extends the range of models for which lifted inference runs in time polynomial in the number of individuals in the domain. This includes an open problem called S4, the symmetric transitivity model, and a first-order logic encoding of the birthday paradox. We further identify new classes S2FO2 and S2RU of domain-liftable theories, which respectively subsume FO2 and recursively unary theories, the largest classes of domain-liftable theories known so far, and show that using domain recursion can achieve exponential speedup even in theories that cannot fully be lifted with the existing set of inference rules.
Author Information
Seyed Mehran Kazemi (UBC)
Angelika Kimmig (KU Leuven)
Guy Van den Broeck (UCLA)
David Poole (UBC)
More from the Same Authors
-
2021 Spotlight: Tractable Regularization of Probabilistic Circuits »
Anji Liu · Guy Van den Broeck -
2021 Poster: A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference »
Antonio Vergari · YooJung Choi · Anji Liu · Stefano Teso · Guy Van den Broeck -
2021 Oral: A Compositional Atlas of Tractable Circuit Operations for Probabilistic Inference »
Antonio Vergari · YooJung Choi · Anji Liu · Stefano Teso · Guy Van den Broeck -
2021 Poster: Tractable Regularization of Probabilistic Circuits »
Anji Liu · Guy Van den Broeck -
2019 : Poster Session #1 »
Adarsh Jamadandi · Sophia Sanborn · Huaxiu Yao · Chen Cai · Yu Chen · Jean-Marc Andreoli · Niklas Stoehr · Shih-Yang Su · Tony Duan · Fábio Ferreira · Davide Belli · Amit Boyarski · Ze Ye · Elahe Ghalebi · Arindam Sarkar · MAHMOUD KHADEMI · Evgeniy Faerman · Joey Bose · Jiaqi Ma · Lin Meng · Seyed Mehran Kazemi · Guangtao Wang · Tong Wu · Yuexin Wu · Chaitanya K. Joshi · Marc Brockschmidt · Daniele Zambon · Colin Graber · Rafaël Van Belle · Osman Asif Malik · Xavier Glorot · Mario Krenn · Chris Cameron · Binxuan Huang · George Stoica · Alexia Toumpa -
2018 Poster: SimplE Embedding for Link Prediction in Knowledge Graphs »
Seyed Mehran Kazemi · David Poole -
2017 Tutorial: Statistical Relational Artificial Intelligence: Logic, Probability and Computation »
Luc De Raedt · David Poole · Kristian Kersting · Sriraam Natarajan -
2015 Poster: Tractable Learning for Complex Probability Queries »
Jessa Bekker · Jesse Davis · Arthur Choi · Adnan Darwiche · Guy Van den Broeck -
2013 Poster: On the Complexity and Approximation of Binary Evidence in Lifted Inference »
Guy Van den Broeck · Adnan Darwiche -
2013 Spotlight: On the Complexity and Approximation of Binary Evidence in Lifted Inference »
Guy Van den Broeck · Adnan Darwiche -
2011 Poster: On the Completeness of First-Order Knowledge Compilation for Lifted Probabilistic Inference »
Guy Van den Broeck -
2011 Oral: On the Completeness of First-Order Knowledge Compilation for Lifted Probabilistic Inference »
Guy Van den Broeck