Hexatagging: Projective Dependency Parsing as Tagging (2023)

Abstract: We introduce a novel dependency parser, the hexatagger, that constructs dependency trees by tagging the words in a sentence with elements from a finite set of possible tags. In contrast to many approaches to dependency parsing, our approach is fully parallelizable at training time, i.e., the structure-building actions needed to build a dependency parse can be predicted in parallel to each other. Additionally, exact decoding is linear in time and space complexity. Furthermore, we derive a probabilistic dependency parser that predicts hexatags using no more than a linear model with features from a pretrained language model, i.e., we forsake a bespoke architecture explicitly designed for the task. Despite the generality and simplicity of our approach, we achieve state-of-the-art performance of 96.4 LAS and 97.4 UAS on the Penn Treebank test set. Additionally, our parser’s linear time complexity and parallelism significantly improve computational efficiency, with a roughly 10-times speed-up over previous state-of-the-art models during decoding.

## introduction the combination of parallel computing hardware and highly parallelizable neural network architectures @xcite has enabled the pretraining of language models on increasingly large amounts of data. in order to apply pretrained language models to downstream nlp tasks, many practitioners fine-tune the pretrained model while the task-specific architecture is jointly trained from scratch. typically, the task-specific architecture is built upon the hidden representations generated by the final layer of a pretrained model. exploiting pretrained language models in this manner has boosted the performance considerably on many nlp tasks @xcite ; figure 1 : from bottom to top, the figure shows the dependency tree, the hexatags, and the binary head tree for the sentence "she reads fascinating papers." @xcite . however, for the end-toend fine-tuning process to be fully parallelizable, it is also necessary to parallelize the training of the task-specific architecture. unfortunately, due to the complexity of the output in many structured prediction tasks in natural language, e.g., in dependency parsing, state-of-the-art models still use architectures with limited parallelization during training @xcite . in an attempt to develop parsers parallelizable during training, a recent line of work recasts parsing as tagging @xcite @xcite . under this approach, a parse tree is linearized into a sequence of tags. 1 the benefit of such a paradigm is that tagging can be done by only adding a linear classifier on top of a pretrained language model and the tags can, thus, be predicted independently. this leads to a parser that is highly parallelizable and whose training can be easily harmonized with the (parallelizable) fine-tuning of pretrained language models. during decoding, an exact algorithm is used to recover a valid sequence of tags which is then converted back to a parse tree. @xcite were the first to propose a parsing-as-tagging scheme with a constant tag space for constituency parsing and, additionally, the first to achieve results competitive with the stateof-the-art non-parallelizable constituency parsers using such a tagger. however, for dependency parsing, all dependency parsing-as-tagging schemes in the literature @xcite @xcite have infinite tag sets whose cardinality grows with the length of the input sequence, which limits such parsers' efficiency and generality @xcite . moreover, in some cases, this growth hinders generalization to sentences longer than the longest training sentence. furthermore, tagging-based dependency parsers still do not perform competitively with the bestperforming parsers in the literature @xcite . in this paper, we propose a novel way of framing projective dependency parsing as a tagging task. our approach makes use of 6 distinct tags, motivating us to naming the scheme hexatagger. in our experiments, hexatagger achieves state-of-the-art performance on the english penn treebank (ptb; @xcite test set. notably, it outperforms parsers with more computationally expensive training procedures and extra constituency annotations, e.g., the parser developed by @xcite . furthermore, hexatagger achieves results competitive to @xcite parser on the chinese penn treebank (ctb; @xcite test set and 12 languages on the pseudo-projectivized data from the universal dependencies (ud2.2; @xcite benchmark. in terms of efficiency, our experiments suggest that hexatagger is 10 times faster than previous top-performing parsers, and consumes significantly less memory, despite using an exact dynamic program for decoding. ## hexatagging in this section, we introduce hexatagging, a tagging scheme that consists of 6 unique tag types. we further prove by construction that there exists an injective mapping between valid sequences of hexatags and dependency trees. ## probability model in this section, we explain how to predict hexatags in parallel. our tagging model predicts two hexatags for each word in the input sequence with the exception of that last word, for which we only predict one tag. as discussed in §2.1, a hexatagger produces a sequence of 2n -1 tags @xmath0, t 2 , . . . , t 2n -1 ] for an input sequence of length n , @xmath1. therefore, an intuitive way to match the tag sequence with the input sequence is to assign two tags to each word. we denote a training corpus s of m tuples of input sequences and tag sequences {(w m , t m )} m @xmath2. to learn the scoring function over tags, we follow the same independence assumption as in @xcite , i.e., the probability of predicting each tag is independent of other tags given the input sequence. this assumption barely harms model performance (see @xcite cotterell, 2022, ## decoding our goal in this section is to develop an efficient algorithm to find the highest-scoring hexatag sequence under the model developed in §3. as stated in theorem 2, the transformation function between bhts and hexatag sequences is not surjective, i.e., not all the tag sequences can be transformed back into a bht. therefore, we need to find a valid hexatag sequence with the maximum probability under the model that can be transformed back to a bht. once such hexatag sequence is found, we can follow the two-step algorithm described in §2.3 to obtain the corresponding dependency tree. to find the highest-scoring valid hexatag sequence, we follow the linear-time algorithm developed by @xcite . for a hexatag sequence to be valid, we should be able to interpret it as actions in a left-corner shift-reduce transitions system, described in §2.3. concretely: we conduct experiments on the english penn treebank (ptb; @xcite , the chinese penn treebank (ctb; @xcite , and the universal dependencies 2.2 (ud2.2; @xcite . for ud2.2, we adopt the pseudo-projective transformation @xcite to convert non-projective trees into projective trees following previous work @xcite . we report dataset statistics in app. e and hyperparameter settings in app. f. ## conclusion in summary, hexatagging, our novel scheme, offers a parallelizable and efficiently decodable backbone for dependency parsing. without relying on custom architecture for dependency parsing, the hexatagger achieves state-of-the-art accuracy on several datasets using no more than a pretrained language model and linear classifiers.