EÆcient EM Learning with Tabulation for
Parameterized Logic Programs
Yoshitaka KAMEYA and Taisuke SATO
Dept. of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology,
Ookayama 2-12-1, Meguro-ku, Tokyo, Japan, 152-8552.
kame@mi.cs.titech.ac.jp, sato@cs.titech.ac.jp

We have been developing a general symbolic-statistical modeling language [6, 19, 20] based on the logic programming frameworkthat semantically uni es (and extends) major symbolic-statistical frameworks such as hidden Markov models (HMMs) [18], probabilistic contextfree grammars (PCFGs) [23] and Bayesian networks [16]. The language,
PRISM, is intended to model complex symbolic phenomena governed byrules and probabilities based on the distributional semantics[19]. Programs contain statistical parameters and they are automatically learned
from randomly sampled data by a specially derived EM algorithm, thegraphical EM algorithm. It works on support graphs representing theshared structure of explanations for an observed goal. In this paper, we
propose the use of tabulation technique to build support graphs, andshow that as a result, the graphical EM algorithm attains the same timecomplexity as specilized EM algorithms for HMMs (the Baum-Welchalgorithm [18]) and PCFGs (the Inside-Outside algorithm [1]).

Abstract.

1

Introduction

We have been developing a general symbolic-statistical modeling language [19,20, 6] based on the logic programming framework that semantically uni es (andextends) major symbolic-statistical frameworks such as hidden Markov models(HMMs) [18], probabilistic context-free grammars (PCFGs) [23] and Bayesian
networks [16]. The language, PRISM (programming in statistical modeling), isintended to model complex symbolic phenomena governed by rules and probabilities using the distributional semantics [19]. Programs contain statistical parameters and they are automatically learned from randomly sampled data by aspecially derived EM algorithm, the graphical EM algorithm. It works on support
graphs representing the shared structure of explanations for an observed goal. In
this paper, we propose the use of tabulation technique to build support graphs,
and show that as a result, the graphical EM algorithm attains the same timecomplexity as specilized EM algorithms for HMMs (the Baum-Welch algorithm[18]) and PCFGs (the Inside-Outside algorithm[1]). Our subject in this paper
is inter-deciplinary, concerning logic programming, probability theory, statistics
and formal languages, and the reader is assumed to be familiar with basics ofthese deciplines [5, 11, 18, 22, 23].

The rest of this paper is as follows. After having a look at background in thenext section, and preparing basic materials of PRISM in Sec 3, we present aneÆcient learning algorithm for PRISM (Sec. 4). We evaluate the time complexityof our algorithm in Sec. 5. Sec. 6 contains a conclusion. Throughout the paper,
we use Prolog conventions for logic programs.

2

Background

2.1 Constraint approach and distribution approach
Since our work is at the crossroads of logic programming and probability, it
might help to rst review various attempts made to integrate probability withlogic, or logic programming (though we do not claim exhaustiveness of the listat all). In reviewing, one can immediately notice there are two di erent basic
attitudes towards the use of probability in logic or logic programming. One type,
constraint approach, emphasizes the role of probabilities as constraints and does
not necessarily seek for a unique probability distribution over logical formulas.
The other type, distribution approach, explicitly de nes a unique distribution bymodel theoretical means or proof theoretical means, to compute various probabilities of propositions.
A typical constraint approach is seen in the early work of probabilistic logic
by Nilsson [15]. He considered probabilities assigned to formulas in a knowledge base as constraints on the possible range of probability of a formula ofinterest. He used linear programming techniques to solve constraints that necessarily delimits the applicability of his approach to nite domains. Turining
to logic programming, probabilistic logic programming formalized by Ng andSubrahmanian used clauses of the form A :  F1 : 1 ; : : :; Fn : n annotatedby probability intervals i s [13]. Lakshmanan and Sadri also used annotatedc B ; : : :; B where c = hI ; I i in the formalization of their probclauses A
1nb dabilistic logic programming. Here Ib represents an expert's belief interval, Id a
doubt interval respectively [10]. Both formalizations only allowed for a nite
number of constant and predicate symbols, but no function symbols[10, 13].
Some of the early works of the distribution approach to combining probability with logic programs came out of the Bayesian network community1. Breesemade a rst attempt to use logic programs to automatically build a Bayesian
network from a query [2]. After identifying atoms relevant to the query, a local Baysian network for them is constructed to compute posterior probabilities. Logical variables can appear in atoms but no function symbol was allowed [2] (see also [14] for recent development of the use of logic programs tobuild Bayesian networks). Poole proposed \probabilistic Horn abduction" [17].
His program consists of de nite clauses and disjoint declarations of the form
disjoint([h1:p1,...,hn:pn]) which speci es a probability distribution overthe hypotheses (abducibles) fh1; : : :; hng. He assigned unique probabilities to all
1

A Bayesian network is a nite directed acyclic graph representing probabilistic dependences between (continuous or discrete) random variables [16]

ground atoms with the help of the theory of logic programming, and furthermore
proved that Bayesian networks are representable in his framework [17]. He however imposed various conditions (the covering property, the acyclicity property,
etc [17]) on the class of applicable programs.
In a more linguistic vein, Muggleton formulated SLP (Stochastic Logic Programming) procedurally, as an extension of logic programming to PCFGs [12].
So, a clause C , which must be range-restricted2 , is annotated with a probability
p like p : C . The probability of a goal G is the products of such ps appearing
in its derivation, but with a modi cation such that if a subgoal g can invoke nclauses, pi : Ci (1  i  n) at some derivation
P step, the probability of choosing k-th clause is normalized, that is pk = ni=1 pi. SLP was further extended
by Cussens by introducing the notion of loglinear models for SLD refutation
proofs and de ning probabilities of ground atoms in terms of their SLD-trees
and \features"[3].

