Hyun-Gue Huh
email: hhuh@univ-mlv.fr

Éric Laporte
email: eric.laporte@univ-mlv.fr

A resource-based Korean morphological annotation system

We describe a resource-based method of morphological annotation of written Korean text. Korean is an agglutinative language. The output of our system is a graph of morphemes annotated with accurate linguistic information. The language resources used by the system can be easily updated, which allows users to control the evolution of the performances of the system. We show that morphological annotation of Korean text can be performed directly with a lexicon of words and without morphological rules.

Introduction

In the first phase of the processing of a written text, words are annotated with basic information, such as part of speech (POS). Two of the criteria of quality of a system performing this task are particularly relevant: the output of this process must be accurate and informative; the language resources used by the system must be able to undergo an evolution in a controlled way. The objective of the work reported here was to explore a method likely to enhance the performances of state-of-the-art systems of Korean morphological annotation in both regards. We decided to make language resources the central point of the problem.

Korean is one of the most studied agglutinative languages in the world. Korean words (eojeol) are delimited by spaces or other symbols, but a word usually consists of an undelimited concatenation of several morphemes: one or several stems, followed by zero, one or several functional morphemes. We will call stems all lexical morphemes, as opposed to functional or grammatical ones. The surface form of a morpheme occurring in a text may depend on neighbouring morphemes. Thus, it may differ from its base form or lexical form. These variations are termed as phonotactic, and the surface variants are called allomorphs. The objective of morphological annotation is to identify morphemes and assign relevant information to them.

The basic units of the Korean alphabet (hangul) are graphical syllables. These syllables can be decomposed over the Korean alphabet of simple and complex letters (jamo): each "letter" is either a cluster of 1 or 2 consonants, or a sequence of 1, 2 or 3 vowels. In addition, Chinese ideograms are sometimes employed also to write Korean stems.

It has been claimed that morphological annotation of Korean text could only be performed by a morphological analysis module accessing a lexicon of morphemes and using a set of rules. We show that it can also be performed directly with a lexicon of words. We describe an implemented system of morphological annotation that uses an actual lexicon of words. Our approach resorts to classical techniques of lexicon compression and lookup, but the application to an agglutinative language involved implementing new software components, which have received an open-source status.

In Section 2, we outline the state-of-the-art approach to Korean morphological annotation. Section 3 describes the alphabets and tag set used by our system. In Section 4, we explain our model of morpheme combinatorics. Section 5 reports the construction and use of the word lexicon. A conclusion and perspectives are presented in Section 6.

State of the art

Several morphological annotators of Korean text are available. The Hangul Analysis Module (HAM1 ) is one of the best Korean morphological analysers. Other fairly representative examples are described in [START_REF] Shin | A HMM Part-of-Speech Tagger for Korean with Wordphrasal Relations[END_REF][START_REF] Park | Machine Aided Error-Correction Environment for Korean Morphological Analysis and Part-of-Speech Tagging[END_REF] and in (Lee et al., 1997a;[START_REF] Cha | Generalized Unknown Morpheme Guessing for Hybrid POS Tagging in Korean[END_REF][START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF]. The output for each morpheme is presented in two parts: the morpheme itself, and a grammatical tag. Morphemes are usually presented in their base form if they are stems, and in they surface form if they are functional morphemes. Tags are represented by symbols; they give the POS of stems, and grammatical information about functional morphemes. In output, 95% to 97% of morpheme/tag pairs are considered correct.

Morphological annotation of Korean text is usually performed in two steps [START_REF] Sproat | Morphology and Computation[END_REF]. In the first step, morpheme segmentation is performed with the aid of a lexicon of morphemes. This generates all possible ways of segmenting the input word. The second step makes a selection among the segmentations obtained and among the tags attached to the morphemes. The second step involves frequency-based learning from a tagged corpus with statistical models such as hidden Markov models, and sometimes also with error-driven learning of symbolic transformation rules [START_REF] Brill | Transformation-based error-driven learning and natural language processing: a case study in part-of-speech tagging[END_REF]Lee et al., 1997a;[START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF]. Morphemes not found in the lexicon undergo a special treatment that guesses at their properties. A recent variant of this approach (Han and Palmer, 2005) swaps the main two steps: first, a sequence of tags is assigned to each word on the basis of a statistical model; then, morphological segmentation is performed with a lexicon of morphemes. The other approaches are less popular among searchers and language engineering companies. Some systems are based on two-level models, such as [START_REF] Kim | A Two-Level Morphological Analysis of Korean[END_REF]) and the Klex system of Han Na-rae2 . [START_REF] Choi | Implantation de dictionnaires électroniques du coréen par automates finis[END_REF] combines a lexicon of stems with a lexicon of endings with the aid of a connectivity table.

The delimitation of morphemes is provided, but some morpheme boundaries are usually modified so that they coincide with syllable boundaries. For example, if two suffixes make up a single syllable, like -셨:-syôss-which is a contraction of -으시:-eusi-(honorification towards sentence subject) and -었:-ôss-(past), they are usually considered as one morpheme. Such simplifications make it possible to encode morphemes on the Korean syllable-based alphabet, and are compatible with syllable-based models [START_REF] Kang | Syllable-Based Model For The Korean Morphology[END_REF]. However, they are an approximation.

We opted for the resource-based approach to obtain more accurate and more informative output.

The language resources used in annotators are corpora, rules and lexicons.

Corpus-based systems have an inherent lack of flexibility. A morphological annotator is not static infrastructure, it has to evolve with time. Due to the evolution of language across time, and especially of technical language, regular updates are necessary; a new application may involve the selection of a domain-specific vocabulary. The flexibility of a resource can be defined as the ability to control its evolution. In order to adapt a corpus-based system, one feeds a new corpus into the training process, since the operation of the system is dependent on the nature of the training corpus. A training process with a tagged corpus gives much better performance than unsupervised training [START_REF] Merialdo | Tagging English text with a probabilistic model[END_REF]. The extension of a system to input texts of new types or of a new period of time involves the costly task of tagging a corpus of new texts. Another type of evolution of a corpus-based system, a refinement of the tag set, such as the addition of new features, involves a re-tagging of existing tagged corpora, a task which is seldom achieved.

The situation is different with rules or lexicons. The flexibility of a manually constructed and updated rule set or lexicon depends on its level of readability and of non-redundancy (see section 4).

