Karën Fort
email: karen.fort@loria.fr

Adeline Nazarenko
email: adeline.nazarenko@lipn.univ-paris13.fr

Sophie Rosset
email: sophie.rosset@limsi.fr

Modeling the Complexity of Manual Annotation Tasks: a Grid of Analysis

Keywords: manual corpus annotation, annotation campaign management, annotation campaign cost estimate

Manual corpus annotation is getting widely used in Natural Language Processing (NLP). While being recognized as a difficult task, no in-depth analysis of its complexity has been performed yet. We provide in this article a grid of analysis of the different complexity dimensions of an annotation task, which helps estimating beforehand the difficulties and cost of annotation campaigns. We observe the applicability of this grid on existing annotation campaigns and detail its application on a real-world example.

Introduction

With the development of NLP applications, the annotation campaigns are becoming more numerous and more varied. Annotated corpora are used for acquiring knowledge as well as for testing theories, models and tools. They can be directly used in end-applications or for specific internal tasks.

Manual annotation is actually a widespread practice in NLP. It consists in adding labels of linguistic nature or reflecting the usage of NLP technologies on some oral or written discourse. This corresponds to a great diversity of phenomena, as these annotations vary in nature (phonetic, morpho-syntactic, semantic or task-oriented labels), in the range they cover (they can concern a couple of characters, a word, a paragraph or a whole text), in their degree of coverage (all the text is annotated or only a part of it) and in their form (atomic value, complex feature structures or relations and even cross-document alignment relations).

It has been a long road since the big pioneer annotation campaigns like the Penn Treebank [START_REF] Marcus | Building a large annotated corpus of English : The Penn Treebank[END_REF], but one problem remains: manual annotation is expensive. Various strategies have been implemented to reduce or control annotation costs. Tools have been developed to assist and guide the work of annotators. Automatic annotation methods, sometimes based on machine learning, have been introduced to relieve the annotator of the most trivial and repetitive work and to allow him/her to focus on the hardest annotation tasks where human interpretation is critical. For simple tasks, the use of crowdsourcing is developed with the idea of dividing up tedious work and exploiting the number of annotators to compensate for the heterogeneity of their competence and reliability. Significant efforts have also been made to develop evaluation protocols and to measure intra and inter-annotator agreements, which allow for a better control of the quality of the produced annotated data. Despite all this work and the experience gained in annotation, we lack a global picture or an overall methodology to a priori determine the various costs of an annotation campaign (task definition, data preparation, recruitment and management of annotators, annotation itself, quality control, etc.), make the necessary compromises and choose the appropriate solutions to alleviate the annotators' work.

This article relies on the analysis of many annotation campaigns, which are described in the state of the art or were managed by the authors. It does not offer a tool or a ready-made solution to tell you "how to build your next annotation campaign". Instead, we propose an analytical framework, a grid of analysis, to understand the complexity of annotation tasks. It is based on a decomposition of these tasks into elementary ones and a decomposition of complexity into 6 dimensions that are orthogonal to each other except for one. We also provide concrete metrics to measure the complexity of annotation tasks, a priori when possible, from already annotated samples or by comparison with similar annotation tasks. Our approach is pragmatic, as our aim is to provide practical tools to analyze the complexity in all its dimensions. Obviously, it gives a simplified view of complex annotation tasks, but it enables to compare different campaigns on a common basis. This article is as follows. Section 2 shows that the notion of complexity is present in many works in the state of the art but that no comprehensive analysis has been proposed so far. The third section presents our analysis of the complexity dimensions of annotation. Section 4 illustrates the practical benefit of this method of analysis and shows how to apply it on a complex task.

Feedback on large-scale campaigns

An effort has been made to document large-scale projects and encountered issues. For example, concerning the Penn Treebank, [START_REF] Marcus | Building a large annotated corpus of English : The Penn Treebank[END_REF] explains that the POS tagset has been largely reduced as compared to that of the Brown corpus, in order to eliminate the categories that could be deduced from the lexicon or the syntactic analysis. It is also noted that reducing the size of the tagset allows to reducing inconsistencies. Finally, in order to "avoid arbitrary decisions", the annotators were allowed to associate several categories to a same token. The same principle was used for the syntactic layer, allowing multiple binding in case of ambiguity. For the same reason, no distinction was made between arguments and circumstants. [START_REF] Abeillé | Building a treebank for French[END_REF] presents the main issues encountered during the French Treebank annotation and the found solutions. One difficulty concerns multi-word expressions that the campaign managers finally chose to annotate both as multi-word expressions and as distinct elements to avoid "linguistic debates". Another interesting issue concerns the hierarchical structure of the tagset. It allows to simplify the annotation as most of the sub-categories end up being unambiguous once the main category is selected. In the speech domain, the MEDIA annotation campaign gave rise to an in-depth reflexion on the methodology [START_REF] Bonneau-Maynard | Semantic annotation of the French media dialog corpus[END_REF], but is addresses the management of annotation campaigns rather than the analysis of annotation tasks.

Good practices in manual annotation

Good practices have progressively emerged to tackle various aspects of annotation tasks. They have been, in particular, inherited from corpus linguistics. [START_REF] Leech | Corpus annotation schemes[END_REF][START_REF] Leech | Developing Linguistic Corpora: a Guide to Good Practice, chapter Adding Linguistic Annotation[END_REF] present a list of what a specification for annotation should contain. It represents an effort toward the identification of several levels of difficulty encountered when making decisions during the manual annotation of a corpus: segmentation, inclusion of units (words or phrases) within other units (clauses or sentences), assigning categories to some textual fragments.

Annotation formats

Recommendations were published within the framework of the standardization effort of the annotation formats, in particular in [START_REF] Ide | Representing linguistic corpora and their annotations[END_REF], that finally gave birth to the ISO 24612 standard. In this view, the authors are little concerned by manual annotation difficulties as such but, to represent annotations they identify complex structuring elements which are of interest here : segmentation (identification of continuous or discontinuous sequences of characters), several layers of annotations (for example morpho-syntactic, then syntactic), relations between these layers, overlapping issues.

Organization of annotation campaigns

An overall schema of the organization of annotation campaigns has also emerged. It involves several actors, among which the client (who can, for example, be the organizer of an evaluation campaign), the annotation manager, that is the person who is going to write the annotation guide from a (clearly) expressed need, and the annotators themselves, who proceed from the annotation guide. The increasing use of so-called "non-experts", through crowdsourcing for example, introduced a further distinction between expert annotators (editors/curators in GATE Teamware [START_REF] Bontcheva | Web-based collaborative corpus annotation: Requirements and a framework implementation[END_REF]) and annotators themselves. The multiplication of actors contributes to the difficulty to organize an annotation campaign but not to that of the annotation task per se. Note also that the analysis we propose here applies whatever the level of expertise of the annotators. Besides, the annotation guide is recognized as the keystone of annotation campaigns, as it defines what should be annotated.

Here, we consider that the need is clearly defined and known from all the participants.

Annotation evaluation Studies concerning the evaluation of the quality of manual annotation allowed to identify some factors influencing inter-and intra-annotator agreements. [START_REF] Gut | Measuring the reliability of manual annotations of speech corpora[END_REF][START_REF] Bayerl | What determines inter-coder agreement in manual annotations? a meta-analytic investigation[END_REF] demonstrated that the inter-annotator agreement and the complexity of the annotation task are correlated (the larger the number of categories, the lower the inter-annotator agreement) and that the categories prone to confusions are in limited number. This brings out two complexity dimensions related to the number of categories and to the ambiguity between some categories. This ambiguity-related complexity dimension also appears in [START_REF] Popescu-Belis | Le rôle des métriques d'évaluation dans le processus de recherche en tal[END_REF]. In the study of the inter-annotator agreements, [START_REF] Krippendorff | Content Analysis: An Introduction to Its Methodology[END_REF]) identified a step of identification of the elements to annotate that is called "unitizing". Similarly, in the Proposition Bank project [START_REF] Palmer | The proposition bank: An annotated corpus of semantic roles[END_REF], the organizers separated role "identification" from role "classification" to compute the inter-annotator agreement, in order to "isolate the role classification decisions" from the (supposedly easier) identification.

Insights from Cognitive Science

Few publications focus on the difficulties of manual annotation. In [START_REF] Tomanek | A cognitive cost model of annotations based on eye-tracking data[END_REF], the authors used an eye-tracking device to analyze and model the annotation cognitive complexity. Their experiment was carried out on a simple named-entity annotation task (persons, locations and organizations), with some pre-identification of complex noun phrases containing at least one potential named entity. They measured the influence of the syntactic and semantic complexities1 as well as the size of context that was used by the annotators. The results show that the annotation performance tends on average to "correlate with the [semantic] complexity of the annotation phrase" and less so with its syntactic complexity, and that the size of the needed context also depends on the semantic complexity of the annotation phrase. However interesting, their conclusions only apply to simple named entity annotation task.

Measuring the complexity of an annotation task

Manual annotation requires the annotator to determine which units should be annotated and how. Measuring the complexity of an annotation task requires a detailed analysis of these localization and characterization operations.

We propose to analyze the complexity of elementary annotation tasks according to six dimensions: the first two (discrimination and delimitation) relate to the localization of annotations, while the next three concern their characterization (expressiveness, tagset dimension and ambiguity degree). The context is a sixth factor of complexity that impacts annotation decisions: it is presented here as a separate dimension for the sake of simplicity, even though it simultaneously affects discrimination, boundaries delimitation and disambiguation.

