A chance-corrected measure of inter-annotator agreement for syntax

It is a truth universally acknowledged that an annotation task in good standing be in possession of a measure of inter-annotator agreement (IAA). However, no such measure is in widespread use for the task of syntactic annotation. This is due to a mismatch between the formulation of the agreement measures, which assumes that the annotations have no or relatively little internal structure, and syntactic annotation where structure is the entire point of the annotation. For this reason efforts to gauge the quality of syntactic annotation are hampered by the need to fall back to simple accuracy measures. As shown in \citeNArt:Poe08, such measures are biased in favour of annotation schemes with fewer categories and do not account for skewed distributions between classes, which can give high observed agreement, even if the annotations are inconsistent.

In this article we propose a family of chance-corrected measures of agreement, applicable to both dependency- and constituency-based syntactic annotation, based on Krippendorff’s $\alpha$ and tree edit distance. First we give an overview of traditional agreement measures and why they are insufficient for syntax, before presenting our proposed metrics. Next, we present a number of synthetic experiments performed in order to find the best distance function for this kind of annotation; finally we contrast our new metric and simple accuracy scores as applied to real-world corpora before concluding and presenting some potential avenues for future work.

The most common metrics used in computational linguistics are the metrics $\kappa$ [, introduced to computational linguistics by []] and $\pi$ []. These metrics express agreement on a nominal coding task as the ratio $\kappa ,\pi =A_o-A_e/1-A_e$ where $A_o$ is the observed agreement and $A_e$ the expected agreement according to some model of “random” annotation. Both metrics have essentially the same model of expected agreement:

differing only in how they estimate the probabilities: $\kappa$ assigns separate probability distributions to each coder based on their observed behaviour, while $\pi$ uses the same distribution for both coders based on their aggregate behaviour.

Now, if we want to perform this same kind of evaluation on syntactic annotation it is not possible to use $\kappa$ or $\pi$ directly. In the case of dependency-based syntax we could conceivably use a variant of these metrics by considering the ID of a token’s head as a categorical variable (the approach taken in []), but we argue that this is not satisfactory. This use of the metrics would consider agreement on categories such as “tokens whose head is token number 24”, which is obviously not a linguistically informative category. Thus we have to reject this way of assessing the reliability of dependency syntax annotation. Also, this approach is not directly generalisable to constituency-based syntax.

For dependency syntax we could generalise these metrics similarly to how $\kappa$ is generalised to ${\kappa }_w$ to handle partial credit for overlapping annotations. Let the function $\text{LAS}\left(t_1,t_2\right)$ be the number of tokens with the same head and label in the two trees $t_1$ and $t_2$, $T\left(i\right)$ the set of trees possible for an item $i\in I$, and tokens the number of tokens in the corpus. Then we can compute an expected agreement as follows:

We see three problems with this approach. First of all the number of possible trees for a sentence grows exponentially with sentence length, which means that explicitly iterating over all possible such pairs is computationally intractable, nor have we been able to easily derive an algorithm for this particular problem from standard algorithms.

Second, the question of which model to use for $P\left(t\right|c)$ is not straightforward. It is possible to use generative parsing models such as PCFGs or the generative dependency models of \citeNEisner96, but agreement metrics require a model of random annotation, and as such using models designed for parsing runs the risk of over-estimating $A_e$, resulting in artificially low agreement scores.

Finally, it may be hard to establish a consensus in the field of which particular metric to use. As shown by the existence of three different metrics ($\kappa$, $\pi$ and $S$ []) for the relatively simple task of nominal coding, the choice of model for $P\left(t\right|c)$ will not be obvious, and thus differing choices of generative model as well as different choices for parameters such as smoothing will result in subtly different agreement metrics. The results of these different metrics will not be directly comparable, which will make the results of groups using different metrics unnecessarily hard to compare.

Instead, we propose to use an agreement measure based on Krippendorff’s $\alpha$ [] and tree edit distance. In this approach we compare tree structures directly, which is extremely parsimonious in terms of assumptions, and furthermore sidesteps the problem of probabilistically modelling annotators’ behaviour entirely. Krippendorff’s $\alpha$ is not as commonly used as $\kappa$ and $\pi$, but it has the advantage of being expressed in terms of an arbitrary distance function $\delta$.

