Amalia Todirascu
email: todirasc@loria.fr

Eric Kow
email: kow@loria.fr

Laurent Romary
email: romary@loria.fr

Towards Reusable NLP Components

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The availability of various NLP tools and linguistic resources for several languages opens the possibility of reusing and sharing them. Unfortunately, most of the tools provide low portability (in particular due to applicationspecific resource representation). Building an NLP tool or adapting it for other languages requires considerable effort in creating or updating linguistic resources (often incomplete) as well as in integrating into new applications.

This paper proposes a methodology to transform an elementary NLP module into a reusable component, integrated into an open and distributed NLP architecture. The methodology requires input/output standardization, the choice of a standard format for parameter resources and the definition of a standardized communication protocol between various components. We experimented this methodology with a Lexicalized Tree Adjoining Grammars (LTAG) parser, illustrating the problems arising in a real and somehow complex situation.

The underlying objective of this work was originally to be able to integrate such a parsing component into various larger NLP environments corresponding to various degrees of complexity from a language engineering point of view: a man-machine dialogue system in the context of the IST/MIAMM project1 (a dialogue environment providing speech, graphical and haptic interface to a musical database), an information extraction environment (a message filtering application on computer security in collaboration with the EADS/MSI company), an on-line network of NLP services based on GRID techniques2 .

General background and objectives

Existing initiatives towards the integration of NLP components in unified architectures

A lot of research efforts have concentrated on the issue of building reusable NLP components within specific integrating frameworks. Several challenges were identified (?) when transforming existing NLP modules into reusable components: software challenges (defining APIs for each type module), semantic challenges (the output of various modules are not always semantically consistent), 'political' challenges (the algorithm and resources are not always publicly available for the research community).

Several projects propose environements for building NLP complex applications, based on existing modules. GATE is one of the most widely known, providing an environement for integrating several NLP tools, from various platforms, using readily NLP modules (a POS tagger, a parser, a discourse expert, etc.) (?). GATE supports the reuse of resources (as CELEX (?) and WordNet (?)) and algorithms, and provides technical support for the I/O interface, graphical interface and client-server structure for NLP tools. The I/O interface conforms with a standard TIP-STER annotation module. It provides such interesting features as JAPE (regular expressions over annotations) and GUK (enhanced unicode support). Despite its widespreadness, it requires huge amount of computer resources (memory, disk space) on a single computer environment, it is not user friendly and it imposes a pipe-line architecture. The SVENSK project aims also at reusing resources and algorithms for Swedish (?), using GATE. From another perspective, SiSSA (?) is an infrastructure for prototyping and validating NLP application architectures. It supports different languages and platforms, it uses the XML recommendation for data interchange, it allows the reuse of various processors and it is flexible as it only requires that each new module be registered at a central SiSSA manager. Each module implements a CORBA interface to communicate with the others.

All these projects require an implementation of I/O interface API (which is application-dependent) for each module. We do not intend to propose another NLP architecture, but we propose a standard methodology for transforming NLP tools into reusable components, based on existing standards for protocol and I/O interface. Our methodology is based on simple XML-like format for exchanging data, free of security constraints (as in CORBA). The architecture is completely descentralized and flexible.

Towards the definition of a parsing service

