Grégory Smits
email: gregory.smits@irisa.fr

Pierre Nerzic
email: pierre.nerzic@irisa.fr

Olivier Pivert
email: olivier.pivert@irisa.fr

Marie-Jeanne Lesot
email: marie-jeanne.lesot@lip6.fr

Efficient Generation of Reliable Estimated Linguistic Summaries

Summarizing data with linguistic statements is a crucial and topical issue that has been largely addressed by the soft computing community. The goal of summarization is to generate statements that linguistically describe the properties observed in a dataset. This paper addresses the issue of efficiently extracting these summaries and rendering them to the final user, in the case where the data to be summarized are stored in a relational data base: it proposes a novel strategy that leverages the statistics about the data distribution maintained by the database system. This paper shows that reliable summaries can be very efficiently estimated based on these statistics only and without any costly data access. Additionally, it proposes a visualization of the set of extracted summaries that offers a fruitful interactive exploration tool to the user. Experiments performed on two real data bases show the relevance and efficiency of the proposed approach: with a negligible loss of accuracy, we provide the first linguistic summarization approach whose processing time does not depend on the size of the dataset. The generation of estimated linguistic summaries takes less than one second even for dataset containing millions of tuples.

I. INTRODUCTION

Many professional activities rely on the analysis of data with the aim of making decisions on the basis of facts or item descriptions. As the volume and heterogeneity of the datasets a user has to deal with are continuously increasing, the generation of meaningful but concise views of the data now constitutes a crucial task. Data summarization is a problem that has been deeply studied by both the DataBase (DB) community and the soft-computing community. Roughly speaking, the DB community has mainly addressed this issue in two ways: schema summarization [START_REF] Yu | Schema summarization[END_REF] and data/table selection [START_REF] Gyssens | A foundation for multi-dimensional databases[END_REF], [START_REF] Yang | Summarizing relational databases[END_REF].

The soft-computing community possesses a long history in data summarization, see e.g. the recent overview in [START_REF] Boran | An overview of methods for linguistic summarization with fuzzy sets[END_REF]. The specificity of its approach comes from the fact that the trends observed in the data are expressed in a linguistic way. These trends are usually structured wrt. a syntactic protoform, i.e. a template, that is generally of one of the two following forms in the case of numerical data [START_REF] Yager | A new approach to the summarization of data[END_REF], [START_REF] Kacprzyk | Protoforms of linguistic data summaries: Towards more general natural-language-based data mining tools[END_REF]: Q of the X's are/have P or Q of the P X's are/have also P , where X is the universe of discourse, i.e. the data to summarize, Q is a quantifier and the P s are summarizers generally expressed by means of conjunctions of linguistic labels. For example, for a data set describing commercial flights, these protoforms can be instantiated as most of the flights have short airtime or a minority of the flights from western airports have a very long arrival delay.

As detailed in Section II, that also provides a more formal description of the linguistic summarization task, the latter faces two major, related, issues, namely the computational cost of the summary extraction and the huge quantities of sentences that can be extracted.

This paper proposes to address these challenges in the case where the data to be summarized are stored in a Relational DataBase (RDB). When the summarization task concerns massive relational data, it is obviously inconceivable to scan or query the data to assess all the candidate linguistic statements. Moreover, contrary to DB querying where the exact answer to the user's query has to be computed, users expect from a data summary to obtain an insight about the data distribution and are thus willing to accept some controlled imprecision for the benefit of a better scalability.

We introduce in this paper a summarization strategy that aims at efficiently providing the user with linguistic descriptions of the data. Instead of scanning the data or executing queries to precisely quantify the cardinality of the different possible summarizers, we propose to take advantage of the RDB storage and to estimate these cardinalities using statistics about the data distribution that are maintained by any RDB Management System (RDBMS). Such statistics are mainly used by the RDBMS to derive query execution plans and to optimize selection queries. We study in this paper their interest in estimating the cardinality of a summarizer composed of a conjunction of fuzzy terms. Our goal is to show that reliable linguistic summaries can be generated in a very efficient way and without any access to the data themselves, thus allowing the management of massive data.

After having formalized the linguistic summarization task and put our approach into perspective with existing works in Section II, preliminary notions about RDBs are introduced in Section III. Section IV presents the proposed approach, detailing how DB statistics can be used to estimate the cardinalities required to extract summaries. Section V describes the derived extraction process and a measure to quantify the confidence of the generated summaries. Section VI gives the results of experiments performed on real data that show the relevance and efficiency of the proposed approach. Finally, we describe in Section VII a possible interactive tool to visualize the summaries generated by the proposed approach that eases the identification of the data relevant characteristics.

II. CONTEXT AND RELATED WORK

This section briefly recalls the formal definition of protoform-based linguistic summaries of data, before presenting some existing approaches dealing with its main challenge of efficient extraction.

A. Linguistic Summaries Based on Protoforms 1) General Principle: Protoform-based summarization strategies [START_REF] Yager | A new approach to the summarization of data[END_REF], [START_REF] Kacprzyk | Linguistic summaries of data using fuzzy logic[END_REF] take as input a set of data to be summarized, here denoted R, that contains the description of m tuples, R = {t 1 , t 2 , . . . , t m } wrt. n attributes {A 1 , A 2 , . . . , A n } that may be of a numerical or categorical type. Moreover users usually provide the definitions of linguistic labels corresponding to imprecise concepts they are interested in: they are defined as fuzzy linguistic variables, as detailed below.

The summarization process consists in projecting the data to summarize onto different conjunctive combinations of the linguistic terms. The cardinality associated with each combination of terms is also linguistically described using quantifiers, usually taken from standard a predefined list. In addition, a degree of truth is generally attached to each summary to quantify the extent to which it faithfully represents the data.

2) Vocabulary and Quantifiers: Formally, the considered vocabulary, denoted by V = {V 1 , . . . , V n }, consists of a set of linguistic variables, associated with each attribute: V j is a triple A j , {v j1 , . . . , v jqj }, {l j1 , . . . , l jqj } where q j denotes the number of modalities associated with attribute A j , v js denote their respective membership functions defined on domain D j and l js their respective linguistic labels, generally adjectives from the natural language. For instance, an attribute A describing prices may be associated with q A = 3 modalities, in turn associated with the labels l A1 ='cheap', l A2 ='reasonable' and l A3 ='expensive'.

It is assumed that the linguistic variables associated with an attribute, say A j , define a strong partition [START_REF] Ruspini | A new approach to clustering[END_REF]: ∀y ∈ D j , qj s=1 v js (y) = 1. As a consequence, any value y can be rewritten in terms of V and y can partially satisfy only up to two modalities, that besides have to be adjacent in the case of a numerical value.

Fuzzy quantifiers [START_REF] Kacprzyk | Softer" optimization and control models via fuzzy linguistic quantifiers[END_REF] linguistically describe relative or absolute cardinalities; in the relative case, they can for instance be taken from the classic partition illustrated in Figure 1.

3) Protoforms and Truth Degree: Many different types of protoforms have been proposed, in particular depending on the considered type of data, e.g. numerical vs time series [START_REF] Cariñena | A language for expressing fuzzy temporal rules[END_REF], [START_REF] Kacprzyk | Linguistic summarization of time series using a fuzzy quantifier driven aggregation[END_REF], [START_REF] Castillo-Ortega | Linguistic local change comparison of time series[END_REF], [START_REF] Almeida | Linguistic Summaries of Categorical Time Series Patient Data[END_REF], [START_REF] Moyse | Linguistic summaries for periodicity detection based on mathematical morphology[END_REF], and of the information a user may be interested in. In the case of numerical data, the two most classic syntactic structures of linguistic statements, introduced by Yager [START_REF] Yager | A new approach to the summarization of data[END_REF], [START_REF] Kacprzyk | Linguistic summaries of data using fuzzy logic[END_REF], are defined as Q R are/have P and Q P R are/have also P , where R is the considered data, P and P are conjunctions of terms taken from V and Q is a quantifier. The selection between the verbs "are" and "have" depends on the considered terms, to make the sentence as natural as possible from a linguistic point-of-view. The relevance of a candidate instantiated protoform for the considered data is then measured by a truth degree that quantifies its validity with respect to R. This truth degree may be computed in the following way that relies on Zadeh's interpretation of quantified statements [START_REF] Zadeh | Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic[END_REF], for the first type of considered protoform:

τ (Q R are/have P ) = µ Q r∈R µ P (r) |R| (1)

B. Efficient Summarization

Classically, two main, related, issues arise when extracting linguistic summaries to describe a given data set: the mining computational cost and the result size. Indeed, the number of output summaries in a naive setting is overwhelming and can make it very difficult for the user to get any benefit from the produced result. Whatever the considered protoform, the search space of possible summaries is huge and considering the volume of data to manage, efficient strategies have to be defined to reduce this search space or to avoid too many costly data access and to generate the most interesting summaries only.

Many methods have been proposed to tackle these two issues: the initial approach (see e.g. [START_REF] Rasmussen | Finding fuzzy and gradual functional dependencies with summarySQL[END_REF], [START_REF] Kacprzyk | On combining intelligent querying and data mining using fuzzy logic concepts[END_REF]) consisted in adopting a user-guided methodology, focusing on the instantiation of partially specified protoforms, limiting the number of data scans to identify the unspecified parts of the summaries. The exploitation of genetic algorithms has also been proposed to explore the whole search space efficiently [START_REF] George | Data summarization using genetic algorithms and fuzzy logic[END_REF].

More recent approaches focus on the issue of the result size and propose methods to a posteriori reduce the set of extracted summaries to the most relevant ones: they do not consider summaries individually, assessing their quality for instance through the truth degree recalled in Equation ( 1), but globally, in particular taking into account their relative redundancy, so as to output a compact final result. They differ by the criteria and rules they propose to prune them [START_REF] Pilarski | Linguistic summarization of databases with quantirius: a reduction algorithm for generated summaries[END_REF], [START_REF] Wilbik | On the generation of useful linguistic summaries of sequences[END_REF].

