ICLP09 PRISM: an overview
 LP connections◦ Semantics◦ Tabling◦ Program synthesis

 ML example

Logic
Probability

Learning

PRISM

ICLP09 Major framework in machine learning◦ clustering, classification, prediction, smoothing,…
in bioinformatics, speech/pattern recognition, text
processing, robotics, Web analysis, marketing,…

 Define p(x,y|θ), p(x|y,θ) (x:hidden cause, y:observed effect,

θ:parameters)◦ by graphs (Bayesian networks, Markov random fields,conditional random fields,…)◦ by rules (hidden Markov models, probabilistic context freegrammars,…)

 Basic tasks:◦ probability computation (NP-hard)◦ learning parameter/structure

ICLP09Graphical models for probabilistic modeling◦ Intuitive and popular but only numbers, no structured data,
no variable, no relation  complex modeling difficultMore expressive formalisms (90’s~)◦ PLL (probabilistic logic learning) {ILP, MRDM}+probability, probabilistic abduction◦ SRL (statistical relational learning) {BNs, MRFs} + relations



Many proposals (alphabet soup)◦ Generative: p(x,y|θ), hidden x generates observation y◦ Discriminative : p(x|y,θ)

ICLP09

Defines a generation process of an output in a sample space◦ Bayesian approach such as LDA
 prior distribution p(θ|α)  distribution p(D|θ)  data D Given D, predict x by

◦ Probabilistic grammars such as PCFGs

 Rules are chosen probabilistically in the derivation
 Prob. of sentence s :Defining distributions by (logic) programs (in PLL)p(τ)◦ PHA[Poole’93], PRISM[Sato et al.’95,97], SLPs[Muggleton’96,
Cussens’01], P-log[Baral et al.’04], LPAD[Vennekens et al.’04],
ProbLog[De Raedt et al.’07]…

ICLP09

Prolog's probabilistic extension◦ Turing machine with statistically learnable state transitions



Syntax: Prolog + msw/2 (random choice)◦ Variables, terms, predicates, etc available for p.-modeling

Semantics: distribution semantics◦ Program DB defines a probability measure PDB( ) on least
Herbrand models



Pragmatics:(very) high level modeling language◦ Just describe probabilistic models declaratively

Implementation:◦ B-Prolog (tabled search) + parameter learning (EM,VB-EM)◦ Single data structure : expl. graphs, dynamic programming

ICLP09

Linear tabling

1995

1997

2003

Distribution
semantics

PRISM

TabledsearchEase of modeling

Negation

2006
BeliefVariational
Bayes

propagation

Bayesian approach

BN subsumed

ICLP09Prism1.9

Modeling
environment

2007

2004

Prism1.11

Gaussian
Log-linear
BDD…

Prism1.12

2009

Negative goals

Prism1.8

EM learning

Prism1.6

Formalsemantics



PRISM subsumes three representative generative models,
PCFGs, HMMs and BNs (and their Bayesian version). They
are uniformly computed/learned by a generic algorithm

PCFGs

IO (inside-outside)
prob. computation

HMMs

FB (forwardbackward)
algorithm

BNs

BP (belief propagation)

PRISM
ICLP09fathermother

a

a

b

AB

o

A

child
b

o

B
ICLP09

btype(X):- gtype(Gf,Gm), pg_table(X,[Gf,Gm]).
pg_table(X,Gtype):((X=a;X=b),(GT=[X,o];GT=[o,X];GT=[X,X]); X=o,GT=[o,o]; X=ab,(GT=[a,b];GT=[b,a])).
gtype(Gf,Gm):- msw(abo,Gf),msw(abo,Gm).
(probabilistic switch)(parameter)
Pmsw(msw(abo,a)=1) = θ(abo,a) = 0.3,…
 PDB(msw(abo,a)=x1,msw(abo,b)=x2,msw(abo,o)=x3,
btype(a)=y1,btype(b)=y2,btype(ab)=y3,btype(o)=y4)
 PDB(btype(a)=1) = 0.4 (parameter learning is inverse direction)

ICLP09 Distribution semantics
 Tabling Program synthesis

ICLP09

