Toward a High-performance System for Symbolic and Statistical Modeling
Neng-Fa Zhou
Department of Computer Science
Brooklyn College & Graduate Center
The City University of New Yorkzhou@sci.brooklyn.cuny.edu
Taisuke Sato
Department of Computer Science,
Tokyo Institute of Technology, CREST JST
sato@mi.cs.titech.ac.jp
Koiti Hasida
Cyber Assist Research Center
AIST Tokyo Waterfront
hasida.k@aist.go.jp
Abstract

and learning. In sample execution mode, a goal may give different results depending on the outcomes of the experiments.
For example, it is possible for a goal to succeed if a coinshows the head after being tossed and to fail if the coin shows
the tail. The probability calculation mode gives the probability of a goal to succeed. In the learning mode, the systemestimates the probabilities of the outcomes of the experimentsfrom given observed data. The PRISM system adopts the EM(Expectation and Maximization) algorithm [Dempster et al.,1976] in probability estimation.
PRISM, as a symbolic statistical modeling language, subsumes several specific statistical tools such as HMM (Hidden Markov Models) [Rabiner, 1989], PCFG (Probabilistic Context Free Grammars) [Wetherell, 1980] and descrete
Bayesian networks [Castillo et al., 1997; Pearl, 1987]. Compared with numeric models where mathematical formulas areused, PRISM offers incomparable flexibility by allowing theuse of arbitrary logic programs to describe probability distributions. PRISM can be used in many areas such as language
processing, decision making, bio-informatics, and game theory where randomness or uncertainty is essential.
This project aims at implementing an efficient system for
PRISM in B-Prolog. For most applications, learning is timeconsuming especially when the amount of observed data islarge. The EM learning algorithm estimates the probabilitiesof outcomes through two phases: the first phase searches forall explanations for the observed facts, and the second phaseestimates the probabilities. The first phase is the neck of thelearning algorithm. We have made several efforts to speed-up
this phase. One is to tabulate partial explanations for subgoals
such that explanations for variant subgoals are searched only
once. With tabling, this phase gives an explanation graph thatfacilitates the estimation of probabilities. The tabling mecha-

We present in this paper a state-of-the-art implementation of PRISM, a language based on Prolog
that supports statistical modeling and learning. We
start with an interpreter of the language that incorporates a naive learning algorithm, and then turn toimprove the interpreter. One of the improvements
is to refine the learning algorithm such that it works
on explanation graphs rather than flat explanations.
Tabling is used to construct explanation graphs sothat variant subgoals do not need to be considered
redundantly. Another technique is compilation.
PRISM programs are compiled into a form thatfacilitates searching for all solutions. The implemented system is, to our knowledge, the first of its
kind that can support real-world applications. The
implemented system, which will be available fromhttp://sato-www.cs.titech.ac.jp/prism/index.html, isbeing applied to several problem domains ranging
from statistical language processing, decision support, to game analysis.

1 Introduction
PRISM (PRogramming In Statistical Modeling) [Sato, 1995;
Sato and Kameya, 2001] is a new language that integrates
probability theory and Prolog, and is suitable for the description of computations in which randomness or uncertainty is
involved. PRISM provides built-ins for describing experiments 1 . A PRISM program can be executed in three different modes, namely sample execution, probability calculation,
1
An experiment is defined by a sample space and a probability distribution for the outcomes in the sample space. For example,
tossing a coin is an experiment where the sample space is {head,tail} and the probability distribution is uniform (this means thatthe events head and tail have the same likelihood to occur) if thecoin is fair.

1

nism of B-Prolog is improved such that copy of data between
the heap and the tabling area is reduced significantly. This
improved version demonstrates a big speed-up when complex
goals with structured data need to be tabulated. Another technique used in the system is compilation. PRISM programs
are compiled into a form that facilitates searching for all solutions.
The main part of this paper is devoted to the implementation techniques. To make the paper self-contained, we startwith an interpreter of PRISM in the next section. The description of the operational semantics is informal and is based on
examples. The reader is referred to [Sato and Kameya, 2001]
for a formal description of the semantics and the EM learningalgorithm adopted in PRISM.