In current practice, words are segmented by a morphological analysis module that accesses a lexicon of morphemes and uses a set of rules. It has been claimed that morphological annotation of Korean text could only be performed this way, because a lexicon of words would be too large (e.g. [START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF][START_REF] Han Ch | A Morphological Tagger for Korean: Statistical Tagging Combined with Corpus-based Morphological Rule Application[END_REF]. We show that it can be performed directly with a lexicon of words; this solution dispenses with rules, thus simplifying and speeding up morphological annotation. The evidence given by [START_REF] Han Ch | A Morphological Tagger for Korean: Statistical Tagging Combined with Corpus-based Morphological Rule Application[END_REF] in support of their claim is the fact that the number of different words in Korean is very large, which is undisputed. In fact, they implicitly assume that the lexicon would be obtained by sequentially generating all words and associated information. Such a naive procedure would surely be impractical. Our system constructs a lexicon of words without generating any list of words at any of the phases of its construction or maintenance.

In our design, all morphological rules are applied to all possible configurations during the compilation of the resources and stored in a lexicon of words, which is searched during text annotation. No morphological rules are applied then. The lexicon of words occupies less than 600 Kb, and specifies 138,000,000 surface forms of words obtained from 39,130 base-form stems. The size of the lexicon does not grow with the number of words, due to our adaptation to Korean of state-of-the-art technology for lexicon management [START_REF] Appel | The world's fastest Scrabble program[END_REF][START_REF] Silberztein | A new approach to tagging: the use of a large-coverage electronic dictionary[END_REF]Revuz, 1992;[START_REF] Lucchesi | Applications of finite automata representing large vocabularies[END_REF]. Our approach could even be adapted further to allow for constructing a lexicon with infinitely many words.

Alphabets and tag set

Our system uses three Unicode character sets: the Korean syllabic alphabet, the Korean alphabet of letters, and the Chinese ideograms. The lexicon of words is constructed from a set of language resources that has been manually constructed and is manually updated by Korean linguists [START_REF] Nam | Construction of Korean electronic lexical system DECO[END_REF]. In order to ensure that these resources are readable, they are encoded in the Korean syllabic alphabet. The only situation when this is impossible is when a morpheme boundary does not coincide with a syllable boundary. In that case, the morpheme boundary divides the syllable into two parts; one of these parts has no vowel and cannot be encoded in the syllabic alphabet: it is then encoded in the Korean alphabet of letters, which is another zone of the Unicode character set. This convention allows for an accurate delimitation of surface forms and base forms of all morphemes, including irregular ones. Chinese ideograms are provided in the information on Sino-Korean stems, which are sometimes spelled in Chinese ideograms in texts.

In the lexicon of words itself, words are encoded over the Korean alphabet of letters, for more efficient lexicon search. During text annotation, words in the text are converted into letters before the lexicon is searched.

Our tag set is more fine-grained than stateof-the-art: it comprises 173 tags for stems [to be compared to 18 in [START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF] and 14 in Han and Palmer ( 2005)], and 84 tags for functional morphemes [15 in [START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF] and in [START_REF] Han Ch | A Morphological Tagger for Korean: Statistical Tagging Combined with Corpus-based Morphological Rule Application[END_REF]]. Tags are more informative.

In addition, the tags are structured. They combine a general tag taken in a list of 16 general tags, and 0 to 4 features specifying subcategories. The list of general tags is displayed in This structure is in conformity with emerging international standards in representation of lexical tags [START_REF] Lee | Towards an international standard on feature struc-ture representation[END_REF]. Tag sets in previous Korean morphological analysers were unstructured or hierarchical [START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF], not feature-based.

Morphotactics and connectivity

The final part of some verbal and adjectival stems undergoes phonotactic variations when a suffix is appended to them. For example, the stem 크:keu-"big" becomes ㅋ:kbefore the suffix -었:-ôss-(past). In order to reduce the level of redundancy of manually updated resources, lexicons of base-form stems were con-structed. Each stem was assigned a structured tag. Stem allomorphs are generated from baseform stems with 71 transducers of the same type as those used to inflect words in inflectional languages [START_REF] Silberztein | Intex: an FST toolbox[END_REF]. The input part of the transducer specifies letters to remove or to add in order to obtain the allomorph from the base form. The output part specifies the tag and compatibility symbol (see below) to be assigned to the allomorph. These transducers are viewed and edited in graphical form with the opensource Unitex system 3 [START_REF] Paumier | Minimization of acyclic deterministic automata in linear time[END_REF].

The combination of a stem with a sequence of suffixes obeys a number of constraints. Checking these constraints is necessary to discard wrong segmentations. We distinguish two types of suffixes: derivational and inflectional.

Derivational suffixes are markers of verbalization, adjectivalization and adverbialization. They are appended by applying transducers of the same type as above. In our current version, 8 transducers append derivational suffixes. These transducers invoke 5 subgraphs, thus constituting recursive transition networks (RTN).

Inflectional suffixes comprise all other types of suffixes. A single (possibly derived) stem can be combined with up to 5,500 different sequences of inflectional suffixes. Compatibility between stems and inflectional suffixes is represented by a set of 59 compatibility symbols (CS). Each stem and stem allomorph is assigned a CS, which defines the set of suffix sequences that can be appended to it. The CSs take into account two types of constraints: grammatical and phonotactic constraints. CSs are comparable with adjacency symbols, except that they include the constraints between all the morphemes in a word, not only between adjacent morphemes. They convey more information than adjacency symbols, but they are less numerous: 59 to be compared to 300 [START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF]. The lexicon of stems assigns CSs to base stems. CSs are automatically assigned to stem allomorphs during the generation of allomorphs.

Connectivity between suffixes obeys phonotactic and grammatical constraints. Phonotactic constraints affect surface forms, whereas grammatical constraints affect base form/tag pairs. The standard model for representing both types of constraints is the finite-state model. For ex-3 http://www-igm.univ-mlv.fr/~unitex/manuelunitex.pdf ample, [START_REF] Lee | Syllable pattern-based unknown morpheme estimation for hybrid part-ofspeech tagging of Korean[END_REF] use a table that encodes connectivity between morphemes with the aid of morpheme tags and adjacency symbols. Such a table can be viewed as a finite-state automaton in which the states are the adjacency symbols and the transitions are labelled by the morpheme tags. In [START_REF] Kim | A Two-Level Morphological Analysis of Korean[END_REF] and in the Klex system of Han Na-rae, these constraints are represented in the two-level formalism, which is equivalent to regular expressions, which are in turn equivalent to finite-state automata. All these forms are computationally relevant, but they are little readable: the inclusion of a new item or the correction of an error is error-prone. Two-level rules have a very low level of redundancy, but they are complex to read because they combine a morphological part and a logical part (the symbols <=>, <=, =>).

In our system, connectivity constraints between suffixes are represented in finite-state transducers, i.e. finite-state automata with input/output labels. These transducers describe sequences of suffixes. Their input represents surface forms and their output represents base forms and tags. We introduced two innovations in order to enhance their readability. Firstly, they are edited and viewed graphically. Secondly, since most of the transducers are large and would not display conveniently on a single screen or page, they take the form of RTNs: transitions can be labelled by a call to a subtransducer instead of an input/output pair. The 59 CSs correspond to 59 transducers. Most of the sub-transducers that they call are shared, which reduces the level of redundancy of the system. The total number of simple graphs making up the RTNs is 230.

In the case of several of the RTNs, the graph of calls to sub-transducers admits cycles. Due to these cycles, these RTNs generate an infinite set of endings. The lexicon compiler allows for keeping the set of generated endings finite by breaking all cycles.

Word lexicon

The various readable resources described above are compiled into an operational lexicon of words whenever one of them is updated. The lexicon of words has an index for fast matching. This index is a finite-state transducer over the Korean alphabet of letters. This is a transposi-tion of the state-of-the-art technology of representation of lexicons of forms in inflectional languages [START_REF] Appel | The world's fastest Scrabble program[END_REF][START_REF] Silberztein | A new approach to tagging: the use of a large-coverage electronic dictionary[END_REF]Revuz, 1992;[START_REF] Lucchesi | Applications of finite automata representing large vocabularies[END_REF]. Another index structure, the trie, has been tested with the same lexicon. The size of the trie (930 Kb) is slightly larger than the size of the transducer (560 Kb), due to the representation of endings which is repeated many times in the trie.

The compilation of the lexicon of words from the readable resources follows several sequential steps. First, all resources are converted from the Korean syllabic alphabet to the Korean alphabet of letters. In a second step, lexicons of stem allomorphs and of derived stems are generated from the base-form stem lexicons by applying the transducers with Unitex. In a third step, the resulting lexicons of stems are compiled by the Unitex lexicon compiler. Each compiled lexicon has an index, which is a finite-state automaton. The final states of the automaton give access to the lexical information, and in particular to the CSs of the stems. In a fourth step, each transducer of sequences of suffixes is converted into a list by a path enumerator, and each of these lists is processed by the lexicon compiler. The names of the compiled ending lexicons contain the corresponding CSs. In the final step, the stem lexicons and the ending lexicons are merged into a word lexicon. This operation links the final states of the stem lexicons to the initial states of the corresponding ending lexicons. The path enumerator and the lexicon link editor have been implemented for this experiment and will receive an open-source status. The path enumerator allows for breaking cycles in the graph of calls to sub-transducers, so that the enumeration remains finite.

The current version of this compilation process generates a lexicon of one-stem words only. Multi-stem words will be represented in later versions.

These operations are independent of the text to be annotated; they are performed beforehand. They need to be repeated whenever one of the language resources is updated.

The operation of the morphological annotator is simple. The text is pre-processed for sentence segmentation, and tokenised (words are tokens). In each word, Korean syllables are converted into Korean letters; then, the lexicon of words is searched for the word. Lexicon search is efficient: it processes 41,222 words per second on a P4-400 Windows PC. When Chinese ideograms occur in a stem, the lexicon search module searches directly the lexical information attached to stem entries. We did not include any modules for processing words not found in the lexicon.

All analyses that are conform to phonotactic and grammatical in-word constraints are retained. However, checking these constraints does not suffice to remove all ambiguity from Korean words. A thorough removal of ambiguity requires a syntactic process [START_REF] Voutilainen | A Syntax-based part-of-speech analyser[END_REF][START_REF] Laporte | Reduction of lexical ambiguity[END_REF]. Our system presents its output in an acyclic finite-state automaton (also called a graph or a lattice) of morphemes, as in Lee et al. (1997b), but displayed graphically. The output for each morpheme is presented in three parts: surface form, base form, and a structured tag providing the general tag of Table 1 and syntactic features. Word separators such as spaces are also present in this automaton.

The annotation of an evaluation sample by the system presented 67 % recall and 46 % precision. The annotation of a morpheme was considered wrong when any of the features was wrong. Among these errors, 78 % are resource errors that can be corrected by updating the resources, whereas the correction of the remaining 22 % would involve enhancing the compilation procedure.

Conclusion

We experimented with a method likely to enhance the performances of state-of-the-art systems of Korean morphological annotation. We made language resources the central point of the problem. All complex operations were integrated among resource management operations. The output of our system is accurate and informative; the language resources used by the system can be easily updated, which allows users to control the evolution of the performances of the system. Morphological annotation of Korean text is performed directly with a lexicon of words and without morphological rules, which simplifies and speeds up the process.

This work opens several perspectives. The resources will be extended by running the annotator and analysing output. Existing approaches to the analysis of unrecognised morphemes could be combined to our system: such approaches are complementary to our resourcebased approach, and would take advantage of the rich information provided on the neighbouring words. Ambiguity resolution techniques can be applied to the output of our annotator: the syntactic approach would take advantage of the rich linguistic information provided in output; classical statistical approaches and priority rules [START_REF] Kang | A Rule-Based Method for Morphological Disambiguation[END_REF] are applicable as well. Finally, a parallel system is under construction for Finnish, another agglutinative language with undelimited morphemes.

Table 1 .

 1 There are 91 features with a total of 152 values.

	A	adjective	Sfx	derivational suffix
	ADV	adverb	Morph pre-final verb/adj. end-
				ing
	DET determiner	Post	postposition
	N	noun	Sc	conjunctive suffix
	NI	bound	Sd	determinative suffix
		noun
	PRO	pronoun Sncomp nominalization suffix
	V	verb	St	final ending
	INT interjection	Suf	pre-final nominal end-
				ing

Table 1 .

 1 General tags

http://nlp.kookmin.ac.kr/HAM/kor/ham-intr.html

http://www.cis.upenn.edu/~nrh/klex.html


Javier M Sastre Martínez
email: sastre@univ-mlv.fr

XML-Based Representation Formats of Local Grammars for the NLP

Introduction

Local grammars are conceived to exactly recognize specific natural language structures and to recursively serve as pieces of further more complex grammars recognizing higher level structures until the construction of an exact grammar covering the whole extension of a natural language is reached. Many new problems have arisen since this approach to the exact recognition was introduced (Gross, 1997). First of all, it was necessary to provide linguists with computer tools which would facilitate the construction of local grammars and would be able to apply them over real corpus in order to validate them. The Intex system [START_REF] Silberztein | Dictionnaires électroniques et analyse automatique de texts: le système INTEX[END_REF] was an already existent tool allowing the construction of local grammars. Subsequently, the Unitex system [START_REF] Paumier | Unitex manuel d'utilisation[END_REF] was developed for this purpose. Both of them use graphical representations of grammars called graphs. The figure 1 shows an example of graph representing a local grammar semantically equivalent to the structure "in order to + verb". The code "<V:W>" represents any infinitive verb defined in an electronic dictionary and the code <a> corresponds to "a" or "an". Grey boxes represent references to other graphs. This way it is possible to reuse grammar definitions in order to easily built larger ones. In this case, the referenced grammars define verbal constructions. As we can see, this graphical representation is simple and easy to read: we can rapidly realize of the recognized sequences just by reading from left to right (e.g.: "in attempts to <V:W>", "in an attempt to <V:W>", etc).

Figure 1: "In order to + verb" graph As the number of constructed grammars increases, it becomes harder to efficiently store and selectively recover them so that we can reuse them for the construction of new ones. Consequently, a local grammar library allowing to search and extract them by means of grammar specific queries has already been conceived [START_REF] Constant | The Construction of Local Grammars[END_REF]. However, it does not exist up to now a common graph representation format; it has been necessary the use of format conversion tools in order to edit graphs with other tools than the one used to create them. If a system for the massive storage and exchange of graphs amongst computer applications is to be built, it is firstly necessary to develop a graph exchange representation format easy to be supported, able to represent any natural language grammars and as most stable as possible. Especially, stability is an important factor since the migration from a representation format to a new one is a hard task that, if not correctly done, can lead to data corruption.

The World Wide Web Consortium (W3C) is an international recognized organization whose purpose is the development of common protocols allowing interoperability over the World Wide Web (WWW). The Extensible Markup Language, or XML [START_REF] Skonnard | Essential XML Quick Reference: A Programmer's Reference to XML, XPath, XSLT, XML Schema, SOAP and More[END_REF], is a simple, very flexible text format derived from SGML and which is being widely used as exchange format of data on the Web and elsewhere. XML Schemas [START_REF] Vlist | XML Schéma[END_REF] provide means for defining the structure, content and semantics of XML documents.

The Unicode Standard (Allen, 2003) is a character coding system designed to support the worldwide interchange, processing and display of the written texts of the diverse languages and technical disciplines of the modern world. In addition, it supports classical and historical texts of many written languages. XML relies on Unicode and closely tracks its revisions.

There exist several tools and libraries which facilitate the development of software dealing with XML and XML Schema based representation formats. For example, the Java Architecture for XML Binding (JAXB) is a Java technology in the Java Web Services Developer Pack, or JWSDP [START_REF] Ball | The Java TM Web Services Tutorial[END_REF], that enables to automatically generate Java code for the analysis, validation and synthesis of XML documents following a given XML Schema specification.

The common graph exchange formats presented in this paper are based on XML and formally defined by means of XML Schemas, thus fulfilling all the presented requirements: stability, language independency and easiness of being supported.

Graph object description

Graphs are graphical objects equivalent to transducers within a recursive transition network (RTN) conceived to facilitate the construction and comprehension of grammars for the NLP. As we can see in the example graph (figure 2), a graph is composed by a set of linked boxes of different types.

Transduction boxes

Transduction boxes recognize a set of input token sequences and optionally generate an output character sequence. If no output is defined, the empty sequence is assumed by default. Graphs can also be referenced within a transduction box allowing the box to recognize every sequence recognized by the referenced graph; from a procedural point of view, we say that the referenced graph is "called" by the graph containing the referencing box. Every directly or indirectly called graph is a subgraph of the calling graph, and recursive calls are also allowed. Each white background line of a transduction box corresponds to an input sequence (e.g.: "nuclear bomb") and each gray background line to a subgraph call (e.g.: "NNMDW" subgraph). An additional line under the box corresponds to the box output sequence (e.g.: "<MDW>$X$</MDW>"), if defined. Once a transduction box recognizes an input sequence fragment, its associated output sequence is appended to the graph output. Transduction boxes that only recognize the empty word are represented by an empty triangle with the associated output below.

Initial and final boxes

Initial and final boxes are to be contained in every wellformed graph, a single one of each type per graph. Only transduction or record boxes are to be the initial box of a graph, which is distinguished from the others by an incoming-from-no-box transition. The application process of a graph starts at its initial box and follows the outgoing links or transitions as the following boxes are able to recognize the next input fragment. By default, transitions start at the box right sides and end at the left box sides. The transition direction can be switch for the representation of right-to-left language grammars. A whole input sequence is recognized by a graph if its last fragment is recognized by a box having an outgoing link towards the final box, which is represented by a circle containing a square. Opposite to the initial box, the final box has no other purpose than marking the recognition of a sequence accepted by the graph.

Record start/stop boxes

Record start/stop boxes represent points within a graph where the input sequence recording mechanism is switched: once a record start box is reached, the associated variable (e.g.: "X") is defined and initialized to an empty sequence value and every later recognized input sequence fragment is appended to the variable content until a record stop box associated to the same variable is attained. Once a record stop box is reached, the associated variable remains defined but its content is no longer modified until a start box associated to the same variable is reached. Recorded input fragments may be parts of transduction box character sequence outputs by specifying the correspondent initialized variable identifier within the output sequence specification (e.g.: "$X$"; we surround variable identifiers with dollar symbols in order to distinct them from merely output character sequences). Once the final box is reached, defined variables within the graph become undefined: variable values are not conserved once a graph application has ended. Called subgraphs may access variables initialized by their calling graphs independently of the call depth. In case of variable identifier conflict between successive graph calls, the inner call graph variable value is assumed (outer variable definitions are hidden by same identifier inner variable definitions). Apart from the recording mechanism, record boxes behave as transduction boxes recognizing the empty word and generating an empty output sequence.

Comment boxes

Comment boxes (e.g.: "Tagger for nuclear bomb and other mass destruction weapons") contain metainformation conceived to facilitate the interpretation of the graph. The presence or absence of such boxes does not alter the represented grammar.

From graphs to FSTs

Let G be a graph, we call compilation of G the transformation process of G and its subgraphs into minimal finite-state transducers (FSTs) and further optimization of the resulting RTN. We call G the main graph of the compilation. Every information w.r.t. the representation format of the graphs is lost. The structure of the resulting RTN may be modified in order to boost its application. The compilation process, as usual, is not reversible.

Opposite to standard FSTs, whose operations associated to their transitions involve uniquely input recognition/output generation, graph equivalent FSTs may have three extra operation types: sub-FST calling, record start and record stop operations. Every transition associated to a sub-FST calling operation is equivalent to an epsilon transition towards the initial state of the called sub-FST and further coming back from any of its final states towards the arriving state of the calling transition. Transitions associated to record start/stop operations are equivalent to epsilon transitions that switch the input sequence recording mechanism analogous to the graph's one. We call main FST of a RTN the first one to be considered during the RTN application process. We say that an FST is a sub-FST of another one iif the former is called within any of the transition operations of the latter.

XML Terms

Terms are the atomic information units to be recognized and which compose input sequences. We represent them as the following XML elements:

1. <epsilon/>: empty word. 2. <blank/>: mandatory blank space occurrence before the next term. 3. <noblank/>: no blank space occurrence before the next term. 4. <symbol>: specified symbol (not a letter). 5. <word/>: any word (sequence of letters). 6. <word case="lowercase"/>: any lowercase word. 7. <word case="uppercase"/>: any uppercase word. 8. <word case="firstupper"/>: any uppercase starting word. 9. <word> specified word (sequence of letters) or any of its variants (e.g., case variants). 10. <word case-sensitive="false"> specified word. 11. <token/>: any token (symbol or word). 12. <token case="lowercase">: any symbol or lowercase word. 13. <token case="uppercase">: any symbol or uppercase word. 14. <token case="firstupper">: any symbol or uppercase starting word. 15. <token> specified token or any of its variants. 16. <token case-sensitive="false"> specified token. 17. <dicentry>: specified dictionary entry.1 18. <dicword/>: any dictionary defined word. 19. <dicword>: any dictionary defined word having the set of properties specified using the dictionary's notation. 20. <punctuation>: any punctuation symbol. 21. <number>: any sequence of numbers. 22. <sentencetag>: end of sentence.

Additionally, any term representing a set of tokens have the optional attributes "complement" and "filter". A term having the former attribute set to "true" represents the complement of the set represented by the original term. If the attribute is not set or is set to "false", default behavior is assumed. If the considered term is <dicword>, the domain of the complementation is restricted to the set of dictionary-defined words. The "filter" attribute value is a POSIX regular expression. When present, the token to be recognized by the term must match the regular expression. This attribute represents a further restriction by means of a regular expression filter. If both complementation and filtering operations are to be applied, the former is considered before the latter.

XML output char subsequences

Output character subsequences are represented by <chars> elements or by <var varid="…"/> elements. The former contains the character subsequence to be generated (direct addressing) and the latter specifies by means of its "varid" attribute value the identifier of the variable containing the subsequence (indirect addressing). An output character sequence is represented by a sequence of one or more <chars> and/or <var/> subsequence elements. Alternate direct/indirect addressing within an output sequence specification is allowed.

XML graphs

A graph is represented by an element <graph pathname="…">, whose attribute "pathname" value is the address of the represented graph. This element has an optional element <format> and an element <boxes>. The former contains information about the graphical representation of the graph and the second the list of boxes that compose the graph. This list must contain an initial box, zero, one or more non initial or final boxes and a single final box. The element <boxes> must have an attribute "initialbox" whose value is the identifier of the initial box.

Box elements

Every box element representing a non-comment box, and therefore a reachable box, has an attribute "id" whose value identifies uniquely the box. Every box element has a pair of optional attributes "posx" and "posy", which represent the coordinates in a Cartesian system where the box is to be located in the graphical representation of the graph. Record start and record stop boxes are represented by <recordstart> and <recorstop> elements respectively. Both of them have an attribute "varid" whose value is the identifier of the variable associated. Comment boxes are represented by <comment> elements, whose only content is the comment text. The final box is represented by the element <final/>, which has no content. Transduction boxes are represented by <transduction> elements. The elements representing record boxes or transduction boxes may contain an element <transitions>. Such element contains the list of box identifiers, separated by a single space, which are pointed by the box outgoing transitions.

Inputs and output elements

Additionally, each <transduction> element contains an <inputs> element, which defines every input recognized by the box, and optionally an <output> element, which defines the output character sequence to be generated by the box. If no output is to be generated, the <output> element is omitted. The element <inputs> contains one or more elements <sequence> or <subgraph/>. The former represents a sequence of terms and the latter a subgraph call. The element <sequence> must contain a sequence of at least one term element. The <subgraph/> elements have an attribute "pathname" whose value is the address of the subgraph to be called. The element <output> contains a sequence of at least one output character subsequence element.

Input subsequence elements

The input subsequence elements <symbols>, <words>, and <tokens> represent sequences of one or more consecutive symbols, words or tokens respectively. Consecutive sequences of <symbol>, <word> or <token> elements can be represented by an input subsequence element containing the list of the correspondent tokens separated by a single space. Input subsequence elements have two optional attributes: "case-sensitive" and "blanks". The former indicates if word variants are accepted ("true" value) or not ("false", default value). The latter indicates if blank spaces between tokens are optional ("optional", default value), mandatory ("mandatory" value) or forbidden ("forbidden" value).

XML RTNs

An RTN is represented by an <rtn pathname="…"> element, whose attribute "pathname" value is the address of the represented RTN. This element contains an element <fsts> and an element <operations>. The former represents the list of FSTs that compose the RTN and the latter the set of operations associated to the transitions of all the FSTs within the RTN.

FST elements

The element <fsts> must contain an element <main>, which represents the main FST, and a list of zero, one or more elements <sub>, which represent the sub-FSTs of the main FST. The structure of both <main> and <sub> elements is the same: they have an attribute "id", whose value identifies uniquely the FST within the RTN, and contain an element <initialstate> and zero, one or more elements <state>. The element <initialstate> corresponds to the initial state of the FST and the <state> elements to the rest of its states. Those elements share the same structure: they have an attribute "id", whose value identifies uniquely the state within the FST, and an attribute "final", whose value indicates if the state is final (true) or not (false, default value). They contain zero, one or more <transition> elements, each one representing a state outgoing transition. Those elements have an attribute "operationid", whose value is the identifier of the operation associated to the transition, and an attribute "stateid", whose value corresponds to the identifier of the arriving state.

Operation set element

The <operations> element contains zero, one or more operation type elements, each one representing a single operation to be associated to any of the FST transitions. Every operation type element has an attribute "id" whose value identifies uniquely the operation within the whole RTN.

Transduction operation element

An element <transduction> within the <operations> element represents an input term recognition/output character sequence generation operation. The input term is represented by a mandatory term child element. In case an output is to be generated, it is represented by an <output> element containing a sequence of at least one output character subsequence element.

Sub-FST call operations

FSTs within a RTN are also considered operations when associated to a transition: the transduction operation defined by the FST. We represent a sub-FST call operation by setting the "operationid" attribute value of the correspondent <transition> element to the identifier of the FST to be called. FST and operation identifiers must be different since they share the same space.

Record operation elements

Record start and record stop operations are respectively represented by <recordstart> and <recordstop> elements within the <operations> element content. In addition to their "id" attribute, they have a "varid" attribute whose value is the identifier of the recording variable.

Conclusion

In this paper we described XML-based representation formats of graphs and RTNs. Those formats have been formally described by means of XML Schemas. Both XML and XML Schemas are solid standards, thus the presented formats are expected to last and consequently to save the effort of developing new formats and to avoid data corruption due to format migration. Thanks to the compatibility of XML with Unicode, any natural language is to be supported. Thanks to tools like JAXB, it will be relatively easy from now on to add support for the presented formats to existing or new computer applications and, therefore, to enable them to exchange local grammars. Graph and RTN format conversion tools have already been developed and tested for the migration from Unitex native formats to the presented XML-based formats. The 88% of the resultant Java source code was automatically generated by JAXB. Now that we have set an appropriated media for local grammar representation we can proceed with the implementation of a local grammar management system for their efficient storage and diffusion among the scientific community.

Figure

  Figure 2: example graph

A dictionary entry corresponds to a non-ambiguous lemma description. Dictionary entry references are to be used in lexically disambiguated corpus by means of added tags.


Matthieu Constant

Microsyntax of Measurement Phrases in French: Construction and Evaluation of a local grammar

This paper focuses on the description of simple measure phrases by means of a local grammar. We show that these linguistic objects can be decomposed in several elementary components and that they are subject to complex internal constraints. From these linguistic observations, we build a global grammar that is then evaluated on two corpora.

Introduction

Finite-state technology is now widely used in Named Entity Recognition (NER) systems. Many studies showed that finite-state representation was linguistically relevant for such entities, in particular numerical expressions (NUMEX). In this paper, we focus on specific numerical expressions related to 'quantities': measurement expressions, that are less studied because of their low frequency relatively to other types of numerical expressions.

A Measurement expression involves a value measuring a property of an item (e.g. length, weight) or a property relating two items (e.g. distance) as it is shown in the examples below:

(1) On this road, the speed of the car is limited to 50 mph.

(2) The villa has a distance of 100 feet to the sea.

In the construction-grammar framework, they are formalized by a relation between three elements: item, dimension and value. An item (e.g. desk) has a dimension (e.g. width, weight) which can be measured with a value (2 m, 2 kg) [START_REF] Hasegawa | [END_REF]]. In addition, each dimension selects a set of appropriate units. Dimensions can be regrouped into families the dimensions of which select the same units: e.g. width, height, radius dimensions belong to the 1D spatial dimension family.

