Discontinuous Incremental Shift-reduce Parsing

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 1202–1212, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Discontinuous Incremental Shift-Reduce Parsing Wolfgang Maier Universit¨at D¨usseldorf Institut f¨ur Sprache und Information Universit¨atsstr. 1, 40225 D¨usseldorf, Germany maierw@hhu.de Abstract We present an extension to incremental shift-reduce parsing that handles discon- tinuous constituents, using a linear clas- sifier and beam search. We achieve very high parsing speeds (up to 640 sent./sec.) and accurate results (up to 79.52 F1 on TiGer). 1 Introduction Discontinuous constituents consist of more than one continuous block of tokens. They arise through phenomena which traditionally in linguis- tics would be analyzed as being the result of some kind of “movement”, such as extraposition or top- icalization. The occurrence of discontinuous con- stituents does not necessarily depend on the de- gree of freedom in word order that a language al- lows for. They can be found, e.g., in almost equal proportions in English and German treebank data (Evang and Kallmeyer, 2011). Generally, discontinuous constituents are ac- counted for in treebank annotation. One annota- tion method consists of using trace nodes that de- note the source of a movement and are co-indexed with the moved constituent. Another method is to annotate discontinuities directly by allowing for crossing branches. Fig. 1 shows an example for the latter approach with which we are concerned in this paper, namely, the annotation of (1). The tree contains a discontinuous VP due to the fact that the fronted pronoun is directly attached. (1) Das That wollen want wir we umkehren reverse “This is what we want to reverse” Several methods have been proposed for pars- ing such structures. Trace recovery can been Das PDS wollen VMFIN wir PPER umkehren VVINF VP S Figure 1: Example annotation with discontinuous constituents from TiGer framed as a separate pre-, post- or in-processing task to PCFG parsing (Johnson, 2002; Dienes and Dubey, 2003; Jijkoun, 2003; Levy and Manning, 2004; Schmid, 2006; Cai et al., 2011, among others); see particularly Schmid (2006) for more details. Directly annotated discontinuous con- stituents can be parsed with a dependency parser, given a reversible transformation from discontin- uous constituency trees to non-projective depen- dency structures. Transformations have been pro- posed by Hall and Nivre (2008), who use com- plex edge labels that encode paths between lexical heads, and recently by Fern´andez-Gonz´alez and Martins (2015), who use edge labels to encode the attachment order of modifiers to heads. Direct parsing of discontinuous constituents can be done with Linear Context-Free Rewriting Sys- tem (LCFRS), an extension of CFG which allows its non-terminals to cover more than one contin- uous block (Vijay-Shanker et al., 1987). LCFRS parsing is expensive: CYK chart parsing with a binarized grammar can be done in O(n3k) where k is the block degree, the maximal number of con- tinuous blocks a non-terminal can cover (Seki et al., 1991). For a typical treebank LCFRS (Maier and Søgaard, 2008), …

Content truncated to 500 words