Examples from PLP 2015
The following ProbLog programs are inspired by examples that have been identified as challenging for PLP inference in Arun Nampally and C.R. Ramakrishnan, Constraint-based Inference in Probabilistic Logic Programs, Probabilistic Logic Programming Workshop at ICLP 2015
The first example considers random strings over the alphabet {a,b} of a fixed length and asks for the probability of such a string containing substring bb given that it is a palindrome.
Here’s a naive generate and test encoding whose running time quickly increases with the length of the string, as inference has to explicitly enumerate all strings of that length:
0.5::pick(N, a) ; 0.5::pick(N,b).
random_string(0,[]).
random_string(N,[X|L]) :-
N > 0,
pick(N,X),
NN is N-1,
random_string(NN,L).
palindrome(L) :- reverse(L,L).
reverse(L,R) :-
reverse(L,[],R).
reverse([],L,L).
reverse([A|B],S,R) :-
reverse(B,[A|S],R).
twoBs([b,b|_]).
twoBs([_|L]) :-
twoBs(L).
string_is_palindrome(N) :- string_is_palindrome(N,_).
string_is_palindrome(N,L) :- random_string(N,L),palindrome(L).
string_with_bb(N) :- string_with_bb(N,_).
string_with_bb(N,L) :- random_string(N,L),twoBs(L).
len(5).
evidence(string_is_palindrome(X)) :- len(X).
query(string_with_bb(X)) :- len(X).
The following variant avoids generating all strings explicitly, which noticably improves scalability (especially if used with forward inference, which is not yet supported by the online interface):
0.5::pick(N, a) ; 0.5::pick(N,b).
% a palindrome of length N spans positions 1 to N
palindrome(N) :-
palindrome(1,N).
% base case for even length: left and right crossed
palindrome(A,B) :-
A > B.
% base case for uneven length: arbitrary middle character
palindrome(N,N) :-
pick(N,_).
% recursive case: add same character at both ends and move positions towards the middle
palindrome(A,B) :-
A < B,
pick(A,X),
pick(B,X),
AA is A+1,
BB is B-1,
palindrome(AA,BB).
bb(N) :-
Max is N-1,
between(1,Max,I),
pick(I,b),
II is I+1,
pick(II,b).
len(5).
evidence(palindrome(X)) :- len(X).
query(bb(X)) :- len(X).
The second example uses constraints imposed by evidence to encode an Ising model on a grid of binary variables.
maxX(4). % number of downward links
maxY(4). % number of rightward links
% node coordinates start from 0
node(X,Y) :- maxX(XM),maxY(YM),between(0,XM,X),between(0,YM,Y).
% these are all links in the factor graph
link(X1,Y,X2,Y) :- node(X1,Y),X2 is X1+1,node(X2,Y). % vertical links
link(X,Y1,X,Y2) :- node(X,Y1),Y2 is Y1+1,node(X,Y2). % horizontal links
% for each link, the potential is the same
0.1::pot(X1,Y1,true,X2,Y2,true);0.2::pot(X1,Y1,false,X2,Y2,true);0.3::pot(X1,Y1,false,X2,Y2,false);0.4::pot(X1,Y1,true,X2,Y2,false) :- link(X1,Y1,X2,Y2).
% a node (X,Y) has a value V if some potential it is involved in assigns that value
node_val(X,Y,V) :- node(X,Y),pot(X,Y,V,_,_,_).
node_val(X,Y,V) :- node(X,Y),pot(_,_,_,X,Y,V).
% but no node can be both true and false at the same time
err :- node_val(X,Y,true),node_val(X,Y,false).
evidence(err,false).
% what is the probability that the top left and bottom right node have the same truth value?
agree(V) :- node_val(0,0,V), maxX(X), maxY(Y), node_val(X,Y,V).
query(agree(_)).