Stéphane Huet
email: stephane.huet@univ-avignon.fr

Philippe Langlais

Identifying the Translations of Idiomatic Expressions using TransSearch

This document presents a case study relating how a user of TransSearch, a translation spotter as well as a bilingual concordancer available over the Web, can use the tool for finding translations of idiomatic expressions. We show that with some care on the queries made to the system, TransSearch can identify a fair number of idiomatic expressions and their translations.

Introduction

Idioms are expressions of a given language, whose sense is not predictable from the meanings and arrangement of their elements [START_REF] Mcarthur | The Oxford Companion to the English Language[END_REF]. For example, an expression like "to be hand in glove" meaning "to have an extremely close relationship" cannot easily been deduced from what a hand and a glove are. Some expressions are more analyzable than others; for instance, the meaning of the expression "fights like cat and dog" might easily be inferred by the senses of "cat" and "dog". This is not so for the expression "it rains cats and dogs". In this work, we are interested in identifying the translation of this second type of expressions.

Idioms -and more generally Multi-Word Expressions (MWEs) -pose significant problems for many applications of natural language processing since they are numerous in most languages and have idiosyncratic meanings that severely disturb deep analysis [START_REF] Sag | Multiword expressions: A pain in the neck for NLP[END_REF]. The problem of MWEs -and idioms in particular -is especially acute in the case of Machine Translation (MT) where a failure of the system to detect such expressions often leads to unnatural, if not hilarious outputs.

Therefore, one important component of an MT system is its lexicon of MWEs. This is true for rule-based MT systems as well as statistical MT (SMT) ones. Currently, state-of-the-art phrase-based SMT systems rely on models (pairs of phrases) that do not handle MWE specifically. Some authors have been trying to group multi-word expressions before the alignment process [START_REF] Lambert | Data inferred multi-word expressions for statistical machine translation[END_REF] or to add a new feature encoding the knowledge that a given phrase pair is a MWE [START_REF] Ren | Improving statistical machine translation using domain bilingual multiword expressions[END_REF][START_REF] Carpuat | Task-based evaluation of multiword expressions: a pilot study in statistical machine translation[END_REF]. This last work showed that using manually defined WordNet MWEs could improve MT.

Not only are idioms interesting for improving MT systems, they are as well notably known to pose problems to non-native persons. This is especially true when a second-language idiom is much different from its translation into the native language. For instance, French speakers might easily catch the English idiom "play cat and mouse" because its French translation "jouer au chat et à la souris" is literal in this case. On the contrary, they could find hard to understand "He couldn't say boo to a goose"3 because its translation into French "Il est d'une timidité maladive" (literaly "He is sickly shy") is completely different.

Idiomatic expressions are interesting for professional translators as well. In [START_REF] Macklovitch | TransSearch: What are translators looking for?[END_REF], the authors analyzed the most frequent queries submitted by users to the bilingual concordancer TransSearch. They found that among others things, users frequently queried idiomatic phrasal verb expressions, such as "looking forward to". Because they were expecting that the users would query idiomatic expressions, they did not investigate further this aspect of the logfile, but instead concentrated on analyzing the prepositional phrases (some of which being idiomatic) frequently submitted to the system.

In this paper, we study the problem of translating idiomatic expressions from a user perspective. We tried to identify the translations of a number of idioms in the Translation Memory (TM) of the new version of the bilingual concordancer TransSearch. Since many idioms have inflected forms, we show the impact of different strategies for querying the database. For instance, in the (idiomatic) expression "to keep oneself to oneself ", both the verb "keep" and the pronoun "oneself " can vary according to conjugation and inflection respectively, and verbatim queries may fail to identify relevant occurrences of the expression.

The remainder of the paper is organized as follows. Section 2 describes TransSearch, the Web application we employed in our experiments. Section 3 presents the data we used and how we submit queries to the TM system to find translations. Section 4 is dedicated to the evaluation of the translations proposed by the system, while Section 5 concludes and explores further perspectives.

TransSearch

TransSearch is a bilingual concordancer that allows its users to query large databases of past translations in order to find ready-made solutions to a host of translation problems. Subscribers of the system are mainly professional translators. A recent study of their query logs exhibits that TransSearch is used to answer difficult translation problems [START_REF] Macklovitch | TransSearch: What are translators looking for?[END_REF]. Among the 7.2 million queries submitted to the system over a six-year period, 87% contain at least two words. Among the most frequent submitted queries, several appear to be idiomatic, like "out of the blue" or "in light of ".

System Features

Made available since 1996 through a Web interface by the Université de Montréal [START_REF] Macklovitch | TransSearch: A free translation memory on the World Wide Web[END_REF], TransSearch has recently been improved to become not only a bilingual concordancer but also a translation finder [START_REF] Bourdaillet | TransSearch: from a bilingual concordancer to a translation finder[END_REF]. Figure 1 which displays the results for the query "is still in its infancy" exemplifies the new capabilities of the system. Where a simple bilingual concordancer (as were the previous versions of TransSearch) would only display a list of parallel sentences containing the query in their English part, the new version of TransSearch highlights for each sentence pair the French part associated with the query. Besides, this version displays on the left hand side the whole range of translations (automatically) found in the TM. For the first suggested translation, "en est encore à ses premiers balbutiements", three of the sentence pairs containing a variant of this translation (see the merging process described in Section 2.2) are displayed in context.

With respect to an ordinary bilingual concordancer, where the identification of translations in sentences is left to the user, we believe the new version of TransSearch dramatically improves usability, by displaying a general view of the TM content for a given query.

The previous query example has shown that the system is able to find results for queries with several words. The user can also submit more advanced queries to search discontinuous expressions. For example, Figure 2 displays the results for the query "make .. hair stand on end ". The '..' operator enables the user to indicate the system that occurrences of 2 words in the query (here "make" and "hair ") can be up to 5 words apart inside a sentence. Another operator '...' allows for searches without constraining the distance between two words. From a linguistic perspective, these two operators are useful since they enable the user to spot expressions where words may be separated by a few words, such as nominal groups in the examples of Figure 2. Besides, another advanced type of query is available in TransSearch: morphological expansions. The system considers all the morphological derivations of the terms associated with the '+' symbol, when retrieving sentence pairs. Figure 3 shows the results for the query "take+ no for an answer ". In this example, the interface displays expressions containing different inflected forms of the verb "take". This last operator is specially useful for morphologically rich languages like French or Spanish and allows the user to spot translations without taking care of their possible inflections.

By default, TransSearch searches for the given expression regardless of languages (French or English). In some cases however, it is necessary to specify the language, for instance in order to distinguish between the French and English words "tape" ("to hit" in French). Using the same mechanism, it is also possible to look up occurrences of a specific translation of a given query by filling at the same time the French and English fields of the query form. For example, a user can check that "les dés sont pipés" is a correct translation of "the dice are loaded " by looking at the same time at these two expressions into the TM sentence pairs.

Processing Steps

In order to suggest several translations for a given query, TransSearch performs several processing steps that we briefly describe hereafter. Many current computer-assisted translation tools mainly rely on sentence-level matching to exploit their translation memory. TransSearch operates at a finer-grained level using word alignment techniques, which are commonly used in SMT. The term translation spotting, coined by [START_REF] Véronis | Evaluation of Parallel Text Alignment Systems -The Arcade Project[END_REF] and relabeled here as transpotting, is defined as the task of identifying the target language word-tokens that correspond to a given source language query in a pair of sentences known to be mutual translations; it is a core step in the new version of TransSearch.

We call transpot the target word-tokens automatically associated with a query in a given pair of sentences. For instance in Figure 1, "en est encore à ses premiers balbutiements" and "soit encore tout nouveau" are 2 out of 14 distinct transpots displayed to the user for the query "is still in its infancy".

The method used to transpot queries in the retrieved sentence pairs is described in details elsewhere. In a nutshell, our transpotting algorithm uses statistical word-alignment models and enforces that the transpots identified are sequences of contiguous words. As mentioned in [START_REF] Simard | Translation spotting for translation memories[END_REF], contiguous tokens in the source language sentence tend to be aligned to contiguous tokens in the target language. This statement is confirmed by the good experimental results presented in the study of [START_REF] Bourdaillet | TransSearch: from a bilingual concordancer to a translation finder[END_REF].

Queries that occur frequently in the TM receive numerous translations using the transpotting methods described above, some being clearly wrong, some others being redundant (morphological variations of the same translation). We estimate that a user will focus on the 10 first translations presented, so we want to provide as many correct and diversified translations as possible at the top of the result page. Therefore, two postprocessing steps were introduced inside the TransSearch engine. The first one filters out bad transpots using supervised learning. A classifier was trained on a corpus where transpots were manually labeled as "good" or "bad", using features such as the ratio of grammatical words inside the hypothesized transpots. Once transpots have been filtered out, the second step merges those which are different inflectional forms of the same sequence of canonical words. For instance, "au nom du" and "au nom des" will be considered as similar, since "du" and "des" are contractions of "de + le" and "de + les" respectively, where "le" and "les" are definite articles. Furthermore, as it was noticed that translations that differ only by a few grammatical words or punctuation marks, like "de la part de" and "part de" are often redundant for the user, those are combined as well. At the end of this second post-processing step, only the most frequent transpot of each merged set is displayed on the left hand side of the user interface (see Fig. 1 to 3). These transpots are shown as a list sorted in the decreasing order of their transpotting frequency.

Methodology

Resources

Translation Memory The largest TM used in TransSearch comes from the Canadian Hansards, a collection of the official proceedings of the Canadian Parliament. For our experiments, we used an in-house sentence aligner [START_REF] Langlais | A system to align complex bilingual corpora[END_REF] to align 8.3 million French-English sentence pairs extracted from the 1986-2007 period of the Hansards. This bitext was indexed with Lucene4 to form our TM.

Idiom Lexicon Classifying an expression as idiomatic or not is not an easy task. Therefore, we resorted to the phrase book [START_REF] Piat | It's raining cats and dogs et autres expressions idiomatiques anglaises[END_REF] written by Jean-Bernard Piat, a translation teacher as well as a translator. This book oriented towards general public market provides a list of 1,467 idiomatic expressions in both languages (French and English) categorized by subjects (e.g. human body).

According to the author, the expressions were chosen because they are frequently used. A minority of these expressions are expressed in an informal language (e.g. "to be well-upholstered "). He also mentioned that it happens sometimes that an idiomatic expression in one language (e.g. "to burn the midnight oil ") is not idiomatic in the other language (e.g. "travailler tard dans la nuit").

