Joseph Le Roux
email: leroux@univ-paris13.fr

Benoît Favre
email: benoit.favre@lif.univ-mrs.fr

Alexis Nasr
email: alexis.nasr@lif.univ-mrs.fr

Seyed Abolghasem Mirroshandel
email: ghasem.mirroshandel@lif.univ-mrs.fr

Generative Constituent Parsing and Discriminative Dependency Reranking: Experiments on English and French

We present an architecture for parsing in two steps. A phrase-structure parser builds for each sentence an n-best list of analyses which are converted to dependency trees. These dependency structures are then rescored by a discriminative reranker. Our method is language agnostic and enables the incorporation of additional information which are useful for the choice of the best parse candidate. We test our approach on the the Penn Treebank and the French Treebank. Evaluation shows a significative improvement on different parse metrics.

Introduction

Two competing approaches exist for parsing natural language. The first one, called generative, is based on the theory of formal languages and rewriting systems. Parsing is defined here as a process that transforms a string into a tree or a tree forest. It is often grounded on phrase-based grammars -although there are generative dependency parsers -in particular context-free grammars or one of their numerous variants, that can be parsed in polynomial time. However, the independence hypothesis that underlies this kind of formal system does not allow for precise analyses of some linguistic phenomena, such as long distance and lexical dependencies.

In the second approach, known as discriminative, the grammar is viewed as a system of constraints over the correct syntactic structures, the words of the sentence themselves being seen as constraints over the position they occupy in the sentence. Parsing boils down to finding a solution that is compatible with the different constraints. The major problem of this approach lies in its complexity. The constraints can, theoretically, range over any aspect of the final structures, which prevents from using efficient dynamic programming techniques when searching for a global solution. In the worst case, final structures must be enumerated in order to be evaluated. Therefore, only a subset of constraints is used in implementations for complexity reasons. This approach can itself be divided into formalisms relying on logic to describe constraints, as the model-theoretic syntax [START_REF] Pullum | On the distinction between model-theoretic and generativeenumerative syntactic frameworks[END_REF], or numerical formalisms that associate weights to lexico-syntactic substructures. The latter has been the object of some recent work thanks to progresses achieved in the field of Machine Learning. A parse tree is represented as a vector of features and its accuracy is measured as the distance between this vector and the reference.

One way to take advantage of both approaches is to combine them sequentially, as initially proposed by [START_REF] Collins | Discriminative Reranking for Natural Language Parsing[END_REF]. A generative parser produces a set of candidates structures that constitute the input of a second, discriminative module, whose search space is limited to this set of candidates. Such an approach, parsing followed by reranking, is used in the Brown parser [START_REF] Charniak | Coarseto-Fine n-Best Parsing and MaxEnt Discriminative Reranking[END_REF]. The approach can be extended in order to feed the reranker with the output of different parsers, as shown by [START_REF] Johnson | Reranking the Berkeley and Brown Parsers[END_REF][START_REF] Zhang | K-best combination of syntactic parsers[END_REF].

In this paper we are interested in applying reranking to dependency structures. The main reason is that many linguistic constraints are straightforward to implement on dependency structures, as, for example, subcategorization frames or selectional constraints that are closely linked to the notion of de-pendents of a predicate. On the other hand, dependencies extracted from constituent parses are known to be more accurate than dependencies obtained from dependency parsers. Therefore the solution we choose is an indirect one: we use a phrase-based parser to generate n-best lists and convert them to lists of dependency structures that are reranked. This approach can be seen as trade-off between phrasebased reranking experiments [START_REF] Collins | Discriminative Reranking for Natural Language Parsing[END_REF] and the approach of [START_REF] Carreras | TAG, Dynamic Programming and the Perceptron for Efficient, Feature-rich Parsing[END_REF] where a discriminative model is used to score lexical features representing unlabelled dependencies in the Tree Adjoining Grammar formalism.

Our architecture, illustrated in Figure 1, is based on two steps. During the first step, a syntagmatic parser processes the input sentence and produces nbest parses as well as their probabilities. They are annotated with a functional tagger which tags syntagms with standard syntactic functions subject, object, indirect object . . . and converted to dependency structures by application of percolation rules. In the second step, we extract a set of features from the dependency parses and the associated probabilities. These features are used to reorder the n-best list and select a potentially more accurate parse. Syntagmatic parses are produced by the implementation of a PCFG-LA parser of [START_REF] Attia | Handling Unknown Words in Statistical Latent-Variable Parsing Models for Arabic, English and French[END_REF], similar to [START_REF] Petrov | Learning Accurate, Compact, and Interpretable Tree Annotation[END_REF], a functional tagger and dependency converter for the target language. The reranking model is a linear model trained with an implementation of the MIRA algorithm [START_REF] Crammer | Online Passive-Aggressive Algorithm[END_REF] 1 . [START_REF] Charniak | Coarseto-Fine n-Best Parsing and MaxEnt Discriminative Reranking[END_REF] and Collins (2000) rerank phrase-structure parses and they also include head-dependent information, in other words unlabelled dependencies. In our approach we take into account grammatical functions or labelled dependencies.

It should be noted that the features we use are very generic and do not depend on the linguistic knowledge of the authors. We applied our method to English, the de facto standard for testing parsing technologies, and French which exhibits many aspects of a morphologically rich language. But our approach could be applied to other languages, provided that The structure of the paper is the following: in Section 2 we describe the details of our generative parser and in Section 3 our reranking model together with the features templates. Section 4 reports the results of the experiments conducted on the Penn Treebank [START_REF] Marcus | The penn treebank: Annotating predicate argument structure[END_REF] as well as on the Paris 7 Treebank [START_REF] Abeillé | Treebanks, chapter Building a treebank for French[END_REF] and Section 5 concludes the paper.

Generative Model

The first part of our system, the syntactic analysis itself, generates surface dependency structures in a sequential fashion (Candito et al., 2010b;Candito et al., 2010a). A phrase structure parser based on Latent Variable PCFGs (PCFG-LAs) produces tree structures that are enriched with functions and then converted to labelled dependency structures, which will be processed by the parse reranker.

PCFG-LAs

Probabilistic Context Free Grammars with Latent Annotations, introduced in [START_REF] Matsuzaki | Probabilistic CFG with Latent Annotations[END_REF] can be seen as automatically specialised PCFGs learnt from treebanks. Each symbol of the grammar is enriched with annotation symbols behaving as subclasses of this symbol. More formally, the probability of an unannotated tree is the sum of the probabilities of its annotated counterparts. For a PCFG-LA G, R is the set of annotated rules, D(t) is the set of (annotated) derivations of an unannotated tree t, and R(d) is the set of rules used in a derivation d. Then the probability assigned by G to t is:

P G (t) = d∈D(t) P G (d) = d∈D(t) r∈R(d) P G (r) (1)
Because of this alternation of sums and products that cannot be optimally factorised, there is no exact polynomial dynamic programming algorithm for parsing. [START_REF] Matsuzaki | Probabilistic CFG with Latent Annotations[END_REF] and [START_REF] Petrov | Improved Inference for Unlexicalized Parsing[END_REF] discuss approximations of the decoding step based on a Bayesian variational approach. This enables cubic time decoding that can be further enhanced with coarse-to-fine methods [START_REF] Charniak | Coarseto-Fine n-Best Parsing and MaxEnt Discriminative Reranking[END_REF].

This type of grammars has already been tested on a variety of languages, in particular English and French, giving state-of-the-art results. Let us stress that this phrase-structure formalism is not lexicalised as opposed to grammars previously used in reranking experiments [START_REF] Collins | Discriminative Reranking for Natural Language Parsing[END_REF][START_REF] Charniak | Coarseto-Fine n-Best Parsing and MaxEnt Discriminative Reranking[END_REF]. The notion of lexical head is therefore absent at parsing time and will become available only at the reranking step.

Dependency Structures

A syntactic theory can either be expressed with phrase structures or dependencies, as advocated for in [START_REF] Rambow | The Simple Truth about Dependency and Phrase Structure Representations: An Opinion Piece[END_REF]. However, some information may be simpler to describe in one of the representations. This equivalence between the modes of representations only stands if the informational contents are the same. Unfortunately, this is not the case here because the phrase structures that we use do not contain functional annotations and lexical heads, whereas labelled dependencies do. This implies that, in order to be converted into labelled dependency structures, phrase structure parses must first be annotated with functions. Previous experiments for English and French as well (Candito et al., 2010b) showed that a sequential approach is better than an integrated one for contextfree grammars, because the strong independence hypothesis of this formalism implies a restricted domain of locality which cannot express the context needed to properly assign functions. Most functional taggers, such as the ones used in the following experiments, rely on classifiers whose feature sets can describe the whole context of a node in order to make a decision.

Discriminative model

Our discriminative model is a linear model trained with the Margin-Infused Relaxed Algorithm (MIRA) [START_REF] Crammer | Online Passive-Aggressive Algorithm[END_REF]. This model computes the score of a parse tree as the inner product of a feature vector and a weight vector representing model parameters. The training procedure of MIRA is very close to that of a perceptron [START_REF] Rosenblatt | The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain[END_REF], benefiting from its speed and relatively low requirements while achieving better accuracy.

