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

Owen Rambow
email: rambow@ccls.columbia.edu

Discourse Relations and Propositional Attitudes

Keywords: Discourse relations, propositional attitude, FactBank

We propose a procedure how discourse should be processed when segments are not asserted by the writer but attributed by her to other sources.

Introduction

SDRT (Segmented Discourse Representation Theory [START_REF] Asher | Logics of Conversation[END_REF]) introduced the notion of a veridical discourse relation. A discourse relation R is veridical iff the following rule is valid: R(α, β) ⇒ K α ∧ K β . In words, if R(α, β) is true then the propositional contents of its arguments, noted as K α and K β , are also true. Most discourse relations are veridical (N arration, Contrast, Evidence, Elaboration, Result, Explanation, ...).

However, the only examples presented in [START_REF] Asher | Logics of Conversation[END_REF] concerning veridical discourse relations are simple to the extent that they only include assertions of the writer, as in (1a) analyzed with N arration(α, β). 3 When at least one argument of a discourse relation is not asserted by the writer but attributed to another source as in (1b) the situation becomes far more complex. In (1b), β is attributed to Jane. The semantics of the verb claim implies that the writer commits to Jane committing to the content of β but the writer doesn't commit to the content of β: she may think that it is false. In other words, independently of the fact that a discourse relation is veridical, the expressed propositional attitude (full assertion, or some weaker form of assertion) towards the content of a discourse segment must be evaluated relative to one or several source(s), e.g. the writer and Jane for the segment noted as β in (1b). [START_REF] Asher | Logics of Conversation[END_REF] discusses in great detail complex issues related to dialogue, but in our understanding, they do not discuss attribution in monologue which is the subject of this paper. Our main point is to take into account propositional attitudes so as to handle monologic discourses which do not only contain writer assertions.

(1)a. (Fred will go to Dax for Christmas) α . Afterwards (he will go to Pau) β .

b. (Fred will go to Dax for Christmas) α . Jane claims that afterwards (he will go to Pau) β .

Moreover, following the annotation in the Penn Discourse Tree Bank (PDTB) [START_REF] Prasad | Attribution and its annotation in the Penn Discourse Treebank[END_REF][START_REF] Pdtb Group | The Penn Discourse Treebank 2.0 annotation manual[END_REF], we argue that it should be one of the goals of discourse analysis to indicate the sources of the discourse relations at play in a discourse structure. For example, it will be shown in Section 4.2 that the source of N arration is Jane in (1b) and the writer in (2a). Furthermore, the propositional attitude of the discourse participants towards the semantics of a "discourse constituent" R s k (α, β) may vary. For example, it will be shown in Section 4.2 that the writer commits to the temporal sequential order of Fred's trips given by afterwards/N arration in (2a) but doesn't in (2b).

(2)a. Fred will go to Dax for Christmas. Jane doesn't know that afterwards he will go to Pau. b. Fred will go to Dax for Christmas. I believe that afterwards he will go to Pau.

In sum, discourse in which some segments are not asserted by the writerwhich are quite frequent in the journalistic genre -require a new paradigm for discourse analysis in which each discourse constituent of the form R(α, β) is annotated with information on the sources of its elements (R, α and β) and the propositional attitude of the relevant agents towards their semantics. This paradigm crucially relies on information about which discourse participants believe which proposition to what degree, as expressed in FactBank [START_REF] Saurí | FactBank: A corpus annotated with event factuality[END_REF].

Section 2 gives a brief introduction to FactBank. Section 3 presents our new paradigm for discourse analysis. Section 4 explains the new paradigm.

FactBank

FactBank is an English corpus annotated with expressed propositional attitude, which it calls "factuality" [START_REF] Saurí | A Factuality Profiler for Eventualities in Text[END_REF][START_REF] Saurí | FactBank: A corpus annotated with event factuality[END_REF]. FactBank is not concerned with discourse relations and discourse analysis. It is concerned only with events (eventualities) whose propositional attitude values are worked out clause by clause, without taking into account the discourse context or world knowledge: these values come only from lexical semantic knowledge, in particular semantic properties of verbs with a sentential complement and presence of modality or polarity markers, the interaction between these various factors being modeled.

The propositional attitude assigned to an event e is relative to the relevant sources at play, the writer and other agents. Therefore, a propositional attitude is represented as f (e, s) = x, where s refers to the agent who has expressed the attitude towards e. 4 The value x, the propositional attitude, is a pair (M od(x), P ol(x)) with a modality value and a polarity value. There exist four modality values (with an order relation), certain (CT), probable (PR), possible (PS), unknown (U), and three polarity values, Positive (+), Negative (-), unknown (u). However, there exist only 8 (and not 12) pairs (M od(x), P ol(x)) abbreviated as M od(x)P ol(x) because four pairs don't exist: U +, U -, P Ru and P Su.

Let us give some illustrations of propositional attitudes. In the discourses in (3a) consisting of a single assertion of the writer, f (e α , W r) = CT -which means that according to the writer, it is certainly the case that e α will not happen, with e α corresponding to the event described in the "positive" version of α, i.e. Fred will go to Dax. In (3b), f (e α , W r) = P R+ which means that according to the writer, it is probably the case that e α will happen, where e α is the event described in the version of α without modality marker, i.e. Fred will go to Dax. In (3c), f (e α , W r) = U u which means that the writer doesn't know what is the factual status of e α or doesn't commit to it; in contrast, f (e α , Jane) = CT +. In (3d), f (e α , Jane) = U u and f (e α , W r) = CT +. In (3e), f (e α , Jane) = CT u and f (e α , W r) = U u.

(3)a. (Fred will not go to Dax) α .

b. (Fred will probably go to Dax) α . c. Jane said that (Fred will go to Dax) α . d. Jane does not know that (Fred will go to Dax) α . e. Jane knows whether (Fred will go to Dax) α .

We conclude with a remark on the PDTB. As said in Section 1, information on sources and propositional attitude on each element of a discourse constituent R(α, β) (i.e. R, α and β) is annotated in PDTB [START_REF] Prasad | Attribution and its annotation in the Penn Discourse Treebank[END_REF], and the new paradigm we propose is inspired by work on the PDTB. However, propositional attitude information in the PDTB is not as elaborate as in FactBank, as explained in [START_REF] Saurí | FactBank: A corpus annotated with event factuality[END_REF]. For a more detailed discussion of the PDTB, see [START_REF] Danlos | Analyse discursive et informations de factivité[END_REF].

New paradigm for discourse analysis

We postulate that, in a dynamic approach, updating the discourse analysis with a new discourse segment should be performed in four steps:

(i) Work out the propositional attitudes f (e, s) = x for all events e and relevant agents (including the writer) s in the new segment, using only linguistic knowledge as in FactBank. (ii) Update the discourse structure with the new segment using one or more discourse relations, based, on the one hand, on the propositional attitude towards these events, and on the other hand, on other linguistic knowledge as well as world and pragmatic knowledge. (iii) Identify the source(s) of the newly introduced discourse relations. (iv) Possibly revise and/or complete the propositional attitudes according to the updated discourse structure. The propositional attitude assignments after the update of the discursive analysis with the segment identified as n are noted f n (e, s).

We have split the operations performed in steps (ii) and (iii) for sake of clarification. However, we don't claim that these operations must be performed sequentially. On the other hand, we do claim that they must be performed after step (i) and we will show evidence for this claim.

Step (iv) naturally comes up after steps (ii) and (iii) and we insist on the fact that this step is crucial for many NLP applications such as textual entailment, question-answering and dialog, since it is in this step that the propositional attitude information relevant for such applications is computed [START_REF] Prabhakaran | Automatic committed belief tagging[END_REF].

4 Arguments for the New Paradigm

Propositional Attitude Revision

This section explains -using a quite simple example -the revision of a propositional attitude, the operation which is performed in step (iv) in our paradigm. The example in (4a), in which both segments are attributed to the writer, is analyzed with Evidence(α, β). Consider (4b) in which β is attributed to another source (Jane); (4i) shows the propositional attitudes, and (4ii) the discourse structure for (4b). This discourse structure with the relation Evidence relies on the fact that the writer endorses what Jane said: there is no relation Evidence in (4c). Therefore interpreting (4b) with Evidence W r (α, β) implies f β (e β , W r) = CT +. There is thus revision of the propositional attitude value for e β relative to the writer: In [START_REF] Hunter | Evidentiality and intensionality: Two uses of reportative constructions in discourse[END_REF], it is postulated that there exist two uses of reportative verbs like say, an "evidential" use as in (4b) and an "intensional" use as in (4c). With the evidential use, the writer endorses the content of the embedded clause (noted γ), which corresponds to M od(f (e γ , W r)) = U ∧ P ol(f (e γ , W r)) = u, while she doesn't with the intensional use, f (e γ , W r) = U u. Our examples above support this claim. However, one of the main arguments put forward in [START_REF] Hunter | Evidentiality and intensionality: Two uses of reportative constructions in discourse[END_REF] is that evidential uses of reportative verbs allow felicitous anaphoric links from indefinites under the scope of embedding verbs to elements in extensional (non modal) contexts, while intensional uses don't. Yet, the situation seems more complex. For example, think in (5a) should be considered as intensional (as there is nothing for which evidence is being supplied), and, in accordance with [START_REF] Hunter | Evidentiality and intensionality: Two uses of reportative constructions in discourse[END_REF], (5b) is incoherent. On the other hand, (5c) is coherent thanks to the discourse connective as a matter of fact. Thus, it seems preferable to postulate that there is a single use of reportative verbs, with different values assigned to f (e γ , W r) and f (e γ , source(γ)) depending on the discourse context, and a possible revision of these values after discourse structure update. The constraints on anaphoric reference to indefinites are really based on the propositional attitudes. We leave an elaboration of a precise account to future work.

f β (e β , W r) = f (e β , W r). (4)
(5)a. Jane thinks that her husband has a mistress. She is supposed to be a redhead. b. # Jane thinks that her husband has a mistress. She is a redhead. c. Jane thinks that her husband has a mistress. As a matter of fact, she is a redhead; he is indeed cheating on her.