2.2 Limitations and problems
Approaches described so far have more or less similar limitations and problems.
Descriptive power con ned to nite domains is the most common limitation,
which is due to the use of linear programming techniques [15], or due to the syntactic restrictions not allowing for in nitely many constant, function or predicate
symbols [10, 13]. Bayesian networks have the same limitation as well (only a nite
number of random variables are representable). Also there are various semantic/syntactic restrictions on logic programs. For instance the acyclicity condition [14, 17] prevents the use of clauses with local variables unconditionally, andthe range-restrictedness [3, 12] excludes programs such as the usual membership
Prolog program. These restrictions would cause problems when we model the
distribution of in nitely many objects such as natural language sentences [11].
There is another type of problem, the inconsistent assignment of probabilities.
Think of extensions of PCFGs to logic programs [3, 12]. Since they de ne theprobability Pr(A) of an atom A in terms of syntactic features of the proof trees
for A, it is quite possible for Pr(A) and Pr(A ^ A) to di er as their proof trees
are di erent, though logically, they are one and the same.
Last but not least, there is a big problem common to any approach using
probabilities: where do the numbers come from? Generally speaking, if we use nbinary random variables, we need to get 2n probabilities to completely specify
their joint distribution, and this kind of attempt quickly becomes impossible as
n grows. Also if there are \hidden variables" in the model such as true causes ofa disease, we need lots of work to get reliable probabilities of those variables. Despite these diÆculties, all approaches in subsection 2.1 assume their numbers are
given a priori, and none of them address the problem of how to nd probabilities,
excepts attempts to use learning techniques for Bayesian networks [8].
2

A syntactic property that variables appearing in the head also appear in the bodyof a clause. So, a unit clause must be ground.

