Paper: Dynamic Programming For Parsing And Estimation Of Stochastic Unification-Based Grammars

ACL ID P02-1036
Title Dynamic Programming For Parsing And Estimation Of Stochastic Unification-Based Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2002
Authors

Stochastic uni cation-based grammars (SUBGs) de ne exponential distributions over the parses generated by a uni cation- based grammar (UBG). Existing algo- rithms for parsing and estimation require the enumeration of all of the parses of a string in order to determine the most likely one, or in order to calculate the statis- tics needed to estimate a grammar from a training corpus. This paper describes a graph-based dynamic programming algo- rithm for calculating these statistics from the packed UBG parse representations of Maxwell and Kaplan (1995) which does not require enumerating all parses. Like many graphical algorithms, the dynamic programming algorithm’s complexity is worst-case exponential, but is often poly- nomial. The key observation is that by using Maxwell and Kaplan packed...