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

Darja Fišer
email: darja.fiser@ff.uni-lj.si

Automatic Extension of WOLF

In this paper we present the extension of WOLF, a freely available, automatically created wordnet for French, the biggest drawback of which has until now been the lack of general concepts that are typically expressed with highly polysemous vocabulary that is on the one hand the most valuable for applications in human language technologies but also the most difficult to add to wordnet accurately with automatic methods on the other. Using a set of features, we train a Maximum Entropy classifier on the existing core wordnet to be able to assign appropriate synset ids to new words, extracted from multiple, multilingual sources of lexical knowledge, such as Wiktionaries, Wikipedias and corpora. Automatic and manual evaluation shows high coverage as well as high quality of the resulting lexicosemantic repository of. Another important advantage of the approach is that it is fully automatic and language-independent and could therefore be applied to any other language still lacking a wordnet.

Introduction

Whatever the framework and representation of lexical knowledge, such as ontologies, framenets or wordnets, semantic lexicons can only contribute to applications in human language technologies, such as word-sense disambiguation, information extraction or machine translation, if their coverage is comprehensive as well as accurate. The language resources development community seems to have reached a consensus that, despite giving the most reliable results, manual construction of lexical resources is to time-consuming and expensive to be practical for most purposes. Several semi-or fully automatic approaches have been proposed instead, exploiting various types of existing resources to facilitate the development of a new semantic lexicon, especially wordnets. However, most proposed approaches to induce a wordnet automatically, still suffer from the necessary trade-off between limited coverage and the desired level of accuracy, both of which are required if the resource is to be useful in a practical application. This is why we present here an approach for wordnet extension by extracting additional lexico-semantic information from already available bilingual language resources and then training a maximum entropy classifier on the existing core wordnet in order to assign the new vocabulary to the appropriate synsets. Our approach, applied on the French wordnet WOLF, is comprehensive in that it can handle monosemous and polysemous words from all parts of speech which belong to the general vocabulary as well as specialized domains and can also deal with multi-word expressions. The rest of the paper is structured as follows: in Section 2 we give an overview of related work. In Section 3 we introduce the current edition of WOLF. In Section 4, we describe the process of extracting lexico-semantic information from bilingual lexical resources. In Section 5 we explain the wordnet enrichment experiment using a maximum entropy classifier that helped us determine whether a translation we extracted from the existing resources is an appropriate candidate for a given synset. Section 6 is dedicated to the analysis and evaluation of the extended resources, and Section 7 contains concluding remarks and ideas for future work.

Related work

Most automatic approaches to create a wordnet for a new language take the Princeton wordnet as a backbone and extend it with the vocabulary inventory of the target language. One of the most straightforward and most widely used resources to obtain lexical knowledge for the language in question are machine-readable bilingual diction-aries. Entries from the dictionary are linked to PWN synsets under the assumption that their counterparts in the target language correspond to the same synset [START_REF] Knight | Building a large-scale knowledge base for machine translation[END_REF]. A wellknown problem with this approach is that bilingual dictionaries are generally not concept-based but follow traditional lexicographic principles, which is why the biggest obstacle is the disambiguation of dictionary entries. When such dictionaries are not available or when they do not contain sufficient information to disambiguate the entries, bilingual lexicons can be extracted from parallel corpora [START_REF] Fung | A pattern matching method for finding noun and proper noun translations from noisy parallel corpora[END_REF]. The underlying assumption here is that senses of ambiguous words in one language are often translated into distinct words in another language [START_REF] Dyvik | Translations as semantic mirrors: from parallel corpus to wordnet[END_REF]. Furthermore, if two or more words are translated into the same word in another language, then they often share some element of meaning [START_REF] Ide | Sense Discrimination with Parallel Corpora[END_REF]. This results in sense distinctions of a polysemous source word or yields synonym sets. The third set of approaches that have become popular in the past few years extract the meaning, translations and relationships between words in one or several languages from Wikipedia. New wordnets have been induced by using structural information to assign Wikipedia categories to WordNet [START_REF] Simone | Large-scale taxonomy mapping for restructuring and integrating Wikipedia[END_REF] or by extracting keywords from Wikipedia articles (Reiter et al. 2008). Vector-space models to map Wikipedia pages to Wordnet have been developed [START_REF] Ruiz-Casado | Automatic Assignment of Wikipedia Encyclopedic Entries to WordNet Synsets[END_REF]. The most advanced approaches use Wikipedia and related projects, such as Wiktionary, to bootstrap wordnets for multiple languages [START_REF] De | Towards a universal wordnet by learning from combined evidence[END_REF]Weikum 2009, Navigli andPonzetto 2010). An unsupervised machine-learning approach has been used by [START_REF] Montazery | Unsupervised Learning for Persian WordNet Construction[END_REF] to construct a wordnet for Persian. Their approach is similar to ours in the sense that they too combine translation candidates obtained from bilingual dictionaries and corpus-based contextual information for these candidates to establish links to Princeton WordNet synsets.

Wordnet Libre du Français (WOLF)

Previous work on the development of WOLF [START_REF] Fišer | Combining multiple resources to build reliable wordnets[END_REF] has focused on benefitting from available resources of three different types: general and domain-specific bilingual dictionaries, parallel corpora and Wiki resources (Wikipedia and Wiktionaries).

The core WOLF was created by disambiguating (literal, synset) pairs obtained from a wordaligned multilingual parallel corpus with the help of already existing wordnets for several languages other than French. For each multilingual lexicon entry, translation equivalents in all these languages were assigned a set of possible synset ids from their wordnets. Assuming that translation equivalents in the word-aligned parallel corpus are lexicalizations of the same concept, they shared one or several intersecting synset ids which were then also assigned to the French equivalent in the lexicon. The approach was limited to almost predominantly basic synsets which were common among all the wordnets used, and to single-word literals because cross-lingual mapping of multi-word expressions was not possible with or word-alignment procedure. In order to compensate these shortcomings, additional (literal, synset) pairs for monosemous English words were also harvested from various freelyavailable bilingual resources (dictionaries, thesauri and Wikipedia). Sense assignment for these was near perfect because they did not require any disambiguation. The wordnet for French created in this way contained about 32,300 non-empty synsets, 87% of which were nominal. With the approach we adopted, we were able to populate just over 50% of Base Concept Sets and 25% of the rest of the concepts from Princeton WordNet. The first version of WOLF was already bigger than the French WordNet (22,121 synsets) that had been developed within the EuroWordNet Project (Vossen 1999) and was comparable to the more recent wordnet construction contribution called JAWS (34,367 synsets) which was developed by Mouton and de Chalendar (2010) from a bilingual dictionary, which however contains only nouns. Manual evaluation of the results showed that the wordnet generated in this way is relatively reliable but does not use full potential of the available resources. This is why we have devised an additional large-scale extension cycle, aiming at taking full advantage of the existing lexical resources in order to improve the coverage of WOLF without compromising its accuracy while the first version of WOLF will serve as the baseline. The procedure is described in the rest of this paper. We begin by presenting the various resources used in the experiment and the way we extracted (literal, synset) candidates from them. Then we introduce the maximum entropy classifier and the features we use for filtering these pairs and extending our initial wordnet. We also report manual and automatic evaluation of the results and look into possible steps to refine the developed resource in the future.

Bilingual lexicon extraction

In this experiment we used two types of sources of lexical knowledge: the structured freelyavailable general and domain specific bilingual dictionaries, and the semi-structured articles from the on-line Wikipedia. The main goal of the extraction process was to extract as many French translation variants for each English word as possible in order to capture as many senses of that word as possible. With this we obtained wordnet candidates in the form of (literal, synset) pairs, i.e. a French translation of an English word with an assigned synset id from Princeton WordNet. General vocabulary was extracted from the English and French Wiktionary in which translations are explicitly encoded for all parts-ofspeech. The number of pairs extracted from each resource is given in Table 1. For domain-specific vocabulary we used Wikispecies, a taxonomy of living species that includes both Latin standard names and vernacular terms. Less structured than dictionaries but with a much more predefined structure than free text is the online multilingual collaborative encyclopaedia Wikipedia. We used English and French articles by following inter-language links that relate two articles on the same topic. We enhanced the extraction process with a simple analysis of article bodies with which we resolved ambiguities arising from to the capitalization of article titles (e.g. Grass-novelist, Grass-plant). In a similar way we also identified synonyms for the article titles (e.g. "Cannabis, also known as marijuana"), their definitions (e.g. "Hockey is a family of sports in which two teams play against each other by trying to manoeuvre a ball or a puck into the opponent's goal using a hockey stick.") and usage examples. The result of our extraction process is a large bilingual lexicon of all English-French translation pairs with the name of the resource they originate from. The figures for both extracted bilingual lexicons are summarized in Table 1.

