A Unified Encoding of Structures in Transition Systems

Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 4121–4133 November 7–11, 2021. c⃝2021 Association for Computational Linguistics 4121 A Unified Encoding of Structures in Transition Systems Tao Ji∗, Yong Jiang, Tao Wang, Zhongqiang Huang, Fei Huang, Yuanbin Wu, Xiaoling Wang School of Computer Science and Technology, East China Normal University DAMO Academy, Alibaba Group {taoji@stu,ybwu@cs,xlwang@cs}.ecnu.edu.cn {yongjiang.jy,leeo.wangt,z.huang,f.huang}@alibaba-inc.com Abstract Transition systems usually contain various dy- namic structures (e.g., stacks, buffers). An ideal transition-based model should encode these structures completely and efficiently. Previous works relying on templates or neu- ral network structures either only encode par- tial structure information or suffer from com- putation efficiency. In this paper, we propose a novel attention-based encoder unifying rep- resentation of all structures in a transition sys- tem. Specifically, we separate two views of items on structures, namely structure-invariant view and structure-dependent view. With the help of parallel-friendly attention network, we are able to encoding transition states with O(1) additional complexity (with respect to basic feature extractors). Experiments on the PTB and UD show that our proposed method signif- icantly improves the test speed and achieves the best transition-based model, and is compa- rable to state-of-the-art methods. 1 1 Introduction Transition systems have been successfully applied in many fields of NLP, especially parsing (depen- dency parsing (Nivre, 2008), constituent parsing (Watanabe and Sumita, 2015), and semantic pars- ing (Yin and Neubig, 2018)). Basically, a transition system takes a series of actions which attach or de- tach some items (e.g., sentence words, intermediate outputs) to or from some structures (e.g., stacks, buffers, partial trees). Given a set of action series, a classifier is trained to predict the next action given a current configuration of structures in the transi- tion system. The performances of the final system strongly depend on how well the classifier encodes those transition system configurations. Ideally, a good configuration encoder should en- code transition system structures completely and ∗This work was conducted when Tao Ji was interning at Alibaba DAMO Academy. 1https://github.com/AntNLP/trans-dep-parser. update configuration stack buffer action input output subtree s-invariant s-dependent action classifier action Figure 1: An overview of our transition-based parser. efficiently. However, challenges appear when we try to have the cake and eat it. For example, tradi- tional template-based methods (Chen and Manning, 2014) are fast, but only encode partial informa- tion of structures (e.g., few top items on stacks and buffers). Structure-based networks (e.g., Stack- RNN (Dyer et al., 2015)) rely on carefully designed network architecture to get a full encoding of struc- tures (actually, they still miss some off-structure information, see our discussions in Section 4.2), but they are usually slow (e.g., not easy to batch). Fur- thermore, different structures have different ways of update (stacks are first-in-last-serve, buffers are first-in-first-serve), it also takes efforts to design different encoders and ways of fusing those en- coders. In this work, we aim to provide a unified encoder for different transition system structures. Instead of inspecting different structures individually, to unify the encoding, we turn to …

Content truncated to 500 words