LTAG parsers are good examples of low reusability of resources: existing parsers use a variety of resource formats (XTAG grammar (?), Feature Tree Adjoining Grammars (FTAG (?), SGML (?)). Complete resources are avail-able for English (lexicon and grammar), but they are not really available for French or for other languages. Resources and parsers are intimately related so that it is far from to, say, use en XTAG grammer as parameter of another parsing module. Still, some experiments have been conducted in providing grammar servers on-line (?), but with no intent to connect such "services" to parsing components proper. In this context, the standardization of TAG resource formats was a necessary step and has resulted in the TAGML proposal (?), an XML application for representing elementary TAG trees and forests3 . To illustrate the methodology, we adapted the Lopez parser (?) to use TAGML-based linguistic resources and to provide XML-based output. The component is incorporated into a distributed architecture, where it is combined with an independant resource server and user interface. Those two components, as we will see in this paper, have been designed to be fully independant from the specificities of the parser. In particular, sharing resource servers avoids redundancy, duplication or creation of new resources. One of our aims here was to make sure that the parsing results could be used both as an independant resource, but also to annotate the primary linguistic content provided as an input to the parser. This induced some constraints on the definition of the transmission protocol which should had the specific feature of keeping track of resource reference within the architecture.

Standardization

One of the crucial points to achieve an easy deployment and re-use of NLP modules is to make sure that there exists, for a given type or class of NLP components, the right standards for representing the various linguistic knowledge structures that will be used as input, output or parameter for this module. Unfortunately, even if there has been numerous attempts to define common formats for such object as lexica (e.g. Genelex), basic annotations (Eagles guidelines for part of speech tagging (?)), or multilevel annotation (CES, Mate), none of these initiatives have led to internationally approved standards, essentially because of the lack of a wide recognition independant from any funded project or industrial pressure group. As a direct consequence, most of the existing NLP architectures or environment have developed their proprietary description formalisms for specifying the data transiting between internal components, as we have observed in the comparative table (see figure ??).

In this context, the creation of the new committee TC3/SC4 within ISO provides the first real international framework General perspective -syntax/semantics • Wide agreement on W3C as a stable technical background -XML • Necessity to provide ways to specify one's format while ensuring interoperability principles with similar data that would be provided or consumed by other components (kind-of semantics) Go deeper into this (cf.(?)) by identifying, in a given format the underlying information organization (metamodel) and what can be seen as a parameterization of such structures (data-categories). Cf. Part of speech tagging: While there can be a general agreement on the basic mechanisms needed to represent data tagged for POS (embbeding of word and multiword units, alternatives to cope with ambiguities etc.), each tagger will implement its own tagset corresponding both to the language that it is dealing with and the granularity of description that one aims at. In the context of international standardization, there is thus a need to provide reference sets of data categories that a given application will use to define its own subset. Still, it can be useful to suggest a reference syntax (or a family thereof) for such specific layers as POS tagging that may make things even easier for someone who does not want to implement his own dialect.

To illustrate how we standardized the existing linguistic TAG resources, we present some properties of TAGML, chosen as a resource format, and the input/output format.

Application: TAGML resources

TAG (?) lexicons associate with lexical entries all the syntactic trees which represent all the possible combinations of the lexical entry with other words. These trees (elementary trees) are combined during the parsing process by two operations: substitution and adjunction. To avoid redundancy, several trees are associated to word lemmas.

Elementary trees contains several node types: standard nodes (no leaf nodes), anchor nodes (a leaf node containing the word associated to the tree), foot nodes (a leaf node indicating a possible adjunction) and substitution nodes (a leaf node indicating a substitution). Trees containing adjunction nodes will be adjuncted to the nodes of the same category as the foot node.

S np ↓ v np ↓
The substitutions are represented by ↓ while the adjunction are represented as *. The operations are identified by their adress in the tree. The nodes are counted from left to right from 1 to n. '

Example. Adress 2.1 means that the operation is done at the first son of the V node.

The results of the parsing process are a set of derived trees (the syntactic structure) and a set of derivation trees (the history of substitutions and adjunctions used to build the derived trees).

The substitutions are represented in trees as continuous lines, while adjunctions are represented as dotted line.

Input/Output Standard

XML (W3 Consortium (?)) is used by many NLP applications, for its adequacy for representing annotated text and for structuring data, to its extensibility and to its transparency. As a natural choice, we use for our component XML for input/output. The input of the parser is a phrase in natural language and a set of resources (lexicon, grammar). The format of the lexicon and grammar will be explained in the next subsection.

GATE

The output of the LTAG parser is a set of derived trees (syntactic structures) and a set of derivation trees (a dependency structure). This reflects all the possible syntactic and dependency structures associated to the existing input phrase.

The derived trees are represented as XML elements as:

s np vp n v
Jean aime np d n la soupe <n address="0" cat="s" lex="" type="0"> <n address="1" cat="np" lex="" type="1"> <n address="1" cat="n" lex="Jean" type="2" /n> </n> <n address="2" cat="vp" lex="" type="1"> <n address="2.1" cat="v" lex="" type="1"> <n address="2.1.1" cat="v" lex="aime" type="2"/> </n> <n address="2.2" cat="np" lex="" type="1"> <n address="1" cat="n" lex="soupe" type="1"> <n address="1" cat="d" lex="la" type="2"> </n> </n> </n> </n>

The n element contains several attributes: the lexical category cat, the address were the operation has been done address, the node type type (standard, anchor, foot, substitution), the word lex.

Example. The derivation tree for the input phrase Jean aime la soupe is aime

Jean soupe la and it is represented in XML as: <subs string="aime"> <subs string="Jean"/> <subs string="soupe"> <adj string="la"/> </subs> </subs> Two types of elements are used: subs for tracing substitution operations, and adj for adjunction operations.

The Resources

Resource format is an important issue when reusing data and algorithms. We propose a simple, standard format. We chose to represent our linguistic resources in a standard format: TAGML (Tree Adjoining Grammar Markup Language). TAGML is also a XML-based format: it is easy to use by linguists and it structures the linguistic resources (a set of lexical entries, related to the associated elementary trees). The availability of TAGML resources is provided by tools (?) translating existing grammars (XTAG grammar, FTAG) or generating them from a meta-grammar.

TAGML proposes a representation of all the elements of the TAG lexicon: lexical entries, lemmas and elementary trees. TAGML structures the TAG resources on three levels: lexical entries, lemmas and tree families. Lexical entries are associated to lemmas and have some specific morpological features as number, tense, mode.

Example of a lexical entry in a TAGML lexicon <morph lex="aimera"> <lemmaref cat="v" name="*AIMER*"> <fs> <f name="num"><val>sing</val></f> <f name="mode"><val>ind</val></f> <f name="tense"><val>fut</val></f> </fs> </lemmaref> </morph> lemmaref contains the pointer to the lemma, and the fs element contains the morphological feature structure.

Lemmas contain pointers to tree families and some constraints imposed on the feature structures associated to elementary trees. anchor keeps the pointer to the family tree and the equations impose some constraints on various nodes of the tree (the attribute restr is plus for the node labeled np at the 0 address).

<lemma cat="v" name="*AIMER*"> <anchor tree_id="family[@name=tn1]"> <equation node_id="np_0" type="top"> <fs> <f name="restr"><val>+</val></f> </fs> </equation> </anchor> </lemma> Tree families contain several elementary trees grouped by their syntactic properties. For example, the following family describes the properties of complex noun phrases, containing relative clauses. A tree is a set of nodes. Each node has a category, a type (standard, anchor, foot, subst, lex), a property adj, allowing or not adjunctions and a set of constraints on each node (narg elements).

<family name="tn1"> <tree name="r0tn1"> <node cat="np" type="std"> <node cat="np" type="foot"> <narg type="top"> <fs> <f id="X0" name="num" /> <f id="X1" name="pers" /> <f id="X7" name="restr" /> </fs> </narg> </node> <node cat="s" adj="no" type="std"> <node cat="np" type="std"> <node lex="qui" type="lex" /> </node> <node cat="s" type="std"> <narg type="bot"> <fs> <f name="inv"><minus /></f> <f id="X2" name="mode" /> </fs> </narg> <node cat="np" id="np_0" adj="no" type="std"> <narg type="top"> <fs> <f id="X7" name="restr" /> </fs> </narg> <node type="lex" /> </node> <node cat="vp" type="std"> <narg type="bot"> <fs> <f id="X3" name="mode" /> <f id="X5" name="num" /> <f id="X6" name="pers" /> </fs> </narg> <narg type="top"> <fs> <f id="X2" name="mode" /> <f id="X0" name="num" /> <f id="X1" name="pers" /> </fs> </narg> <node cat="v" type="anchor"> <narg type="bot"> <fs> <f id="X3" name="mode" /> <f id="X5" name="num" /> <f id="X6" name="pers" /> </fs> </narg> </node> <node cat="np" id="np_1" type="subst" /> </node> </node> </node> </node> </tree> <tree name="r1tn1"> </tree> </family> is represented as: np np * s np s qui np vp v np ↓

SOAP protocol

As our system uses the parser and the resource accessing module installed as services on various sites, we need a communication protocol between various components. SOAP is a XML-based standard (?) for exchanging messages between components of a distributed application, and we chose it because of its simplicity and flexibility. SOAP provides a homegenoeous way of handling all data: messages, input/output, resources.

There are two ways to look at SOAP. The first is on a higher level, as a format for messages between agents in any distributed system. A SOAP message consists of an envelop, which wraps a header and a body. This header is where standard SOAP metadata, such as the actors required to understand a message, go, and the body, the actual data we are interested in. While SOAP does also offer some of its own metadata, exceptions (faults), and some default primitives (ints and strings, for example), it is actually a more useful understanding of the protocol to pretend that in its entirety, SOAP is only composed of those three tags: envelop, header, and body. Because it specificies exactly so little, we are free to design the contents of the body and add things to the header at will. For instance, our SOAP bodies would merely be in TAGML (see figure ??). This is what we mean by flexibility.

On a second, lower level, we can think of what people actually do with SOAP, or rather, how it is used as a communication protocol. One path of very little resistance is to bind these SOAP enveloppes to HTTP headers and send the resulting message along its way. In fact, this is what most default implementations of SOAP do; they are little programs (CGI scripts, servlets) that can be attached to webservers. Any software that uses such a SOAP implementation thus only worries about producing and consuming data, leaving it to the SOAP implementation to wrap such data into SOAP envelops, or unwrap such SOAP envelops and turn it back into useful data. Some sophisticated implementations, like Apache SOAP even go a step further, and provide a Remote Procedural Call mechanism on top of this, such that function calls are translated into SOAP messages, unwrapped by the server, then called accordingly, with the resulting data then being itself wrapped and sent back to the client. Once attached to a such a SOAP implementation, a client then concerns itself with function calls, and the server to the provision of these functions. This is what we mean by simplicity.

We feel that SOAP will bring us to our goal of having a widely adopted methodology towards reusability, and we feel this way not because SOAP is any more technologically interesting than other object-sharing mechanisms, but because it is easy. Rather than dictate plausibily correct specifications for inserting an NLP module into specific architecture, we instead propose a protocol that specifies just enough: data and metadata. It is lightweight, built upon pre-existing standards, tied to familiar transport mechanisms, and has thus been widely implemented. Even the Mozilla web browser has a SOAP implementation. In short, we find SOAP to be useful because its standardness and familiarity provides a path towards reusability, but at a mental cost low enough to compete with the ad hoc approach favoured by the computational linguist of today.

System architecture

To experiment this methodology, we split the parser into various modules: the module implementing the connectedroutes-based algorithm (?), the visual workbench and the resources. We integrate all these modules into a distributed, flexible architecture. Each module contains a XML-based communication level for data exchanges, via the SOAP protocol. We used for tests small resources for French (338 lexical words, 50 trees) and English (279 words, 421 trees). Some extra modules, for resource aquisition (lexicon, annotated corpora) might be added into the architecture.

Users enter its texts via a graphical interface. The input texts are sent to the parser, sentence by sentence. The parser creates an instance for each sentence and it sends a request to the resource server to access LTAG resources. The parser will be a client of the Lexicon server. The lexical entries together with the elementary trees are sent back to the parser which continues the process. It sends the resulting forest of derivation and derived trees back to the user interface. The user interface lets the user browse the forest tree by tree. The resource server contains a maintenance module updating the existing resources with the parser output (validated by the user via the interface).

The services

The initial parser has been splitted into several services: the core of the parser acting as a central service installed on a server, the resource access module (loading the grammar and the lexicon) and the graphical user interface.

The parser

The parser implements a connected-routes-based algorithm (?) for TAG grammars. It builds syntactic structures from elementary trees, combining them by substitution and adjunction. The output of this parser is a forest of derivation and derived trees. Optimisations (unification of feature structures during parsing, other algorithms) are still under development. Its input is a phrase in natural language. It asks the lexicon server for the trees associated with each Figure 2: a simplified example of a SOAP message <?xml version='1.0' encoding='UTF-8'?> <SOAP-ENV:Envelope ...> <SOAP-ENV:Header/> <SOAP-ENV:Body> <tag><family name="tmpfam_Jean"><tree name="np"> <node cat="np" id="np_" type="anchor"/> </tree></family></tag> </SOAP-ENV:Body> </SOAP-ENV:Envelope> input word of the phrase. When the trees are returned to the parser core, the parsing process tries to build derivation and derived trees associated to the phrase and even if the process fails to produce a syntactic structure for all the input phrase, it returns a set of partial derived and derivation trees.

The grammar

The lexicon server is structured into three levels: morphological level (containing flexed words and pointers to lemmas), the lemma level (containing the lemmas, the features associated with lemmas and pointers to trees) and the tree level (containing families of trees). If a word is not found in the lexicon, it returns an null answer.

It returns a set of trees associated to the input phrase. For some applications (Vulcain, MIAMM), we need to select only domain-specific lexicons. We intend to use several lexical services, using existing lexical services.

The metaservices

We also deploy in this architecture a set of reusable diagnostic modules. The first of these is the SOAPMeter, which is to be inserted between two SOAP nodes, such as a parser and its lexicon service. Once in place, the SOAP-Meter analyses the communication between the two nodes, and displays them as a series of individually timestamped SOAP messages. This way, the implementor knows instantly if instead of an actual problem with the modules themselves, there is a lower level problem, say, that the reason the parser is not doing anything useful is that it is not receiving any requests from the client. Once freed from these concerns, the implementor then proceeds to a higher level, seeing a series of requests and responses, rather than losing his place in the flow of HTTP headers and XML text.

To further illuminate these requests and responses, the SOAPMeter acts as a SOAP client for our PRISM 4 service, which receives XML text and returns a graphical representation of that text. XML messages can be challenging to read because so much of the message is dedicated to describe a document's structure, after wading through which, one does not attain a solid grasp on its contents or their relationship to each other. With a graphical representation, we no longer describe the structure, but show it,and furthermore, show it in a way that is relevant to the specific data at hand. Syntatic trees, for example, can be actual trees instead of block upon block of open/close XML tags. Likewise, if we were dealing instead with a logical description (such as Discourse Representation Structures DRSs) it 4 Parameretisably Readable Interpretation of SOAP Messages would be possible to visualise it as something more appropriate (for DRSs, using the classical "box" representation).

In PRISM, we acheive this parameterisability through the use of XML stylesheets (XSL) that describe the transformation of XML to graphics, which is to say that, changing the nature of a SOAP diagnosis is adding or changing a stylesheet rather than modifying any of the diagnostic software. As for the SOAPMeter, this leaves the implementor with a single button-click to visualise any SOAP messages which might be particularly interesting or difficult.

Applications

The system was developped in order to integrate the parser into complex applications: the MIAMM project (Multimedia Information Access using Multiple Modalities), developping a multi-modal interface (combining haptic, text, speech, graphics) to search songs in a database and the Vulcain project, dedicated to message filtering about computer security. The applications have various degrees of complexity and the resources are very different: Vulcain is an information-extraction system using local grammars and domain-specific lexicons, but MIAMM uses resources handling dialogue and reference resolution.

Conclusion

The paper illustrates a methodology for transforming a NLP module into a reusable, parametrizable component for a particular case: a LTAG parser. The methodology requires input/output and resource format standardization (XMLcompatible) and the definition of a communication protocol (SOAP). The methodology will be validated by transforming other NLP modules into reusable components, accessing resources available on-line. The SOAP protocol will be extended with more complex functions (handling XML references, implementing XML query for updating resources, extending the mechanisms for handling errors). The parser component will be integrated into an open architecture handling human-machine dialogues.

Figure 3 :

 3 Figure 3: System architecture

see http://www.loria.fr/projets/MIAMM

see http://www.loria.fr/projets/Guirlande

A revised version of TAGML is under discussion to provide more coverage of implementers' needs (representation of derivation trees, beeter representation of feature structures (closer compatibility with the TEI FS chapter) and should be published in the near future


Alexandre Chotard
email: alexandre.chotard@lri.fr

Martin Holeňa
email: martin@cs.cas.cz

A Generalized Markov-Chain Modelling Approach to (1, λ)-ES Linear Optimization: Technical Report

Keywords: evolution strategies, continuous optimization, linear optimization, linear constraint, linear function, Markov chain models, Archimedean copulas

Several recent publications investigated Markov-chain modelling of linear optimization by a (1, λ)-ES, considering both unconstrained and linearly constrained optimization, and both constant and varying step size. All of them assume normality of the involved random steps, and while this is consistent with a black-box scenario, information on the function to be optimized (e.g. separability) may be exploited by the use of another distribution. The objective of our contribution is to complement previous studies realized with normal steps, and to give sufficient conditions on the distribution of the random steps for the success of a constant step-size (1, λ)-ES on the simple problem of a linear function with a linear constraint. The decomposition of a multidimensional distribution into its marginals and the copula combining them is applied to the new distributional assumptions, particular attention being paid to distributions with Archimedean copulas.

Introduction

Evolution Strategies (ES) are Derivative Free Optimization (DFO) methods, and as such are suited for the optimization of numerical problems in a black-box context, where the algorithm has no information on the function f it optimizes (e.g. existence of gradient) and can only query the function's values. In such a context, it is natural to assume normality of the random steps, as the normal distribution has maximum entropy for given mean and variance, meaning that it is the most general assumption one can make without the use of additional information on f . However such additional information may be available, and then using normal steps may not be optimal. Cases where different distributions have been studied include so-called Fast Evolution Strategies [START_REF] Yao | Fast evolution strategies[END_REF] or SNES [START_REF] Schaul | Benchmarking Separable Natural Evolution Strategies on the Noiseless and Noisy Black-box Optimization Testbeds[END_REF][START_REF] Schaul | High dimensions and heavy tails for natural evolution strategies[END_REF] which exploits the separability of f , or heavy-tail distributions on multimodal problems [START_REF] Hansen | When do heavy-tail distributions help?[END_REF][START_REF] Schaul | High dimensions and heavy tails for natural evolution strategies[END_REF].

In several recent publications [START_REF] Arnold | On the behaviour of the (1,λ)-ES for a simple constrained problem[END_REF][START_REF] Arnold | On the behaviour of the (1, λ)-σSA-ES for a constrained linear problem[END_REF][START_REF] Chotard | Cumulative step-size adaptation on linear functions[END_REF][START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF], attention has been paid to Markov-chain modelling of linear optimization by a (1, λ)-ES, i.e. by an evolution strategy in which λ children are generated from a single parent X ∈ R n by adding normally distributed n-dimensional random steps M , X ← X + σC 1 2 M , where M ∼ N (0, In).

(1)

Here, σ is called step size, C is a covariance matrix, and N (0, I n ) denotes the ndimensional standard normal distribution with zero mean and covariance matrix identity. The best among the λ children, i.e. the one with the highest fitness, becomes the parent of the next generation, and the step-size σ and the covariance matrix C may then be adapted to increase the probability of sampling better children. In this paper we relax the normality assumption of the movement M to a more general distribution H.

The linear function models a situation where the step-size is relatively small compared to the distance towards a local optimum. This is a simple problem that must be solved by any effective evolution strategy by diverging with positive increments of ∇f.M . This unconstrained case was studied in [START_REF] Chotard | Cumulative step-size adaptation on linear functions[END_REF] for normal steps with cumulative step-size adaptation (the step-size adaptation mechanism in CMA-ES [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF]).

Linear constraints naturally arise in real-world problems (e.g. need for positive values, box constraints) and also model a step-size relatively small compared to the curvature of the constraint. Many techniques to handle constraints in randomised algorithms have been proposed (see [START_REF] Coello Coello | Constraint-handling techniques used with evolutionary algorithms[END_REF]). In this paper we focus on the resampling method, which consists in resampling any unfeasible candidate until a feasible one is sampled. We chose this method as it makes the algorithm easier to study, and is consistent with the previous studies assuming normal steps [START_REF] Arnold | On the behaviour of the (1 + 1)-ES for a simple constrained problem[END_REF][START_REF] Arnold | On the behaviour of the (1,λ)-ES for a simple constrained problem[END_REF][START_REF] Arnold | On the behaviour of the (1, λ)-σSA-ES for a constrained linear problem[END_REF][START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF], studying constant step-size, self adaptation and cumulative step-size adaptation mechanisms (with fixed covariance matrix).

Our aim is to study the (1, λ)-ES with constant step-size, constant covariance matrix and random steps with a general absolutely continuous distribution H optimizing a linear function under a linear constraint handled through resampling. We want to extend the results obtained in [START_REF] Arnold | On the behaviour of the (1,λ)-ES for a simple constrained problem[END_REF][START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF] using the theory of Markov chains. It is our hope that such results will help in designing new algorithms using information on the objective function to make non-normal steps. We pay a special attention to distributions with Archimedean copulas, which are a particularly well transparent alternative to the normal distribution. Such distributions have been recently considered in the Estimation of Distribution Algorithms [START_REF] Cuesta-Infante | Bivariate empirical and n-variate archimedean copulas in estimation of distribution algorithms[END_REF][START_REF] Wang | Copula estimation of distribution algorithms based on exchangeable archimedean copula[END_REF], continuing the trend of using copulas in that kind of evolutionary optimization algorithms [START_REF] Salinas-Gutierrez | Using copulas in estimation of distribution algorithms[END_REF].

In the next section, the basic setting for modelling the considered evolutionary optimization task is formally defined. In Section 3, the distributions of the feasible steps and of the selected steps are linked to the distribution of the random steps, and another way to sample them is provided. In Section 4, it is shown that, under some conditions on the distribution of the random steps, the normalized distance to the constraint is a ergodic Markov chain, and a law of large numbers for Markov chains is applied. Finally, Section 5 gives properties on the distribution of the random steps under which some of the aforementioned conditions are verified.

Notations

For (a, b) ∈ N 2 with a < b, [a..b] denotes the set of integers i such that a ≤ i ≤ b.

For X and Y two random vectors, X

= Y denotes that these variables are equal in distribution, X a.s.

→ Y and X P → Y denote, respectively, almost sure convergence and convergence in probability. For (x, y) ∈ R n , x.y denotes the scalar product between the vectors x and y, and for i ∈ [1..n], [x] i denotes the i th coordinate of x. For A a subset of R n , ½ A denotes the indicator function of A. For X a topological set, B(X ) denotes the Borel algebra on X .

Problem setting and algorithm definition

Throughout this paper, we study a (1, λ)-ES optimizing a linear function f : R n → R where λ ≥ 2 and n ≥ 2, with a linear constraint g : R n → R, handling the constraint by resampling unfeasible solutions until a feasible solution is sampled.

Take (e k ) k∈ [1..n] a orthonormal basis of R n . We may assume ∇f to be normalized as the behaviour of an ES is invariant to the composition of the objective function by a strictly increasing function (e.g. h : x → x/ ∇f ), and the same holds for ∇g since our constraint handling method depends only on the inequality g(x) ≤ 0 which is invariant to the composition of g by a homothetic transformation. Hence w.l.o.g. we assume that ∇f = e 1 and ∇g = cos θe 1 + sin θe 2 with the set of feasible solutions X feasible := {x ∈ R n |g(x) ≤ 0}. We restrict our study to θ ∈ (0, π/2). Overall the problem reads

maximize f (x) = [x] 1 subject to g(x) = [x] 1 cos θ + [x] 2 sin θ ≤ 0 . (2)
At iteration t ∈ N, from a so-called parent point X t ∈ X feasible and with step-size σ t ∈ R * + we sample new candidate solutions by adding to X t a random vector σ t M i,j t where M i,j t is called a random step and (M i,j t ) i∈[1..λ],j∈N,t∈N is a i.i.d. sequence of random vectors with distribution H. The i index stands for the λ new samples to be generated, and the j index stands for the unbounded number of samples used by the resampling. We denote M i t a feasible step, that is the first element of (M i,j t ) j∈N such that X t + σ t M i t ∈ X feasible (random steps are sampled until a suitable candidate is found). The i th feasible solution

Y i t is then Y i t := X t + σ t M i t . (3)
Then we denote ⋆ := argmax i∈[1..λ] f (Y i t ) the index of the feasible solution maximizing the function f , and update the parent point where M ⋆ t is called the selected step. Then the step-size σ t , the distribution of the random steps H or other internal parameters may be adapted.

X t+1 := Y ⋆ t = X t + σ t M ⋆ t , (4)
Following [START_REF] Arnold | On the behaviour of the (1,λ)-ES for a simple constrained problem[END_REF][START_REF] Arnold | On the behaviour of the (1, λ)-σSA-ES for a constrained linear problem[END_REF][START_REF] Arnold | On the behaviour of the (1 + 1)-ES for a simple constrained problem[END_REF][START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF] we define δ t as

δ t := - g(X t ) σ t . (5)
3 Distribution of the feasible and selected steps

In this section we link the distributions of the random vectors M i t and M ⋆ t to the distribution of the random steps M i,j t , and give another way to sample M i t and M ⋆ t not requiring an unbounded number of samples.

Lemma 1. Let a (1, λ)-ES optimize the problem defined in (2) handling constraint through resampling. Take H the distribution of the random step M i,j t , and for δ

∈ R * + denote L δ := {x ∈ R n |g(x) ≤ δ}.
Providing that H is absolutely continuous and that H(L δ ) > 0 for all δ ∈ R + , the distribution Hδ of the feasible step and H⋆ δ the distribution of the selected step when δ t = δ are absolutely continuous, and denoting h, hδ and h⋆ δ the probability density functions of, respectively, the random step, the feasible step M i t and the selected step

M ⋆ t when δ t = δ hδ (x) = h(x)½ L δ (x) H(L δ ) , (6)
and

h⋆ δ (x) = λ hδ (x) Hδ ((-∞, [x] 1 ) × R n-1 ) λ-1 = λ h(x)½ L δ (x)H((-∞, [x] 1 ) × R n-1 ∩ L δ ) λ-1 H(L δ ) λ . ( 7
)
Proof. Let δ > 0, A ∈ B(R n ). Then for t ∈ N, i = 1 . . . λ, using the the fact that (M i,j t ) j∈N is a i.i.d. sequence

Hδ (A) = Pr(M i t ∈ A|δ t = δ) = j∈N Pr(M i,j t ∈ A ∩ L δ and ∀k < j, M i,k t ∈ L c δ |δ t = δ) = j∈N Pr(M i,j t ∈ A ∩ L δ |δ t = δ) Pr(∀k < j, M i,k t ∈ L c δ |δ t = δ) = j∈N H(A ∩ L δ )(1 -H(L δ )) j = H(A ∩ L δ ) H(L δ ) = A h(x)½ L δ (x)dx H(L δ ) ,
which yield Eq. ( 6) and that Hδ admits a density hδ and is therefore absolutely continuous.

Since

((M i,j t ) j∈N ) i∈[1..λ] is i.i.d., (M i t ) i∈[1..λ] is i.i.d. and H⋆ δ (A) = Pr(M ⋆ t ∈ A|δ t = δ) = λ i=1 Pr(M i t ∈ A and ∀j ∈ [1..λ]\{i}, [M i t ] 1 > [M j t ] 1 |δ t = δ) = λ Pr(M 1 t ∈ A and ∀j ∈ [2..λ], [M 1 t ] 1 > [M j t ] 1 |δ t = δ) = λ A hδ (x) Pr(∀j ∈ [2..λ], [M j t ] 1 < [x] 1 |δ t = δ)dx = A λ hδ (x) Hδ ((-∞, [x] 1 ) × R n-1 ) λ-1 dx ,
which shows that H⋆ δ possess a density, and with (6) yield Eq. ( 7).

⊓ ⊔

The vectors (M i t ) i∈[1..λ] and M ⋆ t are functions of the vectors (M i,j t ) i∈[1..λ],j∈N and of δ t . In the following Lemma an equivalent way to sample M i t and M ⋆ t is given which uses a finite number of samples. This method is useful if one wants to avoid dealing with the infinite dimension space implied by the sequence

(M i,j t ) i∈[1..λ,j∈N . Lemma 2. Let a (1, λ)-ES optimize problem (2)
, handling the constraint through resampling, and take δ t as defined in [START_REF] Arnold | On the behaviour of the (1,λ)-ES for a simple constrained problem[END_REF]. Let H denote the distribution of M i,j t that we assume absolutely continuous, ∇g ⊥ :=sin θe 1 + cos θe 2 , Q the rotation matrix of angle θ changing (e 1 , e 2 , . . . , e n ) into (∇g, ∇g ⊥ , . . . , e n ). Take

F 1,δ (x) := Pr(M i t .∇g ≤ x|δ t = δ), F 2,δ (x) := Pr(M i t .∇g ⊥ ≤ x|δ t = δ) and F k,δ (x) := Pr([M i t ] k ≤ x|δ t = δ) for k ∈ [3.
.n], the marginal cumulative distribution functions when δ t = δ, and C δ the copula of (M i t .∇g,

M i t .∇g ⊥ , . . . , M i t .e n ).
We define

G : (δ, (u i ) i∈[1..n] ) ∈ R + × [0, 1] n → Q    F -1 1,δ (u 1 )
. . .

F -1 n,δ (u n )    , (8)
G ⋆ : (δ, (v i ) i∈[1..λ] ) ∈ R + × [0, 1] nλ → argmax G∈{G(δ,vi)|i∈[1..λ]} f (G) . (9)
Then, if the copula C δ is constant in regard to δ, for

W t = (V i,t ) i∈[1..λ] a i.i.d. sequence with V i,t ∼ C δ G(δ t , V i,t ) (d) = M i t , (10)
G ⋆ (δ t , W t ) (d) = M ⋆ t . (11)
Proof.

Since V i,t ∼ C δ (M i t .∇g, M i t .∇g ⊥ , . . . , M i t .e n ) (d) = (F -1 1,δ (V 1,t ), F -1 2,δ (V 2,t ), . . . , F -1 n,δ (V n,t )) ,
and if the function

δ ∈ R + → C δ is constant, then the sequence of random vectors (V i,t ) i∈[1..λ],t∈N is i.i.d.. Finally by definition Q -1 M i t = (M i t .∇g, M i t .∇g ⊥ , . . . , M i t .e n )
, which shows Eq. [START_REF] Coello Coello | Constraint-handling techniques used with evolutionary algorithms[END_REF]. Eq. ( 11) is a direct consequence of Eq. ( 10) and the fact that

M ⋆ t = argmax G∈{G(δ,vi)|i∈[1..λ]} f (G) (which holds as f is linear). ⊓ ⊔
We may now use these results to show the divergence of the algorithm when the step-size is constant, using the theory of Markov chains [START_REF] Meyn | Markov chains and stochastic stability[END_REF].

Divergence of the (1, λ)-ES with constant step-size

Following the first part of [START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF], we restrict our attention to the constant step size in the remainder of the paper, that is for all t ∈ N we take σ t = σ ∈ R * + . From Eq. ( 4), by recurrence and dividing by t, we see that

[X t -X 0 ] 1 t = σ t t-1 i=0 M ⋆ i . (12)
The latter term suggests the use of a Law of Large Numbers to show the convergence of the LHS (Left Hand Side) to a constant that we call the divergence rate.

δ t+1 = δ t -g(M ⋆ t ) = δ t -cos θ[M ⋆ t ] 1 -sin θ[M ⋆ t ] 2 . ( 13
)
Proof. By definition in [START_REF] Arnold | On the behaviour of the (1,λ)-ES for a simple constrained problem[END_REF] and since for all t, σ t = σ,

δ t+1 = - g(X t+1 ) σ t+1 = - g(X t ) + σg(M ⋆ t ) σ = δ t -g(M ⋆ t ) ,
and as shown in [START_REF] Chotard | Cumulative step-size adaptation on linear functions[END_REF] the density of M ⋆ t is determined by δ t . So the distribution of δ t+1 is determined by δ t , hence (δ t ) t∈N is a time-homogeneous Markov chain. ⊓ ⊔

We now show ergodicity of the Markov chain (δ t ) t∈N , which implies that the t-steps transition kernel (the function A → Pr(δ t ∈ A|δ 0 = δ) for A ∈ B(R + )) converges towards a stationary measure π, generalizing Propositions 3 and 4 of [START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF].

Proposition 2. Let a (1, λ)-ES with constant step-size optimize problem (2), handling the constraint through resampling. We assume that the distribution of M i,j t is absolutely continuous with probability density function h, and that h is continuous and strictly positive on R n . Denote µ + the Lebesgue measure on (R + , B(R + )), and for α > 0 take the functions V : δ → δ, V α : δ → exp(αδ) and r 1 : δ → 1. Then (δ t ) t∈N is µ + -irreducible, aperiodic and compact sets are small sets for the Markov chain.

If the following two additional conditions are fulfilled

E(|g(M i,j t )| | δ t = δ) < ∞ for all δ ∈ R + , and (14)
lim δ→+∞ E(g(M ⋆ t )|δ t = δ) ∈ R * + , (15)
then (δ t ) t∈N is r 1 -ergodic and positive Harris recurrent with some invariant measure π. Furthermore, if

E(exp(g(M i,j t ))|δ t = δ) < ∞ for all δ ∈ R + , (16)
then for α > 0 small enough, (δ t ) t∈N is also V α -geometrically ergodic.

Proof. The probability transition kernel of (δ t ) t∈N writes

P (δ, A) = R n ½ A (δ -g(x)) h⋆ δ (x)dx = R n ½ A (δ -g(x))λ h(x)½ L δ (x)H((-∞, [x] 1 ) × R n-1 ∩ L δ ) λ-1 H(L δ ) λ = λ H(L δ ) λ g -1 (A) h      δ -[u] 1 -[u] 2 . . . -[u] n      H((-∞, δ -[u] 1 ) × R n-1 ∩ L δ ) λ-1 du , with the substitution of variables [u] 1 = δ -[x] 1 and [u] i = -[x] i for i ∈ [2..n]. Denote L ⋆ δ,v := (-∞, v) × R n-1 ∩ L δ and t δ : u → (δ -[u] 1 , -[u] 2 , . . . , -[u] n ), take C a compact of R + , and define ν C such that for A ∈ B(R + ) ν C (A) := λ g -1 (A) inf δ∈C h(t δ (u))H(L ⋆ δ,[u]1 ) λ-1 H(L δ ) λ du .
As the density h is supposed to be strictly positive on R n , for all δ ∈ R + we have H(L δ ) ≥ H(L 0 ) > 0. Using the fact that H is a finite measure, and is absolutely continuous, applying the dominated convergence theorem shows that the functions δ → H(L δ ) and

δ → H((-∞, δ -[u] 1 )×R n-1 ∩L δ ) are continuous. Therefore the function δ → h(t δ (u))H(L ⋆ δ,[u]1 ) λ-1 /H(L δ )
λ is continuous and C being a compact, the infimum of this function is reached on C is reached on C. Since this function is strictly positive, if g -1 (A) has strictly positive Lebesgue measure then ν C (A) > 0 which proves that this measure is not trivial. By construction P (δ, A) ≥ ν C (A) for all δ ∈ C, so C is a small set which shows that compact sets are small. Since if µ + (A) > 0 we have P (δ, A) ≥ ν C (A) > 0, the Markov chain (δ t ) t∈N is µ + -irreducible. Finally, if we take C a compact set of R + with strictly positive Lebesgue measure, then it is a small set and ν C (C) > 0 which means the Markov chain (δ t ) t∈N is strongly aperiodic.

The function ∆V is defined as δmapstoE(V (δ t+1 )|δ t = δ) -V (δ). We want to show a drift condition (see [START_REF] Meyn | Markov chains and stochastic stability[END_REF]) on V . Using Eq. ( 13)

∆V (δ) = E(δ -g(M ⋆ t )|δ t = δ) -δ) = -E(g(M ⋆ t )) .
Therefore using the condition (15), we have that there exists a ǫ > 0 and a M ∈ R + such that ∀δ ∈ (M, +∞), ∆V (δ) ≤ -ǫ. With condtion [START_REF] Salinas-Gutierrez | Using copulas in estimation of distribution algorithms[END_REF] implies that the function

∆V + ǫ is bounded on the compact [0, M ] by a constant b ∈ R. Hence for all δ ∈ R + ∆V (δ) ǫ ≤ -1 + b ǫ ½ [0,M] (δ) . (17)
For all x ∈ R the level set C V,x of the function V , {y ∈ R + |V (y) ≤ x}, is equal to [0, x] which is a compact set, hence a small set according to what we proved earlier (and hence petite [15, Proposition 5.5.3]). Therefore V is unbounded off small sets and with (17) and Theorem 9.1.8 of [START_REF] Meyn | Markov chains and stochastic stability[END_REF], the Markov chain (δ t ) t∈N is Harris recurrent. The set [0, M ] is compact and therefore small and petite, so with (17), if we denote r 1 the constant function δ ∈ R + → 1 then with Theorem 14.0.1 of [START_REF] Meyn | Markov chains and stochastic stability[END_REF] the Markov chain (δ t ) t∈N is positive and is r 1 -ergodic. We now want to show a drift condition (see [START_REF] Meyn | Markov chains and stochastic stability[END_REF]) on V α .

∆V α (δ) = E (exp (αδ -αg (M ⋆ t )) |δ t = δ) -exp (αδ) ∆V α V α (δ) = E (exp (-αg (M ⋆ t )) |δ t = δ) -1 = R n lim t→+∞ t k=0 (-αg(x)) k k! h⋆ δ (x)dx -1 .
With Eq. ( 7) we see that h⋆ δ (x) ≤ λh(x)/H(L 0 ) λ , so with our assumption that E(exp α|g(M i,j t )||δ t = δ) < ∞ for α > 0 small enough we have that the function δ → E(exp(α|g(M ⋆ t )||δ t = δ) is bounded for the same α. As t k=0 (-αg(x)) k /k! h⋆ δ (x) ≤ exp(α|g(x)|) h⋆ δ (x) which, with condition ( 16), is integrable so we may apply the theorem of dominated convergence to invert limit and integral:

∆V α V α (δ) = lim t→+∞ t k=0 R n (-αg(x)) k k! h⋆ δ (x)dx -1 = k∈N (-α) k E g (M ⋆ t ) k |δ t = δ k! -1 Since h⋆ δ (x) ≤ λh(x)/H(L 0 ) 2 , (-α) k E(g(M ⋆ t ) k |δ t = δ)/k! ≤ (-α) k E(g(M i,j t ) k )/k!
which is integrable with respect to the counting measure so we may apply the dominated convergence theorem with the counting measure to invert limit and serie.

lim δ→+∞ ∆V α V α (δ) = k∈N lim δ→+∞ (-α) k E g (M ⋆ t ) k |δ t = δ k! -1 = -α lim δ→+∞ E (g (M ⋆ t ) |δ t = δ) + o (α) .
With condition (17) we supposed that lim δ→+∞ E(g(M ⋆ t )|δ t = δ) > 0 this implies that for α > 0 and small enough, lim δ→+∞ ∆V α (δ)/V α (δ) < 0, hence there exists M ∈ R + and epsilon > 0 such that ∀δ > M , ∆V α (δ) < -ǫV α (δ). Finally as

∆V α -V α is bounded on [0, M ] there exists b ∈ R such that ∆V α (δ) ≤ -ǫV α (δ) + b½ [0,M] (δ) .
According to what we did before in this proof, the compact set [0, M ] is small, and hence is petite ([15, Proposition 5.5.3]). So the µ + -irreducible Markov chain (δ t ) t∈N satisfies the conditions of Theorem 15.0.1 of [START_REF] Meyn | Markov chains and stochastic stability[END_REF] which with Theorem 14.0.1 of [START_REF] Meyn | Markov chains and stochastic stability[END_REF] proves that the Markov chain (δ t ) t∈N is V α -geometrically ergodic.

⊓ ⊔

We now use a law of large numbers ( [START_REF] Meyn | Markov chains and stochastic stability[END_REF] Theorem 17.0.1) on the Markov chain (δ t , (M i,j t ) i∈[1..λ],j∈N ) t∈N to obtain an almost sure divergence of the algorithm.

Proposition 3. Let a (1, λ)-ES optimize problem (2), handling the constraint through resampling. Assume that the distribution H of the random step M i,j t is absolutely continuous with continuous and strictly positive density h, that conditions ( 16) and (15) of Proposition 2 hold, and denote π and µ M the stationary distribution of respectively (δ t ) t∈N and i,j t ) i∈[1..λ],(j,t)∈N 2 . Then

[X t -X 0 ] 1 t a.s. -→ t→+∞ σE π×µM ([M ⋆ t ] 1 ) . ( 18
)
Furthermore if E([M ⋆ t ] 2 ) < 0, then the right hand side of Eq. ( 18) is strictly positive.

Proof. According to Proposition 2 the sequence (δ t ) t∈N is a Harris recurrent positive Markov chain with invariant measure π. [START_REF] Meyn | Markov chains and stochastic stability[END_REF], we may apply a law of large numbers on the right hand side of Eq. ( 12) to obtain (18).

As (M i,j t ) i∈[1..λ],(j,t)∈N 2 is a i.i.d. sequence with distribution µ M , (δ t , (M i,j t ) i∈[1..λ],j∈N ) t∈N is also a Harris recur- rent positive Markov chain. As [M ⋆ t ] 1 is a function of δ t and (M i,j t ) i∈[1..λ],j∈N , if E π×µM (|[M ⋆ t ] 1 |) < ∞, according to Theorem 17.0.1 of
Using Fubini-Tonelli's theorem

E π×µM (|[M ⋆ t ] 1 |) = E π (E µM (|[M ⋆ t ] 1 ||δ t = δ)
). From Eq. ( 7) for all x ∈ R n , h⋆ δ (x) ≤ λh(x)/H(L 0 ) 2 , so the condition in [START_REF] Beyer | Toward a theory of evolution strategies: Self-adaptation[END_REF] implies that for all

δ ∈ R + , E µM (|[M ⋆ t ] 1 ||δ t = δ) is finite. Furthermore, with condition (15), the function δ ∈ R + → E µM (|[M ⋆ t ] 1 ||δ t = δ) is bounded by some M ∈ R. Therefore as π is a probability measure, E π (E µM (|[M ⋆ t ] 1 ||δ t = δ)) ≤ M < ∞
so we may apply the law of large numbers of Theorem 17.0.1 of [START_REF] Meyn | Markov chains and stochastic stability[END_REF].

Using the fact that π is an invariant measure, we have

E π (δ t ) = E π (δ t+1 ), so E π (δ t ) = E π (δ t -σg(M ⋆ t )) and hence cos θE π ([M ⋆ t ] 1 ) = -sin θE π ([M ⋆ t ]
2 ). So using the assumption that E([M i,j t ] 2 ) ≤ 0 then we get the strict positivity of E π×µM ([M i,j t ] 1 ). ⊓ ⊔

Application to More Specific Distributions

Throughout this section we give cases where the assumptions on the distribution of the random steps H used in Proposition 2 or Proposition 3 are verified.

The following lemma shows an equivalence between a non-identity covariance matrix for H and a different norm and constraint angle θ. Lemma 3. Let a (1, λ)-ES optimize problem (2), handling the constraint with resampling. Assume that the distribution H of the random step M i,j t has positive definite covariance matrix C with eigenvalues (α 2 i ) i∈[1.

.n] and take B = (b i,j ) (i,j)∈[1.

.n] 2 such that BCB -1 is diagonal. Denote A H,g,X0 the sequence of parent points (X t ) t∈N of the algorithm with distribution H for the random steps M i,j t , constraint angle θ and initial parent X 0 . Then for all k ∈ [1.

.n]

β k [A H,θ,X0 ] k (d) = A C -1/2 H,θ ′ ,X ′ 0 k , (19)
where

β k = n j=1 b 2 j,i α 2 i , θ ′ = arccos( β1cosθ βg ) with β g = β 2 1 cos 2 θ + β 2 2 sin 2 θ, and [X ′ 0 ] k = β k [X 0 ] k for all k ∈ [1..n].
Proof. Take (ē k ) k∈[1.

.n] the image of (e k ) k∈ [1..n] by B -1 . We define a new norm

• -such that ēk -= 1/α k . We define two orthonormal basis (e ′ k ) k∈[1..n] and (ē ′ k ) k∈[1..n] for (R n , • -) by taking e ′ k = e k / e k -and ē′ k = ēk / ēk -= α k ēk . As Var(M i,j t .ē k ) = α 2 k , Var(M i,j t .ē ′ k ) = 1 so in (R n , • -) the covariance matrix of M i,j
t is the identity. Take h the function that to x ∈ R n maps its image in the new orthonormal basis (e

′ k ) k∈[1..n] . As e ′ k = e k / e k -, h(x) = ( e k -[x] k ) k∈[1..n]
, where

e k -= n i=1 b i,k ēk -= n i=1 b 2 i,k /α 2 k = β k .
As we changed the norm, the angle between ∇f and ∇g is also different in the new space. Indeed cos

θ ′ = h(∇g).h(∇f )/( h(∇g) -h(∇f ) -) = β 2 1 cos θ/( β 2 1 cos 2 θ + β 2 2 sin 2 θβ 1 ) = β 1 cos θ/β g . If we take N i,j t ∼ C -1/2
H then it has the same distribution as h(M i,j t ). Take X ′ t = h(X t ) then for a constraint angle θ ′ = arccos(β 1 cos θ/β g ) and a normalized distance to the constraint δ t = X ′ t .h(∇g)/σ t the ressampling is the same for N i,j t and h(M i,j t ) so ⊓ ⊔ Although Eq. ( 18) shows divergence of the algorithm, it is important that it diverges in the right direction, i.e. that the right hand side of Eq. ( 18) has a positive sign. This is achieved when the distribution of the random steps is isotropic, as stated in the following proposition. Proposition 4. Let a (1, λ)-ES optimize problem (2) with constant step-size, handling the constraint with resampling. Suppose that the Markov chain (δ t ) t∈N is positive Harris, that the distribution H of the random step M i,j t is absolutely continuous with strictly positive density h, and take C its covariance matrix. If the distribution

N i t (d) = h(M i t ).
C -1/2 H is isotropic then E π×µM ([M ⋆ t ] 1 ) > 0.
Proof. First if C = I n , using the same method than in the proof of Lemma 1

h ⋆ δ,2 (y) = λ R . . . R hδ (u 1 , y, u 3 , . . . , u n ) Pr(u 1 ≥ [M i t ] 1 ) λ-1 du 1 n k=3 du k .
Using Eq.( 6) and the fact that the condition x ∈ L δ is equivalent to

[x] 1 ≤ (δ -[x] 2 sin θ)/ cos θ we obtain h ⋆ δ,2 (y) = λ R . . . δ-y sin θ cos θ -∞ h(u 1 , y, u 3 , . . . , u n ) H(L δ ) Pr(u 1 ≥ [M i t ] 1 ) λ-1 du 1 n k=3 du k .
If the distribution of the random steps steps is isotropic then h(u 1 , y, u 3 , . . . , u n ) = h(u 1 , -y, u 3 , . . . , u n ), and as the density h is supposed strictly positive, for y > 0 and all δ ∈, Proof. Suppose M i,j t ∼ N (0, I n ). Then H is absolutely continuous and h is strictly positive. The function x → exp(g(x)) exp(x 2 /2)/ √ 2π is integrable, so Eq. ( 16) is satisfied. Furthermore, when δ → +∞ the constraint disappear so M i,j t behaves like (N λ:λ , N (0, 1), . . . , N (0, 1)) where N λ:λ is the last order statistic of λ i.i.d. standard normal variables, so using that E(N λ:λ ) > 0 and E(N (0, 1)) = 0, with multiple uses of the dominated convergence theorem we obtain condition (15) so with Proposition 2 the Markov chain (δ t ) t∈N is geometrically ergodic and positive Harris.

h ⋆ δ,2 (y) -h ⋆ δ,2 (-y) < 0 so E([M ⋆ t ] 2 |δ t = δ) < 0.
Finally H being isotropic the conditions of Proposition 4 are fulfilled, and therefore so are every condition of Proposition 3 which shows what we wanted.

⊓ ⊔

To obtain sufficient conditions for the density of the random steps to be strictly positive, it is advantageous to decompose that distribution into its marginals and the copula combining them. We pay a particular attention to Archimedean copulas, i.e., copulas defined

(∀u ∈ [0, 1] n ) C ψ (u) = ψ(ψ -1 ([u] 1 ) + • • • + ψ -1 ([u] n )), (20)
where ψ : [0, +∞] → [0, 1] is an Archimedean generator, i.e., ψ(0) = 1, ψ(+∞) = lim t→+∞ ψ(t) = 0, ψ is continuous and strictly decreasing on [0, inf{t : ψ(t) = 0}), and ψ -1 denotes the generalized inverse of ψ,

(∀u ∈ [0, 1]) ψ -1 (u) = inf{t ∈ [0, +∞] : ψ(t) = u}. (21)
The reason for our interest is that Archimedean copulas are invariant with respect to permutations of variables, i.e.,

(∀u ∈ [0, 1] n ) C ψ (Qu) = C ψ (u). ( 22
)
holds for any permutation matrix Q ∈ R n,n . This can be seen as a weak form of isotropy because in the case of isotropy, (20) holds for any rotation matrix, and a permutation matrix is a specific rotation matrix.

Proposition 6. Let H be the distribution of the two first dimensions of the random step M i,j t , H 1 and H 2 be its marginals, and C be the copula relating H to H 1 and H 2 . Then the following holds:

1. Sufficient for H to have a continuous strictly positive density is the simultaneous validity of the following two conditions. (i) H 1 and H 2 have continuous strictly positive densities h 1 and h 2 , respectively. (ii) C has a continuous strictly positive density c. Moreover, if (i) and (ii) are valid, then

(∀x ∈ R 2 ) h(x) = c(H 1 ([x] 1 ), H 2 ([x] 2 ))h 1 ([x] 1 )h 2 ([x] 2 ). ( 23
)
2. If C is Archimedean with generator ψ, then it is sufficient to replace (ii) with (ii') ψ is at least 4-monotone, i.e., ψ is continuous on [0, +∞], ψ ′′ is decreasing and convex on R + , and (∀t ∈ R + ) (-1) k ψ (k) (t) ≥ 0, k = 0, 1, 2. In this case, if (i) and (ii') are valid, then

(∀x ∈ R 2 ) h(x) = ψ ′′ (ψ -1 (H 1 ([x] 1 )) + ψ -1 (H 2 ([x] 2 ))) ψ ′ (ψ -1 (H 1 ([x] 1 )) + ψ -1 (H 2 ([x] 2 ))) h 1 ([x] 1 )h 2 ([x] 2 ).
(24)

Discussion

The paper presents a generalization of recent results of the first author [START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF] concerning linear optimization by a (1, λ)-ES in the constant step size case. The generalization consists in replacing the assumption of normality of random steps involved in the evolution strategy by substantially more general distributional assumptions. This generalization shows that isotropic distributions solve the linear problem. Also, although the conditions for the ergodicity of the studied Markov chain accept some heavy-tail distributions, an expnentially vanishing tail allow for geometric ergodicity, which imply a faster convergence to its stationary distribution, and faster convergence of Monte Carlo simulations. In our opinion, these conditions increase the insight into the role that different kinds of distributions play in evolutionary computation, and enlarges the spectrum of possibilities for designing evolutionary algorithms with solid theoretical fundamentals. At the same time, applying the decomposition of a multidimensional distribution into its marginals and the copula combining them, the paper attempts to bring a small contribution to the research into applicability of copulas in evolutionary computation, complementing the more common application of copulas to the Estimation of Distribution Algorithms [START_REF] Cuesta-Infante | Bivariate empirical and n-variate archimedean copulas in estimation of distribution algorithms[END_REF][START_REF] Salinas-Gutierrez | Using copulas in estimation of distribution algorithms[END_REF][START_REF] Wang | Copula estimation of distribution algorithms based on exchangeable archimedean copula[END_REF].

Needless to say, more realistic than the constant step size case, but also more difficult to investigate, is the varying step size case. The most important results in [START_REF] Chotard | Markov chain analysis of evolution strategies on a linear constraint optimization problem[END_REF] actually concern that case. A generalization of those results for non-Gaussian distributions of random steps for cumulative step-size adaptation ( [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF]) is especially difficult as the evolution path is tailored for Gaussian steps, and some careful tweaking would have to be applied. The σ self-adaptation evolution strategy ( [START_REF] Beyer | Toward a theory of evolution strategies: Self-adaptation[END_REF]), studied in [START_REF] Arnold | On the behaviour of the (1, λ)-σSA-ES for a constrained linear problem[END_REF] for the same problem, appears easier, and would be our direction for future research.

Fig. 1 .

 1 Fig.1. Linear function with a linear constraint, in the plane spanned by ∇f and ∇g, with the angle from ∇f to ∇g equal to θ ∈ (0, π/2). The point x is at distance g(x) from the constraint hyperplan g(x) = 0.

  Finally the rankings induced by ∇f or h(∇f ) are the same so the selection in the same, hence N ⋆ t

  The random vectors (M ⋆ t ) t∈N are not i.i.d. so in order to apply a Law of Large Numbers on the RHS (Right Hand Side) of the previous equation we use Markov chain theory, more precisely the fact that (M ⋆ t ) t∈N is a function of a (δ t , (M i,j t ) i∈[1..λ],j∈N ) t∈N which is a geometrically ergodic Markov chain. As (M i,j t ) i∈[1..λ],j∈N,t∈N is a i.i.d. sequence, it is a Markov chain, and the sequence (δ t ) t∈N is also a Markov chain as stated in the following proposition.Proposition 1. Let a (1, λ)-ES with constant step-size optimize problem (2), handling the constraint through resampling, and take δ t as defined in[START_REF] Arnold | On the behaviour of the (1,λ)-ES for a simple constrained problem[END_REF]. Then no matter what distribution the i.i.d. sequence (M i,j t ) i∈[1..λ],(j,t)∈N 2 have, (δ t ) t∈N is a homogeneous Markov chain and

  If the Markov chain is Harris recurrent and positive then this imply that E π ([M ⋆ t ] 2 ) < 0 and using the reasoning in the proof of Proposition 3 E π ([M ⋆ t ] 1 ) > 0. For any covariance matrix C this result is generalized with the use of Lemma 3.Proposition 5. Let a (1, λ)-ES optimize problem (2) with constant step-size, handling the constraint with resampling. If H is a multivariate normal distribution with mean 0, then (δ t ) t∈N is a geometrically ergodic positive Harris Markov chain, Eq. (18) holds and its right hand side is strictly positive.

	⊓ ⊔
	Lemma 3 and Proposition 4 imply the following result to hold for multivariate
	normal distributions.

Acknowledgment

The research reported in this paper has been supported by grant ANR-2010-COSI-002 (SIMINOLE) of the French National Research Agency, and Czech Science Foundation (GA ČR) grant 13-17187S.


Daan Broeder

Peter Wittenburg
email: peter.wittenburg@mpi.nl

Thierry Declerck

Laurent Romary

LREP: A Language Repository Exchange Protocol

The recent increase in the number and complexity of the language resources available on the Internet is followed by a similar increase of available tools for linguistic analysis. Ideally the user does not need to be confronted with the question in how to match tools with resources. If resource repositories and tool repositories offer adequate metadata information and a suitable exchange protocol is developed this matching process could be performed (semi-) automatically.

Introduction

The domain of linguistics is faced with an enormous increase of available language resources and an increasing amount and diversity of available tools that operate on these resources. Also the improved computational facilities have made it possible that many tools and resources do no longer depend on storage with one of the large resource distribution agencies as ELRA and LDC but are stored at the many individual research institutes. Add to this the increasing reliability and bandwidth of the Internet and the availability of high quality Internet connections for even home PC's. There we have a situation that demands the development of an organisational plan together with exploitation tools that offer the user one integrated view of these two complementary domains of tools and resources.

A recent [ACL/EACL] workshop [START_REF]Proceedings of the ACL/EACL Workshop Sharing tools and Resources[END_REF] clearly indicated the needs of the community and the potential present in the current registries waiting to be unlocked by appropriate mechanisms and protocols. This work does not appear out of the void; in place already are the DFKI/ACL tool descriptions [START_REF]The ACL Natural Language Software Registry[END_REF] and the IMDI [START_REF]ISLE Metadata Initiative[END_REF] and OLAC [START_REF]Open Language Archive Community[END_REF] language resource description environments.

The purpose of this paper is to show the advantages that an integrated approach would offer and the required mechanisms and protocols for this that are needed.

Required Functionality

From the view point of the typical user a desirable scenario would be:

1. Locate suitable resources using metadata either by browsing or searching. 2. Find out what kind of suitable tools are available for these particular resources. 3. The user makes a selection of one of these tools.

Perhaps after making further inquiries. 4. Start up the selected tool with the resources already specified.

Another less typical scenario would be that of a tool builder who would like to find resources that fit with the particular tool he is testing or developing.

In any case both scenarios require the location of resources using metadata either on the basis of linguistic requirements or requirements concerning the data-type or format.

Once resources have been identified the next step would be to look what kind of tools are available and see if they would fit the particular type of the resources and needs of the users. That last requirement is something only the user can answer. For the moment we assume he will make a choice from a selection offered by a tool. Preferably this would be the same tool he used to locate the language resources in the first place. Note that the located resources are often not locally available and are identified by an URL. From that point on a number of options and possible complications exist that will need to be addressed by a protocol that regulates the proper exchange of relevant information. Just to give an impression here is a (by no means exhaustive) list: a) There can be locally installed tools that might be suitable. b) A tools repository might advertise suitable tools. c) The tool can be present on the tool repository itself. d) The repository might just have a link to its actual (remote) home. e) The site where the resource resides does not allow copying of the resource from the site but has itself a suitable tool available. (Statistics) f) The tool is not available for download.

