Olivier L Georgeon
email: olivier.georgeon@liris.cnrs.fr

Florian J Bernard
email: florian.bernard3@etu.univ-lyon1.fr

Amélie Cordier
email: amelie.cordier@liris.cnrs.fr

Constructing Phenomenal Knowledge in an Unknown Noumenal Reality

In 1781, Immanuel Kant argued that cognitive agents ignored the underlying structure of their world "as such" (the noumenal reality), and could only know phenomenal reality (the world "as it appears" through their experience). We introduce design principles to implement these theoretical ideas. Our agent's input data is not a direct function of the environment's state as it is in most symbolic or reinforcement-learning models. The agent is designed to discover and learn regularities in its stream of experience and to construct knowledge about phenomena whose hypothetical presence in the environment explains these regularities. We report a proof-of-concept experiment in which the agent constructs categories of phenomena, and exploits this knowledge to satisfy innate preferences. This work suggests a new approach to cognitive modeling that focuses on the agent's internal stream of experience. We argue that this approach complies with theories of embodied cognition and enaction.

Introduction

Most artificial intelligence and machine learning models represent artificial agents in a perception/cognition/action loop. For example, to Russell & Norvig [1, p. iv], "the problem of AI is to build agents that receive percepts from the environment and perform actions". Many theoreticians of cognition, however, criticized this cognitive loop model [e.g., 2]. We reviewed some of these criticisms in a previous paper [START_REF] Georgeon | ECA: An enactivist cognitive architecture based on sensorimotor modeling[END_REF]. Here, we introduce an alternative modeling approach that addresses the design of cognitive agents from the other side. Rather than beginning with the agent/environment dualism, we begin with a monist perspective (inspired by Spinoza's monist philosophy) in which the agent and its universe are considered a single system. Figure 1 represents a series of chunks of experience that this monist system experiences successively during its existence. These chunks of experience may have a positive, a negative, or a null valence, as we shall explain below. A monist system's stream of experience. White/blue triangles/squares/circles represent chunks of experience that the system experiences one after another. We do not know what these chunks of experience mean, feel like, or are about. The system ignores the shapes and colors of experiences; they are only intended to the reader. Top: the valence of each chunk of experience displayed as a bar-graph: positive (green bars), negative (red bars), or null. order%of%succession% 1% 0% .1%

As an example, this paper presents a system that can experience six different chunks of experience represented by white/blue circles/squares/triangles. Square and circle experiences have a null valence; white triangles have a positive valence (+1); and blue triangles have a negative valence (-1). These valences are arbitrary and remain constant during the system's existence. That is, we think of this system as if it liked experiencing white triangle experiences, disliked experiencing blue triangle experiences, and was indifferent to experiencing other experiences. For the sake of demonstration, we intentionally place the reader in the same situation as the system: initially ignorant of the meaning of experiences. The impatient reader may make a detour to Section 4 where this meaning is revealed.

At any given moment, the system has partial choice about the experience that it will experience next. In general, the system wants to experience positive experiences, but it may experience negative experiences for two reasons: the reason of multiple motivations and the reason of bounded freedom.

The reason of multiple motivations is that the system may have other motivational drives besides experiencing positive experiences. Section 3 proposes two of these other drives that may make the system choose null or negative experiences.

The reason of bounded freedom is that the system does not have entire freedom to choose the experience that it is going to experience next. At any given step, the system may intend to experience a particular chunk of experience, but this intention may fail due to reasons external to the system's decision, causing the system to actually experience a different chunk of experience. Figure 2 represents the dual structure of such a bounded-freedom system: the system has an Intentional Subsystem (IS), which chooses the next intended chunk of experience i s , and a reactive subsystem (RS), which generates the actually experienced chunk of experience e s . Note that Figure 1 only displays the stream of actual experiences.

Assume that the RS affords regularities in the way it generates the actual experience e s . These regularities may depend both on the intended experience i s and on previous history (the RS may not be Markov, i.e., we don't know the extension of dependency a priori). To be in control of the system's stream of experience, the IS must anticipate the actual experiences on the basis of the RS's regularities. To anticipate actual experiences, the IS must construct knowledge that represents the regularities afforded to it by the RS.

Figure 2:

The dual coupling of a bounded-freedom system. At step s, the Intentional Subsystem (top) chooses the intended experience i s from amongst the set E of experiences available to the system. In return, the reactive subsystem (bottom) generates the actually experienced experience e s . If e s = i s , then the system succeeded in experiencing the intended experience, otherwise, it failed.

Task

We distinguish between two kinds of regularities: immediate regularities and sequential regularities. Immediate regularities determine how actual experiences correlate with intended experiences regardless of the RS's history. In our example, immediate regularities are such that an intended experience always results in an actual experience of the same shape (but not necessarily of the same color). In fact, we chose the shapes (squares, circles, triangles) to reflect immediate regularities. For example, we expect the IS to learn that, when it intends a square experience, the system will indeed actually experience a square, perhaps of a different color, but not a circle or a triangle.

Sequential regularities depend on previous history. A sequential regularity is in the form: in the context when a particular series of experiences has just been experienced (pre-experiences), a particular other series of experiences may probably be successfully experienced next (postexperiences). Figure 3 lists 10 first-order (two-step) regularities afforded by our example RS.

Inten%onal) Subsystem)

Intended experience

Actual experience

e s ∈ E i s ∈ E Reac%ve) Subsystem) E = { , , , , , } Figure 3
: 10 two-step regularities afforded by the RS, consisting of a pre-experience followed by a postexperience. Regularity 1: in the context when white square has just been experienced (pre-experience), it is likely that white square can be experienced again (post-experience); i.e., if the IS intends to experience any of the square experiences again, then the system will more likely experience white square than blue square. Similar, Regularity 3 means that, in the white square context, if the IS intends a triangle experience then the system is likely to experience a white triangle experience (immediate regularities prevail over sequential regularities).

We expect the IS to discover these regularities and exploit them to obtain positive experiences and avoid negative experiences (with the valence of experiences defined in Section 1). As a result, the system should develop the patterns of experience depicted in Figure 4. Once the IS has learned this scheme, it applies it indefinitely.

As illustrated in Figure 4, we expect the IS to learn to use square experiences to inform subsequent behavior. If an intended square experience yields a white square, the system should subsequently experience white triangle because it has a positive valence (Figure 4-a, exploiting Regularity 3 of Figure 3). If the intended square experience yields a blue square, the system should subsequently experience white circle so that it can then experience white triangle (Figure 4-b, exploiting Regularities 8 and then 5). After this, we expect the IS to intend a square experience again and to repeat the same conditional choice again (Figure 4-a or 4-b again). In a previous study, we presented a hierarchical sequence-learning algorithm that learned this kind of behaviors [START_REF] Georgeon | An intrinsically-motivated schema mechanism to model and simulate emergent cognition[END_REF][START_REF] Georgeon | Single Agents Can Be Constructivist too[END_REF].

In this paper, we introduce a new algorithm that allows the IS to explicitly interpret the patterns of behavior in Figure 4 as if this behavior was made possible by the existence of phenomena in the RS. Indeed, this behavior can be interpreted as if the IS used square experiences to observe the state of the RS. If this observation results in a white square, the IS can consider that a certain kind of phenomenon-which we call a white phenomenon-exists in the RS. A white phenomenon affords the white triangle experience. Since there is no sequential regularity based on white triangle, the IS can consider that a white triangle experience causes the disappearance of the white phenomenon, leaving the RS in a state unknown to the IS (as if the IS ate the white phenomenon, and enjoyed eating it, since white triangle has a positive valence). A blue square experience similarly denotes the presence of a blue phenomenon, which affords the blue triangle experience (eating the blue phenomenon, and disliking it, since blue triangle has a negative valence). Blue phenomena also afford the white circle experience, which appears to transform blue phenomena into delicious white phenomena. Overall, we expect the IS to construct the belief system represented in Figure 5. The problem of reconstructing causality from sequences of events has been studied in process mining (PM). For example, Van der Aalst et al. [START_REF] Van Der Aalst | Workflow mining: A survey of issues and approaches[END_REF] surveyed four PM algorithms used to construct Petri nets from event logs. Such surveys show that PM algorithms generally exploit specific properties of the flow of events and of the Petri net to be constructed. Typically, Van der Aalst's [START_REF] Van Der Aalst | Workflow Mining: Discovering process models from event logs[END_REF] foundational α-algorithm exploits the assumption that the Petri net has no internal loops. Our system, however, does not satisfy this assumption.

Our algorithm was inspired by the α-algorithm but exploits two different assumptions: (a) the system is actively generating the events, rather than learning from logs generated beforehand; and (b) there exist "self-loops" (with same starting and ending node). In essence, our algorithm begins with looking for experiences that can be repeated several times in a row (persistent experiences). When the IS finds a candidate persistent experience, it creates a self-loop based on this experience, and a node attached to this self-loop. This node thus represents a hypothetical phenomenon that can be consistently observed through this experience. Next, the IS learns arcs between nodes. Table 1 summarizes this algorithm at the highest level. The IS has three possible motivational states (moods): curious, excited, and hedonist. On initialization, it has only one predefined belief state: unknown, and it is in a curious mood. Lines 03 and 04: if it is in a curious mood, then it intends the experience that has been the least tried in the context of the current belief. Lines 05 and 06: if it is in a hedonist mood, then it intends the experience that has the maximum expected valence in the context of the current belief. Lines 07 and 08: if it is in an excited mood, then it intends to repeat the same experience.

Line 09: The RS computes the actual experience from the intended experience (see Section 4). Lines 10 to 17: if the IS is excited and the intention failed, the intended experience is marked sporadic (not persistent). Otherwise, if the IS has reached a preset excitement threshold, the experience is marked persistent, and a new belief state is created based on this experience, otherwise the IS gets more excited. Line 18: learn regularities and update the current belief state. Lines 19 to 24: if the mood is not excited then it is hedonist. If the experience has neither yet been marked persistent or sporadic, the mood becomes excited. If the IS has not yet experimented much with the current belief state, the mood is curious.

Figure 6 reports an empirical evaluation of this algorithm based upon the trace of its stream of experience.

Figure 6: Our system's first 70 experiences. Line 1: valence of the actual experience as in Figure 1. Line 2: intended experience. Line 3: actual experience. Line 4: current belief: unknown / white phenomenon / blue phenomenon (little grey/white/blue pointed rectangles). Line 5: mood: curious ("?"), excited (black bargraph), or hedonist (blank). Line 6: progressive construction of phenomena. Step 1: the IS intends a blue square and obtains a white square. Since the white square experience is neither yet marked sporadic or persistent, the IS gets excited (black bar in Line 5). Step 2 to 5, the white square keeps succeeding and the IS gets increasingly excited. Step 6: the IS reaches the excitement threshold; it marks the white square persistent, and creates the white phenomenon; Line 4: the current belief becomes white phenomenon; Line 6: thus far, the white phenomenon contains only the white square experience; Line 5: the IS becomes curious to play with the newly created white phenomenon.

