Some Languages Seem Easier to Parse Because Their Treebanks Leak (2020)

Abstract: Cross-language differences in (universal) dependency parsing performance are mostly attributed to treebank size, average sentence length, average dependency length, morphological complexity, and domain differences. We point at a factor not previously discussed: If we abstract away from words and dependency labels, how many graphs in the test data were seen in the training data? We compute graph isomorphisms, and show that, treebank size aside, overlap between training and test graphs explain more of the observed variation than standard explanations such as the above.

## introduction the state of the art in dependency parsing varies a lot across languages: on polish, the best system in the conll 2018 shared task achieved a labeled attachment score of 94.9% on held-out data; on basque, the same number was 19.5%. just a few years ago, a major source of variation was the complexity of the annotation schemes used in the different treebanks; with the universal dependencies project, 1 treebanks now follow the same annotation guidelines, but nevertheless, these performance differences persist. 2 differences are typically attributed to training set size @xcite , linguistic variation 1 https://universaldependencies.org/ 2 while universal dependencices have made the available dependency treebanks more compatible, treebanks were of course developed using very different protocols; some are automatically or semi-automatically converted from other formalisms, others written with the universal dependencies guidelines in mind; some, again, were developed by big teams, some by a single person. while protocol is hard to isolate and study -and while protocol may correlate both positively or negatively with parsing performance, i.e., it is easy to imagine a poorly designed treebank that is easy to parse -the protocol likely has a significant downstream effect on performance; which means we can only hope to explain some of the variance in the experiments below. the two sentences are associated with the same unlabeled directed graphs. @xcite , sentence length or average gold dependency length (in the test data) @xcite , and domain differences between training and test data @xcite . training set size is undoubtedly a very strong predictor of parsing performance, but in this paper, overlap between unlabeled graphs in the training and test sections of a treebank is shown to be more predictive than any of the other factors. specifically, we compute equivalence classes over unlabeled dependency graphs -directed or undirected -and compute the ratio of trees in the treebanks' test sections that are isomorphic to graphs observed in the training section, i.e., the graph-level train-test leakage, and correlate this number with state-ofthe-art performance numbers across languages. to the best of our knowledge, no one has previously considered this predictor of parsing performance, and we show that it is more predictive than factors previously discussed in the literature. ## unlabeled graph isomorphisms exact graph isomorphism is in np, but it remains an open problem whether it is np-complete or in p. we use the vf2 algorithm in @xcite , which is known to be fast in practice with low memory requirements @xcite . the algorithm proceeds by iteratively expanding a subgraph isomorphism, until this procedure fails, or until the subgraph isomorphism covers the input graphs. we compute isomorphisms over dependency trees in the training set by first reducing the trees to a more abstract graph. in our experiments below, we consider two such reductions: to undirected, unlabeled graphs (uugs; removing labels and edge directions) and to directed, unlabeled graphs (dugs; removing only labels). once we have computed the isomorphisms, we count how many of the dependency trees in the test data are members of one of these equivalence classes. we then report the fraction of test dependency trees that are isomorphic to at least one dependency tree in the training data. this number can be seen as a metric of graph-level train-test leakage. see figure 2 for the top 5 most leaking treebanks in the universal dependencies project (version 2.5); the worst has only 3/100 unseen test graphs. in the appendix, we report the full set of results with uugs; both for exact computation of isomorphims with vf2, as well as for a heuristic simply matching a set of edge degrees. ## usual suspects we briefly discuss other factors assumed to be predictive of the performance of dependency parsers. treebank size it is trivially true that parser performance depends on treebank size, and it is unsurprising that the correlation is strong. obviously, if the treebank does not contain any training data, supervised parsers will have to resort to blind guessing, and the more data they see, the less variance they have to resolve. that said, it is well established that increasing the size of a treebank often comes with diminishing returns @xcite . since treebank size is nevertheless trivially related to parsing performance, we correlate all other factors φ in combination with treebank size (see §4): morphology previous work has pointed to morphology as a source of lower parsing performance @xcite . in languages with rich morphology, many relations which are expressed implicitly by word order and adjacency in languages like english, are encoded in morphological affixes, which requires subwordlevel processing to detect (in the tail). expressing functional information morphologically also allows for a high degree of word-order variation. in our experiments, we use the most predictive morphological feature in wals foot_0 and impute the missing values. sentence length parser performance unsurprisingly also depends on input length, i.e., the search space of possible parses @xcite ). this, for example, is why unsupervised dependency parsing has successfully relied on baby steps training @xcite . we correlate state-of-the-art parser performance with training set size and average test sentence length. mcdonald and nivre (2011) discuss graph properties that seem to correlate with parsing performance. we include average dependency length in our experiments below, which we compute by simply dividing the total length of dependencies by word tokens in the test section. ## empirical comparison of factors we correlate the factors φ assumed to influence syntactic dependency parser performance with state-ofthe-art performance figures from the conll 2018 shared task, i.e,. the performance of the best performing system per language. foot_1 see the appendix for the full statistics. while computing their pearson's ρ coefficients is standard methodology for validating performance metrics @xcite and has also been used to evaluate factors predicting system performance @xcite , this is inadequate in our case: many factors are potentially covariate, and we are, for example, not interested in factors that correlate strongly with treebank size, e.g., out-of-vocabulary rate or type-token ratio @xcite . instead we compute the explained variance and mean absolute error of a linear regression model with treebank size and φ as input, i.e., at s + bφ + c with t s treebank size and a, b, c learned parameters. we report explained variance and mean absolute error from three-fold cross-validation experiments to avoid overfitting. we make our code publicly available. foot_2 results our main results are presented in treebank size correlates strongly with parser performance; see the plot in figure bination with treebank size, they do not add much predictiver power, it seems. a-distance correlates strongly with parsing performance; the explained variance improves a little, and the error decreases a bit. average dependency length is only weakly, negatively correlated with parsing performance (ρ ∼ 0.067), a result that is not significant; and the absolute error of the linear regression model decreases only a little from adding the feature; the explained variance improves to 0.05. sentence length, perhaps unsurprisingly, correlates more strongly with parsing performance; and the explained variance of our linear regression model increases a lot from adding this feature. graph-level train-test leakage, however, is more predictive of parsing performance than any of these factors. see the correlation of treebank size over dug-level train-test leakage in figure 3 (right). it also leads to much better performance of our linear regression model; both in terms of explained variance and mean absolute error. we note that using dugs to compute the isomorphisms is slightly more predictive than relying on undirected graphs. ## related work the factors evaluated in the above, from @xcite ; @xcite ; @xcite ; @xcite ; @xcite ; @xcite , were already discussed. a few other factors have been pointed at in the literature that were not applicable to our experiments: @xcite show that the perplexity of the derivation orders of a transition-based dependency parser, is also predictive of parser performance. they report pearson's ρ scores that are considerably higher than those we found. their study suffers from two biases, though; one imposed by the transition-based parser and the other imposed by the language model used to calculate the perplexity. moreover, the results they report, are for only the non-convertedd dependency treebanks in the conll 2006 @xcite and conll 2007 @xcite treebank releases. these treebanks form a very small set, providing limited statistical support, and, moreover, rely on very different linguistic formalisms and annotation guidelines, leading to very different levels of complexity of derivation. in other words, a comparison would be inconclusive because of the free parameters imposed by the language model and the transition oracle, and the fact that no code is publicly available. also, their high correlation scores are unlikely to transfer to universal dependencies. ## discussion and conclusion this paper suggested a factor contributing to variance in (universal) dependency parser performance across languages: graph-level train-test leakage in treebanks. this form of leakage can be quantified by computing graph isomorphisms from training sections and counting the ratio of trees in the test sections that are not isomorphic with any tree in the training data. i compared this factor to previous attempts to explain variance in parser performance across languages through a series of correlation and linear regression experiments; and showed that graph-level train-test leakage, treebank size aside, is the most predictive factor among those proposed, yet complementary. the result is perhaps not too surprising, since graph isomorphisms correlate with syntactic constructions, which in turn correlate with the occurrence of linguistic markers and tail linguistic phenomena. 6 the observation that treebanks leak, quite dramatically, at the graph level, is not only interesting for explaining variance in parser performance. it also suggests a new and improved evaluation methodology: since language is zipfian, not only at the level of words, but at the level of phrases @xcite , standard evaluation methodology relying on random samples @xcite is biased toward frequent phenomena. evaluating only on non-isomorphic trees, i.e., leaving out graphs that have been seen at training time from the test sections of treebanks, would reduce this bias. we hope this is a factor that designers of future syntactic treebanks will take into account. it is an open question whether graph-level train-test leakage is predictive of performance in other sentence-level nlp tasks, i.e., whether the ratio of test sentences whose (predicted) syntactic dependency structure is identical to that of one of our training examples, correlates with state-of-the-art performance.