Analyzing a task along those six dimensions is artificial in the sense that annotators do not make separate decisions, but this analytic approach is meant for the management of annotation. It is independent from both the volume of annotations to be added and the number of annotators involved: these values participate in the cost of a task but not in its complexity, which is important to evaluate as early as possible in the annotation process.

Decomposition of annotation tasks

In an annotation task, one or several human annotators are asked to explicit how they interpret a source signal. The guidelines usually explain what kind of interpretation is expected and for which purpose. Depending on the task, the annotators are provided with a closed tagset or are allowed to introduce any tag they find relevant. The annotators have to read the source document and tag some or all of its segments with one or several tags.

Instead of decomposing annotations tasks into levels or layers [START_REF] Goecke | Different views on markup[END_REF], in order to analyze the task complexity, we propose to decompose a campaign into elementary annotation tasks (EATs). The complexity of the various EATs is computed independently and the complexity of a whole campaign is computed as the combination of the complexity of the elementary tasks. We consider that an annotation task can be decomposed into two or more EATs if the tagset itself is made of smaller independent ones.2 This decomposition in EATs is formal in the sense that it is independent of the pragmatic organization of the work: the annotators can handle different EATs as separate steps on the source signal or all at once depending on the specific nature of the work and the tools they use. The decomposition in EATs does not result in a simplification of the original task as it is often the case for the Human Intelligence Tasks (HITs) to be performed by Turkers (workers) in Amazon Mechanical Turk [START_REF] Cook | Automatically identifying changes in the semantic orientation of words[END_REF]. To take a simple example, the annotation of gene renaming relations can be analyzed as a combination of two EATs. The first one identifies the gene names in the source signal. The second one relies on the first level of annotation and indicates which of the genes hold in a renaming relation. Obviously, the annotators can add both types of annotations at the same time, but the tagsets are independent and it is easier, from a formal point of view, to analyze the annotation task as a combination of two EATs than as a unique, but complex one.

What to annotate?

Localizing the units to be annotated consists in distinguishing what is to be annotated from what is not, and potentially adjusting the boundaries of the identified units.

Discrimination

In some annotation experiments, the question of "what to annotate" is straightforward, for instance when the units to annotate have already been marked in an automatic pre-annotation phase or when all the units are to be annotated, as in a POS-tagging task. However, for the annotators, the corpus is often a haystack within which they must find what to annotate, and discriminating what should be annotated from what should not is a complex task.

Identifying the units on which the annotation work should focus is all the more complex as the units to consider are heterogeneous. [START_REF] Erk | Towards a resource for lexical semantics: a large German corpus with extensive semantic annotation[END_REF] emphasizes that semantic role annotation and discourse annotation mix several levels of segmentation (from less than a word to more than a sentence). As a simple example, it is easier to identify in a text negatively connoted adverbs, in particular, than all the negative expressions, as the latter can be words, phrases, or even entire parts of a text. In the second case several segmentation levels are actually to be considered. This gives a first scale of difficulty. An annotation task is considered difficult to the extent that the discrimination factor, defined by the following formula, is high:

Disc r iminat ion a (F ) = 1 - |A a (F )| n i=1 |D i (F )|
where F is the flow of data to annotate, a is an annotation task, n is the number of segmentation levels that are potentially relevant, |D i (F )| is the number of units obtained during the segmentation of F at level i and |A a (F )| is the number of units to be annotated in the relevant annotation task.

Intuitively, this measure indicates that the discrimination weight is high when the units to annotate or mark are "submerged" within others, and when the proportion of what is to be annotated (|A a (F )|) as compared to what could be annotated or is "markable" ( n i=1 |D i (F )) is low. The identification factor is 0 when all the units of the flow are to be annotated, and approaches 1 when only a few units are actually to be annotated while many could be annotated.

For the classification of pronouns as anaphoric or impersonal, the discrimination factor is 0 if all the occurrences of pronouns have been identified beforehand. By contrast, for gene renaming relations, the discrimination factor is high because only a small proportion of gene name couples participate in a renaming relation and are to be annotated as such. 3It is generally easy to estimate the number of units to be annotated -from the definition of the annotation task, on a sample of the relevant corpus or by reference to comparable tasksbut more difficult to estimate what could be annotated. This requires the choice of a reference segmentation that divides the flow to annotate into units, of which some are to be annotated, and others not. This reference segmentation can be chosen in different ways:

1. The simplest solution is to rely on an obvious segmentation which can be automatically computed or which is intuitive for the annotator, even if it implies reviewing the boundaries of the units to be annotated which do not correspond to this segmentation. For example, with named entities, starting from a segmentation into words leads to consider compound named entities as "modified" units. This strategy reduces the discrimination weight, but increases the issue of boundary delimitation (see section 3.2.2 below).

2. When the units to annotate are too heterogeneous, several reference segmentations can be considered (n > 1 in the preceding formula): this increases the number of "markables", but avoids the need to modify many boundaries. In the case of named entities annotation, one could for instance consider all the words and all the phrases as "markables". This approach must be used if it seems less costly than the previous one.

3. Finally, the annotation task can be decomposed into several layers, corresponding to distinct EATs. In that case, the discrimination weights of the layers are computed independently, each one with a specific reference segmentation. Such a decomposition is needed only when the different types of "markables" resulting from the various segmentations are annotated differently. It would be artificial for instance to decompose the task of named entities annotation into several EATs if the same tagset is used for words and phrases.

Boundary delimitation

Identifying points of interest in the flow of data is not enough, as the elements to be annotated are often data segments. To identify what to annotate, one should also delimit the boundaries of the segment to be annotated.

Here again, the task is easy when a reliable reference segmentation can be computed. However, segmentations that can be computed automatically are often approximations and the annotator must locally modify the boundaries of the discriminated units: for instance, if one starts with a segmentation into words to annotate named entities or terms, the segmentation must be corrected for all the multi-word expressions. In most cases, delimiting the boundaries consists in enlarging or reducing the discriminated unit based on the reference segmentation, but there are also cases in which a discriminated unit should be decomposed in several units or where several contiguous discriminated units are grouped together into one annotation. 4Delimitation of boundaries represents a second complexity factor, Delimi t at ion a (F ), which is computed by comparing the segmentation obtained after the annotation to the reference segmentation. This factor is inspired from the slot error rate [START_REF] Makhoul | Performance measures for information extraction[END_REF], a metric that is used in named entities recognition and classification and which takes boundary errors into account. Once the discriminated units before and after the boundary delimitation are optimally aligned, we can compute the following discrimination rate:

Del imi t at ion a (F ) = min( S + I + D |A a (F )| , 1)
where |A a (F )| is the final number of discriminated units, I the number of inserted units, obtained by initial units decomposition, D the number of units deleted when grouping some of the initial units, and S is the number of substitutions, i.e. the number of discriminated units that underwent a change in their boundaries other than that of the previous decomposition and grouping cases.

This delimitation factor is worth 0 when no discriminated unit has been modified and it rises with the number of decompositions, groupings and boundary modifications performed by the annotator with respect to the reference segmentation. The value is limited to 1 to keep the same interval [0, 1] for the six complexity factors.

The delimitation cost is measured a posteriori, but it can be estimated based on a sample of annotated corpus or by comparison with a similar task.

How to annotate?

Once the units have been discriminated and delimited, they have to be characterized.

Expressiveness of the annotation language

We distinguish between three types of annotation languages: type, relational and higher order languages.

In the simplest case, annotation consists in associating a type with a data segment, i.e. in labeling it. Many annotation tasks rely on such a type language: words of a text are associated with part-of-speech, speech turns are associated with interlocutors or with rhetorical functions, phrases are associated with named entities types. In some cases, the label that is used is itself structured, as with morpho-syntactic labels associating a part-of-speech with a lemma and its morpho-syntactic features, but such structuring increases the size of the tagset (see section 3.3.2) without changing the expressiveness of the annotation language.

Establishing relations between units is also a common task, but it is more complex. The complexity of relational annotations should not be underestimated: even if annotators do not always proceed in exactly this way, they have to locate and type the arguments of the relation, discriminate the couples, triplets, and more generally the n-uplets of segments to annotate among the set of n-uplets that are markable, and finally type the relation existing between the elements of the n-uplet.

A higher-order language is used when annotations are added to other annotations, but the complexity of this type of language, which is difficult to formalize and manipulate, is such, that it is often reduced to a simpler language. For example, to qualify an annotation as uncertain, the generally preferred option is to increase the tagset size so as to add the qualifier as an attribute associated with a main type. Alternatively, the decomposition of an annotation task into EATs also allows to qualify or relate, in a later step, annotations added in a previous one: you obtain several EATs, each one relying on a first order annotation language.

The degree of complexity entailed by the expressiveness of the annotation language is naturally represented by an ordinal qualitative scale, but for the sake of homogeneity with the previous factors, described by numeric values, we associate the different levels of expressiveness with graduations on a numeric scale from 0 to 1. In this scale, 0.25 corresponds to type languages, 0.5 and 0.75 to relational languages, respectively of arity 2 and higher than 2, while the maximal value, 1, is dedicated to higher-order languages.

Tagset dimension

The annotator generally selects the value of an annotation in a predefined tagset that is presented in the annotation guide and this choice is all the more difficult to make as it is open. The size of the tagset is therefore a new factor of complexity.

In the simplest case, the choice is boolean and annotating amounts to assigning the discriminated units into two categories:5 sentences may be marked as relevant or not; the occurrences of the it pronoun are marked as anaphoric or impersonal.

