An introduction toPRISM
z What is PRISM?

z acronym of PRogramming In Statistical Modelingz programming language for symbolic-statistical modelingz downloadable at http://mi.cs.titech.ac.jp/prism/z Modeling targets

z complex phenomena governed by rules and probabilities
z gene-inheritance, stochastic NLP, consumer-behavior,…

z Featuresz programs as statistical models
z probabilities and most likely paths computedz parameter learning by the EM algorithmz See [Sato ’01] for theoretical background
PRISM

Development of PRISM
1995

1997

2000

2003

2004

Distribution
semantics

PRISM

graphicalEM

TabledsearchNegationFirst
probabilistic
semantics
for (logic)
programs
as statisticalmodels

First
programming
languagewith EM
learning ability

FastEM algorithm
based on
AND-OR graphs

Fastall solution
search bylinear tabling

Firstparameter
learning fromnegative goals

PRISM1.4

PRISM1.6

PRISM1.8

PRISM

Basic ideaz

PRISM = Prolog + probability +parameter learning

Top-events(sampling)(search)Clauses
If-then,recursion

programming

EM learning of θ
Simple events by dice throwing
with statistical parameters θ

PRISM
PRISM

An example of PRISM
modeling

PRISM

Gene inheritancefathermotheraabAB

childbo
PRISM

BoA

Program DB = rules +distribution PF over msws

(basic random switch)(parameter)(computed prob.)
PRISM

Observation
Explanation
searchProb. computation
observation (top-event)
1

02

1

3
2
5

6

1

3

3

4

78

4
9explanation

Inside prob.

24

Tabled search

25

6

3

7

8

4

910

10

Explanation graph

PRISM

DynamicprogrammingThree modes of execution
Prob. computation:| ?- prob(btype(a)).
The probability of btype(a) is: 0.4
Search for explanation graph:| ?- probf(btype(a)).
btype(a) <=> gtype(a,a) v gtype(a,o) v gtype(o,a)
gtype(a,a) <=> msw(gene,a) & msw(gene,a)
gtype(a,o) <=> msw(gene,a) & msw(gene,o)
gtype(o,a) <=> msw(gene,o) & msw(gene,a)Sampling:| ?- sample(btype(X)).
X = a?

PRISM

Learning parameters| ?- Gs =[btype(a),btype(o),btype(ab),btype(o),…],learn(Gs).
.
observed data
parameter learning
Finished learningby the EM algorithm
Number of iterations: 5.
Final likelihood:-12.800480
Total learning time: 0.0 seconds.
All solution search time: 0.0 seconds.
learned parameters| ?- show_sw(abo).
Switch abo: a (0.292380) b (0.163031) o (0.544588)

PRISM

Statistical modeling
500 samples
btype(a) :195
btype(b) : 97
btype(o) :159
btype(ab): 49

EMlearning

Calculation by the model
prob(btype(a)) =0.397
prob(btype(b)) =0.201
prob(btype(o)) =0.311
prob(btype(ab))=0.089

Learned parametersprob(msw(abo,a))=0.283
prob(msw(abo,b))=0.158
prob(msw(abo,o))=0.558Fitting test

χ 2 = 0.65
1(accepted, level=0.05)
PRISM

Declarative semantics

PRISM

Parameterized logic
programsz Programz

definite clauses (rules)z

probabilistic facts withz Distribution semantics
zProb. measure over the
Herbrand interpretations of F
parameterized with θProb. measure over the
Herbrand interpretations of DB

is extended bytoz

is the denotation ofz

is set manually or learned from data
PRISM

Distribution semantics (1)[Sato 95]z

Ground atom = random variable taking on
Program represents a set of ground clausesz

Why semantic difficulty?

zzzz

infinite symbols
infinite Herbrand universe
Recursion
infinitely many random variables
D-semantics allows for recursion and infinite domains,
and unconditionally definable (even for loopingprograms)
PRISM

Distribution semantics (2)zAssume a parameterized basic distribution

is given overz Sample
and getª Pick up
a set of true factsª The least Herbrand model
is definedª Every ground atom has a truth value depending on
and hence considered as a random variableªis defined
PRISM

Distribution semantics (3)is a σ-additive probability measure onz

where ω corresponds to an Herbrand interpretationz

closed formula:z Globally consistent probs are assigned to all closed

formulasz

Continuity by σ-additivity

PRISM

Notezzzz

is constructed from finite distributions

