
## 7.2 Limitations And Potential Problems

Approaches described so far have more or less similar limitations and potential problems.

Descriptive power confined to finite domains is the most common limitation, which is due to the use of the linear programming technique (Nilsson, 1986), or due to the syntactic restrictions not allowing for infinitely many constant, function or predicate symbols (Ng
& Subrahmanian, 1992; Lakshmanan & Sadri, 1994). Bayesian networks have the same limitation as well (only a finite number of random variables are representable). 68 Also there are various semantic/syntactic restrictions on logic programs. For instance the acyclicity condition imposed by Poole (1993) and Ngo and Haddawy (1997) prevents the unconditional use of clauses with local variables, and the range-restrictedness imposed by Muggleton (1996) and Cussens (1999) excludes programs such as the usual membership Prolog program.

There is another type of problem, the possibility of assigning conflicting probabilities to logically equivalent formulas. In SLPs, P(A) and P(AAA) do not necessarily coincide because A and A A A may have different refutations (Muggleton, 1996; Cussens, 1999, 2001).

Consequently in SLPs, we would be in trouble if we naively interpret P(A) as the probability of A's being true. Also assigning probabilities to arbitrary quantified formulas seems out of scope of both approaches to SLPs.

Last but not least, there is a big problem common to any approach using probabilities:
where do the numbers come from?  Generally speaking, if we use n binary random variables in a model, we have to determine 2 " probabilities to completely specify their joint distribution, and fulfilling this requirement with reliable numbers quickly becomes im possible as n grows.

The situation is even worse when there are unobservable variables in the model such as possible causes of a disease. Apparently parameter learning from observed data is a natural solution to this problem, but parameter learning of logic programs has not been well studied.

Distribution semantics proposed by Sato (1995) was an attempt to solve these problems aong the line of the global distribution approa. It defines a distribution (probability measure) over the possible interpretations of ground atoms for an arbitrary logic program in any first order language and assigns consistent probabilities to all closed formulas. Also distribution sem antics enabled us to derive an EM algorithm for the parameter learning of logic programs for the first time. As it was a naive algorithm however, dealing with large problems was difficult when there are exponentially many explanations for an observation like HMMs.  We believe that the efficiency problem is solved to a large extent by the graphical EM algorithm presented in this paper.

## 7.3  Em Learning

Since EM learning is one of the central issues in this paper, we separately mention work related to EM learning for symbolic frameworks. Koller and Pfeffer (1997) used in their approach to KBMC (knowledge-based model construction) EM learning to estimate parameters labeling clauses. They express probabilistic dependencies among events by definite clauses annotated with probabilities, similarly to Ngo and Haddawy's (1997) approach, and locally build a Bayesian network relevant to the context and evidence as well as the