Viable Dependency Parsing as Sequence Labeling
Michalina Strzyz David Vilares Carlos Gómez-Rodríguez


One-loop functional renormalization group study for 
the dimensional reduction and its breakdown 
in the long-range random field O(N) spin model 
near lower critical dimension

    Yoshinori Sakamoto
    December 30, 2023
=================================================================================================================================================================================


We recast dependency parsing as a sequence labeling problem, 
exploring several encodings of dependency trees as labels. While dependency parsing by means of sequence labeling had been attempted in existing work, results suggested that the technique was impractical. We show instead that with a conventional bilstm-based model it is possible to obtain fast and accurate parsers. These parsers are conceptually simple, not needing traditional parsing algorithms or auxiliary structures. However, experiments on the PTB and a sample of UD treebanks show that they provide
a good speed-accuracy tradeoff, with results competitive with more complex approaches.




§ INTRODUCTION


The application of neural architectures to syntactic parsing, and especially the ability of long short-term memories (LSTMs) to obtain context-aware feature representations <cit.>, has made it possible to
parse natural language with conceptually simpler models than before. 
For example, in dependency parsing,
the rich feature models with dozens of features used in transition-based approaches 
<cit.> can be simplified 
when using feedforward neural networks <cit.>, and even more with BiLSTM architectures <cit.>, where in fact two positional features can suffice <cit.>. 
Similarly, in graph-based approaches,
<cit.> have shown that an arc-factored model can achieve state-of-the-art accuracy, without the need for the higher-order features used in systems like <cit.>.

In the same way,
neural feature representations have made it possible to
relax the need for structured representations. This is the case of
sequence-to-sequence models that translate sentences into linearized 
trees, which were first applied to constituent 
<cit.> and later to dependency parsing <cit.>. 
Recently, <cit.> have shown that sequence labeling models, where each word is associated with a label (thus simpler than sequence to sequence, where the
mapping from input to output is not one to one)
can learn constituent parsing.




  
Contribution We show that sequence labeling is
useful for dependency parsing, in contrast to previous work <cit.>.
We explore four different encodings to represent dependency trees for a sentence of length n as a set of n labels associated with its words. We then use these representations to perform dependency parsing with an off-the-shelf sequence labeling model. The results show that we produce models with an excellent speed-accuracy tradeoff, without requiring any explicit parsing algorithm or auxiliary structure (e.g. stack or buffer). The source code is available at <https://github.com/mstrise/dep2label>



§ PARSING AS SEQUENCE LABELING


Sequence labeling is a structured prediction problem where a single output label is generated for every input token. This is the case of tasks such as PoS tagging, chunking or named-entity recognition, for which different approaches obtain accurate results <cit.>. 

On the contrary, previous work on dependency parsing as sequence labeling is vague and reports results that are significantly lower than those provided by transition-, graph-based or sequence-to-sequence models <cit.>. Spoustova encoded dependency trees using a relative PoS-based scheme to represent the head of a node, to then train an averaged perceptron. They did not provide comparable results, but claimed that the accuracy was between 5-10% below the state of the art in the pre-deep learning era. Recently, <cit.> used a relative positional encoding of head indexes with respect to the target token. This is used to train Bidirectional LSTM-CRF sequence-to-sequence models <cit.>, that make use of sub-root decomposition. They compared their performance against an equivalent BiLSTM-CRF labeling model. 
The reported UAS for the sequence labeling model was 87.6% on the Penn Treebank, more than 8 points below the current best model <cit.>, concluding that sequence-to-sequence models are required to obtain competitive results. 

In this work, we show that these results can be clearly improved if simpler architectures are used.



§ ENCODING OF TREES AND LABELS


Given a sentence w_1 … w_n, we associate the words with nodes {0, 1, …, n}, where the extra node 0 is used as a dummy root for the sentence. A dependency parser will find a set of labeled relations encoded as edges of the form (h,d,l), where h ∈{0, 1, …, n} is the head, d ∈{1, …, n} the dependent, and l a dependency label. The resulting dependency graph must be acyclic and such that each node in {1, …, n} has exactly one head, so it will be a directed tree rooted at node 0.