Prob. mass distributes only over the set of possible
least H-models
Distribution semantics covers logic programming,
discrete Bayesian net, HMMs, PCFGs,…
Definable for any DB (unlike other approaches:-)
PRISM

Tabled search

PRISM

Explanation graphszzzz

We compute probabilities using explanationgraphs which are a compact representation of
statistical-logical dependency among events.
In an explanation graph, subgraphs are partiallyordered and shared by super-graphs.
Sharing of subgraphs causes sharing ofcomputations by dynamic programming.
Thus efficient computation is achievable.
PRISM

Computation sharingz

E-graph represents
all explanations for G

G:

msw

msw

τ1start

τ2

msw

τ1

msw

τ3

τ2

τ1 :
start

PRISM

msw

τ3

end

msw

τ4

computation is shared!

endTablingzzz

An explanation graph for G is obtainable by searchingfor all explanations of G using tabling.
Tabling remembers successful goals and reuses them toavoid recomputation of the same goal.
There are two ways of tabling in logic programming;zz

Suspension & resumption of multiple processeszbased on OLDT search, difficult to implement (see XSB)Single process with iterative searchz
Based on linear-tabling, easy to implement (see B-Prolog)zAdopted in PRISM
PRISM

Linear Tabling [Zhou 04]
Top-down left-right execution
Pioneer(first occurrence)(looping subgoal)easy to implementz overhead-freez space efficientz cut is easy to handle
ztableAdvantages
z

A...
...

Followerz

Disadvantage
zA’...

z• A’ is a descendant of A but
identical to A.
• A’ immediately fails after consuming
existing answers in the table
PRISM

iterative computation

Optimizations
subgoal optimizationz semi-naïveoptimization possiblez

Learning parameters

PRISM

gEM [Kemeya 00]
zzz

To learn parameters in a program, we apply ML (maximumlikelihood) estimation to observed data (top-goal G)
Usually we do not know which of G’s explanation is true one
G isan incomplete data
Use the EM algorithm.
PRISM uses the gEM (graphical EM) algorithm which is a generic EM
algorithm for PRISM programs unlike specialized ones such as theBW (Baum-Welch) algorithm and the IO (Inside-Outside) algorithm.
zgEM is derived from distribution semantics.
z
gEM runs on explanation graphs in the manner of dynamicprogramming.
z
gEM achieves the same time complexity as BW and IO when
OLDT search [Tamaki & Sato 86] is used for explanation graphconstruction.
PRISM

Search-and-learn schemawith tabulationz Tabled search + the graphical EM algorithm= efficient parameter learning

Tabledsearch
Observed atoms

gEM

ExplanationgraphsPRISMEM learning in PRISM
Old approach:z Design a new EM algorithm for each applicationz Our approach:zz

Write a PRISM program for each application

specify HMMs
by program
specify PCFGs
by program
specify BNs
by program
specify yourmodelby program

Baum-WelchgraphicalEMalgorithm

Inside-Outside
EM for BN
New EMalgorithm foryour model

PRISM

Time complexity of gEM+ OLDTzzz

Total time = OLDT search time + iterations * time/iterationO(OLDT) ≥ O(explanation graphs) = O(updata-time/iteration)
Equal to existing (specialized) EM algorithms

OLDTgEM

Specialized EM

HMMs

O(N 2 LT)O(N 2 LT)

Baum-Welch

PCFGs

O(N 3 L3T )O(N 3 L3T )Inside-Outside

Singly connected
Bayesian net

O(V T )O(V T )

[Castillo et al. 97]

Pseudo PCSGs

O(N 4 L3T )O(N 4 L3T )[Charniak & Carroll 94]

PRISM

N = #symbols, #states, L=sentence length, T = #data, |V| = #nodes

Conditions for fast EMlearningz

Each observation has finitely many explanations:zExclusiveness of explanations:zUniqueness of observable goals:zAcyclicity:zz

caller-callee relation is partial ordering

Independence:zatoms in an explanation are independent
PRISM

gEM vs. the Inside-Outsidealgorithm (1)z PCFG is a CFG with probs assigned to rulesz ATR corpus (size=10,995 min=2 ave.=10max=49)

z PCFG: 860 rules (NT 173, POS 441)z Parser used for explanation graph construction:

Generalized LR (Tomita) parserz gEM is 850 times faster than IO per iteration
PRISMComparing updating time
for sampled 100 sentences (ATR)
time per iteration

