Shanbin Li
email: shanbin.li@cran.uhp-nancy.fr

Dominique Sauter

Christophe Aubrun

Robust Fault Isolation Filter Design for Networked Control Systems

In this paper, the effect of network-induced delay introduced into the control loop is modelled as time-varying disturbance. Based on this model, a fault isolation filter (FIF) for fault detection of networked control systems (NCSs) with multiple faults is then parameterized. Directional residual generations decoupling from the disturbance ensure the treatment of multiple faults appearing simultaneously or sequentially. The remaining degrees of freedom in the design of the filter's gain are used to satisfy an H ∞ disturbance attenuation and poles assignment constraints in the frame of Markov jump linear systems (MJLS). The sufficient existence conditions of the free parameters are formulated as a convex optimization problem over a couple of linear matrix inequalities (LMIs). An illustrative example is given to show the efficiency of the proposed method for NCS.

Introduction

Networked Control Systems (NCSs) may represent a class of spatially distributed systems wherein the plants, sensors, controllers and actuators are assembled feedback loops through a shared communication network. Because of the inherent complexity of such systems, the control issues of NCS have attracted most attention of many researchers with taking into account network-induced delays and/or packet losses, and so on. For instance, the stability and stabilization problems of NCS were investigated in [START_REF] Halevi | Integrated communication and control systems: Part I-Analysis[END_REF][START_REF] Nilsson | Stochastic analysis and control of real-time systems with random time delays[END_REF][START_REF] Branicky | Stability of Networked Control Systems: Explicit Analysis of Delay[END_REF][START_REF] Zhang | Stability of networked control systems[END_REF][START_REF] Li | LMI approach to guaranteed cost control for networked control systems[END_REF] for network-induced delays, [START_REF] Ling | Robust performance of soft real-time networked control systems with data dropouts[END_REF][START_REF] Seiler | An H∞ approach to networked control[END_REF] for packet losses, and [START_REF] Hu | Stochastic optimal control and analysis of stability of networked control systems with long delay[END_REF][START_REF] Yu | An LMI approach to networked control systems with data packet dropout and transmission delays[END_REF][START_REF] Yue | Network-based robust H∞ control of systems with uncertainty[END_REF][START_REF] Li | Guaranteed cost control of networked control systems with time-delays and packet losses[END_REF] for network-induced delays and packet losses. We refer the readers to the survey [START_REF] Tipsuwan | Control Methodologies in Networked Control Systems[END_REF] for more information about the state-of-the-art of NCS.

On the other hand, due to an increasing complexity of dynamical systems, as well as the need for reliability, safety and efficient operation, the model-based fault detection and isolation (FDI) has been becoming an important subject in modern control theory and practice, see e.g. [START_REF] Willsky | A survey of design methods for failure detection in dynamic systems[END_REF][START_REF] Frank | Fault diagnosis in dynamic systems using analytical and knowledge based redundancy-a survey and some new results[END_REF][START_REF] Gertler | Fault Dectection and Diagnosis in Engineering Systems[END_REF][START_REF] Chen | Robust Model-based Fault Diagnosis for Dynamic Systems[END_REF][START_REF] Mangoubi | Model-based fault detection: the optimal past, the robust present and a few thoughts on the future[END_REF] and the references therein. The procedures of model-based FDI problem are i) generations of residuals which are ideally close to zero under fault-free conditions, minimally sensitive to noises and disturbances and maximally sensitive to faults, ii) residual evaluation, namely design of decision rules based on these residuals. When involving the model-based FDI of NCS, the aforementioned problems will be more complex than those of traditional point-to-point systems because of the networkinduced effects. Whereas there are ample significant results on the control issues of NCS, the studies related to FDI of NCS are just at the starting point, which motivates the current research of this paper.

In this paper, we show our attention on the design of a robust fault isolation filter for networked control systems with network-induced delays and multiple faults. Similar to [START_REF] Halevi | Integrated communication and control systems: Part I-Analysis[END_REF], sensor-to-controller network-induced delay and controller-to-actuator network-induced delay are lumped together as a single delay, which is assumed to be random and governed by a Markov chain. Then, the effect of network-induced delays introduced into the control loop is regarded as time-varying disturbance. Based on this model, a fault isolation filter for fault detection of such networked control systems is then parameterized in order to generate the residuals having directional properties in response to a particular fault and decoupling from the disturbance. The remaining degrees of freedom in the design of the filter's gain are used to satisfy an H ∞ disturbance attenuation and poles assignment constraints in the frame of Markov jump linear systems (MJLS). The sufficient existence conditions of the free parameters are formulated as a convex optimization problem over a couple of linear matrix inequalities (LMIs), which can be very efficiently solved by interior-point methods.

The rest of this paper is organized as follows. In Section 2, the networked control systems model taking into account network-induced time-delays and multiple faults is described and main assumptions are presented. Parameterized solutions to the gains of filter and projector, and a sufficient condition for the free parameter satisfying two constrained conditions are developed in Section 3. An illustrative example is presented in Section 4 to show the effectiveness of the result.The paper is concluded in Section 5.

Notations:

In what follows, if not explicitly stated, ma-

.ETWORK T U T N H #ONTROLLER !CTUATOR 0LANT 3ENSOR CA K SC K T Y &$) 5NIT 2ESIDUAL )NFORMATION Figure 1.
A structure of an NCS with FDI unit trices are assumed to have compatible dimensions. R and Z + denote the set of real numbers and the set of nonnegative integer numbers, respectively. R n and R n×m are, respectively, the n-dimensional Euclidean space and the set of n × m real matrices. The notations A > 0 and A < 0 are used to denote a positive and negative definite matrix, respectively. A T denotes the transpose of matrix or vector A. A -1 and A + represent the inverse and pseudo-inverse of A, respectively. diag(a 1 , . . . , a n ) refers to an n × n diagonal matrix with a i as its ith diagonal entry. A denotes the Euclidean norm for vectors or the spectral norms of matrices A. rank(A) stands for the rank operator of matrix A. λ i (A) represents the ith eigenvalue of matrix A.

Problem description and preliminaries

The networked control system structure discussed in this paper is shown in Fig. 1. The plant, sensor, controller and actuator are spatially distributed and closed over network. We suppose that the sensor is time-driven with an identical sampling period h. By event-triggered controller or actuator, we mean that calculation of the new control or actuator signal is started as soon as the new control or actuator information arrives. Similar to [START_REF] Halevi | Integrated communication and control systems: Part I-Analysis[END_REF], the distributed network-induced delays can be lumped together as a single time-delay

τ k = τ sc k + τ ca k ∈ [0, h)
, where τ sc k and τ ca k are delays of sensor-to-controller and controllerto-actuator, respectively.

Suppose that an LTI dynamical model with multiple faults is described as following:

ẋt = Ax t + Bu t + F n t y t = Cx t t ∈ R (1)
where x t ∈ R n is the state vector, y t ∈ R m the output vector, u t ∈ R p the input vector. F = f 1 . . . f i . . . f q is the fault distribution matrix, and n t ∈ R q is the fault vector.

Taking into account the network-induced delay and the control input over a sampling interval [kh, (k + 1)h]:

u t = u k-1 , t ∈ [kh, kh + τ k ]; u k , t∈ [kh + τ k , (k + 1)h]. (2)
Integration the plant (1) over such interval will then give:

