A Unified Encoding of Structures in Transition Systems (2021)

Abstract: Transition systems usually contain various dynamic structures (e.g., stacks, buffers). An ideal transition-based model should encode these structures completely and efficiently. Previous works relying on templates or neural network structures either only encode partial structure information or suffer from computation efficiency. In this paper, we propose a novel attention-based encoder unifying representation of all structures in a transition system. 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 significantly improves the test speed and achieves the best transition-based model, and is comparable to state-of-the-art methods.

## introduction transition systems have been successfully applied in many fields of nlp, especially parsing (dependency parsing @xcite , constituent parsing @xcite , and semantic parsing @xcite ). basically, a transition system takes a series of actions which attach or detach 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 transition 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 encode transition system structures completely and efficiently. however, challenges appear when we try to have the cake and eat it. for example, traditional template-based methods @xcite are fast, but only encode partial information of structures (e.g., few top items on stacks and buffers). structure-based networks (e.g., stack-rnn @xcite ) rely on carefully designed network architecture to get a full encoding of structures (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). furthermore, 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 encoders. 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 inspect items in each structure, which are ultimate targets for any structure encoder. one key observation is that every item has two-views, namely structure-invariant view which is unchanged when the item is placed on different structures, and structure-dependent view which reflects which part of which structure the item stands. for example, when a word w (item) is on the buffer (structure), its structure-invariant view could contain its lexical form and part-of-speech tag, while its structure-dependent view indicates that w is now sitting on the buffer and its distance to the buffer head is p. when w is detached from buffer and attached to the stack, its structure-dependent view will switch to "sitting on the stack" while its structure-invariant view stay unchanged. a unified structure encoder thus suffices to uniformly encode both views. for the structure-invariant view, we share them among different structures, thus it is automatically unified. for the structure-dependent view, we propose a simple yet powerful encoder. it assigns each structure a set of indicating vectors (structure indicators), each indicator specifies certain part of that structure. for example, we use indicators (vectors) to expressing "on top of the stack", "the second position of the buffer", and "index of head words in partial trees". to encode an item, we only need to concatenate its structure-invariant encoding and corresponding indicators according to its position in that structure. regarding completeness and efficiency, we find that with structure indicators, it is relatively easy to encode a structure completely: one only needs to decompose the structure into identifiable subparts. in fact, we can use them to track some parts of structures which are not revealed in previous work (e.g., words have been popped out from stacks). it runs in the same manner as templated-based models, thus the decoding efficiency is guaranteed. we also note that using structure indicator is different from existing ways to include structure information into neural network models @xcite @xcite : it encodes dynamical structures (changing with transition system running) rather than static structures (e.g., fixed parse trees). we can easily implement the unified structure encoding with existing multi-head attention networks (mha, @xcite ). it is also easy to fuse encodings of different structures with multilayer mha. we conduct experiments on the english penn treebank 3.0 and universal dependencies v2.2, show that the unified structure encoder is able to help us achieving state-of-the-art transitionbased parser (even competitive to the best graphbased parser), while retaining a fast training and testing speed. ## transition systems we briefly review transition-based dependency parsing. given a sentence @xmath0, w 1 , • • • , w n (root 0 is a synthetic word) and a relation set r, we denote a dependency tree for x to be {(i, j, r)}, where (i, j, r) represents a dependency relation @xmath1. a transition system is a sound quadruple @xmath2. we will use the grey row as an example for the structural indicator. a is the set of actions, c x is an initialization function mapping x to a unique initial configuration, and c t ⊆ c is a set of terminal configurations. given a configuration @xmath3, a transition-based parser aims to predict a correct action @xmath4. we specifically describe the arc-hybrid system @xcite . in this system, each configuration @xmath5, j|β, t) aggregates information from three structures, namely a stack (σ, where σ|i denotes the stack top is w i ), a buffer (β, where j|β denotes the buffer front is w j ) and a partial tree (t). the actions of arc-hybrid are formalized as (a running example is shown in figure 2 ): there are three actions, sh moves the front item of the buffer (w i ) to the top item of the stack. la r removes the top item the stack w i , attaches it as a dependent to w j with label r, and adds a left-arc (j, i, r) to the partial tree. ra r removes the top of the stack w j attaches it as a dependent to w i with label r, and adds a right-arc (i, j, r) to the partial tree. we note that all actions are actually attaching or detaching item to or from structures, where an item could be a word (in stack and buffer) or an edge (in the partial tree). note that besides structures in the configurations, we can also incorporate other structures to help learning action predictors. for example, we can consider the history action list which contain all previous actions in a sequential manner. in this case, an item in this action list is an action label. ## two views of an item we can see that, while its "content" remains the same, an item may appear in different structures in a transition system's configurations. to uniformly encode an item (and thus structures containing them), we can decouple the encoding of contents and structures, then combine them in a unified way. this simple method also suggests us to design unified structure encoders which make the whole transition system model concise and efficient. the structure-invariant view typically captures the lexical (shallow) form of an item. for example, in the arc-hybrid system, items in stacks and buffers have words as their structure-invariant view, items in action list have actions as their structureinvariant view. this view is shared when the item moving from one structure to another, and we only need to encode it once (e.g., no matter the stack or the buffer a word appears, its structure-invariant representation is identical). we describe how to encode this view in section 4.3. the more interesting problem is how to characterize the structure-dependent view. we would like to have a unified strategy to represent those structures. our major tool is structure indicators, which are basically a set of vectors bounded to each structure. taking the stack for example. we use vectors to indicate "the top of stack" (we name the vector with "1 σ "), "the second to the stack top" (naming with "2 σ "). vector "0 σ " indicates the parts haven't been in the stack. different with previous work, we could also represent "the previous stack top which has been popped" (a vector naming by "-1 σ "), and "the previous previous stack top" (a vector naming by "-2 σ "). that is, for different parts of the structure, we employ vectors to indicate them. similarly, for the buffer we have another set of structure indicators {1 β , -1 β , 2 β , -2 β • • • }, where a positive number indicates the position in the buffer, a negative number indicates the time step passed since the item has been removed from the buffer. for the partial tree with dependency relation, we decompose it into two structures, the tree arc (t arc ) and the dependency relation (t indicates the ids of dependency relations. vectors "0 tarc " and "0 t rel " indicate that this dependency edge is not in partial tree. for the action list we have a set of structure indicators {1 a , 2 a , • • • } where a vector incicates the position in the list. in figure 3 , we show the two-views of an instance from the 4th step in figure 2 . we can observe that the five different structures mentioned above have a unified form now. 4 the unified structure encoder 4.1 encoding with use when a transition system is running at moment t, the parser needs to capture as much information as possible about the current configuration to determine which is the correct action. the key is to encode the configuration containing many structures concisely and efficiently. we propose a unified structure encoder (use) by using multi-head selfattention networks @xcite . each head extracts a feature vector of one structure (e.g., o σ for the stack). a common use function maps a query and a set of key-value pairs to an output. the query vector q represents the current time step and data structure. the key-value pairs both represent two-views of the structure. the output vector o is calculated as a weighted sum of values, where the weight assigned to each value is calculated by a scaled ( 1 it is universal for different structures. take the stack σ for example, we calculate the feature vector o σ,t by assigning the q σ,t , k σ,t , and v σ,t : when the system comes to the next moment t+1, we use the m t+1 , s k σ,t+1 and s v σ,t+1 for an updated configuration. for the other four structures, we calculate their feature vectors o β,t , o α,t , o tarc,t , and o t rel ,t by assigning the corresponding q, k, and v , respectively foot_1 . ## the action classifier the action set a is first divided into three main types: sh, la and ra, then divided into |r| dependency labels only for la and ra actions. thus we perform a two-stage process with 3-class and |r|-class classifications. it effectively reduces the classification space compared with one-stage process. for example, the space of a sh action is 3-class in two-stage process while 2|r|+1 class in one-stage process. to classify the dependency label r between word i and j, based on the lexical representations x i , x j and c (l) t , we follow @xcite which uses a biaffine score function to predict the label's probability, where w 1 is a 3-dimensional parameter tensor, w 2 is a parameter matrix, and b is a parameter vector foot_2 . a slight difference is that we induce c (l) t to model the prior probability of each label under the current configuration. ## interprete the features since a transition system contains various structures, a natural question is which part of structures are important for the parser? to show the importance of a variable, one standard approach is using partial derivatives multiplied by the variable's value @xcite . hence, the importance score ( ) of a structural indicator is a dot product between objective function gradient and indicator embedding: concretely, (σ, i) shows the relevance between the stack indicator i and the decision of our parser. the importance at indicator i of any structure can be derived similarly. we can further accumulate multiple items' relevance. for example, stack inside relevance in (σ) = @xmath6, i), stack outside relevance out (σ) = @xmath7, i), etc. in the experiments, we explain the importance of each structure part by score. data we conduct experiments and analysis on two main datasets including 12 languages: the english penn treebank (ptb 3.0) with stanford dependencies, and the universal dependencies (ud 2.2) (nivre et al., 2018) treebanks used in conll 2018 shared task (zeman et al., 2018). the statistics of datasets are in appendix c. for ptb, we use the standard train/dev/test splits and the external pos tags obtained by the stanford tagger (accuracy ≈ 97.3%). following ji et al. (2019), we select 12 languages from ud, and use conll shared task's official train/dev/test splits, where the pos tags were assigned by the udpipe @xcite . evaluation we mainly report unlabeled (uas) and labeled attachment scores (las). for evaluations on ptb, five punctuation symbols (" " : , .) are excluded, while on ud, we use the official evaluation script. hyper-parameters for structure-invariant part, we directly adopt most parameter settings of @xcite and @xcite , including pretrained embeddings, bilstm, and charcnn. for structure-dependent part, we use a total of 8 structural heads, allocating two each for the stack, buffer and action list, one for the subtree's edges and one for the edges' labels. our pre-experiments show that stacking 6 layers of use yields the best results. the weight λ of the objective function is assigned to 0.5. we trained our parser for up to 1k ## related work we have already surveyed related transition system encoder in section 4.2. here we present several powerful transition-based parsers. ma et al. (2018) decode a parse tree step-by-step based on a depthfirst traversal order. a stack is usually used to maintain the depth-first search. thus they use a stackpointer network for decoding. note that their work is not based on any transition systems. @xcite propose a bidirectional decoding method for a stack-lstms transition-based parser. they perform joint decoding with a left-to-right parser and a right-to-left parser. @xcite propose a graph2graph framework for enhancing expression by treating multiple structures as multiple sentences and using a transformer encoder (bert) to encode top-k words. these works focus on improving the decoding approach or representation learning of structure-invariant parts, but still follow the traditional encoders. our work focuses on proposing a new encoder with both information completeness and computational effectiveness. there have been several attempts to combine attention networks with structures: to represent the sequential structure better, @xcite introduce relative position between words in attention networks instead of concatenating absolute position in input. @xcite define the relative positions on parse trees to encode each word pair's tree distance. they feed these positional embeddings to attention networks too. these two works encode a static structure, while we encode a dynamically changing transition system. shiv and quirk (2019) extend the transformer's sinusoidal position function to the tree structure. similar to us, their decoder dynamically computes the new position encoding when generating a tree structure. but their structural embeddings are computed by fixed sinusoidal function, while ours are learnable. these works encode only one structure, while we encode multiple structures from a transition sys-tem. ## conclusion we presented a comprehensive and efficient encoder for transition system. we separate each structure to the structure-invariant part and structuredependent part. it allows us to dynamically encode the complete structure and also retains the efficiency of training and testing. experiments show that the proposed parser achieves new state-of-theart transition-based results. taro watanabe and eiichiro sumita. 2015. transitionbased neural constituent parsing. in proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: long papers), pages 1169-1179, beijing, china. association for computational linguistics. david weiss, chris alberti, michael collins, and slav petrov. 2015. structured training for neural network transition-based parsing. in proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing of the asian federation of natural language processing, acl 2015, july 26-31, 2015, beijing, china, volume 1: long papers, pages 323-333. pengcheng yin and graham neubig. 2018. tranx: a transition-based neural abstract syntax parser for semantic parsing and code generation. in proceedings of the 2018 conference on empirical methods in natural language processing, emnlp 2018: system demonstrations, brussels, belgium, october 31 -november 4, 2018, pages 7-12. association for computational linguistics. yunzhe yuan, yong jiang, and kewei tu. 2019. bidirectional transition-based dependency parsing. in