However, the choice is often more open, for instance for representing the diversity of morphosyntactic units, annotating syntactic dependencies or typing named entities. For the richest annotations, structured labels are often proposed: the annotator adds several labels on a single given unit, the combination of which forms the final annotation [START_REF] Dandapat | Complex linguistic annotationno easy way out! a case from bangla and hindi POS labeling tasks[END_REF].

Finally, there are annotation tasks for which the choice of a label is entirely left to the annotator, as in speech transcription, where there may be as many labels as words. In such cases, we consider that we have a huge tagset, even though the annotation effort is probably of a slightly different nature for the annotator.

If an annotation A is formed of a sequence of m labels (A = E 1 E 2 . . . E m ) and each label E i can take n i different values, the complete tagset theoretically contains n different labels, with n = n 1 * n 2 * . . . * n m . However, in practice, constraints are defined which reduce the number of combinations: the annotator does not have to choose one label from n at once, but instead first select 1 label among n 1 labels, then 1 among at most n 2 , etc. up to 1 among at most n m . The size of the tagset does not depend on the total number of possible labels but on the degrees of freedom of the successive choices that the annotator has to make. The total degree of freedom ν for the choice of m labels is given by the following formula:

ν ≤ ν 1 + ν 2 + . . . + ν m
where ν i is the maximal degree of freedom the annotator has when choosing the i th label (ν i = n i -1). 6 For instance, the tagset for the POS part of the Penn Treebank contains 36 tags [START_REF] Santorini | Part-of-speech tagging guidelines for the Penn Treebank Project[END_REF], so ν equals 35, but as some tags are subtypes of others (like JJR and JJS for JJ) there are 21 in fact tags corresponding to main categories, and, as the maximum number of subtypes is 6 (for verbs), we may consider that ν = 20 + 5 = 25.

The tagset dimension can be computed using the following formula:

Dimension a (F ) = min( ν τ , 1)
where ν is the global degree of freedom the annotator has when choosing a label for an annotation task a within a flow of data F , and τ is the threshold from which we consider the tagset as arbitrarily large. In the experiments detailed below, τ is worth 50, based on the feedback of the annotators.

The tagset dimension is worth 0 for the binary tagsets presenting a degree of freedom of 1 and it increases with the size of the tagset and the correspondingly increasing degree of freedom. It is worth 0.5 for the Penn Treebank POS tag annotation (0.7, if we consider the tagset as flat). It reaches a ceiling at 1. Annotation tasks with large tagsets (> τ) are very difficult to manage.

Degree of ambiguity

The need to disambiguate the units to annotate introduces a fifth complexity factor, which is more difficult to estimate than the previous ones. As the role of the annotator is precisely to resolve ambiguous cases whenever possible, ambiguities are difficult to observe. Still, we can evaluate the ambiguity degree the annotator must resolve for a given task in two ways.

The first method consists in measuring the residual ambiguity degree by observing the traces left by the annotator during the annotation: the annotation protocol may allow the annotator to annotate with several labels in case of ambiguity, to use an under-determined label, or even to add an uncertainty feature to the chosen label. This allows measurement of the degree of residual ambiguity:

Ambi gui t y Res,a (F ) = |Annot A | |Annot|
where a and F are the annotation task and the flow of data to be considered and where |Annot A | and |Annot| are respectively the number of annotations bearing an ambiguity mark and the total number of annotations added to F . By definition, this residual degree of ambiguity can only be measured a posteriori, once the annotation has been performed, or from a sample of it.

The degree of residual ambiguity is worth 0 when no ambiguity mark was added by the annotator and would be worth 1 in the case (in real life, absurd) where all the annotations were marked as ambiguous, in one way or another. Obviously, depending on the traces which are used to compute it and on the directions given to the annotators, this metric can be more or less reliable and it should be associated, whenever possible, with results from another method.

This second method consists in measuring the theoretical degree of ambiguity for the tasks where several occurrences of the same vocables (vocabulary units) are annotated: this method applies to morpho-syntactic annotation or to semantic disambiguation but not to speech turn analysis or gene renaming relations. This metric relies on the idea that ambiguous vocables have occurrences that are annotated differently at different locations in the flow of data.

The ambiguity factor is given by the proportion of units to be annotated that correspond to ambiguous vocables. The theoretical ambiguity can be measured from a dictionary that lists the possible labels for all the vocables, if the annotation relies on such a dictionary or, directly, on a sample of annotated text. The theoretical ambiguity also depends on the frequency of ambiguous vocables in the flow of data to be annotated. It is computed in the following way:

Ambi gui t y T h,a (F ) = |Voc(F )| i=1 (Ambi g a (i) * f r eq(i, F )) |U ni ts a (F )| with Ambi g a (i) = 1 if |La bels a (i)| > 1 0 else
where Voc is the vocabulary of the units of the flow of data F , |Voc(F )| the size of the vocabulary, f r eq(i, F ) the frequency of the vocable i in F , |U ni ts a (F )| the number of units to annotate in F and |La bels a (i)| the number of labels available for the vocable i for the annotation task a.

When there is no ambiguous vocable, |La bels a (i)| is worth 1 and Ambi g a (i) is worth 0 for every i, the annotation task is trivial and can be easily automated by projecting on the flow of data a dictionary establishing the correspondence between the vocables and their labels. In this case, Ambi gui t y T h,a (F ) is worth 0. Conversely, if all the vocables are ambiguous, Ambi gui t y T h,a (F ) is worth 1. Note that the weight of an ambiguous vocable influences the degree of theoretical ambiguity in proportion to its frequency.

Theoretical ambiguity tends to overestimate the weight of the ambiguity for the annotator as some ambiguities are probably trivial to solve.

The weight of the context

The weight of the context is a sixth complexity factor. Even though it is not independent from the previous factors as they were from each other (it makes discrimination, delimitation and disambiguation more complex for the annotator), we represent it here as such, for the sake of simplicity.

The complexity of an annotation task increases with the size of the window to take into account around the unit to annotate and with the number of knowledge elements to be rallied. While it is difficult to determine the number of words participating in the resolution of an annotation task and a fortiori the number of knowledge elements at issue7 , we can identify two qualitative scales: the size of the data to be taken into account around the unit to be annotated and the degree of accessibility of the sources of knowledge that are consulted.

For the sake of homogeneity with the previous complexity factors, we translate the two preceding qualitative scales into a common discreet scale from 0 to 1:

• 0 corresponds to cases where no data around the unit to be annotated and no additional knowledge come into play. This is a theoretical case, since an annotation task where no context whatsoever is needed should actually be automated.

• Conversely, 1 is for the most complex cases, where the whole data flow and exterior sources of knowledge are necessary to annotate the units. The gene renaming relations annotation is one such, as the renaming relation, often hardly noticeable in the data flow, can often be confused with an isotopy (resemblance) relation or the membership in a common family. One must read the whole abstract to determine the semantics of the relation and sometimes the annotators must refer to an external source to better understand the properties of the genes and support their decision.

• We estimate at 0.25 the weight of the context in two cases: 1) if the annotation depends on the immediate environment of the unit to be annotated, or 2) if only provided sources, such as annotation guidelines, are to be consulted.

• The complexity is evaluated at 0.5 in three cases: 1) if the two previous difficulties combine; 2) if a larger part of the data is needed; or 3) if a well-identified exterior source of knowledge is to be consulted.

• Finally, the complexity is evaluated at 0.75 in three cases: 1) if the annotator must read the whole sentence and consult exterior sources to add annotations; 2) if s/he must take the entire flow of data into account; 3) if s/he must look for new knowledge sources.

This scale is obviously oversimplifying, but it is important to take that factor into consideration when planing an annotation campaign and the above criteria are meant for guiding the analysis and facilitating the comparison between complexity dimensions.

Synthesis

Since the six complexity factors are normalized on the same scale, once the complexity of different tasks is analyzed, it is easy to represent the various dimensions on a spider graph.8

Let us consider for instance the simple task, already mentioned, that consists in classifying pronoun occurrences as impersonal or anaphoric (REF OMITTED). Since the pronouns are previously tagged, both discrimination and delimitation are worth 0. The tagset being composed of two tags, this dimension is also at 0 and the expressiveness of the annotation language is 0.25 (type language). However, the ambiguity degree is high (1) as all occurrences are ambiguous.

From our personal experience of annotation, we know that the context is worth 0.5 (or more) as the whole sentence must be considered to understand the role of the pronouns. The complexity of this task is represented on Figure 1a. The case of gene renaming [START_REF] Jourde | BioNLP shared task 2011 -bacteria gene interactions and renaming[END_REF]) is a little bit more complex and it is best analyzed as a combination of two EATs. Representing each EAT on a separate spider graph gives no idea of the whole task. We rather recommend to represent all EATs of a task in a single graph, which scale must be enlarged in proportion (from 0 to 2), as in Figure 1b. In the present case, the first EAT is the tagging of gene names in the sequence of words that composes the text. The discrimination factor is high (0.9), as only few words are gene names. Delimitation is 0, as gene names, in our example, are simple tokens. On the contrary, the characterizing factors are low: the tagset is boolean (Dimension=0), a type language is used (Expressiveness=0.25) and ambiguity is very low as only few gene names are also common names (theoretical ambiguity can be approximated at 0.019 and residual ambiguity is on average of 0.04 for two annotators). In this case, the context is the highest factor as it is often necessary to read the whole PubMed abstract to understand the role of a mentioned entity and as annotators sometimes consult external resources (context weights 1) (Fort et al., 2010). This first EAT is represented on the same graph as the pronoun classification, thus enabling the comparison of the two tasks (see Figure 1a). If they both show little complexity on three dimensions (delimitation, expressiveness, tagset dimension), the first one (pronouns) presents a high ambiguity dimension and no discrimination problem, while the second one (gene names) shows high complexity levels on the discrimination and context dimensions and no ambiguity. The solutions to alleviate the costs of these campaigns should therefore be adapted (pre-annotation and easy access to context for gene name tagging, and probably a carefully designed documentation for the pronoun classification).

