Emmanuel Ec Kard
email: emmanuel.eckard@a3.epfl.ch

Lucie Barqu E
email: lucie.barque@univ-paris13.fr

Al E X Is N Asr

Benoît Sagot
email: benoit.sagot@inria.fr

Dictionary-Ontology Cross-Enrichment Using TLFi and WOLF to enrich one another

Keywords: Dictionaries, ontologies, WordNet

It has been known since Ide and Veronis [6] that it is impossible to automatically extract an ontology structure from a dictionary, because that information is simply not present. We attempt to extract structure elements from a dictionary using clues taken from a formal ontology, and use these elements to match dictionary definitions to ontology synsets; this allows us to enrich the ontology with dictionary definitions, assign ontological structure to the dictionary, and disambiguate elements of definitions and synsets.

Introduction

It has been known since Ide and Veronis [START_REF] Ide | Extracting knowledge-bases from machine-readable dictionaries: Have we wasted our time?[END_REF] that it is impossible to extract an ontology structure from a dictionary, because this information is simply not present in the dictionnary as it is in the ontology, not even implicitly. Human intuition that dictionary definitions contain an ontology-like structure stems from the world knowledge that we uncounsciously also take into consideration as context when we read them; since this world knowledge is not available to computers, automated extraction fails. For instance, one of the Wiktionary definitions for "lock" is "A segment of a canal or other waterway enclosed by gates, used for raising and lowering boats between levels". The term "canal" here is polysemous, defined either as "An artificial waterway, often connecting one body of water with another" or "A tubular channel within the body". A computer has no straightforward 1 way to tell which of the senses is relevant, while a human, linking "waterway", "boats" and "body of water" to a common semantic field through their experience of the world, will easily choose the boating sense over the anatomic one.

Since the closest thing to a world knowledge available to computers is precisely ontologies, it seems appealing to design an ontology-powered automated process to identify elements of ontological structure present in the dictionary. Clearly, the ontology information that we inject into the process should not excessively constrain it, lest we find that very information. Instead, the process should trigger a virtuous circle where clues from the ontology permit structuring the dictionary, which in turn enriches the ontology with dictionary information. Only under these conditions can the process be both practical and useful. The approach of nurturing interpretation of dictionary definition with ontology information can be considered from two points of view: a minima, as relaxing the strong hypotheses of "dictionary information only", under which Ide and Veronis showed extraction to be impossible2 ; a maxima, as injecting information into the process to mimick Human understanding of definitions through world knowledge.

Resources containing world knowledge can provide their information in different formats: for instance, dictionaries provide a number of definitions for each given word, with a distinct definition for each sense, and possibly hierarchies of sub-meanings; ontologies also provide short definitions, but mostly provide a structured set of relationships between senses, such as hypernymy, meronymy, etc. Although a wealth of resources exists in computer-readable form, resources become scarcer when we consider languages other than English. For instance, the general ontologies WordNet and FrameNet in English are hand-built, quite complete and available under a Free software-like licence [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF][START_REF] Fillmore | Background to Framenet[END_REF]. In French, on the other hand, the most notable alternatives are Euro Wordnet, which is quite complete and hand-built but only available under a commercial licence [START_REF] V O S S E N | EuroWordNet : a multilingual database with lexical semantic networks for European Languages[END_REF], and WOLF, which is available under a Free licence but is computer-generated from WordNet and incompletely translated. WOLF particularly suffers from the difficulty to adequately identify and translate polysemous words [START_REF] Sagot | Automatic Extension of WOLF[END_REF].

Since it provides a great deal of information while leaving room for improvement, WOLF constitutes both a resource and a testing bed for new algorithms and heuristics. As a resource, we can use it to generate clues for our heuristic; as a testing bed, contribute improvements to it. In this work, we attempt to enrich WOLF with dictionary definitions taken from the TLFi (Trésor de la Langue française informatisé). Practically, this comes down to assigning a dictionary definition to ontology synset elements, or to match ontology synsets with precise senses of a word in the dictionary. To achieve this result, we will explore the ambiguous graph structure implicitly formed by TLFi definitions. The heuristic attempts to connect two words h and H through a hypernymy relation by recursively roaming the definitions of words contained in a definition, concentrating on a hypernym; when successful, it stores the list of elementary segments that connect h to H. For instance, WOLF predicts that établissement (establishment) is a hypernym of académie (academy); indeed, in TLFi, these words are connected through certain senses of école (school): we find académie → école → établissement The word école is contained in the definition of académie and its own definition in turn contains établissement. Hence, académie leads to établissement as predicted by the clue provided by WOLF. Each of the words visited by the heuristic yields a number of different senses, each with its own definition which is examined separately. Hence, the hierarchy actually detects académie-6 → école-1 → établissement After a successful connection attempt, the pairs of unique senses immediately connected to each other (like académie-6 → école-1) are recorded and a frequentation counter associated with the sense pair is incremented. The result of the process allows us to tell which sense of école is expressed in the definition of académie that we considered.

Resources

TLFi

The Trésor de la Langue française informatisé (TLFi) [START_REF] Pierrel | Le Trésor de la Langue Française Informatisé : un dictionnaire de référence accessible à tous[END_REF] is the digital version of the Trésor de la Langue française, a large reference dictionary for French. The two main reasons why we have chosen the TLFi is that it is available in electronic form for research purpose and that most of its definitions belong to so-called definitions by genus and differentiae allowing us to extract genus (or hypernym of the defined unit). The TLFi has also a wide coverage with around 270,000 definitions. This study is restricted to nouns, for which the TLFi provide 100,493 definitions describing the meaning(s) of 35,498 nominal entries.

The senses of a lexical entry in TLFi are subdivised into a hierarchy ofs e n s e sa n ds u b s e n s e s , each complete with a unique identification number and a definition; for instance, the word bois (wood) comprises the following senses3 :

1.1.1 Ensemble d'arbres croissant sur un terrain d'étendue moyenne; ce terrain même. 2.1.1.1 Matière (racines, tronc, branches) qui constitue l'arbre (à l'exception du feuillage).

Identification of definitions genus

In the framework of the Definiens project, TLFi definitions of nouns were POS-tagged and processed to determine the genus of a given definition, that is, the noun or noun phrase that corresponds to the hypernym of the defined noun [START_REF] Barque | From the definitions of the trésor de la langue française to a semantic database of the french language[END_REF]. The Definiens heuristic relies on lexicosyntactic patterns that recognise nouns or noun phrases as possible genus candidates. More precisely, around fifty rules have been manually elaborated to identify geni in the TLFi definitions. Represented as finite-state transducers, the rules have been run on definitions previously labeled with part of speech tags by the NLP tool suite MACAON [START_REF] Nasr | Macaon: An nlpt o o ls u i t ef o r processing word lattices[END_REF]. The rule presented in figure 1 identifies nominal definitions that begin with a common noun (nc for nom commun in French), followed by a preposition and then another noun (left hand side of the rule). The right hand side of the rule proposes two possible geni for this kind definition: the first noun or a more specific phrasal genus constituted by the three elements (noun, preposition, noun) detected in the left hand side of the rule. This rule matches for example the definition of JODH-PURS presented below since it begins with a noun (pantalon) followed by a preposition (de) followed by a noun (équitation). The right hand side of the rule thus indicates two possible geni for this definition : pantalon (trousers) and pantalon d'équitation (horse riding trousers). JODHPURS = Pantalon d'équitation importé des Indes par les officiers anglais, ajusté du genou à la cheville et qui se porte sans bottes (Horse riding trousers imported from India by English officers, tight from knee to ankle and that is worn without boots.) ⇒ genus 1: pantalon, genus 2: pantalon d'équitation

