4 and 7-bit Labeling for Projective and Non-Projective Dependency Trees (2023)

Abstract: We introduce an encoding for parsing as sequence labeling that can represent any projective dependency tree as a sequence of 4-bit labels, one per word. The bits in each word’s label represent (1) whether it is a right or left dependent, (2) whether it is the outermost (left/right) dependent of its parent, (3) whether it has any left children and (4) whether it has any right children. We show that this provides an injective mapping from trees to labels that can be encoded and decoded in linear time. We then define a 7-bit extension that represents an extra plane of arcs, extending the coverage to almost full non-projectivity (over 99.9% empirical arc coverage). Results on a set of diverse treebanks show that our 7-bit encoding obtains substantial accuracy gains over the previously best-performing sequence labeling encodings.

## introduction approaches that cast parsing as sequence labeling have gathered interest as they are simple, fast @xcite , highly parallelizable @xcite and produce outputs that are easy to feed to other tasks @xcite . their main ingredient are the encodings that map trees into sequences of one discrete label per word. thus, various such encodings have been proposed both for constituency @xcite and dependency parsing @xcite @xcite . most such encodings have an unbounded label set, whose cardinality grows with sentence length. an exception for constituent parsing is tetratagging @xcite . for dependency parsing, to our knowledge, no bounded encodings were known. simultaneously to this work, @xcite have just proposed one: hexatagging, where projective dependency trees are represented by tagging each word with one of a set of 8 tags. 1 1 the "hexa" in the name comes from a set of six atoms 0 1 2 3 4 5 6 7 -root-it should continue to be defanged . <* < \>*/ <* < \> >* 0100 0000 1111 0100 0000 1010 1100 figure 1 : a dependency tree and its 4-bit encoding. contribution we present a bounded sequencelabeling encoding that represents any projective dependency tree with 4 bits (i.e., 16 distinct labels) per word. while this requires one more bit than hexatagging, it is arguably more straightforward, as the bits directly reflect properties of each node in the dependency tree without an intermediate constituent structure, as hexatagging requires. also, it has a clear relation to existing bracketing encodings, and has a straightforward non-projective extension using 7 bits with almost full non-projective coverage. empirical results show that our encoding provides more accurate parsers than the existing unbounded bracketing encodings, which had the best previous results among sequence-labeling encodings, although it underperforms hexatagging. ## projective encoding let t n be a set of unlabeled dependency trees foot_0 for sentences of length n. a sequence-labeling encoding defines a function φ n : t @xmath0, for a label set l. thus, each tree for a sentence w 1 . . . w n is encoded as a sequence of labels, l 1 . . . l n , that assigns a label l @xmath1. we define the 4-bit projective encoding as an encoding where t n is the set of projective depenused to define the labels. however, the label for each word is composed of two such atoms (one from a set of two, and other from a set of four) so there are eight possible labels per word. all combinations of the four bits are possible, so we have 16 possible labels. for easier visualization and comparison to existing bracketing encodings, we will represent the values of b 0 @xmath2, b 1 as * (true) or blank (false), and b 2 and b 3 respectively as \ and / (true) or blank (false). we will use these representations with set notation to make claims about a label's bits, e.g. >* ∈ l means that label l has b 0 = 1, b 1 = 1. figure 1 shows a sample tree encoded with this method. we will now show how to encode and decode trees, and prove that the encoding is a total, injective map from projective trees to label sequences. encoding and totality encoding a tree is trivial: one just needs to traverse each word and apply the definition of each bit to obtain the label. this also means that our encoding from trees to labels is a total function, as the labels are well defined for any dependency tree (and thus, for any projective tree). ## non-projective encoding for a wider coverage of non-projective dependency trees (including the overwhelming majority of trees found in treebanks), we use the same technique as defined for unbounded brackets in (strzyz et al., 2020): we partition dependency trees into two subsets (planes) of arcs (details in appendix d), and this lets us define a 7-bit non-projective encoding by assigning each word w i a label l @xmath3. . . b 6 ), where: every 7-bit combination is possible, leading to 128 distinct labels. figure 2 shows an example of a non-projective tree represented with this encoding. the encoding is able to cover every possible dependency tree whose arc set can be partitioned into two subsets (planes), such that arcs with the same direction and plane do not cross. this immediately follows from defining the decoding with a set of four algorithms, two for decoding left and right arcs on the first plane (defined as algorithm 1 and its symmetric, but considering only the symbols making reference to arcs in the first plane) and other two identical decoding passes for the second plane. with this, injectivity is shown in the same way as for the 4-bit encoding. decoding is still linear-time. note that the set of trees covered by the encoding, described above, is a variant of the set of 2-planar trees @xcite , which are trees that can be split into two planes such that arcs within the same plane do not cross, regardless of direction. compared to 2-planar trees, and just like the encodings in (strzyz et al., 2020), our set is extended as it allows arcs with opposite directions to cross within the same plane. however, it also loses some trees because the dummy root arc is also counted when restricting crossings, whereas in 2-planar trees it is ignored. ## experiments we compare our 4-bit and 7-bit encodings to their unbounded analogs, the bracketing (strzyz et al., 2019) and 2-planar bracketing encodings @xcite which overall are the best performing in previous work @xcite . we use machamp @xcite as a sequence labeling library, with default hyperparameters (appendix b). we use xlm-roberta (conneau et al., 2020) followed by two separate onelayered feed-forward networks, one for syntactic labels and another for dependency types. we evaluate on the penn treebank stanford dependencies 3.3.0 conversion and on ud 2.9: a set of 9 linguistically-diverse treebanks taken from (anderson and gómez-rodríguez, 2020), and a lowresource set of 7 @xcite . we consider multiple subsets of treebanks as a single subset could be fragile @xcite . the 4-bit encoding has lower coverage than basic brackets: both cover all projective trees, but they differ on coverage of non-projectivity (see appendix c for an explanation of the reasons). more detailed data (e.g. coverage and label set size for low-resource treebanks) is in appendix a. ## conclusion we have presented two new bracketing encodings for dependency parsing as sequence labeling, which use a bounded number of labels. the 4-bit encoding, designed for projective trees, excels in projective treebanks and low-resource setups. the 7-bit encoding, designed to accommodate non-projectivity, clearly outperforms the best prior sequence-labeling encodings across a diverse set of treebanks. the source code is available at https://github.com/polifack/ codelin/releases/tag/1.25 .