Simple, Accurate Parsing with an All-Fragments Grammar

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1098–1107, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Simple, Accurate Parsing with an All-Fragments Grammar Mohit Bansal and Dan Klein Computer Science Division University of California, Berkeley {mbansal, klein}@cs.berkeley.edu Abstract We present a simple but accurate parser which exploits both large tree fragments and symbol refinement. We parse with all fragments of the training set, in con- trast to much recent work on tree se- lection in data-oriented parsing and tree- substitution grammar learning. We re- quire only simple, deterministic grammar symbol refinement, in contrast to recent work on latent symbol refinement. More- over, our parser requires no explicit lexi- con machinery, instead parsing input sen- tences as character streams. Despite its simplicity, our parser achieves accuracies of over 88% F1 on the standard English WSJ task, which is competitive with sub- stantially more complicated state-of-the- art lexicalized and latent-variable parsers. Additional specific contributions center on making implicit all-fragments parsing effi- cient, including a coarse-to-fine inference scheme and a new graph encoding. 1 Introduction Modern NLP systems have increasingly used data- intensive models that capture many or even all substructures from the training data. In the do- main of syntactic parsing, the idea that all train- ing fragments1 might be relevant to parsing has a long history, including tree-substitution grammar (data-oriented parsing) approaches (Scha, 1990; Bod, 1993; Goodman, 1996a; Chiang, 2003) and tree kernel approaches (Collins and Duffy, 2002). For machine translation, the key modern advance- ment has been the ability to represent and memo- rize large training substructures, be it in contigu- ous phrases (Koehn et al., 2003) or syntactic trees 1In this paper, a fragment means an elementary tree in a tree-substitution grammar, while a subtree means a fragment that bottoms out in terminals. (Galley et al., 2004; Chiang, 2005; Deneefe and Knight, 2009). In all such systems, a central chal- lenge is efficiency: there are generally a combina- torial number of substructures in the training data, and it is impractical to explicitly extract them all. On both efficiency and statistical grounds, much recent TSG work has focused on fragment selec- tion (Zuidema, 2007; Cohn et al., 2009; Post and Gildea, 2009). At the same time, many high-performance parsers have focused on symbol refinement ap- proaches, wherein PCFG independence assump- tions are weakened not by increasing rule sizes but by subdividing coarse treebank symbols into many subcategories either using structural anno- tation (Johnson, 1998; Klein and Manning, 2003) or lexicalization (Collins, 1999; Charniak, 2000). Indeed, a recent trend has shown high accura- cies from models which are dedicated to inducing such subcategories (Henderson, 2004; Matsuzaki et al., 2005; Petrov et al., 2006). In this paper, we present a simplified parser which combines the two basic ideas, using both large fragments and symbol refinement, to provide non-local and lo- cal context respectively. The two approaches turn out to be highly complementary; even the simplest (deterministic) symbol refinement and a basic use of an …

Content truncated to 500 words