Gene renaming consists in linking the gene name occurrences that hold a renaming relation. The whole task therefore comprises a second EAT, which consists in marking the renaming relations or its absence on any couple of gene names co-occurring in the same abstract. In that case, the discrimination is high (0.95) as only few gene couples are actually renaming each other. Delimitation is null since the gene names have already been annotated. The tagset is composed of 3 tags as the renaming relation is oriented (Dimension=0.04). Even if the annotations carry relational information, the language is a type language (a couple of gene names bears a tag, which expresses the direction of the relation). Ambiguity is very low (residual ambiguity is on average of 0.02 for the two annotators), but the context is high, as in the previous case. Figure 1b shows how the two EATs are combined to provide an analysis of the complexity of the whole task, which proves to be focused on discrimination and context.

Validation and illustration

Experimental validation

Although, as we showed in section 2, this grid of analysis has never been identified as such, some existing results or experiments confirm its applicability.

One first example of this is related to discrimination. In experiments led on the effects of pre-annotation on POS-tagging, the authors of [START_REF] Fort | Influence of pre-annotation on POS-tagged corpus development[END_REF] showed that if the automatic pre-annotation is of very good quality, i.e. if only few tokens disseminated within the text have to be corrected, very good annotators can end up with less good annotation results, due to lapses in their concentration. This corresponds directly to the discrimination dimension we present here, which tends to get higher if the annotations to perform are submerged within the text. Also, it has been observed that the quality of the annotation decreases with the number of tags involved [START_REF] Bayerl | What determines inter-coder agreement in manual annotations? a meta-analytic investigation[END_REF]. Structuring the tagset allows to reduce the degree of freedom at one point of choice and an appropriate annotation tool can help efficiently dealing with the hierarchy of tags [START_REF] Dandapat | Complex linguistic annotationno easy way out! a case from bangla and hindi POS labeling tasks[END_REF].

Such an annotation tool can also help with complex language types, like relations, providing a graphical, user-friendly way to annotate them, like with Knowtator [START_REF] Ogren | Knowtator: A plug-in for creating training and evaluation data sets for biomedical natural language systems[END_REF]. However, the number of manipulations involved is still higher than for simple type languages.

From the ambiguity point of view, the most obvious way to reduce it is to identify and remove the cases which are problematic. In the syntactic part of the Penn Treebank annotation, significant time was saved by reducing the ambiguity causes: "It proved to be very difficult for annotators to distinguish between a verb's arguments and adjuncts in all cases. Allowing annotators to ignore this distinction when it is unclear (attaching constituents high) increases productivity by approximately 150-200 words per hour." [START_REF] Marcus | Building a large annotated corpus of English : The Penn Treebank[END_REF]. The analysis we propose here should help identifying these cases sooner in the process.

In the context of the gene renaming annotation campaign, we discovered that in some cases, the annotators needed the whole text to make their final decisions, and not only the abstract they had to annotate, as it was initially planned. If this need could have been identified beforehand, it would have been taken into account and the annotation tool would have been parameterized to give an easy access to the whole documents to annotators.

Example: structured named entities

We applied this analysis on a structured named entity annotation campaign for French described in [START_REF] Grouin | Proposal for an extension of traditional named entities: From guidelines to evaluation, an overview[END_REF].

Structured named entities

Within the Quaero program10 , a new definition of structured named entities was proposed. This new structure relies on two principles: the entities are both hierarchical and compositional. An entity is then composed of two kinds of elements: the 7 types (and 32 subtypes) which refer to a general segmentation of the world into major categories and the 31 components which allow to tag every word of the entity expression. Following this definition, the annotation campaign can be decomposed into two EATs: types and components. Figure 2 illustrates this definition on a French phrase. The types (EAT 1) are shown in red tags and the components (EAT 2) in blue tags. Analysis For this illustration, we used the French spoken data provided by the mini-reference corpus (see [START_REF] Grouin | Proposal for an extension of traditional named entities: From guidelines to evaluation, an overview[END_REF]) comprising 11,532 tokens, 1,161 entity types and 1,778 components.11 Figure 3 represents the overall scores for this task using a spider graph.

The discrimination score is of 0.90 for the annotation of the types and 0.14 for the annotation of the components. To compute a delimitation score on such data, we first replaced in the annotated file every tag with a simple tag (annot) and in the same, but unannotated, file (as a reference file, under the hypothesis where tokens constitute the normal delimitation) we added the same tag around each token. Then we computed a slot error rate (SER) between these two files. The SER for types is over 100% (Delimitation=1) and the SER for components is 30% (Delimitation=0.3).

The annotation language is a type language, the degree of expressiveness is therefore of 0.25 for each of the EATs. Taking into account the types and sub-types structure, the total degree of freedom ν for the annotation of the different types (EAT 1) is 10. The dimension score is then of 0.2. Concerning the components EAT, the total degree of freedom is 30 and the dimension score of 0.6. The theoretical ambiguity is computed for each EATs. The score is of 0.15 and 0.12 for the types and components respectively. These scores are low and the tasks do not seem very complex from the point of view of this dimension. The sample size is probably to blame here, as, if we compute this score a posteriori using the overall corpus (which is of course not possible in a real situation) the scores are of 0.49 for the components and of 0.36 for the types. Additional experimental results are necessary to take this scaling factor into account in the measure of ambiguity.

Concerning the weight of the context we estimate it at 0.75 because the annotators had to take into account the entire flow of data (the entity definition is contextual). Moreover, it was sometimes necessary to validate a choice by exploring external data (such as Wikipedia). This analysis validates the choice of the hierarchical tagset that has been done for the annotation campaign described in [START_REF] Grouin | Proposal for an extension of traditional named entities: From guidelines to evaluation, an overview[END_REF]. Had a flat tagset been chosen, the dimension score would have been 1 (ν = 61). Moreover, this analysis is in line with what was observed concerning the context weight within the campaign [START_REF] Rosset | Structured named entities in two distinct press corpora: Contemporary broadcast news and old newspapers[END_REF]. Of course, it presents some limits as it has been shown for the ambiguity score computation.

Conclusion

The grid of analysis we propose here should be used as part of the preparatory work of any annotation campaign, large or small. Obviously, when done a priori, on a small sample of annotations, the results will be approximate, but we believe that the analysis itself helps asking the right questions and finding the appropriate solutions.

Obviously, this pre-campaign work should be supported by an appropriate tool, so that this grid of analysis is computed more or less automatically. We are writing specifications for such a module, intended to be plugged into annotation management tools like Slate [START_REF] Kaplan | Annotation process management revisited[END_REF] or GATE Teamware [START_REF] Bontcheva | Web-based collaborative corpus annotation: Requirements and a framework implementation[END_REF].

Figure 1 :

 1 Figure 1: Two synthesis examples

Figure 2 :

 2 Figure 2: Multi-level annotation of entity types (red tags) and components (blue tags): new minister of budget, François Baroin.

Figure 3 :

 3 Figure 3: Synthesis of the complexity for the structured named entities campaign (2 EATs, double scale)

Respectively measured as the "number of nodes in the parse tree" and the "inverse document frequency of the words in the phrase according to a reference corpus".

Independence, here, means that the tags of two different tagsets are globally compatible (even if some specific combinations may be forbidden), whereas the tags of a single tagset are mutually exclusive (except for encoding ambiguity).

We assume here that the gene names are pre-annotated (or identified in a different EAT) and that all gene name couples in the same abstract are "markable", i.e. subject to expressing a renaming relation.

We neglect here the case of discontinuous units, which are often not annotated as such and which are not numerous enough to impact the present analysis.

This boolean annotation is similar to the discrimination task, though the units to be annotated should be not only located but labeled.

The formula gives a high boundary of the global degree of freedom because the choice of the i th label is often constrained by the labels already added, so the annotator has in practice a degree of freedom that is less than (n i -1), if n i is the number of available labels at this point.

Assuming that the elements of knowledge are countable, which is obviously an oversimplification.

The results presented in all the graphs in the article are rounded up/down to the nearest integer.

To obtained this, we checked how many of the tagged gene names could also be tokens from the Brown corpus.

www.quaero.org

This mini-reference corpus is a sub-part of the whole corpus, that contains 1,291,225 tokens, 113,885 types and 146,405 components.

http://quaero.org/

Acknowledgments

This work was realized as part of the Quaero Programme 12 , funded by OSEO, French State agency for innovation.


Yann Mathet
email: yann.mathet@unicaen.fr

Antoine Widlöcher
email: antoine.widlocher@unicaen.fr

Karën Fort
email: karen.fort@loria.fr

Claire François
email: claire.francois@inist.fr

Olivier Galibert
email: olivier.galibert@lne.fr

Cyril Grouin
email: cyril.grouin@limsi.fr

Juliette Kahn
email: juliette.kahn@lne.fr

Sophie Rosset
email: sophie.rosset@limsi.fr

Pierre Zweigenbaum
email: pierre.zweigenbaum@limsi.fr

Manual Corpus Annotation: Giving Meaning to the Evaluation Metrics

Keywords: inter-annotator agreement, manual corpus annotation, evaluation

