Enriched In-Order Linearization for Faster Sequence-to-Sequence Constituent Parsing (2020)

Abstract: Sequence-to-sequence constituent parsing requires a linearization to represent trees as sequences. Top-down tree linearizations, which can be based on brackets or shift-reduce actions, have achieved the best accuracy to date. In this paper, we show that these results can be improved by using an in-order linearization instead. Based on this observation, we implement an enriched in-order shift-reduce linearization inspired by Vinyals et al. (2015)’s approach, achieving the best accuracy to date on the English PTB dataset among fully-supervised single-model sequence-to-sequence constituent parsers. Finally, we apply deterministic attention mechanisms to match the speed of state-of-the-art transition-based parsers, thus showing that sequence-to-sequence models can match them, not only in accuracy, but also in speed.

## introduction sequence-to-sequence (seq2seq) neural architectures have proved useful in several nlp tasks, with remarkable success in some of them such as machine translation, but they lag behind the state of the art in others. in constituent parsing, seq2seq models still need to improve to be competitive in accuracy and efficiency with their main competitors: transition-based constituent parsers @xcite @xcite . @xcite laid the first stone in seq2seq constituent parsing, proposing a linearization of phrase-structure trees as bracketed sequences following a top-down strategy, which can be predicted from the input sequence of words by any off-the-shelf seq2seq framework. while this approach is very simple, its accuracy and efficiency are significantly behind the state of the art in the fully-supervised single-model scenario. most attempts to improve this approach focused on modifying the neural network architecture, while keeping the top-down linearization strategy. as exceptions, @xcite and @xcite proposed linearizations based on sequences of transition-based parsing actions instead of brackets. @xcite tried a bottom-up linearization, but they obtained worse results than topdown approaches. 1 @xcite kept the top-down strategy, but using transitions of the top-down transition system of @xcite instead of a bracketed linearization, achieving a higher performance. in transition-based constituent parsing, an inorder algorithm has recently proved superior to the bottom-up and top-down approaches @xcite ), but we know of no applications of this approach in seq2seq parsing. ## enriched linearizations to cast constituent parsing as seq2seq prediction, each parse tree needs to be represented as a sequence of symbols that can be predicted from an input sentence. @xcite proposed a top-down bracketed linearization of constituent trees, where opening and closing brackets include non-terminal labels and pos tags are normalized by replacing them with a tag xx. an example is shown in linearization a of figure 1 . as an alternative, liu and zhang (2017a) presented a shift-reduce linearization based on the topdown transition system defined for constituent parsing by @xcite (example b in figure 1 ). this provides three transitions that can be used on a stack and a buffer to build a constituent tree: a shift transition to push words from the buffer into the stack, a non-terminal-x transition to push a non-terminal node x into the stack, and a reduce transition to pop elements from the stack until a non-terminal node is found and create a new subtree with all these elements as its children, pushing this new constituent into the stack. following vinyals et al. (2015)'s linearization where closing brackets also include the nonterminal label, we define an equivalent shift-reduce variant, where the reduce transition is also parameterized with the non-terminal on top of the resulting subtree (reduce-x). in that way, we can one-to-one map opening brackets to non-terminal-x transitions, closing brackets to reduce-x actions and xx-tags to shift transitions as shown in example c of figure 1 . this enriched version will enlarge the vocabulary, but will also add some extra informa-tion that, as we will see below, improves parsing accuracy. as an alternative to the top-down parser of @xcite , @xcite define a transition system based on in-order traversal, as in leftcorner parsing @xcite : the non-terminal node on top of the tree being built is only considered after the first child is completed in the stack, building each subtree in a bottom-up manner, but choosing the non-terminal node on top before the new constituent is reduced. transitions are the same as in the top-down algorithm (plus a finish transition to terminate the parsing process), but the effect of applying a reduce transition is different: it pops all elements from the stack until the first non-terminal node is found, which is also popped together with the preceding element in the stack to build a new constituent with all of them as children of the non-terminal node. 3 this algorithm pushed state-of-the-art accuracies in shift-reduce constituent parsing; and, as we show in section 4, it can be succesfully applied as a linearization method for seq2seq constituent parsing. sequence d in figure 1 exemplifies in-order linearization. similarly to the enriched top-down variant, we also extend the in-order shift-reduce linearization by parametrizing reduce transitions. additionally, we can also add extra information to shift transitions. @xcite leaves pos tags of punctuation symbols out of the normalization proposed by @xcite without further explanation, but possibly they consider it can help seq2seq models. we adapt this idea to our novel enriched in-order linearization and lexicalize shift transitions when a "." or a "," are pushed into the stack as "shift." and "shift,", respectively. 4 in our experiments, we see that lexicalizing shift transitions has indeed an impact on parsing performance. in figure 1 and sequence e, we include an example of this linearization technique. note that, although we use a transition-based linearization of parse trees, our approach is agnostic to the stack structure and the parsing process is performed by a simple seq2seq model that straightforwardly translates input sequences of words into sequences of shift-reduce actions. ## seq2seq neural network baseline model in our experiments, we test all proposed linearizations in the seq2seq neural architecture designed by @xcite and implemented on the framework developed by @xcite . this architecture proved to outperform the majority of seq2seq approaches, even without implementing beam search (which penalizes parsing speed). the difference with respect to the vanilla seq2seq configuration @xcite is that two separate attention models are used to cover two different and variable segments of the input. this provides improvements in accuracy, regardless of the linearization method used. more specifically, liu and zhang (2017a) follow the common practice in stack-lstm-based shiftreduce parsers @xcite @xcite ) that uses a concatenation of pretrained word embeddings (e * w i ) and randomly initialized word (e w i ) and pos tag embeddings (e p i ) to derive (through a relu non-linear function) the final representation x i of the ith input word: as a decoder, a lstm generates a sequence of decoder hidden states from which a sequence of actions is predicted. concretely, the current decoder hidden state d j is computed by: then, the current token y j is predicted from d j as: note that current state-of-the-art transition-based parsers, which rely on stack-lstms to represent the stack structure, are also implemented under the framework by @xcite and, therefore, our approach can be fairly compared to them in terms of accuracy and speed. ## experiments we test the proposed approaches on the ptb treebank @xcite with standard splits. 5 parser beam strat f1 transition-based (cross and huang, 2016a) n bu 90.0 (cross and huang, 2016b) n bu 91.3 (liu and zhang, 2017b) n bu 91.3 (fernández-g and gómez-r, 2019) * n bu 91.7 (dyer et al., 2016) * n td 91.2 (fernández-g and gómez-r, 2018) * n td 91.7 (liu and zhang, 2017b) * n in 91.8 (fernández-g and gómez-r, 2018) * n in 92.0 (zhu et al., 2013) y bu 90.4 (watanabe and sumita, 2015) y bu 90.7 (liu and zhang, 2017c) y bu 91.7 (fried and klein, 2018) y in 92.2 seq2seq (vinyals et al., 2015) y td 88.3 (ma et al., 2017) y bu 88.6 (kamigaito et al., 2017) y td 89.5 (liu et al., 2018) y td 91.2 (suzuki et al., 2018) y td 91.2 (liu and zhang, 2017a) * (baseline) n td 90.5 top-down sh-re w/ det. attention * n td 90.7 enriched top-down sh-re * n td 90.7 in-order sh-re * n in 90.9 enriched in-order sh-re * n in 91.3 w/o lexicalized sh transition * n in 91.2 w/ det. attention * n in 91.2 w/ beam-search * y in 91.6 chart-based (stern et al., 2017) n bu 91.8 (gaddy et al., 2018) n bu 92.1 (kitaev and klein, 2018) n bu 93.6 ## conclusion we present significant accuracy and speed improvements in seq2seq constituent parsing. the proposed linearization techniques can be used by any off-the-self seq2seq model without building a specific algorithm or structure. in addition, any advances in seq2seq neural architectures or pretrained transformer-based language models @xcite can be directly used to enhance our approach. jun suzuki, sho takase, hidetaka kamigaito, makoto morishita, and masaaki nagata. 2018. an empirical study of building a strong baseline for constituency parsing. in proceedings of the 56th annual meeting of the association for computational linguistics (volume 2: short papers), pages 612-618, melbourne, australia. association for computational linguistics. oriol vinyals, lukasz kaiser, terry koo, slav petrov, ilya sutskever, and geoffrey hinton. 2015. grammar as a foreign language. in proceedings of the 28th international conference on neural information processing systems -volume 2, nips'15, pages 2773-2781, cambridge, ma, usa. mit press. taro watanabe and eiichiro sumita. 2015. transitionbased neural constituent parsing. in proceedings of the 53rd annual meeting of the association for computational linguistics, acl 2015, 26-31 july 2015, bejing, china, volume 1: long papers, pages 1169-1179. muhua zhu, yue zhang, wenliang chen, min zhang, and jingbo zhu. 2013. fast and accurate shiftreduce constituent parsing. in proceedings of the 51st annual meeting of the association for computational linguistics, acl 2013, 4-9 august 2013, sofia, bulgaria, volume 1: long papers, pages 434-443.