Thus, to encode a dependency tree, it suffices to encode the unique head position and dependency label associated with each word of w_1 … w_n. To do so, we will give each word w_i a discrete label of the form (x_i,l_i), where l_i is the dependency label and x_i encodes the position of the head in one of the following four ways (see also Figure <ref>):



    
  * Naive positional encoding: x_i directly stores the 
    position of the head, 
    i.e., a label (x_i,l_i) encodes an edge (x_i,i,l_i). This is the encoding 
    used in the CoNLL file format.
    
  * Relative positional encoding: x_i stores the difference between the head index minus that of the dependent, i.e., (x_i,l_i) encodes an edge (i+x_i,i,l_i). This was the encoding used for the sequence-to-sequence and sequence labeling models in <cit.>, as well as for the sequence-to-sequence model in <cit.>.
    
  * Relative PoS-based encoding: x_i is a tuple p_i,o_i. If o_i>0,
    the head of w_i is the o_ith closest among the words to the right of w_i that have PoS tag p_i. 
    If o_i < 0,
    the head of w_i is the -o_ith closest among the words to the left of w_i that have PoS tag p_i. For example, (V,-2) means “the second verb to the left” of w_i. 
    This scheme is closer to the notion of valency, and was used by <cit.>.
    
  * Bracketing-based encoding: based on 
    <cit.>.
    In each label (x_i,l_i), the component x_i is a string 
    following the regular expression
    
    where the presence of character  means that w_i-1 has an incoming arc from the right, k copies of character  mean that w_i has k outgoing arcs towards the left, k copies of  mean that w_i-1 has k outgoing arcs towards the right, and the presence of  means that w_i has an incoming arc from the left. Thus, each right dependency from a word i to j is encoded by a (,) pair in the label components x_i+1 and x_j, and each left dependency from j to i by a (,) pair in the label components x_i+1 and x_j. Note that the intuition that explains why information related to a word is encoded in a neighboring node is that each x_i corresponds to a fencepost position (i.e., x_i represents the space between w_i-1 and w_i), and the character pair associated to an arc is encoded in the most external fencepost positions covered by that arc. These pairs act as pairs of matching brackets, which can be decoded using a stack to reconstruct the dependencies. 


The first three encodings can represent any dependency tree, as they encode any valid head position for each node, while the bracketing encoding only supports projective trees, as it assumes that brackets are properly nested. 
All the encodings are total and injective,
but they are not surjective:
 head indexes can be out of range in the first three encodings, brackets can be unbalanced in encoding 4, and all the encodings can generate graphs with cycles. We will deal with ill-formed trees later.





§ MODEL


We use a standard encoder-decoder network, to show that dependency parsing as sequence labeling works without the need of complex models.



  
Encoder We use bidirectional LSTMs <cit.>.
Let LSTM_θ(x⃗) be an abstraction of a long short-term memory network that processes the sequence of vectors x⃗=[x⃗_1,...,x⃗_|x⃗|], then output for x⃗_i is defined as h⃗_i = BiLSTM_θ(x⃗,i) = LSTM_θ^l(x⃗_[1:i]) ∘ LSTM_θ^r(x⃗_[|x⃗|:i]). We consider stacked BiLSTMs, where the output h⃗^m_i of the mth BiLSTM layer is fed as input to the m+1th layer. Unless otherwise specified, the input token at a given time step is the concatenation of a word, PoS tag, and another word embedding learned through a character LSTM.



  
Decoder 
We use a feed-forward network, which is fed the output of the last BiLSTM. The output is computed as P(y_i|h⃗_i) = softmax(W ·h⃗_i + b⃗).



  
Well-formedness (i) Each token must be assigned a head (one must be the dummy root), and (ii) the graph must be acyclic. If no token is the real root (no head is the dummy root), we search for candidates by relying on the three most likely labels for each token.[If single-rooted trees are a prerequisite, the most probable node will be selected among multiple root nodes.] If none is found, we assign it to the first token of the sentence. The single-head constraint is ensured by the nature of 
the encodings themselves,
but some of the predicted head indexes might be out of bounds. If so, we attach those tokens to the real root. If a cycle exists, we 
do the same for the leftmost token in the cycle.



§ EXPERIMENTS


We use the English Penn Treebank (PTB) <cit.> and its splits for parsing.
We transform it into Stanford Dependencies <cit.> and obtain the predicted PoS tags using Stanford tagger <cit.>.
We also select a sample of UDv2.2 treebanks <cit.>: Ancient-GreekPROIEL, CzechPDT, ChineseGSD, EnglishEWT, FinnishTDT, HebrewHTB, KazakhKTB and TamilTTB, as a representative sample, following <cit.>.
As evaluation metrics, we use Labeled (LAS) and Unlabeled Attachment Score (UAS).
We measure speed in sentences/second, both on a single core of a CPU[Intel Core i7-7700 CPU 4.2 GHz.] and on a GPU[GeForce GTX 1080.].



  
Setup 
We use NCRFpp as our sequence labeling framework <cit.>. For PTB, we use the embeddings by emb, for comparison to BIST parser <cit.>, which uses a similar architecture, but also needs a parsing algorithm and auxiliary structures. For UD, we follow an end-to-end setup and run UDPipe[The pretrained models from the CoNLL18 Shared Task.] <cit.> for tokenization and tagging. We use the pretrained word embeddings by embed. 
Appendix <ref> contains additional hyperparameters.



 §.§ Encoding evaluation and model selection


We first examine the four encodings on the PTB dev set.
Table <ref> shows the results and also compares them against <cit.>, who proposed seq2seq and sequence labeling models that use a relative positional encoding.



As the relative PoS-based encoding and bracketing-based encoding provide the best results, we will conduct the rest of our experiments with these two encodings.
Furthermore, we perform a small hyperparameter search involving encoding, number of hidden layers, their dimension and presence of character embeddings, as these parameters influence speed and accuracy.
From now on, we write P^z_x,y for a PoS-based encoding model and B^z_x,y for a bracketing-based encoding model, where z indicates whether character representation was used in the model, x the number of BiLSTM layers, and y the word hidden vector dimension.