In this paper, we focus on the microsyntax and the recognition of the value in French measurement expressions, which, roughly speaking, consists of a simple phrase composed of a cardinal numerical determiner and a unit. We note them Dnum Unit. This is an obligatory step before a deeper automatic syntactic and semantic analysis. At first sight, this appears simple but we will show that this type of expressions is subject to complex lexical and syntactic contraints that can be well described and identified by a finite-state system. Our study is based on our previous work in [START_REF] Constant | Methods for Constructing Lexicon-Grammar Resources. The Example of Measure Expressions[END_REF]]. We use the formalism of local grammars introduced by [Silberztein 2000] and [Gross 1997]. They are made of finite-state graphs representing and structuring complex linguistic forms. They can recursively refer to other graphs and are based on large-scaled lexicons. The grammars were encoded, compiled and applied with different programs of the platform Unitex [Paumier 2008] 1 .

The first part of the paper is devoted to a linguistic description of the elementary components that are numerical determiners and scientific units. Then, we detail the linguistic constraints on the combination of these two components. Finally, we show how to construct the global local grammar recognizing a regular language and we evaluate it on three distinct corpora.

Cardinal numerical determiners

Numerical determiners are well studied linguistic components in the field of NLP. Many researchers showed that Finite state models are best suited for their representation (in particular [START_REF] Chrobot | Description des déterminants numéraux anglais par automates et transducteurs finis[END_REF],Silberztein 2003,Karttunen 2006,Laporte 2007]). They can be divided into three categories: cardinal numbers written in words, cardinal numbers constiting of digits, nominal numerical determiners.