Examples of entries in this book are reported in Table 1. A few entries have several equivalent translations such as "make your flesh creep" and "give you goose pimples" for "donner la chaire de poule". Globally, there are on average 1.17 English translations and 1.01 French translations per entry.

All expressions but seven, are used in the context of a sentence. According to the author, using expressions in a context makes them easier to understand and to use for the readers. The lexicon contains a high proportion of verbal phrases (around four out of five of the available entries) that are used in their inflected form, like "He took to his heels" for the phrase "to take one's heels". Other entries are fixed expressions such as "When there's a will, there's a way" or "Hands off ! ".

Preprocessing

In order to take into account contextualization that makes lexicon entries too specific, the used lexicon was manually annotated by the first author of this paper.

Table 1. Excerpt of the entries we considered in our experiment. r stands for the reference translation, g stands for the translation made by Google Translate (provided as a proxy to literal translation). Words in parenthesis have been manually marked as contextual words that are not part of the idiomatic expression.

French English

Il All words judged as extra-information with respect to the idiomatic expression were annotated as such in the lexicon. Those are the words in parenthesis in the examples of Table 1. They are typically modal verbs (e.g. "can", "must"), semimodal verbs (e.g. "am going to", "are likely to"), catenative verbs (e.g. "want to", "keep"), adverbs (e.g. "only", "finally"), adverbial phrases (e.g. "in Italy", "when he heard the news") or noun phrases (e.g. "this poet", "his latest book "). Finally, at least one word was classified as extra-information for 486 out of 1,467 entries.

Queries to the Translation Memory

In order to test the ability of TransSearch to find translations for idioms, three types of queries were submitted to the system: queries built from either the English side or the French side of the entry, and bilingual queries where both sides where searched for at the same time. As mentioned in Section 3.1, a few entries have more than one English or French reference translations. For these entries, we collected results found from all the equivalent translations. Since TransSearch user interface doest not allow users to write an "or" operator between several equivalent translations, we had to simulate the behavior of this operator by submitting independently translations and then by merging results retrieved by TransSearch.

Table 2 shows the number of lexicon entries found in the TM, using bilingual (column 2), English (column 3) or French queries (column 4) and considering various ways of querying the system. As expected, building verbatim queries from the lexicon leads to retrieve information inside the TM for a small number of expressions only (line 1). After taking into account the manual preprocessing step introduced in Section 3.2, that is, after removing extra words, nearly three times as many queries have at least one hit in the TM (line 2). Still, at best, a user could retrieve no more than 410 (French) expressions from the 1,467 ones by simply querying them verbatim or removing extra words.

An inspection of the submitted queries revealed that many of them correspond to flexible idioms, that is, idiomatic expressions that can vary from one occurrence to another. In order to capture those variations and to increase therefore the number of hits in the TM, we wrote rules that abstract away some of those variations. For this, we used a mix of linguistic information as well as the operators we described earlier. We resisted to the temptation of adjusting this process for each query and instead applied some rules in a systematic way, given a set of linguistic markers semi-automatically annotated in the lexicon.

The performed processing steps for the entry ["I have no axe to grind ", "Je ne prêche pas pour ma paroisse"] are illustrated in Table 2. A set of rules deleted personal pronouns at the beginning of an expression (see line 3); a list of pronouns to be removed has been collected for this in each language. Then, lemmatized verbs were replaced by the corresponding lemma and auxiliary verbs were removed (see line 4); we used for this an in-house lemmatization resource available for both languages. Last, we also considered lemmatizing pronouns and determiners within an expression (see line 5).

It should be noted that we chose to modify entries using a set of limited rules in order to avoid over-abstracting idiomatic expressions. For instance, we noticed that the indefinite pronoun "it" in English usually occurs in fixed expressions and cannot be replaced by another personal pronoun. Therefore, we kept this pronoun verbatim in the queries made.

We observe in Table 2 the dramatic increase of the number of hits in the TM according to the level of abstraction of the query. At best, the rewriting rules we applied allow TransSearch to return sentence pairs for 700 English entries and for 705 French entries, i.e. roughly half of the lexicon. Each set of rules increases the number of queries with at least one hit. Surprisingly, verb lemmatization led to a higher improvement of the coverage for English queries than for French ones. This shows that, on the contrary to what we expected first, this process is also relevant for weakly inflected languages.

This experiment also shows that in order to get the best of the system, users should use the linguistic operators at their disposal. Since we know that most queries made by real users of the application do not use those operators it could mean one of two things. When users submit a query to the system without getting any answer, they might simply abandon the search for a translation or on the contrary, they might figure out a way to process the query in order to find a match in the TM. Inspecting the log-files of the application exhibits evidences that both strategies happen in practice. This means that automatically processing the query of a user is an interesting prospect to consider.

Another interesting outcome of the experiment we conducted is that the Hansards indexed by TransSearch are rather good for identifying the idiomatic expressions we considered.

Evaluation

We have measured the quantity of idiomatic expressions we could find by querying the Hansards indexed by TransSearch. We now turn to the evaluation of how good the application is for spotting the translations of the retrieved expressions. Once again, it should be noted that in most bilingual concordancers we know of, this part is left to the user.

Objective Evaluation

For the French and English queries obtained after applying our rewriting rules, TransSearch was able to retrieve on average respectively 36.1 and 31.7 sentence pairs from the TM. Among this material, the transpoting algorithm identified respectively 12.5 French and 14.9 English (different) translations (shown to the user on the left of the navigator). Since a manual analysis of all the suggested translations would be a tedious task, an evaluation was performed thanks to the sanctioned translations belonging to the idiom lexicon described in Section 3. As shown in Table 2 (last line), a query and its sanctioned translation are found simultaneously in the sentence pairs returned by the system for 238 lexicon entries. Therefore we restrained our objective evaluation to those 238 queries. Table 3 provides the proportion of those queries where the k-first translations displayed by TransSearch contain (at least) one of the reference translations sanctioned by the lexicon. 5The recall of 75% measured when all the translations returned by the system are considered demonstrates that the embedded transpotting algorithm has the ability to find translations in the retrieved sentence pairs. The result of 41,6% obtained when considering the first translation returned by the system (that is, the most frequent one) is not bad either, especially since the reference we used is rather incomplete. For instance, our lexicon contains the translation "être dans un état second " for the idiom "to be in a daze", while TransSearch displays this translation after "est nébuleux ", which is as well a good translation of the English idiom. Similarly, TransSearch returns no less than 34 different translations6 of the query "be+ around the corner ", most of which being perfectly legitimate translations, while our reference contains only one.

Manual Evaluation

The objective evaluation revealed the great potential of TransSearch for identifying the translation of idiomatic expressions, but also showed that a manual evaluation was required in order to account for the sparseness of our bilingual lexicon. Therefore, we conducted a manual evaluation involving 5 bilingual annotators that were presented with lists of identified translations among 100 randomly chosen French queries. They were asked to indicate in those lists those translations that they found correct, partially correct or wrong. No specific guidelines were given to explain these labels. At the time of writing, 50 queries were judged by 3 annotators and the 50 other by 2.

Globally, the quality appreciated by the annotators turned out to be variable, some annotators tending to classify more easily translations as correct. This translated into a low value of 0.25 obtained when computing the Fleiss interannotator agreement [START_REF] Fleiss | Statistical Methods for Rates and Proportions[END_REF]. Figure 4 illustrates some cases of divergence.

The results of this evaluation are reported in Table 4. Since a given query can be rated differently by several judges, we credited divergent annotations equally. For instance, if a translation is judged correct by one annotator, and wrong by another one, a credit of 0.5 will be given to each label.

For all but 7 queries, TransSearch is able to identify a translation classified as correct by at least one annotator. For these queries, the average rank of the first correct translation is 1.4, which indicates that relevant translations can usually be found among the two first displayed by TransSearch. Also, on average, we observe that only 36% of the translations proposed to the user are labeled as wrong.

Conclusion

In this work, we have studied the problem of identifying translations of idiomatic expressions in both English and French, using a brand new version of the bilingual concordancer TransSearch. We showed that a user that would query the system verbatim would often fail to find a match in the TM and that some cleverness is required in order to get good use of the system, such as resorting to the morphological (+) and the proximity (..) operators available in the query language recognized by the system. We automatized the querying process and showed that a rough half of the idiomatic expressions queried to the system finally got a match in the TM, while a high proportion of the translations returned by the system are correct.

Fig. 1 .

 1 Fig. 1. Result returned by the new TransSearch to the query "is still in its infancy". The left column shows likely translations in decreasing order of likelihood, while the main columns shows concordances. The query and the selected translation are shown in color in each of them.

Fig. 2 .

 2 Fig. 2. Result returned by TransSearch to the query "make .. hair stand on end ".

Fig. 3 .

 3 Fig. 3. Result returned by TransSearch to the query "take+ no for an answer ".

Fig. 4 .

 4 Fig. 4. Examples of annotations of some French idiomatic queries.

Table 2 .

 2 Number of the lexicon entries found inside the translation memory using several types of query.

	Query types	bilingual English French
	verbatim queries	37	136	248
	en: I have no axe to grind
	fr: Je ne prêche pas pour ma paroisse
	+ manual removal of extra words	91	302	410
	en: I have .. axe to grind
	fr: Je .. prêche .. pour ma paroisse
	+ removal of extra pronouns	106	381	509
	en: have .. axe to grind
	fr: prêche .. pour ma paroisse
	+ verb lemmatization	210	624	650
	en: have+ .. axe to grind
	fr: prêcher+ .. pour ma paroisse
	+ pronoun and determiner lemmatization	238	700	705
	en: have+ .. axe to grind
	fr: prêcher+ .. pour sa+ paroisse

Table 3 .

 3 Recall (%) measured using the lexicon sanctioned by the translation memory as a reference.

	k	1	2	3	5	10	all
	English queries	41.6	56.3	59.2	65.1	69.3	74.8
	French queries	41.6	49.6	54.6	62.6	69.3	76.5

Table 4 .

 4 Average percentage of translations judged correct, partially correct or wrong per query on a sample of 100 English queries randomly selected. avr stands for the average number of translations produced per query, while rank indicates the average rank of the first translation labeled as correct by at least one annotator.

	correct	partial	wrong	avr	rank
	42%	22%	36%	13.4	1.4

At the time of writing, Google Translate produces the literal translation "Il ne pouvait pas dire boo à une oie".

http://lucene.apache.org

In order to account for inflectional variations, we compared lemmatized translations.

The 10 most frequent ones are: est à nos portes, arrive à grand pas, était imminent, nous attend, me guette, est sur le point, s'annonce, est en vue, sommes au bord de, and survenir.

www.terminotix.com

Acknowledgments

