Computation of Infix Probabilities for Probabilistic Context-Free Grammars

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1213–1221, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Computation of Infix Probabilities for Probabilistic Context-Free Grammars Mark-Jan Nederhof School of Computer Science University of St Andrews United Kingdom markjan.nederhof@gmail.com Giorgio Satta Dept. of Information Engineering University of Padua Italy satta@dei.unipd.it Abstract The notion of infix probability has been intro- duced in the literature as a generalization of the notion of prefix (or initial substring) prob- ability, motivated by applications in speech recognition and word error correction. For the case where a probabilistic context-free gram- mar is used as language model, methods for the computation of infix probabilities have been presented in the literature, based on vari- ous simplifying assumptions. Here we present a solution that applies to the problem in its full generality. 1 Introduction Probabilistic context-free grammars (PCFGs for short) are a statistical model widely used in natural language processing. Several computational prob- lems related to PCFGs have been investigated in the literature, motivated by applications in model- ing of natural language syntax. One such problem is the computation of prefix probabilities for PCFGs, where we are given as input a PCFG G and a string w, and we are asked to compute the probability that a sentence generated by G starts with w, that is, has w as a prefix. This quantity is defined as the possi- bly infinite sum of the probabilities of all strings of the form wx, for any string x over the alphabet of G. The problem of computation of prefix probabili- ties for PCFGs was first formulated by Persoon and Fu (1975). Efficient algorithms for its solution have been proposed by Jelinek and Lafferty (1991) and Stolcke (1995). Prefix probabilities can be used to compute probability distributions for the next word or part-of-speech, when a prefix of the input has al- ready been processed, as discussed by Jelinek and Lafferty (1991). Such distributions are useful for speech recognition, where the result of the acous- tic processor is represented as a lattice, and local choices must be made for a next transition. In ad- dition, distributions for the next word are also useful for applications of word error correction, when one is processing ‘noisy’ text and the parser recognizes an error that must be recovered by operations of in- sertion, replacement or deletion. Motivated by the above applications, the problem of the computation of infix probabilities for PCFGs has been introduced in the literature as a generaliza- tion of the prefix probability problem. We are now given a PCFG G and a string w, and we are asked to compute the probability that a sentence generated by G has w as an infix. This probability is defined as the possibly infinite sum of the probabilities of all strings of the form xwy, for any pair of strings x and y over the alphabet of G. Besides applications in computation of the probability distribution for the next word …

Content truncated to 500 words