The performance of Part-of-Speech tagging varies significantly across the treebanks of the Universal Dependencies project. This work points out that these variations may result from divergences between the annotation of train and test sets. We show how the annotation variation principle, introduced by Dickinson and Meurers (2003) to automatically detect errors in gold standard, can be used to identify inconsistencies between annotations; we also evaluate their impact on prediction performance. The performance of Part-of-Speech (PoS) taggers significantly degrades when they are applied to test sentences that depart from training data. To illustrate this claim, Table 1 reports the error rate achieved by our in-house PoS tagger on the different combinations of train and test sets of the French treebanks of the Universal Dependencies (UD) project (Nivre et al., 2018). 1 It shows that depending on the train and test sets considered, the performance can vary by a factor of more than 25. Many studies (Foster, 2010; Plank et al., 2014) attribute this drop in accuracy to covariate shift (Shimodaira, 2000), characterizing the differences between domains by a change in the marginal distribution p ( x ) of the input (e.g. increase of out-of-vocabulary words, missing capitalization, different usage of punctuation, etc), while assuming that the conditional label distribution remains unaffected. This work adopts a different point of view : we believe that the variation in tagging performance is due to a dataset shift (Candela et al., 2009), i.e. a change in the joint distribution of the features and labels. We assume that this change mainly results from incoherences in the annotations between corpora or even within the same corpus. Indeed, ensuring inter-annotator agreement in PoS tagging is known to be a difficult task as annotation guidelines are not always interpreted in a consistent manner (Marcus et al., 1993). For instance, Manning (2011) shows that many errors in the WSJ corpus are just mistakes rather than uncertainties or difficulties in the task; Table 2 reports some of these annotation divergences that can be found in UD project. The situation is naturally worse in cross-corpora settings, in which treebanks are annotated by different laboratories or groups. The contribution of this paper is threefold :  we show that, as already pointed out by de Marneffe et al. (2017), the variation principle of Boyd et al. (2008) can be used to flag potential annotation discrepancies in the UD project. Building on this principle, we introduce, to evaluate the annotation consistency of a corpus, several methods and metrics that can be used, during the annotation to improve the quality of the corpus. we generalize the conclusions of Manning (2011), highlighting how error rates in PoS tagging are stemming from the poor quality of annotations and inconsistencies in the resources; we also systematically quantify the impact of annotation variation on PoS tagging performance for a large number of languages and corpora. we show that the evaluation of PoS taggers in cross-corpora settings (typically in domain adaptation experiments) is hindered by systematic annotation discrepancies between the corpora and quantify the impact of this divergence on PoS tagger evaluation. Our observations stress the fact that comparing inand out-domain scores as many test  FTB GSD ParTUT SRCMF Sequoia Spoken PUD  train FTB 2.8% 7.0% 6.5% 45.4% 5.4% 18.7% 12.9% GSD 6.7% 3.7% 7.2% 45.5% 5.4% 16.3% 10.2% ParTUT 11.2% 10.9% 5.9% 55.7% 11.3% 22.9% 15.8% SRCMF 38.8% 37.8% 36.2% 7.5% 37.4% 34.7% 36.1% Sequoia 7.5% 7.5% 8.4% 48.0% 4.0% 19.3% 13.6% Spoken 32.1% 30.3% 25.7% 51.8% 29.5% 7.9% 30.1% Table 1: Error rate (%) achieved by a PoS tagger trained and tested on all possible combinations of the French train and test sets of the UD project. works do (e.g. to evaluate the quality of a domain adaptation method or the measure the difficulty of the domain adaptation task) can be flawed and that this metrics has to be corrected to take into account the annotation divergences that exists between corpora. The rest of this paper is organized as follows. We first present the corpora and the tools used in our experiments (  2). We then describe the annotation variation principle of Dickinson and Meurers (2003) (  3) and its application to the treebanks of the Universal Dependencies project (  4). We eventually assess the impact of annotation variations on prediction performance (  5 and  6). The code and annotations of all experiments are available on the first author website. 2 For the sake of clarity, we have only reported our observations for the English treebanks of the UD project and, sometimes, for the French treebanks (because it has seven treebanks). Similar results have however been observed for other languages and corpora. Data All experiments presented in this work use the Universal Dependencies (UD) 2.3 dataset (Nivre et al., 2018) that aims at developing cross-linguistically consistent treebank annotations for a wide array of languages. This version of the UD project contains 129 treebanks covering 76 languages. Among those, 97 treebanks define a train set that contains between 19 sentences and 68,495 sentences and a test set that contains between 34 and 10,148 sentences. For 21 languages, several test sets are available : there are, for instance, 7 test sets for French, 6 for English, 5 for Czech and 4 for Swedish, Chinese, Japanese, Russian and Italian. Overall, it is possible to train and test 290 taggers (i.e. there are 290 possible combinations of a train and a test set of the same language), 191 of these conditions (i.e. pairs of a train set and a test set) correspond to a cross-corpus setting and can be considered for domain adaptation experiments. Many of these corpora 3 result from an automatic transformation (with, for some of them, manual corrections) from existing dependency or constituent treebanks (Bosco et al., 2013; Lipenkova and Soucek, 2014). Because most treebanks have been annotated and/or converted independently by different groups, 4 the risk of inconsistencies and errors in the application of annotation guidelines is increased. There may indeed be several sources of inconsistencies in the gold annotations : in addition to the divergences in the theoretical linguistic principles that governed the design of the original annotation guidelines, inconsistencies may also result from automatic (pre-)processing, human post-editing, or human annotation. Actually, several studies have recently pointed out that treebanks for the same language are not consistently annotated (Vilares and Gmez-Rodrguez, 2017; Aufrant et al., 2017). In a closely related context, Wisniewski et al. (2014) have also shown that, in spite of common annotation guidelines, one of the main bottleneck in cross-lingual transfer between UD corpora is the difference in the annotation conventions across treebanks and languages. 3. For PoS, only 23 treebanks have been manually annotated natively with the Universal PoS tagset. PoS tagger In all our experiments, we use a history-based model (Black et al., 1992) with a LaSO-like training method (Daum III and Marcu, 2005). This model reduces PoS tagging to a sequence of multi-class classification problems : the PoS of the words in the sentence are predicted one after the other using an averaged perceptron. We consider the standard feature set for PoS tagging (Zhang and Nivre, 2011) : current word, two previous and following words, the previous two predicted labels, etc. This standard' feature set has been designed for English and has not been adapted to the other languages considered in our experiments. Our PoS tagger achieves an average precision of 91.10% over all UD treebanks, a result comparable to the performance of UDPipe 1.2 (Straka and Strakov, 2017), the baseline of CoNLL'17 Shared Task  Multilingual Parsing from Raw Text to Universal Dependencies ' that achieves an average precision of 91.22%. When not otherwise specified, all PoS tagging scores reported below are averaged over 10 runs (i.e. independent training of a model and evaluation of the test performance). with different annotations, one of these two label sequences may be inconsistently annotated. Our work relies on this principle to identify discrepancies in the PoS annotation of treebanks. We call repeat a sequence of words that appears in, at least, two sentences and suspicious repeat a repeat that is annotated in at least two different ways. Identifying suspicious repeats requires, first, to find all sequences of words that appear in two different sentences; this is an instance of the maximal repeat problem : a maximal repeat , is a substring that occurs at least in two different sentences and cannot be extended to the left or to right to a longer common substring. Extracting maximal repeats allows us to find all sequence of words common to at least two sentences without extracting all their substrings. This problem can be solved efficiently using Generalized Suffix Tree (GST) (Gus-field, 1997) : if the corpus contains n words, extracting all the maximal repeats takes O ( n ) to build the GST and O ( n ) to list all the repeats. PoS annotations for these repeats can then be easily extracted and the ones that are identical can be filtered out to gather all suspicious repeats in a set of corpora. A detailed description of our implementation can be found in (Wisniewski, 2018). truly ambiguous. We consider two heuristics to filter out suspicious repeats. First with the size heuristic , we assume that longer suspicious repeats are more likely to result from annotation errors than shorter ones. For instance, Table 2 displays suspicious repeats with at least 10 words that all stem from an annotation error. Second, with the disjoint heuristic , we assume that actual ambiguities will be reflected in intra-corpus suspicious repeats, whereas errors will likely correspond to cases where differences in labelings are observed in different corpora. Formally, the disjoint heuristic flags repeats m occurring in at least two corpora A and B , and such that the set of labelings of m observed in A are disjoint from the set of labelings observed in B . For instance, in French, la porte can either be a determiner and a noun (e.g. in the sentence la porte est ferme  the door is closed) or a pronoun followed by a verb (e.g. in the sentence je la porte  I carry her). Observing these two possible labelings in at least two corpora is a good sign of an actual ambiguity. The disjoint heuristic allows us to detect that this suspicious repeat is an actual ambiguity. To reiterate, the intuition beyond the disjoint heuristic is that for ambiguities, the two possible annotations will appear in, at least, one of the two corpora. Conversely, systematic divergences in labeling observed across corpora are likely to be errors : for instance, in English, depending on the treebank, cardinal points are labeled as either proper nouns or as nouns. In this case, the set of labelings of the repeats in the first corpus is disjoint from the set of labeling in the second corpus and the the disjoint heuristic captures the annotation inconsistency. Analyzing filtering heuristics To further analyze these two heuristics, we have manually annotated the suspicious repeats between the train set of the English EWT corpus and the test set of the English PUD corpus. For each suspicious repeat, we record whether it is an annotation error or an actual ambiguity. Examples of annotations are given in Table 3. Results are in Table 4. It appears that, for the heuristics considered, a large part of the suspicious repeats correspond to annotation discrepancies rather than ambiguities. In many cases, these discrepancies result from systematic divergences in the interpretation of the UD guidelines. 5 For instance, the contraction  n't  is always labeled as a particle in the train set of the EWT corpus, but either as particle or an adverb in the PUD corpus. Most of these systematic differences involve distinction between nouns and proper nouns, auxiliaries and verbs and adjectives and verbs (for past participles). We will first show how the annotation variation principle allows us to characterize the noise and/or the difficulty of PoS tagging. Table 5 reports the number of repeats and suspicious repeats in the English corpora of the UD project. These numbers have been calculated by applying the method described in the previous section to the concatenation of train, development and test sets of each treebanks. To calibrate these measures, we conducted 5. Discrepancies are not only due to improper interpretations of the guidelines, but also sometimes to actual ambiguities in the annotation rules. the same experiments with the Wall Street Journal (Marcus et al., 1993), 6 the iconic corpus of PoS tagging for which a thorough manual analysis of the annotation quality is described in (Manning, 2011). The observations reported in Table 5 show that the number of repeats varies greatly from one corpus to another, which is not surprising considering the wide array of genres covered by the treebanks that includes sentences written by journalists or learner of English (the genres with the largest number of repeats) or sentences generated by users on social media (that contain far less repeated parts). These observations also show that the percentage of repeats that are not consistently annotated is slightly larger in the UD treebanks than in the WSJ, a corpus in which a manual inspection of the corpus reveals that many variations are mistakes' rather than representing uncertainties or difficulties in the PoS prediction (Manning, 2011). More interestingly, Table 6 shows the percen-Treebank # sent. 6. The Penn Treebank tagset has been manually converted to the Universal PoS tagset using the mapping of (Petrov et al., 2012) generalized to the extended UD PoS tagset. tage of repeats that are not consistently annotated for all possible combinations of a train and a test sets (ignoring sequences of words that do not appear at least once in both corpora). It appears that in all cases there are (sometimes significantly) more variations in annotations in cross-treebank settings than in situations where the train and the test sets belong to the same treebank. This observation suggests that there may be systematic differences in the annotations of different treebanks which could make the domain adaptation setting artificially more difficult. To characterize the difference between two treebanks, we measure the error rate of a binary classifier deciding from which corpus an annotated sentence is coming from. 7 Intuitively, the higher this error rate, the more difficult it is to distinguish sentences of the two corpora and the more similar the treebanks are. More formally, it can be shown (Ben-David et al., 2010) that this error rate is an estimation of the H -divergence (Kifer et al., 2004), a metric introduced in machine learning theory to quantify the impact of a change in domains by measuring the divergence between the distributions of examples sampled from two datasets. In our experiments, we use a Naive Bayes classifier 8 and three sets of features to describe a sentence pair and their annotation : words , in which each example is represented by the bag of its 1-gram and 2-gram of words; labels , in which examples are represented in the same way, but this time, considering PoS; and combi which uses the same representation after the words of all the treebanks have been concatenated with their PoS. The first set aims at capturing a potential covariate shift, the last two target divergence in annotations. To reduce the impact of the strong between-class imbalance, 9 in all our experiments we sub-sample the largest set to ensure that the two datasets we try to distinguish always have the same number of examples. All scores in this experiment are averaged over 20 train-test splits. 7. More precisely, the classifier analyses pairs of sentences and predicts whether they belong to th same corpus or not.8.We used the implementation provided by (Pedregosa et al., 2011) without tuning any hyper-parameters. Experiments with a logistic regression show similar results. Table 7 reports the results achieved with the different features sets averaged over all combinations of a train and a test set of the same language and gives the percentage of conditions for which each feature set achieved the best results; Figure 1 details these results for the English and French treebanks. Results for other languages show similar patterns. These results suggest that, in many cases, it is possible to accurately identify from which treebank a sentence and its annotation are coming, although these raw numbers are difficult to interpret as prediction performances are averaged over many different experimental conditions. In more than 50% of the cases, combining words to their PoS results in the best performance, which is consistent to the qualitative study reported in Section 3 : some words appear in two corpora with different PoS allowing to distinguish these corpora. This observation strongly suggests that divergence in annotations across corpora are often genuine. To study annotation divergence in the UD project, we propose to analyze suspicious repeats (i.e. sequence of repeated words with different anno-tations). We start by extracting all the suspicious repeats that can be found when considering all the possible combinations of a train set and a test features median % best words 78.2 31.0 labels 70.9 13.5 combi 78.8 55.5 Table 7: Precision (%) achieved over all cross-treebank conditions by a classifier identifying to which treebank a sentence belongs to. or development set of a given language. These matches are then filtered using the heuristics described in 3. There are, overall, 357 , 301 matches in the UD project, 69 , 157 of which involve 3 words or more and 14 , 142 5 words or more; the disjoint heuristic selects 122 , 634 of these matches (see Table 8 in  A). To highlight the connection between prediction errors and annotation divergence, we compute, for each possible combination of a train and a test set (considering all languages in the UD project), the correlation between the error rate achieved on a corpus B when training our PoS on a corpus A and the number of suspicious repeats between A and B normalized by the number of tokens in A and B . The Spearman correlation coefficient between these two values is 0 . 72 indicating a correlation generally qualified as strong' following the interpretation proposed by (Cohen, 1988) : the more there are sequences of words with different annotations in the train and test sets, the worse the tagging performance, which shows that annotation inconsistencies play an important role in explaining the poor performance of PoS tagger on some conditions. For a more precise picture, we also estimate the number of suspicious repeats that contain a prediction error. Using the disjoint heuristics to filter suspicious repeats, it appears that 70.2% (resp. 73.0%) of the suspicious repeats for English (resp. French) contain a prediction error. As expected, these numbers fall to 51.7% (resp. 49.9%) when the suspicious repeats are not filtered and therefore contain more ambiguous words. Figure 2 displays a similar trend when the suspicious repeats are filtered by their length; similar results are observed for all other languages. These observations suggest that annotation variations often results in prediction errors, espe-French FTB GSD PUD ParTUT SRCMFSequoiaSpoken test FTBGSDP a r TUTS e q u o i a Sp o k e n t r a i n 60.0% 69.0% 80.1% 77.2% 98.3% 67.8% 97.9% 82.0% 57.9% 69.4% 75.3% 98.7% 69.4% 97.3% 82.8% 73.3% 82.9% 68.5% 98.5% 72.5% 97.5% 80.1% 68.4% 79.5% 74.3% 95.7% 48.0% 94.9% 97.1% 95.2% 99.2% 97.8% 95.3% 93.4% 67.9% features words 0.5 0.6 0.7 0.8 0.9 FTB GSD PUD ParTUT SRCMFSequoiaSpoken test FTBGSDP a r TUTS e q u o i a Sp o k e n t r a i n 54.2% 66.6% 80.8% 75.8% 99.1% 67.1% 97.9% 75.1% 61.1% 77.8% 72.3% 99.6% 66.7% 98.1% 75.4% 71.0% 85.8% 63.7% 99.5% 72.8% 98.2% 71.0% 64.3% 81.1% 70.8% 98.2% 51.5% 95.8% 97.3% 97.5% 98.8% 94.0% 89.1% 94.8% 61.3% features labels 0.6 0.7 0.8 0.9 FTB GSD PUD ParTUT SRCMFSequoiaSpoken test FTBGSDP a r TUTS e q u o i a Sp o k e n t r a i n 60.0% 71.9% 85.6% 79.5% 98.2% 70.7% 98.4% 85.1% 58.8% 81.4% 73.6% 98.6% 69.2% 97.7% 87.1% 76.3% 87.3% 68.0% 98.7% 75.5% 98.1% 81.6% 69.8% 86.8% 73.1% 95.2% 49.0% 95.5% 97.7% 94.9% 99.3% 97.3% 96.4% 93.1% 68.2% features combi 0.5 0.6 0.7 0.8 0.9 English ESL EWT GUM LinES PUD ParTUT test EWTGUML i n ESP a r TUT t r a i n 73.0% 62.6% 73.4% 72.3% 79.1% 76.1% 79.3% 76.0% 67.2% 75.0% 71.7% 71.3% 78.1% 79.3% 78.4% 60.4% 77.9% 73.5% 85.0% 83.8% 75.7% 78.9% 74.0% 65.6% features words 0.65 0.70 0.75 0.80 0.85 ESL EWT GUM LinES PUD ParTUT test EWTGUML i n ESP a r TUT t r a i n 87.1% 59.4% 66.7% 65.9% 73.9% 78.2% 85.5% 69.3% 56.2% 67.9% 69.1% 75.3% 84.0% 73.7% 71.1% 51.1% 75.1% 73.1% 86.5% 81.1% 73.0% 74.7% 67.8% 63.5% features labels 0.54 0.60 0.66 0.72 0.78 0.84 ESL EWT GUM LinES PUD ParTUT test EWTGUML i n ESP a r TUT t r a i n 87.0% 62.7% 74.1% 74.0% 77.6% 75.6% 89.2% 77.2% 66.6% 76.5% 72.7% 74.3% 87.8% 80.4% 77.9% 58.8% 78.3% 73.8% 91.3% 85.4% 78.8% 81.9% 78.6% 65.2% features combi 0.60 0.66 0.72 0.78 0.84 0.90 Figure 1: Precision of a classifier identifying to which French (top) or English (bottom) treebank a sentence belongs to. cially when there are good reasons to assume that the variation actually stems from an inconsistency. To evaluate the impact of annotation errors on prediction performance, we propose, for each combination of a train and a test set, to train a PoS tagger and compare  full , the error rate achieved on the full test set to  ignoring the error rate achieved ignoring errors that occur in a suspicious repeat. More precisely,  ignoring is defined as :  ignoring = # { err }  # { err in suspicious repeats } # { words } (1) where # { err in suspicious repeats } in the number of errors in the suspicious repeats that have survived filtering. Intuitively  ignoring can be seen as an oracle' score corresponding to a tagger that would always predict the labels of suspicious repeat correctly. In the following, We will consider three different filters : the disjoint heuristic, keeping only suspicious repeats with more than three words and keeping all of them. Figure 3 reports these errors rates for French and English. Results for other languages show similar results. As expected, ignoring errors in suspicious repeats significantly improve prediction performance. It even appears that  ignoring is often on par with the score achieved on in-domain sets. Overall, in more than 43% (resp. 25%) of all the conditions the error rate ignoring errors in suspicious repeats filtered with the disjoint heuristic (resp. minimum heuristic) is lower than the error rate achieved on in-domain data. These values are naturally over-estimated as, in these experiments, we remove all potential annotation errors as well as words and structures that are ambiguous and therefore are more difficult to label. They can however be considered as lower-bound on the predic-ud lines partut test 0 2 4 6 8 10 e rr o rr a t e ( % ) en(UD)  full  ignoring ( minsize )  ignoring ( disjoint )  ignoring ( all ) ud lines partut test 0 2 4 6 8 10 12 14 16 en(LINES)  full  ignoring ( minsize )  ignoring ( disjoint )  ignoring ( all ) ud lines partut test 0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 en(PARTUT)  full  ignoring ( minsize )  ignoring ( disjoint )  ignoring ( all ) ud ftb partut sequoia test 0 2 4 6 8 10 e rr o rr a t e ( % ) fr(PARTUT)  full  ignoring ( minsize )  ignoring ( disjoint )  ignoring ( all ) ud ftb partut sequoia test 0 1 2 3 4 5 6 7 8 fr(SEQUOIA)  full  ignoring ( minsize )  ignoring ( disjoint )  ignoring ( all ) ud ftb partut sequoia test 0 1 2 3 4 5 6 fr(UD)  full  ignoring ( minsize )  ignoring ( disjoint )  ignoring ( all ) ud ftb partut sequoia test 0 1 2 3 4 5 6 7 fr(FTB)  full  ignoring ( minsize )  ignoring ( disjoint )  ignoring ( all ) Figure 3: Error rate achieved by a PoS tagger on the different English treebanks of the UD project when errors in suspicious repeats are ignored. To assess their quality, we have manually checked all the suspicious repeats between the train set of French UD and the test set of the French FTB correcting inconsistencies and errors (almost 2,000 PoS were modified). 10 When trained on the original UD corpus, the PoS tagger achieved an error rate of 6.78% on the FTB corpus (4.51% on in-domain data). After correcting inconsistencies, the out-domain error rate falls down to 5.11%. This value is close to the error rate ignoring suspicious repeats containing three and more words, showing the validity of the heuristics we have considered. In this work, we have shown that, for PoS tagging, many prediction errors in cross-corpora settings (which is a typical domain adaptation scenario) stem from divergence between annotations. We have also described a method to quantify this divergence. We have only considered here corpora from the UD project and PoS annotation, but we consider that our method is very generic and can be easily applied to other corpora or tasks (e.g. to-kenization, dependency parsing, etc.) that we will address in future work. We also plan to see how the different experiments we have made to identify annotation errors and inconsistencies can be used during the annotation process to reduce the workload 10. The corrected' corpora will be made available upon publication. In this experiment, the impact of annotation errors is under-estimated as we have only corrected errors that appear in a suspicious repeat without trying to generalize' these corrections to words that appear only in one corpus. This work has been partly funded by the French Agence Nationale de la Recherche under Par-SiTi (ANR-16-CE33-0021) and MultiSem projects (ANR-16-CE33-0013).
abstain result result abstain result abstain abstain method result abstain abstain abstain abstain abstain result result result result abstain method objective abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain method abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain method abstain abstain abstain abstain abstain method other method abstain abstain abstain result abstain method result abstain abstain other