Cross-Entropy and Estimation of Probabilistic Context-Free Grammars

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 335–342, New York, June 2006. c⃝2006 Association for Computational Linguistics Cross-Entropy and Estimation of Probabilistic Context-Free Grammars Anna Corazza Department of Physics University “Federico II” via Cinthia I-80126 Napoli, Italy corazza@na.infn.it Giorgio Satta Department of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova, Italy satta@dei.unipd.it Abstract We investigate the problem of training probabilistic context-free grammars on the basis of a distribution defined over an infinite set of trees, by minimizing the cross-entropy. This problem can be seen as a generalization of the well-known maximum likelihood estimator on (finite) tree banks. We prove an unexpected the- oretical property of grammars that are trained in this way, namely, we show that the derivational entropy of the gram- mar takes the same value as the cross- entropy between the input distribution and the grammar itself. We show that the re- sult also holds for the widely applied max- imum likelihood estimator on tree banks. 1 Introduction Probabilistic context-free grammars are able to de- scribe hierarchical, tree-shaped structures underly- ing sentences, and are widely used in statistical nat- ural language processing; see for instance (Collins, 2003) and references therein. Probabilistic context- free grammars seem also more suitable than finite- state devices for language modeling, and several language models based on these grammars have been recently proposed in the literature; see for in- stance (Chelba and Jelinek, 1998), (Charniak, 2001) and (Roark, 2001). Empirical estimation of probabilistic context-free grammars is usually carried out on tree banks, that is, finite samples of parse trees, through the max- imization of the likelihood of the sample itself. It is well-known that this method also minimizes the cross-entropy between the probability distribution induced by the tree bank, also called the empirical distribution, and the tree probability distribution in- duced by the estimated grammar. In this paper we generalize the maximum like- lihood method, proposing an estimation technique that works on any unrestricted tree distribution de- fined over an infinite set of trees. This generalization is theoretically appealing, and allows us to prove un- expected properties of the already mentioned maxi- mum likelihood estimator for tree banks, that were not previously known in the literature on statistical natural language parsing. More specifically, we in- vestigate the following information theoretic quanti- ties • the cross-entropy between the unrestricted tree distribution given as input and the tree distri- bution induced by the estimated probabilistic context-free grammar; and • the derivational entropy of the estimated prob- abilistic context-free grammar. These two quantities are usually unrelated. We show that these two quantities take the same value when the probabilistic context-free grammar is trained us- ing the minimal cross-entropy criterion. We then translate back this property to the method of max- imum likelihood estimation. Our general estima- tion method also has practical applications in cases one uses a probabilistic context-free grammar to ap- proximate strictly more powerful rewriting systems, 335 as for instance probabilistic tree adjoining gram- …

Content truncated to 500 words