Neural Discontinuous Constituency Parsing

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1666–1676 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Neural Discontinuous Constituency Parsing Miloˇs Stanojevi´c and Raquel G. Alhama Institute for Logic, Language and Computation (ILLC) University of Amsterdam {m.stanojevic, rgalhama}@uva.nl Abstract One of the most pressing issues in dis- continuous constituency transition-based parsing is that the relevant information for parsing decisions could be located in any part of the stack or the buffer. In this pa- per, we propose a solution to this prob- lem by replacing the structured percep- tron model with a recursive neural model that computes a global representation of the configuration, therefore allowing even the most remote parts of the configura- tion to influence the parsing decisions. We also provide a detailed analysis of how this representation should be built out of sub-representations of its core elements (words, trees and stack). Additionally, we investigate how different types of swap or- acles influence the results. Our model is the first neural discontinuous constituency parser, and it outperforms all the previ- ously published models on three out of four datasets while on the fourth it obtains second place by a tiny difference. 1 Introduction Research on constituency parsing has been mostly concentrated on projective trees, which can be modeled with Context-Free Grammars (CFGs). One of the main reasons for this is that modeling non-projective trees often requires richer gram- mar formalisms, which in practice implies slower runtime. For instance, the parsing algorithms for binary LCFRS—the most prominent grammar- based approach to parsing non-projective con- stituency trees—have computational complexity O(n3k), where k is the fan-out of the grammar. For this reason, researchers turned to faster ap- proximate methods. Approximations can be done in two ways: either on the types of structures that are predicted or on the parsing algorithm. The first approach approximates discontinu- ous constituency structures with simpler structures for which more efficient algorithms exist. This method works as a pipeline: it converts the input to a simpler formalism, parses with it, and then con- verts it back. Relevant examples are the parsers by Hall and Nivre (2008) and Fern´andez-Gonz´alez and Martins (2015), who convert discontinuous constituents to dependencies, and Versley (2016), who also applied a conversion but in this case to the projective constituency trees. The second approach—approximation on the parsing algorithm—consists of an approximate search for the most probable parse. This is analogous to the search done by transition-based parsers, which greedily search through the space of all possible parses, resulting in very fast mod- els. The first transition-based discontinuous con- stituency parser of this sort was presented in Vers- ley (2014), and it consists of a shift-reduce parser that handles discontinuities with swap transitions. This parser was very similar to dependency parsers with swap transitions (Nivre, 2009; Nivre et al., 2009), but unlike its dependency equivalents, it did not exhibit higher accuracy. Later work on discon- tinuous transition-based parsing was largely fo- cused on finding alternative transitioning systems to …

Content truncated to 500 words