Current State of Affairs

We will now make a small inventory of the current state of affairs with respect to required technology and start with the available standards that describe (metadata) language resources and linguistic tools. Then we look at possible mechanisms of communications between tool and language resource consumers and providers.

Language resource descriptions

First we will investigate what the current situation is with respect to language resource storage and description. The for our purposes, that is resource location and access, relevant way of describing language resources is by using metadata that is made available on the Internet.

At the moment there are two initiatives that claim to provide a relevant metadata set for the linguistic domain. First there is the ISLE Metadata Initiative (IMDI) started in 2000 that has tried to develop a metadata vocabulary from the bottom up starting with the requirements of the researcher and finally arrived at a complex set that can be considered the beginning of an ontology for the domain.

IMDI does not claim to describe more than the language resources only, but does offer a complete metadata environment that has handles to organise resources in browsable structures and bundle related resources in administrative units. Tools to create manipulate and exploit IMDI tagged resources are also provided. The IMDI project is also relevant because one of the tools developed shows tight functional integration of available linguistic tools and resources. The IMDI-BCBrowser, a tool to navigate the universe of IMDI tagged resources allows a user to map available local linguistic tools on resource types. Whenever a suitable resource comes in focus the applicable tools are available directly from this browser tool. See [START_REF]The IMDI Metadata Set, it's Tools and accessible Linguistic Databases[END_REF] for more details. This is a local variant of what we would like to achieve with a Language Repository Exchange Protocol (LREP).

