Accurate Parsing with Compact Tree-Substitution Grammars: Double-DOP

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 84–95, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Accurate Parsing with Compact Tree-Substitution Grammars: Double-DOP Federico Sangati and Willem Zuidema Institute for Logic, Language and Computation University of Amsterdam Science Park 904, 1098 XH Amsterdam, The Netherlands {f.sangati,zuidema}@uva.nl Abstract We present a novel approach to Data-Oriented Parsing (DOP). Like other DOP models, our parser utilizes syntactic fragments of arbitrary size from a treebank to analyze new sentences, but, crucially, it uses only those which are encountered at least twice. This criterion al- lows us to work with a relatively small but representative set of fragments, which can be employed as the symbolic backbone of sev- eral probabilistic generative models. For pars- ing we define a transform-backtransform ap- proach that allows us to use standard PCFG technology, making our results easily replica- ble. According to standard Parseval metrics, our best model is on par with many state-of- the-art parsers, while offering some comple- mentary benefits: a simple generative proba- bility model, and an explicit representation of the larger units of grammar. 1 Introduction Data-oriented Parsing (DOP) is an approach to wide-coverage parsing based on assigning structures to new sentences using fragments of variable size extracted from a treebank. It was first proposed by Scha in 1990 and formalized by Bod (1992), and preceded many developments in statistical parsing (e.g., the “treebank grammars” of Charniak 1997) and linguistic theory (e.g., the current popularity of “constructions”, Jackendoff 2002). A rich lit- erature on DOP has emerged since, yielding state- of-the-art results on the Penn treebank benchmark test (Bod, 2001; Bansal and Klein, 2010) and in- spiring developments in related frameworks includ- ing tree kernels (Collins and Duffy, 2002), reranking (Charniak and Johnson, 2005) and Bayesian adaptor and fragment grammars (e.g., Johnson et al., 2007; O’Donnell et al., 2009; Cohn et al., 2010). By for- malizing the idea of using large fragments of earlier language experience to analyze new sentences, DOP captures an important property of language cogni- tion that has shaped natural language. It therefore complements approaches that have focused on prop- erties like lexicalization or incrementality, and might bring supplementary strengths in other NLP tasks. Early versions of DOP (e.g., Bod et al., 2003) aimed at extracting all subtrees of all trees in the treebank. The total number of constructions, how- ever, is prohibitively large for non-trivial treebanks: it grows exponentially with the length of the sen- tences, yielding the astronomically large number of approximately 1048 for section 2-21 of the Penn WSJ corpus. These models thus rely on a big sample of fragments, which inevitably includes a substan- tial portion of overspecialized constructions. Later DOP models have used the Goodman transforma- tion (Goodman, 1996, 2003) to obtain a compact representation of all fragments in the treebank (Bod, 2003; Bansal and Klein, 2010). In this case the grammatical constructions are no longer explicitly represented, and substantial engineering effort is needed to optimally tune the models …

Content truncated to 500 words