This work was funded by an NSERC grant in collaboration with Terminotix. 7 We are indebted to Sandy Dincky, Fabienne Venant and Neil Stewart who kindly participated to the annotation task.


J Ér

Ôme Coville

A NOTE ON LIOUVILLE TYPE RESULTS FOR A FRACTIONAL OBSTACLE PROBLEM

This note is a synthesis of my reflexions on some questions that have emerged during the MATRIX event "Recent Trends on Nonlinear PDEs of Elliptic and Parabolic Type" concerning the qualitative properties of solutions to some non local reaction-diffusion equations of the form

where K ⊂ R N is a bounded smooth compact "obstacle", L is non local operator and f is a bistable nonlinearity. When K is convex and the nonlocal operator L is a continuous operator of convolution type then some Liouville-type results for solutions satisfying some asymptotic limiting conditions at infinity have been recently established by Brasseur, Coville, Hamel and Valdinoci [4]. Here, we show that for a bounded smooth convex obstacle K, similar Liouville type results hold true when the operator L is the regional s-fractional Laplacian.

Introduction

A classical topic in applied analysis consists in the study of "diffusive processes" in complex media e.g. media containing obstacles. Roughly speaking, this corresponds to study dispersal processes that follows a random motion in an environment that possess an inaccessible region. At the macroscopic level, this problem can be translated into a reaction -diffusion equation that is defined outside a set K, which acts as an impenetrable obstacle.

One of the cornerstones in the study of these processes lies in suitable rigidity results of Liouvilletype, which allow the classification of stationary solutions, at least under some geometric assumption on the obstacle K.

In this note, we investigate further non local version of a diffusion equation and provide new Liouville-type result (whose precise statements will be given in Section 2).

Concretely, we will suppose that the random motion is modelled by a Lévy flight which at the macroscopic level, leads to consider an integral operator with a singular positive kernel. For such type of processes we will show that the solutions of the stationary equation with a prescribed behaviour at infinity are necessarily constant, at least when the obstacle is convex.

We now provide the detailed mathematical description of the problem that we take into account.

1.1. A fractional obstacle problem. Throughout this note, K denotes a smooth compact set of R n with n 2, |•| denotes the Euclidean norm in R n and L denotes the regional fractional nonlocal operator ( [START_REF] Guan | Boundary problems for fractional laplacians[END_REF][START_REF]Reflected symmetric α-stable processes and regional fractional laplacian[END_REF]) defined for s ∈ (0, 1) by (1.1) L[u](x) := C n,s lim ε→0 ˆ|x-y|>ε,y∈R n \K u(y) -u(x) |x -y| n+2s dy .

We are interested in qualitative properties of smooth bounded solutions to the following non local semilinear equation

L[u](x) + f (u(x)) = 0 for all x ∈ R n \ K, (1.2)
where f is a C 1 "bistable" non-linearity and when necessary with the Neumann boundary condition below ∇u(x) • ν(x) = 0 for all x ∈ ∂K, (1.3) where ν(x) denotes the outer normal derivative of the set K. The precise assumptions on K, u, f and L will be given later on. Typically, this homogeneous Neumann boundary condition is required to define properly the regional fractional Laplacian L on the boundary of the obstacle when s ∈ 1 2 , 1 . This problem may be thought of as a fractional version of the following problem

(1.4) ∆u + f (u) = 0 in R n \ K, ∇u • ν = 0 on ∂K.
For problem (1.4) with the local diffusion operator ∆u, it was shown in [START_REF] Berestycki | Bistable traveling waves around an obstacle[END_REF] that there exist a timeglobal classical solution u(t, x) to the parabolic problem

(1.5)    ∂u ∂t = ∆u + f (u) in R × R n \ K, ∇u • ν = 0 on R × ∂K satisfying 0 < u(t, x) < 1 for all (t, x) ∈ R × R n \ K, and a classical solution u ∞ (x) to the elliptic problem          ∆u ∞ + f (u ∞ ) = 0 in R n \ K, ∇u ∞ • ν = 0 on ∂K, 0 u ∞ 1 in R n \ K, u ∞ (x) → 1 as |x| → +∞. (1.6)
The function u ∞ is a stationary solution of (1.5) and it is actually obtained as the large time limit of u(t, x), in the sense that u(t, x) → u ∞ (x) as t → +∞ locally uniformly in x ∈ R n \ K. Under some geometric conditions on K (e.g. if K is starshaped or directionally convex, see [START_REF] Berestycki | Bistable traveling waves around an obstacle[END_REF] for precise assumptions) it is shown in [3, Theorems 6.1 and 6.4] that solutions to (1.6) are actually identically equal to 1 in the whole set R n \ K. This Liouville property shows that the solutions u(t, x) of (1.5) constructed in [START_REF] Berestycki | Bistable traveling waves around an obstacle[END_REF] then satisfy

u(t, x) -→ t→+∞ 1 locally uniformly in x ∈ R n \ K. (1.7)
From an ecological point of view, such a results can be interpreted as follows. Let us consider that u(t, x) represents the density of a population that moves according to a Brownian motion in a environment consisting of the whole space R n with a compact obstacle K and that the demography of this population can be described by the nonlinear function f . Then, the equation (1.5) can be understood as the evolution of this population int the region R n \ K. In this context, (1.7) means that, at large time, the population tends to occupy the whole space.

Assuming now that the random movement of the individuals follows, say, a reflected symmetric α-stable Lévy process, then the resulting reaction-diffusion equation will be ∂u ∂t

(t, x) = L[u](t, x) + f (u(t, x)) for all t > 0, x ∈ R n \ K (1.8)
+ A Neumann type boundary condition when necessary whereL is the regional fractional Laplacian defined above.

The numerical simulations below (see Figure 1) obtained for a non singular version of the fractional operator L namely when we replace the singular measure δ+|z| n+2s with δ = 0.01, the bistable non-lineartity f is a cubic non-linearity f (s) = s(s -0.1)(1 -s) and the initial condition is of Heaviside type. We can see that the density u(t, x) tends to 1 on the all space and the influence of the obstacle on the shape of the transition In this note, we deal with qualitative properties of the stationary solutions of equation (1.8), together with some asymptotic limiting conditions at infinity similar to those appearing in (1.6). Namely, we will be mainly concerned with solutions of

     L[u] + f (u) = 0 in R n \ K, 0 u 1 in R n \ K, u(x) → 1 as |x| → +∞.
(1.9) with, when necessary, the additional homogeneous Neumann boundary condition

(1.10) ∇u • ν = 0 on ∂K.
1.2. General assumptions. Let us now state precisely the assumptions we will use. Along this note, we suppose that the domain K is a smooth (at least C 0,1 ) bounded compact domain of R n , and that f is a smooth bistable non-linearity, that is f will always satisfies

(1.11) f ∈ C 1 ([0, 1]), f (0) = 0 = f (1) 0, f (1) < 0, (1.12)      ∃ θ ∈ (0, 1), f (0) = f (θ) = f (1) = 0, f < 0 in (0, θ), f > 0 in (θ, 1), ˆ1 0 f > 0, f (0) < 0, f (θ) > 0.
Observe that the assumption on f implies that the associated potential is unbalanced which is a necessary condition to observe the propagation of a front with a positive speed [START_REF] Achleitner | Traveling waves for a bistable equation with nonlocal diffusion[END_REF][START_REF] Gui | Traveling wave solutions of allen-cahn equation with a fractional laplacian[END_REF]. Thus it seems reasonable to assume such condition in our setting since we expect that the solution u of (1.9) reflect the outcome of the invasion of the population in the environment R n \ K.

Main results

For the local problem (1.6), the Liouville property obtained in [START_REF] Berestycki | Bistable traveling waves around an obstacle[END_REF] says that u = 1 in R n \ K under some geometric conditions on K,in particular when K is convex. Similar Liouville type property was recently obtained for continuous solution of (1.9) when the singular kernel 1 |z| n+2s is replaced by a non negative integrable kernel J, i.e. J ∈ L 1 (R), see [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF]. More precisely, if J is assume to satisfy the assumptions below (2.13) J ∈ L 1 (R n ) is a non-negative, radially symmetric kernel with unit mass, there are 0 r 1 < r 2 such that J(x) > 0 for a.e. x with r 1 < |x| < r 2 , and there exists a function φ ∈ C(R) satisfying

(2.14) J 1 * φ -φ + f (φ) 0 in R, φ is increasing in R, φ(-∞) = 0, φ(+∞) = 1,
where J 1 ∈ L 1 (R) is the non-negative even function with unit mass given for a.e. x ∈ R by

J 1 (x) := ˆRn-1 J(x, y 2 , • • • , y n ) dy 2 • • • dy n .
then in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] the authors prove the following Theorem 2.1 (Brasseur, Coville, Hamel,Valdinoci [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF]). Let K ⊂ R n be a compact convex set. Assume that f satisfies (1.11) and (1.12) and J satisfies (2.13) and (2.14) and let

u ∈ C(R n \ K, [0, 1]) (2.15) be a function satisfying (2.16)      ˆRn \K J(x -y)(u(y) -u(x)) dy + f (u(x)) 0 for x ∈ R n \ K, u(x) → 1 as |x| → +∞. Then, u = 1 in R n \ K.
Observe that the problems (2.16) and (1.9) only differ in their formulation by the singularity of the kernels used. In particular, the problem (2.16) can be reformulated in to the framework of problem (1.9) since for all J ∈ L 1 (R n ) and for all

x ∈ R n \ K and u ∈ L ∞ (R n ) lim ε→ ˆRn \K,|x-y|>ε J(x -y)(u(y) -u(x)) dy = ˆRn \K J(x -y)(u(y) -u(x)) dy.
Therefore, it is expected that (2.16) and (1.9) share some common properties. On of the goals of the present note is to extend the results known for (2.16) to the solutions of (1.9) and when possible to highlight the role of the singularity of the kernel in this context.

Our main results show that under the right regularity assumptions we can transposed the results of theorem 2.1 to solutions to (1.9). Namely, we first prove that Theorem 2.2. Let K ⊂ R n be a compact smooth convex set (C 0,1 ). Assume (1.11), (1.12) and s ∈ (0, 1 2

). Let u ∈ C 0,β (R n \ K, [0, 1]) with β > 2s be a function satisfying L[u] + f (u) 0 in R n \ K, u(x) → 1 as |x| → +∞. (2.17) Then, u = 1 in R n \ K.
Our second result complete the picture, namely we show that Theorem 2.3. Let K ⊂ R n be a compact smooth convex set (C 0,1 ). Assume (1.11), (1.12) and s

