R eplicating and Extending “ B ecause Their Treebanks Leak”: G raph Isomorphism, Covariants, and Parser Performance (2021)

Abstract: Søgaard (2020) obtained results suggesting the fraction of trees occurring in the test data isomorphic to trees in the training set accounts for a non-trivial variation in parser performance. Similar to other statistical analyses in NLP, the results were based on evaluating linear regressions. However, the study had methodological issues and was undertaken using a small sample size leading to unreliable results. We present a replication study in which we also bin sentences by length and find that only a small subset of sentences vary in performance with respect to graph isomorphism. Further, the correlation observed between parser performance and graph isomorphism in the wild disappears when controlling for covariants. However, in a controlled experiment, where covariants are kept fixed, we do observe a correlation. We suggest that conclusions drawn from statistical analyses like this need to be tempered and that controlled experiments can complement them by more readily teasing factors apart.

## introduction we undertake a replication study of @xcite which introduced graph isomorphism (dug -directed unlabelled graph isomorphism) as a means of explaining differences in parser performance across different treebanks. it measures the ratio of graphs foot_0 in the test set that were also observed in the training data. it is intuitive that this would likely be related to parser performance. however, dug has two important covariants. the size of the training data impacts dug because the smaller a treebank is, the less likely there will be many crossovers between training and test data. dug is also tied to the mean sentence length in the test data: smaller sentences are much more likely to have a tree structure already seen in the training, as there are fewer possible trees and the reverse is true for longer sentences, e.g. the number of possible trees for a sentence with 20 tokens is 12,826,228. ## related work there is a long history of investigating the causes of variance in parser performance. the effect of training data size on parser performance is well attested @xcite @xcite . sentence length has also been observed to impact performance @xcite . one likely factor behind this is different sentence lengths having difference dependency distance distributions @xcite which in turn affects parsing as longer dependencies are typically harder to parse @xcite . others have offered explanations based on linguistic characteristics such as morphological complexity @xcite , part-of-speech bigram perplexity @xcite , and word order freedom @xcite . the history of reproduction and replication in nlp is not so well established, with only a few studies in recent years, e.g. on universal dependency (ud) parsing (c ¸öltekin, 2020) and on automatic essay scoring systems @xcite . linear techniques, linear regression models or evaluating correlation coefficients are commonly used for statistical analyses of nlp systems. they have been used to model constituency parser performance @xcite , to evaluate what affects annotation agreement @xcite , to investigate what impacts statistical mt systems @xcite , what impacts performance on span identifying tasks @xcite , and many other examples. therefore, it is likely that lessons drawn from this replication analysis will be impactful in a broader sense as the conclusions here can be applied in many subareas of nlp, namely the sensitive handling of covariants by using partial coefficients, controlled experiments, or signal subtraction; a strong adherence to visualising data; and considering whether the phenomena under consideration are likely to be sensitive to sentence length, as is often the case in nlp, and if so undertaking a sentence-length binning analysis to complement coarser analyses. ## analysis and results we evaluate directed graph isomorphism (dug) as it was more strongly related to parser performance in the original paper. ## conclusion with this case study we have shown the value of replicating analyses in nlp. our analysis has shown that the original results were unreliable and it has highlighted methodological issues the original analysis had. also, the results regarding the methodology presented here (i.e. the need to visualise and evaluate correlations before considering linear regression techniques, the potential sensitivity to sentence length of measurements used in nlp statistical analyses, the need to control for all covariants and evaluate their impact using partial coefficients at the very least, and finally that using controlled experiments can help better evaluate the impact of specific measurements and can complement statistical analyses) will likely be useful for other statistical analyses in different areas of nlp.