x k+1 = Ax k + B0,τ k u k + B1,τ k u k-1 + F n k y k = Cx k , k ∈ Z + (3)
where

A = e Ah , C = C, B 0,τ k = h-τ k 0 e As dsB, B 1,τ k = h h-τ k e As dsB, F = h 0 e As dsF .
According to the property of definite integral, Equation ( 3) is rewritten as:

x k+1 = Ax k + Bu k + F n k + B 1,τ k Δu k , y k = Cx k , (4)
where

B = h 0 e As dsB, Δu k = u k-1 -u k , F = f 1 . . . f i . . . f q .
Remark 1 Different from the sampled-data system without taking into account the network-induced delay, there exists a time-varying term B 1,τ k Δu k in the state evolution equation of system [START_REF] Gertler | Fault Dectection and Diagnosis in Engineering Systems[END_REF]. Therefore, the traditional strategy of detecting and isolating multiple faults must be reevaluated for the NCS.

Remark 2 Inspired by the principles of Delta-Modulation which was introduced in [6] for NCS to generally decrease bits to specify the control signal, we propose to send the decrements of the control signals rather than sending them directly. The actual input signal u k is readily reconstructed by discrete-time integration as u

k = u k-1 -Δu k = u 0 - k i=1 Δu i ,
where u 0 is the initial control signal and assumed to be known in advance. Because the FDI scheme considered in this paper is open-loop, the term Bu k in the dynamics equation [START_REF] Gertler | Fault Dectection and Diagnosis in Engineering Systems[END_REF] will not be important and can be omitted when computing the residual. Therefore, we only focus the attention on the property of Δu k .

In the sequel, we further impose two communication schemes on the design as follows:

S1

The data from the controller to each actuator is restricted to belong to a small and fixed finite set of scalars, U.

S2

The inputs of the plant (Δu i ) k (i = 1, . . . , p) can be lumped together into one network packet and transmitted at the same time. Between updates, all plant inputs are held at their previous values.

Communication schemes 1 and 2 can be summarized by a simple finite-set constraint on the decrements Δu k = u k-1u k . More precisely, at every time instant k, the vector

Δu k (Δu 1 ) k • • • (Δu p ) k T (5)
is restricted to belong to the set V, which is defined as

V {η ∈ R p : η = υ • • • υ T , for some υ ∈ U}.

Remark 3

The communication scheme S2 is suitable for networks with large packets size, e.g. Ethernet which can hold a maximum of 1500 bytes of data in a single packet, see e.g. [START_REF] Srinivasagupta | Timestamped model predictive control: an algorithm for control of processes with random delays[END_REF][START_REF] Tang | Ethernet-based Predictive Control of an Industrial Hydraulic Machine[END_REF].

Remark 4 Utilizing a receding horizon scheme as deployed in model predictive control, see e.g. [START_REF] Goodwin | A moving horizon approach to networked control system design[END_REF][START_REF] Yu | Predictive compensation for stochastic time delay in network control systems[END_REF], the optimal Δu k can be obtained which is not within the scope of this paper. When implementing the design of FDI, Δu k is assumed to be known.

Without loss of generality, we assume that the statistical behavior of network-induced delay τ k is random and governed by the Markov chain

θ k ∈ S = {1, 2, . . . , s}, ∀k ∈ Z + (6)
with the transition probabilities λ ij denoting as

λ ij = Pr[θ k+1 = j|θ k = i], λ ij ≥ 0 and s j=1 λ ij = 1 for any i ∈ S.
For sake of simplifying notations, we denote B 1,τ k as B 1,θ k and Δu k as w k . Then, the model of networked control system considered in this paper is replaced the state space system (4) with the following particular Markov jump linear system:

x k+1 = Ax k + Bu k + F n k + B 1,θ k w k , y k = Cx k , (7)
The following filter is presented as the residual generator of NCS [START_REF] Haddad | Controller design with reginal pole constraints[END_REF]:

xk+1 = Ax k + Bu k + K(y k -C xk ), α k = L(y k -C xk ), (8)
where xk is the state of the filter, α k the residual generator or the fault indicator. Filter gain K ∈ R n×m and projector L ∈ R q×m are unknown matrices to be found for the solution of the fault detection and isolation problem. The objectives of this paper are i) to construct a fault isolation filter as [START_REF] Halevi | Integrated communication and control systems: Part I-Analysis[END_REF] for fault detection and isolation of multiple faults in networked control system, ii) to design a free parameter ensuring that the energy ratio between useful and disturbance signal w k defined on the fault indicators is maximized, iii) to locate the closed-loop poles within a prescribed region in the complex plane in order that the residual dynamical has the given transient properties.

It should be noted that the particular case we have focused on ensures that the definitions of fault detectability indexes and matrices introduced in [START_REF] Keller | Fault isolation filter design for linear stochastic systems[END_REF] still hold true for system [START_REF] Haddad | Controller design with reginal pole constraints[END_REF]. We end this section by recalling these definitions which will be essential for the proofs in the next section.

Definition 1 The networked control system ( 7) is said to have fault detectability indexes ρ = {ρ 1 , ρ 2 , . . . , ρ q } if ρ i = min{ν : CA ν-1 f i = 0, ν = 1, 2, . . .}.

Definition 2

If the networked control system [START_REF] Haddad | Controller design with reginal pole constraints[END_REF] has finite fault detectability indexes, the fault detectability matrix Ψ is defined as:

Ψ = CD (9)
with

D = A ρ1-1 f 1 • • • A ρi-1 f i • • • A ρq-1 f q .
3 Robust FIF for NCS

In this section, we will firstly give the parameterized solutions of filter gain and projector. Under two constrained conditions, a robust FIF for NCS will then be designed from reduced gains describing the available degrees of freedom.

From ( 4) and ( 8), the state estimation error e k = x kxk and the output of the filter α k propagate as

e k+1 = (A -KC)e k + F n k + B 1,θ k w k α k = LCe k , k ∈ Z+, θ k ∈ S (10)
Let G nα (z) be the transfer function from n k to the output residual α k . Then the following theorem is presented to design K and L such that

Gnα(z) = LC(zI -(A -KC)) -1 F = diag{z -ρ 1 , . . . , z -ρq }, (11)
which ensures the isolation of multiple faults.

Theorem 1 Under the condition rank(Ψ) = q, the solutions of ( 11) can be parameterized as

K = ωΠ + Kθ k Σ, L = Π, with Σ = β(I -ΨΠ), Π = Ψ + , ω = AD
and Ψ = CD,where Kθ k ∈ R n×m-q is the free parameters to be designed, Ψ + is the pseudo-inverse of Ψ and β is an arbitrary matrix chosen so that rank(Σ) = mq.

Proof. From (11), we have

G nα (z) = LC(zI -(A -KC)) -1 F = k≥0 LC(A -KC) k F z -k-1 = k≥0 z -k-1 • • • LC(A -KC) k f i • • • (12)
where

k≥0 z -k-1 LC(A -KC) k fi = z -1 LCfi + z -2 LC(A -KC)fi + • • • = LCA ρ i -1 fiz -ρ i + k≥0 LC(A -KC) k+1 A ρ i -1 fiz -k-1-ρ i (13)
Substituting ( 13) into ( 12), we have

Gnα(z) = • • • LCA ρ i -1 fiz -ρ i + k≥0 LC(A -KC) k+1 A ρ i -1 fiz -k-1-ρ i • • • (14)
If the filter gain K satisfies the following algebraic constraint

