next goal and unfolds it (Tamaki & Sato, 1984) into subgoals using a nondeterministically chosen clause. The computed result by the SLD refutation, i.e. a solution , is an answer substitution (variable binding) θ such that DB þ Gθ. 9 Usually there is more than one refutation for ~ G, and the search space for all refutations is described by an SLD tree which may be infinite depending on the program and the goal (Lloyd, 1984; Doets, 1994).

More often than not, applications require all solutions. In natural language processing for instance, a parser must be able to find all possible parse trees for a given sentence as ery one of them is syntactically correct. Similarly in statistical abduction, we need to examine all explanations to determine the most likely one. All solutions are obtained by sseeeerr the entire SLD tree, and there is a choice of the search strategy. In Prolog, the standard logic programming language, backtracking is used to search for all solutions in conjunction with a fixed search order for goals (textually from left-to-right) and clauses (textually top-to-bottom) due to the ease and simplicity of implementation.

The problem with backtracking is that it forgets everything until up to the previous choice point, and hence it is quite likely to prove the same goal again and again, resulting in exponential search time. One answer to avoid this problem is to store computed results and reuse them whenever necessary. OLDT is such an instance of memoizing scheme (Tamaki
& Sato, 1986; Warren, 1992; Sagonas et al., 1994; Ramakrishnan et al., 1995; Shen et al.,
2001).  Reuse of proved subgoals in OLDT search often drastically reduces search time for all solutions, especially when refutations of the top goal include many common subrefutations. Take as an example a logic program coding an HMM. For a given string s, there exist exponentially many transition paths that output s. OLDT search applied to the program however only takes time linear in the length of s to find all of them unlike exponential time by Prolog's backtracking search.

What does OLDT have to do with statistical abduction? From the viewpoint of statistical abduction, reuse of proved subgoals, or equivalently, structure sharing of sub-refutations for the top-goal G brings about structure sharing of explanations for G , in addition to the reduction of search time mentioned above, thereby producing a highly compact representation of all explanations for G

## 2.2  Em Learning

Parameterized distributions such as the multinomial distribution and the normal distribution provide convenient modeling devices in statistics. Suppose a random sample x 1 , . . . , x T
of size T on a random variable X drawn from a distribution P ( X = x | θ ) parameterized by unknown 0, is observed. The value of 0 is determined by ML estimation as the MLE
(maximum likelihood estimate) of θ , i.e. as the maximizer of the likelihood Π 1< i< T P ( x i | θ ).

Things get much more difficult when data are incomplete. Think of a probabilistic relationship between non-observable cause X and observable effect Y such as one between diseases and symptoms in medicine and assume that Y does not uniquely determine the cause X. Then Y is incomplete in the sense that Y does not carry enough information to completely determine X. Let P(X = x,Y = y | 0) be a parameterized joint distribution over X and Y. Our task is to perform ML estimation on 0 under the condition that X is