Bracketing Encodings for 2-Planar Dependency Parsing (2020)

Abstract: We present a bracketing-based encoding that can be used to represent any 2-planar dependency tree over a sentence of length n as a sequence of n labels, hence providing almost total coverage of crossing arcs in sequence labeling parsing. First, we show that existing bracketing encodings for parsing as labeling can only handle a very mild extension of projective trees. Second, we overcome this limitation by taking into account the well-known property of 2-planarity, which is present in the vast majority of dependency syntactic structures in treebanks, i.e., the arcs of a dependency tree can be split into two planes such that arcs in a given plane do not cross. We take advantage of this property to design a method that balances the brackets and that encodes the arcs belonging to each of those planes, allowing for almost unrestricted non-projectivity (∼99.9% coverage) in sequence labeling parsing. The experiments show that our linearizations improve over the accuracy of the original bracketing encoding in highly non-projective treebanks (on average by 0.4 LAS), while achieving a similar speed. Also, they are especially suitable when PoS tags are not used as input parameters to the models.

## introduction in the last few years, approaches that cast syntactic parsing as the task of finding a sequence have gained traction for both dependency and constituency parsing. in sequence-to-sequence (seq2seq) parsing @xcite , parse trees are represented as arbitrary-length sequences, where the attention mechanism can be seen as an abstraction of the stack and the buffer in transition-based systems that decides what words are relevant to make a decision at a given time step. in sequence labeling parsing @xcite , the tree for a sentence of length n is represented as a sequence of n labels, one per word, so the parsing process is word-synchronous @xcite and can be addressed by frameworks traditionally used for other natural language processing tasks, such as part-of-speech tagging or named-entity recognition. current sequence labeling parsers combine competitive accuracy with high computational efficiency, while providing extra simplicity using off-the-shelf sequence labeling software without the need for ad-hoc parsing algorithms. in the realm of dependency parsing, pioneering work dates back to @xcite , who used a relative pos-tag based encoding to represent trees as label sequences, but the resulting accuracy was not practical even for the standards of the time, probably due to the inability of pre-deep-learning architectures to successfully learn the representation. using more modern architectures with the ability to contextualize words based on the sentence, and various tree encodings, @xcite were the first to show that competitive accuracy could be reached. subsequently, this accuracy has been improved further by techniques like the use of multi-task learning to parse dependencies and constituents together @xcite and of contextualized embeddings @xcite . while parsing as sequence labeling does not need specific parsing algorithms or data structures, as in graph-based or transition-based parsing, the responsibility of providing suitable parsing representations the red, dotted lines refer to the arcs represented in the second plane, denoted by * in the encoding label. with reasonable coverage and learnability falls instead on the encoding used to represent trees as sequences of labels. @xcite used four different encodings that obtained substantially different parsing accuracies in the experiments, with two encodings achieving competitive accuracy: the relative pos tag (rel-pos) encoding of @xcite and a new encoding based on balanced brackets, inspired by @xcite . while the encoding of @xcite achieved a good accuracy, and it has full coverage of non-projective dependency trees, it requires pos tags to encode the dependency arcs. this can be seen as a weakness, not just because computing and feeding pos tags increases the latency, but also because the traditional assumption that pos tagging is needed for parsing is being increasingly called into question @xcite @xcite . low-frequency pos tags can cause sparsity in the encoding, and low-quality pos tags could be a potential source of errors in low-resource languages. for this reason, @xcite proposed two alternative encodings with the same relative indexing philosophy, but without using pos tags. however, these encodings require a composition of two sequence labeling processes instead of one. on the other hand, the bracketing encoding inspired in @xcite represents the trees independently of pos tags or any other previous tagging step, but it has the limitation of being restricted to a very mild extension of projective trees. contribution. in this paper, we extend the idea of the bracketing-based encoding to non-projective parsing by defining a variant that can encode all 2-planar dependency trees @xcite . 2-planar dependency trees have been shown to cover the vast majority of non-projective trees in attested sentences @xcite and have been used in transition-based parsing @xcite . we show that our encoding provides better parsing accuracy than the original bracketing-based encoding on highly non-projective ud treebanks; and than the rel-pos encoding when assuming pos tags are not fed as input parameters to the models. the source code is available at https://github.com/mstrise/dep2label . ## preliminaries given a sentence w 1 . . . w n , we associate the words with nodes 0, 1, . . . , n, where 0 is a dummy root node. then, a dependency graph is an edge-labeled graph (v, e) with @xmath0, 1, . . . , n} and e a set of edges of the form (h, d, l) where @xmath1, @xmath2, and l is the dependency label. the goal of a dependency parser is to find a dependency graph that is a tree (i.e. without cycles, and with no dependent having more than one head) rooted at node 0. ## 2-planar bracketing encodings in order to support the extended non-projective coverage provided by 2-planarity in the bracketing system, we balance a different set of brackets for each plane. we introduce a set of "star" bracket elements denoting arcs belonging to the second plane, b * = {< * , / * , / * , > * }. a token w i can be assigned elements from both b and b * . brackets only match when they are on the same plane, i.e., (<, /), (/, >) are matching pairs of brackets that encode arcs in the first plane, and (< * , / * ), (/ * , > * ) are matching pairs of brackets that encode arcs in the second plane. the decoding process is implemented by operating on separate stacks for the first-plane brackets and the second-plane brackets. ## bracketing decoding when a sentence is represented with the bracketing encoding in a single plane, a valid left arc is associated with a pair of matching @xmath3. for each sentence we create two initially empty stacks, σ l and σ r , in order to keep the elements separate with respect to the arc direction. thus, the output labels generated by the system are read from left to right, decomposed into their brackets, and then brackets corresponding to left arcs are processed in σ l and those that encode right arcs are processed in σ r . in order to handle a second plane with brackets represented as (< * , / * ) and (/ * , > * ), we simply use additional stacks: σ * l and σ * r . more particularly, decoding proceeds by reading a label for each token and pushing each opening bracketing element to the corresponding stack while preserving the token's index. for instance, when reading a new label that contains <, the bracket element is pushed into the σ l stack and can only be popped once there is a later matching label with a closing bracketing element / that will be used to create a left arc, by recovering the index stored together with @xmath4. analogously, right arcs are processed in the same way, but in a different stack. postprocessing decoded labels do not ensure creating a well-formed tree. for that reason, we adapt some common heuristics for all encodings in order to postprocess them. in case some of the brackets in any of the stacks are unbalanced, the outermost bracket elements are discarded. tokens that are not assigned any head are recovered by attaching them to the word that is attached to the dummy root (i.e., the syntactic head of the sentence). cycles are also solved by removing the leftmost arc in the cycle. ## experiments data we extracted the most non-projective treebanks from udv2.4 (nivre and others, 2019) based on the percentage of non-projective sentences, and discarded some of them due to the lack of a pre-trained udpipe model or due to the lack of a development set. the selected treebanks were: ancient greek perseus , basque bdt , hungarian szeged , portuguese bosque , urdu udtb , afrikaans afribooms , korean kaist , danish ddt , gothic proiel , lithuanian hse . in addition, two fully projective treebanks (galician ctg and japanese gsd ) were included as control treebanks. model for our experiments we use bidirectional long short-term memory networks @xcite as implemented in the ncrf++ framework @xcite . 1 each input word w i is represented as a vector which comes from a concatenation of (i) an external pre-trained word embedding, which is further fine-tuned during training, and (ii) a second word embedding which results from the output of a char-lstm, which is trained end-to-end together with the rest of the network. in this context, let lstm θ ( x) be a black-box long short-term memory network that processes the sequence of vectors @xmath5, ..., x | x| ], then the output for x i is a hidden vector h i which represents the word based on its left and right sentence context: more particularly, we stack 2 bilstms before computing the output layer. for this, we consider a simple hard-sharing multi-task learning architecture, where each h i is sent to three separate layers in order to generate the classifications through regular softmaxes: two labels predicted for each plane (one label per plane) foot_1 and another one for the word's dependency relation. afterwards, label decoding is followed by a postprocessing step with some heuristics to ensure a valid dependency tree (as described in §4). ## conclusion we have shown a new bracketing-based linearization of 2-planar trees compatible with parsing as sequence labeling. our main goal was to introduce a bracketing encoding with the ability to perform unrestricted non-projective dependency parsing, which remained as an open challenge in sequence labeling parsing under the family of bracketing encodings. together with the proposed plane assignment strategies and a bilstm-based network, our 2-planar bracket representations improve the performance over the existing bracketing-based encoding for parsing as sequence labeling, and also outperform the pos-based encoding in the absence of pos-tags as input parameters to the model. thus, it can be a useful alternative where an encoding that depends on pos tags is not desirable, e.g. domains with low-frequency or low-quality pos tags, or to decrease even further the latency of sequence labeling parsers. finally, it is worth noting that we have proposed plane assignment strategies that minimize the use of the second plane. however, it is a possible avenue for future work to examine other strategies based on different criteria than the one presented in this paper.