(A-KC)[ • • • A ρ i -1 fi • • • ]= 0⇐⇒ (A-KC)D = 0, then (14)
gives

G nα (z) = LΨdiag{z -ρ1 , . . . , z -ρq }, (15)
and ( 11) is satisfied under LΨ = I. By the generalized inverse of matrix [START_REF] Rao | Generalized inverse of matrices and its applications[END_REF], K and L can be parameterized as the statements of this theorem. The proof is complete.

Remark 5 It's should be noted that the free parameter

Kθ k is independent of the multiple faults isolation because any Kθ k ensures [START_REF] Li | Guaranteed cost control of networked control systems with time-delays and packet losses[END_REF]. So, the filter gain K is independent of Kθ k and hence independent of the Markov chain θ k ∈ S when the theorem is proven. Otherwise, K governed by Markov chain θ k will bring about the complexity of analysis in the case where the filter ( 8) and the error system [START_REF] Keller | Fault isolation filter design for linear stochastic systems[END_REF] are hybrid. However, the introduction of Kθ k gives an extra degree of freedom to satisfy some other design requirements.

From Theorem 1, the FIF ( 8) is rewritten from the free parameter Kθ k as :

xk+1 = Ax k + Bu k + ωα k + Kθ k Σ(y k -C x), α k = Π(y k -C xk ), (16)
where α k is a deadbeat filter of fault n k and given by:

α k = αk + n 1 k-ρ1 • • • n i k-ρi • • • n q k-ρq T (17)
where αk is the faults indicator signal without faults and propagates from the fault-free state estimation error ēk = xkxk as:

ēk+1 = ( Ā -Kθ k C)ē k + B 1,θ k w k , αk = ΠC ēk , (18)
where Ā = A -ωΠC, C = ΣC and xk is the fault-free state. The transfer function from w k to αk is then given by:

G w α(z) = ΠC(zI -( Ā -Kθ k C)) -1 B 1,θ k . ( 19
)
Let αk be the faults indicator signal without disturbances. From Equation [START_REF] Li | Guaranteed cost control of networked control systems with time-delays and packet losses[END_REF], the transfer function G n α(z) from fault n to fault indicator αk is a pure delay and

G n α(z) ∞ := sup θ0∈S sup 0 =n∈ 2 α 2 n 2 = 1, (20)
where

s 2 = ( ∞ k=0 s k ) 1/2 is the 2 norm of the sig- nal s k .
Rest of three aims of this paper are then to design the free parameters Kθ k satisfying the constraints as:

C1 the H ∞ -norm of transfer function G w α(z) is less than a prescribed scalar γ > 0, namely G w α(z) ∞ := sup θ0∈S sup 0 =w∈ 2 α 2 w 2 < γ (21)
C2 the poles of ( Ā -Kθ k C) are inside discs D θ k (ξ θ k , δ θ k ) in the complex plane with the center ξ θ k + j0 and -1

< -ξ θ k + δ θ k < 1, namely λ i Ā-Kθ k C-ξ θ k I δ θ k ⊂ D(0, 1), i = 1, . . . , n, ∀θ k ∈ S.
Remark 6 By locating the closed-loop poles in a prescribed region in the complex plan, the constraint C2 ensures that the error system [START_REF] Rao | Generalized inverse of matrices and its applications[END_REF] has the given transient properties. This scheme is borrowed from the robust control of linear system with poles constraints, see e.g. [START_REF] Haddad | Controller design with reginal pole constraints[END_REF][START_REF] Wang | Controller design for continuous systems with variance and circular pole constraints[END_REF][START_REF] Yu | Robust control of linear uncertain systems with regional pole and variance constraints[END_REF].

Before proceeding further, we recall the notation of second-moment stability (SMS) and some related results. Consider the following stochastic system P:

(P) : x k+1 e k = A θ k B θ k C θ k D θ k x k w k ( 22
)
where x k ∈ R nx is the state, w k ∈ R nw is the disturbance vector and e k ∈ R ne is the error vector. The notation of θ k is given as [START_REF] Goodwin | A moving horizon approach to networked control system design[END_REF].

Definition 3 ([19])

The system P is weakly controllable if for every initial state/mode, (x 0 , θ 0 ), and any final state/mode, (x f , θ f ), there exists a finite time T c and an input d c,k such that Pr[x Tc = x f and θ Tc = θ f ] > 0.

Lemma 1 ([19]

) System P is SMS if and only if there exist matrices

P i > 0 that satisfy A T i Pi A i -P i < 0 ∀i = θ k ∈ S where Pi := s j=1 λ ij P j .
Lemma 2 (Bounded Real Lemma) Assume the system P is weakly controllable and let x 0 = 0. The following conditions are equivalent: i) P is SMS and the H ∞ -norm denoted as

P ∞ := sup θ0∈S sup 0 =w∈ 2 e 2 w 2 (23)
satisfies P ∞ < γ.

ii) there exist matrices

P i > 0 that satisfy Ai Bi Ci Di T Pi 0 0 I Ai Bi Ci Di - Pi 0 0 γ 2 I < 0 ( 24
)
where Pi = s j=1 λ ij P j and i = θ k ∈ S. iii) there exist matrices P i > 0 and G i that satisfy

GiAi GiBi Ci Di T Pi -Gi -G T i 0 0 I -1 × GiAi GiBi Ci Di - Pi 0 0 γ 2 I < 0 ( 25
)
where Pi = s j=1 λ ij P j and i = θ k ∈ S.

Proof. The equivalence of i) and ii) has been proven in [START_REF] Seiler | A bounded real lemma for jump systems[END_REF]. By the so-called slack variable method which was introduced in [START_REF] Oliveira | A new discrete-time robust stability condition[END_REF][START_REF] Peaucelle | A new robust D-stability condition for real convex polytopic uncertainty[END_REF], the equivalences of i) and iii), ii) and iii) will be proven.

Remark 7

Due to the slack variables G i , the condition iii) gives potential advantages over condition ii), especially for the design of the free parameters Ki in the following theorem.

Theorem 2 For given discs D i (ξ i , δ i ), if there exist matrices

P i = P T i > 0, G i and Y i for prescribed scalars γ > 0, -1 < -ξ i + δ i < 1, ∀i = θ k ∈ S such that ⎡ ⎢ ⎣ -Pi 0 ĀT G T i -CT Y T i C T Π T 0 -γ 2 I B T 1,i G T i 0 Gi Ā -Yi C GiB1,i Pi -Gi -G T i 0 ΠC 0 0 -I ⎤ ⎥ ⎦ < 0, (26)
-δ 2 i P i ĀT G T i -CT Y T i -ξ i G T i G i Ā -Y i C -ξ i G i P i -G i -G T i < 0, (27)
where Ā = A -ωΠC, C = ΣC, then the free parameters are designed as Ki = G -1 i Y i ensuring the SMS of the error system [START_REF] Rao | Generalized inverse of matrices and its applications[END_REF] and the constraints C1 and C2. At the minimal possible value of γ leading to a solution P i = P T i > 0, G i and Y i , the energy ratio between useful and disturbance signal defined on the fault indicators will be maximized.

Proof. If there exist matrices

