A Viterbi-like algorithm and EM learning for statistical abduction

Taisuke SATO

Yoshitaka KAMEYA

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
sato@mi.cs.titech.ac.jp

Abstract

Introduction

Abduction is a form of inference that generates best
hypotheses explaining an observed fact. For example,
if one notices a fact that the grass is wet in the yard,
he/she might abduce that it rained last night, or thesprinkler was on, by using general rules such as \if itrains, things get wet." Abduction has been used for
diagnosis systems, planning, natural language processing, etc in AI.
It is straightforward to formalize (part of) abductionin the logic programming framework [6, 9]. 1We havea background theory T consisting of clauses
and anobserved fact G (usually a ground atom2 ) to be explained, and the task of abduction is to generate ahypothesis H = h1; . . . ; hn , i.e. an explanation, bychoosing his from a particular
set of hypothesis candidates called abducibles,3 such that T H G andfis consistent.4 The quality of H , the abduced
hypothesis, is evaluated by various criteia such as simplicity, abduction cost, and so on [9, 8, 18].
While the above framework is logically sound, it is obviously incomplete. Especially it entirely ignores the
problem of uncertainty in the real world. Our observations are often partial, inconsistent or contaminatedby noise. So the abduced hypothesis should be treatedas being true only to some degree. Also it must be
noticed that our obsevations are always nite but potentially in nite (we may have another observation inde nitely), and we would like to know the eventual
outcome of in nitely many observations. It is therefore natural, even desirable, to build a new abductive
framework that uni es the logical framework with astatistical framework such as Bayesian networks.
This amalgamation is made possible by introducing
probabilistic elements into logic programs. More exactly, it is made possible by introducing a (parameterized) probability distribution over abducibles, whichenables us to identify the best hypothesis as the most
likely hypothesis and the likelihood can be maximized
by statistical learning. The resulting logical-statisticalsystem will bene t both abductive logic programmingand Bayesian networks, as the former is expected to
become robust against noise and missing data and thelatter gets rst-order expressiveness as knowledge representation language. We term this uni cation statistical abduction.
There are however theoretical and practical problems
to achieve the uni cation. First of all, statistical abduction must deal with in nitely many objects sanctioned by the language of rst-order logic and theirjoint distribution, which gives rise to a theoreticalproblem of constructing an in nite joint distributionof structured objects. It requires to extend the realmof traditional Bayesian networks considerably.
Secondly, to use statistical abduction in practice, weneed to know all values of statistical parameters justT [HWe propose statistical abduction as a rstorder logical framework for representing andlearning probabilistic knowledge. It combines logical abduction with a parameterized distribution over abducibles. We showthat probability computation, a Viterbilike algorithm and EM learning for statistical abduction achieve the same eÆciency
as specilzed algorithms for HMMs (hidden Markov models), PCFGs (probabilistic
context-free grammars) and sc-BNs (singlyconnetcted Bayesian networks).
1

kame@mi.cs.titech.ac.jp

g

[

`

1
Syntactically, a clause (in implicative form) is a logicalformula L0 L1 ^ . . . ^ Lm (m  0) where Li (0  i  m)is an atom or its negation, and all variables are universallyquanti ed at the outermost position. L0 is called a head
and L1 ^ . . . ^ Lm the body. A de nite clause is one suchthat every Li is an atom. Note that we adopt Prolog conventions in this paper, so a conjunction A ^ B is expressedas (A; B ), and variables begin with an upper case letter.
2
A ground atom is one that contains no variables.
3
Usually abducibles are ground atoms.

4
Induction also has similar formalization, and the distinction between induction and abduction is a subtle issue[7].

like conditional probabilities for Bayesian networks.
Determining a large number of statistical parameters
is a tough task, known as the where-do-the-numberscome-from problem. Although one might hope thatthe problem is mitigated by using learning techniques,
there has been little work on statistical learning in theliterature of logical framework of abduction.
The objective of this paper is to point out that we have
now a thereoretical foundation for statistical abduction, an eÆcient algorithm for computing probabilities,an eÆcient EM algorithm for parameter learning, andnally a Viterbi-like algorithm that generates the most
likely hypothesis. Since the subject is broad and thespace is limited, descriptions are necessarily sketchy,
and proofs and details are left to a full paper we arepreparing. Also, we assume that the reader is familiar
with the basics of logic programming [6].
In what follows, after a short review of backgroundin Sec. 2, we explain PRISM programs in Sec. 3.
Sec. 4 contains the description of eÆcient computation of probabilities, OLDT search, EM learning and a Viterbi-like algorithm, followed by thecomplexity analysis of PRISM programs for HMMs,
PCFGs (probabilistic context-free grammars) and scBNs (singly-connected Bayesian networks). Sec. 5 is aconclusion.
2

BackgroundThe use of rst-order clauses in relation to Bayesian
networks has been pursued in the past decade in two
strands. In the KBMC (knowledge-based model construction) approach [3, 1, 11, 14], initiated by Breesein [3], they are used as a macro language to compactly represent similar Bayesian networks. Basicallya knowledge base KB contains clauses representing
general rules and CPTs (conditional probability tables). Each time a set of evidence and context is
given as ground atoms, a specialized Bayesian network
is constructed by tracing logical/probabilistic dependencies in KB to compute the probability of a queryatom. Uncertain parameters associated with CPTs
can be learned by applying the EM learning algorithm
for Bayesian networks [4] to the constructed network[11]. The KBMC approach is characterized as a local
approach, implicitly de ning a set of local distributions as Bayesian networks, each of which corresponds
to a query, evidence and context.
Statistical abduction on the other hand takes a global
approach which de nes a single distribution overground atoms. It was began by Poole as \probabilistic Horn abduction" [15]. In his approach, a program
contains non-probabilistic de nite clauses and probabilistic disjoint declarations. A disjoint declaration isof the form disjoint([h1:p1,. . . ,hn:pn]). It says
hi , an abducible atom, becomes exclusively true withprobability pi (0 i n). Abducibles in di rent declarations are supposed to be independent. The probability of a non-abducible ground atom is then calculated by reduction in a top-down manner throughprogram clauses to a DNF formula made out of abducibles in the disjoint declarations. The probabilistic
Horn abduction not only de nes probabilities of atoms
without referring to Bayesian networks but can represent Bayesian networks themselves [15].
While the probabilistic Horn abduction opened a newvista on extending Bayesian networks to rst-orderlanguage, it left behind some problems.5 First it assumed a priori6 the acyclicity condition and the covering property of programs. These assumptions are
hard to verify
and could be severe restrictions in programming.7 Also the de ned probability measure is
not guaranteed to be completely additive. As a result, for instance, limn!1 Prob(p(t1) . . . p(tn)) =Prob( Xp(X )) where the tis are ground terms, is notguaranteed. More serious is the problem of determining parameters in disjoint declarations. How can we
get them? It remained unanswered.
Aiming at providing a broader theoretical basis anda learning algorithm of uncertain parameters for the
global approach, Sato proposed distribution semantics[19] and developed
a rst-order statistical modelinglanguage PRISM8 [19, 20]. The proposed semantics
de nes an in nite joint distribution over ground atoms
as the denotation of a given program containing abducibles with statistical parameters declared just likethose in Poole's disjoint declarations. It is a probabilistic extension of the least Herbrand model semantics
for de nite clause programs [6] to the possible world
semantics with a completely additive probability measure. Since our extension is based on the least Herbrand model semantics, we don't need the covering
assumption or the acyclicity condition (because every de nite program has a least Herbrand model andthe i completion [6] holds in it.). Similarly, neither
the range-restrictedness condition nor normalization isnecessary in our approach, which is required in prooftheoretic approaches to assigning probabilities to logic
programs [5, 13].
__

9

It says that every ground atom A must be assigned aunique integer n(A) such that n(A) > n(B1 ); . . . ; n(Bn )for every ground instance of a clause of the form A
B1 ; . . . ; Bn .
6
It requires that when there are nite ground instnacesAi (1  i  m) about a ground atom A in the program, A , 1 _ . . . _ m holds. The case of in nitely manyground instances is not mentioned. Intuitively the property
ensures every observation has an explanation. Logically it
is equivalent to assuming the i completion [6].
7Under the acyclicity condition, when a clause includes local variables like Y in p(X )q(X; Y ); . . .
we cannot write recursive clauses about q such as
member(X; cons(H;Y )) member(X;Y ). Also it is notclear how to check the covering property, as it speci es therelationship between what is potentially observable (which
depends on nature) and what we can explain (which depends on the program).
8
URL is http://sato-www.cs.titech.ac.jp/prism/
5

Theoretically, we may use as many constant symbols,
function symbols and predicate symbols as we need,and can write whatever program. Of course, in actual programming, we have to care about eÆciency,
termination, etc.
Syntacticaly, our program DB is a set of clauses F R
where F is a set of unit clauses and R is a set of definite clauses. For the purpose of theoretical explanation however, we consider DB as a set of in nitely
many ground clauses made up of all possible groundinstances of original clauses in DB. F then is a setof in nitely many ground atoms. We associate withF an in nite joint distribution PF . So atoms in F
are probabilistically true and 0random sampling determines a set of true atoms F0 . Then
think of a newde nite clause program0 DB = F 0 0 R and its least
Herbrand model M (DB ) [6]. M (DB ) determines thetruth values of all ground atoms in DB, which implies
that every ground atom A is a random variable (taking
1 when A true and 0 otherwise), and therefore a joint
distribution PDB for all ground atoms is de nable. PF
is constructedfrom a collection of nite joint distrituions PF(n)(A1 = x1; . . . ; An = xn) (n = 1; 2; . . .) where
Ai s are random variables (abducibles). The resulting
PDB becomes a -additive probability measure over0; 1 ! (the set of all countably in nite sequences of 0
and 1).
For statistical abduction to be useful however, we needeÆcient methods forcomputing the probabilities of observations,computing the most likely explanation for the
given observation, andlearning parameters
As for HMMs, these methods correspond to the forward procedure, the Viterbi algorithm, and the BaumWelch algorithm respectively [17].
PRISM, an implementation of the statistical abduction with PF being constrained to a speci c form, hasbeen developed as a modeling language designed forcomplex symbolic statistical phenomena [19, 20]. It
comes with a built-in EM algorithm9 for parameter
learning, but still lacks eÆciency compared to HMMs.
In what follows, we show that there exist algorithms
for PRISM programs that run as eÆciently as specialized ones when they are applied to HMMs, PCFGs andsc-BNs.
[

[

f

g






3

PRISM programs

A PRISM program is de ned as a de nite clause program DB = F R which satis es the following conditions on facts F , their distribution PF and rules R.
[

The EM algorithm is a standard statistical method forMLE (maximum likelihood estimation) [23].
91. F is a set of ground atoms of the form
msw(i,n,v). The arguments i and n are calledgroup-id (or switch name) and trial-id, respectively. We assume that a nite set Vi of groundterms 10is associated with each i, and v Vi
holds. Vi corresponds to a set of values of switchi.
2. Let Vi be v1; v2; . . . ; vjV j . Then, one of theground atoms msw(i,n,v1), msw(i,n,v2), ...,
msw(i,n,vjV j ) becomes exclusively true (takes
the value 1) on each trial. For each i, i;v [0; 1]
is a parameter of the probabilityof msw(i, ,v)
being true (v Vi), and Pv2V i;v = 1 holds.
3. For each ground terms i, i0, n, n0, v Vi and v0
Vi , random variable msw(i,n,v) is independentof msw(i0,n0,v0) if n = n0 or i = i0.
4. De ne head (R) as a set of atoms appearing in thehead of R. Then, F head (R) = .
msw=3 in the rst condition is 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." The second and the third
condition say that a logical variable V in msw(i,n,V)behaves similarly to a random variable which is re-11
alized to vk with probability i;v (k = 1 ... Vi ).
Moreover, from the third condition, the logical variables V1 and V2 in msw(i,n1,V1) and msw(i,n2,V2)
can be seen as independent and identically distributed(i.i.d.) random variables if n1 and n2 are di erent
ground terms. From an abductive point of view, msws
are all abducibles, and the fourth condition requiresthat no msw appears in the heads of R.
As an example of representing temporal processes inan abductive framework, we describe an HMM as a
PRISM program. It looks like a usual Prolog program, but denotes a discrete stochastic process (of nite length, 3 in this case).
2

f

i

g

i

2



2

i

2

2

0

6

6

\

;

j

k

j

1) target(hmm/1).
4) values(init,[s0,s1]).
2) data('hmm.dat').
5) values(out(_),[a,b]).
3) table([hmm/1,hmm/3]). 6) values(tr(_),[s0,s1]).
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.

Procedurally, the above HMM program simulates thegeneration process of strings. Clauses 7 9 represent the probabilistic behavior of the HMM. In clause
8, to output a symbol C, we use di erent switches10
We consider DB as a countably in nite set of groundclauses, and i and n are arbitrary ground terms in the
Herbrand universe.
11
Recall however that, in distribution semantics, logicalvariables themselves are not random variables.

out(S) conditioned on the state S.12 Note that T
in msw(out(S),T,C) is used to guarantee indepen-dency among the choices at each time step. Recursive
clauses like 8 are allowed in PRISM. Clauses 1 6 contain additional information about the program (theyare called control declarations). Clause 1 declares13
only 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 = s0; s1 , Vout( ) = a; b , Vtr( ) = s0; s1
from clauses 4 6.


f

g



f

g

f



g



4

To apply statistical abduction to the real world, we
consider, based on the analogy of HMMs [17], threebasic tasks: (1) computing PDB (G =1 ~),14 the probability ofan atom G representing an observation, (2)nding S , the most likely explanation for G, and (3)adjusting the parameters to maximize the probability of a given sequence = G1; G2; . . . ; GT of observations. All solutions should be computationallytractable.
Poole [15] described a method for the rst task. Let us
consider the following if-and-only-if (i ) relation undercomp (R), the Clark's completion of the rules R [6]:comp (R) = G S (1)S (m) :(1)(j)
He assumes that all abducibles in S (a nite conjunction of abducibles) are independent andS (1) ; . . . ; S (m) are exclusive to each other (we say
DB satis es the exclusiveness condition).
Let
DB (G)15 be S (1) ; ; S (m) and i;v (S ) the numberof msw(i, ,v)s occurring in S. His method for solving
the rst task is formulated in our notation as follows:
PS2 (G) Qi2I;v2V i;v (S):PDB (G =1 ~) =A little modi cation of the above formula would give
one for the second task: Q
 (S )
S  = argmaxS 2 (G) i2I;v2V i;v:
Unfortunately, (G) , the number of explanations forG, often grows exponentially in the complexity of themodel (e.g. the number of states in an HMM), or in thecomplexity of each observation (e.g. the string length).
j

G

f

h

$



i

__

g



i;v

j

i

i;v

i

j

OLDT search for factorized explanations

In order to derive eÆcient algorithms for the threetasks, comparable to the forward procedure and theViterbi algorithm, we need to add a couple of assumptions about programs. We assume that DB satis es
the exclusiveness condition, and that m is nite in
Eq. 116(we say DB satis es the nite support condition).
Furthermore, we assume that the following
i -relational formula holds for some nite ordered set
DB (G) = 1; . . . ; K of table atoms (atoms containing the table predicate17 ):comp (R) = (G S0;1
S0;m0 )
(2)
(1 S1;1
S1;m1 )
(K SK;1
SK;m );
where, letting G be a special table atom 0, eachin ~DB (k) def= Sk;1; . . . ; Sk;m (1 k K ) is asubset of F k+1; . . . ; K called a factorized-(ortabled-)explanation for k , and each of Sk;1; ... ; Sk;m(0 k K ) is a set of independent atoms.
~DB (k) and DB (G) can be obtained by OLDT
search18[22], a complete refutation technique with tabulation for logic programs. We rst translate thesource PRISM program to Prolog similarly to de niteclause grammars (DCGs) [21], or Poole's Theorist [16].
The following Prolog program is a translation of the
HMM program in Sec. 3. Clauses Tj and Tj' are generated from the clause j:
f

g

j

$

^

Three basic tasks

j

4.1

j

12
Generally, a CPT of a random variable X is representable as a switch msw(fX (c1,c2 ,. . . ,cn),,x), where
fX is the id of X , n is the number of conditional variables,ci (i = 1; . . . ; n) is the value of each conditional variable
Ci , and x is the value of X . Of course, X 's possible values
should be declared in advance like Clause 46.
13
This is just for the ease of implementation.
14 ~ is the vector consisting of parameters associated withall abducibles which forms the explanations for the observed fact G or an observation in G .
15
For simplicity, we hereafter omit the subscript DB(Similar abbreviation may occur later).

$

^^

__

__

t $

f

[ f

kg

__



K



g

k





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.

As can be seen, in translation, we add two arguments
to collect factorized explanations and rename the predicates of abducibles (msws) and table atoms. We thenperform OLDT search, noting extra arguments do notin uence the search procedure, while saving in the solution table a list of factorized explanations every time
16
This condition says that every observation has a nite
number of explanations. Without it, our search for explanations would not terminate.
17
Table predicates are assumed to be declared by the
programmer in advance, like Clause 3 in the HMM program.
18
OLDT stands for Ordered Linear resolution for De nite clauses with Tabulation.

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

Figure 1: Solution table for the observation hmm([a,b,a]).
the table atom is solved. For example, the OLDT
search for the above translation yields Fig. 1. Finally,
we extract ~, the set of all factorized explanations fromthe solution table. The remaining task is to get totallyordered table atoms, i.e. the ordered set DB (G), respecting the acyclicity in Eq. 2, which can be done by
topological sorting.
4.2

Computing the observation probability
and the most likely explanation

Given the i -relational formula in Eq. 2, an eÆcientalgorithm for computing PDB (G =1 ~) (the rst task)
is derivable based on the analogy of the inside probabilities in Baker's Inside-Outside algorithm [2]. In ourformulation however, the inside probability of a table
atom  is PDB ( =1 ~), the probability of  being true.
It should be noted that, when computing [k], theinside probabilities [K ]; [K 1]; . . . ; [k+1] havebeen already computed. The computation terminateswith [G](= [0]), the inside probability of G.
j

j

P

P

P

P

P

P

procedure Get-Inside-Probs (DB ; G) begin
Put G = 0 ;for k := K downto 0 do
P [k ] :=

P

end.

S 2 ~(k )Q

msw(i,,v )2S

i;v

Q

]

 2S \fk+1 ;...;K g P [Similarly, an eÆcient algorithm
for computing themost likely explanation S (i.e. the second task) is derived. The algorithm Get-ML-Expl rst computes
Æ [k ], the maximum probability of factorized explanations for each table atom k. [k], the most likely factorized explanation
for k , is then constructed. Finally,
we construct S from [ ]. For an HMM program (seeSec. 3), Get-ML-Expl is equivalent to the Viterbi
algorithm, a standard algorithm for nding the most
likely state-transition path of HMMs. Furthermore,when we write a probabilistic context-free grammar(PCFG) in PRISM, it is easily shown that probabilistic parsers for PCFGs, which nds most likely parseof a given sentence, are equivalent to Get-ML-Expl.
EE 

1: procedure Get-ML-Expl(DB ; G) begin
2: Put G = 0 ;3: for k := K downto 0 do begin
4:
foreach S 2 ~(k ) do

Q

Q

5:
Æ0 [k ; S ] :=6:
msw(i,,v )2S i;v
 2S \fk+1 ;...;K g Æ [ ];7:
Æ[k ] := maxS2 ~(k ) Æ0 [k ; S ];08:
E [k ] := arg max S 2 ~( ) Æ [k ; S ]k
9: end;10: s := fGg; S  := ;;11: while s 6= ; do begin
12:
Select and remove A from s;
13:
if A = msw(,,) then add A to S 
14:else s := s [ E [A]
15: end
16: end
4.3

Learning algorithm

The learning of PRISM programs means MLE (maximum likelihood estimation) of statistical parametersof msws embedded in a program, for which the EM
algorithm is appropriate [23]. A new EM algorithm
named graphical EM algorithm that takes advantage ofthe structure of the i -relational formula in Eq. 2 hasbeen derived on the analogy of computation of the outside probabilities in the Inside-Outside algorithm [10].
We added an assumption that all observable atoms are
exclusive to each other and the probabilities of theseatoms sum up to one (we say DB satis es the uniqueness condition).
The graphical EM algorithm rst initializes the parameters ~ and then iterates re-estimation until thelikelihood saturates. In each iteration, the expectedoccurrence is computed rst for each abducible atom
msw(i,n,v) from its parameter i;v , the inside probabilities and the outside probabilities, and then allparameters are simultaneously re-estimated by using
such expected occurrences. Final values of parameters
become learned ones.
4.4

Complexity

In this section, we primarily evaluate time complexity of our methods for the rst and the second task due to space limitations. The method
for the rst (resp. the second) task comprises
two phases | OLDT search and Get-Inside-Probs(resp. Get-ML-Expl). Hence, we should estimate
each algorithm separately. Assuming that all table operations can be performed in O(1) time, thecomputation time of OLDT search is measured by

the size of the search tree. As for the computation
time of Get-Inside-Probs and Get-ML-Expl, it
is O(num maxsize),19 whereSnum def=  , maxsize def=
def~
maxS2 S , and  =  2DB DB ( ). In thecase of the HMM program, num = O(N 2L) andmaxsize = O(1). Hence, the computation time of
Get-Inside-Probs and Get-ML-Expl is O (N 2 L).
This is the same order as that of the forward procedureand the Viterbi algorithm. So Get-ML-Expl (resp.
Get-Inside-Probs) is a generalization of the Viterbi
algorithm (resp. the forward procedure). For existing
symbolic-statistical models,
we summarize computation time as follows:20
j

j

j

j

Model
HMMs
sc-BNsPCFGs

OLDT timeO(N 2 L)
O(jV j)O(M 3 L3 )GIP/GMLE timeO(N 2 L)
O(jV j)O(M 3 L3 )The second (resp. the third) column\OLDT
time" (resp. \GIP/GMLE time") indicates thatthe computation time of OLDT search (resp.
Get-Inside-Probs and Get-ML-Expl) for themodel in the rst column. N , L, T , V and M are
the number of states of the target HMM, the maximum length of input strings, the size of training data,
the number of nodes in the target Bayesian network,and the number of non-terminal symbols in the target PCFG, respectively. The above table exempli es
that our general framework can subsume speci c algorithms such as the Viterbi algorithm.
j5jConclusion

We have proposed statistical abduction as the combination of abductive logic programming with a distribution over abducibles. It has rst-order expressive power and integrates current most powerful probabilistic knowledge representation frameworks such as
HMMs, PCFGs and Bayesian networks. Besides, ourgeneral algorithms developed for the three tasks (probability computation, the search for the most likely
explanation, and EM learning) achieve the same eÆciency as specialized algorithms for above three frameworks.
Acknowledgments

This research is supported by Grant-in-Aid for Scienti c Research on Priority Area \Discovery Science"
19
By the way, our method for the third task (EM learning) comprises OLDT search and the graphical EM algorithm whose computation is measured by the re-estimation
time (since we do not know the number of re-estimations inadvance). It is shown, analogously to Get-Inside-Probs
and Get-ML-Expl, to be O(nummaxsizeT ).
20
In PCFGs, we assume grammars are in Chomsky normal form, and in sc-BNs, we assume the maximum numberof parent nodes are xed.

1999 of the Ministry of Education, Science, Sports andCulture, Japan.
References[1] Bacchus, F. Using rst-order probability logic for theconstruction of Bayesian networks. Proc. of UAI'93,
1993.
[2] Baker, J. K. Trainable grammars for speech recognition. Proc. of Spring Conference of the AcousticalSociety of America, 1979.
[3] Breese, J. S. Construction of belief and decision networks. Comput. Intell., 8(4), 1992.
[4] Castillo, E., Gutierrez, J. M., and Hadi, A. S. Expert
Systems and Probabilistic Network Models. SpringerVerlag, 1997.
[5] Cussens, J. Loglinear models for rst-order probabilistic reasoning. Proc. of UAI'99, 1999.
[6] Doets, K. From Logic to Logic Programming. The MIT
Press, Cambridge, 1994.
[7] Flach, P. and Kakas, A. (eds). Abduction and Induction { essays on their relation and integration {.
Kluwer Academic Publishers, 2000.
[8] Hobbs, J. R., Stickel, M. E., Appelt, D. E. and Martin,
P. Interpretation as abduction. Artif. Intell., 63, 1993.
[9] Kakas, A. C., Kowalski, R. A. and Toni, F. Abductive
logic programming. J. Logic Comput., 2(6), 1992.
[10] Kameya, Y. and Sato, T., EÆcient EM learning withtabulation for parameterized logic programs, to bepresented at the 1st Conf. on Computational Logic(CL2000), 2000.
[11] Koller, D. and Pfe er, A. Learning probabilities fornoisy rst-order rules. Proc. of IJCAI'97, 1997.
[12] Manning, C. D. and Schutze, H., Foundations of Statistical Natural Language Processing, The MIT Press,
1999.
[13] Muggleton, S. Stochastic logic programs. In Advancesin Inductive Logic Programming (Raedt, L. De ed.),OSP Press, 1996.
[14] Ngo, L. and Haddawy, P. Answering queries fromcontext-sensitive probabilistic knowledge bases. Theoretical Computer Science, 171, 1997.
[15] Poole, D. Probabilistic Horn abduction and Bayesian
networks. Artif. Intell., 64, 1993.
[16] Poole, D., Compiling a default reasoning system into
Prolog, New Generation Comput., 9(1), 1991.
[17] Rabiner, L. and Juang, B. Foundations of Speech
Recognition, Prentice-Hall, 1993.
[18] Sakama,T. and Inoue,K., Representing Priorities in
Logic Programs, Proc. of JICSLP96, MIT Press, 1996.
[19] Sato, T. A statistical learning method for logic programs with distribution semantics. Proc. of ICLP'95,
1995.
[20] Sato, T. and Kameya, Y. PRISM: a language
for symbolic-statistical modeling. Proc. of IJCAI'97,
1997.
[21] Sterling, L. and Shaprio, E. The Art of Prolog, The
MIT Press, 1986.
[22] Tamaki, H. and Sato, T. OLD resolution with tabulation. Proc. of ICLP'86, LNCS 225, 1986.
[23] Tanner, M. Tools for Statistical Inference (2nd ed.).
Springer-Verlag, 1986.