850 : 1

PRISM

sentence length

gEM vs. the Inside-Outsidealgorithm (2)z EDR corpus (size=9,900 min=5 ave.=20 max=63)z PCFG: 2,687 rules / 12,798 rules (CNF),

3*10^8 parses/sentence at sentence length 20
6.7*10^19 at 38z Parser used for explanation graph construction:

Generalized LR (Tomita) parserz gEM is 1300 times faster than IO per iteration
PRISM

Comparing updating time
for sampled 100 sentences (EDR)
time per iteration

1,300 : 1

sentence lengthPRISMPCFGs in PRISMz

Probabilistic LL(1) parser withtarget(pdcg,1).
values(vp,[[v],[v,np]]).
…

% we observe pdcg([boys,run]),…
% vp has two rules {vp->v, vp->v np}% one of {msw(vp,[v]), msw(vp,[v,np])}% is probabilistically chosen

pdcg(L):- start_symbol(C), pdcg2([C],L,[]).
pdcg2([Wd|R],[Wd|L0],L2):- terminal(Wd), pdcg2(R,L0,L2).
pdcg2([A|R],[Wd|L0],L2):first(A,Wd),% Wd is in first(A)msw(A,RHS),% probabilistic choicepdcg2(RHS,[Wd|L0],L1), pdcg2(R,L1,L2).
Meta-interpreterpdcg2([],L1,L1).

zParameter learning of PDCG form + ATR corpus
completes in 3 min by a PC (3.4Ghz,2GB)
PRISM

Exploring diverse modelingand parameter learningzzzzzzzNaïve Bayes
Profile HMM
one report so far
Linkage analysis
PCFGs (PDCG, PLC,PGLR(k))
HPSGs
no report so far
Graph grammars (HR, NLC)
Shogi palyer
PRISM

Negation andprobabilistic
constraint modeling

PRISM

Failure by constraints[Sato 05]

Generative models
z simulate how observations are generated
z no failure assumed (e.g.BNs,HMMs,PCFGs)z Complex models use constraints
z failure is inevitable (e.g.HPSGs)z Let’s model probabilistic agreement in numberzagree(A):agree(A):msw(coin0,A),
msw(coin0,A),
msw(coin1,B),
msw(coin1,B),
A=B.
A=B.

agree(A) succeeds only
when A=B. O.w. fails
PRISM

The fgEM algorithm
zFailure means loss of probability massz gEM is not usablez Distribution is log-linear;zEM learning of parameters is possible by fgEMz fgEM [Sato 04] = gEM [Kameya 00] + FAM [Cussens 01]
z FAM computes average count of msws in a failed computation

zfgEM requires a failure program
PRISM

Failure programz

A failure program is one that explicitly describes
how failure occurs.
agree(A):agree(A):msw(coin0,A),
msw(coin0,A),
msw(coin1,B),
msw(coin1,B),
A=B.
A=B.

z

failure:failure:msw(coin0,A),
msw(coin0,A),
msw(coin1,B),
msw(coin1,B),¥+A=B.
¥+A=B.

failure= no output generated= not(∃X agree(X))

PRISM1.8 uses FOC to automatically derive a failure
program from the negation of a source program.
PRISM

FOC (first-order compiler)
Full automatic program synthesis for logic programs withnegation [Sato 89]
cz Compiled program DB positively computes the finite
failure of DBzM(DB)M(DBc)

If DBc is terminating,failure = negation andM(DBc)= HB-M(DB)The program terminates
for every ground goal

HB
PRISM

Negation elimination byFOCSource program DBeven
even(0).
even(s(X)) :- not(even(X)).

Compiled program DBceveneven(0).
even(s(A)):- closure_even0(A,f0).
closure_even0(s(A),_):- even(A).
PRISM

Extensionz Original FOC = for non-probabilistic programsz Extended for PRISM programs containing

negationz This transformation is meaning-preserving in viewof a new distribution semantics (not included inslides)
PRISM

Constrained HMMs anda dieting professor
 Constrained HMMs are an instance ofprobabilistic constraint modeling.
 They are HMMs with constrains that
may fail.
 Suppose a professor wishes to diet.
 There are two restaurants R0 and R1
 He visits them and orders pizza or
sandwich at R0, and hamburger or
sandwich at R1, probabilstically.
 He records lunches like [s,s,h,p,s,h,s].
 He tries to keep the total lunch calories
in a week < 4000.
 Only successful records are kept.