A full derivation of $\alpha$ is beyond the scope of this article, and we will simply state the formula used to compute the agreement. Krippendorff’s $\alpha$ is normally expressed in terms of the ratio of observed and expected disagreements: $\alpha =1-D_o/D_e$, where $D_o$ is the mean squared distance between annotations of the same item and $D_e$ the mean squared distance between all pairs of annotations:

Note that in the expression for $D_e$, we are computing the difference between annotations for different items; thus, our distance function for syntactic trees needs to be able to compute the difference between arbitrary trees for completely unrelated sentences. The function $\delta$ can be any function as long as it is a metric; that is, it must be (1) non-negative, (2) symmetric, (3) zero only for identical inputs, and (4) it must obey the triangle inequality:

1. 1.

   $\forall x,y:\delta \left(x,y\right)\ge 0$

2. 2.

   $\forall x,y:\delta \left(x,y\right)=\delta \left(x,y\right)$

3. 3.

   $\forall x,y:\delta \left(x,y\right)=0\iff x=y$

4. 4.

   $\forall x,y,z:\delta \left(x,y\right)+\delta \left(y,z\right)\ge \delta \left(x,z\right)$

This immediately excludes metrics like ParsEval [] and Leaf-Ancestor [], since they assume that the trees being compared are parses of the same sentence. Instead, we base our work on tree edit distance. The tree edit distance (TED) problem is defined analogously to the more familiar problem of string edit distance: what is the minimum number of edit operations required to transform one tree into the other? See \citeNBille05 for a thorough introduction to the tree edit distance problem and other related problems. For this work, we used the algorithm of \citeNZha:Sha89. Tree edit distance has previously been used in the TedEval software [] for parser evaluation agnostic to both annotation scheme and theoretical framework, but this by itself is still an uncorrected accuracy measure and thus unsuitable for our purposes.³³While it is quite different from other parser evaluation schemes, TedEval does not correct for chance agreement and is thus an uncorrected metric. It could of course form the basis for a corrected metric, given a suitable measure of expected agreement.

When comparing syntactic trees, we only want to compare dependency relations or non-terminal categories. Therefore we remove the leaf nodes in the case of phrase structure trees, and in the case of dependency trees we compare trees whose edges are unlabelled and nodes are labelled with the dependency relation between that word and its head; the root node receives the label $ϵ$. An example of this latter transformation is shown in Figure 1.

We propose three different distance functions for the agreement computation: the unmodified tree edit distance function, denoted ${\delta }_{plain}$, a second function ${\delta }_{diff}\left(x,y\right)=\mathrm{TED}\left(x,y\right)-\mathrm{abs}\left(\left|x\right|-\left|y\right|\right)$, the edit distance minus the difference in length between the two sentences, and finally ${\delta }_{norm}\left(x,y\right)=\mathrm{TED}\left(x,y\right)/\left|x\right|+\left|y\right|$, the edit distance normalised to the range $\left[0,1\right]$.⁴⁴We can easily show that $\left|x\right|+\left|y\right|$ is an upper bound on the TED, corresponding to deleting all nodes in the source tree and inserting all the nodes in the target.

The plain TED is the simplest in terms of parsimony assumptions, however it may overestimate the difference between sentences, we intuitively find to be syntactically similar. For example the only difference between the two leftmost trees in Figure 2 is a modifier, but ${\delta }_{plain}$ gives them distance 4 and ${\delta }_{diff}$ 0. On the other hand, ${\delta }_{diff}$ might underestimate some distances as well; for example the leftmost and rightmost trees also have distance zero using ${\delta }_{diff}$, despite our syntactic intuition that the difference between a transitive and an intransitive should be taken account of.

The third distance function, ${\delta }_{norm}$, takes into account a slightly different concern; namely that when comparing a long sentence and a short sentence, the distance has to be quite large simply to account for the difference in number of nodes, unlike comparing two short or two long sentences. Normalising to the range $\left[0,1\right]$ puts all pairs on an equal footing.

