# Parameter Learning Of Logic Programs For Symbolic-Statistical Modeling

## Taisuke Sato Yoshitaka  Ka Meya

Dept. of Computer Science, Graduate School of Information Science and En gin eering, Tokyo In stitute of Techn ology 2-12-1 Ookayama Meguro-ku Tokyo Japan 152-8552 SATO@MI.CS.TITECH.AC.JP
K A ME @MI . CS . TITE CH . A C . J P

## Abstract

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

We also propose a new EM algorithm, the graphical EM algorithm, that runs for a class of parameterized logic programs representing sequential decision processes where each decision is exclusive and independent. It runs on a new data structure called support graphs describing the logical relationship between observations and their explanations, and learns parameters by computing inside and outside probability generalized for logic programs.

The complexity analysis shows that when combined with OLDT search for all explanations for observations, 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. Learning experiments with PCFGs using two corpora of moderate size indicate that the graphical EM algorithm can significantly outperform the Inside-Outside algorithm.

## 1. Introduction

Parameter learning is common in various fields from neural networks to reinforcement learning to statistics. It is used to tune up systems for their best performance, be they classifiers or statistical models. Unlike these numerical systems described by mathematical formulas however, symbolic systems, typically programs, do not seem amenable to any kind of parameter learning. Actually there has been little literature on parameter learning of programs.

This paper is an attempt to incorporate parameter learning into computer programs.

The reason is twofold. Theoretically we wish to add the ability of learning to computer programs, which the authors believe is a necessary step toward building intelligent systems. Practically it broadens the class of probability distributions, beyond traditionally used numerical ones, which are available for modeling complex phenomena such as gene inheritance, consumer behavior, natural language processing and so on.