The rule presented in figure 1 also matches the definiton of BOIS-1.1.1 given above. Nevertheless, geni like "ensemble de N" have to be treated in a particular way. Thus, the rules can also include lexical elements, as illustrated below in figure 2: when a definition matches the <rule> <lhs> <elt cat="nc"/> <elt cat="prep"/> <elt cat="nc"/> </lhs> <rhs> <genus><elt num="1"/></genus> <rhs> <genus> <elt num="1"/> <elt num="2"/> <elt num="3"/> </genus> </rhs> </rhs> </rule> sequence ensemble de/d' + nc (set of), the selected genus is not ensemble but the common noun that follows the preposition. The noun is moreover applied to the function "set of". <regle> <lhs> <elt lex="ensemble"/> <elt cat="prep"/> <elt cat="nc"/> </lhs> <rhs> <function><elt num="1"/></function> <genus><elt num="3"/></genus> </rhs> </regle> When the rules propose multiple geni for a given word sense, as in the rule presented in figure 1 above, the genus that is selected is the most specific one, provided that this most specific genus is classifying (i. e. appears as a genus in at least another definition). In other words,thegenus that is nor too specific nor too general is assumed to represent the most accurate genus. In the JODHPURS example, the genus pantalon d'équitation (horse riding trousers) is more specific than pantalon (trousers) but the processing of the whole corpus tells us that pantalon d'équitation appears only once, in the definition of JODHPURS, whereas pantalon appears in the definition of eighteen word senses (BLUE-JEAN, SAROUAL,...) intheTLFi. This automatic process, that consists in counting every possible geni of every definitions through the corpus, allows us to obtain the data described in table 1b

Adaptation of the sense hierarchy to limit ambiguity

The number of distinct senses can be high, and the differences between some of them can be quite subtle. For instance, the verb "to dive" distinguishes the senses "move briskly and rapidly downwards" and "being directed downwards". TLFi also records unusual or archaic senses of words: for instance, the term fourchette ("fork") lists the chess configuration, which might not be the first to spring to mind, as well as an archaic vernacular word for "bayonet".

In TLFi, the different senses of a word are organised in a hierarchy of sense numbers, such as "1", "2.3.1", etc. Senses with more decimals in their sense number are children of the parent sense, i.e. variants of the parent sense in a particular framework. Senses with 4 or more decimals in their sense number tend to be very specific senses, with long definitions. To avoid hyper-correction, we deem it adequate to trim this sense hierarchy, as the fine granularity achieved by human lexicographers is not a realistic goal for our automatic system [START_REF] Ide | Making sense about sense[END_REF].W e devise two simple schemes to this purpose: the "cut" scheme simply ignores all definitions whose sense number bears more than a given number of decimals; and the "merge" scheme deletes all definitions whose sense number bears more than a given number of decimals, but concatenates their definition to that of their direct parent. For instance, "cut 2" will retain senses "1", "2.1" and "3.1", but will eliminate senses "1.2.1", "2.1.1", "3.1.2.1", etc.; and "merge 1" will retain senses "1" and "2", and will eliminate sense "2.1" and "2.3.1.1" after concatenating their definition to the definition of sense "2". In cases where definitions are merged, their geni are stored in a vector, which allows us to take them into consideration one by one.

WOLF

WOLF (WOrdNet Libre du Français) 4 is a French-language ontology, automatically built from the Princeton WordNet (PWN) and various other resources [START_REF] Sagot | Automatic Extension of WOLF[END_REF]. Monosemous literals in the PWN 2.0 were translated using a bilingual French-English lexicon built from various multilingual resources. Polysemous PWN literals were handled by an alignment approach based on a multilingual parallel corpus. The synsets obtained from both approaches were then merged. The resulting resource, WOLF, preserves the hierarchy and structure of PWN 2.0 and contains the definitions and usage examples provided in PWN for each synset. Although new approaches are currently being used for increasing its coverage [START_REF] Hanoka | Wordnet creation and extension made simple: A multilingual lexicon-based approach using wiki resources[END_REF], WOLF is rather sparse, as information was not found for all PWN synsets by these automatic methods. Indeed, one of the difficulties in completing WOLF is to disambiguate the words contained in its synsets as to allow a correct translation, since the level of polysemy is high.

In this work, we used the version 0.2.0 of the WOLF, in which 46,449 out of the 115,424 PWN 2.0 synsets are filled with at least one French literal. WOLF 0.2.0 contains 50,968 unique literals which take part in 86,235 (literal, synset) pairs, i.e., lexical entries (to be compared with the 145,627 such pairs in the PWN 2.0). Approximately half of these pairs are nouns, i.e., belong to nominal synsets.

Since the WOLF was created automatically using several distinct techniques, each (literal, synset) pair is associated with the set of techniques that suggested its creation, together with a technique-specific confidence measure. This information is used for filtering out (literal, synset) pairs with the lowest confidence scores. We defined two filters: a medium filter, which retain more candidates, and a strong filter, which retain only the most reliable candidates (cf. figures in the next section).

Using hypernymic paths for synset-definition matching

Our aim is to enrich WOLF and TLFi with one another, entailing that we need to assign specific definitions to given WOLF synsets. These synsets, or sets of synonyms, contain words that share a same meaning, but this meaning is yet not explicitly determined. As such, these words are ambiguous with respect to TLFi, and it is not straightforward to decide which of the TLFi definitions should be associated with them, if any. To solve this issue, we propose to use the two resources and compound them with a heuristic.