Propositional Attitudes for Discourse Constituents

First, we address the following question: what does it mean to assign a propositional attitude to the event described in a segment such as β in (6a) which includes a discourse connective (afterwards), an anaphoric element? The modality introduced in β att (I think ) has scope over Fred's trip to Dax or over the temporal succession of his trips, as shown in the coherent discourse in (6b). Therefore, we propose to segment (6a) as shown, with the propositional attitudes in (6i) and the discourse structure in (6ii). The segment β 1 corresponds to β without the discourse connective. So a propositional attitude can be assigned to e β1 in a standard way, see (6i). The notation seq(e α , e β1 ) corresponds to the temporal succession of e α and e β1 . seq(e α , e β1 ) is expressed through afterwards in [START_REF] Pdtb Group | The Penn Discourse Treebank 2.0 annotation manual[END_REF] and not through an eventuality expression, however the temporal succession of two events can be expressed with a "discourse verb" [START_REF] Danlos | Discourse verbs and discourse periphrastic links[END_REF] such as precede or an NP such as succession. Therefore, seq(e α , e β1 ) is an element to which a propositional attitude value can be assigned, see (6i). The discourse structure in (6ii) indicates that N arration (attributed to the writer) links β and β 1 , which is accurate.

(6)a. (Fred will go to Dax for Christmas) α . (I think that) βatt (afterwards (he will go to Pau)

β1 ) β . i f (e α , W r) = CT + ∧ (f (e β1 , W r) = P R + ∨ f (e β1 , W r) = CT + ∧ f (seq(e α , e β1 ), W r) = P R+) ii Attribution W r (β att , β) ∧ N arration W r (α, β 1 )
b. Fred will go to Dax for Christmas. I think that afterwards he will go to Pau. However, it is possible that he will not go to Pau or that he will go to Pau before going to Dax.

We are now going to address the (difficult) issue of determining the source of the discourse relation in a discourse constituent. In [START_REF] Prabhakaran | Automatic committed belief tagging[END_REF], segmented as (6), N arration is necessarily attributed to the writer because of the semantics of the factive verb know used in a negative form. ( 7) (Fred will go to Dax for Christmas) α . (Jane doesn't know that) βatt (afterwards (he will go to Pau) β1 )

β . i f (e α , W r) = CT + ∧ f (e β1 , W r) = CT + ∧ f (seq(e α , e β1 ), W r) = CT + ∧ f (e β1 , Jane) = U u ∧ f (seq(e α , e β1 ), Jane) = U u ii Attribution W r (β att , β) ∧ N arration W r (α, β 1 )
On the other hand, in (8a), which differs from [START_REF] Prabhakaran | Automatic committed belief tagging[END_REF] only by the verb and polarity used in β att , N arration must be attributed to Jane. N arration Jane (α, β 1 ) implies that Jane is aware of Fred's trip to Dax, as shown by the incoherence of (8b). This results in f β (e α , Jane) = CT + with "completion" of the propositional attitude value for e α relative to Jane. Indeed, α being asserted by the writer, no value is assigned to f (e α , Jane). That is the reason why we speak of completion (and not revision) of the propositional attitudes.

(8)a. (Fred will go to Dax for Christmas) α . (Jane thinks that) βatt (afterwards (he will go to Pau) β1 ) β . ii Attribution W r (β att , β) ∧ N arration Jane (α, β 1 ) b. #Fred will go to Dax for Christmas, which Jane does not know. She thinks that afterwards he will go to Pau.

In conclusion, propositional attitude information is crucial to identify the sources of the discourse relations at stake. This is why step (iii) in our paradigm should be performed after step (i).

Updating the Discourse Structure

This section, whose aim is to explain why the update of the discourse structure must take into account propositional attitudes, focuses on the veridical relation Contrast, lexically marked with yet or but. Contrast W r (α, β) is often observed when there is an "unexpected result", as illustrated in (9a) in which breastfeeding normally entails ¬ constipated. When at least one of the arguments of Contrast is attributed to a source other than the writer through factive verbs (confirm or discover ) as in (9b-d), Contrast W r (α, β) can be maintained.

(9)a. (Bébé is being breastfed) α , yet (he is constipated) β .

b. (Jane has confirmed that) αatt (she is breastfeeding Bébé) α , yet (he is constipated) β . c. (Bébé is being breastfed) α , yet (Julie has discovered that) βatt (he is constipated) β . d. (Jane has confirmed that) αatt (Bébé is being breastfed) α , yet (Julie has discovered that) βatt (he is constipated) β .

However, there are a number of examples built on the patterns in (9b-d) for which Contrast s (α, β) cannot hold for any source s. First, consider examples on the pattern of (9b) with β asserted by the writer, α attributed to another source: in (10) e α = e β , in [START_REF] Saurí | FactBank: A corpus annotated with event factuality[END_REF] α entails that β cannot happen.

(10)a. (Jane does not know that) αatt (Fred will go to Dax) α , but (he will) β .

b. (Jane does not think that) αatt (Fred will go to Dax) α , but (he will) β . c. (Jane thinks that) αatt (Fred will not go to Dax) α , but (he will) β . d. (Jane suspects that) αatt (her husband is cheating on her) α , but (he is probably not) β .

(11)a. (Jane thinks that) αatt (only Fred will go to Dax) α , but (Paul will go, too) β . b. (Jane suspects that) αatt (her husband is cheating on her) α , but (he is faithful to her) β .

When asserting β in [START_REF] Saurí | A Factuality Profiler for Eventualities in Text[END_REF] or [START_REF] Saurí | FactBank: A corpus annotated with event factuality[END_REF], the writer gives evidence that Jane is wrong concerning her propositional attitude towards e α : technically, in [START_REF] Saurí | A Factuality Profiler for Eventualities in Text[END_REF], f β (e α , W r) = f (e β , W r), in [START_REF] Saurí | FactBank: A corpus annotated with event factuality[END_REF], f β (e α , W r) = CT -and in both casesf β (e α , W r) = f (e α , Jane).

The situation is similar with examples such as (12a-b) in which α is asserted by the writer and β attributed to another source. The semantics of such examples is mainly that the propositional attitude of Jane and the writer diverge towards e β : f (e β , Jane) = f β (e β , W r). Finally, in (12c) with e α = e β , f β (e β , Jane) = f β (e β , Julie).

(12)a. (Fred will go to Dax) α , but (Julie does not think that) βatt (he will go) β .

b. (Fred never cheats on his wife) α , but (she suspects that) βatt (he is sleeping around) β . c. (Jane thinks that) αatt (Fred will go to Dax) α , but (Julie does not think that) βatt (he will go) β .

It can be argued that each example of this section -except (9a) -can be analyzed with a Contrast relation between two complex segments analyzed with an Attribution relation, see the discourse structure in (13a) for (9d) or (12c), in which the complex segments are surrounded by brackets. The attribution text spans must then be considered as implicit for the segments asserted by the writer, corresponding to I know or I affirm and noted α att or β att . See for example (13b) for (12a).

(13)a.

Attribution W r (α att , α) ∧ Attribution W r (β att , β) ∧ Contrast W r ([α att , α], [β att , β]) b. Attribution W r (α att , α) ∧ Attribution W r (β att , β) ∧ Contrast W r ([α att , α], [β att , β])
The discourse analyses in (13) are quite plausible, however it should be noted that distributivity rules -see [START_REF] Asher | Complex discourse units and their semantics[END_REF] for distributivity rules over complex segments -such as

Contrast W r ([α att , α], [β att , β]) ⇒ Contrast W r (α, β
) and the variants of this rule when α or β is asserted by the writer cannot be maintained: they are valid in (9b-d) but not in ( 10)-( 12) for which Contrast W r (α, β) doesn't hold. Moreover, consider (14) which is identical to (9b) except that say is used in α att instead of confirm. This discourse is ambiguous in that the writer's opinion can be twofold: either she thinks that Jane is lying or she doesn't.

The lying case implies that the propositional attitudes towards α of Jane and the writer differ (f β (e α , W r) = CT -and so f β (e α , W r) = f (e α , Jane)) as in [START_REF] Saurí | A Factuality Profiler for Eventualities in Text[END_REF] or [START_REF] Saurí | FactBank: A corpus annotated with event factuality[END_REF], and the writer underlines this difference. The non-lying case implies that Jane and the writer share the same propositional attitude towards α (f β (e α , W r) = f (e α , Jane) = CT +) and the writer underlines the contrast between α and β as in (9b).

(14) (Jane said that) αatt (she is breastfeeding Bébé) α , but (he is constipated) β .

i f (e α , Jane) = CT + ∧ f (e α , W r) = U u ∧ f (e β , W r) = CT + In sum, it seems that we can postulate Rule 2 with a disjunction in the right part. Determining which member(s) of the disjunction is (are) true depends both on the semantics relation between α and β and on the propositional attitude value assigned to f (e α , W r). Similar rules could be postulated as well when α is asserted by the writer, β being or not asserted by the writer. In conclusion, the various examples discussed in this section about Contrast show that the discourse structure crucially depends on the event propositional attitude information. That is the reason why we claim that step (ii) should be performed after step (i) in our new paradigm for discourse analysis (Section 3).

Conclusion and perspectives

We have proposed a new paradigm for discourse analysis in which expressed propositional attitude information (such as that given in FactBank) plays a crucial role. This article sketches an initial outline for this new paradigm and a number of (technical) issues that still require attention. Specifically, we have seen that the "lying" interpretation requires an explicit modeling of the difference between expressed and inferred (revised) propositional attitude.

  a. (The neighbors have gone on vacation) α . (Newspapers are accumulating on their doorstep) β . b. (The neighbors have gone on vacation) α . (Jane told me that) βatt (newspapers are accumulating on their doorstep) β . i f (e α , W r) = CT + ∧ f (e β , W r) = U u ∧ f (e β , Jane) = CT + ii Attribution W r (β att , β) 5 ∧ Evidence W r (α, β) c. The neighbors have gone on vacation. Jane claimed that newspapers are accumulating on their doorstep, but that is wrong.

Rule 1

 1 Contrast W r ([α att , α], [β att , β]) ⇒ Contrast W r (α, β) ∨ R(α, β) 6

N arration in SDRT is called Sequence in RST.

In fact, the propositional attitude assignments are more complex because of nested sources as in Julie said that Jane claims Fred will go to Dax. However, nested sources will be ignored in this paper. This allows us to make the following simplification : we use f (e, s) instead of f (e, writer -s) used in FactBank for a source s different from the author.

As in RST[START_REF] Redeker | Says who? on the treatment of speech attributions in discourse structure[END_REF], the relation Attribution is used to link an attribution text span (e.g. Jane told me) to the attributed text span. Attributions(γatt, γ) implies that s claims that the source of γ is given in γatt. In the examples presented in this paper, γatt is built around a verb introducing a clausal complement and the source of γ is the referent of the subject of this verb.

We have not found an appropriate name for R with R(α, β) ⇒ f β (eα, W r) = f (eα, source(eα)). This relation is close to Correction as defined in[START_REF] Asher | Logics of Conversation[END_REF] but should not be confused with it.


Pascal Denis
email: pascal.denis@inria.fr

† Alpage

Philippe Muller
email: muller@irit.fr

Predicting Globally-Coherent Temporal Structures from Texts via Endpoint Inference and Graph Decomposition

, but becomes impractical when considering all possible interval relations. This paper proposes two innovations, inspired from work on temporal reasoning, that control this combinatorial blow-up, therefore rendering an exact ILP inference viable in the general case. First, we translate our network of constraints from temporal intervals to their endpoints, to handle a drastically smaller set of constraints, while preserving the same temporal information. Second, we show that additional efficiency is gained by enforcing coherence on particular subsets of the entire temporal graphs. We evaluate these innovations through various experiments on TimeBank 1.2, and compare our ILP formulations with various baselines and oracle systems.

Introduction

Learning the temporal ordering over events, dates and other temporal entities in a text consists in finding a set of temporal relations (precedence, inclusion, etc.) between these entities. This task is an important aspect of discourse understanding and its automation has potential applications (e.g., discourse parsing, text summarization, information extraction). An important challenge of this task is that temporal relations carry algebraic properties reflecting the linear structure of time (e.g., the transitivity of precedence and inclusion) which make the determination of the temporal relations between entity pairs strongly interdependent. While prior work acknowledges this, most recent approaches to temporal ordering assume a fairly idealized setting, wherein [START_REF] Mani | [END_REF]: a. the pairs of entities to be related by the system have been pre-selected by an oracle b. each of these pairs are labeled independently by a locally-trained classifier Predicting temporal relations this way (even under assumption (a)) runs the risk of producing structures that are incoherent at the level of the text, which are of little applicative use (especially, if further reasoning is performed on them).

There are a few exceptions to this methodology [START_REF] Bramsen | [END_REF][START_REF] Tatu | [END_REF][START_REF] Chambers | [END_REF]. These approaches directly exploit the inferential properties of the temporal relations to constrain the classifier decisions in a way that ensures overall coherence. Specifically, the following scenario is assumed: (i) learn a soft classifier which outputs a score for each local pair and relation and (ii) combine these local preferences with coherence constraints on the temporal graph within a global optimization problem. Both exact and approximated inference schemes have been investigated for the second step. To perform exact inference, [START_REF] Bramsen | [END_REF][START_REF] Chambers | [END_REF] propose to use Integer Linear Programming (ILP). This framework has interesting properties: temporal constraints can be encoded in a declarative fashion and efficient solvers are available off-the-shelf. Moreover, ILP has been shown to outperform greedy inference algorithms on this task [START_REF] Bramsen | [END_REF]]. An important restriction used in both papers is to consider only the strict precedence relation (i.e., before, after). This restriction guarantees formulations that remain manageable by current solvers, but at the expense of expressiveness. Many situations described in texts (e.g., inclusion, overlap) cannot be represented with precedence alone, and it is not clear how this restriction can be mixed with later generalizations. The standardized TimeML annotation [START_REF] Pustejovsky | [END_REF] has indeed 12 relations, the interval algebra of [Allen, 1983] has 13, with more complex interactions that can lead to increased combinatorial complexity. Being an NP-hard problem, inference in ILP is highly sensitive to the number of variables and constraints used to represent our problem. In the general case these numbers are both exponential in the number of temporal relations that are used.