Computing inter-annotator agreement measures on a manually annotated corpus is necessary to evaluate the reliability of its annotation. However, the interpretation of the obtained results is recognized as highly arbitrary. We describe in this article a method and a tool that we developed which "shuffles" a reference annotation according to different error paradigms, thereby creating artificial annotations with controlled errors. Agreement measures are computed on these corpora, and the obtained results are used to model the behavior of these measures and understand their actual meaning.

Introduction

The quality of manual annotations has a direct impact on the applications using them. For example, it was demonstrated that machine learning tools learn to make the same mistakes as the human annotators, if these mistakes follow a certain regular pattern and do not correspond to simple annotation noise [START_REF] Reidsma | Reliability measurement without limits[END_REF][START_REF] Schluter | Treebank-Based Deep Grammar Acquisition for French Probabilistic Parsing Resources[END_REF]. Furthermore, errors in a manually annotated reference corpus (a "gold-standard") can obviously bias an evaluation performed using this corpus as a reference. Finally, a bad quality annotation would lead to misleading clues in a linguistic analysis used to create rule-based systems. However, it is not possible to directly evaluate the validity of manual annotations. Instead, interannotator agreement measures are used: at least two annotators are asked to annotate the same sample of text in parallel, their annotations are compared and a coefficient is computed. The latter can be of many types and the well-known Kappa-family is described in details in [START_REF] Artstein | Inter-coder agreement for Computational Linguistics[END_REF]. However, as pointed out by the authors of this article, the obtained results are difficult to interpret. Kappa coefficients, for example, are difficult to compare, even within the same annotation task, as they imply a definition of the markables that can vary from one campaign to the other [START_REF] Grouin | Proposal for an extension of traditional named entities: From guidelines to evaluation, an overview[END_REF]. More generally, we lack clues to know if a Kappa of 0.75 is a "good" result, or if a Kappa of 0.8 is twice as good as one of 0.4 or if a result of 0.6 obtained using one coefficient is better than 0.5 with another one, and for which annotation task.

We first briefly present the state of the art (Section 2), then detail the principles of our method to benchmark measures (Section 3) and show on some examples how different coefficients can be compared (Section 4). We finally discuss current limitations and point out future developments.

State of the art

A quite detailed analysis of the most commonly used inter-annotator agreement coefficients is provided by [START_REF] Artstein | Inter-coder agreement for Computational Linguistics[END_REF]. They present the pros and cons of these methods, from the statistical and mathematical points of view, with some hints about specific issues raised in some annotation campaigns, like the prevalence of one category. A section of their article is dedicated to various attempts at providing an interpretation scale for the Kappa family coefficients and how they failed to converge. Works such as [START_REF] Gwet | Handbook of Inter-rater Reliability[END_REF] are also to be mentioned. They present various inter-rater reliability coefficients and insist on benchmarking issues related to their interpretation.

Many authors, among whom [START_REF] Grouin | Proposal for an extension of traditional named entities: From guidelines to evaluation, an overview[END_REF][START_REF] Fort | Analyzing the impact of prevalence on the evaluation of a manual annotation campaign[END_REF], tried to obtain a more precise assessment of the quality of the annotation in their campaigns by computing different coefficients and analyzing the obtained results. However, their analyses lack robustness, as they only apply to similar campaigns. Other studies concerning the evaluation of the quality of manual annotation identified some factors that influence inter-and intra-annotator agreements, thereby giving clues on their behavior. [START_REF] Gut | Measuring the reliability of manual annotations of speech corpora[END_REF] thus demonstrated that the inter-annotator agreement and the complexity of the annotation task are correlated: the larger the number of categories, the lower the inter-annotator agreement. However, categories prone to confusion are in limited number. The meta-analysis presented by [START_REF] Bayerl | What determines inter-coder agreement in manual annotations? A meta-analytic investigation[END_REF] extends this research on the factors influencing agreement results, identifying 8 such factors and proposing useful recommendations to improve manual annotation reliability. However, neither of these studies provides a clear picture of the behavior of the agreement coefficients or of their meanings. The experiments detailed in [START_REF] Reidsma | Reliability measurement without limits[END_REF]) constitute an interesting step in this direction, focusing on the effect of annotation errors on machine learning systems and showing the impact of the form of disagreements on the obtained quality (random noise disagreement being tolerable, but not patterns in disagreements). This work puts Kappa-like coefficients results into perspective but presents a tool-oriented view, limited to these coefficients. In summary, the domain lacks a tool providing a clear and generic picture of the agreement coefficients behavior, allowing to better qualify the obtained agreement results.

Generating benchmarking corpora: the Corpus Shuffling Tool

The method presented in this section is currently restricted to annotation campaigns consisting in delimiting a span of text and characterizing it. It will be extended in the future to relations and more complex structures.

Objectives and principles

Manual annotation, as already mentioned, is subject to human errors. Except for very simple annotation tasks, these errors may involve several paradigms. Indeed, each manually annotated element may diverge from what it should be (which is called the reference, see below), in one or multiple ways, including: (i) the location is not correct (the frontiers of an element do not exactly match those of the reference); (ii) the characterization is not correct (wrong category, or wrong feature value); (iii) the annotation does not belong to the reference (false positive); or (iv), on the contrary, a reference element is missing (false negative). All of these error paradigms tend to damage the annotations, so each of them should be taken into account by agreement measures. We propose here to apply each measure to a set of corpora, each of which embeds errors from one or more paradigms, and with a certain magnitude (the higher the magnitude, the higher the number of errors). This experiment should allow us to observe how the measures behave w.r.t. the different paradigms, and with a full range of magnitudes. The idea of creating artificial damaged corpora is inspired by [START_REF] Pevzner | A critique and improvement of an evaluation metric for text segmentation[END_REF], then [START_REF] Bestgen | Quels indices pour mesurer l'efficacité en segmentation thématique[END_REF] in thematic segmentation, but our goal (giving meaning to measures) and our method (e.g. applying progressive magnitudes) are very different.

Protocol

Reference. A reference annotation set (called reference) is provided to the system: a true Gold Standard or an automatically generated set based on a statistical model. It is assumed to correspond exactly to what annotations should be, with respect to the annotation guidelines.

Shuffling.

A shuffling process is an algorithm that automatically generates a multi-annotated corpus given three parameters: a reference annotation, a number n of annotators to simulate, and a coefficient 0 ≤ m ≤ 1 called magnitude (in reference to earthquake measures). Each time it is run, it creates a set of n parallel annotations (simulating n different annotators) on the corpus, but with a quality damaged according to magnitude m. Process. The system iteratively runs a given shuffling process on the full range of possible magnitudes (from 0 to 1) with a parametrizable step (default is 0.05).

Agreement measure graph. For each of these annotation sets, i.e., for each magnitude, we submit each agreement measure we want to evaluate, and record its score. At the end of the process, we obtain a graph showing how a given measure reacts to a progressive shuffling, where the x-axis represents the magnitude from 0 to 1, and the y-axis represents the agreement.

Overview of the implemented shuffling processes

All processes described here come from real observations of various corpora: false positives and false negatives are usual in many campaigns, fragmentation and shift are observed in thematic segmentation, category mistake is so usual that most agreement measures (e.g. Kappa) address it, and combination of them appear for instance in discourse annotation.

False negative

A false negative is the fact for an annotator not to annotate an element belonging to the reference. It is simulated as follows: (i) magnitude m = 0: the annotator did not miss any annotation;

(ii) magnitude m = 1: the annotator missed all the annotations and therefore did not produce any; and (iii) 0 < m < 1: each element to be annotated has a probability m of being missed.

False positive

Reversely, a false positive is the fact for an annotator to annotate an element not belonging to the reference. We made the following decisions: (i) the maximum shuffling corresponds to adding x times the number of elements of the reference, x default value being 1; (ii) for 0 ≤ m ≤ 1, m • x elements are added; (iii) the way annotations are added is done with respect to the characteristics of the reference (statistical distribution of categories, etc.)

Fragmentation

Sometimes, annotators have the choice between using several contiguous elements (of the same category), or just one (covering the same text spans). Fragmentation simulates this by splitting up reference elements. The protocol is as follows, n being the number of reference elements: (i) the number of fragmentations to apply is n frag = n • x • m, where x is settable (its default value is 1); (ii) for each fragmentation to apply, one element is chosen at random, and is split (not necessarily in its center); (iii) the fragment of a split may be re-split next time, so that we finally get several levels of fragmentation.

Shift

In some annotation campaigns, annotators manage to properly identify the phenomenon to annotate, but have trouble locating it perfectly. We try to reproduce this error paradigm with the shift shuffling, that moves the frontiers of the reference annotations. It is defined as follows: (i) for magnitude m, we take into account the average length of the elements (w.r.t. their category), using for instance a statistical model as described in section 3.2, called maxlength, to compute the possible shifting latitude of each frontier, called maxlat, as follows: maxlat = maxlength • m • x, where m is the magnitude and x is a parameter whose default value is 2; (ii) a number is chosen at random for each frontier, in the range from -maxlat to +maxlat, and the frontier is shifted by this algebraic value. This shuffling process is conceptually more difficult to design than the previous ones because the shuffling space being finite (the text length), it is difficult to know to what extent it is actually possible to shuffle the annotations.

Category mistake