The second relevant initiative is the Open Language Archive (OLAC). OLAC has created a specialisation of the well-known Dublin Core (DC) [START_REF]DC or DCMES Dublin Core Metadata Element Set[END_REF] set for use in the linguistic domain. The specialisation involves the introduction of one new element in addition to the existing 15 of DC and the further adjustment of the other 15 by means of specialised qualifiers. OLAC claims not only to describe language resources but also wants to describe linguistic tools and "best practice" recommendations.

Currently there is an experiment transforming IMDI records to OLAC format in order to allow, although with considerable information loss, OLAC users to locate IMDI tagged resources.

Linguistic tool descriptions

With respect to tool repositories we refer mainly to the DFKI ACL Natural Language Software registry that maintains an exhaustive list of tools and offers it in a human readable form on the web but also allows export to DC records in an XML format so that its data can be harvested by protocols such as suggested by OAI [START_REF] Oai | [END_REF]. It uses a well-described taxonomy [START_REF]Art in the Human Language Technology[END_REF] that for our purposes will need to be further specialised.

The OLAC proposal uses DC elements to describe tools and although they have made the step to machine readable metadata what we require for our purposes, it remains to be seen if their set can describe these tools in sufficient detail.

Suitable exchange protocols.

Defining an exchange protocol can capitalize on the experience of other earlier initiatives. There is GATE [9,10] that is presented as a software architecture for NLP components. It enables experienced users to easily configure NLP systems. Although this tightly integrated system is a local one i.e. the software modules exchange information locally, it shows that some experience exists about the nature of the information to be exchanged.