Step 7: the IS tries blue square. Step 8: the IS tries blue triangle and obtains white triangle; Line 6: the IS notes that the white phenomenon affords white triangle. Step 9: white triangle is learned to be sporadic since it failed on the second attempt. Step 11: similar, blue triangle is sporadic.

Step 17: blue square is persistent and the IS creates the blue phenomenon.

Step 21: the white phenomenon is complete. Step 25: the blue phenomenon is complete; the IS continues learning the arcs of the Petri net (function updateAndGetBelief(), not examined in this paper). From Step 41 on, the system exhibits the behavior described in Figure 4, demonstrating that it has learned the belief system that we expected it to learn. [START_REF] Georgeon | An intrinsically-motivated schema mechanism to model and simulate emergent cognition[END_REF] The agent/environment coupling The environment is implemented as a subprogram of the ReactiveSubsystem() function (Table 1, Line 09). The rest of the main loop implements the agent. Unbeknownst to the agent, the environment is an arbitrary string of 10 digits initialized with E 0 = [START_REF] Russell | Artificial Intelligence, A Modern Approach[END_REF][START_REF] Van Der Aalst | Workflow Mining: Discovering process models from event logs[END_REF][START_REF] Georgeon | ECA: An enactivist cognitive architecture based on sensorimotor modeling[END_REF][START_REF] Hurley | Consciousness in action[END_REF][START_REF] Georgeon | Inverting the interaction cycle to model embodied agents[END_REF][START_REF] Georgeon | ECA: An enactivist cognitive architecture based on sensorimotor modeling[END_REF][START_REF] Georgeon | Single Agents Can Be Constructivist too[END_REF][START_REF] Van Der Aalst | Workflow mining: A survey of issues and approaches[END_REF][START_REF] Van Der Aalst | Workflow Mining: Discovering process models from event logs[END_REF][START_REF] Froese | Enactive artificial intelligence: Investigating the systemic organization of life and mind[END_REF], plus an integer p in the interval [0, 9], initialized with p 0 = 0, which represents the agent's position in this string. This environment is similar to Georgeon & Hassas's [START_REF] Georgeon | Single Agents Can Be Constructivist too[END_REF] String Environment.

Triangle experiences consist of moving the agent to the next digit (if p < 9 then p ← p + 1 else p ← 0). If this takes the agent to a lower digit then it yields blue triangle, otherwise, white triangle. Note that triangle experiences are uninformative of the resulting situation of the agent; the agent's input data is not necessarily a representation of the current state of the environment. Square experiences consist of testing whether the next digit is lower than the current one, if yes it yields blue square, otherwise, white square. Circle experiences consist of swapping the current digit with the next (only if p < 9); if the resulting current digit is lower than the next, it yields blue circle, otherwise, white circle.

The trace in Figure 6 shows that, over time, the agent learns to use square experiences as active perception to test whether the current digit is lower than the next, and, if yes, to use a circle experience to swap the digits, in order to always move to a greater or equal next digit (because the agent has an innate preference for moving towards greater or equal digits implemented through the positive valence of the white triangle experience).

Conclusion

This proof-of-concept algorithm illustrates how an agent can construct knowledge from regularities observed in its stream of experience-a question which theoreticians and philosophers of mind consider crucial to cognition. All along, the agent ignores the underlying reality in which it exists (noumenal reality: the string of digits); it only constructs its own interpretation of this reality in the form of phenomenal knowledge (white and blue phenomena). We proposed a design paradigm that focuses on the system's stream of experience rather than separating perception from action. This design paradigm does not contradict the traditional perception/action paradigm; the relation between the two is examined in Section 4. Yet, we found that it facilitated the conception and the explanation of the algorithm. Additionally, it complies with theories of embodied cognition and enaction [e.g., 8] in that the agent is an active observer of its environment, and constructs knowledge from sensorimotor schemes of experience. We develop these arguments further in previous papers [e.g., [START_REF] Georgeon | ECA: An enactivist cognitive architecture based on sensorimotor modeling[END_REF][START_REF] Georgeon | Inverting the interaction cycle to model embodied agents[END_REF].

Our agent has three motivational drives: curiosity, excitement, and hedonism. These drives implement inborn preferences analogous to natural organisms' preferences that presumably evolved through natural selection (e.g., playing, liking ingesting nutritive food and disliking ingesting toxic food). Such inborn preferences relate to Jonas's [START_REF] Jonas | The Phenomenon of Life: Toward a Philosophical Biology[END_REF] notion of needful freedom; they drive the agent's behavior without imposing predefined goal states.

This preliminary study led us to formulate crucial questions that remain to be answered if we want to design agents that can construct higher-level knowledge from their experience interacting with a more complex reality (e.g., the real world): how to revise erroneous hypothetical phenomena; how to learn to interact with an environment in which several phenomena can exist simultaneously at different locations (i.e., spatial environment); how to distinguish between phenomena that afford some experiences in common but differ by some others; how to learn complex spatio-sequential patterns of interactions afforded by phenomena; and how to handle noise in the agent's input data.

Figure 1 :

 1 Figure 1:A monist system's stream of experience. White/blue triangles/squares/circles represent chunks of experience that the system experiences one after another. We do not know what these chunks of experience mean, feel like, or are about. The system ignores the shapes and colors of experiences; they are only intended to the reader. Top: the valence of each chunk of experience displayed as a bar-graph: positive (green bars), negative (red bars), or null.

Figure 4 :

 4 Figure 4: Patterns of experience that we expect the system to develop. The curly brackets represent a conditional scheme that results in sequence (a) or (b) depending on the current state of the RS.Once the IS has learned this scheme, it applies it indefinitely.

Figure 5 :

 5 Figure5: Petri net representing the belief system that we expect the IS to construct. Nodes represent beliefs that the IS may hold about the RS's state: white phenomenon (top-left), blue phenomenon (top-right), or unknown (bottom). Phenomena are represented by pointed rectangles split in two areas: upper area: the persistent experience that allows observing this phenomenon; lower area: the sporadic (not persistent) experiences afforded by this phenomenon. Arcs show the sporadic experiences that cause the IS to transition from one belief state to another.

Table 1 :

 1 A proof-of-concept algorithm to infer phenomena from regularities of experience

	01	belief ← "unknown", mood ← "curious"
	02	Loop
	03	if mood = "curious"
	04	intention ← leastTriedExperience(Belief)
	05	if mood = "hedonist"
	06	intention ← intentionWithMaxExpectedOutcomeValence(belief)
	07	if mood = "excited"
	08	intention ← experience
	09	experience ← ReactiveSubsystem(intention)
	10	if mood = "excited"
	11	if experience ≠ intention
	12	intention is sporadic
	13	else if excitement > excitementThreshold
	14	experience is persistent
	15	createNewBeliefState(experience)
	16	else
	17	excitement++
	18	belief ← updateAndGetBelief(experience)
	19	if mood ≠ "excited"
	20	mood ← "hedonist"
	21	if experience is unknown
	22	mood ← "excited"
	23	if all the experiences have not been tried yet in the context of this belief
	24	mood ← "curious"


Nicolas Dugué

Anthony Perez

Directed Louvain : maximizing modularity in directed networks

In this paper we consider the community detection problem from two different perspectives. We first want to be able to compute communities for large directed networks, containing million vertices and billion arcs. Moreover, in a large number of applications, the graphs modelizing such networks are directed. Nevertheless, one is often forced to forget the direction between the connections, either for the sake of simplicity or because no other options are available. This is in particular the case on large networks, since there are only a few scalable algorithms at the time. We thus turn our attention to one of the most famous scalable algorithms, namely Louvain's algorithm [3], based on modularity maximization. We modify Louvain's algorithm to handle directed networks based on the notion of directed modularity defined by Leicht and Newman [13], and provide an empirical and theoretical study to show that one should prefer directed modularity. To illustrate this fact, we use the LFR benchmarks by Lancichinetti and Fortunato [8] to design an evaluation benchmark of directed graphs with community structure. We also give some examples and insights on the situations where one should really consider direction when maximizing modularity. Finally, for the sake of completeness, we compare the results obtained with Oslom [12], one of the best algorithms to detect communities in directed networks. While the results obtained with such an algorithm are by far better on the LFR benchmarks, we emphasize that it is still not well-suited to deal with very large networks.

Introduction

In various domains such as social networks or bioinformatics, being able to detect communities efficiently constitutes a very important research interest [6]. In most cases, the underlying graphs representing data are directed. This happens for instance when considering some social network graphs, where relations between two users u and v can be represented by stating that u has an influence over v rather than simply saying that they both interact. It thus seems quite obvious to consider direction when detecting communities, and several algorithms were proposed in this sense, such as Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] or InfoMap [START_REF] Rosvall | The map equation[END_REF][START_REF] Rosvall | Maps of random walks on complex networks reveal community structure[END_REF]. In this article, we are interested in detecting communities in very large networks such as the Twitter graph [START_REF] Cha | Measuring User Influence in Twitter: The Million Follower Fallacy[END_REF], which contains more than 50 millions vertices and almost 2 billions arcs. As we shall see Section 5, Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] fail to efficiently produce communities when considering such networks [START_REF] Cha | Measuring User Influence in Twitter: The Million Follower Fallacy[END_REF], especially if one wants to use only a few computer ressources. Due to this fact, a common solution is to simply forget direction when detecting communities in really large network and to run Louvain's algorithm [START_REF] Vincent | Fast unfolding of communities in large networks[END_REF] (which is extremely well-suited for large networks). To the best of our knowledge, there is no version of this algorithm maximizing directed modularity [START_REF] Leicht | Community structure in directed networks[END_REF]. This fact can also be seen in a survey comparing algorithms for community detection, where Lancichinetti and Fortunato [START_REF] Lancichinetti | Community detection algorithms: a comparative analysis[END_REF] did not even consider Louvain's algorithm for their directed networks analysis. Instead, they used simulated annealing for modularity optimization [6] even if they confirmed on undirected networks that Louvain's algorithm performs better and runs a lot faster.

Our results. In this work, we give some insights about the importance of direction while detecting communities. To that aim, we consider Louvain's algorithm [START_REF] Vincent | Fast unfolding of communities in large networks[END_REF], which is implemented for non-directed graphs only. By modifying the existing source code [START_REF] Blondel | Louvain method: Finding communities in large networks[END_REF], we manage to deal with directed graphs, following the notion of directed modularity introduced by Leicht and Newman [START_REF] Leicht | Community structure in directed networks[END_REF] (Section 2). We then generated a benchmark of directed graphs using the framework provided by Fortunato et al. [START_REF] Lancichinetti | Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[END_REF], and computed communities on such graphs using both versions of the Louvain's algorithm1 . Our results show strong evidence that direction is important when detecting communities (Section 5). Finally, we also compare these results to communities obtained by a recent community detection algorithm called Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF], both from the semantic and complexity viewpoints (Section 5). We emphasize that Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] cannot deal with large graphs such as the Twitter graph [START_REF] Cha | Measuring User Influence in Twitter: The Million Follower Fallacy[END_REF] (billions of edges), while Louvain's algorithm produces results in a couple of hours.

