Marion Gilson
email: [marion.gilson@cran.uhp-nancy.fr

Hugues Garnier
email: hugues.garnier]@cran.uhp-nancy.fr

Peter C Young
email: p.young@lancaster.ac.uk

Paul M J Van Den Hof

Refined Instrumental Variable methods for closed-loop system identification

Keywords: System identification, closed-loop identification, optimal instrumental variable

This paper describes optimal instrumental variable methods for identifying discretetime transfer function models when the system operates in closed-loop. Several noise models required for the design of optimal prefilters and instruments are analyzed and different approaches are developed according to whether the controller is known or not. Moreover, a new optimal refined instrumental variable technique is developed to handle the identification of a linear (ARX) predictor combined with an ARMA noise model in a closed-loop framework. The proposed refined instrumental variable algorithm achieves minimum variance estimation of the process model parameters. The performance of the proposed approaches is evaluated by Monte-Carlo analysis in comparison with other alternative closed-loop estimation methods.

INTRODUCTION

Feedback is present in a variety of practical situations due to safety and/or economic restrictions. In the last two decades, various attempts have been made to handle linear system identification in the presence of feedback. Indeed, closed-loop system identification leads to several difficulties due to the correlation between the disturbances and the control signal induced by the loop. Several methods have therefore been developed to cope with this problem either for discrete-time transfer function model identification (see e.g. [START_REF] Söderström | System identification[END_REF], [START_REF] Van Den Hof | Closed-loop issues in system identification[END_REF], [START_REF] Forssell | Efficiency of prediction error and instrumental variable methods for closed-loop identification[END_REF], [START_REF] Forssell | Closed-loop identification revisited[END_REF], [START_REF] Zheng | Application of BELS based methods in direct identification of linear systems from closed loop data[END_REF], [START_REF] Gevers | Identification for control: from the early achievements to the revival of experiment design[END_REF]) or for continuous-time TF model identification (see e.g. [START_REF] Gilson | Identification of Continuous-time Models from Sampled Data, chapter Instrumental variable methods for closed-loop continuous-time model identification[END_REF]). This paper focusses more specifically on instrumental variable (IV) techniques which present the major advantage of being able to consistently identify plant models in closedloop while relying on simple linear-like ("pseudo-linear regression") algorithms and not relying on linearity nor knowledge of the controller. For closed-loop identification, a basic IV estimator was first suggested by [START_REF] Young | An instrumental variable method for realtime identification of a noisy process[END_REF]; the topic was later discussed in more detail by [START_REF] Söderström | Instrumental variable methods for closed-loop systems[END_REF]. More recently a so-called "tailormade IV algorithm" was proposed [START_REF] Gilson | On the relation between a bias-eliminated least-squares (BELS) and an IV estimator in closed-loop identification[END_REF], where the closed-loop plant is parameterized using the (open-loop) plant parameters. Then, an optimal (minimal) variance result was developed in the closed-loop extended IV identification case, revealing consequences for the choice of weights, filters and instruments [START_REF] Gilson | Instrumental variable methods for closed-loop system identification[END_REF]. This paper aims at presenting several solutions according to the chosen model structure. Therefore, after a quick review of two available solutions (for ARX and ARARX models), a new optimal IV-based technique is presented which is based on the identification of a more realistic Box-Jenkins (BJ) model, where the plant and the noise models are not constrained to have common polynomials. The identification problem is rewritten to make use of a linear-in-the-parameters predictor next to an additional noise model identification required for determining the optimal prefilter and instrument. Moreover, two situations are studied depending on the controller knowledge. The paper is organized as follows. After the preliminaries, the lower bound of the covariance matrix is recalled in Section 3. Section 4 shows how the refined IV method can be used to provide consistent and efficient estimates to the closed-loop identification problem. The different algorithms are then presented in Section 5. Finally, in Section 6, the comparison between different methods is illustrated with the help of Monte Carlo simulation examples.

PROBLEM FORMULATION

Preliminaries.

Consider a stable, linear, Single Input Single Output, closed-loop system of the form shown in Figure 1. The data generating system is assumed to be given by the relations S :

y(t) = G 0 (q)u(t) + H 0 (q)e 0 (t) u(t) = r(t) -C c (q)y(t).
(1)

Cc(q) G0(q) H0(q) ❞ + - ❞ + + ❞ + + ✲ ❄ ✲ ✻ ✲ ✲ ✲ ✲ ❄ ❄ r1(t) r2(t) u(t) ξ(t) y(t) e0(t) Fig. 1. Closed-loop configuration
The process is denoted by G 0 (q) = B 0 (q -1 )/F 0 (q -1 ) with the numerator and denominator degree equals to n 0 , the controller is denoted by C c (q) and q -1 is the delay operator with q -i x(t) = x(t -i). u(t) describes the process input signal, y(t) the process output signal. For ease of notation we introduce an external signal r(t) = r 1 (t) + C c (q)r 2 (t).

(2) A coloured disturbance ξ 0 (t) = H 0 (q)e 0 (t) is assumed to affect the closed-loop, where e 0 (t) is a white noise, with zero mean and variance σ 2 e0 . The following general model structure is chosen to model the system (1) M : y(t) = G(q, ρ)u(t) + H(q, η)ε(t, θ),

(3) where the parameter vector is given as θ T = (ρ T η T ). The parameterized process model takes then the form,

G : G(q, ρ) = B(q -1 , ρ) A(q -1 , ρ) = b 1 q -1 + • • • + b n q -n 1 + a 1 q -1 + • • • + a n q -n , (4)
where n denotes the process model order and with the pair (A, B) assumed to be coprime. The process model parameters are stacked columnwise in the parameter vector

ρ = [a 1 • • • a n b 1 • • • b n ] T ∈ R 2n .
(5) The process model order n is assumed known or identified from the data and the parameterized noise model is assumed to be in the form of the following ARMA process,

H : H(q, η) = C(q -1 , η) D(q -1 , η) = 1 + c 1 q -1 + • • • + c m q -m 1 + d 1 q -1 + • • • + d m q -m
, (6) where the associated noise model parameters are stacked columnwise in the parameter vector,

η = [d 1 • • • d m c 1 • • • c m ] T ∈ R 2m .
(7) Note that this paper deals with IV-based methods which are known to give consistent plant model parameter estimates of G 0 irrespective of the structure of H 0 . Additionally, the controller C c (q) is given by

C c (q) = Q(q -1 ) P (q -1 ) = q 0 + q 1 q -1 + • • • + q nc q -nc p 0 + p 1 q -1 + • • • + p nc q -nc , (8)
with the pair (P, Q) assumed to be coprime. In the following, the closed-loop system is assumed to be asymptotically stable and r(t) is an external signal that is persistently exciting of sufficient high order. With these notations, the closed-loop system can be described as

y(t) = G 0 (q) 1 + C c (q)G 0 (q) r(t) + 1 1 + C c (q)G 0 (q) ξ o (t) u(t) = 1 1 + C c (q)G 0 (q) r(t) - C c (q) 1 + C c (q)G 0 (q) ξ o (t). (9)
In the following instrumental variable algorithms, use is made of the noise-free input/output signals deduced from (2) and denoted from hereon as

ů(t) = 1 1 + C c (q)G 0 (q) r(t), ẙ(t) = G 0 (q) 1 + C c (q)G 0 (q)
r(t).

(10) The noise-free regressor is then defined as follows φT

(t) = [-ẙ(t -1) • • • -ẙ(t -n) ů(t -1) • • • ů(t -n)]. (11)
Now consider the relationship between the process input and output signals in (1), y(t) = G 0 (q)u(t) + H 0 (q)e 0 (t). ( 12) If the plant G 0 is included into the chosen model set G (G 0 ∈ G), y(t) can be written as

y(t) = ϕ T (t)ρ 0 + v 0 (t),
(13) where ρ 0 denotes the true plant parameter vector,

ϕ T (t) = [-y(t -1) • • • -y(t -n) u(t -1) • • • u(t -n)] (14) and v 0 (t) = F 0 (q -1 )H 0 (q)e 0 (t).
The objective is to estimate the parameter vector from the collected data y(t), u(t) and r(t) with or without the knowledge of the controller.

Extended IV

The well-known extended-IV estimate is given by (see e.g. [START_REF] Söderström | Instrumental Variable Methods for System Identification[END_REF])

ρxiv (N ) = arg min ρ 1 N N t=1 L(q)ζ(t)L(q)ϕ T (t) ρ - 1 N N t=1 L(q)ζ(t)L(q)y(t) 2 W , (15)
where ζ(t) is the instrument vector, x 2 W = x T W x, with W a positive definite weighting matrix and L(q) a stable prefilter. By definition, when G 0 ∈ G, the extended-IV estimate provides a consistent estimate under the following two conditions 1

• ĒL(q)ζ(t)L(q)ϕ T (t) is full column rank, • ĒL(q)ζ(t)L(q)v 0 (t) = 0.

LOWER BOUND FOR AN IV METHOD

The choice of the instrumental variable vector ζ(t), the number of instruments n ζ , the weighting matrix W and the prefilter L(q) may have a considerable effect on the covariance matrix P xiv produced by the IV estimation algorithm. In the open-loop situation the lower bound of the covariance matrix for any unbiased identification method is given by the Cramer-Rao bound (see e.g. [START_REF] Söderström | Instrumental Variable Methods for System Identification[END_REF] and [START_REF] Ljung | System Identification : Theory for the User -Second Edition[END_REF]). The closed-loop situation has been investigated recently in [START_REF] Gilson | Instrumental variable methods for closed-loop system identification[END_REF], therefore only the main results to be used in the following are recalled here. It has been shown that a minimum value of the covariance matrix P xiv as a function of the design variables ζ(t), L(q) and W exists under the restriction that ζ(t) is a causal function of the external signal r(t) only. In that case

P xiv ≥ P opt xiv 1 The notation Ē[.] = lim N →∞ 1 N N t=1 E[.]
is adopted from the prediction error framework of [START_REF] Ljung | System Identification : Theory for the User -Second Edition[END_REF].

with

P opt xiv = σ 2 e0 [ Ēφ f (t)φ T f (t)] -1 , (16) φf (t) = L opt (q)φ(t), (17)
L opt (q) = 1 F 0 (q -1 )H 0 (q) , (18)
and where φ(t) is the noise-free part of ϕ(t) (see equation ( 11)). It has been shown that the minimum variance result can be achieved by the following optimal choice of design variables

W = I and n ζ = 2n, (19) L(q) = L opt (q) (20) ζ(t) = φ(t).
(21) Using equations ( 15) and ( 19)-( 21), the IV estimate using these optimal design variables is given by ρopt

(N ) = R-1 ζ f ϕ f (N ) Rζ f y f (N ) (22) with Rζ f ϕ f (N ) = 1 N N t=1 ζ f (t)ϕ T f (t), ( 23
) Rζ f y f (N ) = 1 N N t=1 ζ f (t)y f (t) (24)
and where the regressor ϕ f (t) = L opt (q)ϕ(t), the output y f (t) = L opt (q)y(t) and the instrument vector

ζ f (t) = L opt (q)ζ(t) are filtered by L opt (q) (18).
As a result, note that in the considered IV estimator (15), the optimal choice of instruments and prefilter is dependent on unknown system properties, i.e. the plant as well as the noise dynamics. Whereas dependency of plant dynamics could be taken care of by an iterative procedure where the instruments and prefilter are constructed on the basis of a previous process model ρi-1 in order to provide an improved process model ρi by applying (15); knowledge of the noise dynamics H 0 (q) is generally missing in an IV estimator like (15) as it is not particularly estimated. Therefore the next step in an optimal IV method should be to extend the estimator (15) with a procedure to estimate an appropriate noise model, to be used as a basis for constructing the optimal prefilter L opt (q) given in (18).

OPTIMAL IV IDENTIFICATION IN CLOSED-LOOP

Introduction

The optimal IV identification method is based on estimator (15). However, this latter one needs to be complemented with the estimation of a noise model. In this perspective, a general prediction error identification step is added to estimate a model for H 0 (q). This requires the choice of a particular parametrization for H(q, θ), possibly in relation to G(q, ρ). Two options have been used so far in the literature [START_REF] Gilson | Instrumental variable methods for closed-loop system identification[END_REF]:

• ARX structure: A(q -1 , ρ)y(t) = B(q -1 , ρ)u(t) + ε(t, ρ).
In this case the noise model H(q, ρ) = 1/A(q -1 , ρ) (25) is already available from the process model estimate, and no additional noise model estimate is required.

On the basis of the estimated process model G(q, ρ) the corresponding filter is given by L(q, ρ) = 1/[A(q -1 , ρ)H(q, ρ)] = 1 (26) ρ is estimated during the model identification step.

• ARARX structure:

A(q -1 , ρ)y(t) = B(q -1 , ρ)u(t) + 1 D(q -1 , η) ε(t, θ).
In this case the corresponding noise model H(q, η) = 1/A(q -1 , ρ)D(q -1 , η) (27) is not available from the process model ρ only as previously, but an additional noise model estimate is required. In [START_REF] Gilson | Instrumental variable methods for closed-loop system identification[END_REF], this is achieved by identifying D(q -1 , η) as an autoregressive model D(q -1 , η)w(t) = ε(t, η) with w(t) = A(q -1 , ρ)y(t) -B(q -1 , ρ)u(t), (28) by using a first process model estimate (ρ) and by applying a least square estimator

η = arg min η 1 N N t=1 ε(t, η) 2 .
The optimal filter that results from this identification procedure is therefore

L(q, η) = D(q -1 , η). ( 29
)
Note that these two methods rely on special structures of the estimated noise models, and therefore limit the possibility to reach consistent estimates of H 0 (q) in situations where these structures are not in accordance with the properties of the underlying systems. Therefore, in this paper, the options are extended to other more general model structures.

Extension to BJ and OE structure

The more general structure is obtained by choosing a Box Jenkins (BJ) model structure for identifying the noise dynamics, which takes the form

y(t) = B(q -1 , ρ) F (q -1 , ρ) u(t) + C(q -1 , η) D(q -1 , η) ε(t, ρ, η), (30)
and a natural way to extend the IV estimator (15) with an identification of the noise model η is to write

v(t) = C(q -1 , η) D(q -1 , η) ε(t, ρ, η) (31)
with v(t) = y(t) -B(q -1 , ρ)/F (q -1 , ρ)u(t) being available as a measured/reconstructed signal once IV estimator (15) has delivered a process model ρ. Estimation of η in the above equation is then undertaken by an ARMA estimation algorithm on the basis of v(t).

The optimal prefilter that results from this identification procedure is then given by

L(q, ρ, η) = D(q -1 , η)/[F (q -1 , ρ)C(q -1 , η)]. ( 32
)
When choosing an Output Error (OE) model structure for the noise dynamics, we arrive at

y(t) = B(q -1 , ρ) F (q -1 , ρ) u(t) + ε(t, ρ), (33)
and of course no additional estimation of the noise dynamics is required. The optimal prefilter however changes, and now becomes given by L(q, ρ) = 1/F (q -1 , ρ). ( 34)

THE ITERATIVE IV ALGORITHM

The outline of the optimal IV algorithm in a unified way for the 4 considered model structures, within the closedloop context is given below. Two versions are provided according to whether the controller is known or not. Moreover, the proposed algorithm is chosen to be iterative to refine the parameter estimates as it is achieved in the optimal refined IV estimation technique initially developed for open-loop system identification (see e.g. [START_REF] Young | Recursive Estimation and Time-Series Analysis[END_REF]).

Case 1 -cliv with known controller

Step 1. Initialisation: estimate a first model Apply a basic IV method

ρ0 = N t=1 ζ(t)ϕ T (t) -1 N t=1 ζ(t)y(t), (35)
where ϕ(t) is given by ( 14). Several IV methods may be chosen, as e.g. using the delayed version of the excitation signal r(t) as instruments. This yields B(q -1 , ρ0 ) and F (q -1 , ρ0 ). Denote the corresponding transfer function by G(q, ρ0 ) = B(q -1 , ρ0 )/F (q -1 , ρ0 ). Set the initial noise model estimates C(q -1 , η0 ) = D(q -1 , η0 ) = 1 and i = 1.

Step 2. Estimate by IV Generate the filtered instruments 2 according to the model structure used as

                      
L(q, θi-1 ) computed using either ( 26), ( 29), (32), or ( 34)

ŷ(t, ρi-1 ) = G(q, ρi-1 ) 1 + C c (q)G(q, ρi-1 ) r(t), û(t, ρi-1 ) = 1 1 + C c (q)G(q, ρi-1 ) r(t),
ζ f (t, θi-1 )=L(q, θi-1 ) -ŷ(t -1, ρi-1 ) . . . -ŷ(t -n, ρi-1 ) û(t -1, ρi-1 ) . . . û(t -n, ρi-1 )

ζ f (t, θi-1 ) can be seen as a filtered estimate of the noisefree part of the regressor vector ϕ(t) (14) based on estimates ŷ(t) and û(t) of the noise-free output and input to the plant, respectively. Determine the IV estimate using the prefilter and these instruments ρi =

N t=1 ζ f (t, θi-1 )ϕ T f (t, θi-1 ) -1 N t=1 ζ f (t, θi-1 )y f (t, θi-1 ) (36) ϕ f (t, θi-1 ) = L(q, θi-1 )ϕ(t) y f (t, θi-1 ) = L(q, θi-1 )y(t) (37)
This yields B(q -1 , ρi ) and F (q -1 , ρi ). Denote the corresponding transfer function by G(q, ρi ) = B(q -1 , ρi )/F (q -1 , ρi ).

Step 3. Obtain an optimal estimate of the noise model parameter vector η i based on the estimated noise sequence: Use one of the noise model identification scheme described in Section 4 to estimate ηi and the associated transfer function H(q, ηi ).

Step 4. For OE and BJ model strutures: repeat from step 2. Stop when F (q -1 , ρ), B(q -1 , ρ), H(q, η) and L(q -1 , θ) have converged.

2 i stands for the ith iteration

Step 5. Compute the estimated parametric error covariance matrix Pθ associated with the cliv parameter estimates, from

Pθ = σ2 ϕ T f (t, θ)ϕ f (t, θ) -1 , ( 38
)
where σ2 is the sample variance of the estimated residuals.

Then, according to the model structure used, the resulting algorithm will be referred to as cliv arx , cliv ararx , cliv bj or cliv oe .

Case 2 -cliv with unknown controller

When the controller is known, it is worthwhile to use this information into the identification procedure, to provide with more accurate results. In the previous algorithm, the controller is used with the open-loop system model to construct the instruments and the filter. However, when it is unknown, another solution may be used to build up the instrumental vector which satisfies the optimal conditions ( 19)-( 21). Indeed, the noise-free estimation of this instrumental vector can be achieved by using the two closed-loop transfers between r(t), u(t) and between r(t), y(t) instead of the open-loop one (between u(t) and y(t)). The second step consists then in identifying the two closed-loop transfers G yr (q, Θ yr ) and G ur (q, Θ ur ) using two basic IV methods as

Θyr = N t=1 ζ r (t)ϕ T yr (t) -1 N t=1 ζ r (t)y(t) (39) Θur = N t=1 ζ r (t)ϕ T ur (t) -1 N t=1 ζ r (t)u(t), (40)
where the instruments are a delayed version of the excitation signal and the regressors make use of the input/ouput signals. These closed-loop estimates are then used to compute the instruments as ŷ(t, Θyr ) = G yr (q, Θyr )r(t), û(t, Θur ) = G ur (q, Θur )r(t).

The estimation of ρ is then achieved using the same way as in (36), only the instrument vector computation is changed.

Comments

• Adaptive optimal prefiltering of both I/O data signals is an inherent part of the cliv estimation. • One of the advantages of the proposed algorithms is that it provides consistent plant estimates while still exploiting the pseudo-linear regression type of estimation. Indeed, the IV based pseudo-linear regression method recently suggested in [START_REF] Young | An instrumental variable approach to ARMA model identification and estimation[END_REF] can be used to estimate the ARMA process noise in the third step of the algorithms. • The cliv oe algorithm obtained when C(q -1 , η) = D(q -1 , η) = 1 has some similarities with the algorithm of Steiglitz and McBride adapted to the closedloop situation. However, the Steiglitz-McBride algorithm uses iterative least-squares rather than iterative optimal IV; as a result it is consistent only under restrictive conditions (see [START_REF] Stoica | The Steiglitz-McBride identification algorithm revisited-Convergence analysis and accuracy aspects[END_REF]) and therefore is less robust than cliv oe .

SIMULATION EXAMPLES

The numerical examples presented in this section are used to illustrate the performance of the proposed methods. The plant to be identified is described by equation ( 1), where

G 0 (q) = 0.0997q -1 -0.0902q -2 1 -1.8858q -1 + 0.9048q -2 , n = 2 C c (q) = 10.75 -9.25q -1 1 -q -1 , r (t
) is a deterministic sequence: realization of a pseudo random binary signal of maximal length, with the number of stages of the shift register set to 9 and the clock period set to 8; e 0 (t) is a white noise uncorrelated with r(t).

Example 1: white noise

Firstly, a white noise disturbance (H 0 (q) = 1) is considered in order to evaluate the performance cliv oe algorithm in the case S ∈ M. The plant parameters are estimated on the basis of closed-loop data of length N = 4088. A Monte-Carlo simulation of 100 runs is used for a signal-tonoise (SNR) ratio equal to 35dB. The proposed method is compared to:

• clivr : the first basic IV method developed to handle the closed-loop case and which uses the delayed version of the reference signal as instruments [START_REF] Söderström | Instrumental variable methods for closed-loop systems[END_REF]); • cliv arx : the optimal IV method with an ARX model structure making use of the controller knowledge; • pem: applied to the closed-loop data as described e.g.

in [START_REF] Forssell | Closed-loop identification revisited[END_REF] known to be theoretically efficient in the S ∈ M case; • cliv oe1 : making use of the controller knowledge;

• cliv oe2 : assuming the controller unknown.

The Monte Carlo simulation (MCS) results are presented in Table 1 where the mean and standard deviation of the estimated parameters are displayed. The average number of iterations (N iter ) for the pem and cliv oe algorithms are also given. It can be seen that all of the methods deliver accurate results, with smaller standard deviations for pem and for the proposed cliv oe type of methods. Indeed, these methods lead to better results thanks to the iterative estimation procedure, even though the number of iterations required for convergence is quite low. As expected, the clivr method provides the least accurate results since it is a simple basic (and not optimal) IV approach.

Example 2: colored noise

A second example is used to analyse the performance of the proposed methods in the case of a colored noise, with H 0 (q) = 1 + 0.5q -1 1 -0.85q -1 . As previously, the proposed cliv bj methods are compared to clivr, cliv ararx , pem algorithms. The plant parameters are estimated on the basis of closed-loop data of length N = 4088. A Monte Carlo simulation of 100 experiments is performed for SNR = 25dB. The mean and standard deviation of the estimated parameters for the 100 realizations are given in Table 2 along with the averaged number of iterations needed for the cliv bj methods. The Bode diagrams of the 100 models identified by the clivr, pem, cliv ararx and cliv bj algorithms are displayed in Figure 2. These results show that all of the optimal-IV based methods give efficient results whereas the classical clivr and the pem algorithms fail to give accurate estimates. Indeed, the approximate optimal IV type of algorithms (cliv ararx and cliv bj ) give estimates with smaller standard deviation errors compared to the clivr algorithm, thanks to the optimal choices of instruments and filter. Furthermore, the cliv bj algorithms yields results with smaller standard deviation than the cliv ararx algorithm thanks to a more accurate noise model estimation. Moreover, on the Bode diagrams, it can be noticed that the pem algorithm is not able to converge to the global minimum at each run and therefore leads to erroneous results. It can also be noted that although the cliv bj2 algorithm uses less information to identify the model (the controller is supposed to be unknown), the corresponding results remain really accurate. Therefore this method which aims at identifying a consistent BJ model without the knowledge of the controller should be very interesting in many practical situations.

CONCLUSION

This paper has considered the identification of several transfer function model structures within a closed-loop environment, using the instrumental variable technique modified to solve the closed-loop situation. The general Box-Jenkins model structure identification has been handled by making use of a linear-in-the-parameters predictor next to an additional noise model identification required for determining the optimal filter and the instruments. Two approaches have then been suggested according to whether the controller is known or not. It has been shown that a minimal value of the associated parametric error covariance matrix can be achieved by an appropriate choice of instruments and prefilters. 0.0997 ± 0.7e-3 -0.0903 ± 0.7e-3 -1.8856 ± 3.6e-3 0.9048 ± 3.2e-3 5.88 cliv bj2 0.0997 ± 0.6e-3 -0.0903 ± 0.7e-3 -1.8860 ± 3.7e-3 0.9050 ± 3.4e-3 5

Table 2. Mean and standard deviation of the 100 estimated models, colored noise

Fig. 2 .

 2 Fig.2. Estimated Bode diagrams (gain and phase (degree)) of the plant model G(q, η) over the 100 MCS, colored noise

Table 1 .

 1 The estimated Box-Jenkins model has the advantage of not constraining the plant and the noise models to have common polynomials. Mean and standard deviation of the 100 estimated models, white noise

	parameters	b1	b2	â1	â2	N iter
	true values	0.0997	-0.0902	-1.8838	0.9048
	clivr	0.0997 ± 0.3e-3	-0.0898 ± 3.8e-3	-1.8821 ± 35e-3	0.9014 ± 32.4e-3
	clivarx	0.0997 ± 0.3e-3	-0.0900 ± 1.1e-3	-1.8772 ± 9e-3	0.8977 ± 8.5e-3
	pem	0.0996 ± 0.05e-3	-0.0901 ± 0.06e-3	-1.8858 ± 0.12e-3	-0.9048 ± 0.10e-3	4.14
	cliv oe1	0.0997 ± 0.05e-3	-0.0902 ± 0.06e-3	-1.8858 ± 0.10e-3	0.9048 ± 0.09e-3	3.89
	cliv oe2	0.0997 ± 0.05e-3	-0.0902 ± 0.06e-3	-1.8858 ± 0.12e-3	-0.9048 ± 0.10e-3	3.53
	parameters	b1	b2	â1	â2	N iter
	true values	0.0997	-0.0902	-1.8838	0.9048
	clivr	0.0992 ± 0.5e-3	-0.0900 ± 4.9e-3	-1.8834 ± 44.3e-3	0.9025 ± 41.1e-3
	clivararx	0.0998 ± 0.5e-3	-0.0898 ± 2.4e-3	-1.8823 ± 21.1e-3	0.9014 ± 19.6e-3
	pem	0.0793 ± 64.8e-3	-0.0715 ± 64e-3	-1.8993 ± 34.7e-3	0.9181 ± 33.8e-3	4.22
	cliv bj1


Emmanuel Navarro
email: navarro@irit.fr

Franck Sajous
email: sajous@univ-tlse2.fr

Bruno Gaume
email: gaume@univ-tlse2.fr

Laurent Prévot
email: laurent.prevot@lpl-aix.fr

Hsieh Shukai
email: shukai@gmail.com

Kuo Tzu-Yi
email: tzuyikuo@ntu.edu.tw

Pierre Magistry
email: pmagistry@gmail.com

Huang Chu-Ren
email: churenhuang@gmail.com

Wiktionary and NLP: Improving synonymy networks

Wiktionary, a satellite of the Wikipedia initiative, can be seen as a potential resource for Natural Language Processing. It requires however to be processed before being used efficiently as an NLP resource. After describing the relevant aspects of Wiktionary for our purposes, we focus on its structural properties. Then, we describe how we extracted synonymy networks from this resource. We provide an in-depth study of these synonymy networks and compare them to those extracted from traditional resources. Finally, we describe two methods for semiautomatically improving this network by adding missing relations: (i) using a kind of semantic proximity measure; (ii) using translation relations of Wiktionary itself.

Introduction

Reliable and comprehensive lexical resources constitute a crucial prerequisite for various NLP tasks. However their building cost keeps them rare. In this context, the success of the Princeton Word-Net (PWN) [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF] can be explained by the quality of the resource but also by the lack of serious competitors. Widening this observation to more languages only makes this observation more acute. In spite of various initiatives, costs make resource development extremely slow or/and result in non freely accessible resources. Collaborative resources might bring an attractive solution to this difficult situation. Among them Wiktionary seems to be the perfect resource for building computational mono-lingual and multi-lingual lexica. This paper focuses therefore on Wiktionary, how to improve it, and on its exploitation for creating resources.

In next section, we present some relevant information about Wiktionary. Section 3 presents the lexical graphs we are using and the way we build them. Then we pay some attention to evaluation ( §4) before exploring some tracks of improvement suggested by Wiktionary structure itself.

Wiktionary

As previously said, NLP suffers from a lack of lexical resources, be it due to the low-quality or non-existence of such resources, or to copyrightsrelated problems. As an example, we consider French language resources. [START_REF] Jacquin | French EuroWordNet Lexical Database Improvements[END_REF] highlighted the limitations and inconsistencies from the French EuroWordnet. Later, [START_REF] Sagot | Building a Free French Wordnet from Multilingual Resources[END_REF] explained how they needed to recourse to PWN, BalkaNet [START_REF] Tufis | Balkanet design and development of a multilingual balkan wordnet[END_REF] and other resources (notably Wikipedia) to build WOLF, a free French WordNet that is promising but still a very preliminary resource. Some languages are straight-off purely under-resourced.

The Web as Corpus initiative arose [START_REF] Kilgarriff | Introduction to the special issue on the web as corpus[END_REF] as an attempt to design tools and methodologies to use the web for overcoming data sparseness [START_REF] Keller | Using the web to overcome data sparseness[END_REF]. Nevertheless, this initiative raised non-trivial technical problems described in [START_REF] Baroni | Cleaneval: a Competition for Cleaning Web Pages[END_REF]. Moreover, the web is not structured enough to easily and massively extract semantic relations.

In this context, Wiktionary could appear to be a paradisiac playground for creating various lexi-cal resources. We describe below the Wiktionary resource and we explain the restrictions and problems we are facing when trying to exploit it. This description may complete few earlier ones, for example Zesch et al. (2008a).

Collaborative editing

Wiktionary, the lexical companion to Wikipedia, is a collaborative project to produce a free-content multilingual dictionary.1 As the other Wikipedia's satellite projects, the resource is not experts-led, rather filled by any kind of users. The might-be inaccuracy of the resulting resource has lengthily been discussed and we will not debate it: see [START_REF] Giles | Internet encyclopaedias go head to head[END_REF] and Britannica ( 2006) for an illustration of the controversy. Nevertheless, we think that Wiktionary should be less subject (so far) than Wikipedia to voluntary misleading content (be it for ideological, commercial reasons, or alike).

Articles content

As one may expect, a Wiktionary article2 may (not systematically) give information on a word's part of speech, etymology, definitions, examples, pronunciation, translations, synonyms/antonyms, hypernyms/hyponyms, etc.

Multilingual aspects

Wiktionary's multilingual organisation may be surprising and not always meet one's expectations or intuitions. Wiktionaries exist in 172 languages, but we can read on the English language main page, "1,248,097 entries with English definitions from over 295 languages". Indeed, a given wiktionary describes the words in its own language but also foreign words. For example, the English article moral includes the word in English (adjective and noun) and Spanish (adjective and noun) but not in French. Another example, boucher, which does not exist in English, is an article of the English wiktionary, dedicated to the French noun (a butcher) and French verb (to cork up).

A given wiktionary's 'in other languages' left menu's links, point to articles in other wiktionaries describing the word in the current language. For example, the Français link in the dictionary article of the English wiktionary points to an article in the French one, describing the English word dictionary.

Layouts

In the following paragraph, we outline wiktionary's general structure. We only consider words in the wiktionary's own language.

An entry consists of a graphical form and a corresponding article that is divided into the following, possibly embedded, sections:

• etymology sections separate homonyms when relevant;

• among an etymology section, different parts of speech may occur;

• definitions and examples belong to a part of speech section and may be subdivided into subsenses;

• translations, synonyms/antonyms and hypernyms/hyponyms are linked to a given part of speech, with or without subsenses distinctions. In figure 1 is depicted an article's layout example.

Figure 1: Layout of boot article (shortened) About subsenses, they are identified with an index when first introduced but they may appear as a plain text semantic feature (without index) when used in relations (translations, synonyms, etc.). It is therefore impossible to associate the relations arguments to subsenses. Secondly, subsense index appears only in the current word (the source of the relation) and not in the target word's article it is linked to (see orange French N. and Adj., Jan. 10, 20083 ).

A more serious issue appears when relations are shared by several parts of speech sections. In Ital-ian, both synonyms and translations parts are common to all words categories (see for example cardinale N. and Adj., Apr. 26, 2009 4 ).

Technical issues

As Wikipedia and the other Wikimedia Foundation's projects, the Wiktionary's content management system relies on the MediaWiki software and on the wikitext. As stated in Wikipedia's MetaWiki article, "no formal syntax has been defined" for the MediaWiki and consequently it is not possible to write a 100% reliable parser.

Unlike Wikipedia, no HTML dump is available and one has to parse the Wikicode. Wikicode is difficult to handle since wiki templates require handwritten rules that need to be regularly updated. Another difficulty is the language-specific encoding of the information. Just to mention one, the target language of a translation link is identified by a 2 or 3 letters ISO-639 code for most languages. However in the Polish wiktionary the complete name of the language name (angielski, francuski, . . . ) is used.

Parsing and modeling

The (non-exhaustive) aforementioned list of difficulties (see §2.2.2 and §2.3) leads to the following consequences:

• Writing a parser for a given wiktionary is possible only after an in-depth observation of its source. Even an intensive work will not prevent all errors as long as (i) no syntax-checking is made when editing an article and (ii) flexibility with the "tacitly agreed" layout conventions is preserved. Better, flexibility is presented as a characteristic of the framework: "[. . . ] it is not a set of rigid rules. You may experiment with deviations, but other editors may find those deviations unacceptable, and revert those changes. They have just as much right to do that as you have to make them.5 " Moreover, a parser has to be updated every new dump, as templates, layout conventions (and so on) may change.

• Writing parsers for different languages is not a simple adjustment, rather a complete overhaul.

• When extracting a network of semantic relations from a given wiktionary, some choices are more driven by the wiktionary inner format than scientific modelling choices. An illustration fol-lows in §3.2. When merging information extracted from several languages, the homogenisation of the data structure often leads to the choice of the poorest one, resulting in a loss of information.

The bigger the better?

Taking advantage of colleagues mastering various languages, we studied the wiktionary of the following languages: French, English, German, Polish and Mandarin Chinese. A first remark concerns the size of the resource. The official number of declared articles in a given wiktionary includes a great number of meta-articles which are not word entries As of April 2009, the French wiktionary reaches the first rank6 , before the English one. This can be explained by the automated import of public-domain dictionaries articles (Littré 1863 and Dictionnaire de l 'Académie Française 1932-1935). Table 1 shows the ratio between the total number of articles and the "relevant" ones (numbers based on year 2008 snapshots). By "relevant", we mean an article about a word in the wiktionary's own language (e.g. not an article about a French word in the English Wiktionary). Among the "relevant" articles, some are empty and some do not contain any translation nor synonym link. Therefore, before deciding to use Wiktionary, it is necessary to compare the amount of extracted information contribution and the amount of work required to obtain it .

Study of synonymy networks

In this section, we study synonymy networks built from different resources. First, we introduce some general properties of lexical networks ( §3.1). Then we explain how we build Wiktionary's synonymy network and how we analyse its properties. In §3.3, we show how we build similar graphs from traditional resources for evaluation purposes.

Structure of lexical networks

In the following sections, a graph G = (V, E) is defined by a set V of n vertices and a set E ⊂ V 2 of m edges. In this paper, V is a set of words and E is defined by a relation E

R -→ E : (w 1 , w 2 ) ∈ E if and only if w 1 R → w 2 .
Most of lexical networks, as networks extracted from real world, are small worlds (SW) networks. Comparing structural characteristics of wiktionary-based lexical networks to some standard resource should be done according to wellknown properties of SW networks [START_REF] Watts | Collective dynamics of small-world networks[END_REF][START_REF] Barabasi | Power-Law Distribution of the World Wide Web[END_REF][START_REF] Newman | The structure and function of complex networks[END_REF][START_REF] Gaume | Toward a cognitive organization for electronic dictionaries, the case for semantic proxemy[END_REF]. These properties are:

• Edge sparsity: SW are sparse in edges

m = O(n) or m = O(n log(n))
• Short paths: in SW, the average path length (L)7 is short. Generally there is at least one short path between any two nodes.

• High clustering: in SW, the clustering coefficient (C) that expresses the probability that two distinct nodes adjacent to a given third one are adjacent, is an order of magnitude higher than for Erdos-Renyi (random) graphs: C SW C random ; this indicates that the graph is locally dense, although it is globally sparse.

• Heavy-tailed degree distribution: the distribution of the vertices incidence degrees follows a power law in a SW graph. The probability P (k) that a given node has k neighbours decreases as a power law, P (k) ≈ k a (a being a constant characteristic of the graph). Random graphs conforms to a Poisson Law.

Wiktionary's network Graph extraction

Considering what said in §2.2.2 and §2.4, we made the following choices:8

• Vertices: a vertex is built for each entry's part of speech.

• Parts of speech: when modeling the links from X (X having for part of speech P os X ) to one of its synonyms Y , we assume that P os Y = P os X , thus building vertex P os Y .Y.

• Subsenses: subsenses are flattened. First, the subsenses are not always mentioned in the synonyms section. Second, if we take into account the subsenses, they only appear in the source of the relation. For example, considering in figure 1 the relation boot syn --→ kick (both nouns), and given the 10 subsenses for boot and the 5 ones for kick, we should build 15 vertices. And we should then add all the links between the mentioned boot's subsenses and the 5 kick's existing subsenses. This would lead to a high number of edges, but the graph would not be closer to the reality. The way subsenses appear in Wiktionary are unpredictable. "Subsenses" correspond sometimes to homonyms or clear-cut senses of polysemous words, but can also correspond to facets, word usage or regular polysemy. Moreover, some entries have no subsenses distinction whereas it would be worthy. More globally, the relevance of discrete word senses has been seriously questioned, see [START_REF] Victorri | La polysémie, construction dynamique du sens[END_REF] or [START_REF] Kilgarriff | I don't believe in word senses[END_REF] for very convincing discussions. Two more practical reasons led us to this choice. We want our method to be reproducible for other languages and some wiktionaries do not include subsenses. At last, some gold standard resources (eg. Dicosyn) have their subsenses flattened too and we want to compare the resources against each other.

• Edges: wiktionary's synonymy links are oriented but we made the graph symmetric. For example, boot does not appear in kick's synonyms. Some words even appear as synonyms without being an entry of Wiktionary. From the boot example (figure 1), we extract vertices {N.boot, V.boot}, build {N.buskin, N.kick, V.kick} and we add the following (symmetrized) edges: N.boot↔N.buskin, N.boot↔N.kick and V.boot↔V.kick.

Graph properties By observing the table 2, we can see that the graphs of synonyms extracted from Wiktionary are all typical small worlds. Indeed their l lcc remains short, their C lcc is always greater or equal than 0.2 and their distribution curves of the vertices incidence degree is very close to a power law (a least-square method gives always exponent a lcc ≈ -2.35 with a confidence r 2 lcc always greater than 0.89). It can also be seen that the average incidence k lcc ranges from 2.32 to 3.32. 9 It means that no matter which language 9 It is noteworthy that the mean incidence of vertices is almost always the same (close to 2.8) no matter the graph size is. If we assume that all wiktionary's graphs grow in a similar way but at different speed rates (after all it is the same framework), graphs (at least their statistical properties) from different languages can be seen as snapshots of the same graph at different times. This would mean that the number of graphs edges tends to grow proportionally with the number of vertices. This fits with the dynamic properties of small worlds [START_REF] Steyvers | The largescale structure of semantic networks: Statistical analyses and a model of semantic growth[END_REF]. It means that for a wiktionary system, even with many contributions, graph density is likely to remain constant and we will see that in comparison to traditional lexical resources this density is quite low. [START_REF] Newman | The structure and function of complex networks[END_REF][START_REF] Gaume | Toward a cognitive organization for electronic dictionaries, the case for semantic proxemy[END_REF].

Building synonymy networks from

known standards WordNet There are many possible ways for building lexical networks from PWN. We tried several methods but only two of them are worth to be mentioned here. The graphs we built have words as vertices, not synsets or senses. A first straightforward method (method A) consists in adding an edge between two vertices only if the corresponding words appear as elements of the same synset. This method produced many disconnected graphs of various sizes. Both the computational method we planned to use and our intuitions about such graphs were pointing towards a bigger graph that would cover most of the lexical network.

We therefore decided to exploit the hypernymy relation. Traditional dictionaries indeed propose hypernyms when one look for synonyms of very specific terms, making hypernymy the closest relation to synonymy at least from a lexicographic viewpoint. However, adding all the hypernymy relations resulted in a network extremely dense in edges with some vertices having a high number of neighbours. This was due to the tree-like organisation of WordNet that gives a very special importance to higher nodes of the tree.

In the end we retained method B that consists in adding edges in following cases:

• if two words belong to the same synset;

• if a word only appears in a synset that is a leaf of the tree and contains only this word, then create edges linking to words included in the hypernym(s) synset.

We would like to study the evolution through time of wiktionaries, however this is outside the scope of this paper.

Therefore when a vertice w do not get any neighbour according to method A, method B adds edges linking w to words included in the hypernym(s) synset of the synset {w}. We only added hypernyms for the leaves of the tree in order to keep our relations close to the synonymy idea. This idea has already been exploited for some WordNet-based semantic distances calculation taking into account the depth of the relation in the tree [START_REF] Leacock | Combining local context and wordnet similarity for word sense identification[END_REF].

Dicosyn graphs Dicosyn is a compilation of synonym relations extracted from seven dictionaries (Bailly, Benac, Du Chazaud, Guizot, Lafaye, Larousse and Robert):10 there is an edge r → s if and only if r and s have the same syntactic category and at least one dictionary proposes s being a synonym in the dictionary entry r. Then, each of the three graphs (Nouns, Verbs, Adjectives) obtained is made symmetric (dicosyn-fr-N, dicosynfr-V and dicosyn-fr-A).

Properties of the graphs extracted Table 3 sums-up the structural properties of the synonyms networks built from standard resources.

We can see that all the synonymy graphs extracted from PWN or Dicosyn are SW graphs. Indeed their l lcc remains short, their C lcc is always greater or equal than 0.35 and their distribution curves of the vertices incidence degree is very close to a power law (a least-square method gives always exponent a lcc near of -2.30 with a confidence r 2 lcc always greater than 0.85). It can also be observed that no matter the part of speech, the average incidence of Dicosyn-based graphs is always lower than WordNet ones. • The average number of synonyms for an entry of a Wiktionary-based resource is smaller than those of standard resources. For example, common synonyms such as to act/to play appear in PWN and not in Wiktionary. Nevertheless, some other appear (rightly) in Wiktionary: to reduce/to decrease, to cook/to microwave.

• The clustering rate of Wiktionary-based graphs is always smaller than those of standard resources. This is particularly the case for English. However, this specificity might be due to differences between the resources themselves (Dicosyn vs. PWN) rather than structural differences at the linguistic level. Evaluation of synonymy In order to evaluate the quality of extracted synonymy graphs from Wiktionary, we use recall and precision measure. The objects we compare are not simple sets but graphs (G = (V ; E)), thus we should compare separately set of vertices (V ) and set of edges (E). Vertices are words and edges are synonymy links. Vertices evaluation leads to measure the resource First of all, the global picture (table 4) shows clearly that the lexical coverage is rather poor. A lot of words included in standard resources are not included yet in the corresponding wiktionary resources. Overall the lexical coverage is always lower than 50%. This has to be kept in mind while looking at the evaluation of relations shown in table 5. To compute the relations evaluation, each resource has been first restricted to the links between words being present in each resource.

About PWN, since every link added with method A will also be added with method B, the precision of Wiktionary-based graphs synonyms links will be always lower for "method A graphs" than for "method B graphs". Precision is rather good while recall is very low. That means that a lot of synonymy links of the standard resources are missing within Wiktionary. As for Dicosyn, the picture is similar with even better precision but very low recall.

Exploiting Wiktionary for improving Wiktionary

As seen in section 4, Wiktionary-based resources are very incomplete with regard to synonymy. We propose two tasks for adding some of these links: Task 1: Adding synonyms to Wiktionary by taking into account its Small World characteristics for proposing new synonyms. Task 2: Adding synonyms to Wiktionary by taking into account the translation relations. We evaluate these two tasks against the benchmarks presented in section 3.2.

Improving synonymy in Wiktionary by

exploiting its small world structure We propose here to enrich synonymy links of Wiktionary by taking into account that lexical networks have a high clustering coefficient. Our hypothesis is that missing links in Wiktionary should be within clusters.

A high clustering coefficient means that two words which are connected to a third one are likely to be connected together. In other words neighbours of my neighbours should also be in my neighbourhood. We propose to reverse this property to the following hypothesis: "neighbour of my neighbours which are not in my neighbourhood should be a good neighbour candidate". Thus the first method we test consist simply in connecting every vertex to neighbours of its neighbours. One can repeat this operation until the expected number of edges is obtained. 11Secondly we used the PROX approach proposed by [START_REF] Gaume | Semantic associations and confluences in paradigmatic networks[END_REF]. It is a stochastic method designed for studying "Hierarchical Small Worlds". Briefly put, for a given vertex u, one computes for all other vertices v the probability that a randomly wandering particle starting from u stands in v after a fixed number of steps. Let P (u, v) be this value. We propose to connect u to the k first vertices ranked in descending order with respect of P (u, v). We always choose k proportionally to the original degree of u (number of neighbours of u).

For a small number of steps (3 in our case) random wanderings tend to be trapped into local cluster structures. So a vertex v with a high P (u, v) is likely to belong to the same cluster as u, which means that a link u↔v might be relevant.

Figure 2 shows precision, recall and f-score evolution for French verbs graph when edges are added using "neighourhood" method (neigh), and using "Prox" method. Dashed line correspond to the value theoretically obtained by choosing edges at random. First, both methods are clearly more efficient than a random addition, which is not surprising but it seems to confirm our hypothesis that missing edges are within clusters. Adding sharply neighbours of neighbours seems to be as good as adding edges ranked by Prox, anyway the rank provided by Prox permits to add a given number of edges. This ranking can also be useful to order potential links if one think about a user validation system. Synonyms added by Prox and absent from gold standards are not necessarily false. For example Prox proposes a relevant link absolve/forgive, not included in PWN. Moreover, many false positive are still interesting to consider for improving the resource. For example, Prox adds relations such as hypernyms (to uncover/to peel) or inter-domain 'synonyms' (to skin/to peel). This is due to high clustering (see §3.1) and to the fact that clusters in synonymy networks correlates with language concepts [START_REF] Gaume | Toward a cognitive organization for electronic dictionaries, the case for semantic proxemy[END_REF][START_REF] Duvignau | Between words and world: Verbal "metaphor" as semantic or pragmatic approximation[END_REF][START_REF] Gaume | Semantic associations and confluences in paradigmatic networks[END_REF][START_REF] Fellbaum | La représentation des verbes dans le réseau sémantique Wordnet[END_REF].

Finally note that results are similar for other parts of speech and other languages.

Using Wiktionary's translation links to

improve its synonymy network Assuming that two words sharing many translations in different languages are likely to be synonymous, we propose to use Wiktionary's translation links to enhance the synonymy network of a given language.

In order to rank links to be potentially added, we use a simple Jaccard measure: let T w be the set of a word w's translations, then for every couple of words (w, w ) we have:

Jaccard(w, w ) = |T w ∩ T w | |T w ∪ T w |
We compute this measure for every possible pair of words and then, starting from Wiktionary's synonymy graph, we incrementally add links according to their Jaccard rank.

We notice first that most of synonymy links added by this method were not initially included in Wiktionary's synonymy network. For example, regarding English verbs, 95% of 2000 best ranked proposed links are new. Hence this method may be efficient to improve graph density. However one can wonder about the quality of the new added links, so we discuss precision in the next paragraph.

In figure 3 is depicted the evolution of precision, recall and F-score for French verbs in the enlarged graph in regard of the total number of edges. We use Dicosyn graph as a gold standard. The dashed line corresponds to theoretical scores one can expect by adding randomly chosen links.

First we notice that both precision and recall are significantly higher than we can expect from random addition. This confirms that words sharing the same translations are good synonym candidates. Added links seem to be particularly relevant at the beginning for higher Jaccard scores. From the first dot to the second one we add about 1000 edges (whereas the original graph contains 1792 edges) and the precision only decreases from 0.71 to 0.69.

The methods we proposed in this section are quite simple and there is room for improvement. First, both methods can be combined in order to improve the resource using translation links and then using clusters structure. One can also think to the corollary task that would consists in adding translation links between two languages using synonymy links of others languages. This paper gave us the opportunity to share some Wiktionary experience related lexical resources building. We presented in addition two approaches for improving these resources and their evaluation.

The first approach relies on the small world structure of synonymy networks. We postulated that many missing links in Wiktionary should be added among members of the same cluster. The second approach assumes that two words sharing many translations in different languages are likely to be synonymous. The comparison with traditional resources shows that our hypotheses are confirmed. We now plan to combine both approaches.

The work presented in this paper combines a NLP contribution involving data extraction and rough processing of the data and a mathematical contribution concerning graph-like resource. In our viewpoint the second aspect of our work is therefore complementary of other NLP contributions, like (Zesch et al., 2008b), involving more sophisticated NLP processing of the resource. Support for collaborative editing Our results should be useful for setting up a more efficient framework for Wiktionary collaborative editing. We should be able to always propose a set of synonymy relations that are likely to be. For example, when a contributor creates or edits an article, he may think about adding very few links but might not bother providing an exhaustive list of synonyms. Our tool can propose a list of potential synonyms, ordered by relevancy. Each item of this list would only need to be validated (or not). Diachronic study An interesting topic for future work is a "diachronic" study of the resource. It is possible to access Wiktionary at several stages, this can be used for studying how such resources evolve. Grounded on this kind of study, one may predict the evolution of newer wiktionaries and foresee contributors' NLP needs. We would like to set up a framework for everyone to test out new methodologies for enriching and using Wiktionary resources. Such observatory, would allow to follow not only the evolution of Wiktionary but also of Wiktionary-grounded resources, that will only improve thanks to steady collaborative development. Invariants and variabality Wiktionary as a massively mutiligual synonymy networks is an extremely promising resource for studying the (in)variability of semantic pairings such as house/family, child/fruit, feel/know... [START_REF] Sweetser | From etymology to pragmatics[END_REF][START_REF] Gaume | Semantic associations and confluences in paradigmatic networks[END_REF]. A systematic study within the semantic approximation framework presented in the paper on Wiktionary data will be carried on in the future.

  Wiktionary vs. Dicosyn Precision Recall Nouns 10393/18017 = 0.58 10393/29372 = 0.35 Adj. 3076/5411 = 0.57 3076/9452 = 0.33 Verbs 2966/3897 = 0.76 2966/9147 = 0.32

  French wiktionary vs. Dicosyn Precision Recall Nouns 3510/5075 = 0.69 3510/44501 = 0.08 Adj. 1300/1677 = 0.78 1300/17404 = 0.07 Verbs 899/1267 = 0.71 899/23968 = 0.04

Figure 2 :

 2 Figure 2: Precision, recall and F-score of French verbs graph enlarged using only existing synonymy links

Figure 3 :

 3 Figure 3: Precision, recall and F-score of French verbs graph enlarged using translation links 6 Conclusion and future work

Table 1 :

 1 Ratio of "relevant" articles in wiktionaries

		Total Meta * Other * *	Relevant
	fr	728,266 25,244	369,948	337,074	46%
	en 905,963 46,202	667,430	192,331	21%
	de	88,912	7,235	49,672	32,005	36%
	pl 110,369	4,975	95,241	10,153	9%
	zh 131,752	8,195	112,520	1,037 0.7%

* templates definitions, help pages, user talks, etc. * * other languages, redirection links, etc.

Table 2 :

 2 Wiktionary synonymy graphs properties or part of speech, m = O(n) as for most of SW graphs

  The lexical coverage of Wiktionary-based synonyms graphs is always quantitatively lower than those of standard resources although this may change. For example, to horn (in PWN), absent from Wiktionary in 2008, appeared in 2009. At last, Wiktionary is more inclined to include some class of words such as to poo (childish) or to prefetch, to google (technical neologisms).

	graph	n	m	n lcc	m lcc	k lcc	l lcc	C lcc	a lcc	r 2 lcc
	pwn-en-N-A 117798 104929 12617 28608	4.53	9.89 0.76 -2.62 0.89
	pwn-en-N-B 117798 168704 40359 95439	4.73	7.79 0.72 -2.41 0.91
	pwn-en-A-A	21479	22164	4406	11276	5.12	9.08 0.75 -2.32 0.85
	pwn-en-A-B	21479	46614	15945 43925	5.51	6.23 0.78 -2.09	0.9
	pwn-en-V-A	11529	23019	6534	20806	6.37	5.93	0.7	-2.34 0.87
	pwn-en-V-B	11529	40919	9674	39459	8.16	4.66 0.64 -2.06 0.91
	dicosyn-fr-N	29372	100759 26143 98627	7.55	5.37 0.35 -2.17 0.92
	dicosyn-fr-A	9452	42403	8451	41753	9.88	4.7	0.37 -1.92 0.92
	dicosyn-fr-V	9147	51423	8993	51333 11.42	4.2	0.41 -1.88 0.91
		Table 3: Gold standard's synonymy graphs properties
	4 Wiktionary graphs evaluation
	Coverage and global SW analysis By compar-
	ing tables 2 and 3, one can observe that:
	•

Table 4 :

 4 Wiktionary coverage coverage whereas edges evaluation leads to measure the quality of the synonymy links in Wiktionary resource.

Table 5 :

 5 Wiktionary synonymy links precision & recall

http://en.wiktionary.org/

What article refers to is more fuzzy than classical entry or acceptance means.

http://fr.wiktionary.org/w/index.php? title=orange&oldid=2981313

http://it.wiktionary.org/w/index.php? title=cardinale&oldid=758205

http://en.wiktionary.org/wiki/WT:ELE

http://meta.wikimedia.org/wiki/List_ of_Wiktionaries

Average length of the shortest path between any two nodes.

These choices can clearly be discussed from a linguistic point of view and judged to be biased. Nevertheless, we adopted them as a first approximation to make the modelling possible.

Dicosyn has been first produced at ATILF, before being corrected at CRISCO laboratory. (http://elsap1.unicaen.fr/dicosyn.html)

We repeat it only two times, otherwise the number of added edges is too large.