We take as starting points (1) the hyperparameters used by the BIST parser <cit.>, as it uses a BiLSTM architecture analogous to ours, with the difference that it employs a transition-based algorithm that uses a stack data structure instead of plain sequence labeling without explicit representation of structure, and (2) the best hyperparameters used by <cit.> for constituent parsing as sequence labeling, as it is an analogous task for a different parsing formalism. 

From there, we explore different combinations of parameters and evaluate 20 models on the PTB development set, with respect to accuracy (UAS) and speed (sentences/second on a single CPU core), obtaining the Pareto front in Figure <ref>. The two starting models based on previous literature (P_2,250 and P^C_2,800, respectively) happen to be in the Pareto front, confirming that they are reasonable hyperparameter choices also for this setting.
In addition, we select two more models from the Pareto front (models P^C_2,400 and B_2,250) for our test set experiments on PTB, as they also provide a good balance between speed and accuracy.














 §.§ Results and discussion


Table <ref> compares the chosen models, on the PTB test set, against state-of-the-art models. Contrary to previous dependency-parsing-as-sequence-labeling attempts, we are competitive and provide a good speed-accuracy tradeoff. For instance, the P^C_2,800 model runs faster than 
the BIST parser <cit.> while being almost as accurate (-0.18 LAS). This comes in spite of its simplicity. While our BiLSTM architecture is similar to that of BIST,
the sequence labeling approach does not need a stack, a specific transition system or a dynamic oracle. Using the BIST hyperparameters for our model (P_2,250) yields further increases in speed, at some cost to accuracy: 3.34x faster and -0.04 LAS score than the graph-based model, and 3.51x faster and -0.94 LAS score than their transition-based one.

We now extend our experiments to the sample of UD-CoNLL18 treebanks. To this end, we focus on the P^C_2,800 model and since our PoS tag-based encoding can be influenced by the specific PoS tags used, we first conduct an experiment on the development sets to determine what tag set (UPoS, the universal PoS tag set, common to all languages, or XPoS, extended language-specific PoS tags) produces the best results for each dataset. 

Table <ref> shows how the number of unique UPoS and XPoS tags found in the training set differs in various languages. The results suggest that the performance of our system can be influenced by the size of the tag set. It appears that a very large tag set (for instance the XPoS tag set for Czech and Tamil) can hurt the performance of the model and significantly slow down the system, as it results into a large number of distinct labels for the sequence labeling model, increasing sparsity and making the classification harder. In case of Ancient Greek and Kazakh, the best performance is achieved with the XPoS-based encoding. In these corpora, the tag set is slightly bigger than the UPoS tag set. One can argue that the XPoS tags in this case were possibly more fine-grained and hence provided additional useful information to the system facilitating a correct label prediction, without being so large as to produce excessive sparsity. 

Table <ref> shows experiments on the UD test sets, with the chosen PoS tag set for each corpus. P^C_2,800 outperforms transition-based BIST in LAS in 3 out of 8 treebanks,[For Ancient Greek, this may be related to the large amount of non-projectivity (BIST is a projective parser). For extra comparison, a non-projective variant of BIST <cit.> obtains 71.58 LAS with mono-treebank training, but from better segmentation and morphology than used here. UDpipe <cit.> obtains 67.57 LAS.
Czech and Kazakh have a medium amount of non-projectivity.
]
and is clearly faster in all analyzed languages.
We believe that the variations between languages in terms of LAS difference with respect to BIST can be largely due to differences in the accuracy and granularity of predicted PoS tags,
since our chosen encoding relies on them to encode arcs.
The bracketing-based encoding, which does not use PoS tags, may be more robust to this. On the other hand, finding the optimal granularity of PoS tags for the PoS-based encoding can be an interesting avenue for future work.

In this work, we have also examined the impact of the training data size on the performance of our system compared to the performance of BIST parser. The results in Figure <ref> suggest that our model requires more data during the training than BIST parser in order to achieve similar performance. The performance is slightly worse when little training data is available, but later on our model reduces the gap when increasing the training data size.



§ CONCLUSION


This paper has explored fast and accurate dependency parsing as sequence labeling. We tested four different encodings, training a standard BiLSTM-based architecture. In contrast to previous work, our results on the PTB and a subset of UD treebanks show that this paradigm can obtain competitive results, despite not using any parsing algorithm nor external structures to parse sentences.



§ ACKNOWLEDGMENTS


This work has received funding from the European
Research Council (ERC), under the European
Union's Horizon 2020 research and innovation
programme (FASTPARSE, grant agreement No
714150), from the TELEPARES-UDC project
(FFI2014-51978-C2-2-R) and the ANSWER-ASAP project (TIN2017-85160-C2-1-R) from MINECO, and from Xunta de Galicia (ED431B 2017/01). We gratefully acknowledge NVIDIA Corporation for the donation of a GTX Titan X GPU.

acl_natbib





§ MODEL PARAMETERS


During the training we use Stochastic Gradient Descent (SGD) optimizer with a batch size of 8, and the model is trained for up to 100 iterations. We keep the model that obtains the highest UAS on the development set. Additional hyperparameters are shown in Table <ref>.




