Ji Hyungsuk

Isc

Sabine Ploux
email: ploux@isc.cnrs.fr

Eric Wehrli Latl

Lexical Knowledge Representation with Contexonyms

) classifies them in a multi-dimensional semantic space. Trained on very large corpora, the model provides relevant, organized contexonyms that reflect the fine-grained connotations and contextual usage of the target word, as well as the distinct senses of homonyms and polysemous words. Further study on the neighbor effect showed that the model can handle the data sparseness problem.

Introduction

With progress in natural language processing techniques (NLP), increasingly sophisticated models and methods have been proposed in the machine translation (MT) research.

New techniques distinguish the minute differences between similar words [START_REF] Edmonds | Nearsynonymy and lexical choice[END_REF] or take into account collocations [START_REF] Edmonds | Choosing the word most typical in context using a lexical co-occurrence network[END_REF], idioms [START_REF] Wehrli | Translating idioms[END_REF], or contextually related words [START_REF] Dagan | Word sense disambiguation using a second language monolingual corpus[END_REF][START_REF] Lin | Concept discovery from text[END_REF], etc.

This kind of approach depends to varying extents on adequate references. For the fine-grained lexical knowledge model (FLK) [START_REF] Edmonds | Nearsynonymy and lexical choice[END_REF], having adequate references is indispensable, or the model will not work in practical applications.

However, such detailed references are limited in number, and manual lexicographic coding is too time-consuming to continuously update new information. Other problems with the classical lexicographic organization have been pointed out, such as its inability to represent the semantic distance between defined senses and its failure to properly organize the senses, and alternatives have been proposed [START_REF] William | Word sense ambiguation: clustering related senses[END_REF][START_REF] Budanitsky | Semantic distance in wordnet: An experimental, applicationoriented evaluation of five measures[END_REF][START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF][START_REF] Christopher | Automatic acquisition of a large subcategorization dictionary from corpora[END_REF][START_REF] Ploux | Modélisation et traitement informatique de la synonymie[END_REF][START_REF] Pustejovsky | Lexical knowledge representation and natural language processing[END_REF].

In addition, subtle lexical knowledge is too vague and too broad to handle. For instance, relations like * Institut des Sciences Cognitives, UMR 5015 CNRS, 67, boulevard Pinel, 69675 BRON cedex France † Institut National Polytechnique de Grenoble ‡ Laboratoire d'Analyse et de Technologie du Langage stagger -drunken, which could be informative for non-English speakers or machines, are too numerous to be processed. Intra-word relations share this problem: while the English word write is considered to have the same semantic value in "write a diary" and "write an article", the French words écrire and rédiger, respectively, are widely used in these two phrases. This sort of sense division is also too minute and too frequent to be captured using conventional manual lexicography techniques.

An alternative would therefore be to automatically generate the related words for a given word, which could serve as a reference. Clearly, contextually related words are meaningful indicators of the target word's semantic value in a given context. For instance, two sets of words { lit, candle, cigarette } and { tennis, final, win } are trustworthy cue-word sets for disambiguating the word match; stupid is more closely related to blunder than to error [START_REF] Edmonds | Nearsynonymy and lexical choice[END_REF], and peace distinguishes treaty from contract [START_REF] Dagan | Word sense disambiguation using a second language monolingual corpus[END_REF].

Such word lists may be obtained for target words by selecting seed words and performing an iterative, decision-list-making task [START_REF] Yarowsky | Unsupervised word sense disambiguation rivaling supervised methods[END_REF], or by latent semantic indexing (LSI) [START_REF] Landauer | An introduction to latent semantic analysis[END_REF]. A common limitation of these approaches, however, is that they do not provide a fully automatic method for organizing the related words obtained: identifying seed words needs human intervention and LSI does not provide an automatic classification other than a restricted matching-based one that requires an encyclopedia as a source text [START_REF] Laham | Latent semantic analysis approaches to categorization[END_REF].