2.3 The idea of PRISM
We have been developing a general symbolic-statistical modeling language called
PRISM since 1995 along the line of the distribution approach that is free of limitations mentioned above [19, 20]. It is a probabilistic logic programming language
equipped with a new semantic framework termed the distributional semantics[19], an extension of the least Herbrand model semantics to possible world semantics with a distribution. Theoretically, a PRISM program DB = F [ R iscomprised of a denumerable3 number of ground facts (hypotheses, abducibles) F
and a denumerable number of rules (de nite clauses) R in a rst-order languagewith a denumerable number of constant symbols, function symbols and predicate
symbols. F is supposed to come with a basic distribution PF that is a completely
additive probability measure. So every ground atom in F is considered a randomvariable taking on 1 (true) or 0 (false). A sampling of PF determines a set F 0of true atoms, which in turn determines the set of true atoms as MDB (F 0 [ R)where MDB denotes the least Herbrand model of F 0 [ R. Hence, every groundatom in DB is a random variable. Their joint distribution PDB , a completely additive probability measure as an extension of PF , is de ned to be the denotation(declarative semantics) of DB (the distributional semantics) [19].
Thanks to a general semantic framework, we need none of restrictions suchas no function symbols and a nite number of constant and predicate symbols [2,4, 8, 10, 13], the acyclicity [14, 17] and the covering assumption [17], the rangerestrictedness of clauses [3, 12], or the niteness of domains [2, 4, 15]. A user
can write whatever program he/her likes at their own risk without a fear ofinconsistent probabilities. Also we succeeded in deriving a new EM learningalgorithm for learning statistical parameters in PRISM programs (BS programs)[19], and hence every program can learn from positive examples. So far, we havecon rmed the descriptive/learning power of PRISM by tackling various domains
including three major symbolic-statistical models, HMMs, PCFGs and Bayesian
networks [20].4

2.4 Problem of computational complexity
The major problem with the current implementation of PRISM is the slow speedof learning. After determining the scope of symbolic-statistical phenomena wemodel such as stochastic language generation, we write a parameterized model
DB (= F [R) that can explain conceivable observations (sentences for instance).
If independent observations G1; : : :; GT are given, we let our
Q EM algorithm tolearn statistical parameters in DB by (locally) maximizing t PDB (Gt = 1). The
learning process starts with collecting all such S  F that S [ R j= G for eachobservation Gt. This all solution search usually contains a lot of redundancy,
We hereafter use a term \denumerable" as a synonym of \countably in nite." Thenite case is similarly treated.
4
Koller has proposed a probabilistic functional language [9] which can represent
HMMs, PCFGs and Bayesian networks, but left the problem of declarative semantics
and learning untouched.
3and in case of HMMs, we end up in the time complexity exponential in thelength of an input string. The reason is obvious: in the stochastic automata
such as HMMs, the number of transition paths is exponential, but the BaumWelch algorithm [18], the specialized EM algorithm for HMMs, achieves linear
time complexity by taking advantage of structure-sharing of transition paths
represented as a trellis diagram, which corresponds to the reuse of solved subgoals
in logic programming. We therefore introduced a reuse mechanism of solved goals
such as OLDT search [21] in PRISM, and thus rederived the whole EM algorithm
to combine with the OLDT search. Owing to this entire reconstruction, our EM
algorithm, though applicable to even type-0 stochastic grammars, has achieved
the same time complexity as specialized EM algorithms as far as HMMs and
PCFGs are concerned, as described in the sequel.

3

PRISM programs

In this section, we de ne PRISM programs and the related concepts. See also
the basic idea of the distributional semantics in Sec. 2.3.

De nition 1. A PRISM program is a de nite clause program DB = F [ Rwhich satis es the following conditions on facts F , their distribution PF andrules R.

1. F is a set of ground atoms of the form msw(i,n,v). The arguments i and n
are called group-id (or switch name) and trial-id, respectively. We assume
that a nite set Vi of ground terms is associated with each i, and v 2 Vi
holds.5 Vi corresponds to a set of possible values of switch i.
2. Let Vi be fv1 ; v2; : : :; vjVij g. Then, one of the ground atoms msw(i,n,v1),
msw(i,n,v2), . . . , msw(i,n,vjVij ) becomes exclusively true (takes the value1) on each trial. For each i, i;v 2 [0; 1] is a parameterof the (marginal)P
probability of msw(i,,v) being true (v 2 Vi ), and v2Vi i;v = 1 holds.
3. For each ground terms i, i0 , n, n0, v 2 Vi and v0 2 Vi , random variable
msw(i,n,v) is independent of msw(i0,n0,v0 ) if n 6= n0 or i 6= i0 .
4. De ne head (R) as a set of atoms appearing in the head of R. Then, F \head (R) = ;.
0

In the rst condition, we introduce a predicate msw=3 to represent a basic
probabilistic choice such as coin-tossing (msw stands for multi-valued switch). A
ground atom msw(i,n,v) represents an event \a switch named i takes on v as asample value on the trial n." We combine these switches to build a probability
distribution of complex phenomena. The second and the third condition saythat a logical variable V in msw(i,n,V) behaves like a random variable which isrealized to vk with probability i;vk (k = 1 : : : jVij).6 Moreover, from the third
condition, the logical variables V1 and V2 in msw(i,n1,V1) and msw(i,n2,V2) can
As described before, we consider DB as a denumerable set of ground clauses, i andn are arbitrary ground terms in the Herbrand universe.
6
These probabilities are either learned or given by the user.
5be seen as independent and identically distributed (i.i.d.) random variables if n1
and n2 are di erent ground terms. The fourth condition says that no msw(,,)appears in the head of R.

3.1 A program example
We here pick up a PRISM program which represents an HMM, also known as aprobabilistic regular grammar. HMMs de ne a probability distribution over thestrings of given alphabets, and can be considered as probabilistic string generators [18], in which an output string is a sample from the de ned distribution.
The HMM represented below7 has two states fs0; s1g and outputs a symbol aor b in each state. For simplicity, the length of output strings is xed to three.
(1) target(hmm/1).
(2) data('hmm.dat').
(3) table([hmm/1,hmm/3]).
(7) hmm(Cs):msw(init,null,Si),
hmm(1,Si,Cs).
(8) hmm(T,S,[C|Cs]):- T=<3,
msw(out(S),T,C),
msw(tr(S),T,NextS),
T1 is T+1,
hmm(T1,NextS,Cs).
(9) hmm(T,_,[]):- T>3.

(4) values(init,[s0,s1]).
(5) values(out(_),[a,b]).
(6) values(tr(_),[s0,s1]).
% To generate a string (chars) Cs...
%
Set initial state to Si, and then%Enter the loop with clock = 1.
% Loop:%
Output C in state S.
%
Transit from S to NextS.
%
Put the clock ahead.
%Continue the loop (recursion).
% Finish the loop if clock > 3.

Procedurally, the above HMM program simulates the generation process ofstrings (see the comments in the program). Clauses (7)(9) represent the probabilistic behavior of the HMM. In clause (8), to output a symbol C, we use di erent switches out(S) conditional on the state S.8 Note that T in msw(out(S),T,C)
is used to guarantee the independency among the choices at each time step. Recursive clauses like (8) are allowed in the distributional semantics, and so are
in PRISM. Clauses (1)(6) contain additional information about the program.
Clause (1) declares only the ground atoms containing hmm=1 are observable.
hmm([a,b,a]) being true means this HMM generates the string aba. Clause (2)speci es a le storing learning data. Clause (3) speci es the table predicates(described later) are hmm=1 and hmm=3. We can read that Vinit = fs0; s1g,
Vout() = fa; bg, Vtr() = fs0; s1g from clauses (4)(6).

3.2 Further de nitions and assumptions
For the learning algorithm for PRISM, we need some de nitions and assumptions. For the moment, we assume the set I of group-ids coincides with the
78

The clause numbers are not written in the actual program.
Generally speaking, a conditional probability table (CPT) of a random variable
X can be represented by the switch msw(f (c1,c2 ,...,cn),,x), where n is thenumber of conditional variables, f is the id of X , ci (i = 1 : : : n) is the value of eachconditional variable Ci , and x is one of X 's possible values x1 ; x2 ; : : : ; xk . Of course,
Vf (c1 ,c2,...,cn) = fx1 ; x2 ; : : : ; xk g should be declared in advance.

Herbrand universe of DB . Based on I , a(-n in nite-dimension) parameter space is de ned as follows:
Q
P
 def
= i2I fhi;v1 ; : : :; i;v Vi i j Vi = fv1 ; : : :; vjVij g; v2Vi i;v = 1g: (1)jj

We next de ne the probabilistic inconsistency (consistency), probabilistic
exclusiveness, and independency w.r.t. facts and goals.

De nition 2. Consider a PRISM program DB = F [ R and a set S of facts in
F (S  F ). S is said to be p-inconsistent if PF (S = 1j) = 0 for any parameters 2 .9 Otherwise, S is said to be p-consistent. Consider two sets S1 and S2
of facts in F , which are p-consistent. Then S1 is said to be p-exclusive to S2 if
S1 [ S2 is p-inconsistent. Furthermore, let B1 and B2 be arbitrary two atoms
in head (R). Then, B1 is said to be p-exclusive to B2 if and only if PDB (B1 =1;B2 = 1j) = 0 for any  2 .

De nition 3. For each B in head (R), let S (1) ; : : :; S (m) be minimal subsets ofF such thatcomp (R) j= B $ S (1) _    _ S (m) ;(2)where 0  m and comp (R) is the completion [5] of R.10 Then, each of S (1) ,. . . ,S(m) is referred
to as a minimal support set or an explanation for B . We put
DB (B ) = fS (1) ; : : :;S (m) g.

Together with a PRISM program DB = F [ R, we always consider a (denumerable) subset obs (DB ) of head (R), which is referred to as a set of observable
atoms. Each G 2 obs (DB ) is called a goal. Note that the following assumptions
are made only for practical reasons (e.g. program termination and eÆciency),
and that the distributional semantics itself does not require these assumptions.

Assumption 1. Consider a PRISM program DB . In Eq. 2, m is nite (m <1), and each of S (1) , . . . , S (m) is a nite set ( nite support condition). For
any G 2 obs (DB ), explanations in DB (G) are p-consistent and p-exclusive(exclusivenesscondition). Goals in obs (DB ) are p-exclusive to each another,P
and G2obs (DB ) PDB (G = 1j) = 1 holds for some parameter  2  (uniquenesscondition).

From the uniqueness condition, we know that just one atom in obs (DB )becomes true at each observation. Suppose we make T (< 1) independent observations, and Gt is the atom obtained at the t-th observation (Gt 2 obs (DB ),t = 1 : : :T ). Observed data G is a nite sequence hG1; G2; : : :; GT i. Then, I
def
isSTredeS ned here as a set of the group-ids of relevant switches to G , i.e. I =t=1 S 2 DB (Gt ) fi j 9n; v(msw(i,n,v) 2 S )g. Also, we rede ne  as the ( nitedimension) parameter space by Eq. 1.

S is a random vector whose elements are in S . 1 (resp. 0) is a vector consisting of
all 1s (resp. 0s). S = 1 means all atoms in S are true.
10
We sometimes consider a conjunction of atoms A1 ; A2 ; : : : as a set fA1 ; A2 ; : : :g.
9

4

Learning PRISM programs

Learning a PRISM program means maximum likelihood estimation (MLE) of theparameters in the program. That is, given observations G = hG1 ; : : :; GT i, wend the parameter  2  which (locally) maximizes the likelihood (Gj) def
=
QT
11
P
(
G
=
1
j

).
Althoughthe
PRISM
program
is
a
ected
by
the
beDB
t
t=1
havior, hence by the parameters  of switches msw(,,) it contains, we cannot
directly observe their behavior (i.e. these switches are \hidden"). Hence we apply
the EM algorithm [22]. The learning procedure comprises two phases:{ Find all explanations DB (Gt) for each goal Gt (t = 1 : : :T ).
{ Run the EM algorithm based on the statistics from DB (Gt) (t = 1 : : :T ).

In the rest of this section, we rst quickly derive a naive version of the EM
algorithm,12 assuming DB . We then introduce support graphs, a compact datastructure for DB . After the introduction of support graphs, the graphical EM
algorithm, an eÆcient EM algorithm working on support graphs, is described.

4.1 Naive approach

To derive an EM algorithm for PRISM, we must de ne a Q function. First, fromthe exclusiveness and the uniqueness condition, it is easily shown that explaS
nations in DB def= G2obs (DB ) DB (G) are all p-exclusive each other. Besides,
also from the uniqueness condition,
P
P
P
G2obs(DB ) PDB (G = 1j) = PG2obs (DB ) S 2 DB (G) PDB (S = 1j)= S 2DB PDB (S = 1j) = 1

holds for any  2 . Hence, exactly one of the explanations in DB is true.
Since DB is denumerable, we can consider an isomorphic map f : DB ! N + ,where N + is a set of positive integers, and temporarily introduce a new randomvariable E on F such that E = f (S ) if S 2 DB is exclusively true (S = 1),
or E = 0 otherwise. Now we are in a position to de ne the Q function:
P P
Q(0; ) def= Tt=1 e2N PDB (E = ejGt = 1; ) log PDB (E = e; Gt = 1j0); (3)where N is a set of non-negative integers. It is easy to show Q(0 ; )  Q(; ) )PDB (Gt = (0)1j0 )  PDB (Gt = 1j). Therefore, for MLE, starting with some parameters  , we iteratively update parameters by  (m+1) := argmax Q(;  (m) )11

Under the exclusiveness condition, each marginal probability of Gt being true isdef 
calculated as below. i;v (S ) is de ned as i;v (S ) = n msw(i,n,v) 2 S .

PDB (Gt =1j) =
12

P

P

j

S2 DB (Gt ) F (S = 1 ) =P

S2 DB (Gt)Qi;v (S)i2I;v2Vi i;v;

In [6], PRISM* programs are introduced to remove computationally intractableterms. We here present an alternative way to remove them.

until the log-likelihood log (Gj) converges. Transforming Eq. 3, the following
formula is obtained:


P
P

(i;v; )00P
Q( ; ) = i2I;v2Vi (i; v; ) log i;v  i;v (i; v; ) log
(i;v ;)v 0 2Vi

0;P
P
where (i; v;  ) def= Tt=1 PDB (G1t =1j) S 2 DB (Gt) PF (S = 1j)i;v (S ). Hence, wereach the procedure learn-naive in Fig. 1 that nds the MLE of the parameters. The array variable [i; v] contains (i; v;  ) under the current  . In thisprocedure, the calculations for PDB (Gt = 1j) and [i; v] (Line 2, 5 and 9) arecomputationally intractable when j DB (Gt)j is exponential (though nite) in
the complexity of the model.13

4.2 Tabulation approach

For eÆcient computation of PDB (Gt = 1j) and [i; v], we introduce structuresharing of explanations by tabulation, which requires more assumptions on DB .
We assume that a set of table predicates table (DB ) is declared in advance (like be a set of ground atoms containing
the HMM program in Sec. 3.1). Let DB
the table predicate in table (DB ). We use comp (R), the completion of rules R,
again in the following assumption.
Assumption 2. Let DB be a PRISM program which satis es the nite supportcondition, the exclusiveness condition, and the uniqueness condition. Assume
that, for each t = 1 : : :T , the following condition holds for some nite orderedt = f1t; : : :; Kt g of DB :14subset DBtcomp (R) j= Gt $ S~0t ;1 _    _ S~0t ;m0
(4)




^ 1t $ S~1t ;1 _    _ S~1t ;m1 ^    ^ Kt t $ S~Kt t ;1 _    _ S~Kt t ;mKt ;wheret 1; : : :; S~k;mt is a subset of F [ fkt+1 ; : : :; Kt g,{ Letting Gt be 0t , each of S~k;kt
15
and is also called a t-explanation for kt (for k = 0 : : :Kt ). We here put~DB (kt ) def= fS~k;1; : : :; S~kmk g (for k = 0 : : :Kt).
t (k = 0 : : :Kt) is a set of independent atoms.16{ Each of S~k;t 1 ; : : :; S~k;mkEach kt (k = 1 : : :Kt) is referred to as a table atom. We call the former condition
acyclic support condition, and the latter independent support condition.

For example, the complexity of the HMM depends on the number of states, thelength of input/output string or the number of output alphabets.
14t , : : :,From the nite support condition, for k = 0 : : : Kt, mk is nite and each of S~k;
1
t
t
t
~
~
~
Sk;mk is nite. Also, from the exclusive condition, Sk;1 ; : : : ; Sk;mk are p-consistenttand p-exclusive (k = 0 : : : Kt). Besides, from the uniqueness condition, Gt0 62 DBholds for any t; t0 = 1 : : : T .
15
Pre x \t-" is an abbreviation of \tabled-".
16
For B1 ; B2 2 head(R), B1 is independent of B2 if PDB (B1 = y1 ; B2 = y2 j) =PDB (B1 = y1 j)  PDB (B2 = y2 j) for any y1 ; y2 2 f0; 1g and any  2 .
13

1: procedure learn-naive (DB ; G ) beginP
2: Select some  from ; (0) := Tt=1 log PDB (Gt =1j);
3: repeat4:
foreach i 2 I; v 2 Vi doPP
5:[i; v] := Tt=1 PDB (G1t=1j ) S2 DB (Gt ) PF (S = 1j)i;v (S );6:foreach i 2 I; v 2 Vi doP
7:i;v := [i; v]= v0 2Vi [i; v0 ];8:
m := m P+ 1;
9:
(m) := Tt=1 log PDB (Gt =1j)
10: until (m) (m 1) < "11: end.
Fig. 1. A procedure for naive approach.

t from the source PRISM proThe task here is to construct such ~DB and DBgram. One way is to use OLDT (OLD with tabulation) [21], a complete searchtechnique for logic programs. In OLDT, a (sub-)goal g containing a table predicate is registered into a solution table, whereas the instance of g is registered ina lookup table. The latter reuses solutions in the solution table. In what follows,
we illustrate our tabulation approach by using the HMM program in Sec. 3.1.
First, we translate the PRISM program to another logic program. Similarly
to the translation of de nite clause grammars (DCGs) in Prolog, we add twoarguments (which forms D-list) to each predicate for collecting t-explanations.
In the case of the HMM program, the translation results in:(T1) top_hmm(Cs,X):- tab_hmm(Cs,X,[]).
(T3) tab_hmm(Cs,[hmm(Cs)|X],X):- hmm(Cs,_,[]).
(T3') tab_hmm(T,S,Cs,[hmm(T,S,Cs)|X],X):- hmm(T,S,Cs,_,[]).
(T4) e_msw(init,T,s0,[msw(init,T,s0)|X],X).
(T4') e_msw(init,T,s1,[msw(init,T,s1)|X],X).
:(T7) hmm(Cs,X0,X1):- e_msw(init,null,Si,X0,X2), tab_hmm(1,Si,Cs,X2,X1).
(T8) hmm(T,S,[C|Cs],X0,X1):T=<3, e_msw(out(S),T,C,X0,X2), e_msw(tr(S),T,NextS,X2,X3),
T1 is T+1, tab_hmm(T1,NextS,Cs,X3,X1).
(T9) hmm(T,S,[],X,X):- T>3.

Clauses (Tj ) and (Tj ') correspond to the original clause (j ), respectively. In
the translated program, p=(n + 2) is a table predicate if p=n is a table predicate
in the original program. We use the predicate tab_p=(n + 2) to keep the texplanations (in Eq. 4). Note that tab_p=(n + 2) is called instead of the tablepredicate p=(n + 2). We then apply OLDT search while noting (i) added D-list
does not in uence the original OLDT procedure, and (ii) we associate a list of
t-explanations with each solution. For example, running OLDT for the abovetranslated program gives the solution table in Fig. 2. Finally, we extract ~DB ,the set of all t-explanations, from this table. The remaining task is to get totallyt , respecting the acyclicity in Eq. 4.
ordered table atoms, i.e. the ordered set DB
Obviously, it can be done by topological sorting.

hmm([a,b,a]): [hmm([a,b,a]):[[m(init,null,s0),hmm(1,s0,[a,b,a])],[m(init,null,s1),hmm(1,s1,[a,b,a])]]]
hmm(1,s0,[a,b,a]):[hmm(1,s0,[a,b,a]):[[m(out(s0),1,a),m(tr(s0),1,s0),hmm(2,s0,[b,a])],[m(out(s0),1,a),m(tr(s0),1,s1),hmm(2,s1,[b,a])]]]
hmm(1,s1,[a,b,a]):[hmm(1,s1,[a,b,a]):[[m(out(s1),1,a),m(tr(s1),1,s0),hmm(2,s0,[b,a])],:[m(out(s1),1,a),m(tr(s1),1,s1),hmm(2,s1,[b,a])]]]
Fig. 2.

Solution table (m is an abbreviation of msw).

To help visualizing our learning algorithm, we introduce a data-structure
called support graphs, though the algorithm itself is de ned using only ~DBt . As illustrated in Fig 3 (a), the support graph forand the ordered set DB
Gt (t = 1 : : :T ), a graphical representation of Eq. 4, consists of disconnectedtsubgraphs, each of which is labeled with the corresponding table atom kt in DBt(k = 1 : : :Kt ). Each subgraph labeled k comprises two special nodes, the startnode and the end node, and explanation graphs, each of which corresponds tot in ~DB (kt ) (j = 1 : : :mk ). An explanation graph of S~k;jta t-explanation S~k;j
is cascaded nodes, where each node is labeled with a table atom  or a switch
t . It is called a table node or a switch node. Support graphs
msw(,,) in S~k;jhave a similar structure to recursive transition networks (RTNs). Fig 3 (b) is
the support graph for hmm([a,b,a]) obtained from the solution table in Fig 2.
Each table node labeled  refers to the subgraph labeled  , so data-sharing isachieved by the distinct table nodes referring to the same subgraph.

4.3 Graphical EM algorithm
We describe here a new learning algorithm, the graphical EM algorithm, thatt ). We prepare four
works on support graphs (more speci cally, on ~DB and DBarrays for each support graph for Gt (t = 1 : : :T ): P [t;  ] for inside probabilitiesof  , Q[t;  ] for outside probabilities of  , R[t; ; S~] for explanation probabilitiesof S~ in ~DB ( ), and [t; i; v] for expected counts of msw(i,,v). The algorithm is
explanation graph

Gt:
start

τ
msw

τ

msw

τ:

msw

end

hmm(1,s0,[a,b,a])m(init,null,s1)

hmm(1,s1,[a,b,a])

end

msw

hmm(1,s0,[a,b,a])::m(o(s0),1,a)m(tr(s0),1,s0)

hmm(2,s0,[b,a])m(o(s0),1,a)m(tr(s0),1,s1)

hmm(2,s1,[b,a])

start
end
msw

Fig. 3.

m(init,null,s0)

start

start

(a)

hmm([a,b,a]):

msw

:

end

msw

(b)

:

A support graph (a) in general form, (b) for the HMM program with Gt =hmm([a,b,a]). A double-circled node refers to a table node.

1: procedure learn-gEM (DB ; G )2: begin
3: Select some  from ;
4: get-inside-probs(DB ; G );P
5: (0) := Tt=1 log P [t;Gt ];6: repeat7:
get-expectations(DB ; G );1: procedure get-inside-probs (DB ; G )2: begin
3: for t := 1 to T do begin
4:
Put Gt = 0t ;5:
for k := Kt downto 0 do begin
6:
P [t;kt ] := 0;~ 2 ~DB (kt ) do begin
7:
foreach S
8:
Put S~ = fA1 ; A2 ; : : : ; AjS~j g;8:foreach i 2 I; v 2 Vi do
9:R[t;kt ; S~] := 1;9:[i; P
v] :=
~j do
T
10:
for ` := 1 to jS
10:
t=1 [t; i; v]=P [t;Gt ];11:
if A` = msw(i,,v ) then11:
foreach i 2 I; v 2 Vi do
12:
R[t;kt ; S~] = i;v
P
0
12:
i;v := [i; v]= v0 2Vi [i; v ]; 13:t ~] = P [t; A ];else R[t; k ; S
`
t
14:
P
[t;k ] += R[t;kt ; S~]
13:
get-inside-probs(DB ; G );
P
~ */
15:
end /* foreach S
14:
(m) := Tt=1 log P [t;Gt ]16:
end /* for k */15: until (m) (m 1) < "17: end /* for t */16: end.
18: end.
1: procedure get-expectations (DB ; G ) begin
2: for t := 1 to T do begin
3:
Put Gt = 0t ; Q[t; 0t ] := 1; for k := 1 to Kt do Q[t; kt ] := 0;
4:
for k := 0 to Kt do~ 2 ~DB (kt ) do begin
5:
foreach S
6:
Put S~ = fA1 ; A2 ; : : : ; AjS~j g;~j do
7:for ` := 1 to jS
t
t ~]
8:
if A` = msw(i,,v ) then  [t; i; v ] += Q[t; k ]  R[t;k ; Stt~
9:else Q[t; A` ] += Q[t; k ]  R[t; k ; S ]=P [t; A` ]~ */10:
end /* foreach S
11: end /* for t */12: end.
Fig. 4.

Graphical EM algorithm.

shown in Fig. 4. Due to the space limitation, details are omitted. It can be shownhowever that learn-gEM is equivalent to the procedure learn-naive (Sec. 4.1).17
As shown in Sec. 4.1, learn-naive is the MLE procedure, hence the following
theorem holds.

Theorem 1. Let DB be a PRISM program, and G be the observed data. Then
learn-gEM nds   2  which (locally) maximizes the likelihood (Gj).
17

To be more speci c, under the same parameters , the value of [i; v] in learn-naive(Line 5) is equal to that in learn-gEM (Line 10). Hence, the parameters are updated to the same value. Furthermore, starting with the same initial parameters,
the converged parameters are also the same.

Td?-q(1,d,L)
2=<j=<N

2 =< k =< N

2 =< k =< N?-q(1,d,d+1), ?-q(1,d,d+1), ?-q(j,d,d+1),q(1,d+1,L)q(1,d+1,L)q(1,d+1,L)?-q(j,d,d+1),q(k,d+1,L)?-q(1,d+1,L) ?-q(1,d+1,L)?-q(1,d+1,L)?-q(1,d+1,L)q(i,d’,d’’) already appears
d+1=<d’<d’’=< L, 1=<i=<N

Td+1[Note] qq

1 =< i =< N

1 =< j =< N
d+2 =< e =< L-1

2 =< k =< N?-q(j,d,e),q(1,e,L)?-q(j,d,e),q(k,e,L)

1 =< i’ =< N,
1 =< j’ =< N,
d+2 =< e’ < e?-q(i’,d,e’),q(j’,e’,e),q(1,e,L)Td’?-q(k,e,L)?-q(j’,e’,e),q(1,e,L)?-q(1,e,L)

...
p(i)

p(1) p(2) p(N)Fig. 5.

5

an OLDT tree Td for the query ?-q(1,d,L).

Complexity

In this section, we estimate the time complexity of our learning method in case of
PRISM programs for PCFGs, and compare with the Inside-Outside algorithm.
Since our method comprises two phases (OLDT and the graphical EM), we
estimate the computation time in each phase.
In the Inside-Outside algorithm, time complexity is measured by N , thenumber of non-terminals, and L, the number of terminals in the input/output
sentence. Assuming that the target grammar is in Chomsky normal form, theworst-case time complexity is the computation time for the largest grammar, i.e.
a set of all combinations of terminals and non-terminals. Hence, we may startwith a logic program (not a PRISMprogram) representing the largest grammar:q(i,d,d0):- q(j ,d,d00),q(k,d00,d0) i; j; k = 1 : : :N; 0  d < d00 < d0  L[ q(i,d,d0) i = 1 : : :N; 0  d  L 1; d0 = d + 1 :(5)q(i,d,d0) says that the i-th non-terminal spans from (d + 1)-th word to d0-th
word. The textual order over the clauses \q(i,d,d0):- q(j ,d,d00),q(k,d00,d0)"

is the lexicographic order over the tuples (i; j; k; d; d0; d00). We then make an
exhaustive search for the query by OLDT. Assuming that the solution table
is accessible in O(1) time, the time complexity of OLDT is measured by the
number of nodes in OLDT tree (the search tree for OLDT). We x the searchstrategy to multi-stage depth- rst strategy [21]. Let Td be an OLDT tree for thequery ?-q(1,d,L). Fig. 5 illustrates the case of 0  d  L 3. As can beseen, even for this simple grammar, the tree has many similar subtrees, so weput them together (see [Note] in Fig. 5). Then, due to the depth- rst strategy,

Td has a recursive structure, i.e. Td is a part of Td . We enumerate hd, thenumber of the nodes in Td but not in Td . The node with an underlined leftmost
atom is a lookup node, which only consumes the solution obtained in otherplace. From Fig. 5, hd = O(N (L d) ). Total time for OLDT search is thenumber of nodes in the OLDT tree for ?-q(1,0,L) (the whole sentence), that is,PL
d hd = O(N L ). In the case of a DCG program below, it can be proved
similarly that the time complexity is O(N L ).
q(i,L0,L1):- q(j ,L0,L2),q(k,L2,L1) i; j; k = 1 : : :N
[ q(i,L0,L1):- L0=[w|L1] i = 1 : : :N; w is a terminal symbol
+1

+1

3

3
=0

3

3

2

18

19

3

3

Since our method respects the original OLDT procedure, the search time for thecorresponding PRISM program given T observed goals is O(N 3 L3 T ).
On the other hand, the learning time of the graphical EM algorithm is propotional to the size of the support graphs used, i.e. the number of nodes in thegraphs. It is easily shown, from the description of learn-gEM, that the size ofthe graphs is O(num maxsize T ), where num def= max1tT j~tDB j, maxsize def
=
S
def
t
~
~
~
max1tT;S~2~tDB jS j, and DB =  2DBt
DB ( ). In the case of the PCFG pro3 3
gram, num = O(N L ) and maxsize = O(1). Hence, the computation time per
update of the graphical EM algorithm is O(N 3L3 T ). We therefore have:

Proposition 1. Let DB be a PRISM program representing a PCFG, and G =hG1; G2; : : :; GT i be the observed data. We assume each table operation in OLDT
search is done in time O(1). Then OLDT search for the goal Gt and each iteration in learn-gEM is done in time O(N 3L3 T ).

O(N 3L3T ) is also the time complexity of the Inside-Outside algorithm, hence
our algorithm is as eÆcient as the Inside-Outside algorithm.20 Similarly, we canshow that, for HMM programs like ones in Sec. 3.1, the search and the learning
time is O(N^ 2LT ), the same order as that of the Baum-Welch algorithm (N^ isthe number of states).
6

Conclusion

We have proposed an eÆcient EM learning algorithm for the parameterized logic
programs which seamlessly uni es logical semantics and probabilistic semantics.
It is shown our general algorithm works as eÆciently as the specialized EM algorithms such as the Baum-Welch algorithm and the Inside-Outside algorithm.
18
We here focus on the subtree Td0 . Each of j , i0 , j 0 ranges from 1 to N , andf(e; e0 ) j d + 2  e0 < e  L 1 g = O((L d)2 ). Hence, the number of nodes in
Td0 is O(N 3 (L d)2 ). The number of nodes in Td but neither in Td+1 nor in Td0 is
negligible, therefore hd = O(N 3 (L d)2 ).
The number of nodes of TL 1 and TL 2 is negligible.
20
Ours can be better than the Inside-Outside algorithm as only relevant grammar rules
are involved in the EM learning phase as is observed experimentally.
19

Furthermore, due to the generality of the language and the learning algorithm,
our framework can be applied to the stochastic grammars with context dependencies such as the bigram model of production rules [7], in which case the timecomplexity of the EM learning is polynomial (details are omitted). The omitted
details in this paper will be included in the full paper we are preparing.

References
1. Baker, J. K., Trainable grammars for speech recognition, Proc. of Spring Conf. of
the Acoustical Society of America, pp.547{550, 1979.
2. Breese, J. S., Construction of belief and decision networks, Computational Intelligence, Vol.8, No.4, pp.624{647, 1992.
3. Cussens, J., Loglinear models for rst-order probabilistic reasoning, Proc. of
UAI'99, pp.126{133, 1999.
4. Dekhtyar, A. and Subrahmanian, V. S., Hybrid probabilistic programs, Proc. of
ICLP'97, pp.391{405, 1997.
5. Doets, K., From Logic to Logic Programming, The MIT Press, 1994.
6. Kameya, Y., Ueda, N. and Sato, T., A graphical method for parameter learning ofsymbolic-statistical models, Proc. of DS'99, LNAI 1721, pp.264{276, 1999.
7. Kita, K., Morimoto, T., Ohkura, K., Sagayama, S. and Yano, Y., Spoken sentence
recognition based on HMM-LR with hybrid language modeling, IEICE Trans. on
Information & Systems, Vol.E77-D, No.2, 1994.
8. Koller, D. and Pfe er, A., Learning probabilities for noisy rst-order rules, Proc.
of IJCAI'97, pp.1316{1321, 1997.
9. Koller, D., McAllester, D. and Pfe er, A., E ective Bayesian Inference for Stochastic Programs, Proc. of AAAI'97, pp.740{747, 1997.
10. Lakshmanan, L. V. S. and Sadri, F., Probabilistic deductive databases, Proc. of
ILPS'94, pp.254{268, 1994.
11. Manning, C. D. and Schutze, H., Foundations of Statistical Natural Language Processing, The MIT Press, 1999.
12. Muggleton, S., Stochastic logic programs, In Advances in Inductive Logic Programming (Raedt,L.De ed.), OSP Press, pp.254{264, 1996.
13. Ng, R. and Subrahmanian, V. S., Probabilistic logic programming, Information
and Computation, Vol.101, pp.150{201, 1992.
14. Ngo, L. and Haddawy, P., Answering queries from context-sensitive probabilisticknowledge bases, Theoretical Computer Science, Vol.171, pp.147{177, 1997.
15. Nilsson, N. J., Probabilistic logic, Arti cial Intelligence, Vol.28, pp.71{87, 1986.
16. Pearl, J., Probabilistic Reasoning in Intelligent Systems, Morgan Kaufmann, 1988.
17. Poole, D., Probabilistic Horn abduction and Bayesian networks, Arti cial Intelligence, Vol.64, pp.81{129, 1993.
18. Rabiner, L. and Juang, B., Foundations of Speech Recognition, Prentice-Hall, 1993.
19. Sato, T., A statistical learning method for logic programs with distribution semantics, Proc. of ICLP'95, pp.715-729, 1995.
20. Sato, T. and Kameya, Y., PRISM: a language for symbolic-statistical modeling,
Proc. of IJCAI'97, pp.1330{1335, 1997.
21. Tamaki, H. and Sato, T., OLD resolution with tabulation, Proc. of ICLP'86, LNCS
225, pp.84{98, 1986.
22. Tanner, M., Tools for Statistical Inference (2nd ed.), Springer-Verlag, 1986.
23. Wetherell, C.S., Probabilistic languages: a review and some open questions, Computing Surveys, Vol.12, No.4, pp.361{379, 1980.