The predicate direction(D) determines the direction to
go by tossing a coin; D is bound to left if the head isshown, and to right if the tail is shown. To set uniform distribution, we use set sw(coin,[0.5,0.5]) to set theprobabilities to the two outcomes. Notice that the following
gives a different definition of direction:
direction(left):msw(coin,head).
direction(right):msw(coin,tail).
While for the original definition, the query direction(D)always succeeds, binding D to either left or right.
The same query may fail for the new definition sincemsw(coin,head) and msw(coin,tail) are two separate trials. If the first trial gives tail and the second trial
gives head, then the query direction(D) fails.
In addition to msw/2, PRISM provides several other builtins, including prob(Goal,Prob) for computing the probability of a goal, sample(Goal) for sample executing agoal, and learn(Facts) for estimating the probabilitiesof the switches in the program from the observed facts. Thesebuilt-ins will be explained in the subsequent subsections.
A predicate is said to be probabilistic if it is defined interms of msw or predicates that are probabilistic. Predicatesthat do not use (either directly or indirectly) msw in its definition are said to be non-probabilistic. This terminology isextended naturally to goals. A goal is said to be probabilistic
if its predicate is probabilistic.

2 PRISM: The Language and its
Implementation
PRISM is an extension of Prolog that provides built-ins forstatistical modeling and learning.

2.1

Built-ins

The built-in msw(I,V) describes a trial of an experiment,
where I is the identifier of an experiment, and V is the outcome of the trial2 . The identifier I can be any complex term,
but I must be ground when the trial is conducted. In thesample-execution mode, the built-in msw(I,V) succeeds if
the trial of the experiment I gives the outcome V. If V is avariable, then the built-in always succeeds, binding V to theoutcome of the experiment.
For each experiment, the user must specify the sample
space by defining the predicate values(I,Space), where
I is the identifier and Space is a list of possible outcomesof the experiment. A probability distribution of an experiment tells the probabilities of the outcomes in the sample
space. The sum of the probabilities of the outcomes in any
experiment must be 1.0. Probability distributions are either
given by the programmer or obtained through learning fromgiven sample data. The predicate set sw(I,Probs) sets
the probabilities of the outcomes in the experiment I, where
Probs is a list of probabilities (floating-point numbers). The
length of Probs must be the same as the number of outcomesin the sample space and the sum of the probabilities must be
equal to 1.0.
The following shows an illustrative example:

2.2

Sample execution

The subgoal sample(Goal) starts executing the programwith respect to Goal in the sample execution mode. If Goalis the built-in msw(I,V), then sample(Goal) succeeds
if the trial of the experiment I gives the outcome V. The outcome of an experiment is chosen randomly, but the probability distribution is respected such that those outcomes thathave the highest probabilities have the most chances to bechosen. Trials of experiments are independent regardless ofwhether or not the experiments are the same.
If Goal is non-probabilistic, then sample(Goal) behaves in the same way as call(Goal). Otherwise, if Goal
is probabilistic, then a clause H:-Body is selected from its
predicate such that H unifies Goal, and sample(Goal) is
reduced to sample(Body).
The following shows a simplified version of the interpreter
for sample execution:

direction(D):msw(coin,Face),(Face==head−>D=left;D=right).

sample((A,B)):-!,
sample(A),sample(B).
sample(msw(I,V)):-!,
R is random(0.0,1.0),% R is a random number in the range of 0.0..1.0
prob distribution(I,Values,Probs),% probability distribution assigned to the experimentchoose outcome(R,Values,Probs,V).
sample(Goal):-prob predicate(Goal),!,clause(Goal,Body),
sample(Body).

values(coin,[head,tail]).
2

The name msw is an abbreviation for multi-outcome switch. In
the version presented in [Sato and Kameya, 2001], the built-in takes
another argument called trial number. The same trial of the same
experiment must give the same outcome. In the new version, alltrials are considered independent by default. If the outcome of atrial needs to be reused, the programmer must have it passed as anargument or have it saved in the global database.

