Sorin Olaru

Hiroshi Ito

Characterization of ultimate bounds for systems with state-dependent disturbances

Keywords:

This paper pursues a framework of set characterization of dynamical systems with state-dependent disturbances. It aims to propose a new approach to analysis and design of nonlinear systems involving non-differentiability and asymmetric components which hamper application and effectiveness of local linearization methods. Several characterizations of ultimate bounds are developed.The utility of shifting the fix point is formulated as a parametrization of the ultimate bounds.

I. INTRODUCTION

The disturbance invariant sets for linear systems with static bounds on the additive disturbances have been characterized in the '90s [START_REF] Kuntsevich | Minimal invariant sets of dynamic systems with bounded disturbances[END_REF], [START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF]. The particular set known as "minimal robust positive invariant set" received an important attention [START_REF] Hirata | -feasible approximation of the state reachable set for discrete-time systems[END_REF]- [START_REF] Ong | The minimal disturbance invariant set: Outer approximations via its partial sums[END_REF] with applications in several analysis and control design problems involving set-theoretic approaches [START_REF] Blanchini | Set-theoretic methods in control[END_REF], fault detection [START_REF] Reppa | Sensor fault diagnosis[END_REF] or robust predictive control [START_REF] Mayne | Robust model predictive control of constrained linear systems with bounded disturbances[END_REF], [START_REF] Rawlings | Model predictive control: Theory and design[END_REF] to mention only a few. The closely related concept of ultimate bounds [START_REF] Khalil | Nonlinear systems[END_REF] has been used for the characterization of dynamical systems in the presence of non-vanishing perturbation. It proved to be instrumental in the study of linear systems with bounded disturbances for at least two decades [START_REF] Blanchini | Ultimate boundedness control for uncertain discrete-time systems via set-induced Lyapunov functions[END_REF]. There are effective computational methods for the characterization of ultimate bounds for linear dynamics with (state-dependent) bounds for the disturbances [START_REF] Kofman | A systematic method to obtain ultimate bounds for perturbed systems[END_REF], [START_REF] Olaru | Ultimate bounds and robust invariant sets for linear systems with state-dependent disturbances[END_REF]. An interpretation of the ultimate bounds is given by the input-to-state stability (ISS) [START_REF] Sontag | Input to state stability: Basic concepts and results[END_REF], [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF].

The present paper deals with discrete-time nonlinear systems affected by disturbance inputs with state-dependent bounds. These disturbances are allowed to be arbitrary as long as they are contained in sets which are bounded point-wise. This includes asymmetrically non-Lipschitz state-dependent This work was initiated during the visit of the first author at the Kyushu Institute of Technology. The support of the Matsumae International Foundation is gratefully acknowledged. The first author acknowledges the support via the CNCS -UEFISCDI grant, number PN-III-P1-1.1-TE-2016-0862, MOSCBIOS, within PNCDI III. 1 Laboratoire des Signaux et Systèmes, CentraleSupélec, Université Paris Saclay, 3 rue Joliot Curie, 91190, Gif-sur-Yvette, France (sorin.olaru@centralesupelec.fr) 2 Department of Systems Design and Informatics, Kyushu Institute of Technology, Iizuka 820-8502, Japan (e-mail: hiroshi@ces.kyutech.ac.jp) disturbance whose systematic treatment is non-trivial with the existing techniques. Small-gain techniques are popular for verifying stability of equilibria of systems in the presence of state-dependent disturbances [START_REF] Jiang | Small-gain theorem for ISS systems and applications[END_REF], [START_REF] Ito | Utility of iISS in composing lyapunov functions for interconnections[END_REF]. However, their standard formulations by themselves do not readily provide sharp estimates of ultimate bounds. The main objective of the present paper is to put a light on the usefulness of numerical computations of ultimate bounds for linear systems with point-wise bounded sets of disturbances in the study of nonlinear dynamics. As expected, the linear part offers only local information on the ultimate boundedness. This paper presents a parametrization of these local bounds in terms of the linear dynamics, topology of the disturbance set and fixed-points, which will play an important role in the global analysis and design of nonlinear control systems.

II. PRELIMINARY NOTIONS

The Minkowski sum of two given sets S, P ⊂ R n is described by S ⊕ P = {x + y|x ∈ S, y ∈ P }. The norm of a finite dimensional vector x ∈ R n is denoted |x| and the epsilon ball centered at the origin is represented by B = {x ∈ R n : |x| ≤ } . The notation P(R n ) := {S|S ⊂ R n } represents the power set of R n in general, and P cl (R n ) is the set of all closed subsets of R n , including the empty set:

P cl (R n ) := S ∈ P(R n )|S = S or S = ∅ . Definition 1 A set S ⊂ R n is star-shaped at x ∈ S if for any point x ∈ S and 0 ≤ β ≤ 1 it holds that βx + (1 -β)x ∈ S. The kernel of S ⊂ R n denoted by kern(S) is defined as: kern(S) = {x ∈ S : βx + (1 -β)x ∈ S, ∀x ∈ S, β ∈ [0, 1]} .
Whenever the center x of a star-shaped set S is relevant, the notation S x is used. S x(R n ) denotes the set of closed starshaped sets S x, containing x in their kernel. The Minkowski function associated to a set S ∈ S 0 (R n ) is defined as H S (x) :

