Left-corner Transitions on Dependency Parsing

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 2140–2150, Dublin, Ireland, August 23-29 2014. Left-corner Transitions on Dependency Parsing Hiroshi Noji and Yusuke Miyao Department of Informatics The Graduate University for Advanced Studies National Institute of Informatics, Tokyo, Japan {noji,yusuke}@nii.ac.jp Abstract We propose a transition system for dependency parsing with a left-corner parsing strategy. Unlike parsers with conventional transition systems, such as arc-standard or arc-eager, a parser with our system correctly predicts the processing difficulties people have, such as of center-embedding. We characterize our transition system by comparing its oracle behaviors with those of other tran- sition systems on treebanks of 18 typologically diverse languages. A crosslinguistical analysis confirms the universality of the claim that a parser with our system requires less memory for parsing naturally occurring sentences. 1 Introduction It is sometimes argued that transition-based dependency parsing is appealing not only from an engi- neering perspective due to its efficiency, but also from a scientific perspective: These parsers process a sentence incrementally similar to a human parser, which have motivated several studies concerning their cognitive plausibility (Nivre, 2004; Boston and Hale, 2007; Boston et al., 2008). A cognitively plausible dependency parser is attractive for many reasons, one of the most important being that dependency tree- banks are available in many languages, so it is suitable for crosslinguistical studies of human language processing (Keller, 2010). However, current transition systems based on shift-reduce actions fully or partially employ a bottom-up strategy1, which is problematic from a psycholinguistical point of view: Bottom-up or top-down strategies are known to fail in predicting the difficulty for certain sentences, such as center-embedding, which people have troubles in comprehending (Abney and Johnson, 1991). We propose a transition system for dependency parsing with a left-corner strategy. For constituency parsing, unlike other strategies, the arc-eager left-corner strategy is known to correctly predict processing difficulties people have (Abney and Johnson, 1991). To the best of our knowledge, however, the idea of left-corner strategy has not been introduced in the dependency parsing literature. We define the memory cost for a transition system as the number of unconnected subtrees on a stack. Under this condition, the proposed system incurs non-constant memory cost only when encountering center-embedded structures. After developing the transition system, we characterize it by looking into the following question: Is it true that naturally occurring sentences can be parsed on this system with a lower memory overhead? This should be true under the assumptions that 1) people avoid generating a sentence that causes diffi- culty for them, and 2) center-embedding is a kind of such structure. Specifically, we focus on analyzing the oracle transitions of the system, i.e., parser actions to recover the gold dependency tree for a sen- tence. In English, it is known that left-corner transformed treebank sentences can be parsed with less memory (Schuler et al., 2010), but our focus in this paper is on the language universality of the claim in a crosslingual setting. Two different but relevant motivations …

Content truncated to 500 words