In this paper, we explore another strategy that circumvents the complexity problem but in a way that preserves all the information provided by annotations. First, we re-express the network of temporal constraints on intervals into constraints on their endpoints (i.e., from 13 to 3 simple relations), thus dramatically reducing the number of variables and constraints.

Crucially, this conversion leads to a much simpler optimiza-tion problem and the result of the optimization can be "unpacked" without loss of information. Second, we decompose the set of temporal entities in "meaningful" sub-graphs and maintain coherence only within these substructures. We report on two main sets of experiments on the TimeBank dataset and confirm that the ILP strategy performs well on the task of predicting consistent relations from a local classifier, both when the relevant event pairs are known in advance and when they aren't. Our contribution is thus two-fold: we show how to generalize ILP for temporal prediction with the full set of relations used in available annotations, and we provide the first attempt at solving the task without any of the relaxed constraints assumed in prior work. The rest of the paper is organized as follows. Section 2 presents the context of this study (data, representations, related work). Section 3 details our translation of the problem into point representations using ILP, and Section 4 develops our methods for decomposing the global temporal problem. Finally we discuss our experiments and results in Section 5.

Background

The problem of constructing temporal structures from texts is illustrated on a small, slightly simplified example from the Aquaint TimeML corpus:

President Joseph Estrada on Tuesdayt 4 condemnede 1 the bombingse 5 of the U.S. embassies in Kenya and Tanzania and offerede 12 condolences to the victims.

[...] In all, the bombingse 10 last weekt 5 claimede 4 at least 217 lives.

The fully specified temporal graph for this document is given in Figure 1 with the 5 original human annotated links (in light shade) and a relation between dates based on a simple calculation from the annotation (in dark shade); it is augmented with the 6 relations (or 17 if we include inverses) that can be inferred from it. The graph exhibits 3 different types of relations: event-event (E-E, solid lines) relations, event-time (E-T, dashed) relations, and time-time (T-T, dotted) relations. In line with previous work, our focus will be on predicting E-E relations, but we will however make use of E-T and T-T information to ensure global coherence (more on this in Section 5).

Data and representation

Most recent research efforts on temporal processing have been based on TimeBank.1 This corpus (version 1.2) contains 186 news report documents collected from the DUC and ACE evaluation campaigns, annotated using the TimeML standard for tagging events (and states) and time expressions (timex for short), including dates and durations, and their temporal relations (called tlinks). There are 11 types of relation, whose semantics is similar to the well known Allen relations on intervals [Allen, 1983], excluding the overlap relation and its inverse. Allen relations defines all possible ways of relating two intervals according to all possible orderings of their endpoints. The distribution of these relations on E-E pairs is summarized in Table 1, with Allen and TimeML names. This table includes the additional E-E relation instances proposed by [Bethard et al., 2007]. The "Base" column lists the relations annotated in the corpus, while the "Sat." column lists the relations that can be deduced from the annotations with the proper inference procedure (or "saturation") explained below. We also added relations between dates that are implicit because of the values put by the annotator (in the example, t 4 had the value 1998-08-11 and t 5 1998-08-04). Combined with other E-T and E-E relations, these generate also new E-E relations. Each relation has an inverse relation (not shown in the table) except equals. The majority class in each case (28 and 37%) is thus based on twice as many relations. In order to make explicit the relations that are implicit in human annotated corpora, a procedure is needed to combine the already existing information in the most precise way. Initially, authors have relied on composition rules for simple relations only but turned to more general models dedicated to temporal reasoning [Verhagen, 2005]. The most appropriate in the context of annotation of event relation is the interval algebra of [Allen, 1983], as TimeML relations have the same semantics as a subset of Allen relations. A relation algebra defines a calculus on a set of base relations and any disjunctions of these relations, with union and intersection operators on disjunctions, and a composition of relations. Knowing relations between (x,y) and (y,z), one can compose them to add constraints on the relation bearing on (x,z), only using a table of composition of the 13 base relations, union and intersection. Applying this to all possible triplets of relation of a graph of temporal constraints is known as path-consistency checking, and can enrich a representation as seen Table 1, but can also detect an inconsistent set of constraints, which is crucial in the context of relation prediction. In the general case, path-consistency checking is correct but not complete: some inconsistent configurations cannot be detected that way. Fortunately, in the case of human temporal annotations, only simple relations are initially present, and their compositions generate a sub-algebra of so-called "convex" relations over which path-consistency is complete [Van Beek, 1990].

Evaluation

The evaluation methodology of studies that consider relations independently is simply to estimate the accuracy of the classifier on the annotated event pairs. To take coherence into account and address the problem at the text level, the evaluation must also consider the whole graph of E-E pairs, including relations that can be inferred from the reference. In the example, it means we must provide an answer for the relation e 5 < e 1 , which was not annotated but can be inferred from the annotation. The methodology followed in [START_REF] Mani | [END_REF] is to propagate constraints in the graph and evaluate system and reference with respect to all the event pairs that end up related with a simple TimeML relation in the reference and the system, yielding precision and recall scores. In a global setting, a more complete methodology should also evaluate the consistency of the graphs produced.

Previous work

Research on temporal ordering has a long in NLP.

Early work was mainly concerned with the study of language mechanisms and information sources (such as tense, aspect, lexical semantics, rhetorical relations) that impact temporal ordering. The recent availability of annotated ressources like the TimeBank corpus, and the organization of two TempEval campaigns, has revived interest in temporal processing and triggered a shift to machine learning techniques. The standard tasks include the detection of events and timex, the anchoring of events to times, and the ordering of events restricted to selected contexts (sentences/consecutive sentences) [START_REF] Verhagen | [END_REF] or document-wide [START_REF] Mani | [END_REF]. Even when they address the task of event ordering at the document level, researchers simplify the problem to allow for the straightforward application of classification techniques. Thus, most research have focused on the task of independently predicting the correct relation for pre-selected pairs of events, explicitly in the human annotations. Going back to our example, this means only predicting for the unique E-E pair (e 5 , e 12 ). It is furthermore usually assumed that the E-E pair is already ordered (i.e., (e 5 , e 12 ) is a decision point, but (e 12 , e 5 ) is not), thus reducing the number of possible relation labels from 13 to 6 [START_REF] Mani | [END_REF]. Temporal reasoning is sometimes invoked, but only during training and only to expand the pool of pair examples. [START_REF] Mani | [END_REF] use this resampling technique and report an accuracy score of 93.1% (62.5% without resampling) for the 6-way classification task.