The heuristic attempts to connect two words with a hypernymy relation, and stores the senses through which the connection goes in case of success. At each step, a definition is associated with hypernym candidate words -typically the head of the genus of the TLFi definition, provided by a pre-processing of TLFi (see section 2.1.1 ; the senses of this word are explored recursively in a breadth-first search until the goal is reached.

The WOLF hypernymy hierarchy provides us with numerous hyponym-hypernym couples, including measures of confidence for these couples. The heuristic processes all these couples, storing the elementary steps that constitute successful hypernymy paths, and keeping track of their frequentation.

The nature of dictionary definitions -short bursts of text completely independent from one another -prevents us from using machine learning techniques. Instead, we take advantage of the graph structures that are explicitly expressed in the ontology, and to some extent implicitly in the dictionary. Given a word h and a hypernym H of h, we use a graph exploration technique to connect senses of h and H. We then record pairs to constitute the path between h and H. This provides us with a set of word sense pairs that TLFi puts in direct hypernymy relation. We can then use these pairs to populate WOLF: if two words w and W are deemed to have definitions d and D in direct hypernymy according to TLFi, and belong to synsets s and S in WOLF, these synsets also being in the hypernymy relation, then we cans a f e l yi d e n t i f yd to s and D to S.

To disambiguate the hyponyms of an (h, H) pair, we explore the graph by hypernymic ascent: we consider the different senses h 1 ,...,h n that TLFi provides for h, and attempt to connect each of them to any of the senses of H. Inspired by [START_REF] Navigli | Using cycles and quasi-cycles to disambiguate dictionary glosses[END_REF], we propose a connection scheme whereby we jump from one word to a word of its definition, iteratively, until we reach the target H. In our implementation of the hypernymic ascent scheme, we select the genus of the definition of a word (that can also be considered as its hypernym) to carry on the next iteration step, taking advantage of the preprocessing performed in the Definiens project [START_REF] Barque | From the definitions of the trésor de la langue française to a semantic database of the french language[END_REF].

This process is illustrated in figure 3. In the left hand part of the figure, we have represented the TLFi ambiguous structure. In this figure, the dots represent word senses while ellipses represent words. An ellipse that contains two dots therefore represent a polysemous word that has two possible different senses. An arrow linking a sense s (a dot) to an ellipse w (a word) indicates that the w is a hypernym of s. The problem, of course, is that we do not know which sense of w is actually the hypernym of s.

The right hand side of the figure represents the WOLF synset structure. Synsets are represented as rectangles while dots represent word senses. It must be noted that, in WOLF, word senses are not associated with definitions. In case of a polysemous word such that one of its senses is part of a synset, we do not actually know which sense it is. The arrows between rectangles represent the hypernymic relation.

In our example, we can extract from the WOLF subgraph that one sense of abordage has as a hypernym one sense of action although we do not know which sense of abordage nor which sense of action are linked by this relation. This is where the hypernymic ascent comes into play by looking, in the TLFi graph, for a path that links one sense of abordage with one sense of action.

The result of the hypernymic ascent is represented in figure 3. A path relating one sense of abordage to the word action has been discovered, it goes through a given sense of assaut (assault) as well as a given sense of attaque (attack). The number that labels the arcs between two senses corresponds to the number of paths that go through this arc.

Hypernymic ascent described can fail for several reasons. The main ones are described below:

1. Either the hypernym of the hyponym in an (h, H) pair extracted from the WOLF is absent from the TLFi. When used with the medium filter, a total number of 86, 636 (h, H) couples are extracted from the WOLF. For 49, 908 of them, both the hyponym and the hypernym are present in the TLFi. When the strong filter is used, 47, 858 couples are extracted out of which 24, 443 have both their hyponym and hypernym present in the TLFi. (b) Non standard definition. Although TLFi definitions generally follow a genus differentia schema some of them do not, some senses are defined, for example, by means of synonyms. In such cases the identification of the genus in the definition fails.

3. The (h, H) pair extracted from WOLF is incorrect. In such a case, a path can be found which contains at least one incorrect arc.

When the process actually succeeds, it can be the case that several paths are found that link h to H. A crude but quite effective way to deal with this situation is to select the shortest paths.

With the strong filter on WOLF hypernym couples (supposedly the most reliable set of (h, H) pairs given as clues), the success rate for connections is 21%; this falls to 18% with the medium filter (more details in table 2: for the strong and medium filters on WOLF (strong is the strictest and produces the most reliable couples), we give the number of words to explore, the number of senses yielded by the words, the number of successful connections, and the success rate of the connection attempts. The low success rate is ultimately neither a surprise, since a successful connection on one particular hyponym-hypernym pair is subject to many imponderables, nor a severe hindrance to our endeavour, since it is the accumulation of the elementary components yielded by the successful connections that constitutes our result. Therefore, success rates around 20% are both well explained, and quite fit for our purpose.

It is worth noting that the scheme described above does not generalise as to disambiguate the hypernym in the (h, H) couple as well. This is ultimately due to a fundamental asymetry between the definitions of h and H: though the hyponym is often defined in terms that ultimately lead to the hypernym (either directly or through other definitions), the converse is not true since the hypernym H contains no information leading to the hyponym h.F o re x a m p l e ,a clue tells us that "snake" is the ultimate hypernym of "naja". The direct hypernym of "naja" is "cobra", which has several senses; only one of these senses has "snake" for hypernym, allowing us to discard cars and helicopters as candidate semantic fields. However, we have no way to determine which sense of "snake" is relevant (see figure 5).

Naja Cobra (

? ? Figure 5: Ambiguous hypernym One could attempt to reverse the hypernymic ascent into a hyponymic descent. However, this cannot be done simply by backtracking the path found during the hypernymic ascent, since the path is then completely determined. Hyponymic relationships linking TLFi dictionary definitions together should be available independently from the previously performed hypernymic ascent, for the hyponymic descent scheme to be viable. Unfortunately, this information is not present in TLFi. It is not possible to efficiently recreate this information by an exploratory preprocessing. For instance, envision a couple of direct hyponym-hypernym (w, W ), such as one of the w i is defined as being a kind of W ; a pre-exploration of these relations would accurately detect that w i is a hyponym of one of the W 1 ,...,W n , but it would have no direct way to tell the relevant W i . In consequence, it is impossible to tell one W i from another with this method, making hyponymic descent impractical with TLFi alone.

In summary, existence of quasi-hypernymic information in the form of geni of definitions featured in TLFi makes hypernymic ascent possible; absence of similar hyponymic data in definitions (like examples would partially provide) makes it impossible in practice to reverse the scheme.

Experiments

In order to measure the performances of the method, we ran it over two samples of 48,188 and 23,291 clues respectively (see table 2). After completion of the task, we randomly choose one hundred of the elementary hyponym-hypernym pairs and manually checked whether the chosen senses for the hyponym and the hypernym are relevant i.e. we answer the question : "is H an appropriate hypernym of h?". The answer is yes for the "homme-10 / mâle-1" pair given below and no for the "verbe-4 / expression-1" pair :

• homme-10 = Mâle adulte de l'espèce humaine (adult male human) / mâle-1 = Individu appartenant au sexe qui possède le pouvoir de fécondation We find a 45% accuracy in the tested sample. Given the average polysemy of 4.03 for Central Components in our sample, a random baseline will yield performance in the order of 25%; with our 45% accuracy, we are therefore significantly higher than the baseline.

The frequency of a segment (the number of times a segment appear in a successful path) did not correlate with the correctness of the segment. Instead, they tend to correlate with how high the segment is in the ontology, and thus to how general or abstract a segment is: many hypernymic paths tend to feature them as they climb towards the root oft h eo n t o l o g y . U s i n g them as an indicator for the correctness of a segment will need some kind of normalization with respect to the abstractness of the segment.

In order to get a better understanding of what happens during the hypernymic ascent, we present below a few examples of partially successful or failed paths.

academy -establishment, an unexpected and convoluted connection:

We have seen a correct connection of "academy" to "establishment", through an adequate meaning of "school". Nevertheless, "academy" has no less than 15 meanings in TLFi. Notably, académie-18 is defined as "house of gaming or pleasure" 5 . This triggers a search through the heavily polysemic word maison (28 definitions) which eventually leads to "establishment" through académie-18 → maison-41 → bâtiment-11 → grange-4 → établissement Interestingly, all of the segments yielded by this search are actually valid. This is a good illustration of the fact that the connection of the terms of the WOLF clue is a mere pretext to the research of elementary segments: it does not matter much that the connection has taken a detour, as long as the elementary segments are valid -it can in fact yield more segments to enrich our collection.

baboon -animal, a connection through irrelevant definitions: WOLF predicts that animal (animal) is a hypernym of babouin (baboon); indeed, in TLFi, these words are connected through certain senses of singe (monkey) and voyageur (traveller): we find babouin-1 → singe-24 → voyageur-14 → animal By examining the definitions of these senses, we see there that the word voyageur ("traveller"), perhaps surprising at a first glance, is in fact taken in its acceptation of "moving animal" 6 ;o n the other hand, the word singe ("monkey" or "ape") is taken in its unusual and little-known acceptation of "surnumerary passenger"7 , which is clearly not relevant in the context 8 .T h i s case has successfully connected "baboon" to "animal", yet it yields two segments, babouin-1 → singe-24 and singe-24 → voyageur-14, that are both incorrect.

Similarly WOLF predicts that adonis (adonis) is a hyponym of mâle (male). One of the connections found is adonis-7 → papillon-3 → personne-1 → individu-11 → homme-10 → male

Starting with the entomological sense of "adonis" (a Lycaena butterfly), we jump to "butterfly", but in the sense of "socialite"; from there, we follow a foreseeable path through "person", "individual", "man" and eventually "male". Here, the segment adonis-7 → papillon-3 is false, though the others are correct. Obviously, the overall path connecting the terms of the WOLF clue makes little sense to the Human eye, but this is less problematic than incorrect segments. The overall path is merely a pretext to the research of elementary segments. By contrast, another path found for the same clue is adonis-8 → nom-30 → partie-31 → individu-11 → homme-10 → male which makes more sense, but does not yield more correct elementary segments than the previous example.

steal mill -factory, a trivial connection: WOLF predicts that aciérie (steal mill) is a hyponym of usine (factory); indeed, in TLFi, the first and only definition of aciérie is "factory where steal is manufactured"9 , entailing that the connection is direct and trivial. Since the term usine has seven different definitions on TLFi, and since our heuristic leaves the ultimate hypernym ambiguous, it is impossible to select which sense of usine is relevant. Thus, in spite of a successful connection, this path yields no useful segment.

poster -worker, an erroneous WOLF clue: WOLF predicts that affiche (poster) is a hypernym of ouvrier (worker), a rather counter-intuitive pair; our heuristic manages to finda convoluted path that connects these two words, but it is clear that integrity of the semantic field has been lost en route. The connection path goes affiche-8 → action-2 → mise-72 → investissement-1 → manoeuvre-1 → ouvrier

The word mise is here taken as "stakes in a gamble", leading to "investment" taken in its economic sense; the sense of "investment" then switches to the military term for "surrounding an enemy", yielding the word manoeuvre ("manoeuver"); manoeuvre then switches to its meaning of "unqualified worker", eventually completing the connection. Yet, the segments mise-72 → investissement-1 and investissement-1 → manoeuvre-1 are incorrect.

Conclusions

We have described an exploration scheme of how the hypotheses of Ide and Veronis can be relaxed as to make it possible to automatically align a dictionary and an ontology. We use "clues" extracted from an ontology to search consistent paths in the dictionary linking a hyponym to a hypernym, recording the intermediary steps that form the overall path. We attempted this using WOLF and TLFi, taking advantage of the TLFi dataset that was made available to us.

This "hypernymic ascent" scheme yields a high rate of connection failures, which is not in itself a problem as these connections are a pretext to recording the elementary segments that form the connection. Nevertheless, this indicates that relying on Central Components to in the hypernymy chain is not very efficient in the context of a natural language dictionary. We could envision better performances using more rigidely formatted dictionaries and less naive approximations for the hypernym of a definition than merely using its Central Component.

Another issue is that words close to the root of the ontology tend to be very fundamental and highly polysemic. Therefore, a connection that passes through them is likely to have lost its semantic integrity. The yields semantically inconsistant segments, thereby generating noise.

In spite of the many difficulties that we encounter with the data and the naive nature of some elements of our system, we still managed to obtain a 45% accuracy on a randomly selected sample, significantly above the random baseline. This makes our system suitable as a weak classifier as it is, and leaves much room for improvement using more rigidely formatted and self-consistent data, better management of word inflexions, and refined selection of definition features beyond mere central components.

Figure 1 :

 1 Figure 1: Example of a syntactic genus extraction rule

Figure 2 :

 2 Figure 2: Example of a lexico-syntactic genus extraction rule

Figure 3 :

 3 Figure 3: TLFi ambiguous structure (left) WOLF structure (right)

Figure 4 :

 4 Figure 4: Result of the hypernymic ascent

• verbe- 4 =

 4 Expression verbale de la pensée (à l'oral ou par écrit) (verbal expression ofthethought) / expression-1 = Action d'extraire d'un corps le liquide qu'il contient (extraction of liquid from a substance)

Table 1 :

 1 e l o w . A ss h o w ni n Geni extracted from the TLFi this table, the 13,924 classifying geni are composed of 5,578 simple nouns (e.g. conifère (conifer), formule (formula), . . . ) and 8,346 phrasal nouns (e.g. conifère de grande taille (tall conifer), courte formule (short formula); . . . ). Let's recall that phrasal geni are very interesting in that they "naturally" disambiguate ambiguous forms (cf. carte vs carte géographique (map) and carte à jouer (playing card)). The 8,346 phrasal geni that have been yet detected are based on only 1,754 distinct nominal heads and more than 90 percent of them are included in the simple nouns set. The total number of words to disambiguate is therefore equal to 5,578 simple nouns plus 175 heads of complex nouns that are not already included in the simple geni set. Most of these geni are ambiguous, for an average of 4 senses per genus.

	Nominal words	35,498
	Nominal word senses 100,493
	Distinct geni	17,204
	Classifying geni :	13,924
	Simple nouns	5,578
	Phrasal nouns	8,346

Table 2 :

 2 ). Connection attempts through hypernyms between two given words in hypernymic relationship.

		words	senses	success success rate
	medium 48,188 109,306	8,787	18.23%
	strong	23,291	52,408	4,916	21.11%

Recognising a common semantic field for two segments of text that share few ornocommonwordsgoesbeyond mere co-occurrence count; it is feasible, but requires sophisticated strategies such as latent semantics, for instance, and is difficult on small samples.

Several studies proposed automatic or semi-automatic methods to develop lexical hierarchies from dictionary data, e.g.[START_REF] Chodorow | Extracting semantic hierarchies from a large on-line dictionary[END_REF][START_REF] Navigli | From glossaries to ontologies: Extracting semantic structure from textual definitions[END_REF].

"Wood" 1.1.1 Set of trees growing on a medium-sized area of land; said terrain. 2.1.1.1 Matter (roots, trunk, branches) that constitute a tree (except the foliage). This particular case is provided here to examplify definition numbering, without prejudice of further questions, like whether the "said terrain" metonymy should ideally be numbered separately. In the Princeton Wordnet, only the first half of this definition appears at all.

http://alpage.inria.fr/~sagot/wolf.html

maison de jeu ou de plaisir

The definition for voyageur-14 gives "Animal roaming its natural habitat (air, sea, ground), particularly migratory birds" (Animal se déplaçant dans son milieu naturel (air, mer, terre); en particulier, oiseau migrateur.)

The definition for singe-24 gives "Traveller installed on the upper floor out of a lack of space in the inside of a public car" (Voyageur installé sur l'impériale faute de place à l'intérieur d'une voiture publique.)

One set of experiments considered ignoring archaic meanings, as well as all specialised meaning marked by a domain tag in TLFi, to aleviate ambiguity somewhat; this did not yield significant improvement in performance.

Usine où se fabrique l'acier

Acknowledgments

This work has been funded by the French Agence Nationale pour la Recherche, through the project EDYLEX (ANR-08-CORD-009).


Marie Rebouah

Grégory Chagnon

Denis Favier

Development of constitutive equation of filled silicone architectured membrane

  L'archive ouverte pluridisciplinaire

Development of constitutive equation of filled silicone architectured membrane M. Rebouah & G. Chagnon & D. Favier Université de Grenoble/CNRS, Lab 3SR, Grenoble, France ABSTRACT: Architectured membranes can be developed in order to mimic living tissues. The main point is to generate anisotropic membranes that can endure large deformations. In this way, crenellated membranes are elaborated with a filled silicone rubber. The aim of this work is to develop a constitutive equation which describes the mechanical behavior of such architectured materials. Membranes with different crenel orientations are elaborated and tested. The architectured membranes endure the same phenomena as the bulk silicone, they are made with, i.e. principally the Mullins effect for this filled silicone. This phenomenon must be taken account in the modeling. An equivalent constitutive equation is built for the architectured membrane by taking into account the mechanical behavior of the silicone and the geometrical parameters of the crenelated membrane. First, a constitutive equation is chosen to describe the core of the membrane. Second, this equation is adapted to the behavior of the crenels and third a coupling term describing the interactions between the crenels and the membrane is developed. Finally, the model is validated on experimental data.

INTRODUCTION

Architectured materials take a place more and more important in many applications due to their specific properties including mechanical properties [START_REF] Bouaziz | Heterogeneous and architectured materials: A possible strategy for design of structural materials[END_REF]. It exists several types of architectured materials, for instance some materials are architectured due to their microstructure (grain size, polymer chain design, state of crystallization), for metals this strategy operates at scales between 1nm and 10 µm. In other way architectured materials are also composed of the association of several materials (hybrid material) and of geometrical arrangements. This architectured materials allow to build multifonctionnary material [START_REF] Brechet | Architectured materials: Expanding materials space[END_REF][START_REF] Ashby | Designing architectured materials[END_REF][START_REF] Bouaziz | Geometrically induced strain hardening[END_REF]. For instance they can be used in many medical applications by means of their ability to exhibit anisotropic behavior. Natural material and particularly soft tissues are architectured materials [START_REF] Dunlop | Multilevel architectures in natural materials[END_REF]. It is proposed in this paper to study an architectured membrane of filled silicone. [START_REF] Meunier | Contribution la conception, l'experimentation et la modélisation de membranes hyperélastiques architécturées anisotropes[END_REF] developed a model and experimental data of an architectured membrane, nevertheless the study is limited to an unfilled silicone rubber [START_REF] Meunier | Multiscale approach to model the mechanical behaviour of heterogeneous hyperelastic membranes[END_REF], this rubber is perfectly hyperelastic but suffers from bad fracture properties which makes it difficult to use in real applications.

In this paper it is chosen to use a filled silicone rubber. Due to the fillers this material presents good fracture properties nevertheless it presents too non linear phenomena. The Mullins effect is the prevailing phenomenon into the used material Machado et al. (2012a), thus the other non linear phenomena as the hysteresis or the relaxation are neglected. A model has already been developed to describe the behavior of this filled rubber silicone for membrane [START_REF] Rebouah | Anisotropic mullins stress softening of a deformed silicone holey plate[END_REF]. The aim of this paper is to study the behavior and to build an equivalent model for a filled silicone architectured membrane. The architectured membrane is composed of a flat membrane and crenels on the upper and lower surfaces of this membrane. As described by [START_REF] Meunier | Contribution la conception, l'experimentation et la modélisation de membranes hyperélastiques architécturées anisotropes[END_REF] the orientation of the crenels permits to control the anisotropy. The paper is constructed as follows. In Section 2, the experimental set up is described and the experimental results are presented. In Section 3, a theorical study presents the constitutive equation developed to analyze the behavior of the architectured membrane and a comparison with the experimental results is done. Finally, in Section 4 some conclusions are presented. 2 . An illustration is presented in Fig1. For each architectured membrane rectangular sample, a cyclic tensile test was processed. The samples are loading up to three different but fixed stretches of λ = 1.5, then λ = 2. after unloading, then λ = 2.5 after unloading and finally a reloading to λ = 2.5. The measurements are made by means of a 100N sensor which is synchronized to a three-dimensional image correlation (3D-DIC) system to evaluate the strain fields at any point of the surfaces. The specimens present a periodic structure, but boundary conditions can influence the behavior. Thus, a Representative Elementary Volume (REV) is defined in the middle of the sample. Due to the crenels orientations, the section of the specimens is varying with the angle, thus it is proposed to analyze the results using the tension

T T = F w (1)
where F represents the force and w the actual width of the sample. All experimental data are presented in Fig.

EQUIVALENT MODEL CONSTITUTIVE EQUATIONS

RTV3428 is a filled silicone rubber which presents several non linear effects like hysteresis, relaxation [START_REF] Machado | Analysis of the isotropic models of the Mullins effect based on filled silicone rubber experimental results[END_REF][START_REF] Rey | Influence of the temperature on the mechanical behavior of unfilled and filled silicone rubbers above crystallization temperature[END_REF] and induced anisotropy [START_REF] Machado | Induced anisotropy by the mullins effect in filled silicone rubber[END_REF]. As illustrated by [START_REF] Rey | Influence of the temperature on the mechanical behavior of unfilled and filled silicone rubbers above crystallization temperature[END_REF] the Mullins effect is the prevailing non linear phenomenon so this study focuses on the introduction of this phenomenon into the constitutive equation of the architectured membrane. The other phenomena are not taken into account in a first approach. Rubber like materials are described by means of an hyperelastic strain energy function that can evolve according to the Mullins effect. It is proposed to decompose the strain energy function W as the sum of the strain energies of the core of the membrane W(core-membrane) and of each crenel W(crenel-1),W(crenel-2), a last term taking into account the coupling between the two directions in the membrane W(coupling) is added.

W = W(core-membrane) + W(crenel-1) +W(crenel-2) + W(coupling) (2)

Core of the membrane

The model proposed by [START_REF] Rebouah | Anisotropic mullins stress softening of a deformed silicone holey plate[END_REF] which take into account the induced anisotropy by a stress softening is used, it is written as :

W(core-membrane) = W cc (I 1 , I 2 ) + 42 i=1 ω (i) F (i) W (i) cf (I (i) 4 ).
(3)

The [START_REF] Mooney | A theory of large elastic deformation[END_REF] strain energy function is chosen for W cc where I 1 , I 2 are the first and second strain invariants of the right Cauchy-Green strain tensor C and ω (i) represents the weight of each direction, F (i) is the Mullins effect evolution function and W

W (i) cf = K 2 I (i) 4 (ln I (i) 4 -1) (4)
Where K is a material parameter. The evolution function which depends on the first and fourth invariants with only one material parameter η is considered :

F (i) = 1 -η I 1max -I 1 I 1max -3 I (i) 4 max -I (i) 4 I (i) 4 max -1 I (i) 4 max I 4 max 4
(5)

The crenels

The crenels are processed with the same material as the core of the membrane, so the mechanical characteristics are the same. During the deformation, it can be considered that crenels are only submitted to tension-compression, it is estimated that there is no flexion in the crenels and that they can rotate, so they are modeled as bars. To determine the stress of each crenel, it is proposed to re-writte the Eq.( 3) in term of unidirectional components to represent the uniaxial tension endured by the crenels. That means that the second term of the anisotropic part of the strain density energy (Eq.( 3)) should be replace by a function of the elongation in the direction (E (i) ) of the crenel, that implies that the behavior of each crenel can be modeled only by means of the fourth invariant corresponding to its direction Let us define B c (i) as the left Cauchy-Green deformation tensor for each crenel. Since the crenel is only in tension-compression, B c (i) is defined in the basis of each crenel R (i) (E (i) ,y (i) ,z (i) ) where y (i) and z (i) are vectors which permit to obtain an orthogonal basis.

I (i) 4c = tr(C.(E (i) ⊗ E (i) ), i.e: W(crenel-i) = W(I 4 (i) c ) (6
B (i) c =    λ 2 E (i) 0 0 0 1 λ E(i) 0 0 0 1 λ E(i)    (7)
Where λ Ē(i) is the elongation of the crenel and depend of the fourth invariant

I (i) 4c = λ 2 E(i) .
. In the same way the first (I

(i) 1c ), second (I (i) 2c
) and fourth (I

(i) 4c ) invariant
are defined in the basis of each crenel R (i) By means of the Bazant theory it is known that the description of the behavior in only 1 direction modifies too the weight ω (i) c which has to be recalculated By considering, the projection of the 42 directions, it is possible to replace these directions by only one direction affected with a new weight ω = 0.21. The evolution function was described as the product of three terms (cf Eq.( 5)). The third term is useless with only one direction. According to the definition of the fourth invariant, the first and the second term are dependent since I 4c exists only for one direction. It is chosen to express the evolution function only with the fourth invariant, the evolution function is adapted as:

F (i) c = 1 -ηχ I (i) 4c max -I (i) 4c I (i) 4c max -1 2 (8)
Where χ represents the intensity of the evolution function for one direction instead of 42. The intensity χ of the crenels evolution function must be of 0.5 to limit the rupture of slope.

Finally, the strain energy density of the crenel is directly expressed as:

W(crenel i ) = W cc (I (i) 4c ) + ωF (i) c W (i) cf c (I (i) 4c ) (9)
Nevertheless the comportment described previously is in fact for a membrane behavior, not for crenels, so due to the geometry of the architectured membrane a new quantity is introduced to evaluate the proportion of crenels on the upper and lower faces of the flat membrane β. According to the structure of the architectured membrane (Fig. 1) we deduce β = 1 3

Strain energy of coupling

It is proposed to develop a term to take into account the coupling effects between the crenels and the core of the membrane. The strain energy of the coupling term takes into account the shear induced by the crenels on the external faces of the core of the membrane, i.e. along the two directions Ē1 and Ē2 . Different coupling terms were proposed in literature. [START_REF] Reese | Finite element modelling of orthotropic material behaviour in pneumatic membranes[END_REF] developed a strain energy coupling between orthotropic directions composed by the product of terms isotropic and anisotropic or just anisotropic to control easily the influence of each term. [START_REF] Natali | Biomechanical behaviour of oesophageal tissues: Material and structural configuration, experimental data and constitutive analysis[END_REF] developed a term of coupling for living tissues by using the eighth and ninth invariant. [START_REF] Göktepe | Computational modeling of passive myocardium[END_REF] and [START_REF] Nerurkar | Modeling interlamellar interactions in angle-ply biologic laminates for annulus fibrosus tissue engineering[END_REF] define also a constitutive equations by using the eight invariant to model living tissue as heart or annulus fibrosus of the intervertebral disc. It is proposed here to developed a coupling term by using the eight and ninth invariant too

W(coupling) = W(I 8 , I 9 ) (10)
Where I 8 allows to take into account the shear dependent of α and I 9 to norm the strain energy density, by adaptation of [START_REF] Spencer | Theory of Invariants[END_REF]:

I 8 = 1 2 C : E (1) ⊗ E (2) + C : E (2) ⊗ E (1) ) (11)
I 9 = E (1) .E (2) (12)
The strain energy density proposed is:

W(coupling) = C 8 (α) ln(1 + I 8 -I 9 )dI 8 (13)
Where C 8 (α) represents a parameter dependent on the orientation α between the crenels. According to the theory of the hyperelasticity the stress term of coupling is easily deduced. A quadratic function is used to describe the evolution of the coupling term with the angle

C 8 (α) = aα 2 (14)

Comparisons with experimental data

The total strain energy were implemented in a Finite Element code, the simulation results of cyclic tensile tests were compared to the experimental data as illustrated in Fig. 4. A good match with the experimental results for each orientation of the crenels is observed. For each mechanical parameters of the filled silicone the following values were used (C 1 = 0.065, C 2 = 0.045, η = 9, K = 0.41), this values are fitted only on a membrane of filled silicone. The only parameter fitted with the equivalent model is the parameter a for the quadratic function that describe the evolution of the coupling term (a = 0.0446).

CONCLUSIONS

Crenellated membrane of filled silicone were molded for different orientations of crenels. According to the literature, and previous work, an existing model to describe Mullins effect anisotropy is used. This model has been adapted to the crenel and a coupling term has been developed. Thus, every parts of the crenellated membrane can be evaluated. Several experimental tests were realized to validate the model. It has been observed that the coupling term could not be neglected on cyclic tensile test for different orientations of the crenels.

Figure 1 :

 1 Figure 1: Geometry of the architectured membrane

  2. The Fig.2(a) represents the evolution of the transverse elongation during the tensile test. The continuum line represents the theorical transverse elongation for a tensile test and the dashes line represents the transverse elongation obtained for different orientations α. For orientations of α = 0 • , 45 • , 90 • the transversal elongation is close to the isotropic material (λ 2 = 1 √ λ 1 where λ 2 is the transversal elongation and λ 1 the maximal principal elongation), but for α = 135 • , 180 • the transversal elongation does not match to the theory of uniaxial tensile test for isotropic material. The Fig.2(b) illustrates the evolution of the tension in function of the tensile elongation. It is observed that the orientation between the crenels α, influence the behavior of the material. The lower orientation requires the higher tension to deform the architectured membrane, at the opposite the higher value of α induce a lower tension. If α is superior to 135 • the tension necessary to deform the material decreases very slowly. This results are similar to Meunier (2011) and proves the existence of an induced anisotropy by the architectured membrane.

Figure 2 :

 2 Figure 2: Evolution of the transverse elongation (a) and tension (b) of the architectured membrane for α = 0 • , 45 • , 90 • , 135 • , 180 •

  strain energy of each direction. A different form from[START_REF] Rebouah | Anisotropic mullins stress softening of a deformed silicone holey plate[END_REF] is used

Figure 3 :

 3 Figure 3: Representation of a eighth the 42 directions of Bazant and Oh (1986) of reimplacement of the 42 directions by only one.

Figure 4 :

 4 Figure 4: Comparison of experimental tests (dotted lines) and FE simulation (full lines) of architectured membrane for different orientations of the crenels with coupling


S Descombes

B Dussoubs

S Faure

L Gouarin

V Louvet

M Massot

Editors V Miele

J.-M Etancelin

T Fevrier
email: tony.fevrier@math.u-psud.fr

C Huynh
email: chuhuynh@cisco.com

MACROSCOPIC MODELIZATION OF THE CLOUD ELASTICITY *

La gestion des ressources informatiques à la demande est une caractéristique propre à l'informatique en nuage. Pour que cela devienne une réalité, les fournisseurs de solutions en nuage ont besoin d'un modèle mathématique leur permettant de simuler l'allumage et l'extinction des ressources en fonction de la demande. Cet article propose une première étape de modélisation basée sur des outils issus de la simulation d'écoulements de fluides. D'une part, nous traiterons la question du temps de service dans l'optique de satisfaire simultanément les contraintes du fournisseur et du client. D'autre part, nous complèterons le modèle afin de simuler un comportement élastique des ressources du nuage. Ce comportement sera établi en temps réel et en fonction des demandes éventuellement concurrentes des clients. Nous intégrerons également au modèle des mécanismes utilisés en pratique dans les serveurs comme l'arrêt de requêtes trop longues. Ces problématiques seront illustrées par des simulations numériques menées à l'aide d'un schéma volume fini implicite.

Introduction

Is it necessary to define Cloud computing since it is heard and overheard? Cloud computing is about revolutionizing the Information Technology (IT) consumption behavior without questioning the underlying technologies, be it applications or infrastructure. Cloud computing is about doing more business with less i.e. fewer infrastructures (servers, network, and storage) and less effort (self service portal, orchestration).

It is important to notice that Cloud computing is enduring an inflection point; it's all about shared elastic capabilities [START_REF] Kuperberg | Defining and quantifying elasticity of resources in cloud computing and scalable platforms[END_REF]. Let's quote a Gartner's analysis that is often reflected in reality: "Vendors across many categories have grabbed the term and use it for marketing purposes. Hosting solutions that have a pay-per-userper-month pricing model, but without shared elastic capabilities, are being called cloud. As cloud is used to apply to an ever-widening set of external services without regard to sharing, elasticity and the other characteristics that set cloud apart, the term becomes even more unclear. Companies may buy these cloud services and then be surprised to find that they do not get the agility and cost savings promised by cloud computing. This has pushed cloud toward the Trough of Disillusionment." [START_REF] Smith | Hype cycle for cloud computing[END_REF] A first solution is a deal where each cloud consumer subscribes for a given amount of resources (number of virtual machines, network, and storage) and has a means of manually tune up and down consumption according to spotted demands. Such solution assumes that cloud consumers know exactly and timely what their needs may be. Unfortunately, reality check tends to prove the opposite: cloud consumer candidates are used to own IT resources and ignore completely how they are really used.

Our challenge is to fill the gap with a quantitative analysis. What if IT resources can be provisioned and deprovisioned automatically using a small set of variables, such as Service Level Agreement (SLA), reserved resource, elasticity ratio, total resource pool size? Unlike some research, not any assumption on application type is made. Our model is designed to be attractive to as many cloud providers as possible. There is no use of consumer behavior statistics, since our model has to be applicable to local cloud providers who do not have the same range of IT resources than Google, Amazon, and the likes.

SLA is narrowed to two values: upper and lower watermarks on the service time. It's tempting to reflect a more sophisticated model. However, the simpler is the model, the faster cloud provider will implement. The upper watermark is the maximum delay a cloud consumer may tolerate. Above this limit, a cloud consumer expects his counterpart to activate elasticity to absorb pressure. The lower watermark is the minimum delay a consumer is ready to pay for. Under this limit, a cloud consumer expects his counterpart to save costs by deprovisioning IT resources.

Reserved resource is an amount of IT elements that a cloud subscriber deems necessary to have permanently, no matter it is used or idle. Elasticity ratio is a number of IT resources that is provisioned and deprovisioned according to temporary needs. The total resource pool size is the total capacity set by a cloud provider. It is the sum of all reserved pools and the elasticity pool shared among all cloud consumers.

First, the model from Jaisson and de Vuyst is exposed and adjusted to the cloud context. Second, a mechanism is added to satisfy upper and lower service bounds. It consists in the optimization of a cost function. This allows us to handle concurrent requests in the cloud. A model considering the drop of requests when the server is saturated is also implemented. The last part is devoted to use our tool in order to attribute a first IT set to a consumer according to his forecast of consumption.

Adjustment of Jaisson-de Vuyst model to the cloud

Description of the initial model

The following model for multithreads systems has been developed by Jaisson and De Vuyst [START_REF] Jaisson | An innovating pde model based on fluid flow paradigm for multithread systems[END_REF]. It mimics the fluid flow behavior in a macroscopic way. Indeed, microscopic models become irrelevant when big amounts of data have to be scheduled and the cloud purpose is to fill up the virtual machines (VM) constituting it of requests to treat a lot of data. Moreover, it introduces a space variable to take into account memory and delay features of the transport of information. In the following, we reuse Jaisson's and De Vuyst's notations, see [START_REF] Jaisson | An innovating pde model based on fluid flow paradigm for multithread systems[END_REF].

Let us consider a system delivering services with a capacity φ o corresponding to the maximal requests flux it can encounter. A variable x ∈ ]0, 1[ representing the rate of completion of a task in the system is introduced. Thus, one can define the space and time dependant density ρ(x, t) of completed tasks at level x at any time t and then the total mass m(t) of requests in the system :

m(t) = 1 0 ρ(x, t)dx. (1)
The input rate of requests is denoted by φ i .

To derive the model equations, a mass balance is written. The variation of the current mass of requests being processed between two levels of completion w l and w r is the difference between the entering flux at w l and the leaving flux at w r :

d dt wr w l ρ(x, t)dx = ρ(w l , t)φ o m(t) - ρ(w r , t)φ o m(t) . (2)
Making w r tend to w l in (2) gives the following Partial Differential Equations (PDE):

∂ t ρ + v(t)∂ x ρ = 0, x ∈ ]0, 1[, t > 0, v(t) = φ o m(t) .
However this transport equation allows the velocity, v(t), to tend to infinity when the mass goes to zero that is physically impossible. That's why a limiter is used to have a maximal velocity equal to the system capacity φ o :

v(t) = φ o max(1, m(t))
.

The integration of the transport equation on space gives a mass conservation Ordinary Differential Equation (ODE). To complete the model, initial conditions at t = 0 on the flux and the mass and a boundary condition at x = 0 (input flux) are added. It comes:

∂ t ρ + v(t)∂ x ρ = 0, x ∈ ]0, 1[, t > 0, ( 3a
)
∂ t m = φ i (t) -ρ(1, t)v(t), t > 0, (3b)
v(t) = φ o max(1, m(t)) , (3c) ρ
(x, 0) = ρ 0 (x), (3d)
m(0) = 1 0 ρ 0 (x)dx ≥ 0, (3e) ρ(0, t)v(t) = φ i (t). ( 3f
)
In the context of the cloud, the evaluation of the service time of the system is an important issue. We denote by d(x, t 0 , x 0 ) the time for a request to be completed at level x given that it was at level x 0 at time t 0 . So the whole service time of a task at time t is defined by D(t) = d(1, t, 0) and d is transported at the velocity v(t):

∂ t d + v(t)∂ x d = 1, x ∈ ]0, 1[, t > 0, (4a) d(0, t, 0) = 0. ( 4b
)
A change of variable u = t -d in (4) gives the following homogeneous system over service time:

∂ t u + v(t)∂ x u = 0, x ∈ ]0, 1[, t > 0, (5a) u(0, t) = t, (5b)
D(t) = t -u(1, t). (5c)
The quantity of interest, D(t), is computed by solving simultaneously the two systems of equations ( 3) and ( 5) with the numerical scheme detailed in section 1.3.

Adjustment to the cloud

The cloud is made of an initial set of virtual machines (VM) which can be allocated on demand to cloud consumers. Each customer subscribes to a number of VM for a certain duration, typically a year, usually three years. Resignation can happen at any time (its obtention is explained later in Section 2.4). This number corresponds to a certain capacity φ o which belongs to the cloud consumer. Once assigned to a consumer, a VM is no longer available nor accessible to other clients. It is called multi-tenancy and implies that cloud consumers share the resources provided by the cloud provider with all the required confidentiality, integrity, and availability levels.

As a consequence, to each cloud user corresponds one system as above with its own capacity φ o and its own set of equations to solve: systems (3) and ( 5). There are as many independent systems as cloud consumers, since there are no communication between them. There are also a pool of unassigned VM that a cloud user may request according to its SLA and cloud provider commitment to elasticity (see Section 2.2). Without any client, the pool may be the whole capacity of the cloud provider. As clients keep coming, the pool size decreases, unless the cloud provider refills it by adding extra capacity.

In Section 2.3 the model will be enriched in order to integrate the possibility for the VM to drop requests when the service time is too long. It reproduces the usual behavior of servers for timeout requests.

Numerical scheme

Following [START_REF] Jaisson | Systèmes complexes gouvernés par des flux: schémas de volumes finis hybrides et optimisation numérique[END_REF], the system (3)-( 5) is solved by a Finite Volume method (see for example [START_REF] Eymard | Finite volume methods[END_REF]). The domain [0; 1] is discretized by N control volumes defined by [x j-1 2 ; x j+ 1 2 ] where x j+ 1 2 = jh, j ∈ {0, . . . , N } and h = 1/N . The cells centers are the points

x j = (j -1/2) h, j ∈ {1, . . . , N }.
The time discretization is ensured by an upwind implicit scheme with a time step dt n which is unconditionally stable and can be solved explicitly. Hence, for j ∈ {1, . . . , N }, the unknowns are meant to be approximations of the cell averages with t n = t n-1 + dt n for n = 1, . . . , N t and t 0 = 0:

ρ n j = 1 h x j+ 1 2 x j-1 2 ρ(x, t n )dx, (6)
m n j = 1 h x j+ 1 2 x j-1 2 m(x, t n )dx, (7)
u n j = t n - 1 h x j+ 1 2 x j-1 2 d(x, t n )dx. ( 8
)
Using the above notations, the full discretization of the system (3)-( 5) is given by the following scheme, with

λ n = dt n /h: v n = φ o max(1, m n ) , (9a)
ρ n+1 1 = ρ n 1 -λ n (ρ n+1 1 v n -φ n+1 i ), (9b)
ρ n+1 j = ρ n j -λ n (ρ n+1 j -ρ n+1 j-1 )v n , (9c)
m n+1 = m n + dt n (φ n+1 i -ρ n+1 N v n ), (9d)
u n+1 1 = t n+1 , (9e)
u n+1 j = u n j -λ n (u n+1 j -u n+1 j-1 )v n , (9f)
D n+1 = t n+1 -u n+1 N . (9g)

Numerical validation

The model is validated choosing different input request rates. In the following, we consider a 24 hour simulation with a time discretization of 1 minute (i.e. 1, 440 time-steps). For the spatial discretization, 1, 000 grid points are considered. The cloud consumer is using a cloud resource capacity of 120 requests per time-step. On Figure 1, the three input rates considered present a plateau of height 120, 150 and 200 requests per timesteps between 6 and 16 hours. In the first case, the system can process the whole input at its maximum speed whereas, for the others, the system is saturated and the service time increases. One can note that the bigger the amount of saturating requests is, the longer the service time takes to fall back to decent.

Service time optimization

The cost function

The easiest way to control the service time is to adjust the amount of resources allocated to a cloud consumer. In fact this time varies with the number of VMS and their computational characteristics. In our model, it means to vary φ o .

As service time is a key quantity in networks, several optimizations can be done. From an end-user point of view, the service time should not be higher than a given time denoted T max . For the cloud provider, it must be greater than T min in order to prevent quality overachievement and keep resources available for incoming cloud consumers. These bounds over the service time depend on each kind of requests. For example, for a basic web service we could choose T max = 3 seconds and T min = 0.1 seconds. For data archiving, it could be respectively 6 hours and 1 hour.

In the real life, there is no means for a cloud provider to predict the requests input rate. The best that one can do is to monitor it. Therefore, optimizations are performed at a certain frequency, depending on the kind of service. Requests are supposedly independent, most of the time. Things may change when customer gets angry and retries the same request over and over again. We are interested in controlling the service time over small time windows of length ∆t, regarding last input data available (such an assumption relates to the most of applications eligible to the cloud). We search for an optimal capacity φ * o ∈ ]0; φ o ] over ∆t time windows with the minimization of the following cost function:

J n (φ * o ) = t n +∆t t n (D(t, φ * o ) -T min ) 2 + (D(t, φ * o ) -T max ) 2 dt. (10)
We denote by φ * n o the capacity that realizes:

J n (φ * n o ) = Min φ * o ∈ ]0;φo] J n (φ * o ). (11)
Therefore, the evolution of the optimal capacity for a cloud consumer is defined by a time dependent piecewise constant function φ * o (t):

φ * o (t) = φ * n o if t ∈ ]t n ; t n+1
]. However switching on or switching off VM takes a certain time. So modifying capacity is not instantaneous. That is the reason why we introduce a delay δt before applying the optimal capacity. This optimal capacity function becomes:

φ * o (t) = φ * n o if t ∈ ]t n + δt; t n+1 + δt]. (12)
The capacity optimization influence can be observed on Figure 2. The service time is computed for three cloud consumers with identical inputs. One of them has his capacity optimized to have D(t) ∈ [0.5; 5]. In the first case, the client is running a constant low capacity and sees his service time exploding at t = 6 hours. In the second case, he is using all his VM and then obtains a constant low service time except at t = 15 hours where his system is lightly saturated. Finally, in the last case, optimization is performed every 20 minutes, the cloud consumer uses the elasticity of the cloud. One can observe that the service time is correctly placed between the bounds, the capacity is reduced when the input is quite low and increased when it is necessary. We have therefore the evidence that there is no need to commit to a too low service time and both client and cloud provider are better off switching off VM when they don't use them. Nevertheless, the cloud provider can not always deliver him the whole φ eo . Indeed, he can not provide more than the remaining free resources in the cloud. As in section 2.1, one can define the available capacity by a piecewise function:

Generalization to many cloud consumers

φ n av = Φ - c∈clients φ * n o,c . (13)
So if φ n av = 0, J is optimized on ]0; max(φ o , φ * n o )] (the cloud consumer can keep the extra capacity he has already used). Else we calculate the rest of capacity he can take to satisfy his φ eo :

