Session 5: Advanced topics

Exercise: algebraic ProbLog

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).

Probability semiring (default)

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\)).

:- use_module(library(aproblog)). :- use_semiring( sr_plus, % addition (arity 3) sr_times, % multiplication (arity 3) sr_zero, % neutral element of addition sr_one, % neutral element of multiplication sr_neg, % negation of fact label true, % requires solving disjoint sum problem? false). % requires solving neutral sum problem? sr_zero(0.0). sr_one(1.0). sr_plus(A, B, C) :- C is A + B. sr_times(A, B, C) :- C is A * B. sr_neg(A, B) :- B is 1 - A. % An example program: 0.6::edge(1,2). 0.1::edge(1,3). 0.4::edge(2,5). 0.3::edge(2,6). 0.3::edge(3,4). 0.8::edge(4,5). 0.2::edge(5,6). path(X,Y) :- edge(X,Y). path(X,Y) :- edge(X,Z), path(Z,Y). query(path(1,6)).

Most-probable explanation semiring (default)

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\)).

:- use_module(library(aproblog)). :- use_module(library(lists)). :- use_semiring( sr_mpestate_plus, % addition (arity 3) sr_mpestate_times, % multiplication (arity 3) sr_mpestate_zero, % neutral element of addition sr_mpestate_one, % neutral element of multiplication sr_mpestate_neg, % negation of fact label false, % requires solving disjoint sum problem? true). % requires solving neutral sum problem? % MPE+state semiring sr_mpestate_zero(s(0.0, [])). sr_mpestate_one(s(1.0, [])). sr_mpestate_plus(s(VA, SA), s(VB, SB), s(VA, SA)) :- VA > VB. sr_mpestate_plus(s(VA, SA), s(VB, SB), s(VB, SB)) :- VA < VB. sr_mpestate_plus(s(VA, SA), s(VB, SB), s(VA, SC)) :- VA == VB, append(SA, SB, SC1), sort(SC1, SC). sr_mpestate_times(s(VA, SA), s(VB, SB), s(VC, SC)) :- VC is VA*VB, append(SA, SB, SC1), sort(SC1, SC). sr_mpestate_neg(s(V, [K]), s(V1, [\+K])) :- V1 is 1.0 - V. s(0.6, [edge(1,2)])::edge(1,2). s(0.1, [edge(1,3)])::edge(1,3). s(0.4, [edge(2,5)])::edge(2,5). s(0.3, [edge(2,6)])::edge(2,6). s(0.3, [edge(3,4)])::edge(3,4). s(0.8, [edge(4,5)])::edge(4,5). s(0.2, [edge(5,6)])::edge(5,6). path(X,Y) :- edge(X,Y). path(X,Y) :- edge(X,Z), path(Z,Y). query(path(1,6)).

Exercise: DT-ProbLog

Here’s a small example illustrating Decision-Theoretic ProbLog.

  • G. Van den Broeck, I. Thon, M. van Otterlo and L. De Raedt. DTProbLog: A decision-theoretic probabilistic Prolog. Proceedings of the twenty-fourth AAAI conference on artificial intelligence, pp. 1217 - 1222, AAAI Press, 2010. PDF
  • % probabilistic facts 0.3::rain. 0.5::wind. % decision facts ?::umbrella. ?::raincoat. broken_umbrella :- umbrella, rain, wind. dry :- rain, raincoat. dry :- rain, umbrella, not broken_umbrella. dry :- not(rain). % utilities utility(broken_umbrella, -40). utility(raincoat, -20). utility(umbrella, -2). utility(dry, 60).

    A famous decision problem is the Monty Hall problem.

    Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

    Model this problem in DT-ProbLog.

    % %