Other proposals aim at avoiding the generation of nonrelevant summaries that are later discarded, using integrated methods: some of them exploit the relations between linguistic summaries and fuzzy or quantitative association rules [START_REF] Kacprzyk | Linguistic summarization of data sets using association rules[END_REF], [START_REF] Kacprzyk | Derivation of linguistic summaries is inherently difficult: Can association rule mining help[END_REF], others exploit the same principle of anti-monotonicity of quality criteria, e.g. considering degree of focus or a measure inspired by the degree of appropriateness, beside the truth degree [START_REF] Wilbik | Towards an efficient generation of linguistic summaries of time series using a degree of focus[END_REF], [START_REF] Dijkman | Linguistic summarization of event logs-a practical approach[END_REF], [START_REF] Wilbik | A method for improving the generation of linguistic summaries[END_REF].

To the best of our knowledge, no method has been proposed to exploit the specific principles of a DB storage, as it is the case in this paper.

III. PRELIMINARIES: RELATIONAL DATA BASES

This paper focuses on the case where the data to be summarized are stored by an RDBMS in a set of relations linked by foreign key constraints. For the sake of clarity and simplicity, we thus consider that the data to summarize come from a relation R that may result from joins between different relations.

This section recalls the principle of the statistics maintained by the RDBMS and in particular the notion of selectivity degree.

A. Meta-data Table about the Tuple Distribution

For each attribute, the RDBMS maintains, transparently for the user, a meta-data table, stored in the so-called DB catalog, that describes the data distribution on the definition domain of the different attributes.

In the case of a numerical attribute, say A, the data distribution is described by a histogram of k intervals denoted by H A : {h 1 , h 2 , . . . , h k } and defined by their boundary values. These k intervals can be of different widths as their bounds are dynamically defined so as to guarantee that they all cover the same amount of data: narrow intervals thus describe dense areas of the definition domain.

In the case of categorical attributes, the data distribution is described by the list of the k most frequent values possessed by the tuples.

B. Associated Selectivity Degrees

For each interval (for numerical attributes) and for each frequent value (for categorical attributes), say h for simplicity, the RDBMS additionally stores and maintains a so-called selectivity degree that corresponds to a relative cardinality: this value in [0, 1], denoted by σ h , corresponds to an estimation of the proportion of tuples whose value falls in the interval or is equal to the given categorical value.

In the case of numerical attributes, as mentioned above, the interval widths are defined so that they cover the same amount of data. Therefore, for a histogram H A : {h 1 , h 2 , . . . , h k }, one should theoretically have σ h1 = σ h2 = . . . = σ h k . In practice, the RDBMS tries to maintain these selectivity degrees as close as possible, without achieving equality.

Given the selectivity degree of an interval h as computed by the RDBMS, the number of tuples associated with h, denoted by |h|, can then be computed as:

|h| = σ h × |R|.
The RDBMS then considers that these |h| tuples are uniformly distributed within the interval covered by h.

In the case of categorical attributes, the number of tuples concerned by a frequent value, say h, of selectivity σ h , is computed as for the numerical case: |h| = σ h × |R|. The selectivity degree of non-frequent values is then deduced: denoting H the set of frequent values for a given attribute A, the selectivity of a non-frequent value, say h , is computed as

σ h = 1 N (1 -h∈H σ h ),
where N is the number of non frequent distinct values for A.

In the rest of the paper, the term RDB statistics is used to name these histograms and lists of frequent values associated with their selectivity degrees. In this section, we show how RDB statistics maintained by any RDBMS can be used to efficiently derive interesting estimations of the cardinalities of a candidate summarizer P : it first considers the case of an atomic P , i.e. a summarizer defined as one of the linguistic labels, and the case of conjunctive summarizers, i.e. a combination of atomic labels. These estimations are then used in the algorithm proposed in Section V to establish relevant linguistic summaries of the data.

A. Case of Atomic Summarizers

This section first considers an atomic summarizer, denoted by P , associated with attribute A and fuzzy subset v. The task is to estimate the relative (wrt. the size of the considered relation) fuzzy cardinality of v based on the selectivity degrees attached to histograms (for the numerical case) and frequent categorical values (for the categorical case) in the DB metadata. Figure 2 provides a graphical representation of this issue for the case of a numerical attribute A.

We first explain how the relative cardinality of v, denoted by σ v , is computed in the case of a numerical attribute, thus involving the use of a histogram, to then show that the computation is mainly the same in the case of categorical values.

Let H : {h 1 , h 2 , . . . , h k } be the histogram maintained by the RDBMS for attribute A. The principle of the computation is to determine the extent to which each interval of the histogram contributes to the computation of σ v , and to thus sum up their selectivity degrees weighted by their respective contributions. For example, for the case represented in Figure 2, the selectivity of the third interval should be fully taken into account, whereas that of the second one should only contribute with an approximate weight of two thirds.

In order to have a tractable approach for this computation, an α-cut method is proposed: let α 1 = 1 > α 2 > . . . > α q = 0 + be a scale of membership degrees used to build α-cuts of v, respectively denoted by v α .

Then for each α i of the considered scale, one builds the fuzzy set of histogram intervals intersecting with v αi . We denote by H αi v such fuzzy set of the intervals from H concerned by v αi . Each histogram interval in H αi v , say h, is associated with a membership degree denoted by µ H α i v (h) that tells us about the overlapping ratio between h and v αi .

Based again on the hypothesis of uniform distribution of the tuples inside each histogram interval, we compute the selectivity of an α-cut in the following way:

f (H αi v ) = h∈H α i v µ H α i v (h) × σ h . (2)
It is straightforward to show that f is a capacity, as f (∅) = 0, f (H) = 1 and the use of the sum aggregator makes f a non-decreasing function of its argument. The estimation of the overall selectivity of v may thus be simply computed by a Choquet integral:

σ v = q i=2 α i × [f (H αi v ) -f (H αi-1 v )]. (3)
In the case of a categorical attribute and thus the use of a list of frequent values and their associated selectivity degrees instead of histograms, the only difference concerns the definition of the fuzzy set H αi v . Instead of gathering histogram intervals overlapping with v αi , H αi v contains the categorical values present in v αi . Let x be one these values, then the membership degree of x in H αi v is simply equal to its membership degree in v αi , i.e. µ H α i v (x) = µ v (x).

B. Case of Conjunctive Summarizers

When P is of a conjunctive type, P = P 1 ∧ . . . ∧ P u , the selectivity σ P has to be estimated from the individual selectivities of its conjuncts σ Pi , i = 1..u, respectively estimated using Equation (3) defined in the previous section. Indeed, an RDBMS only maintains statistics about tuples distribution on the different attributes individually, but not on the Cartesian product of their domains.

To estimate the cardinality of an intersection between two histogram intervals h a and h b of respective cardinality σ ha and σ h b , the RDBMS again applies the hypothesis of a uniform distribution of the tuples that are covered by h a on the definition domain of the attribute concerned by h b , hence the use of the probabilistic norm to compute the selectivity of h a ∧ h b .

Without any additional statistics about data distribution on conjunctions of properties, we cannot do better than using the same hypothesis of a uniform distribution of the tuples. The relative cardinality of a conjunctive summarizer is thus computed in the following way, for P = P 1 ∧ . . . ∧ P u :

σ P = i=1..u σ Pi . (4)
V. LINGUISTIC SUMMARIZATION USING RDB STATISTICS This section first details the proposed RDB-statistics-based summarization process (Section V-A) exploiting the estimation described in the previous section. Section VI-A3 then proposes a criterion to assess the reliability of this estimation, defining a confidence degree.

;

v 1 ^v2 v 1 ^v3 v 1 ^v4 v 3 ^v4 v 2 ^v3 v 2 ^v4 v 1 ^v2 ^v3 v 1 ^v2 ^v4 v 2 ^v3 ^v4 v 1 ^v2 ^v3 ^v4 v 1 v 2 v 3 v 4
histogram-based estimation of the cardinalities Fig. 3. Apriori-like summarization process

A. Summarization Process

As reminded in Section II, the goal of a linguistic summarization process is to generate a set of sentences that the different data trends. These sentences are a predefined syntactic structure, Q R are/have P in our case, and use terms from the user vocabulary to form the summarizer P that may be of an atomic or conjunctive nature.

The summarization algorithm follows a principle similar to the one of the classic frequent itemset extraction algorithm APRIORI, it relies on a classical breadth first search of the lattice of the possible summarizers, lattice structured by means of an inclusion relation between the conjunctive terms. Each element of this lattice constitutes a summarizer P for which one has to compute its cardinality to then identify the quantifier that best describes it. Considering the fact that the available quantifiers form a Ruspini partition (Figure 1), we mean by "best quantifier" for a relative cardinality σ P , the relative quantifier Q such that µ Q (σ P ) ≥ 0.5. In the special case where two best quantifiers exist, i.e. when σ P is the middle point between two adjacent quantifiers, then one adopts a pessimistic choice by selecting the one describing lowest cardinalities.

The search space of the possible summarizers is depicted in Figure 3. Contrary to existing approaches that rely on a scan or a querying of the data, the strategy proposed in this paper uses the statistics maintained by any RBDMS about the data distribution to estimate the cardinality of each atomic summarizers (see Section IV-A), i.e. the cardinalities σ v1 , σ v2 , σ v3 and σ v4 in Figure 3. Once these cardinalities about each term from the vocabulary estimated, no more access to the DB statistics are needed as the cardinalities for conjunctive summarizers are estimated by aggregating the estimated cardinalities of their conjuncts (see Section IV-B and Equation ( 4)).

The relative cardinality of a conjunctive summarizer being estimated as the product of the cardinalities of its conjuncts, it is always strictly positive. A cardinality threshold κ is thus used to stop the exploration process when the current conjunction has a very low relative cardinality, e.g. below 0.01. However, it must be underlined that contrary to association rules that focus on main trends in the data, linguistic summaries also aim at extracting information about surprising or rare summarizers, in the case of summaries associated with the quantifier 'Few'. A low value of κ should thus be considered, that can be related to the fuzzy quantifier 'almost none'. The proposed linguistic statements being generated from estimated cardinalities, we consider important to be able to inform the user about the confidence the system has in each of these statements.