As can be seen in Table 1, we were able to extract a substantial amount of bilingual entries from the various resources. However, the extracted entries suffer from an important drawback: they do not contain any explicit information that can help us map these entries to PWN, neither do they contain contextual information from corpus occurrences that would help us determine their sense based on their usage. For example, an English-French translation pair (dog,chien), which we extracted from the Wiktionary, does not contain any information that would make it possible for us to determine which of the 8 synsets in WPN containing the literal dog would be appropriate to be translated with chien in WOLF. In Wiktionary articles, translations of a given word are sometimes organized into senses and described with short glosses. These have been compared to PWN glosses in order to map Wiktionary senses to PWN synsets (see [START_REF] Bernhard | Combining Lexical Semantic Resources with Question & Answer Archives for Translation-Based Answer Finding[END_REF]. The first sentence of a Wikipedia article can be used in a similar way (see [START_REF] Ruiz-Casado | Automatic Assignment of Wikipedia Encyclopedic Entries to WordNet Synsets[END_REF]. However, this is not the case for all Wiktionary entries or for other resources. Therefore, at this point, we assign to each translation pair all possible synset ids and disambiguate it in the next step.

Large-scale wordnet extension

Restricting the use of a bilingual lexicon to monosemous English literals is a safe but very limited approach that does not exploit the available resources to their full potential, which is a waste of resources and should be improved. However, using lexicon-based candidates generated from polysemous English literals is only possible if we can establish the likelihood with which a word should be added to a particular synset, i.e. can compute the semantic distance between a given French literal and PWN synset id.

In this paper we propose a technique to achieve exactly that. It is based on the core version of WOLF and a probabilistic classifier that uses various features associated with each (literal, synset) candidate.

Training set and feature selection

First we extract all (literal, synset) pairs from the bilingual lexicon that are already in the baseline wordnet and consider them as valid ones (score 1). All the other candidates, on the other hand, are considered invalid (score 0). This creates a noisy but reasonable training set for a probabilistic model. It is noisy for two reasons: first, our baseline wordnet does contain some mistakes because synsets were generated automatically and have not been completely manually validated; second, and more important reason is the fact that the baseline wordnet is not complete, which is why our new candidates may be valid even though they are not present in the baseline wordnets. It is precisely these candidates we are looking for in our wordnet extension procedure.

In order to use the baseline wordnet as a training set for our classifier that will assign scores to all the candidates in the lexicon, we need to extract features from (literal, synset) pairs in WOLF.

Semantic proximity

The central feature we use models the semantic proximity between a literal and a synset. The feature can be illustrated on the example (dog, chien) we already used above. There are 8 PWN synsets that contain the literal dog, which is why this bilingual entry yields 8 different (literal, synset) candidates. We now need to determine which of these 8 candidates are valid. In other words, we need to establish which of the 8 corresponding synsets the French literal chien should be added to in WOLF. We therefore compute the semantic similarity of the literal chien w.r.t. each of these 8 synsets. For doing this, we first represent each WOLF synset by a bag of words obtained by extracting all literals from this synset and all the synsets up to 2 nodes apart in WOLF. For example, the synset {andiron, firedog, dog, dog-iron} in PWN, which is empty in the baseline WOLF, is represented by the bag of words {appareil, mécanisme, barre, rayon, support, balustre,…} (~device, mechanism, bar, shelve, baluster,…). Next, we use a distributional semantic model for evaluating the semantic similarity of chien w.r.t. this bag of words. We use the freely-available SemanticVectors package [START_REF] Widdows | Semantic vectors: a scalable open source package and online technology management application[END_REF]. The distributional semantic model was built from the 65,000 lemmatised webpages from the French web corpus frWaC corpus [START_REF] Ferraresi | Web Corpora for Bilingual Lexicography: A Pilot Study of English/French Collocation Extraction and Translation[END_REF]. This gives us a semantic similarity score between chien and the synset {andiron, firedog, dog, dog-iron}, which is only 0.035, while the similarity between chien and one of its valid synsets, {dog, domestic dog, Canis familiaris} is as high as 0.331.

Additional features

In The idea is that if the candidate is generated from at least one monosemous PWN literal, it is very likely to be correct, whereas if it was generated from only highly polysemous PWN literals, it is much more questionable. Finally, the number of tokens in T is used as a feature (often, literals with many tokens are not translations of PWN literals but rather glosses).

Classifier training

Based on these features, we train a classifier using the Maximum-Entropy package megam (Hal [START_REF] Daumé | The Feasibility of Bootstrapping an Arabic WordNet leveraging Parallel Corpora and an English WordNet[END_REF]). An analysis of the models shows that the semantic similarity is by far the strongest feature. As expected, the lowest polysemy index among English literals also contributes positively, as does the number of different English literals yielding the generation of the candidate, and the number of sources involved.

On the other hand, also as expected, the number of tokens in the target language literal has a negative impact on the certainty score.

The result of our classifier on a given (literal,synset) candidate is a score between 0 (bad candidate) and 1 (good candidate). We empirically set the threshold at 0.1 (see Section 6.1) for adding the candidate to the wordnet. The results are presented and evaluated in the next section.

6 Results and evaluation

Analysis of the results

Our wordnet extension procedure yielded 55,159 French wordnet candidates (out of 177,980). As in PWN, by far the most frequent domain is Factotum, and the order for the following three most frequent domains is the same in both wordnets as well (Zoology, Botany, Biology). Most synsets belonging to these domains were generated from Wikispecies and Wikipedia while Wiktionary was the most frequent source for the Factotum domain. Of all the wordnet domains, only 3 are missing in WOLF (Paleontology, Rugby, and Volleyball) but these domains have less than 10 synsets in total even in PWN. Average synset length in the extended WOLF is 1.79 literals per synset, which is slightly more than in PWN 3.0 (1.76). It is the lowest for nominal synsets (1.72) and the highest for adverbial ones (2.06). In PWN adverbial synsets are by far the shortest (1.54) while verbal ones are the longest (1.82). The longest synset in the extended WOLF is an adverbial one which contains as many as 27 literals, while in PWN the longest synset is a nominal one with 28 literals. Table 3 contains a comparison between the level of polysemy when taking into account all literals vs. considering only polysemous ones. The comparison shows that while English literals are on average more polysemous than the French ones, there are big differences between English and French verbs, suggesting that automatically gen-erated French verbal synsets contain some noise which will have to be filtered out in the future. A comparison of unique literals in PWN and WOLF shows that we were able to automatically generate as much as 25% of all multi-word expressions and over 30% of proper names found in PWN, which is a very good result, considering that the only source of both of these groups of literals was Wikipedia.

Manual evaluation of the results

In this section we report the results of manual evaluation of the wordnet extension where we evaluate the accuracy of the (literal, synset) candidates we obtained with the classifier as well as the accuracy of the candidates we discarded. For the evaluation we randomly selected 400 hundred (literal, synset) and evaluated them manually, using only two tags: "OK" if it would be correct to add that literal to the synset, and "NO" if it would be wrong, regardless of what the reason was for the error and how semantically close it was to the synset. The accuracy of a set of candidates is as usual as the proportion of candidates receiving the "OK" tag. Moreover, in order to assess the quality of our scoring technique, we compared the accuracy of the candidates per quartile w.r.

Automatic evaluation of the results

In this section we report the results of automatic evaluation of the generated wordnet against the already existing wordnet for French that was developed within the EuroWordNet project. With this evaluation we will gain an insight into the precision and recall of the wordnet we created with the proposed extension procedure. However, such an evaluation is only partial, because the detected discrepancies between the two resources are not only errors in our automatically created wordnets but can also stem from a missing literal in the resource we use for comparison. Automatic evaluation was performed on non-empty synsets, which means that adjectival and adverbial synsets in WOLF could not be evaluated this way at all because other existing French wordnets do not cover them.

When considering non-empty synsets in FWN, any (literal, synset) pair that is common to both resources is considered correct. When the number of valid (literal, synset) pairs of all types are combined, we reach a total of ~65,690 valid pairs out of 76,436, reaching a ~86% accuracy. A direct comparison to other related resources developed by Navigli and Ponzetto (2010) and di Melo and Weikum ( 2010) is not straightforward because even though the resources we used overlap to a great extent, their aim was to create a multilingual network while we focused only on

French. An important difference between our approach and the one proposed by Navigli and Ponzetto (2010) is that they machine-translated the missing translations, while we only use resources that were created by humans, which is why we have more accurate translations. On the other hand, while di Melo and Weikum's (2010) wordnet for French has a slightly higher accuracy, it is smaller than ours. This shows that the approach we used to benefit as much as possible from available resources using basic NLP tools only is very efficient for building large-scale reliable wordnets.

Results and evaluation

In this paper we described an approach to extend an existing wordnet from heterogeneous re-sources. Using various features such as distributional similarity, we were able to reuse automatically extracted bilingual lexicons for translating and disambiguating polysemous literals, which had so far been dealt only with word-aligned corpora. The result of our work is a freely available lexical semantic resource that is large and accurate enough for use in real HLT applications. Compared to other similar resources for French, our wordnet is bigger than the much older French WuroWordNet and more comprehensive than the much more recent JAWS database. Due to the multiple human-produced resources which it was based on is more accurate than BabelNet (Navigli and Ponzetto, 2010) and larger than the French part of the multilingual wordnet developed by di Melo and Weikum (2010). Analysis and evaluation of the approach shows that it is both versatile and accurate enough to successfully extend a wordnet of limited coverage. Another major advantage of the approach is that it is fully modular, adaptable and language independent and can therefore be used for any language still lacking a substantial wordnet.

In the future we plans to adapt the distributional similarity measure in order to automatically detect literas that are outliers in synsets and should therefore be removed from the developed wordnet. This procedure will provide an even more accurate and useful source of the much needed lexcal knowledge that is much needed in virtually all HLT tasks.

Table 1 :

 1 Results of bilingual lexicon extraction from heterogeneous resources

	Resources used	En-Fr equivalents
	English Wiktionary	39,286
	French Wiktionary	59,659
	Wikispecies	48,046
	Wikipedia	286,818
	Total (duplicates removed)	417.419

Table 2 :

 2 Results of the wordnet extension procedure

	Among the 55,159 French candidates, 15,313
	(28%) correspond to (literal, synset) pairs al-
	ready present in the previous version of WOLF,
	which means that 39,823 (72%) new pairs were
	added. As a consequence, 13,899 synsets that
	were empty in the previous version of WOLF
	now have at least one French literal.
	A comparison of WOLF before and after the ex-
	tension paralleled with the figures from Prince-
	ton WordNet 3.0 is given in in Table 2. The ex-
	tended version of WOLF has 43% more non-
	empty synsets than before the extension. The
	increase in the number of (literal, synset) pairs in
	the new WOLF is even higher; the number rose
	from 46,411 to 76,436 (+65%).
		PWN 3.0 WOLF old WOLF new
	N	82,114	28,559	36,933
	V	13,767	1,554	4,105
	Adj	18,156	1,562	4,282
	Adv	3,621	871	1,125
	Total	117,658	32,550	46,449
	BCS1-3	4,671	4,339	6,171
	Non-BCS	112,987	28,211	40,278

Table 3 :

 3 Results of the wordnet extension procedure

		PWN 3.0	WOLF new
	avg. poly. + mono.	1.39	1.28
	N	1.23	1.19
	V	2.17	3.36
	avg. poly. -mono	2.91	2.11
	N	2.77	1.84
	V	3.57	5.0

Table 4 :

 4 Manual evaluation of (literal, synset) candidates generated for extending WOLF

	t. their certainty scores.
	The results of manual evaluation are shown in
	Table 4. They show a strong correlation between
	the certainty score they received and the accura-
	cy of the candidates, thus justifying our decision
	to use this threshold but other threshold values
	could have been used too: higher values would
	have provided candidates with an even higher
	accuracy but the scale of the wordnet extension
	would have been lower; on the other hand, lower
	threshold values would have extended our word-
	nets even more, but would have introduced much
	more noise.
	No. of candidates evaluated	400
	No. of candidates added to wordnet	27%
	Accuracy of all candidates	52%
	Acc. of the candidates added to WOLF	81%

Table 5 :

 5 Automatic evaluation of the extended WOLF based on FWN

		Correct (literal, synset) pairs	Correct WOLF	Incorrect WOLF	Correct FWN
		in WOLF and FWN	pairs not in FWN	pairs not in FWN	pairs not WOLF
	Nominal pairs not	8,474	11,627	15,474
	empty in FWN		~7,441	incorrect pairs:
		correct pairs: ~15,915	~4,186
	Verbal pairs not	1,826		3,859	6,168
	empty in FWN		~1,351	incorrect pairs:
		correct pairs: ~3,177	~2,508
	Empty pairs in	0	50,650	0
	FWN		~46,598	incorrect pairs:
		correct pairs: ~46,598	~4,052
	All pairs	10,300	66,136	21,642 + the no.
		~65,690	~55,390	incorrect pairs: ~10,746	of literals miss-ing in synsets not covered by
		overall precision: ~86 %		FWN

Acknowledgments

The work described in this paper has been funded in part by the French-Slovene PHC PRO-TEUS project "Building Slovene-French linguistic resources: parallel corpus and wordnet" (22718UC), by the French national grant EDyLex (ANR-09-CORD-008) and by the Slovene national postdoctoral grant (Z6-3668).


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

Darja Fišer
email: darja.fiser@ff.uni-lj.si

Extending wordnets by learning from multiple resources

Keywords: WordNet extension, WOLF, sloWNet, word sense disambiguation, distributional semantic models

In this paper we present an automatic, language-independent approach to extend an existing wordnet by recycling existing freely available bilingual resources, such as machine-readable dictionaries and on-line encyclopaedias. The approach is applied to Slovene and French. The words extracted from the bilingual resources are assigned one or several synset ids based on a classifier that relies on several features, including distributional similarity. Automatic and manual evaluation shows that the resulting extensions of sloWNet and WOLF are lexico-semantic repositories of high coverage as well as high quality.

Introduction

As the role of lexical knowledge is gaining importance in many areas of natural language processing, several frameworks for organizing and representing it have been proposed, such as ACQUILEX, MindNet, ConceptNet or Cyc. One of the best-known and most widely used lexico-semantic resources is Princeton WordNet [START_REF] Fellbaum | WordNet: An Electronic Database[END_REF] and its sister wordnets for languages other than English, such as EuroWordnet (Vossen, 1999) and BalkaNet [START_REF] Tufiş | BalkaNet -Design and Development of a Multilingual Balkan WordNet[END_REF]. Because manual construction of such resources is too time-consuming and expensive to be feasible for most research scenarios, semi-or fully automatic approaches have recently become popular, which exploit various types of existing resources to facilitate the development of a new wordnet. However, a common problem with automatically induced wordnets is the necessary trade-off between a limited coverage and the desired level of accuracy, both of which are required if the resource is to be useful in a practical application. We present here an approach for extending existing wordnets by extracting additional lexico-semantic information from already available bilingual language resources and then training a maximum entropy classifier on the existing core wordnet in order to assign the new vocabulary to the appropriate synsets. Our approach, applied on the French wordnet WOLF and the Slovene wordnet sloWNet, handles monosemous and polysemous words from all parts of speech. This paper is structured as follows: in Section 2 we give an overview of related work. In Section 3 we introduce WOLF and sloWNet. In Section 4, we describe the process of extracting lexico-semantic information from bilingual lexical resources. In Section 5 we explain the wordnet enrichment experiment using a maximum entropy classifier that helped us determine whether a translation we extracted from the existing resources is an appropriate candidate for a given synset. Section 6 is dedicated to the evaluation of the extended resources.

Related work

Most automatic approaches to create a wordnet for a new language take the Princeton wordnet as a backbone and extend it with the vocabulary inventory of the target language. Among the most straightforward resources to obtain lexical knowledge for the language in question are machine-readable bilingual dictionaries. Entries from the dictionary are linked to PWN synsets under the assumption that their counterparts in the target language correspond to the same synset [START_REF] Knight | Building a large-scale knowledge base for machine translation[END_REF]. Obviously, bilingual dictionaries are generally not concept-based but follow traditional lexicographic principles, which is why the biggest obstacle is the disambiguation of dictionary entries. This problem is overcome by a different set of approaches in which bi-or multilingual lexicons are extracted from parallel corpora [START_REF] Fung | A pattern matching method for finding noun and proper noun translations from noisy parallel corpora[END_REF]. The main underlying assumption in these approaches is that senses of ambiguous words in one language are often translated into distinct words in another language [START_REF] Dyvik | Translations as semantic mirrors: from parallel corpus to wordnet[END_REF][START_REF] Ide | Sense Discrimination with Parallel Corpora[END_REF]. Furthermore, if two or more words are translated into the same word in another language, then they often share some element of meaning. This results in sense distinctions of a polysemous source word or yields synonym sets. The third set of approaches that have become popular in the past few years draw upon Wikipedia. New wordnets have been induced by using structural information to assign Wikipedia categories to WordNet [START_REF] Ponzetto | Large-scale taxonomy mapping for restructuring and integrating Wikipedia[END_REF] or by extracting keywords from Wikipedia articles (Reiter et al., 2008). Vector-space models to map Wikipedia pages to Wordnet have been developed (e.g., by [START_REF] Ruiz-Casado | Automatic Assignment of Wikipedia Encyclopedic Entries to WordNet Synsets[END_REF]. The most advanced approaches use Wikipedia and related projects, such as Wiktionary, to bootstrap wordnets for multiple languages [START_REF] De Melo | Towards a universal wordnet by learning from combined evidence[END_REF][START_REF] Navigli | BabelNet: Building a Very Large Multilingual Semantic Network[END_REF].

WOLF and sloWNet

Previous work on the development of sloWNet and WOLF [START_REF] Erjavec | Building the Slovene Wordnet : first steps, first problems[END_REF]Fišer and Sagot, 2008) has focused on benefitting from available resources of three different types: general and domain-specific bilingual dictionaries, parallel corpora and Wiki resources (Wikipedia and Wiktionaries). More precisely, the development of the initial versions of WOLF and sloWNet was achieved in a three-step process. First, baseline versions of these wordnets were created (Fišer and Sagot, 2008) by using only (literal, synset) pairs obtained from a word-aligned multilingual parallel corpus, which could be disambiguated based on all languages but French and Slovene, as well as pairs extracted from lexical resources (dictionaries, lexica and Wikipedia) via monosemous English literals: such pairs required no disambiguation. The resulting wordnets were relatively reliable but did not use full potential of the available lexical resources. This is why we describe here a large-scale extension process, aiming at taking full advantage of these lexical resources for improving the coverage of both wordnets without lowering their accuracy. In the next section, we describe the lexical resources we used and how we extracted (literal, synset) candidates from them. In Section 5 we introduce the maximum entropy classifier we used for filtering these pairs and extending both wordnets, which are then evaluated in Section 6.

Extracting bilingual lexicons

In this section we describe the extraction of translation pairs from two types of resources: structured (general and domain-specific dictionaries and lexica), and semi-structured (Wikipedia articles). In the extraction process, our task is to extract as many translation variants for each word as possible in order to capture as many senses of that word as possible, in order to create wordnet candidates from the extracted translation pairs in the form of (literal, synset) pairs, i.e. translation of a source word with an assigned synset id from wordnet. We used English, French and Slovene Wiktionary and extracted translation pairs for all parts-of-speech from these three resources on the basis of translation sections within the articles. The number of pairs extracted from each resource is given in Table 1. In order to extract the general vocabulary that was available in Wiktionary for French but not for Slovene we used a traditional English-Slovene [START_REF] Grad | Slovene-English Dictionary, DZS Grad[END_REF] and a Slovene-English dictionary [START_REF] Grad | Slovene-English Dictionary, DZS Grad[END_REF]. For domain-specific vocabulary we used Wikispecies, a taxonomy of living species that includes both Latin standard names and vernacular terms. We also obtained translation pairs from the domain-specific thesaurus Eurovoc, an on-line dictionary of informatics islovar and a military glossary (Korošec et al., 2001) that will at least partially make up for the difference in the sizes of French and Slovene Wikispecies (cf. Table 1). The result of our extraction process is two large bilingual lexicons containing all English-French and English-Slovene translation pairs with the name of the resources they originate from. The figures for both extracted bilingual lexicons are summarized in Table 1. Less structured than dictionaries but still with a much more predefined structure than free text is the on-line multilingual collaborative encyclopaedia Wikipedia.

We used English, French and Slovene Wikipedia for extracting bilingual lexicons by following inter-language links that relate two articles on the same topic in the two corresponding wikipedias. We enhanced the extraction process with a simple analysis of article bodies with which we resolved ambiguities arising from to the capitalization of article titles (e.g. Grass-author, Grass-plant). With the analysis we also identified synonyms for the key terms (e.g. Cannabis, also known as marijuana), their definitions (e.g. Hockey is a family of sports in which two teams play against each other by trying to manoeuvre a ball or a puck into the opponent's goal using a hockey stick.) and usage examples. The number of translation pairs extracted is shown in Table 2. The bilingual entries we extracted from lexical resources are numerous. However, they suffer from an important drawback: they do not necessarily contain any additional information that can help to map them to PWN, neither do they contain contextual information from specific corpus occurrences. For example, an English-French entry we extracted from Wiktionary (dog, chien) does not contain any information that would make it possible for us to determine which of the 8 synsets containing dog as a literal in PWN would be appropriate to be translated with chien in WOLF. In Wiktionary articles, translations of a given word are sometimes organized by senses that are associated with short glosses. These have been compared to PWN glosses in order to map Wiktionary senses to PWN synsets [START_REF] Bernhard | Combining Lexical Semantic Resources with Question & Answer Archives for Translation-Based Answer Finding[END_REF]. The first sentence of a Wikipedia article can be used in a similar way [START_REF] Ruiz-Casado | Automatic Assignment of Wikipedia Encyclopedic Entries to WordNet Synsets[END_REF]. However, this is not the case for all Wiktionary entries or for other resources. Therefore, at this point, we assign to each translation pair all possible synset ids.

Automatic wordnet extension

Baseline wordnets

The first step in the development of sloWNet and WOLF was achieved in 2008, when the first versions were created (Fišer and Sagot, 2008). Then, all PWN literals were used for adding target language literals in the synsets found by the alignment-based approach, but only candidates generated from lexical resources via monosemous PWN literals were used.

After the restricted versions of wordnets were produced, they underwent some improvement steps that were performed independently, according to the specific needs of the two research teams. Quantitative information about the first two versions of WOLF are given in the second column in Table 3, which is compared to PWN 2.0, to the result of the work presented here (WOLF 0.2), as well as wordnets for

French that were developed by other researchers (French EuroWordNet (Vossen, 1999) and JAWS [START_REF] Mouton | JAWS: Just Another WordNet Subset[END_REF]). Parallel figures for sloWNet are shown as well.

Large-scale wordnet extension

Restricting the use of bilingual lexicon to monosemous English literals is a safe but limited approach that does not exploit the available resources to their full potential. However, using lexicon-based candidates generated from polysemous English literals is only possible if we can establish the likelihood with which a word should be added to a particular synset, i.e. can compute the semantic distance between a given French or Slovene literal and synset id. We designed such a technique based on already-existing French and Slovene wordnets, which we introduce in this Section.

Our technique relies on a probabilistic classifier that uses various features associated with each (literal, synset) candidate. The underlying idea is as follows: we start from baseline wordnets and a large set of lexicon-based candidates to be evaluated. We extract all (literal, synset) pairs that are already in the baseline wordnets and consider these candidates as valid ones (score 1) while all other candidates are considered invalid (score 0), thus creating a "copper standard", i.e., a reasonable although noisy training set for a probabilistic model. It is noisy for two reasons: first, our baseline wordnets do contain noise, as not all synsets were manually validated; second, and more importantly, many of our new candidates are valid even though they are not in the baseline wordnets. In fact, such candidates are exactly those we are looking for. In order to use the copper standard as training set for a classifier and then to assign scores to all candidates, we have to extract from them suitable features.

The most important feature that we use models the semantic proximity between a literal and a synset. Let us illustrate it on our running example (dog, chien). In PWN, 8 synsets contain the literal dog, which is why we generated 8 different (literal, synset) candidates from this bilingual entry. We now need to know which of them are valid, i.e., to which of the 8 corresponding synsets the French literal chien should be added in WOLF. We therefore compute the semantic similarity of the literal chien w.r. We use the freely available SemanticVectors package [START_REF] Widdows | Semantic vectors: a scalable open source package and online technology management application[END_REF]. The documents we used for building our distributional semantic models are 65,000 lemmatised webpages from the web-based frWaC corpus [START_REF] Ferraresi | Web Corpora for Bilingual Lexicography: A Pilot Study of English/French Collocation Extraction and Translation[END_REF] for French (390,000 distinct lemmas) and 334,000 lemmatised paragraphs from the reference FIDA-Plus corpus [START_REF] Arhar | Korpus FidaPLUS: nova generacija slovenskega referenčnega korpusa[END_REF] for Slovene (180,000 distinct lemmas). On our example, the semantic similarity between chien and the synset {andiron, firedog, dog, dog-iron} is only 0.035, while the similarity between chien and one of its valid synsets, {dog, domestic dog, Canis familiaris} is as high as 0.331. Based on these features, we trained one classifier per language using the Maximum-Entropy package megam (Hal [START_REF] Daumé | The Feasibility of Bootstrapping an Arabic WordNet leveraging Parallel Corpora and an English WordNet[END_REF]. A look at the resulting models (not shown here for space restrictions) shows that the semantic similarity we computed is relevant as it is the feature with the highest weight. As expected, the lowest polysemy index among English literals also contributes positively, as does the number of different English literals yielding the generation of the candidate, and the number of sources involved. On the other hand, also as expected, the number of tokens in the target language literal negatively contributes to the certainty score.

The result of our classifiers on a given (literal, synset) candidate is a score between 0 (bad candidate) and 1 (good candidate). We empirically set the threshold at 0.1 (see Section 6.1) for further addition in the corresponding wordnet. Quantitative information on the resulting wordnets (WOLF 0.2 and sloWNet 3.0) is provided in Table 3. In short, WOLF 0.2.0 has 43% more non-empty synsets than before the extension, and sloWNet 3.0 as much as 141% more. For (literal, synset) pairs, the increase is even higher: the extension of WOLF has increased the number of such pairs from 46,411 to 76,436 (+65%), and the extension of sloWNet has increased this number from 24,081 to 82,721 (+244%).

Evaluation

Before assessing the accuracy of the wordnets extended using the above-described approach, we begin with a manual evaluation of the extension step per se. We evaluate the accuracy of the candidates we obtained as well as the accuracy of the candidates we discarded. Next, we perform an automatic evaluation of the extended wordnets against a gold standard or a comparable resource developed by other authors.

Manual evaluation of wordnet extension

For measuring the accuracy of our extension approach (see Section 4.3), we randomly selected 400 (literal, synset) candidates for each language and evaluated them manually, using only two tags: "OK" if it would be correct to add that literal to the synset, and "NO" if it would be wrong, regardless of the cause of the error and how semantically close it was to the synset. The accuracy of a set of candidates is the proportion of candidates tagged "OK". Moreover, in order to assess the quality of our scoring technique, we compared the accuracy of the candidates per quartile w.r.t. their certainty scores. The results (see

Evaluation against other wordnets

In this section we report the results of automatic evaluation of the generated wordnets, which are compared to other wordnets that exist for the two target languages. However, such an evaluation is only partial, because the detected discrepancies between the two resources are not only errors in our automatically created wordnets but can also stem from a missing literal in the resource it is compared to. Automatic evaluation was performed on non-empty synsets, which means that adjectival and adverbial synsets in WOLF could not be evaluated this way at all because other existing French wordnets do not cover them.

The results of automatic evaluation of WOLF w.r.t. the FWN are not given here in full details due to space restrictions. However, let us consider first non-empty synsets in FWN. Any (literal, synset) pair that is common to both resources is considered correct. There also exist WOLF pairs that are not present in FWN although their synsets are not empty in FWN. Some of these are correct (i.e. even non-empty FWN synsets are incomplete), others not (i.e. these are errors in WOLF).

For an estimate of the precision of such pairs, we manually evaluated 100 randomly selected such nominal and 100 verbal pairs. This allowed us to estimate the number of correct vs. incorrect (literal, synset) pairs among those present in WOLF but not in FWN. And last but not least, many synsets are empty in FWN. We manually validated 100 randomly chosen pairs for such synsets and obtained an accuracy as high as 92%. In fact, empty synsets in FWN are rare or specific concepts whose literals are often monosemous and therefore easy to translate. Adding up the (exact or estimated) number of valid (literal, synset) pairs of all types, we reach a total of ~65,690 valid pairs out of 76,436, hence a ~86% accuracy.

The reference we used for evaluating sloWNet is a manually built gold standard (SWN) that was built by validating the results of the preliminary Slovene wordnet construction experiments based on the Serbian wordnet [START_REF] Fišer | Combining multiple resources to build reliable wordnets[END_REF]. The result is approximately the same: we get a ~85% accuracy.

Conclusion

We have described the different resources and techniques we used for extending WOLF and sloWNet, wordnets for French and Slovene that were built automatically. By using various features including distributional similarity, we were able to reuse automatically extracted bilingual lexicons for translating and disambiguating polysemous literals, which had been dealt only with word-aligned corpora for building the first versions of these wordnets. The result of our work is freely available lexical semantic resources that are large and accurate enough for being used in real NLP applications. The extended wordnets, which are much larger than the previous versions, were then carefully evaluated in terms of accuracy. The accuracy of (literal, synset) pairs is estimated at 86% for WOLF 0.2 and 85% for sloWNet 3.0. These figures show that both resources have a much higher coverage than the baseline wordnets and that they outperform the French EuroWordNet as well as JAWS, that currently only covers French nouns. A direct comparison with other related resources developed by [START_REF] Navigli | BabelNet: Building a Very Large Multilingual Semantic Network[END_REF] and di Melo and Weikum (2010) is not straightforward because even though the resources we used overlap to a great extent, their aim was to create a multilingual network while we focused only on the two target languages. Also, while [START_REF] Navigli | BabelNet: Building a Very Large Multilingual Semantic Network[END_REF] machine-translated the missing translations, we only use resources that were created by humans, which is why we expect to have more accurate translations but would have to carry out a detailed comparison to be certain. While di Melo and Weikum's (2010) wordnet for French has a slightly higher accuracy, it is smaller than ours. This shows that the approach we used, namely trying to benefit as much as possible from available resources using basic NLP tools only, is very efficient for building large-scale reliable wordnets.

Table 1 :

 1 Bilingual lexicon extracted from structured resources

	Input Resource	En-Fr unique	En-Sl unique
		pairs	pairs
	English wiktionary	39,286	6,052
	French / Slovene wiktionary	59,659	7,029
	Wikispecies	48,046	2,360
	Slovene-English dictionary	-	72,954
	English-Slovene dictionary	-	207,972
	Eurovoc + specialized voc.	-	31,702
	Total (duplicates removed)	130,601	282,789

Table 2 :

 2 Bilingual lexicon extracted from Wikipedia

Table 3 :

 3 Table 3 uses the three Base Concept Sets (BCS) for assessing the coverage of the most basic word senses. BCS were introduced in the BalkaNet project and cover the 8,516 most basic synsets in wordnet. Quantitative data about the different versions of WOLF and sloWNet, and comparison with the PWN 2.0, the French wordnet from the EuroWordNet project (FWN) and the JAWS nominal wordnet for French.

		PWN	WOLF	WOLF	WOLF	FWN	JAWS
		2.0	0.1.4	0.1.6	0.2
	All	115,424 32,351 32,550 46,449 22,121 34,367
	BCS1 1,218	869	870	1,067	1,211	760
	BCS2 3,471	1,665	1,668	2,519	3,022	1,729
	BCS3 3,827	1,796	1,801	2,585	2,304	1,706
	Non-	106,908 27,492 28,211 40,278 15,584 30,172
	BCS
	N	79,689	28,187 28,559 36,933 17,381 34,367
	V	13,508	1,546	1,554	4,105	4,740	0
	Adj	18,563	1,422	1,562	4,282	0	0
	Adv	3,664	667	871	1,125	0	0
		PWN 2.0	sloWNet	sloWNet	sloWNet
				2.0	2.2		3.0
	All	115,424	29,108	17,817	42,919
	BCS1	1,218	714	1,203		1,208
	BCS2	3,471	1,361	2,192		3,111
	BCS3	3,827	1,611	1,232		2,698
	Non-BCS 106,908	25,422	13,190	35,902
	N	79,689	22,927	16,234	30,911
	V	13,508	1,547	1,097		5,337
	Adj	18,563	4,376	429		6,218
	Adv	3,664	258	57		453

Table 4

 4

	) show a strong
	correlation between the certainty score and the accuracy
	of the candidates, leading us to set the threshold value
	at 0.1. Other threshold values could have been used:
	higher values would have provided candidates with
	even a higher accuracy but the scale of the wordnet
	extension would have been lower; on the other hand,

Table 4 :

 4 Manual evaluation of (literal, synset) candidates generated for extending WOLF and sloWNet.


Guido Nolte

Dominik Lutter

Andreas Ziehe

Francesco Nesta

Emmanuel Vincent

Zbynek Koldovsky

Alexis Benichoux

Shoko Araki

The 2011 Signal Separation Evaluation Campaign (SiSEC2011): -Biomedical data analysis

This paper summarizes the bio part of the 2011 community based Signal Separation Evaluation Campaign (SiSEC2011). Two different data sets were given. In the first task, participants were asked to estimate the causal relations of underlying sources from simulated bivariate EEG data. In the second task, participants were asked to reconstruct signaling pathways or parts of it from the microarray expression profiles. The results for each task were evaluated using different objective performance criteria. We provide an overview of the biomedical datasets, tasks and criteria, and we report on the achieved results.

Introduction

The Signal Separation Evaluation Campaign (SiSEC) is a regular campaign focused on the evaluation of methods for signal separation. While its main focus is on separation of audio data, after the campaign in 2010 [START_REF] Araki | The 2010 Signal Separation Evaluation Campaign (SiSEC2010): Biomedical Source Separation[END_REF] this is now the second time that tasks on biomedical data analysis are proposed. This article describes the bio part of SiSEC 2011.

The standard application of ICA-algorithms in biomedical data analysis are EEG and MEG data. In contrast to signal separation in audio datasets, the respective mixing model is static. The algorithms to solve such a problem are well established and are applied routinely by many researches. It is our opinion that conceptually only minor technical details could be added to present day knowledge. Additionally, a formulation of an ICA challenge for EEG/MEG data is problematic because of two reasons: a) in contrast to audio data, for real EEG/MEG data the ground truth is almost never known, and b), existing ICA algorithms exploit different statistical properties, and the winning method for simulated data will then be the one for which, essentially by coincidence, the simulated statistical properties match the exploited ones.

We therefore decided to deviate from the 'standard' problem and to propose two different tasks. In the first task, source separation shall be applied to analyze gene expressions, and in the second we simulate EEG data, but the task is not to separate sources but to separate the effect of confounding noise in an estimate of causal relations.

Details of the tasks can be found at http://sisec.wiki.irisa.fr/ and following the link to 'biomedical data analysis'.

Estimating causal relations

Task

Noninvasive electrophysiological measurements like EEG/MEG measure to large extent unknown superpositions of very many sources. Any relation observed between channels is dominated by meaningless mixtures of mainly independent sources. The question is how to observe and properly interpret true interactions in the presence of such strong confounders. Since recently, a focus of research are the causal relations between groups of neurons. Many methods have been suggested to address this question for EEG or MEG data [START_REF] Chen | Stochastic modeling of neurobiological time series: power, coherence, Granger causality, and separation of evoked responses from ongoing activity[END_REF][START_REF] Kaminski | Evaluating causal relations in neural systems: granger causality, directed transfer function and statistical assessment of significance[END_REF][START_REF] Baccala | Partial directed coherence: a new concept in neural structure determination[END_REF][START_REF] Schreiber | Measuring information transfer[END_REF][START_REF] Nolte | Robustly estimating the flow direction of information in complex physical systems[END_REF].

In this task contributors are requested to estimate the direction of interaction for simulated unidirectional bivariate dynamical systems. The difficulty is the presence of additive noise which is both non-white and spatially correlated.

The task is to estimate the direction of the interaction of the signal. A submitted result is a vector with 1000 numbers having the values 1, -1, or 0. Here, 1 means direction is from first to second sensor, -1 means direction is from second to first sensor, and 0 means 'I do not know'.

Dataset

The dataset consists of 1000 examples of bivariate data for 6000 time points. Each example is a superposition of a signal (of interest) and noise. The signal is constructed from a unidirectional bivariate AR-model of order 10 with (otherwise) random AR-parameters and uniformly distributed input. The noise is constructed of three independent sources, generated with 3 univariate ARmodels with random parameters and uniformly distributed input, which were instantaneously mixed into the two sensors with a random mixing matrix. The relative strength of noise and signal was set randomly. The Matlab code used to generate the data was provided. Note, that the phrase 'simulated EEG data' is meant loosely. The simulation addresses the conceptual problems of EEG data, but e.g. the actual spectra can be quite different from real EEG data.

The data z(t) were generated as

z(t) = (1 -γ) x(t) ||X|| + γ By(t) ||BY || (1)
where x is a unidirectional linear system and y are two independent noise sources which are mixed into channels by a random matrix B. The parameter γ was set randomly between 0 and 1, || • || denotes Frobenius matrix norm, and X and Y denote the full data as a matrix, e.g. X = (x(1), x(2), ..., x(N )) for N data points. The noise y(t) was generated with an AR(10)-model with diagonal but otherwise random parameters and uniformly distributed input, i.e.

y i (t) = 10 p=1 A i (p)(t -p) + η i (t) (2)
for i = 1, 2, 3. For each data set the parameters A ik were selected randomly according to a Gaussian distribution with a standard deviation 0.25. Nonstationary, i.e. diverging, systems were excluded. If the standard is substantially larger, almost all systems are nonstationary. If it is chosen substantially smaller, the spectra are nearly white. The 'innovation' η i (t) was uniformly distributed in the range [-. 5, .5]. This takes into account that some algorithms require non-Gaussian data or, especially, non-Gaussian innovations.

The signal x(t) was generated in the following way. If, e.g., the first channel was the sender, then x 1 (t) was generated with a random AR-model of order 10 in the same way as the noise term, and x 2 (t) was generated as

x 2 (t) = p A 22 (p)x 2 (t -p) + A 21 (p)x 1 (t -p) + 2 (t) (3)
where, again, 2 (t) was uniformly distributed in the range [-.5, .5]. The construction for the other direction is analogous.

Evaluation criterion

For all examples either 1 or -1 is correct. The most important point here is the way it is counted: you get +1 point for each correct answer; you get -10 points for each wrong answer; and you get 0 points for each 0 in the result vector. With this counting confidence about the result is added into the evaluation. It is strongly recommended that for each example the evidence for a specific finding is assessed. To our knowledge, this causality challenge is the first time that such an evaluation scheme is proposed.

Results

We received a total of 5 submissions. Results are shown in table1Another submission arrived after the deadline and after announcement of the results and was not counted. All participants were among the list of people who were contacted personally and were encouraged to submit. This kind of challenge is new within the SiSEC campaign and can therefore not be compared to previous challenges.

Submission Total Points Correct Detections False Detection S1

-2289 701 299 S2 [START_REF] Hu | Causality analysis of neural connectivity: critical examination of existing methods and advances of new methods[END_REF] 252 352 10 S3 [START_REF] Leistritz | Development of interaction measures based on adaptive non-linear time series analysis of biomedical signals[END_REF] -357 773 113 S4 [START_REF] Chavez | Statistical assessment of nonlinear causality: application to epileptic EEG signals[END_REF][START_REF] Palus | Synchronization as adjustment of infomation rates: Detection from bivariate time series[END_REF][START_REF] Prichard | Generalized redundancies for time series analysis[END_REF][START_REF] Theiler | Testing for Nonlinearity in Time Series: The Method of Surrogate Data[END_REF][START_REF] Vakorin | Confounding effects of indirect connections on causality estimation[END_REF] 218 278 6 S5 [START_REF] Vicente | Transfer entropy-a modelfree measure of effective connectivity for the neurosciences[END_REF][START_REF] Wibral | Transfer entropy in magnetoencephalographic data: Quantifying information flow in cortical and cerebellar networks", RID e-1566-2011[END_REF] -247 163 41

Table 1. Results of causality challenge. The total points can be calculated as the number of correct detections minus ten times the number of false detections.

3 Cancer pathway reconstruction

The task

Cellular signaling pathways are the key transducers from extracellular signals to cellular reaction. Dysfunction of signaling pathways is often involved in the formation of cancer [START_REF] Hoffman | Dynamic molecular processes mediate cellular mechanotransduction[END_REF]. Thus, understanding the biology of cell signaling helps to understand cancer and to develop new therapies. The regulation of these signaling pathways takes place on multiple layers, from extracellular receptors to intracellular transduction, ending with the transcriptional activation of target genes. Single genes can take part in more than one pathway and the expression profiles can be regarded as linear superpositions of different signaling pathways or more generally biological processes. All gene expression levels are represented by an M ×N data matrix X = [x i . . . x M ] with each row-vector x m representing the gene expression levels off all N genes measured in one experiment, or microarray. Assuming a linear mixture model, each vector x m represents a mixture of K unknown source signals s k , each representing a pathway related gene expression profile with the corresponding mixing coefficients represented as a column-vector a m . Thus, using blind source separation (BSS) techniques, the data-matrix X can be decomposed into X = AS, where A is the M × K mixing matrix and S the K × N matrix of source signals. These source signals can now be used as a basis to identify distinct signaling pathways in terms of cellular responses [START_REF] Lutter | Analyzing time-dependent microarray data using independent component analysis derived expression modes from human macrophages infected with F. tularensis holartica[END_REF].

A more detailed discussion of the linear factor model can be found in [START_REF] Lutter | Analyzing m-csf dependent monocyte/macrophage differentiation: expression modes and meta-modes derived from an independent component analysis[END_REF][START_REF] Teschendorff | Elucidating the altered transcriptional programs in breast cancer using independent component analysis[END_REF].

Here, the task is to reconstruct these signaling pathways or parts of it from the microarray expression profiles using BSS techniques. In a first approximation we consider a signaling pathways as gene lists. These pathway gene lists were taken from NETPATH (www.netpath.org).

Dataset

The microarray technology a method for mRNA profiling has become one of the most popular approaches in the field of gene expression analysis. Based on the complexity of gene expression profiles, a variety of statistical methods have been developed to provide insights into the biological mechanisms of gene expression regulation [START_REF] Quackenbush | Computational approaches to analysis of DNA microarray data[END_REF][START_REF] Schachtner | Knowledge-based gene expression classification via matrix factorization[END_REF][START_REF] Kowarsch | Knowledge-based matrix factorization temporally resolves the cellular responses to IL-6 stimulation[END_REF]. The dataset consists of the i gene expression profiles. Each expression profile x i mirrors the expression of N genes via measuring the level of the corresponding mRNA under a specific condition. In our case, mRNA was extracted from i = 189 invasive breast carcinomes [START_REF] Sotiriou | Gene expression profiling in breast cancer: understanding the molecular basis of histologic grade to improve prognosis[END_REF] and measured using Affymetrix U133A Gene-chips. The Affymetrix raw data was normalized using the RMA algorithm [START_REF] Irizarry | Summaries of Affymetrix GeneChip probe level data[END_REF] from the R Bioconductor package simpleaffy. Non-expressed genes were filtered out and Affymetrix probe sets were mapped to Gene Symbols. This resulted in a total of N = 11815 expressed genes.

Evaluation

Evaluation of the reconstructed pathways was performed by testing for the significance of enriched genes that can be mapped to the distinct pathways. For each source signal or estimated pathway we identify the number of genes that map to the distinct pathways and calculate p-values using Fisher's exact test.

To correct for multiple testing we use the Benjamini-Hochberg procedure to estimate false positive rates (FDR). Now, after Benjamini-Hochberg correction a reconstructed pathway was declared as enriched if the p-value was below 0.05. Finally, the number of all different significantly reconstructed pathways were counted.

Results

There were no submissions.

Conclusion

In this paper we presented the specifications of the biomedical data analysis part of SiSEC2011 and summarized the performance obtained over all the submissions. Two different tasks of very different nature we given. The 'Cancer pathway reconstruction' received no submission which could be due to the fact that the mathematical details were unclear to people not familiar with the biology.

For the EEG/MEG data analysis it might appear natural that ICA challenges were proposed. However, the ICA model for these data is not convolutive, which, from an algorithmic viewpoint, is a much simpler case than acoustic data. For instantaneous mixtures the algorithms have become standard. Probably everything which could be said , apart from minor details, was said already, and such a challenge does not attract researchers working on the technical aspects.

It was therefore decided to propose a different kind of challenge, in which causal direction in the presence of noise were to be estimated and in which evidence had to assessed for a successful submission. The large variation across final scores that it is largely unclear how to optimally solve this problem. Although the data were, strictly speaking, nonlinear (i.e. non-Gaussian), the nonlinearity was small, and people working on nonlinear methods were effectively left out. For the future we intend to expand the simulations such that both linear and nonlinear methods can reasonably be applied.

Acknowledgements. The authors gratefully acknowledge financial support by EU, BMBF and DFG. We would like to thank our co-authors for their permission to use material from joint publications.


Hélène Frankowska
email: frankowska@math.jussieu.fr

Marco Mazzola
email: m.mazzola7@campus.unimib.it

Optimal Synthesis and Normality of the Maximum Principle for Optimal Control Problems with Pure State Constraints

The objective of the present paper is investigation of the optimal synthesis and normality of the maximum principle for the Mayer optimal control problem under pure state constraints. Such models do arise in many applied areas such as space industry, robotics, drug administration, economy, etc. We express the optimal synthesis using Dini derivatives of an associated cost-to-go function and derive the normal maximum principle from a new Neighboring Feasible Trajectories theorem (NFT). For a state constraint with smooth boundary, NFT theorems imply that under standard assumptions on control system and an inward pointing condition, feasible trajectories depend in a Lipschitz way on the initial states. Some recent counterexamples indicate that, if the state constraint is an intersection of two half spaces in R n , surprisingly conclusions of NFT theorems might be no longer valid. We propose here a new inward pointing condition implying a new NFT theorem.

I. INTRODUCTION

Consider a complete separable metric space U , a mapping f : [0, 1]×R n ×U → R n and a closed non-empty subset K ⊂ R n . Open loop controls are Lebesgue measurable mappings u : [0, 1] → U . Let x 0 ∈ K. We associate to these data the control system

x ′ (t) = f (t, x(t), u(t)), u(t) ∈ U x(0) = x 0 , (I. [START_REF] Aubin | Set-valued Analysis[END_REF] under the state constraint

x(t) ∈ K for all t ∈ [0, 1]. (I.2)
An absolutely continuous function x : [0, 1] → R n that satisfies (I.1) and (I.2) is called a feasible trajectory. S K (x 0 ) denotes the set of all feasible trajectories. Consider a function g : R n → R and the Mayer optimal control problem minimize g(x(1)) | x(•) ∈ S K (x 0 ) .

(I.3)

For every (t 0 , y 0 ) ∈ [0, 1] × R n denote by S K [t0,1] (y 0 ) the set of all solutions x(•) to (I.1) defined on [t 0 , 1] with the initial time 0 replaced by t 0 , the initial state x 0 replaced by y 0 and such that x(t) ∈ K for all t ∈ [t 0 , 1].

The cost-to-go function V : [0, 1] × R n → R ∪ {+∞} associated to problem (I.3) is defined by: V (t, x) = +∞ if (t, x) / ∈ [0, 1] × K and for all t 0 ∈ [0, 1], y 0 ∈ K V (t 0 , y 0 ) = inf g(x(1)) | x(•) ∈ S K [t0,1] (y 0 ) , (I. [START_REF] Bettiol | Zero-sum state constrained differential games: existence of value for Bolza problem[END_REF] where we have set V (t 0 , y 0 ) = +∞ if S K [t0,1] (y 0 ) = ∅. We underline that V is, in general, discontinuous on the set [0, 1] × K even if f , g and boundary of K are smooth.

We recall next the maximum principle for the problem (I.3) (see for instance [START_REF] Vinter | Optimal Control[END_REF]). Consider an optimal trajectory/control pair (x, ū). Then, under some regularity assumptions, there exist λ ∈ {0, 1}, a positive (scalar) Radon measure µ on [0, 1] with (λ, µ) = 0 and a Borel measurable function ν(.)

: [0, 1] → R n satisfying ν(t) ∈ N K (x(t)) ∩ B µ -a.e., (I.5)
(where N K (x(t)) denotes the normal cone to K at x(t)) such that the absolutely continuous solution p : [0, 1] → R n to the system

-p ′ = ∂f ∂x (t, x(t), ū(t)) * p + [0,t] ν(s)dµ(s) (I.6) p(1) = -λ∇g(x(1)) - [0,1] ν(s)dµ(s) (I.7)
satisfies almost everywhere the maximum principle

p(t) + [0,t] ν(s)dµ(s), f (t, x(t), ū(t)) = max u∈U p(t) + [0,t] ν(s)dµ(s), f (t, x(t), u) (I.8) When λ = 1 the above maximum principle is called normal. If x 0 ∈ ∂K, then a trivial choice of multipliers is 0 = ζ ∈ N K (x(0)), ν = ζ, p ≡ -ζ, λ = 0 and µ = δ 0 ,
where δ 0 denotes the unit measure concentrated at {0}. In this case p(t)+ [0,t] ν(s)dµ(s) is equal to zero for all t ∈ [0, 1] and any feasible trajectory satisfies the maximum principle with such choice of multipliers.

Define ψ(t) := [0,t] ν(s)dµ(s) for all t ∈]0, 1] and ψ(0) = 0. In [START_REF] Cernea | A connection between the maximum principle and dynamic programming for constrained control problems[END_REF] under a geometric condition imposed on the boundary of K a maximum principle was proved with the following additional sensitivity relation

-p(0) ∈ λ∂ x V (0, x 0 ),
where ∂ x V (0, x 0 ) denotes a generalized gradient of V (0, •) at x 0 ∈ K and an additional non degeneracy condition λ + var(ψ, (0, 1]) = 0, where var(ψ, (0, 1]) is the total variation of ψ on (0, 1]. In particular, this eliminates the above trivial choice of multipliers for x 0 ∈ ∂K. It was also shown that λ = 1 (that is the maximum principle is normal) whenever the boundary ∂K of K is smooth and the classical inward pointing condition holds true : there exists ρ > 0 such that for all (t, x)

∈ [0, 1] × ∂K, ∃ u t,x ∈ U satisfying n(x), f (t, x, u t,x ) ≤ -ρ,
where n(x) denotes the unit outward normal to K at x. In the autonomous case such condition was used in [START_REF] Soner | Optimal control problems with state-space constraints[END_REF] to prove continuity of the cost-to-go function associated to an infinite horizon optimal control problem under state constraints with smooth boundary.

Normality of the maximum principle is important to study regularity of optimal trajectories (see for instance [START_REF] Galbraith | Lipschitz continuity of optimal controls for state constrained problems[END_REF] and [START_REF] Frankowska | Regularity of minimizers and of adjoint states for optimal control problems under state constraints[END_REF]) and is crucial for second order optimality conditions. The above normality result was extended in [START_REF] Frankowska | Regularity of minimizers and of adjoint states for optimal control problems under state constraints[END_REF] to K being an intersection of a finite family of closed sets with smooth boundary for Lipschitz optimal trajectories (see also [START_REF] Bettiol | Normality of the maximum principle for non convex constrained Bolza problems[END_REF] for more general sets K). For absolutely continuous optimal trajectories and constraints with smooth boundary a further extension can be found in [START_REF] Frankowska | Normality of the maximum principle for absolutely continuous solutions to Bolza problems under state constraints[END_REF], where a new inward pointing condition was introduced.

For f Lipschitz with respect to t, x and when ∂K is smooth, a normal maximum principle was derived in [START_REF] Rampazzo | A theorem on existence of neighbouring trajectories satisfying a state constraint, with applications to optimal control[END_REF] for strong local minimizers under the assumption of existence of a continuous feedback control u(t, x) ∈ U such that f (t, x, u(t, x)) is pointing inward.

For the Mayer problem we extend this result to a much more general case of W 1,1 local minimizers when ∂K may be nonsmooth, f continuous with respect to t and under a less restrictive inward pointing condition.

The second question we investigate here is the characterization of optimal trajectories as solutions to a differential inclusion involving feedback controls.

More precisely, for all t ∈ [0, 1),

x ∈ K such that V (t, x) = +∞ and all v ∈ R n define the lower directional derivative of V at (t, x) in the direction (1, v) ∈ R n+1 by D ↑ V (t, x)(1, v) := lim inf h→0+, v→v V (t + h, x + hv) -V (t, x) h
and consider the sets

U (t, x) = {u ∈ U | D ↑ V (t, x)(1, f (t, x, u)) ≤ 0} .
By the dynamic programming principle if x(•) ∈ S K (x 0 ) is optimal for the Mayer problem and u(•) is a corresponding optimal control, then

u(t) ∈ U (t, x(t)) a.e. in [0, 1]. Thus x(•) satisfies the differential inclusion x ′ (t) ∈ f (t, x(t), U (t, x(t))) a.e., x(0) = x 0 . (I.9)
The above necessary optimality condition becomes also sufficient whenever V is locally Lipschitz on [0, 1] × K. That is every solution x(•) to the differential inclusion (I.9) defined on [0, 1] is optimal and an optimal control satisfying ū(t) ∈ U (t, x(t)) a.e. in [0, 1] may be associated to it by using a measurable selection theorem.

If g is locally Lipschitz, then the local Lipschitz continuity of V can be proved whenever feasible trajectories depend on initial states in a locally Lipschitz way.

We provide here sufficient conditions for the following property: for every x 0 ∈ K there exist constants L > 0 and ε > 0 such that for any y 1 , y 2 ∈ B(x 0 , ε) ∩ K and any feasible trajectory ȳ1 (•) ∈ S K (y 1 ) we can find a feasible trajectory ȳ2 (•) ∈ S K (y 2 ) satisfying

||ȳ 1 (•) -ȳ2 (•)|| W 1,1 ≤ L |y 1 -y 2 |, (I.10)
where W 1,1 ([0, 1]; R n ) denotes the space of absolutely continuous functions from [0, 1] into R n with the usual norm

• W 1,1 .
In other words the set-valued map S K (•) :

K ❀ W 1,1 ([0, 1]; R n
) is locally Lipschitz. Such estimates are deduced from a new Neighboring Feasible Trajectories (NFT) theorem. This theorem provides sufficient conditions for the existence of a constant C > 0 such that for any solution x(•) : [0, 1] → R n to (I.1) that satisfies x(0) ∈ K but possibly "violates" the state constraint, there exists a feasible trajectory

x(•) ∈ S K (x(0)) such that ||x(•) -x(•)|| W 1,1 ≤ C max t∈[0,1] d K (x(t)), (I.11)
where d K (y) denotes the distance from a point y ∈ R n to K. NFT theorems have been extensively studied and have various applications in Optimal Control Theory and Differential Games under state constraints (see for instance [START_REF] Bettiol | On trajectories satisfying a state constraint: W 1,1 estimates and counter-examples[END_REF] - [START_REF] Bettiol | Regularity of solution maps of differential inclusions for systems under state constraints[END_REF], [START_REF] Bettiol | Sensitivity interpretations of the co-state variable for optimal control problems with state constraints[END_REF], [START_REF] Forcellini | On nonconvex differential inclusions whose state is constrained in the closure of an open set. Applications to dynamic programming[END_REF], [START_REF] Frankowska | Filippov's and Filippov-Wazewski's theorems on closed domains[END_REF], [START_REF] Frankowska | Existence of neighbouring feasible trajectories: applications to dynamic programming for state constrained optimal control problems[END_REF], [START_REF] Rampazzo | A theorem on existence of neighbouring trajectories satisfying a state constraint, with applications to optimal control[END_REF] - [START_REF] Soner | Optimal control problems with state-space constraints[END_REF] and the references therein). When f is locally Lipschitz with respect to t and x and K is an arbitrary closed set, then under an inward pointing condition involving interior of Clarke's tangent cones to K, an NFT theorem holds true with W 1,1 norm replaced by L ∞ norm, see [START_REF] Frankowska | Filippov's and Filippov-Wazewski's theorems on closed domains[END_REF]. However, an example from [START_REF] Bettiol | L ∞ estimates on trajectories confined to a closed subset[END_REF] shows that estimates provided by NFT theorems may not hold when f is merely continuous with respect to t and K is an intersection of two halfspaces in R 3 , even with W 1,1 norm replaced by L ∞ norm. We propose here a new inward pointing condition of a similar nature as the one in [START_REF] Frankowska | Normality of the maximum principle for absolutely continuous solutions to Bolza problems under state constraints[END_REF] that allows to get NFT results for K having a nonsmooth boundary and f continuous in t.

II. NFT THEOREM

By | • | we denote the Euclidean norm in R n and by •, • the inner product. Let B(x 0 , r) be the closed ball of radius r > 0 centered at x 0 ∈ R n and B the closed unit ball in R n centered at zero.

Consider a closed non-empty subset K of R n . We denote by Int K its interior and by ∂K its boundary. Henceforth,

d K (x) := inf y∈K |x-y| is the distance from a point x ∈ R n to K.
Let (X, d X ) be a metric space, Y be a Banach space and G : X ❀ Y be a set-valued map. The graph of G is defined by Graph (G) := {(x, y) | y ∈ G(x)}. G is called locally Lipschitz if for every x 0 ∈ X there exist ε > 0 and L ≥ 0 such that G has nonempty values on B(x 0 , ε) and

G(x 1 ) ⊂ G(x 2 ) + L d X (x 1 , x 2 ) B ∀ x 1 , x 2 ∈ B(x 0 , ε). WedA3.2
In other words G is L-Lipschitz on B(x 0 , ε) ⊂ X. The Clarke's tangent cone to K at x is defined by

C K (x) = v ∈ R n | lim h→0+, x ′ → K x d K (x ′ + hv) h = 0
and the normal cone to K at x by

N K (x) = {p ∈ R n | p, v ≤ 0 ∀ v ∈ C K (x)} .
For properties of tangent and normal cones see [START_REF] Aubin | Set-valued Analysis[END_REF]. Consider a set-valued map F : [0, 1] × R n ❀ R n with closed nonempty values and the differential inclusion

x ′ (t) ∈ F (t, x(t)) a.e. in [0, 1] x(0) = x 0 .
(II.1)

An absolutely continuous function x : [0, 1] → R n satisfying (II.1) is called an F -trajectory. It is called feasible (in K) if for all t ∈ [0, 1], x(t) ∈ K.
Recall that if f is continuous, then the set of trajectories of control system (I.1) coincides with the set of Ftrajectories of (II.1) for F (t, x) := f (t, x, U ).

We impose the following assumptions on

F                  F (•, x) is Lebesgue measurable for every x ∈ R n ; F is upper semicontinuous at every (t, x) ∈ [0, 1] × ∂K; ∃ γ ∈ L 1 ([0, 1] ; R + ) , sup v∈F (t,x) |v| ≤ γ (t) (1 + |x|) for a.e. t ∈ [0, 1] , ∀ x ∈ R n ; ∀R > 0, ∃λ R ∈ L 1 ([0, 1] ; R + ) , F (t, •) is λ R (t) -Lipschitz on RB for a.e. t ∈ [0, 1]
(II.2) and the following inward pointing condition on K, F

                   ∀ R > 0, ∃ M R > 0, ρ R > 0 such that ∀ t ∈ [0, 1] ∀ x ∈ ∂K ∩ RB, ∀ v ∈ F (t, x) \ Int C K (x) , ∃ w ∈ Liminf (s,y)→(t,x) F (s, y) ∩ B (v, M R ) satisfying (a) sup n∈N K (x)∩S n-1 n, w ≤ -ρ R (b) sup n∈N K (x)∩S n-1 n, w -v ≤ -ρ R .
(II.3) In the above Liminf denotes the Painlevé-Kuratowski lower set limit. That is for every (s, y) ∈ [0, 1] × R n there exists w s,y ∈ F (s, y) such that lim

(s,y)→(t,x)
w s,y = w = w t,x .

Remark:

1. If K is the closure of an open set Ω with smooth boundary ∂Ω having a positive reach and F is continuous, then (a) of assumption (II.3) is the classical inward pointing condition. Moreover, in this case, (b) is an immediate consequence of (a).

2. If F is lower semicontinuous at (t, x), then we always have F (t, x) ⊂ Liminf (s,y)→(t,x) F (s, y). In particular if f is continuous and F (s, y) = f (s, y, U ) for all (s, y), then F is lower semicontinuous.

3. Note that (a) and (b) of assumption (II.3) are independent. Indeed consider the constant set-valued map

R 2 ∋ x ❀ F (x) = G := co{(2, 1), (-2, 1), (0, 0)} and K = {(x 1 , x 2 ) ∈ R 2 | x 2 ≥ |x 1 |}
(see Figure 1 below). Then (a) is satisfied for every x ∈ ∂K, while (b) fails at (0, 0) ∈ R 2 . Indeed for v = (2, 1) / ∈ Int C K (0) there is no w ∈ G satisfying inequality (b).

If we replace the set G defined above by the set

G 1 = G ∪ {(2, 3), (-2, 3)}, then the set valued map R 2 ∋ x ❀ F 1 (x) := G 1
satisfies assumption (II.3) for the same set of constraints K.

Theorem 2.1: (NFT) Assume (II.2), (II.3) and that Int C K (x) = ∅ for all x ∈ ∂K. Then ∀ r 0 > 0, ∃ C > 0 such that ∀ σ ∈ [0, 1], for every F -trajectory x (•) on [σ, 1] with x (σ) ∈ K ∩ r 0 B and for any ε 0 > 0, there exists an

F - trajectory x (•) on [σ, 1] satisfying x (σ) = x (σ), x ((σ, 1]) ⊂ Int K and x -x W 1,1 ([σ,1];R n ) ≤ C max t∈[σ,1] d K (x (t)) + ε 0 .
In particular, if max t∈[σ,1] d K (x (t)) > 0, then an Ftrajectory x (•) as above may be chosen so that

x -x W 1,1 ([σ,1];R n ) ≤ 2C max t∈[σ,1] d K (x (t)) .
The proof of the above NFT theorem is very long and technical. It involves arguments of nonsmooth analysis and an explicit construction of a feasible F -trajectory x (•). It will be published elsewhere. The Filippov [START_REF] Filippov | Classical solutions of differential equations with multivalued right-hand side[END_REF] and the NFT theorems imply the following corollary.

Corollary 2.2: Under all the assumptions of Theorem 2.1 the set-valued map S K (•) :

K ❀ W 1,1 ([0, 1]; R n ) is locally Lipschitz continuous on K.
In [START_REF] Bettiol | On trajectories satisfying a state constraint: W 1,1 estimates and counter-examples[END_REF] the set K and the set-valued map F of Remark 3 above were used to provide a counter example to the Neighboring Feasible Trajectories theorem under the inward pointing condition (a). Thanks to the additional requirement (b) we could prove a new NFT theorem. In particular the set-valued map F 1 of Remark 3 satisfies (II.3).

WedA3.2

III. NORMAL MAXIMUM PRINCIPLE

For a locally Lipschitz φ : R n → R denote by ∂ C φ (x) Clarke's generalized gradient of φ at x ∈ R n .

Let g : R n → R be locally Lipschitz and consider the Mayer optimal control problem (I.3). The Pontryagin Hamiltonian is defined by

H(t, x, p, u) = p, f (t, x, u) . Hypothesis (H): i) U ⊂ R m is compact, g is locally Lipschitz, f is continuous; ii) For some c > 0, max u∈U |f (t, x, u)| ≤ c(1 + |x|), for all (t, x) ∈ [0, 1] × R n ; iii) ∀ R > 0, ∃ λ R > 0 such that ∀ t ∈ [0, 1] , ∀ u ∈ U f (t, •, u) is λ R -Lipschitz on RB. iv) ∀ R > 0, ∃ ρ R > 0, ∀ t ∈ [0, 1] , ∀ x ∈ ∂K ∩ RB, if u ∈ U is such that n, f (t, x, u) ≥ 0 for some n ∈ N K (x), then there exists v t,x,u ∈ U satisfying sup n∈N K (x)∩S n-1 n, f (t, x, v t,x,u ) ≤ -ρ R sup n∈N K (x)∩S n-1 n, f (t, x, v t,x,u ) -f (t, x, u) ≤ -ρ R . A feasible trajectory/control pair (x(•), ū(•)) is called a W 1,1
local minimizer for the problem (I.3) if for some ε > 0 and every feasible trajectory/control pair (x(•), u(•)) of (I.1) satisfying xx W 1,1 ≤ ε we have g(x(1))) ≤ g(x(1)).