2

soning.

sample(Goal):- % non-probablisticcall(Goal).

You have a blood test for some rare disease which occurs
choose outcome(R,Values,Probs,V):by chance in 1 in every 100,000 people. The test is fairly
choose outcome(R,0.0,Values,Probs,V).
reliable; if you have the disease it will correctly say sochoose outcome(R,Sum,[V|Values],[P|Probs],V):- with probability 0.95; if you do not have the disease, theSum1 is Sum+P,
test will wrongly say you do with probability 0.005. If the
R=<Sum1,!.
test says you do have the disease, what is the probability
choose outcome(R,Sum,[ |Values],[P|Probs],V):- that this is a correct diagnosis?
Sum1 is Sum+P,
choose outcome(R,Sum1,Values,Probs,V).
Let D be the event that you have the disease, D 0 the eventthat you do not have the disease, and T the event that the testsays you do. Then the probability P (D|T ) is calculated asfollows based on the Bayes’ Theorem:Foranexperiment
whose
samplespace
is[V1,V2,...,Vn] and whose probability distribution
is [P1,P2,...,Pn], the callchoose outcome(R,[V1,V2,...,Vn],[P1,P2,...,Pn],V)P (T |D)P (D)P (T )P (T |D)P (D)P (T |D)P (D)+P (T |D 0 )P (D 0 )0.95×0.00001
0.95×0.00001+0.005×0.99999=== 0.1896

Pk
selects the outcome Vk such that
i=1 P i ≥ R and
Pk−1
P
i
<
R.
i=1
The real interpreter handles other constructs including
negation, disjunction, if-then-else, and the cut operator in addition to conjunction.

2.3

P (D|T )=The Bayesian network for this problem consists of two
nodes, called disease and test. The outcomes of both
nodes are {yes, no}. The node test is dependent on
the node disease. The following clause represents the network:

Calculating the probabilities of goals

disease test(D,T):msw(disease,D),
msw(test(D),T).

In statistical modeling, it is often necessary to calculate the probability of events. In PRISM, the built-inprob(Goal,Prob) calculates the probability Prob withwhich Goal becomes true. It is assumed that all probabilistic ground atoms in the Herbrand base of a program are probabilistically independent and exclusive. With these assumptions, the probability of the conjunction (A,B) is computed
as the product of the probabilities of A and B (independent),
and the probability of the disjunction (A;B) is computed as
the sum of the probabilities of A and B (exclusive). For aswitch msw(I,V), the probability is 1.0 if V is a variable,
and the probability assigned to the outcome V if V an element
is the sample space.
For example, recall the illustrative example direct. Assume the distribution of the coin experiment is uniform. The
probability of direction(left) is 0.5 since the probability of msw(coin,head) is 0.5. The probability of
direction(D) is 1.0 sine the sum of the probabilities ofmsw(coin,head) and msw(coin,tail) is 1.0.
The programmer must bear the above assumptions in mind
when writing programs. Programs that violates this assumption will give wrong results. For example, the conjunction(A,A), which makes sense logically, is not allowed probabilistically since the conjuncts are not independent. Likewise
the disjunction (A;A) is not allowed. If the disjuncts are notindependent, the probability of a goal may exceed 1.0.
One question arises: if events are assumed to be independent, then how to represent conditional events in PRISM? Let
B and C be two experiments. Assume C has the possible
outcomes {c1 , ..., cn }. The conditional event (B|C) can be
represented by using n switches: msw(b(ci ), Vi ) (i=1,...,n).
Consider, for example, the following problem taken from
[Stirzaker, 1994], which is a typical example of Bayesian rea-

