Juliette Thuilier
email: jthuilier@linguist.jussieu.fr

Laurence Danlos
email: laurence.danlos@linguist.jussieu.fr

Semantic annotation of French corpora: animacy and verb semantic classes

Keywords: manual annotation, animacy, verb semantics

. For the higher level (generic classes), the measures of agreement are Multi-π = 0.84 and Multi-κ = 0.87 (k = 3, N = 1346). The inter-annotator agreements show that the annotated data are reliable for both animacy and verbal semantic classes.

Introduction

In this paper, we present a first corpus of French annotated for animacy and for verb semantic classes. The resource consists of 394 sentences from the French Treebank (FTB, (Abeillé and Barrier, 2004)), 622 sentences from the corpus Est-Républicain corpus (ER)1 and 330 from the ES-TER corpus 2 . This resource was manually annotated and manually corrected.

The corpus and the annotation

The constitution of the corpus ties in with the research question we are interested in, namely the order of post-verbal complements in French. That order is relatively free as shown in example (1) and (2). Aside from the relative length of the constituents, we aim to find which constraints affect the choice between NP-PP or PP-NP order.

(1) il montrait [aux copains]PP [son butin]NP.

(2) il montrait [son butin]NP [aux copains]PP.

(from Est-Républicain Corpus) "he showed his loot to his friends"

Studies dealing with constituent order in English have demonstrated that animacy and verb semantics play a role in dative alternation [START_REF] Th | Towards a corpus-based identification of prototypical instances of con-structions[END_REF]Bresnan et al., 2007, among others) and that animacy also affects genitive alternation [START_REF] Rosenbach | Animacy versus weight as determinants of grammatical variation in english[END_REF].

In order to study the effect of these two constraints in French, we created a database of 1,346 sentences extracted from three corpora (FTB, ESTER, ER) that contains a ditransitive verb followed by only two complements subcategorized by the verb.

First, the sentences were automatically extracted from FTB using the already annotated syntactic structure and grammatical functions. Second, the sentences from ER and ES-TER were manually selected according to the verbal head. Therefore, they were automatically parsed and the treebanks were manually corrected. This database was annotated for the animacy of both complements' referents, following the categories of [START_REF] Zaenen | Animacy encoding in english: why and how[END_REF] adapted to French. The semantics of the ditransitive verbs was annotated using an existing resource: "Les Verbes du Franc ¸ais" (LVF, [START_REF] Dubois | Les verbes franc ¸ais[END_REF]). The Salto Annotation Tool [START_REF] Burchardt | SALTO -A Versatile Multi-Level Annotation Tool[END_REF] was used for the annotation process because it is an easy to use tool for graphical annotation of treebanks. Thus, the database is a set of parsed sentences with annotations on the verb and on both complements, in the TIGER XML format [START_REF] Mengel | An xmlbased representation format for syntactically annotated corpora[END_REF]. Figure 1 shows an example of an annotated sentence visualized with the Salto tool.

Animacy

Animacy is an inherent semantic property of referents. Animacy is often conceived as a hierarchical property going from human to inanimate. In this work, the hierarchy that we used is presented in [START_REF] Garretson | Coding practices used in the project optimal typology of determiner phrases[END_REF] Even though much of the work based on animacy coded data uses simpler distinctions (e.g. animate vs. inanimate), such an elaborate hierarchy is useful for the anno- tation task. For instance, the distinction between organization and non-concrete inanimate referent is often difficult and uncertain. However, organization is categorized as animate, whereas non-concrete falls into the inanimate class. Thus, the discrimination between organization and non-concrete appears to be essential. We believe that using fine-grained categories with detailed definitions gives the annotator more elements to classify the difficult cases, and consequently, provides better annotation quality. Three annotators carried out the annotation task: one of them was the author; the other two were undergraduate students in computational linguistics at Université Paris 7.