The majority class (i.e., before) baseline in this case is 75.2% (51.6% without resampling). An obvious shortcoming of this "local" approach is that it ignores the algebraic properties of temporal relations at prediction time, and does not guarantee the coherence of the event graph at the document level. We will see in Section 5 that most structures predicted this way are incoherent, therefore useless for downstream applications. More recently, various attempts have been made at predicting globally coherent structures. These approaches still rely on a locally-trained classifier but they use the algebraic properties of relations as constraints during inference. For example, [START_REF] Tatu | [END_REF] propose a greedy search procedure with backtracking that is applied to a graph of events, in which the pairs are set to the reference pairs. In another context, [START_REF] Bramsen | [END_REF] describe various other greedy inference schemes. Finally, [START_REF] Bramsen | [END_REF][START_REF] Chambers | [END_REF] reformulate the problem of "decoding" a temporal graph under coherence constraints as a global optimization problem that can solved exactly with integer programming. Importantly, both papers use a small subset of the TimeML relations: only strict precedence relations (before, after). This has a clear advantage from a combinatorial perspective: by reducing the number of relations from 13 to 2, they manage to obtain ILP formulations that have a reasonable number of variables and constraints, at the expense of expressiveness. Chambers and Jurafsky [START_REF] Chambers | [END_REF]]'s global model provides accuracy gains over the local classifier alone (from 66.8% to 70.4%), on the saturated gold event graph. But these improvements are partly obtained thanks to additional constraints derived from the gold (namely, all the E-T and T-T relations, which they saturated and supplemented with their automatically computed T-Ts). So it is unclear where these improvements come from between the global optimization and the E-T/T-T oracle. We will check this in our own experiments by directly measuring the peformance of this oracle. The approach proposed by [START_REF] Bramsen | [END_REF] is similar to [START_REF] Chambers | [END_REF], but its scope is different. They consider the task of ordering entire paragraphs (from the biomedical domain), so that the number of entities to relate is much smaller (they report 20 segments on average), but do not assume the reference pairs and are closer to the global task. Another related work is [START_REF] Yoshikawa | [END_REF], who also adopt a global approach that uses Markov Logic (instead of ILP) to jointly predict E-T and E-E relations (but only between entities appearing in consecutive sentences).

It should be clear that trying to generalize the approach of [START_REF] Chambers | [END_REF] to the full interval algebra is going to create an important combinatorial explosion both in terms of the number of variables and the number of constraints needed to represent the problem. In order to generalize to all TimeML relations, one has to consider every "generalized" relation and their combinations. The composition of any generalized relation, as we just saw, requires a specification of the 13 × 13 base compositions. The number of possible relations between two events is in general 2 13 = 8192, and 82 if one only considers convex relations. This translates into a minimum of 82 * n 2 LP variables (for n entities), and 82 2 * n 3 constraints (for relation compositions alone); that is, 8200 variables and close to 7 million constraints for just 10 entities. Section 3 comes back in detail on these aspects, but it is important to note that disjunctive information is crucial for the checking of the consistency of predictions.

A global model over endpoints

Section 2 indicated that the global inference strategy used by [START_REF] Bramsen | [END_REF] and [START_REF] Chambers | [END_REF] is not likely to scale up when considering the full set of temporal relations in the TimeBank. This section proposes a simple solution to control this combinatorial complexity: to reformulate the optimization problem into a simpler yet semantically equivalent form by using the conversion between interval and interval endpoints.

Events and event endpoints

As for intervals, one can define an algebra on interval endpoints or Point Algebra (PA) [Vilain et al., 1990]. By relying on a smaller relation set (and also fewer possible compositions), this algebra is better suited for inference purposes in our context. While there are 13 possible base relations on intervals, there are only 3 base relations (and only 7 when considering all the possible disjunctions). The basic relations are noted ≺, , and =. The disjunctions are noted , , ≺ , and the general disjunction {≺, =, }, meaning no information is known ("vague"). We will use only 5 of these, since the vague relation is implied in absence of a more specific information, and ≺ is impossible when we start with only basic (precise) relations on points. Translations from or into PA indeed preserve the convex property, and path-consistency is thus complete for the translation of a convex graph into PA.

The resulting compositions are listed in Table 2; a blank indicates the result is the vague relation so this composition needs not be expressed. There are now only 17 constraints resulting from compositions for each event pair. Once the composition

• ≺ = ≺ ≺ ≺ ≺ ≺ = ≺ = Allen order/endpoints b (≺, ≺, ≺, ≺) m (≺, =, ≺, ≺) o (≺, , ≺, ≺) s (=, , ≺, ≺) d ( , , ≺, ≺) f ( , , ≺, =)
Table 2: Composition of point relations (left) and correspondence events/points (right).

constraints are taken into account, we can translate back to a set of constraints on events. For each event pair (e 1 , e 2 ), we consider the four relations between their endpoints , (e - 1 , e - 2 ), (e + 1 , e - 2 ), (e - 1 , e + 2 ), (e + 1 , e + 2 ) shown Table 2. If these relations are all specified and non disjunctive, it translates as a unique Allen base relation. If the point relations are disjunctive, the translation is the disjunction of all the translations obtained by distributing the point disjunctions: e.g. the four relations ( , , ≺, ≺) correspond to the two possibilities (≺, , ≺, ≺), (=, , ≺, ≺), translated as overlaps or starts.

ILP formulation

We detail here the encoding of global constraints on events in Integer Linear Programming. ILP solves constraints while optimizing an objective function, a linear combination of a set of weighted variables. In our case, these variables correspond to triples (r, p, q), where p and q are endpoints, and r a possible relation over them. The weights on those variables, noted c (r,p,q) , are derived from the classifier scores (on event pairs) by summing over the relevant interval relations on intervals containing those points. For instance, the score for {≺, p, q} is obtained by summing the scores for relations before, meet, duringi, and finishi for the event pairs that includes p and q as endpoints. Formally, let P be the set of points resulting from the translation of events. Let R = {≺, , =}, and R + = R ∪ { , }. Let also Inv: R → R be the inverse operator, and Comp: (R × R) → R the composition operator. The objective function is defined as:

max (p,q)∈C r∈R c (r,p,q) • x (r,p,q)
(1)

x (r,p,q) ∈ {0, 1} ∀ p, q ∈ P × P, p = q, ∀r ∈ R + (2)

Note that for n initial events, there are 2n points, so we end up with 5 * (2n) 2 = 20n 2 variables (i.e., 4 times less than for the equivalent event-based formulation). We now put the following additional constraints on these integer variables. For all pairs of points e - i , e + i defining the event e i , we set x (≺,e - i ,e

+ i ) = 1 and x (=,e - i ,e + i ) = x ( ,e - i ,e + i ) = 0.
At most one base relation can hold between 2 points:

r∈R x (r,p,q) ≤ 1 ∀ p, q ∈ P × P, p = q (3)
Disjunctive relations are related to simple relations:

x (≺,p,q) + x (=,p,q) ≤ x ( ,p,q) (4) x ( ,p,q) + x (=,p,q) ≤ x ( ,p,q) (5)

In case compatible relations x ( ,p,q) and x ( ,p,q) are separately inferred, we must ensure the most specific information and incompatible relations cannot be inferred at the same time, which is achieved with:

x ( ,p,q) + x ( ,p,q) ≤ x (=,p,q) + 1 (6) x ( ,p,q) + x ( ,p,q) ≤ 1 (7) x (≺,p,q) + x ( ,p,q) ≤ 1 (8)

These correspond to the "intersections" of relations in the algebra. Also, we add symmetry constraints:

x (r,p,q) ≤ x (Inv(r),q,p) ∀r ∈ R+ (9) x (r,p,q) ≥ x (Inv(r),q,p) ∀r ∈ R+ (10)

Finally, the triangular constraints from Table 2 are, ∀ p, q, t ∈ P × P × P, p = q = t, ∀r 1 , r 2 ∈ R + :

x (r1,p,q) + x (r2,q,t) ≤ x (Comp(r1,r2),p,t) + 1 (11)

These represent the bulk of our constraints: they are in the order of

|P | 3 × |R + | 2 , ie 8 * 17n 3 if n is the number of events (|P | = 2n
). The equivalent generalized (convex) event based version has 82 * 82n 3 constraints, about 50 times more, and would need a huge additional set of intersective constraints per edge (vs. 3 in PA).

Graph decomposition

Considering all possible relations on the graph of events puts a considerable burden on the decoding phase, and the translation into PA partially addresses this problem. But considering all possible E-E pairs has also a strong (potentially negative) impact on the precision of the predictions. As it stands, our ILP formulation is biased toward predicting simple relations. This is due to the fact that disjunctive relations are not part of the objective function (the classifier does not assign them any score), so disjunctions are only going to be predicted in cases where none of the base relations produce a coherent structure. One possible way within ILP to avoid this "overzealous" behavior of the system is to add a "vague" class to all unrelated event pairs and add them to the training phase, as in [START_REF] Chambers | [END_REF], but this leads to an overrepresentation of the vague relations. Another solution is to find a decomposition of the temporal graph so as to limit the decisions to relevant subgroups of events, and predict relations only within these subgroups. This assumes it is possible to structure temporal situations into so-called time-frames that help mental representations. This is in a way the mirror image of the idea proposed in [START_REF] Bramsen | [END_REF], where consecutive events are grouped within large segments, and relations are predicted between these segments. The decomposition must be meaningful for that strategy to succeed, and we must find a way of adding between-groups relation afterwards. We tried two different decompositions. The first is based on an observation: human annotations are often scattered, and events appear in separate, smaller, self-connected components. Using the structural knowledge encoded in the gold as an oracle, we restrict our constrained prediction strategy to these connected components. No other knowledge from the gold was considered (in particular, no knowledge as to which events were related in the gold).

