
| Mo del      | Program        | OLDT time           | g EM   | Specialized EM          |
|-------------|----------------|---------------------|--------|-------------------------|
| HMMs        | DB             | O ( N 2 L )         | O(N2L) | Baum-Welch              |
| O(M 3 L 3 ) | O(M 3 L 3 )    |                     |        |                         |
| PCFGs       | DB,,           | Inside-Outside      |        |                         |
| s- BNs      | DB G           | 0(|V|)              | 0(|V|) | (Castillo et al., 1997) |
| user model  | 0(|OLDT tree|) | O(|support graph |) |        |                         |

## 5.6 Modeling Language Prism

We have been developing a symbolic-statistical modeling laguage PRISM since 1995 (URL
= http://mi.cs.titech.ac.jp/prism/ ) as an implementation of distribution semantics
(Sato, 1995; Sato & Kameya, 1997; Sato, 1998). The language is intented for modeling complex symbolic-statistical phenomena such as discourse in terpretation in natural language processing and gene inheritance interacting with social rules. As a programming language, it looks like an extension of Prolog with new built-in predicates in cluding the msv predicate and other special predicates for manipulating msw atoms and their parameters.

A PRISM program is comprised of three parts, one for directives, one for modeling and one for utilities. The directive part contains declarations such as values, telling the system wh at msw atoms will be used in the execution. The modeling part is a set of non-unit definite clauses that define the distribution (denotation) of the program by using msw atoms. The last part, the utility part, is an arbitary Prolog program which refers to predicates defined in the modeling part. We can use in the utility part learn built-in predicate to carry out EM learning from observed atoms.

PRISM provides three modes of execution. The sampling execution correponds to a random sampling drawn from the distribution defined by the modeling part. The second one computes the probability of a given atom. The third one returns the support set for a given goal. These execution modes are available through built-in predicates.

We must report however that while the implementation of the graphical EM algorithm with a simpified OLDT search mechanism has been under way, it is not completed yet. So currently, only Prolog search and learn-naive ( DB, G ) in Section 4 are available for EM learning though we realized, partially, structrure sharing of explanations in the implemention of learn-naive( DB, G ). Putting computational efficiecy aside however, there is no problem in expressing and learning HMMs, PCFGs, pseudo PCSGs, Bayesian networks and other probailistic models by the current version. The learning experiments in the next section used a parser as a substitute for the OLDT interpreter, and the independently implemented graphical EM algorithm.

## 6. Learning Experiments

After complexity analysis of the graphical EM algorithm for popular symbolic-probabilistic models in the previous section, we look at an actual behavior of the graphical EM algorithm with real data in this section. We conducted learning experiments with PCFGs using two