Detecting community in large (directed) networks

Modularity. A classic way of detecting communities is to find a partition of the vertex set that maximizes an optimization function. One of the most famous optimization function is called modularity [START_REF] Newman | The Structure and Function of Complex Networks[END_REF]. This function provides a way to value the existence of an edge between two vertices of an undirected network by comparing it with the probability of having such an edge in a random model following the same degree distribution than the original network. For instance, an edge between two vertices of large degree is not surprising, and thus does not contribute much to the modularity of a given partition, whereas an edge between two vertices of small degree is more surprising. Formally, the modularity Q of a partition C of an undirected graph G = (V, E) is defined as follows :

Q = 1 2m i,j A ij - d i d j 2m δ(c i , c j )
where m stands for the number of edges of G, A ij represents the weight of the edge between i and j (set to 0 if such an edge does not exist), d i is the degree of vertex i (i.e. the number of neighbors of i), c i is the community to which vertex i belongs and the δ-function δ(u, v) is defined as 1 if u = v, and 0 otherwise. Leicht and Newman [START_REF] Leicht | Community structure in directed networks[END_REF] adapted the notion of modularity for directed graphs, motivated by the following observation: if two vertices u and v have small in-degree/large out-degree and small out-degree/large in-degree, then having an arc from v to u should be considered more surprising than having an arc from u to v. Taking this into account, the definition for directed modularity of a partition of a directed network can be easily formulated:

Q d = 1 m i,j A ij - d in i d out j m δ(c i , c j )
where A ij now represents the existence of an arc between i and j and d in i (resp. d out j ) stands for the in-degree (resp. out-degree) of i.

Louvain's algorithm. We now briefly describe the behavior of Louvain's algorithm to maximize modularity. The algorithm is the same for both the classic and directed versions of modularity. It relies on a greedy procedure: starting from any partition of the vertices (usually the partition into singletons), the algorithm tries to increase the value of modularity by moving vertices from their community to any other neighbor one. In other words, the algorithm computes the gain of modularity obtained by adding vertex i to community C as follows (for the undirected case):

∆ Q = in +d C i 2m - tot +d i 2m 2 - in 2m - tot 2m 2 - d i 2m 2 = d C i 2m -tot •d i 2m 2
where d C i denotes the degree of node i in community C, in the number of edges contained in community C and tot the total number of edges incident to community C. Actually, the first formula is the one as described in [START_REF] Vincent | Fast unfolding of communities in large networks[END_REF], but one can see that it reduces to the second one. The algorithm does a similar calculation to compute the gain obtained by removing vertex i from its own community C i in a first place. The algorithm carries on as long as it exists a move that improves the value of modularity.

The behavior of the algorithm is exactly the same in the directed case, the main difference lying in the calculation for the gain of modularity obtained by adding vertex i to community C, which can now be done using the following:

∆ Q d = d C i m - d out i • in tot +d in i • out tot m 2
where in tot (resp.

out tot ) denotes the number of in-going (resp. out-going) arcs incident to community C.

Theoretical comparison between undirected and directed modularity

Our goal is to validate the observation made by Leicht and Newman [START_REF] Leicht | Community structure in directed networks[END_REF] by showing what happens if one uses the modularity Q [START_REF] Newman | The Structure and Function of Complex Networks[END_REF] on a directed graph instead of using its directed version Q d [START_REF] Leicht | Community structure in directed networks[END_REF].

To that aim, we use a straightforward case study where we consider two subgraphs C 1 and C 2 which both are communities of a directed network (see Figure 1). We are basically studying when merging these communities lead to a value increase of both modularities. To calculate the undirected modularity on a network which is usually directed, we have to ignore the links direction. Thus, if we are processing a directed network

D = (V, A) where (u, v) ∨ (v, u) ∈ A, then (u, v) ∈ E in the undirected version G = (V, E). We use Q C 1 \C 2 (resp. Q C 1 \C 2 d
) to refer to the undirected (resp. directed) modularity value of the network with C 1 and C 2 distinct communities. In the same way, we use

Q C 1 ∪C 2 (resp. Q C 1 ∪C 2 d
) to refer to the modularity value of the network where C 1 and C 2 are part of the same community. We name A 1,2 arcs between communities C 1 and C 2 , and E 1,2 the corresponding edges in the undirected network. Considering the undirected case,

|E 1,2 | = |A 1,2 | if ∀(u, v) ∈ A 1,2 then (v, u) / ∈ A 1,2 . We also have that |E 1,2 | = 1 2 • |A 1,2 | if ∀(u, v) ∈ A 1,2 then (v, u) ∈ A 1,2 . Thus, |E 1,2 | |A 1,2 | 2 • |E 1,2 |.

Undirected case

When C 1 and C 2 are considered as part of the same community, E 1,2 links contribute to increase modularity value, as shown in bold in the following formula.

Q C 1 ∪C 2 = d int C 1 m + d int C 2 m + |E 1,2 | m -   i,j∈C 1 d i d j 4m 2 + i,j∈C 2 d i d j 4m 2 + i∈C 1 ,j∈C 2 d i d j 2m 2  
When C 1 and C 2 are splitted in two different communities, both the terms in bold before disappear.

Q C 1 \C 2 = d int C 1 m + d int C 2 m -   i,j∈C 1 d i d j 4m 2 + i,j∈C 2 d i d j 4m 2  
Thus, if summing these bold terms results in a positive number, C 1 and C 2 are merged. At the contrary, if the sum is negative, C 1 and C 2 are considered as two distinct communities. Therefore, studying when these communities are merged or not consists in studying the sum of these terms as follows.

δ Q = Q C 1 ∪C 2 -Q C 1 \C 2 = |E 1,2 | m - i∈C 1 ,j∈C 2 d i d j 2m 2 = 1 m |E 1,2 | - i∈C 1 ,j∈C 2 d i d j 2m
Hence:

δ Q > 0 ⇔ |E 1,2 | > i∈C 1 ,j∈C 2 d i d j 2m (1)

Directed case

In the directed case, we obtain a quite similar result. Indeed, when C 1 and C 2 are considered as being part of the same community, we obtain:

δ Q d = Q C 1 ∪C 2 d -Q C 1 \C 2 d = |A 1,2 | 2m - i∈C 1 ,j∈C 2 d in i d out j 4m 2 - i∈C 1 ,j∈C 2 d out i d in j 4m 2
Hence:

δ Q d > 0 <=> |A 1,2 | > i∈C 1 ,j∈C 2 d in i d out j 2m + d out i d in j 2m

Comparison

To compare the choices made by both modularities, we replace the vertex degree of Equation 1 by its in-and out-going counterparts.

d i d j = (d in i + d out i )(d in j + d out j )
We thus obtain the following equivalence :

|E 1,2 | > i∈C 1 ,j∈C 2 d in i d out j 2m + d out i d in j 2m + i∈C 1 ,j∈C 2 d in i d in j 2m + d out i d out j 2m
Let us define the following terms :

S = i∈C 1 ,j∈C 2 d in i d out j 2m + d out i d in j 2m T = i∈C 1 ,j∈C 2 d in i d in j 2m + d out i d out j 2m
Thus, in the undirected case, C 1 and C 2 are merged when |E 1,2 | > S + T while in the directed case, the fusion is done when |A 1,2 | > S, T being absent from the equation.

The term S confirms the observation made by Leicht and Newman [START_REF] Leicht | Community structure in directed networks[END_REF]. Furthermore, we can see that T is not relevant at all. Multiplying the incoming degrees in one side and the outgoing degrees in the other side does not allow to estimate links probability to exist between communities in a random network. This may explain the better results obtained with the Louvain algorithm implementing the directed modularity.

Analysis of the differences

We study the conditions that make differences arise between the two versions of Louvain's algorithms. We first give some intuition on the configurations that can lead to two different moves in the algorithm, and then provide several examples where the difference is significant.

Sufficient conditions to have a difference. To complete the previous observations, we give some conditions that will influence community detection between the two methods. Recall that the gain of modularity can be easily computed (in both cases) using the following:

∆ Q ∼ d C i -tot •d i 2m ∆ Q d = d C i - d out i • in tot +d in i • out tot m
We thus have to study the behavior of the terms tot •d i m and

d out i • in tot +d in i • out tot m
for a given vertex i and a given community C. In particular, we want to express the conditions when the first one is positive and the second one negative, or vice-versa. Recall that, in the first case, the classic Louvain's algorithm will not consider adding vertex i to community C to increase modularity, while the directed version will do so.

Cases that make a difference. We first provide some simple examples when the classic Louvain's algorithm fails at detecting communities, whereas the algorithm maximizing directed modularity finds a perfect match with the ground truth communities. Consider the graph represented Figure 2, which contains 100 vertices and 2 communities. When maximizing directed modularity, Louvain's algorithm succeeds in retrieving the communities whereas the classic modularity maximization fails to merge two communities. The explanation for this situation follows from our previous arguments. Indeed, the graph contains vertices with unbalanced in and out-degrees, who thus influence the greedy method of Louvain's algorithms. Such a situation can also be observed on larger graphs2 (see Figure 3).

3: On top, the groundtruth communities. On the bottom left, the communities found by the directed version of the algorithm and on the bottom right the ones provided by the classic one.

Experimental results

We now present empirically the differences that arise between classic modularity maximization and the directed one. To that aim, we evaluate the results of both the modulairies over the so-called directed LFR benchmarks [START_REF] Lancichinetti | Community detection algorithms: a comparative analysis[END_REF].We consider partitions (that is non-overlapping communities).

The LFR benchmarks

To validate the efficiency of Louvain algorithm adapted to directed graphs, we use benchmarks introduced by Lancichinetti and Fortunato [START_REF] Lancichinetti | Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[END_REF]. These benchmarks allow to test community detection algorithms on directed graphs, and are designed in order to be as realistic as possible with respect to real networks. It is indeed possible to set important features such as the power-law distribution of the degrees of the nodes or of the communities sizes, as well as the maximum and average degrees of nodes in the graphs. Another major feaure introduced in these benchmarks is the mixing parameter. The mixing parameter allows to create graphs with communities more or less well-defined. A low mixing parameter indicates communities well-defined, and hence easy to detect. Reciprocally, a high mixing parameter allows to create graphs with communities which will be hard to detect.

Measures

To compare the results obtained by the community detection methods, we use three evaluation measures. The results of the community detection algorithms are thus compared with the communities defined by the benchmarks we use. In the following, we use clustering to denote the community sets obtained by the algorithms used. The term cluster is thus one community of these sets. We use community to talk about the groundtruth communities established by the benchmark.