Another example is the Browser tool [START_REF] Broeder | Interaction of Tools and Metadata-Descriptions for Multimedia Language Resources[END_REF] developed within the IMDI project mentioned before. The Browser facilitates an information exchange between the two domains of "Language Resources" and "Linguistic Tools" by examining a configuration file that maps tools to resource types/formats and offering the user a choice of tools for a specific set of resources. This is limited to locally installed tools only although it allows specification of tools that work on remote resources.

Evidently we need to generalise the described exchange mechanisms to more flexible exchange mechanisms that support distributed systems by nature. These requirements seem to be full-filled by emerging standards such as SOAP [START_REF]SOAP -A Simple Object Access Protocol[END_REF] but could just as well be supported by exchanging specific XML formatted messages via an existing network protocols as HTTP.

Functionality to add

The exact nature of the underlying protocol for communication between users, Resources Repositories and Tool Repositories either is not important. More important is to establish the information content that is to be exchanged. Following the typical usage scenario described above, we summarise the information sent by the Browser or Search tool to the Tool Repository in the form of a Tool Request Packet (TRP) as:

i.

Administrative information ii.

Function specification (what is the tool needed for) iii.

A resource type selection (The user might only be interested in audio while there are also annotations available) iv.

Operating environment for the tool (OS, available execution environment such as Java, Perl, available fonts etc.)