∈ 1 2 , 1 . Let u ∈ C 1,β (R n \ K, [0, 1]) with β > 2s -1 be a function satisfying      L[u] + f (u) 0 in R n \ K, ∇u • ν = 0 on ∂K, u(x) → 1 as |x| → +∞.
(2.18)

Then, u = 1 in R n \ K.
We can already see clearly the effect of the singularity of the kernel. Indeed, unlike the non local operators with integrable kernel the s-fractional Laplacian is well defined in R n \ K only for regular function, i.e. u should be at least C 0,β . In this singular setting, requiring that the super-solution u is solely continuous is not enough.

These results complete our knowledge on the validity of such type of Liouville property for a broad class of reaction diffusion equation. They show some universality of such type of property and prove that such rigidity type result can be viewed as an intrinsic property of the problem which can be related to a generic property of the equation rather than a special property of the diffusion process considered.

2.1. Further comments and strategy of proofs. Prior to proving these results, let us make some comments on our hypotheses and highlight some of the differences that arise when the singular measure 1 |z| n+2s is replaced by an integrable kernel J. First, let us observe that thanks to the regularising property of the regional fractional Laplacian L, see [START_REF] Caffarelli | Regularity theory for fully nonlinear integro-differential equations[END_REF][START_REF] Guan | Boundary problems for fractional laplacians[END_REF][START_REF]Reflected symmetric α-stable processes and regional fractional laplacian[END_REF] the continuity assumption made on u can be easily weakened when u is assumed to be a solution to (1.9) instead of a super-solution. Thus, in this situation, the result of Theorems 2.2 and 2.3 hold as well for bounded solution u that satisfies the equation (2.17) respectively (2.18) in the sense of viscosity solutions. Note that contrary to the regional fractional Laplacian L, the nonlocal operator M[u] := ´Rn \K J(x -y)(u(y) -u(x)) dy has no regularising properties and as a consequence weakening the regularity assumption on the solution u is a hard task which, for the moment, can only been achieved by imposing further restrictions on the data f and J. Nevertheless, in this non regularising context, the regularity of the obstacle K is no more an issue and K can be any arbitrary convex domain. The regularisation effect on the solutions induced by the singularity is in fact the only main distinction between the problem (2.16) and the singular problems (2.17) and (2.18).

This distinction appears also clearly in the set of assumption needed for the existence of monotone travelling front with a positive speed, which is an essentiel key element of the proof of Theorem 2.1. In particular, as already mentioned at Section 1.2, assumptions (1.11) and (1.12) are actually necessary and sufficient for the existence of a travelling wave solution with positite speed c to the one dimentional fractional equation, i.e. a monotone solution to

c ∂ z ϕ = ∂ s z ϕ + f (ϕ)
, with a positive speed c > 0. Such assumptions are not any more sufficient in the context of (2.16), where there exists data f and J that satisfy (1.11)-(1.12) for which only discontinuous null speed fronts exist.

Let us also note that, similar condition are also necessary and suffisent for the existence of one dimentional travelling wave with positive speed for the local problem, namely solution of c ϕ = ϕ + f (ϕ) with positive speed (see e.g. [START_REF] Aronson | Multidimensional nonlinear diffusion arising in population genetics[END_REF]). This fact, then suggest a strong connexion between the regularity of the front and the minimal set of assumptions that are required to produced a front of positive speed.

Let us emphasize that the motivation behind these assumptions are that, by analogy with the local problem (1.5), we expect a solution to (1.9) to be the large time limit of an entire solution to the evolution problem (1.8) which behaves like ϕ(x 1 + ct) when t → -∞. For this interpretation to even make sense it is necessary to work in a setting where the function ϕ exists.

Let us now say a word on our strategy of proofs. The proofs are a rather straightforward adaptation of the arguments developed in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] for the non local obstacle problem (2.16). The main idea is to compare by means of adequate sliding method, a family of planar function of the type ϕ(x • e -r), where e ∈ ∂B 1 , r ∈ R and ϕ ∈ C 1,1 (R) a given monotone function with a given super-solution u. To adapt such technique to our situation, we need first to verify that, as proved for (2.16) similar comparison principles in half-spaces hold true as well for the fractional equations (2.17) and (2.18).

The outline of this note will be as follow. In Section 3 we provide several comparison principles and recall some known results on the 1d travelling fronts for fractional bistable equation. Then we prove in Section 4, following the arguments developed in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF], we prove the Liouville property described in Theorems 2.2 and 2.3.

Some mathematical background

In this section, we start by collecting some comparison principles that fit for our purposes and to shortened the presentation we only fully state the necessary comparison principle for regional fractional Laplacian with s ∈ 1 2 , 1 . Throughout this section, K is any compact subset of R n , f is any C 1 (R) function.

We start with a weak maximum principle Lemma 3.1 (Weak maximum principle). Assume that s ∈ 1 2 , 1 and

(3.19) f -c 1 in [1 -c 0 , +∞), for some c 0 > 0, c 1 > 0. Let H ⊂ R n be an open affine half-space such that K ⊂⊂ H c = R n \ H. Let u, v ∈ L ∞ (R n \ K) ∩ C 1,β H for some β > 1 -2s be such that (3.20) L[u] + f (u) 0 in H, L[v] + f (v) 0 in H.
Assume also that

(3.21) u 1 -c 0 in H, that (3.22) lim sup |x|→+∞ v(x) -u(x) 0
and that

(3.23) v u a.e. in H c \ K.
Then, v u a.e. in R n \ K.

The next lemma is concerned with a strong maximum principle.

Lemma 3.2 (Strong maximum principle). Assume that s ∈ 1 2 , 1 and let H ⊂ R n be an open affine half-space such that K ⊂⊂ H c . Let u, v ∈ L ∞ (R n \ K) ∩ C 1,
β H for some β > 1 -2s be such that (3.20) holds true. Assume also that

(3.24) v u a.e. in R n \ K
and that there exists x ∈ H such that v(x) = u(x). Then, v = u a.e. in H.

These comparison principles are in essence identical to the one derived in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] and as such we point the interested reader to [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] for a detailed proof of these results.

Remark 3.3. The above comparison principles have only been stated for regional fractional operators with exponent s ∈ 1 2 , 1 . Identical weak and strong maximum principles can be formulated for the regional fractional Laplacian with exponent s ∈ 0, 1 2 as soon as we impose the adequate regularity to the functions u and v in order to properly define the regional fractional Laplacian of u and v. In such case, the above statement will holds true if instead of having u

, v ∈ L ∞ (R n \ K) ∩ C 1,β H we assume that u, v ∈ L ∞ (R n \ K) ∩ C 0,β H with β > 2s.
Lastly, we recall some known result on the existence and properties of travelling fronts ϕ(x • e + ct), solution of the fractional evolution equation

∂ t u(t, x) = ∆ s u(t, x) + f (u(t, x)) for t ∈ R, x ∈ R n
that is, solution of the following

-c∂ z ϕ(z) + ∂ s z ϕ(z) + f (ϕ(z)) = 0 for z ∈ R (3.25) lim z→+∞ ϕ(z) = 1, lim z→-∞ ϕ(z) = 0 (3.26)
where ∂ s z ϕ denotes the one dimentional s-fractional Laplacian. The existence, uniqueness and some asymptotic properties of such solution ϕ have been obtained in several context [START_REF] Achleitner | Traveling waves for a bistable equation with nonlocal diffusion[END_REF][START_REF] Cabré | Nonlinear equations for fractional laplacians ii: existence, uniqueness, and qualitative properties of solutions[END_REF][START_REF] Gui | Traveling wave solutions of allen-cahn equation with a fractional laplacian[END_REF][START_REF] Palatucci | Local and global minimizers for a variational energy involving a fractional norm[END_REF]. The next statement is a summary of these results. Theorem 3.4 (Fractional Travelling wave [START_REF] Achleitner | Traveling waves for a bistable equation with nonlocal diffusion[END_REF][START_REF] Cabré | Nonlinear equations for fractional laplacians ii: existence, uniqueness, and qualitative properties of solutions[END_REF][START_REF] Gui | Traveling wave solutions of allen-cahn equation with a fractional laplacian[END_REF][START_REF] Palatucci | Local and global minimizers for a variational energy involving a fractional norm[END_REF]). Assume f is a bistable function that satisfies (1.11) and (1.12) and let s ∈ (0, 1). Then there exists a unique c ∈ R and a monotone smooth (at least C 1,1 ) increasing function ϕ such that (c, ϕ) is a solution to (3.25)-(3.26). Moreover, if f is unbalanced with ´1 0 f (s) ds > 0, then c > 0.

As a trivial consequence of the existence of a smooth front of positive speed, for any separating open affine half-space H ⊂ R n such that K ⊂⊂ H c , we can derive a family of function which will be a "sub-solution to the problem (1.9)" for all x ∈ H. More precisely, let H be an affine subspace of R n such that K ⊂ H c . By definition of the affine space, there exists a unit vector e ∈ ∂B 1 and x 0 ∈ R n such that H = x 0 + H e with H e an open-halfspace of direction e, i.e.

H e := {x ∈ R n |x • e 0}.
For this direction e and for all real r ∈ R, we can define the family of functions φ e,r (x) := ϕ(x•e-r) where ϕ is the smooth increasing profile obtained in Theorem 3.4. By construction, since ϕ is monotone increasing we have

(3.27) ∀ x ∈ H, ∀ y ∈ K φ r,e (y) -φ r,e (x) 0.
In addition, we can check that for all x ∈ H, we have Hence, for all x ∈ H, we get

L[φ r,e ](x) = lim ε→0 ˆRn \K,|x-y|>ε φ r,e (
(3.28) L[φ e,r ](x) + f (φ e,r ) ∆ s φ e,r (x) + f (φ e,r ) = ∂ s ϕ(x.e -r) + f (ϕ(x.e -r)) = c∂ z ϕ(x • e -r) > 0.

The case of convex obstacles: proofs of the main Theorem

In this section, based on the arguments introduced in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] we sketch the proof our main results (Theorems 2.2 and 2.3). The proofs of the Theorems 2.3 and 2.2 being identical, we only sketch the proof of Theorem 2.3.

But before we start our argumentation,let us first start with the following simple observation.

Lemma 4.1. Let s ∈ 1 2 , 1 , K ⊂ R n be a smooth compact convex set and assume (1.11) and (1.12). Let u ∈ C 1,β (R n \ K), [0, 1]) with β > 1 -2s be such that Then there exists γ ∈ (0, 1] such that γ u 1 in R n \ K.

L[u] + f (u) 0 in R n \ K,
The proof of this Lemma being an elementary adaptation of the argument used in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF], we will refer to [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] for its proof.

We now turn to the proof of Theorem 2.3 .