φ o (1 + φ eo ) -φ * n o . If φ o (1 + φ eo ) -φ * n o ≤ φ n av , J is optimized on ]0; φ o (1 + φ eo )], else it is optimized on ]0; φ * n o + φ n av ].
An illustration of this algorithm is presented on Figure 3: there are two cloud consumers in the cloud. Each one owns a capacity of 120 and a free set a of capacity 12 is available. Both are authorized to take at most an extra capacity of 10% of their initial set (132). Clients don't have any reason to share the same numbers (120, 12, 10%) and the logic remains beyond 2 clients. Numbers are chosen for the sake of simplicity and clarity in the graphs. The same input (with a maximum of 132 requests per time-step) is launched by both, slightly before for the first client. As a consequence, he is the first to need an extra capacity: he takes all the available VM to satisfy his 10%. This relieves his service time which evolves in the expected interval. The second client becomes saturated later but no extra capacity is available until 16 hours. During this period, his service time grows and overpasses the upper bound. At 16 hours, the first consumer releases his extra capacity because of his input decrease. Thus the second one can take his 10% and stabilize his service time.

Add request cessation in the model

We also want to model the fact that web applications are typically designed to drop requests after a certain time delay. Such applications capture the end user behavior cancelling a request if an answer doesn't come back timely. Doing so, applications have the opportunity to catch up.

