and learn the parameters of the distribution associated with the program. Redundancy in the second phase is removed by the introduction of inside and outside probability for logic programs computed from the support graph.

The graphical EM algorithm has accomplished, when combined with OLDT search for all explanations, the same time complexity as the specialized ones, e.g. the Baum-Welch agorithm for HMMs (Rabiner, 1989) and the Inside-Outside algorithm for PCFGs (Baker, 1979), despite its generality. What is surprising is that, when we conducted learning experiments with PCFGs using real corpora, it outperformed the Inside-Outside algorithm by orders of magnitudes in terms of time for one iteration to update parameters. These experimental results enhance the prospect for symbolic-statistical modeling by parameterized logic programs of even more complex systems than stochastic grammars whose modeling has been difficult simply because of the lack of an appropriate modeling tool and their sheer complexities. The contributions of this paper therefore are

- distribution semantics for parameterized logic programs which unifies existing symbolicstatistical frameworks,
- the graphical EM algorithm (combined with tabulated search), a general yet efficient EM algorithm that runs on support graphs and
- the prospect suggested by the learning experiments for modeling and learning complex symbolic-statistical phenomena.
The rest of this paper is organized as follows. After preliminaries in Section 2, a probability space for parameterized logic programs is constructed in Section 3 as a m athematical basis for the subsequent sections. We then propose a new EM algorithm, the graphical EM algorithm, for parameterized logic programs in Section 4. Complexity analysis of the graphical EM algorithm is presented in Section 5 for HMMs, PCFGs, pseudo PCSGs and sc-BNs. 7  Section 6 contains experimental results of parameter learning with  PCFGs by the graphical EM algorithm using real corpora that demonstrate the efficiency of the graphical EM algorithm. We state related work in Section 7, followed by conclusion in Section 8. The reader is assumed to be familiar with the basics of logic programming (Lloyd, 1984; Doets, 1994), probability theory (Chow & Teicher, 1997), Bayesian networks (Pearl, 1988; Castillo et al., 1997) and stochastic grammars (Rabiner, 1989; Manning & Schütze, 1999).

## 2. Preliminaries

Since our subject intersects logic programming and EM learning which are quite different in nature, we separate preliminaries.

## 2.1  Logic Programming And Oldt

In logic programming, a program DB is a set of definite clauses 8 and the execution is search for an SLD refutation of a given goal ← G . The top-down interpreter recursively selects the