Theorem 3.1: Assume (H) and that Int C K (x) = ∅ for all x ∈ ∂K. Let (x(•), ū(•)) be a W 1,1 local minimizer for the Mayer problem (I.3). Then for a positive Radon measure µ on [0, 1] and a Borel measurable ν : [0, 1] → R n as in (I.5), there exists an absolutely continuous solution p : Proof : We proceed in a way similar to [START_REF] Rampazzo | A theorem on existence of neighbouring trajectories satisfying a state constraint, with applications to optimal control[END_REF] using a Clarke penalization theorem. Let ε > 0 be such that for every feasible trajectory/control pair (x(•), u(•)) satisfying x-x W 1,1 ≤ ε we have g(x(1)) ≤ g(x(1)) and let k be a Lipschitz constant of g on B(x(1), ε). By [10, p.51] for any trajectory x(•) of control system (I.1) satisfying x -

[0, 1] → R n to -p ′ ∈ ∂ C x H t, x(t), p + [0,t]
x W 1,1 ≤ ε we have g(x(1)) ≤ g(x(1))+ k inf{ x -y W 1,1 | y ∈ S K (x 0 ), y -x W 1,1 ≤ ε}.
By Theorem 2.1 there exists C > 0 such that for any trajectory x(•) of control system (I.1),