The second decomposition groups events with dates appearing in the same sentence, exploiting the fact that most dates in TimeBank have determined values. Events located in sentences without dates were arbitrarily attached to the most recently introduced date. We then predict relations within each subgroup with a consistent prediction; finding relations between subgroups boils down to finding relations between the dates they are centered on, and that information is already available from the extraction phase we assumed, as in the previous experiments.

Experiments

We carried out two main sets of experiments to evaluate our global ILP model on endpoints. First, we evaluated the bare model presented in Section 3 on the fully closed reference event graph, i.e. the graph resulting from saturating all E-E, E-T, and T-T annotations (including the extra relations from Bethard, and those obtained by date calculations). Secondly, we combine the ILP point model with the graph decompositions described above. All our experiments were performed using 5-fold cross-validation on the TimeBank 1.2 corpus.

The ILP-based system (ILP) is compared with a number of other systems: the base classifier without consistency checking, a baseline ordering events in the order of the text (BE-FORE), a greedy natural reading ordering taking the most probable relations in sequence (NRO), and an oracle (ZERO-EE) that provides E-E relations predicted only by saturation over the E-T and T-T relations we start with. As our base model, we used a log-linear (aka Maxent) 11-way classifier trained on the fully closed TimeBank (each E-E pair of the graph was used as training instance). The feature set relies on the attributes provided in the TimeBank (event class, tense, aspect) as in [START_REF] Mani | [END_REF][START_REF] Chambers | [END_REF]. Parameters were estimated using the Megam package2 under the default settings. For training, the data was sampled from the TimeBank in a way that mirrors the decompositions; no resampling was performed for the first experiment. The LP solver we used is SCIP3 , which is currently the fastest noncommercial mixed integer programming solver. The solver was timed out after 1 hour or stopped when it reached 2 × 10 6 triangular constraints. These cases are reported as inconsistent output in the results. The evaluation is always made w.r.t. to all simple relations inferrable from the reference annotations. This only makes sense if the resulting reference graph is consistent, and we thus restricted this evaluation to the 139 texts where this is true (out of 186). We use micro-average to balance the contributions made by short and long texts.

Results for the first experiment are shown in Table 3. We report scores in terms of accuracy, since we assume the reference event graph, to match experiments in [START_REF] Chambers | [END_REF]. The systems also generate different inferences and produce simple relations on pairs not in the reference, and this will be evaluated with recall/precision in the context of the more complete second experiment.

Making zero E-E predictions and assuming only E-T relations (before saturation of the graph) yields an accuracy of 26%; this is to be considered as the minimum information provided before predicting E-E relations. The relatively high accuracy of this oracle method should however be taken with caution, as it assumes perfect knowledge of E-T relations, while the best dedicated systems in simpler settings reach accuracies of 80-90% [START_REF] Verhagen | [END_REF][START_REF] Mani | [END_REF]. We tested that by changing at random 10% of these assumed relations, a lot of inconsistencies arise and accuracy drops to 5%. Accuracy here is actually a recall measure: [START_REF] Chambers | [END_REF] don't consider predictions made by their system (even if it's a precise precedence relation) when the reference does not imply a before/after relation. The importance of this can be seen from the fact that a simple consistent baseline as BEFORE reaches about 38% of recall while generating 94% of erroneous predictions. The consistent NRO fares better on precision (60%), at the expense of a drop in accuracy on the reference. The base classifier has an accuracy on separate decisions of 60.1% (trained and tested on saturated data), but 82% of the graph it predicts are inconsistent. When ILP is used to constrain these predictions we reach a recall of almost 50%. This is the score reached by [START_REF] Tatu | [END_REF] on the reference predictions where they actually managed to preserve consistency, and we use the whole set of relations while they have only six.

In a comparable setting but with only two relations, [START_REF] Chambers | [END_REF] and again ILP has a better recall while NRO has a better precision. The percentage of inconsistent predictions by ILP is now up to 8.6%, due to the absence of consistency constraints between subgroups. This is less than 3% more than the number of time-outs, an indication that this decomposition is not too damaging for consistency. Assuming this decomposition the base classifier produces now 96% of inconsistent graphs. Our decomposition method is clearly too crude, and can only serve as a starting point for more elaborate approaches. We can nonetheless claim that the problem of temporal structure prediction is doable within this framework, without assuming anything about E-E relations, or resampling the test environment. For each experiment, we tested the differences between ILP and the other methods with a Wilcoxon signed-rank test over the measures for each text and found high significance levels (p <10 -5 at worst).

Conclusion

We have generalized proven strategies for temporal prediction from a few simple relations to the complete set of relations used in existing temporally annotated corpora like TimeBank. We also provide the definition of intermediate steps in the direction of predicting temporal structures without assuming too much of the target representation, mainly without assuming the small subset of event pairs to relate among the n 2 possible pairs. This is done by looking at decompositions of the temporal structure, either using some knowledge about the gold annotation, or using a basic heuristics, and to the best of our knowledge the latter is the first attempt at the unrestricted global task on a significative corpus of texts. It has room for improvement, since we did not use any linguistic knowledge about global attachment of temporal entities. Event grouping could be a relevant subtask for temporal extraction. The use of point based representations could be pushed further in future work to check whether it can also help the learning phase, by translating the corpus before training. We have not devoted too much attention to the learning phase here, but in the context of a global prediction, we could test on the utility of learning to predict not only simple relations (since this forces a lot of decisions to be made) but also vaguer ones (in a manner similar to the final experiment of [START_REF] Chambers | [END_REF]).

Figure 1 :

 1 Figure 1: The full temporal graph for the Aquaint excerpt. Labels b and d stand for before and during.

Table 3 :

 3 reach 70% accuracy. Results on TB, assuming reference event pairsWe now turn to the much harder task of predicting the temporal structure without pre-selecting event pairs; performance scores with a decomposition in self-connected maximal components are given in Table4. We repeat BEFORE scores for clarity, although it is by construction insensitive to the different setting (as ZERO-EE). On the connected component oracle, we can see that NRO holds its ground even without selecting event pairs, and ILP benefits the most of the context, even though it times out on a few texts. We estimated that ILP was practical up to 25 nodes in a sub-graph. The base classifier predicts 88% inconsistent graphs here. Results on decomposition around dates are of

	System	ZERO-EE	BEFORE	NRO	ILP
	Accuracy	26.01	37.93 20.08 49.80
	System	Precision Recall F1-score Inco.
	ILP	33.02	54.07	41.00	5.93
	NRO	49.98	17.02	25.40	0.00
	BEFORE	6.22	37.93	10.69	0.00

Table 4 :

 4 Decomposition on connected components course lower since no knowledge of E-E relations is provided. NRO and ILP are close (respectively 16.3% and 15.0% in F1),

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence

http://timeml.org/site/timebank/

http://www.cs.utah.edu/˜hal/megam/

http://scip.zib.de/


Pascal Denis

Benoît Sagot

Coupling an annotated corpus and a lexicon for state-of-the-art POS tagging

Keywords: Part-of-speech tagging, maximum entropy models, morphosyntactic lexicon, French, language resource development

This paper investigates how to best couple hand-annotated data with information extracted from an external lexical resource to improve POS tagging performance. Focusing mostly on French tagging, we introduce a Maximum Entropy Markov Model-based tagging system that is enriched with information extracted from a morphological resource. This system gives a 97.75% accuracy on the French Treebank, an error reduction of 25% (38% on unknown words) over the same tagger without lexical information. We perform a series of experiments that help understanding how this lexical information helps improving tagging accuracy. We also conduct experiments on datasets and lexicons of varying sizes in order to assess the best trade-off between annotating data vs. developing a lexicon. We find that the use of a lexicon improves the quality of the tagger at any stage of development of either resource, and that for fixed performance levels the availability of the full lexicon consistently reduces the need for supervised data by at least one half.

Introduction

Over recent years, numerous systems for automatic part-of-speech (POS) tagging have been proposed for a large variety of languages. Among the best performing systems are those based on supervised machine learning techniques (see [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF] for an overview). For some languages like English and other European languages, these systems have reached performance that comes close to human levels. Interestingly, the majority of these systems have been built without resorting to any external lexical information sources; they instead rely on a dictionary that is based on the training corpus (see however [START_REF] Hajič | Morphological Tagging: Data vs. Dictionaries[END_REF]). This raises the question of whether we can still improve tagging performance by exploiting this type of resource. Arguably, a potential advantage of using an external dictionary is in a better handling of unknown words (i.e., words that are not present in the training corpus, but that may be present Alpage, INRIA Paris-Rocquencourt & Université Paris 7 Domaine de Voluceau -Rocquencourt, BP 105 78153 Le Chesnay Cedex, France {pascal.denis,benoit.sagot}@inria.fr in the external dictionary). A subsequent question is how to best integrate the information from a lexical resource into a probabilistic POS tagger. In this paper, we consider two distinct scenarios: (i) using the external dictionary as constraints that restrict the set of possible tags that the tagger can choose from, and (ii) incorporating the dictionary tags as features in a probabilistic POS tagging model. Another interesting question is that of the relative impact of training corpora and of lexicons of various sizes. This issue is crucial to the development of POS taggers for resource-scarce languages for which it is important to determine the best trade-off between annotating data and constructing dictionaries.

This paper addresses these questions through various tagging experiments carried out on French, based on our new tagging system called MElt (Maximum-Entropy Lexicon-enriched Tagger). An obvious motivation for working on this language is the availability of a training corpus (namely, the French Treebank [START_REF] Abeillé | Building a treebank for French[END_REF]) and a large-scale lexical resource (namely, Lefff [START_REF] Sagot | The Lefff 2 syntactic lexicon for French: architecture, acquisition, use[END_REF]). Additional motivation comes from the fact that there has been comparatively little work in probabilistic POS tagging in this language. An important side contribution of our paper is the development of a state-of-the-art, freely distributed POS tagger for French. 1Specifically, we here adopt Maximum Entropy Markov Models (MEMMs), an extension of MaxEnt models for sequence labeling. MEMMs remain among the best performing tagging systems for English and they are particularly easy to build and fast to train.