The first measure, called V-Measure [START_REF] Rosenberg | V-measure: A conditional entropy-based external cluster evaluation measure[END_REF] made of two criteria: homogeneity and completeness. This may be compared to the F-measure based on precision and recall measures. A clustering maximizes the homogeneity if for each cluster, we find only elements of a same community. Symetrically, completeness is maximized when for each community, all elements of a same community are in a single cluster. By computing the harmonic mean of these two values, we obtain the so-called V-measure. The second one is the NMI [21] for Normalized Mutual Information. Built upon concepts from information theory, this measure is commonly used to compare clusterings. Roughly speaking, this measure defines how much knowing one of two clusterings reduces uncertainty about the other. Thus, the higher the NMI, the more information the two clusterings share. We use the normalization introduced by Strehl and Gosh [21] defined as follows.

definition 1 (NMI [21]) Let U and V be two clusterings. Then the Normalized Mmutual Information is defined as a function of the mutual information I and the conditional entropy H:

N M I(U, V) = I(U, V) H(U) • H(V)
Finally, to compute the Purity [START_REF] Zhao | Criterion functions for document clustering: Experiments and analysis[END_REF], we assign each cluster to the community which nodes are more frequent in the cluster. Then, by summing all well-classified nodes for each of these clusters and dividing it by the number of vertices, we obtain the accuracy of our clustering.

Classic LFR benchmarks

We begin this section by giving some results obtained by generating LFR benchmarks using parameters described by Lancichinetti and Fortunato [START_REF] Lancichinetti | Community detection algorithms: a comparative analysis[END_REF]. Those parameters consider two different cases, namely graphs having small and big community sizes. In the first case, the communities are set to contain between 10 and 50 vertices, while they are required to contain between 20 and 100 vertices in the latter one. In such graphs, the average degree is set to 20 and the maximum degree is set to 50. We consider graphs having respectively 1000 and 5000 nodes, and make the mixing parameter go from 0.1 (i.e. well-defined communities) to 0.6. Finally, we set the power law distribution to 2 in all cases. We first give a general picture of the results we obtained w.r.t. to the number of vertices and the size of the communities (Table 1 Louvain's algorithm maximizing directed modularity is better in almost 75% of the cases. Moreover, we would like to mention that if the improvement is rather low on average, there are some interesting cases where the improvement is drastic. then compare the outputs of both version of Louvain's algorithms according to the aforementioned quality measures. We conducted such an experimentation by considering different networks sizes, and also by modifying the mixing parameter. As one can observe

Generated LFR benchmarks

In this Section, we present similar observations on a new set of benchmarks that we generated for this purpose. Recall that the average and maximum degree are respectively fixed to 20 and 50 in the classic LFR benchmarks. This seems quite unrealistic when trying to simulate social networks: on Table 3 we observe in several well-known complex networks that the average degree is in general much lower, while the maximum degree is much higher. Hence, it seems quite restrictive to impose a maximum degree of 50, when it is really common for vertices of such networks to have a degree close to n 3 . To complete our analysis, we generated about 40000 graphs with different parameters closely related to those observed in real networks. In particular, we infered the average and maximum degrees w.r.t. the power law and mixing parameter. For every combination of such parameters, we generated 100 different graphs and ran a statistical analysis. We first give a general picture of our observations. n # graphs It arises from Table 4 that in 70% of the cases, directed modularity provides better results than the classic Louvain's algorithm. We would like to mention that very similar results can be observed when considering other similarity measures such as F-measure, V-measure, purity, completeness, homogeneity. To be consistent with the results presented in [START_REF] Lancichinetti | Community detection algorithms: a comparative analysis[END_REF], we have a closer look on the measures for 1000 and 5000 nodes, respectively. The results presented Figure 4 were obtained by taking the average of the measures over 100 different graphs with the same parameters.

Network

We would like to mention that Louvain's algorithm seems to be particularly well-suited to maximize directed modularity, since the results obtained seem to be really better than the ones presented Fortunato et al. LF09a, obtained using simulated annealing for modularity optimization [6].

A comparative analysis with Oslom [12]

To conclude this part of our work, we would like to compare Louvain's algorithm optimizing directed modularity with another algorithm used to detect communities in directed networks, namely Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF]. We are particularly interested in the time complexity needed to run such algorithms. We want to emphasize that such an algorithm is really not well-suited for handling large (directed) networks.

Results. We now present the results obtained by running Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] on the classic LFR benchmarks. We focus on both the accurency and the time complexity needed to obtain such results. As one can see on Table 5, Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] is drastically better than Louvain's algorithm on the classic LFR benchmarks. This is not a surprising result, since Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] seems to provide really good results [START_REF] Lancichinetti | Community detection algorithms: a comparative analysis[END_REF]. However, as we shall see in the remaining of the paper, Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] cannot provide results in a reasonnable amount of time for networks with relatively small size. Time complexity. We now focus on the time complexity needed to obtain results when using OSLOM or Louvain's algorithm with directed modularity. We conduct our analysis on a set of real networks extracted from Konect Database [START_REF] Konect | KONECT datasets[END_REF] (see Table 6). As mentioned previously, we do not consider here the quality of the output (OSLOM performs better than Louvain's algorithm), but we only focus on the time needed to obtain such an output. For networks with 10000 vertices, Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] already takes a significant amount of time3 to compute the results. On the largest graph we consider, the classic configuration of Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] fails at producing any output even after hours of computation. Thus, if one should clearly prefer using Oslom [START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] on small networks, its use is absolutely impossible for networks as large as the ones that really often arise in the literature. We hope that our study will enlight that the version of Louvain's algorithm that maximizes directed modularity should be considered as more reliable to deal with such networks.

Name

Figure 1 :

 1 Figure 1: Figure extracted from the article of Lancichinetti and Fortunato [11].

Figure 2 :

 2 Figure 2: On the left, the three communities obtained by maximizing standard modularity are represented. On the right, the ones obtained using directed modularity.

Figure 4 :

 4 Figure 4: The values of the mutual information are represented on the Y axis, while the mixing parameter is on the X axis.

Table 1 :

 1 ). Proportion of graphs where the NMI of the classic modularity (nmi o ) is greater than the one of the directed modularity (nmi d ) by a given percentage.

	n	minc	maxc	# graphs		+0.05	+0.1	+0.2
	1000	10	50	900	839	83	54	5
	1000	20	100	900	776	70	27	3
	5000	10	50	900	804	0	0	0
	5000	20	100	900	785	54	31	3

Table 2 ,

 2 the directed version (which corresponds to the bottom table) is better in most cases.

	n	mu	NMI	V-measure	Homogeneity Completeness Purity
	1000	0.1	0.987	0.987	1.000	0.975	1.000
	1000	0.6	0.965	0.964	0.999	0.932	0.999
	5000	0.1	0.966	0.965	1.000	0.934	1.000
	5000	0.6	0.909	0.905	0.999	0.828	0.999
	n	mu	NMI	V-measure	Homogeneity Completeness Purity
	1000	0.1	0.995	0.995	1.000	0.990	1.000
	1000	0.6	0.978	0.978	1.000	0.958	1.000
	5000	0.1	0.978	0.978	1.000	0.957	1.000
	5000	0.6	0.920	0.917	0.999	0.848	0.999

Table 2 :

 2 Results obtained on the classic LFR benchmarks with the classic and the directed versions of Louvain algorithm. Each mesure indicates the average taken over 100 graphs with the indicated parameters.

Table 3 :

 3 Basic properties of several physical, social or reference based network from literature.

		Nodes	Edges	Avg degree Max degree Power-law
	Zachary karate club [22]	34	78	4.59	17	2.16
	Openflight [17]	2, 939	30, 501	20.76	473	1.79
	Arxiv Astro-ph [14]	18, 771	198, 050	21.10	504	2.60
	Internet AS [23]	34, 761	171, 403	9.86	5, 305	1.86
	SlashDot [5]	51, 083	140, 778	5.51	3, 357	1.91
	Flickr [15]	2, 302, 925 33, 140, 018	28.78	34, 174	2.02
	DBPedia [1]	2, 152, 642 7, 494, 124	6.96	329, 714	2.15

Table 4 :

 4 Proportion of graphs where nmi o is greater than nmi d by a given percentage.

	+0.05	+0.1	+0.25

Table 5 :

 5 Results obtained on the classic LFR benchmarks. Each mesure indicates the average taken over 100 graphs with the indicated parameters.

	n	mu	NMI	V-measure	Homogeneity Completeness Purity
	1000	0.1	0.999	0.999	0.999	0.999	0.999
	1000	0.6	0.999	0.999	0.999	0.999	0.999
	5000	0.1	0.994	0.999	0.999	0.999	0.999
	5000	0.6	0.999	0.999	0.999	0.999	0.999

Table 6 :

 6 Directed networks used for time complexity analysis.

		Vertices Arcs Louvain	Oslom
	E-Coli		212	∼ 0 seconds	1.8 seconds
	Bio-Yeast	688	1079	∼ 0 seconds	∼ 35 seconds
	Spanish-Book	12643	57772 ∼ 0.2 seconds	∼ 27 minutes
	Word-Association	10617	72168 ∼ 0.26 seconds ∼ 30 minutes
	Edinburg	23219	325624 ∼ 1 seconds	> 10 hours

Louvain's algorithm is usually non-deterministic, but in order to obtain consistent results, we always consider the vertices in the same order.

For the sake of visiblity we do not consider larger graphs, but mention that similar situations happen also.

We would like to mention that our results differ significantly from the ones presented in[START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF]. This comes from the fact that a new version of Oslom[START_REF] Lancichinetti | Finding Statistically Significant Communities in Networks[END_REF] has been released. While such a version provides better results than the previous ones, it seems that the time needed to obtain the results is more important.


Liangquan Zhang
email: liangquan.zhang@inria.fr

Qinghua Zhang
email: qinghua.zhang@inria.fr

Observability conservation by output feedback and observability Gramian bounds

Keywords: observability Gramian, uniform complete observability, time varying system, closed loop system

Though it is a trivial fact that the observability of a linear state space system is conserved by output feedback, it requires a rigorous proof to generalize this result to uniform complete observability, which is defined with the observability Gramian. The purpose of this paper is to present such a proof. Some issues in existing results are also discussed. The uniform complete observability of closed loop systems is useful for the analysis of some adaptive systems and of the Kalman filter.

Introduction

For a linear time varying (LTV) state space system ẋ(t) = A(t)x(t) + B(t)u(t) (1a)

y(t) = C(t)x(t) (1b)
with the state x(t) ∈ R n , the input u(t) ∈ R k , the output y(t) ∈ R m , and with bounded piecewise continuous matrices A(t), B(t), C(t) of appropriate sizes, it is well known that its observability depends only on the matrix pair [A(t), C(t)].

