Transforming Dependencies into Phrase Structures

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 788–798, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics Transforming Dependencies into Phrase Structures Lingpeng Kong School of Computer Science Carnegie Mellon University Pittsburgh, PA, USA lingpenk@cs.cmu.edu Alexander M. Rush Facebook AI Research New York, NY, USA srush@seas.harvard.edu Noah A. Smith School of Computer Science Carnegie Mellon University Pittsburgh, PA, USA nasmith@cs.cmu.edu Abstract We present a new algorithm for transforming dependency parse trees into phrase-structure parse trees. We cast the problem as struc- tured prediction and learn a statistical model. Our algorithm is faster than traditional phrase- structure parsing and achieves 90.4% English parsing accuracy and 82.4% Chinese parsing accuracy, near to the state of the art on both benchmarks. 1 Introduction Natural language parsers typically produce phrase- structure (constituent) trees or dependency trees. These representations capture some of the same syn- tactic phenomena, and the two can be produced jointly (Klein and Manning, 2002; Hall and Nivre, 2008; Carreras et al., 2008; Rush et al., 2010). Yet it appears to be completely unpredictable which will be preferred by a particular subcommunity or used in a particular application. Both continue to receive the attention of parsing researchers. Further, it appears to be a historical accident that phrase-structure syntax was used in annotating the Penn Treebank, and that English dependency annotations are largely derived through mechani- cal, rule-based transformations (reviewed in Sec- tion 2). Indeed, despite extensive work on direct- to-dependency parsing algorithms (which we call d- parsing), the most accurate dependency parsers for English still involve phrase-structure parsing (which we call c-parsing) followed by rule-based extraction of dependencies (Kong and Smith, 2014). What if dependency annotations had come first? Because d-parsers are generally much faster than c-parsers, we consider an alternate pipeline (Sec- tion 3): d-parse first, then transform the depen- dency representation into a phrase-structure tree constrained to be consistent with the dependency parse. This idea was explored by Xia and Palmer (2001) and Xia et al. (2009) using hand-written rules. Instead, we present a data-driven algorithm using the structured prediction framework (Sec- tion 4). The approach can be understood as a specially-trained coarse-to-fine decoding algorithm where a d-parser provides “coarse” structure and the second stage refines it (Charniak and Johnson, 2005; Petrov and Klein, 2007). Our lexicalized phrase-structure parser, PAD, is asymptotically faster than parsing with a lexical- ized context-free grammar: O(n2) plus d-parsing, vs. O(n5) worst case runtime in sentence length n, with the same grammar constant. Experiments show that our approach achieves linear observable runtime, and accuracy similar to state-of-the-art phrase-structure parsers without reranking or semi- supervised training (Section 7). 2 Background We begin with the conventional development by first introducing c-parsing and then defining d-parses through a mechanical conversion using head rules. In the next section, we consider the reverse transfor- mation. 2.1 CFG Parsing The phrase-structure trees annotated in the Penn Treebank are derivation trees from a context-free grammar. Define a binary1 context-free …

Content truncated to 500 words