The sample spaces of all the experiments are [yes,no].
The switch msw(disease,yes) says that you have thedisease, and the switch msw(disease,no) says no. The
switch msw(test(D),T), which depends on the outcomeof the node disease, says that the diagnostic result is T if
the outcome of disease is D. For the problem, the given
probabilities are set as follows:
set sw(disease,[0.00001,0.99999]),% P(D)=0.00001
set sw(test(yes),[0.95,0.05]),% P(T|D)=0.95
set sw(test(no),[0.005,0.995])% P(T|D’)=0.005
If the test says you do have the disease, then the probability
that this is a correct diagnosis is calculated by the query:prob(disease test(yes,yes),P1),
prob(disease test( ,yes),P2),
P is P1/P2.
The
goal
prob(disease test(yes,yes),P1)
gives the probability of the event that you havethe disease and is also diagnosed so, and the goalprob(disease test( ,yes),P2) gives the probability of the event that you are diagnosed of the disease
regardless whether or not you have the disease. The querygives the same result 0.1896 as the one obtained by using
Bayes’ Theorem directly.
Since new switches can be created when needed, it is possible to represent in PRISM any Bayesian networks and perform Bayesian reasoning on them.
3

2.4

procedure em(F) begin
initialize  to a small positive number;foreachPi ∈ I, v ∈ Vi initialize θi,v ;λ1 = f ∈F (ln(θf )); /* initial likelihood */repeatλ0 = λ 1 ;foreach i ∈ I, v ∈ P
Vi(θe ×δi,v (e))
Pe∈Ef
ηi,v = f ∈F ()θf/* expected count of msw(i, v) */foreach i ∈ I, v ∈ Viη
θi,v = P i,v(η )i,v00v ∈V iP
λ1 = f ∈F (ln(θf ));until λ1 − λ0 < 
endLearning

The built-in learn(Facts) takes Facts, a list ofobserved facts, and estimates the probabilities of theswitches that explain Facts. While sample(Goal) andprob(Goal,Prob) are deductive, using the current distributions of switches to deduct Goal, learn(Facts) is
abductive, which finds the explanations for Facts and use
the explanations to estimate the distributions of the switches.
PRISM adopts the EM learning algorithm to learn distributions. It first finds all the explanations for the observed facts.
Then it repeatedly estimates and maximizes the likelihood of
the observed facts until the estimation is stable.
An explanation for an observed fact is a set of switches that
occur in a path of the execution of the fact. The following is
an interpreter that searches for explanations for a goal:
expls(G,Exs):- %Exs is a list of explanations for G
findall(Ex,expl(G,Ex,[]),Exs).
expl((G1,G2),Ex,ExR):-!,
expl(G1,Ex,Ex1),
expl(G2,Ex1,ExR).
expl(msw(I,V),[mse(I,V)|ExR],ExR):-!,
values(I,Values), % sample space is Values
member(V,Values).
expl(G,Ex,ExR):prob predicate(G),!, %G is a probabilistic
clause(G,B),
expl(B,Ex,ExR).
expl(G,Ex,Ex):call(G).
Recall our illustrative example direction.
For
the fact direction(left), the interpreter finds[msw(coin,head)], and for the fact direction(right) it finds [msw(coin,tail)] as the
explanations. In general, there may exist multiple execution
paths for an observed fact and each execution path may
contain multiple switches.
After all the explanations are found, the EM algorithm
turns to estimate the probabilities of the switches in the explanations. Let I be the set of switches, and Vi be the sample
space of switch i. For each switch msw(i, v), θi,v denotes
the probability of the outcome v. The following assertion
must hold∀i∈I Σv∈V i θi,v = 1.0.
Let F be a set of observed facts. For each fact f ∈ F , Ef
denotes the set of explanations. Let e ∈ Ef be an explanation.
The probability of e is the product of the probabilities of all
the switches in the explanation:Y(θi,v )
θe =Figure 1: The EM algorithm
algorithm. The algorithm repeats the estimation until the likelihood of the observed facts becomes stable.
The use of the term ηi,v , which estimates the number ofoccurrences of the switch msw(i, v) that contribute to the observed facts, is essential in the algorithm. The probability of
msw(i, v) is estimated as the ratio of its count to the count of
all the outcomes of the switch.
ηi,v
θi,v = Pv 0 ∈V i (ηi,v 0 )For our illustrative example, the algorithm converges ina few iterations. If only direction(left) is observed,
then the estimated probability of head is close to 1.0 and thatof tail is close to 0.0; if direction(left) and direction(right) each occupy half of the observed facts,
then the estimated distribution is close to uniform. For more
complicated programs, more iterative steps are required toobtain a stable estimation.

