Kullback-Leibler Distance between Probabilistic Context-Free Grammars and Probabilistic Finite Automata

Kullback-Leibler Distance between Probabilistic Context-Free Grammars and Probabilistic Finite Automata Mark-Jan Nederhof Faculty of Arts University of Groningen P.O. Box 716 NL-9700 AS Groningen, The Netherlands markjan@let.rug.nl Giorgio Satta Department of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova, Italy satta@dei.unipd.it Abstract We consider the problem of computing the Kullback-Leibler distance, also called the relative entropy, between a probabilistic context-free grammar and a probabilistic fi- nite automaton. We show that there is a closed-form (analytical) solution for one part of the Kullback-Leibler distance, viz. the cross-entropy. We discuss several ap- plications of the result to the problem of distributional approximation of probabilis- tic context-free grammars by means of prob- abilistic finite automata. 1 Introduction Among the many formalisms used for descrip- tion and analysis of syntactic structure of natu- ral language, the class of context-free grammars (CFGs) is by far the best understood and most widely used. Many formalisms with greater gen- erative power, in particular the different types of unification grammars, are ultimately based on CFGs. Regular expressions, with their procedural counter-part of finite automata (FAs), are not able to describe hierarchical, tree-shaped struc- ture, and thereby seem less suitable than CFGs for full analysis of syntactic structure. How- ever, there are many applications where only partial or approximated analysis of structure is needed, and where full context-free processing could be prohibitively expensive. Such appli- cations can for example be found in real-time speech recognition systems: of the many hy- potheses returned by a speech recognizer, shal- low syntactic analysis may be used to select a small subset of those that seem most promis- ing for full syntactic processing in a next phase, thereby avoiding further computational costs for the less promising hypotheses. As FAs cannot describe structure as such, it is impractical to write the automata required for such applications by hand, and even diffi- cult to derive them automatically by training. For this reason, the used FAs are often derived from CFGs, by means of some form of approx- imation. An overview of different methods of approximating CFGs by FAs, along with an ex- perimental comparison, was given by (Nederhof, 2000). The next step is to assign probabilities to the transitions of the approximating FA, as the ap- plication outlined above requires a qualitative distinction between hypotheses rather than the purely boolean distinction of language member- ship. Under certain circumstances, this may be done by carrying over the probabilities from an input probabilistic CFG (PCFG), as shown for the special case of n-grams by (Rimon and Herz, 1991; Stolcke and Segal, 1994), or by training of the FA on a corpus generated by the PCFG (Jurafsky et al., 1994). See also (Mohri and Nederhof, 2001) for discussion of related ideas. An obvious question to ask is then how well the resulting PFA approximates the input PCFG, possibly for different methods of deter- mining an FA and different ways of attaching probabilities to the transitions. Until now, any direct way of measuring the distance between a …

Content truncated to 500 words