However, we cannot a priori say which of the three functions is the optimal choice of distance functions. The different functions have different properties, and different advantages and drawbacks, and the nature of their strengths and weaknesses differ. We will therefore perform a number of synthetic experiments to investigate their properties in a controlled environment, before applying them to real-world data.

In the previous section, we proposed three different agreement metrics ${\alpha }_{plain}$, ${\alpha }_{diff}$ and ${\alpha }_{norm}$, each involving different trade-offs. Deciding which of these metrics is the best one for our purposes of judging the consistency of syntactic annotation poses a bit of a conundrum. We could at this point apply our metrics to various real corpora and compare the results, but since the consistency of the corpora is unknown, it’s impossible to say whether the best metric is the one resulting in the highest scores, the lowest scores or somewhere in the middle. To properly settle this question, we first performed a number of synthetic experiments to gauge how the different metrics respond to disagreement.

The general approach we take is based on that used by \citeNMathet:etal12, adapted to dependency trees. An already annotated corpus, in our case 100 randomly selected sentences from the Norwegian Dependency Treebank [], are taken as correct and then permuted to produce “annotations” of different quality. For dependency trees, the input corpus is permuted as follows:

1. 1.

   Each token has a probability $p_{relabel}$ of being assigned a different label uniformly at random from the set of labels used in the corpus.

2. 2.

   Each token has a probability $p_{reattach}$ of being assigned a new head uniformly at random from the set of tokens not dominated by the token.

The second permutation process is dependent on the order the tokens are processed, and we consider the tokens in the post-order⁵⁵That is, the child nodes of a node are all processed before the node itself. Nodes on the same level are traversed from left to right. as dictated by the original tree. This way tokens close to the root have a fair chance of having candidate heads if they are selected. A pre-order traversal would result in tokens close to the root having few options, and in particular if the root has a single child, that node has no possible new heads unless one of its children has been assigned the root as its new head first. For example in the trees in figure 2, assigning any other head than the root to the Pred nodes directly dominated by the root will result in invalid (cyclic and unconnected) dependency trees. Traversing the tokens in the linear order dictated by the sentence has similar issues for tokens close to the root and close to the start of the sentence.

For our first set of experiments, we set $p_{relabel}=p_{reattach}$ and evaluated the different agreement metrics for 10 evenly spaced $p$-values between 0.1 and 1.0. Initial exploration of the data showed that the mean follows the median very closely regardless of metric and perturbation level, and therefore we only report the mean scores across runs in this paper. The results of these experiments are shown in Figure 3, with the labelled attachment score⁶⁶The de facto standard parser evaluation metric in dependency parsing: the percentage of tokens that receive the correct head and dependency relation. (LAS) for comparison.

The ${\alpha }_{diff}$ metric is clearly extremely sensitive to noise, with $p=0.1$ yielding mean ${\alpha }_{diff}=15.8\mathrm{\%}$, while ${\alpha }_{norm}$ is more lenient than both LAS and ${\alpha }_{plain}$, with mean ${\alpha }_{norm}=14.5\mathrm{\%}$ at $p=1$, quite high compared to $\text{LAS}=0.9\mathrm{\%}$, ${\alpha }_{plain}=-6.8\mathrm{\%}$ and ${\alpha }_{diff}=-246\mathrm{\%}$. To further study the sensitivity of the metrics to the two kinds of noise, we performed an additional set of experiments, setting one $p=0$ while varying the other over the same range as in the previous experiment, the results of which are shown in Figures 4 and 5.

The LAS curves are mostly unremarkable, with one exception: Mean LAS at $p_{reattach}=1$ of Figure 5 is 23.9%, clearly much higher than we would expect if the trees were completely random. In comparison, mean LAS when only labels are perturbed is 4.1%, and since the sample space of trees of size $n$ is clearly much larger than that of relabellings, a uniform random selection of tree would yield a LAS much closer to 0. This shows that our tree shuffling algorithm has a non-uniform distribution over the sample space.