Proof of Theorem 2.3. Let us fix s ∈ 1 2 , 1 and let K, f , and u be as in Theorem 2.3. Let us now follow the argument developed in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF]. Firstly, without loss of generality, one can assume by (1.11) that f is extended to a C 1 (R) function satisfying (3.19). Secondly, by (2.17) and the boundedness of K, there exists R 0 > 0 large enough so that K ⊂ B R 0 and u 1 -c 0 in R n \ B R 0 , where c 0 > 0 is given in (3.19).

We now proceed by contradiction, and suppose that inf

R n \K u < 1. (4.32)
From (2.18) and (4.32), together with the continuity of u, there exists then

x 0 ∈ R n \ K such that u(x 0 ) = min R n \K u ∈ [0, 1).
We observe that, by Lemma 4.1, one has u(x 0 ) > 0. In addition, since K is convex, there exists e ∈ ∂B 1 such that K ⊂ H c e , where H e is the open affine half-space defined by H e := x 0 + x ∈ R n ; x • e > 0 .

As in section 3, let us define for all r ∈ R, the family of functions

φ r (x) := φ r,e (x) = ϕ(x • e -r), x ∈ R n ,
where ϕ is a smooth monotone increasing function given by Theorem 3.4. Note that by construction, since K ⊂ H c e , we can check (as in the section 3) that for any r ∈ R, φ r satisfies (4.33)

L[φ r ](x) + f (φ r (x)) > 0 for x ∈ H e .
First, we claim that Claim 4.2. There exists r 0 ∈ R such that φ r 0 u in R n \ K.

Again the proof of this claim is an elementary adaptation of a proof done in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] that for the sake of clarity we give the details.

Proof. First let us define H := x 1 + H e with x 1 to be chosen such that B R 0 ⊂ H c . Let us fix x 1 such that H ⊂⊂ H e . By construction the function ϕ is monotone increasing and satisfies lim z→-∞ ϕ(z) = 0. So we can find r 0 >> 1 such that φ r 0 (x) = ϕ(x • e -r 0 ) u(x 0 ) u(x) for all x ∈ H c . Now thanks to our choice of x 1 we have H ⊂⊂ H e and from (4.33) we deduce

       L[u](x) + f (u(x)) 0 for x ∈ H, L[φ r 0 ](x) + f (φ r 0 (x)) > 0 for x ∈ H, u(x) φ r 0 (x) for x ∈ H c \ K,
We then get the desired results by applying the weak-maximum principle (Lemma 3.1).

Equipped with the claim 4.2, we can now define the following quantity

r * := inf r ∈ R ; φ r u in R n \ K .
All the game now is to show that r * = -∞. So, we claim that Claim 4.3. r * = -∞.

Assume for the claim is true, then the proof of Theorem 2.3 is thereby complete. Indeed, from this claim we infer that φ r u in R n \ K for any r ∈ R. In particular, recalling that ϕ(+∞) = 1, we get that

1 > u(x 0 ) lim r→-∞ φ r (x 0 ) = lim r→-∞ ϕ(x 0 • e -r) = 1,
a contradiction. Therefore, (4.32) can not hold. In other words, inf

R n \K u = 1, i.e. u = 1 in R n \ K proving thereby Theorem 2.3.
Let us now conclude our proof by establishing the Claim 4.3. Again, the proof of this last claim is done by a very elementary adaption of the arguments used to prove Theorem 2.1. As a consequence we will only highlights the main differences.

Proof of the Claim 4.3. The proof of (4.3) is by contradiction. We assume that r * ∈ R. Then, there exists a sequence (ε j ) j∈N of positive real numbers such that φ r * +ε j (x) = ϕ(x • e -r * -ε j ) u(x) for all x ∈ R n \ K and ε j → 0 as j → +∞. Thus, passing to the limit as j → +∞, we obtain that φ r * (x) u(x) for all x ∈ R n \ K.

Let us denote H the open affine half-space

H = x ∈ R n ; x • e > R 0 .
Notice that H ∩ K = ∅ and that u is well defined and continuous in H. We also observe that, by construction, sup H c φ r * < 1. (4.34) Two cases may occur. Case 1: inf H c \K (u -φ r * ) > 0. In this situation, the argument is identical as in for (2.16), and we point the reader to [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF] for the details.

Case 2: inf H c \K (u -φ r * ) = 0. In this situation, by (4.31) and (4.34), and by continuity of u and φ r * , there exists a point x ∈ H c \ K such that u(x) = φ r * (x). Note that x ∈ H e , since otherwise x ∈ R n \ H e , namely x • e < x 0 • e, and the chain of inequalities u(x) = φ r * (x) < φ r * (x 0 ) u(x 0 ) = min This last contradiction then rules out also this situation and therefore rules out Case 2 too.

Remark 4.4. The proof of Theorem 2.2 is identical to the one given in [START_REF] Brasseur | Liouville type results for a non-local equation in a presence of an obstacle[END_REF]. This is due to the fact that the s-fractional operator is well defined and continuous up to the boundary of ∂K when s ∈ 0, 1 2 and as such the strong maximum principle (Lemma 3.2) holds also true for any half space H such that K ⊂ H c . In this situation, the case x ∈ ∂K does not need to be analysed separately from the other cases.

Figure 1 .

 1 Figure 1. Simulation of the singular non local evolution problem (1.8) where the singular Levy kernel has been replaced by a non singular measure1

  y) -φ r,e (x) |x -y| n+2s dy = lim ε→0 ˆRn ,|x-y|>ε φ r,e (y) -φ r,e (x) |x -y| n+2s dy -ˆK,|x-y|>ε φ r,e (y) -φ r,e (x) |x -y| n+2s dy = ∆ s φ r,e (x) -ˆK φ r,e (y) -φ r,e (x) |x -y| n+2s dy. which combined with (3.27) enforces L[φ r,e ](x) ∆ s φ r,e (x) for x ∈ H.

  (4.29) ∇u • ν = 0 in ∂K, (4.30) u(x) → 1 as |x| → +∞. (4.31)

  R n \K u leads to a contradiction. Therefore, we have φ r * u in R n \ K with equality at a point x ∈R n \ K ∩ H e .Again, two situations can occur either x ∈ R n \ K or x ∈ ∂K. Assume for the moment that the latter situation occurs. Then thanks to convexity of K, ν(x) the outward normal to ∂K at x is then the vector e, i.e. ν(x) = e and thanks to (2.18) ∇u • ν(x) = 0 we deduce 0 ∇(u -φ r * ) • ν(x) -∇(φ r * ) • ν(x) = -ϕ (x • e -r * ) < 0.This contradiction then rules out this situation. Lastly assume that x ∈ R n \ K, then in this situation K ⊂⊂ H c e and ϕ r * and u satisfy respectivelyL[u] + f (u) 0 in H e , L[φ r * ] + f (φ r * ) > 0 in H e (by (4.33)), .In particular, it follows from the strong maximum principle (Lemma 3.2) that φ r * = u in H e . Thus, for any e ⊥ ∈ ∂B 1 such that e ⊥ • e = 0, one infers from (4.31) and the definition of φ r * that 1 = lim t→+∞ u(x 0 + t e ⊥ ) = lim t→+∞ φ r * (x 0 + t e ⊥ ) = φ r * (x 0 ) < 1.

  1 |z| n+2s by 1 δ+|z| n+2s for δ << 1, suggest that the long time behaviour of solution of positive equation (1.8) should be identical as those observed in the classical reaction-diffusion equation.

Acknowledgements. The author would like to thank Professor Changfeng Gui for raising to my attention this topic during the MATRIX event "Recent Trends on Nonlinear PDEs of Elliptic and Parabolic Type"

The author has been supported by the ANR DEFI project NONLOCAL (ANR-14-CE25-0013). The author want to thank professor Changfeng Gui for bringing to my attention this question during the Matrix event "


Julien Villemonteix

Emmanuel Vazquez

Maryan Sidorkiewicz

Eric Walter

Global optimization of expensive-to-evaluate functions: an empirical comparison of two sampling criteria

Keywords: expected improvement, Gaussian process, global optimization, Kriging

In many global optimization problems motivated by engineering applications, the number of function evaluations is severely limited by time or cost. To ensure that each of these evaluations usefully contributes to the localization of good candidates for the role of global minimizer, a stochastic model of the function can be built to conduct a sequential choice of evaluation points. Based on Gaussian processes and Kriging, the authors have recently introduced the informational approach to global optimization (IAGO) which provides a onestep optimal choice of evaluation points in terms of reduction of uncertainty on the location of the minimizers. To do so, the probability density of the minimizers is approximated using conditional simulations of the Gaussian process model behind Kriging. In this paper, an empirical comparison between the underlying sampling criterion called conditional minimizer entropy (CME) and the standard expected improvement sampling criterion (EI) is presented. Classical tests functions are used as well as sample paths of the Gaussian model and an actual industrial application. They show the interest of the CME sampling criterion in terms of evaluation savings.

Introduction

To minimize an expensive-to-evaluate function f , a common approach is to use a cheap approximation of this function, which can lead to significant savings over traditional methods. In this context, global optimization techniques based on Gaussian processes and Kriging (see, e.g., [START_REF] Chilès | Geostatistics, Modeling Spatial Uncertainty[END_REF]) are often preferred, for this provides an appealing probabilistic framework to account for the uncertainty on the function approximation. Expensive-to-evaluate functions are often encountered in industrial optimization problems, where the function value may be the output of complex computer simulations, or the result of costly measurements on prototypes.

Most Kriging-based strategies proposed in the past few years (see, e.g., Jones [2001] and the references therein) implicitly seek a likely value for a global minimizer, and then assume it to be a suitable location for the next evaluation of f . Yet, making full use of Kriging, it is possible to explicitly account for the uncertainty on the global minimizers. The most likely location of a global optimizer is actually not necessarily a good evaluation point to improve the accumulated knowledge on the global minimizers.

Based on these considerations, the Informational Approach to Global Optimization (IAGO) strategy recently proposed in [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF] evaluates f where the potential for the reduction of uncertainty on the location of the minimizers is deemed to be the highest. The entropy of the conditional distribution of the global minimizers is taken as the uncertainty measure, and is approximated using conditional simulations of the Gaussian process modeling f . This approach has two main advantages over classical Kriging-based global optimization methods, such as the Efficient Global Optimization (EGO) algorithm (see Jones et al. [1998]). First, it should lead to significant savings on the number of evaluations of f . Second, results under the form of probability distributions are particularly attractive. The purpose of this paper is to evidence the evaluation savings that can be obtained via the use of IAGO.