P i = P T i > 0, G i and Y i = G i Ki such that (26) holds, we obtain: ⎡ ⎢ ⎢ ⎣ -P i 0 A T i G T i C T i 0 -γ 2 I B T i G i 0 G i A i G i B i Pi -G i -G T i 0 C i 0 0 -I ⎤ ⎥ ⎥ ⎦ < 0, (28)
where

A i = Ā -Ki C, B i = B 1,i , C i = Π C.
By Schur complement, we obtain that (28) implies [START_REF] Willsky | A survey of design methods for failure detection in dynamic systems[END_REF]. So, the free parameter Ki = G -1 i Y i ensures the SMS of the error system [START_REF] Rao | Generalized inverse of matrices and its applications[END_REF] and the constraint C1.

Furthermore, if there exist matrices [START_REF] Yu | An LMI approach to networked control systems with data packet dropout and transmission delays[END_REF] holds, pre-multiplying and post-multiplying δ -1 i I, -δ -1 i ( Ā -Ki Cξ i I) T and its transpose to [START_REF] Yu | An LMI approach to networked control systems with data packet dropout and transmission delays[END_REF] will yield:

P i = P T i > 0, G i and Y i = G i Ki such that
Ā -Ki C -ξ i I δ i T P i Ā -Ki C -ξ i I δ i -P i < 0, (29)
which immediately implies [START_REF] Yu | An LMI approach to networked control systems with data packet dropout and transmission delays[END_REF] satisfying the constraint C2. In summary, the free parameters are designed as Ki = G -1 i Y i ensuring the SMS of the error system [START_REF] Rao | Generalized inverse of matrices and its applications[END_REF] and the constraints C1 and C2. The proof is complete.

Remark 8 Given discs D i (ξ i , δ i ), i = θ k ∈ S,
which can be effectively solved by the existing Matlab LMI toolbox [START_REF] Ghainet | LMI Control Toolbox-for Use with Matlab[END_REF].

Illustrative Example

In this section, we will present an example to illustrate the design approach proposed in this paper. We borrow the modified example from [START_REF] Keller | Fault isolation filter design for linear stochastic systems[END_REF] described by [START_REF] Haddad | Controller design with reginal pole constraints[END_REF], where the parameters are as follows:

A = ⎡ ⎢ ⎢ ⎣ 0.2 1 0 0.2 0 0.5 1 0.4 0 0 0.8 1 0 0 0 0.3 ⎤ ⎥ ⎥ ⎦ , B = ⎡ ⎢ ⎢ ⎣ 0 -1 -1 1 1 0 -1 1 ⎤ ⎥ ⎥ ⎦ , F = ⎡ ⎢ ⎢ ⎣ -1 1 1 0 0 -1 1 1 ⎤ ⎥ ⎥ ⎦ , C = ⎡ ⎣ 0 1 0 0 0 0 1 0 0 0 0 1 ⎤ ⎦ ,
and sampling time h = 0.1sec. Therefore, the parameters of original continuous time LTI system (1) can be obtained by the Matlab command d2c, for example, [A, B] = d2c(A, B, h). The transition probability matrix of ( 6) is

Λ = ⎡ ⎣ 0.
K1 = ⎡ ⎢ ⎢ ⎣ 0.7900 -0.9002 -1.7999 -0.3003 ⎤ ⎥ ⎥ ⎦ , K2 = ⎡ ⎢ ⎢ ⎣ 0.7834 -0.7293 -1.9742 -0.4672 ⎤ ⎥ ⎥ ⎦ , K3 = ⎡ ⎢ ⎢ ⎣ 0.8038 -1.0827 -1.6090 -0.1293 ⎤ ⎥ ⎥ ⎦ .
The fault associated to the first column of the matrix F occurs at time instant r 1 = 50 with n 1 k = 10 sin(0.1k). The fault associated to the second column occurs at time instant r 2 = 120 with n 2 k = 5. Fig. 2 gives the innovation sequences of Markov chain mode, the networkinduced time-delay governed by such Markov chain and the control decrements

Δu k = [(Δu 1 ) k , (Δu 2 ) k ]
T . It should be noted that the finite scalar set U of the communication scheme S1 is given as U = {-1, 0, 1} when implementing simulation. Fig. 3 shows the innovation sequences of residual

α k = [(α 1 ) k , (α 2 ) k ]
T and

α k = (α 1 ) k , ( α 2 ) k T
, where (a) and (b), (c) and (d) correspond to the residual obtained by the FIF [START_REF] Oliveira | A new discrete-time robust stability condition[END_REF] with the free parameters Ki (i = 1, 2, 3) and the FIF [START_REF] Oliveira | A new discrete-time robust stability condition[END_REF] without the free parameters, respectively. In order to compare the obtained results by different methods, we propose the root mean square (RMS) of the fault estimation error as a performance index. This error for the scalar variable n i with respect to its estimate α i for N s simulation steps is defined as

RMS i Ns j=1 n j i -α j i 2 N s (31)
where n j i is the value of the variable n i in the j-th step, α j i is the estimate of n j i , and i = 1, 2. From Fig. 3 and Tab.1 which shows the RMS of the fault estimation errors, we can conclude that the FIF ( 16) with the free parameters Ki (i = 1, 2, 3) works better than the FIF (16) without the free parameters does.

Conclusion

This paper modelled the effect of network-induced delay introducing into the control loop as time-varying disturbance. Based on this model, a fault isolation filter for fault detection of networked control systems with multiple faults was then parameterized. Directional residual generations decoupling from the disturbance ensured the treatment of multiple faults appearing simultaneously or sequentially. The remaining degrees of freedom in the design of the filter's gain were used to satisfy an H ∞ disturbance attenuation and poles assignment constraints within the framework of H ∞ control for Markov jump linear systems. The sufficient existence conditions of the free parameters were formulated as a convex optimization problem over a couple of linear matrix inequalities. An Illustrative example was then given to show the efficiency of the proposed method for NCS. In contrast with the fault isolation filter without free parameters, it can be concluded that the proposed fault isolation filter works better for NCS.

Throughout the paper, only the network-induced delays shorter than one sampling period were taken into account in the model of the networked control system. Since the inherent complexity is concerned with the model of networked control system, much work can be carried out especially for the case where the network-induced delays are longer than one sampling period. On the other hand, the control decrement sequences in this paper are assumed to be known in advance. If the network scheduling algorithm is adopted to optimize the sequences, the fault estimation performance will be expected to increase. Study of integrating network scheduling and fault detection and isolation problem for networked control systems is also encouraged.

Figure 2 .Figure 3 .

 23 Figure 2. Innovation sequences of (a) Markov chain mode θ k (b) the network-induced time delay τ k (c) the control decrements (Δu 1 ) k (d) the control decrement (Δu 2 ) k

  the search problem of the lowest possible value of γ can be formulated as the following convex optimization problem:

	OP :	min Pi=P T i >0,Gi,Yi	γ
		s.t. LMI (26), (27)