3 Improvements of the Implementation
The interpreters and the EM learning algorithm presented in
the previous section are naive and inefficient. The number of
explanations for a set of observed facts may be exponential.
Therefore, it is expensive to find explanations and it is also
expensive to go though the explanations to estimate the probabilities of the switches in the explanations. In this section,
we propose several techniques for improving the implementation, especially the learning algorithm.

3.1

msw(i,v)∈e

Explanation Graphs

It is not hard to notice that explanations differ from each otherby only a small number of switches. Just as it is importantto factor out common sub-expressions in evaluating expressions, it is important to factor out common switches amongexplanations. Actually, a logic program provides a natural
structure for factoring out common switches. Instead of considering explanations as lists of switches, we consider explanations as a graph.

The probability of fact f is the sum of the probabilities of allits explanations:
X
θf =
(θe )
e∈Ef

The log likelihood of fact f is defined as ln(θf ). For eachexplanation e ∈ Ef , let δi,v (e) denote the number of occurrences of the switch msw(i, v) in e. Figure 1 shows the EM4hmm([a,b,a],3)→ hmm(1,3,s0,[a,b,a]) & msw(init,s0)→ hmm(1,3,s1,[a,b,a]) & msw(init,s1)
hmm(1,3,s0,[a,b,a])→ hmm(2,3,s0,[b,a]) & msw(tr(s0),s0), msw(out(s0),a)→ hmm(2,3,s1,[b,a]) & msw(tr(s0),s1), msw(out(s0),a)hmm(1,3,s1,[a,b,a])→ hmm(2,3,s0,[b,a]) & msw(tr(s1),s0), msw(out(s1),a)→ hmm(2,3,s1,[b,a]) & msw(tr(s1),s1), msw(out(s1),a)hmm(2,3,s0,[b,a])→ hmm(3,3,s0,[a]) & msw(tr(s0),s0), msw(out(s0),b)→ hmm(3,3,s1,[a]) & msw(tr(s0),s1), msw(out(s0),b)hmm(2,3,s1,[b,a])→ hmm(3,3,s0,[a]) & msw(tr(s1),s0), msw(out(s1),b)→ hmm(3,3,s1,[a]) & msw(tr(s1),s1), msw(out(s1),b)hmm(3,3,s0,[a])→ hmm(4,3,s0,[]) & msw(tr(s0),s0), msw(out(s0),a)→ hmm(4,3,s1,[]) & msw(tr(s0),s1), msw(out(s0),a)hmm(3,3,s1,[a])→ msw(tr(s1),s0), msw(out(s1),a)→ msw(tr(s1),s1), msw(out(s1),a)An explanation path for a fact H is defined as (H →Bg & Bs ) where Bg is a set of facts and Bs is a set ofswitches. H is called the root of the path. An explanation
path corresponds to an instance of a clause where Bg is theset of probabilistic subgoals, and Bs the set of switches inthe body. An explanation tree for a fact consists of a set of
explanation paths that have the fact as the root. The root of
the paths is also called the root of the tree. An explanation
tree corresponds to an instance of a predicate. An explanation graph consists of a set of explanation trees whose roots
are all distinct.
a,b
s0

a,b

a,b

s1

a,b

Figure 3: The explanation graph for hmm([a,b,a],3).

Figure 2: An example HMM.

general. Recall the explanation graph in Figure 3. The sizeof the graph is O(N × S) where N is the length of the string
and S is the size of the largest sample space. If shared goals
in different paths, such as the two underlined ones, are considered only once, then it takes only linear time to construct
the explanation graph.
Tabling or memoization [Tamaki and Sato, 1986; Warren,
1992; Zhou et al., 2000] can used to avoid redundant computations. The idea of tabling is to memorize the answers to
subgoals and use the answers to resolve subsequent variant
subgoals. The table area is global and answers stored in it
can survive over backtracking. Therefore, variant subgoals
can share answers regardless where they occur in execution.
They can occur in the same execution path or different paths.
The following gives an interpreter for constructing the explanation graph for a goal.
expls(G):expl(G, ,[], ,[]),fail.
%backtrack to find all paths
expls(G).