This paper is organized as follows. Section 2 describes the datasets and the lexical resources that were used. Section 3 presents a baseline MEMM tagger for French that is inspired by previous work, in particular [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF] and [START_REF] Toutanova | Enriching the knowledge sources used in a maximum entropy part-ofspeech tagger[END_REF], that already outperforms TreeTagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF] retrained on the same data. In Section 4, we show that the performance of our MEMM tagger can be further improved by incorporating features extracted from a large-scale lexicon, reaching a 97.75% accuracy, which compares favorably with the best results obtained for English with a similar tagset. In order to assess the robustness of our approach, we apply it to various languages and of different sizes. Finally, Section 6 evaluates the relative impact on accuracy of the training data and the lexicon during tagger development by varying their respective sizes. These last two sections build on two previous conference publications, [START_REF] Denis | Exploitation d'une ressource lexicale pour la construction d'un étiqueteur morphosyntaxique état-de-l'art du franc ¸ais[END_REF] and [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art pos tagging with less human effort[END_REF], respectively.

Resources and tagset

Corpus

The morphosyntactically annotated corpus we used is a variant of the French TreeBank or FTB, [START_REF] Abeillé | Building a treebank for French[END_REF]. It differs from the original FTB in so far that all compounds that do not correspond to a syntactically regular sequence of categories have been merged into unique tokens and assigned a category corresponding to their spanning node; other compounds have been left as sequences of several tokens (Candito, p.c.). The resulting corpus has 350, 931 tokens in 12, 351 sentences.

In the original FTB, words are split into 13 main categories, themselves divided into 34 subcategories. The version of the treebank we used was obtained by converting subcategories into a tagset consisting of 28 tags, with a granularity that is intermediate between categories and subcategories. Basically, these tags enhance main categories with information on the mood of verbs and a few other lexical features. This expanded tagset has been Cette/DET mesure/NC ,/PONCT qui/PROREL pourrait/V être/VINF appliquée/VPP dans/P les/DET prochaines/ADJ semaines/NC ,/PONCT permettrait/V d'/P économiser/VINF quelque/DET 4/ADJ milliards/NC de/P francs/NC ./PONCT Fig. 1 Sample data from FTB in Brown format shown to give the best statistical parsing results for French [START_REF] Crabbé | Expériences d'analyses syntaxique statistique du franc ¸ais[END_REF]. 2 A sample tagged sentence from the FTB is given in Figure 1.

As in [START_REF] Candito | On statistical parsing of French with supervised and semisupervised strategies[END_REF], the FTB is divided into

Lexicon

One of the goals of this work is to study the impact of using an external dictionary for training a tagger, in addition to the training corpus itself. We used the morphosyntactic information included in the large-coverage morphological and syntactic lexicon Lefff , developed in the Alexina framework [START_REF] Sagot | The Lefff , a freely available, accurate and large-coverage lexicon for French[END_REF]. 3Although Lefff contains both morphological and syntactic information for each entry (including sub-categorization frames, in particular for verbs), we extracted only the morphosyntactic information. We converted categories and morphological tags into the same tagset used in the training corpus, hence building a large-coverage morphosyntactic lexicon containing 507, 362 distinct entries of the form (form, tag, lemma), corresponding to 502, 223 distinct entries of the form (form, tag). If grouping all verbal tags into a single "category" while considering all tags as "categories", these entries correspond to 117, 397 (lemma, category) pairs (the relevance of these pairs will appear in Section 6).

Baseline MEMM tagger

This section presents our baseline MaxEnt-based French POS tagger, MElt 0 fr . This tagger is largely inspired by [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF] and [START_REF] Toutanova | Enriching the knowledge sources used in a maximum entropy part-ofspeech tagger[END_REF], both in terms of the model and the features being used. To date, MEMM taggers are still among the best performing taggers developed for English. 4 An important appeal of MaxEnt models is that they allow for the combination of very diverse, potentially overlapping features without assuming independence between the predictors. These models have also the advantage of being very fast to train. 5

Description of the task

Given a tagset T and a string of words w n 1 , we define the task of tagging as the process of assigning the maximum likelihood tag sequence tn 1 ∈ T n to w n 1 . Following [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF], we can approximate the conditional probability P (t n 1 |w n 1 ) so that:

tn 1 = arg max t n 1 ∈T n P (t n 1 |w n 1 ) ≈ arg max t n 1 ∈T n n i=1 P (t i |h i ) (1)
where t i is the tag for word w i , and h i is the "history" (or context) for (w i , t i ), which comprises the preceding tags t i-1 i and the word sequence w n i .

Model and features

In a MaxEnt model, the parameters of an exponential model of the following form are estimated:

P (t i |h i ) = 1 Z(h) • exp m i=j λ j f j (h i , t i ) (2)
f m 1 are feature functions defined over tag t i and history

h i (with f (h i , t i ) ∈ {0, 1}), λ m 1
are the parameters associated with f m 1 , and Z(h) is a normalization term over the different tags. In this type of model, the choice of the parameters is subject to constraints that force the model expectations of the features to be equal to their empirical expectations over the training data [START_REF] Berger | A maximum entropy approach to natural language processing[END_REF]. In our experiments, the parameters were estimated using the Limited Memory Variable Metric Algorithm [START_REF] Malouf | A comparison of algorithms for maximum entropy parameter estimation[END_REF] implemented in the Megam package. 6The feature templates we used for designing our French tagging model is a superset of the features used by [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF] and [START_REF] Toutanova | Enriching the knowledge sources used in a maximum entropy part-ofspeech tagger[END_REF] for English (these were largely language independent). These features fall into two main categories. A first set of features try to capture the lexical form of the word being tagged: these include the actual word string for the current word w i , prefixes and suffixes (of character length 4 and less), as well as binary features testing whether w i contains special characters like numbers, hyphens, and uppercase letters. A second set of features directly model the context of the current word and tag: these include the previous tag, the concatenation of the two previous tags, as well as the surrounding word forms in a window of 5 tokens.

The detailed list of feature templates we used in this baseline tagger is shown in Table 2.7

Internal lexical features

t i = uni X, if lefff(w i ) = {X} & t i = T t i = X, ∀X ∈ lefff(w i ) if |lefff(w i )| > 1 & t i = T t i = lefff(w i ) if |lefff(w i )| > 1 & t i = T t i = unk, if lefff(w i ) = ∅ & t i = T External lexical features t i+j = lefff(w i+1 ), j ∈ {-2, -1, 1, 2} & t i = T t i+j t i+k = lefff(w i+j ) lefff(w i+k ), (j, k) ∈ {(-2, -1), (1, 2), (-1, 1)} & t i = T Table 2 Baseline model features
An important difference with [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF] in terms of feature design is that we did not restrict the application of the prefix/suffix features to words that are rare in the training data. In our model, these features always get triggered, even for frequent words. We found that the permanent inclusion of these features led to better performance during development, which can probably be explained by the fact that these features get better statistics and are extremely useful for unknown words. These features are also probably more discriminative in French than in English, since it is morphologically richer. Another difference to previous work regards smoothing. [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF] and [START_REF] Toutanova | Enriching the knowledge sources used in a maximum entropy part-ofspeech tagger[END_REF] use a feature count cutoff of 10 to avoid unreliable statistics for rare features. We did not use cutoffs but instead use a regularization Gaussian prior on the weights 8 , which is arguably a more principled smoothing technique. 9

Testing and Performance

The test procedure relies on a beam search to find the most probable tag sequence for a given sentence. That is, each sentence is decoded from left to right and we maintain for each word w i the n highest probability tag sequence candidates up to w i . For our experiments, we used a beam size of 3. 10 In addition, the test procedure utilizes a tag dictionary which lists for a given word the tags associated with this word in the training data. This drastically restricts the allowable labels that the tagger can choose from for a given word, in principle leading to fewer tagging errors and reduced tagging time.

The maximum entropy tagger described above, MElt 0 fr , was compared against two other baseline taggers, namely: UNIGRAM and TreeTagger. UNIGRAM works as follows: for a word seen in the training corpus, this tagger uses the most frequent tag associated with this word in the corpus; for unknown words, it uses the most frequent tag in the corpus (in this case, NC). TreeTagger is a statistical, decision tree-based POS tagger [START_REF] Schmid | Probabilistic part-of-speech tagging using decision trees[END_REF]. 11 The version used for this comparison was retrained on the FTB training corpus. The performance results of the three taggers are given in Table 3; scores are reported in terms of accuracy over both the entire test set and the words that were not seen during training.

As shown in Table 3, MElt 0 fr achieves accuracy scores of 97% overall and 86.1% on unknown words. 12 Our baseline tagger significantly outperforms the retrained version of TreeTagger, with an improvement of over 10% on unknown words. 13 There are several possible explanations for such a discrepancy in handling unknown words. The first one is that MaxEnt parameter estimation is less prone to data fragmentation for sparse features than Decision Tree parameter estimation due to the fact that it does not partition the training sample. A second related explanation is that TreeTagger simply misses some of the generalizations regarding lexical features due to the fact that it only includes suffixes and this only for unknown words.

Lexicon-enriched MEMM tagger

For trying to further improve MElt 0 fr , we investigate in this Section the impact of coupling it with an external lexical resource, and compare two ways of integrating this new information: as constraints vs. as features.

Integrating lexical information in the tagger

The most natural way to make use of the extra knowledge supplied by a lexicon is to represent it as "filtering" constraints: that is, the lexicon is used as an additional tag dictionary guiding the POS tagger, in addition to the lexicon extracted from the training corpus. Under this scenario, the tagger is forced for a given word w to assign one of the tags associated with w in the full tag dictionary: the set of allowed tags for w is the union of the sets of its tags in the corpus and in Lefff . This approach is similar to that of [START_REF] Hajič | Morphological Tagging: Data vs. Dictionaries[END_REF], who applied it to highly inflected languages, and in particular to Czech.