This information is received and validated by a tool repository that will try to match the received information with the tools it describes in its database. After processing it will return a response package with the following information:



Description of resources

The description of the resources needed by a tool repository to determine if a tool is suitable has until now been indicated by "resource type". This will obviously need to be more complex than just a single type specification element. The IMDI project has experimented with mime-types following the convention used on the Internet where resources are characterized by a type and sub-type (see Multipurpose Internet Mail Extensions as described in RFC 2046 [13]). In this way an annotation file in CHAT format would be described as "text/x-chat". This scheme is however not sufficient to express all necessary information as there is in some cases also need to describe different encoding types. IMDI did recognise this and later added special fields as "content-encoding" as the name of the encoding scheme used for annotation purposes and "character-encoding" to specify the character set used. A CHAT annotation file with morphosyntax information would be described as: o Type: annotation-unit/morpho-syntax o Format: text/chat o Content-encoding: eurotyp o Character-encoding: ISO-Latin1

As yet it is uncertain if this is a sufficient set for all the tools we need to administrate with LREP, the elements of the IMDI set for resource file typing are not altogether othogonal and any new extension will only complicate this further.

Groups of Coupled Resources

Often it will be the case that the user wants to operate on a group of linked resources. Think of the example that a multimedia/multi-modal resource has tightly coupled files for two video cameras, an internal and an external microphone, a track for laryngoscopic data and various annotations in separate files (see Figure 1).