inf{ x -y W 1,1 | y ∈ S K (x 0 )} ≤ C max t∈[0,1] d K (x (t)) .
Hence (x, 0, ū) is a W

C d K (x(t)) ⊂ N K (x(t)) ∩ B which completes the proof. ✷
Example. We would like to underline that the inward pointing condition iv) is sufficient, but not necessary for normality of a maximum principle.

Indeed consider f :

[0, 1] × R 2 × U → R 2 , where U = [-1, 1] × [-1, 1], f (t, x, (u 1 , u 2 )) = (u 1 , u 2 + u 1 -1), a control system x ′ = f (t, x, u(t)), u(t) ∈ U, the closed set of constraints K = (R -× R -) ∪ (R + × R)
and the Mayer problem minimizex 2 (1)

over solutions to the above control system satisfying the state constraints x(t) ∈ K and the initial condition

x 1 (0) = -1/2, x 2 (0) = 0.
Then the trajectory x given by

x(t) = (x 1 (t), x2 (t)) =    (t -1/2, 0) if t ≤ 1/2 (t -1/2, t -1/2) if t ≥ 1/2 is optimal. Note that f (t, x, U ) = G := {(g 1 , g 2 ) | g 1 ∈ [-1, 1], g 1 -2 ≤ g 2 ≤ g 1 }
(see Figure 2 below) and that for u = (1, 1), the second inequality in iv) is not satisfied at x = 0 for any v ∈ U . Nevertheless it was shown in [START_REF] Cernea | A connection between the maximum principle and dynamic programming for constrained control problems[END_REF] that a maximum principle corresponding to this (globally) optimal trajectory is normal. This observation is in line with results of [START_REF] Frankowska | Regularity of minimizers and of adjoint states for optimal control problems under state constraints[END_REF], where

VI. CONCLUSIONS

We obtained a new Neighboring Feasible Trajectories theorem that yields, in particular, the local Lipschitz continuity of the cost-to-go function of the Mayer problem under pure state constraints. We applied it to prove a nonsmooth normal maximum principle for W 1,1 local minimizers of the Mayer problem and to express the optimal synthesis using the Dini directional derivatives. These results substantially improve those existing in the literature. Finally we derived non-degenerate necessary conditions for optimality for a differential inclusion optimization problem under pure state constraints and a relation of the adjoint variable to the value function at the initial time.

ν

  (s)dµ(s), ū(t) (III.1) satisfying (I.8) a.e. in [0, 1] and such that -p(1) -[0,1] ν(s)dµ(s) ∈ ∂ C g(x(1)).

ν 1 t

 1 (s)dµ(s) ∈ λ∂ C g(x(1)). (III.2) Moreover (p(•), b, µ, λ) = 0 for some b ∈ R such that b, -b + [0,1] dµ(s) = (0, λ k C). (III.3) (Note that in [21, p.329] integrals are taken over intervals [0, t) instead of [0, t], however, the mapping ψ(t) := [0,t] ν(s)dµ(s) being of bounded total variation, it has at most countable number of jumps and therefore the adjoint equation and maximum principle are satisfied a.e. also with closed intervals [0, t]). By (III.3), b = 0. If λ = 0, then [0,1] dµ(s) = 0 implying that µ = 0 and, by (III.2), p(1) = 0. Consider any R > x ∞ . By the definition of H and (III.1) for all t ∈ [0, 1], |p(t)| ≤ λ R |p(s)|ds. This and the Gronwall inequality yield p = 0 which is in a contradiction with (p(•), b, µ, λ) = 0. Therefore λ = 0. By [10, p.51] ∂

WedA3. 2 iii)

 2 For some m ≥ 0, A (t, •) is m-Lipschitz on R n for a.e. t ∈ [0, 1]. Theorem 5.1: Assume that Int C K (x) = ∅ for all x ∈ ∂K, that g (•) is locally Lipschitz and that (II.2), (II.3) and (A) hold true. Let x (•) be an optimal solution to the Mayer problem (I.3). Then there exist λ ∈ {0, 1}, ψ ∈ N BV ([0, 1]) and an absolutely continuous function p :[0, 1] → R n satisfying p ′ (t) ∈ A * (t, -p (t)ψ (t)) for a.e. t ∈ [0, 1] , p (t) + ψ (t) , x ′ (t) = max v∈F (t,x(t)) p (t) + ψ (t) , v a.e. , -p (1)ψ (1) ∈ λ∂ C g (x (1)) and -p (0) ∈ λ∂ x V (0, x 0 ) .Furthermore, for a positive Radon measure µ on [0, 1] and a Borel measurable function ν : [0, 1] → R n satisfying (I.5) and for all t ∈ (0, 1],ψ (t) = [0,t] ν (s) dµ (s), ψ (0+) ∈ N K (x (0)) , ψ (t)ψ (t-) ∈ N K (x (t)) .Moreover the following non degeneracy conditions hold true λ + sup t∈(0,1) |p(t) + ψ(t)| = 0 and λ + var(ψ, (0, 1]) = 0. The above result follows from Theorem 4.1 and[START_REF] Cernea | A connection between the maximum principle and dynamic programming for constrained control problems[END_REF]. ✷

  By[21, pp. 157 and 329] for a positive Radon measure µ on [0, 1] and a Borel measurable selection ν(t) ∈ ∂ C d K (x(t)) there exists an absolutely continuous solution p : [0, 1] → R n to (III.1) satisfying (I.8) a.e. and

	-p(1) -
	[0,1]