Recall that parsing under this model consists in (1) generating a n-best list of constituency parses using the generative model, (2) annotating each of them with function tags, (3) converting them to dependency parses, (4) extracting features, (5) scoring each feature vector against the model, ( 6) selecting the highest scoring parse as output.

For training, we collect the output of feature extraction (4) for a large set of training sentences and associate each parse tree with a loss function that denotes the number of erroneous dependencies compared to the reference parse tree. Then, model weights are adjusted using MIRA training so that the parse with the lowest loss gets the highest score. Examples are processed in sequence, and for each of them, we compute the score of each parse according to the current model and find an updated weight vector that assigns the first rank to the best parse (called oracle). Details of the algorithm are given in the following sections.

Definitions

Let us consider a vector space of dimension m where each component corresponds to a feature: a parse tree p is represented as a sparse vector φ(p). The model is a weight vector w in the same space where each weight corresponds to the importance of the features for characterizing good (or bad) parse trees. The score s(p) of a parse tree p is the scalar product of its feature vector φ(p) and the weight vector w.

s(p) = m i=1 w i φ i (p) (2)
Let L be the n-best list of parses produced by the generative parser for a given sentence. The highest scoring parse p is selected as output of the reranker:

p = argmax p∈L s(p) (3)
MIRA learning consists in using training sentences and their reference parses to determine the weight vector w. It starts with w = 0 and modifies it incrementally so that parses closest to the reference get higher scores. Let l(p), loss of parse p, be the number of erroneous dependencies (governor, dependent, label) compared to the reference parse. We define o, the oracle parse, as the parse with the lowest loss in L.

Training examples are processed in sequence as an instance of online learning. For each sentence, we compute the score of each parse in the n-best list. If the highest scoring parse differs from the oracle (p = o), the weight vector can be improved. In this case, we seek a modification of w ensuring that o gets a better score than p with a difference at least proportional to the difference between their loss. This way, very bad parses get pushed deeper than average parses. Finding such weight vector can be formulated as the following constrained optimization problem:

minimize: ||w|| 2 (4) subject to: s(o) -s(p) ≥ l(o) -l(p) (5)
Since there is an infinity of weight vectors that satisfy constraint 5, we settle on the one with the smallest magnitude. Classical constrained quadratic optimization methods can be applied to solve this problem: first, Lagrange multipliers are used to introduce the constraint in the objective function, then the Hildreth algorithm yields the following analytic solution to the non-constrained problem:

w = w + α (φ(o) -φ(p)) (6) α = max 0, l(o) -l(p) -[s(o) -s(p)] ||φ(o) -φ(p)|| 2 (7)
Here, w is the new weight vector, α is an update magnitude and [φ(o) -φ(p)] is the difference between the feature vector of the oracle and that of the highest scoring parse. This update, similar to the perceptron update, draws the weight vector towards o while pushing it away from p. Usual tricks that apply to the perceptron also apply here: (a) performing multiple passes on the training data, and (b) averaging the weight vector over each update2 . Algorithm 1 details the instructions for MIRA training.

Features

The quality of the reranker depends on the learning algorithm as much as on the feature set. These features can span over any subset of a parse tree, up to the whole tree. Therefore, there are a very large set of possible features to choose from. Relevant features must be general enough to appear in as many parses as possible, but specific enough to characterize good and bad configurations in the parse tree.

We extended the feature set from [START_REF] Mcdonald | Discriminative Training and Spanning Tree Algorithms for Dependency Parsing[END_REF] which showed to be effective for a range of languages. Our feature templates can be categorized in 5 classes according to their domain of locality. In the following, we describe and exemplify these templates on the following sentence from the Penn treebank, in which we target the PMOD dependency between "at" and "watch."

Probability Three features are derived from the PCFG-LA parser, namely the posterior probability of the parse (eq. 1), its normalized probability relative to the 1-best, and its rank in the n-best list.

Unigram Unigram features are the most simple as they only involve one word. Given a dependency between position i and position j of type l, governed by x i , denoted x i l → x j , two features are created: one for the governor x i and one for the dependent x j . They are described as 6-tuples (word, lemma, pos-tag, is-governor, direction, type of dependency). Variants with wildcards at each subset of tuple slots are also generated in order to handle sparsity.

In our example, the dependency between "looked" and "at" generates two features:

[at, at, IN, G, R, PMOD] and [looked, look, NN, D, L, PMOD]
And also wildcard features such as:

[-, at, IN, G, R, PMOD], [at, -, IN, G, R, PMOD] ... [at, -, -, -, -, PMOD]
This wildcard feature generation is applied to all types of features. We will omit it in the remainder of the description.

Bigram Unlike the previous template, bigram features model the conjunction of the governor and the dependent of a dependency relation, like bilexical dependencies in [START_REF] Collins | Three Generative, Lexicalised Models for Statistical Parsing[END_REF].

Given dependency x i l → x j , the feature created is (word x i , lemma x i , pos-tag x i , word x j , lemma x j , pos-tag x j , distance3 from i to j, direction, type).

The previous example generates the following feature:

[at, at, IN, watch, watch, NN, 2, R, PMOD]

Where 2 is the distance between "at" and "watch".

Linear context This feature models the linear context between the governor and the dependent of a relation by looking at the words between them. Given dependency x i l → x j , for each word from i + 1 to j -1, a feature is created with the pos-tags of x i and x j , and the pos tag of the word between them (no feature is create if j = i + 1). An additional feature is created with pos-tags at positions i -1, i, i + 1, j -1, j, j + 1. Our example yields the following features:

[IN, PRP$, NN],
and

[VBD, IN, PRP$, PRP$, NN, .].
Syntactic context: siblings This template and the next one look at two dependencies in two configurations. Given two dependencies x i l → x j and x i m → x k , we create the feature (word, lemma, pos-tag for x i , x j and x k , distance from i to j, distance from i to k, direction and type of each of the two dependencies). In our example: → x k , we create the feature (word, lemma, pos-tag of x i , x j and x k , distance from i to j, distance from i to k, direction and type of each of the two dependencies). In our example:

[looked, look, VBD, at, at, IN, watch, watch, NN, 1, 2, R, ADV,

R, PMOD]

It is worth noting that our feature templates only rely on information available in the training set, and do not use any external linguistic knowledge.

Experiments

In this section, we evaluate our architecture on two corpora, namely the Penn Treebank [START_REF] Marcus | The penn treebank: Annotating predicate argument structure[END_REF] and the French Treebank [START_REF] Abeillé | Treebanks, chapter Building a treebank for French[END_REF]. We first present the corpora and the tools used for annotating and converting structures, then the performances of the phrase structure parser alone and with the discriminative reranker.

Treebanks and Tools

For English, we use the Wall Street Journal sections of the Penn Treebank. We learn the PCFG-LA from sections 02-21 4 . We then use FUNTAG [START_REF] Chrupała | Better training for function labeling[END_REF] to add functions back to the PCFG-LA analyses. For the conversion to dependency structures we use the LTH tool [START_REF] Johansson | Extended constituent-to-dependency conversion for English[END_REF]. In order to get the gold dependencies, we run LTH directly on the gold parse trees. We use section 22 for development and section 23 for the final evaluation.

For French, we use the Paris 7 Treebank (or French Treebank, FTB). As in several previous experiments we decided to divide the 12,350 phrase structure trees in three sets: train (80%), development (10%) and test (10%). The syntactic tag set for French is not fixed and we decided to use the one described in [START_REF] Candito | Improving Generative Statistical Parsing with Semi-Supervised Word Clustering[END_REF] to be able to compare this system with recent parsing results on French. As for English, we learn the PCFG-LA without functional annotations which are added afterwards. We use the dependency structures developed in (Candito et al., 2010b) and the conversion toolkit BONSAÏ. Furthermore, to test our approach against state of the art parsing results for French we use word clusters in the phrase-based parser as in [START_REF] Candito | Improving Generative Statistical Parsing with Semi-Supervised Word Clustering[END_REF].

For both languages we constructed 10-fold training data from train sets in order to avoid overfitting the training data. The trees from training sets were divided into 10 subsets and the parses for each subset were generated by a parser trained on the other 4 Functions are omitted. 9 subsets. Development and test parses are given by a parser using the whole training set. Development sets were used to choose the best reranking model.

For lemmatisation, we use the MATE lemmatiser for English and a home-made lemmatiser for French based on the lefff lexicon [START_REF] Sagot | The lefff, a freely available and large-coverage lexicon for french[END_REF].

Generative Model

The performances of our parser are summarised in Figure 2, (a) and (b), where F-score denotes the Parseval F-score5 , and LAS and UAS are respectively the Labelled and Unlabelled Attachment Score of the converted dependency structures6 . We give oracle scores (the score that our system would get if it selected the best parse from the n-best lists) when the parser generates n-best lists of depth 10, 20, 50 and 100 in order to get an idea of the effectiveness of the reranking process.

One of the issues we face with this approach is the use of an imperfect functional annotator. For French we evaluate the loss of accuracy on the resulting dependency structure from the gold development set where functions have been omitted. The UAS is 100% but the LAS is 96.04%. For English the LAS from section 22 where functions are omitted is 95.35%.

From the results presented in this section we can make two observations. First, the results of our parser are at the state of the art on English (90.7% F-score) and on French (85.7% F-score). So the reranker will be confronted with the difficult task of improving on these scores. Second, the progression margin is sensible with a potential LAS error reduction of 41% for English and 40.2% for French.

Adding the Reranker

Learning Feature Weights

The discriminative model, i.e. template instances and their weights, is learnt on the training set parses obtained via 10-fold cross-validation. The generative parser generates 100-best lists that are used as learning example for the MIRA algorithm. Feature extraction produces an enormous number of features: about 571 millions for English and 179 mil- lions for French. Let us remark that this large set of features is not an issue because our discriminative learning algorithm is online, that is to say it considers only one example at a time, and it only gives non-null weights to useful features.

Evaluation

In order to test our system we first tried to evaluate the impact of the length of the n-best list over the reranking predictions 7 . The results are shown in Figure 2, parts (c) and (d).

For French, we can see that even though the LAS and UAS are consistently improving with the number of candidates, the F-score is maximal with 50 candidates. However the difference between 50 candidates and 100 candidates is not statistically significant. For English, the situation is simpler and scores improve continuously on the three metrics.

Finally we run our system on the test sets for both treebanks. Results are shown 8 in Table 1 for English, and Table 2 for French. For English the improvement is 0.9% LAS, 0.7% Parseval F-score and 7 The model is always trained with 100 candidates. 8 F < 40 is the parseval F-score for sentences with less than 40 words. For French we have improvements of 0.3/0.7/0.9. If we add a template feature indicating the agreement between part-of-speech provided by the PCFG-LA parser and a part-of-speech tagger [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for stateof-the-art pos tagging with less human effort[END_REF], we obtain better improvements: 0.5/0.8/1.1.

Comparison with Related Work

We compare our results with related parsing results on English and French.

For English, the main results are shown in Table 3. From the presented data, we can see that indirect reranking on LAS may not seem as good as direct reranking on phrase-structures compared to F-scores obtained in [START_REF] Charniak | Coarseto-Fine n-Best Parsing and MaxEnt Discriminative Reranking[END_REF] and [START_REF] Huang | Forest Reranking: Discriminative Parsing with Non-Local Features[END_REF] with one parser or [START_REF] Zhang | K-best combination of syntactic parsers[END_REF] with several parsers. However, our system does not rely on any language specific feature and can be applied to other languages/treebanks. It is difficult to compare our system for LAS because most systems evaluate on gold data (part-of-speech, lemmas and morphological information) like [START_REF] Bohnet | Top Accuracy and Fast Dependency Parsing is not a Contradiction[END_REF].

Our system also compares favourably with the system of [START_REF] Carreras | TAG, Dynamic Programming and the Perceptron for Efficient, Feature-rich Parsing[END_REF] that relies on a more complex generative model, namely Tree Adjoining Grammars, and the system of [START_REF] Suzuki | An empirical study of semi-supervised structured conditional models for dependency parsing[END_REF] that makes use of external data (unannotated text). For French, see Table 4, we compare our system with the MATE parser [START_REF] Bohnet | Top Accuracy and Fast Dependency Parsing is not a Contradiction[END_REF], an improvement over the MST parser [START_REF] Mcdonald | Online Large-Margin Training of Dependency Parsers[END_REF] with hash kernels, using the MELT part-of-speech tagger [START_REF] Denis | Coupling an annotated corpus and a morphosyntactic lexicon for stateof-the-art pos tagging with less human effort[END_REF] and our own lemmatiser.

F LAS UAS

We also compare the French system with results drawn from the benchmark performed by Candito et al. (2010a). The first system (BKY-FR) is close to ours without the reranking module, using the Berkeley parser adapted to French. The second (MST-FR) is based on MSTParser [START_REF] Mcdonald | Online Large-Margin Training of Dependency Parsers[END_REF]. These two system use word clusters as well.

The next section takes a close look at the models of the reranker and its impact on performance.

Model Analysis

It is interesting to note that in the test sets, the one-best of the syntagmatic parser is selected 52.0% of the time by the reranker for English and 34.3% of the time for French. This can be explained by the difference in the quantity of training data in the two treebanks (four times more parses are available for English) resulting in an improvement of the quality of the probabilistic grammar.

We also looked at the reranking models, specifically at the weight given to each of the features. It shows that 19.8% of the 571 million features have a non-zero weight for English as well as 25.7% of the 179 million features for French. This can be explained by the fact that for a given sentence, features that are common to all the candidates in the n-best list are not discriminative to select one of these candidates (they add the same constant weight to the score of all candidates), and therefore ignored by the model. It also shows the importance of feature engineering: designing relevant features is an art [START_REF] Charniak | Coarseto-Fine n-Best Parsing and MaxEnt Discriminative Reranking[END_REF].

We took a closer look at the 1,000 features of highest weight and the 1,000 features of lowest weight (negative) for both languages that represent the most important features for discriminating between correct and incorrect parses. For English, 62.0% of the positive features are backoff features which involve at least one wildcard while they are 85.9% for French. Interestingly, similar results hold for negative features. The difference between the two languages is hard to interpret and might be due in part to lexical properties and to the fact that these features may play a balancing role against towards non-backoff features that promote overfitting.

Expectedly, posterior probability features have the highest weight and the n-best rank feature has the highest negative weight. As evidenced by In terms of LAS performance, on the PTB test set the reranked output is better than the baseline on 22.4% of the sentences while the opposite is true for 10.4% of the sentences. In 67.0% of the sentences, they have the same LAS (but not necessarily the same errors). This emphasises the difficulty of reranking an already good system and also explains why oracle performance is not reached. Both the baseline and reranker output are completely correct on 21.3% of the sentences, while PCFG-LA correctly parses 23% of the sentences and the MIRA brings that number to 26%.

Figures 3 and4 show hand-picked sentences for which the reranker selected the correct parse. The French sentence is a typical difficult example for PCFGs because it involves a complex rewriting rule which might not be well covered in the training data (SENT → NP VP PP PONCT PP PONCT PP PONCT). The English example is tied to a wrong attachment of the prepositional phrase to the verb instead of the date, which lexicalized features of the reranker handle easily.

Conclusion

We showed that using a discriminative reranker, on top of a phrase structure parser, based on converted dependency structures could lead to significant improvements over dependency and phrase structure parse results. We experimented on two treebanks for two languages, English and French and we mea-sured the improvement of parse quality on three different metrics: Parseval F-score, LAS and UAS, with the biggest error reduction on the latter. However the gain is not as high as expected by looking at oracle scores, and we can suggest several possible improvements on this method.

First, the sequential approach is vulnerable to cascading errors. Whereas the generative parser produces several candidates, this is not the case of the functional annotators: these errors are not amendable. It should be possible to have a functional tagger with ambiguous output upon which the reranker could discriminate. It remains an open question as how to integrate ambiguous output from the parser and from the functional tagger. The combination of n-best lists would not scale up and working on the ambiguous structure itself, the packed forest as in [START_REF] Huang | Forest Reranking: Discriminative Parsing with Non-Local Features[END_REF], might be necessary. Another possibility for future work is to let the phrase-based parser itself perform function annotation, but some preliminary tests on French showed disappointing results.

Second, designing good features, sufficiently general but precise enough, is, as already coined by [START_REF] Charniak | Coarseto-Fine n-Best Parsing and MaxEnt Discriminative Reranking[END_REF], an art. More formally, we can see several alternatives. Dependency structures could be exploited more thoroughly using, for example, tree kernels. The restricted number of candidates enables the use of more global features. Also, we haven't used any language-specific syntactic features. This could be another way to improve this system, relying on external linguistic knowledge (lexical preferences, subcategorisation frames, copula verbs, coordination symmetry . . . ). Integrating features from the phrase-structure trees is also an option that needs to be explored.

Third this architecture enables the integration of several systems. We experimented on French using a part-of-speech tagger but we could also use another parser and either use the methodology of [START_REF] Johnson | Reranking the Berkeley and Brown Parsers[END_REF] or [START_REF] Zhang | K-best combination of syntactic parsers[END_REF] which fusion n-best lists form different parsers, or use stacking methods where an additional parser is used as a guide for the main parser [START_REF] Nivre | Integrating graphbased and transition-based dependency parsers[END_REF].

Finally it should be noted that this system does not rely on any language specific feature, and thus can be applied to languages other that French or English without re-engineering new reranking features. This makes this architecture suitable for morphologically rich languages.

Figure 1 :

 1 Figure1: The parsing architecture: production of the nbest syntagmatic trees (1) tagged with functional labels (2), conversion to a dependency structure (3) and feature extraction (4), scoring with a linear model (5). The parse with the best score is considered as final.

Figure 2 :

 2 Figure 2: Oracle and reranker scores on PTB and FTB data on the dev. set, according to the depth of the n-best.

Figure 3 :Figure 4 :

 34 Figure3: English sentence from the WSJ test set for which the reranker selected the correct tree while the first candidate of the n-best list suffered from an incorrect attachment.SENT

Table 1 :

 1 System results on PTB Test set

	0.8% UAS.
		Baseline Reranker
	F	90.4	91.1
	F < 40	91.0	91.7
	LAS	88.9	89.8
	UAS	93.1	93.9

Table 2 :

 2 System results on FTB Test set

		Baseline Reranker Rerank + MElt
	F	86.6	87.3	87.4
	F < 40	88.7	89.0	89.2
	LAS	87.9	89.0	89.2
	UAS	91.0	91.9	92.1

Table 3 :

 3 Comparison on PTB Test set

	Huang, 2008	91.7 -	-
	Bohnet, 2010	-	90.3	-
	Zhang et al, 2008	91.4 -	93.2
	Huang and Sagae, 2010 -	-	92.1
	Charniak et al, 2005	91.5 90.0 94.0
	Carreras et al. 2008	-	-	93.5
	Suzuki et al. 2009	-	-	93.8
	This work	91.1 89.8 93.9

Table 4 :

 4 Comparison on FTB Test set

		F < 40 LAS UAS
	This work	89.2	89.2 92.1
	MATE + MELT -	89.2 91.8
	BKY-FR	88.2	86.8 91.0
	MST-FR	-	88.2 90.9

Table 5

 5

	,

This implementation is available at https://github. com/jihelhere/adMIRAble. the resources -treebanks and conversion tools -exist.

This can be implemented efficiently using two weight vectors as for the averaged perceptron.

In every template, distance features are quantified in 7 classes: 1, 2, 3,

4, 5, 5 to 10, more.

We use a modified version of evalb that gives the oracle score when the parser outputs a list of candidates for each sentence.

 6 All scores are measured without punctuation.

Acknowledgments

This work has been funded by the French Agence Nationale pour la Recherche, through the project SEQUOIA (ANR-08-EMER-013).


In search of the causes of Parkinson's disease, seasons 1 to 4 Alexis Elbaz 1,2 1 INSERM, U708, Neuroepidemiology, F-75013, Paris, France 2 UPMC Univ Paris 06, UMR_S708, Neuroepidemiology, F-75005, Paris, France Corresponding author Alexis Elbaz, MD, PhD. Inserm Unit 708, Neuroepidemiology. Hôpital de la Salpêtrière. 75651 Paris Cedex 13. France. Email: alexis.elbaz@upmc.fr A comprehensive review on the etiology and epidemiology of Parkinson"s disease (PD), authored by Wirdefeldt and colleagues, is published as a separate supplement by the European Journal of Epidemiology [START_REF] Wirdefeldt | Epidemiology and etiology of Parkinson's disease: a review of the evidence[END_REF]. The authors have undertaken an enormous task, reviewing and synthesizing evidence from over 600 references covering descriptive epidemiology, pre-symptomatic symptoms, genetic epidemiology, and several risk or protective factors of PD. This review provides an up-to-date reference guide and I am certain that it will be of interest to a wide range of scientists and largely cited by them. In another paper from this issue of the Journal, Wang and colleagues investigate the relation between Parkinson's disease and ambient exposure to pesticides in the Central Valley of California using an innovative method of exposure assessment [START_REF] Wang | Parkinson's disease risk from ambient exposure to pesticides[END_REF].

Both papers demonstrate that the field has evolved considerably and represents an exciting area of research with a number of highlights and striking turns of events. We now live in a world in which TV series have become one of the most popular forms of entertainment. While I am certainly not a specialist (indeed, my TV has been broken for quite some time), I am unaware of any show featuring epidemiologists and geneticists as main characters. What would such a show on the continuing search for the causes of PD look like? Let"s turn on the TV.

Season 1

Season 1 is set in London, England, in the XVIIIth and XIXth centuries and it tells the fascinating life of a remarkable man whose name was James Parkinson (1755Parkinson ( -1824)). With each new episode, we see Parkinson grow into a man and become involved in social and revolutionary causes. At the same time, he becomes a doctor and takes over his father"s practice. In addition to numerous medical works in different areas, including gout, appendicitis, and mental health, Parkinson"s major contribution is An Essay on the Shaking Palsy (1817) in which he establishes PD as a clinical entity and gives its classic clinical description. We then see how Parkinson progressively turns from medicine to geology and palaeontology and writes his Organic Remains of the Former World. Many other wonderful stories about this character are told.

One of the last episodes takes place in Paris, a few decades later, when Jean-Martin Charcot, from the Salpêtrière hospital, recognises the significance of Parkinson"s work and, for the first time, calls the condition la maladie de Parkinson.

Unfortunately, despite wonderful actors, beautiful scenery, and historical costumes, season 1 fails to attract a large audience. In order to promote interest, the producers skip many years and, for this season's last episode, transport us to the US in the late 1970s-early 1980s. In 1976, we see a college student manufacturing 1-methyl-4-phenyl-4-propionpiperidine (MPPP), an analog of the synthetic opioid meperidine. The process goes wrong one day and MPTP (1-methyl-4-phenyl-1,2,3,6-tetrahydropyridine) contaminates MPPP. A few days after injecting himself with the product, he rapidly develops Parkinsonism. The next scene takes place in California (1982) where seven young addicts who also used MPPP contaminated with MPTP are diagnosed with Parkinsonism.

The producers have succeeded: as the suspense rises, the audience does too!

Season 2

In the first episode of season 2, scientists are able to determine that MPTP is the responsible agent [START_REF] Langston | Chronic Parkinsonism in humans due to a product of meperidine-analog synthesis[END_REF]. Studies in primates are performed and show that MPTP injections result in Parkinsonism which is improved by levodopa. Scientists determine that MPTP is metabolized into MPP+, which is transported into the neurons by the dopamine transporter and has a chemical structure similar to that of paraquat, a widely used herbicide. This major finding leads to the investigation of pesticides as potential risk factors for PD. Many case-control studies are performed and several show that farming and professional exposure to pesticides are associated with PD; findings for rural living and well-water drinking are less clear [START_REF] Priyadarshi | A meta-analysis of Parkinson's disease and exposure to pesticides[END_REF][START_REF] Priyadarshi | Environmental risk factors and Parkinson's disease: a metaanalysis[END_REF][START_REF] Brown | Pesticides and Parkinson's disease--is there a link?[END_REF].

At the same time, another striking finding emerges. Several epidemiologic studies show that people who smoke cigarettes have a decreased risk of PD. In several episodes of this season and the following ones, this unexpected association is confirmed and meta-analyses show that there is a clear dose-response [7;8]. Researchers try to elucidate what leads to this surprising association, but, as the show progresses, it becomes clear that there is no definitive answer. Twin studies are not in favour of a genetic common cause [9;10]. Cohort studies suggest that survival bias is an unlikely explanation [11;12], and that duration, rather than intensity, of smoking is protective [START_REF] Chen | Smoking duration, intensity, and risk of Parkinson disease[END_REF], a finding that has important implications for animal studies and clinical trials [START_REF] Ritz | After half a century of research on smoking and PD, where do we go now?[END_REF]. It also becomes clear that this association is present as long as 20 years before the disease starts [START_REF] Chen | Smoking duration, intensity, and risk of Parkinson disease[END_REF]. Researchers develop alternative study designs, including assessment of passive [START_REF] Mellick | Passive smoking and Parkinson's disease[END_REF] and parental smoking [START_REF] O'reilly | Smoking and Parkinson's Disease: Using Parental Smoking as a Proxy to Explore Causality[END_REF]. In addition, studies show that the activity of monoamine oxidase B, which metabolizes MPTP into MPP+, is reduced in smokers" brains [START_REF] Fowler | Inhibition of monoamine oxidase B in the brains of smokers[END_REF], and that two cigarette smoke compounds, nicotine and hydroquinone, inhibit the aggregation of alpha-synuclein [START_REF] Hong | Smoking and Parkinson's disease: does nicotine affect alphasynuclein fibrillation?[END_REF]. Over 4000 chemical compounds are created by burning a cigarette and it remains unknown whether other compounds play a role. Altogether, these findings suggest that either smoking is truly neuro-protective, although the precise biological mechanisms are not elucidated, or that reduced smoking in PD patients results from presymptomatic PD (reverse causation) since increasing evidence shows that non-motor symptoms may be present many years before the motor signs appear [START_REF] Savica | When does Parkinson disease start?[END_REF].

A few episodes later, we learn that coffee drinking and the daily amount of caffeine are also inversely associated with PD, independently of smoking [START_REF] Hernan | A meta-analysis of coffee drinking, cigarette smoking, and the risk of Parkinson's disease[END_REF]. In Singapore, black tea, which contains caffeine, is associated with reduced PD risk, while green tea, which does not contain caffeine, is not [START_REF] Tan | Differential effects of black versus green tea on risk of Parkinson's disease in the Singapore Chinese Health Study[END_REF]. Caffeine inhibits the adenosine A2 receptor and clinical trials start investigating selective antagonists of the adenosine A2 receptor as potential PD treatments [START_REF] Stacy | A 12-week, placebo-controlled study (6002-US-006) of istradefylline in Parkinson disease[END_REF].

As season 2 unfolds, the identification of several environmental exposures that modify PD risk gives the audience the impression that PD is mainly due to environmental causes [START_REF] Williams | MPTP parkinsonism[END_REF].

Hey, wait! The last episode takes place at a scientific meeting where geneticists have gathered to discuss their latest findings. Several teams have identified large families in which PD is transmitted as a Mendelian trait. Do genetic factors also play a role? The audience is left with this burning question and will have to wait until season 3.

The ratings have never been that high, Dr House makes a guest appearance, and the show wins its first international award! Season 3

In Season 3, things pick up even more. Several episodes take place in genetic laboratories and each tells the discovery of a new PD gene. Several genes associated with Mendelian forms of the disease are identified, which has a major impact on the understanding of the mechanisms of the disease. Terms such as alphasynuclein aggregation, mitochondrial dysfunction, oxidative stress, or proteasome inhibition are repeatedly cited. Not only are major genes discovered, but susceptibility genes associated with lower penetrance are also identified and shown to increase the risk of sporadic PD.

In parallel, several large cohorts in the US and other parts of the world have identified sufficient numbers of PD patients to investigate a wide range of exposures, such as physical activity, body mass index, dairy products, and uric acid and cholesterol level, without the limitations of case-control studies.

In season 3, we also see how an increasing number of studies find an association between PD and professional exposure to pesticides, although most lack precise exposure assessments and include few exposed subjects [START_REF] Brown | Pesticides and Parkinson's disease--is there a link?[END_REF]. It becomes obvious that professional exposure to pesticides is a complex type of exposure because it entails a large variety of products that have evolved considerably over time and different types of agriculture involve different patterns of exposure (mainly due to different types, frequencies, or methods of spraying, and different types of products). Some studies, including the Agricultural Health Study (AHS) [START_REF] Kamel | Pesticide exposure and selfreported Parkinson's disease in the agricultural health study[END_REF], a French study among farmers [START_REF] Elbaz | Professional exposure to pesticides and Parkinson's disease[END_REF], and a collaborative European study [START_REF] Dick | Environmental risk factors for Parkinson's disease and parkinsonism: the Geoparkinson study[END_REF], take a step further and try to investigate specific products or dose-effect relations using more precise exposure assessment tools. In parallel, toxicological studies start to develop and show that specific pesticides, such as organochlorines, rotenone, paraquat, maneb, are toxic for dopaminegic neurons and induce changes compatible with the mechanisms involved in PD [START_REF] Hatcher | Parkinson's disease and pesticides: a toxicological perspective[END_REF].

Let"s focus on a specific episode of season 3. We are back in California, more precisely in an agricultural region known as the Central Valley. The episode starts in a quiet orchard and the camera zooms on a beautiful orange tree. Suddenly, we hear a plane flying over the countryside and see how it sprays a cloud that progressively falls over the trees: these are the pesticides used to kill the weeds, insects, and fungi that ruin the harvests. Then, we hear the wind blowing and see how the cloud drifts from its target towards a nearby village. The next scene finds Beate Ritz, an environmental epidemiologist, in her UCLA office. While she draws circles on beautifully coloured maps, she explains the Parkinson"s Gene and Environment (PEG) case-control study that aims at investigating whether people who live close (i.e., at a distance of less than 500 meters) to fields sprayed with pesticides are at higher risk of PD. The authors combine land-use data together with data from the Pesticide Use Report (PUR) system that has existed in California since 1974 and the study participants" residential addresses to assess environmental exposure to pesticides. Based on developmental animal models [START_REF] Da | Developmental pesticide models of the Parkinson disease phenotype[END_REF], the authors focus on paraquat and maneb (dithiocarbamate fungicide) and show that people living close to fields sprayed with both pesticides have an increased risk of PD, even after adjusting for occupational exposure. These findings have important implications since they suggest that non-occupational exposure to lower doses of pesticides may increase PD risk, therefore increasing the population attributable fraction due to pesticides if this relation was causal. In addition, this study provides evidence that genetic susceptibility may interact with pesticide exposure [28;29]; other investigators explore this new area of research [START_REF] Dick | Gene-environment interactions in parkinsonism and Parkinson's disease: the Geoparkinson study[END_REF][START_REF] Dutheil | Interaction between ABCB1 and professional exposure to organochlorine insecticides in Parkinson's disease[END_REF][START_REF] Kiyohara | GST polymorphisms, interaction with smoking and pesticide use, and risk for Parkinson's disease in a Japanese population[END_REF], and these findings need to be replicated.

A this point, given the increasing number of studies on the relation between PD and pesticides, agribusiness companies producing pesticides start to become interested in this question, and to fund research, such as the review performed by Wirdefeldt and colleagues [START_REF] Wirdefeldt | Epidemiology and etiology of Parkinson's disease: a review of the evidence[END_REF]. As season 3 becomes ever more intricate, the audience understands that the cause of PD is multifactorial and involves environmental and genetic risk or protective factors.

Several awards later, the audience increases every week and the show has its own Facebook page with millions of fans "liking" it!

Season 4

We are now in the middle of season 4 and the action still isn't letting on. This is the era of genome-wide association studies (GWAS); the actors keep talking about microarrays, SNPs, pathways, interactions, multiple testing, and extremely small p-values. Several GWAS are published and show that in addition to two major susceptibility genes, alpha-synuclein and MAPT [START_REF] Elbaz | Independent and joint effects of the MAPT and SNCA genes in Parkinson disease[END_REF], nine other genes may be associated with sporadic PD [START_REF] Parkinson | Imputation of sequence variants for identification of genetic risks for Parkinson's disease: a meta-analysis of genome-wide association studies[END_REF].

The last episode to date highlights new findings from the AHS [START_REF] Tanner | Rotenone, Paraquat and Parkinson's Disease[END_REF]. The authors of this study focus specifically on pesticides that induce oxidative stress or mitochondrial dysfunction, including rotenone and paraquat, and find them associated with PD. These findings suggest that different pesticides sharing similar mechanisms of action may actually play a role, rather than a single type of product, and that associations with PD may therefore not be limited to a single type of pesticides; therefore, more mechanistic studies on pesticides are needed in order to define which ones are relevant for PD and help exposure assessment. Discussions on causality should consider these recent observations as they are tightly linked to biological plausibility.

In a forthcoming episode, Anthony Wang, a student working with Ritz, presents new findings from the PEG study published in this issue of the Journal [START_REF] Wang | Parkinson's disease risk from ambient exposure to pesticides[END_REF]. This paper investigates ambient exposure to maneb and paraquat based on both residential and occupational addresses, and ziram, another dithiocarbamate fungicide that causes dopaminergic neuron damage in cell culture, is added to the analysis. Except for paraquat, few subjects are exposed to only one of the pesticides, which makes the assessment of their individual effects difficult. The main finding of this paper is that combined exposure to the three pesticides is strongly associated with PD. Pesticides are usually sprayed during working hours: an important strength of the study is that it investigates whether persons who work near fields sprayed with pesticides are at higher risk of PD. The study shows stronger associations for ambient workplace exposure than for residential exposure, thus suggesting that ambient workplace exposure should not be overlooked; it is unclear, however, to what extent working in farms plays a role. Stronger associations are observed for persons younger than 60 years than for older people; the interpretation of this difference is not straightforward since the PUR system exists since 1974 and exposures that may have been relevant for older persons are not included. In this study, combined exposure does not necessarily means exposures occurring at the same time; one important implication is that not only different pesticides may play a role as discussed above, but also the effects of pesticides involving different mechanisms may accumulate, in agreement with a multiple-hit hypothesis.

The GIS-based exposure assessment method developed by the authors represents an important improvement over studies based on self-report and it allows to investigate a wide-range of specific products. This study is the first to implicate ziram, an inhibitor of the ubiquitin-proteasom system, in PD. There are, however, hundreds of pesticides that are often used in conjunction and teasing out their independent effect is likely to be unrealistic. Obviously, the authors need to make a selection of candidate pesticides and they reasonably use prior knowledge for that purpose. Unfortunately, data on the effects of many pesticides in humans and animals remain limited, and it is therefore possible that there may be some degree of confounding; for instance, effect estimates decrease (but remain significant) after adjustment for organochlorine and organophosphate insecticides. Altogether, this study, through the implementation of an innovative method of exposure assessment, makes an important contribution on the role of ambient workplace and residential exposure in PD, and replication of the findings on ziram is needed.

Keep watching

What will happen next? Creative approaches, including detailed exposure assessment methods such as those developed by Ritz"s team, will be required. Sophisticated statistical methods will be needed to analyze multiple correlated exposures and genes and their interactions in large samples. Hopefully, we will see more collaboration between researchers from different fields and we hope to see more toxicologists in the show.

Ideally, these findings will translate into medical practice and help to alleviate PD symptoms, slow PD progression, and even prevent PD. There are, however, still many difficulties and Wirdefeldt and colleagues conclude: "Hence, our hopes to control PD through primary intervention in the foreseeable future are not high" [START_REF] Wirdefeldt | Epidemiology and etiology of Parkinson's disease: a review of the evidence[END_REF].

The show will run and run: keep watching!

Acknowledgments

I thank Hilary Boys, Frédéric Moisan, Marie Vidailhet, and Elisabeth Vincentelli for helpful comments.


Dalil Ichalal

Benoît Marx

Saïd Mammar

Didier Maquin

José Ragot

Observer for Lipschitz nonlinear systems: Mean Value Theorem and Sector Nonlinearity Transformation

The problem of observer design for nonlinear Lipschitz systems is dealt with in this work. An emphasis is put on the maximization of the admissible Lipschitz constant for which the observer design is possible. This problem is tackled using a Takagi-Sugeno modeling approach. The idea is to rewrite the state estimation error dynamics as an autonomous Takagi-Sugeno system, using the Mean Value Theorem and the sector nonlinearity transformation. State estimation error dynamics stability is studied with the Lyapunov theory by choosing a non-quadratic Lyapunov function and by computing its variation between m consecutive samples. The interest of these manipulations is to obtain LMI conditions admitting solutions for large values of the Lipschitz constant. Finally, illustrative examples are provided in order to highlight the performances of the proposed approach.

I. INTRODUCTION

Many problems in control and monitoring need the knowledge of the state variables and the parameters of the system. However, measuring these variables is faced to two major problems. The first one concerns the technical and economical reasons, indeed, nowadays many sensors are very expensive and bulky. The second problem is that some state variables are not accessible for measure. Therefore, the problems of state estimation and observer design become the heart of control and monitoring design systems.

Most of the developed state estimation methods are based on linear models of the studied systems [START_REF] Luenberger | An introduction to observers[END_REF], [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF], [START_REF] Darouach | Full-order observers for linear systems with unknown inputs[END_REF]. However, linear models only describe the behavior of the system around a specific operating point which leads to degraded performances far from this particular point. In order to increase the system performances the use of nonlinear models seems very interesting and appropriate because it allows an accurate representation of the system on a wide operating range. Despite the accurate system description, the disadvantage of the nonlinear approach is the lack of a unified and general solution for observer design. The existing results are dedicated to specific classes of nonlinear systems, such as Lipschitz systems or bilinear systems. Many approaches have been then elaborated, for example, those based on the nonlinear transformation of the original nonlinear system into a linear one such as using immersion, Lie algebraic transformations, etc [START_REF] Besanc ¸on | An immersion-based observer design for rank-observable nonlinear systems[END_REF], [START_REF] Besanc ¸on | Nonlinear observers and applications[END_REF], [START_REF] Keller | Nonlinear observer design by transformation into a generalized observer canonical form[END_REF]. It is pointed out in many works that this kind of approaches is very Dalil Ichalal and Saïd Mammar are with the IBISC Laboratory, Evry-Val-d'Essonne University, 40, rue de Pelvoux, 91020 Evry Courcouronne Cedex {dalil.ichalal, said.mammar}@ibisc.univ-evry.fr Benoit Marx, José Ragot and Didier Maquin are with CRAN, Université de Lorraine, France {benoit.marx, didier.maquin, jose.ragot}@univ-lorraine.fr difficult to achieve due to the strong conditions under which these transformations exist. When these transformations fail to solve the problem, it has also been proposed to use the "high gain observer". The key point in this type of observers is to determine the gains in order to counteract the effect of the nonlinearities (see [START_REF] Thau | Observing the state of non-linear dynamic systems[END_REF]). However, high gains penalize the state estimation in the presence of measurement noises.

Recently, observer design for Lipschitz systems has intensively been studied since many nonlinearities encountered in practical systems satisfy the Lipschitz condition, at least locally. Firstly, in [START_REF] Thau | Observing the state of non-linear dynamic systems[END_REF], the problem of observer design for Lipschitz systems is studied and sufficient conditions are established to guarantee the asymptotic stability of the state estimation error dynamics. However, a design method is not proposed to determine the observer gain. In [START_REF] Raghavan | Observer design for a class of nonlinear systems[END_REF], an iterative design approach is proposed to find the observer gain by solving an algebraic Riccati equation. Unfortunately, this algorithm may fail to provide a solution even if the observability condition is satisfied. In [START_REF] Rajamani | Observers for Lipschitz nonlinear systems[END_REF], necessary and sufficient existence conditions of an observer are proposed, by formulating them as an H ∞ standard problem. However, it is pointed out that this standard problem may have no solution because the regularity assumption is not satisfied. This work is extended in [START_REF] Pertew | H ∞ observer design for lipschitz nonlinear systems[END_REF] by transforming the problem in order to satisfy the regularity assumption required in the H ∞ optimization.

The main idea of the work cited above is still to compute the observer gain in order that the linear part counteract the effect of the nonlinear part; the major problem is that if the Lipschitz constant of the nonlinearity is greater than an admissible value, the design methods cannot be applied. In some recent works [START_REF] Zemouche | Observers for a class of Lipschitz systems with extension to H-infinity performance analysis[END_REF], the mean value theorem (MVT) is used to write the state estimation error as a linear parameter varying (LPV) system. Contrarily to the other methods, the use of the MVT allows to obtain a solution, even for large Lipschitz constant. Many of the cited works are extended to discrete time case [START_REF] Bara | Observer synthesis for lipschitz discrete-time systems[END_REF], [START_REF] Korbicz | LMI-based strategies for designing observers and unknown input observers for non-linear discretetime systems[END_REF], [START_REF] Abbaszadeh | Robust H ∞ filter design for Lipschitz nonlinear systems via multiobjective optimization[END_REF].

In this work, the problem of observer design for Lipschitz nonlinear system is considered. An approach combining the MVT and the sector nonlinearity transformation is proposed. First, based on a Lipschitz assumption, the state estimation dynamics is written as a Linear Parameter Varying (LPV) system. Secondly, the sector nonlinearity transformation is used to transform the LPV system into a Takagi-Sugeno (T-S) system. The aim of this last step is to apply the recent developments in stability analysis and stabilizing controller design [START_REF] Kruszewski | Nonquadratic stabilization conditions for a class of uncertain nonlinear discrete time TS fuzzy models: A new approach[END_REF]. As pointed out above, the proposed result may have a solution, even for large values of the Lipschitz constant. Moreover, if no solution exists, it is possible to relax the conditions by using the results proposed in [START_REF] Kruszewski | Nonquadratic stabilization conditions for a class of uncertain nonlinear discrete time TS fuzzy models: A new approach[END_REF] for T-S systems.

The paper is organized as follows. Some preliminaries are detailed and the addressed problem is stated in Section II. The transformation of a Lipschitz system into a T-S one and the observer design for the latter are exposed in Section III. Before concluding, illustrative examples are provided in Section IV.

Notations. The symbol * denotes the terms induced by symmetry in a block matrix or in a matrix product (i.e., for any matrices M and N, * MN stands for N T MN). The notation ξ s,i is used to denote the i th vector of the canonical basis of R s (i.e. with all components are null, except the i th which is equal to "1").

II. PRELIMINARIES AND PROBLEM STATEMENT

Let us consider the discrete-time nonlinear system given by

x(k + 1) = Ax(k) + f (x(k), u(k))
(1)

y(k) = Cx(k) (2)
where x(k) ∈ R n , u(k) ∈ R n u , y(k) ∈ R n y are the system state, input and output respectively and

f (x(k), u(k)) is a function of x(k) and u(k) containing nonlinearities of the system. Assume that f (x(k), u(k)
) is globally Lipschitz or at least locally Lipschitz in a region D including the origin with respect to x(k) and uniformly in u(k). So, we have

f (x 1 , u) -f (x 2 , u) ≤ γ x 1 -x 2 (3) ∀x 1 , x 2 ∈ R n globally Lipschitz ∀x 1 , x 2 ∈ D locally Lipschitz (4)
The parameter γ > 0 is the Lipschitz constant and . is the 2-norm. The state observer for the system (1)-( 2) is given in the form

x(k + 1) = A x(k) + f ( x(k), u(k)) + L(y(k) -ŷ(k)) (5) ŷ(k) = C x(k) (6)
Defining the state estimation error e

(k) = x(k) -x(k), from (1)
-( 2) and ( 5)-( 6), the state estimation error dynamics is given by

e(k + 1) = (A -LC) e(k) + f (x(k), u(k)) -f ( x(k), u(k)) (7)
The goal consists on determining the observer gain L such that the observer error dynamics is asymptotically stable (lim k→+∞ e(k) = 0). Many approaches are proposed in the literature in order to cope with this problem [START_REF] Bara | Observer synthesis for lipschitz discrete-time systems[END_REF], [START_REF] Abbaszadeh | Robust H ∞ observer design for a class of nonlinear uncertain systems via convex optimization[END_REF], [START_REF] Abbaszadeh | A robust observer design method for continuous-time Lipschitz nonlinear systems[END_REF], [START_REF] Raghavan | Observer design for a class of nonlinear systems[END_REF], [START_REF] Rajamani | Observers for Lipschitz nonlinear systems[END_REF]. In particular, design methods based on LMI conditions are studied but it is known that in general, the Lipschitz constant γ appears in the LMI conditions, like in the following lemma.

Lemma 1: [START_REF] Bara | Observer synthesis for lipschitz discrete-time systems[END_REF] The state estimation error converges asymptotically to zero if there exists two matrices K ∈ R n×n y , P = P T > 0 ∈ R n×n and a positive scalar τ such that the following LMI holds  

-P + τγ 2 I A T P -C T K T A T P -C T K T * P -τI 0 * * -P   < 0 (8)
The observer gain L is then obtained by L = P -1 K. These approaches are based on finding the gain L in order that the linear part of the state estimation error dynamics counteracts the effect of the nonlinear part, but if the Lipschitz constant is greater than a maximal admissible value, denoted γ ad , the approaches fail to provide the gain L.

In this work, a new approach is proposed in order to increase the value of the admissible Lipschitz constant by transforming this problem into a stability relaxation one for T-S system, using the MVT and sector nonlinearity transformation. The stability is then studied using a Lyapunov theory and a non-quadratic Lyapunov function. The stability conditions are formulated in term of linear matrix inequalities which have a solution for large values of the Lipschitz constant.

The following lemmas are used in the remainder of the paper.

Lemma 2: [START_REF] Peaucelle | A new robust D-stability condition for real convex polytopic uncertainty[END_REF] For any matrices Q and A of appropriate dimensions, finding P = P T > 0 satisfying ( 9) is equivalent to finding P = P T > 0 satisfying [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF] and also to finding P = P T > 0 and G satisfying ( 11)

A T PA -Q < 0 (9) -Q A T P PA -P < 0 (10) -Q A T G T GA -G -G T + P < 0 ( 11
)
Lemma 3: [START_REF] Delmotte | Continuous Takagi-Sugeno's models: Reduction of the number of LMI conditions in various fuzzy control design technics[END_REF] For any matrices T 1 , T 2 , T 3 and A of appropriate dimensions, finding P = P T > 0 satisfying [START_REF] Korbicz | LMI-based strategies for designing observers and unknown input observers for non-linear discretetime systems[END_REF] is equivalent to finding P = P T > 0 and G satisfying (13)

T 3 * T 2 T 1 + A T PA < 0 (12)   T 3 * * T 2 T 1 * 0 GA P -G -G T   < 0 (13) Lemma 4: (Mean value theorem) Consider g(z) : R n → R. Let a, b ∈ R n . If g(z) is differentiable on [a, b] then there exists a vector z ∈ R n with z ∈]a, b[ (i.e. zi ∈]a i , b i [, for i = 1, . . . , n), such that g(a) -g(b) = ∂ g ∂ z (z)(a -b) (14) Lemma 5: (Sector nonlinearity approach) [21], [16] Any nonlinear function g(z) : R → R satisfying g ≤ g(z) ≤ g, ∀z (15)
can be written as

g(z) = µ 1 (z)g + µ 2 (z)g (16)
where

µ 1 (z) = g -g(z) g -g µ 2 (z) = g(z) -g g -g ( 17
)
and the functions µ i (z) satisfy the convex sum property i.e. µ 1 (z) + µ 2 (z) = 1 and 0 ≤ µ i (z) ≤ 1, ∀z.

III. NEW OBSERVER DESIGN ALGORITHM

In order to compute the gain of the observer ( 5)-( 6), the state estimation error dynamics ( 7) is transformed into a T-S system. For that purpose, the last two terms in [START_REF] Chilali | H-infinity design with pole placement constraints : an LMI approach[END_REF]

are studied. Let us denote z T (k) = [x T (k) u T (k)] and ẑT (k) = [ xT (k) u T (k)].
Since the function f (z) is differentiable, using lemma 4, there exists n constant vectors zi (k), with zi

j (k) ∈ ]z j (k) ẑ j (k)[ for j = 1, . . . , n + n u , such that f (z(k)) -f (ẑ(k)) = n ∑ i=1 n+n u ∑ j=1 ξ n,i ξ T n+n u , j ∂ f i ∂ z j (k) (z i )(z(k) -ẑ(k)) (18) where ξ n,i = 0 1 • • • 0 i-1 1 i 0 i+1 • • • 0 n ( 19
)
which means that ξ n,i is a vector of dimension n that the component i is "1" and the others are zero. Since the n u last components of (zẑ) are null, it follows

f (z(k)) -f (ẑ(k)) = n ∑ i=1 n ∑ j=1 ξ n,i ξ T n, j ∂ f i ∂ x j (k) (z i (k))(x(k) -x(k)) (20
) Then, the state estimation error dynamics (7) obtained with the system (1)-( 2) and the observer ( 5)-( 6) becomes

e(k + 1) = n ∑ i=1 n ∑ j=1 ξ n,i ξ T n, j ∂ f i ∂ x j (k) (z i (k)) + A -LC e(k) (21)
Since the function f (x, u) is Lipschitz with respect to x, its derivatives are bounded

ãi j2 ≤ ∂ f i ∂ x j (x, u) ≤ ãi j1 , ∀x, u, i, j = 1, ..., n (22)
where ãi j1 and ãi j2 are known constants. With the lemma 5, each derivative can be written as

∂ f i ∂ x j (k) (z(k)) = 2 ∑ l=1 v l i j (z(k)) ãi jl ( 23
)
where the functions v 1 i j and v 2 i j are defined by

v 1 i j (z(k)) = ∂ f i ∂ x j (k) (z(k)) -ãi j2 ãi j1 -ãi j2 , v 2 i j (z(k)) = ãi j1 -∂ f i ∂ x j (k) (z(k)) ãi j1 -ãi j2 (24) 2 ∑ l=1 v l i j (z(k)) = 1, 0 ≤ v l i j (z(k)) ≤ 1, l = 1, 2 (25)
Using [START_REF] Zemouche | Observers for a class of Lipschitz systems with extension to H-infinity performance analysis[END_REF], the dynamics of the state estimation error can now be written as

e(k + 1) = A -LC + n ∑ i=1 n ∑ j=1 2 ∑ l=1 v l i j (z(k))ξ n,i ξ T n, j ãi jl e(k) (26)
Following the sector nonlinearity transformation [START_REF] Tanaka | Fuzzy Control Systems Design and Analysis: A Linear Matrix Inequality Approach[END_REF], where the functions v l i j are factorized, it is possible to rewrite (26) under the form

n ∑ i=1 n ∑ j=1 2 ∑ l=1 v l i j (z(k))ξ n,i ξ T n, j ãi jl = q ∑ i=1 h i (z(k))A i ( 27
)
where q ≤ 2 n 2 and where the different components of the matrices A i are given by the parameters ãi jl . Since the functions h i (z(k)) are defined by the products of some functions v 1 i j and v 2 i j , they satisfy the convex sum property

q ∑ l=1 h i (z(k)) = 1, 0 ≤ h i (z(k)) ≤ 1, ∀k ∈ N, i = 1, . . . , q (28)
From (28), it follows that

A -LC = q ∑ i=1 h i (z(k)) (A -LC).
Then, defining Π i = A i + A -LC, the dynamics of the state estimation error (26) is written in the following form

e(k + 1) = q ∑ i=1 h i (z(k))Π i e(k) (29)
Note that a general sector nonlinearity approach has been recently proposed in [START_REF] Nagy | Model structure simplification of a biological reactor[END_REF] allowing an adequate choice of additional parameters in order to ensure the observability of the local models (namely, the pairs (A i ,C i )). In our problem, this result can be used in order to guarantee the observability of the pairs

(A i + A,C).
The stability of such type of systems has been extensively studied these recent years. Hence, useful results exist such as the quadratic stability obtained by a quadratic Lyapunov function. Thereafter, some relaxed stability conditions are provided with particular Lyapunov functions [START_REF] Kruszewski | Nonquadratic stabilization conditions for a class of uncertain nonlinear discrete time TS fuzzy models: A new approach[END_REF].

The stability of the system (29) is studied, in this section, in order to determine the gain L which stabilizes the state estimation error dynamics. We start with a result for stability analysis with quadratic Lyapunov function. The result is then extended using a new type of Lyapunov function for relaxed stability conditions.

A. Classic Lyapunov function for observer design

Based on the stability analysis of the autonomous T-S system generating the state estimation error (29), sufficient observer existence conditions are derived in the following theorem.

Theorem 1: The state estimation error in equation ( 29) converges asymptotically towards zero if there exists a symmetric positive definite matrix P ∈ R n×n and a matrix K ∈ R n×n y such that the following LMIs hold ∀i = 1, ..., q

-P A T P + A T i P -C T K T PA + PA i -KC -P < 0 (30)
The gain L of the observer is computed from L = P -1 K. Proof: Consider the quadratic Lyapunov function defined by

V (e(k)) = e T (k)Pe(k), P = P T > 0 (31)
Its discrete time derivative is defined by

∆V (e(k)) = V (e(k + 1)) -V(e(k)) (32) = q ∑ i=1 h i (z(k))e T (k) Π T i PΠ i -P e(k) < 0 (33) Obviously, ∆V (e(k)) < 0 holds if q ∑ i=1 h i (z(k)) Π T i PΠ i -P < 0 (34)
With the Schur complement, (34) is equivalent to

q ∑ i=1 h i (z(k)) -P Π T i P PΠ i -P < 0 (35)
where Π i is defined in (29). Finally, using the convex sum property (28) and the variable change K = PL, the LMI (30) in theorem 1 are obtained.

It is known that if the number of sub-models increases then it becomes difficult or even impossible to obtain a common matrix P satisfying the LMIs proposed in theorem 1. This conservatism has been largely studied and some results have been established to reduce it. In the next section, the approach proposed by [START_REF] Kruszewski | Nonquadratic stabilization conditions for a class of uncertain nonlinear discrete time TS fuzzy models: A new approach[END_REF] for controller design is adapted to observer design.

B. Multi-samples Lyapunov function for observer design

The main idea is to compute the variation of the Lyapunov function between the samples k and k + m where m > 1.

It is proved that increasing m relaxes the obtained LMI conditions. Obviously, setting m = 1 will lead to the result given in the theorem 1. The observer existence conditions derived with this approach are given in the next theorem.

Theorem 2: If there exists symmetric and positive definite matrices P i ∈ R n×n and matrices G ∈ R n×n and K ∈ R n×n y such that the LMIs (36) hold, then the state estimation error converges asymptotically towards zero.

          -P 0 Φ i 0 0 0 • • • 0 * Ω 0,1 Φ i 1 0 • • • 0 * * Ω 1,2 . . . . . . . . . * * * . . . Φ i m-2 0 * * * * Ω m-2,m-1 Φ i m-1 * * * * * Ω m-1           < 0 (36) i 0 = 1, ..., q / i 1 = 1, ..., q ... i m-1 = 1, ..., q
where

Ω i,i+1 = -G -G T + P i -P i+1 , i = 0, . . . , m -2 Ω m-1 = -G -G T + P m-1 Φ i j = A T G T + A T i j G T -C T K T , j = 0, ..., m -1 The observer gain is computed by L = G -1 K (37) Proof: Let us define the Lyapunov function candidate V m (E m (k)) by V m (E m (k)) = m-1 ∑ i=0 e T (k + i)P i e(k + i) ( 38
)
where the matrices P i are symmetric and positive definite and E m (k) is defined by

E m (k) = e T (k) . . . e T (k + m) T ( 39
)
Defining Ψ k by

Ψ k = q ∑ i=1 h i (z(k))Π i (40)
the equation (29) leads to

e(k + 1) = Ψ k e(k) (41) e(k + 2) = Ψ k+1 Ψ k e(k) (42) . . . e(k + m) = Ψ k+m-1 • • • Ψ k+2 Ψ k+1 Ψ k e(k) (43)
The variation of the Lyapunov function is given by

∆V m (E m (k)) = m-1 ∑ j=0 e T (k + j + 1)P j e(k + j + 1) - m-1 ∑ j=0 e T (k + j)P j e(k + j) (44)
With (43), the following stability condition is obtained

e T (k) m-1 ∑ j=0 ( * )P j Ψ k+ j × • • • × Ψ k - m-1 ∑ j=0 ( * )P j Ψ k+ j-1 × • • • × Ψ k e(k) < 0 (45)
After calculation, (45) becomes

m-2 ∑ j=0 ( * ) P j -P j+1 Ψ k+ j × • • • × Ψ k (46) +( * )P m-1 Ψ k+m-1 × • • • × Ψ k -P 0 < 0 For ℓ = 1, . . . , m -1, let us define Γ ℓ by Γ ℓ = ( * )P m-1 Ψ k+m-1 × • • • × Ψ k+ℓ + m-2 ∑ j=ℓ ( * ) P j -P j+1 Ψ k+ j × • • • × Ψ k+ℓ + P ℓ-1 -P ℓ (47)
From this definition, it can be seen that Γ ℓ satisfies

Γ ℓ = Ψ T k+ℓ Γ ℓ+1 Ψ k+ℓ + P ℓ-1 -P ℓ (48)
The inequality (46) can be written in the form

Ψ T k Γ 1 Ψ k -P 0 < 0 ( 49
)
Using Lemma 2, (49) is equivalent to

-P 0 (GΨ k ) T GΨ k -G -G T + Γ 1 < 0 ( 50
)
With Lemma 3 and (48), (50) becomes  

-P 0 (GΨ k ) T 0 GΨ k -G -G T + P 0 -P 1 (GΨ k+1 ) T 0 GΨ k+1 Γ 2 -G -G T   < 0 (51)
Finally, repeating this procedure (m -2) times, with the variable change K = GL and since the functions h i (z(t)) satisfy (28), the LMI (36) of the theorem 2 are obtained.

IV. ILLUSTRATIVE SIMULATIONS In this section, illustrative examples are studied. In the first example, the proposed approach is compared to existing ones. The chosen criterion is the maximum value of the Lipschitz constant for which a solution exists. In the second one, the observer proposed in theorem 2 is applied to estimate the state of a nonlinear model.

A. Example 1

Let us consider the discrete-time Lipschitz nonlinear system, proposed in [START_REF] Korbicz | LMI-based strategies for designing observers and unknown input observers for non-linear discretetime systems[END_REF], given by ( 1)-( 2)

A = 0.2 0.01 0.1 0.2 , C = 1 0 (52) and f (x(k)) = 0 α sin(x 1 (k)) (53)
The nonlinear function f (x(k)) is Lipschitz with constant γ = |α|. The observer design method in [START_REF] Korbicz | LMI-based strategies for designing observers and unknown input observers for non-linear discretetime systems[END_REF] admits a solution only for a Lipschitz constant γ ≤ 0.7916 and the approach in [START_REF] Bara | Observer synthesis for lipschitz discrete-time systems[END_REF] admits a maximal Lipschitz constant γ ≤ 0.81. Then if γ is greater than these values, these methods fail to provide a solution to the LMI conditions. Using the MVT combined with the sector nonlinearity transformation, the LMI conditions are relaxed and the existence of a solution could be expected for larger values of the constant Lipschitz.

Let us compute the Jacobian matrix of f (x(k)) as follows

∂ f (x(k)) ∂ x(k) = 0 0 α cos(x 1 (k)) 0 (54)
Considering the premise variable z(k) = cos(x 1 (k)) and calculating the matrices A i , the parameter α giving the Lipschitz constant appears, then, in the matrices A i allowing us to make a comparison between the cited approaches and the proposed one. For example, using theorem 3 with m = 2, the admissible Lipschitz constant is γ = 101. These results are summarized in the following table.

Method

Maximum γ [START_REF] Korbicz | LMI-based strategies for designing observers and unknown input observers for non-linear discretetime systems[END_REF] 0.7916 [START_REF] Bara | Observer synthesis for lipschitz discrete-time systems[END_REF] 0.81 Theorem 3 (m = 2) 101

B. Example 2: Rossler's system

In this second example, the proposed method is implemented to estimate the state variables of a Rossler's system, which is a nonlinear system [START_REF] Mata-Machuca | Chaotic systems synchronization via high order observer design[END_REF]. The discrete time version with sampling time T = 0.01 of this system is given by the following equations

x(k + 1) = Ax(k) + f (x(k)) + D ( 55
)
where

A =   1 -0.01 -0.01 0.01 1.002 0 0 0 0.95   , D =   0 0 0.02   , (56)
f (x(k)) =   0 0 0.01x 1 (k)x 3 (k)   (57)
Assuming that only the state variable x 2 (k) is measured, the output equation is y(k) = Cx(k) with C = [0 1 0]. By applying the mean value theorem, one obtains

f (x) -f ( x) = ∂ f ∂ x ( x)(x -x) (58) where ∂ f (x) ∂ x =   0 0 0 0 0 0 0.01x 3 0 0.01x 1   (59)
It is known that the Rossler's system state are bounded, as it can be seen on the figure 1. The lemma 5 is applied to the bounded state variables x 1 and x 3 . The state estimation error dynamics can be given as follows

e(k + 1) = 4 ∑ i=1 h i (z(k)) (A + A i -LC) e(k) (60)
where

A 1 =   0 0 0 0 0 0 0.20452 0 0.104   , A 2 =   0 0 0 0 0 0 1.52 × 10 -4 0 0.104   , A 3 =   0 0 0 0 0 0 0.20452 0 -0.0815   , A 4 =   0 0 0 0 0 0 1.52 × 10 -4 0 -0.0815  
Note that it is not necessary to compute the functions h i because they are not required for observer design. Only the matrices A i are needed. With these matrices, theorem 3 is applied with m = 2. The states and their estimates are depicted in figure 2 for k ∈ [0 5000] and the state estimation errors are illustrated in the figure 3 only for k ∈ [0 500] in order to show the forgetting of the initial conditions. The asymptotic convergence is then illustrated. The transient phenomenon can be reduced by pole clustering in a LMI region as illustrated in [START_REF] Chilali | H-infinity design with pole placement constraints : an LMI approach[END_REF]. In this paper, a new observer design for discrete time nonlinear Lipschitz systems is proposed. It is based on the transformation of the state estimation error dynamics by the use of the Mean Value Theorem in order to use the sector nonlinearity transformation to derive an autonomous Takagi-Sugeno system. The stability of the latter is studied with the Lyapunov theory using different Lyapunov functions in order to obtain more relaxed stability conditions. LMI formulation of the stability conditions are provided. The focus is made on the fact that the problem of admissible Lipschitz constant is transformed on a relaxed stability problem. From the examples it is clear that when the classical methods fail to provide a solution the proposed one may have a solution by changing the number of samples on which the variations of the Lyapunov function are computed. In future works, the proposed observer will be extended for uncertain Lipschitz systems and unknown input estimation with an application for vehicles and motorcycles state estimation.

Fig. 1 .

 1 Fig. 1. State trajectory of the Rossler's nonlinear system

3 Fig. 2 . 3 Fig. 3 .

 3233 Fig. 2. State variables and their estimates