A frequent annotation mistake is to assign a wrong category to an annotated element. Two important phenomena are to be mentioned, that are quite frequent and lead to some important differences among current measurement methods: Prevalence is the fact that some categories are more frequent than others. Some measures take this phenomenon into account in their definition of so-called (and controversial) chance correction in order not to overrate the observed agreement. Overlapping is the fact for two categories to cover, even slightly, a same phenomenon: in such cases, annotators happen to choose a wrong but not so different category, and some measures consider them as less important mistakes. The question now is to define how best to simulate, the more gradually possible, a progressive category assignation mistake. To define such a simulation, we rely, for a given magnitude, on a matrix that indicates, for each category of the reference annotation, what is the probabilistic distribution of the chosen categories for 100 annotations. We have made the following choices: (i) for m = 0, we use the perfect matrix A (as given in table 1); (ii) for m = 1, we use the worst matrix B or C depending on the choice of simulating prevalence (B) or not (C). The prevalence matrix B simulates a (semi) random behavior with respect of the prevalence observed in the reference, while the noPrevalence matrix C reflects a full random choice; (iii) Besides, overlapping is simulated by the overlapping matrix D, which describes the way an annotator, for a given category in the reference, makes mistakes more often in favor of friendly categories than in favor of others; (iv) then, for each 0 < m < 1, we built a matrix by weighted averaging of perfect matrix (100% weighted at m = 0) and worst matrix (100% weighted at m = 1), as shown in Figure 1 (right). When the overlapping option is chosen, the overlapping matrix is integrated in the averaging, with a weight distribution being zero at m = 0 and m = 1, and a maximum in the intermediate magnitudes, as shown in Figure 1 (left). Indeed, we consider such errors as neither belonging to perfect annotation, nor to worst annotation.

Combination

Each previously defined shuffling process involves a particular paradigm. However, in the real world, human annotation errors in a given campaign may involve several paradigms at the same time, sometimes on the same annotated element (e.g. a slight shift and a category mistake). To address this situation, we provide a shuffling process that combines as many shuffling processes as needed, defined as follows: (i) n sub-processes are chosen in a given order; (ii) for a magnitude m, the main process shuffles the reference annotation, successively applying each sub-process (in the given order) with magnitude m/n (hence, this multi-shuffling is not n times faster as classic ones).

Using shuffled corpora to compare measures: a brief overview

To demonstrate the consistency of the method we briefly show in this section how it can be used with two types of annotation paradigms.

Segmentation: Comparison of WindowDiff, and GM

Segmentation consists in determining frontiers between contiguous textual segments. We compare here two metrics already compared by [START_REF] Bestgen | Quels indices pour mesurer l'efficacité en segmentation thématique[END_REF]: WindowDiff (WD) described in [START_REF] Pevzner | A critique and improvement of an evaluation metric for text segmentation[END_REF] and Generalized Hamming Distance (GH) described in [START_REF] Bookstein | Generalized Hamming distance[END_REF], as well as a new versatile measure, the Glozz Measure (GM), described in [START_REF] Mathet | Une approche holiste et unifiée de l'alignement et de la mesure d'accord inter-annotateurs[END_REF], which can be adapted to several paradigms, including segmentation. WD and GH cannot exactly be considered as agreement measures, as they are distances between a reference and a human annotation. These distances equal 0 when annotations are the same, and 1 in the worst case. We have adapted the results as follows: agreement = 1 -distance. Moreover, since these metrics consider two annotators only, we have averaged the one-to-one results when working with 3 or more annotators. Figure 2 shows the behavior of these three measures for three paradigms and their combination: for false negatives WD and GH are quite close, with an almost linear response until magnitude 0.6. Their drawback is that their responses are limited by an asymptote, while GM shows a full range of agreements, but is not linear; again, for false positives, WD and GH are very similar, and their responses, if not asymptotic, show a lower limit at a quite high value (resp. 0.7 and 0.6). GM behaves in the same way as for false negatives, but with an asymptote at agreement = 0.2 much lower than WD and GH; once again, for shifts, WD and GH show an asymptote at about agreement = 0.4, when GM shows values from 1 to 0. Not surprisingly, when using combination, the overall responses look like an average of the other paradigms. This very first and brief comparison reveals that WD and GH are quite close, but GH scores are a little more severe, and with a wider range. For these reasons, according to this experiment, GH seems slightly better. GM is quite different, with almost a full range of agreements, probably because it takes chance into account.

Categorization: Comparison of Kappa, W-Kappa and GM

We focus here on categorization only, assuming a situation where the elements to annotate are pre-located. Four sets of corpora were created, with respect to the two available options described in section 3.3.5. The measures we compare here are Cohen's Kappa [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF], the weighted Kappa [START_REF] Cohen | Weighted kappa: Nominal scale agreement with provision for scaled disagreement or partial credit[END_REF], with two different weight matrices (W-Kappa 1 being much more forgiving than W-Kappa 2); and GM [START_REF] Mathet | Une approche holiste et unifiée de l'alignement et de la mesure d'accord inter-annotateurs[END_REF], with two different options, GM1 which has overlapping capabilities, and GM2 which has not. We also add a very simple percentage agreement value as a baseline (called BM, for Baseline Measure) for all the other measures. The results are shown in Figure 3. First of all, when neither overlapping nor prevalence is involved, all the measures behave almost in the same way (even though BM slightly overrates the agreement as magnitude increases, because it does not take chance into account). When a prevalence phenomenon occurs, all the measures (except BM) still perform equivalently, but BM increasingly overrates the agreement by up to about 0.25. Taking chance into account has more impact here. The overlapping phenomenon clearly opposes W-Kappa and GM to others. Whatever the prevalence option (top-left and top-right figures), the differences are important in the 0.1 to 0.6 magnitude range (where the overlapping matrix has more influence), with a difference of up to 0.15 for GM, and up to about 0.25 for W-Kappa-1. The latter reacts with more strength because we set it with a very forgiving weight matrix, while W-Kappa-2 is set with a less forgiving one, and is very close to GM whose weight matrix is data-driven. Besides, it is interesting to note that when applying these two measures to non-overlapping data (bottom figures), they behave almost exactly the same way as their basic versions not taking overlapping into account.

Limitations and future work

Enhancing annotators' simulation. We shall try in the future to get closer to real annotation constraints. For instance, shifting is currently free, whereas in some campaigns annotating overlapping entities is prohibited. We will also address the question of differences of behavior between annotators.

Using real Gold Standard corpora. It is also possible to use a real Gold Standard corpus as a reference for the system, and then to shuffle it. We started this work with the TCOF-POS-tagged corpus [START_REF] Benzitoun | TCOF-POS : un corpus libre de français parlé annoté en morphosyntaxe[END_REF], for which annotators reached a 0.96 Kappa agreement, which corresponds to a magnitude of 0.1 in the Shuffling Tool, i.e., to a matrix averaged between the perfect one at 95% and the worst one at 5%.

Playing with more parameters. For each experiment this tool makes possible, it will be possible to generate sub-experiments, each of which taking into account a given parameter, including: (i) the number of annotators, (ii) the number of categories, (iii) the number of annotated elements, as already studied with statistical considerations by [START_REF] Gwet | Handbook of Inter-rater Reliability[END_REF].

Relations and more complex structures. Finally, we shall extend the current work, focused on entities as textual segments, to relations and sets of entities, in order to address other annotation types such as co-reference chains and discourse relations.

Conclusion

According to the results on various types of paradigms, and with quite different agreement measures, the proposed method and corpora happen to be consistent: as expected, it is confirmed that the different measures provide decreasing scores from 1 to 0. Some important differences as well as some similarities, appear between the studied methods. This seems promising for further comparisons, in particular for measures with multi error paradigms capabilities, e.g. Krippendorff's α U [START_REF] Krippendorff | On the reliability of unitizing contiguous data[END_REF] and GM. To sum up, this tool will help to (i) objectively compare the behavior of different agreement measures, (ii) obtain a new and enhanced interpretation of their results: a given result of a given method corresponds to a certain magnitude, of which we have a clear and formal definition, (iii) set and enhance existing or future measures (checking improvements and regressions). The shuffling tool used in this work to generate the damaged corpora is written in Java and is freely available1 under the GPL license and all the corpora we generated and used for this paper are also freely available.

Figure 1 :

 1 Figure 1: Weight distributions for averaging with overlapping (left) or without it (right)

Figure 2 :

 2 Figure 2: False negatives (upper left), false positives (upper right), shift (lower left) and combination (lower right)

Figure 3 :

 3 Figure 3: Results of different measures with prevalence (bottom-left), overlapping (top-right), overlapping+prevalence (top-left), and none (bottom-right)

Table 1 :

 1

The four confusion matrices used for interpolation Combining the two options, 4 different experiments can be built: with or without overlapping and with or without prevalence.

This work has been partially financed by OSEO, the French State Agency for Innovation, under the Quaero program.

http://www.glozz.org/shufflingtool