Consider the output feedback u(t) = -L(t)y(t) with some matrix L(t) ∈ R k×m and let K(t) B(t)L(t) ∈ R n×m , then the closed loop system ẋ(t) = A(t)x(t)-K(t)y(t) (2a) y(t) = C(t)x(t) (2b) and the equivalent system ẋ(t) = (A(t)-K(t)C(t))x(t) (3a) y(t) = C(t)x(t).

(3b) have the same observability property as (1). It is then clear that, if the matrix pair [A(t), C(t)] is observable, then so is the matrix pair [(A(t) -K(t)C(t)), C(t)]. The converse is also true. In (Anderson et al., 1986, page 38), the statement of this result was generalized to uniform complete observability (UCO, definition recalled in the next section), but without being proved. Proofs of the generalized result can be found in [START_REF] Sastry | Adaptive Control: Stability, Convergence and Robustness[END_REF][START_REF] Ioannou | Robust Adaptive Control[END_REF], but some details of these proofs merit revision and comments, as discussed in Appendix A. The purpose of this paper is to propose a complete proof with new observability Gramian bounds. In [START_REF] Aeyels | Asymptotic stability for time-variant systems and observability: Uniform and nonuniform criteria[END_REF] a similar result is presented, but it does not provide an estimation of the bounds of the observability Gramian, and assumes an extra condition: the uniform stability of the considered systems, which is not required in the present paper. Matrices of the form (A(t)-K(t)C(t)) appear naturally in the error dynamics equation of the Kalman filter, and similarly in state observers. The UCO of the matrix pair [(A(t) -K(t)C(t)), C(t)] helps to establish the stability of the Kalman filter or of state observers [START_REF] Kalman | New methods in Wiener filtering theory[END_REF]. It is also useful for the analysis of some adaptive systems (Anderson et al., 1986, chapter 2), (Sastry and Bodson, 1989, chapter 2), (Ioannou and Sun, 1996, chapter 4).

Observability Gramian bounds

Let Φ(t, t 0 ) denote the state transition matrix of system (1). The observability Gramian of this system is

M (t 1 , t 2 ) = t2 t1 Φ T (t, t 2 )C T (t)C(t)Φ(t, t 2 )dt. (4)
System ( 1) is said uniformly completely observable (UCO1 ) (Kalman, 1963, p. 358) if there exist positive constants σ, α, β such that (I n denotes the n×n identity matrix)

0 < αI n ≤ M (t -σ, t) ≤ βI n (5)
hold for all t ∈ R. Similarly, let Φ(t, t 0 ) be the state transition matrix of system (3), and its observability Gramian

M (t 1 , t 2 ) = t2 t1 ΦT (t, t 2 )C T (t)C(t) Φ(t, t 2 )dt. ( 6
)
System (3) is said UCO if there exist positive constants σ, α, β such that, for all t ∈ R,

0 < αI n ≤ M (t -σ, t) ≤ βI n . (7)
The following result was stated in (Anderson et al., 1986, p. 38 2 For a rigorous proof of this result, it should be shown that the existence of σ, α, β implies the existence of σ, α, β, and vice versa. No such proof was given in [START_REF] Anderson | Stability of adaptive systems: passivity and averaging analysis[END_REF]. The same lemma (up to minor differences) is presented in [START_REF] Sastry | Adaptive Control: Stability, Convergence and Robustness[END_REF][START_REF] Ioannou | Robust Adaptive Control[END_REF] with similar proofs, but some details merit revision and comments, as discussed in Appendix A. Throughout this paper, " • " will denote the Euclidean vector norm or the matrix norm induced by the Euclidean vector norm. Let us prove the following more complete result. Lemma 2 Assume that the positive constants γ, η, ρ are such that the inequalities A(t) ≤ γ, C(t) ≤ η, K(t) ≤ ρ (8) hold for all t ∈ R, and that the observability Gramian of the matrix pair [A(t), C(t)] satisfies the inequalities (5) with some positive constants σ, α, β, then the observability Gramian of the matrix pair [(A(t)-K(t)C(t)), C(t)] satisfies the inequalities (7) with σ = σ and

α =        √ β -α + ϕα - √ β ϕ -1 2 > 0 if ϕ = 1 α 2 4β > 0 if ϕ = 1 (9a) β = β -α + ψβ + β 2 (9b)
where

ϕ = η 2 ρ 2 e 2γσ -1 4γ 2 - σ 2γ (10) ψ = η 2 ρ 2 e 2(γ+ηρ)σ -1 4(γ + ηρ) 2 - σ 2(γ + ηρ) . ( 11
) 2 Notice the "symmetry" between A(t) and Ã(t) A(t)-K(t)C(t), (12) in the sense that A(t) = Ã(t) -(-K(t))C(t), (13)
hence the converse of Lemma 2 is implied by the lemma itself.

The proof of Lemma 2 will need the following result. Lemma 3 Let Φ(t, t 0 ) be the state transition matrix of ẋ(t) = A(t)x(t) with A(t) ≤ γ, then Φ(t, t 0 ) ≤ e γ|t-t0| for all t, t 0 ∈ R. 2 See [START_REF] Chicone | Ordinary Differential Equations with Applications[END_REF], Theorem 2.4. for a proof of this result.

Proof of Lemma 2

Let us first establish the relationship between Φ(t, t 0 ) and Φ(t, t 0 ). The solution of (3a), with some initial state x(t 0 ), is

x(t) = Φ(t, t 0 )x(t 0 ).
(14) On the other hand, rewrite (3a) as

ẋ(t) = A(t)x(t) -K(t)C(t)x(t) (15)
and treat -K(t)C(t)x(t) = -K(t)C(t) Φ(t, t 0 )x(t 0 ) as the input term, then

x(t) = Φ(t, t 0 )x(t 0 )- t t0 Φ(t, p)K(p)C(p) Φ(p, t 0 )x(t 0 )dp.
(16) For any initial state x(t 0 ) ∈ R n , the right hand sides of ( 14) and of ( 16) are equal, hence

Φ(t, t 0 ) = Φ(t, t 0 ) - t t0 Φ(t, p)K(p)C(p) Φ(p, t 0 )dp.
This equation holds for any pair of real numbers (t, t 0 ), which can be replaced by any other pairs, say (s, t),

Φ(s, t) -Φ(s, t) = - s t Φ(s, p)K(p)C(p) Φ(p, t)dp.
(17) Left multiply both sides by C(s) and right multiply by any (arbitrary) unit vector v ∈ R n , and take the integral of the squared norm of both sides, then

t t-σ C(s) Φ(s, t) -Φ(s, t) v 2 ds = t t-σ C(s) t s Φ(s, p)K(p)C(p) Φ(p, t)vdp 2 ds.
Develop the squared Euclidean norm at the left hand side and rearrange the terms, then

t t-σ C(s)Φ(s, t)v 2 ds = - t t-σ C(s) Φ(s, t)v 2 ds + t t-σ 2v T Φ T (s, t)C T (s)C(s) Φ(s, t)vds + t t-σ C(s) t s Φ(s, p)K(p)C(p) Φ(p, t)vdp 2 ds. ( 18
)
Each of the terms involved in (18) will be examined in the following in order to derive an inequality bounding the observability Gramian.

As v = 1 (unit vector), it follows from (5) that

α = v T αI n v ≤ v T M (t -σ, t)v = t t-σ C(s)Φ(s, t)v 2 ds ≤ v T βI n v = β, therefore α ≤ t t-σ C(s)Φ(s, t)v 2 ds ≤ β. (19)
Define

χ t t-σ C(s) Φ(s, t)v 2 ds = v T M (t -σ, t)v. ( 20
)
By the Schwarz inequality,

t t-σ 2v T Φ T (s, t)C T (s)C(s) Φ(s, t)vds ≤ 2 t t-σ C(s)Φ(s, t)v 2 ds t t-σ C(s) Φ(s, t)v 2 ds ≤ 2 βχ (21)
where the last inequality is based on ( 19) and ( 20).

The assumption that A(t) ≤ γ implies (see Lemma 3) Φ(s, p) ≤ e γ|s-p| .

(22) Notice that in the inner integral of the last term of ( 18

) t -σ ≤ s ≤ p ≤ t, then t s Φ(s, p) 2 dp ≤ t s e 2γ(p-s) dp (23) = 1 2γ e 2γ(t-s) -1 . (24)
Replace C(s) and K(p) by their respective upper bounds and apply the Schwarz inequality to the inner integral of the last term of (18), then

t t-σ C(s) t s Φ(s, p)K(p)C(p) Φ(p, t)vdp 2 ds ≤ η 2 ρ 2 t t-σ t s Φ(s, p) 2 dp t s C(p) Φ(p, t)v 2 dpds ≤ η 2 ρ 2 t t-σ 1 2γ e 2γ(t-s) -1 χ ds = η 2 ρ 2 1 4γ 2 (e 2γσ -1) - σ 2γ χ. ( 25
)
It then follows from ( 18), ( 19), ( 20), ( 21) and ( 25) that

α ≤ -χ + 2 βχ + ϕχ (26) with ϕ η 2 ρ 2 e 2γσ -1 4γ 2 - σ 2γ . (27)
Treat (26) as a polynomial inequality in terms of √ χ, of second degree if ϕ = 1, or of first degree otherwise.

Some straight-forward computations then show that

χ ≥        √ β -α + ϕα - √ β ϕ -1 2 > 0 if ϕ = 1 α 2 4β > 0 if ϕ = 1 (28)
As χ is defined in (20) with an arbitrary unit vector v ∈ R n , the result expressed in (28) provides a lower bound of M (t -σ, t), namely α as stated in Lemma 2.

The upper bound of M (t -σ, t) will be established similarly. Due to the "symmetry" between A(t) and Ã(t) expressed in ( 12) and ( 13), the "symmetric" counterpart of ( 18) corresponds to interchanging Φ(s, t) and Φ(s, t) and replacing K(p) by -K(p). It results in

t t-σ C(s) Φ(s, t)v 2 ds = - t t-σ C(s)Φ(s, t)v 2 ds + t t-σ 2v T ΦT (s, t)C T (s)C(s)Φ(s, t)vds + t t-σ C(s) t s Φ(s, p)K(p)C(p)Φ(p, t)vdp 2 ds.
Interchange the positions of the left hand side term and the first term of the right hand side, then, by reminding ( 19),

α ≤ t t-σ C(s)Φ(s, t)v 2 ds = - t t-σ C(s) Φ(s, t)v 2 ds + t t-σ 2v T ΦT (s, t)C T (s)C(s)Φ(s, t)vds + t t-σ C(s) t s Φ(s, p)K(p)C(p)Φ(p, t)vdp 2 ds (29)
Like in the case of ( 21), the Schwarz inequality is applied to the second term of the right hand side of (29). The inequality Φ(s, p) ≤ e (γ+ηρ)|s-p| (30) is derived from Lemma 3. By treating the last term of (29) in the same manner as the last term of (18), then (29) leads to

α ≤ -χ + 2 βχ + ψβ (31) with ψ η 2 ρ 2 e 2(γ+ηρ)σ -1 4(γ + ηρ) 2 - σ 2(γ + ηρ)
.

Treat (31) as a second degree polynomial inequality in terms of √ χ, it then yields

χ ≤ ( β -α + ψβ + β) 2 , ( 32
)
establishing an upper bound of M (t -σ, t), namely β as stated in Lemma 2. 2

A more accurate bound estimation

In the proof of Lemma 2, the lower bound was based on inequality (26), whereas the upper bound based on inequality (31). In fact, each of these two inequalities constrains both the lower and the upper bounds. In the previous section, the choice of ignoring the intersection of the solutions of the two inequalities was for the purpose of deriving lower and upper bounds in a relatively simple form. In what follows, a more accurate estimate of the two bounds will be established, by carefully taking into account this intersection. Lemma 4 Under the same assumptions and with the same notations as in Lemma 2, an estimation of the lower and upper bounds α and β as defined in (7) is given as follows, exhaustively in four different situations (notice that 0 ≤ ϕ ≤ ψ always hold, following the definitions (10) and ( 11)

): if 0 ≤ ϕ ≤ ψ < α β < 1, then α = max √ β -β -(1 -ϕ) α 1 -ϕ 2 , β -β + ψβ -α 2 (33)
≤ β = min √ β + β -(1 -ϕ) α 1 -ϕ 2 , β + β + ψβ -α 2 ; ( 34
) if 0 ≤ ϕ < 1, α β ≤ ψ and ϕ ≤ ψ, then α = √ β -β -(1 -ϕ) α 1 -ϕ 2 (35) ≤ β = min √ β + β -(1 -ϕ) α 1 -ϕ 2 , β + β + ψβ -α 2 ; ( 36
) if 1 = ϕ ≤ ψ, then α = α 2 4β (37) < β = β + β + ψβ -α 2 ; (38) if 1 < ϕ ≤ ψ, then α = - √ β + β + (ϕ -1) α ϕ -1 2 (39) ≤ β = β + β + ψβ -α 2 . ( 40
)
2 Following the same symmetry remark as in the case of Lemma 2, the converse of Lemma 4 is also implied by the lemma itself.

Proof of Lemma 4

The proof will be based on inequalities ( 26) and ( 31), which are established in the proof of Lemma 2 under the same conditions as the present lemma. The proof consists of 3 steps: the computations of the solution sets of inequalities ( 26) and ( 31) in the first two steps, then the combination of them in the last step.

Step 1: solution of inequality (26) First notice that β > α > 0 and ϕ ≥ 0 imply 4β + 4 (ϕ -1) α > 0. This fact is useful for solving inequality (26). Treat (26) as a polynomial inequality in terms of √ χ.

The solution is found in the following cases.

Case 1a: ϕ > 1. It is straightforward to check

- √ β + β + (ϕ -1) α ϕ -1 2 ≤ χ.
Case 1b: ϕ < 1. Similarly,

√ β -β -(1 -ϕ) α 1 -ϕ 2 ≤ χ ≤ √ β + β -(1 -ϕ) α 1 -ϕ 2 . Case 1c: ϕ = 1. More easily, χ ≥ α 2 4β .
Step 2: solution of inequality (31) Notice that β -α + βψ > 0 always holds and treat (31) as a polynomial inequality in terms of √ χ, the solution is found in the following cases. Case 2a: α -ψβ > 0. The solution is

β -β + ψβ -α 2 ≤ χ ≤ β + β + ψβ -α 2 . Case 2b: α -ψβ ≤ 0. Similarly, 0 ≤ χ ≤ β + β + ψβ -α 2 .
Step 3: combination of the two inequality solutions

The lower and upper bounds α and β as defined in ( 7) are derived by taking the intersection of the two solution sets bounding χ in the two previous steps. To this end, the following facts will be used to ensure that α ≤ β:

if 0 ≤ ϕ ≤ ψ < α β < 1, then √ β -β -(1 -ϕ) α 1 -ϕ ≤ β + β + ψβ -α; (41) β -β + ψβ -α ≤ √ β + β -(1 -ϕ) α 1 -ϕ ; (42) if 0 ≤ ϕ < 1, α β ≤ ψ and ϕ ≤ ψ, then √ β -β -(1 -ϕ) α 1 -ϕ ≤ β + β + ψβ -α; (43) if 1 = ϕ ≤ ψ, then α 2 √ β < β + β + ψβ -α; (44) if 1 < ϕ ≤ ψ, then - √ β + β + (ϕ -1) α ϕ -1 ≤ β + β + ψβ -α. (45)
The proof of these inequalities involves only tedious elementary mathematics.

Based on these results, the combination of Steps 1 and 2 lead to the lower and upper bounds α and β as summarized in Lemma 4. 2

A numerical example

Consider the example

A =        0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0        , C =     1 1 1 1 0 1 0 0 0 0 1 1     , K =        1 1 1 1 1 1 1 1 0 1 0 0        , σ = 1.
The lower and upper bounds of the symmetric positive definite matrix M (t-1, t) are taken as its smallest and largest eigenvalues α = 0.1160, β = 2.8384. The constants defined in (8) are γ = 1, η = 2.3244, ρ = 2.8092. According to Lemma 2, the lower and upper bounds of M (t-1, t) in this example are respectively 6.5340 × 10 -4 I 4 and 1.8555 × 10 6 I 4 . The bounds of (Ioannou and Sun, 1996, p. 226) are a revised version of those of (Sastry and Bodson, 1989, p. 73). After a correction of the bounds of [START_REF] Ioannou | Robust Adaptive Control[END_REF] suggested by the Associate Editor in charge of the present paper (see Appendix A), the lower and upper bounds of M (t -1, t) are respectively 4.2289 × 10 -4 I 4 and 6.9497 × 10 119 I 4 .

Conclusion

This paper presented a complete proof of a classical result on the bounds of observability Gramian. This result is useful for the analysis of some adaptive systems. Two estimations of the bounds of the closed loop system observability Gramian are presented, at different levels of complexity and accuracy.

In this paper "UCO" is used either as a noun or as an adjective. Some variants of the definition exist[START_REF] Sastry | Adaptive Control: Stability, Convergence and Robustness[END_REF][START_REF] Ioannou | Robust Adaptive Control[END_REF]. The definition recalled here follows[START_REF] Kalman | New methods in Wiener filtering theory[END_REF].Preprint submitted to Automatica

Acknowledgement. The authors would like to thank the associate editor and the reviewers for their comments that have helped to improve this paper.

This work has been supported by the ITEA MODRIO project.

A Discussion on existing results

In (Sastry and Bodson, 1989, p. 73), Lemma 2.5.2 is about the relation between the matrix pairs [A(t), C(t)] and [A(t), (A(t) + K(t)C(t))], which is equivalent to the case considered in this paper, up to the sign of K(t). The proof of Lemma 2.5.2 on page 332 starts by considering the two systems

) with respectively their associated state transition matrices Φ(t, t 0 ) and Φ(t, t 0 ). The authors then introduce the unit vector