A fully automated sense-discrimination method based on a second-order comparison in semantic space has been proposed [START_REF] Schütze | Automatic word sense discrimination[END_REF]. Because this approach focuses on comparing vectors for disambiguation, it does not explicitly produce a relevant set of words. Unlike a direct method (e.g. Yarowsky's), this technique takes all word relations into account, not just those between the target word and its neighbors. This technique proved effective for data sparseness problems (along with LSI) but it has some distance to go for lexical knowledge representation. For instance, words that have never cooccurred with a target word can, in principle, be the closest ones to it.

Dagan and Itai demonstrated how contextually related words could contribute to selecting a proper target word in MT tasks [START_REF] Dagan | Word sense disambiguation using a second language monolingual corpus[END_REF]. However, since their study focused on target-word selection, the problem of how to organize and assign source-word senses was not addressed.

In this paper, we present a model that explicitly produces contextually related words and classifies them after training on a large corpus. The model uses a rather straightforward method, in the sense that it considers co-occurrences of words. The main distinction between the model presented here and other statistical ones is that it generates the minimal senses of words (cliques) in order to organize the related words obtained. Cliques are then represented on the principal plane. This makes it possible to represent several target words in MT tasks. Ploux et al. proposed the prototype of a model that represents synonym senses from a non-senseclassified synonym database [START_REF] Ploux | Modélisation et traitement informatique de la synonymie[END_REF][START_REF] Ploux | Construction d'espaces sémantiques à l'aide de dictionnaires informatisés des synonymes[END_REF] and a two-language synonymmatching model based on a mapping method [START_REF] Ploux | A model for matching semantic maps between languages (French / English, English / French)[END_REF]. The main difference between the present model and the previous one is that the present model is fully automated, insofar as it does not need any kind of hand-coded references, only raw text sources. Furthermore, different sets of cliques can be obtained according to chosen criteria. This will be explained later.

Contexonym

We define contexonyms as relevant contextually related words for a target word. By context, we mean a certain number of neighboring words of the target word (from a small-sized window to one or more paragraphs). Unlike synonyms or antonyms, contexonyms are not symmetric or transitive (i.e., when target word W has contexonyms c 1 , c 2 , ..., c n , W is not necessarily a contexonym of c i (1 ≤ i ≤ k), and this is also true between c i s).

Second, contexonyms are more dynamic and fuzzy than synonyms or antonyms, and they evolve faster (cf. [START_REF] Ji | Automatic contexonym organizing model[END_REF]. Without any neighboring words, the contexonyms of a target word reflect various typical semantic relations. The word match, for example, may have contexonyms related to "wooden lighter", "game" and "marriage". On the other hand, the presence of the neighbors of the word could change this equivocal situation, giving a polarized semantic field of the word. Finally, unlike synonyms or antonyms, contexonyms are often from mixed grammar categories.

We hypothesize that the more adequate a training corpus is, the more relevant and robust the contexonyms obtained from it will be. By an adequate corpus, we mean a sufficiently large and well balanced corpus.1 . If correctly designed, the model is expected to also simulate the above characteristics of contexonyms.

The procedure for constructing an automatic contexonym-organizing model is briefly presented below.

Model STEP 1

For a given corpus, co-occurrences of all types in a defined passage (a sentence in this study) are counted and stored. Each headword W n i (1 ≤ i ≤ N , where N is the total number of types in the corpus) has children (c j s) that are arranged in descending order of co-occurrence with W n i ; children with co-occurrences smaller than a 10,000th of the global frequency of the headword W n i are removed to reduce noise:

W n i : c 1 , c 2 , . . . , c n STEP 2
For the target word, a word-association table is constructed using four factors.

STEP 2-1

In order to eliminate children that rarely co-occur with W n i , the first α portion (where 0 < α ≤ 1)) of the words is selected. And W n i becomes:

W n i : c 1 , c 2 , . . . , c k ,
where k = nα and n is the original number of children of W n i .

STEP 2-2

The factor β(0 < β ≤ 1) serves to cut off rarely co-occurring children of the child c j :

c m j : g 1 , g 2 , . . . , g l (1 ≤ j ≤ k, l = mβ).
In this way, the following word-association table is obtained:

Headword Selected Rejected W n i c 1 , c 2 , . . . , c k c k+1 , . . . , c n c m 1 g 1 , g 2 , . . . , g l g l+1 , . . . , g m . . . c p k h 1 , h 2 , . . . , h q h q+1 , . . . , h p Table 1: Candidate contexonym table.

STEP 2-3

The factor γ(0 < γ ≤ β) has the same role as β except that γ is smaller, which makes it possible to have different sets of cliques without changing the global contexonyms obtained in the previous step. This gives another word-association table (Table 2), which will be used later to obtain cliques (l ′ = mγ and q ′ = pγ).

Headword Selected Rejected W n i c 1 , c 2 , . . . , c k c k+1 , . . . , c n c m 1 g 1 , g 2 , . . . , g l ′ . . . , g l , . . . , g m . . . c p k h 1 , h 2 , . . . , h q ′ . . . , h q , . . . , h p Table 2: Second contexonym table.

STEP 2-4

The factor δ is on/off Boolean. If the headword W n i is not found among c j children (g 1 , . . . , g l ) in Table 1, c j itself in W n i and the c j row (which contains c j 's children) are removed from both tables whenever δ is on (in this study, δ was set to on). This filtering step gives the following final contexonym set (C n i ) for W n i :

C n i = {c i : 1 ≤ i ≤ k, c i ∈ D} (k = nα),
where D is the set of c j words removed by filtering.

STEP 3

Cliques are calculated from these two tables. A clique is a mathematical term in graph theory meaning a maximum, complete subgraph. If w 1 has w 2 and w 3 as its members and vice versa for w 2 and w 3 , then w 1 , w 2 and w 3 form a clique. Otherwise, if say w 3 has only w 1 as its member, they fail to form a clique. If w 1 , w 2 , w 3 , and w 4 form another clique, it 'absorbs' the clique w 1 , w 2 , w 3 , resulting in only one clique. Table 2 can be used to calculate these cliques. Composed of several sets of words, cliques are considered in our model as minimal units of a contexonym that represent finer meanings than the word itself.

STEP 4

A correspondence factor analysis (proposed by Benzécri [START_REF] Benzécri | Correspondence Analysis Handbook[END_REF]) was used to represent correlations between cliques. The output is represented as a geometric semantic space that has as many axes as the total number of contexonyms chosen, in such a way that each axis could represent the corresponding word. The distance χ 2 between two cliques, y i and y j , is calculated in order to represent the cliques in a multi-dimensional space:

χ 2 (y i , y j ) = n k=1 x .. x .k x ik x i.
x jk x j.

2

, where x .. = n i=1 p j=1 x ji , x .i = p k=1 x ki and x i. = n k=1 x ik ; n is the total number of contexonyms and p is the total number of cliques; x ji is equal to 1 if the i th contexonym belongs to the j th clique, and equal to 0 otherwise. Since every clique has its own coordinates, clique distances are proportional to clique relatedness.

When (1) cliques y i and y j have many contexonym members or (2) many contexonyms belong to cliques y i and y j , they should be less representative. This was considered in the first and second terms of the equation, respectively, by a distance-reducing effect.

STEP 5

Cliques are projected onto a two-dimensional space and are classified by hierarchical clustering. This detailed feature of the model is explained with some examples below.

Test on Examples

The model was first trained on an English corpus maintained by Project Gutenberg (PG), which includes literature, essays, and other writings. Any kind of electronic dictionary or encyclopedia was excluded from the training corpus. The database thus constructed was combined with another, separate database trained on the British National Corpus (BNC). The total number of tokens in the training corpora was over 300 million. For French words, the model was trained on five years of the French newspapers Le Monde and L'Humanité.

With α = β = γ = 0.05, 50 contexonyms and 133 cliques were obtained for the target word match. Some of the cliques are: Clustering can be done with either cliques or contexonyms. In this study, the latter was always used. In general, stricter constraints (smaller values of α, β and γ) give fewer contexoyms than lenient ones. Below are some examples. Brackets indicate disjoint relations between contexonyms, curly brackets denote classifications on the principal plane, and parentheses, classifications on a nonprincipal plane. The contexonyms kick and kicked for the word bucket suggest the idiom "kick the bucket" (an example in [START_REF] Wehrli | Translating idioms[END_REF], and the contexonym article for the French rédiger reflects their relatedness.

• drunken (α = 0.05 β = 0.05 γ = 0.05):

[

Test on Edmonds and Hirst's Examples

In discussing near-synonymy, Edmonds and Hirst carefully investigated the subtle differences between the words blunder, error, lapse and slip, and the pairs of words order/enjoin, forest/woods [START_REF] Edmonds | Nearsynonymy and lexical choice[END_REF].

As shown in Table 3, while blunder has the contexonyms stupid and stupidity, there are no such contexonyms for error, suggesting that the former has stupidity as a connotation while the latter does not. Contexonyms like unpardonable, fatal, grievous, awful, indiscretion and egregious characterize the target word blunder by its strength, blameworthiness, and pejorative character, unlike the word error. The contexonyms of lapse like forgotten, memory, and minutes also reflect the word's usage; the contexonyms written, wrote, lines and tongue, among other senses of the word slip, suggest that it is used for mistakes in speech or writing.

The test on woods gave the contexonyms houses, path, walk, and walking, which were not among the contexonyms of forest, while deer, beasts, hunting, castle and knight were the contexonyms of forest and not of woods. This is consistent with Room's observation (1985, as cited in (Edmonds and[START_REF] Edmonds | Nearsynonymy and lexical choice[END_REF]).

Overall, the fine-grained subcategorical differences between similar words, as discussed in the FLK model [START_REF] Edmonds | Nearsynonymy and lexical choice[END_REF], were successfully reflected here. Moreover, other subcate-gorical features that were not discussed in the original studies were found: the contexonyms of error reflect its scientific usage; the contexonyms coffee, wine, supper and tea for order suggest that the verb is applicable to asking for drinks (α = β = γ = 0.05 for the GP corpus). This information is not trivial, since the English order in this situation should be translated into the French commander and not ordonner, which fits other situations such as military ones.

Test on Dagan and Itai's Examples

In discussing the problem of selecting a proper target word in MT, Dagan and Itai presented some examples: sign (rather than seal, finish or close) is the correct verb to use with treaty, and treaty (rather than contract) is the proper word to use with peace. In the following sentence, the first word in curly brackets is the correct one in each case [START_REF] Dagan | Word sense disambiguation using a second language monolingual corpus[END_REF]: The five words peace, treaty, chances, achieved and diplomats were tested using the model trained on the GP and BNC corpora. In Table 4, the boldface words in the contexonym list are more closely related to the headword than similar words (e.g. sealed, closed, enlarge, conversations, etc.), which were not selected as contexonyms in the given factor condition. match + wins matches, strength, play, chance, won, league, cricket, games, fight, club, final, game, points, united, record, victory, team, season, marriage, daughter, prix, match, box, draws, wins, loses, lighted, cigarette, lit, , champion, won, defeat, play, game, champions, doubles, player, league, players, tennis, davis, sets, minutes, michael, tournament, team, victory, season, yesterday, today, wins, weeks, jim, agassi, match, edberg, ivanisevic, sampras Table 5: The merging effect for match and its neighbors (α = β = γ = 0.05). The contexonyms are ordered by nearness to the origin (i.e., representativeness).

•

Test with the Merging Method

Since the information carried by a target word's contexonyms is relevant, it is directly applicable to some MT tasks. Consider the sentence below:

• The final was Hewitt's first and Sampras' 17th, but the less experienced 20-year-old Australian was much more energetic. After consecutive wins against former champions Pat Rafter, Andre Agassi and Marat Safin, Sampras appeared to have nothing left for his second match in barely 24 hours.

Widely-used machine translators like Systran, Babel Fish, and FreeTranslation incorrectly translate the words the final into the French words le final, and match into allumette (wooden lighter), whereas the correct translations are la finale and match, respectively.

Trained on five years of the French newspapers Le Monde and L'Humanité, our model produces the contexonyms finale and match for the target words Agassi, champions and victoires, and finale only for Rafter and Sampras. This clearly points to the correct target-language words.

Yet, two problems remain unsolved: first, unlike the target-language selection phase, no disambiguation is performed for the source language; second, potential data sparseness problems [START_REF] Lee | Distributional similarity models: Clustering vs. nearest neighbors[END_REF] are not covered by this direct approach. The first problem involves assigning the meaning of the word match in the concerned paragraph to a proper cluster. But as Figure 2 shows, there are no contexonyms shared with the text in question.

We present the contexonym merging method as a remedy to these problems. This consists in inputting more than one target word to get the contexonyms. To compensate for the global frequency effect, a normalizing merging method is used. Table 5 shows the gradual exclusion of less-closely-related contexonyms like cigarette and marriage, and the gradual inclusion of more relevant ones such as player and tennis.

Another way to discriminate the target word's sense is to observe the linking contexonyms. For example, match and wins have no shared cliques and the region they cover is disjoint in the principal projection. But they are linked by the intermediate contexonyms play and games, which share areas with the match and wins cliques. One solution to the data sparseness problem is to build a decision list, as proposed by Yarowsky [START_REF] Yarowsky | Unsupervised word sense disambiguation rivaling supervised methods[END_REF], using contexonyms as starting seed words 3 . Although the current model was not designed to solve such a problem, the merging method could be considered as an indirect alternative. For instance, stars and mathematician have no common contexonyms but they are linked by astronomer in a merging search, suggesting that stars should be interpreted as celestial bodies and not as actors.

Conclusion

In this paper, we presented a model that automatically produces and organizes the contexonyms of a target word. The test results show that the model (1) reflects the fine-grained senses of the word, and (2) provides typical trustworthy target-language words for MT that reflect the contextual usage of the word. The merging effect for more than one word shows that the model can also be used in disambiguation tasks and as a lexical knowledge representation reference.

•

  1: applied, marriage, match, proved 6: box, candle, dropped, lighted, match, struck, threw 68: burned, candle, flame, lamp, lighted, lit, match 93: cigar, cigarette, lighted, lit, match, pipe 109: fight, game, match, proved, shot, won While the contexonyms shooting and maker each belong to only one clique, struck belongs to 49 cliques. In other words, maker has only one minimal semantic value and struck has 49 'different semantic values'. This difference is represented in Figure1by the region that each contexonym covers (i.e., possessing clique points).

Figure 1 :

 1 Figure 1: Some contexonyms of match.

Figure 2 :

 2 Figure 2: Classification of the contexonyms of match.

Figure 3 :

 3 Figure 3: Representation of conductor.

Figure 2

 2 Figure 2 shows the output of this classification. Figure 3 is another example of such a representation 2 .In general, stricter constraints (smaller values of α, β and γ) give fewer contexoyms than lenient ones. Below are some examples. Brackets indicate disjoint relations between contexonyms, curly brackets denote classifications on the principal plane, and parentheses, classifications on a nonprincipal plane. The contexonyms kick and kicked for the word bucket suggest the idiom "kick the bucket" (an example in[START_REF] Wehrli | Translating idioms[END_REF], and the contexonym article for the French rédiger reflects their relatedness.

  Diplomats believe that the joining of Hon Son {increases | enlarges | magnifies} the chances for achieving {progress | advance | advance ment} in the {talks | conversations | calls}.

Figure 4 :

 4 Figure 4: Merging of wins and match.

Table 3 :

 3 Output of test on Edmonds and Hirst's examples.

	Word	α	β	γ	Contexonyms
	blunder	0.05 0.10 0.05	{blunder, mistake} {commit, committed} {stupid}
		0.30 0.30 0.30	[{corrected, political, reckon, blunder, mistake, minister, serious, fatal, pardon, terrible, aw-
					ful, joke} {unpardonable, gross, committing, stupidity, grievous, stupid, ignorance, guilty,
					commit, committed, excuse, mistakes} {survived, tragic} {egregious}] [speelman] [tacti-
					cal]
	lapse	0.10 0.20 0.10	{considerable, mere, ten, twenty, lapse, slow, absence, rate, sudden, fifty, forgotten, mem-
					ory, allowed, minute, months} {evidence, species, progress, century, original, changes,
					vast, ages, centuries} {recall, moments, interval, minutes} {geological, organic} {strata}
					{momentary}
	slip	0.05 0.10 0.05	{past, slip, tried, run, fall, hold, managed, opportunity, try, allowed, easy, chance, eas-
					ily} {tree, watch, rope, letting, quietly} {foot, caught, front, drew, fingers, neck, handed,
					pocket} {tongue, book, paper, written, wrote}
	enjoined	0.10 0.20 0.10	{commands, strictly, obedience, instructions, obey, strict, commanded, enjoined, ab-
					stain, duty, expressly, orders} {multitude, earnestly, silence} {penance, perform, priests}
					{secrecy}
	ordered	0.05 0.05 0.05	{captain, horse, immediately, company, send, placed, ready, six, service, ordered, party,
					court, pay} {troops, attack, enemy, city, command, line, horses, officers, war, army, sol-
					diers} {carriage, dinner, master, table} {march} {costs}
	error	0.05 0.05 0.05	{trial, evil, human, errors, lead, false, wrong, error, truth, correct, ignorance, fatal, com-
					mitted, opinion, due, judgment, causes, serious, avoid, fault} {fallen, source, lies, ways,
					discovered, common, fall} {mistake} {mistaken, supposing}

Table 4 :

 4 france, peace, war, law, nation, city, sense, free, cause, desire} {earth, happiness, live, spirit, hold, land} {foreign, nations, terms, justice, states, united} {heaven, happy, soul, joy, quiet} {security, treaty} treaty {terms, rights, united, states, treaty, france, french, british, foreign, spain, peace, powers, agreed, subject, war, article, britain} {alliance, majesty, concluded, emperor} {territory, commerce, american, citizens, congress, mexico} {signed, ratified, senate} chances {calculated, finding, risk, probability, ten, election, favour, nine, success, chances, favor} {game, missed, desperate, plenty, calculate, chance, getting, happen, escape, survival} {increase, increased, reduce, diminished, improve} {promotion, victory, winning} achieved {achieved, real, period, process, history, result, increase, development, greater, actually, considerable, progress, growth, results, purpose, per, objectives, using} {economic, aim, position, areas, ways} {success, record, sales, task} {independence, status} {victory} diplomats {libya, embassy, p., talks, sanctions, saudi, jan., libyan, reported, iraqi, kuwait, diplomatic, embassies, diplomats, ambassador, foreign} {politicians, journalists, consuls, countries, officials, intelligence, claimed, ministry} {expulsion, expelled, yugoslav} {diplomacy, eighteenth} {statesmen} Test on Dagan and Itai's Examples other words can be tested interactively on-line (http://dico.isc.cnrs.fr/dico/context/search).

		{eaten, feast} {brutal, mob} {reeled, stag-
		gered} {reeling, staggering}] [orgies] [stagger]
		[swearing]
		• bucket (α = 0.05 β = 0.05 γ = 0.05):
		[buckets] [contents, emptied, tin] [mop] [rope]
		• bucket (α = 0.05 β = 0.10 γ = 0.05):
		[{carrying, empty, filled, tin, wash, buck-
		ets, fill, contents, emptied, poured} {bottom,
		mop, bucket, ice, wooden} {chain, rope}
		{file, record}] [dipped] [kick, kicked] [pack-
		ing] [pump] [spade]
		• rédigé (α = 0.05 β = 0.10 γ = 0.05):
	brawl] [brute] [drink, drunk, sober, wine]	{lui-même, rendu, rédigé, signé, acte, article, présenté, publication, daté, document, base, in-
	[reeled, staggered] [reeling, staggering] [sailor]	struction, chambre, avis, bureau, communiqué}
	[stupor]	{intitulé, lire, professeur, commun, essen-
	• drunken (α = 0.05 β = 0.10 γ = 0.05): [ {(coarse, shouts, street, streets, dirty, songs, mad, fellow, driver, driving, dancing,	tiel, pages, publié, guide, manifeste, ouvrage, langue, mémoire, rapports} {code} {tiberi} {alinéa}
	fool, singing, drunken, laughter) (drunk, brute, asleep, wine, drank, sober, drink, song) (stupor, sailor, sailors, brawl, crying) (killed) (fury)}	Since there is no room in this paper to list complete examples, our demonstration of the model is limited to the examples introduced in
		two articles that share some interests with the
		current paper.	More than 100,000 types of

2 From now on, no more than 30 of the most closely-related contexonyms are presented for each example (in lowercase).

  whoever match + wins + championswon, game, division, champions, defeat, final, united, games, champion, club, yesterday, season, draw, points, victory, strength, fight, play, team, players, australia, chance, defending, match, record, matches, wins, daughter, struck, lighted

	match + agassi + sampras	tennis, champion, minutes, struck, play, final, davis, won, doubles, yesterday, players,
		michael, game, player, jim, tournament, today, defeat, victory, weeks, opening, monday,
		sets, agassi, match, wimbledon, edberg, goran, ivanisevic, sampras
	match + champions + wins +	final
	agassi + sampras

A specific corpus would be considered adequate if a specific domain is being processed (e.g. science, religion, or spoken language).


R Delpoux
email: romain.delpoux@inria.fr

T Floquet

On-line parameter estimation via algebraic method: An experimental illustration

Keywords: Parameter identification, Algebraic method, Magnetic bearing, PMSM

This article presents an algebraic on-line parameters estimation method for Linear Time Invariant (LTI) systems subject to polynomial perturbations. Particular attention is given to practical implementation. The estimator may be expressed as simple FIR filter, which is advantageous for online application, since the coefficients may be computed offline. The robustification against possible singularities is shown and the approach has the advantage of eliminating singularities that may occur in the experimental identification. This algorithm is illustrated experimentally on a Permanent Magnet Stepper Motor (PMSM) and a magnetic bearing for which parametric estimation is known to be a difficult task. The parameters to be estimated are sometimes measurable with difficulties and may slightly vary over time.

I. INTRODUCTION

This article is concerned with parameter identification based on an algebraic method. The general framework of this method has been introduced by M. Fliess and H. Sira-Ramirez [START_REF] Fliess | An algebraic framework for linear identification[END_REF][START_REF] Fliess | Closed-loop parametric identification for continuous-time linear systems via new algebraic techniques[END_REF]. It is based on differential algebra and operational calculus. Unlike traditional methods, the proposed estimator is non-asymptotic: the solutions are obtained by exact algebraic formulas, one to obtain estimates in finite time. The desired parameters are expressed as a function of integrals of the measured outputs and inputs of the system. It does not need any statistical knowledge of the noise (for instance, the assumption that the noise is Gaussian is not required). Moreover, the estimator is able to treat identification in the presence of bias and of structured perturbations (cf. Definition 4 of [START_REF] Mboup | Parameter estimation for signals described by differential equations[END_REF]). For these reasons, the algebraic method has been applied to many fields such as abrupt change detection, delay identification [START_REF] Belkoura | Estimation problems for a class of impulsive systems[END_REF][START_REF] Belkoura | Parameters estimation of systems with delayed and structured entries[END_REF][START_REF] Fliess | Algebraic change-point detection[END_REF][START_REF] Tiganj | An algebraic method for eye blink artifacts detection in single channel EEG recordings[END_REF], and numerical differentiation [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF][START_REF] Riachy | Différentiation numérique multivariable I : estimateurs algébriques et structure[END_REF].

Many different methods for parameter identification exist in the literature. One of the most popular concepts is the regression (linear or nonlinear), such as in [START_REF] Söderström | System Identification[END_REF][START_REF] Blauch | High-speed parameter estimation of stepper motors[END_REF]. Observer based approaches can also be found, such as asymptotic observers using the extended Kalman filter [START_REF] Bittanti | On the parametrization and design of an extended Kalman filter frequency tracker[END_REF] or finite time ones like sliding modes observers [START_REF] Barbot | Iterative higher order sliding mode observer for nonlinear systems with unknown inputs[END_REF][START_REF] Bejarano | Finite-Time Converging Jump Observer for Switched Linear Systems with Unknown Inputs[END_REF][START_REF] Floquet | Parameter estimation via second order sliding modes with application to thermal modelling in a high speed rotating machine[END_REF][START_REF] Pisano | Contact force estimation and regulation in active pantographs : an algebraic observability approach[END_REF]. The general framework of parameter identification via algebraic method initially was proposed in [START_REF] Mboup | Parameter estimation for signals described by differential equations[END_REF], based on Mikusiński's field of operators. The theory and the methodology are described and illustrated with numerical simulation. In [START_REF] Morales | Nonlinear Control for Magnetic Levitation Systems Based on Fast Online Algebraic Identification of the Input Gain[END_REF], an experimental application was proposed for a one direction magnetic levitation system for the identification of one parameter with the annihilation of a constant perturbation. The identification of several parameters has experimentally been applied for a LTI system in [START_REF] Cortes-Romero | Algebraic parameter identification for induction motors[END_REF]. In the literature, one can find articles dealing with estimation for sinusoidal signal parameters [START_REF] Trapero | An algebraic frequency estimator for a biased and noisy sinusoidal signal[END_REF][START_REF] Ushirobira | Algebraic parameter estimation of a biased sinusoidal waveform signal from noisy data[END_REF]. Linear infinite dimensional systems parameter identification was proposed in [START_REF] Rudolph | An algebraic approach to parameter identification in linear infinite dimensional systems[END_REF] and the approach was developed for delay systems and systems described by spatially-dependent partial differential equations (PDEs).

This paper presents a method for parameter identification in the case of n th order LTI systems subject to polynomial perturbations. While the general framework was introduced in [START_REF] Mboup | Parameter estimation for signals described by differential equations[END_REF], in this paper, particular attention is given to the practical implementation. Explicit formulas are given for the integral computations. The expressions are written as FIR filters, which allows their coefficients to be computed offline and provides more efficient estimators for real time application. Finally, an approach is proposed to robustify the estimation. The approach has the advantage of eliminating singularities that may occur in the experimental identification. Finally a concrete application of the results is applied to two different electromechanical systems: (i) a Permanent Magnet Stepper Motor (PMSM) and (ii) a magnetic bearing. Both systems are nonlinear, and several parameters have to be identified simultaneously.

This article is divided into three parts. Section II presents a general formula for the estimation of the parameters of LTI systems subject to perturbations. In the second section, practical issues are introduced concerning the implementation of the estimator. The last section is devoted to the identification of the parameters on two experimental applications where the performance of the algorithm is highlighted.

II. Algebraic Approach

The parameter identification using an algebraic approach for linear time invariant differential equations has been studied in several papers. The obtained analytical expressions are not unique. Different expressions can be derived [START_REF] Gensior | Algebraic Parameter Identification and Asymptotic Estimation of the Load of a Boost Converter[END_REF][START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF][START_REF] Rudolph | An algebraic approach to parameter identification in linear infinite dimensional systems[END_REF][START_REF] Tian | Fast state estimation in linear time-varying systems: an algebraic approach[END_REF][START_REF] Trapero | An algebraic frequency estimator for a biased and noisy sinusoidal signal[END_REF][START_REF] Linares-Flores | A comparison between the algebraic and the reduced order observer approaches for on-line load torque estimation in a unit power factor rectifier-DC motor system[END_REF]. Consider the following LTI system subject to perturbations:

n i=0 a i y (i) (t) = m i=0 b i z (i) (t) + ̟(t). (1)
where the a i and b i are the system parameters (to be identified), with a n = 1 and m < n. y(t) ∈ R and z(t) ∈ R are measured quantities of the system. The variable

̟(t) = κ i=1 c i t i-1
(i-1)! , κ ∈ N stands for perturbations or uncertainties assumed to be polynomial.

Theorem 1 An estimation of the unknown parameters a 0 , ..., a n-1 , b 0 , ...b m of equation ( 1) is given by:

Θ(t) =            â0 . . . ân-1 b0 . . . bm            = F 1a -F 1b F 2a -F 2b -1 [∆P (t)] -1           -F n,1 [y(t)] . . . -Fn,n[y(t)] -F n,n+1 [y(t)] . . . -F n,n+m+1 [y(t)]           ∆Q(t) , (2)
with:

F 1a =    F 0,1 [y(t)] . . . F n-1,1 [y(t)] . . . . . . . . . F 0,n [y(t)] . . . F n-1,n [y(t)]    , F 1b =    F 0,1 [z(t)] . . . F m,1 [z(t)] . . . . . . . . . F 0,n [z(t)] . . . F m,n [z(t)]    , F 2a =    F 0,n+1 [y(t)] . . . F n-1,n+1 [y(t)] . . . . . . . . . F 0,n+m,1 [y(t)] . . . F n-1,n+m+1 [y(t)]    , F 2b =    F 0,n+1 [z(t)] . . . F m,n+1 [z(t)] . . . . . . . . . F 0,n+m+1 [z(t)] . . . F m,n+m+1 [z(t)]    ,
where

F i,p [f (t)] = κ+n j=n-i c i,j t 0 (t -τ ) γ (-τ ) j f (τ )dτ γ! , (3)
with γ = κ + 2n + p -i -j -1, c i,j = κ + n j (κ + i)! (i + j -n)! ,
and p ∈ {1, . . . , n + m + 1} represents the number of unknown parameters to be estimated.

Proof of Theorem 1: The expressions obtained in Theorem 1 are constructed as follows:

Consider the Laplace transformation of (1):

n i=0 a i (s i Y (s) -s i-1 y(0) -... -y (i-1) (0)) = m i=0 (s i Z(s) -s i-1 z(0) -... -z (i-1)(0) + κ i=0 c i s i . (4)
The initial conditions, as well as the perturbations are considered as undesired parameters. The perturbations, being structured, are easily annihilated by multiplying both sides of (4) with s κ , followed by a derivation of order κ.

The initial conditions are eliminated by differentiating equation ( 4) n times more . It leads to the linear differential operator:

Π = d κ+n ds κ+n s κ . (5)
In light of the Leibniz formula:

d h (X(s)Y (s)) ds h = h j=0 h j d h-j (X(s)) ds h-j d j (Y (s)) ds j , (6)
and the relationship:

d k (s l ) ds k =      l! (l-k)! s l-k , if 0 < k ≤ l, 0, if 0 < l < k, (-1) k (k-l-1)! (-l-1)! s l-k , if l < 0 < k. (7)
one obtains:

n i=0 a i   κ+n j=n-i κ + n j (κ + i)!s i+j-n (i + j -n)! d j (Y (s)) ds j   = m i=0 b i   κ+n j=n-i κ + n j (κ + i)!s i+j-n (i + j -n)! d j (Z(s)) ds j   . (8)
Recall that derivation w.r.

c i,j s κ+2n+p-i-j d j (Y (s)) ds j = m i=0 b i κ+n j=n-i c i,j s κ+2n+p-i-j d j (Z(s) ds j , (9)
where:

c i,j = κ + n j (κ + i)! (i + j -n)! .
Use the following formulas to obtain [START_REF] Cortes-Romero | Algebraic parameter identification for induction motors[END_REF] in the time domain:

L -1 1 s l d k Y (s) ds k = t 0 . . . τ2 0 (-τ 1 ) k y(τ 1 )dτ 1 . . . dτ l ,
for l ≥ 1, and:

t 0 . . . τ2 0 y(τ 1 )dτ 1 . . . dτ l = t 0 (t -τ ) l-1 y(τ ) (l -1)! dτ.
These two formulas together give:

L -1 1 s l d k Y (s) ds k = t 0 (t -τ ) l-1 (-τ ) k y(τ ) (l -1)! dτ. (10)
In the time domain, equation (9) leads to:

n i=0 a i   κ+n j=n-i c i,j t 0 (t -τ ) κ+2n+p-i-j-1 (-τ ) j y(τ )dτ (κ + 2n + p -i -j -1)!   = m i=0 b i   κ+n j=n-i c i,j t 0 (t -τ ) κ+2n+p-i-j-1 (-τ ) j z(τ )dτ (κ + 2n + p -i -j -1)!   . (11)
with p ∈ {1, . . . , n + m + 1}.

One obtains as many equations as parameters to identify. This can be written under the form (2).

✷ Remark 1 Algebraic manipulations to obtain [START_REF] Bejarano | Finite-Time Converging Jump Observer for Switched Linear Systems with Unknown Inputs[END_REF] are not unique. A method to find minimal annihilators, as well as differential numerators with good numerical properties once back in the time domain can be found in [START_REF] Ushirobira | Algebraic parameter estimation of a biased sinusoidal waveform signal from noisy data[END_REF].

III. Implementation Issues

In this section, implementation issues are discussed. First, the integrals are rewritten as linear filters in order to optimize the computation time required for on-line estimation. Then, a method is proposed to avoid singularities that may occur when inverting the matrix in (2).

FIR representation of the estimator

In the previous section, Theorem 1 was proposed to obtain an algebraic estimator for parameter identification. The algebraic estimator is expressed systematically as a combination of expressions similar to [START_REF] Delpoux | Parameter estimation of permanent magnet stepper motors without position or velocity sensors[END_REF]:

v(t) = t 0 (t -τ ) γ (-τ ) k y(τ ) γ! dτ. ( 12
)
This expression is an integral on the time intervals [0, t[. For long time interval, the measurement noise and unmodelled term contributions, such as assumptions on the polynomial perturbation on a window, are considered as unstructured perturbations and have harmful effects on the calculation of integrals. One can mention [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF], concerning a study about the noise contribution on these estimators. In order to minimize these effects, the integrals are computed on a sliding window [t -T f , t], where T f represents the size of the latter . The integral [START_REF] Fliess | Algebraic change-point detection[END_REF] then is approximated on a sliding horizon by:

v(t) = t t-T f (t -σ) γ (t -T f -σ) j γ! f (σ)dσ (13)
Setting

σ 1 = τ -(t -T f ),
we get an expression of integral ( 13) on the interval [0, T f ]:

v(t) = T f 0 (T f -σ 1 ) γ (-σ 1 ) j γ! g(σ1) f (t -T f + σ 1 )dσ 1 . (14)
It is important to note that the function g(σ) is independent of the time t. Thus, this function can be computed off-line which reduces the computational load during real-time estimation. Finally, the time interval is normalized on an interval I = [0, 1] by introducing σ 2 = σ 1 T f . The integral [START_REF] Fliess | Closed-loop parametric identification for continuous-time linear systems via new algebraic techniques[END_REF] becomes:

1 0 T γ+j f (1 -σ 2 ) γ (-σ 2 ) j γ! g2(σ2) f (t -T f (1 -σ 2 ))dσ 2 = 1 0 g 2 (σ 2 )f T f (1 -σ 2 )dσ 2 , (15)
where

f T f (u) = f (t -T f u).
The integral in the interval [0, 1] is a classical input-output linear time filtering relation [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF].

For implementation purposes, considering that the sampling period T s is constant and that T f = M T s , the integrals are approximated with the numerical integration method:

1 0 h(λ)dλ ≈ M m=0 W m h(t m ), (16)
where W m and t m = mT s /T f , m = 0, . . . , M are the weights and the abscissas. Using the trapezoidal integration method, the weights correspond to:

W 0 = W M = T s 2 and W m = T s , m = 1, . . . , M -1.
From the approximation [START_REF] Gensior | Algebraic Parameter Identification and Asymptotic Estimation of the Load of a Boost Converter[END_REF] and from [START_REF] Floquet | Parameter estimation via second order sliding modes with application to thermal modelling in a high speed rotating machine[END_REF], one obtains:

1 0 g(σ 2 )f T f (1 -σ 2 )dτ ≈ M m=0 W m g m f M-m , (17)
where

g m = g(mT s /T f ) and f M-m = f T f (1 -mT s /T f ).
The integral is obtained from the output of a classical FIR digital filter with impulse response c m = W m g m , where the input is the sampled signal.

Note that the results obtained from the FIR implementation of the sliding window lead to the implementation using the MAC Unit of a DSP proposed in [START_REF] Gensior | Algebraic Parameter Identification and Asymptotic Estimation of the Load of a Boost Converter[END_REF]. The generalized estimator could also be applied to the case of this article.

Robust estimation

From equation ( 2), the algebraic estimator can be expressed as:

∆P Θ = ∆Q, ( 18
)
where Θ is the vector of the parameters to be estimated,

∆P = F 1a -F 1b F 2a -F 2b and ∆Q =          -F n,1 [y(t)] . . . -F n,n [y(t)] -F n,n+1 [y(t)] . . . -F n,n+m+1 [y(t)]          .
The vector of estimated parameters is obtained if the matrix ∆P is invertible. The matrix ∆P is generically invertible, i.e. for almost every t, there are time instants where ∆P is singular. In order to provide an estimation of the parameters at any instant, one needs to robustify the estimation against possible singularities of the matrix ∆P . Pre-multiply both terms of equation ( 18) by (∆P ) T . Integrate both terms of the equation during a time interval [t -T f , t], extracting the constant vector of parameters Θ out of the integration, to obtain:

S(t) Θ = t t-T f (∆P ) T ∆Qdλ , (19)
where S(t) = t t-T f (∆P ) T ∆P dλ . This matrix is symmetric and positive definite because ∆P is generically invertible. For online application and especially when the number of parameters to be estimated is large, solving this linear equation system can be done without computing any determinant, one can use the LU decomposition for example. Since the matrix S(t) is symmetric and positive definite, the Cholesky decomposition would be better, because it is about twice as efficient as the method previously mentioned.

Remark 2 Note that the estimation of the parameters is not obtained before time t = T f . Thus, the parameter vector is chosen arbitrarily for t ∈ [0, T f [. After time t = T f , the estimation is obtained from [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF].

IV. Applications

The performance of the estimators is presented experimentally in this section through its application on two different electromechanical processes. The parameter estimation algorithm first is applied for the identification of the electrical parameters of a PMSM. Then, the estimator will be applied on a magnetic bearing which is a more complex example since it is an inherently unstable system where the dynamics are strongly nonlinear. In both cases, the experiments are performed as illustrated in Fig. 1. The value of the parameters to be estimated is chosen arbitrarily at the beginning of the experiment. For a while, the control is applied with the wrong parameters to show the behavior of the misidentified system. Then, at t = T f the parameter estimation starts. Once the time reaches the first sliding window length, the estimated parameters are applied to the control. Choosing the window length is not straightforward because the window should be chosen long enough to attenuate the noise. Indeed, the estimator plays the role of low pass filter. In the absence of perturbations, increasing the window length T f would lead to a more accurate estimation. Nevertheless, the estimator is designed under the assumption that the structured perturbations, to be annihilated, are polynomials on the window. This limits the window length so that the assumption remains true. The computer hardware on the test benches are dSpace cards 1104, with ControlDesk software as interface. Using the library RTlib developed by dSpace, the algorithms are implemented in C language. To solve this problem, closed-loop control methods must be used. For such methods to succeed, the model of the motor and its parameters have to be well-known, which brings to the forefront the necessity of parameter identification. Equations [START_REF] Löwis | Flatness-based trajectory tracking control of a rotationg shaft[END_REF] give the standard PMSM model in the phase (or winding) variables:

           L di a dt = v a -Ri a + Kω sin(n p θ), L di b dt = v b -Ri b -Kω cos(n p θ), J dω dt = K (i b cos(n p θ) -i a sin(N θ)) -τ, (20)
where, v a and v b are the voltages applied to the two phases of the PMSM, i a and i b are the two phase currents, L is the inductance of a phase winding, R is the resistance of a phase winding, K is the back-EMF constant (and also the torque constant), θ is the angular position of the rotor, ω = dθ/dt is the angular velocity of the rotor, n p is the number of pole pairs (or rotor teeth), J is the moment of inertia of the rotor (including the load) and τ represents the load torque.

The phase model can be transformed using Park's transformation [START_REF] Park | Two-reaction theory of synchronous machines generalized method of analysis-part I[END_REF]. The system ( 20) is transformed into the so-called d -q model:

           L di d dt = v d -Ri d + n p Lωi q , L di q dt = v q -Ri q -n p Lωi d -Kω, J dω dt = Ki q -τ. (21)
The d -q transformation is commonly used for PMSM (and synchronous motors in general) because it results in constant voltages and currents at constant speed (instead of the high-frequency phase variables). Also, the model highlights the role of the quadrature current i q in determining the torque. This application is concerned with the identification of the electrical parameters R, L and K. It is important to identify these parameters because they may vary for different reasons, such as heating. Another parameter that could be identified is the inertia J. Nevertheless the inertia is identifiable when the acceleration is non-null. In order to identify this parameter, it would be necessary to apply large variations on the motor, so that high acceleration is produced. Such trajectories are not suitable for on-line applications. Moreover, this parameter does not really vary and can be estimated off-line using methods similar to those in [START_REF] Delpoux | Parameter estimation of permanent magnet stepper motors without position or velocity sensors[END_REF].

With the objective being to identify the electrical parameters, one must consider the electrical equations of ( 21), and one notes:

ω d = n p ωi d , ω q = n p ωi q ,
and

Γ 1 = 1 L , Γ 2 = R L , Γ 3 = K L .
The equations are written under the form:

       di d dt = Γ 1 v d -Γ 2 i d + ω q , di q dt = Γ 1 v q -Γ 2 i q -ω d -Γ 3 ω. ( 22a
) (22b) 4.1.2

. Estimation of the electrical parameters

Several algebraic manipulations can lead to the identification of the three parameters. This identification is performed by generating two equations with the equation of the direct current i d and a third one which is obtained from the equation of the quadrature current i q . Thus, we obtain three equations to identify the three parameters R, L and K.

In order to apply Theorem 1, one considers equation (22a) with the quantities di d dt , ω q , v d and i d . There is no perturbation in these equations, so κ = 0. Finally, p = 2 is the number of unknowns. The estimator is expressed as:

-F 0,1 [v d (t)] F 0,1 [i d (t)] -F 0,2 [v d (t)] F 0,2 [i d (t)] Γ 1 Γ 2 = -F 1,1 [i d (t)] + F 0,1 [ω q (t)] -F 1,2 [i d (t)] + F 0,2 [ω q (t)] , (23)
where, for any function f (t), F i,p [f (t)] are defined in [START_REF] Belkoura | Estimation problems for a class of impulsive systems[END_REF].

From the second electrical equation (22b), one can write:

-F 0,1 [v q (t)] F 0,1 [i q (t)] F 0,1 [ω(t)]   Γ 1 Γ 2 Γ 3   = -F 1,1 [i q (t)] -F 0,1 [ω d (t)] . (24)
Define the vector Γ = Γ1 Γ2 Γ3 T . Equations ( 23) and ( 24) are rewritten together under the form:

∆P Γ = ∆Q, (25)
The matrices ∆P ∈ R 3×3 and ∆Q ∈ R 3×1 are given by:

∆P =   -F 0,1 [v d (t)] F 0,1 [i d (t)] 0 -F 0,2 [v d (t)] F 0,2 [i d (t)] 0 -F 0,1 [v q (t)] F 0,1 [i q (t)] F 0,3 [ω(t)]   , (26)
∆Q =   -F 1,1 [i d (t)] + F 0,1 [ω q (t)] -F 1,2 [i d (t)] + F 0,2 [ω q (t)] -F 1,1 [i q (t)] + F 1,1 [ω d (t)]   . ( 27
)
One obtains:

  Γ1 Γ2 Γ3   = ∆P -1 ∆Q. ( 28
)
Finally, the estimated parameters L, R and K are obtained from the relations: The experiments were realized using a stepper motor bench developed in LAGIS at École Centrale de Lille (see Fig. 2). The parameters of the motor with coils in series were identified using the offline procedure described in [START_REF] Delpoux | Parameter estimation of permanent magnet stepper motors without position or velocity sensors[END_REF], leading to L = 9mH, R = 3.01Ω, K = 0.27N.m.A -1 and J = 3.18.10 -4 kg.m 2 . The number of pole pairs is n p = 50. The input voltages v a and v b of each coil were delivered by two D/A outputs of the dSpace card and amplified by two linear amplifiers. The currents i a and i b are measured using Hall effect sensors with a precision of 1% of the nominal current I n = 3A. The power supply provided a maximum voltage v max = 30V and i max = 3A. The sampling period for this experiment is constant and equal to 10 -4 s for the control. The results were obtained using a classical velocity tracking control described in [START_REF] Bodson | High performance nonlinear feedback control of a permanent magnet stepper motor[END_REF]. Alternatively, a passivity plus flatness controller [START_REF] Sira-Ramírez | A Passivity plus Flatness Controller for Permanent Magnet Stepper Motor[END_REF] or sliding mode controller [START_REF] Corradini | A Quasi-Sliding Mode Observer-based Controller for PMSM Drives[END_REF] could have been applied. The reference trajectory was defined such that the parameters were identifiable. Indeed, the parameters are identifiable if the direct current is non-zero. The velocity must also be non-zero in order to identify the back-EMF constant. For this reason, the torque maximization given in [START_REF] Verl | Torque Maximization for Permanent Magnet Synchronous Motors[END_REF] was applied, such that at non-zero speed, the direct current was non-zero. The reference velocity was sinusoidal with ω * = r sin(ωt) + r 0 where r = 5rad.s -1 , ω = 5 • 2πrad.s -1 and r 0 = 20rad.s -1 was a bias.

L = 1 Γ1 , R = Γ2
The choice of the window length was set experimentally. Experience has shown that a window length T f = 0.2s gives good results. With a sampling period of 1.10 -4 s, it gives a window of 2000 points. Such a long window is not computable online. To solve this problem, the estimation was sampled at 10 -3 s, leading to a window length of 200 points. At the beginning of the experiment, the three parameters to be estimated are chosen arbitrarily: R = 5Ω, L = 0.03H and K = 0.4N.m.A -1 . As this system is stable by nature, the arbitrary parameters can be chosen far from the true parameters.

Fig. 3 shows the identification of the parameters R, L and K. The black line represents the instant τ where the estimation started. At t = τ + T f , with T f = 0.2s, the estimated parameters were applied to the control. The parameters R = 3.1Ω, L = 9.7mH and K = 0.28N.m.A -1 were obtained, as compared with L = 9mH, R = 3.01Ω and K = 0.27N.m.A -1 . To show the effects on the control, Fig. 4 represents the reference velocity (blue) and the measured one (red) and the velocity tracking. The black line represents the time instant when the parameter estimates were injected into the control. In this figure, the velocity tracking error is considerably decreased using the estimated parameters. Finally, the last figure, Fig. 5, shows the control input voltages applied to the motor. It is shown that the necessary voltages to be applied to the motor were considerably decreased, for a better velocity tracking.

Time [s] Time [s] Time [s] R [Ω] L [H] K [N m.A -1 ]
The results presented on the PMSM show an application of the parameter estimation using an algebraic approach. In this application, the electrical dynamics are known, and the equations are not disturbed.

Application 2: a magnetic bearing

Description of the experiment

Magnetic bearings can be used for machine tool spindles to produce circular and non-circular holes with high precision. Especially in high-speed applications, magnetic bearings have won importance. Moreover, because they have a contact free suspension, they provide advantages compared to conventional bearings, such as no lubrication and no friction. This improves reliability and performance. There is a real industrial demand for such processes, which allows non-circular motion in the range of 50 micro-meters. The required precision is very important: the path tracking error must be less than 1 micrometer on circular paths and 3 micrometers on non-circular ones with a rotation speed up to 1000 rpm. The magnetic shaft used in our laboratory consists of one electromagnetic radial bearing and two axial bearings. It is similar to the one presented in [START_REF] Eckhardt | High Precision Synchronous Tool Path Tracking with an AMB Machine Tool Spindle[END_REF]. It is an inherently unstable system, where the dynamics are strongly nonlinear. The modelling simplifications lead to perturbations, which have to be considered in parameter identification. We refer the reader to [START_REF] Eckhardt | High Precision Synchronous Tool Path Tracking with an AMB Machine Tool Spindle[END_REF][START_REF] Grochmal | Control of a self-bearing servomotor[END_REF][START_REF] Löwis | Flatness-based trajectory tracking control of a rotationg shaft[END_REF] concerning the control of magnetic shaft.

v d (t) [V ] v q (t) [V ]
The rotor is levitated via a three-phases electromagnetic radial bearing, arranged like three coupled "horseshoe magnets" around the rotor (Fig. 6). The three generated currents are three independent control inputs. The mathematical model of the bearing is based on the assumption of a rigid body, which leads to decoupled equations for forces . Therefore, the dynamic equations can be written as follows:

m Ÿ = F y , (29)
m Z = F z , (30)
where Y and Z represent the coordinates of the center of mass of the rotor in a Cartesian frame (with axes y and z), which is fixed in the space at a point being considered as the center of the device. F y and F z represent the resulting Fig. 6. Sketch of the three-phase radial bearing.

forces applied in the directions y and z, respectively. The rotor has a mass m. Gravity does not appear in these equations since the motions are in a plane perpendicular to gravity. The resulting forces in the plane (y -z) are given by the superposition of the forces generated by the magnets:

F y F z = sin α 1 sin α 2 sin α 3 cos α 1 cos α 2 cos α 3   F 1 F 2 F 3   . (31)
The angles that appear in [START_REF] Tiganj | An algebraic method for eye blink artifacts detection in single channel EEG recordings[END_REF] are presented in Fig. 6. Individually, the magnetic forces can be modelled by

F k = λ k i 2 k s - sin α k cos α k T Y b Z b 2 , k ∈ {1, 2, 3} (32)
where Y b and Z b are the positions in the bearing plane, s is the nominal air gap, and λ k are the parameters depending on the geometry and materials of the bearing. They will be estimated on-line.

Calculating control currents: the reference currents were obtained from the desired forces. In order to simplify the notations, it was assumed that the bearing was symmetric, i.e. α 1 = π, α 2 = -π 3 and α 3 = π 3 . In each of the models described above, we obtained a couple of independent forces for each bearing plane. Define F 1 such that:

F 1 = F 0 , if F z ≥ |Fy| √ 3 , F 0 - |Fy| √ 3 + F z , else. (33)
With F 0 ≥ 0 arbitrarily chosen, the two remaining forces were obtained from the model (31):

F 2 = F 1 + F y √ 3 + F z , F 3 = F 1 - F y √ 3 + F z .
The currents were calculated from the desired magnetic forces using the relation [START_REF] Trapero | An algebraic frequency estimator for a biased and noisy sinusoidal signal[END_REF]. The above equations reflect the dynamics of the unperturbed model. Model simplifications in ( 29)- [START_REF] Tian | Fast state estimation in linear time-varying systems: an algebraic approach[END_REF] and modelling errors (e.g. due to an incorrect relationship between the input currents i k , k = y, z and the corresponding forces F k , k = y, z) are assumed to have a similar effect as perturbations.

The rotor rotation is also a perturbation source with harmonic components. When the rotor moves along an ellipsoid trajectory, the positions in the directions y and z are sinusoidal functions. A significant error in the relation between the currents and the forces can also change sinusoidally. Therefore, the perturbations must be rejected in the λ i estimation algorithm (or must be estimated in order to be compensated for in the control).

The perturbed model can be written as:

m Ÿ = F y + p y (t), (34)
m Z = F z + p z (t), (35)
where p k (t), k = y, z represent the perturbations on each axis. Using equation ( 34), (35), [START_REF] Tiganj | An algebraic method for eye blink artifacts detection in single channel EEG recordings[END_REF] and [START_REF] Trapero | An algebraic frequency estimator for a biased and noisy sinusoidal signal[END_REF], relationships of the following forms are obtained:

Ÿ = 3 k=1 λ k u y,k + p y (t) m , (36)
Z = 3 k=1 λ k u z,k + p z (t) m , (37)
with u y,k = sin(α k )i 2 k m   s- sin α k cos α k T Y b Z b   2 ,
and

u z,k = cos(α k )i 2 k m   s- sin α k cos α k T Y b Z b   2 .
These two equations depend on the measured inputs and the accelerations in the plane. The parameters λ k are the parameters to be estimated from the measurements Y and Z despite the perturbations. The identification of magnetic bearing parameters is usually slow to be implemented and is often made off-line. In the next section, the expressions for the identification leading to an on-line, fast, and robust estimation of these parameters are developed.

Estimation of λ k parameters

The three unknown parameters λ 1 , λ 2 and λ 3 can be estimated using equation (37). In order to simplify the computations, it is assumed that the perturbations are constant over a short time interval. Equation ( 37) is an input/output relationship of the form of equation ( 1) with three inputs, where n = 2, m = 0. The choice of constant perturbation implies κ = 1. Using Theorem 1 for equation (37) with the three unknown parameters (i.e. p = 3) leads to:

  λ1 λ2 λ3   = -F b 1 -F b 2 -F b 3 -1   -F 2,1 [Z(t)] -F 2,2 [Z(t)] -F 2,3 [Z(t)]   , (38)
with:

F b * =   F 0,1 [u Z, * (t)] F 0,2 [u Z, * (t)] F 0,3 [u Z, * (t)]   ,
where, for any function f (t), F i,p [f (t)] are defined in (3). Define the vector: Λ = [ λ1 λ2 λ3 ] T . Equation (38) gives the expressions of the estimate of the parameters λ1 , λ2 and λ3 :

∆P 2 Λ = ∆Q 2 , (39)
with the matrices ∆P 2 ∈ R 3×3 and ∆Q 2 ∈ R 3×1 given by:

∆P 2 =   -F 0,1 [u Z,1 (t)] -F 0,1 [u Z,2 (t)] -F 0,1 [u Z,3 (t)] -F 0,2 [u Z,1 (t)] -F 0,2 [u Z,2 (t)] -F 0,2 [u Z,3 (t)] -F 0,3 [u Z,1 (t)] -F 0,3 [u Z,2 (t)] -F 0,3 [u Z,3 (t)]   , (40)
∆Q 2 =   -F 2,1 [Z(t)] -F 2,2 [Z(t)] -F 2,3 [Z(t)]   . (41)
One obtains:

  λ1 λ2 λ3   = ∆P -1 2 ∆Q 2 . (42)

Experimental results

The known parameters in this experiment are the rotor mass m = 6.7kg and the nominal air gap s = 5.10 -4 m. The control is realized as a cascade, with a current controller in the inner loop and a position controller in the outer loop. The inner loop can be characterized by a control based on the electrical model of the bearing coils. The outer loop is based on the rigid body mechanical model ( 34)-(35). The chosen control design is a flatness based trajectory tracking control, as described in [START_REF] Löwis | Flatness-based trajectory tracking control of a rotationg shaft[END_REF]. This control law is designed using an extended Luenberger observer to estimate and reject the perturbations. The reference trajectory is an elliptical one where y * = r Y cos(ωt) and z * = r Z sin(ωt) with r Y = 30.10 -6 m and r Z = 70.10 -6 m. The shaft is rotating with an angular velocity of about 3000 rpm, i.e. ω = 50 • 2πrad.s -1 . All currents are generated by three DC brush amplifiers that serve as three independent control inputs (Fig. 11). The system's sampling period is equal to 1.10 -4 s. The test bench is shown Fig. 7.

Since the dynamics of the magnetic bearing are faster than the ones of the PMSM, the window length has to be chosen shorter. Therefore, the window length was divided by 10 compared to the PMSM one. The window length was taken equal to 0.02s. With a sampling period of 1.10 -4 s, the window had 200 points, which can be implemented in real time. In order to reject the remaining harmonic perturbation with frequencies close to the rotational speed, the resulting numerator and denominator of each estimated parameter were filtered using a low-pass filter. The filter used was similar to the one presented in [START_REF] Trapero | An algebraic frequency estimator for a biased and noisy sinusoidal signal[END_REF]:

λi (t) = F (s)n(t) F (s)d(t) , (43)
where

F (s) = ω 2 n s 2 +2ζωn+ω 2 n
, with ζ = 0.707 and w n = 15rad/s.

Fig. 8 shows the experimental results of the identification of the parameters λi . As mentioned before, one does not have a precise knowledge of λ i . The parameters are arbitrarily set to 4.0.10 -6 (N m 2 /A 2 ). Again, the black line represents the instant τ where the estimation started. At t = τ + T f , with T f = 0.02s here, the arbitrary values are replaced by the estimated ones. One obtains the three parameters: λ1 = 2.53.10 -6 N m 2 /A In order to check the parameter estimation accuracy, Fig. 9 and 10 show the trajectory tracking before and after the parameter estimation along the y and z trajectories, respectively. A black line on the figures represents this delimitation. These figures give the reference positions (blue) and the measured ones (green), the position tracking errors and estimate of the perturbations. It can be seen on these figures that the parameter estimation does not have much as an effect on the tracking errors, although at low speed (i.e. y-trajectory) the error is more regular and the amplitude slightly lower. The most obvious effect is on the perturbation estimation. In fact, it is clear that the modelling is better since the amplitude of the perturbations decreases considerably when the estimated parameters are used. This observation is due to the use of an observer to estimate the perturbations. When the parameters are badly identified, the observer takes into consideration the modelling errors, hence a low tracking error. Nevertheless the currents furnished to reach this performance will be more important, as depicted in Fig. 11, where two zooms of the currents are plotted, between time t = 0.2s and 0.3s for the currents before identification and between t = 0.6s and 0.7s for the currents after identification. Finally, Fig. 12 and 13 give an idea of the shape of the hole before and after identification, where it can be seen the accuracy of the trajectory tracking is improved. One can see that the trajectory obtained with the estimated parameters presents a bias; nevertheless, the results are experimental, this bias may be due to several reasons. First, the information on the positions y and z are obtained by the use of eight position sensors. Each of them could be poorly calibrated and have a bias that would affect the estimation as well as the tracking. One other reason is that the control law used for these experiments is very basic. A more advanced control law could improve the tracking accuracy.

The results show that the given online estimator is able to identify parameters with very low amplitude compared to the signals and works in spite of perturbations. Moreover, the identification of three parameters simultaneously has been achieved.

Fig. 1 .

 1 Fig. 1. Estimation procedure.

4. 1 .

 1 Application 1: a PMSM 4.1.1. Description of the experiment PMSM are widely used in industry for position control, especially in manufacturing applications. PMSM are more robust than brushed DC motors and produce higher torque per volume. They are often controlled in openloop, although the potential loss of synchronism limits operation away from resonances and from high acceleration trajectories.

Fig. 2 .

 2 Fig. 2. PMSM test-bench.

Fig. 3 .

 3 Fig. 3. Estimation of the parameters R, L and K.

Fig. 4 .

 4 Fig. 4. Trajectory tracking evaluation of the motor velocity.

Fig. 5 .

 5 Fig. 5. Inputs voltages applied to the motor.

Fig. 7 .

 7 Fig. 7. Magnetic bearing test-bench.

Fig. 8 .

 8 Fig. 8. Experimental estimation of the parameters λ 1 , λ 2 and λ 3 [N m 2 /A 2 ].

Fig. 9 .

 9 Fig. 9. Trajectory tracking evaluation on the y axis.

Fig. 10 .

 10 Fig. 10. Trajectory tracking evaluation on the z axis.

i 1 (

 1 t), i 2 (t), i 3 (t) [A]

i 1 (

 1 t), i 2 (t), i 3 (t) [A]

i 1 i 2 i 3 Fig. 11 .

 311 Fig. 11. Control currents before identification (left), after identification (right).

  )[µm]

Fig. 12 .

 12 Fig. 12. Desired and measured position in the yz plane before identification.

  t. s in the operational domain translates into multiplication by -t in the time domain. Multiplication by s in the operational domain corresponds to derivation in the time domain. Applying the linear estimator (8) is not appropriate. Derivation amplifies the high frequency components and consequently, the noise contribution. A simple solution is to make the estimator proper. It is enough to multiply both sides of (8) by s -(κ+n+p) to eliminate the derivation terms and obtain a relationship in the function of integral operators:

	n	κ+n
	a i
	i=0	j=n-i

  2 , λ2 = 2.04.10 -6 N m 2 /A 2 and λ3 = 2.42.10 -6 N m 2 /A 2 .

	y(t) [µm]	-50 0 50		y * y
				0	0.2	0.4	0.6	0.8	1
						Time [s]
	y (t) [µm]	0 10		e y
	e	-10	0	0.2	0.4	0.6	0.8	1
						Time [s]
	py (t) [N ]		0 10		py
		-10	0	0.2	0.4	0.6	0.8	1
						Time [s]

This work was supported by EU Interreg IV A 2 Mers Seas Zeeen Cross-border Cooperation Programme under SYSIASS project 06-020. It was also supported by Nord-Pas de Calais Regional Council and FEDER through the Contrat de Projets Etat Region (CPER) 2007-2013. The authors would like to thank Laurentiu Hetel for his constructive comments on the article.

V. CONCLUSION

In this article, a procedure for on-line parameter estimation using an algebraic approach has been presented. The main contributions of this article are: (i) the generalization of an existing estimator for perturbed systems, assuming that the perturbations are polynomial on a short time interval; (ii) a method to solve implementation issues in order to be able to apply this estimator for online identification. The parameter identification is obtained from the inputs and measured outputs only. It does not need to differentiate any signals. Moreover, it leads to finite time estimation and it is possible to identify several parameters simultaneously.

The proposed estimator was applied experimentally for two different processes. The estimator has shown its performance on the identification of the electrical parameters of a PMSM. Then, the algorithm was applied to identify the parameters of a magnetic bearing. The results showed that the identification is performed on a strongly nonlinear system, whereas the dynamics are affected by perturbations. Moreover, their parameters have very small amplitude compared to the signals. These two applications show that the same algorithm can easily be applied to different processes and gives good results.

The proposed estimator is robust and also fast; the estimation error is small in spite of noise and perturbations. Both experiments have shown that the estimations were obtained in less than a second. Using the on-line estimation of the parameters, the trajectories are well tracked and the inputs amplitude is lower leading to energy saving. Finally, the comparison of both identifications shows the influence of the system dynamics on the sliding window. As an improvement, it would be interesting to simultaneously identify the perturbations.