Estimators for Stochastic “Unification-Based” Grammars

Estimators for Stochastic "Unification-Based" Grammars* Mark Johnson Cognitive and Linguistic Sciences Brown University Stuart Geman Applied Mathematics Brown University Stephen Canon Cognitive and Linguistic Sciences Brown University Zhiyi Chi Dept. of Statistics The University of Chicago Stefan Riezler Institut fiir Maschinelle Sprachverarbeitung Universit~t Stuttgart Abstract Log-linear models provide a statistically sound framework for Stochastic "Unification-Based" Grammars (SUBGs) and stochastic versions of other kinds of grammars. We describe two computationally-tractable ways of estimating the parameters of such grammars from a train- ing corpus of syntactic analyses, and apply these to estimate a stochastic version of Lexical- Functional Grammar. 1 Introduction Probabilistic methods have revolutionized com- putational linguistics. They can provide a systematic treatment of preferences in pars- ing. Given a suitable estimation procedure, stochastic models can be "tuned" to reflect the properties of a corpus. On the other hand, "Unification-Based" Grammars (UBGs) can ex- press a variety of linguistically-important syn- tactic and semantic constraints. However, de- veloping Stochastic "Unification-based" Gram- mars (SUBGs) has not proved as straight- forward as might be hoped. The simple "relative frequency" estimator for PCFGs yields the maximum likelihood pa- rameter estimate, which is to say that it minimizes the Kulback-Liebler divergence be- tween the training and estimated distributions. On the other hand, as Abney (1997) points out, the context-sensitive dependencies that "unification-based" constraints introduce ren- der the relative frequency estimator suboptimal: in general it does not maximize the likelihood and it is inconsistent. * This research was supported by the National Science Foundation (SBR,-9720368), the US Army Research Of- fice (DAAH04-96-BAA5), and Office of Naval Research (N00014-97-1-0249). Abney (1997) proposes a Markov Random Field or log linear model for SUBGs, and the models described here are instances of Abney's general framework. However, the Monte-Carlo parameter estimation procedure that Abney proposes seems to be computationally imprac- tical for reasonable-sized grammars. Sections 3 and 4 describe two new estimation procedures which are computationally tractable. Section 5 describes an experiment with a small LFG cor- pus provided to us by Xerox PAaC. The log linear framework and the estimation procedures are extremely general, and they apply directly to stochastic versions of HPSG and other theo- ries of grammar. 2 Features in SUBGs We follow the statistical literature in using the term feature to refer to the properties that pa- rameters are associated with (we use the word "attribute" to refer to the attributes or features of a UBG's feature structure). Let ~ be the set of all possible grammatical or well-formed analyses. Each feature f maps a syntactic anal- ysis w E ~ to a real value f(w). The form of a syntactic analysis depends on the underlying linguistic theory. For example, for a PCFG w would be parse tree, for a LFG w would be a tuple consisting of (at least) a c-structure, an f- structure and a mapping from c-structure nodes to f-structure elements, and for a Chomskyian transformational grammar w would be a deriva- tion. Log-linear models are models in which the log probability is a …

Content truncated to 500 words