Possible world semantics:
For a closed α, p(α) is thesum of probabilities ofpossible worlds M thatmakes α true
◦ pM(α(M)) = 1 if M |= α
= 0 o.w.

When α has a freevariable x, pM(α(M)) is theratio of individuals in M
satisfying α

ICLP09

DB = F U R◦ F : set of ground msw/2 atoms= { msw(abo,a),msw(abo,o),… }◦ R : set of definite clauses, msw/2 allowed only in the body= {btype(X):- gtype(Gf,Gm), pg_table(X,[Gf,Gm]) … }◦ PF( ) : infinite product of some finite distributions on msws

We extend PF( ) to PDB( ), probability measure over Hinterpretations for DB using the least model semantics
and Kolmogorov’s extension theorem◦ F’ ~ PF : ground msw atoms sampled from PF( )◦ M(R U F’) : the least H-model for R U F’ always exists (infinite) random vector taking H-interpretations◦ PDB( ) : prob. measure over such H-interpretations inducedby M(R U F’)
ICLP09

R

F

 DB = { a :- b, a :- c, b, c } PF(b,c) given
Sample (b,c) ~PF(.,.)
bc

SampledDB’Herbrandmodela

PDB(a,b,c)

0 (false)

0a:-b, a:-c{}0

= PF(0,0)0

1 (true)

a:-b, a:-c
c

{c,a}

1

= PF(0,1)1

0

a:-b, a:-c
b

{b,a}

1

= PF(1,0)1

1

a:-b, a:-cb, c{b,c,a}1= PF(1,1)

anything

else=0

ICLP09

Unconditionally definable◦ Arbitrary definite program allowed (even a:- a)◦ No syntactic restriction (such as acyclic, range-restricted)

Infinite domain◦ Countably many constant/function/predicate symbols◦ Infinite Herbrand universe allowed

Infinite joint distribution (prob. measure)◦ Not a distribution on infinite ground atoms◦ Countably many i.i.d. ground atoms available
 recursion, PCFG possible

Parameterized with LP semantics◦ Currently the least model semantics used
◦ The greatest model semantics, three valued semantics,…
ICLP09 Distribution semantics
 Tabling Program synthesis

ICLP09

PDB(iff(DB))=1 holds in our
semantics
 We rewrite goal G by SLD
to an equivalent randomboolean formula G ⇔E1v…vEN, Ei = msw1&…&
mswk
 Assume the exclusivenessof Eis, then PDB(G) =PDB(E1)+…+PDB(EN) andPDB(Ei) = PDB(m1) … PDB(mk)

Simple but exponential in#explanations  tabling
ICLP09

All solution search for ?- btype(a)with tabling btype/1, gtype/2 yields
AND/OR boolean formulas

PDB(btype(a))
0

1
2

1

2

1

3

3

4

4

2
5

6

2

5

6

3
7

8

3

7

8

9

10

4

9

10

4

Explanation graph
ICLP09

PRISM uses linear tabling (Zhou et al.’08)◦ single thread (not suspend/resume scheme)◦ iteratively computes all answers by backtracking foreach top-most-looping subgoal



Looping subgoals◦ … :-A,B …:-A’,C and A, A’ are:-pvariants, they are looping subgoals◦ If A has no ancestor in any loop
containing A, it is the top-most goal

:-q
:-r
:-q

:-p

SLD tree
ICLP09

Thanks to tabling, PRISM's prob. computation is as
efficient as the existing model-specific algorithms
Model family

EM algorithm

Time complexity

O(N2L)
Baum-Welch
Hidden Markov models
N: number of statesalgorithm
L: max. length of sequences
O(N3L3)
Probabilistic context-free Inside-outside
N: number of non-terms
grammarsalgorithm
L: max. length of sentences
O(N)Singly-connected
EM based on
π-λ computation N: number of nodes
Bayesian networks
BP (belief propagation) is an instance of PRISM’s general probability
computation scheme(Sato’07)

