I'm reading the paper DeepStochLog: Neural Stochastic Logic Programming. The authors differentiate between Probabilistic Logic Programming (PLP) and Stochastic Logic Programming (SLP), but I can't seem to understand what the difference is.

They briefly explain the difference by saying:

The more popular PLPs (De Raedt and Kimmig 2015) are based on a possible worlds semantics (i.e. the distribution semantics (Sato 1995)), which extends probabilistic graphical models, while the SLPs (Muggleton 1996, 2000; Cussens 2001) are based on stochastic grammars. The difference can also be described as a random graph vs a random walk model.

I think I understand possible world semantics. But what is the difference to using stochastic grammars? And how does this relate to the random graph vs random walk comparison?


1 Answer 1


Probabilistic Logic Programming (PLP), usually adopts the Distribution Semantics (DS) (see the paper ''A Statistical Learning Method for Logic Programs with Distribution Semantics'' by T. Sato). More recently, ProbLog introduced the notation $\Pi::f$ to denote probabilistic facts: the atom $f$ is true with probability $\Pi$. Under the DS, a choice value for every probabilistic facts defines a world. If a program has $n$ probabilistic facts, there are $2^n$ worlds. The probability of a world $w$ is computed as $$ P(w) = \prod_{i \mid f_i = \top} \Pi_i \cdot \prod_{i \mid f_i = \bot} (1 - \Pi_i) $$ $f_i = \top$ states that the probabilistic fact $f_i$ is considered true in the world $w$ while $f_i = \bot$ that it is considered false. The probability of a query $q$, which can be a conjunction of ground atoms, is computed as the sum of the probabilities of the worlds where the query is true, so $$ P(q) = \sum_{w \models q} P(w). $$ The main concept is that the probability is computed by considering worlds.

Differently, Stochastic Logic Programs (SLP) (see the works of Muggleton and Cussens, for example) consider clauses with an attached probability and the probability distribution is defined over refutations of goals, rather than worlds. Probabilistic clauses are of the form $$ \Pi : C :- b. $$ where $C:- b$ is a definite clause. There are two types of SLPs: pure, where every clause is a probabilistic clause, and impure, where only some of the clauses are probabilistic. Consider a pure SLP and the program obtained by removing the probability in front of the clauses. Every derivation for a query $q$ is assigned to a real value given by the product of the values of its steps (i.e., the probability of the clauses that unifies at any given step). The probability of a successful derivation for a query $q$ is its label divided by the sum of the labels of all successful derivations.

Overall, the main difference is that the DS defines a probability distribution over worlds while SLPs define a probability distribution over refutations (i.e., paths in the SLD derivations).

  • $\begingroup$ Thanks! Are the paths in the SLD derivation, where the comparison of SLPs to random walks comes from? $\endgroup$
    – Pav
    Jul 6, 2023 at 13:22
  • $\begingroup$ Yes, I think so $\endgroup$ Jul 7, 2023 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.