To this aim, we define in this section a measure that takes into account the possible imprecision of an estimated cardinality to quantify the confidence one can have in its associated linguistic statement. The confidence degree attached to a statement of the form S = Q R are/have P is denoted by η(S).

This degree depends on the estimated relative cardinality of P (i.e. σ P ). We propose to measure it as a function of its location in the membership function of the quantifier Q that best describes it: the closer this cardinality is to the middle of the core of the membership function of Q and the larger this core is, the higher the confidence. Indeed, if this cardinality falls close to the middle of the core of Q, then the imprecision of the estimated cardinality has a reduced impact on the choice of its attached quantifier . This principle is illustrated in Figure 4: one can be more confident in the linguistic rewriting of the estimated cardinality 0.8 by the quantifier most than for the cardinality 0.57. Indeed, a small variation in the estimation of 0.57 may turn it to 'around half'.

Formally, let Q be a quantifier of a trapezoidal shape whose 0.5-cut is the interval [a, b], then the confidence measure η is defined as follows:

η(Q R are/have P ) = 1 - | b-a 2 -σ P | b -a . ( 5
)
The confidence degree η defined in the unit interval may then be translated in a more interpretable way using a linguistic variable such as the one illustrated in Figure 5. We leverage this linguistic rewriting of the confidence degree in the graphical interface provided to the user described in Section VII.

VI. EXPERIMENTATIONS

Experimentations have been conducted to assess both the relevance and the efficiency of the proposed summarization strategy based on estimated cardinalities. The second dataset, named cars 3 , contains the description of 98,562 secondhand cars. A common sense vocabulary has also been defined on the six attributes {nbDoors, price, mileage, year, horsePower, initialNewPrice}.

A. Relevance of the RDB-statistics-based Cardinality Estimation

We successively assess the relevance of the proposed estimation based on selectivity degrees in terms of accuracy of the estimated value, accuracy of the selected quantifier and relevance of the computed confidence degree, as detailed in turn below.

1) Accuracy of the Estimated Relative Cardinalities: For the two datasets, we first compare the cardinality estimated from the RDB statistics and the real one (computed directly from the data) for each vocabulary term and also for each possible conjunctive combination of up to six terms (the cardinality threshold κ is set to 0.02). Figure 6 clearly shows that the difference of cardinality (y-axis) is rather low, especially for atomic properties (value 1 on the x-axis). Moreover, it stays low even for conjunctive properties (other values of the x-axis), showing no significant difference with the atomic case. The worst estimation indeed only differs from the real cardinality of 0.16 for the flights dataset and 0.13 for the cars dataset, and the difference is in average 0.01 for flights and 0.015 for cars.

2) Accuracy of the Summaries Generated from Estimated Relative Cardinalities: We then observe the impact of the use 1 Stored in a PostgreSQL server v.9.6 running on a 3,1 GHz i7 with 16 GB 1867 MHz DDR3. 2 This set is published by Research and Innovative Technology Administration (RITA) and Bureau of Transportation Statistics (BTS) http: //stat-computing.org/dataexpo/2009/the-data.html 3 Extracted from real classified ads published on leboncoin.fr of estimated cardinalities on the target task, i.e. the linguistic summarization of data. To do so, we compare the linguistic summaries generated based on the real cardinality with the ones generated based on the estimated ones. More precisely, for a given summarizer P , we check whether the quantifiers that best describe the real cardinality of P and its estimated one are the same. The result of this comparison for atomic summarizer as well as summarizers of two and four conjuncts are given in Figure 7 for the flights dataset and in Figure 8 for the cars dataset. The light grey part in each bar represents the number of summaries to find for the different quantifiers (i.e. summaries computed using the real cardinalities). The top dark grey part of each bar gives the number of summaries not found using RDB-statistics-based estimated cardinalities. For example, among the 22 expected atomic summaries of the form SOM E f lights are/have P , (left graph of Figure 7), only one is not correctly generated by our estimation-based approach. In this case and in all other error cases as well, the estimated cardinality is very close to the transition point between two adjacent quantifiers and a small difference of cardinality in such areas may lead to the choice of the wrong quantifier (e.g. most instead of few or vice-versa). But, as we will see in Section VI-A3, a confidence degree is computed to identify these cases.

The results of this study clearly show that cardinalities estimated from RDB statistics can be reliably used to identify the main trends in the data as all the summaries describing all, most or around half of the dataset are correctly generated by our approach. All of the errors concern inversions between some and few, i.e. minor trends; the average error rate for summaries involving up to six conjuncts is only 7% for the flights and 5% for the cars. 3) Relevance of the Confidence Degree: We also check that the confidence degree (as defined in Section VI-A3) attached to each estimated summary makes it possible to discriminate between the correct and the incorrect estimated summaries. It is worth recalling that by incorrect summaries we mean that a wrong quantifier is used to describe the estimated cardinality of a summarizer and that in all of the erroneous cases the quantifier used is adjacent to the correct one.

Figure 9 indicates the average confidence degree attached to correctly estimated summaries involving up to six conjuncts (values 1+, 2+, 3+, 4+, 5+ and 6+ on the x-axis) and the one attached to incorrect summaries involving up to six conjuncts (values 1-, 2-, 3-, 4-, 5and 6on the x-axis). For the two datasets, the confidence degree attached to each summary appears to be meaningful as it clearly distinguishes between the correctly and incorrectly estimated summaries. Whereas the previous experiments study the relevance of the proposed approach, this section considers the efficiency issue, in terms of needed computational time, with respect to the search space and the data sizes: we compare the time needed to generate the linguistic summaries of a dataset using cardinalities estimated from RDB-statistics, method denoted statBased hereafter, and using real cardinalities computed by querying the DB, method denoted queryBased. This last approach relying on DB queries integrates the pruning criteria of the search space (Figure 3) detailed in [START_REF] Dijkman | Linguistic summarization of event logs-a practical approach[END_REF] (pruning of conjunctions based on the monotonicity of the cardinality computation, implied quantifiers and summarizers).

1) Processing Time wrt. the Size of the Search Space: To observe the impact of the size of the search space (i.e. the lattice illustrated in Figure 3), we first compare the time needed (y-axis in second) by the two approaches, statBased vs. queryBased, to summarize the cars dataset wrt. the maximal number of conjuncts considered in the summarizers, from 1 to 6 conjuncts (x-axis).

Figure 10 and 11 clearly show that the time needed to summarize a relation (storing the cars dataset composed of 98,562 tuples in this case) grows exponentially wrt. the size of the search space, for both approaches.

2) Processing Time wrt. the Size of the Relation to Summarize: Another efficiency comparison criterion considers the processing time as a function of the data base size, it leads to a clear and indisputable conclusion. Indeed, an approach based on data access, as the queryBased one, is not scalable and cannot be envisaged to summarize large datasets such as the total flight ones. However, as confirmed by Figure 12, the proposed strategy exploiting the statistics about the data distribution available in any RDBMS without any additional computation, does not depend on the size of the dataset. Figure 12 indeed shows that the time needed (y-axis in second) by the statBased approach to generate all the linguistic summaries (still using κ = 0.02) is constant whatever the size of the flights dataset (x-axis in million of tuples). As a final comparison, it takes 4597 seconds to linguistically summarize a table of 7,000,000 flights using the queryBased approach (with indexes defined on each attribute to speed up the queries execution); it only takes 0.814 second for the statBased approach to generate the 333 linguistic statements with only 12 erroneous quantifiers (9 uses of some instead of few, and 3 uses of few instead of some).

VII. VISUALIZATION OF THE EXTRACTED LINGUISTIC SUMMARIES

Soft-computing-based strategies to data summarization generally generate a list of linguistic statements that are given to the user, in a decreasing order of their cardinality and truth degree. As mentioned in Section II, one of the challenges is the huge amount of produced results. We propose to address this issue using a graphical representation, that is in line with the user demands: domain experts faced with data analysis tasks are nowadays mainly looking for graphical views of the data and of the extracted knowledge [START_REF] Smits | Linguistic and graphical explanation of a clusterbased data structure[END_REF], [START_REF] Smits | Interactive data exploration on top of linguistic summaries[END_REF].

Instead of providing the user with an ordered list of linguistic phrases of the form Q R are/have P , we propose to only display the summarizers as a tag cloud. Figure 13 illustrates the proposed graphical rendering: the position and orientation is randomly set, the size of the font is proportional to the cardinality of the data subset it covers and the font color depends on the confidence in the estimated cardinality (Section VI-A3). The cloud simultaneously contains atomic and conjunctive summarizers.

On the top of the view, an interactive exploration tool offers the user the possibility to filter the set of summarizers according to their confidence, their cardinality (in Figure 13 only the properties describing at least around half of the data are shown), or/and the attribute they describe.

VIII. CONCLUSION AND FUTURE WORKS

In order to extract linguistic summaries, we propose a new approach in the prospect of handling large amounts of data. Instead of scanning or querying the data to identify relevant terms and conjunctions of terms from the user vocabulary that describe the data we propose to make the most of statistics about data distribution that are maintained by any RDBMS, to estimate the cardinality of the candidate summarizers, making it possible to identify the ones that best describe the data. In addition to this novel strategy of data summarization, we define a measure to quantify a confidence degree for each estimated cardinality. Experiments conducted on two different real data sets show the relevance of the estimated cardinalities and the efficiency of the summarization process that does not depend any more on the size of the dataset: it achieves a 10,000 speed up factor as compared to a query-based approach and it takes the same amount of time to summarize a dataset of one thousand tuples and a dataset containing millions of tuples. We also propose to graphically render and explore the linguistic statements that form the data summary.

An interesting aspect of this work comes from the intersection created between the soft computing, data mining and DB domains, and we plan to continue making the most of the complementarity of these fields for other data mining tasks, such as the related association rules discovery for instance. Another direction for future works concerns the summarization of tuples using other types of protoforms, in particular Q of the P R's are/have also P , which may require to precompute additional statistics and imply the proposal of dedicated strategies.