In this section, we integrate to our model a mechanism that lighten the servers workload: when the service time overpasses a certain threshold, the cloud must stop a chosen rate of requests. Let's note τ (t) the damping of requests transport and T th the threshold. It is assumed that the damping is uniform over the completion rate. Let τ (t) be equal to 0 when D(t) ≤ T th and be a positive constant elsewhere. To model this suspension phenomenon, an additional term appears in the mass balance [START_REF] Jaisson | Systèmes complexes gouvernés par des flux: schémas de volumes finis hybrides et optimisation numérique[END_REF] representing the part of the deleted mass between w l and w r :

d dt wr w l ρ(x, t)dx = ρ(w l , t)φ o m(t) - ρ(w r , t)φ o m(t) -τ (t) wr w l ρ(x, t)dx.
The flux equation becomes:

∂ t ρ + v(t)∂ x ρ = -τ (t)ρ(x, t), x ∈ ]0, 1[, t > 0, (14)
v(t) = φ o max(1, m(t)) . ( 15
) (16)
The requests density is still transported with the same velocity v but a damping factor when the service time is too high is added as a source term. Integrating this equation in space, the mass ODE reads

∂ t m = φ i (t) -ρ(1, t)v(t) -τ (t)m(t), t > 0. (17)
Regarding the numerical scheme, these new terms are treated implicitly.

We show the damping influence on Figure 4 where a cloud consumer is handled with different values for τ . The first case corresponds to previous results with no requests dropping. As one can see, the amount of input requests makes the client saturated between 12 and 19 hours. The use of requests cessation makes the service time below the threshold time T th during the saturation period. It decreases as strong as τ is high. We notice also that as much as τ is increasing, the system needs less and less drops.

Cloud consumer resources dimensioning

When a consumer subscribes to the cloud, he chooses different types of applications. These applications can be translated in an equivalent number of requests per time-step and more precisely in a forecasting of input for a certain time sample. Note that the real input can be different from this forecasting. The client may not know exactly what resources amount he needs for his applications, so we could use the model as a sizing tool.

First we assume that there is one cloud consumer to size in the cloud. As it is explained above, with his subscription, the client provides an estimation of the future input. The idea is to launch the optimization algorithm on this forecasting input, the first φ o being fixed to the total available cloud resources. The simulation gives a capacity profile from which we extract the maximum of capacity we propose to the client as the capacity he needs to handle his requests.

However if we want to size many cloud consumers, we can not give to everybody the cloud size to launch the first optimization. Indeed, nothing guarantees in this case that the sum of maximal capacities obtained remains in the limit of the cloud size. One solution is to size clients thanks to their estimation of input: each input mass is calculated (we integrate the input in time) and the part of the cloud received by the consumer is proportional to the mass he brings to the system. Then the system delivers to each cloud consumer the maximal capacity he could use for the real time input.

Conclusion

In this paper, the model from Jaisson and De Vuyst allowed us to make a first step in the modelling of the cloud elasticity. The way to modulate the IT resources was exposed: an optimization functional over the real time capacity was derived to satisfy not only the cloud consumer but also the cloud provider. Some validations tests were performed to show the usefulness of an "automatic" elasticity. The case of dropping requests was also considered when the system is saturated and we used our model to size a client (as a decision helper to a new client regarding an estimation of his input). Now, this work should be verified in a real case, and adjusted accordingly. In particular, the model could be adapted to get closer to the reality of cloud computing and should be tested on real data sets. Some improvements could also be made with the addition of a variance term on capacity in the functional to prevent the excess of capacity oscillations.

Figure 1 .

 1 Figure 1. Basic model validation.

Figure 2 .

 2 Figure 2. Capacity optimization influence.

Figure 3 .

 3 Figure 3. Two semi-shared ressources cloud consumers.

Figure 4 .

 4 Figure 4. Influence of request cessation, T th = 3T max .

* This work was supported in part by AMIES (http://www.agence-maths-entreprises.fr) and by the GDR CNRS Mathématiques et Entreprises (