ICLP09S  NP VP (1.0)
NP  NP PP (0.2) |cars (0.1) |stars (0.2) |telescopes (0.3) |astronomers (0.2)
PP  P NP (1.0)
V  see (0.5) |saw (0.5)
P  in (0.3) |at (0.4) |with (0.3)• compacts(X,[]) :- np(X,Y), vp(Y,[]).
• readablenp(X,Z) :- msw(np,RHS),( RHS=[np,pp], np(X,Y), pp(Y,Z); RHS=[ears], X=[ears|Z] ; … ).
pp(X,Z]) :- p(X,Y), np(Y,Z).
vp(X,Z) :- msw(np,RHS),( RHS=[vp,pp], vp(X,Y), pp(Y,Z); RHS=[v,np], v(X,Y), np(Y,Z) )v(X,Y) :- msw(v,RHS), ( RHS=[see], X=[see|Y] ;RHS=[saw], X=[saw|Y] ).
p(X,Y) :- msw(p,RHS),( RHS=[in], X=[in|Y] ; RHS=[at], X=[at|Y]; RHS=[with] & X=[with|Y] ).

values_x(np, [[np,pp],[ears],…], [0.1,0.2,…]).
values_x(v, [[see],[saw]], [0.5,0.5]).
values_x(p,[ [in],[at],[with]], [0.3,0.4,0.3]).
ICLP09Parsing by 20,000 CFG rules extracted from 49,000 (POS) sentences from WSJ
portion of Penn tree bank with uniform prob.
Randomly selected 20 sentences are used for the average probability
computation (on the left) and Viterbi parsing (on the right)

ICLP09 Distribution semantics
 Tabling Program synthesis

ICLP09Agreement of number (A=singular, plural)agree(A):msw(subj,A),
msw(verb,B),
A=B.



A, B randomly chosen
agree(A) succeeds only
when A=B, o.w. fails

Observable distribution is a conditional one
P(agree(A) | ∃X agree(X) )= P(msw(subj,A))P(msw(verb,A)) / P(∃X agree(X) )P(∃X agree(X) ) = ΣA=sg,pl P(msw(subj,A))P(msw(verb,A))

Parameters are learnable by FAM(Cussens ’01) but it
requires a failure program
ICLP09

A failure program for agree/1: “failure  not(∃X agree(X))”
expresses how ?- agree(X) probabilistically fails
agree(A):msw(subj,A),
msw(verb,B),
A=B.



failure:msw(subj,A),
msw(verb,B),¥+A=B.

PRISM uses FOC(first-order compiler) to automaticallysynthesize failure programs (negation elimination)

ICLP09FOC automatically eliminates negation from thesource program using continuation (Sato ’89)c
 Compiled program DB positively computes thefinite failure set of DBIf DBc is terminating,
failure = negation andM(DBc)= HB-M(DB)M(DBc)M(DB)HB
ICLP09Source program DBeven
even(0).
even(s(X)) :- not(even(X)).

Compiled program DBceven
even(0).
even(s(A)):- evenc(A,f0).
evenc(s(A),_):- even(A).

ICLP09

Automated construction/evaluation of probabilisticclassifiers◦ Modeling is part of machine learning, post- processing is
as troublesome as modeling◦ PRISM 1.12 provides facilities to ease model-evaluation thatmake your code much shorter

votes’ dataset from UCI ML repository
 Classifier: Naive Bayes– Many missing values in the dataset  We use (VB)EM– From known vote records, we classify unknown votes asrepublican or democrat using 16 yes/no features– We perform 5-fold cross-validation
ICLP09

Basic:
Sampling
For a given goal G, return answer substitution s with the probability Pq (Gs)
Probability computation
For a given goal G, compute Pq (G)Viterbi computation
For a given goal G, find the most probable explanation E* = argmaxEÎ y (G)Pq (E)where y (G) are possible explanations for G
Hindsight computation
For a given goal G, compute Pq (G') or Pq (G' | G) where G' is a subgoal of G
EM learning
Given a bag {G1, G2, ..., GT} of goals, estimate the parameters qthat maximizes the likelihood P t Pq (Gt)
Advanced:◦ Handling failures in the generation process (version 1.8)
◦ Model selection (version 1.10)◦ Variational Bayesian learning (version 1.11)◦ Top-N Viterbi computation (version 1.11)◦ Data-parallel EM learning (version 1.11)◦ Deterministic annealing EM algorithm (version 1.11)
ICLP09predict

