Transition-based Semantic Dependency Parsing with Pointer Networks (2020)

Abstract: Transition-based parsers implemented with Pointer Networks have become the new state of the art in dependency parsing, excelling in producing labelled syntactic trees and outperforming graph-based models in this task. In order to further test the capabilities of these powerful neural networks on a harder NLP problem, we propose a transition system that, thanks to Pointer Networks, can straightforwardly produce labelled directed acyclic graphs and perform semantic dependency parsing. In addition, we enhance our approach with deep contextualized word embeddings extracted from BERT. The resulting system not only outperforms all existing transition-based models, but also matches the best fully-supervised accuracy to date on the SemEval 2015 Task 18 datasets among previous state-of-the-art graph-based parsers.

## introduction in dependency parsing, the syntactic structure of a sentence is represented by means of a labelled tree, where each word is forced to be attached exclusively to another that acts as its head. in contrast, semantic dependency parsing (sdp) @xcite aims to represent binary predicate-argument relations between words of a sentence, which requires producing a labelled directed acyclic graph (dag): not only semantic predicates can have multiple or zero arguments, but words from the sentence can be attached as arguments to more than one head word (predicate), or they can be outside the sdp graph (being neither a predicate nor an argument) as shown in the examples in figure 1 . since existing dependency parsers cannot be directly applied, most sdp research has focused on adapting them to deal with the absence of singlehead and connectedness constraints and to produce an sdp graph instead. as in dependency parsing, we can find two main families of approaches to efficiently generate accurate sdp graphs. on the one hand, graph-based algorithms have drawn more attention since adapting them to this task is relatively straightforward. in particular, these globally optimized methods independently score arcs (or sets of them) and then search for a high-scoring graph by combining these scores. from one of the first graph-based dag parsers proposed by @xcite to the current state-of-the-art models @xcite , different graph-based sdp approaches have been presented, providing accuracies above their main competitors: transitionbased dag algorithms. a transition-based parser generates a sequence of actions to incrementally build a valid graph (usually from left to right). this is typically done by local, greedy prediction and can efficiently parse a sentence in a linear or quadratic number of actions (transitions); however, the lack of global inference makes them more prone to suffer from error propa-gation: i.e., since transitions are sequentially and locally predicted, an erroneous action can affect future predictions, having a significant impact in long sentences and being, to date, less appealing for sdp. in fact, in recent years only a few contributions, such as the system developed by @xcite , present a purely transition-based sdp parser. it is more common to find hybrid systems that combine transition-based approaches with graph-based techniques to alleviate the impact of error propagation in accuracy @xcite , but this penalizes the efficiency provided by transition-based algorithms. away from the current mainstream, we present a purely transition-based parser that directly generates sdp graphs without the need of any additional techniques. we rely on pointer networks @xcite to predict transitions that can attach multiple heads to the same word and incrementally build a labelled dag. this kind of neural networks provide an encoder-decoder architecture that is capable of capturing information from the whole sentence and previously created arcs, alleviating the impact of error propagation and already showing remarkable results in transition-based dependency parsing @xcite . we further enhance our neural network with deep contextualized word embeddings extracted from the pre-trained language model bert @xcite . the proposed sdp parser foot_0 can process sentences in sdp treebanks (where structures are sparse dags with a low in-degree) in o(n 2 log n) time, or o(n 2 ) without cycle detection. this is more efficient than the current fully-supervised state-of-theart system by @xcite (o(n 3 ) without cycle detection), while matching its accuracy on the semeval 2015 task 18 datasets @xcite . in addition, we also prove that our novel transition-based model provides promising accuracies in the semi-supervised scenario, achieving some state-of-the-art results. ## related work an early approach to dag parsing was implemented as a modification to a graph-based parser by @xcite . this produced dags using approximate inference by first finding a dependency tree, and then adding extra edges that would increase the graph's overall score. a few years later, this attempt was outperformed by the first transition-based dag parser by @xcite . they extended the existing transition system by @xcite to allow multiple heads per token. the resulting algorithm was not able to produce dags with crossing dependencies, requiring the pseudo-projective transformation by @xcite (plus a cycle removal procedure) as a post-processing stage. more recently, there has been a predominance of purely graph-based dag models since the se-meval 2015 task 18 @xcite . almeida and @xcite adapted the pre-deep-learning dependency parser by @xcite to produce sdp graphs. this graph-based parser encodes higher-order information with hand-crafted features and employs the ad 3 algorithm @xcite to find valid dags during decoding. this was extended by @xcite with bilstm-based feature extraction and multitask learning: the three formalisms considered in the shared task were jointly learned to improve final accuracy. after the success of @xcite in graphbased dependency parsing, @xcite proposed minor adaptations to use this biaffine neural architecture to produce sdp graphs. to that end, they removed the maximum spanning tree algorithm @xcite necessary for decoding well-formed dependency trees and simply kept those edges with a positive score. in addition, they trained the unlabelled parser with a sigmoid cross-entropy (instead of the original softmax one) in order to accept multiple heads. the parser by @xcite was recently improved by two contributions. firstly, @xcite manage to add second-order information for score computation and then apply either mean field variational inference or loopy belief propagation information to decode the highestscoring sdp graph. while significantly boosting parsing accuracy, the original o(n 2 ) runtime complexity is modified to o(n 3 ) in the resulting sdp system. secondly, @xcite significantly improve the original parser's accuracy by not only using contextualized word embeddings extracted from bert @xcite , but also introducing contextual string embeddings (called flair) @xcite , which consist in a novel type of word vector representations based on character-level language modeling. both extensions, @xcite and @xcite , are currently the state of the art on the semeval 2015 task 18 in the fully-supervised and semi-supervised scenarios, respectively. @xcite have also recently proposed a complex approach that iteratively applies the syntactic dependency parser by @xcite , sequentially building a dag structure. at each iteration, the graph-based parser selects the highest-scoring arcs, keeping the single-head constraint. the process ends when no arcs are added in the last iteration. the combination of partial parses results in an sdp graph. since the graph is built in a sequential process, they use reinforcement learning to guide the model through more optimal paths. following @xcite , multi-task learning is also added to boost final accuracy. on the other hand, the use of transition-based algorithms in the sdp task had been less explored until very recently. @xcite presented a voting-based ensemble of fourteen graph-and transition-based parsers. in their work, they noticed that individual graph-based models outperform transition-based algorithms, assigning, during voting, higher weights to them. among the transition systems used, we can find the one developed by @xcite , which is not able to cover all sdp graphs. we have to wait until the work by @xcite to see that a purely transition-based sdp parser (enhanced with a simple model ensemble technique) can achieve competitive results. they simply modified the preconditions of the complex transition system by @xcite to produce unrestricted dag structures. in addition, their system was implemented by means of stack-lstms @xcite , enhanced with bilstms and tree-lstms for feature extraction. we are, to the best of our knowledge, first to explore dag parsing with pointer networks, proposing a purely transition-based algorithm that can be a competitive alternative to graph-based sdp models. finally, during the reviewing process of this work, the proceedings of the conll 2019 shared task @xcite were released. in that event, sdp parsers were evaluated on updated versions of semeval 2015 task 18 datasets, as well as on datasets in other semantic formalisms such as abstract meaning representation (amr) @xcite and universal cognitive conceptual annotation (ucca) @xcite . although graph-based parsers achieved better accuracy in the sdp track, several bert-enhanced transition-based approaches were proposed. among them we can find an extension @xcite of the system by @xcite , several adaptations for sdp @xcite of the transition-based ucca parser by @xcite , as well as an sdp variant @xcite of the constituent transition system introduced by @xcite . also in parallel to the development of this research, @xcite proposed a transition-based parser that, while it can be applied for sdp, was specifically designed for amr and ucca parsing (where graph nodes do not correspond with words and must be generated during the parsing process). in particular, this approach incrementally builds a graph by predicting at each step a semantic relation composed of the target and source nodes plus the arc label. while this can be seen as an extension of our approach for those tasks where nodes must be generated, its complexity penalizes accuracy in the sdp task. ## multi-head transition system we design a novel transition system that is able to straightforwardly attach multiple heads to each word in a single pass, incrementally building, from left to right, a valid sdp graph: a labelled dag. to implement it, we use pointer networks @xcite . these neural networks are able to learn the conditional probability of a sequence of discrete numbers that correspond to positions in an input sequence and, at decoding time, perform as a pointer that selects a position from the input. in other words, we can train this neural network to, given a word, point to the position of the sentence where its head @xcite or dependent words @xcite are located, depending on what interpretation we use during training. in particular, @xcite proved to be more suitable for dependency parsing than @xcite since it requires half as many steps to produce the same dependency parse, being not only faster, but also more accurate (as this mitigates the impact of error propagation). inspired by @xcite , we train a pointer network to point to the head of a given word and propose an algorithm that does not use any kind of data structures (stack or buffer, required in classic transitionbased parsers @xcite ), but just a focus word pointer i for marking the word currently being processed. more in detail, given an input sentence of n words w 1 , . . . , w n , the parsing process starts with i pointing at the first word w 1 . at each time step, the current focus word w i is used by the pointer network to return a position p from the input sentence (or 0, where the root node is located). this information is used to choose between the two available transitions: the parsing ends when the last word from the sentence is shifted, meaning that the input is completely processed. as stated by @xcite for attaching dependent words, it is necessary to fix the order in which (in our case, head) words are assigned in order to define a deterministic decoding. as the sentence is parsed in a left-to-right manner, we adopt the same order for head assignments. for instance, the sdp graph in figure 1(a ) is produced by the transition sequence described in it is worth mentioning that we manage to significantly reduce the amount of transitions necessary for generating dags in comparison to those proposed in the complex transition systems by @xcite and @xcite , used in the sdp systems by @xcite and @xcite , respectively. in addition, the described multi-head transition system is able to directly produce any dag structure without exception, while some transition systems, such as the mentioned @xcite , are limited to a subset of dags. finally, while the outcome of the proposed transition system is a sdp graph without cycles, in other research, such as @xcite and state-of-the-art models by @xcite and @xcite , the parser is not forced to produce well-formed dags, allowing the presence of cycles. we follow previous work in dependency parsing @xcite to design our neural architecture: @xcite is used to encode the input sentence w 1 , . . . , w n , word by word, into a sequence of encoder hidden states h 1 , . . . , h n . cnns with max pooling are used for extracting character-level representations of words and, then, each word w i is represented by the concatenation of character (e c i ), word (e w i ), lemma (e l i ) and pos tag (e p i ) embeddings: after that, the x i of each word w i is fed one-by-one into a bilstm that captures context information in both directions and generates a vector representation h i : in addition, a special vector representation h 0 , denoting the root node, is prepended at the beginning of the sequence of encoder hidden states. decoder an lstm is used to output, at each time step t, a decoder hidden state s t . as input of the decoder, we use the encoder hidden state h i of the current focus word w i plus extra high-order features. in particular, we take into account the hidden state of the last head word (h h ) attached to w i , which will be a co-parent of a future predicate assigned to w i . following @xcite , we use element-wise sum to add this information without increasing the dimensionality of the input: note that feature information like this can be easily added in transition-based models without increasing the parser's runtime complexity, something that does not happen in graph-based models, where, for instance, the second-order features added by @xcite penalize runtime complexity. we experimented with other high-order features such as grandparent or sibling information of the current focus word w i , but no significant improvements were obtained from their addition, so they were discarded for simplicity. further feature exploration might improve parser performance, but we leave this for future work. once s t is generated, the attention vector a t , which will work as a pointer over the input, must be computed in the pointer layer. first, following the previously cited work, the scores between s t and each encoder hidden representation h j from the input sentence are computed using this biaffine attention scoring function @xcite : the resulting attention vector a t can now be used as a pointer to select the highest-scoring position p from the input. this information will be employed by the transition system to choose between the two available actions and create a predicate-argument relation between w p and w i (attach-p) or move the focus word pointer to w i+1 (shift). in case the chosen attach-p is forbidden due to the acyclicity constraint, the next highest-scoring position in a t is considered as output instead. figure 2 depicts the neural architecture and the decoding procedure for the sdp structure in figure 1(a) . ## conclusions and future work our multi-head transition system can accurately parse a sentence in quadratic worst-case runtime thanks to pointer networks. while being more efficient, our approach outperforms the previous stateof-the-art parser by @xcite and matches the accuracy of the best model to date @xcite , proving that, with a state-ofthe-art neural architecture, transition-based sdp parsers are a competitive alternative. by adding bert-based embeddings, we significantly improve our model accuracy by marginally affecting computational cost, achieving state-ofthe-art f-scores in out-of-domain test sets. despite the promising results, the accuracy of our approach could probably be boosted further by experimenting with new feature information and specifically tuning hyper-parameters for the sdp task, as well as using different enhancements such as implementing the hierarchical decoding recently presented by @xcite , including contextual string embeddings @xcite like @xcite , or applying multi-task learning across the three formalisms like @xcite .