Table 1 . RMS of the fault estimation errors

 1 Furthermore, the discs D i (ξ i , δ i ) (i = 1, 2, 3) are given as D 1 (0, 0.3), D 2 (-0.2, 0.4), D 3 (0.2, 0.3). According to (α 1 ) k (α 1 ) k (α 2 ) k (α 2 ) k RMS 0.7368 0.8005 0.5378 0.6787 Theorem 2, the minimal possible value of γ is found to be 1.5854 and the free parameters Ki are constructed as:

		67 0.17 0.16	⎤
		0.3 0.47 0.23	⎦ ,
		0.26 0.10 0.64
	and the corresponding random network-induced delays
	are τ 1 = 0.06sec, τ 2 = 0.07sec, τ 3 = 0.08sec. Accord-
	ing to Theorem 1, we have Ψ = CF and D = F since
	rank(CF ) = q (ρ 1 = 1, ρ 2 = 1). The parametrization
	of the FIF's gain K is given by
	Σ = -0.333 0.333 0.333 ,
	Π =	0.6667 -0.3333 -0.6667 0.3333 0.3333 0.3333	.

Acknowledgments

The authors would like to acknowledge the FP6 IST program of European Union under Grant NeCST EU-IST-2004-004303 for funding the research.


Claire Gardent

Anastasia Shimorina

Shashi Narayan

Laura Perez-Beltrachini

Creating

Creating Training Corpora for NLG Micro-Planning

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

Introduction

To train Natural Language Generation (NLG) systems, various input-text corpora have been developed which associate (numerical, formal, linguistic) input with text. As discussed in detail in Section 2, these corpora can be classified into three main types namely, (i) domain specific corpora, (ii) benchmarks constructed from "Expert" Lin-guistic Annotations and (iii) crowdsourced benchmarks 1 .

In this paper, we focus on how to create datato-text corpora which can support the learning of wide-coverage micro-planners i.e., generation systems that handles such NLG subtasks as lexicalisation (mapping data to words), aggregation (exploiting linguistic constructs such as ellipsis and coordination to avoid repetition), surface realisation (using the appropriate syntactic constructs to build sentences), sentence segmentation and referring expression generation.

We start by reviewing the main existing types of NLG benchmarks and we argue for a crowdsourcing approach where data units are automatically built from an existing knowledge base and where text is crowdsourced from the data (Section 2).

We then propose a generic framework for semiautomatically creating training corpora for NLG (Section 3) from existing Knowledge Bases. In Section 4, we apply this framework to DBpedia data and we compare the resulting dataset with [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF]'s using various metrics to evaluate the linguistic and computational adequacy of both datasets. By applying these metrics, we show that while [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF]'s dataset is more than twice larger than ours, it is less diverse both in 1 We ignore here [START_REF] Lebret | Neural Text Generation from Structured Data with Application to the Biography Domain[END_REF]'s dataset which was created fully automatically from Wikipedia by associating infoboxes with text because this dataset fails to ensure an adequate match between data and text. We manually examined 50 input/output pairs randomly extracted from this dataset and did not find a single example where data and text matched. As such, this dataset is ill-suited for training microplanners. Moreover, since its texts contain both missing and additional information, it cannot be used to train joint models for content selection and micro-planning either.

terms of input and in terms of text. We also compare the performance of a sequence-to-sequence model [START_REF] Vinyals | Grammar as a foreign language[END_REF] on both datasets to estimate the complexity of the learning task induced by each dataset. We show that the performance of this neural model is much lower on the new data set than on the existing ones. We thus propose our corpus generation framework as a novel method for creating challenging data sets from which NLG models can be learned which are capable of generating complex texts from KB data.

NLG Benchmarks

Domain Specific Benchmarks. Several domain specific data-text corpora have been built by researchers to train and evaluate NLG systems. In the sports domain, Chen and Mooney (2008) constructed a dataset mapping soccer games events to text which consists of 1,539 data-text pairs and a vocabulary of 214 words. For weather forecast generation, [START_REF] Liang | Learning Semantic Correspondences with Less Supervision[END_REF]'s dataset includes 29,528 data-text pairs with a vocabulary of 345 words. For the air travel domain, [START_REF] Ratnaparkhi | Trainable methods for surface natural language generation[END_REF] created a dataset consisting of 5,426 datatext pairs with a richer vocabulary (927 words) and in the biology domain, the KBGen shared task [START_REF] Banik | The KBGen challenge[END_REF] made available 284 data-text pairs where the data was extracted from an existing knowledge base and the text was authored by biology experts.

An important limitation of these datasets is that, because they are domain specific, systems learned from them are restricted to generating domain specific, often strongly stereotyped text (e.g., weather forecast or soccer game commentator reports). Arguably, training corpora for NLG should support the learning of wide-coverage generators. By nature however, domain specific corpora restrict the lexical and often the syntactic coverage of the texts to be produced and thereby indirectly limit the expressivity of the generators trained on them.

