PDF《DNF Sampling for ProbLog Inference》

DNF Sampling for ProbLog Inference Dimitar Sht.

Shterionov, Angelika Kimmig, Theofrastos Mantadelis and Gerda Janssens Department of Computer Science, Katholieke Universiteit Leuven dimitar.shterionov@student.kuleuven.be, {firstname.lastname}@cs.kuleuven.be Abstract. Inference in probabilistic logic languages such as ProbLog, an extension of Prolog with probabilistic facts, is often based on a reduc- tion to a propositional formula in DNF. Calculating the probability of such a formula involves the disjoint-sum-problem, which is computation- ally hard. In this work we introduce a new approximation method for ProbLog inference which exploits the DNF to focus sampling. While this DNF sampling technique has been applied to a variety of tasks before, to the best of our knowledge it has not been used for inference in probabilis- tic logic systems. The paper also presents an experimental comparison with another sampling based inference method previously introduced for ProbLog.

1 Introduction In the past few years, a multitude of formalisms combining probabilistic rea- soning with logics, databases or logic programming has been developed, see for instance [1,2] for overviews. To use such formalisms in statistical relational learn- ing, e?cient inference algorithms are crucial, as learning requires evaluating large numbers of queries. ProbLog [3] is a simple extension of Prolog de?ning the suc- cess probability of a query in terms of random subprograms. E?cient inference algorithms for ProbLog have been implemented on top of the YAP-Prolog sys- tem [4]. ProbLog has been motivated by and applied to link mining in large collections of uncertain biological data, and its inference methods have been shown to increase the scalability of exact inference for probabilistic logic systems that do not rely on additional simplifying assumptions. However, as inference in such systems is computationally hard, approximation techniques are needed for complex queries. While [4] introduced a sampling based inference technique for ProbLog which directly exploits the distribution over subprograms de?ned by a ProbLog program, in this paper, we follow a more query-centered approach. We introduce DNF Sampling, a new approximate inference technique for ProbLog based on the sampling scheme of [5], where in a ?rst phase, as in ProbLog'

s exact inference, a Boolean formula in disjunctive normal form representing all proofs of the query is constructed. Samples are then drawn from this formula, thereby focussing on the subspace relevant for the current task. We experimen- tally compare both approaches in the context of biological networks, showing that Program Sampling has a better convergence than DNF Sampling. arXiv:1009.3798v2 [cs.LO]

21 Sep

2010 The paper is organised as follows: We start by reviewing ProbLog and its key inference methods in Section 2. Section

3 introduces our new approximate inference method, and Section

4 reports on experiments comparing the di?erent methods. After discussing related work in Section 5, we conclude in Section 6.

2 ProbLog ProbLog is a probabilistic extension of Prolog inspired by typical machine learn- ing applications. It is developed as a simple but powerful probabilistic logic pro- gramming language, and used for mining large biological networks (where nodes represent genes, proteins, and so on), with probability labels on their edges. As these tasks are computationally hard, the e?ciency in processing complex queries is very important. For this reason, ProbLog is build on top of the state- of-the-art YAP-Prolog system. YAP is a high performance Prolog system, based on the Warren Abstract Machine (WAM) with di?erent optimisations, which make it a suitable host for ProbLog. ProbLog is closely related to other probabilistic logic systems such as PHA [6], PRISM [7], and ICL [8]. However, PRISM and PHA impose additional assump- tions to simplify probability calculation, and the ICL implementation ailog2 does not scale to larger problems. ProbLog'