which is required in the following part of the proof. However, e(s) is not well defined when K(s)C(s)w(s) = 0. This situation can indeed happen for w(s) = 0 if the matrix K(s)C(s) is rank deficient. In particular, e(t 0 ) is not well defined when the initial state w(t 0 ) satisfies K(t 0 )C(t 0 )w(t 0 ) = 0. Moreover, the following part of the proof looks for upper and lower bounds of

for all unit vector w(t 0 ) ∈ R n , where Φ(τ, t 0 ) is the state transition matrix associated to A(t) + K(t)C(t), hence it is impossible to avoid the case of K(s)C(s)w(s) = 0 when K(s)C(s) is rank deficient.

In (Ioannou and Sun, 1996, p. 226), the authors tried to remedy this problem with e(s)

Notice that e(s) is an n × m matrix in the second case of this new definition, whereas e(s) was always a vector in (A.3). One of the steps of the proof (see (Ioannou and Sun, 1996, p. 226), the line of two inequalities before 5 (4.8.10)) is based on the two inequalities

Unfortunately, inequality (A.5) is incorrect, as shown by the counter example

Following a suggestion by the Associate Editor in charge of this paper, the incorrect bound β 2 can be replaced by

Nevertheless, the modified definition of e(s) in (A.4) does not fully avoid the problem of division by zero, as C(s)w(s) = 0 does not prevent that K(s)C(s)w(s) = 0. The correction with β * 2 was for the mistake of inequality (A.5), it does not repair this problem of possible division by zero.


Keywords: Inverse scattering, cable health monitoring, soft fault diagnosis, frequency domain reflectometry

Recently published theoretic results and numerical simulations have shown the ability of inverse scattering-based methods to diagnose soft faults in electric cables, in particular, faults implying smooth spatial variations of cable characteristic parameters. The purpose of the present paper is to report laboratory experiments confirming the ability of the inverse scattering method for retrieving spatially distributed characteristic impedance from reflectometry measurements. Various smooth or stepped spatial variations of characteristic impedance profiles are tested. The tested electric cables are CAN unshielded twisted pairs used in trucks and coaxial cables.

I. INTRODUCTION

HE FAST development of electronic devices in modern engineering systems comes with more and more connections through cables, and consequently, the reliability of electric connections becomes a crucial issue. For example, in a modern automotive vehicle, the total length of onboard cables has tremendously increased during the last decades and is now up to 4km. These cables are composed of twisted pairs, coaxial cables, simple wires and many different connectors. These wires and connectors are subject to aging or degradation because of severe environmental conditions. In this area, reliability becomes a safety issue. In some other domains, cable defects may have catastrophic consequences [START_REF] Furse | A Critical Comparison of Reflectometry Methods for Location of Wiring Faults[END_REF]. It is thus a crucial challenge to design smart embedded diagnosis systems able to detect wired connection defects in real time. This fact has motivated research projects on methods for fault diagnosis in electric transmission lines. Many diagnosis methods based on Time or Frequency Domain Reflectometry (TDR or FDR) have been developed to detect, locate and characterize defects in electrical harnesses [START_REF] Furse | Spread spectrum sensors for critical fault location on live wire networks[END_REF]- [START_REF] Loete | Diagnostic of connectors degradation level by frequency domain reflectometry[END_REF] [START_REF] Furse | Frequency domain reflectometry for on board testing of aging aircraft wiring[END_REF]. These methods are based on the same principle as radar technology, but applied to guided waves in electric cables. A high frequency electrical signal is sent down a cable, where it is reflected at impedance discontinuities or at other inhomogeneities along the cable. The reflected wave is analyzed to detect, locate and characterize the defects. It has been reported that this technology is able to detect and to locate hard faults (open or short circuits) up to an accuracy of about 3 cm [START_REF] Smith | Fault location on aircraft wiring using spread spectrum time domain reflectometry[END_REF]. On the other hand, it is a much more difficult problem to deal with soft faults which imply only smooth and localized characteristic impedance changes in electric cables. Some recent methods have been reported that amplify fault signatures and improve the detection of the small echoes caused by soft faults [START_REF] Franchet | The use of the pseudo wigner ville transform for detecting soft defects in electric cables[END_REF]- [START_REF] Abboud | A non-iterative method for locating soft faults in complex wire networks[END_REF] but, except for connectors [START_REF] Loete | Diagnostic of connectors degradation level by frequency domain reflectometry[END_REF], to our knowledge, no satisfactory experimental result of reflectometry-based method for the diagnosis of such soft faults has been reported. The characteristic impedance is the main parameter characterizing an electric cable. When a healthy and uniform cable is considered, the characteristic impedance is usually specified as a single value for the whole cable. In order to deal with localized defects, it is necessary to consider distributed characteristic impedance all along the cable, denoted as with indicating the position along the cable in some coordinate system.

