Graph-based dependency parsing consists of two steps: first, an encoder produces a feature representation for each parsing substructure of the input sentence, which is then used to compute a score for the substructure; and second, a decoder} finds the parse tree whose substructures have the largest total score. Over the past few years, powerful neural techniques have been introduced into the encoding step which substantially increases parsing accuracies. However, advanced decoding techniques, in particular high-order decoding, have seen a decline in usage. It is widely believed that contextualized features produced by neural encoders can help capture high-order decoding information and hence diminish the need for a high-order decoder. In this paper, we empirically evaluate the combinations of different neural and non-neural encoders with first- and second-order decoders and provide a comprehensive analysis about the effectiveness of these combinations with varied training data sizes. We find that: first, when there is large training data, a strong neural encoder with first-order decoding is sufficient to achieve high parsing accuracy and only slightly lags behind the combination of neural encoding and second-order decoding; second, with small training data, a non-neural encoder with a second-order decoder outperforms the other combinations in most cases.    Dependency parsing (Kübler et al., 2009) is an important task in natural language processing (NLP) and a large number of methods have been proposed, most of which can be divided into two categories: graph-based methods (Dozat & Manning, 2017; Shi & Lee, 2018) and transition-based methods (Weiss et al., 2015; Andor et al., 2016; Ma et al., 2018) . In this paper, we focus on graphbased dependency parsing, which traditionally has higher parsing accuracy. A typical graph-based dependency parser consists of two parts: first, an encoder that produces a feature representation for each parsing substructure of the input sentence and computes a score for the substructure based on its feature representation; and second, a decoder that finds the parse tree whose substructures have the largest total score. Over the past few years, powerful neural techniques have been introduced into the encoding step that represent contextual features as continuous vectors. The introduction of neural methods leads to substantial increase in parsing accuracy (Kiperwasser & Goldberg, 2016) . High-order decoding techniques, on the other hand, have seen a decline in usage. The common belief is that high-order information has already been captured by neural encoders in the contextual representations and thus the need for high-order decoding is diminished (Falenska & Kuhn, 2019) . In this paper, we empirically evaluate different combinations of neural and non-neural encoders with first-and second-order decoders to thoroughly examine their effect on parsing performance. From the experimental results we make the following observations: First, powerful neural encoders indeed diminish to some extend the necessity of high-order decoding when sufficient training data is provided. Second, with smaller training data, the advantage of a neural encoder with a second-order decoder begins to decrease, and its performance surpassed by other combinations in some treebanks. Finally, if we further limit the training data size to a few hundred sentences, the combination of a simple non-neural encoder and a high-order decoder emerges as the preferred choice for its robustness and relatively higher performance. We empirically evaluate the combinations of neural and non-neural encoders with first-and secondorder decoders on six treebanks with varied data sizes. The results suggest that with sufficiently large training data (a few tens of thousands of sentences), one should use a neural encoder and perhaps a high-order decoder to achieve the best parsing accuracy; but with small training data (a few hundred sentences), one should use a traditional non-neural encoder plus a high-order decoder. Possible future work includes experimenting with second-order sibling decoding, third-order decoding, neural encoders with biaffine and triaffine score computation, and finally transition-based dependency parsers.
An empirical study that examines the effectiveness of different encoder-decoder combinations for the task of dependency parsing Empirically analyzes various encoders, decoders, and their dependencies for graph-based dependency parsing.