Fig. 1 .

 1 Fig. 1. Example of possible relative quantifiers

A h 1 h 2 h k v Fig. 2 .

 v2 Fig. 2. Cardinality estimation of a term using a histogram about data distribution

Fig. 5 .

 5 Fig. 4. Illustration of the confidence measure

Fig. 6 .

 6 Fig. 6. Cardinality comparison (left flights, right cars)

Fig. 7 .Fig. 8 .

 78 Fig. 7. Comparison of the selected quantifier, for the real and the estimated cardinality (flightsdata set): summarizers with one (left), two (center) and four conjuncts (right)

Fig. 9 .

 9 Fig. 9. Average confidence degree in the estimation, as a function of the summarizer size, for correctly (+ part) and incorrectly selected quantifiers (i part), left: flights data set, right: cars data set

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Computation time of the summarization wrt. the size of the search space: Method queryBased

Fig. 12 .Fig. 13 .

 1213 Fig. 12. Computation time of the statBased approach, for datasets of various sizes, defined as subparts of the flights dataset

Acknowledgments

This work has been partially funded by the French DGE (Direction Générale des Entreprises) under the project ODIN (Open Data INtelligence).


Carlos F Crispim-Junior

Qiao Ma

Baptiste Fosty

Rim Romdhane

Francois Bremond

Monique Thonnat

Combining Multiple Sensors for Event Detection of Older People

We herein present a hierarchical model-based framework for event detection using multiple sensors. Event models combine a priori knowledge of the scene (3D geometric and semantic information, such as contextual zones and equipment) with moving objects (e.g., a Person) detected by a video monitoring system. The event models follow a generic ontology based on natural language, which allows domain experts to easily adapt them. The framework novelty lies on combining multiple sensors at decision (event) level, and handling their conflict using a probabilistic approach. The event conflict handling consists of computing the reliability of each sensor before their fusion using an alternative combination rule for Dempster-Shafer Theory. The framework evaluation is performed on multisensor recording of instrumental activities of daily living (e.g., watching TV, writing a check, preparing tea, organizing week intake of prescribed medication) of participants of a clinical trial for Alzheimer's disease study. Two fusion cases are presented: the combination of events (or activities) from heterogeneous sensors (RGB ambient camera and a wearable inertial sensor) following a deterministic fashion, and the combination of conflicting events from video cameras with partially overlapped field of view (a RGB-and a RGB-D-camera, Kinect). Results showed the framework improves the event detection rate in both cases.

INTRODUCTION

Human Behavior (or event) monitoring has experienced continuous advances since last decade promoted by Computer Vision, Wearable and Ubiquitous Computing Fields. Examples of applications range from security field, such as video surveillance, crime prevention, and older people monitoring at home, to tools to support objective assessment of emerging symptoms of diseases (medical diagnosis), and even as a part of human-machine interfaces for game entertainment. [START_REF] Ali | A new combination rule for conflict problem of Dempster-Shafer evidence theory[END_REF] Wearable and Pervasive Computing communities have proposed multimodal event monitoring based on sensors such as, wearable inertial sensors, passive infrared presence sensors, change of state sensors, microphones. For instance, Gao et al. [START_REF] Gao | A system for activity recognition using multi-sensor fusion[END_REF] and Rong and Ming [START_REF] Rong | Recognizing Human Activities Based on Multi-Sensors Fusion[END_REF] have demonstrated the fusion of wearable inertial sensors at the waist, chest, and sides of a person body for the detection of daily living activities, where data fusion was carried out by classification methods (e.g., Naïve Bayes, C4.5). Although wearable inertial sensors provide a rich representation of body dynamics, they are subjected to problems such as motion noise, inter sensorcalibration, and in case of large scale research studies, the need of placing sensors in a relatively similar body position among monitored people, what may introduce noise in experimental data. Fleury et al. [START_REF] Fleury | Introducing knowledge in the process of supervised classification of activities of Daily Living in Health Smart Homes[END_REF] have presented a multi-modal event monitoring system using actimeters, microphones, PIR (Passive Infrared) presence sensor, and door contact sensors. Data fusion is performed using a SVM classifier. Medjahed and Boudy [START_REF] Medjahed | A pervasive multi-sensor data fusion for smart home healthcare monitoring[END_REF] have proposed a smart-home setting which performs event detection relying only on ambient sensors like infrared, change of state sensors, and microphones, and physiological sensors; all fused by a Fuzzy classifier.

Computer Vision approaches for event detection may be summarized in three categories (adapted from [START_REF] Lavee | Understanding Video Events: A Survey of Methods for Automatic Interpretation of Semantic Occurrences in Video[END_REF]): classification methods, probabilistic graphical models (PGM), and semantic models, which rely on at least of the following data abstraction: pixel-level, feature-level, or event-level. Probabilistic Graphical Models refer to techniques such as Conditional Random Fields, Dynamic Bayesian Networks, and Hidden Markov Models. Kitani et al. [START_REF] Kris | European Conference on Computer Vision[END_REF] has proposed a Hidden Variable Markov Model approach for event forecasting based on people trajectories and scene features. Examples of classification methods are Artificial Neural Networks, Support-Vector Machines (SVM), and Nearest Neighbor. In this context, Le et al. [START_REF] Le | Learning hierarchical invariant spatio-temporal features for action recognition with independent subspace analysis[END_REF] have presented an extension of the Independent Subspace Analysis algorithm applied for learning invariant spatio-temporal features from unlabeled video data for event detection. Wang et al. [START_REF] Wang | Action recognition by dense trajectories[END_REF] have proposed new descriptors for dense trajectory estimation in action representation as input for non-linear support vector machines. Although PGMs and classification methods have considerably increased the event detection performance in benchmark data sets, as they focus on pixel-and feature-based representations, they have limitations at describing the scene semantics and the temporal dynamics and hierarchical structure of complex events. Moreover, these approaches only focus on video data, ignoring other modalities which could provide additional information in the presence of ambiguous data.

In the recent domain of video search in internet videos, multimodal event analysis have investigated event representations consisting of different image cues, like motion and appearance, combined with other modalities such as audio and text, and exploring fusion in different data abstraction levels. Jhuo et al. [START_REF] Jhuo | Discovering joint audiovisual codewords for video event detection, pages=33-47[END_REF] introduced a feature-level representation which combines audio and video data by mapping the joint patterns among these two modalities. Myers et al. [START_REF] Myers | Evaluating multimedia features and fusion for example-based event detection[END_REF] have learned a set of base classifiers, each from a single data type/source (low-level vision, motion, audio, high-level visual concepts, or automatic speech recognition), and evaluated their fusion using different methods at event level (late fusion scheme). They report average output was one of the most effective fusion schemes. Similarly, Oh et al., [START_REF] Oh | Multimedia event detection with multimodal feature fusion and temporal concept localization[END_REF] have presented a multimodal (audio and video) system, where base classifiers are learned from different subsets of features, and score fusion are used to combine them into complex events. Mid-level features, such as object detectors, were employed to enrich event model semantics. Even though multimedia event analysis approaches have demonstrated significant advances by seeking to capture the hierarchical nature of events and incorporating auxiliary sources of information, most methods rely on learning steps involving large amounts of training data.

Semantic (or Description-based) models make use of a description language and logical operators to build event representations incorporating knowledge of domain expert. These languages allows to explicitly model the semantic information and hierarchical structure of event, besides to not require as much data as PGMs and classification methods. For instance, Zaidenberg et al. [START_REF] Zaidenberg | A generic framework for video understanding applied to group behavior recognition[END_REF] have presented a generic model-based framework for group behavior detection on surveillance applications such as airport, subway, and shopping center.

Cao et al. [START_REF] Cao | An event-driven context model in elderly health monitoring[END_REF] proposed a multimodal event detection where two context model are defined: the human and the environment contexts. The human context (e.g., body posture) is obtained from data of a set of cameras, while the environment context (semantic information about the scene) is based on accelerometer devices attached to objects of daily living which once manipulated trigger an event, (e.g., TV remote control or doors use). A rule-based reasoning engine is used for combining both context types at event detection level. Although semantic models ability to easily incorporate scene semantics, they are sensitivity to noise of underlying process, like image segmentation and people tracking in vision systems. To overcome such limitations, probabilistic frameworks may be adopted to handle data uncertainty as in [START_REF] Zouba | An Activity Monitoring System for Real Elderly at Home: Validation Study[END_REF] and [START_REF] Medjahed | A pervasive multi-sensor data fusion for smart home healthcare monitoring[END_REF]. For example, Zouba et al. [START_REF] Zouba | An Activity Monitoring System for Real Elderly at Home: Validation Study[END_REF] have evaluated a multimodal monitoring system at the identification of activities of daily living of older people on a model apartment. Video-camera data was used to track people over the scene and environmental sensor to obtain complementary data on object interaction. Dempster-Shafer theory was employed for reasoning under imprecise data.

This paper presents hierarchical model-based framework to multiple sensor context. We extend the generic ontology proposed by Vu et al. [START_REF] Vu | Automatic Video Interpretation: A Novel Algorithm for Temporal Scenario Recognition[END_REF] to describe event models in terms of elementary (low-level) events coming from different sensors, as a basis to infer Multimodal Complex Events. Event level fusion is chosen as it provides a flexible way to deal with sensor heterogeneity, and has been reported to presented a higher performance than early fusion schemes based on pixel-and feature-level representations [START_REF] Snoek | Early Versus Late Fusion in Semantic Video Analysis[END_REF] [START_REF] Myers | Evaluating multimedia features and fusion for example-based event detection[END_REF]. A Dempster-Shafer-based probabilistic approach is presented to handle event conflict using an adapted combination rule. The framework is evaluated on real multisensor recordings of participants of a clinical protocol for Alzheimer disease study.

HIERARCHICAL MODEL-BASED FRAMEWORK