In traditional reflectometry-based methods, the reflected waveforms are visualized and analyzed in the time domain (TDR) or in the frequency domain (FDR), and sometimes a mixture of them is used. As these methods do not directly analyze the characteristic impedance of the cable, it may be difficult to interpret their results for soft faults diagnosis, in particular when such faults do not cause any discontinuity, but only smooth 4 variations of the characteristic impedance along the cable. It is thus useful to develop inverse methods retrieving the spatially distributed characteristic impedance profile from reflectometry measurements (in opposition to direct methods simulating reflectometry measurements from specified cable characteristics), but few methods of this nature have been reported [START_REF] Smail | Detection and location of defects in wiring networks using Time Domain reflectometry and neural networks[END_REF]. The inverse scattering theory [START_REF] Jaulent | The inverse scattering problem for LCRG transmission lines[END_REF] provides a powerful theoretic framework for the estimation of distributed characteristic impedance from reflectometry measurements, in particular for smoothly varying characteristic impedance profiles along cables. Based on this theory, the ability of directly visualizing and analyzing the distributed characteristic impedance of a cable opened a new avenue for the interpretation and processing of reflectometry measurements, notably for the purpose of soft fault diagnosis. The theoretic study and numerical simulations reported in [START_REF] Zhang | Inverse scattering for soft fault diagnosis in electric transmission lines[END_REF], [START_REF] Tang | An inverse scattering approach to soft fault diagnosis in lossy electric transmission lines[END_REF] have shown that the inverse scattering method is a promising tool for soft fault diagnosis through the estimation of distributed characteristic impedance. The purpose of the present paper is to confirm these results through laboratory experiments. Some preliminary experiments have been presented in [START_REF] Loete | Inverse scattering experiments for electrical cable soft fault diagnosis and connector location[END_REF]. The present paper presents more complete experimental results, including a study on the errors of characteristic impedance estimation by the inverse scattering method.

This paper is organized as follows. After briefly recalling in Section II the inverse scattering method for electric cable monitoring, in Section III experimental results will be presented with cables exhibiting smooth characteristic impedance variations. The robustness of the inverse scattering method to characteristic impedance discontinuities is experimentally studied in Section IV. Section V then concludes the paper.

II. THE INVERSE SCATTERING METHOD

This section shortly recalls the inverse scattering method for lossless cables. More details can be found in [START_REF] Zhang | Inverse scattering for soft fault diagnosis in electric transmission lines[END_REF]. For the electric cables of less than 10 meters length studied in this paper, losses are neglected. A lossless cable driven by a harmonic voltage wave can be modeled by the frequency domain telegrapher's equations

, , 0 (1a)
, , 0 (1b)
where is the angular frequency (denoted so because it is strongly related to the wavenumber in the inverse scattering theory), , and , denote the voltage and the current, and are distributed inductance and capacitance at the point along the cable; is the imaginary unit. The boundary conditions associated to (1) represent a generator at the left end and a load at the right end of the cable.

Define the electrical distance, the characteristic impedance, the reflected and direct power waves, as follows 5 , ∈ 0, 5 Where is the length of the cable and is a monotonic function, implying the existence of its inverse function

(2) ν , , , (3a)
. By abuse of notation,

ν , , , (3b)
Some direct computations then lead to the following Zakharov-Shabat equations [START_REF] Jaulent | The inverse scattering problem for LCRG transmission lines[END_REF]:

ν , ν , ν , (4a) ν , ν , ν , (4b) where (5)
In theory, it is assumed that the function is absolutely continuous, so that its scattering transform is well defined [START_REF] Ramm | A new approach to the inverse scattering and spectral problems for the Sturm-Liouville equation[END_REF]. This smoothness assumption means essentially that is continuously differentiable and does not vanish on the interval 0,

. In practice it excludes high frequency variations beyond the instrumentation bandwidth.

At the left end (corresponding to 0), the reflection coefficient ν , 0 /ν , 0 is typically measured with a network analyzer. It is known [START_REF] Zhang | Inverse scattering for soft fault diagnosis in electric transmission lines[END_REF] that the characteristic impedance can be computed from measured at the left end of the cable through the following steps:

1. Compute the Fourier transform of the reflection coefficient . where 0 is equal to the internal impedance of the signal generator connected to the left end of the cable (typically integrated in a network analyzer).

V ,

will be simply written as V , , so will other similar notations depending on .

III. EXPERIMENTS WITH TWISTED PAIRS

In order to experimentally validate the inverse scattering method for estimating the distributed characteristic impedance along a cable, we need to configure electrical cables with known smooth spatial variations of the characteristic impedance. It is realized with twisted pairs for the experiments reported in this section.

A. Inverse scattering for a cable with smoothly varying impedance profile

The characteristic impedance profile of a cable composed of two wires can be easily modified by controlling locally the distance between the two wires. Based on a geometrical model of the cable characteristics, particular forms of the characteristic impedance profile can be realized in this way. Such modified cables will be used to experiment the inverse scattering method, by comparing the characteristic impedance profile computed by inverse scattering method with the one known from the geometric model.

In the lossless case, the characteristic impedance , as defined in equations ( 2), depends only on the inductance L and the capacitance C per unit length. It is known that L and C for a cable composed of two wires are determined by the radius r of the copper wires, the distance D between the two wires, the magnetic permeability and the dielectric permittivity of the air and the relative dielectric permittivity of the dielectric insulation, as formulated in the following equations:

(6a) (6b)
By choosing the distance between the two wires as a function of z, a particular characteristic impedance profile can be obtained. In this study, a cosine function is chosen:

1 2 ( 7
)
where 2mm is the diameter of the insulated wire, A = 4mm and l = 25cm, as shown in Before applying the inverse scattering method to such a cable, let us first experimentally verify the model of based on (2), (6a) and (6b). Given the characteristic impedance profile computed through ( 2), (6a), (6b) and ( 7) as shown in Fig. 2, we numerically simulate the impulse response (also known as the reflectogram) of the cable, and compare this simulated impulse response with the experimentally measured impulse response of the true cable. The experimental setup is presented in Fig. 3. At the left end, the cable is connected to a network analyzer (VNA), and the right end the cable is terminated by a 110 Ω resistance as load. The reflection coefficient measurement is carried out over the 2 MHz -1.102 GHz with 2 MHz frequency steps. The impulse response of the line is then obtained by computing the IFFT of the reflection coefficient. The results presented in Fig. 4 show a satisfactory agreement between the simulated and the experimental impulse responses of the tested cable. The maximum error is about 25% of the magnitude of the impulse response. Now we are going to apply the inverse scattering method to the same cable in order to retrieve the distributed characteristic impedance profile from the reflection coefficient measured with the network analyzer. Fig. 5 shows the results of the inverse scattering method for two experiments made on the same cable but with two different loads connected at the right end (resistances of 110 Ω and 220 Ω). The two curves in Fig. 5 are almost identical except at their right ends. The highest bump corresponds to the part of untwisted wires shown in Fig. 1. The right ends of the two curves correspond to the loads of 110 Ω and 220 Ω connected in the two experiments. The fact that the two curves are almost identical in their major part suggests that the variations in the two curves, except at the right end, do correspond to the geometrical variations of the same tested cable.

In Fig. 6 the part corresponding to the cosine untwisted wires is zoomed and compared to the curve computed from (2), (6a), (6b) and [START_REF] Furse | An inexpensive distance measuring system for navigation of robotic vehicles[END_REF]. The maximum error in percentage of the estimated characteristic impedance is similar to that of the impulse response shown in Fig. 4. The errors can be partly explained by the fact that the losses in the cable are neglected by the inverse scattering method. This fact is further confirmed by two more experiments with a longer cable segment inserted between the network analyzer and the cosine untwisted wires. As shown in Fig. 7, the part corresponding to the cosine untwisted wires (the same as in the previous experiments) produces a lower bump of the estimated characteristic impedance profile than in the previous experiments (170 Ω against 220 Ω). The farther is the untwisted part of the wires from the network analyzer, the more important is the effect of the losses neglected by the inverse scattering method. Nevertheless, if this artificially made characteristic impedance variation was caused by a fault of the cable (smooth variation of about 170 Ω), the accuracy of the inverse scattering method would be sufficient enough for the detection, location and characterization of the fault. In Fig. 7 the right ends of the two lines correspond to the two loads connected to the right end of the cable in the two experiments. There is a 14% error on the estimation of the 220 Ω. One explanation of this error is the effect of the losses neglected by the inverse scattering method. Another source of error is the impedance mismatch between the cable and the load, implying an impedance discontinuity, a case that is not covered by the inverse scattering method, in theory. More discussions about impedance discontinuities will be made in Section IV. Fig. 7: Inverse scattering performed on a longer twisted pair. The 0.25 m cosine profile is inserted between the two twisted pair segments of respectively 5.9 m and 0.9 m. In the two presented experiments the line is terminated with a 110 Ω load (-) or with a 220 Ω load (--).

B. Application to the monitoring of connectors on an automotive electrical harness

The characteristic impedance variation studied in the previous experiments is similar to those observed around connectors in automotive harnesses (see Fig. 8) where the distance between the two wires is increased. We then applied the inverse scattering method to the monitoring of twisted pairs and their connectors used in a truck. A cable of 5.4m long is linked to 0.9m of similar cable through the connector shown in Fig. 8. As shown in Fig. 9, the connector's location and the impedance variation caused by the connector can be inspected by the inverse scattering method. It is then possible to elaborate some diagnosis rules of the connector based on the evolution of the estimated impedance profile over the time [START_REF] Loete | Diagnostic of connectors degradation level by frequency domain reflectometry[END_REF].

IV. ROBUSTNESS OF THE INVERSE SCATTERING METHOD TO IMPEDANCE DISCONTINUITIES

