Prefix Probabilities from Stochastic Tree Adjoining Grammars
| dc.creator | Nederhof, Mark-Jan | |
| dc.creator | Sarkar, Anoop | |
| dc.creator | Satta, Giorgio | |
| dc.date | 1998-09-18 | |
| dc.date.accessioned | 2026-07-07T03:23:32Z | |
| dc.date.available | 2026-07-07T03:23:32Z | |
| dc.description | Language models for speech recognition typically use a probability model of the form Pr(a_n | a_1, a_2, ..., a_{n-1}). Stochastic grammars, on the other hand, are typically used to assign structure to utterances. A language model of the above form is constructed from such grammars by computing the prefix probability Sum_{w in Sigma*} Pr(a_1 ... a_n w), where w represents all possible terminations of the prefix a_1 ... a_n. 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 computation in O(n^6) time. The probability of subderivations that do not derive any words in the prefix, but contribute structurally to its derivation, are precomputed to achieve termination. This algorithm enables existing corpus-based estimation techniques for stochastic TAGs to be used for language modelling. | |
| dc.description | 7 pages, 2 Postscript figures, uses colacl.sty, graphicx.sty, psfrag.sty | |
| dc.identifier | https://arxiv.org/abs/cs/9809026 | |
| dc.identifier | http://arxiv.org/abs/cs/9809026 | |
| dc.identifier | In Proceedings of COLING-ACL '98 (Montreal) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32976 | |
| dc.subject | Computation and Language | |
| dc.subject | I.2.7; D.3.1 | |
| dc.title | Prefix Probabilities from Stochastic Tree Adjoining Grammars | |
| dc.type | text |