Algebraic ProbLog (semirings)¶

Setup¶

To define a custom semiring, load the aproblog module and define the operations using the use_semiring predicate.

:- use_module(library(aproblog)).

:- use_semiring(
    sr_plus,   % addition (arity 3)
    sr_times,  % multiplication (arity 3)
    sr_zero,   % neutral element of addition (arity 1)
    sr_one,    % neutral element of multiplication (arity 1)
    sr_neg,    % negation of fact label (arity 2)
    true,      % requires solving disjoint sum problem?
    false).    % requires solving neutral sum problem?

Your program should then include definitions for each of the sr_* predicates. This also allows you to use arbitrarily complex weights, that is, any Prolog term is a valid weight as long as it is accepted by the operators you define.

The last two arguments specify whether this semiring requires solving the disjoint and neutral sum problems.

• The disjoint sum problem occurs when plus is not idempotent (that is \(a \oplus a \not \equiv a\)).
• The neutral sum problem occurs when \(a \oplus \mathit{neg}(a) \not \equiv e^\otimes\).

ProbLog will produce results no matter which flags you set (they just might not be what you expect).

Example: the probability semiring¶

The default semiring used by ProbLog is the probability semiring. The weights are numbers between 0 and 1 and the semiring operations can be defined as shown in the following model.

For this semiring, we need to address the disjoint sum problem (because \(p + p \not \equiv p\)), but not the neutral sum problem (because \(p + (1-p) \equiv 1\)).

Example: Most Probable Explanation¶

ProbLog has a special mode for computing the most probable explanation (MPE), that is, the most probable possible world in which a given observation is true.

In the simple version that only computes the probability of the most probable world, the operators are defined as \(\oplus = \max\) and \(\otimes = \cdot\).

The model below also returns the truth values of the relevant facts in that most probable world. In this semiring we use weights of the form s(Probability, ListOfFacts).

In this semiring, we have no disjoint sum problem (because \(\max(a, a) \equiv a\)), but we do have to address the neutral sum problem (because \(\max(a, (1-a)) \not \equiv 1\)).

Example: Negation without Negation¶

David Buchman and David Poole introduced an alternative representation of probabilities called probability-strengths to express a more intuitive notion of negation in logic programming (and allow for negated effects in cycles):

• David Buchman and David Poole, Negation Without Negation in Probabilistic Logic Programming, International Conference on the Principles of Knowledge Representation and Reasoning (KR), 2016
• David Buchman and David Poole, Negation Without Negation in Probabilistic Logic Programming, International Journal of Approximate Reasoning, 2016

The ideas of Buchman and Poole can be easily implemented in ProbLog using a semiring. We use the s/1 function the wrap a probability-strength and the corresponding probability as p/1. This means that s(S) and p(P) are related as follows: \(P = 1-e^{-S}\) (non-wrapped weights are assumed to be probabilities but you could as well use probability-strenghts as the default to avoid the s/1 function).