Cardinal numbers written in words

Cardinal numbers written in words have been studied and described in the form of local grammars by [Silberztein 2003] for French. For this work, we used the proposed graph structuration to construct a local grammar, describing natural integers in words up to one trillion. The main difficulty comes from different spellings of some words depending on the context. For instance, cent (hundred) is spelled differently in deux cents (two hundred) and in deux cent deux (two hundred and two). The number quatrevingt has two spellings whether it is located on the right or on the left of words like mille (thousand) or million : quatre-vingt mille deux cent quatre-vingts (i.e. 80, 280)

Cardinal numbers consisting of digits

A finite-state graph is also very convenient to describe cardinal numbers consisting of digits. There exits a writing convention, and so a specific syntax, for numbers with more than three digits: for example, in French, in 1 298, there exists a white space between the third and the fourth digits; in English, the white space is replaced by a coma (1,298). From a general point, a white space (a comma in English) occurs in the sequence of digits every 3 digits starting from the right. Note that such strict conventional constraints are not always true in texts depending on the writer. Sometimes, required internal whitespaces do not even exist or are replaced by dots (.). Integer values are therefore sometimes ambiguous with some dates (ex. 2009).

Decimal numbers can also be simply represented. In French, the integer and decimal parts are separated by a comma (12,7 ou 3,896). In English, it's a dot (12.7 ou 3.896). Numbers in scientific notation also have a specific syntax: e.g. 1,23.10E5; 1,23x10+52 or 4,8x10-6. They include a coefficient and a base. The coefficient is a decimal number between 1 and 10 not included. The integer part solely contains one digit. The decimal part is more free in size: it depends on the precision required. The number is then adjusted by means of the base which is either a positive or negative integer.

Nominal numerical determiners

Nominal numerical determiners were systematically described with a finite state representation in [Silberztein 2003,Laporte 2007] These deteminers can include a limited set of modifiers that bring little semantic nuances such as in:

(5) Paul a perdu une petite douzaine de kilos.

Paul lost a few dozen kilograms.

There also exist semi-fixed forms of these determiners: des Nnum et des Nnum de.

(6) Marie a gagné des centaines et des centaines de dollars.

Mary earned hundreds and hundreds of dollars

Sequences of nominal numerical determiners are also accepted:

(7) 1,67 milliardième de milliardième de milliardième de kg. 1.67 billion billion billionth of kg

Units

The use of a type of unit depends on the dimension to be measured. Dimensions can be gathered in families the members of which share the same class of appropriate units.