A cold-atom random laser Q. Baudouin, N. Mercadier † , V. Guarrera ‡ , W. Guerin Conventional lasers make use of optical cavities to provide feedback to gain media. Conversely, mirrorless lasers can be built by using disordered structures to induce multiple scattering, which increases the effective path length in the gain medium and thus provides the necessary feedback [START_REF] Letokhov | Light generation by a scattering medium with a negative resonant absorption[END_REF] . These so-called random lasers [START_REF] Markushev | Luminescence and stimulated emission of neodymium in sodium lanthanum molybdate powders[END_REF][START_REF] Lawandy | Laser action in strongly scattering media[END_REF][START_REF] Cao | Random Laser Action in Semiconductor Powder[END_REF][START_REF] Wiersma | A temperature-tunable random laser[END_REF][START_REF] Wiersma | The physics and applications of random lasers[END_REF][START_REF]Special issue on Nano and Random Laser[END_REF] potentially offer a new and simple mean to address applications [START_REF] Wiersma | The physics and applications of random lasers[END_REF] such as lighting [START_REF] Redding | Speckle-free laser imaging using random laser illumination[END_REF] . To date, they are all based on condensedmatter media. Interestingly, light or microwave amplification by stimulated emission occurs also naturally in stellar gases [START_REF] Weaver | Observations of a strong unidentified microwave line and of emission from the OH molecule[END_REF][START_REF] Letokhov | Laser action in stellar atmospheres[END_REF][START_REF] Letokhov | Astrophysical Lasers[END_REF] and planetary atmospheres [START_REF] Johnson | Nonthermal 10 micron CO 2 emission lines in the atmospheres of Mars and Venus[END_REF][START_REF] Mumma | Discovery of natural gain amplification in the 10-micrometer carbon dioxide laser bands on Mars: a natural laser[END_REF] . The possibility of additional scattering-induced feedback (that is, random lasing) has been discussed [START_REF] Letokhov | Astrophysical Lasers[END_REF][START_REF] Lavrinovich | The possibility of the laser effect in stellar atmospheres[END_REF] and could explain unusual properties of some space masers [START_REF] Truitt | Transition to oscillation regime in flaring water vapour masers[END_REF] . Here, we report the experimental observation of random lasing in a controlled, cold atomic vapour, taking advantage of Raman gain. By tuning the gain frequency in the vicinity of a scattering resonance, we observe an enhancement of the light emission of the cloud due to random lasing. The unique possibility to both control the experimental parameters and to model the microscopic response of our system provides an ideal test bench for better understanding natural lasing sources, in particular the role of resonant scattering feedback in astrophysical lasers.

A cloud of cold atoms constitutes a new medium to study random lasing, allowing a detailed microscopic understanding of gain and scattering. Multiple scattering of light in cold atoms has been extensively studied in the past [START_REF] Labeyrie | Slow Diffusion of Light in a Cold Atomic Cloud[END_REF][START_REF] Labeyrie | Multiple scattering of light in a resonant medium[END_REF] . Also, quasi-continuous lasing with cold atoms as gain medium, either placed inside optical cavities [START_REF] Mckeever | Experimental realization of a one-atom laser in the regime of strong coupling[END_REF][START_REF] Guerin | Mechanisms for Lasing with Cold Atoms as the Gain Medium[END_REF][START_REF] Vrijsen | Lasing with a Cold Atom Gain Medium in a High-Finesse Optical Cavity[END_REF][START_REF] Bohnet | A steady-state superradiant laser with less than one intracavity photon[END_REF] or based on distributed feedback [START_REF] Schilke | Optical parametric oscillation with distributed feedback in cold atoms[END_REF] , has recently been demonstrated, illustrating the potential for a variety of gain mechanisms in a regime where optical coherence is limited by purely radiative decay channels. This is significantly different with respect to most random lasing devices, based on pulsed excitation of condensed matter systems, where the relaxation rates of the optical coherence are several orders of magnitude faster than the decay of the excited state population. Long phase coherence times however allow for efficient feedback by resonant scattering, as expected in astrophysical lasers [START_REF] Letokhov | Astrophysical Lasers[END_REF] .

To combine sufficient gain and scattering while using only one atomic species, we take advantage of the multilevel structure of rubidium atoms, shown in Fig. 1a (D 2 line of 85 Rb, wavelength λ = 780 nm). Two-photon Raman gain is obtained by a population inversion between the two hyperfine ground states |2> and |3> sustained by optical pumping. A Raman laser drives the |3> |2'> transition with a large detuning Δ, so that atoms can be transferred into the |2> state by stimulated emission. Scattering required for random lasing is provided by the |2> |1'> line, which is a closed transition efficient for multiple scattering. Both Raman gain and scattering can occur at the same frequency (that is, for the same photons) by an appropriate choice of the Raman detuning Δ = -4.8 Γ, determined by the hyperfine splitting between the |1'> and |2'> states (Γ/2π = 6 MHz is the linewidth of the transition). We thus tune the Raman laser to the vicinity of this condition and define the detuning δ = Δ + 4.8 Γ as the relevant parameter (Fig. 1a). This scheme takes advantage of the selection rules, which forbid electric dipole transitions between the states |3> and |1'>, so that the |1'> level does not affect the Raman gain.

For a given amount of gain and scattering, the threshold of random lasing is determined by a critical minimum size of the sample 1 . In our case, gain and scattering are provided by the same atoms and depend on the atomic density n. We have shown [START_REF] Froufe-Perez | Threshold of a Random Laser with Cold Atoms[END_REF][START_REF] Guerin | Threshold of a random laser based on Raman gain in cold atoms[END_REF][START_REF] Guerin | Towards a random laser with cold atoms[END_REF] that the critical parameter defining the random-laser threshold is the on-resonance optical thickness b 0 , defined for a homogeneous cloud of radius R as b 0 = 2nσ 34' R, with σ 34' the on-resonance scattering crosssection for the |3> |4'> transition (used to measure b 0 , see Methods). Moreover, its critical value can be computed from the atomic polarizability only (see Supplementary Information).

Our sample consists of a cloud of cold 85 Rb atoms collected in a magneto-optical trap. A controlled compression period provides a variable optical thickness b 0 with a constant number of trapped atoms (see Methods). We then switch off all lasers and magnetic field gradients during 1 ms before applying strong counterpropagating Raman beams (intensity I Ra = 4.25 mW/cm 2 per beam with crossed linear polarizations) tuned around δ ~ 0. In addition, we use an opticalpumping laser tuned slightly below the |2> |3'> transition to sustain a steady-state population inversion between the two hyperfine levels involved in our scheme. The relative intensity between the two external lasers allows us to adjust the relative populations, and thus to tune continuously from a sample with large gain and no scattering (with all atoms in the |3> state) to a situation without gain and with large scattering on the |2> |1'> line (with all atoms in the |2> state). The data presented here have been obtained with an optical-pumping intensity I OP = 2.9 mW/cm 2 , corresponding, at δ = 0, to 71% of atoms in the |3> state (evaluated for a single atom).

The signature of random lasing is obtained in our system by the detection of the total emitted light from the sample, which we collect with a solid angle of 10 -2 sr at an angle of 40° with respect to the Raman beam axes (Fig. 1b). Indeed, in contrast to other random-lasing devices, where the scattered pump light is orders of magnitude stronger than the random-laser emission itself, the random-laser line in our system has a strength comparable to the one of the other involved transitions. In addition, the external lasers are not scattered by the |2> |1'> transition. Figure 2 shows the measured fluorescence as the Raman laser frequency is swept through the region of interest, for different values of the optical thickness b 0 of the atomic cloud (see Methods). We stress that for these measurements we vary b 0 while keeping the atom number constant. Variations in the fluorescence can thus only be related to collective features.

The first signature of such a collective behaviour can be seen in a regime of negligible scattering, far from the |2> |1'> transition (regions 1 of Fig. 2): amplified spontaneous emission (ASE) induces an overall increase of the fluorescence as a function of b 0 . Photons from the Raman beam can indeed undergo a spontaneous Raman transition. The subsequent scattered light is then amplified by Raman gain produced by the surrounding atoms while leaving the sample with a ballistic path. The efficiency of this process is directly related to the optical thickness (see Supplementary Information). The ASE signal decreases as the Raman laser is detuned further away from the |3> |2'> transition (located at δ = +4.8 Γ) since both the spontaneous (source contribution) and stimulated (gain contribution) Raman scattering rates decrease for larger detuning. Note that when tuning the Raman laser very close to the |3> |2'> line, single-photon scattering dominates. As detailed in ref. 26, population redistribution is then responsible for the increase of fluorescence. This effect is negligible for the detunings considered here, and only gain can explain the observed features.

When the Raman laser is tuned close to δ = 0 (region 2 of Fig. 2), the combination of gain and scattering gives rise to a random laser. It appears as an enhanced fluorescence bump that emerges as the optical thickness b 0 is increased. To better extract this signal, we fit the wings of the curves (regions 1) by adjustable slope and curvature and remove this ASE background. The remaining random-laser signal is a Gaussian peak, well-centred at δ = 0 (Fig. 3a), which thus comes from the scattering due to the |2> |1'> transition. Therefore, the observed peak is due to the combination of gain and scattering. Moreover, the peak amplitude shows a threshold behaviour, with a change of slope at b 0 = 6±1 (Fig. 3b). This threshold is the signature of the occurrence of random lasing in our sample when the Raman beams are tuned around δ ~ 0 and when b 0 > 6. We stress that varying the optical thickness acts simultaneously on the amount of gain and feedback provided by the medium. This is unusual in laser physics, where the threshold is most-commonly defined as a critical pump power. In our case, increasing the optical-pumping intensity increases indeed the population inversion that provides gain, but simultaneously decreases the feedback, so that random lasing needs a fine tuning of the laser parameters. |1'> line, the mean-free path ℓ sc and the gain length ℓ g , including saturation effects due to the random laser intensity I RL inside the sample. Like in conventional laser theory, we look for a steady-state solution where gain exactly compensates losses. In the diffusive regime and taking into account only the diffuse mode with the longest lifetime, this condition is equivalent to Letokhov's result on the random-lasing threshold 1,23 , ,