16 features (vote record)Naïve Bayes

republican, n,y,n,y,y,y,n,n,n,y,?,y,y,y,n,y
republican, n,y,n,y,y,y,n,n,n,n,n,y,y,y,n,?
democrat, ?,y,y,?,y,y,n,n,n,n,y,n,y,y,n,n
democrat, n,y,y,n,?,y,n,n,n,n,y,n,y,n,n,y
democrat y,y,y,n,y,y,n,n,n,n,y,?,y,y,y,ydemocrat, n,y,y,n,y,y,n,n,n,n,n,n,y,y,y,ydemocrat, n,y,n,y,y,y,n,n,n,n,n,n,?,y,y,y
republican, n,y,n,y,y,y,n,n,n,n,n,n,y,y,?,y…
…
republican, n,y,n,y,y,y,n,n,n,y,n,y,y,y,?,nC

V1

P(C,V1,…,V16) =P(C)P(V1|C)..P(V16|C)
C = republican, democrat
Vi = y, n

V16

Learn P(V1|C),..,P(V16|C) from data
435 data
Estimate precision bycross-validation

Predict C for unknown V1,…,V16 by
C = argmax_c P(C|V1,…,V16)

ICLP09modeling partvalues(class,[democrat,republican]).
% class labels
values(attr(_,_),[y,n]). % all attributes have two values: y or nnbayes(C,Vals):- msw(class,C),nbayes(1,C,Vals).
nbayes(_,_,[]):- !.
nbayes(J,C,[V|Vals]):choose(J,C,V),
J1 is J+1,!, % cut is ok
nbayes(J1,C,Vals).
choose(J,C,V):( nonvar(V) -> msw(attr(J,C),V); msw(attr(J,C),_) ).
%%%% Utilities
vote_learn:- load_data_file(Gs), learn(Gs).
%% Batch routine for N-fold cross validation
vote_cv(N):random_set_seed(81729),
load_data_file(Gs0), % Load the entire data
random_shuffle(Gs0,Gs), % Randomly reorder the data
numlist(1,N,Js),% Get Js = [1,...,N] (B-Prolog built-in)
maplist(J,Rate,vote_cv(Gs,J,N,Rate),Js,Rates),
avglist(Rates,AvgRate), % Get the avg. of the precisions
maplist(J,Rate,format("Test #~d: ~2f%~n",[J,Rate*100]),
Js,Rates),format("Average: ~2f%~n",[AvgRate*100]).

%% Subroutine for learning and testing for J-th split data (J = 1...N)
vote_cv(Gs,J,N,Rate):format("<<<< Test #~d >>>>~n",[J]),separate_data(Gs,J,N,Gs0,Gs1),
learn(Gs0),
maplist(nbayes(C,Vs),R,(viterbig(nbayes(C0,Vs)),(C0==C->R=1;R=0)),Gs1,Rs),
avglist(Rs,Rate),
format("Done (~2f%).~n~n",[Rate*100]).
separate_data(Data,J,N,Learn,Test):length(Data,L),
L0 is L*(J-1)//N,% L0: offset of the test data (// - integer division)
L1 is L*(J-0)//N-L0, % L1: size of the test data
splitlist(Learn0,Rest,Data,L0), % Length of Learn0 = L0
splitlist(Test,Learn1,Rest,L1), % Length of Test = L1
append(Learn0,Learn1,Learn).
load_data_file(Gs):load_csv('UCI/house-votes-84.data',Gs0,[missing('?')]),% '?' in the data will be converted into an anonymous variable (_)
maplist(csvrow([C|Vs]),nbayes(C,Vs),true,Gs0,Gs).

utility part

Let PRISM automatically estimate
the precision of the model by crossvalidation and paste it in thesubmitted paper!
ICLP09Logic and probability have been cross-fertilizing eachother, in particular in PLL/SRL Their integration can make a powerful probabilistic
modeling language with rigorous semantics
 In PRISM◦ the user encodes a probabilistic model as a program
DB at predicate level using variables and relations◦ DB uniquely defines a prob. measure◦ The remaining tasks (prob. computation, parameter
learning etc) are automatically carried out by the
PRISM system


ICLP09