EGO and IAGO differ only by the sampling criterion used for choosing the next evaluation point. These two criteria, namely expected improvement (EI) for EGO and conditional minimizer entropy (CME) for IAGO, undergo a series of numerical experiments. The first experiments are conducted on four classical test functions. Later on, empirical convergence rates are estimated using sample paths of a Gaussian process. A final comparison is performed on a real-case application to the design of intake ports in the automotive industry, for which a single evaluation of the function to be optimized requires about ten hours of computer time.

The Kriging framework is briefly recalled in Section 2, as well as the definitions of the EI and CME criteria. A brief description of computational aspects of the IAGO approach is also presented. Section 3 reports the empirical comparison of these two criteria. Finally, Section 4 presents conclusions and offers perspectives for future work.

Kriging-based global optimization

Let X, the factor space, be a compact subset of R d and f : X → R be the function to be minimized. The objective is to find x * a global minimizer of f over X when the evaluation of f is expensive. To do so, a cheap model of f (also known as surrogate approximation) based on previous evaluations will be used. Even if deterministic models have been discussed (as in the response surface methodology, see, e.g., [START_REF] Myers | Response Surface Methodology: Process and Product Optimization Using Designed Experiments[END_REF]), it is stochastic models that will retain our attention, and more precisely the Bayesian approach to global optimization (see, e.g., [START_REF] Mockus | Bayesian Approach to Global Optimization: Theory and Applications[END_REF]). In this framework, f is viewed as a realisation (or sample path) of a stochastic process F (F can also be viewed as a Bayesian prior on f ). The distribution of F conditionally to past evaluation results for f is used to design a sampling criterion to be optimized to choose an additional evaluation point for f .

When F is Gaussian (we make this assumption in the rest of the paper), the conditional distribution of F at an untried point is also Gaussian with mean and variance that can be obtained analytically using Kriging (prediction based on Gaussian processes has been known for more than 50 years as Kriging in geostatistics and we shall keep to this terminology). Gaussian models and Kriging have been introduced in the field of Bayesian optimization in Jones et al. [1998], through the Efficient Global Optimization (EGO) algorithm. Since then (see [START_REF] Mockus | Bayesian Approach to Global Optimization: Theory and Applications[END_REF] for an overview of previous work in the field), Gaussian processes and Kriging have been the object of most publications in the field of Bayesian global optimization, with improvements of the EGO algorithm (see, e.g., [START_REF] Williams | Sequential design of computer experiments to minimize integrated response functions[END_REF] or Huang et al. [2006]) and comparative studies (see, e.g. Jones [2001] or [START_REF] Sasena | Exploration of metamodeling sampling criteria for constrained global optimization[END_REF]). Our contribution to the field is also based on Kriging.

Linear prediction

In this section, we recall some well-known facts about Kriging on which the rest of the paper is based (for more details, see [START_REF] Chilès | Geostatistics, Modeling Spatial Uncertainty[END_REF], [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF]) and the references therein).

Let k(., .) be the covariance function of F, and x be a point in X where F is to be predicted. The mean of F(x) is assumed to be a finite linear combination of known functions p i of x, m(x) = β β β T p(x), where β β β is a vector of fixed coefficients to be computed, and p(x) = [p 1 (x), ..., p l (x)] T . Usually the functions p i are monomials of low degree in the components of x (in practice, their degrees do not exceed two).

Given the vector f

n = [ f (x 1 ), ..., f (x n )] T of past evaluations at points in S n = {x 1 , ..., x n } ∈ X n (a sample value of F n = [F(x 1 ), ..., F(x n )] T ), the Kriging predictor F(x) of F(x)
is the minimum-variance unbiased linear predictor in the vector space span{F(x 1 ), ..., F(x n )}. It can be written as

F(x) = λ λ λ(x) T F n , (1)
with F n = [F(x 1 ), ..., F(x n )] T , and λ λ λ(x) the vector of Kriging coefficients for the prediction at x.

The vector of coefficients λ λ λ(x) is solution of the linear system of equations

  K P P T 0     λ λ λ(x) µ µ µ(x)   =   k(x) p(x)   , (2)
with 0 a matrix of zeros, K = k(x i , x j ) 1≤i, j≤n the covariance matrix of F at all evaluation points in S n , k(x) = [k(x 1 , x), ..., k(x n , x)] T , the vector of covariances between F(x) and F n , and

P =      p(x 1 ) T . . . p(x n ) T     
.

The Kriging coefficients at x can thus be computed without evaluating f (x), along with the variance of the prediction error

σ2 (x) = k(x, x) -λ λ λ(x) T k(x) -p(x) T µ µ µ(x) , (3)
as these quantities only depend on the covariance of F. Once f has been evaluated at all x i in S n , the prediction of f (x) is the conditional mean of F, given by

f (x) = E[ F(x)|F n ] = λ λ λ(x) T f n , with F n = {F n = f n } the evaluation results. When f is evaluated exactly, Kriging is an interpolation (∀ x i ∈ S n , F(x i ) = F(x i )).
Although noise on the evaluation results could easily be taken into account in the prediction, in what follows, the evaluations are assumed to be noise-free (see [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF] for the noisy case).

As advocated in [START_REF] Stein | Interpolation of Spatial Data: Some Theory for Kriging[END_REF], the covariance of F is chosen within the Matérn class of covariance functions (cf. [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF] and the reference therein for more details on the choice of a covariance), and the covariance parameters are either set a priori or estimated from the data using the maximum-likelihood method.

After the evaluations in S n , f (x) is viewed as a sample path of F that interpolates the data f n . Such sample paths, known as conditional sample paths, are realizations of F conditionally to F n and are essential to the IAGO approach. They represent all the behaviors that are deemed possible for f given the results of evaluations in S n . Figure 1(a) illustrates the relationships between f , f , σ and the conditional sample paths.

Kriging-based sampling criteria

Among the many sampling criterion available in the literature, we feel that expected improvement (EI), which has been the object of most publications in the field for the last ten years, is the most suited for a comparison with the one we proposed in [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF].

Expected improvement

This sampling criterion corresponds to a one-step optimal strategy given the Gaussian prior F on the unknown function f . Let f * = min x∈X f (x) be the global minimum of f , S n be a set of n evaluation points in X, and consider M n = min x i ∈S n F(x i ) an estimator for f * . For the loss function

L(S n , F) = M n -f * ,
the risk, or expected loss for a candidate point c for the evaluation of f , given the evaluation results f n , is given by

E(L(S n ∪ {c}, F)|F n ) = E(min{M n , F(c)}|F n ) -f * . ( 4
)
One can show that minimizing (4) is equivalent to maximizing the EI criterion as presented for example in Jones [2001], i.e.,

EI(c) = E [I(c)|F n ] , (5)
with

I(c) =    0 if F(c) ≥ M n M n -F(c) otherwise .
One can easily rewrite (5) as

EI(c) = σ(c) uΦ(u) + Φ ′ (u) , (6)
with

u = m n -f (c) σ(c) , m n = E[M n |F n ] = min x i ∈S n f (x i
) the current estimation of the minimum, and Φ the normal cumulative distribution. The new evaluation point is then chosen as a global maximizer of EI(c).

Conditional minimizer entropy

The IAGO approach is based on two complementary principles, that set it apart from previous work in Bayesian global optimization. First, a one-step optimal sampling criterion for the reduction of the uncertainty on the minimizers. Second, the use of Kriging to evaluate this sampling criterion by approximating the distribution of the minimizers conditionally to past evaluations. We now briefly present our sampling criterion, and refer to [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF] for computational details.

In [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF], conditional entropy has been introduced to measure the information gained on the minimizers by an additional evaluation of f . This Stepwise Uncertainty Reduction (SUR) strategy [START_REF] Geman | An active testing model for tracking roads in satellite images[END_REF], chooses the point that potentially brings the largest reduction in entropy (seen as a measure of uncertainty).

More formally, given our Gaussian prior F on the function f to be minimized, the uncertainty on the minimizer x * can be measured by the entropy of the global minimizers

H(X * ) = -∑ x∈G p X * (x)log(p X * (x)),
with X * a random vector uniformly distributed in the set of the global minimizers of F over a discrete approximation G of X, and p X * the point mass density of X * . Now, given a vector f n of evaluation results, the uncertainty left on x * is the entropy of p X * (•|F n ) the point mass density of X * conditionally to the evaluation results F n (or in short conditional minimizer density),

H(X * |F n ) = -∑ x∈G p X * (x|F n )log(p X * (x|F n )).
The idea of the IAGO strategy is iteratively to ensure a one-step optimal reduction of the entropy of this distribution.

The risk associated with a candidate evaluation at c ∈ X is then chosen as the differential entropy of the global minimizers conditionally to the potential result of an evaluation at c (in short CME for conditional minimizer entropy)

H n (c) = H(X * |F n , F(c)),
and the evaluation is performed at

x n+1 = arg min c∈X H n (c).
From the definition of conditional entropy [START_REF] Cover | Elements of Information Theory[END_REF]), we can write

H n (c) = Z y∈R p F(c) (y|F n ) -∑ x∈G p X * (x|F n , F(c) = y)log(p X * (x|F n , F(c) = y)) dy, (7) with p F(c) (•|F n ) the distribution of F(c) and p X * (•|F n , F(c) = y) the distribution of X * conditionally to F n and {F(c) = y}.
The CME H n (c), as written in ( 7), can be viewed as an expected loss, the loss function being the entropy of p X * (•|F n , F(c) = y) the conditional minimizer density after n + 1 evaluations.

Practical aspects

The distribution p F(c) (•|F n ) is Gaussian, with mean and variance simply obtained by Kriging. There is, however, no result in the literature that we can use to describe analytically any useful property of the conditional minimizer density. To compute (7), we resort to an approximation that is conducted via Monte-Carlo simulations of F conditionally to available evaluation results F n and to a potential evaluation result y at c (this approximation Algorithm Input: Initial design of evaluation points and corresponding values of f Output: Additional evaluations 1. while the evaluation budget is not exhausted or some other convergence condition is not satisfied 2.

do Estimate the parameters of the covariance 3.

Compute the Kriging model 4.

Optimize the sampling criterion (EI or CME here) 5.

Evaluate f

Table 1 Efficient global optimization (EGO) framework as well as recommendations for the choice of G are described in details in [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF]). This approximation leads to a complexity in O(N) for the computation of H n (c), with N the size of the discrete approximation of X. Note that in IAGO the conditional minimizer density is thus available at each step and provides (at least for lowdimensional problems) a clear view of the progress achieved in the optimization process (cf. Figure 1(b)).

