Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

New liftable classes for first-order probabilistic inference

Kazemi, Seyed Mehran, Kimmig, Angelika, Broeck, Guy Van den and Poole, David 2016. New liftable classes for first-order probabilistic inference. Presented at: Neural Information Processing Systems, Barcelona, Spain, 5-10 December 2016.

[thumbnail of kazemi-nips16.pdf]
PDF - Accepted Post-Print Version
Download (502kB) | Preview


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.

Item Type: Conference or Workshop Item (Paper)
Date Type: Acceptance
Status: Unpublished
Schools: Computer Science & Informatics
Date of First Compliant Deposit: 5 August 2019
Date of Acceptance: 12 August 2016
Last Modified: 16 Oct 2020 01:49

Citation Data

Cited 13 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics