Paper: Prefix Probabilities from Stochastic Free Adjoining Grammars

ACL ID P98-2157
Title Prefix Probabilities from Stochastic Free Adjoining Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1998

Language models for speech recognition typ- ically use a probability model of the form Pr(an[al,a2,...,an-i). Stochastic grammars, on the other hand, are typically used to as- sign structure to utterances, A language model of the above form is constructed from such grammars by computing the prefix probabil- ity ~we~* Pr(al.-.artw), where w represents all possible terminations of the prefix The main result in this paper is an algorithm to compute such prefix probabilities given a stochastic Tree Adjoining Grammar (TAG). The algorithm achieves the required computa- tion in O(n 6) time. The probability of sub- derivations that do not derive any words in the prefix, but contribute structurally to its deriva- tion, are precomputed to achieve termination. This algorithm enables existing...