For each family, it is therefore necessary to define the associated class, that is the list of all types of appropriate units. Each class is usually divided into two sub-classes: unit symbols -e.g. m -and unit names -e.g. mètre (meter)-. In practice, each dimension family X (e.g. Energy) is associated with two hand-drafted graphs: XUnit (e.g. EnergyUnit) for unit names and XUnitSymb (e.g. EnergyUnitSymb) for unit symbols. For instance, graph EnergyUnit would look like in figure 1. It refers to the graphs representing the different types of units belonging to the class: Calory, Joule, ElectronVolt and WattHour.

In the two following subsections, we show how these graphs were constructed (either automatically -prefix genbase-, either manually -prefix base-).

Basic units

Firstly, we enumerated measurement units by using the scientific classification. We generated a specific dictionary where lexical entries correspond to unit forms (ex. millimètres, mm). Each entry is assigned a lemma (ex. millimètre, mm), a category (Unit), morphological information, its scientific unit class (ex. MeterUnit) and information weither the form is a unit name (+Name) or a unit symbol (+Symb). Given a base unit (meter, m), we automatically list all multiples and sub-multiples (e.g. kilometer, km ; millimeter, mm) by adding relevant prefixes and suffixes when required. All morphological information were encoded in a specific configuration file for each base unit, in order to be used at the dictionary generation. For instance, the configuration below for byte units (ByteUnit) indicate that the base name and symbol are respectively octet and o. All derived forms would be in masculine (code m) and names accept the plural form by adding suffix -s (code morpho). All standard prefixes are not accepted and are limited to those encoded SUP (kilo-octet, *milli-octet). Names also accept a hyphen between the prefix and the base form (code hyphen).

(8) octet:o::Byte:morpho+SUP+m+hyphen

We also generated two graphs for each scientific type: one for unit symbols, another one for unit names. Both make reference to unit forms encoded in the dictionary. For example, graphs in figure 2 represent units derived from Joule: <Unit+JouleUnit+Symb> and <Unit+JouleUnit+Name> respectively indicate all unit symbols (+Symb) and names (+Name) of type JouleUnit. In total, we constructed graphs for 21 unit types. In addition, we constructed manually graphs of compound unit names with some variants. For instance, mille nautique (nautical mile) have several variants : e.g. mille (E+marin+nautique)(E+international+britannique)2 . Finite state graphs are therefore of great interest to represent them. It is even clearer with currency units that contain many lexical variants. Graph 3 represents the different types of dollars.

Complex units

Some units are defined by the combination of basic units. For instance, in physics, a speed unit is the "division" of a 1D spatial unit and a time unit: centimètres par heure (centimeters an hour), km/s. In everyday language, there exists some variants such as kilomètres à l'heure ou kilomètres-heure. Exemple 9 shows that the first expression can also be reduced in the sequence à l'heure, but this is only available with the unit name heure: Below is given the graph SpeedUnit representing this type of units. LengthUnit is the union of graphs of units measuring length. TimeUnit gathers units measuring time. Note that it contains a simple unit name noeud measuring the speed of boats.

The area dimension lexicalized by the words aire, surface, superficie also selects complex units:

-the combination of a length unit followed by either the digit 2 if it's a symbol or the modifier carré (square) if it's a unit name: e.g. m2, mètre carré; -simple surface units like are, hectare symbolized by a and ha.

In a similar way, units measuring volume are formed of two types of units: a length unit followed by the digit 3 or the modifier cube (cubic); units derived from litre (liter)

The scientific unit traditionally associated with frequency is hertz. Nevertheless, in everyday language, the unit is more free. It can be any countable noun phrase with no determiner followed by a preposition (or symbol '/'), an optional determiner and a time unit: The factory produces thirty chicken a minute Thus, it is necessary to describe a complete noun phrase which in theory is not finitestate. Nevertheless, in practice, this phrase is short because it is followed by a sequence expressing time. We therefore limited our noun phrase graph to the following maximal sequence Adj N Adj de Det N. Note that frequency expressions can be expressed in a non-connex manner. They may require the analysis of a whole sentence, which makes finite-state description more difficult even if pragmatic solutions based on finite-state techniques exist. Examples 12 and 13 are equivalent in meaning, which shows that uterrance par an (a year) can be inserted in different locations of the sentence (like standard adverbials). (18) Paul a couché avec environ mille femmes au total Paul slept with around one thousand women in total

Internal constraints

This section focuses on the description of the linguistic constraints existing between the numerical determiner (Dnum) and the measurement unit (Unit).

Stylistic constraints

The two components Dnum and Unit are firstly subject to stylistic contraints. For instance, the combination of a numerical determiner written in words followed by a unit symbol is not natural although the other combinations are allowed: There exists a constraint of homogeneity between the left and right parts of the nonconnex determiner: they are either both written in words or both written with digits. In addition, the left part of the determiner must be an integer.

Precision

The structure Dnum Unit can sometimes be commuted to a sequence of several Dnum Unit. It has a specific syntax for each unit class. This is mainly used to add precision to a measurement. The following examples show constraints on the sequences of simple phrase Dnum Meter:

(24) Jean a couru 10 kilomètres et (30 mètres+*3 000 mètre+*30 secondes) John ran 10 kilometers and (30 meters+*3,000 meters+*30 seconds) (25) Ce champ a une surface de 100x200m This field has an area of 100m by 200m

Approximations

In this section, we focus on more complex combinations representing approximations of values. In construction de ... à ..., the preposition de is not always obligatory like it is shown in example 30. In many cases, it is soly the introducer of a prepositional measurement phrase and should not be included: for instance, un bateau de cinq à six tonnes (a boat of five to six tons). Moreover, the construction with de is naturally ambiguous. It can also express an evolution in time. Its interpretation depends on the main verb of the elementary sentence.

(32) Le prix du pain est passé de 65 à 70 centimes

The price of the bread went from 65 to 70 cents

In this sentence, the initial price of the bread is 65 cents and reaches 70 cents at the final state. In many cases, this ambiguity is impossible to remove locally.

Construction of a Local Grammar

All linguistic constraints described in the previous sections were gathered in a local grammar making use of morphological finite-state resources. These resources consisted of the general language dictionary DELA [ [START_REF] Courtois | [END_REF]] and the dictionary of 2,007 simple unit forms, generated in section 3.1. The elementary linguistic components (numerical determiners and predeterminers, plus units) are described in various graphs:

-Numerical predeterminers can be either predeterminers located before sequence Dnum Unit (graph PreDnum) or ones located after (graph PreDnumPost) -Numerical determiners can be of different types (graphs NumberWithLetters, Nomi-nalDnum, NumberWithDigits) and subtypes (graphs IntegerNumber, DecimalNumber, ...). -Each dimension family has its own graphs of appropriate units.

For each dimension family, we automatically produced a graph DnumUnit recognizing: (1) simple expressions Dnum Unit including predeterminers and internal constraints combining numerical determiners and units; (2) complex structures formed of simple expressions (ex. entre 10 mm et 15 cm). We used a so-called parameterized graph4 (cf. figure 5) that contains all possible constructions which include parameters (@...@) the values of which depend on the dimension family processed. Parameter @dim family@ is the name of the dimension family (e.g. Energy). The graph refers to two other graphs: SimpleDnum@dim family@Unit (e.g. SimpleDnumEnergyUnit) representing simple measurement expressions and SimpleDnum@dim family@UnitZ (e.g. SimpleDnumEnergyUnit) representing simple measurement expressions where the unit can be absent. All generated graphs are gathered in one single graph DnumUnit, equivalent to a finite state transducer.

The two types of simple expression graphs were also built using a parameterized graph (cf. figure 6). Parameter @precision@ indicates whether there exists a graph descibing precised expressions (cf. subsection 4.2). Parameter @zeroing@ indicates whether the absence of a unit is allowed. For each dimension family @dim family@, two graphs (SimpleDnum@dim family@Unit and SimpleDnum@dim family@UnitZ) were produced by resolving the parameters. According to their values, there are two cases: (1) the parameter is replaced by the empty word or the lexical value corresponding to the parameter; (2) the parameter transition is removed.

Evaluation

