Estimation of Consistent Probabilistic Context-free Grammars

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 343–350, New York, June 2006. c⃝2006 Association for Computational Linguistics Estimation of Consistent Probabilistic Context-free Grammars Mark-Jan Nederhof Max Planck Institute for Psycholinguistics P.O. Box 310 NL-6500 AH Nijmegen The Netherlands MarkJan.Nederhof@mpi.nl Giorgio Satta Dept. of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova Italy satta@dei.unipd.it Abstract We consider several empirical estimators for probabilistic context-free grammars, and show that the estimated grammars have the so-called consistency property, under the most general conditions. Our estimators include the widely applied ex- pectation maximization method, used to estimate probabilistic context-free gram- mars on the basis of unannotated corpora. This solves a problem left open in the lit- erature, since for this method the consis- tency property has been shown only under restrictive assumptions on the rules of the source grammar. 1 Introduction Probabilistic context-free grammars are one of the most widely used formalisms in current work in sta- tistical natural language parsing and stochastic lan- guage modeling. An important property for a proba- bilistic context-free grammar is that it be consistent, that is, the grammar should assign probability of one to the set of all finite strings or parse trees that it generates. In other words, the grammar should not lose probability mass with strings or trees of infinite length. Several methods for the empirical estimation of probabilistic context-free grammars have been pro- posed in the literature, based on the optimization of some function on the probabilities of the observed data, such as the maximization of the likelihood of a tree bank or a corpus of unannotated sentences. It has been conjectured in (Wetherell, 1980) that these methods always provide probabilistic context-free grammars with the consistency property. A first re- sult in this direction was presented in (Chaudhuri et al., 1983), by showing that a probabilistic context- free grammar estimated by maximizing the likeli- hood of a sample of parse trees is always consistent. In later work by (S´anchez and Bened´ı, 1997) and (Chi and Geman, 1998), the result was in- dependently extended to expectation maximization, which is an unsupervised method exploited to es- timate probabilistic context-free grammars by find- ing local maxima of the likelihood of a sample of unannotated sentences. The proof in (S´anchez and Bened´ı, 1997) makes use of spectral analysis of ex- pectation matrices, while the proof in (Chi and Ge- man, 1998) is based on a simpler counting argument. Both these proofs assume restrictions on the un- derlying context-free grammars. More specifically, in (Chi and Geman, 1998) empty rules and unary rules are not allowed, thus excluding infinite ambi- guity, that is, the possibility that some string in the input sample has an infinite number of derivations in the grammar. The treatment of general form context- free grammars has been an open problem so far. In this paper we consider several estimation meth- ods for probabilistic context-free grammars, and we show that the resulting grammars have the consis- tency property. …

Content truncated to 500 words