They annotated the referent of both complements in the 1,346 sentences of the database using annotation guidelines (in French). Note that 332 complements are propositions introduced by a complementizer, so they are not relevant from the animacy point of view. The database for animacy is then composed of 2 360 referents (2 x 1014 + First, the annotators worked independently. Then, during the adjudication process, they discussed the annotations on which they disagreed in order to reach consensus. So, the result of the annotation consists of three annotated corpora and one adjudicated corpus. Following the terminology of [START_REF] Artstein | Inter-coder agreement for computational linguistics[END_REF], we report agreement in terms of Fleiss Multi-π (also known as Carletta's kappa [START_REF] Carletta | Assessing agreement on classification tasks: the kappa statistic[END_REF]) and Multi-κ (generalization of Cohen's [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF]), in order to estimate the reliability of the annotation with three annotators: Multiπ = 0.82 and Multi-κ = 0.86 (k = 3, N = 2360). The two measures indicate a good inter-annotator agreement, given that values higher than 0.8 are considered as reliable. In order to give an idea of the distribution of the categories, Table 2 contains the frequency with which each category is classified in the same way by the three annotators (the diagonal of the table) and the frequency of disagreement (other boxes). More precisely, considering the coders one pair at a time, Table 2 is a confusion matrix that displays the frequency with which one coder of the pair chose the category named in the row header while the other chose the category named in the column header for the same referent. We observe that the categories non-concrete, organization and human are the ones with most disagreement. These disagreements are similar to those observed by Zaenen et al.

( 2004) and can be understood as reflecting differences of interpretation of the constituent in the context. In the following subsections, we present two typical cases that annotators disagreed on.

Organization vs. Non-concrete

As mentioned earlier, the distinction between organization and non-concrete is essential, because non-concrete referents are categorized as inanimate while organizations are considered as animate.

( In sentence (3) and ( 4), two annotators chose the tag organization for the PPs, considering that "groupe familial" and "groupe franc ¸ais" refer to a group of humans, whereas the other coder used the tag non-concrete considering that they refer to an abstract entity 'company'. In the adjudicated version of the corpus, we went for organization in sentence (3), since the beneficiary of the transaction seems to be the persons heading the company. As for sentence (4), we chose the non-concrete tag because we considered the referent to be the abstract business entity more than the organized group of persons.

Human vs. Organization

We observe disagreements between organization and human, because, in some contexts, it is difficult to say if the referent is more a human or a group of humans.

( In sentence (5), the PP can be interpreted as referring either to communities owing communal lands in Mexico or to the community members which actually feed the chicks. Two annotators used the organization tag and the other one the human tag. We chose organization for the adjudicated corpus, considering that the PP refers more to the community than to the members.

Verb semantic classes

The "Les Verbes du Franc ¸ais" dictionary (Dubois and Dubois-Charlier, 1997) is a hand-written resource containing 25,610 verbal entries, representing 12,310 verbs classified according to their syntactico-semantic properties. This dictionary is a very detailed resource, with a large coverage. The classification is based on the analysis of the types of subjects, complements and adjuncts (animate, inanimate, abstract, singular/plural, collective...), the realizations of the arguments (NP, PP, clause...), as well as the syntactic alternations allowed by the verb. We used three of the five levels of classification for the annotation:

• 14 generic classes represented by an uppercase letter;

• 54 semantico-syntactic classes labeled with a digit;

• 248 syntactic sub-classes labeled with a lowercase letter.

The 14 generic classes indicate the general meaning of the verb. They are:

• C: communication The verb is annotated D2a, which means that it has:

• the generic class D (standing for 'donation/deprivation');

• the semantico-syntactic class D2 (standing for 'to give something to somebody/to get something from somebody');

• the syntactic sub-class D2a (standing for 'to supply somebody with something').

The same three coders realized this annotation task using the online version of the dictionary3 as annotation guidelines. They annotated the 1,346 verbs of the database and enriched the annotation guidelines, listing and explaining the main difficulties and annotation choices. Like the animacy corpus, the adjudicated corpus is the result of a consensus between the three annotators for the cases they disagreed on.

The main difficulty lies in the fact that the hand-written resource has not been conceived for an annotation task. Thus, uses of verbs found in corpora do not systematically correspond to lexical entries. For example, the database contains occurrences of the verb mettre 'to put' employed with predicative PPs, as in mettre en valeur 'to emphasize'. However, the LVF has no entry corresponding to this kind of meaning. Moreover, the LVF differentiates between very close meanings of a verb, and it is sometimes difficult to identify these differences in contextualized examples.

Considering the syntactic sub-classes, Multi-π = 0.76 and Multi-κ = 0.78 (k = 3, N = 1346). Given the number of categories ( 248) and the nature of the resource used for the annotation, the agreement between the 3 annotators seems reasonable. The confusion matrix (Table 3) was conceived in the same way as the one concerning animacy. It only contains the generic classes. The corresponding Multi-π and Multi-κ are respectively 0.84 and 0.87.

First observations and results

These annotated data have been used in linguistics-oriented studies, dealing with the problem of verbal complement order.

First, animacy seems to not be relevant in French. In the sub-corpus composed of the sentences containing two phrasal complements, 10.2% of the NP and 37.0% of the PP are animate (= human, organization, animal). As shown in [START_REF] Thuilier | Do animate arguments come first?[END_REF], when the relative length of both complements, the verbal lemma, and the collocation effect between the verb and the PP are controlled, animacy does not show a significant effect on the relative order of postverbal complements in our data. This result seems to be confirmed by an experiment based on a questionnaire where the length effect was neutralized [START_REF] Thuilier | Do animate arguments come first?[END_REF]. Second, we observe that the verbs associated with their semantic classes have different behavior according to verbal complements order. Thuilier (Forthcoming) points out that we can have a better modeling of the order of verbal complements when taking into account the disambiguated verb.

The measures of agreement indicate that the corpus presented here is a reliable semantically annotated resource for animacy and general semantic classes of verbs. It is a relevant data set from a linguistic point of view, as shown in the last section. Additionally, it can be used as a training set for automatic classification of semantic layers on treebanks.

Figure 1 :

 1 Figure 1: Example of annotated sentence visualized with Salto tool.

•

  D: donation/deprivation • E: entrance/exit • F: to hit/to touch • H: physical condition/behavior • L: locative • M: movement in place • N: to provide/to remove • P: psychological verbs • R: achievement/setting up • S: to grab/to grip/to own • T: transformation/change • U: to combine/to bring together • X: auxiliary verbsThe semantico-syntactic classes are generally arranged according the type of subject and the use of the verb (literal or figurative sense), except for C, D, P and X generic classes. This means that we need the generic class in order to interpret the semantico-syntactic level.

Table 1

 1

	and inspired by Garretson

Table 1 :

 1 Hierarchy of animacy

Table 3 :

 3 Confusion matrix for generic classes of verbs (Overb stands for 'I don't know')

	• X (auxiliaries)
	-1 : temporal or aspectual auxiliaries

Freely available at http://www.cnrtl.fr/corpus/ estrepublicain/.We used the lemmatized version of this corpus, which will be presented at LREC

[START_REF] Seddah | Ubiquitous usage of a french large corpus: Processing the est republicain corpus[END_REF] and which is freely available at http://alpage.inria.fr/estrepu/ .2 Distributed by ELRA.

http://rali.iro.umontreal.ca/Dubois/

Acknowledgements

Alpage (INRIA Paris-Rocquencourt & Université Paris 7) supported this work by paying two coders for the annotation task. Thank you to these annotators, Kévin Deturck and Fabien Andreani, for their work.


Introduction

The main objective of Workpackage 5 was to organize an international competition of solvers of package upgradeability problems. These problems are expressed in the CUDF format developed by the Mancoosi project [START_REF] Treinen | Description of the CUDF format[END_REF][START_REF] Treinen | Common upgradeability description format (CUDF) 2.0[END_REF]. A problem instance expressed in CUDF contains the metadata of currently installed, as well as of available packages, and a request to install new packages, remove currently installed packages, or upgrade packages to newer versions. The metadata of a package is comprised, among others, of name and version of packages, dependency, conflicts and provided virtual packages.

Problems of this kind are theoretically NP-complete [DCMB + 06]. However, if a problem instance is satisfiable then it typically has a huge number of solutions. One of the goals of the Mancoosi project was to design a language of optimization criteria that would allow a user to specify what would constitute the best among all the solutions. Hence, we consider the package upgradeability problem as a combinatorial optimization problem. The goal of organizing an international competition of solvers for such problems was to make the research community aware of this problem, and to promote this particular instance of combinatorial optimization in the different research communities. The competition was designed to be open to any interested participant, including but not limited to, the solvers developed in Workpackage 4 of the project.

Chapter 2

Before MISC 2010

Organizing a solver competition is a complex task. Besides organizational issues, the technical setup of the competition proved to be challenging for the Mancoosi team. For this reason we decided to prepare the official international MISC competition by some trial runs (MISC-live 1 and MISC-live 2) with the goal of detecting early the problems in the setup, and thus avoiding them in the first official competition. The first trial run, called at that time Mancoosi internal Solver Competition (MiSC), was run in January 2010 followed by a second trial run before the official MISC competition in June 2010. Because of the positive feedback we got from the community after the first trial run, and because of the benefit to allow solver developers to continually test their solvers in a formal setting, we decided after MiSC to repeat such trial runs at irregular intervals in the future, and we baptized these trial runs MISC-live.

The purpose of running an internal competition was two-fold. On one hand it allowed the organizers of the competition to test their setup in a realistic setting. Since the MISC competition was the first of its kind the organizers had to experiment with the definition of the rules of the competition and the technical setup. Experience from the SAT community1 proved very helpful in this regard. However, because of the inherent differences between the two competitions, we were unable to reuse their infrastructure and we were forced to build the execution and ranking environment from scratch.

On the other hand, these trial runs were most helpful to the prospective participants of the official competition. Because of the technical complexity of the CUDF format and its semantic, we felt that it was necessary to provide a strong support to test and run prospective solvers in a realistic test environment which is as close as possible to the one used in the official competition. This internal competition was open to all interested participants, both internal to the Mancoosi project and external to the project. Participants of this internal competition were :

• apt-pbo: a modified apt tool using pseudo-Boolean-optimization (minisat+ or wbo), submitted by Mancoosi partner Caixa Mágica.

• p2cudf: a solver built on top of the Eclipse Provisioning Platform p2, based on the SAT4J library and submitted by a team from Université d'Artois and IBM which is not part of the Mancoosi project.

• inesc-udl: a SAT-based solver using the p2cudf parser (from Eclipse) and the MaxSAT solver MSUnCore, submitted by Mancoosi partner Inesc-ID.

• unsa: a solver built using ILOG's CPLEX, submitted by Mancoosi partner Université Nice/Sophia-Antipolis.

The trial runs proved indeed very useful both for the participants and for the organizers. For instance, some of the participants found at MISC Live 1 that their solvers failed for some unexpected but trivial reason, like some mistake in the implementation of the parser for the input language. The most important lesson for the organizers of MISC Live 1 was that the initial system of limiting the resources of solver processes, based on the ulimit utility, was not sufficient since it did not allow to notify the solvers when they were about to overstep their time limit. As a consequence of this experience, the resource limitation was reimplemented from scratch, using the runsolver utility due to Olivier Roussel from Sat Live.

Chapter 3

MISC 2010

The first official international competition, the Mancoosi International Solver Competition (MISC), was run in the summer of 2010. The competition was announced on various mailing lists and electronic newsletters. The timeline was as follows:

• April 22, 2010: official announcement of the competition.

• May 31, 2010: participants have to declare by email their intention to participate.

• June 13, 2010: deadline for the submission of solvers.

• July 10, 2010: announcement of the results.

The results of the competition were announced at the First International Workshop on Logics for Component Configuration (LoCoCo 2010). LoCoCo 2010 took place during SAT 2010, the Thirteenth International Conference on Theory and Applications of Satisfiability Testing. Both LoCoCo 2010 and SAT 2010 were part of the Federated Logic Conference 2010, which was the major international event for computational logics in 2010 consisting of 8 main conferences and about 50 workshops. The FLoC conference is held every three to four years as a federation of most of the major international conferences on computational logics.

The Rules of MISC 2010

All problems used in the competition are expressed in the CUDF format developed by the Mancoosi project [START_REF] Treinen | Description of the CUDF format[END_REF][START_REF] Treinen | Common upgradeability description format (CUDF) 2.0[END_REF]. A CUDF document contains a complete abstraction of a software installation on a user machine plus the user request. It contains the metadata of currently installed, as well as of available packages, and a request to install new packages, remove currently installed packages, or upgrade packages to newer version. The metadata of a package is comprised, among others, of name and version of packages, dependency, conflicts and provided virtual packages. An overview of the CUDF format is given below in Subsection 3.1.1.

Since, if a solution exists, there exist in general many of them, one also needs a criterion to distinguish an optimal solution (which is not necessarily unique). We hence proposed a system to define precisely different complex optimization criteria. The exact definition of this system is given below in Subsection 3.1.2. For MISC 2010 we had two different tracks, each of them defined by a different optimization criterion

Problem Format

CUDF (for Common Upgradeability Description Format) is a specialized language used to describe upgrade problem instances, that is presented in detail in [START_REF] Treinen | Description of the CUDF format[END_REF]. Here we just recall that it has been designed with the following goals in mind:

Platform independence We want a common format to describe upgrade scenarios coming from diverse environments. As a consequence, CUDF makes no assumptions on a specific component model, version schema, dependency formalism, or package manager.

Solver independence

In contrast to encodings of inter-component relations which are targeted at specific solver techniques, CUDF stays close to the original problem, in order to preserve its structure and avoid bias towards specific solvers.

Readability CUDF is a compact plain text format which makes it easy for humans to read upgrade scenarios, and facilitates interoperability with package managers.

Extensibility Only core component properties that are shared by mainstream platforms and essential to the meaning of upgrade scenarios are predefined in CUDF. Other auxiliary properties can be declared and used in CUDF documents, to allow the preservation of relevant information that can then be used in optimization criteria, e.g. component size, number of bugs, etc.

Formal semantics CUDF comes with a rigorous semantics that allows package managers and solver developers to agree on the meaning of upgrade scenarios. For example, the fact that self-conflicts are ignored is not a tacit convention implemented by some obscure line of code, but a property of the formal semantics.

Figure 3.1 shows an excerpt of a CUDF document in a sample upgrade scenario. A CUDF document consists in general of three parts:

• A preamble, which in particular may declare additional package properties, together with their type, that may be used in the package metadata. In the example of Figure 3.1 we have declared an additional package property called bugs of type int, this property is optional and the default value is 0.

• A list of package stanzas, each of them started on the keyword package. This list gives the metadata of all the packages that are currently installed on the system, or available for future installation.

• A request stanza that defines the problems to be solved. In the example, we require of a solution that it must contain (have installed) some package called bicycle, and also some package called gasoline-engine in version 1.

A package stanza is a record consisting of some standard fields, plus additional fields if declared in the preamble. The most important package fields are package name and version (which together serve to uniquely identify a package), dependencies and conflicts. The dependency field of a package p specifies other packages that must be installed together with the given package p, and the conflicts field is exclusion list of packages that must not be installed together with p. Dependencies are conjunctions of disjunctions, the elements of which are package names, probably together with a version constraint.

Optimization Criteria

Two different fixed optimization criteria were used for MISC 2010, each of them defining one track in the competition. Both criteria are lexicographic combinations of different integer-valued utility functions to be evaluated w.r.t. a given solution.

Each of these utility functions calculates a value only from the initial installation status and a given solution. These utility function have therefore a global scope. As a consequence, the user request is not included the optimization criterion itself. The reason for this is that each proposed solution must first of all satisfy the user request, and only if this is the case is compared with other solutions w.r.t. the given optimization criteria. Solutions that do not satisfy the user request will be discarded and the solver will obtain a penalty value. Only those of the proposed solutions that actually satisfy the user request will yield a score according to the ranking function described below in Subsection 3.1.3.

Two tracks were proposed for MISC: the paranoid and the trendy track. The motivation behind choosing these two criteria was to model the intentions of two different categories of users: the sysadm -paranoid track -which privileges solutions that change the least number of packages, and the gamer -trendy track -which prefers the latest version of software installed on the system, and who does not strongly oppose to installing additional packages on the system.

May 24, 2011

We have choosen two fixed criteria for the competition, in contrast to a domain-specific language allowing for the free definition of functions like MooML [START_REF] Treinen | Expressing advanced user preferences in component installation[END_REF], in order to not overburden participants of the competition with a too complex input language. For the next edition of MISC, however, we have generalized the choice of optimization criteria (see Section 4).

The first criterion ("paranoid") uses only standard package properties as defined in the CUDF standard. For the second criterion ("trendy") we made use of an extra package property which is not among the mandatory package properties. This additional property is recommends, that is expressed as a conjunctions of disjunctions of package, possibly with version constraints (as the property depends).

The idea is that recommended packages are non-mandatory dependencies. For that reason, the CUDF documents used as problem instances in the competition contain a specification of that property in the document preamble, like this:

preamble: property: recommends: vpkgformula = [ true! ]
The precise definition of the different utility functions used in the formal definitions of the criteria are defined as follows. Suppose that a solver tool outputs for the initial universe I (the set of initially installed packages) a proposed solution S. We write V (X, name) for the set of versions in which name (the name of a package) is installed in X, where X may be I or S. That set may be empty (if name is not installed), contain one element (if name is installed in exactly that version), or even contain multiple elements in case a package is installed in multiple versions.

We write The two optimization criteria are now defined as follows:

• #removed(I, S)
• paranoid : we want to answer the user request, minimizing the number of packages removed in the solution, and also the packages changed by the solution. Formally:

lex(min#removed, min#changed)
Hence, two solutions S 1 and S 2 will be compared as follows:

1. compute, for i ∈ {1, 2}:

r i = #removed(I, S i ) c i = #changed(I, S i )
2. S 1 is better than S 2 iff r 1 < r 2 or (r 1 = r 2 and c 1 < c 2 ).

• trendy: we want to answer the user request, minimizing the number of packages removed in the solution, minimizing the number of outdated packages in the solution, minimizing the number of unsatisfied recommendations, and minimizing the number of extra packages installed. Formally:

lex(min#removed, min#notuptodate, min#unsatisf ied -recommends, min#new)
Hence, two solutions S 1 and S 2 will be compared as follows:

1. compute, for i ∈ {1, 2}:

r i = #removed(I, S i ) u i = #notuptodate(I, S i ) ur i = #unsatisf ied -recommends(I, S i ) n i = #new(U, S i )
2. S 1 is better than S 2 iff r 1 < r 2 or (r 1 = r 2 and (u 1 < u 2 or (u 1 = u 2 and (ur 1 < ur 2 or (ur 1 = ur 2 and n 1 < n 2 ))))).

May 24, 2011

Ranking of Solutions

All participating solvers were executed on the same set of input problems. The ranking routine operates in three steps. First, all individual problems are ranked based on the solvers' output. Second, all individual solutions are numerically ranked, aggregating problems by track and problem set. In the end, the aggregate solutions for each track are aggregated together to determine the winner.

We first define how several participating solvers are ranked on one particular problem instance.

Let m be the number of participating solvers. For each input problem we give points to each solver, according to whether the participant yields 1. a claimed solution that really is a solution 2. FAIL (that is, the solver declares that he has not found a solution)

3. ABORT (timeout, segmentation fault, . . .)

4. a claimed solution that in reality is not a solution to the problem Note: After MIC 2010 we found that the difference between FAIL and ABORT is somewhat artificial. A smart solver might want to respond FAIL whenever it was able to detect a crash or a timeout. Despite the fact that this might prove the solver unsound, it will be ranked better then a solver that decided not to declare ABORT as FAIL. For this reason, in further editions of MISC (see Section 5), the cases FAIL and ABORT will be ranked the same.

The number of points a solver gets on a given input problem is calculated as follows:

1. All solvers in case (1) are ordered according to the optimization criterion (best solution first), and a participant in case (1) gets the number of points that corresponds to his position in that list. In case two solvers have found equally good solutions they get the same number of points. In other words, the number of points obtained be a solver is 1 plus the number of solvers that are strictly better.

To give an example with 4 participating solvers s 1 , s 2 , s 3 and s 4 : If s 1 gives the best solution, followed by s 2 and s 3 giving an equally good solution, and s 4 who gives the worst solution, then s 1 gets 1 point, s 2 and s 3 each get 2 points, and s 4 get 4 points.

2. A participant in case (2) gets 2 * m points.

3. A participant in case (3) gets 3 * m points.

A participant in case (4) gets 4 * m points

Note that it is possible that an input problem indeed doesn't have a solution. In that case, (1) above is not possible, so the solvers that correctly say FAIL are ranked best.

The total score of a solver is the sum of the number of points obtained for all problems of the problem set. The solver with the minimal score wins.

If several solvers obtain the best total score then the winner is determined by choosing among those having obtained the best total score the one with the minimal total success time. The total success time of a solver is the sum of execution times of that solvers over all problems in May 24, 2011 case 1 (correct solution), plus f * timeout where f is the number of problems where the result of that solver is in one of the cases 2 (FAIL) or 3 (abort, timeout,...) or 4 (wrong solution), and timeout is the time limit defined in the execution environment.

The Execution Environment of MISC 2010

The solver is executed on a virtual machine that simulates a GNU/Linux host of architecture x86, 32 bit, single-processor. On the virtual machine are installed:

• A standard POSIX environment. In particular a POSIX-compatible shell, which may be invoked by /bin/sh, is available, as well as a GNU Bourne-Again SHell (invoked as /bin/bash).

• A Java Runtime Environment (JRE) 6; the Java application launcher can be invoked as /usr/bin/java.

• A Python 2.5 environment; the main Python interpreter can be invoked as /usr/bin/python.

No other libraries, for any programming language, can a priori be assumed to be available in the virtual machine environment. This means:

• Solvers prepared using compilers supporting compilation to ELF must be submitted as statically linked ELF binaries. No assumptions can be made on available shared libraries (.so) in the virtual machine environment.

• Solvers written in some (supported) interpreted language must use the usual shebang lines (#!/path/to/interpreter) to invoke their interpreter.

• Solvers written in Java must be wrapped by shell scripts invoking the Java application launcher as needed.

• Solvers needing other kind of support in the virtual machine must make specific arrangements with the competition organizers before the final submission.

The solver execution is additionally constrained by the following limits (as implemented by ulimit):

• Maximum execution time: 5 minutes

• Maximum memory (RAM): 1 GB • Maximum file system space: 1 GB (including the solver itself)

The execution time is CPU time, measured in the same way as ulimit -t. About 20 seconds before the timeout, the signal SIGUSR1 will be sent to the solver process. It is the responsibility of the solver to catch that signal, produce an output, and terminate normally. The resource limitation and the notification of the solvers is implemented in the execution environment by using the runsolver utility due to Olivier Roussel from Sat Live.

May 24, 2011

Requirements on Participating Solvers

The following instructions on how solvers are to be invoked were given to the participants:

• The solver will be executed from within the solver directory.

• Each problem of the competition will be run in a fresh copy of the solver directory.

• The solver will be called with 2 command line arguments: cudfin and cudfout, in this order. Both arguments are absolute file systems paths.

1. cudfin points to a complete CUDF 2.0 document, describing an upgrade scenario.

The CUDF document is encoded as ASCII plain text, not compressed. According to the specifications, the document consists of an optional preamble stanza, followed by several package stanzas, and is terminated by a request stanza.

2. cudfout points to a non-existing file that should be created by the solver to store its result.

Solvers were expected to yield their solution as follows:

• The solver's standard output may be used to emit informative messages about what the solver is doing.

• If the solver is able to find a solution, then it must:

write to cudfout the solution encoded in CUDF syntax as described in Appendix B of the CUDF 2.0 specification;

exit with an exit code of 0.

• If the solver is unable to find a solution, then it must:

write to cudfout the string "FAIL" (without quotes), possibly followed by an explanation in subsequent lines (lines are separated by newline characters, ASCII 0x0A);

exit with an exit code of 0.

• All exit codes other than 0 will be considered as indications of unexpected and exceptional failures not related to the inability to find a solution.

Selection of Input roblems

The corpus of input problems selected for the MISC competition consists of two kinds of problems:

• problems originating from real world scenarios that users have encountered, or might encounter, during the normal evolution of a software distribution,

• purely artificial problems, with the goal to foster the advancement of combinatorial solving techniques at hand of challenging problems.

In the first class of problems originating from real-world scenarios, the organizers selected a number of CUDF documents distilled from the community-submitted DUDF upgrade problem reports [AGL + 10] that were submitted to the central repository at UPD [START_REF] Abate | UPDB infrastructure to collect traces of ugradeability problems in CUDF format[END_REF], namely from the Debian, Mandriva and Caixa Mágica communities.

Other then these submitted problems, we generated a number of artificial problems. The utility used is called randcudf and it was freely available to all participants to train their solvers. Despite the name of the utility, the generated problems are not purely random CUDF instances, but they are based on a common real universe. From this starting point, randcudf is able to generate random upgrade requests and to disturb the initial installation status according to a number of configuration parameters. The rationale behind this choice was to provide random variations of real problems that were increasingly challenging.

Among the parameters of randcudf are:

• the size of the universe: a universe can be composed by the union of all packages coming from different official releases. This allowed us to simulate the -usual -case where users mix packages coming from old and new software repositories.

• a list of packages declared as installed in the universe (status). We can associate to the same universe different installation status effectively changing the nature of the problem.

• the probability of generating install / remove requests with a version constraint. This parameter controls the CUDF request stanza and permits to adjust the constraints of individual requests.

• the number of packages declared as installed but whose dependencies might not be satisfied. This parameter allows to disturb the given base installation status effectively creating a completely different problem.

• the number of packages marked as keep and the type of keep (version or package). A package declared as keep in CUDF adds an additional constraint to be respected by the solver.

The combination of these variables allowed us to to produce problems of different size and different degree of complexity. For the official competition we generated three problem categories, with, respectively, a universe size with 30.000 (called easy), 50.000 (called difficult) and 100.000 packages (called impossible).

Moreover, to further control the type of proposed problems, we discarded all problems for which it is impossible to find a solution.

One last category of artificial problems we used in the competition were obtained by encoding into CUDF well-known difficult instances of 1-IN-3 SAT, a problem which is known to be NPcomplet [START_REF] Thomas | The complexity of satisfiability problems[END_REF].

Finally, the following five categories of problems instances were used in both tracks of the MISC competition :

Results

The Participants of MISC 2010

The following solvers were participating in MISC 2010:

• apt-pbo: apt-get replacement using a PBO solver, submitted by Mancoosi partner Caixa Mágica.

• aspcud: a CUDF-Solver based on Answer Set Programming using Potassco, the Potsdam Answer Set Solving Collection, submitted by a team from University of Potsdam.

• inesc: a SAT-based solver using the p2cudf parser (from Eclipse) and the MaxSAT solver MSUnCore, submitted by Mancoosi partner Inesc-ID.

• p2cudf : a family of solvers on top of the Eclipse Provisioning Platform p2, based on the SAT4J library, submitted by a team from Université d'Artois and IBM.

• ucl: a solver based on graph constraints, submitted by Mancoosi partner Université Catholique de Louvain,

• unsa: a solver built using ILOG's CPLEX, submitted by Mancoosi partner Université Nice/Sophia-Antipolis

Outcome

The results of the MISC competition highlight the unsa solver from the Université Nice/Sophia-Antipolis clearly as the overall winner in both categories, and at the same time show that a clever encoding tailored for a specific category can still win over a general purpose encoding. In particular, the solver p2cudf is the clear winner of the debian-dudf category, providing high quality results.

The two tables below summarize the scores obtained by the participants in both categories. The execution time was measured for each solver execution but is not shown in the tables since it was not necessary to break any ties. In general, on easy instances, all solvers took between 3 and 30 seconds to complete, while on difficult instances, the entire allotted time was used (300 secs). In addition to this summary, we also published a detailed table of results for each category, allowing all participants to inspect the solver trace (including stderr and stdout), the produced solution and the input problem. This information was meant to allow all participant to reproduce the execution and to further debug their solvers. A screen shot from the competition website is provided below:

The complete detailed results of the competition can be found at http://www.mancoosi. org/misc-2010/results/paranoid/ for the paranoid track, and http://www.mancoosi.org/ misc-2010/results/trendy/ for the trendy track.

Chapter 4

Since MISC 2010

4.1 MISC-live 3 and 4

After having organized the MISC competition 2010, two more MISC-live competitions were organized in November 2010 (MISC-live 3) and then in February 2011 (MISC-live 4). These trial runs were used in particular to test the new third user track which will be used in the international competition 2011. The novelty of the user track is that one searches for an optimal solution according to an optimization criterion provided by the user. The criterion is given by a list of utility functions taken from a fixed list of possible functions, together with a polarity ("+" for maximize, or "-" for minimize) for each of them. This is a generalization of the first two tracks "paranoid" end "trendy", since they can now be seen as special instance of the new "user" track:

• the paranoid criterion could be written as -removed, -changed

• the trendy criterion could be written as -removed, -notuptodate, -unmet recommends, -new

Towards MISC 2011

The international competition MISC 2011 will be organized at the LoCoCo 2011 workshop, which will take place on September 12, 2011, in Perugia, Italy, as a satellite event of the 17th International Conference on Principles and Practice of Constraint Programming. The preliminary timeline is:

• Participants have to declare their intention to participate by August, 1.

• Deadline for submission for solvers is August, 12.

Chapter 5

Conclusion

Running a competition is not as easy as it may seem. Some of the difficulties we encountered are:

• One has to define a standard environment in which the submitted solvers are executed. The specification of the environment must be precise enough to prevent that s submitted solver fails for some trivial reason like non-availability of a library, different version as expected of a programming language systems or interpreters like perl, python or java, or too restrictive access rights to directories.

• One has to define precisely the interface of the participating solvers. This does not only include the syntax and semantics of the command-line arguments used in the competition to invoke the solver, but also specifying in which way resource restrictions on memory and cpu time are implemented. For instance, one participant of MISC live 3 was expecting that only the top-level process of the process group of his solver instance would receive a SIGUSR1 signal shortly before the timeout, where in reality the signal was sent to all processes. This unexpected signal received by a child process caused the solver to crash, instead of writing the best solution he had found up to that moment.

• Defining the right rules for electing the winner is tricky. For instance, we had in the MISC 2010 competition four different cases of the outcome of a solver on a particular problem instance: a solver could (1) give a correct result, (2) declare that he did not find a result, (3) crash, or (4) propose a solution which is wrong (i.e., a solution which is incoherent or does not satisfy the request). Only when reviewing the results of MISC 2010 we found that the distinction between cases (2) and (3) does not make sense since the difference between the two cases is just catching, or failing to do so, all exceptions that may be thrown.

Another delicate question was how the running time of solvers should be taken into consideration. The problem is that on the one hand the running time is part of the user experience and should have some importance when ranking the participants, but that on the other hand a fast solver that yields bad solutions should never be able to win over a slow solver that finds very good solutions. We came up with a definition where running time is only taken into account for breaking ties between participants that have found equally good solutions in the average.

• Last but not least the results must be reproducible. This implies publishing all the problem instances used in the competition, instructions to rebuild the execution environment, and

  Rules of MISC 2010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Problem Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Optimization Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Ranking of Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The Execution Environment of MISC 2010 . . . . . . . . . . . . . . . . . . . . . 3.3 Requirements on Participating Solvers . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Selection of Input roblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 The Participants of MISC 2010 . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 Outcome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Since MISC 2010 4.1 MISC-live 3 and 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Towards MISC 2011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 3

 3 Figure 3.1: Sample CUDF document.

•

  is the number of packages removed in the proposed solution S w.r.t. the original installation I: #removed(I, S) = #{name | V (I, name) = ∅, V (S, name) = ∅} • #new(I, S) is the number of new packages in the proposed solution S w.r.t. the original installation I: #new(I, S) = #{name | V (I, name) = ∅, V (S, name) = ∅} • #changed(I, S) is the number of packages with a modified (set of) version(s) in the proposed solution S w.r.t. the original installation I: #changed(I, S) = #{name | V (I, name) = V (S, name)} For the next definition we need the notion of latest version of package: We write latest(name) for the most recent available version of a package with name name. We define #notuptodate(I, S) as the number of installed packages but not in the latest available version: #notuptodate(I, S) = {name | V (S, name) = ∅, latest(name) ∈ S} • #unsatisf iedrecommends(I, S) counts the number of disjunctions in Recommendsfields of installed packages that are not satisfied by S: #unsatisf iedrecommends(I, S) = {(name, v, c) | v ∈ V (S, name), c ∈ recommends(name, v), S |= c} May 24, 2011 In that definition, recommends(name, v) denotes the set of recommendations of the package with name name and version v. Each such recommendation may be a single package, possible with a version constraint, or in general a disjunction of these. Such a recommendation c is satisfied by a proposed installation S, written S |= c, if at least one of the elements of the disjunction c is realized by S. For instance, if package a recommends b, c | d | e, e | f | g, b | g, h and if S installs a, e, f , and h, but neither of b, c, d, or g , then one would obtain for the package a alone a value of 3 for #unsatisfied-recommends since the 2nd, 3rd and 5th disjunct of the recommendation are satisfied, and the others are not. If no other package contains recommendations then #unsatisfied-recommends(I,S)=3. Note that in any case the value of #unsatisfied-recommends(I,S) only depends on S but not on I.

Table 3 .

 3

	Category	apt-pbo aspcud inesc p2cudf uns
	cudf-set		135	93	90	90	107
	debian-dudf	211	189	194	39	74
	difficult		415	70	101	98	49
	easy		410	46	64	61	21
	impossible	225	190	220	181	15
	Total		1396	588	669	469	266
		Table 3.2: Trendy Track Summary
	Category	apt-pbo aspcud inesc p2cudf ucl-cprel uns
	cudf-set	162	118	108	108		108	111
	debian-dudf	236	222	32	32		216	86
	difficult	522	58	92	99		264	55
	easy	504	21	63	63		252	21
	impossible	300	270	120	120		180	15
	Total	1724	689	415	422		1020	288

3: Paranoid Track Summary

http://www.satlive.org/

Deliverable D5.4Version 1.0 page 10 of 27

source code of all the tools used for verifying and ranking solutions.

We are quite satisfied with the field of participants in the MISC and MISC-live competitions. In total, we have seen participating solvers from 4 different sites of the Mancoosi project, and 3 different teams who are not part of Mancoosi. Participating solvers are using quite different combinatorial solving techniques like SAT solving, mixed integer linear programming, pseudo-Boolean constraints, answer set programming, or graph constraints. Most of the participating solvers are totally or partly open source (the case where a solver is only partially open source usually happens when the frontend for encoding CUDF problems is open source but then uses a solving engine which itself is not open source).

Detailed information about the MISC-live trial runs, the first international MISC competition 2010, and upcoming MISC competitions can be found at the competition web site at http: //www.mancoosi.org/misc/.


One of the objectives of the Mancoosi project is to resolve some of the problems that users of Free and Open Source Software distributions experience when trying to install, remove, or upgrade packages installed on their machines. The specific goal of Workpackage 5 is to to build a data base of problem reports generated from such user requests to a meta-installer, which then will be used by the Mancoosi project, and the research community in general, to develop better algorithms to compute upgrade paths.

We have in earlier work defined CUDF as a common format for describing package upgrade problems in a common, vendor-independent way [TZ08], and different vendors have set up the tools and infrastructure to collect upgrade problem reports from their respective users [AGL + 10]. This deliverable describes the infrastructure to build a common data base of upgrade problems at a central, project-wide repository.

Introduction

Modern software systems are deployed in the form of a collection of components from which users may chose the software packages that they wish to install on a machine. This choice is not permanent and is subject to modification when a user applies updates, installs additional software in order to satisfy new requirements, removes unwanted software, or replaces one software component by an alternative component that provides the same functionality. In Free and Open Source Software (FOSS) collections, the set of available software components itself is rapidly changing, which adds further dynamics to the scenario.

In the FOSS world, software components are commonly called packages, and a collection of packages is called a distribution. It is the job of the distribution editor to create and maintain a coherent distribution. Each distribution editor chooses his format of metadata that describes some abstract properties of the packages in the distribution. The most important pieces of information in the package metadata are the name and version number of a package, its requirements, what it conflicts with, and the features it provides.

One of the objectives of the Mancoosi project is to resolve some of the problems that users experience when trying to modify the installation status of packages on their machine. In particular, Workpackage 4 of the Mancoosi project aims at developing better algorithms for finding solutions (in terms of versions of packages to install and remove) of such a user request. In Workpackage 5, we build a database of problem reports regarding failed attempts to modify the installation status of the packages that where produced with instrumented versions of currently popular tools. This database will then be available as data set to to researchers working on better algorithms, both in Workpackage 4 of the Mancoosi project, and researchers who do not participate in Mancoosi.

In order to build such a database we implemented the infrastructure to collect and store upgrade problems and make them accessible to the research community. The architecture of our infrastructure, as defined in Deliverable 5.1 [START_REF] Treinen | Description of the CUDF format[END_REF], is summarized in Figure 1.1:

1. The meta-installer available on user machines is instrumented so that they can generate a report of a failed package upgrade attempt. The format of the report is specific to the software distribution used, but follows a general project-wide scheme called DUDF (Distribution Upgradeability Description Format) [START_REF] Treinen | Description of the CUDF format[END_REF].

2. Problem reports are uploaded to a server specific to the software distribution. Chapter 2

Central Cudf Database

The final point of collection for all end-user upgrade problems is the central CUDF database. This database receives documents in the CUDF format that are generated and collected by all distribution editors. CUDF documents are distribution independent per design, and therefore constitute an homogeneous corpus of problems ready to be used by the research community.

Database Backend

Validation

The central CUDF database aims to establish a collection of difficult problems that can be used by the research community. Consequently, before selecting a CUDF problem for long term storage we perform a number of tests to check the correctness of the document and evaluating the semantic coherence.

We define coherence as the ratio of the number of broken (that is, not installable) packages to the total number of packages present in a CUDF document. Informally, a package is said to be broken if it is not possible to satisfy all it's dependencies and conflicts in an empty universe.

By empirical evaluation on a large sets of CUDF documents that we have analyzed, we noticed that a coherence index greater then 0.3, that is more then 30% of broken packages, is often an indication of a problem in the CUDF document. These kind of problems, despite originating from syntactically correct CUDF, can often be easily linked to an error in the translation process from DUDF to CUDF. It is important to notice that semantic coherence in this context can only be used to guess which documents are more likely to create problems. For this reason, our tests are not fully automatic, but generate a report containing the suspicious problems to be periodically reviewed by a human operator.

There are a number of tools involved in the validation process:

Correctness. Each Cudf document is checked using a syntax checker developed as part of the Cudf library. cudf check takes as input a CUDF document and returns true if May 9, 2011 the document is compliant with the CUDF syntax and semantic as specified in [START_REF] Treinen | Description of the CUDF format[END_REF].

Otherwise, it returns a detailed error message specifying the localization of the problem.

Coherence. Document coherence is checked using the tool distcheck which is part of the library dose32 . distcheck reads a CUDF document and returns the coherence index as described above, plus a detailed analysis of the problems encountered.

Cudf : debian/e69a0e36-9ef1-11df-9d4a-00163e46d37a.

Database Frontend

Since the CUDF central database is still in a prototype phase at the time of this writing, the front end of the database is composed of a number of static HTML pages with direct link to the CUDF problems and a summary of their validation report. We also give users full access to the database to download it and mirror. The database is accessible online at http://data.mancoosi.org/cudf/db/.

State of the Data Base

As of February 3, 2011, the data base contains 434 problem reports, coming from Caixa Mágica and debian users.

  Backend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Database Frontend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 State of the Data Base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of Figures 1.1 Reporting infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Database Backend and Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Cudf database validation report . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 1

3.

  Collected reports are translated by the distribution editor into a common format called CUDF (Common Upgradeability Description Format) [TZ08].4. Translated reports in CUDF format are transferred from the distribution editor's server to a central server of the Mancoosi project, where they will be used in the construction of a project-wide problem database.

Figure 1

 1 Figure 1.1: Reporting infrastructure Deliverable 5.2 [AGL + 10] described the submission infrastructure from end-users to distribution editors and the translation from DUDF to CUDF. The current deliverable describes the process of transferring CUDF documents to the project-wide server and the establishment of the problem data base.

Figure 2 .

 2 Figure2.1 details the implementation of the database backend. The submission mechanism is based on the rsync service 1 , which is a very common tool available on most UNIX platforms. It is efficient, and as a UNIX tool it can be easily used in scripts. We have chosen a push model where all distribution editors periodically send new CUDF documents to the central database. In order to avoid abuse of the service, each distribution editor is authenticated via a simple asymmetric encryption schema.

Figure 2

 2 Figure 2.1: Database Backend and Validation

Figure 2 . 2 :

 22 Figure 2.2: Cudf database validation report

http://rsync.samba.org/

http://www.mancoosi.org/software/#index2h1


Frédéric Landragin
email: frederic.landragin@ens.fr

Thierry Poibeau
email: thierry.poibeau@ens.fr

Bernard Victorri
email: bernard.victorri@ens.fr

ANALEC: a New Tool for the Dynamic Annotation of Textual Data

Keywords: cyclic annotation, visualization, data query

We introduce ANALEC, a tool which aim is to bring together corpus annotation, visualization and query management. Our main idea is to provide a unified and dynamic way of annotating textual data. ANALEC allows researchers to dynamically build their own annotation scheme and use the possibilities of scheme revision, data querying and graphical visualization during the annotation process. Each query result can be visualized using a graphical representation that puts forward a set of annotations that can be directly corrected or completed. Text annotation is then considered as a cyclic process. We show that statistics like frequencies and correlations make it possible to verify annotated data on the fly during the annotation. In this paper we introduce the annotation functionalities of ANALEC, some of the annotated data visualization functionalities, and three statistical modules: frequency, correlation and geometrical representations. Some examples dealing with reference and coreference annotation illustrate the main contributions of ANALEC.

Introduction

Corpus annotation is often described as a linear process in which one defines an annotation scheme, annotates data according to this scheme and then exploits these annotations for linguistic studies. Most annotation tools are developed taking this assumption as granted and do not provide any facilities to adapt the annotation scheme, which is often necessary during the annotation process. Contrary to this assumption, we think that designing an annotation scheme is a major issue that requires a 'trial and error' strategy.

Our experience shows that corpus annotation is cyclic and requires to gradually refine the annotation scheme, either because an intermediate version of it is not complete or because it is not tractable (this is typically the case when the scheme is too complex and time consuming for practical applications). In this situation, researchers and annotators need versatile tools, allowing them to refine the annotation scheme, rename or merge some features, create new features, annotate a new part of the corpus or add new annotations to an already partially annotated corpus, etc. It is thus clear that data annotation is not a static process but a dynamic one, which depends on corpus visualization and data queries. ANALEC (Victorri, 2011) 1 1 Based on the architecture of ANALOR [START_REF] Avanzi | ANALOR, A Tool for Semi-Automatic Annotation of French Prosodic Structure[END_REF].

is a new annotation tool: its goal is to allow researchers to dynamically build their own annotation scheme, using the possibilities of partial annotation, dynamic scheme revision, data querying and visualization during the

Corpus visualization zone

Corpus annotation zone:

In this example, the features are classified using three levels (some features can be edited, others not depending on the 'view').

annotation procedure itself. Automatic annotation (i.e. annotations produced by other tools like part of speech taggers) can also be integrated to help corpus annotation.

In this paper, we have chosen to present the main functionalities of ANALEC taking co-reference annotation as an example. In the four sections of this paper we will show how to annotate a corpus using ANALEC, how to visualize and update the annotated data, how to search for correlations, and how to exploit geometrical representations to help finding trends and specificities in the corpus. We discuss the differences between ANALEC and other annotation tools before reaching the conclusion of the paper.

Annotating text using ANALEC

ANALEC is an open source piece of software dedicated to text annotation (Figure 1). More precisely, it is dedicated to manual annotation and is therefore especially useful for semantic and pragmatic annotation, where automatic tools are still not accurate enough. All the examples we take in this paper deal with the annotation of semantic roles of some discourse units or noun phrases. Some of them deal with referring phenomena, and consist in the annotation of referential expressions and of links between several referential expressions.

There are three main objects that can be manipulated using ANALEC: units, i.e. chunks of texts, relations between text units and schemas to group complex sets of units and relations. Figure 2 highlights these three objects: the first column corresponds to 'units', i.e., text chunks that are marked and enriched with annotations; the second one to 'relations', i.e., links between units (note that annotations can be added to each link); the third one to 'schemas', i.e., sets of units, relations and possibly other schemas, which can also include specific annotations. Some features depend on other features (for ex., tense and mood are relevant only for verbs, not for other linguistic units): ANALEC makes it possible to define different annotation levels, some levels depending on others (on Figure 1, the different levels are visible at the bottom of the screen shot).

For co-reference annotation, referring expressions are defined as units, and co-reference chains as schemas. This is the result of several attempts to annotate these objects using different strategies (for example, modeling co-reference chains as a series of relations between text units is possible but not as clear as schemas, especially for subsequent calculations). So, while defining our annotation scheme, we had to delete some features, add new ones, rename or merge some others, etc. All this is possible with ANALEC, which implements various control mechanisms (merging two different fields may erase previous information or may create a conflict between two different possible values, ANALEC detects these kinds of problems and interact with the user whenever necessary). Lastly, annotated corpora are often difficult to visualize due to the high number of annotations, most of the time piled the ones on top of the others. In order to solve this issue, we have imagined the notion of 'view'. For the same corpus and the same set of annotations, several 'points of view' on the data can be defined, in order to make pieces of information appear or not in the annotation interface (bottom part of Figure 1). Views can be saved in separated files, as well as the annotation schemes. Moreover, some features may be locked (e.g. for non modifiable properties of a view).

Annotation visualizations with ANALEC

In traditional annotation tools, units are usually emphasized with colours, links are materialized by arrows between units, and schemes (if they exist) are represented by boxes or chains that include all related units and relations. ANALEC makes it possible to get new visualization modes that fit better with the kind of data one wants to observe. For example, in the case of co-reference chains, one wants to be able to immediately observe the succession of referring units, along with their referent. Figures 3,4 and 5 provide three different views of chained referring units, This window allows the user to navigate in the annotation scheme.

Each type, each element and each value of an element can be renamed and deleted. When deleting, ANALEC checks the presence of annotated data and informs the user whenever necessary. When renaming, ANALEC checks the presence of an already existing item with the same name. In this case, renaming implicates merging annotations. Merging two elements or two values is done in a dynamic and ergonomic manner.

The three parts of this window correspond to the three kinds of annotations: units, relations, and schemas.

In this example, there are 6 types of units, 4 types of relations, and 2 types of schemas.

their link with text and their structure in paragraphs. We are currently developing tools to exploit this information and automatically extract specific patterns from these data: to the best of our knowledge, this has never been done on a large scale before and would be very difficult and time consuming, if it had it to be done manually. The use of graphs like the one in Figure 4 is interesting because points, groups of points and colours are immediately interpretable. This kind of figures can reveal very quickly some trends in the annotated data that several tables of numbers will not reveal so easily. Whereas the colours in Figure 3 were linked to one of the features of isolated referring units, in Figure 4 they correspond to the length of reference chains and provide some information on the way the characters are mentioned in each section of the text (red corresponds to a co-reference chain with more than 10 elements, orange to a chain with 4 to 10 elements, yellow to a chain with 2 or 3 elements, and grey to singletons).

Figure 5 corresponds to a short story from Maupassant where all referring expressions have been annotated and grouped into reference chains. The colours are here linked to the types of referring expressions: pink for a proper name, yellow for a possessive determiner or pronoun, and so on.

Searching for correlations between features

ANALEC includes three kinds of computation and visualization modules to analyse annotated data: frequencies, correlations, and geometrical representations.

Most annotation tools provide frequency information, so we will rather focus on correlations and geographical relations here. Identifying correlations is automatic in ANALEC using the correlations window introduced in Figure 6. The user can choose a unit and two different features, and ANALEC automatically computes a table displaying their correlations. The cells in the table are coloured following the result of a classical chi-squared test. The red-coloured cells are then identified as significant, and the user may have a look at them. The examples corresponding to one cell are displayed when one clicks on the cell (see the concordance at the bottom of Figure 6)2

Geometrical representations of annotated data

.

Lastly, ANALEC provides advanced graphical visualization tools based on various kinds of correspondence analyses. The idea is to offer graphical representations of annotated data, where units sharing similar contexts appear together, while other ones appear isolated. It makes it easy for the linguist to identify canonical examples, more interesting ones, and rare events (here again, inspecting these examples may help to discover either interesting facts or inconsistencies in the annotation). For example in Figure 7, each point in the graph is linked Linear graphical representation of all the annotated units of a particular kind (referring expressions in this example).

Text with annotated units in yellow.

The numbers correspond to the referents.

Visualization parameters.

Caption (colour code).

to a linguistic unit, and some interesting groupings may appear depending on the features taken into account. This module is especially useful to check that all the elements of a certain type are grouped together or not. Like with the correlations window (and the frequency window), each click on a point or a group of points updates the concordance field at the bottom of the window. This module can also be used to observe the relative weight of different features during the analysis of linguistic phenomena. For example, one can observe on Figure 8 that grammatical functions and thematic roles of referring expressions are somehow correlated in the annotated corpus. Although this is not new, ANALEC makes it possible to observe and prove linguistic hypotheses in vivo, directly from the observation of the data.

Figure 5: The complete references chain of a short story.

Captions : number code (referents) and colour code (types of referring expressions).

Figure 6: ANALEC correlation window.

Comparisons with previous works

It is possible to find various annotation tools that can be compared with ANALEC, but none implements the same range of functionalities in a compact piece of software. We especially examined MMAX [START_REF] Müller | MMAX: A tool for the Annotation of Multi-modal Corpora[END_REF], WordFreak [START_REF] Morton | WordFreak: An Open Tool for Linguistic Annotation[END_REF], Glozz [START_REF] Widlöcher | La plate-forme Glozz : environnement d'annotation et d'exploration de corpus[END_REF][START_REF] Victorri | ANALEC download Web page[END_REF] and Gate [START_REF] Cunningham | GATE: A Framework and Graphical Development Environment for Robust NLP Tools and Applications[END_REF], among several others. None of these platforms offers the easy-to-use, integrated and visual environment implemented in ANALEC. They all require to a priori define the annotation scheme, using an XML file most of the time. With ANALEC, even if all the information is encoded using XML, graphical interfaces make it possible to define a model without for the end user the need to know XML or even notions such as document type definition, XML elements or labelled tree. Our experiments with various groups of linguists have proven that people who are sometimes not at ease with computers can easily use this tool. This is not the case with a platform like Gate, which includes a wide range of facilities for text annotation as well, but is much more complex to use for non experts.

Conclusion

We have introduced a new annotation tool called ANALEC that includes various facilities for the manual and semi-automatic annotation of corpora. This tool is already used by dozens of end-users for various corpus-based linguistics studies (among other, co-reference resolution, discourse structure analysis, lexical semantics of prepositions, etc.). It is an open source piece of software, the external format used for annotation is XML to ensure the compatibility with various other tools and platform, including Glozz that provides complementary modules for visualization (esp. for relations). Graphical interfaces make it possible to use the tool even without having any knowledge of XML or related technologies. ANALEC is developed using Java and J2EE so that it is multi-platform. It is available for free at: http://www.lattice.cnrs.fr/Analec. Future work concerns the development of new facilities to help the integration of ANALEC into other tools. We are currently studying the possibility to deliver ANALEC as a plug-in so that this integration would be relatively straightforward.

Figure 1 :

 1 Figure 1: Annotating one unit with several annotation levels.

Figure 2 :

 2 Figure 2: The dynamic management of the annotation scheme.

Figure 4 :

 4 Figure 4: Representation of references per paragraph.

Figure 3 :

 3 Figure 3: Linear representation of references in a text.

This is especially useful to correct inconsistencies in the annotation, making the tool being really dynamic.

Acknowledgements

We would like to thank all the linguists who use ANALEC and provided useful comments on the tool. We would also like to thank the anonymous LREC reviewers, who provided useful comments to improve the quality of this paper. This research is partially sponsored by the contract PEPS MC4 (Modélisation Contrastive et Computationnelle des Chaînes de Coréférence) from CNRS INSHS and INS2I.