Figure 1 Coupled MM resources

In the IMDI project this situation was understood from the beginning and the term "session" was introduced [START_REF] Broeder | A browsable Corpus: accessing linguistic resources the easy way[END_REF]. A session bundles various related data files and the corresponding metadata description contains links to all of them.

It is the task of the tool to use this information appropriately. When using the resource repository browser the user will select the session and not a particular file. When connecting to the tool repository he could want to operate on all or on a selection of them.

The resource type list field in the Tool Request Package (TRP) specifies if a subset of the included resources was selected, i.e. the user has to have the possibility to not only specify the function of the operation (in the shown example a wish to start an image processing tool would automatically imply that only the mpg files are relevant), but also the resource type to specify whether for example video or audio should be used 1 . Of course, there is a link between applications and resource types. However, it is expected that for example including all resource types of a metadata description as indicated above would result in offering almost all tools that are in the repository. Therefore, the user should be able to define a function -it should be an optional parameter -that indicates an analysis or display function beforehand. This information is present in the TRP. Questions whether for example video1 or video2 or both should be included in an operation have to be answered by the browser who will offer a list of all resources selected. The user should be able to tune his list.

All information is sent to the Tool Repository which will check on which formats the available tools can operate and will calculate a rating and generate warnings. The ratings will specify the degree of match and the warnings will say which types and formats cannot be included when using a certain tool. When a user selects one of the tools only those files that are compatible will be included in the start script. For the moment we assume a framework of separately executable tools that can be called from a script. More advanced schemes such as remotely executable tools are conceivable and need to be provided for.