Consider, for example, the following program that represents the two-state HMM3 in Figure 2,hmm(L,N) :msw(init,Si),
hmm(1,N,Si,L).
% Current state is S, current position is I.
hmm(I,N,S,[]) :- I>N,!.
hmm(I,N,S,[C|L]) :msw(out(S),C),
msw(tr(S),NextS),
I1 is I+1,
hmm(I1,N,NextS,L).
values(init,[s0,s1]).
values(out( ),[a,b]).
values(tr( ),[s0,s1]).
The predicate hmm(L,N) analyses or generates a string L oflength N. The explanation graph for hmm([a,b,a],3) isshown in Figure 3.
It is assumed that explanation graphs are acyclic, i.e., afact cannot be used to explain the fact itself. This assumption, however, does not rule out left recursion. Consider, forexample, the following CFG rule,s(I,J):-s(I,I1),a(I1,J).
Although s(I,J) and s(I,I1) are variants as subgoals,
they are instantiated to different instances and thus no fact isused to explain the fact itself.

3.2

expl((G1,G2),Bg,BgR,Bs,BsR):-!,
expl(G1,Bg,Bg1,Bs,Bs1),
expl(G2,Bg1,BgR,Bs1,BsR).
expl(msw(I,V),Bg,Bg,[mse(I,V)|Bs],Bs):-!,
values(I,Values), % sample space is Values
member(V,Values).
expl(G,[G|Bg],Bg,Bs,Bs):prob predicate(G),!,%G is a probabilistic predicate
expl prob goal(G).
expl(G,Bg,Bg,Bs,Bs):call(G).

Constructing Explanation Graphs Using
Tabling

If goals were treated independently in constructing explanation graphs, the computation would still be exponential in:-table expl prob goal/1.
expl prob goal(G):clause(G,Body),
expl(Body,Bg,[],Bs,[]),
add to database(path(G,Bg,Bs)).

3

An HMM is a probabilistic automaton in which the selectionsof the initial state, output symbols, and transitions on the symbols
are all probabilistic.

5

The expl(G,Bg,BgR,Bs,BsR) is true if Bg-BgR isthe list of probabilistic subgoals and Bs-BsR is the listof switches in G. For each probabilistic subgoal G, theexpl prob goal(G) finds the explanation paths for G.
The predicate expl prob goal/1 is tabled. So variant probabilistic subgoals share explanation paths. The
add to database(path(G,Bg,Bs)) adds the path tothe database if the path is not there yet.
The naive EM learning algorithm is reformulated such that
it works on explanation graphs. Since explanation graphs areacyclic, it is possible to sort the trees in an explanation graphbased on the calling relationship in the program. The refinedalgorithm is able to exploit the hierarchical structure to propagate probabilities over sorted explanation graphs efficiently.

Table 1: Learning times for a corpus (seconds).
# sentences all-solution-search EM learning
1000
268
2022
1500
445
3938
2000
855
5542
Notice that no path is added to the database for the first clausesince the body does not contain switches nor probabilistic
subgoals.

4 Experience