The proposed framework is composed of two main components: an event ontology and a temporal event detection algorithm [START_REF] Vu | Automatic Video Interpretation: A Novel Algorithm for Temporal Scenario Recognition[END_REF]. The temporal algorithm is responsible for event inference based on the event models defined by domain expert and available input data. The video event ontology proposed in [START_REF] Vu | Automatic Video Interpretation: A Novel Algorithm for Temporal Scenario Recognition[END_REF] is extended for multiple sensor scenario (then referred as Event Ontology), and the temporal algorithm to deal with mutually exclusive conflicting events of different sensors during people monitoring.

Fig. 1 presents the architecture of the extended event detection framework, where a wearable inertial sensor and two video-cameras are given as examples of sensors. Sensor data is individually processed and their resulting output is taken as input for the multisensor framework (Event Detection Module). For instance, inertial sensor data would consist of a set of attribute-based events (e.g., from posture: person bending, person lying down), while for video camera data it would be a set of people detected in the scene and/or elementary events provided provided by vision module. All sensors are assumed to be time-synchronized.

Event Ontology or MultiModal

The event models are described using a constraint-based ontology language based on natural terminology to allow domain experts to easily add and change them. An event model is composed of up to six parts [START_REF] Vu | Automatic Video Interpretation: A Novel Algorithm for Temporal Scenario Recognition[END_REF]:

• Physical Objects refer to real objects involved in the recognition of the modeled event. Examples of physical object types are: mobile objects (e.g. person herein, or vehicle in another application), contextual objects (equipment) and contextual zones (chair zone); • Components refer to sub-events that the model is composed of; • Forbidden Components refer to events that should not occur in case of the event model is recognized; • Constraints are conditions that the physical objects and/or the components should hold. These constraints could be logical, spatial and temporal; • Alert describes the importance of a detection of the scenario model for a given specific treatment; and • Action in association with the Alert type describes a specific action which will be performed when an event of the described model is detected (e.g. send a SMS to a caregiver responsible to check a patient over a possible falling down).

Three types of Physical Object are defined: Mobile, Person, and Contextual Objects. Mobile class defines a set of attributes which be common to any mobile object (e.g., height, width, position, speed). Person class extends Mobile by adding person-related attributes like body posture, appearance, etc. Contextual Objects refer to a priori knowledge of the scene. A priori knowledge refers to a decomposition of a 3D projection of the scene floor plan into a set of spatial zones (e.g., TV zone, Armchair Zone), and equipment, (e.g., home appliances and furniture such as TV, armchair, Coffee machine) which hold semantic information to the modeled events. Constraints define conditions that physical object property(-ies) and/or components should satisfy. They can be non-temporal, such as spatial and appearance constraints; or they could be temporal and specify two instances ordering which should generate a third event, for example, Person crossing f rom Zone1toZone2 is defined as Person in zone1 before Person in zone2. Temporal constraints are expressed using Allen's interval algebra (e.g., BEFORE, MEET, and AND) [START_REF] Allen | Maintaining Knowledge about temporal intervals[END_REF].

The ontology hierarchically categorizes models according to their complexity on (in ascending order):

• Primitive State models an instantaneous value of a property of a physical object (Person posture, or Person inside a semantic zone). Fig. 2 presents a description of Primitive State called Person sitting, which checks whether the attribute posture of a person object assumes the value sitting. Fig. 3 presents an example of Composite Event, called Person sitting and using Office Desk, which defines a constraint between two sub-events (components). First component checks whether the person position lies inside of a priori defined zone relative to an office desk, while second component verifies whether the person posture is sitting (using Fig. 2 model). Model constraint defines the model will be valid when both components should are recognized at the same time (c1 AND c2).

Modeling Events from Different Sensors

Previous section has described how the event ontology categorizes and models events. We have chosen to model events generated by different sensor data using Primitive States, since they are the most basic building block of the event ontology.

Handling sensor input at an early stage in hierarchy level avoids the propagation of noise to high-level events, and also abstracts the derived models from the sensor data they are conditioned on.

Fig. 4 describes the class Person where an attribute is created for each posture estimation, e.g., Posture W I for the estimation from wearable inertial sensor, and Posture V for the estimation of the video-based algorithm.

Fig. 5 illustrates an example of Primitive state using the posture estimation from a inertial sensor. If one aims to increase system precision over recall, a Composite Event may be devised to combine (be composed of) both posture estimation Fig. 6 Person Sitting MS Fig. 7 presents the event model "Person sitting and using Office Desk" which relies on a multisensor event for the detection of posture sitting. Using an ontology language for event modeling on multisensor scenarios allows to decompose event complexity and provides a flexible way to add or change sensor-based events.

The presented model examples described how to combine estimations of multiple sensor over the same attribute of Person class. But, there is not restriction on how event models from different sensors are combined. A complex event model may have a person posture estimated from an inertial sensor (Posture W I) while his/her localization is provided by a vision system.

Event Conflict Handling

To address conflicting evidence among (mutually exclusive) events generated by different sensors, a probabilistic framework is proposed to assess event reliability for event fusion. The conflict handling framework works as follows: firstly, event instantaneous likelihood is computed; secondly, event temporal reliability is computed from the current and close past event instantaneous likelihood (see [START_REF] Romdhane | Complex Event Recognition with Uncertainty Handling[END_REF]); finally, a variant of Dempster-Shafer rule of combination is used to decide upon event reliability which of the events is being performed.

The event conflict handling framework is performed at primitive state level to reduce the propagation of noise from low-level components to hierarchically higher event models, abstract high-level events from the sensor estimated events, and derive semantically high-level event only from consolidated information.

Instantaneous likelihood of a Primitive State

The instantaneous likelihood of Primitive States is computed based on the feature(s) the event constraints are based on. Assuming the Primitive state feature (e.g., height) follows a Gaussian distribution, a learning step is performed a priori to obtain the expected feature distribution parameters (mean, µ, and variance, σ 2 ) given a primitive state and a sensor. The learning procedure is performed for each mutually exclusive event model affected by the analyzed feature.

Learned distribution parameters are then used during event inference (detection) to compute the instantaneous likelihood of an event given the feature value and the sensor providing it using Equation 1.

P inst Ω ,k,i = exp(-(Height Ω ,k,i -µ 2 Ω ,i )) 2σ 2 Ω ,i (1)
where, k: video frame number (current instant), Ω : event model, i: sensor identifier

Temporal reliability of a Primitive State

The instantaneous likelihood of the Primitive State considers the probability of a given primitive state (e.g., sitting, standing) been recognized at the current frame. But, noise from underlying vision algorithms can compromise the feature value which a primitive state is based on for a short interval of time, (e.g., problems at image segmentation can harm the height estimation of a person). To cope with instantaneous deviations of primitive state probabilities we compute the event temporal reliability which considers the instantaneous likelihood of an event and its previous values for a given time interval (time window). Equations 2 and 3 present an adapted computation of temporal reliability using a time window of fixed size [START_REF] Romdhane | Complex Event Recognition with Uncertainty Handling[END_REF]. A cooling function is used to reinforce the information of near frames and lessen the influence of farther ones. The window size parameter used in these equations was set to match the minimum expected duration of the modeled primitive states.

P temp Ω ,k,i = P inst Ω ,k,i + M ∑ t=k-1 t=k-w exp(-(k -t)) (2)
M = t=k-1 ∑ t=k-w [exp(-(k -t))(P temp Ω ,k,i -P inst Ω ,k,i )] (3)
where, k: video frame number (current instant), Ω : event model, i: sensor identifier, w: temporal window size Primitive State Temporal Reliability is then considered as a belief level value on "how strongly it is believed that the event generated by the sensor i is true at the evaluated time instant". From here on Primitive State Temporal Reliability will be referred as Primitive State Reliability.

Primitive State Conflict Handling

Once the reliability of all mutually exclusive Primitive States are computed it is then necessary to decide which events are being actually performed. To perform such task we have adopted Dempster-Shafer Theory (DS). DS theory was proposed by Dempster [START_REF] Dempster | Generalization of Bayesian inference[END_REF] and then improved by Shafer [START_REF] Shafer | A mathematical theory of evidence[END_REF]. It extends the Bayesian inference by allowing uncertainty reasoning based on incomplete information. The major components of evidence theory are the frame of discernment (Θ , Equation 4), and the basic probability assignment (BPA). The frame of discernment contains all possible mutually exclusive hypotheses.

Θ = {Sitting, Standing, ...} (4)
The BPA is a function m: 2 Θ → [0, 1] related to a proposition satisfying conditions ( 5) and ( 6) [START_REF] Ali | A new combination rule for conflict problem of Dempster-Shafer evidence theory[END_REF]:

m( / 0) = 0 (5) ∑ A∈Θ m(A) = 1 (6)
where, A is any subset of the frame of discernment, and refers to the empty set. For any A ∈ 2 Θ , m(A) is considered as the subjective confidence level on the event A. Accordingly, the whole body of evidence of one sensor is the set of all the BPAs greater than 0 (zero) under one frame of discernment. The combination of multiple evidences defined on the same frame of discernment is the combination of the confidence level values based on BPAs (e.g., pre-defined by experts). Given two sensors (1 and 2), where each sensor has its body of evidence (m s1 and m s2 ), these are the corresponding BPA functions of the frame of discernment. The combination rule of the classical DS theory can be implemented to fuse data from two sensors, but it can lead to illogical results in the presence of highly conflicting evidence [START_REF] Ali | A new combination rule for conflict problem of Dempster-Shafer evidence theory[END_REF]. We herein adapt the combination rule proposed by Ali et al. [START_REF] Ali | A new combination rule for conflict problem of Dempster-Shafer evidence theory[END_REF], as it has been demonstrated to provide more realistic results than the standard DS rule when combining conflicting evidence from multiple sources. Equations 7 and 8 present the mass function for computing Sitting (Sit.) and Standing (Sta.) primitive states, respectively:

(m s 1 m s 2)(Sit.) = (1 -(1 -m s 1(Sit.))(1 -m s 2(Sit.))) (1 + (1 -m s 1(Sit.))(1 -m s 2(Sit.))) (7)
(m s 1 m s 2)(Sta.) = (1 -(1 -m s 1(Sta.))(1 -m s 2(Sta.))) (1 + (1 -m s 1(Sta.))(1 -m s 2(Sta.))) (8)
Among a set of mutually exclusive events the framework chooses the event with the highest probability (mass function). The combination rule can be used on an iterative fashion to combine more than two body of evidence.

EVALUATION

To evaluate the proposed framework we have used multisensor recordings from real participants of a clinical protocol for Alzheimer disease study. This data set is chosen due to the growing applicability of monitoring systems for older people care, assisted living, and frailty diagnosis.

The event detection performance is evaluated in two scenarios: firstly, we compare the crisp multisensor approach using data from an 2D-RGB camera and a wearable inertial sensor to a mono-sensor (camera) approach. Inertial sensor raw data is pre-processed using its (proprietary) software to generate the list of postures performed by the participant during the experimentation. Multi-sensor event models use wearable inertial sensor data for posture-based events and video-based data for person localization in the scene. Second scenario evaluates the proposed probabilistic approach for event conflict handling on events generated by two vision modules (the 2D-RGB camera vision system and a variant of it using a RGBD sensor). For this scenario, posture data is obtained per vision module and then propagated for fusion in the form of events.

All sensors are assumed to be time synchronized, but none spatial correspondence is computed among the cameras in the second scenario. Briefly, we assume the multi-sensor system does not know the transformation function amongst the coordinate-systems of the cameras.

Performance Evaluation

Event detection performance is measured using the indexes of sensitivity, precision, and F-Score described in Equations 9, 10, and 11, respectively. System event detection is compared to event annotation performed by domain experts.

Sensitivity =

T P T P + FN (9)

Precision = T P T P + FP (10)
where, TP: True Positive rate, FP: False Positive rate, FN: False Negative rate.

F -Score = 2 * (Sensitivity * Precision) Sensitivity + Precision (11)

Vision Module

The Vision Module used to test the proposed framework is a evaluation platform locally developed that allows the testing of different algorithms for each step of the computer vision chain (e.g., video acquisition, image segmentation, physical objects detection, physical objects tracking, actor identification, and actor events detection). Image segmentation is performed by an extension of the Gaussian Mixture Model algorithm for background subtraction proposed by [START_REF] Nghiem | Controlling background subtraction algorithms for robust object detection[END_REF]. People tracking is performed by an implementation of the multi-feature tracking algorithm proposed in [START_REF] Chau | A multi-feature tracking algorithm enabling adaptation to context variations[END_REF], using the following features: 2D size, 3D displacement, color histogram, and dominant color. The vision component is responsible for detecting and tracking mobile objects on the scene. These objects (so-called physical objects) are classified according to a set of a priori defined classes, e.g., a person, a vehicle. The detected physical objects are then passed to the event detection module which assess whether the actions/activities of these actors match the event models defined by the domain experts.

Data set

Event Modeling

Each one of the eight focused IADL is modeled using two composite models and three primitive states. First composite model is composed of two of the primitive states: one for the recognition of the person position inside a contextual zone (a priori defined), and another for his/her proximity to a static object (equipment) located into the respective zone (also a priori defined, e.g., phone table, coffee machine). Second composite model is composed of the first composite model to include the recognition a given IADL, and a primitive state model related to the posture of the person. The primitive states for posture recognition used data from the inertial sensor only. The activities "writing a check" and "writing a shopping list" are not differentiated and are referred instead as "Person using Office Desk" due to the lack of information about the object been manipulated by the patient. The name of the activity "Organize the prescribed drugs" is shortened as "Person using pharmacy basket".

RESULTS AND DISCUSSION

Table 1 presents the performance of the framework at recognizing the IADLs a person is undertaking and his/her posture. Results are presented for mono-and multisensor approaches (2D-RGB camera and wearable inertial sensor). Average performance is presented for IADLs with and without posture sub-events. The row "Average of IADL without Posture" refers to event models based only on the person localization in the scene provided by the video-camera, therefore no difference is expected between Mono-and multisensor approach in this case. The deterministic (or crisp) modeling of multisensor events has improved by ∼ 19 % the precision index of IADLs involving sitting posture by the replacement of the vision system by an inertial sensor for posture estimation. However, the multisensor event models had a slightly lower performance on the detection of IADL involving standing posture than the mono-sensor approach. These results point that none of the two employed sensors can completely replace the other, and limiting the detection performance to the quality of the individual sensors output.

The difference in performance between IADL detection with and without posture component shows that by reducing the number of model constraints a higher detection performance can be achieved at the expenses of less information about how the event was performed. To tackle this problem, the probabilistic approach should be used to combine both posture estimations and also make models more robust to noise.

Table 2 presents the results of the proposed framework for conflict handling on the recognition of the Person posture using events from two different videocameras (2D-RGB and RGB-D). The individual performance of the hierarchical model-based framework per camera is presented for comparative purposes. The results in Table 2 showed the conflict handling framework improves the detection of posture-related primitive states on both posture categories. The precision achieved at standing recognition is higher than the one achieved by each video camera individually, demonstrating the suitability of the conflict handling framework for the assessing of event reliability and the combination of multiple sensor events for a more accurate detection.

CONCLUSIONS

We highlight as contributions of this paper a hierarchical model based framework for multisensor combination and a probabilistic approach for event conflict handling and fusion. The hierarchical model-based framework following a crisp combination of events from different sensors improves the detection of people seated while undertaking IADLs, and present similar results to the mono-sensor approach in the other cases. Therefore in the crisp modeling case the detection performance is limited to the quality of the output of individual sensors. However, with the event conflict handling approach we showed it is possible to obtain better results than the ones individually achieved by the combined sensors by measuring the event reliability before the fusion process. Moreover, the probabilistic approach would also reduce the influence of errors from low-level sensor in the inference of high-level events.

The hierarchical model based framework (event ontology + event conflicting handling) is a hybrid approach between the hand-crafted semantic-models and the completely learned parameters of Probabilistic Graphical Models, but requiring a much smaller amount of training data. Future work will extend the evaluation of the framework for a larger variety of sensors (heterogeneous and homogeneous) and types of primitive states, and verify possible alternatives to remove the learning step.

Fig. 1

 1 Fig. 1 Overall Architecture of the Video Monitoring System (adapted from [28])

Fig. 2 Fig. 3

 23 Fig. 2 Person sitting

Fig. 4

 4 Fig. 4 Class Person

Fig. 7

 7 Fig. 7 Person sitting and using OfficeDesk

Fig. 8

 8 Fig. 8 shows the recording viewpoint of the 2D-RGB and RGB-D cameras in A and B, and WI sensor at image B.

Fig. 8

 8 Fig. 8 Participant' activities by the point of view of different sensors: (A) RGB camera view and actimetry provided the inertial sensor (the bottom of image A); (B) RGB-D camera view of participant, which shows the inertial sensor worn by the participant; and (C) Drawn points on the ground represent the trajectory information of the participant during the experimentation.

  • Composite State refers to a composition of two or more primitive states. • Primitive Event models a change in a value of physical object property (e.g., Person changes from Sitting to Standing posture). • Composite Event refers to the composition of two previous event models which should hold a temporal relationship (Person changes from Sitting to standing posture before Person in Corridor Zone).

Table 1

 1 Comparison of Mono and multisensor approaches

	F-SCORE	Mono-multisensor
	IADLs + Sitting posture	52.00 71.00
	IADLs + Standing posture	73.15 71.00
	Average of IADL with Posture	68.00 71.00
	Average of IADL without Posture	81.22 81.22
	N: 9; 15 min. each; Total: 64800 frames (135 min).

Table 2

 2 Postures Recognition in Physical Tasks

	Posture	Sitting		Standing
	Sensor	Precision	Sensitivity	Precision	Sensitivity
	RGB	84.29	69.41	79.82	91.58
	RGB-D	100.00	36.47	86.92	97.89
	Fusion	82.35	91.30	91.04	95.31

N: 10. A window of 5 second is used for Temporal Probability.


Rémi Author

Géraud

Cyberspace and Time: A Light through the Fog?

Keywords: Territorial sciences, Cyberspace, Internet, Synchronicity, Mathematics cyberespace, internet, synchronicité, mathématiques

One usually describes cyberspace as a virtual realm. In truth, it is grounded in real infrastructures, which therefore inherit local regulations and broader geopolitical influences from the location where they are set up. The consequences of this attachment to a place can be measured to some extent from the communications happening in cyberspace, i.e., through communication networks. But there is also a temporal anchorage resulting from phenomena such as synchronisation in communications which, when analysed, reveals deep and surprising proximities, shedding new light on the relationships between actors in cyberspace. We discuss in particular how an analysis of synchronicity in cyberspace helped to identify collusions and a diffusion network active in spreading radical messages, as well as providing insight in these groups' internal structure.

INTRODUCTION

The fabric of cyberspace is woven from telecommunication channels. Over these channels, information is created, transported, transformed, and exchanged; but these channels are drawn between concrete devices and infrastructures: this makes them objects of real geopolitical interest. Indeed these infrastructures are bound to undergo various cultural, political, and socio-economic pressures, which therefore bear in some way on any network in which they participate [START_REF] Douzet | Géopolitique du cyberespace : 'territoire', frontières et conflits[END_REF].

One may thus wonder to what extent it is possible to recognise or identify such influences, mapping similarities or dissimilarities, by participating in a communication network. Indeed, the network itself introduces additional information along with the mere messages it transports; for instance: routing and addressing protocols (BGP, ARP...) used by the different devices in the network to organise themselves, regulate traffic, avoid congestion, and other such tasks; incomplete or partial messages, echoes, resulting from, e.g., some defective piece of equipment; and side channel information, that can be measured from the network but is not explicitly transported over it, such as latency, packet drop, or timing correlations.

In this work, we discuss how to capture and leverage timing information on a public network to define a first notion of synchronicity, and form rough communities based on activity patterns; we then refine this analysis to identify message diffusion patterns (causal avalanches). Finally, we use network latency estimates to identify automated posters on the public network, and show that they are likely to be operated by few entities.