R n → R + with:

H S (x) = inf {α ∈ R + : x ∈ αS} (1)
Definition 2 A set-valued map F : R n → P(R m ) is called increasing from x ∈ R n if for all x ∈ R n it holds that F (x + λ 1 (x -x)) ⊆ F (x + λ 2 (x -x)) for 0 ≤ λ 1 ≤ λ 2 .
Proposition 1 For any set-valued map F : R n → P(R m ), there exists a companion set-valued map increasing from x ∈ R n defined as Fx : R n → P(R m ) with

Fx (x) = 0≤λ≤1 F (x + λ(x -x)) (2)
Example 1 Consider F : R → P(R) defined by:

F (x) = -|x| + sin πx 2 , |x| + sin πx 2 (3)
The graph of F (.) as depicted in blue in Figure 1 illustrates that this is not increasing from 0. The union of the black and the blue envelopes presents the companion increasing setvalued map F0 (.) derived from F (.) based on (2).

Consider a discrete-time system:

x(k + 1) = f (x(k)) + w(k), (4)
where x(k) ∈ R n is the state vector and w(k) ∈ R n is a disturbance input at the time k ∈ Z + . The function f : R n → R n admits the origin as equilibrium in the disturbance-free case f (0) = 0.

Assumption 1

The system (4) is internally stable, in the sense that the only equilibrium is globally asymptotically stable in the disturbance-free case, i.e., whenever w(k) ≡ 0, ∀k ∈ Z + .

For the system (4), the signal w(k) ∈ R n representing the additive disturbance is supposed to belong, at each sampling time, to a set described by a set-valued map: w(k) ∈ W (x(k)) with W (.) defined as W : R n → P cl (R n ) and satisfying the following point-wise boundedness:

Assumption 2 With the notation w(x) = sup{|w| : w ∈ W (x)}, it is considered that w(x) < ∞ for each x ∈ R n .
For completeness, the following convention is used:

sup{|w| : w ∈ W = ∅} = 0.
The point-wise boundedness excludes the case where x(t) explodes in finite time. The following definition of boundedness will be used: Definition 3 The solution x of (4) is ultimately bounded 1 if there exists a bounded set S ⊂ R n , possibly dependent on x 0 , and a nonnegative integer T (x 0 , S) < ∞, such that x(k) ∈ S for all k ≥ T (x 0 , S) and for all x 0 ∈ R n .

The paper proposes a method to compute ultimate bounds for the dynamics (4) and clarifies their properties in a set theoretic framework. In this context, it is important that the disturbance w(k) is described by the state-dependent set, i.e., a set-valued map W (x(k)). This allows w(k) to describe an endogenous signal in (4).

III. NONLINEARITIES REPRESENTATION

The theory of ultimate bounds for linear time-invariant (LTI) dynamical systems affected by point-wise bounded disturbances is relatively mature. The analysis of LTI systems prove to be used for the study of the general system (4) by starting from the simple observation that:

x(k + 1) = f (x(k)) + w(k) (5) = Ax(x) + (f (x(k)) -Ax(k) + w(k))) w(k) , (6)
with w(k) ∈ W (k) which contains, on top of the additive uncertainty, the mismatch between the linear and the nonlinear model. This can be achieved via the transformation of the state-dependent disturbance:

W (x(k)) = W (x(k)) ⊕ {f (x(k)) -Ax(k)} . (7)
Is worth to be mentioned that both f (.) and W (.) can be asymmetric and non-Lypschitz and consequently this will be the case for the resulting mapping W (.).

Example 2 Consider the dynamics (4) with

f (x) = x 3 -0.2x(x-2) 2 x 3 -0.2(x-8)(x-2) 2 for x ∈ [-3, 3] x/2 + 3 for x / ∈ [-3, 3] (8)
1 The attribute robustly is to be added to these notions if the properties hold for any w ∈ W (x)

f(x) ⊕ W(x) f(x) ⊕ W(x) f(x)
(k) ∈ -|x(k)| + sin( πx(k) 2 ), |x(k)| + sin( πx(k) 2 ) W(x(k))
, corresponding to (3). Figure 2 shows that the nonlinear map f (•) + w(•) in the neighbourhood of the origin substantially differs from the local linear approximation, i.e., the Jacobian of f at zero. Figure 3 illustrates the uncertainty around the nonlinear model (4) as measured by the state-dependent bound and the increasing-from-0 counterpart. Figure 4 shows the poor global quality when Jacobian linearization is used for A in (6). Interestingly, Figure 5 shows that choosing A = 0.5, reduces the impact on the increasing-from-0 disturbance set. Despite the mismatch around the equilibrium, the uncertainty envelope associated with A = 0.5 is sharp as shown in Figure 6.

This example illustrates that the matrix A should not be conceived only as a local approximation (via the Jacobi linearization for example) of the (stable) nonlinear mapping x

⊕ W f(x) -δf δx x=0 x ⊕ W (x) f(x) ⊕ W (x) δf δx x=0
x Fig. 4. Mapping using a Jacobi linearization vs. the increasing from 0 counterpart.