While the behaviour of our alphas and LAS are relatively similar in Figure 3, Figures 4 and 5 show that they do in fact have important differences. Whereas LAS responds linearly to perturbation of both labels and structure, with its parabolic behaviour in Figure 3 being simply the product of these two linear responses, the $\alpha$ metrics respond differently to structural noise and label noise, with label disagreements being penalised less harshly than structural disagreements.

The reason for the strictness of the ${\alpha }_{diff}$ metric and the laxity of ${\alpha }_{norm}$ is the effects the modified distance functions have on the distribution of distances. The ${\delta }_{diff}$ function causes an extreme shift of the distances towards 0; more than 30% of the sentence pairs have distance 0, 1, or 2, which causes $D_e^{diff}$ to be extremely low and thus gives disproportionally large weight to non-zero distances in $D_o^{diff}$. On the other hand ${\delta }_{norm}$ causes a rightward shift of the distances, which results in a high $D_e^{norm}$ and thus individual disagreements having less weight.

Synthetic experiments do not always fully reflect real-world behaviour, however. Therefore we will also evaluate our metrics on real-world inter-annotator agreement data sets. In our evaluation, we will contrast labelled accuracy, the standard parser evaluation metric, and our three $\alpha$ metrics. In particular, we are interested in the correlation (or lack thereof) between LAS and the alphas, and whether the results of our synthetic experiments correspond well with the results on real-world IAA sets. Finally, we also evaluate the metric on both dependency and phrase structure data.

The most important conclusion we draw from this work is the most appropriate agreement metric for syntactic annotation. First of all, we disqualify the LAS metric, primarily due to the methodological inadequacies of using an uncorrected measure. While our experiments did not reveal any serious shortcomings (unlike those of [] who in the case of categorisation showed that for large $p$ the uncorrected measure can be increasing), the methodological problems of uncorrected metrics makes us wary of LAS as an agreement metric. Next, of the three $\alpha$ metrics, ${\alpha }_{plain}$ is clearly the best; ${\alpha }_{diff}$ is extremely sensitive to even moderate amounts of disagreement, while ${\alpha }_{norm}$ is overly lenient.

Looking solely at Figure 3, one might be led to believe that LAS and ${\alpha }_{plain}$ are interchangeable, but this is not the case. As shown by Figures 4 and 5, the paraboloid shape of the LAS curve in Figure 3 is simply the combination of the metric’s linear responses to both label and structural perturbations. The behaviour of $\alpha$ on the other hand is more complex, with structural noise being penalised harder than perturbations of the labels. Thus, the similarity of LAS and ${\alpha }_{plain}$ is not at all assured when the amounts of structural and labelling disagreements differ. Additionally, we consider this imbalanced weighting of structural and labelling disagreements a benefit, as structure is the larger part of syntactic annotation compared to the labelling of the dependencies/bracketings. Finally our experiments show that $\alpha$ is a single metric that is applicable to both dependencies and phrase structure trees.

Furthermore, $\alpha$ metrics are far more flexible than simple accuracy metrics. The use of a distance function to define the metric means that more fine-grained distinctions can be made; for example, if the set of labels on the structures is highly structured, partial credit can be given for differing annotations that overlap. For example, if different types of adverbials (temporal, negation, etc.) receive different relations, as is the case in the Swedish Talbanken05 [] corpus, confusion of different adverbial types can be given less weight than confusion between subject and object. The $\alpha$-based metrics are also far easier to apply to a more complex annotation task such as the tectogrammatical annotation of the PCEDT. In this task inserting and deleting nodes is an integral part of the annotation, and if two annotators insert or delete different nodes the all-or-nothing requirement of identical yield of the LAS metric makes it impossible as an evaluation metric in this setting.

I would like to thank Jan Štěpánek at Charles University for data from the PCEDT and help with the conversion process, the CDT project for publishing their agreement data, Per Erik Solberg at the Norwegian National Library for data from the NDT, and Emily Bender at the University of Washington for the SSD data.