All in all, we provide a framework and tools to detect non-local collusions, which may be attributed to forethought, automation, or hidden communication channels not immediately accessible to the analyst, but visible through their effects -all three possibilities being relevant to a thorough understanding of cyberspace.

WHY TIME MATTERS

The network fog of war

Computer networks are built atop infrastructures that belong to the physical world, where cyberspace collides with geographic space. Because of this, key assets (datacenters, largest network routes, etc.) can be mapped, to some extent, using traditional means, and lend themselves to an extended geopolitical analysis [START_REF] Douzet | Géopolitique du cyberespace : 'territoire', frontières et conflits[END_REF][START_REF] Limonier | La Russie dans le cyberespace : représentations et enjeux[END_REF]. The resulting cartography is still in its infancy, although it shows beyond doubt that some states have already embraced cyberwarfare as part of their doctrine. However, building (and concealing) new infrastructures is a long and costly process. While this is compatible with some objectives, e.g. controlling data routes or storage, it constitutes too much of a risk of being exposed in sensitive operations, such as influence campaigns or massive distributed denial of service attacks. This does not mean that state actors refrain from engaging in such operations; but they need plausible deniability.

To that end, they can leverage the absence of integrity and authenticity guarantees offered by computer networks, in particular Internet1 . Indeed, attackers can send crafted packets having wrong sender information (which is one way to launch DDoS attacks), or hide behind intermediation platforms such as social media websites. As a result, attack attribution is made very difficult, and identifying the attack's precise source is close to impossible. This is a famous issue in the context of network security, which ridicules attempts at automatically retaliating in name of "active defence" strategies, lest some additional information is known from e.g. intelligence sources that the attack indeed originated from the claimed source. Thus, attackers can craft data to hide their position, number, and possibly any sensitive information, thereby providing strong deniability guarantees.

What we suggest in this note is that the immediacy of computer network communications, made sharper by technological evolution, provides the analyst with new means to measure "closeness" or "similarity" beyond geographical vicinity, and complementary to it.

From a theoretical standpoint, we hope to extend the toolkit available for researchers and actors to analyse abstract networks (and in particular communication networks), aiming at extending the classical cartographic approach to the virtual world.

Synchronicity, causality, sychnometry

This "geography of time" is not a mere accident of the network's internals, but reveals underlying structures, and to a degree, causal influence between actors. As such it provides a better understanding of event dynamics in cyberspace, and gives additional insight into the geopolitical approaches of cyber actors.

We define this notion of time vicinity using the mathematical notion of stochastic processes, which give a precise meaning to "random" events occurring over time, and give means to measure their statistical dependence. There could be many ways in which two events influence one another; we focus on two of them: excitation and repetition. Excitation means that a certain class of events suddenly becomes much more probable; informally, this captures synchronicity between events (including runaway phenomena). Repetition means that the occurrence of an event strongly correlates to the occurrence of the same event at some later time; we refer to this analysis as sychnometry2 .

It is a basic fact that statistical correlation usually does not imply causation, and thus we shall refrain from making such a confusion. However, under some hypotheses, we can make an educated guess about the causal structure of events. For instance, if event A happens before event B for all observers, then B is unlikely to be the cause of A. Alternatively, if we observe that causation typically happens over a short period of time (e.g., days), but A and B are separated by a too short (e.g., millisecond) or too long (e.g., months) amount of time, then it is unlikely that they are causally (directly) related. Mathematically, we model the phenomena of interest as Hawkes processes [START_REF] Bacry | Hawkes processes in finance[END_REF], fitted using Maximum Likelihood estimation; from this we can extract synchronicity and sychnometric information efficiently, and to some extent reconstruct the (early) causal structure of events. We shall insist, here and later, that this is only causality in a probabilistic sense, and therefore may return wrong results (as any other tool).

The results of this analysis on a concrete case are given in section 3 below, after some technical preliminaries and methodological care. The context of heated debate over cyberspace territoriality and sovereignty is paramount to understand our motivations; we expect that the approach highlighted here participates in mending the disconnect between "virtual" and "concrete" geopolitics.

Our focus is on communication networks in general, of which social networks are an example and provide an interesting source, as they happen to be central hubs of influence for geopolitical questions.

MEASURING TIME OVER THE INTERNET

Defining and measuring network latency

