Inferring an Arithmetic Expression
Following the examples in
Probabilistic Models of Cognition on inferring
arithmetic expressions
(chapter 8),
we show how to sample an arithmetic expression.
Using annotated disjunctions
Let’s start with a version where we sample an arithmetic expressing using annotated disjunctions:
0.7::leaf(T).
0.5::operator('+',T) ; 0.5::operator('-',T).
Px::l(x,T); P::l(0,T); P::l(1,T); P::l(2,T); P::l(3,T); P::l(4,T); P::l(5,T); P::l(6,T); P::l(7,T); P::l(8,T); P::l(9,T) :- Px = 0.5, P is (1-Px)/10.
expr(A) :- expr(A,1,R).
expr(L,T1,T2) :- leaf(T1), T2 is T1+1, l(L,T1).
expr(S,T1,T2) :-
\+ leaf(T1),
Ta is T1+1,
expr(E1,Ta,Tb),
expr(E2,Tb,T2),
operator(Operator,Ta),
S =.. [Operator,E1,E2].
query(expr(A)).
The output of sampling this program will be similar to:
expr(x)
expr(7)
expr('+'('+'('-'(5,8),x),1))
expr('+'('-'(x,x),6))
expr('-'(x,'+'('+'(7,8),'-'('+'(x,'-'(x,'+'(1,x))),'+'(4,9)))))
Using the lists library
As an alternative to an annotated disjunction which may be cumbersome to write down, we can we also make use of the lists library that is included with ProbLog. More specifically, the select_uniform predicate allows us to uniformly sample an element from a list.
:- use_module(library(lists)).
0.7::leaf(T).
0.5::operator('+',T) ; 0.5::operator('-',T).
0.5::select_x(T).
l(x,T) :- select_x(T). % x=1
l(Value,T) :-
\+select_x(T),
findall(X, between(0,9,X), L),
select_uniform(T, L, Value, _).
expr(A) :- expr(A,1,R).
expr(L,T1,T2) :- leaf(T1), T2 is T1+1, l(L,T1).
expr(S,T1,T2) :-
\+ leaf(T1),
Ta is T1+1,
expr(E1,Ta,Tb),
expr(E2,Tb,T2),
operator(Operator,Ta),
S =.. [Operator,E1,E2].
query(expr(A)).