Self Attended Stack-Pointer Networks for Learning Long Term Dependencies (2020)

Abstract: We propose a novel deep neural architecture for dependency parsing, which is built upon a Transformer Encoder (Vaswani et al. 2017) and a Stack Pointer Network (Ma et al. 2018). We first encode each sentence using a Transformer Network and then the dependency graph is generated by a Stack Pointer Network by selecting the head of each word in the sentence through a head selection process. We evaluate our model on Turkish and English treebanks. The results show that our trasformer-based model learns long term dependencies efficiently compared to sequential models such as recurrent neural networks. Our self attended stack pointer network improves UAS score around 6% upon the LSTM based stack pointer (Ma et al. 2018) for Turkish sentences with a length of more than 20 words.

## introduction dependency parsing is the task of finding the grammatical structure of a sentence by identifying syntactic and semantic relationships between words. dependency parsing has been utilized in many other nlp tasks such as machine translation @xcite , relation extraction @xcite , named entity recognition @xcite , information extraction @xcite , all of which involve natural language understanding to an extent. each dependency relation is identified between a head word and a dependent word that modifies the head word in a sentence. although such relations are considered syntactic, they are naturally built upon semantic relationships between words. for example, each dependent has a role in modifying its head word, which is a result of a semantic influence. within the context of dependency parsing, relations between heads and dependents are also la-beled by specifying the type of the grammatical relation between words. in the universal dependencies @xcite tagset, there are 37 dependency relation types defined. in the latest universal dependencies (ud v2.0) tagset, relations are split into four main categories (core arguments, non-core dependents, nominal dependents and other) and nine sub-categories (nominals, clauses, modifier words, function words, coordination, mwe, loose special and other). one way to illustrate the grammatical structure obtained from dependency parsing is a dependency graph. an example dependency graph is given below: thank you , mr. poettering . root obj punct vocative flat punct here, the relations are illustrated by the links from head words to dependent words along with their dependency labels. every sentence has a global head word, which is the root of the sentence. there are two main difficulties in dependency parsing. one is the long term dependencies in especially long sentences that are difficult to be identified in a standard recurrent neural network due to the loss of the information flow in long sequences. another difficulty in parsing is the outof-vocabulary (oov) words. in this work, we try to tackle these two problems by using transformer networks @xcite by introducing subword information for oov words in especially morphologically rich languages such as turkish. for that purpose, we integrate character-level word embeddings obtained from convolutional neural networks (cnns). the morphological complexity in such agglutinative languages makes the parsing task even harder because of the sparsity problem due to the number of suffixes that each word can take, which brings more problems in syntactic parsing. dependencies in such languages were also defined between morphemic units (i.e. inflectional groups) rather than word tokens @xcite , however this is not in the scope of this work. in this work, we introduce a novel two-level deep neural architecture for graph-based dependency parsing. graph-based dependency parsers build dependency trees among all possible trees, therefore the final dependency tree has the highest score globally. however, in transition-based dependency parsers, each linear selection in a sentence is made based on a local score which may lead to erroneous trees at the end of parsing. for this reason, we prefer graph-based dependency parsing in our approach to be able to do global selections while building dependency trees. in the first level of our deep neural architecture, we encode each sentence through a transformer network @xcite , which shows superior performance in long sequences compared to standard recurrent neural networks (rnns). in the second level, we decode the dependencies between heads and dependents using a stack pointer network @xcite , which is extended with an internal stack based on pointer networks @xcite . since stack pointer networks benefit from the full sequence similar to self attention mechanism in transformer networks, they do not have left-to-right restriction as in transition based parsing. hence, we combine the two networks to have a more accurate and efficient dependency parser. we evaluate our model on turkish which is a morphologically rich language and on english with a comparably poorer morphological structure. although our model does not outperform other recent model, it shows competitive performance among other neural dependency parsers. however, our results show that our self attended stack pointer network improves uas score around 6% upon the lstm based stack pointer @xcite for turkish sentences with a length of more than 20 words. the paper is organized as follows: section 2 reviews the related work on both graph-based and transition-based dependency parsing, section 3 explains the dependency parsing task briefly, section 4 describes the proposed deep neural architecture based on transformer networks and stack pointer networks, and finally section 5 presents the experimental results of the proposed model for both english and turkish. ## related work dependency parsing is performed by two different approaches: graph-based and transition-based parsing. we review related work on both of these approaches. graph-based dependency parsing: graphbased approaches are generally based on performing the entire parsing process as graph operations where the nodes in the graph represent the words in a sentence. for the sentence, "john saw mary", we can illustrate its parse tree with a weighted graph g with four vertices where each of them refers to a word including the root . edges store the dependency scores between the words. the main idea here is to find the maximum spanning tree of this graph g. the parse tree of the sentence is given in figure 1 . the dependencies are between root and saw, saw and john; and saw and m ary where the first ones are the heads and the latter ones are the dependents. when the parsing structure is represented as a graph, finding dependencies becomes easier to visualize, and moreover the task becomes finding the highest scored tree among all possible trees. edge scores in the graphs represent the dependency measures between word couples. neural architectures have been used for graphbased dependency parsing extensively in the last decade. @xcite introduce a seq2seq model using bi-directional lstms (bilstms) @xcite , where an attention mechanism is involved between the encoder and decoder lstms. @xcite propose another model using bilstms, where the right and left arcs in the dependency trees are identified through the bilstms. @xcite proposes a parser that uses biaffine attention mechanism, which is extended based on the models of @xcite , @xcite , and @xcite . the biaffine parser @xcite provides a baseline for other two models introduced by @xcite and @xcite , which forms trees in the form of head-driven phase structure grammar (hpsg) and uses self-attention mechanism respectively. ji et al. (2019) propose a graph neural network (gnn) that is improved upon the biaffine model. another lstm-based model is introduced by @xcite , where dependency parsing is considered as part of language modelling (lm) and each sentence is parsed with a lstm-lm architecture which builds parse trees simultaneously with the language model. the recent works generally focus on the encoder in seq2seq models because a better encoding of an input eliminates most of the cons of the sequence models. for example, @xcite and @xcite aim to improve the lstmbased encoders while @xcite introduce an attention-based approach to improve encoding, where they propose cross-view training (cvt). in this work, we encode each sentence through a transformer network based on self-attention mechanism @xcite and learn the head of each word using a stack pointer network as a decoder @xcite in our deep neural architecture. our main aim is to learn long term dependencies efficiently with a transformer network by removing the recurrent structures from encoder. transformer networks @xcite and stack pointer networks @xcite have been used for dependency parsing before. however, this will be the first attempt to combine these two methods for the dependency parsing task. transition-based dependency parsing: in transition-based dependency parsing, local selections are made for each dependency relationship without considering the complete dependency tree. therefore, globally motivated selections are normally not performed in transition-based parsing by contrast with graph-based dependency parsing. for this purpose, two stacks are employed to keep track of the actions made during transition-based parsing. similar to graph-based parsing, neural approaches have been used extensively for transitionbased parsing. @xcite introduce a feed forward neural network with various extensions by utilizing single-word, word-pair and three-word features. @xcite improve upon the model by @xcite with a deeper neural network and with a more structured training and inference using structured perceptron with beam-search decoding. @xcite use also feed forward neural networks similar to others and argue that feed forward neural networks outperform rnns in case of a global normalization rather than local normalizations as in @xcite , which apply greedy parsing. @xcite utilize a transformer network, in which graph features are employed as input and output embeddings to learn graph relations, thereby their novel model, graph2graph transformer, is introduced. @xcite propose a transition-based algorithm that is similar to the stack pointer model by @xcite ; however, left-to-right parsing is adopted on the contrary to @xcite , where top-down parsing is performed. hence, each parse tree is built in n actions for an n length sentence without requiring any additional data structure. in addition to these models, there are some works such as the greedy parser of @xcite and @xcite , and the highperformance parser by @xcite . @xcite indicate that graphbased and transition-based parsers can be also combined by integrating their features. and several works follow this idea @xcite @xcite @xcite . ## the formal definition of dependency parsing dependency parsing is the task of inferring the grammatical structure of a sentence by identifying the relationships between words. dependency is a head-dependent relation between words and each dependent is affected by its head. the dependencies in a dependency tree are always from the head to the dependents. the parsing, no matter which approach is used, creates a dependency tree or a graph, as we mentioned above. there are some formal conditions of this graph: a dependency tree is projective if there are no crossing edges on the dependency graph. figure 2 illustrates a projective tree and figure 3 illustrates a non-projective dependency graph. ## conclusion & future work our experiments show that using self-attention mechanism increases parsing accuracy especially in longer sentences in turkish. however, our parser requires more data to learn better for also shorter sentences. the results also show that using character level word embeddings along with word embeddings and pos tag embeddings gives the highest accuracy for our model. we leave integrating morpheme-level information in especially morphologically rich languages such as turkish as future work.