Dynamic programming for parsing and estimation of stochastic unification-based grammars

Dynamic programming for parsing and estimation of stochastic unification-based grammars∗ Stuart Geman Division of Applied Mathematics Brown University geman@dam.brown.edu Mark Johnson Cognitive and Linguistic Sciences Brown University Mark Johnson@Brown.edu Abstract Stochastic unification-based grammars (SUBGs) define exponential distributions over the parses generated by a unification- 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 repre- sentations, the required statistics can be rewritten as either the max or the sum of a product of functions. This is exactly the kind of problem which can be solved by dynamic programming over graphical models. ∗ We would like to thank Eugene Charniak, Miyao Yusuke, Mark Steedman as well as Stefan Riezler and the team at PARC; naturally all errors remain our own. This research was supported by NSF awards DMS 0074276 and ITR IIS 0085940. 1 Introduction Stochastic Unification-Based Grammars (SUBGs) use log-linear models (also known as exponential or MaxEnt models and Markov Random Fields) to de- fine probability distributions over the parses of a uni- fication grammar. These grammars can incorporate virtually all kinds of linguistically important con- straints (including non-local and non-context-free constraints), and are equipped with a statistically sound framework for estimation and learning. Abney (1997) pointed out that the non-context- free dependencies of a unification grammar require stochastic models more general than Probabilis- tic Context-Free Grammars (PCFGs) and Markov Branching Processes, and proposed the use of log- linear models for defining probability distributions over the parses of a unification grammar. Un- fortunately, the maximum likelihood estimator Ab- ney proposed for SUBGs seems computationally in- tractable since it requires statistics that depend on the set of all parses of all strings generated by the grammar. This set is infinite (so exhaustive enumer- ation is impossible) and presumably has a very com- plex structure (so sampling estimates might take an extremely long time to converge). Johnson et al. (1999) observed that parsing and related tasks only require conditional distributions over parses given strings, and that such conditional distributions are considerably easier to estimate than joint distributions of strings and their parses. The conditional maximum likelihood estimator proposed by Johnson et al. requires statistics that depend on the set of all parses of the strings in the training cor- Computational Linguistics (ACL), Philadelphia, July 2002, pp. 279-286. Proceedings of the 40th Annual Meeting of the Association for pus. For most linguistically realistic grammars this set is finite, and for moderate sized grammars and training corpora this estimation …

Content truncated to 500 words