1,1

local minimizer of the problem minimize g(x(1)) + k Cz

[START_REF] Aubin | Set-valued Analysis[END_REF]

over trajectory/control pairs (x, z, u) of control system (I.1) augmented by z ′ = 0, satisfying d K (x(t))z(t) ≤ 0.

This work was co-funded by the European Union under the 7th Framework Programme FP7-PEOPLE-2010-ITN. Grant agreement number 264735-SADCO. *Hélène Frankowska is with

normality was studied for global minimizers. However, our Theorem 3.1 applies also to W 1,1 local minimizers.

IV. OPTIMAL SYNTHESIS

The set of all feasible trajectories to (II.1) is denoted again by S K (x 0 ).

Given a map g : K → R and x 0 ∈ K consider the Mayer optimal problem (I.3). The associated value function 1)) over all Ftrajectories x (•) of (II.1) with the initial time t 0 (instead of 0) and the initial state at time t 0 equal to y 0 satisfying x([t 0 , 1]) ⊂ K. By the dynamic programming principle a feasible F -trajectory x (•) is optimal for the Mayer problem (I.3) if and only if the map t → V (t, x (t)) is constant and finite.

Using a standard method it is possible to deduce the following result from Corollary 2.2.

Theorem 4.1: Let K be such that Int C K (x) = ∅ for all x ∈ ∂K. Assume (II.2), (II.3) and that g (•) is locally Lipschitz. Then the value function