The evaluation process requires a corpus where measure expressions are annotated. Unfortunately, such a corpus does not exist for French. We therefore constituted three corpora: the first one (namely SCIENCE) made of articles of two French scientific periodicals (Science et Vie, Science et Avenir); the second and third ones (namely NEWS1 and aim at evaluating the grammar on expressions in a more common language. NEWS1 is the strict concatenation of journalistic articles. In table 9, we observe that NEWS1 is almost limited to the three main types of numerical expressions studied for NER (time, percentage and monetary expressions). NEWS2 is a concatenation of paragraphs containing the other types of expressions.

Each corpus was divided in two parts of the same size: the first one for the development of the grammar; the other one for its evaluation. After the construction of the grammar, we manually annotated the evaluation part of the three corpora. Different figures on the annotated evaluation corpora can be found in figure 6. Note that the corpora are rather small in terms of number of annotated expressions5 . An example of the SCIENCE corpus in given below:

De violentes tempêtes de sable emportent {au moins 150 000 tonnes,.XN+Weight} de sel et de sable du lit asséché de la mer et les transportent sur {plusieurs centaines de kilomètres,.XN+Length}.

The evaluation stage consists in applying separately three different grammars compiled into their equivalent finite-state transducers on the three corpora with the longest match rule: (1) BASELINE (composed of 135 graphs: 325 states and 9,554 transitions) recognizing very simple sequences formed of a number (with digits and with letters) followed by a unit; (2) SIMPLE (165 graphs: 5,578 states and 69,553 transitions) recognizing simple expressions (cf. section 5); (3) COMPLEX (203 graphs: 8,940 states and 131,408 transitions) being the local grammar described in section 5. The grammars were all compared by using standard evaluation measures: precision (p), recall (r) and F1-measure (f). The results are shown in figure 8.

Eventhough the small size of the corpus attenuates the significance of the results obtained, it is possible to draw some conclusions. Firstly, the COMPLEX grammar reaches relatively good scores for NEWS1 and NEWS2. The heterogeneity of measure expressions in SCIENCE makes them more difficult to annotate automatically: for instance, some infrequent complex units are missing such as seconde d'arc measuring an angle; some expressions are not described, e.g. +55 45' 24"; there are other nonconnex types of expressions (ex. 100g CO2/km). The experiments also confirm that the measure phrases studied in this paper cannot be reduced to a number followed by a unit. By looking carefully at the annotations produced, we can observe the importance of nominal determiners. Even if complex structures are not so frequent in the corpora, the grammar recognizing them is very useful, especially in the corpus SCIENCE.

Corpus

Conclusions and Future Work

This paper focused on a description of measure phrases expressing a value by means of a finite-state approach. We showed that the resulting grammar reaches correct scores when it is applied in a context-free manner. In the short-run, we would to like to size up the evaluation corpora and to increase the coverage of our linguistic resources for improving recall. Future work would also involve integrating the grammar in a more global process taking all other linguistic phenomena into account (a finite-state chunker for instance) in order to improve precision. From this, it should be interesting to implement an automatic process that analyses complete expressions of measurement and annotates the relation between items, dimensions and values.

Fig

  Fig. 1. EnergyUnit

  Fig. 2. Joule type

Fig

  Fig. 3. Dollar

( 9 )

 9 Max roule à une vitesse de 80 (kilomètres+E) à l'heure Max has a speed of 80 (kilometers+E) an hour (10) Ce météorite a une vitesse de 2 (kilomètres + *E) à la seconde This meteor has a speed of 2 (kilometers+*E) a second

Fig. 4 .

 4 Fig. 4. SpeedUnit

( 12 )

 12 Par an, l'usine produit dix mille voitures (13) L'usine produit dix mille voitures par an The factory produces ten thousand cars a year 4 Measure expressions Dnum Unit 4.1 Numerical Predeterminers Simple measurement expressions often contain numerical predeterminers that can be located either before or after Dnum Unit like presque (almost), environ (around), exactement (precisely), à peu près (around): (14) Marie a (environ+exactement) 10 ans (15) Marie a 10 ans (environ+exactement) Mary is (around+precisely) 10-year old These words modify the interpretation of the value of the numerical determiner. The distributions of the predeterminers situated before Dnum Unit (PreDnum) and after (PreDnumPost) are different like in: (16) Luc possède (à peu près+environ+*ou presque+presque) 30 voiliers (17) Luc possède 30 voiliers (?à peu près+environ +ou presque+*presque) Luc owns (around+almost) 30 sailboats Predeterminers PreDnum et PreDnumPost can occur in the same sequence and are easy to represent in the form of graphs in order to integrate them in the basic structure Dnum Unit.

  dix + quelques dizaines de) mètres Determiner connexity Numerical determiners are not always connex and can be divided in two parts separated by the unit as shown in the examples below. (22) Max a un retard de huit minutes (trente + et demi) Max is eight minutes and 30 seconds late (23) Marie a sauté 5 m 60 Mary jumped 5.60 meters

Fig

  Fig. 5. parameterized DnumUnit

FigFig. 9 .

 9 Fig. 8. Evaluation

  Unit 1 -Dnum 2 Unit 2 . In all structures, Unit 1 and Unit 2 can be factorized if Unit 1 equals Unit 2 .

	Conjunction ou (or) The conjunction ou (or) is used to approximate the numerical
	value of the determiner in the form of a choice between several values.
	(26) Max a cinq ou six ans
	Max is five or six year-old.
	The sequence cinq ou six (five or six) could be interpretated as a compound determiner,
	but this involves issues because the sentence 26 is equivalent to the sentence :
	(27) Max a cinq ans ou six ans
	Max is five year-old or six year-old
	Moreover, it is possible to have a sentence like:
	(28) La table est à une distance de 90 cm (ou+voire) 3 1 m du mur
	The table is 90 cm or 1 m from the wall
	(29) La longueur est comprise entre 90 cm et 1,10m
	The length is comprised between 90 cm and 1.10 m
	(30) La température atteint (de + E) 13 à 15 degrés
	The temperature reaches 13 to 15 degrees
	(31) L'intensité du courant sur cette ligne est de 150 ampères-200 ampères
	The electric intensity on this line is 150 amperes-200 amperes

Range There exist three types of complex structures that are used to express ranges of values: (1) entre entre Dnum 1 Unit 1 et Dnum 2 Unit 2 (between ... and ...), (2) de Dnum 1 Unit 1 à Dnum 2 Unit 2 (from ... to ...), (3) Dnum 1

This free open-source system has the advantage of allowing users to add external lexicons and to refer to their lexical entries in the implemented grammars.

Symbol E is the empty word

voire is a variant of ou

This concept has been first introduced in the software INTEX[Silberztein 2000]. Note that the system NOOJ[Silberztein 2005] has also an interesting simpler mechanism to integrate such lexical and syntactic constraints into grammars. For this, it uses non strictly finite-state methods.

The small size of the annotated corpora and the high number of lexical and syntactic measure variants prevent from using a statistical process.


Matthieu Constant
email: mconstan@univ-mlv.fr

Anthony Sigogne
email: sigogne@univ-mlv.fr

MWU-aware Part-of-Speech Tagging with a CRF model and lexical resources

This paper describes a new part-of-speech tagger including multiword unit (MWU) identification. It is based on a Conditional Random Field model integrating language-independent features, as well as features computed from external lexical resources. It was implemented in a finite-state framework composed of a preliminary finite-state lexical analysis and a CRF decoding using weighted finitestate transducer composition. We showed that our tagger reaches state-of-the-art results for French in the standard evaluation conditions (i.e. each multiword unit is already merged in a single token). The evaluation of the tagger integrating MWU recognition clearly shows the interest of incorporating features based on MWU resources.

Introduction