In a learning-based tagging approach, there is another possibility to accommodate the extra information provided by Lefff : we can directly incorporate the tags associated by Lefff to each word in the form of features. Specifically, for each word, we posit a new lexical feature for each of its possible tags according to the Lefff , as well as a feature that represents the disjunction of all Lefff tags (provided there is more than one). Similarly, we can also use the Lefff to provide additional contextual features: that is, we can include Lefff tags for all the words in a window of 5 tokens centered on the current token. Table 4 summarizes these new feature templates.

Integrating the lexical information in this way has a number of potential advantages. First, features are by definition more robust to noise (in this case, to potential errors in the lexicon or simply mismatches between the corpus annotations and the lexicon categories). Furthermore, some of the above features directly model the context, while the filtering constraints are entirely non contextual. corpus (all words taken into account). Words that are unknown to both the corpus and Lefff are assigned NC. The second tagger, TreeTagger Lefff is a retrained version of TreeTagger to which we provide Lefff as an external dictionary. Finally, we also compare our tagger to F-BKY, an instantiation of the Berkeley lexicalized parser adapted for French by [START_REF] Crabbé | Expériences d'analyses syntaxique statistique du franc ¸ais[END_REF] and used as a POS tagger. The performance results for these taggers are given in Table 5.

Lexical features Lefff tag for w

i = X & t i = T Lefff tags for w i = X 0 . . . Xn & t i = T Contextual features Lefff tag for w i+j = X, j ∈ {-2, -1, 1, 2} & t i = T Lefff tags for w i+j = X 0 . . . Xn, j ∈ {-2, -1, 1, 2} & t i = T

Tagger

Overall accuracy (%) Unknown words accuracy (%) The best tagger is MElt f fr , with accuracy scores of 97.75% overall and 91.36% for unknown words. This represents significant improvements of .75% and 5.26% over MElt 0 fr , respectively. 14 By contrast, MElt c fr achieves a rather limited (and statistically insignificant) performance gain of .1% overall but a 2.9% improvement on unknown words. Our explanation for these improvements is that the Lefff -based features reduce data sparseness and provide useful information on the right context: first, fewer errors on unknown words (a direct result of the use of a morphosyntactic lexicon) necessarily leads to fewer erroneous contexts for other words, and therefore to better tagging; second, the possible categories of tokens that are on the right of the current tokens are valuable pieces of information, and they are available only from the lexicon. The lower result of MElt c fr can probably be explained by two differences: it does not benefit from this additional information about the right context, and it uses Lefff information as hard constraints, not as (soft) features.

Accuracy scores put MElt f fr above all the other taggers we have tested, including the parser-based F-BKY, by a significant margin. To our knowledge, these scores are the best scores reported for French POS tagging. 15 Other taggers have been proposed for French, some of which have been evaluated during the GRACE evaluation campaign. 16 Although a direct comparison is difficult, given the differences in terms of reference corpus and tagsets, it is worth mentioning that the best scores during this campaign, approximately 96%, have been obtained by parser-based taggers [START_REF] Adda | Métrique et premiers résultats de l'évaluation grace des étiqueteurs morphosyntaxiques pour le franc ¸ais[END_REF]. Finally, [START_REF] Nasr | Couplage d'un étiqueteur morpho-syntaxique et d'un analyseur partiel représentés sous la forme d'automates finis pondérés[END_REF] report a 97.82% accuracy on the FTB, but their tagger/chunker does not take unknown words into account.

Error analysis

In order to understand whether the 97.75% accuracy of MElt f fr could still be improved, we decided to examine manually its first 200 errors on FTB-DEV, and classify them according to an adequate typology of errors. The resulting typology and the corresponding figures are given in Table 6.

These results show that the 97.75% score can still be improved. Indeed, standard named entity recognition techniques could help solve most errors related to named entities, i.e., more than one out of four errors. Moreover, simple regular patterns could allow for replacing automatically all numbers by one or several placeholder(s) both in the training and evaluation data. Indeed, preserving numbers as such inevitably leads to a sparse data problem, which prevents the training algorithm from modeling the complex task of tagging numbers -they can be determiners, nouns, adjectives or pronouns. Appropriate placeholders should significantly help the training algorithm and improve the results. Finally, no less than 13.5% of MElt f fr 's apparent errors are in fact related to FTB-DEV's annotation, because of errors (9%) or unclear situations, for which both the gold tag and MElt f fr 's tag seem valid. Given these facts, we consider it feasible to improve MElt f fr from 97.75% to 98.5% in the future.

Impact of various sets of Lefff -based lexical features

In order to understand better the relative impact on MElt f fr 's model of various types of information extracted from the Lefff , we have run a series of ablation experiments on the set of features described in 4. Specifically, we have evaluated the 8 possible configurations consisting in including (or not) internal lexical features (INT), external lexical features defined on the left context (LEFT), and external lexical features defined on the right context (RIGHT). The results of these experiments performed on the development corpus FTB-DEV are given in Table 7. Note that the experiments named here ∅ and INT+LEFT+RIGHT, correspond respectively to the variants MElt 0 fr and MElt f fr of our system. These results indicate that it is the combination of internal and right external lexical features that brings the most information to the tagger. Indeed, the subset INT+RIGHT yields the best results after MElt f fr itself, both on all words and on unknown words only. These two subsets of lexical features are complementary: INT features improve the lexical coverage of the tagger (some unknown words, i.e., unseen in the training corpus, are covered by the lexicon), whereas RIGHT features provide important information about the right context that MElt 0 fr 's features only model in a rough way.

Lefff features

Varying tagsets and languages

In order to validate the robustness of our approach, we have trained two series of taggers with the same architecture as MElt f fr : -several other taggers trained on the same corpus and the same lexicon, but with tagsets of different granularities; indeed, different NLP tasks may require tagging with a different level of detail, including only major categories (tagset small, 15 tags), standard categories (standard taget, 28 tags) and detailed tags that include morphological features such as gender, number, person, tense, and others (tagset large, 239 tags); -two other taggers trained on corpora and lexicon for other languages, namely English and Spanish; for English, we used the Penn TreeBank [START_REF] Marcus | Building a large annotated corpus of English: The Penn Treebank[END_REF] as a corpus (sections 2 to 21 for training and section 23 for tagging, as usual in the parsing community; 46 tags) and the lexicon EnLex developed in the same framework as the Lefff , Alexina; for Spanish, we used the Ancora corpus [START_REF] Taulé | Ancora: Multilevel Annotated Corpora for Catalan and Spanish[END_REF] (the first 60,000 sentences as a training corpus, the last 3,328 sentences as a test corpus; 16 tags) and the Alexina lexicon for Spanish, the Leff e [START_REF] Molinero | A morphological and syntactic wide-coverage lexicon for Spanish: The Leff e[END_REF]. Results are shown in Table 8. Note that the last three experiments (French large, English, Spanish) rely on lexicons that do not use the same tagset as the corpus. 17 Indeed, since lexical information extracted from the lexicon is used in the form of features, there is no particular need for having the same tags in the lexicon as in the corpus. These results are satisfying not only for MElt f fr itself. For example, the state-of-the-art for English on the same corpus (not necessarily split in the same way, though) is approximately 97.4% [START_REF] Spoustová | Semi-supervised training for the averaged perceptron POS tagger[END_REF], a figure that is reached by combining several taggers.

Varying training corpus and lexicon sizes

Motivations and experimental setup

The results achieved by MElt f fr have been made possible by the (relatively) large size of the corpus and the broad coverage of the lexicon. However, such resources are not always available for a given language, in particular for so-called under-resourced languages. Moreover, the significant improvement observed by using Lefff shows that the information contained in a morphosyntactic lexicon is worth using. The question arises whether this lexical information is able to compensate for the lack of a large training corpus. Symmetrically, it is unclear how various lexicon sizes impact the quality of the results.

Therefore, we performed a series of experiments by training MElt f fr on various subcorpora and sub-lexicons. Extracting sub-corpora from FTB-TRAIN is simple: the first s sentences constitute a reasonable corpus of size s. However, extracting sub-lexicons from the Lefff is less trivial. We decided to extract increasingly large sub-lexicons in a way that approximately simulates the development of a morphosyntactic lexicon. To achieve this goal, we used the MElt f fr tagger described in the previous section to tag a large raw corpus. 18 We then lemmatized the corpus by assigning to each token the list of all of its possible lemmas that exhibit a category consistent with the annotation. Finally, we ranked all resulting (lemma, category) pairs w.r.t. frequency in the corpus. Extracting a sub-lexicon of size n then consists in extracting all (form,tag,lemma) entries whose corresponding (lemma, category) pair is among the l best ranked ones.

We reproduced the same experiments as those described in Section 4, but training MElt f fr on various sub-corpora and various sub-lexicons. We used 9 different lexicon sizes and 8 different corpus sizes, summed up in Table 9. For each resulting tagger, we evaluated on FTB-TEST the overall accuracy and the accuracy on unknown words.

Results and discussion

Before comparing the respective relevance of lexicon and corpus manual development for optimizing the tagger performance, we need to be able to quantitatively compare their development costs, i.e., times.

In [START_REF] Marcus | Building a large annotated corpus of English: The Penn Treebank[END_REF], the authors report a POS annotation speed that "exceeds 3, 000 words per hour" during the development of the Penn TreeBank. This speed is reached after a 1 month period (with 15 annotation hours per week, i.e., approximately 60 hours) during which the POS tagger used for pre-annotation was still improving. The authors also report on a manual tagging experiment (without automatic pre-annotation); they observed an annotation speed that is around 1, 300 words per hour. Therefore, it is probably safe to assume that, on average, the creation of a manually validated training corpus starts at a speed that is around 1,000 words (30 sentences) per hour, and increases up to 3, 000 words (100 sentences) per hour once the corpus has reached, say, 5, 000 sentences.

For lexicon development, techniques such as those described in [START_REF] Sagot | Automatic acquisition of a Slovak lexicon from a raw corpus[END_REF] allow for a fast validation of automatically proposed hypothetical lemmas. Manual intervention is then limited to validation steps that take around 2 to 3 seconds per lemma, i.e., about 1, 500 lemmas per hour.