The local Lipschitz continuity of the value function allows to characterize optimal trajectories as solutions of a new differential inclusion.

Let D ↑ V (t, x)(1, v) be as defined in the introduction. An immediate necessary condition for the optimality of a feasible F -trajectory x (•) is

for all t ∈ [0, 1] such that x ′ (t) does exist. We show next that if the value function V is locally Lipschitz continuous on [0, 1] × K, then (IV.1) is also a sufficient condition for optimality.

For any

Proof : Suppose that x (•) solves the above inclusion. Then V (t, x (t)) = +∞ and x (t) ∈ K for all t ∈ [0, 1]. Define the function ψ : [0, 1] → R by ψ (t) = V (t, x (t)). From the definition of V (•, •), we know that ψ (•) is non decreasing. Moreover, by Theorem 4.1, ψ (•) is locally Lipschitz continuous. For all t ∈ [0, 1] such that ψ ′ (t) and x ′ (t) do exist and x ′ (t) ∈ G (t, x (t)), we have

Thus the map ψ (•) is nonincreasing and so it is constant. Consequently x(•) is optimal. ✷

V. ADJOINT VARIABLE AND THE VALUE FUNCTION

In this section we state a necessary condition for optimality that includes a relation between the adjoint variable p (•) of the Maximum Principle and an appropriate generalized gradient of the value function V (0, •).

Let φ : K → R be locally Lipschitz on a neighborhood of x in K. For every

A generalized gradient is defined using dφ (x) (•):

Observe that for x ∈ Int K we have ∂φ (x) = ∂ C φ (x).

Let Φ : R n ❀ R n be Lipschitz continuous around x and let y ∈ Φ (x). The adjacent derivative of Φ at (x, y) is the set-valued map dΦ (x, y) : R n ❀ R n defined by dΦ (x, y) u := Liminf h→0+ Φ (x + hu)y h .

Let A : R n ❀ R n be a set-valued map whose graph is a closed convex cone. Such map is called a closed convex process. Its adjoint process A * : R n ❀ R n is defined by

Below N BV ([0, 1]) states for the space of mappings ψ : [0, 1] → R n of bounded total variation on [0, 1], continuous from the right on (0, 1) and such that ψ (0) = 0. Denote by co F (t, x) the closed convex hull of F (t, x), by d x co F (t, x (t) , x ′ (t)) the adjacent derivative of co F (t, •) at (x (t) , x ′ (t)) and by ∂ x V (0, x 0 ) the generalized gradient of V (0, •) at x 0 introduced above.

Consider an optimal solution x (•) to the Mayer problem (I.3).

Assumption (A):

For a family of closed convex processes A (t, •) : R n ❀ R n , t ∈ [0, 1] we have i)

for a.e. t ∈ [0, 1];

WedA3.2