Over the Internet, data is grouped into "packets" before transmission, that are transported from network device to network device until their destination is reached, or the packet is lost or corrupted to the point that transport is no longer relevant. In theory, packets are forwarded by intermediate network nodes asynchronously (first-in, first-out), which results in a processing delay, a transmission delay (pushing the packet's bits onto the link), and a propagation delay, i.e., the time taken for a signal to reach its destination.

In reality, additional mechanisms are used to shape traffic, guarantee delivery or fairness between users (e.g., "quality of service" mechanisms), and the physical medium's limitations must be taken into account (e.g., in wireless networks). All of these result in varying queuing delays that add to the full transmission time [START_REF] Nygren | The Akamai network: a platform for high-performance internet applications[END_REF].

The round-trip delay time (RTT) accounts for all the above effects and measures the time taken between the moment a message is sent and the moment it is fully echoed back. However, the RTT does not discriminate between forward (from sender to recipient) and backward (from recipient back to sender) delays. A more robust approach is to use active measurements, for instance with the minimum-pairs algorithm [START_REF] Abdou | Accurate One-Way Delay Estimation With Reduced Client Trustworthiness[END_REF], which requires the use of three trusted and synchronised nodes to reliably measure the one-way latency to a fourth (not necessarily trusted) node. Alternative methods are possible but typically less reliable [START_REF] Gummadi | King: Estimating latency between arbitrary internet end hosts[END_REF].

Note that any measurement performed on a remote device will necessarily be stained by some latency (this is akin to the situation in astrophysics, as one observes a remote star). This has to be corrected, and can be to some degree, as we now explain.

Time-of-flight measurements and relative positioning

Informally, the more intermediate nodes a packet has to go through, the longer the delay. By probing several well-positioned nodes on the network we can therefore infer how "far away" they are in terms of network hops, and to some extent reconstruct the underlying "informational highways", even if they are invisible from available (meta)data.

Representing this information is highly non-trivial however, as latency measurements aggregate several independent delay sources, and vary over repeated experiments. Nevertheless, large trends are visible and this average "time-of-flight" already highlights privileged or hampered routes. In particular we are interested in the latency distribution, which contains information about typical delays and variations (fig. 1) 3 .

Trusted time reference

In some situations we can have a public and trusted time reference. To that end we synchronise with GPS time [START_REF] Lombardi | Time and frequency measurements using the global positioning system[END_REF] and measure latency distribution from a fixed point to a given public server. In our case, the public server will be one of Twitter's CDN nodes. This allows us to measure the time elapsed between the moment a message is sent to the Twitter platform and the value indicated by the timestamp appearing on the platform when that message has been received. By monitoring the public API, we therefore get precise timings of when we received notification of the message, when the notification was sent (corrected by subtracting the one-way delay estimation from the server to our device), and when the message was acknowledged on the Twitter platform (as per the API-provided timestamp). Comparing these timings shows that we get a reasonably precise estimate of when the message is received by Twitter, and we will henceforth proceed using this information.

Using a trusted time reference, we can monitor events, record information, and order events in an unambiguous way. This was done for Twitter data over the course of several months. We can then use the tools described in section 1, which gives the results described below.

SYNCHRONICITY PATTERNS AND NON-LOCAL COLLUSIONS

Synchronicity measures: Multi-scale visualisation of influence

On figure 2, we represent the synchronicity/excitation measures extracted from retweet activity based on our captured data. A striking observation is that there is a regular pattern of activity strongly aligned with a given time zone (despite users declaring various time zones), which is observed independently from the message content. These graphs show, for instance, that a message is more likely to be retweeted 24 hours after the initial post, than 12 hours after. The near linear (rather than exponential) decay in synchronicity may be interpreted as the manifestation of a causal avalanche: a first set of users propagate the message over the next day, then another set of users (following roughly the same activity pattern) propagate the message over the next day, etc. Such a scenario can be simulated and exhibits a similar linear decay in synchronicity. However this information alone is not sufficient to guarantee that what is observed actually follows a propagation avalanche. Identifying the peaks in figure 2 is easily done algorithmically as it corresponds to values where the first derivative vanishes and the second derivative is negative. We should insist here that figure 2 is obtained without any smoothing and is the direct result of synchronicity measures over aggregated data, which shows how very clear and reliable activity patterns can be identified.

Limiting ourselves to the first minutes of diffusion, synchronicity measures provide a representation of how information propagates across the network, from neighbour to neighbour (fig. 3).

Figure 3. Synchronicity measures, capped to 3 minutes, mapped as relationships between nodes on a portion of the Twitter network Two nodes in this graph are linked when they typically react within 3 minutes of one another Synchronicity can be observed at several scales, and we have very good temporal resolution (1 ms). This gives a multi-scale picture of influence in the network, complemented by other community measures (e.g., network centrality).

Sychnometry measures: Visualising collusions

Our other measure focuses on repetition in activity, even when there is no link between two users (i.e., they do not interact). Following probability theory, we should expect a uniform ("flat") distribution for synchrometric estimates when all the nodes behave independently. As we saw on the synchronicity measures, there is latent variable in the form of a day-night cycle that must be accounted for. But in fact, when we turn our attention to very short time spans (where the day-night cycle's influence is negligible), and a portion of the network known to contain radical messages, we obtain figure 4.

What is visible on this figure is the presence of highly coordinated actors: actors that post at different moments of the day, and do not interact with one another, but do so "similarly'. They would not be otherwise visible! This is remarkable not only because of this sudden break through the mist, but because the sychnometric patterns appear extremely thin. Concretely, this means that groups of posters follow the exact same pattern within less than a second. They can be automatically identified using classical outlier detection techniques. Our interpretation is that this can only be done if these groups of posters are controlled by very few individuals ("senders"). Indeed it is extremely unlikely (under one chance in a billion) that such correlations are due to chance. Based on earlier estimates on latency distribution to Twitter's CDN nodes, we can see that all the 2-minute peaks originate from a single sender (using several dozen accounts), and all the 3-minute peaks originate from two, slightly distant senders (again using many accounts). We shall call members of such collusions seeds.

From a network point of view, each seed is the centre of a user community, and typically two such communities are fairly distant. But the operators planting seeds across the network have tight control over the content and can efficiently give the impression that some information is true because diffusion patterns ensure a quick propagation. After a few minutes, several a priori independent sources convey this message.

The amount of precision required to operate all seeds is compatible with the use of dedicated computer programs (such wide-scale coordination at the sub-second level is very unlikely to be a manual labour); however the choice of placement and the contents are engineered strategically.

CONCLUSION AND FURTHER WORK

On the importance of being timely

This study shows how to leverage timing measurements to extract hitherto hidden information about a network's operation, highlighting the structure of influence operations and calling for an integration of related measures in the representations of cyberspace. The extremely precise and abundant availability of time measurements makes it a reliable and efficient material.

Exploiting latent linguistic information

The same observations made for networks and network protocols hold for messages themselves, when they are exchanged between communities. To make the message understandable to its intended recipients, users have to convene of some format, which forces them to abide to some rules (grammatical or other); some users are less literate than others; messages have a given length, are typed at a certain speed, etc. In a sense, there is linguistic metadata readily available. In a network context, it is not possible to correctly participate in a 137 communication without giving some reasonable accurate information, such as an IP address to establish a TCP connection; likewise participants in a conversation will leak some details about them or relations between them.

These two approaches -leveraging network and linguistic metadata-combine naturally and provide insights about how communities are formed; notions of network and linguistic centrality shed light on how a network operates and which elements hold influence over which others.

Figure 1 .

 1 Figure 1. Latency distribution to a Twitter CDN node. Horizontal scale is in milliseconds

Figure 2 .

 2 Figure 2. Synchronicity measures for retweets over the course of 3 days (left) and two weeks (right)

Figure 4 .

 4 Figure 4. Sychnometric estimates for a period of 800 seconds on a portion of the network

By "Internet" we really mean the Internet protocol (IP), and its two most used super-layers: the transport control protocol (TCP/IP) and the user datagram protocol (UDP/IP). Together they account for the entirety of the traffic to web pages and to more than 80% of all traffic worldwide.

From Greek "συχνός", which means "frequent, repeated".

THE AUTHOR

Rémi Géraud

Département d'informatique de l'ENS, CNRS, PSL Research University remi.geraud@ens.fr


C Grenat

S Baguet

R Dufour
email: regis.dufour@insa-lyon.fr

C-H Lamarque
email: claude.lamarque@entpe.fr

Sevilla (Spain) MODAL INTERACTIONS IN A TWO-NANOMECHANICAL-RESONATOR ARRAY

Most studies on nanomechanical resonators in the literature are concerned with a single resonator. In this work, an array of two nanomechanical resonators is analyzed. A quasi-analytic approach with averaging method is used to compare the beams responses with and without electrostatic coupling terms. The results show modal interactions between the two beams due to the electrostatic coupling. It is shown that the qualitative behavior of the coupled resonators can be infered from the response curves of the uncoupled resonators. In particular, additional loops occur due to the algebraic structure of the coupled system. The contribution lies in the deduction of the beam array responses curve by using multiple uncoupled responses of the single-beam resonators.

INTRODUCTION

Arrays of MEMS or NEMS present complex dynamical behaviors due to electric, magnetic and mechanic nonlinear couplings. Lifshitz and Cross [START_REF] Lifshitz | Nonlinear Dynamics of Nanomechanical and Micromechanical Resonators[END_REF] studied the responses of n electrical and mechanical coupled oscillators with parametric resonance in the low nonlinear limit by using a perturbation method. Gutschmidt and Goettlieb worked on arrays with electrical coupling. They focused on the n-beam dynamic behaviour in the region of internal one-to-one, parametric and several internal three-to-one resonances corresponding to low, medium and large DC voltages [START_REF] Gutschmidt | Nonlinear dynamic behavior of a microbeam array subject to parametric actuation at low, medium and large dc-voltages[END_REF]. Kacem et al. developped a single beam model to investigate the sensitivity of the resonance with respect to the electrostatic forcing. Their researches were carried out using averaging method validated by HBM+ANM [START_REF] Kacem | Computational and quasi-analytical models for non-linear vibrations of resonant mems and nems sensors[END_REF]. In this paper, an array of n = 2 identical clampedclamped beams is also considered but coupled only by an electrostatic force in order to study the modal interactions between the two beams due to the electrostatic coupling.

ARRAY OF TWO NANOMECHANICAL RESONATORS

A 2-moving-beam array is considered, as sketched in Figure 1. The two beams located at the ends of the array are fixed and serve only as electrostatic actuator. All 4 beams are identical. l, b, h, I, g are the dimensions of the beams, i.e., length, width, height, moment of inertia, gap between two adjacent beams. E, ρ be the Young's modulus and the material density. Each beam is an electrostatic actuator for its adjacent beams. V s,s+1 = V dcs,s+1 + V acs,s+1 cos(Ωt) is the voltage applied between the successive beams s and s + 1 with V dc , V ac the continuous and alternative voltages. The equation of the beam s in bending is as follows [START_REF] Gutschmidt | Nonlinear dynamic behavior of a microbeam array subject to parametric actuation at low, medium and large dc-voltages[END_REF].

EI ∂ 4 ws (x, t) ∂ x4 + ρbh ∂ 2 ws (x, t) ∂ t2 -Ñ + Ebh 2l l 0 ∂ ws (x, t) ∂ x 2 dx ∂ 2 ws (x, t) ∂ x2 = 0 bC n 2 V 2 s,s+1 g + ws+1 -ws 2 - V 2 s-1,s g + ws -ws-1 2 (1)
with s = 1, 2. Let 0 , C n be the dielectric constant and fringing the coefficient respectively. Ñ represents the lineic load along the x-axis. The beams 1 and 2 are clamped-clamped.

MEDYNA 2017 25-27 Apr 2017, Sevilla (Spain)

AVERAGING METHOD

The responses of the beams are more complicated than those of a single beam resonator. A quasi-analytic solution obtained by the averaging method can be used to explain why the electrostatic coupling generates additional loops onto the responses. First, the beam lateral deflection is expanded on its fundamental mode only:

w 1 (x, t) = φ 1 (x)a 11 (t), w 2 (x, t) = φ 1 (x)a 21 (t) (2)
First-order Taylor series are then used to simplify the analytic calculation:

1 (1 + w s+1 -w s ) 2 1 -2(w s+1 -w s ), 1 (1 + w s -w s-1 ) 2 1 -2(w s -w s-1 ) (3)
Since the resonators of the 2-beam array have the same boundary conditions, their eigenmodes are identical. Therefore, a Galerkin method is used to eliminate the spatial dependence from the equation of motion [START_REF] Lifshitz | Nonlinear Dynamics of Nanomechanical and Micromechanical Resonators[END_REF]. Then using the averaging method and considering the solutions a 11 (t), a 21 (t) in following forms

a 11 = A 11 (t) cos(Ωt) + B 11 (t) sin(Ωt), (4)
a 21 = A 21 (t) cos(Ωt) + B 21 (t) sin(Ωt), (5)
yield

Ω Ȧ11 = -B 11 ω 1 σ 1 - 1
where the coefficients β ij , γ ij , δ ij depend on the beam characteristics and on the applied voltages. They are not detailed here for the sake of conciseness. In Equations ( 6)-(9), the coupling terms ( 1 2 δ 11 + 1 8 δ 13 )B 21 and ( 1 2 δ 11 + 1 8 δ 13 )A 21 represent the influence of the second beam on the first beam and the coupling terms ( 1 2 δ 21 + 1 8 δ 23 )B 11 , ( 1 2 δ 21 + 3 8 δ 23 )A 11 the influence of the first beam on the second beam. When Ȧ11 = Ḃ11 = Ȧ21 = Ḃ21 = 0 the steady-state motions appear. The corresponding nonlinear algebraic system is solved by an adapted numerical method, the obtained approximated solution is in agreement with a reference solution obtained by HBM+ANM [START_REF] Kacem | Computational and quasi-analytical models for non-linear vibrations of resonant mems and nems sensors[END_REF] not shown here.

In order to analyze the influence of the coupling terms, Equations ( 6)-( 9) with and without coupling terms are examined. The response curves with (red curves) and without (blue curves) coupling terms are plotted in Figure 2. Without these coupling terms Equations ( 6)-( 7 and ( 8)-(9) form two independent systems of equations. Therefore, the responses of the two beams, (blue response curves in Figure 2) are similar to two single-beam responses. With coupling terms Equations ( 6)-( 9) are dependent and share the same bifurcation points and stability. When a bifurcation point is present on a response curve, the same bifurcation point will also be present at the same frequency on the other beam response. Therefore, the limit points originated from the responses without coupling terms will be present on all the other beam responses with coupling terms. This leads to the appearance of additional limit points on the response curves. In Figure 2, the limit points B 1 and C 1 on the first beam response generate at the same frequencies the loop B 2 -C 2 on the second-beam response. In the same way, D 2 and E 2 on the second-beam response produce the loop D 1 -E 1 on the first-beam response.

CONCLUSION

A quasi-analytic analysis with the averaging method of a two-nanomechanical-resonator array has been carried out. The existence of modal interactions between the two beams due to the electrostatic coupling has been enlightened. The appearance of additional loops onto response curves has been explained. The form of the response curves of an electrostatic coupled beam array can be anticipated using the uncoupled single-beam-resonator responses. This research represents an increment towards the comprehension and modeling of resonator arrays for application in mass sensing.

Figure 1 :

 1 Figure 1: Array of two clamped-clamped M/NEMS beams.

Figure 2 :

 2 Figure 2: Design 1 without added mass, Response by neglecting the coupling terms (blue), complete response (red). (a): first-beam response, (b): second-beam response.