In the Bayesian optimization framework, the expensive-to-evaluate function is replaced by a cheap criterion, updated after each evaluation, which has to be optimized for a new evaluation point to be chosen. Up to now, we have focused on the choice of criterion, but no attention has been paid to the entire procedure for global optimization, including for example an update process for the Kriging prediction. To keep this paper focused on a comparison between sampling criteria, we shall only mention the classical framework of the Efficient Global Optimization (EGO) presented in Table 1.

EGO (see, e.g. Jones et al. [1998]) starts with a small initial design used to get a first estimate of the parameters of the covariance and to compute a first Kriging model. Based on this model, an additional point is selected in the design space to be the location of the next evaluation of f in order to maximize the EI criterion. The parameters of the covariance are then re-estimated, the Kriging model is re-computed, and the process of choosing new points continues until the improvement expected from sampling additional points has become sufficiently small. The CME criterion can easily be inserted in a similar algorithm in place of EI to transform EGO into IAGO.

Empirical comparison between EI and CME

As presented in the previous section, EI and CME are both Kriging-based sampling criteria and both one-step optimal in some sense. CME should lead to faster convergence rates, and this for three major reasons.

First, EI aims at estimating the minimum, while CME concentrates on the minimizers.

The search is therefore likely to be more global when based on the latter. Second, EI aims at improving the estimation of the minimum by sampling where its appearance is most probable. It seems more reasonable to try diminishing the uncertainty associated with its position. For example, it might be excessively costly to refine the estimation in a small neighborhood of a potential minimum, which may only be local, while evaluations using H n could show that a large part of the search space has a very low probability of containing the global minimum (this idea will be confirmed in Section 3.3). Third, the computation of CME involves the statistical properties of the sample paths of F, while, by contrast the computation of EI involves only the conditional mean and variance of F at c. A more thorough use of the available information on the function is indeed appealing in this context of expensive, and therefore sparse, evaluations.

To substantiate these intuitions, a comparison of EI and CME is in order.

Experimental conditions

To make this comparison fair, we propose to study the behaviors of EI and CME independently from the choice (or estimation) of the covariance (Step 2 in Table 1) and from the optimization method to be used to optimize the sampling criteria (Step 4 in Table 1). These aspects are quite complex, and ad-hoc strategies have been proposed in the literature (see Jones [2001] for an example of optimization method for the sampling criteria). However, our first objective here is to motivate the choice of a sampling criterion.

Therefore, we conducted our experiments using the same Matérn covariance with the same values, fixed a priori, for the covariance parameters. The set G of potential evaluation points was identical for both criteria, and the choice of the next evaluation point was carried out via an exhaustive computation of the relevant sampling criterion over this set. The question to be addressed in what follows then boils down to the following interrogation: Given the same prior information on the function, which sampling criterion chooses the best point (in a sense to be discussed later) amongst a finite set of possible evaluations points?

Tests on classical benchmarks

The four test functions used in this section are taken from Huang et al. [2006], where a comparison was conducted between EI and classical global optimization schemes such as DIRECT (see, e.g., [START_REF] Perttunen | A computational geometric approach to feasible region division in constrained global optimization[END_REF]). The problem dimensions range from two to five, and all functions present several local minimizers (see Table 3 in Appendix 2). The covariance parameters are estimated beforehand on the results of 200 evaluations randomly chosen in search space (using a latin hyper cube sampler), and the two criteria are optimized over a latin hyper cube design containing 1000 points randomly re-sampled after every evaluation.

A single point x 1 is randomly chosen in search space as a common starting point for both criteria, and 50 runs are conducted for each function to reduce the dependency on the starting point. After the i-th evaluation of f , the efficiency of each criteria is measured by

G i = f (x 1 ) -m i f (x 1 ) -f * ,
with m i = min x∈{x 1 ,...x i } f (x) the current estimate of the global minimum. G i (a modified version of the quality measure used in [START_REF] Barton | Minimization algorithms for functions with random noise[END_REF]) thus describes the reduction, after i iterations of the optimization process, of the initial estimation error for the global minimum f (x 1 )f * . three test functions CME converges faster towards the optimum than EI, and significantly so for the Hartman 3 function.

Tests on Gaussian processes simulations

Even if a comparison on classical test functions gives some perspectives on the qualities of each of the criteria, the variability of the results from one test problem to the next may be significant, so one can hardly use them to decide beforehand which sampling criterion to use on a specific problem. It therefore would be best to derive some analytical convergence rates for both criteria under reasonable hypotheses on the function to be optimized. In our context of expensive-to-evaluate functions, these convergence rates would have to be non-asymptotic, and we do not know of any such results in the literature. However, the probabilistic framework considered here makes it possible to estimate empirical convergence rates. Since the function to be optimized is assumed to be a sample path of a Gaussian process, we can estimate the convergence rates with both criteria when optimizing sample paths of a Gaussian process whose covariance is the same as that chosen for the optimization algorithm.

For the sake of brevity, we shall limit our presentation to two Gaussian processes, one with very smooth sample paths, and the other with irregular sample paths.

Two sets of 1000 sample paths were generated over a regular grid of 1500 points in [0, 1] 2 . 15 evaluations are then performed on each sample paths using both criteria. After each new evaluation, and for each criterion, estimation errors are computed for the global minimum and the minimizer, as well as the entropy of the conditional minimizer density. Two estimators of the global minimum are considered here, namely m n = min x∈{x 1 ,...x n } f (x), the best evaluation result obtained so far, and

mn = f (arg max x∈G p X * (x|F n )),
the predicted value associated with the point where the conditional minimizer density is the highest. The average convergence rates for irregular sample paths are presented on Figure 2 As expected, since the entropy of the conditional minimizer is the loss function behind CME, CME performs significantly better than EI in terms of the entropy of the conditional minimizer density and, in average, the uncertainty on the positions of the global minimizers diminishes faster if points are chosen using CME (cf. Figure 2(a)). This fact was guaranteed for the first evaluation since CME is one-step optimal for this loss function, but it had to be checked for several evaluations.

Similarly, if the convergence is measured by the estimation error m nf * , EI is bound to perform better if we consider only the first evaluation, since the convergence measure is the loss function behind EI. However, it appears that after 15 evaluations, the performance of EI and CME are similar (cf. Figure 2(b)), suggesting that even if EI is one-step optimal, in the long run, CME will bring the largest reduction for m nf * (this is confirmed by computations, not presented here, with a larger number of evaluations).

EI would thus seem to be a better criterion in a context where very few evaluations are allowed. However, m n is estimator actually a rather poor estimator of the global minimum, and it appears that when a faster-to-converge estimator is used instead of m n , CME performs significantly better than EI (Figure 2(c)), and this right form the start. This estimator is mn , whose interest is apparent for the three search strategy considered here, for which m nf * is significantly bigger than mnf * , and more than three times so after the first evaluation (Figure 2(b) and Figure 2(c)). CME should therefore be preferred to EI when one is confronted with irregular sample paths, since it allows a better estimation of f * .

If we look at what happens on a typical sample path (see Figure 4), the drawbacks of EI are clearly evidenced. As intuitively stated at the beginning of the section, EI stalls on a local optimum because with (4) as a loss function, it is better to ensure a small improvement near a minimum already found than to check that it is effectively a global minimum. In the case of irregular sample paths this might be highly dangerous, and IAGO performs better simply because it first addresses the question of whether a minimizer is global before improving the precision on its exact position. When the sample paths are more regular, this advantage diminishes (cf. Figure 3), as the local optima are scarcer.

A significant problem is left aside here, namely what happens in practice if the parameters of the covariance are poorly estimated? Does the optimization strategy still perform well? Robustness to a poor choice of covariance parameters is of course a major issue but it is not considered here.The EI and CME criteria should have similar robustness properties and may both be deceived by a poor choice of covariance as demonstrated in Jones [2001]. We feel that this problem should be tackled from a Bayesian point of view, with some prior on the covariance parameters. This will be done in future work, where we shall compare an extended version of IAGO to the methods in Jones [2001] designed to be robust to a poor choice of covariance. Fig. 3. Convergence rates using EI (dotted line) and IAGO (bold line), when convergence is measured by H(X * |F n ) (a), and when convergence is measured by the estimation error for the minimum with mn as estimator (b). The dashed line represents, as reference, the convergence rate for a random choice of evaluation points. The sample paths used here are smoother than those used for Figure 2 (the parameter for the Matérn covariance are ν = 5, ρ = 0.3 and σ = 1).

Test on an industrial application: intake port design

This section presents an industrial optimization problem in the automotive field, also used for the comparison of CME and EI.

Problem description

Intake ports (Figure 5) are engine components that convey a mixture of air and fuel to the combustion chambers. The importance of this type of component lies in the properties of the flow it induces in the combustion chamber, which has a direct impact on both the performance and the emissions of pollutant by the engine. To comply with new emission standards (Euro V and Euro VI), while satisfying the ever increasing need for engine performance, the shape of intake ports has to be carefully optimized. Two often-conflicting objectives have to be maximized simultaneously, namely the flow rate and a scalar characteristic of the turbulent flow known as tumble [START_REF] Lumley | Engines: An Introduction[END_REF]). Physics tells us that the higher the flow rate, the larger the amount of fuel that can be burnt, and consequently the larger the power delivered by the engine. Similarly, pollutants as nitrogen oxides (NO x ) and carbon monoxide (CO) are, to a large extent, created when the air/fuel mix is not homogeneous. Therefore, the larger the turbulence (and tumble accounts for the relevant properties of it), the smaller the pollution.

The specifications for these two objectives are liable to change during conception. Therefore, it is important to determine not only an optimal geometry for a given set of preferences but rather the full Pareto front. However, building prototypes for tests is exceedingly expensive, and each flow simulation by finite-element methods takes about ten hours on powerful servers. The approach advocated in this paper is therefore particularly attractive given the general will for reduction of duration and cost associated with development.

Computational issues

To extend our sampling criteria to a multi-objective problem, we use a standard procedure and consider several linear combinations of the objective functions (a.k.a. aggregations), each accounting for a different zone of the Pareto front. In [START_REF] Knowles | Parego: A hybrid algorithm with on-line landscape approxiamtion for expensive multiobjective optimization problems[END_REF], this approach has been used to extend the EI criterion to a multi-objective problem by randomly selecting a new aggregation after each evaluation of f . In this paper, we follow the same route, but use the IAGO framework to compute the entropy of the conditional density of the minimizers for the mono-objective optimization problem corresponding to each aggregation in a given set. The search can thus be directed towards the most uncertain regions of the Pareto front.

