Paper: Prefix Probabilities from Stochastic Tree Adjoining Grammars

ACL ID C98-2152
Title Prefix Probabilities from Stochastic Tree Adjoining Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1998

Language models for speech recognition typ- ically use a probability model of the form Pr(an]al,a~,...,an-1). Stochastic grammars, on the other hand, are typically used to as- sign structure to utterances. A lm~guage model of the above form is constructed from such grammars by computing the prefix probabil- ity ~c>:* Pr(al... aT~w), where w represents all possible terminations of the prefix al "" an. 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 (9(n a) time. The probability of sub- derivations that do not derive any words in the prefix, but contribute structurally to its deriva- tion, are preeomputed to achieve termination. This algor...