Benchmarks Constructed from "Expert" Linguistic Annotations. NLG benchmarks have also been proposed where the input data is either derived from dependency parse trees (SR'11 task, [START_REF] Belz | The First Surface Realisation Shared Task: Overview and Evaluation Results[END_REF] or constructed through manual annotation (AMR Corpus [START_REF] Banarescu | Abstract meaning representation (AMR) 1.0 specification. In Parsing on Freebase from Question-Answer Pairs[END_REF]). Contrary to the domain-specific data sets just mentioned, these corpora have a wider coverage and are large enough for training systems that can generate linguistically sophisticated text.

One main drawback of these benchmarks however is that their construction required massive manual annotation of text with complex linguistic structures (parse trees for the SR task and Abstract Meaning Representation for the AMR corpus). Moreover because these structures are complex, the annotation must be done by experts. It cannot be delegated to the crowd. In short, the creation of such benchmark is costly both in terms of time and in terms of expertise.

Another drawback is that, because the input representation derived from a text is relatively close to its surface form2 , the NLG task is mostly restricted to surface realisation (mapping input to sentences). That is, these benchmarks give very limited support for learning models that can handle micro-planning NLG subtasks such as lexicalisation, aggregation, sentence segmentation and referring expression generation.

Crowdsourced Benchmarks. More recently, data-to-text benchmarks have also been created by associating data units with text using crowdsourcing. [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF] first created data by enumerating all possible combinations of 14 dialog act types (e.g., request, inform) and attribute-value pairs present in four small-size, hand-written ontologies about TVs, laptops, restaurants and hotels. They then use crowdsourcing to associate each data unit with a text. The resulting dataset is both large and varied (4 domains) and was successfully exploited to train neural and imitation learning data-to-text generator [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF][START_REF] Lampouras | Imitation learning for language generation from unaligned data[END_REF]. Similarly, [START_REF] Novikova | The aNALoGuE Challenge: Non Aligned Language GEneration[END_REF] described a framework for collecting data-text pairs using automatic quality control measures and evaluating how the type of the input representations (text vs pictures) impacts the quality of crowdsourced text.

The crowdsourcing approach to creating inputtext corpora has several advantages.

First, it is low cost in that the data is produced automatically and the text is authored by a crowdworker. This is in stark contrast with the previous approach where expert linguists are required to align text with data.

Second, because the text is crowd-sourced from the data (rather than the other way round), there is an adequate match between text and data both semantically (the text expresses the information contained in the data) and computationally (the data is sufficiently different from the text to require the learning of complex generation operations such as sentence segmentation, aggregation and referring expression generation).

Third, by exploiting small hand-written ontologies to quickly construct meaningful artificial data, the crowdsourcing approach allows for the easy creation of a large dataset with data units of various size and bearing on different domains. This, in turn, allows for better linguistic coverage and for NLG tasks of various complexity since typically, inputs of larger size increases the need for complex microplanning operations.

A Framework for Creating

Data-to-Text, Micro-Planning Benchmarks

While as just noted, the crowdsourcing approach presented in [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF] has several advantages, it also has a number of shortcomings. One important drawback is that it builds on artificial rather than "real" data i.e., data that would be extracted from an existing knowledge base. As a result, the training corpora built using this method cannot be used to train KB verbalisers i.e., generation systems that can verbalise KB fragments.

Another limitation concerns the shape of the input data. [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF]'s data can be viewed as trees of depth one (a set of attributes-value pairs describing a single entity e.g., a restaurant or a laptop). As illustrated in Figure 1 however, there is a strong correlation between the shape of the input and the syntactic structure of the corresponding sentence. The path structure T 1 where B is shared by two predicates (mission and operator) will favour the use of a participial or a passive subject relative clause. In contrast, the branching structure T 2 will favour the use of a new clause with a pronominal subject or a coordinated VP. More generally, allowing for trees of deeper depth is necessary to indirectly promote the introduction in the benchmark of a more varied set of syntactic constructs to be learned by generators.

To address these issues, we introduce a novel method for creating data-to-text corpora from large knowledge bases such as DBPedia. Our method combines (i) a content selection module designed to extract varied, relevant and coherent data units from DBPedia with (ii) a crowdsourcing process for associating data units with human authored texts that correctly capture their meaning. Example 1 shows a data/text unit created by our method using DBPedia as input KB.

( Our method has the following features. First, it can be used to create a data-to-text corpus from any knowledge base where entities are categorised and there is a large number of entities belonging to the same category. As noted above, this means that the resulting corpus can be used to train KB verbalisers i.e., generators that are able to verbalise fragments of existing knowledge bases. It could be used for instance, to verbalise fragments of e.g., MusicBrainz3 , FOAF4 or Linked-GeoData5 .

Second, as crowdworkers are required to enter text that matches the data and a majority vote validation process is used to eliminate mis-matched pairs, there is a direct match between text and data. This allows for a clear focus on the non content selection part of generation known as microplanning.

Third, because data of increasing size is matched with texts ranging from simple clauses to short texts consisting of several sentences, the resulting benchmark is appropriate for exercising the main subtasks of microplanning. For instance, in Example (1) above, given the input shown in (1a), generating (1b) involves lexicalising the occupation property as the phrase worked as (lexicalisation); using PP coordination (born in San Antonio on 1942-08-26) to avoid repeating the word born (aggregation); and verbalising the three triples using a single complex sentence including an apposition, a PP coordination and a transitive verb construction (sentence segmentation and surface realisation).

DBPedia

To illustrate the functioning of our benchmark creation framework, we apply it to DBPedia. DBPedia is a multilingual knowledge base that was built from various kinds of structured information contained in Wikipedia [START_REF] Mendes | DBpedia: A Multilingual Cross-domain Knowledge Base[END_REF]. This data is stored as RDF (Resource Description Format) triples of the form (subject, property, object) where the subject is a URI (Uniform Resource Identifier), the property is a binary relation and the object is either a URI or a literal value such as a string, a date or a number. We use an English version of the DBPedia knowledge base which encompasses 6.2M entities, 739 classes, 1,099 properties with reference values and 1,596 properties with typed literal values.6

Selecting Content

To create data units, we follow the procedure outlined in [START_REF] Perez-Beltrachini | Building RDF Content for Data-to-Text Generation[END_REF] and sketched in Figure 2. This method can be summarised as follows.

First, DBPedia category graphs are extracted from DBPedia by retrieving up to 500 entity graphs for entities of the same category7 . For example, we build a category graph for the Astronaut category by collecting, graphs of depth five for 500 entities of types astronaut.

Next, category graphs are used to learn bigram models of DBPedia properties which specify the probability of two properties co-occuring together. Three types of bi-gram models are extracted from category graphs using the SRILM toolkit: one model (S-Model) for bigrams occurring in sibling triples (triples with a shared subject); one model (C-Model) for bigrams occurring Finally, the content selection task is formulated as an Integer Linear Programming (ILP) problem to select, for a given entity of category C and its entity graph G e , subtrees of G e with maximal bigram probability and varying size (between 1 and 7 RDF triples).

We applied this content selection procedure to the DBPedia categories Astronaut (A), Building (B), Monument (M), University (U), Sports team (S) and Written work (W), using the three bi-gram models (S-Model, C-Model, M-Model) and making the number of triples required by the ILP constraint to occur in the output solutions vary between 1 and 7. The results are shown in Table 1. An input is a set of triples produced by the content selection module. The number of input is thus the number of distinct sets of triples produced by this module. In contrast, input patterns are inputs where subject and object have been abstracted over. That is, the number of input patterns is the number of distinct sets of properties present in the set of inputs. The number of properties is the number of distinct RDF properties occurring in the dataset. Similarly, the number of entities is the number of distinct RDF subjects and objects occurring in each given dataset.

Associating Content with Text

We associate data with text using the Crowdflower platform8 . We do this in four main steps as follows. 1. Clarifying Properties. One difficulty when collecting texts verbalising sets of DBPedia triples is that the meaning of DBPedia properties may be unclear. We therefore first manually clarified for each category being worked on, those properties which have no obvious lexicalisations (e.g., crew1up was replaced by commander).

Getting Verbalisations for Single Triples.

Next, we collected three verbalisations for data units of size one, i.e. single triples consisting of a subject, a property and an object. For each such input, crowdworkers were asked to produce a sentence verbalising its content. We used both a priori automatic checks to prevent spamming and a posteriori manual checks to remove incorrect verbalisations. We also monitored crowdworkers as they entered their input and banned those who tried to circumvent our instructions and validators. The automatic checks comprise 12 custom javascript validators implemented in the CrowdFlower platform to block contributor answers which fail to meet requirements such as the minimal time a contributor should stay on page, the minimal length of the text produced, the minimal match of tokens between a triple and its verbalisation and various format restrictions used to detect invalid input. The exact match between a triple and its verbalisation was also prohibited. In addition, after data collection was completed, we manually checked each data-text pair and eliminated from the data set any pair where the text either did not match the information conveyed by the triple or was not a well-formed English sentence.

Getting Verbalisations for

Input containing more than one Triple. The verbalisations collected for single triples were used to construct input with bigger size. Thus, for input with a number of triples more than one, the crowd was asked to merge the sentences corresponding to each triple (obtained in step 2) into a natural sounding text.

In such a way, we diminish the risk of having misinterpretations of the original semantics of a data unit. Contributors were also encouraged to change the order, and the wording of sentences, while writing their texts. For each data unit, we collected three verbalisations.

Verifying the Quality of the Collected Texts.

The verbalisations obtained in Step 3 were verified through crowdsourcing. Each verbalisation collected in Step 3 was displayed to CrowdFlower contributors together with the corresponding set of triples. Then the crowd was asked to assess its fluency, semantic adequacy, and grammaticality. Those criteria were checked by asking the following three questions: Does the text sound fluent and natural?, Does the text contain all and only the information from the data?, Is the text good English (no spelling or grammatical mistakes)?. We collected five answers per verbalisation. A verbalisation was considered as bad, if it received three negative answers in at least one criterion. After the verification step, the total corpus loss was of 8.7%.

Table 2 shows some statistics about the text obtained using our crowdsourcing procedure.

Comparing Benchmarks

We now compare a dataset created using our dataset creation framework (henceforth WEBNLG) with [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF]'s dataset 9 (henceforth, RNNLG). Example 2 shows a sample data-text pair taken from the RNNLG dataset. The WEBNLG dataset has been uploaded with this submission.

(2) Dialog Moves recommend(name=caerus 33;type=television; screensizerange=medium;family=t5;hasusbport=true) The caerus 33 is a medium television in the T5 family that's USB-enabled

As should be clear from the discussion in Section 2 and 3, both datasets are similar in that, in both cases, data is built from ontological information and text is crowdsourced from the data. An important difference between the two datasets is that, while the RNNLG data was constructed by enumerating possible combinations of dialog act types and attribute-value pairs, the WEBNLG data is created using a sophisticated content selection procedure geared at producing sets of data units that are relevant for a given ontological category and that are varied in terms of size, shape and content [START_REF] Perez-Beltrachini | Building RDF Content for Data-to-Text Generation[END_REF]. We now investigate the impact of this difference on the two datasets (WEBNLG and RNNLG). To assess the degree to which both datasets support the generation of linguistically varied text requiring complex microplanning operations, we examine a number of data and text related metrics. We also compare the results of an out-of-the-box sequence-to-sequence model as a way to estimate the complexity of the learning task induced by each dataset.

Data Comparison

Terminology. The attributes in [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF]'s dataset can be viewed as binary relations between the object talked about (a restaurant, a laptop, a TV or a hotel) and a value. Similarly, in WEBNLG, DBpedia RDF properties relate a subject entity to an object which can be either an entity or a datatype value. In what follows, we refer to both as attributes.

Table 3 shows several statistics which indicate that, while the RNNLG dataset is larger than WEBNLG, WEBNLG is much more diverse in terms of attributes, input patterns and input shapes.

Number of attributes.

As illustrated in Example (3) below, different attributes can be lexicalised using different parts of speech. A dataset with a larger number of attributes is therefore more likely to induce texts with greater syntactic variety.

(3) Verb: X title Y / X served as Y

Relational noun: X nationality Y / X's nationality is Y Preposition: X country Y / X is in Y Adjective: X nationality USA / X is American
As shown in Table 3, WEBNLG has a more diverse attribute set than RNNLG both in absolute (172 attributes in WEBNLG against 108 in RNNLG) and in relative terms (RNNLG is a little more than twice as large as WEBNLG).

Number of Input Patterns. Since attributes may give rise to lexicalisation with different parts of speech, the sets of attributes present in an input (input pattern 10 ) indirectly determine the syntactic realisation of the corresponding text. Hence a higher number of input patterns will favour a 10 Recall from section 3 that input patterns are inputs where subjects and objects have been remove thus, in essence, an input pattern is the set of all the attributes occurring in a given input.

higher number of syntactic realisations. This is exemplified in Example (4) where two inputs with the same number of attributes give rise to texts with different syntactic forms. While in Example (4a), the attribute set { country, location, startDate } is realised by a passive (is located), an apposition (Australia) and a deverbal nominal (its construction), in Example (4b), the attribute set { al-maMater, birthPlace, selection } induced a passive (was born) and two VP coordinations (graduated and joined). Again, despite the much larger size of the RNNLG dataset, the number of input patterns in both datasets is almost the same. That is, the relative variety in input patterns is higher in WEBNLG.

Number of Input / Number of Input Patterns.

The ratio between number of inputs and the number of input patterns has an important impact both in terms of linguistic diversity and in terms of learning complexity. A large ratio indicates a "repetitive dataset" where the same pattern is instantiated a high number of times. While this facilitates learning, this also reduces linguistic coverage (less combinations of structures can be learned) and may induce overfitting. Note that because datasets are typically delexicalised when training NLG models (cf. e.g., [START_REF] Wen | Semantically conditioned lstm-based natural language generation for spoken dialogue systems[END_REF][START_REF] Lampouras | Imitation learning for language generation from unaligned data[END_REF]) , at training time, different instantiations of the same input pattern reduce to identical input.

The two datasets markedly differ on this ratio which is five times lower in WEBNLG. While in WEBNLG, the same pattern is instantiated in average 2.40 times, it is instantiated 10.31 times in average in RNNLG. From a learning perspective, this means that the RNNLG dataset facilitates learning but also makes it harder to assess how well systems trained on it can generalise to handle unseen input.

Input Shape. As mentioned in Section 3, in the RNNLG dataset, all inputs can be viewed as trees of depth one while in the WEBNLG dataset, input may have various shapes. As a result, RNNLG texts will be restricted to syntactic forms which permit expressing such multiple predications of the same entity e.g., subject relative clause, VP and sentence coordination etc. In contrast, the trees extracted by the WEBNLG content selection procedure may be of depth five and therefore allow for further syntactic constructs such as object relative clause and passive participials (cf. Figure 1).

We can show this empirically as well that WEBNLG is far more diverse than RNNLG in terms of input shapes. The RNNLG dataset has only 6 distinct shapes and all of them are of depth 1, i.e., all (attribute, value) pairs in an input are siblings to each other. In contrast, the WEBNLG dataset has 58 distinct shapes, out of which only 7 shapes are with depth 1, all others have depth more than 1 and they cover 49.6% of all inputs.

Text Comparison

Table 4 gives some statistics about the texts contained in each dataset.

( The size and the content of the vocabulary is another important factor in ensuring the learning of wide coverage generators. While a large vocabulary makes the learning problem harder, it also allows for larger coverage. WEBNLG exhibits a higher corrected type-token ratio (CTTR), which indicates greater lexical variety, and higher lexical sophistication (LS). Lexical sophistication measures the proportion of relatively unusual or advanced word types in the text. In practice, LS is the proportion of lexical word types (lemma) which are not in the list of 2,000 most frequent words generated from the British National Corpus11 . Typetoken ratio (TTR) is a measure of diversity defined as the ratio of the number of word types to the number of words in a text. To address the fact that this ratio tends to decrease with the size of the corpus, corrected TTR can be used to control for corpus size. It is defined as T /

√

2N , where T is the number of types and N the number of tokens.

Overall, the results shown in Table 4 indicate that WEBNLG texts are both lexically more diverse (higher corrected type/token ratio) and more sophisticated (higher proportion of unfrequent words) than RNNLG's. They also show a proportionately larger vocabulary for WEBNLG (2992 types for 290479 tokens in WEBNLG against 3524 types for 531871 tokens in RNNLG).

Neural Generation

Richer and more varied datasets are harder to learn from. As a proof-of-concept study of the comparative difficulty of the two datasets with respect to machine learning, we compare the performance of a sequence-to-sequence model for generation on both datasets. In particular, we use a multilayered sequence-to-sequence model with an attention mechanism [START_REF] Vinyals | Grammar as a foreign language[END_REF]. 12 The model was trained with 3 layers of 512 units each. To allow for a fair comparison, we use a similar amount of data (13K data-text pairs) for both datasets. As RNNLG is bigger in size than WEBNLG, we constructed a balanced sample of RNNLG which included equal number of instances per category (tv, laptop, etc). We use a 3:1:1 ratio for training, developement and testing. The training was done in two delexicalisation modes: fully and name only. In case of fully delexicalisation, all entities were replaced by their generic terms, whereas in name only mode only subjects were modified in that way. For instance, the triple FC Köln manager Peter Stöger was delexicalised as SportsTeam manager Manager in the first mode, and as Sport-sTeam manager Peter Stöger in the second mode. The delexicalisation in sentences was done using the exact match between entities and tokens.

Table 5 shows the perplexity results. In both modes, RNNLG yielded lower scores than WEBNLG. This is inline with the observations made above concerning the higher data diversity, larger vocabulary and more complex texts of WEBNLG. Similary, the BLEU score of the generated sentences [START_REF] Papineni | BLEU: a Method for Automatic Evaluation of Machine Translation[END_REF] is lower for WEBNLG suggesting again a dataset that is more complex and therefore more difficult to learn from.

Conclusion

We presented a framework for building NLG datato-text training corpora from existing knowledge 12 We used the TensorFlow code available at https://github.com/tensorflow/models/ tree/master/tutorials/rnn/translate.

Alternatively, we could have used [START_REF] Wen | Multidomain Neural Network Language Generation for Spoken Dialogue Systems[END_REF]'s implementation which is optimised for generation. However the code is geared toward dialog acts and modifying it to handle RDF triples is non trivial. Since the comparison aims at examining the relative performance of the same neural network on the two datasets, we used the tensor flow implementation instead. bases. One feature of our framework is that datasets created using this framework can be used for training and testing KB verbalisers an in particular, verbalisers for RDF knowledge bases. Following the development of the semantic web, many large scale datasets are encoded in the RDF language (e.g., MusicBrainz, FOAF, LinkedGeoData) and official institutions13 increasingly publish their data in this format. In this context, our framework is useful both for creating training data from RDF KB verbalisers and to increase the number of datasets available for training and testing NLG.

Another important feature of our framework is that it permits creating semantically and linguistically diverse datasets which should support the learning of lexically and syntactically, wide coverage micro-planners. We applied our framework to DBpedia data and showed that although twice smaller than the largest corpora currently available for training data-to-text microplanners, the resulting dataset is more semantically and linguistically diverse. Despite the disparity in size, the number of attributes is comparable in the two datasets. The ratio between input and input patterns is five times lower in our dataset thereby making learning harder but also diminishing the risk of overfitting and providing for wider linguistic coverage. Conversely, the ratio of text per input is twice higher thereby providing better support for learning paraphrases.

We are currently working on further extending the WEBNLG dataset and once completed, will make it available as part of a shared task for evaluating data-to-text micro-planners. While we only report on a dataset developed using 6 DBpedia categories, we have collected content for 14 further categories using the content selection procedure described in Section 3 and will collect the corresponding texts using our selective crowdsourcing procedure.

Recently, several sequence-to-sequence models have been proposed for generation. Our exper-iments suggest that these are not optimal when it comes to generate linguistically complex texts from rich data. More generally, they indicate that the data-to-text corpora built by our framework are challenging for such models. We hope that the WEBNLG dataset which we will make available in the shared task will drive the deep learning community to take up this new challenge and work on the development of neural generators that can handle the generation of linguistically rich texts.

  in E. She worked as an engineer.S2.2A was born in E and worked as an engineer.

Figure 1 :

 1 Figure 1: Input Shape and Linguistic Structures (A = Susan Helms, B = STS 78, C = NASA, D = engineer, E = Charlotte, North Carolina).

Figure 2 :

 2 Figure 2: Extracting Data Units from DBPedia

(

Table 1 :

 1 Data Statistics from content selection (A:Astronaut, B:Building, M:Monument, U:University, W:Written work, S:Sports team )

	Category	A	B	M	U	S	W
	#Inputs	663 1220 333 508 1137 1207
	#I. Patterns 546	369 300 432	184	277
	#Properties	38	46	30	41	32	50
	#Entities	74	278	47	75	264	224

Table 2 :

 2 Text Statistics from crowdsourcing (min/max/avg).

	# Triples	1	2	3	4	5	6	7
	# Tokens	4/30/10.48 11/45/22.97 7/37/16.96 17/60/36.38 14/53/29.61 29/80/49.14 24/73/42.95
	# Sentences	1/2/1.00	1/4/1.23	1/3/1.02	1/5/2.05	1/4/1.64	1/6/2.85	1/5/2.42

9 https://github.com/shawnwun/RNNLG

  4) a. ('108 St Georges Terrace location Perth', 'Perth country Australia', '108 St Georges Terrace start-

	Date 1981')
	country, location, startDate
	108 St. Georges Terrace is located in Perth, Aus-
	tralia. Its construction began in 1981.
	passive, apposition, deverbal nominal
	b. ('William Anders	selection	1963',
	'William Anders birthPlace British Hong Kong',
	'William Anders almaMater "AFIT, M.S. 1962"')
	almaMater, birthPlace, selection
	William Anders was born in British Hong Kong,
	graduated from AFIT in 1962, and joined NASA in
	1963.
	passive, VP coordination, VP coordination

Table 3 :

 3 Comparing DBPNLG and RNN. Attributes are properties in RDF triples or slots in dialog acts.

		DbpNLG RNNLG
	Nb. Input	5068	22225
	Nb. Data-Text Pairs	13339	30842
	Nb. Domains	6	4
	Nb. Attributes	172	108
	Nb. Input Patterns	2108	2155
	Nb. Input / Nb Input Pattern	2.40	10.31
	Nb. Input Shapes	58	6

Table 4 :

 4 As illustrated by the contrast between example 5 and 6 above, text length (number of tokens per text) and the number of sentences per text are strong indicators of the complexity of the generation task. We use the Stanford Part-Of-Speech Tagger and Parser version 3.5.2 (date 2015-04-20) to tokenize and to perform sentence segmentation on text. As shown in Table4, WEBNLG's texts are longer both in terms of tokens and in terms of number of sentences per text. Another difference between the two datasets is that WEBNLG contains a higher number of text per input thereby providing a better basis for learning paraphrases. Text Statistics from WEBNLG and RNNLG.

	5) a. (Alan Bean birthDate "1932-03-15")
	Alan Bean was born on March 15, 1932
	(6) a. ('Alan Bean	nationality	United States',
	'Alan Bean birthDate "1932-03-15"', 'Alan Bean
	almaMater "UT Austin, B.S. 1955"', 'Alan Bean
	birthPlace Wheeler, Texas', 'Alan Bean selection
	1963')
	Alan Bean was an American astronaut, born on
	March 15, 1932 in Wheeler, Texas. He received
	a Bachelor of Science degree at the University of
	Texas at Austin in 1955 and was chosen by NASA
	in 1963.

Table 5 :

 5 Perplexity and BLEU scores.

		Delexicalisation Mode DbpNLG RNNLG
	Perplexity	Fully Name only	27.41 25.39	17.42 23.93
	BLEU	Fully Name only	0.19 0.10	0.26 0.27

For instance, the input structures made available by the shallow track of the SR task contain all the lemmas present in the corresponding text. In this case, the generation task is limited to determining (i) the linear ordering and (ii) the full form of the word in the input.

https://musicbrainz.org/

http://www.foaf-project.org/

http://linkedgeodata.org/

http://wiki.dbpedia.org/ dbpedia-dataset-version-2015-10

An entity graph for some entity e is a graph obtained by traversing the DBPedia graph starting in e and stopping at depth five.

http://www.crowdflower.com

We compute LS and CTTR using the Lexical Complexity Analyzer developed by[START_REF] Lu | The relationship of lexical richness to the quality of ESL learners' oral narratives[END_REF].

See http://museum-api.pbworks.com for examples.