Since equation (4) contains the spatial derivative of the characteristic impedance, it is assumed in theory that is derivable. Consequently, the inverse scattering method presented in section II is, in theory, limited to smooth characteristic impedance profiles, thus excluding the case of impedance discontinuities. Impedance discontinuities are frequently present in practice, typically at the connection between the network analyzer and the tested cable if there is an impedance mismatch. Nevertheless, experimental results reported in the previous section show that the inverse scattering method can tolerate impedance discontinuities to some extent, as e.g. with the impedance mismatch between the network analyzer and the cable, or with the mismatched load. The aim of this section is to further study the robustness of the inverse scattering method in presence of impedance discontinuities and to quantify the error.

The experiments presented in this section are designed with 50 Ω coaxial RG-58 cables with low loss characteristics. They also have good noise immunity, and a well-controlled spatially homogeneous 50 Ω characteristic impedance. The tested configurations are very simple, but they are in no way favorable to the inverse scattering method, because of impedance discontinuities. The accuracy of the characteristic impedance of the coaxial cables allows us to quantitatively evaluate the error of the inverse scattering method. The measurements are carried out over the 4 MHz -2204 MHz bandwidth with 4 MHz frequency steps.

In this section, coaxial cables will be used to build composite lines with piecewise constant characteristic impedance profiles. However, the applied inverse scattering algorithm is exactly the same one as in the previous section, which does not assume piecewise constant characteristic impedance profiles.

A. Characteristic impedance drop on a single segment

Two identical 50 Ω coaxial cables in parallel (Fig. 10) are used as an equivalent cable of 25 Ω. Similarly, three and four identical cables in parallel form respectively equivalent 16.67 Ω and 12.5 Ω cables. Such a composite segment is then connected to simple 50 Ω coaxial cables as shown in Fig 10 and illustrated in Fig. 11, in order to build a cable with piecewise constant characteristic impedance. The advantage of this configuration is the accuracy of the characteristic impedance (50 Ω, 25 Ω, etc.) in each segment, based on the high quality coaxial cables used in the experiment. Fig. 12 shows the inverse scattering results carried out on the cables illustrated in Fig. 11. The location of impedance discontinuities, as well as the impedance level of the composite segment, are estimated with a good accuracy. Nonetheless, one can see some artifacts in the part immediately following the segment composed of parallel cables, especially for strong impedance discontinuities. It is possible to remedy this drawback by increasing the bandwidth of the reflectometry measurements, but in practice the network analyzer has a limited bandwidth. These artifacts are also reduced by adding zeros to complete high frequency measurements (zero padding), because the inverse scattering algorithm then uses a smaller integration step size. For example, in one of the experiments, the same reflection coefficient is processed twice by the inverse scattering method, first with zero padding up to 15 GHz and then up to 30 GHz. The results are shown in Fig. 13, confirming that a higher zero padding improves the result. However, the practice of zero padding is limited by the computer memory size when the data are processed. The results shown in Fig. 12 have been obtained with zero padding up to 30 GHz.

Remember that this study is only for the purpose of evaluating the robustness of the inverse scattering method to impedance discontinuities. If it is known in advance that the tested cable has a piecewise constant characteristic impedance profile, some other methods designed for this particular case may be more appropriate.

Fig. 12: (z) profiles obtained by inverse scattering on the line including an (equivalent) segment of (-) 50 Ω (--) 25 Ω (▪▪) 16.6 Ω and (▪ ─) 12.5 Ω. Fig. 13: Comparison of two Z (z) profiles obtained by inverse scattering on the same line including an (equivalent) segment of 12.5 Ω with zero padding up to 15 GHz (-) and 30 GHz (--). These results show that a higher zero padding leads to a more accurate result.

B. Double characteristic impedance drop

This example is intended to study the ability of the inverse scattering method to estimate more complex discontinuous characteristic impedance profiles. As shown in Fig. 14, in the middle of a 50 Ω coaxial cable, a segment of doubled cables and another one of tripled cables are inserted, with equivalent characteristic impedances of 25 Ω and 16.67 Ω. The result of the inverse scattering method is also shown in Fig. 14. The characteristic impedance profile is estimated with a good accuracy, despite the multiple discontinuities present in the characteristic impedance profile.

In Fig. 14, the estimated characteristic impedance profile exhibits spikes at each junction between the different segments of the line (e.g. at the injection point, at the connection of the 50 Ω coaxial cable and the segment of doubled cables etc). These are caused by the 50 Ω connectors which are slightly improperly adapted to the line and furthermore locally add some extra lengths to the line (each straight or Tee connector adds about 2cm to the 50 Ω coaxial line). This explains the small two first impedance spikes observed at 0m and 0.6m. The spike at the third connection point (between the 25 Ω and the 16.66 Ω segments) is all the more observed since 3 BNC Tees are stacked in order to connect the doubled and tripled cables segments.

C. Accuracy of the inverse scattering method in the case of piecewise constant characteristic impedance profiles.

Remember that, in theory, the case of characteristic impedance with discontinuities is not suitable for the inverse scattering method. Nevertheless, the reported experiments show that this method can tolerate discontinuities to some extent. The results of section IV.A show that, the higher is the step jump of the characteristic impedance, the larger is the error of the inverse scattering method. To complete these results, numerical simulations have been made to further characterize the errors. The simulated cable configurations are similar to that of Fig. 11, but the characteristic impedance level jump in the middle segment can be freely chosen for numerical simulations. The reflection coefficients of the simulated cables with various impedance level jumps ΔZ are simulated in the 50Ω; 350Ω range and then are given as input to the inverse scattering method. The relative accuracy of the inverse scattering method was calculated as:

% ∆ ∆ ∆
where ∆ is the impedance level jump of the middle segment estimated by the inverse scattering method. The results are plotted in Fig. 15. As expected, the error is increasing with ΔZ.

Therefore, in presence of strong impedance jumps, the error term can rapidly reach quite high values. Nevertheless, when ∆ ∈ 50Ω; 100Ω , the error is less than 5%. So one must be careful when interpreting impedance values computed in presence of strong discontinuities.

When both smooth variations and discontinuities are present in the characteristic impedance profile of a cable, the reflection coefficient measured at one end of the cable is the result of all these imperfections of the cable. As waves injected in a cable are essentially reflected at the discontinuities, too strong discontinuities may mask the effects of the reflections caused by smooth variations. It is thus important to avoid strong discontinuities when smooth variations should be monitored. In the experiments reported in the previous section, it was shown that an impedance jump of 60 Ω (impedance mismatch between the network analyzer and the 110 Ω cable), and another one of 110 Ω (impedance mismatch between the 110 Ω cable and the 220 Ω load) are well tolerated when smoothly varying characteristic impedance profiles are estimated, with a satisfactory accuracy for the purpose of soft fault detection, location and characterization.

V. CONCLUSION

The experimental results presented in this paper confirm the previously reported theoretic results and numerical simulations about the inverse scattering method. These results provide a new way for the interpretation of reflectometry measurements. In the first experiment, a spatially smooth variation of the characteristic impedance was created by modifying the spacing of the two wires of a twisted pair. This well-controlled profile leads to a smoothly varying characteristic impedance, which can be computed through a geometric model of the cable. This result was in good agreement with the characteristic impedance profile estimated by the inverse scattering method. To further characterize the errors of the inverse scattering method, high quality coaxial cables were then used to build composite lines with piecewise constant characteristic impedance profiles. It is shown that the inverse scattering method can tolerate to some extent impedance discontinuities. The robustness of the inverse scattering method to moderate noises has been studied by numerical simulation in [START_REF] Zhang | Inverse scattering for soft fault diagnosis in electric transmission lines[END_REF] where it is shown that, when the signal-to-noise ratio is 24dB, the result of the proposed method is still satisfactory.

The reported results confirm the ability of the inverse scattering method for estimating smoothly varying characteristic impedance profiles, with a satisfactory accuracy for the purpose of soft fault diagnosis in electric cables. Moreover, the implemented inverse scattering algorithm is numerically efficient: for each of the experiments presented in this paper, the processing of the data by the inverse scattering algorithm takes less than a second on a typical notebook computer.

VI. ACKNOWLEGMENTS

This work has been supported by the ANR SODDA project.

1 2 exp 2 .

 2 Solve the integral equations (known as Gel'fand-Levitan-Marchenko equations) for their unknown kernels , and , :

  Fig 1. Following (6a), (6b) and (7) the computed distributed characteristic impedance corresponding to the cosine profile D(z) is shown in Fig. 2

Fig. 1 :

 1 Fig. 1: Untwisted pair with a cosine profile .

Fig. 2 :

 2 Fig. 2: Distributed characteristic impedance corresponding to the cosine profile.

Fig. 3 :

 3 Fig. 3: Experimental setup. The cosine profile is inserted between two 110 Ω twisted pair segments.

Fig. 4 :

 4 Fig. 4: Simulated (-) and experimental (--) impulse responses of the cable illustrated in Fig. 3.

Fig. 5 :

 5 Fig. 5: Inverse scattering performed on the cable including the cosine profile in two experiments, one with a 110 Ω load (-) and the other with a 220 Ω load (--).

Fig. 6 :

 6 Fig. 6: Comparison of the measured (-) and simulated (--) characteristic impedance of the cosine part of the cable.

Fig. 8 :

 8 Fig. 8: Spatial spacing variation of the two wires of a twisted pair around an automotive connector.

Fig. 9 :

 9 Fig. 9: Monitoring of a connector's impedance profile with the inverse scattering method.

.

Fig. 10 :

 10 Fig. 10: Composite line including two RG-58 50 Ω coaxial cables in parallel.

Fig. 11 :

 11 Fig. 11: Topology of the composite lines used. Equivalent cables of characteristic impedance smaller than 50 Ω are realized by putting multiple 50Ω coaxial cables in parallel.

Fig. 14 :

 14 Fig. 14: Above: Two segments of doubled and tripled cables inserted in the middle of a 50 Ω coaxial. Below: Result of the inverse scattering method.

Fig. 15 :

 15 Fig. 15: Inverse scattering method accuracy in case of impedance discontinuities. (▲)Accuracy obtained from the inversion of experimentally measured reflection coefficient. (■) Accuracy obtained from the inversion of simulated reflection coefficient.

Florent Loete is with GEEPS-SUPELEC, 11 rue Joliot Curie 91192 Gif sur Yvette, France. Contacting author email : florent.loete@supelec.fr

Qinghua Zhang is with Inria Rennes, Campus de Beaulieu,

Rennes, France.

Michel Sorine is with Inria Paris-Rocquencourt, Domaine de Voluceau, 78153 Le Chesnay, France.

The meaning of "smoothness" will be specified in Section II.Experimental validation of the inverse scattering method for distributed characteristic impedance estimationFlorent Loete[START_REF] Furse | A Critical Comparison of Reflectometry Methods for Location of Wiring Faults[END_REF] , Qinghua Zhang[START_REF] Furse | Spread spectrum sensors for critical fault location on live wire networks[END_REF] , and Michel Sorine[START_REF] Lelong | On line wiring diagnosis by modified spread spectrum time domain reflectometry[END_REF]