Bayesian Dataflow¶

The examples on this page are ProbLog versions of those in Claret et al, Bayesian Inference Using Data Flow Analysis, ESEC/FSE 2013 (and the appendix of the accompagnying technical report).

Introduction¶

Example 1¶

Tossing two fair coins: what are the outcomes?

0.5::c1. 0.5::c2. outcome(t,t) :- c1, c2. outcome(t,f) :- c1, \+ c2. outcome(f,t) :- \+ c1, c2. outcome(f,f) :- \+ c1, \+ c2. query(outcome(_,_)).

Example 2¶

Tossing two fair coins and observing at least one comes up heads: what are the outcomes?

0.5::c1. 0.5::c2. outcome(t,t) :- c1, c2. outcome(t,f) :- c1, \+ c2. outcome(f,t) :- \+ c1, c2. outcome(f,f) :- \+ c1, \+ c2. c1_or_c2 :- c1. c1_or_c2 :- c2. query(outcome(_,_)). evidence(c1_or_c2).

Example 3¶

While loop with probabilistic condition c: what is the final value of b if we start with true and toggle on every execution of the while loop?

% c is always random 0.5::c(_). % at t=0, b=1 b(0,1). % if c is true, enter the loop to toggle b b(T1,V1) :- T1>0, T is T1-1, b(T,V), c(T), V1 is 1-V. % if c is false, return current b (we restrict time to max. 20 steps for finite support) ret(V) :- between(0,20,T), b(T,V), \+c(T). % what do we return? query(ret(_)).

Example 4¶

The goal is to keep tossing two coins until at least one of them comes up heads, and then report the outcomes of the last toss.

Here’s a first (wrong) attempt:

% toss both coins for the first time 0.5::c1(0). 0.5::c2(0). % keep tossing if none was heads 0.5::c1(T) :- T > 0, TT is T-1, \+ or_c1_c2(TT). 0.5::c2(T) :- T > 0, TT is T-1, \+ or_c1_c2(TT). or_c1_c2(T) :- c1(T). or_c1_c2(T) :- c2(T). % return return(T,1,1) :- or_c1_c2(T), c1(T), c2(T). return(T,1,0) :- or_c1_c2(T), c1(T), \+ c2(T). return(T,0,1) :- or_c1_c2(T), \+ c1(T), c2(T). return(T,0,0) :- or_c1_c2(T),\+c1(T),\+c2(T). query(return(T,_,_)) :- between(0,5,T).

Clearly, the probability of every return combination should decrease over time, and not oscillate as it does here. The problem is that ProbLog uses Prolog’s negation as failure, which means or_c1_c2(TT) also fails (and its negation succeeds) if we did not toss any coin at TT (because the or was false at TT-1). We can fix that by making explicit that we stop tossing if we see some heads.

% toss both coins for the first time 0.5::c1(0). 0.5::c2(0). % keep tossing if there was no reason to stop before 0.5::c1(T) :- T > 0, TT is T-1, \+ stop(TT). 0.5::c2(T) :- T > 0, TT is T-1, \+ stop(TT). % we stop if we tossed and or is true... stop(T) :- or_c1_c2(T). % ... or if we stopped before stop(T) :- T > 0, TT is T-1, stop(TT). or_c1_c2(T) :- c1(T). or_c1_c2(T) :- c2(T). % return return(T,1,1) :- or_c1_c2(T),c1(T),c2(T). return(T,1,0) :- or_c1_c2(T),c1(T),\+c2(T). return(T,0,1) :- or_c1_c2(T),\+c1(T),c2(T). return(T,0,0) :- or_c1_c2(T),\+c1(T),\+c2(T). query(return(T,_,_)) :- between(0,5,T).

Benchmarks¶

Unfair Coin¶

Simulating a coin with parameter p comparing up to d digits of the binary expansion of p to a sequence of bits drawn uniformly at random.

0.5::bit(T,0); 0.5::bit(T,1). % base cases: return the current bit if it equals the truth value of 2*p>=1.0 step(T,D,P,1) :- T =< D, 2*P >= 1.0, bit(T,1). step(T,D,P,0) :- T =< D, 2*P < 1.0, bit(T,0). % recursive cases: else, continue with the fractional part of 2*p as new value of p step(T,D,P,V) :- T =< D, 2*P >= 1.0, bit(T,0), TT is T+1, PP is float_fractional_part(2*P), step(TT,D,PP,V). step(T,D,P,V) :- T =< D, 2*P < 1.0, bit(T,1), TT is T+1, PP is float_fractional_part(2*P), step(TT,D,PP,V). coin(P,D,V) :- step(1,D,P,V). query(coin(0.12,D,_)) :- digits(D). query(coin(0.7,D,_)) :- digits(D). digits(20).

Here’s a version that takes the list of bits in the binary expansion as input:

0.5::bit(T,0); 0.5::bit(T,1). % base case step([X|_],T,X) :- bit(T,X). % recursive case step([H|Tail],T,V) :- bit(T,X), X \= H, TT is T+1, step(Tail,TT,V). coin(L,V) :- step(L,1,V). % 0.6 expanded is (1001)* query(coin([1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1],_)). query(coin([A,B,C,A,B,C,A,B,C],1)) :- between(0,1,A),between(0,1,B),between(0,1,C).

Uniform¶

Simulating a uniform distribution over [0,N-1]

% parameter N -- note this is converted to binary ranges, e.g., every n between 5 and 8 inclusive samples from {0..7} n(8). loop1(G,N,R,T) :- G >= N, loop2(0,1,NG,NN,T,TT), loop1(NG,NN,R,TT). loop1(G,N,G,_) :- G < N. loop2(G,N,NG,NN,T,TT) :- n(BN), N < BN, NN2 is 2*N, next(G,NG2,T), % carrying around the T(ime) for independent samples here NT is T+1, loop2(NG2,NN2,NG,NN,NT,TT). loop2(G,N,G,N,T,T) :- n(BN), N >= BN. 0.5::next(G,G1,T) ; 0.5::next(G,G2,T) :- G1 is 2*G, G2 is 2*G+1. uniform(X) :- n(N),loop1(N,N,X,0). query(uniform(_)).

Markov Chain¶

% transition matrix 0.9::go(a,a,T); 0.05::go(a,b,T); 0.05::go(a,c,T). 0.7::go(b,a,T); 0.3::go(b,c,T). 0.8::go(c,a,T) ; 0.2::go(c,c,T). % add initial distribution and define walk 1/3::in(a,0); 1/3::in(b,0); 1/3::in(c,0). in(X,T) :- T > 0, TT is T-1, in(Y,TT), go(Y,X,TT). query(in(_,3)). evidence(in(a,5),false).

Students¶

An example of a soft constraint in a students and teachers setting, with an arbitrary input database added.

% uniform prior on students liking teachers 0.5::likes(S,T) :- student(S),teacher(T). % if S takes T's course, S should like T 0.7::should_like(S,T) :- student_course(S,C),teacher_course(T,C). % constraint on acceptable worlds: should_like implies like bad_pair :- should_like(S,T), \+ likes(S,T). evidence(bad_pair,false). % posterior of likes? query(likes(S,T)). teacher(t1). teacher(t2). teacher(t3). student(s1). student(s2). student(s3). teacher_course(t1,c4). teacher_course(t2,c1). teacher_course(t2,c2). teacher_course(t3,c3). student_course(s1,c1). student_course(s2,c1). student_course(s2,c2). student_course(s3,c2). student_course(s3,c4).

Friends¶

A more complex soft constraint that depends on random variables, not just the input database as in the students example above.

% prior on friendship 0.5::friend(S1,S2) :- student(S1),student(S2). % friendship is (probabilistically) transitive 0.6::should_be_friend(S1,S3) :- friend(S1,S2), friend(S2,S3). % constraint on acceptable worlds: should_be_friends implies friends bad_pair :- student(S1), student(S2), should_be_friend(S1,S2), \+ friend(S1,S2). evidence(bad_pair,false). query(friend(X,Y)) :- student(X),student(Y), X \= Y. evidence(friend(s1,s3)). evidence(friend(s3,s4)). evidence(friend(s3,s2)). student(s1). student(s2). student(s3). student(s4).

Compare¶

We have two random n-bit sequences a and b and observe that a<b. What are the posterior probabilities of the individual bits?

% parameter n (number of bits) n(3). % bits of a 0.5::a(I,1); 0.5::a(I,0) :- n(N), between(1,N,I). % bits of b 0.5::b(I,1); 0.5::b(I,0) :- n(N), between(1,N,I). % start comparing at bit 1 compare(Res) :- compare(1,Res). % base cases compare(I,equal) :- n(I), a(I,A), b(I,A). compare(I,smaller) :- n(N), I =< N, a(I,A), b(I,B), A < B. compare(I,larger) :- n(N), I =< N, a(I,A), b(I,B), A > B. % recursive case compare(I,Res) :- n(N), I < N, a(I,A), b(I,A), II is I+1, compare(II,Res). query(a(_,1)). query(b(_,1)). evidence(compare(smaller)).

One Coin¶

Keep tossing a coin until it comes up heads.

0.5::coin(T,true); 0.5::coin(T,false). b(0,false). b(T,V) :- T>0, TT is T-1, b(TT,false), coin(T,V). query(b(X,true)) :- between(1,5,X).

Dice¶

0.5::roll(ID,T,true); 0.5::roll(ID,T,false). % start with all three false dice(0,false,false,false). % while all three are false or all three are true, continue dice(N,A,B,C) :- N > 0, NN is N-1, dice(NN,X,X,X), roll(d1,N,A), roll(d2,N,B), roll(d3,N,C). % and stop if not dice_return(NN,A,B,C) :- NN >= 0, dice(NN,A,B,C), \+ allsame(A,B,C). allsame(X,X,X). query(dice_return(X,_,_,_)) :- between(1,3,X).

« Probabilistic...

Aircraft Flap... »