Inference in probabilistic logic languages such as ProbLog, an extension of Prolog with probabilistic facts, is often based on a reduction to a propositional formula in DNF. Calculating the probability of such a formula involves the disjoint-sum-problem, which is computationally 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 probabilistic logic systems. The paper also presents an experimental comparison with another sampling based inference method previously introduced for ProbLog.
As mentioned earlier, DNF Sampling is based on the general sampling scheme introduced in @cite_14 . This scheme has been used for probability estimation in the context of probabilistic databases @cite_12 @cite_13 and probabilistic graph mining @cite_9 . In the context of statistical relational learning, the scheme has been used to estimate the number of true groundings of a clause @cite_2 . While the use of sampling in combination with a reduction to a DNF formula for probabilistic logic programs has already been proposed (but not realized) by @cite_7 , to the best of our knowledge, this paper is the first to actually use DNF Sampling for inference in a probabilistic logic programming system. The ProbLog system also includes approximate inference methods that do not use sampling, but rely on restricting the number of proofs encoded in the DNF @cite_3 .
@cite_14 @cite_7 @cite_9 @cite_3 @cite_2 @cite_13 @cite_12
2066720893 2256219492 2084591860 2121075864 2044494469 2126033088
The aim of this paper is to generalize logic programs, for dealing with probabilistic knowledge. Using the possible-worlds approach of probabilistic logic ([Nil]), we define probabilistic logic programs so that their clauses may be true or false with some probabilities and goals may succeed or fail with probabilities too. Probabilistic logic programs may contain negation, their semantics agrees with negation as failure (unlike probabilistic logic which is based on the standard logical negation). Graph data are subject to uncertainties in many applications due to incompleteness and imprecision of data. Mining uncertain graph data is semantically different from and computationally more challenging than mining exact graph data. This paper investigates the problem of mining frequent subgraph patterns from uncertain graph data. The frequent subgraph pattern mining problem is formalized by designing a new measure called expected support. An approximate mining algorithm is proposed to find an approximate set of frequent subgraph patterns by allowing an error tolerance on the expected supports of the discovered subgraph patterns. The algorithm uses an efficient approximation algorithm to determine whether a subgraph pattern can be output or not. The analytical and experimental results show that the algorithm is very efficient, accurate and scalable for large uncertain graph databases. Markov logic networks (MLNs) combine logic and probability by attaching weights to first-order clauses, and viewing these as templates for features of Markov networks. In this paper we develop an algorithm for learning the structure of MLNs from relational databases, combining ideas from inductive logic programming (ILP) and feature induction in Markov networks. The algorithm performs a beam or shortest-first search of the space of clauses, guided by a weighted pseudo-likelihood measure. This requires computing the optimal weights for each candidate structure, but we show how this can be done efficiently. The algorithm can be used to learn an MLN from scratch, or to refine an existing knowledge base. We have applied it in two real-world domains, and found that it outperforms using off-the-shelf ILP systems to learn the MLN structure, as well as pure ILP, purely probabilistic and purely knowledge-based approaches. Modern enterprise applications are forced to deal with unreliable, inconsistent and imprecise information. Probabilistic databases can model such data naturally, but SQL query evaluation on probabilistic databases is difficult: previous approaches have either restricted the SQL queries, or computed approximate probabilities, or did not scale, and it was shown recently that precise query evaluation is theoretically hard. In this paper we describe a novel approach, which computes and ranks efficiently the top-k answers to a SQL query on a probabilistic database. The restriction to top-k answers is natural, since imprecisions in the data often lead to a large number of answers of low quality, and users are interested only in the answers with the highest probabilities. The idea in our algorithm is to run in parallel several Monte-Carlo simulations, one for each candidate answer, and approximate each probability only to the extent needed to compute correctly the top-k answers. Data exchange between embedded systems and other small or large computing device increases. Since data in different data sources may refer to the same real world objects, data cannot simply be merged. Furthermore, in many situations, conflicts in data about the same real world objects need to be resolved without interference from a user. We report on an attempt to make a RDBMS probabilistic, i.e., data in a relation represents all possible views on the real world, in order to achieve unattended data integration. We define a probabilistic relational data model and review standard SQL query primitives in the light of probabilistic data. It appears that thinking in terms of 'possible worlds' is powerful in determining the proper semantics of these query primitives.