0.5x ⊕ W (f(x) -0.5x ⊕ W(x)) f(x) ⊕ W(W(x))
Fig. 6. Comparison of the set valued mapping using increasing from 0 set disturbances. Original nonlinear system vs. linear approximation of the dynamics.

f (.). The choice of the linear part represents an important degree of freedom which can be exploited as long as the model mismatch (x) = f (x) -Ax is incorporated in the disturbance set for all x ∈ R n . The state-dependent bounding W (.) defined in [START_REF] Reppa | Sensor fault diagnosis[END_REF] represents the envelope of the mismatch.

The freedom of A can be used to reduce globally the impact on the uncertainty.

A. Linear systems with bounded additive disturbances Consider the linear system with additive disturbances

x(k + 1) = Ax(k) + w(k), (9)
with w(k) ∈ S with S ∈ S 0 (R n ), a star-shaped set at the origin and Assumption 1 holds true for f (x(k)) = Ax(k).

For the dynamics (9) there exists an invariant set 2 :

Ω A (S) := ∞ i=0 A i S ( 10
)
containing a collection of initial states for which the future trajectories remain within the same set and which satisfy: AΩ A (S) ⊕ S = S. Independent of the star-shaped properties of the argument, the relationship (10) defines a mapping

Ω A (.) : P cl (R n ) → P cl (R n ). (11)
Theorem 1 For any set S ∈ S 0 (R n ) there exists a starshaped set Ω A (S) ⊕ B ∈ S 0 (R n ) which represents a robust ultimate bounded set for the system (9). This robust ultimate bounded is not dependent on the initial state.

Proof: The start-shaped property follows from the fact that the Minkowski sum is a closed operation over the class of starshaped sets (see [START_REF] Olaru | Positive invariant sets for fault tolerant multisensor control schemes[END_REF]). On one hand, the ball B is convex, contains the origin and thus is star-shaped at the origin. On the other hand Ω A (S) is an infinite Minkowski sum of star shaped sets. The set Ω A (S) is positive invariant with respect to [START_REF] Rawlings | Model predictive control: Theory and design[END_REF] and by consequence the trajectories initiated from Ω A (S) will remain in Ω A (S) at all future instances according to [START_REF] Khalil | Nonlinear systems[END_REF]. This proves the ultimate boundedness for the initial points x 0 ∈ Ω A (S). For the initial states x 0 / ∈ Ω A (S) it is sufficient to observe that the trajectories are representing a superposition of two trajectories

x 1 (k + 1) = Ax 1 (k) (12)
x 2 (k + 1) = Ax 2 (k) + w(k) (13)
initiated at x 1 (0) and x 2 (0) respectively and satisfying x 0 = x 1 (0) + x 2 (0). While x 2 (k) ∈ Ω A (S), ∀k ≥ 0 in virtue of the positive invariance properties, there exists a nonnegative integer T < ∞ such that x 1 (k) ∈ B , ∀k ≥ T and for any fixed > 0 according to Assumption 1. The proof of ultimate boundedness is complete.

Based on the ultimate bounds obtained for disturbances within the star-shaped set S ⊂ S 0 (R n ), the homogeneity properties of the dynamics (9) can be exploited to define:

Ω A (αS) × (αS) = (αΩ A (S)) × (αS) = α (Ω A (S) × S)
where the ultimate-bound set (1st block) and the disturbance set (2nd block) are scaled by alpha. This leads to a parameterized family of ultimate bounds:

F A (α, S) : R + × S 0 (R n ) → S 0 (R n ) × P 0 (R n ) F A (α, S) = α (Ω A (S) × S) (14)
This parametrization simply says that given a Schur matrix A, for any star shaped disturbance one has a unique ultimate bounded set with respect to the LTI dynamics. The scaling of the disturbance leads to a scaling of the ultimate bound.

B. Nonlinear systems with state-dependent disturbances

The link between the parameterized family of ultimate bounds for LTI systems and the ultimate bounds for the nonlinear dynamics (4) can be drawn via the transformation [START_REF] Reppa | Sensor fault diagnosis[END_REF] by defining the function:

G A (α, S) : R + × S 0 (R n ) → S 0 (R n ) × P cl (R n ) G A (α, S) = (αΩ A (S)) × W (αΩ A (S)) (15)
and its comparison with the counterpart in [START_REF] Sontag | Input to state stability: Basic concepts and results[END_REF].

Theorem 2 Consider a star-shaped-set S ∈ S 0 (R n ). The set

Ω A (S) ⊕ B ∈ S 0 (R n ) is an ultimate bound for (4) if F A (α, S) ⊇ G A (α, S), ∀α ≥ 1. ( 16
)
Proof: The set S being fixed, it characterizes uniquely the set Ω(S) and consequently the ultimate bounds for a LTI system in terms of Ω(S)⊕B . In the same time, by multiplying with the scalar α ∈ R + , one obtains the set αΩ(S) which preserves the invariance and leads to ultimate-boundedness properties for an LTI systems with additive disturbances within αS. With respect to the nonlinear system (4), the set αΩ(S) ⊕ B represent a candidate ultimate bound. By writing the nonlinear dynamics in the equivalent form [START_REF] Blanchini | Set-theoretic methods in control[END_REF], the link to the LTI case is established and the validity of the ultimate bounds is related to the covering of the admissible disturbance set W (x) by αS with an appropriate (state-dependent) scaling α. Two cases need to be treated in order to prove the ultimate boundedness. Case 1: The invariance of Ω A (S) is guaranteed if W (x) ⊆ S, ∀x ∈ Ω A (S). This last inclusion holds if W (Ω A (S)) ⊆ S and is equivalent with F A (1, S) ⊇ G A (1, S), i.e., the limit case (α = 1) in ( 16). It follows that for the initial states x 0 ∈ Ω A (S) the set Ω A (S) itself represent an ultimate bound.

