Prefix Probability for Probabilistic Synchronous Context-Free Grammars

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 460–469, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Prefix Probability for Probabilistic Synchronous Context-Free Grammars Mark-Jan Nederhof School of Computer Science University of St Andrews North Haugh, St Andrews, Fife KY16 9SX United Kingdom markjan.nederhof@googlemail.com Giorgio Satta Dept. of Information Engineering University of Padua via Gradenigo, 6/A I-35131 Padova Italy satta@dei.unipd.it Abstract We present a method for the computation of prefix probabilities for synchronous context- free grammars. Our framework is fairly gen- eral and relies on the combination of a sim- ple, novel grammar transformation and stan- dard techniques to bring grammars into nor- mal forms. 1 Introduction Within the area of statistical machine translation, there has been a growing interest in so-called syntax- based translation models, that is, models that de- fine mappings between languages through hierar- chical sentence structures. Several such statistical models that have been investigated in the literature are based on synchronous rewriting or tree transduc- tion. Probabilistic synchronous context-free gram- mars (PSCFGs) are one among the most popular ex- amples of such models. PSCFGs subsume several syntax-based statistical translation models, as for in- stance the stochastic inversion transduction gram- mars of Wu (1997), the statistical model used by the Hiero system of Chiang (2007), and systems which extract rules from parsed text, as in Galley et al. (2004). Despite the widespread usage of models related to PSCFGs, our theoretical understanding of this class is quite limited. In contrast to the closely related class of probabilistic context-free grammars, a syn- tax model for which several interesting mathemati- cal and statistical properties have been investigated, as for instance by Chi (1999), many theoretical prob- lems are still unsolved for the class of PSCFGs. This paper considers a parsing problem that is well understood for probabilistic context-free gram- mars but that has never been investigated in the con- text of PSCFGs, viz. the computation of prefix prob- abilities. In the case of a probabilistic context-free grammar, this problem is defined as follows. We are asked to compute the probability that a sentence generated by our model starts with a prefix string v given as input. This quantity is defined as the (pos- sibly infinite) sum of the probabilities of all strings of the form vw, for any string w over the alphabet of the model. This problem has been studied by Jelinek and Lafferty (1991) and by Stolcke (1995). Prefix probabilities can be used to compute probabil- ity distributions for the next word or part-of-speech. This has applications in incremental processing of text or speech from left to right; see again (Jelinek and Lafferty, 1991). Prefix probabilities can also be exploited in speech understanding systems to score partial hypotheses in beam search (Corazza et al., 1991). This paper investigates the problem of computing prefix probabilities for PSCFGs. In this context, a pair of strings v1 and v2 is given as input, and we are asked to compute the probability that any string …

Content truncated to 500 words