PRISM

p,s
R0

h,s
R1

 Given: we have a list of
his successful records.
 Task: infer the failure
probability.

Program for the dieting
professor
failure:- not(success).
success:- success(_).
success(L):- diet(L,r0,0,7).

p,sR0diet(L,R,C,N):N>0,msw(lunch(R),D), % order lunch( R == r0,% pizza or sandwich( D = p, C2 is C+900 ; D = s, C2 is C+400 ); R == r1,% hamburger or sandwich( D = h, C2 is C+400 ; D = s, C2 is C+500 ) ),L=[D|L2],
N2 is N-1,msw(tr(R),R2),% next restaurant
diet(L2,R2,R2,N2).
PRISM
diet([],_,C,0):- C < 4000. % calorie constraint must be met

h,sR1

Failure program by FOC
failure:- closure_success0(f0).
closure_success0(A):- closure_chmm0(r0,0,7,A).
closure_chmm0(R,B,C,D): tail recursive just like
( C>0,positive casemsw(tr(R),R2), msw(lunch(R),F),
Æ dynamic programming( R¥==r0; R==r0,( ¥+F=p ; F=p, G is B+900,H is C-1, closure_chmm0(R2,G,H,D)),( ¥+F=s ; F=s, I is B+400,J is C-1,closure_chmm0(R2,I,J,D))),( R¥== r1; R == r1,( ¥+F=h ; F=h, K is B+400,L is C-1,closure_chmm0(R2,K,L,D)),( ¥+F=s ; F=s, M is B+500,N is C-1,closure_chmm0(R2,M,N,D))); C=<0 ),( ¥+C=0 ; C=0, B>=4000 ). PRISM

fgEM learning| ?- prismn(‘prof.psm'),set_sw,generate_goals(500,Gs),learn([failure|Gs]).
success([s,s,p,p,s,h,s])sampled goal...
.........50..(Converged: -2905.412443514)
Finished learning
Number of iterations: 63
Total learning time: 0.2 seconds
All solution search time: 0.08 seconds
0.4

0.6

Switch lunch(r0): p (0.4014) s (0.5986)
0.5
Switch lunch(r1): h (0.5339) s (0.4661) 0.5
Switch tr(r0): r0 (0.7190)0.7r1 (0.2810)0.3
Switch tr(r1): r1 (0.7236)0.7r0 (0.2764)0.3?- prob(failure).
0.3486
The probability of failure is: 0.3448
PRISM

original values

 If failure is not assumed, theestimated failure probability
deteriorates to 0.0823.

NotezFailure programs can be obtainable by other methods
zzz

Manual derivation
z traces all failed paths of computation by inspection andrepresent them as a program.
Negation technique [Sato 89]
z gives better code than FOC but there are restrictions on
applicability

More complex probabilistic constraint modeling thanconstrained HMMs is possible.
zz

Finite PCFGs = PCFGs with failure constraints [Sato 04]
HPSGs = unification based constraint grammar, approximatedby PCFGs
PRISM

References
Please visit http://mi.cs.titech.ac.jp/prism/z Current version is PRISM1.8
z Papers ([Sato 01] is a most comprehensive paper)z[Sato 05] Sato, T., Kameya, Y. and Zhou, N.-F.: Generative modeling withfailure in PRISM. IJCAI2005, to appear, 2005.
[Zhou 04] Zhou, N.-F., Shen, Y.-D. and Sato, T.: Semi-naive Evaluation inLinear Tabling, PPDP04, pp.90–97, 2004.
[Sato 01] Sato, T. and Kameya, Y.: Parameter learning of logic programs forsymbolic-statistical modeling. JAIR, Vol.15, pp.391–454, 2001.
[Cussens 01] Cussens, J.: Parameter estimation in stochastic logic programs.
Machine learning, Vol.44, Issue 3, pp.245–271, 2001.
[Kameya 00] Kameya, Y. and Sato, T.: Efficient EM learning with tabulation forparameterized logic programs. CL2000, LNAI, Vol.1861, pp.269–294, 2000.
[Sato 95] Sato, T.: A statistical learning method for logic programs withdistribution semantics, ICLP95, Tokyo, pp.715–729, 1995.
PRISM

Future planz More sophisticated learning

Conditional random fields
z DAEMz Better tabled searchzz More computer power

Parallel search on a grid machinez 64bitzz More applications

Graph grammars
z User modelingzPRISM