Case 2: For any initial states x 0 / ∈ Ω A (S), using the fact that the origin is a point in the interior of S, there exists α(x 0 ) > 1 such that x 0 ∈ α(x 0 )Ω A (S). The level of admissible additive disturbances in this particular point of the state space is represented by a set which is increasing from the origin (or more precisely from Ω A (S)). As long as the level of disturbances satisfies W (x) ⊆ α(x)S, the convergence towards the ultimate bound is guaranteed based on the LTI model contractiveness. The condition F A (α, S) ⊇ G A (α, S) resumes this requirement for all α > 1.

Example 3 Consider the system (4) with x(k), w(k

) ∈ R 2 and f (x(k)) = A θ (x(k))x(k) with A θ (x(k)) = 0.75 * cos(θ(x(k))) -sin(θ(x(k))) sin(θ(x(k))) cos(θ(x(k))) , and θ(x(k)) = π 2 + π 0.01+|x(k)|1 . The bounds are W (x) = max{0.1(1+0.1|x 1 |+0.1|x 1 x 2 | 0.2 +0.5 √ x 2 ); 0.9}P.
where P denotes the star-shaped set in Fig. 7 (left). Take A = A θ (0), i.e., A is the Jacobian of f at the origin. A star-shaped ultimate bound can be obtained readily as illustrated on the right of Fig. 7. Theorem 2 guarantees this ultimate bound to represent a ultimate bound for (4) ∀α ≥ 1.

IV. EXTENSIONS

A. Parametrization of ultimate bounds with respect to the fixed-points

Although the focused equilibrium is the origin, the nonlinear state-dependent bounds W (k) does not have to be centered at zero. Indeed, introducing flexibility in choosing the center of the disturbance set can often reduce conservativeness of computed ultimate bounds. This section will point to the structural properties of the parametrization and provide the formal extension to non-zero centered disturbances.

One of the structural properties of the results presented in the previous section is that a given star-shaped set S ∈ S 0 (R n ) bounding the disturbances for LTI dynamics (9) induces a function for admissible state-dependent disturbances:

φ(x) : R n → S 0 (R n ) × S 0 (R n ) (17) φ(x) = F(H Ω A (S) (x), S) (18)
which is increasing from zero. This function, defined for each point in the state space, provides the pair of admissible disturbances and the related ultimate bound.

Although the origin is a fixed point for both the nonlinear system (4) and the linear system (9), the function

γ(x) : R n → S 0 (R n ) × P cl (R n ) (19) γ(x) = G(H Ω A (S) (.), W (Ω A (S))) (20)
is not necessarily increasing from the origin. This makes a major difference between the linear (homogeneous) construction and the original nonlinear form (4) leading to possible conservative results whenever the Theorem 2 is used. The mitigation of a part of this conservatism represents the motivation for introducing a supplementary degree of freedom for the parametrization of the ultimate bounds inherited from the linear dynamical models. The idea will be to relax the hypothesis of a disturbance set centered at the origin and to admit an arbitrary point in the kernel of the star-shaped set.

Consider the generalized counterpart of the function [START_REF] Sontag | Input to state stability: Basic concepts and results[END_REF]:

F A (α, S) : R + × S w(R n ) → S (I-A) -1 w(R n ) × S w(R n ) F A (α, S) = (I -A) -1 w ⊕ αΩ A (S ⊕ {-w}) × ( w ⊕ α(S ⊕ {-w})) (21)
and the generalized function with respect to [START_REF] Jiang | Input-to-state stability for discrete-time nonlinear systems[END_REF]:

G A (α, S) : R + × S w(R n ) → S (I-A) -1 w(R n ) × P cl (R n ) G A (α, S) = (I -A) -1 w ⊕ αΩ A (S ⊕ {-w}) (22) × W (I -A) -1 w ⊕ αΩ A (S w ⊕ {-w})
then the following result resumes the sufficient conditions for the existence of ultimate bounds with respect to the non-linear dynamics.

Theorem 3 Consider S, a star-shaped-set in R n . Ω A (S) ⊕

B is an ultimate bound for (4) if there exists a point w ∈ Int(kern(S)) such that F A (α, S w) ⊇ G A (α, S w), ∀α ≥ 1.

Proof: Similar to Theorem 2. Example 4 In order to illustrate the reduction of conservativeness in the ultimate bound estimation let us consider the system:

x(k + 1) = 0.5x(k) + w(k) (23)
with state-dependent bounds on the disturbance:

-1 ≤ w(x) ≤ 0.5 + 0.5 √ x if x ≤ 0 -0.2 ≤ w(x) ≤ 0.2 + 0.1x if 0 ≤ x ≤ 3 -0.2 ≤ w(x) ≤ 0.1(2 + x + 5 * √ x -3) if x ≥ 3
The parametrization of invariant sets is particularly simple:

F A (α, S) = α ((2S) × S) .
By considering S = [-1, 1], the sufficient condition in Theorem 2 leads to the ultimate bound |x| ≤ 2.618 shown in Fig. 8. By using w = 0.2 in Theorem 3, the symmetry with respect to the origin is relaxed and the ultimate bounds can be improved up to |x| ≤ 2.02 as shown in Fig. 8.

B. Active input design and impact on the ultimate-bounds

Based on the previous discussion, the parametrization can be utilized for active input design. By considering the system with both disturbances and inputs:

x(k + 1) = f (x(k)) + w(k) + ū, (24)
the natural idea is to consider the case where the exogenous signal can be complemented with a feed-forward control w 1 (k) = w(k) + ǔ thus playing an active role in the design of improved ultimate bounds upon the theoretical foundations of the Theorem 2. Finally, once the system trajectory enter the ultimate bounds, the input signal can be updated in order to further adjust the shape of the ultimate bounds thus leading to a feedback scheme w 2 (k) = w(k) + u(k).

To illustrate the concept, consider again Example 4. In the absence of an active input, the system converge towards an ultimate bound presented in the left part of Fig. These design avenues are subject to current developments, the algorithmic part of the developments being of primer importance, according to the topology to the set-valued maps in Assumption 2. For example, to achieve a desired small ultimate bound, a judicious switching procedure is needed, according to the assumptions, in order to make sure that equilibria are not in the exterior of the ultimate set in the presence of w i .

V. CONCLUSIONS

A novel framework for the analysis of systems affected by additive state-dependent disturbances has been introduced based on set-theoretic notions. It aims to relax the assumptions on the bounds and mappings as for example to deal with systems which have asymmetric nonlinearities. The basic principle is to make use of a linear nominal part for which the ultimate bounds exist. The ultimate bounds of the whole nonlinear system are parameterized in terms of shapes and scaling factors of the disturbances representing nonlinearities. It is worth to be mentioned that star-shaped sets are employed within the parametrization thus avoiding the usual convexity assumptions of the linear analysis. Several sufficient conditions are presented for the characterization of ultimate bounds, with details on the degrees of freedom within the parametrization. The approach is considered attractive for the design of openloop or closed-loop excitation signals to improve the ultimate bounds.

Fig. 1 .

 1 Fig. 1. Example of the set valued mapping F (.) in (3) and the increasing from 0 counterpart F0 (.) constructed upon[START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF]

Fig. 2 .

 2 Fig. 2. Disturbance-free mapping vs. the mapping with uncertainty

Fig. 3 .

 3 Fig. 3. Mapping with uncertainty vs. the increasing from 0 counterpart

Fig. 5 .

 5 Fig.5. Mapping using a linear approximation vs. the increasing from 0 counterpart.

Fig. 7 .

 7 Fig. 7. A star-shaped set (left), a ultimate bound (right, red) and trajectories with random disturbances (right, colored lines)

Fig. 8 .

 8 Fig. 8. Validation of the sufficient condition in Theorem 2 for F A (α, S) depicted in blue, based on a set centered at the origin S = [-1, 1] ∈ S 0 (R n ). The state dependent bounds are depicted in red.

Fig. 9 .

 9 Fig. 9. Validation of the sufficient condition in Theorem 3 for F A (α, S) depicted in blue, based on a set S = [-0.8, 1.2] ∈ S 0.2 (R n ). The state dependent bounds are depicted in red.

Fig. 10 .

 10 Fig. 10. Superposition of 1000 trajectories of (23) generated with different initial conditions and random disturbance realizations within the bounds. Left: absence of an active control signal u(k) = 0, ∀k. Right: piecewise constant active input (25).

10

 10

1

  for 0 ≤ k ≤ 30 0.5 for 30 ≤ k ≤ 80 0.18 for 80 ≤ k (25) leads to the result presented in the right hand side of Fig. 10 with obvious improvements in terms of ultimate bounds.

Denoted minimal robust positive invariant set, see[START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF] for further definitions and related characterizations.


Charles Riondet

Foppiano Luca

Almanach

Anne Baillot

When engineering meets History

While doing research in digital based context, historians often face the same kind of problem: how to translate their research questions in machine readable format? Find out how to annotate efficiently their material and which techniques/methods to apply are technical steps that tend to become everyday tasks for many Humanities researchers. The main issue is that their questions are too specific to simply apply generic tools and, on the other hand, adapting such tools may require technical abilities that humanists hardly ever have. In such cases, interacting with experts of different backgrounds (e.g. information technologies, developers) could be difficult due to different views, approach to the problem, way of reasoning, etc. In this paper is proposed a methodology, and the research use case on which it is tested, where the close collaboration between historians and engineers allows for a better understanding of the needs of each party, and helps the creation of customizable tools capable of being used in many different contexts and domains. The use-case is to study and compare entities corresponding to the actors of conflicts in a corpus of personal diaries written during World War II. The discourses analyzed are characterized by multiple and very peculiar terminologies, often very ambiguous (like pejorative nicknames). The challenge is to apply generic tools (like named-entity recognition tool -NERD, a POS tagger) and a domain specific dictionary to this corpus, trying not to cross the thin line between generic customization and ad hoc development.

Full text

Introduction While doing research in digital based context, historians often face the same kind of problem: how to translate their research questions in machine readable format? Find out how to annotate efficiently their material and which techniques/methods to apply are technical steps that tend to become everyday tasks for many Humanities researchers. The main issue is that their questions are too specific to simply apply generic tools and, on the other hand, adapting such tools may require technical abilities that humanists hardly ever have. In such cases, interacting with experts of different backgrounds (e.g. information technologies, developers) could be difficult due to different views, approach to the problem, way of reasoning, etc. In this paper is proposed a methodology, and the research use case on which it is tested, where the close collaboration between historians and engineers allows for a better understanding of the needs of each party, and helps the creation of customizable tools capable of being used in many different contexts and domains. The use-case is to study and compare entities corresponding to the actors of conflicts in a corpus of personal diaries written during World War II. The discourses analyzed are characterized by multiple and very peculiar terminologies, often very ambiguous (like pejorative nicknames). The challenge is to apply generic tools (like named-entity recognition tool -NERD, a POS tagger) and a domain specific dictionary to this corpus, trying not to cross the thin line between generic customization and ad hoc development.

Context

The work presented in this paper is a case study made possible by the very transdisciplinary nature of the Inria ALMAnaCH team. ALMAnaCH means Automatic Language Modelling and Analysis & Computational Humanities and is a joint team between Inria and EPHE (École pratique des hautes études). As a matter of fact, it is a strange mixture of people with different skills working side by side: computer engineering people specialized in data mining and information extraction, NLP experts in semantic and syntactic analysis, parsing, etc., Digital Humanities people (with History and Literature background) focusing more on data modelling, textual analysis, digital philology. Why not combining all the skills available around? The original situation of the ALMAnaCH team was seen as an opportunity to learn new things and be creative, even if the different partners involved in this project were not at first meant to work together, and were involved in different projects. The first tries were very empirical and rather unfruitful. Usually, the person with the data is the trigger, and the risk is that the computer science expert might be considered as a simple service provider. In the present case, working alongside on a daily basis allowed the team to reshape this collaboration as a reciprocal enrichment. For historians, it is the opportunity to improve the data and consider new questions. For data mining specialists, it is a way to improve tools, workflows and find new use cases. As a final result, the ambition is to provide a sustainable data mining toolbox generic enough to answer a great variety of Humanities research questions.

Research question

The context of war surely has a strong influence on the language (Antoine, Martin, 1999, p. 3) and sometimes the occasion for lexical creations (Gérard, Lacoste, 2014). Personal writings testify this influence maybe better than any other type of text, because they offer less filtered corpora and cover, at least in the case of WWI and WWII, a diverse range of socio-economic situations, locations, age, gender, etc. The diaristic form also allows for very precise diachronic analysis. In such texts, determining how the Self and the Other are being represented, and how this representation evolve, can offer interesting lines for thoughts. These mentions reveal often structural elements of an individual (or a group) in a given time, how they see themselves, as individuals, as a group, as opponents, winners, losers, etc. When compared to the course of the war, it also allows for the identification of external elements that influence the language. In the present case, the analysis is limited to the mentions of actors of WWII in French personal writings, more precisely, diaries. What is the Other in this context? First, it is the enemy, the other nation/nations the writers are fighting against (themselves of their group, their nation). The most obvious case is to find how French see the German. But the idea is to broaden the study to all the mentions of nations, organisations, persons, person types, trying to determine the complete panorama of these witnesses and/or actors.

An important parallel goal is to bring together different tools, set up a solid editorial and hermeneutical workflow and make it available for further research. Ideally, this workflow would allow researchers to process historical texts from digitization to publication, via OCR, annotation, edition, etc. The digitization and OCR parts are left aside, to focus on the annotation task. All instances appearing in the discourse are modelized and brought in relation to one another. This corpus of annotations is the foundation for both synchronic and diachronic analyses. In other words, the future development of this framework will make possible to analyse the variations of the mentions over the corpus and, because the material -diaries -are chronological in essence, over time. Variations can be semantic evolutions, variations in spelling, or appearance and disappearance of a mention.

Methodology

In order to tackle the research question in a structured way, two main tasks were defined: the recognition of the actors and the extraction of the related structural discourse (actions or qualifier). Actors, either "the others", or "ourselves" are usually people, locations or institution. As these tokens appear in the text as Named Entities the more reasonable approach is the use of a Named Entity Recognition (NER) tool. The NER task "is a subtask of information extraction that seeks to locate and classify named entities (a real-world object, such as persons, locations, organizations, products, etc, that can be denoted with a proper name) in text (..)" (Jurafsky et al.) These Named entities are classified in predefined classes, such as the names of persons, organizations, locations, etc.