Part-of-speech (POS) tagging reaches excellent results thanks to powerful discriminative multifeature models such as Conditional Random Fields (Lafferty et al., 2001), Support Vector Machine [START_REF] Giménez | SVMTool: A general POS tagger generator based on Support Vector Machines[END_REF], Maximum Entropy [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF]. Some studies like [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art POS tagging with less human effort[END_REF] have shown that featuring these models by means of external morphosyntactic resources still improves accuracy. Nevertheless, current taggers rarely take multiword units such as compound words into account, whereas they form very frequent lexical units with strong syntactic and semantic particularities [START_REF] Sag | Multiword Expressions: A Pain in the Neck for NLP[END_REF][START_REF] Copestake | Multiword expressions: linguistic precision and reusability[END_REF] and their identification is crucial for applications requir-ing semantic processing. Indeed, taggers are generally evaluated on perfectly tokenized texts where multiword units (MWU) have already been identified.

Our paper presents a MWU-aware POS tagger (i.e. a POS tagger including MWU recognition1 ). It is based on a Conditional Random Field (CRF) model that integrates features computed from largecoverage morphosyntactic lexicons and fine-grained MWU resources. We implemented it in a finite-state framework composed of a finite-state lexical analyzer and a CRF-decoder using weighted transducer composition.

In section 2, we will first describe statistical tagging based on CRF. Then, in section 3, we will show how to adapt the tagging models in order to also identify multiword unit. Next, section 4 will present the finite-state framework used to implement the tagger. Section 5 will focus on the description of our working corpus and the set of lexical resources used. In section 6, we then evaluate our tagger on French.

Statistical POS tagging with Linear Chain Conditional Random Fields

Linear chain Conditional Ramdom Fields (CRF) are discriminative probabilistic models introduced by (Lafferty et al., 2001) for sequential labelling. Given an input sequence x = (x 1 , x 2 , ..., x N ) and an out-put sequence of labels y = (y 1 , y 2 , ..., y N ), the model is defined as follows:

P (y|x) = 1 Z(x) N t=1 exp K k=1 λ k f k (t, x, y t , y t-1 )
where Z(x) is a normalization factor depending on x. It is based on K features each of them being defined by a binary function f k depending on the current position t in x, the current label y t , the preceding one y t-1 and the whole input sequence x. The feature is activated if a given configuration between t, y t , y t-1 and x is satisfied (i.e. f k (t, y t , y t-1 , x) = 1). Each feature f k is associated with a weight λ k . The weights are the parameters of the model. They are estimated during the training process by maximizing the conditional loglikelihood on a set of examples already labeled (training data). The decoding procedure consists in labelling a new input sequence with respect to the model, by maximizing P (y|x) (or minimizing -logP (y|x)). There exist dynamic programming procedures such as Viterbi algorithm in order to efficiently explore all labelling possibilities.

Features are defined by combining different properties of the tokens in the input sequence and the labels at the current position and the preceding one. Properties of tokens can be either binary or textual: e.g. token contains a digit, token is capitalized (binary property), form of the token, suffix of size 2 of the token (textual property). Most taggers exclusively use language-independent properties -e.g. [START_REF] Ratnaparkhi | A maximum entropy model for part-of-speech tagging[END_REF][START_REF] Toutanova | Feature-rich part-of-speech tagging with a cyclic dependency network[END_REF][START_REF] Giménez | SVMTool: A general POS tagger generator based on Support Vector Machines[END_REF][START_REF] Tsuruoka | Fast Full Parsing by Linear-Chain Conditional Random Fields[END_REF]. It is also possible to integrate languagedependant properties computed from an external broad-coverage morphosyntactic lexicon, that are POS tags found in the lexicon for the given token (e.g. [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art POS tagging with less human effort[END_REF]). It is of great interest to deal with unknown words2 as most of them are covered by the lexicon, and to somewhat filter the list of candidate tags for each token. We therefore added to our system a language-dependent property: a token is associated with the concatenation of its possible tags in an external lexicon, i.e. the ambibuity class of the token (AC).

In practice, we can divide features f k in two families: while unigram features (u k ) do not depend on the preceding tag, i.e. f k (t, y t , y t-1 , x) = u k (t, y t , x), bigram features (b k ) depend on both current and preceding tags, i.e. f k (t, y t , y t-1 , x) = b k (t, y t , y t-1 , x). In our practical case, bigrams exlusively depends on the two tags, i.e. they are independent from the input sequence and the current position like in the Hidden Markov Model (HMM)3 . Unigram features can be sub-divided into internal and contextual ones. Internal features provide solely characteristics of the current token w 0 : lexical form (i.e. its character sequence), lowercase form, suffice, prefix, ambiguity classes in the external lexicons, whether it contains a hyphen, a digit, whether it is capitalized, all capitalized, multiword. Contextual features indicate characteristics of the surroundings of the current token: token unigrams at relative positions -2,-1,+1 and +2 (w -2 , w -1 , w +1 ,w +2 ); token bigrams w -1 w 0 , w 0 w +1 and w -1 w +1 ; ambiguity classes at relative positions -2,-1,+1 and +2 (AC -2 , AC -1 , AC +1 ,AC +2 ). The different feature templates used in our tagger are given in table 2.

Internal unigram features

w 0 = X &t 0 = T Lowercase form of w 0 = L &t 0 = T Prefix of w 0 = P with |P | < 5 &t 0 = T Suffix of w 0 = S with |S| < 5 &t 0 = T w 0 contains a hyphen &t 0 = T w 0 contains a digit &t 0 = T w 0 is capitalized &t 0 = T w 0 is all capital &t 0 = T w 0 is capitalized and BOS 4 &t 0 = T w 0 is multiword &t 0 = T Lexicon tags AC 0 of w 0 = A & w 0 is multiword &t 0 = T Contextual unigram features w i = X, i ∈ {-2, -1, 1, 2} &t 0 = T w i w j = XY , (j, k) ∈ {(-1, 0), (0, 1), (-1, 1)} &t 0 = T AC i = A & w i is multiword, i ∈ {-2, -1, 1, 2} &t 0 = T Bigram features t -1 = T ′ &t 0 = T Table 1: Feature templates

MWU-aware POS tagging

MWU-aware POS tagging consists in identifying and labelling lexical units including multiword ones.

It is somewhat similar to segmentation tasks like chunking or Named Entity Recognition, that identify the limits of chunk or Named Entity segments and classify these segments. By using an IOB5 scheme [START_REF] Ramshaw | Text chunking using transformation-based learning[END_REF], this task is then equivalent to labelling simple tokens. Each token is labeled by a tag in the form X+B or X+I, where X is the POS labelling the lexical unit the token belongs to. Suffix B indicates that the token is at the beginning of the lexical unit. Suffix I indicates an internal position. Suffix O is useless as the end of a lexical unit corresponds to the beginning of another one (suffix B) or the end of a sentence. Such procedure therefore determines lexical unit limits, as well as their POS.

A simple approach is to relabel the training data in the IOB scheme and to train a new model with the same feature templates. With such method, most of multiword units present in the training corpus will be recognized as such in a new text. The main issue resides in the identification of unknown multiword units. It is well known that statistically inferring new multiword units from a rather small training corpus is very hard. Most studies in the field prefer finding methods to automatically extract, from very large corpus, multiword lexicons, e.g. [START_REF] Dias | Multiword Unit Hybrid Extraction[END_REF][START_REF] Caseli | Alignment-based extraction of multiword expressions[END_REF], to be integrated in Natural Language Processing tools.

In order to improve the number of new multiword units detected, it is necessary to plug the tagger to multiword resources (either manually built or automatically extracted). We incorporate new features computed from such resources. The resources that we use (cf. section 5) include three exploitable features. Each MWU encoded is obligatory assigned a part-of-speech, and optionally an internal surface structure and a semantic feature. For instance, the organization name Banque de Chine (Bank of China) is a proper noun (NPP) with the semantic feature ORG; the compound noun pouvoir d'achat (purchasing power) has a syntactic form NPN because it is composed of a noun (N), a preposition (P) and a noun (N). By applying these resources to texts, it is therefore possible to add four new properties for each token that belongs to a lexical multiword unit: the part-of-speech of the lexical multiword unit (POS), its internal structure (STRUCT), its semantic feature (SEM) and its relative position in the IOB scheme (POSITION). Table 2 shows the encoding of these properties in an example. The property extraction is performed by a longest-match contextfree lookup in the resources. From these properties, we use 3 new unigram feature templates shown in table 3: (1) one combining the MWU part-of-speech with the relative position; (2) another one depending on the internal structure and the relative position and (3) a last one composed of the semantic feature.

FORM POS STRUCT POSITION SEM Translation un - - O - a gain - - O - gain de - - O - of pouvoir NC NPN B - purchasing d' NC NPN I - achat NC NPN I - power de - - O - of celles - - O - the ones de - - O - of la - - O - the Banque NPP - B ORG Bank de NPP - I ORG of Chine NPP - I ORG China
Table 2: New token properties depending on Multiword resources

New internal unigram features

POS 0 /POSITION 0 &t 0 = T STRUCT 0 /POSITION 0 &t 0 = T SEM 0 &t 0 = T

Weighted finite-state transducers

Finite-state technology is a very powerful machinery for Natural Language Processing [START_REF] Mohri | Finite-state transducers in language and speech processing[END_REF][START_REF] Kornai | Conditional random Fields: Probabilistic models for segmenting and labeling sequence data[END_REF][START_REF] Karttunen | Applications of Finite-State Transducers in Natural Language Processing[END_REF], and in particular for POS tagging, e.g. [START_REF] Roche | Deterministic part-ofspeech tagging with finite-state transducers[END_REF]. It is indeed very convenient because it has simple factorized representations and interesting well-defined mathematical operations. For instance, weighted finite-state transducers (WFST) are often used to represent probabilistic models such as Hidden Markov Models. In that case, they map input sequences into output sequences associated with weights following a probability semiring (R + ,+,×, 0, 1) or a log semiring (R ∪ {-∞, +∞},⊕ log ,+, +∞, 0) for numerical stability6 . A WFST is a finitestate automaton which each transition is composed of an input symbol, an output symbol and a weight.

A path in a WFST is therefore a sequence of consecutive transitions of the WFST going from an initial state to a final state, i.e. it puts a binary relation between an input sequence and an output sequence with a weight that is the product of the weights of the path transitions in a probability semiring (the sum in the log semiring). Note that a finite-state transducer is a WFST with no weights. A very nice operation on WFSTs is composition [START_REF] Salomaa | Automata-Theoretic Aspects of Formal Power Series[END_REF]. Let T 1 be a WFST mapping an input sequence x into an output sequence y with a weight w 1 (x, y), and T 2 be another WFST mapping a sequence y into a sequence z with a weight w 2 (y, z).

The composition of T 1 with T 2 results in a WFST T mapping x into z with a weight w 1 (x, y).w 2 (y, z) in the probability semiring (w 1 (x, y) + w 2 (y, z) in the log semiring).

Lexical analysis and decoding

The lexical analyzer is driven by lexical resources represented by finite-state transducers like in (Silberztein, 2000) (cf. section 5) and generates a TFST containing candidate analyses. Transitions of the TFST are labeled by a simple token (as input) and a POS tag (as output). This stage allows for reducing the global ambiguity of the input sentence in two different ways: (1) tag filtering, i.e. each token is only assigned its possible tags in the lexical resources;

(2) segment filtering, i.e. we only keep lexical multiword units present in the resources. This implies the use of large-coverage and fine-grained lexical resources. The decoding stage selects the most probable path in the TFST. This involves that the TFST should be weighted by CRF-based probabilities in order to apply a shortest path algorithm. Our weighing procedure consists in composing a WFST encoding the sentence unigram probabilities (unigram WFST) and a WFST encoding the bigram probabilities (bigram WFST). The two WFSTs are defined over the log semiring. The unigram WFST is computed from the TFST. Each transition corresponds to a (x t ,y t ) pair at a given position t in the sentence x. So each transition is weighted by summing the weights of the unigram features activated at this position. In our practical case, bigram features are independent from the sentence x. The bigram WFST can therefore be constructed once and for all for the whole tagging process, in the same way as for order-1 HMM transition diagrams [START_REF] Nasr | Integrating a POS Tagger and a Chunker Implemented as Weighted Finite State Machines[END_REF].

Linguistic resources

French TreeBank

The French Treebank (FTB) is a syntactically annotated corpus7 of 569,039 tokens [START_REF] Abeillé | Building a treebank for French[END_REF]. Each token can be either a punctuation marker, a number, a simple word or a multiword unit. At the POS level, it uses a tagset of 14 categories and 34 sub-categories. This tagset has been optimized to 29 tags for syntactic parsing [START_REF] Crabbé | Expériences d'analyse syntaxique statistique du franais[END_REF] and reused as a standard in a POS tagging task [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art POS tagging with less human effort[END_REF] Multiword tokens encode multiword units of different types: compound words and named entities. Compound words mainly include nominals such as acquis sociaux (social benefits), verbs such as faire face à (to face) adverbials like dans l' immédiat (right now), prepositions such as en dehors de (beside). Some Named Entities are also encoded: organization names like Société suisse de microélectronique et d' horlogerie, family names like Strauss-Kahn, location names like Afrique du Sud (South Africa) or New York. For the purpose of our study, this corpus was divided in three parts: 80% for training (TRAIN), 10% for development (DEV) and 10% for testing (TEST).

Lexical resources

The lexical resources are composed of both morphosyntactic dictionaries and strongly lexicalized local grammars. Firstly, there are two generallanguage dictionaries of simple and multiword forms: DELA [START_REF] Courtois | Un système de dictionnaires électroniques pour les mots simples du franc ¸ais[END_REF]Courtois et al., 1997) and Lefff [START_REF] Sagot | The Lefff, a freely available, accurate and large-coverage lexicon for French[END_REF]. DELA has been developped by a team of linguists. Lefff has been automatically acquired and then manually validated. It also resulted from the merge of different lexical sources. In addition, we applied specific manually built lexicons: Prolex [START_REF] Piton | The Prolex Data Base : Toponyms and gentiles for NLP[END_REF] containing toponyms ; others including organization names and first names [START_REF] Martineau | Annotation et normalisation des entités nommées[END_REF] This set of dictionaries is completed by a library of strongly lexicalized local grammars [START_REF] Gross | The construction of local grammars[END_REF][START_REF] Silberztein | INTEX: an FST toolbox[END_REF] that recognize different types of multiword units such as Named Entities (organization names, person names, location names, dates), locative prepositions, numerical determiners. A local grammar is a graph representing a recursive finite-state transducer, which recognizes sequences belonging to an algebraic language. Practically, they describe regular grammars and, as a consequence, can be compiled into equivalent finite-state transducers. We used a library of 211 graphs. We manually constructed from those available in the online library GraalWeb [START_REF] Constant | Networking Multiword Units[END_REF].

Lexical resources vs. French Treebank

In this section, we compare the content of the resources described above with the encodings in the FTB-DEV corpus. We observed that around 97,4% of lexical units encoded in the corpus (excluding numbers and punctuation markers) are present in our lexical resources (in particular, 97% are in the dictionaries). While 5% of the tokens are unknown (i.e. not present in the training corpus), 1.5% of tokens are unknown and not present in the lexical resources, which shows that 70% of unknown words are covered by our lexical resources.

The segmentation task is mainly driven by the multiword resources. Therefore, they should match as much as possible with the multiword units encoded in the FTB. Nevertheless, this is practically very hard to achieve because the definition of MWU can never be the same between different people as there exist a continuum between compositional and non-compositional sequences. In our case, we observed that 75.5% of the multiword units in the FTB-DEV corpus are in the lexical resources (87.5% including training lexicon). This means that 12.5% of the multiword tokens are totally unknown and, as a consequence, will be hardly recognized. Another significant issue is that many multiword units present in our resources are not encoded in the FTB. For instance, many Named Entities like dates, person names, mail addresses, complex numbers are absent. By applying our lexical resources8 in a longestmatch context-free manner with the platform Unitex [START_REF] Paumier | Unitex 2.1 user manual[END_REF], we manually observed that 30% of the multiword units found were not considered as such in the FTB-DEV corpus.

Experiments and Evaluation

We firstly evaluated our system for standard tagging without MWU segmentation and compare it with other available statistical taggers that we all trained on the FTB-TRAIN corpus. We tested the well-known TreeTagger [START_REF] Schmid | Probabilistic Part-of-Speech Tagging Using Decision Trees[END_REF] based on probabilistic decision trees, as well as TnT [START_REF] Brants | TnT -A Statistical Part-of-Speech Tagger[END_REF] implementing second-order Hidden Markov. We also compared our system with two existing discriminative taggers: SVMTool [START_REF] Giménez | SVMTool: A general POS tagger generator based on Support Vector Machines[END_REF] based on Support Vector Models with language-independent features; MElt [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for state-of-the-art POS tagging with less human effort[END_REF] based on a Maximum Entropy model also incorporating language-dependent feature computed from an external lexicon. The lexicon used to train and test MElt included all lexical resources9 described in section 5. For our CRF-based system, we trained two models with CRF++10 : (a) STD using language-independent template features (i.e. excluding AC-based features); (b) LEX using all feature templates described in table 2. We note CRF-STD and CRF-LEX the two related taggers when no preliminary lexical analysis is performed; CRF-STD+ and CRF-LEX+ when a lexical analysis is performed. The lexical analysis in our experiment consists in assigning for each token its possible tags found in the lexical resources11 . Tokens not found in the resources are assigned all possible tags in the tagset in order to ensure the system robustness. If no lexical analysis is applied, our system constructs a TFST representing all possible analyzes over the tagset. The results obtained on the TEST corpus are summed up in table 5. Column ACC indicates the tagger accuracy in percentage. We can observe that our system (CRF-LEX+) outperforms the other existing taggers, especially MElt whose authors claimed state-of-the-art results for French. We can notice the great interest of a lexical analysis as CRF-STD+ reaches similar results as a MaxEnt model based on features from an external lexicon.

We then evaluated our MWU-aware tagger trained on the TRAIN corpus whose complex tokens have been decomposed in a sequence of simple tokens and relabeled in the IOB representation. We used three different sets of feature templates lead- With respect to the statistics given in section 5.3, it appears clearly that the evaluation of MWU-aware taggers is somewhat biased by the fact that the definition of the multiword units encoded in the FTB and the ones listed in our lexical resources are not exactly the same. Nevertheless, this evaluation that is the first in this context, brings new evidences on the importance of multiword unit resources for MWU-aware tagging.

Conclusions and Future Work

This paper presented a new part-of-speech tagger including multiword unit identification. It is based on a CRF model integrating language-independent features, as well as features computed from external lexical resources. It was implemented in a finitestate framework composed of a preliminary finitestate lexical analysis and a CRF decoding using weighted finite-state transducer composition. The tagger is freely available under the LGPL license 13 . It allows users to incorporate their own lexicons in order to easily integrate it in their own applications.

We showed that the tagger reaches state-of-the-art results for French in the standard evaluation environment (i.e. each multiword unit is already merged in a single token). The evaluation of the tagger integrating MWU recognition clearly shows the interest of incorporating features based on MWU resources. Nevertheless, as there exist some differences in the MWU definitions between the lexical resources and the working corpus, this first experiment requires further investigations. First of all, we could test our tagger by incorporating lexicons of MWU automatically extracted from large raw corpora in order to 13 http://igm.univ-mlv.fr/˜mconstan/research/software deal with low recall. We could as well combine the lexical analyzer with a Named Entity Recognizer. Another step would be to modify the annotations of the working corpus in order to cover all MWU types and to make it more homogeneous with our definition of MWU. Another future work would be to test semi-CRF models that are well-suited for segmentation tasks.

Table 3 :

 3 New features based on the MW resources

	4 A Finite-state Framework
	In this section, we describe how we implemented a
	unified Finite-State Framework for our MWU-aware
	POS tagger. It is organized in two separate clas-
	sical stages: a preliminary resource-based lexical
	analyzer followed by a CRF-based decoder. The
	lexical analyzer outputs an acyclic finite-state trans-

ducer (noted TFST) representing candidate tagging sequences for a given input. The decoder is in charge of selecting the most probable one (i.e. the path in the TFST which has the best probability).

  . Below is a sample of the FTB version annotated in POS.

	,	PONCT ,
	soit	CC	i.e.
	une	DET	a
	augmentation	NC	raise
	de	P	of
	1 , 2	DET	1 , 2
	%	NC	%
	par rapport au P+D	compared with the
	mois	NC	preceding
	précédent	ADJ	month

  . Figures on these dictionaries are detailed in table 4.

	Name	# simple forms	#MW forms
	DELA	690,619	272,226
	Lefff	553,140	26,311
	Prolex	25,190	97,925
	Organizations	772	587
	First names	22,074	2,220

Table 4 :

 4 Morphosynctatic dictionaries

Table 5 :

 5 Comparison of different taggers for French ing to three CRF models: CRF-STD, CRF-LEX and CRF-MWE. The two first ones (STD and LEX) use the same feature templates as in the previous experiment. MWE includes all feature templates decribed in sections 2 and 3. CRF-MWE+ indicates that a preliminary lexical analysis is performed before applying CRF-MWE decoding. The lexical analysis is achieved by assigning all possible tags of simple tokens found in our lexical resources, as well as adding, in the TFST, new transitions corresponding to MWU segments found in the lexical resources.

	Tagger	Model	ACC
	TnT	HMM	96.3
	TreeTagger	Decision trees 96.4
	SVMTool	SVM	97.2
	CRF-STD	CRF	97.4
	MElt	MaxEnt	97.6
	CRF-STD+	CRF	97.6
	CRF-LEX	CRF	97.7
	CRF-LEX+ CRF	97.7

Table 6 :

 6 Evaluation of MWU-aware tagging

This strategy somewhat resembles the popular approach of joint word segmentation and part-of-speech tagging for Chinese, e.g.(Zhang and Clark

, 2008). Moreover, other similar experiments on the same task for French are reported in[START_REF] Constant | Intégrer des connaissances linguistiques dans un CRF : application à l'apprentissage d'un segmenteur-étiqueteur du franc ¸ais[END_REF].

Unknown words are words that did not occur in the training data.

Hidden Markov Models of order n use strong independance assumptions: a word only depends on its corresponding tag, and a tag only depends on its n previous tags. In our case, n=1.

I: Inside (segment); O: Outside (segment); B: Beginning (of segment)

A semiring K is a 5-tuple (K, ⊕, ⊗, 0, 1) where the set K is equipped with two operations ⊕ and ⊗; 0 and 1 are their respective neutral elements. The log semiring is an image of the probability semiring via the -log function.

It is made of journalistic texts from Le Monde newspaper.

We excluded local grammars recognizing dates, person names and complex numbers.

Dictionaries were all put together, as well as with the result of the application of the local grammars on the corpus.

CRF++ is an open-source toolkit to train and test CRF models (http://crfpp.sourceforge.net/). For training, we set the cutoff threshold for features to 2 and the C value to 1. We also used the L2 regularization

algorithm. 11 Practically, as the tagsets of the lexical resources and the FTB were different, we had to first map tags used in the dictionaries into tags belonging to the FTB tagset.

f-score f = 2pr p+r where p is precision and r is recall.