Parsing as Reduction

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1523–1533, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Parsing as Reduction Daniel Fern´andez-Gonz´alez†∗ Andr´e F. T. Martins‡# †Departamento de Inform´atica, Universidade de Vigo, Campus As Lagoas, 32004 Ourense, Spain ‡Instituto de Telecomunicac¸˜oes, Instituto Superior T´ecnico, 1049-001 Lisboa, Portugal #Priberam Labs, Alameda D. Afonso Henriques, 41, 2o, 1000-123 Lisboa, Portugal danifg@uvigo.es, atm@priberam.pt Abstract We reduce phrase-based parsing to depen- dency parsing. Our reduction is grounded on a new intermediate representation, “head-ordered dependency trees,” shown to be isomorphic to constituent trees. By encoding order information in the depen- dency labels, we show that any off-the- shelf, trainable dependency parser can be used to produce constituents. When this parser is non-projective, we can perform discontinuous parsing in a very natural manner. Despite the simplicity of our ap- proach, experiments show that the result- ing parsers are on par with strong base- lines, such as the Berkeley parser for En- glish and the best non-reranking system in the SPMRL-2014 shared task. Results are particularly striking for discontinuous parsing of German, where we surpass the current state of the art by a wide margin. 1 Introduction Constituent parsing is a central problem in NLP—one at which statistical models trained on treebanks have excelled (Charniak, 1996; Klein and Manning, 2003; Petrov and Klein, 2007). However, most existing parsers are slow, since they need to deal with a heavy grammar con- stant. Dependency parsers are generally faster, but less informative, since they do not produce con- stituents, which are often required by downstream applications (Johansson and Nugues, 2008; Wu et al., 2009; Berg-Kirkpatrick et al., 2011; Elming et al., 2013). How to get the best of both worlds? Coarse-to-fine decoding (Charniak and John- son, 2005) and shift-reduce parsing (Sagae and Lavie, 2005; Zhu et al., 2013) were a step forward ∗This research was carried out during an internship at Priberam Labs. to accelerate constituent parsing, but typical run- times still lag those of dependency parsers. This is only made worse if discontinuous constituents are allowed—such discontinuities are convenient to represent wh-movement, scrambling, extrapo- sition, and other linguistic phenomena common in free word order languages. While non-projective dependency parsers, which are able to model such phenomena, have been widely developed in the last decade (Nivre et al., 2007; McDonald et al., 2006; Martins et al., 2013), discontinuous con- stituent parsing is still taking its first steps (Maier and Søgaard, 2008; Kallmeyer and Maier, 2013). In this paper, we show that an off-the-shelf, trainable, dependency parser is enough to build a highly-competitive constituent parser. This (sur- prising) result is based on a reduction1 of con- stituent to dependency parsing, followed by a sim- ple post-processing procedure to recover unaries. Unlike other constituent parsers, ours does not require estimating a grammar, nor binarizing the treebank. Moreover, when the dependency parser is non-projective, our method can perform discon- tinuous constituent parsing in a very natural …

Content truncated to 500 words