For each actor mention identified in the text, the secondary task is to collect all meaningful tokens, usually verbs, adjectives and nominal modifiers, linked to it.. These are the tokens carrying information (sentiment, judgement, point of view of the writer, etc.) about the actors and they often spanning towards extremes depending period, location and social origin of the author. The approach for the recognition of structural discourse is based on the part of speech tagging (POST), which is "is the process of assigning a part-of-speech or other lexical class marker to each word in a corpus". Traditional grammar classifies words based on eight parts of speech: verb, noun, adjective, pronoun, preposition, adverb, conjunction and the interjection. According to [Jurafsky et al.] the part of speech for a word gives a significant amount of information about the word and its neighbors.

These two tasks are combined in the following workflow:

The main components of this schema are:

-entity-fishing1 (NERD): tool performing the entity recognition (NER) and disambiguation against wikipedia and wikidata -UDPipe2 (POST): tool trained to perform Universal Dependency parsing and part of speech tagging.

Assuming to have input as text (but it could be a PDF document as well) it is crunched in parallel by POST and NERD, the result is further post-processed and combined to obtain the annotated text. The annotations obtained in output are composed by the actor and the qualifiers.

Entity fishing

Entity fishing is a tool written by Patrice Lopez3 and released open source under the licence Apache 2.0. It is also more generically named (N)ERD that stands for (Named) Entities Recognition and Disambiguation, Named is between parentheses because the obtained entities might not necessarily Named Entities but just mentions. In addition the found mentions are matched against Wikipedia and Wikidata to find the article related to the real entity. Wikipedia/Wikidata are used for disambiguation because they are the largest and most complete knowledge bases available nowadays.

This task is called disambiguation or entity-linking and for certain cases can be quite subtle, as illustrated in the figure below where the ambiguities can be only resolved by the context itself:

In this case, it is possible to choose the right article for German Army only by reading the whole text and understand whether it's talking about the first or second World War.

UDPipe

UDPipe is a trainable pipeline for tokenization, tagging, lemmatization and dependency parsing. This tool is used to obtain the dependency graph of the sentence combined with the Part-of-Speech tagging of each token. The dependency graph represent each sentence as hierarchical tree having the verb as root. Each token is connected to one head (a token closer to the root) and one or more more descendents tokens.

Thanks to this approach, it is possible to discover relations between various components of the sentence. In the example in figure, the entity bourgeois is modified by the descendant adjective gauliste.

The corpus

This workflow is tested with a rather small corpus: two diaries written in French by persons living in Paris during WW2. They report two different personal experiences.

The main text of the corpus is the Journal de Léo Hamon (Archives nationales, 72AJ42). Léo Hamon (1908Hamon ( -1993) ) was a French lawyer of Russian origin, and one of the leaders of the Parisian Resistance. His diary relates his underground daily life, reports on his comments on the course of the war, meetings he attended, the organization of the Resistance and on the preparation of the seizure of power in Paris (Riondet, 2016). Another diary used is the Journal d'Henri Chabasse (Musée de la Résistance nationale, 13/3907b). Chabasse is a nationalist middle-class Parisian, not involved in the Resistance nor in the Collaboration. His diary reports daily life but contain mostly comments on the course of the war and the French political situation, from the D-Day to autumn 1944 and an additional entry related to the Hiroshima bombing.

Specific dictionary

These two diaries contains a peculiar vocabulary, that was known at the time it was written. Therefore, numerous entities are difficult to recognize for a generic Named-entity recognition system. Many context based expressions are present in both texts. For example, "souris grises" means "grey mice", but in the context of WWII is a nickname to designate the German army female auxiliaries. Such expression was commonly used by parisians talking about the situation during WWII and might appear in other sources.

Another problem is the use of a different internal terminology for each diary. For instance, Léo Hamon uses a very specific term when mentioning the members of the French communist party: "les cocs", from the pejorative diminutive "coco", itself shorten.

There are other cases that may seem less important but required to be taken into account to avoid losing important information. For example unnormalized spelling (e.g.: Gaulisme for Gaullisme) or metonymies (e.g.: Vichy for Régime de Vichy and not Vichy town).

Due to these particularities, even a complete source like Wikipedia doesn't contains everything. Therefore it is necessary to create a specific domain dictionary to record all the possible terminology variations and link them the concept they represent. This dictionary is based on other domain dictionaries like the Dictionnaire historique de la Résistance (Marcot et al., 2006), other scholarly work (Vast, 2008) and on manual curation. The dictionary is modeled with the XML format TEI-TBX, a combination of two standards, Text Encoding Initiative (TEI)4 and the TermBase eXchange (TBX)5 . This format offers the possibility to cluster all the mentions related to a concept and link concepts between one another (Pernes, Romary, Warburton, 2017). As it is a standard, the resource created is sustainable.

<conceptEntry xml:id="c_1067"> <langSec xml:lang="fr"> <form type="lemma"> <orth>Gaullisme</orth> </form> <form type="variant"> <orth>Gaulisme</orth> </form> </langSec>

</conceptEntry>

The concept "Gaullisme" and its variant "Gaulisme" expressed in TEI-TBX.

Workflow

In this section is described the implemented workflow that combines all the tasks described above:

-mentions extraction and entity disambiguation against Wikipedia/Wikidata -specific domain entities extraction using the dictionary -dependency parsing and POS tagging

The result is composed of the entities representing the actors of the text linked to their respective qualifiers. For example:

The first step is the analysis of the text and the extraction of named entities and mentions. The extracted entities are then filtered by Named Entity classes (Entity Fishing cover up to 27 classes6 ) as mentions of actors of the conflict are likely to bo entities of the following classes:

-LOCATION -PERSON -TITLE -ACRONYM -PERSON TYPE -ORGANISATION -INSTITUTION -ANIMAL
In the following example, taken from the diary of Léo Hamon, can be found entities particularly relevant within the classes PERSON, ORGANISATION and LOCATION:

"Nous parlons du procès Pucheu. La question est plus actuelle. (...) J'indique qu'á mon avis tout ce proces a ete mal conduit -il fallait (...) proclamer que devant des crimes inouïs, (...) la nation prenait une décision politique, immoler les hommes de la haute trahison: "Jetons à l'Europe, en défi une tête de roi", jetons aux combinards de Vichy et de Washington, en défi, une tête de traitre. (...) Je vois Yves qui m'avait cité l'impatience d'Alger devant le cas Pucheu comme une illustration de la crise de Gaulisme."

In addition to the NE classes, Entity Fishing provides a link to the corresponding article in Wikipedia/Wikidata by looking into all possible mentions, that means that if a token (word) is not recognised as a Named Entity but has a corresponding article in Wikipedia/Wikidata, it will be found, increasing the overall recall.

The entity Vichy, present in the above example, have 21 corresponding articles in Wikipedia.

The first two meanings are Vichy, the city in France, and Régime de Vichy, the government allied with the Germans, led by Philippe Pétain during WW2.

Whether the mention Vichy refers to one or another of the 21 articles is inferred by the context of the whole text. For instance, processing a text describing the Ironman race of Vichy would more likely select the city of Vichy as the real entity corresponding to the mention. This example is not particularly fortunate as Vichy can well appear in WW2 texts as the city, hence the results have always a margin of error.

This disambiguation process return the following results: The disambiguation process add precious information in the treatment of this text, once the correct article is found, the access to the corresponding wikidata information rich set of properties, statements and translations that can be further exploited (outside the scope of this article).

Adjusting entity resolution

During the tests with this specific corpus were found many expressions either widely used at the time of the war or specific of the author. Léo Hamon uses a lot of nicknames to identify other members of the Resistance (many of them can be mapped to the real person), he uses also expressions which are not found in Wikipedia nor in any other knowledge base. As discussed before, since these expressions are countable and very specific, it is inevitable to use a dictionary in order to identify them and extend the pool of generic entities found with the NERD. The dictionary is also used to override the resolution phase in order to force the correct definition:

Place de la République, Hotel Moderne, vaste bâtisse où étaient logées les petites souris grises, d'autres disent « les Salamandres », jeunes allemandes en uniforme.

In this case, the tokens petites souris grises, Salamandres and jeunes allemandes en uniforme all refer to the same entity: German Army female auxiliaries. Two of these mentions are nicknames based on animals. This can only be infer by the use of the specific dictionary. There is, however, a limitation in its use: if the author uses the real expression with the nickname, the disambiguation is impossible. The first approximation is to assume that the author doesn't talk about grey mice (souris grises) or salamanders (Salamandres) in his World War 2 diary. A second approximation (suitable for a future paper) would be to use the probability returned by Entity Fishing to make a decision whether to use the dictionary to override the real entity found from Wikipedia.

POS tagging and parsing

The last building block of this process is to link the found entities to their modifiers, using the dependency graph provided by UDPipe.

For each entity, the goal is to find the node marked as HEAD and the nodes marked as descendants. The HEAD is the node upstream in the graph, the one whose the entity directly depends on. On the other hand the DESCENDANTS are nodes depending on the entity itself.

For example the sentence: "Nous devons jeter aux combinards de Vichy et de Washington, en défi, une tête de traître."

From the dependency graph showing the whole syntactic structure (see below), it is necessary to select the relevant elements.

From a theoretical perspective the named entities "Vichy" (i.e. Régime de Vichy) and Washington (i.e. the US government) share a nominal modifier combinards (schemer)

In the parsing results, the modifier combinards is identified as the HEAD of Vichy, it is also linked to Washington via the conjunction et (and) and the fact the Vichy is the HEAD of Washington.

Expected results

This paper represents a first step for this broad research subject. The main expected results are twofold: clustering entities and their modifiers and the generation of multilingual terminology focused on our topic (French-German modern wars). These results can be seen as a graph where relevant and disambiguated entities are connected to all their modifiers, their adjectives, etc. This graph would show clusters of entities, according to certain criterias: their polarity, by the persons who uses them, by the chronological extent of their use, etc. The same approach should also be applied to the extracted qualifiers.

The onomasiological terminology, that records all the terms used to designate the concept can also be considered as a layer of the entities graph.

http://www.github.com/kermitt2/nerd

http://ufal.mff.cuni.cz/udpipe

http://github.com/kermitt2

http://www.tei-c.org/About/mission.xml

https://www.iso.org/standard/45797.html

http://grobid-ner.readthedocs.io/en/latest/class-and-senses/

Bibliography

• Gérard Antoine, Robert Martin (ed.), Histoire de la langue française des origines à nos jours (1880 -1914), Paris, CNRS, [1975]