
## Appendix B. The Mar (Missing At Random) Condition

In the original formulation of the EM algorithm by Dempster et al. (1977), it is assumed that there exists a many-to-one mapping y = χ( x ) from a complete data x to an incomplete (observed) data y . In the case of parsing, x is a parse tree and y is the input sentence and x uniquely determines y. In this paper, the uniqueness condition ensures the existence of such a many-to-one mapping from explanations to observations. We however sometimes face a situation where there is no such many-to-one mapping from complete data to incomplete data but nonetheless we wish to apply the EM algorithm.

This dilemma can be solved by the introduction of a missing-data mechanism which makes a complete data incomplete. The missing-data mechanism, m, has a distribution g ( m | x ) parameterized by φ and y , the observed data, is described as y = χ m ( x ). It says x becomes incomplete y by m . The correspondence between x and y,i.e. {{x,y) | 3m(y =
Xm (x))} naturally becomes many-to-many.

Rubin (1976) derived two conditions on g A (data are missing at random and data are observed at random) collectively called the MAR (missing at random) condition , and showed that if we assume a missing-data mechanism behind our observations that satisfies the MAR
condition, we may estimate parameters of the distribution over x by simply applying the EM algorithm to y, the observed data.

We adapt the MAR condition to parameterized logic programs as follows. We keep a generative model satisfying the uniqueness condition that outputs goals G such as parse trees. We further extend the model by additionally inserting a missing-data mechanism m between G and our observation O like O = χ m ( G ) and assume m satisfies the MAR
condition. Then the extended model has a many-to-many correspondence between explanations and observations, and generates non-exclusive observations such that P(O A O') > 0
( O ̸ = O ′ ), which causes ∑ O P( O ) ≥ 1 where P( O ) = ∑ G; 3m O= Xm( G ) PDB( G ). Thanks to the MAR condition however, we are still allowed to apply the EM algorithm to such nonexclusive observations. Put it differently, even if the uniqueness condition is seemingly destroyed, the EM algorithm is applicable just by (imaginarily) assuming a missing-data mechanism satisfying the MAR condition.

## References

Abney, S. (1997). Stochastic attribute-value grammars. Computational Linguistics, 23 (4),
597-618.

Arimura, H. (1997). Learning acyclic first-order horn sentences from entailment.

In Proceedings of the Eighth International Workshop on Algorithmic Learning Theory.

Ohmsha/Springer-Verlag.

Bacchus, F., Grove, A., Halpern, J., & Koller, D. (1996). From statistical knowledge bases to degrees of belief. Artificial Intelligence, 87 , 75 - 143.

Baker, J. K. (1979). Trainable grammars for speech recognition. In Proceedings of Spring Conference of the Acoustical Society of America, pp. 547-550.