
## 8. Conclusion

We have proposed a logical/mathematical framework for statistical parameter learning of parameterized logic programs, i.e. definite clause programs containing probabilistic facts with a parameterized probability distribution. It extends the traditional least Herbrand model semantics in logic programming to distribution semantics , possible world semantics with a probability distribution over possible worlds (Herbrand interpretations) which is unconditionally applicable to arbitrary logic programs including ones for HMMs, PCFGs and Bayesian networks.

We also have presented a new EM algorithm, the graphical EM algorithm in Section 4, which learns statistical parameters from observations for a class of parameterized logic programs representing a sequential decision process in which each decision is exclusive and independent. It works on support graphs , a new data structure specifying a logical relationship between an observed goal and itsexplanations, and estimates parameters by computing inside and outside probability generalized for logic programs.

The complexity analysis in Section 5 showed that when OLDT search, a complete tabled refutation method for logic programs, is employed for the support graph construction and table access is done in O(1) time, the graphical EM algorithm, despite its generality, has the same time complexity as existing EM algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside algorithm for PCFGs and the one for singly connected Bayesian networks that have been developed independently in each research field. In addition, for pseudo probabilistic context sensitive grammars with N nonterminals, we showed that the graphical EM algorithm runs in time O( N 4 L 3 ) for a sentence of length L .

To compare actual performance of the graphical EM algorithm against the Inside¬
Outside algorithm, we conducted learning experiments with PCFGs in Section 6 using two real corpora with contrasting characters. One is ATR corpus containing short sentences for which the grammar is not much ambiguous (958 parses/sentence), and the other is EDR corpus containing long sentences for which the grammar is rather ambiguous (3.0 x 10 8 at average sentence length 20). In both cases, the graphical EM algorithm outperformed the Inside-Outside algorithm by orders of magnitude in terms of time per iteration, which suggests the effectiveness of our approach to EM learning by the graphical EM algorithm.

Since our semantics is not limited to finite domains or finitely many random variables but applicable to any logic programs of arbitrary complexity, the graphical EM algorithm is expected to give a general yet efficient method of parameter learning for models of complex symbolic-statistical phenomena governed by rules and probabilities.

## A Cknow Ledgment S

The authors wish to thank three anonymous referees for their comments and suggestions.

Special thanks go to Takashi Mori and Shigeru Abe for stimulating discussions and learning experiments, and also to Tanaka-Tokunaga Laboratory for kindly allowing them to use MSLR parser and the linguistic data.