The resulting multi objective extensions of CME and EI have been applied to the optimization of six shape parameters of an intake port (these parameters are not detailed here for confidentiality reasons). To improve the number of simulations achievable in a given time, the geometry and mesh are automatically generated for each finite-element simulation. The optimization algorithm is then directly interfaced with the solver, limiting human intervention to the initialization of the procedure.

The initial value for the parameters of the Matérn covariance are estimated on simulations that have been collected during the design of previous intake ports. It thus becomes possible to initialize the algorithms with very few randomly chosen points (here with five points).

One thousand candidate points are used (N = 1000) and the parameters of the Matèrn covariance are fixed.

Tumble

Flow rate -1 -0.95 -0.9 -0.85 -0.8 -0.75 -0.7 -0.65 -0.6 -0.55 -0.5 -2 -1.9

-1.8 -1.7 -1.6 -1.5 -1.4 -1.3 -1.2
Fig. 6. Results of 20 evaluations randomly chosen using an LHC (dots), or optimally chosen by CME (crosses) or by EI (squares). For CME and EI, only the Pareto-optimal points are presented. For LHC, a larger dot size indicates points that are, within the considered set of points, Pareto-optimal. Tumble and flow rate have been rescaled for confidentiality reasons. The dashed lines delimit the set of points that are dominated by the Pareto-optimal points obtained using CME and which dominate the "worst point", i.e. the point with worst values attained for both objectives .

Results

For comparison purposes, simulations were conduced on twenty intake ports whose parameters were chosen using EI, CME, or a Latin Hyper Cube (LHC) as a reference. The Pareto-optimal points within each of the three sets of evaluation results are presented in Figure 6. Comparison between sets estimates of Pareto fronts is a tricky process, which may involve various quality measures [START_REF] Knowles | A tutorial on the performance assessment of stochastive multiobjective optimizers[END_REF]. Here however, the comparison is clearly in favor of CME, as

• among all evaluation results, the point closest to an "ideal" solution (i.e. with best value yet obtained for both objectives, here [-0.97, -1.97] T ) has been chosen by CME; • all but one point chosen by EI are dominated by points chosen by CME. In other words, almost any good solution found by EI is bettered by a solution found by CME; • the volume of the set of points dominated by the Pareto-optimal points (cf. [START_REF] Knowles | A tutorial on the performance assessment of stochastive multiobjective optimizers[END_REF] for details on this quality measure) is 0.31 for CME (this volume is represented on Figure 6), while it is only 0.26 for EI (the reference for the computation is the point with worst values attained for both objectives as coordinates).

This test case confirms that Bayesian global optimization is easily applicable to an industrial problem, even with a very small evaluation budget. The interest of CME is apparent after only a few evaluations, as predicted by the convergence rates of Section 3.3.

Computational burden

The comparison made so far dealt only with convergence rates. The superiority of CME over EI was demonstrated for sample paths of Gaussian random processes, at least for two very different regularities of the sample paths (cf. Section 3.3), while the convergence rates are generally in favor of CME when applied to some classical test functions (cf. Section 3.2) or to an actual industrial problem. However, EI is easier to compute since it only requires the mean and variance of the prediction at the candidate point, while the complexity of the computation of IAGO is in O(N), with N the size of a discrete approximation of X used for the estimation of the conditional density.

In practice, with our implementation of IAGO (cf. [START_REF] Villemonteix | An informational approach to the global optimization of expensive-to-evaluate functions[END_REF]) around 40s are required on an AMD opteron 285 server to choose an additional evaluation point for the sample paths of Section 3.3 (by extensive computation of H n over 1500 candidate points, which is enough in practice since this set is randomly re-sampled after each evaluation). By comparison, choosing a point with EI takes less than half a second under the same conditions. To broaden the range of potential applications, we tried to limit the computational expense by testing other approximations for the conditional minimizer density (since the manipulation of sample paths, necessary for the approximation proposed here, is responsible for most of the computational burden). We proposed for example, to estimate the derivatives of f by Kriging (as in, e.g., [START_REF] Vazquez | Estimating derivatives and integrals with kriging[END_REF]) and to compute the probability for a given point to be a local optimum and under a certain threshold. It was then easy to build a relatively accurate approximation of the conditional minimizer density, but the approximation had a detrimental effect on the convergence rate, so that EI then became more efficient. In fact, the quality of the approximation of the conditional minimizer density is important for CME to perform better than EI.

IAGO therefore remains destined to the optimization of functions that require a large amount of computer time (or more generally a significant expense) to be evaluated, which is after all what it was designed for and is the case in many applications in the industrial world including the one we presented here.

Conclusions and perspectives

In this paper, we have evidenced a clear superiority of CME over EI, especially when the function to be optimized is irregular. The comparison has been conducted using classical test functions and an actual industrial application, but above all using sample paths of the model behind Kriging. The use of sample paths indeed allows the computation of empirical convergence rates that can also be useful to tune other components of any Kriging-based algorithms (e.g., the optimization of the sampling criterion). Now that the interest of the CME criterion has been demonstrated, attention should turn to other crucial aspects of any Kriging-based optimization algorithm. One of these aspects is the improve-ment of robustness against a bad choice of covariance for the Gaussian process model. We feel that the Bayesian framework that we have used until now should also be useful in this respect.

Appendices

Appendix 1: Matèrn covariance

In this paper, we follow [START_REF] Stein | Interpolation of Spatial Data: Some Theory for Kriging[END_REF] and use of the isotropic Matérn covariance:

k(x, y) = k(h) = σ 2 2 ν-1 Γ(ν) 2ν 1/2 h ρ ν K ν 2ν 1/2 h ρ ∀ (x, y) ∈ X 2 , (8)
with h the Euclidean distance between x and y, and K ν the modified Bessel function of the second kind [START_REF] Yaglom | Correlation Theory of Stationary and Related Random Functions I: Basic Results[END_REF]). The parameters of this covariance are easy to interpret, as ν controls regularity, σ 2 is the variance (k(0) = σ 2 ), and ρ represents the range of the covariance, i.e., the characteristic correlation distance. They can either be fixed using prior knowledge on the system, or be estimated from experimental data. In geostatistics, estimation is carried out using the adequacy between the empirical and model covariance (see, e.g., [START_REF] Chilès | Geostatistics, Modeling Spatial Uncertainty[END_REF]). In other areas, cross validation (cf. [START_REF] Wahba | Support vector machines, reproducing kernel Hilbert spaces, and randomized GACV[END_REF]) and maximum likelihood (cf. [START_REF] Stein | Interpolation of Spatial Data: Some Theory for Kriging[END_REF]) are mostly employed. For simplicity and generality reasons (cf. [START_REF] Stein | Interpolation of Spatial Data: Some Theory for Kriging[END_REF]), the maximum-likelihood method is preferred here.

Appendix 2: Test functions

  Fig. 1. (a): Conditional sample paths of F, and corresponding Kriging prediction. The squares represent available values of f , the bold line is the conditional mean f as computed by the Kriging predictor, the dotted lines provide 95% confidence intervals for the prediction ( f ± 1.96 σ) and the thin lines are conditional sample paths. (b): Estimated conditional minimizer density (p X * (•|F n )) associated with the Kriging prediction.

  (a) in terms of the entropy of the conditional minimizer density, on Figure 2(b) in terms of the estimation error for m n , and on Figure 2(c) in terms of the estimation error for mn .

Fig. 2 .

 2 Fig.2. Convergence rates using EI (dotted line) and IAGO (bold line), when convergence is measured by H(X * |F n ) (a), by the estimation error for the global minimum with the best value obtained so far (m n ) as an estimator (b), by the estimation error for the global minimum with mn as an estimator (c). The convergence measures are averaged over 1000 sample paths of a Gaussian process with a Matérn covariance with parameters ν = 1, ρ = 0.3 and σ = 1 (see Appendix 5.1). The dashed line represents, as a reference, the convergence rate for a random choice of evaluation points.

Fig. 4 .

 4 Fig. 4. Minimization of a sample path from the Gaussian process used to evaluate the convergence rates of Figure 2. The dots indicate the evaluation points chosen by EI. The crosses indicate the evaluation points chosen by CME. The order in which the evaluations are carried out is also indicated for CME.

Fig. 5 .

 5 Fig. 5. Intake port. The component itself is in the middle. Below is the combustion chamber. The upper cylinder is a tranquilizing volume necessary for the convergence of finite-element simulations.

f

  x 1 ≤ 2.4, -0.8 ≤ x 2 ≤ 1.2N local = 6, N global = 2 x * = [0.089, 0.713] T and [0.089, 0.713] T , f * = -1x 1 + 10 + 0.5x 1 -5 ≤ x 1 ≤ 10, 0 ≤ x 2 ≤ 15 N local = 3, N global = 1 x * = [-3.2, 12.3] T f * = -1.17Hartman 3 Hartman[1973] d = 3 f (x) = -∑ 4 i=1 d i exp -∑ 3 j=1 α i j (x jp i j ) , i ≤ 1, i = 1, 2, 3 N local > 1, N global = 1 x * = (0.114, 0.556, 0.852) T , f * = -3(x) = -20 exp[-0.2 1 d ∑ d i=1 x 2 i ]exp[ 1 d ∑ d i=1 cos(2πx i )] + 20 + e ∀i ∈ 1, 3 -32.8 ≤ x i ≤ 32.8 N local > 1, N global = 1 x * = 0, f * = 0Table 3 Test functions to be minimized Huang et al. [2006] . J.K. Hartman. Some experiments in global optimization. Nav. Res. Logist. Q., 20:569-576, 1973. D. Huang, T. Allen, W. Notz, and N. Zeng. Global optimization of stochastic black-box systems via sequential kriging meta-models. J. Global Optim., 34:441-466, 2006. D.R. Jones. A taxonomy of global optimization methods based on response surfaces. J. Global Optim., 21:345-383, 2001. D.R. Jones, M. Schonlau, and J. William. Efficient global optimization of expensive

  For each criterion, the convergence measure G i is averaged over 50 runs (the estimated standard error for the estimation of these figures is always smaller than 0.01). Table2Comparison of EI and CME on four test functions taken from Huang et al.[2006]

		G i when points are chosen using EI	G i when points are chosen using CME
		i = 20	i = 50	i = 100	i = 20	i = 50	i = 100
	Six-Hump Camel Back	0.65	1	1	0.76	1	1
	Tilted Branin	0.83	0.92	0.98	0.89	0.95	0.97
	Hartman 3	0.64	0.98	1	0.82	0.99	1
	Ackley 5	0.36	0.75	0.73	0.34	0.59	0.72
	*

Table 2 presents, for each criterion, the averaged efficiency after 20, 50 and 100 evaluations. EI beats CME for the Ackley function when i = 40, but for the other * .