Seq2seq Dependency Parsing

Proceedings of the 27th International Conference on Computational Linguistics, pages 3203–3214 Santa Fe, New Mexico, USA, August 20-26, 2018. 3203 Seq2seq Dependency Parsing Zuchao Li1,2, Jiaxun Cai1,2, Shexia He1,2, Hai Zhao1,2∗ 1Department of Computer Science and Engineering, Shanghai Jiao Tong University 2Key Laboratory of Shanghai Education Commission for Intelligent Interaction and Cognitive Engineering, Shanghai Jiao Tong University, Shanghai, China {charlee, caijiaxun, heshexia}@sjtu.edu.cn, zhaohai@cs.sjtu.edu.cn Abstract This paper presents a sequence to sequence (seq2seq) dependency parser by directly predicting the relative position of head for each given word, which therefore results in a truly end-to-end seq2seq dependency parser for the first time. Enjoying the advantage of seq2seq modeling, we enrich a series of embedding enhancement, including firstly introduced subword and node2vec augmentation. Meanwhile, we propose a beam search decoder with tree constraint and sub- root decomposition over the sequence to furthermore enhance our seq2seq parser. Our parser is evaluated on benchmark treebanks, being on par with the state-of-the-art parsers by achieving 94.11% UAS on PTB and 88.78% UAS on CTB, respectively. 1 Introduction Dependency parsing for syntactic structure can be unstrictly put into two categories in terms of searching strategies over parsing trees, graph-based and transition-based. The previous work (Eisner, 1996; Mc- donald et al., 2005) searched the entire tree space but limited to local features with higher computational costs, while (Nivre, 2003) could adopt rich features but subjected to limited searching space. Besides, ensemble or hybrid methods on both the basic models have been well studied (Nivre and Mcdonald, 2008; Zhang and Clark, 2008). Most traditional dependency parsers rely heavily on feature engineering, especially for graph-based parser, which suffers from poor efficiency and generalization ability. Re- cent tendency for dependency parsing is adopting neural networks due to their significant success in a wide range of applications. Specially, leveraging sequence-to-sequence (seq2seq) model for dependency parsing started to appear (Wiseman and Rush, 2016; Zhang et al., 2017b). The recently proposed seq2seq parsers focus on predicting a transition sequence to build a depen- dency tree, which makes them actually fall back into the transition-based model constrained by the adopted transition parsing algorithm. In this paper, we propose a seq2seq parser with a novel parsing structure encoding independent of transition parsing operation sequence. The proposed parser first di- rectly generates the head position for each word in an input sentence using a seq2seq model, and then employs a BiLSTM-CRF model (Huang et al., 2015) to predict the relation label for each determined dependency arc. Since the greatest challenge of the applying seq2seq model in dependency parsing is to guarantee the tree structure of the outputs, a beam search with tree constraint method is proposed to enforce a well-formed dependency tree in the decoder side. Besides, dependency parsing has to well handle long-distance parsing with corresponding to too long sequence learning bias in seq2seq models, we accordingly introduce a sub-root based sequence decomposition to effectively alleviate this issue. Our proposed parser is evaluated on benchmark treebanks on both English and Chinese, which demon- strates that our …

Content truncated to 500 words