Paper: Kullback-Leibler Distance Between Probabilistic Context-Free Grammars And Probabilistic Finite Automata

ACL ID C04-1011
Title Kullback-Leibler Distance Between Probabilistic Context-Free Grammars And Probabilistic Finite Automata
Venue International Conference on Computational Linguistics
Session Main Conference
Year 2004
Authors

We consider the problem of computing the Kullback-Leibler distance, also called the relative entropy, between a probabilistic context-free grammar and a probabilistic - 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 nite automata.