The PRISM system has been fully implemented in B-Prolog,
a CLP system that supports tabling. The tabling system in
B-Prolog was first implemented in 1999 [Zhou et al., 2000]
The interpreter presented above is inefficient since it introand was recently re-implemented to meet the requirements ofduces an extra level of interpretation. The interpreter version
PRISM. The new implementation inherits the linear tablingof the PRISM system is used in debugging programs. For
idea, and incorporates new strategies and optimization techlearning from a large amount of data, it is recommended thatniques for fast computation of fixpoints [Zhou and Sato,the compiler version be used. The PRISM compiler trans2003]. As a tabling system, B-Prolog is twice as fast as andlates a program into a form that facilitates the construction of
consumes an order of magnitude less stack space than XSB,
explanation graphs.
a Prolog system developed at SUNY Stony Brook.
Let p(X1,...,Xn):-B be a clause in a probabilistic
The current version of PRISM is, to our knowledge, thepredicate. The compiler translates it into:
first of its kind that can support real-world applications. Several application projects are going on at the moment [Satoexpl p(X1,...,Xn):and Zhou, 2003]. One of the projects is to use PRISM to learn
B’,
add to database(path(p(X1,...,Xn),Bg,Bs)).probabilities of the Japanese grammar rules from corpora. Table 1 shows the times spent in learning from various numbers
where B’ is the translation of B, Bg is the list of probabilisof sentences on Windows XP (1.7G CPU, 760M RAM). The
tic subgoals in B’, and Bs is the list of switches in B. For
first phase of learning, i.e., finding explanations has improved
each subgoal G in B, if G is msw(I,V), then it is transsignificantly thanks to the adoption of the new tabling system
lated into values(I,Values),member(V,Values).
in B-Prolog. The EM learning phase dominates the learnOtherwise, it is copied to B’, renaming each predicate p toing time now. In the current version, explanation graphs are
expl p. The translated predicate is declared as a tabled
represented as Prolog terms. The EM learning phase can bepredicate, so explanation trees need to be constructed only
improved if better data structures are used.
once for variant subgoals.
For example, the predicate

3.3

Compilation

5 Related Workhmm(I,N,S,[]) :- I>N,!.
hmm(I,N,S,[C|L]) :msw(out(S),C),
msw(tr(S),NextS),
I1 is I+1,
hmm(I1,N,NextS,L).

PRISM was first designed by Sato [Sato, 1995] who proposed a formal semantics, called distribution semantics, forlogic programs with probabilistic built-ins, and derived an
EM learning algorithm for the language from the semantics.
The need for structural explanations was envisioned in [Satoand Kameya, 2001], but this paper presents the first serious
is translated into:
implementation of the EM learning algorithm that works on
explanation graphs.
:-table expl hmm/4.
Poole’s abduction language [Poole, 1993] incorporates
expl hmm(I,N,S,[]) :- I>N,!.
Prolog and Bayesian networks, in which probability distribuexpl hmm(I,N,S,[C|L]) :tions are given as joint declarations. Muggleton’s stochastic
values(out(S),Values1), % msw(out(S),C),
logic language [Muggleton, 1996] is an extension of PCFG
member(C,Values1),
values(tr(S),Values2), % msw(tr(S),NextS) where clauses are annotated with probabilities. In both languages, probability distributions are specified by the users,
member(NextS,Values2),
and learning from sample data is not considered.
I1 is I+1,
Non-logic based languages have also been designed to supexpl hmm(I1,N,NextS,L),
add to database(path(hmm(I,N,S,[C|L]), port statistical modeling (e.g., [Pfeffer et al., 1999; Ramsey and Pfeffer, 2002]). The built-in function choose in[hmm(I1,N,NextS,L)],the stochastic lambda calculus [Ramsey and Pfeffer, 2002][msw(out(S),C),
is similar to msw in PRISM, which returns a value from themsw(tr(S),NextS)])).
6

