Search

Lifting aims at improving the efficiency of probabilistic inference by exploiting symmetries in the model. Various methods for lifted probabilistic inference have been proposed, but our understanding of these methods and the relationships between them is still limited, compared to their propositional counterparts. The only existing theoretical characterization of lifting is a completeness result for weighted first-order model counting. This paper addresses the question whether the same completeness result holds for other lifted inference algorithms. We answer this question positively for lifted variable elimination (LVE). Our proof relies on introducing a novel inference operator for LVE. ispartof: pages:572- ispartof: Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, JMLR workshop and conference proceedings vol:31 pages:572- ispartof: International Conference on Artificial Intelligence and Statistics (AISTATS) location:Scottsdale, USA date:29 Apr - 1 May 2013 status: published

A probabilistic program often gives rise to a complicated underlying probabilistic model. Performing inference in such a model is challenging. One solution to this problem is lifted inference which improves tractability by exploiting symmetries in the underlying model. Our group is pursuing a lifted approach to inference for probabilistic logic programs. ispartof: Proceedings of the NIPS Probabilistic Programming Workshop ispartof: Probabilistic Programming Workshop location:Lake Tahoe date:7 Dec - 8 Dec 2012 status: published

Lifted probabilistic inference methods exploit symmetries in the structure of probabilistic models to perform inference more efficiently. In lifted variable elimination the symmetry among a group of interchangeable random variables is captured by counting formulas, and exploited by operations that handle such formulas. In this paper we generalize the structure of counting formulas and present a set of inference operators that introduce and eliminate these formulas from the model. This generalization expands the range of problems that can be solved in a lifted way. Our work is closely related to the recently introduced method of joint conversion. Due to its more fine grained formulation, however, our approach can provide more efficient solutions than joint conversion. ispartof: pages:1-8 ispartof: Proceedings of the Second International Workshop on Statistical Relational AI (StaRAI) pages:1-8 ispartof: International Workshop on Statistical Relational AI (StaRAI-12) location:Catalina Island, CA, USA date:18 Aug - 18 Aug 2012 status: published

Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once for each group, as opposed to once for each variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference rely on (in)equality constraints. We show how inference methods can be generalized to work with arbitrary constraints. This allows them to capture a broader range of symmetries, leading to more opportunities for lifting. We empirically demonstrate that this improves inference efficiency with orders of magnitude, allowing exact inference in cases where until now only approximate inference was feasible. ispartof: pages:1194-1202 ispartof: Proceedings of the fifteenth international conference on Artificial Intelligence and Statistics, JMLR workshop and conference proceedings vol:22 pages:1194-1202 ispartof: International conference on artificial intelligence and statistics (AISTATS) location:La Palma, Canary Islands date:21 Apr - 23 Apr 2012 status: published

Probabilistic logical languages provide powerful formalisms for knowledge representation and learning. Yet performing inference in these languages is extremely costly, especially if it is done at the propositional level. Lifted inference algorithms, which avoid repeated computation by treating indistinguishable groups of objects as one, help mitigate this cost. Seeking inspiration from logical inference, where lifted inference (e.g., resolution) is commonly performed, we develop a model theoretic approach to probabilistic lifted inference. Our algorithm compiles a first-order probabilistic theory into a first-order deterministic decomposable negation normal form (d-DNNF) circuit. Compilation offers the advantage that inference is polynomial in the size of the circuit. Furthermore, by borrowing techniques from the knowledge compilation literature our algorithm effectively exploits the logical structure (e.g., context-specific independencies) within the first-order model, which allows more computation to be done at the lifted level. An empirical comparison demonstrates the utility of the proposed approach. acceptance rate 17% ispartof: pages:2178-2185 ispartof: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence pages:2178-2185 ispartof: International Joint Conference on Artificial Intelligence (IJCAI) location:Barcelona, Spain date:16 Jul - 22 Jul 2011 status: published

Many approaches to probabilistic logical learning have been proposed by now, and several of these have been implemented into powerful learning and inference systems. Given this state of the art, it appears natural to start using these systems for solving concrete problems. This paper presents some results of a case study where several probabilistic logical learning systems have been applied to a seemingly simple problem that exhibits both probabilistic and relational aspects. The results are surprisingly negative: none of the systems we have tried could adequately handle the problem at hand. We discuss the reasons for this. This leads to several conclusions. First, still more effort must be invested in developing full-fledged implementations that can handle a wide range of realistic problems. Second, the intrinsic limitations of certain approaches may not yet be fully understood. Third, the problem we discuss here may be an interesting application for probabilistic logical learning systems, and we invite other researchers to use it as a benchmark for evaluating the applicability of their favorite systems. ispartof: CW Reports nrpages: 8 status: published

Efficient probabilistic inference is key to the success of statistical relational learning. One issue that affects inference cost is the presence of irrelevant random variables. The Bayes-ball algorithm can identify such irrelevant variables in a propositional Bayesian network. This paper presents a lifted version of Bayes-ball, which works directly on the first-order level, and shows how this algorithm applies to CP-logic inference. ispartof: pages:1-3 ispartof: International Workshop on Statistical Relational Learning 2009 pages:1-3 ispartof: International Workshop on Statistical Relational Learning (SRL-2009) location:Leuven, Belgium date:2 Jul - 4 Jul 2009 status: published