where R cr is the critical sample size. As a consequence, for a given b 0 , we find the value of I RL such that Eq. ( 1) is fulfilled. Considering the simplicity of our model and the absence of adjustable parameter, the qualitative agreement between the experimental data and the computed values for the additional fluorescence is very satisfactory (Fig. 3b,c). The quantitative discrepancies suggest the need for more involved models. Many ingredients have indeed been neglected, like interference effects on light transport, light polarization, the Zeeman degeneracy of the involved atomic levels, the finite temperature, the inhomogeneous atomic density distribution, and cooperative effects [START_REF] Bohnet | A steady-state superradiant laser with less than one intracavity photon[END_REF][START_REF] Goetschy | Euclidean matrix theory of random lasing in a cloud of cold atoms[END_REF] . The comparison between the experiment and new models including some of these effects will allow one to identify the most relevant ones and thus to better understand random-laser physics.

In summary, we have presented an experimental evidence of combined gain and scattering of light in a cloud of cold atoms, demonstrating random lasing in a dilute vapour. This type of experiments, based on well-controlled atomic systems, with the possibility of ab initio calculations, will allow the comparison to different models of random lasing [START_REF] Froufe-Perez | Threshold of a Random Laser with Cold Atoms[END_REF][START_REF] Goetschy | Euclidean matrix theory of random lasing in a cloud of cold atoms[END_REF][START_REF] Türeci | Strong interactions in multimode random lasers[END_REF][START_REF] Conti | Dynamic light diffusion, three-dimensional Anderson localization and lasing in inverted opals[END_REF] and help understanding complex situations encountered in astrophysical systems. Testing light propagation models with realistic atomic structures and designing novel detection schemes, based for instance on high-order photon correlations [START_REF] Dravins | Photonic Astronomy and Quantum Optics[END_REF] , are promising examples of such an approach.

Methods

Sample preparation. In our experiment 6 counter-propagating trapping beams with a waist of 3.4 cm (1/e 2 radius of the intensity distribution) are used to load 85 Rb atoms from a background vapour into a magneto-optical trap (MOT). The trapping beams are detuned by -3Γ from the |3> |4'> hyperfine transition. To maintain the atomic populations in |3>, we add 6 repumper beams tuned slightly below the |2> |3'> transition. We can load between 10 8 and 10 11 atoms by changing the background vapour pressure and the duration of the trap loading (from 10 to 500 ms). Once the atoms are trapped in the MOT, we perform a temporal dark-MOT stage by increasing the detuning of the trapping beams to -6 Γ and by reducing the intensity of the repumper beams to few percents of their initial value. This leads to an increase of the spatial density and thus of the optical thickness b 0 of the cloud, without loss of atoms. By changing the duration of this compression stage, we are able to tune b 0 from 1.9 to 27, while keeping almost constant the total number of atoms, which, for the measurements presented here, is set to 7×10 8 ± 12%. The temperature is T ~ 50 µK. The optical thickness b 0 is measured by a transmission spectrum with a small and weak probe beam on the |3> |4'> transition [START_REF] Guerin | Threshold of a random laser based on Raman gain in cold atoms[END_REF] . The shot-to-shot fluctuations of b 0 (horizontal error bars in Fig. 3b) are evaluated by repeating the measurement five times.

Data acquisition.

After the sample preparation, we switch off magnetic field gradients and trapping lasers and we expose the sample to two counterpropagating Raman beams with waists of 2.4 cm and intensities of 4.25 mW/cm 2 each and 6 optical pumping beams with waists of 3.4 cm and intensities of 0.48 mW/cm 2 each at a detuning of -2Γ from the |2> |3'> transition. Note that the diameters of these lasers are large enough to insure that their effective intensities on the atom cloud are independent from the chosen optical thickness. The Raman laser is obtained from a distributed-Bragg-reflector laser diode and is frequency-tuned by a double-pass acousto-optic modulator before it is amplified by two stages of saturated slave lasers. This system allows us to scan the frequency in a range up to 16Γ with intensity variations of only 0.1%. The measuring procedure consists in scanning in 2 ms the Raman beam detuning δ from -3,2Γ to 4,8Γ while a high gain photodiode gathers the fluorescent emission of the cloud in a solid angle of ~ 10 -2 sr. We checked that the direction of the sweep does not change the detected fluorescence, and that the duration of the sweep is short enough to avoid significant variations of b 0 during the measurements (< 5%) and long enough to probe a quasi-steady state (the sweep rate is 4Γ/ms). We averaged over 4000 subsequent measurements in order to increase the signal-to-noise ratio, thus performing also an averaging over the disorder configurations. [START_REF] Letokhov | Light generation by a scattering medium with a negative resonant absorption[END_REF][START_REF] Froufe-Perez | Threshold of a Random Laser with Cold Atoms[END_REF] . Due to saturation effects, this threshold depends on the random-laser intensity. Therefore, for each b 0 , we find the randomlaser intensity such that the computed threshold equals b 0 , corresponding to a steady state (see Supplementary Information).

Received 14 December 2012

Finally, we

  have exploited the possibility to perform ab initio theory by developing two simple models, one for ASE and the other for random lasing. Both are detailed in the Supplementary Information. Here, we describe briefly the random-lasing model. It consists in self-consistently coupling the atomic response, based on optical Bloch equations (OBE) with additional scattering on the |2> |1'> line, to a diffusion equation for the light scattered on the |2> |1'> resonance. The OBE allows us to compute the atomic polarizability and, including the additional scattering on the |2>

Figure 1 |

 1 Figure 1 | Working principle of the random laser. a, Atomic transitions of the D 2 line of 85 Rb used to create random lasing in cold atoms. The two hyperfine ground states are |2> = |F=2> and |3'> = |F'=3>. Similarly, the involved hyperfine excited states are the states |F'=1,2,3> denoted |1'>, |2'>, and |3'>. Optical pumping creates a population inversion between |2> and |3>. This allows us to create Raman gain by applying a laser with a detuning Δ from the |3> |2'> transition. The gain frequency has a detuning δ from the closed |2> |1'> transition. Around δ ~ 0, this transition provides efficient scattering. Random lasing can thus occur around this frequency. b, Schematic representation of the experiment. The magneto-optical trap (yellow sphere) is exposed to two Ramanlaser beams (green) and six optical-pumping beams (red). Its fluorescence is collected by a lens and detected by a photodiode. Zoom-in: light (in blue) is scattered by atoms in the |2> state (black) and amplified by atoms in the |3> state (yellow background).

Figure 2 |

 2 Figure 2 | Fluorescence measurement. Total fluorescence P F as a function of the Raman laser detuning δ (in units of the linewidth Γ of the optical transition) recorded for optical thickness varying from b 0 = 1.9 to b 0 = 26. The number of atoms is kept constant at N = 7×10 8 ± 12 %. Two collective features are visible. In the wings (regions 1), the overall increase of the fluorescence with b 0 is due to amplified stimulated emission. Around δ ~ 0 (region 2), an additional peak appears for large optical thickness. This enhanced light emission is due to the combination of Raman gain and multiple scattering provided by the |2> |1'> transition and is thus a signature of random lasing.

Figure 3 |

 3 Figure 3 | Random laser emission around δ = 0. a, Supplementary fluorescence δP F due to random lasing as a function of the Raman laser detuning δ, measured for optical thickness varying from b 0 = 1.9 to b 0 = 26. The source data are the same as in Fig. 2, but the wings (regions 1 in Fig. 2) have been subtracted. The inset illustrates the fitting procedure. For clarity we also smoothed the data, corresponding to a detuning resolution of 0.3 Γ. b, Amplitude of the additional peak due to random lasing. A threshold optical thickness is clearly visible at b 0 ~6. Vertical error bars correspond to the rms noise on the data of Fig. 2 and horizontal error bars to shot-to-shot fluctuations of b 0 . c, Computed fluorescence P F as a function of the detuning δ with three different optical thicknesses (b 0 = 0 corresponds to the single-atom limit), using our self-consistent model for random lasing. It shows that an increase of the total fluorescence is expected around δ = 0 when random lasing occurs. d, Solution at δ = 0 of the self-consistent model for random lasing. Only the supplementary fluorescence δP F is plotted, to allow for a comparison with the experimental data (panel b). Inset: principle of the model. The atomic response allows the computation of the threshold optical thickness following Letokhov's criterion[START_REF] Letokhov | Light generation by a scattering medium with a negative resonant absorption[END_REF][START_REF] Froufe-Perez | Threshold of a Random Laser with Cold Atoms[END_REF] . Due to saturation effects, this threshold depends on the random-laser intensity. Therefore, for each b 0 , we find the randomlaser intensity such that the computed threshold equals b 0 , corresponding to a steady state (see Supplementary Information).

  and R. Kaiser* Institut Non Linéaire de Nice, CNRS, Université de Nice Sophia-Antipolis, 1361 route des Lucioles, 06560 Valbonne, France † Present address: Saint-Gobain Recherche, 39 quai Lucien Lefranc, 93303 Aubervilliers, France ‡ Present address: Research Center OPTIMAS, Technische Universität Kaiserslautern, 67663 Kaiserslautern, Germany *e-mail: robin.kaiser@inln.cnrs.fr

Acknowledgments

We acknowledge financial support from ANR (project ANR-06-BLAN-0096), CG06, PACA, DGA and the Research Executive Agency (program COSCALI, No. PIRSES-GA-2010-268717). We thank R. Carminati and S. Skipetrov for fruitful discussions, and A. Aspect and S. Tanzilli for useful comments on the manuscript.

Author contributions Q.B., N.M. and V.G. made the experiment and analysed the data; Q.B., N.M. and R.K. developed the theory; Q.B., W.G. and R.K. wrote the paper; R.K. supervised the project. Q.B. and N.M. contributed equally to the study. All authors discussed the results and commented on the manuscript.