Integrating Graph-Based and Transition-Based Dependency Parsers in the Deep Contextualized Era (2020)

Abstract: Graph-based and transition-based dependency parsers used to have different strengths and weaknesses. Therefore, combining the outputs of parsers from both paradigms used to be the standard approach to improve or analyze their performance. However, with the recent adoption of deep contextualized word representations, the chief weakness of graph-based models, i.e., their limited scope of features, has been mitigated. Through two popular combination techniques – blending and stacking – we demonstrate that the remaining diversity in the parsing models is reduced below the level of models trained with different random seeds. Thus, an integration no longer leads to increased accuracy. When both parsers depend on BiLSTMs, the graph-based architecture has a consistent advantage. This advantage stems from globally-trained BiLSTM representations, which capture more distant look-ahead syntactic relations. Such representations can be exploited through multi-task learning, which improves the transition-based parser, especially on treebanks with a high ratio of right-headed dependencies.

## introduction dependency parsers can roughly be divided into two classes: graph-based @xcite and transition-based @xcite . the two paradigms differ in their approach to the trade-off between access to contextual features in the output dependency tree and exactness of search @xcite . the complementary strengths of those paradigms have given grounds to numerous diversity-based methods for integrating parsing models @xcite . to date, the methods are commonly used for improving the accuracy of single parsers foot_0 , achieving robust predictions for the silver-standard resource preparation @xcite , or as analysis tools @xcite . one of the most significant recent developments in dependency parsing is based on encoding rich sentential context into word representations, such as bilstm vectors @xcite and deep contextualized word embeddings @xcite . including these representations as features has set a new state of the art for both graph-based and transition-based parsers @xcite . however, it also brought the two architectures closer. @xcite showed that after including deep contextualized word embeddings, the average error profiles of graph-and transition-based parsers converge, potentially reducing gains from combining them. on the other hand, the authors also noticed that the underlying trade-off between the parsing paradigms is still visible in their results. thus, it is an open question to what extent the differences between the parsing paradigms could still be leveraged. in this paper, we fill the gaps left in understanding the behavior of transition-and graph-based dependency parsers that employ today's state-ofthe-art deep contextualized representations. we start from the setting of @xcite , i.e., @xcite seminal transition-based and graph-based parsers extended with deep contextualized word embeddings. we show that, on average, the differences between bilstm-based graph-based and transition-based models are reduced below the level of different random seeds. interestingly, the diversity needed for a successful integration vanishes al- ## diversity-based integration we start by evaluating the two integration methods (stack and blend) and applying them to our transition-and graph-based parsers (tb and gb). average results. the first column in comparing single baselines (tb vs. gb), we note that gb has a clear advantage over tb. it surpasses tb on twelve out of thirteen treebanks (all improvements are significant). we reproduce analysis from @xcite and confirm that this advantage is consistent across arcs of different lengths, distances to root, and sentences with different sizes (we provide corresponding plots in appendix a). interestingly, the dominance of gb over tb significantly differs across treebanks and is especially prominent for more challenging ones, e.g., with small amounts of training data or a high level of non-projectivity. for instance, the largest difference of 2.25 las is visible for basque, which is the treebank with the largest number of non-projective arcs, and turkish, which has the smallest training dataset. moreover, those are the treebanks where stack tb gb offers small improvements (0.39 las and 0.24 las, respectively), but both stack gb tb and blend 3 3 cannot make use of the diversity in predictions of the two models and cause the accuracy to drop (comparing stack gb tb vs. gb and blend 3 3 vs. blend 0 6 ). in the case of non-neural parsers, a big gap between the performance of a strong graph-based model and a greedy transition-based model does not prevent the former to learn from the latter @xcite . therefore, the questions arise where those treebank-specific differences come from and why integration methods cannot benefit from them. we address these questions in section 5. ## parsing architectures and diversity in this section, we investigate which aspects of the k&g architecture are responsible for no gains from the integration. for this purpose, we run ablation experiments and apply blending and stack-ing on models trained with and without bilstms and with and without elmo representations. ## representations and treebank-specific diversity in the previous section, we saw that bilstms mitigate average benefits from integration methods. one explanation might be that when both tb and gb use the same feature representations, the diversity between them is much smaller, thus reducing the gains the models could draw from each other. however, when comparing treebank-specific results in ## related work traditional integration of dependency parsers. classical integration methods were initially introduced to take advantage of differences in the strengths of the component parsers. such differences were usually the result of different parsing paradigms, as in the case of feature-based stacking, blending, or beam search-based transitionbased parsers with features strongly inspired by graph-based models @xcite . however, combining parsers that process input left-to-right and rightto-left @xcite , or even parsers and sequence labelers @xcite , was also proposed. blending was usually applied to a mixture of graphbased and transition-based left-to-right and rightto-left parsers @xcite @xcite . moreover, in the case of stacking, integrating two parsers of the same type gives at most minor improvements @xcite . ## discussion and conclusion in this paper, we investigated the recent advances in dependency parsing from the perspective of the traditional integration methods. these methods are known for exploiting diversity in the strengths and weaknesses of transition-and graph-based parsing paradigms. we found out that when models use bilstms, such diversity is on the level of different random seeds. adding deep contextualized representations on top of bilstms improves the performance of both parsers but does not change the picture regarding the integration. rich-feature sets used to be the advantage of the transition-based parsers. now that the parsers do not need structural features @xcite , the graph-based parsers have an advantage that the locally-trained transition-based parsers cannot make up for. therefore, improving parsers through combination methods is not as straightforward as it used to be. such a combination has to take into consideration the specificity of the treebank and depend on whether accuracy or parsing time is the priority. the greatest gains in accuracy can be obtained by blending multiple graphbased models. however, the method comes with the cumbersome overhead of running multiple predictors at application time. when speed is essential and the accuracy can be sacrificed @xcite greedy transition-based parsers or even sequence labelers are the preferable choices @xcite . in such cases, alternative integration approaches such as multitask learning can boost the performance of locallytrained models without requiring additional computational effort at parsing time.