Figure 2 compares contour lines 19 for two functions of corpus and lexicon sizes: tagger accuracy and development time. 20 These graphs show different things:

-during the first steps of development (less than 3 hours of manual work), the distribution of the manual work between lexicon and corpus development has no significant impact on overall tagging accuracy, but accuracy on unknown words is better when focusing more or equally on the lexicon than on the corpus; -in later stages of development, the optimal approach is to develop both the lexicon and the corpus, and this is true for both overall and unknown words tagging accuracy; however, it is by far better to concentrate only on corpus than only on lexicon development; -using a morphological lexicon drastically improves the tagging accuracy on unknown words, whatever the development stage; 21 -for fixed performance levels, the availability of the full lexicon consistently reduces the need for training data by at least one half (and up to two thirds). These results demonstrate the relevance of developing and using a morphosyntactic lexicon for improving tagging accuracy both in the early stages of development and for long-term optimization.

Conclusions and perspectives

We have introduced a new MaxEnt-based tagger, MElt, that we trained on the FTB for building a tagger for French. We show that this baseline, named MElt 0 fr , can be significantly improved by coupling it with the French morphosyntactic lexicon Lefff . The resulting tagger, MElt f fr , reaches a 97.75% accuracy that are, to our knowledge, the best figures reported for French tagging, including parsing-based taggers. More precisely, the addition of lexiconbased features yield error reductions of 25% overall and of 38% for unknown words (corresponding to accuracy improvements of .75% and 5.26%, respectively) compared to the baseline tagger.

We also showed that the use of a lexicon improves the quality of the tagger at any stage of lexicon and training corpus development. Moreover, we approximately estimated development times for both resources, and show that the best way to optimize human work for tagger development is to work on the development of both an annotated corpus and a morphosyntactic lexicon.

In future work, we plan on trying and demonstrating this result in practice, by developing such resources and the corresponding MElt f fr tagger for an under-resourced language. We also intend to study the influence of the tagset, in particular by training taggers based on larger tagsets. This work should try and understand how to benefit as much as possible from the internal structure of tags in such tagsets (gender, number, etc.).

Fig. 2

 2 Fig. 2 Contour lines for two functions of corpus and lexicon sizes: tagger accuracy and development time. In (a), the tagger accuracy is measured overall, whereas in (b) it is restricted to unknown words

Table 1

 1 3 sections: training (80%), development (10%) and test (10%). The dataset sizes are presented in Table 1 together with the number of unknown words. Data sets

	Data Set	# of sent.	# of tokens	# of unk. tokens
	FTB-TRAIN	9, 881	278, 083
	FTB-DEV	1, 235	36, 508	1, 892 (5.2%)
	FTB-TEST	1, 235	36, 340	1, 774 (4.9%)

Table 3

 3 Baseline tagger performance

	Tagger	Overall Accuracy	Unknown Word Accuracy
	UNIGRAM	91.90	24.50
	TreeTagger	96.12	75.77
	MElt 0 fr	97.00	86.10

Table 4

 4 Lexicon-based features 4.2 Comparative evaluation We compared the performance of the Lefff -constraints based tagger MElt c fr and Lefff -features based tagger MElt f fr to other lexicon-enriched taggers. The first of these taggers, UNIGRAM Lefff , like UNIGRAM, is a unigram model based on the training corpus, but it uses Lefff for labeling unknown words: among the possible Lefff tag for a word, this model chooses the tag that is most frequent in the training

Table 5

 5 Lexicon-based taggers performance

	UNIGRAM Lefff	93.40	55.00
	TreeTagger Lefff	96.55	82.14
	F-BKY	97.30	82.90
	MElt 0 fr MElt c fr MElt f fr	97.00 97.25 97.75	86.10 86.47 91.36

Table 6

 6 Manual error analysis of the 200 first errors of MElt f fr on the development corpus

	Error type		Frequency
		Adjective vs. past participle	5.5%
	Standard errors	Errors on de, du, des	4.0%
		Other errors	34.0%
	Errors on numbers		15.5%
	Errors related to named entities		27.5%
		Error in FTB-DEV	8.5%
	MElt f fr 's result seems correct	Unclear cases (both tags seem valid) Truncated text in FTB-DEV	4.5% 0.5%

Table 7

 7 Comparative accuracy of MElt f fr using various subsets of lexical features on FTB-DEV

		Overall accuracy (%)	Unknown words accuracy (%)
	∅ (MElt 0 fr ) INT	96.54 97.04	83.95 91.4
	LEFT	96.38	85.36
	RIGHT	96.39	86.48
	INT+LEFT	96.92	91.28
	INT+RIGHT	97.30	92.01
	LEFT+RIGHT	96.57	86.93
	INT+LEFT+RIGHT (MElt f fr )	97.41	92.35

Table 8

 8 Applying the MElt system on other tagsets and languages (see text for information about test corpora)

	Language	Training Corpus	Tagset Size	Overall Acc. (%)
	French	FTB-TRAIN (small tagset)	15	97.69%
	French (MElt f fr ) French	FTB-TRAIN (standard tagset) FTB-TRAIN (large tagset)	28 239	97.25% 93.73%
	English	Penn TreeBank (sec. 2-23)	46	97.03%
	Spanish	Ancora (60,000 first sentences)	16	97.73%

Table 9

 9 Varying training corpus and lexicon sizes: experimental setups

	Lexicon size (lemmas)	0; 500; 1, 000; 2, 000; 5, 000;
		10, 000; 20, 000; 50, 000; 110, 000
	Corpus size (sentences)	50; 100; 200; 500; 1, 000; 2, 000;
		5, 000; 9, 881

The MElt tagger is freely available from http://lingwb.gforge.inria.fr/. Results reported in this paper correspond to release MElt 1.0.

This tagset is known as TREEBANK+ in[START_REF] Crabbé | Expériences d'analyses syntaxique statistique du franc ¸ais[END_REF], and since then as CC[START_REF] Candito | On statistical parsing of French with supervised and semisupervised strategies[END_REF].

The Lefff is freely distributed under the LGPL-LR license at http://alexina.gforge.inria. fr/

[START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF] and[START_REF] Toutanova | Enriching the knowledge sources used in a maximum entropy part-ofspeech tagger[END_REF] report accuracy scores of 96.43% and 96.86% on section 23-24 of the Penn Treebank, respectively.

Arguably better suited for sequential problems, Conditional Random Fields (CRF)[START_REF] Lafferty | Conditional random fields: Probabilistic models for segmenting and labeling sequence data[END_REF] are considerably slower to train.

Available from http://www.cs.utah.edu/ ˜hal/megam/.

Recall that features in MaxEnt are functions ranging on both contexts and classes. A concrete example of one of our features is given below:f 100 (h, t) = 1 if w i = "le" & t = DET 0 otherwise(3)

Specifically, we used a prior with precision (i.e., inverse variance) of 1 (which is the default in Megam); other values were tested during development but did not yield improvements.

Informally, the effect of this kind of regularization is to penalize artificially large weights by forcing the weights to be distributed according to a Gaussian distribution with mean zero.

We tried larger values (i.e., 5, 10, 15, 20) during development, but none of these led to significant improvements.

Available at http://www.ims.uni-stuttgart.de/projekte/corplex/TreeTagger/.

The accuracy results of MElt 0 fr on FTB-DEV are: 96.7% overall and 86.2% on unknown words.

Chi-square statistical significance tests were applied to changes in accuracy, with p set to 0.01 unless otherwise stated.

The accuracy results of MElt f fr on FTB-DEV are: 97.23% overall and 90.01% on unknown words.

An adaptation to French of the Morfette POS-tagger[START_REF] Chrupała | Learning morphology with morfette[END_REF] using the FTB and the Lefff has been realized by G. Chrupała and D. Seddah (p.c.). Their accuracy results are similar to ours, although slightly lower (on the same data sets, Henestroza and Candito have obtained a 97.68% accuracy). On other variants of the FTB, Chrupała and Seddah report 97.9% (p.c.). However, these figures do not correspond exactly to the same experimental setup, as Morfette extracts and uses in its models an additional source of information, namely lemmas.

http://www.limsi.fr/TLP/grace/

MElt has also been used for training POS taggers for Persian[START_REF] Sagot | A new morphological lexicon and a POS tagger for the Persian Language[END_REF] and Kurmanji Kurdish[START_REF] Walther | Fast Development of Basic NLP Tools: Towards a Lexicon and a POS Tagger for Kurmanji Kurdish[END_REF] (see below) based on noisy corpora and medium-size lexicons, with promising results.

We used a corpus of 20 million words extracted from the L'Est Républicain journalistic corpus, freely available at the web site of the CNRTL (http://www.cnrtl.fr/corpus/estrepublicain/).

As computed by the bspline mode of gnuplot's contour lines generation algorithm.

The development times per sentence and per lexical entry mentioned in the previous paragraphs lead to the following formula for the total development time t(s, l) (expressed in seconds), in which s is the number of sentences, l the number of lexical entries: t(s, l) = 36s + 8400 • log(s/100 + 1) + 2.4 • l.

Performing POS tagging with a morphological lexicon but without any training corpus is a significantly different task, addressed by an increasing literature [START_REF] Merialdo | Tagging English text with a probabilistic model[END_REF][START_REF] Smith | Contrastive estimation: Training log-linear models on unlabeled data[END_REF][START_REF] Ravi | Minimized models for unsupervised part-of-speech tagging[END_REF]. In that regard, MElt has been used in a simple experiment on Kurmanji Kurdish, a resource-scarse Iranian language [START_REF] Walther | Fast Development of Basic NLP Tools: Towards a Lexicon and a POS Tagger for Kurmanji Kurdish[END_REF]: in that paper, the authors project the morphological lexicon they have built for that language, disambiguate the resulting ambiguous annotation in three different ways, merge these annotations for producing a (noisy) training corpus, and train a MElt tagger based on this corpus and their lexicon. Despite the simplicity of the three disambiguation techniques, the authors report a 85.7% accuracy on a tiny gold standard using a 36-tag tagset.