Group of Unrelated Resources

The user may have selected various resources, which for example can be various text files only taken from various subjects, but it also could be that various sessions with mixed file types were selected. Operations like this could be wanted for example to train speech recognizers on a whole set of speech files together with their annotation files or a search on textual data which could be in various formats such as a certain XML format or an older legacy format such as CHAT. 1 Another option would be to present both filenames to the tool such that the tool will ask the user which one to select. But this will require more intelligence at the side of the tools. It cannot be assumed that builders of already existing tools want to modify their code extensively. We will discuss the most general case first. In the case of unrelated resources the user can only execute mass operations such as search, statistics, speech recognizer training etc. on them. Currently, there are already tools, which operate on different input formats, which means that a variety of formats is not problematic and the tool repository can match tools for them. In the future we can expect cases where search operations can be executed on texts as well as on sound or video files, i.e. there also a variety of file types does not have to be excluded. The user though, should have the possibility to make selections to decrease the complexity of the task.

It is therefore suggested that the Resource Repository Browser determines a list of file types and formats by reading all metadata descriptions of the selected resources and by interacting with the user.

All other configurations are specializations of this general one and can be handled in the same way.

Tool Execution

The usual working environment will need to have the standard tools already present on the local machine and the Resource Browser aware of this. Preferably these local tools are obtained from tool repositories during a previous work session. That way their configuration and start-up information can be in the same format as used for remote tools. Only if the user requires functionality not available from the locally configured tools or enters an explicit command, remote tool repositories will be contacted and queried.

We can distinguish between a number of cases with respect to the place where the tool and resources remain.

Local tool & local resources. The tool may have been downloaded first or have been present at the local site before. Important is that the Resource Browsing Tool has knowledge how to startup the tool and how to specify the resources the tool works on when executing the tool.

Local tool & remote resources. As above the Browse Tool knows how to start the tool. The tool itself must be able to handle remote resources (specified as an URL). Since not many tools are able to deal with remote resources the Browser can implement a mechanism to automatically download the resources to the local machine. This reduces to case 1. In case of multi-media resources this can be a slow affair.

Remote tool & remote resources at same site. Some sites offer resources as well as the tools that work on them. These sites have already integrated their resources localisation service with tools that work on these resources. It should be considered for each such a site what added value could be generated by opening up their resources to be used with other tools. As an example of an integrated service look at LACITO [START_REF]Linguistic Data Archiving Project (LACITO)[END_REF].

Remote Tool (not downloadable) & resources at different site. The only way to exploit such a tool would be if the tool in question would be remote executable and would work on remote resources or the site would allow the download of resources. This is certainly an interesting possibility when a site has a great quantity of statistic and search engines that depend on optimised machine configurations.

Future Developments

The development of the LREP protocol and working environment are part of the INTERA project that seems to start later this year.

Figure 2 .

 2 Figure 2. The session bundling resources