[Rabiner, 1989] L. R. Rabiner. A tutorial on hidden Markov
models and selected applications in speech recoginition.
Proceedings of the IEEE, 77:257–286, 1989.
[Ramsey and Pfeffer, 2002] Norman Ramsey and Avi Pfeffer. Stochastic lambda calculus and monads of probability
distributions. In Conference Record of POPL’02: The 29th
ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 154–165, Portland, Oregon,
January 16–18, 2002.
[Sato and Kameya, 2001] A. Sato and Y. Kameya. Parameter
learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research, pages
391–454, 1999.
[Sato and Zhou, 2003] T. Sato and N.F. Zhou. A new perspective of prism. IJCAI Workshop on Learning Statistical
Models from Relational Data, submitted, 2003.
[Sato, 1995] Taisuke Sato. A statistical learning method forlogic programs with distribution semantics. In Leon Sterling, editor, Proceedings of the 12th International Conference on Logic Programming, pages 715–730, Cambridge,
June 13–18 1995. MIT Press.
[Stirzaker, 1994] D. Stirzaker.
Elementary Probability.
Cambridge University Press, 1 edition, 1994.
[Tamaki and Sato, 1986] Hisao Tamaki and Taisuke Sato.
OLD resolution with tabulation. In Ehud Shapiro, editor, Proceedings of the Third International Conference on
Logic Programming, Lecture Notes in Computer Science,
pages 84–98, London, 1986. Springer-Verlag.
[Warren, 1992] D. S. Warren. Memoing for logic programs.
Comm. of the ACM, Special Section on Logic Programming, 35(3):93, March 1992.
[Wetherell, 1980] C. S. Wetherell. Probabilistic languages:
A review and some open questions. ACM Computing Surveys, 12(4):361–379, December 1980.
[Zhou and Sato, 2003] N.F. Zhou and T. Sato. Efficient fixpoint computation in linear tabling. to be submitted, 2003.
[Zhou et al., 2000] Neng-Fa Zhou, Yi-Dong Shen, Li-Yan
Yuan, and Jia-Huai You. Implementation of a linear
tabling mechanism. Lecture Notes in Computer Science,
1753:109–123, 2000.

sample space randomly. Non-logic languages do not support
nondeterminism. Therefore, it would be difficult to devise an
EM like learning algorithm for these languages.
Tabling shares the same idea as dynamic programming inthat both approaches make full use of intermediate resultsof computation. Using tabling in constructing explanationgraphs is analogous to using dynamic programming in the
Baum-Welch algorithm for HMM [Rabiner, 1989] and theInside-Outside algorithm for PCFG [Baker, 1979].

6 Concluding Remarks
This paper has presented an efficient implementation of
PRISM, a language designed for statistical modeling andlearning. The implementation is the first serious one of its
kind that integrates logic programming and statistical reasoning/learning. The high performance is attributed to several
techniques. One is to adopt explanation graphs rather than flat
explanations in learning and use tabling to construct explanation graphs. Another technique is compilation. Programs arecompiled into a form that facilitates searching for all solutions.

Acknowledgement
Thanks go to Shigeru Abe for his help in implementing therefined EM learning algorithm. Part of the work by NengFa Zhou was conducted while he visited Tokyo Institute ofTechnology in the summer of 2002.

References[Baker, 1979] J. K. Baker. Trainable grammars for speech
recognition. In Speech Communication Papers for the 97th
Meeting of the Acoustical Society of America, pages 547–
550, 1979.
[Castillo et al., 1997] Enrique Castillo, Jose Manuel Gutierrez, and Ali S. Hadi. Expert Systems and Probabilistic
Network Models. Springer, New York, 1 edition, 1997.
[Dempster et al., 1976] A. P. Dempster, N. M. Laird, andD. B. Rubin. Maximum likelihood from incomplete data
via the EM algorithm. Proceedings of the Royal StatisticalSociety, pages 1–38, 1976.
[Muggleton, 1996] S. Muggleton. Stochastic logic programs. In L. De Raedt, editor, Advances in Inductive Logic
Programming, pages 254–264. IOS Press, 1996.
[Pearl, 1987] J. Pearl. Probabilistic Reasoning in Intelligent
Systems. Morgan Kaufmann Publishers, Inc., 1987.
[Pfeffer et al., 1999] Avi Pfeffer, Daphne Koller, Brian
Milch, and Ken T. Takusagawa. SPOOK: A system forprobabilistic object-oriented knowledge representation. In
Kathryn B. Laskey and Henri Prade, editors, Proceedingsof the 15th Conference on Uncertainty in Artificial Intelligence (UAI-99), pages 541–550, S.F., Cal., July 30–
August 1 1999. Morgan Kaufmann Publishers.
[Poole, 1993] David Poole. Probabilistic Horn abduction andBayesian networks. Artificial Intelligence, 64(1):81–129,
1993.
7