Nazih Mechbal
email: nazih.mechbal@ensam.eu

Juan Sebastian Uribe

Marc Rébillat
email: marc.rebillat@ensam.eu

A Probabilistic Multi-class Classifier for Structural Health Monitoring

Keywords: Structural health monitoring, Support vector machine, Probabilistic decision tree, Pattern recognition, Wave diffraction patterns, Piezoelectric elements

In this paper, a probabilistic multi-class pattern recognition algorithm is developed for damage detection, localization, and quantification in smart mechanical structures. As these structures can face damages of different severities located at various positions, multi-class classifiers are naturally needed in that context. Furthermore, because of the lack of available data in the damaged state and of environmental effects, the experimentally obtained damage sensitive features may differ from those learned offline by the classifier. A multiclass classifier that provides probabilities associated with each damage severity and location instead of a binary decision is thus greatly desirable in that context. To tackle this issue, we propose an original support vector machine (SVM) multi-class clustering algorithm that is based on a probabilistic decision tree (PDT) and that produces a posteriori probabilities associated with damage existence, location, and severity. Furthermore, the PDT is here built by iteratively subdividing the surface of the structure and thus takes into account the actual structure geometry. The proposed algorithm is very appealing as it combines both the computational efficiency of tree architectures and the classification accuracy of SVMs. The effectiveness of this algorithm is illustrated experimentally on a composite plate instrumented with piezoelectric elements on which damages are simulated using added masses. Damage sensitive features are computed using an active approach based on the permanent emission of non-resonant Lamb waves into the structure and on the recognition of amplitude disturbed diffraction patterns. On the basis of these damage-sensitive features, the proposed multi-class probabilistic classifier generates decisions that are in excellent agreement with the actual severities and locations of the simulated damages.

Introduction

Structural health monitoring (SHM) is an emerging technology designed to automate the inspection process undertaken to assess the health condition of structures. In a smart structure, SHM systems may automatically process data, state regarding structural conditions, and highlight any need for human intervention [START_REF] Worden | The fundamental axioms of structural health monitoring[END_REF]. The output of any SHM process should provide information regarding the type, the location, and the severity of the damage. Thereby, the SHM process is classically decomposed into four sequential steps: detection, localization, quantification, and prognosis. SHM involves many disciplinary fields (material science, structural analysis, signal processing, data mining, fracture mechanics, fatigue life analysis…) and has been the topic of extensive research efforts over the last thirty years. This technology is now progressing toward operational service and recent surveys have shown that even reluctant industry areas are now convinced that SHM is the key technology that will enable the transition from schedule-driven maintenance to condition-based maintenance [START_REF] Chang | Structural Health Monitoring: Condition-based Maintenance[END_REF]. Rresearchers are now exploring ways to adapt information technologies in order to reduce system monitoring costs while simultaneously broadening their functional capabilities. In this paper, we address the detection, localization and quantification steps of the SHM process.

Damage-sensitive features generated using Amplitude Disturbed Diffraction Pattern

SHM system operational results can be classified into four different sequential levels: detection, localization, quantification, and prognosis [START_REF] Worden | The fundamental axioms of structural health monitoring[END_REF]. Several different techniques that depend on the structure's material, on the technology used for acting and sensing, on the position, size, and nature of damage may be employed to perform SHM [START_REF] Balageas | Structural Health Monitoring[END_REF]. They could be sorted in two main categories: global or local.

Among others global SHM methods, we can highlight vibration based approaches [START_REF] Carden | Vibration based Based Condition Monitoring: A Review[END_REF][START_REF] Chesné | Damage localization using transmissibility functions: A critical review[END_REF]. These methods are categorized based on the type and nature of measured data. Significant examples include: model updating [START_REF] Fritzen | Damage detection based on model updating methods[END_REF]; statistical time series and modal analysis [START_REF] Carden | Vibration based Based Condition Monitoring: A Review[END_REF]. In those approaches we seek to track changes in global structural parameters (mass, stiffness, flexibility, damping) and modal parameters (modal frequencies, associated damping values and mode shapes) by analyzing changes induced in the global dynamic behavior of a structure. Experimental identification of these dynamic properties indeed gives insight on the structural damage conditions, see [START_REF] Zou | Vibration-based lmodeldependent damage (delamination) identification and health monitoring for composite structures -a review[END_REF][START_REF] Basseville | Statistical model-based damage detection and localization: subspace-based residuals and damage-to-noise sensitivity ratios[END_REF][START_REF] Mevel | LPTV subspace analysis of wind turbines Data[END_REF] and references therein. Multivariate techniques have been also used in global vibration-based SHM: examples are the PCA (Principal Components Analysis) [START_REF] Hajrya | Principal Component Analysis and Perturbation Theory Based Robust Damage Detection of Multifunctional Aircraft Structure[END_REF] and ICA [START_REF] Hajrya | Perturbation analysis for robust damage detection with application to multifunctional aircract structures[END_REF]. In the case of nonlinear damage, specific vibration-based approaches have also been developed recently by the authors using cascade Hammerstein models [START_REF] Rebillat | Nonlinear structural damage detection based on cascade of hammerstein models[END_REF]. An extensive overview of nonlinear global vibrationbased SHM methods can be found in [START_REF] Farrar | Nonlinear system identification for damage detection[END_REF].

For local inspection, we can employ electro-mechanical impedance or displacement/strain as features indicating the presence of damage [START_REF] Balageas | Structural Health Monitoring[END_REF]. As these methods are local, their sensibility is strongly linked to the position of the sensors. In that category, we can also highlight acoustic emission or high frequency wave-based approaches that have the advantage to be sensitive to very small damages and offer the capability of propagation over a significant distance [START_REF] Su | Identification of Damage Using Lamb Waves[END_REF]. Evaluation of wave propagation on solids is one of the most successful techniques for damage monitoring [START_REF] Ihn | Pitch-catch active sensing methods in structural health monitoring for aircraft structures[END_REF]. One piezoelectric actuator emits periodic burst pulses exciting Lamb waves in the structure under inspection, and a set of sensors records signals, representing the respective structural responses. These signals are processed in order to extract damage related information such as location, size, orientation, type among others [START_REF] Su | Identification of Damage Using Lamb Waves[END_REF]. One of the outstanding advantages of using Lamb waves for SHM is that such waves can travel over relatively long distance and can be used to monitor various types of damage (as delamination, disbonds, fiber breaking, impact,...) [START_REF] Zhongqing | Guided Lamb waves for identification of damage in composite structures: A review[END_REF].

To construct measurements that are sensitive to the damage, we use in this work an active SHM approach based upon a correlation technique that relies on wave diffraction patterns recognition. Damage-sensitive features are generated thanks to the Amplitude Disturbed Diffraction Pattern (ADDP) phenomenon observed using permanent emission of selected non-resonant Lamb waves in the structure. ADDP assesses the disturbances that damage brings to the acoustic wave propagation in the structure. These disturbances depend upon the damage severity and position as well as on the frequency of the exciting signal. With an appropriate calibration procedure, it is thus possible to detect, localize, and quantify the damage using ADDP. This process has already been successfully used as a multi-touch sensing approach to tactile sensing [START_REF] Liu | An acoustic multi-touch sensing method using amplitude disturbed ultrasonic wave diffraction patterns[END_REF]. The formulation of this process as a damage location one has been presented in [START_REF] Liu | Damage monitoring based on wave illumination of structures[END_REF]. In this paper, the ADDP process will be used to generate the damage-sensitive features that will allow detecting, localizing, and quantifying the damage.

The need for a probabilistic multiclass classification tool in SHM

The extraction of damage-sensitive features from measurements is a process that is most powerful when it is followed by pattern recognition [START_REF] Farrar | Structural Health Monitoring: A Machine Learning Perspective[END_REF]. Indeed, in a statistical pattern recognition paradigm for SHM, it is usually rather difficult to obtain data from damaged structures because of cost and of practical constraints. However, when such data are available, a whole new range of algorithms can be used [START_REF] Farrar | Structural Health Monitoring: A Machine Learning Perspective[END_REF] and the problem of damage detection, localization, and quantification can be cast as one of classification [START_REF] Roseiro | Neural networks in damage detection of composite laminated[END_REF][START_REF] Saeed | Artificial Neural Network Based Structural Damage Diagnosis Using Nonparametric Subspace Residual[END_REF] .

As the structures under study can face damages of different severities located at various positions, multi-class classifiers are naturally needed. Furthermore, because of the lack of available data in the damaged state and of the environmental effects, the experimentally obtained damagesensitive features may differ from those learned offline by the multi-class classifier. A multiclass classifier that provides probabilities associated with damage existence and with each damage location and severity instead of a binary decision is thus greatly desirable for SHM. With such a classifier, damage locations can for example be ranked from the most probable to the least one, thus providing helpful guidance for the inspection task. Indeed, the reliability assessment of SHM systems is the key issue in ensuring their successful implementation. For example in aerospace maintenance procedure minimizing structural teardown to access regions to be monitored is one of the claimed benefits in using SHM rather than classical nondestructive evaluation (NDE) systems. Moreover, given that the diagnosis (class assignment) will be made on the basis of measured data, it is important that the chosen pattern recognition algorithm is able to accommodate a degree of imprecision commensurate with expected levels of measurement error and noise. This requires that the damage detection, localization and quantification SHM outputs' have to be assorted with a probability. This probability is then considered as a level of the trust in the SHM systems results.

In this work, where a statistical pattern recognition paradigm for SHM is considered, we propose to provide a metric helping the condition-based maintenance decisions for in-service structures. This is possible by capturing during the training phase a part of the effect of environmental variability. This will represent the probability of how likely are SHM system outputs. Moreover, to ease the practical implementation, by simply thresholding these a posteriori probabilities at each node, the soft-decision approach can be converted to the conventional hard-decision approach.

Towards probabilistic binary decision trees

Formally, we seek for an algorithm able to solve a multi-class data classification problem in a manner that produces confidence probabilities associated with each class. This algorithm should also ideally take into account some a-priori knowledge related to the structure (geometry, material…) in order to speed up the diagnostic. Moreover, in this work, we propose to use predefined class hierarchy. That means that the internal (non-leaf) nodes of the structured tree are chosen based on data where we built the hierarchy during training and then classify new samples by using the hierarchical tree.

Generally speaking, there exist two main types of classifiers: hard and soft [START_REF] Liu | Hard or soft classification? large-margin unified machines[END_REF]. Hard classifiers, such as support vector machine (SVM) [START_REF] Vapnik | Statistical learning theory[END_REF] , build a frontier between classes. They only label new unknown points with the class associated to the side of the frontier in which they fall, without giving any idea of the certitude of the decision or the degree of membership to that class. These classifiers are very appealing, because in general they tend to give very accurate predictions. The formulation of bi-class SVMs finds the hyperplane that separates the two classes by ensuring the largest margin with respect to each of the class. Extending this formulation directly to more than two classes is generally avoided due to the complex optimization equation that it leads to. Instead, the multi-class SVM problem is often dealt with by using an ensemble of two-class SVMs. Various strategies exists to achieve such combinations, the most popular ones being "one-against-one" [START_REF] Friedman | Another approach to polychotomous classifcation[END_REF][START_REF] Eichelberger | Does One-Against-All or One-Against-One Improve the Performance of Multiclass Classifications?[END_REF], "one-against-all" [START_REF] Vapnik | Statistical learning theory[END_REF][START_REF] Rifkin | In Defense of One-Vs-All Classification[END_REF] and Error-correcting output codes (ECOC) [START_REF] Dietterich | Solving multiclass learning problems via error correcting output codes[END_REF]. A less known approach consists in dividing the problem in a hierarchical way where classes which are more similar to one another are grouped together into mata-classes, resulting in a Binary Hierarchical Classifier [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF][START_REF] García-Pedrajas | An empirical study of binary classifier fusion methods for multiclass classification[END_REF]. Regarding hierarchical classification [START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF] where classes are organized in tree or a DAG-like structures (Directed Acrylic Graph), the damage localization classification problem can be naturally cast as a hierarchical classification problem where the classes to be predicted are organized into meta-classes (for example subdividing geometric zones to be monitored) hierarchy as a tree.

Considering a local classifier per node approach [START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF], Madzarov [START_REF] Madzarov | A multi-class svm classifier utilizing binary decision tree[END_REF] has come up with a simple and intuitive method based on building a binary SVM decision tree. Actually, a class binarization is the mapping of a multiclass problem into several two-class problems in a way that allows the derivation of a prediction for the multiclass problem from the predictions of the two-class classifiers. By selecting specific features, such as the distance between gravity centers of the different classes, an automatic graph is generated where at each node a bi-class SVM is trained [START_REF] Madzarov | A multi-class svm classifier utilizing binary decision tree[END_REF].. However, such multi-class hard classifiers only provide one predicted class without any associated score indicating the confidence of the classification. On the opposite, soft classifiers like Logistic Regression (LR) [START_REF] David | Applied Logistic Regression[END_REF] are able to build probability estimations for the belonging of an incoming example to all the classes, and then with this information they choose the most likely class. However, their classification performances are in general poorer than the hard classifiers ones. We are thus interested, in a multi-class context, by the probabilities estimation offered by soft classifiers while keeping the hard classifiers proved performances [START_REF] Platt | Large margin DAGs for multiclass classification[END_REF]. Standard SVMs do not provide such probabilities, but solutions to this issue were proposed. In a bi-class context, Platt [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF] proposed a method to compute the probabilities 𝑝(𝑐𝑙𝑎𝑠𝑠|𝑖𝑛𝑝𝑢𝑡) from SVM outputs. The approach consists in training the parameters of a sigmoid function to map the SVM outputs into probabilities. The underlying idea of this so-called Probabilistic SVM classifier (PSVM) is that when the distance from an example to the frontier is large, the example will very likely belong to that class. However all these works were developed for the bi-class problem only. By adapting Platt's method to a multi-class context by means of a binary decision tree, it is thus in principle possible to extract probabilities from SVMs outputs while keeping the demonstrated performances of hard classifiers.

This approach has been developed previously by the authors and successfully applied to automotive repairing backdrop [START_REF] Uribe | Probabilistic Decision Trees using SVM for Multi-class Classification[END_REF]. Using damage-sensitive features generated through ADDP, this approach is extended here to detect, localize and quantify damages. Moreover, by assuming that the structure has an Euclidean geometry and topology (which is not restrictive as the structure can be subdivided in areas that satisfied this property), we propose to construct the decision tree by iteratively partitioning the structure along affine hyperplanes. By doing so, each leaf of the tree, represent, a geometric zone of the structure. This leads to a new algorithm: SVM geometric probabilistic decision tree (SVM-GPDT), where a multi-class probabilistic classifier is then built on the basis of this decision tree. Therefore, using this topological a priori knowledge, the SVM-GPDT will provide fast classification (logarithmic complexity) along with associated posterior probabilities 𝑝(𝑐𝑙𝑎𝑠𝑠|𝑖𝑛𝑝𝑢𝑡). In a SHM context, this approach is very appealing because due to restrictions upon actually damaging structures, few data are usually available to train the classifier, and few data are needed to train this one. Furthermore, it is sufficient in several applications to only locate the most likely damaged area. For example, in aeronautical structures, it is satisfactory to give the damaged panel and an estimate of damage severity and then to use precise nondestructive testing and evaluation procedures. This algorithm thus offers an original and practical way to generate probability information related to the presence and severity of damage in each structural zone to be monitored.

The paper is organized as follows: Section 2 describes the original SVM based multi-class classification approach proposed here, including the geometric approach used to generate the damage decision tree. Section 3 validates the proposed approach for damage detection, localization, and quantification experimentally. Concluding remarks and future perspectives are drawn in the last sections.

A probabilistic multi-class classification algorithm

Optimized soft margins Support Vector Machines with Gaussian kernels

Classic support vector machines (SVMs) have proved to be very effective classification methods [START_REF] Ma | Support Vector Machines Applications[END_REF]. They are binary linear classification techniques which search for the hyperplane (in the hyperspace of attributes) that separates two classes in a training set. This hyperplane is found by maximizing the so-called margin, which is the distance from the hyperplane to the closest points, denoted support vectors. A common variant of classic SVM, is called soft margin and it consists of admitting some misclassified points in the training set to prevent the over fitting problem. However, we want to avoid too many points being misclassified. Thus we impose a penalty 𝐶 that will penalize every misclassified example. 𝐶 can take values in the range 0 < 𝐶 ≤ ∞. A high value of 𝐶, means a strict classifier that doesn't admit many misclassified points. On the opposite, a small 𝐶 means a very flexible classifier. Formally, we have a training set {(𝒙 𝟏 , 𝒚 𝟏 ), … , (𝒙 𝒏 , 𝒚 𝒏 )}, where every point 𝒙 𝒊 = (𝒙 𝒊𝟏 , … , 𝒙 𝒊𝒎 ) has 𝑚 attributes and one of the two possible labels 𝒚 𝒊 = {-1 ,1}. A soft margin SVM classifier will label a new unknown point 𝒙 𝒕 according to the decision function:

𝑦(𝐱 𝑡 ) = 𝑠𝑔𝑛((𝒘. 𝒙 𝑡 ) + 𝑤 0 ) (1)
where 𝒘 and 𝑤 0 are the hyperplane parameters to find on the basis of a training set.

In SVM, kernels can be used to project the data into a virtual space where it might be easier to separate them [START_REF] Vapnik | Statistical learning theory[END_REF]. The main advantage of kernel functions is that the only operation needed to be defined in the new virtual space is the inner product 𝜅(𝒙 𝑖 , 𝒙 𝑗 ) = ⟨𝒙 𝑖 , 𝒙 𝑗 ⟩ . Applying a kernel function together with the soft margin, a soft margin SVM classifier will label a new unknown point 𝒙 𝒕 according to the new decision function [START_REF] Chang | LIBSVM: A library for support vector machines[END_REF]:

𝑦(𝐱 𝑡 ) = 𝑠𝑔𝑛(𝑓(𝒙 𝒕 ))
(2) where 𝑓(𝒙) is defined as:

𝑓(𝒙) = ∑ 𝛼 𝑖 𝑢 𝑖 𝜅(𝒙 𝑖 , 𝒙) + 𝑤 0 𝑚 𝑖=1 (3)
The values of 𝛼 i and 𝑢 𝑖 are found by solving the following constrained optimization problem on the basis of the training examples:

{ max 𝛼 𝑖 [∑ 𝛼 𝑖 - 1 2 ∑ 𝛼 𝑖 𝛼 𝑗 𝑢 𝑖 𝑢 𝑗 𝜅(𝒙 𝒊 , 𝒙 𝒋 ) 𝑚 𝑖,𝑗=1 𝑚 𝑖=1 ] 0 ≤ 𝛼 𝑖 ≤ 𝐶, 𝑖 = 1, … , 𝑚 ∑ 𝛼 𝑖 𝑢 𝑖 𝑚 𝑖=1 = 0 (4)
In the case of Gaussian kernel the only tuning parameter is 𝜎 2 . A small value of 𝜎 2 will lead to curved hyperplanes and a high value will constrain the hyperplanes to be straighter. In [START_REF] Keerthi | Asymptotic behaviors of support vector machines with Gaussian kernel[END_REF] it is shown that for some combinations of the hyperparameters (𝐶, 𝜎 2 ), the Gaussian kernel tends towards the linear kernel, which makes the Gaussian kernel the most general method and one that would work for a large range of datasets. The hyper parameters (𝐶, 𝜎 2 ) have to be optimized for every classification problem. In this work we used Lin's approach to optimize the choice of the coefficients (𝐶, 𝜎 2 ) [START_REF] Keerthi | Asymptotic behaviors of support vector machines with Gaussian kernel[END_REF].

Probabilistic Support Vector Machines (PSVM)

As stated before, SVM produce a value that is not a probability. Indeed, SVM only give a class prediction output that will be either +1 or -1. In order to extract the associated probabilities from SVM outputs, several approaches have been proposed [START_REF] Vapnik | Statistical learning theory[END_REF][START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF]. We will focus on Platt's approach [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF] who proposed a technique that has been largely used in the literature. He builds a sigmoid function between the outputs 𝑓(𝒙) of the SVM and the probability of membership 𝑝(𝑦 = 𝑖|𝒙) to a class 𝑖, given the attributes of 𝒙. A simple bi-class example is shown in Fig. 1. The sigmoid will have the following parametric expression:

𝑝 (𝑦 = 1|𝑓(𝒙)) = 1 1 + 𝑒 𝑎𝑓(𝒙)+𝑏 (5)
where 𝑎 and 𝑏 are parameters computed from the minimization of the negative log-likelihood function on a set of training examples [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF],

-∑ 𝑡 𝑖 log 𝑝(𝑓(𝒙 𝒊 )) + (1 -𝑡 𝑖 ) log(1 -𝑝(𝑓(𝒙 𝒊 )) 𝑖 (6)
and 𝑡 𝑖 is the new label of the classes: +1 becomes 𝑡 + and -1 becomes 𝑡 -. This relabeling procedure is conducted so that the sigmoid fitting is softer. These new labels are computed using:

𝑡 + = 𝑁 + + 1 𝑁 + + 2 𝑡 -= 1 𝑁 -+ 2 (7)
where 𝑁 + and 𝑁 -are the number of points that belong to class 1 and class 2 respectively.

The PSVM as proposed by Platt [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF], uses first a SVM classifier that has to be trained with a training set s 1 . Then the sigmoid parameters (𝑎, 𝑏) have to be found. To do so, it is recommended [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF] to use a second training set 𝑠 2 . The sigmoid fit requires the inputs 𝑓(𝒙) and the labels 𝑡 𝑖 . We use 𝑠 2 as a test set for the classifier. Thus we obtain the output values 𝑓(𝑠 2 ). Knowing the labels of 𝑠 2 (number of positives ones and number of negatives ones) we can calculate 𝑡 + and 𝑡 - for this sub-training set. With values (𝑓(𝑠 2 ), 𝑡 𝑖 (𝑠 2 )) we then find (𝑎, 𝑏) by optimizing Eq. ( 12) using a Newton's method with backtracking. After these two steps, we have built a posterior probability estimator for the bi-class problem. Regarding the practical implementation of the algorithm, we have improved Platt's method [START_REF] Platt | Probabilistic outputs for support vector machines and comparison to regularized likelihood methods[END_REF] by introducing modifications based on ideas sketched by Lin and coauthors in [START_REF] Lin | A note on Platt's probabilistic outputs for support vector machines[END_REF]. The new algorithm is more precise and more efficient than Platt's one in terms of computational cost.

From bi-class to multi-class problems

SVM were originally designed for bi-class classification problems and the passage to multi-class problems is still an on-going research area [START_REF] Hsu | A comparison of methods for multiclass support vector machines[END_REF][START_REF] Aly | Survey on Multiclass Classification Methods[END_REF][START_REF] Khan | A survey of recent trends in one class classification[END_REF][START_REF] Mehra | Survey on multiclass classification methods[END_REF]. There are two major approaches to solve this type of problems. The first and intuitive one named "All-together", consists in formulating a cost function with 𝑄 (the number of classes in our problem) hyperplanes [START_REF] Weston | Multi-class support vector machines[END_REF][START_REF] Ganu | Sparse Max-Margin Multiclass and Multi-label Classifier Design for Fast Inference[END_REF]:

{ min 𝒘,𝜉 1 2 ∑ (𝒘 𝒎 . 𝒘 𝒎 ) + 𝐶 ∑ ∑ 𝜉 𝑖 𝑚 𝑚≠𝑦 𝑖 𝑙 𝑖=1 𝑄 𝑚=1 (𝒘 𝒚 𝒊 . 𝒙 𝒊 ) + 𝑏 𝑦 𝑖 ≥ (𝒘 𝒎 . 𝒙 𝒊 ) + 𝑏 𝑚 + 2 -𝜉 𝑖 𝑚 𝜉 𝑖 𝑚 ≥ 0, 𝑖 = 1, … , 𝑙 𝑚 ∈ {1, … , 𝑄} ∖ 𝑦 𝑖 (8)
This optimization problem, with so many variables, is in general difficult to solve [START_REF] Hsu | A comparison of methods for multiclass support vector machines[END_REF][START_REF] Ganu | Sparse Max-Margin Multiclass and Multi-label Classifier Design for Fast Inference[END_REF]. Therefore, an alternate approach consists in dividing the multi-class problem in several binary subproblems. There are numerous methods that perform this subdivision. The most popular are One against one [START_REF] Friedman | Another approach to polychotomous classifcation[END_REF][START_REF] Eichelberger | Does One-Against-All or One-Against-One Improve the Performance of Multiclass Classifications?[END_REF][START_REF] Tsujinishi | Why Pairwise is Better Than One-Against-All or All-at-Once[END_REF], One against all [START_REF] Vapnik | Statistical learning theory[END_REF][START_REF] Rifkin | In Defense of One-Vs-All Classification[END_REF], and Error-correcting output codes (ECOC) [START_REF] Dietterich | Solving multiclass learning problems via error correcting output codes[END_REF][START_REF] Bagheri | A subspace approach to error correcting output codes[END_REF].

Yet another approach for tackling the multiclass classification problem utilizes a hierarchical division of the output space i.e. the classes are arranged into a hierarchical structure: Directed Acyclic Graph (DAG) [START_REF] Platt | Large margin DAGs for multiclass classification[END_REF], or Binary decision Trees (BDT) [START_REF] Madzarov | A multi-class svm classifier utilizing binary decision tree[END_REF]. In the tree structure, The tree is created such that the classes at each parent node are divided into a number of clusters, one for each child node. The process continues until the leaf nodes contain only a single class. For sake of shortness, we will only focus on the BDT method, because it is the one we will use in the sequel. It is important to note that the BDT processing time is smaller than the other methods because the depth of the decision tree is of order log 2 ( 𝑄) since at every level the tree eliminates approximately half of the remaining classes.

In [START_REF] Madzarov | A multi-class svm classifier utilizing binary decision tree[END_REF], it is proposed to build a binary decision tree in which at every node the remaining classes are separated in two subgroups 𝑔 1 and 𝑔 2 . A SVM classifier decides to which subgroup the new point belongs to, and hence in which direction to move. In order to build the tree (the first step in the classification procedure) a clustering algorithm divides all the 𝑄 classes into subgroups 𝑔 1 and 𝑔 2 . The algorithm calculates the gravity centers of all classes. The two classes with the biggest Euclidean distance from each other are assigned to each of the sub-groups. Then the algorithm checks the closest class to one of the sub-groups, this class is assigned to that sub-group, their gravity center is recalculated with the new points that have just been added. This is repeated until all classes have been assigned to one of the groups. For each sub-group the clustering algorithm is repeated until there is no more than one class per sub-group.

Probabilistic decision trees (PDT)

In this paper, we propose to use a binary decision tree following the idea introduced by Madzarov [START_REF] Madzarov | A multi-class svm classifier utilizing binary decision tree[END_REF] presented in the previous section. But instead of using a simple SVM classifier at each node, we use a SVM classifier associated with a sigmoid function to estimate the probability of membership to each sub-group in the node, as shown in Fig. 2.

We can then build a probability function for each leaf, knowing the path that we have to follow to reach it. Note that there is only one way to get to a leaf. It follows that the probability functions are unique for a trained tree:

𝑝(𝑦 = 𝑖|𝑥) = ∏ 𝑝 𝑛𝑜𝑑𝑒 (ℎ,𝑙) 𝑙𝑒𝑎𝑓 ℎ=1 (9)
The parameter ℎ represents the level of the tree (ℎ = 1 corresponds to the root node). The previous expression states that the probability of membership of an element in the class 𝑖 is calculated as the product of the probabilities of the decisions taken in all the nodes visited until reaching the leaf. By 𝑛𝑜𝑑𝑒(ℎ, 𝑙) we mean the 𝑙 𝑡ℎ node in the ℎ 𝑡ℎ level. For a given tree, we know the probability functions of the 𝑄 classes. For future unknown cases, we just have to evaluate the 𝑄 analytical functions and then choose the class with the highest score. However, one of the most interesting issues of the PDT is that we can have more than one prediction for one example. We can have a list of all the possible classes, ordered following their plausibility, which is measured with the posterior probabilities estimation.

A geometry based probabilistic decision trees (GPDT)

The probabilistic decision tree, described previously, can be built using many different criteria [START_REF] Madzarov | A multi-class svm classifier utilizing binary decision tree[END_REF]. For example using the Euclidian distance between the gravity centers, the margin obtained by pairwise SVM, or some physical or functionalities criteria (mechanical, geometrical, etc.). This degree of freedom could be very helpful, because in this way we can introduce knowledge on the system that might help the classification task. In the case of damage location and due to restrictions upon actually damaging structures, it is sufficient in several applications only to locate the most likely damaged area instead of having the exact damage location. We thus propose here to build the probabilistic decision tree by partitioning the structure in subparts and to generate decisions associated with each of these geometrical subparts.

Let's consider that the structure has a geometrical topology that can be partitioned iteratively along affine hyperplanes. Then, one can constrain the decision tree to generate decision boundaries following these specific axes. The method that we propose is based on a recursive division, at each node of the decision tree, of the upstream classes in two disjoint groups with respect to their spatial location. The structure will thus be subdivided into small geometric zones to be monitored and the groups are simply determined according to their zone membership with respect to the symmetry axis. This geometric tree will furthermore facilitate the training step by giving an automatic and systematic procedure to perform it. In summary, the decision tree is deduced here from the specifications of the geometric boundaries of the structures and each of its leaves will represent a subpart of the structure.

Illustration of the SVM-GPDT algorithm

The whole SVM-GPDT algorithm is illustrated within a simple example. Let's consider a rectangular structure that is divided in 8 subzones to be monitored (Fig. 3(a)). In addition to the localization step, we also add a detection step but no quantification step in this geometric based probabilistic decision tree. Suppose that a database containing examples for each zone in the damaged and undamaged states has been constructed. 9 classes are considered: the 8 zones in presence of a damage (classes 1 to 8) and the undamaged class with healthy examples of all the zones (class 0). The first step of the tree is the detection step, where the classifier is trained to generate a decision with respect to the presence or not of damage. If a damage is detected, then decisions are taken recursively by following the symmetry axes of the structures to localize it. Upstream classes are divided in two groups by clustering symmetrical zones as shown in Fig. 3(a). The logical and geometric depiction of this tree is illustrated in Fig. 3(b). As we are dealing with PSVM classifier, the posterior probability of a damage to belong to each zone is also available at the end of the process (see Fig. 3(e) and Fig. 3(d)). 3 Damage detection, localization, and quantification on an active composite plate

Experimental setup

The proposed damage detection, localization, and quantification method is applied to a free-free composite plate (300 × 400 × 2.4 𝑚𝑚) with three circular piezoelectric buzzers of diameter 20 𝑚𝑚 bonded on its surface (Fig. 4.). These active elements can work either as actuators or sensors [START_REF] Benjeddou | Piezoelectric smart structures and systems[END_REF]. The structure is made up of 8 layers carbon epoxy material all oriented along the length of the plate (i.e. at 0°). The mechanical properties of the composite material are given in Table 1. The experimental setup and the actual smart plate are presented in Fig. 4. The piezoelectric elements are arbitrarily positioned (Fig. 4) but care is taken to avoid putting them on the axis of symmetry, which may introduce confusions in the localization process. For the present application, only one emitter is used.

Property

As we cannot impose real damage in a reversible manner, we have experimentally simulated its effect. In this work, local masses were added on predefined area of the structure as a mean of simulating damage. The justification behind that approach was that local stiffness reductions will reduce the natural frequencies and an alternative way of reducing the frequencies might be to locally increase mass. Therefore, to simulate damage at different locations and with different severities 𝑆 1 and 𝑆 2 , the plate was divided into damaged zones (Fig. 5) and two calibrated masses (𝑆 1 : 𝑚 1 = 20𝑔 and 𝑆 2 : 𝑚 2 = 10𝑔 ) have been positioned on each zone. As each damage scenario is reversible, this also allows monitoring the repeatability of the measurements. The number of damaged zones has been first fixed to 16 zones. Then to test the spatial selectivity of the approach we have increased the number of monitored zones to 32 (Fig. 5).

Features extraction

To extract damage-sensitive features, we use an active SHM approach based on a correlation technique that relies on wave diffraction pattern recognition. This approach, developed by the authors for tactile sensing purposes [START_REF] Liu | Tactile objects based on an amplitude disturbed diffraction pattern method[END_REF] is diverted here to be used to generate damage-sensitive features. The strategy retained here consists in monitoring the acoustic wave propagation (or the energy carried out by the Lamb wave) that can be affected by impact damages. Considering that the energy propagation is disturbed by the presence of damage, the diffraction signal can then provide the information needed to locate and quantify it. Following this observation, we use an active damage monitoring process based on the Amplitude Disturbed Diffraction Pattern (ADDP) phenomenon observed using the permanent emission of selected non-resonant Lamb waves (> 20). Lamb waves at different frequencies have different propagating velocities and ratios between the normal and the shear components. Therefore, they provide distinct diffraction behaviors when damage occurs on the plate. With an appropriate analysis and calibration procedure, we are able to locate the damage position and to quantify it. For our application, an excitation signal composed of 31 frequency components distributed from 20 kHz to 100 kHz has been constructed with a sampling frequency of 2 MHz and duration of 1 ms as depicted in Fig. 6. The number of the chosen frequencies is a tuning parameter selected to discriminate between features at numerous predefined damage positions. The reliability of this process depends highly on this choice. Following the approach developed in [START_REF] Liu | Tactile objects based on an amplitude disturbed diffraction pattern method[END_REF], we use the contrast value of the ADDP image as a criterion to validate a particular frequency excitation. In the sequel, we propose to use as damage features, the FFT (Fast Fourier Transform) of the signal received by each sensor 𝑅1 and 𝑅2.

Given that each sensor perceives different parts of the information, we have concatenated the signals coming from both sensors, obtaining a vector containing 400 attributes.

𝑥 𝑖 = [ 𝑓 1 (𝑅 1 ), 𝑓 2 (𝑅 1 ), … , 𝑓 200 (𝑅 1 ), 𝑓 1 (𝑅 2 ), … , 𝑓 200 (𝑅 2 )] 𝑖 = {1, … , 𝑛}
In terms of SVM (see Section. 2.1), the labels 𝑦 𝑗 associated with the examples 𝑥 𝑖 will be the 𝑄 zones in which the plate is divided (𝑄 = 16 or 32), as shown in Fig. 5.

SHM framework and SVM-GPDT classification architecture

The damage detection, localization and quantification algorithm proposed here is a sequential process that can be described by three main steps: calibration, learning and identification (Fig. 7). In the proposed framework, the first step consists in training the system. Then, when damage is detected, we first quantify its severity and then locate it. The general architecture of the classifier is illustrated in Fig. 8. The detection test is a simple probabilistic SVM, where we have to choose between two classes damaged and undamaged. As the number of severity classes are smaller than the number of damaged location (here only 2 classes), we have decided to perform an SVM-PDT to select which severity class we are concerned with and then to locate the damage. Knowing that SVM performances are heavily dependent on the hyper-parameters (𝐶, 𝜎 2 ) being used, it is recommended to perform a model selection procedure on each database to be learned (severity, location). This has been done according to Lin's algorithm [START_REF] Keerthi | Asymptotic behaviors of support vector machines with Gaussian kernel[END_REF] designed to choose the optimal hyper-parameters. The procedure for training is described in Fig. 8(b).

Probabilistic damage localization

To assess the performances of the proposed geometric classification approach, we have applied it first to locate damages on the plate partitioned into 16 zones. The idea in this subsection is to show how the posterior probability of a damage location is constructed. In these tests, only one type of damage (𝑚 1 = 20 g) has been considered. The database is composed of 96 normalized measures made on the plate (6 repetitions for each position, 𝑛 = 6). In Fig. 9(a), an example of damaged features (from zone 1 and 16) used to train the classifier is shown. One can notice from these signals, that the difference is not obvious and thus that it is hard to distinguish between them. The SVM-PDT classifier has been trained using a k-fold Cross-Validation method [START_REF] Rodriguez | Sensitivity Analysis of k-Fold Cross Validation in Prediction Error Estimation[END_REF], with 𝑘 = 4. So the classifier is trained 4 times, using 75% of the data to train the classifier and the remaining 25% of the points for testing. Once trained, the probability associated with each damage position can be shown on a figure with a color amplitude scale. The algorithm had a performance of 88% of examples well classified (i.e. well localized here) using a Gaussian kernel and the optimal hyper-parameters found after the optimization mechanism, which are 𝐶 = 10 6 and 𝜎 = 10 3 .

Fig. 10: GPDT decision boundaries for damage locate in zone 1

As presented in Section 3, a geometric approach based on the recursive generation of decision boundaries following symmetries along affine hyperplanes is used to generate the GPDT. As results, we depict in Fig. 9(b) the damage posterior spatial distribution provided by our algorithm. For this damage location test, snapshots at different nodes of the tree are illustrated in Fig. 10. The upstream classes are divided in two groups by clustering symmetrical zones. If we analyze the decision boundaries generated to locate the damage in zone 1, one can see from Fig. 10 that the symmetry axes are alternatively chosen along 𝑌 axis and 𝑋 axis. This automatic way of subdividing the structure and constructing the tree is not mandatory and alternate splitting strategies can be chosen.

In Fig. 11(a), the probability distribution over the plate is shown for a test that was made with a damage located in zone 13. This test shows one of the advantage of the proposed pattern recognition approach, which is that not only the most likely damaged zone is given but also zones with small damage probability. Indeed, we can notice from Fig. 11(a), that the neighbor's zones, have small probabilities of being the damaged zone. This information can be useful in the decision and prognostic steps as it can help improving the specification of robust bounds. The tree construction with the respective posterior probability at each node is illustrated in Fig. 11(b). To evaluate the posterior probability of a damaged zone, we use equation ( 9) by following the path generated to reach it. Note that there is only one way to get to a leaf (or equivalently a damaged zone). As depicted in Fig. 11, the algorithm detects and locates the damage in zone 13. The posterior probability associated with this diagnostic is 𝑝(𝑧𝑜𝑛𝑒 13|𝑢) = 0.5948 for zone 13 and 𝑝(𝑧𝑜𝑛𝑒 9|𝑢) = 0.1301 for damage in zone 9.

Probabilistic damage localization and quantification

We present now the results of the SVM-GPDT for damage localization and severity quantification. The plate is now divided in 32 zones (Fig. 5(b)) and electromechanical tests with added masses, simulating damage, have been conducted. We performed 8 tests (𝑛 = 8) for each zone, using the two masses 𝑚 1 = 20𝑔 and 𝑚 2 = 10𝑔. and hence two severity (𝑆 1 and 𝑆 2 ) Therefore, our database has now 512 entries (32 𝑧𝑜𝑛𝑒𝑠 × 2 𝑚𝑎𝑠𝑠𝑒𝑠 × 8 𝑟𝑒𝑝𝑒𝑡𝑖𝑡𝑖𝑜𝑛𝑠).

Following the architecture presented in Figure 12, our first concern was to determine the severity of the damage. To do so, all the examples from the tests performed with the mass 𝑚 1 have been assigned to a class, and the tests performed with the mass 𝑚 2 to another class. This way, we have a simple bi-class probabilistic SVM classifier to quantify severity. Again, we selected the Gaussian kernel and used Lin's algorithm [START_REF] Keerthi | Asymptotic behaviors of support vector machines with Gaussian kernel[END_REF] to determine the optimal hyper-parameters. The algorithm had a performance of 99.42% of examples well classified in terms of severity with 𝐶 = 10 6 and 𝜎 = 10 3 .

After the determination of the severity of the damage, we proceed to its localization. A second classifier is trained, using a procedure similar to the one shown in Fig. 8(b), the only difference being that we will only present the data for one type of severity to this classifier. This makes the task easier for the classifier, because different severities have different features and it will be very hard to the classifier to learn different signatures pointing to the same zone. So, it is better to only have a single signature for each zone, knowing the severity of the damage. For severity 𝑆 1 , we had a localization performance of 65.62%, using 𝐶 = 10 6 and 𝜎 = 10 2 . Using the test subset, normalized probability of several damage locations are depicted in Fig. 13 showing the effectiveness of the proposed approach. For severity 𝑆 2 we obtained a performance of 62.5%, using 𝐶 = 10 5 and 𝜎 = 10 3 . Results for some damage location are shown in Fig. 14. As expected, results for severity 𝑆 1 are better than those for 𝑆 2 . This was expected as the damage effects on measured signals are less significant with a smaller mass. Moreover, for some damaged zones as shown in Fig. 14(b), the location results could be misclassified in a neighboring zone, which is not such a problem. This classification error is related to the accuracy of the ADPP process used to generate damage features. Better results can be obtained with more frequencies in the excitation signal in order to discriminate some spurious features that can appear with wave reflections.

Discussion

Availability of a learning database

In the proposed approach, monitoring small zones facilitate the diagnostic but assume the availability of a damaged database for each zone. Moreover, good spatial resolutions suppose that several damaged structures are used in order to construct the precise database needed for the learning process. This is generally unrealistic unless the structures are cheap and easily available. To overcome this problem, one can simulate experimentally the damage effect instead of imposing a real one on the structure. For example, by changing locally in a reversible manner some of the characteristics of the structure (stiffness, natural frequencies …). The problem of acquiring data for each damage location can also be alleviated by using first, a high-fidelity physical model of the structure, usually by means of finite element analysis, that simulates the entire physical phenomenon: non linearity, degradation, and environmental operational conditions. And then, a surrogate model could be derived from the precise one to avoid a large number of heavy computations. This lower fidelity model will approximate the response of the complete one in an efficient manner and generate sufficient data for the learning process [START_REF] Echard | [END_REF].

Hierarchical or "flat" classification for damage monitoring?

Notionally, one can substitute hierarchical classification with "flat" one (standard binary or multiclass classification). Indeed, if we overlook our geometric class structure and replace the hierarchy with a set of classes, we can perform a multi-class classification problem. This means that all the relevant information that we have introduced through our knowledge about the damage monitoring problem and the structure geometry are ignored. In order, to show how this geometric hierarchical class structure boosts the performance of the damage localization, we have performed new experiments by comparing the performance of our classifier against other known classifiers. A multiclass SVM, using the one against all (SVM-OAA) method was chosen. This flat classifier was trained with all the samples from the training base (16 zones and 𝑆 1 severity), doing a k-fold cross-validation method with 𝑘 = 4. The classifier has good results when testing with training data (91%) but difficulty for generalization as shown in Fig. 15. In this figure the two classifiers had to classify new test points generated with slightly different environmental conditions. The damages have been introduced by the small weight that has been positioned at: (𝑎) the center of zone 9, (𝑏) the center of zone 11 and (𝑐) at the frontier between zones 12 and 16. As it can be seen, even the SVM-GPDT misclassified damage location, one could give credit to these partially correct results by checking the neighbor and the top-level zones given by the geometric hierarchy structure. Therefore, the maintenance procedure is facilitated and enhanced.

Multi class or multi-label classification problem?

The purpose of the present paper is to derive an original answer to the problem of damage detection, localization and quantification. A question that can be raised is whether a multi-class formulation of this problem is more appropriate than a multi-label formulation. The difference between the notions of class and label lies in the fact that an example can belong to only class, but can have multiple labels. Multi-label classification is thus an extension of multi-class classification where data can have one or more labels [START_REF] Gao | On the consistency of multi-label learning[END_REF]. Due to its great potential applications, multi-label learning has now been receiving more and more attention from many fields [START_REF] Tsoumakas | Multi-Label Classification: An Overview[END_REF][START_REF] Boutell | Learning multi-label scene classification[END_REF][START_REF] Ganu | Sparse Max-Margin Multiclass and Multi-label Classifier Design for Fast Inference[END_REF]. According to [START_REF] Tikk | A hirarchical text categorization approach and its application to FRT expansion[END_REF][START_REF] Silla | A survey of hierarchical classification across different application domains[END_REF], in the context of hierarchical classification, most approaches could be called multi-label. Indeed, if we recall the tree class structure presented in Fig. 3b, and suppose that the output of the classifier is the class {1}. Then it's natural to say also that the classifier have 3 outputs because class {1} belongs to classes {1 3} and {1 3 5 7} too. Therefore, with this simple definition, any hierarchical classification could be considered multi-label in this sense. Hierarchical multi-label classification algorithm is still a challenging problem and most approaches consider the case where it can be assigned more than one class at any level of the tree [START_REF] De Comité | Learning Multi-label Alternating Decision Trees from Texts and Data[END_REF].

Going back to the SHM problem, the output of SHM systems is a vector with 3 features: (i) damage zone, (ii) damage severity, (iii) damage type. The definition of each features is straightforward: several damage locations, several severity levels (BVID , VID) and different damage types (impact, debonding, delamination, …). With that in mind, it comes out that a class can be defined in a unique manner: one zone, one severity level and one type. With this class definition, the only overlapping examples are those lying along the frontier between two classes for a given feature. For example, damage could be located at the frontier between two zones or having a severity level between two pre-defined levels. These overlapping examples are thus a direct consequence of the a priori discretization of the features location and severity that are, in reality, continuous and not an intrinsic property of the problem under study. From the authors point of view, the SHM problem can therefore be naturally cast as a multiclass problem and not as a multi-label one. From that point of view, the proposed classification algorithm can be seen as an implicit probabilistic multi-label method where labels exist at the frontiers between classes. However, another point of view would be to define classes in relation to the different features. Following that idea, there will be one class for each damage location, one class for each damage type, and one class for each damage severity. Knowing this, there is a natural overlap between the different classes: for example, damages located in a given zone can be of distinct types and of severities. So with this definition of class, classes are indeed labels and the problem to face is a multi-label one. In Section 4.1, the consequence of spatial discretization is studied. It is shown that if the localization result has an ambiguity between neighborhood zones then by looking to the node just above in the decision tree, a macro-damaged zone can be defined. This is still a helpful guidance for the inspection task as afterwards the damage location can be refined by using traditional inspection techniques.

Spatial resolution versus computational cost

The performances of the classifier in term of spatial selectivity depend heavily on the method used to generate features and the availability of the damaged learning database. Increasing the spatial resolution will increase the training and testing times. The training time depends on the number of classes 𝑄 and the number of training samples. However, increasing the number of zones will enhance the detection process by reducing the rate of false damage localization. To illustrate this point, we have given to the two classifier (16 and 32 classes or zones), "unknown" damages to detect and locate. These damages are new experiences performed by introducing the mass 𝑚 1 = 20𝑔 on the plate with 16 classes at positions located on the edge of the separation zones and then this damage is monitored with 32 zones. In Fig. 16, a result is presented. We can notice that as expected the ambiguity of localization has decreased with the increase of the number of zones and consequently an increase of computational cost. We can also notice that, in general, the output of both classifiers is inline with the actual damage location. Therefore, this should be a tradeoff that one have to deal with when the applying such approaches in practice. In the literature, it is very often stated that the localization step should occur before the quantification phase [START_REF] Worden | The fundamental axioms of structural health monitoring[END_REF]. However, in the present work the quantification step has been performed before the localization one and gave excellent discrimination results between the two damages of different severities (added mass of 20 𝑔 and the added mass of 10 𝑔). Moreover, getting one and only one signature for each zone makes easier the classification task. If the localization is done first, different signatures will be assigned for the same localization. Those signatures could be very different if the gap between the severities becomes higher. It may even happen that the classifier could not find similar attributes in these groups of mixed severities, which would lead to poor classification performances. Another solution could have been to perform first the localization, and then, at the end of the GPDT to add a bi-class classifier to each leaf to assess the severity of the damage. However, this approach suffers from the fact that instead of one classifier needed for the present approach, one needs now 32 classifiers. So, from a computational point of view, this approach does not seem to be justified here. It can nevertheless be interesting, as a perspective, to implement a "localization then quantification" version of the present algorithm to compare its results with the present results.

In this paper, an original process for damage detection, localization and quantification on smart mechanical structures instrumented with piezoelectric active elements has been presented and validated experimentally. The SVM Geometric Probabilistic Decision Trees (SVM-GPDT) constitutes an original approach to the multi-class probabilistic damage classification problem. This algorithm takes advantage of the decision tree architecture and of the posterior probability provided by PSVM. At each node of the PDT, SVM classification associated with a sigmoid function is performed to estimate the probability of membership to each sub-group. A probability function is then built for each leaf by following the path that the PDT has generated for it. For each branch the outputs of all the nodes composing the branch are combined to lead to a complete evaluation of the probability when reaching the final leaf (representing the class associated with the branch). Formally, we thus presented and validated an interesting solution to solve a multiclass data classification problem in a manner that produces confidence probabilities associated with each damage feature. Moreover, the availability of the damage posterior probability will facilitate embedded damage monitoring. The SHM process will be trained offline and assessed online by calculating in real time the probabilities of having damages.

The approach has been tested experimentally on a composite plate, giving reliable predictions in terms of detection, localization and quantification. For real, applications, this approach is interesting as the chosen damage-sensitive feature is not very sensitive to border conditions, and the excitation with non-resonance frequencies will not accentuate the damage progression and impact the durability of the monitored structure.

Regarding the classification performances of the prosed method, it first advantage lies in the fact that it allows not just for classification, but for classification with an associated posterior probability. The second one is that the classification procedure proposed here is relatively fast as it is of logarithmic complexity. The third one is that the notion of geometry is introduced to the classifier. Because SHM is a problem in the real space, we can help the classifier by giving it some a-priori information that might discard data that is not relevant in a particular classification process, reducing the data to be treated, the time for treating it and the possibilities of mistakes. The last advantage is that as it relies on SVM, relatively few examples are needed for training. Regarding drawbacks, the first one is that the proposed method is based on discrete classes and thus imposes quantification of the different data features. The second one concerns the fact that in order to train the method example of damaged states are needed, and such examples are in practice not widely available. Actually, it is well known, that the main issue when applying pattern recognition approaches to damage monitoring is to construct a database of damage conditions. Indeed, the damage diagnostic system will not perform better than the data used to build it. As we need to avoid damaging the structure, two approaches can be used: multi-physical modeling and/or simulation of damage effects. It's this last approach that was used in this work. Another drawback is related to training set of data and the classifier generalization performances. Every classifier has its limits regarding the generalization capacity. Further tests should be performed in order to have a more precise idea about its capacities. We think that this drawback might be mitigated thanks to the probabilistic output. When the classifier is completely lost, he should provide a low probability associated to the uncertain prediction. The last drawback is linked to the training stage. Indeed, there is in reality, two training stage: the training of the SVMs of each node, and the training to get the probabilities out of each node. Thus, the previously mentioned advantage of the method (which is the need of few training points) has to be evaluated by considering that drawback. Suppose now that actual data related to damaging locations are available to train the machine learning diagnostics. Then, another problem rise which is how to elaborate features that could reliably discriminate between damage and undamaged states. The ADDP process has been used within this paper but maybe some other damage-sensitive features will perform better.

Another useful issue in a data mining is to have access to posterior probability associated with each damage classification. The approach presented throughout this work proposes a solution to the multi-class data classification problem in a manner that produces confidence probabilities associated with each damage feature. Each damage feature is classified from the most probable one to the least probable one. This is very interesting because this information can be valuable in the decision and prognostic steps and can help in improving the specification of robust bounds. Moreover, this knowledge could help the maintenance procedure by crossing with expert data.

Fig. 1 :

 1 Fig. 1: Example of SVM classification and probability estimation for a 2D binary problem

Fig. 2 :

 2 Fig. 2: Example of a probability decision tree

Fig. 3 :

 3 Fig. 3: SVM-GPDT example: (𝒂) rectangular structure with 8 zones and their associated axes of symmetry. (𝒃) GPDT construction. (𝒄) spatial damage probability distribution for zone 2.

Fig. 4 :

 4 Fig. 4: The smart structure and the test bench.

Fig. 5 :

 5 Fig. 5: The predefined damage zones: (𝒂) 16 damaged zones and (𝒃) 32 damaged zones with two levels of severity.

Fig. 6 :

 6 Fig. 6: (𝒂) Excitation signal (𝒃) Time response (c) FFT response

Fig. 7 :

 7 Fig. 7: The SHM classification based framework

Fig. 8 :

 8 Fig. 8: General Architecture. (𝒂) Severity-zone classification. (𝒃) Adaptation strategy

Fig. 9 :

 9 Fig. 9: Damage localization in zone 1: (𝒂) damage features, (𝒃) spatial probability distribution

Fig. 11 :

 11 Fig. 11: (a) Probability of damage location. (b) Probability path for damage in zone 13.

Fig. 13 :

 13 Fig. 13: Normalized location probability for a damage with severity 𝑆 1

Fig. 14 :

 14 Fig. 14: Normalized location probability for a damage with severity 𝑆 2

Fig. 15 :

 15 Fig. 15: Predicted damaged zones for the SVM-OAA (white cross) and SVM-GPDT.

Fig. 16 :

 16 Fig. 16: Spatial selectivity, number of zones and damage localization 4.5 Localization before quantification, or the opposite?

Table 1 :

 1 Mechanical properties of the composite material

		𝐸 11 = 𝐸 22 (GPa)	𝐸 33 (GPa)	𝐺 12 = 𝐺 13 = 𝐺 23 (GPa)	𝜈 21	𝜌 (𝐾𝑔/𝑚 3 )
	Value	65.7	8.1	5.2	0.02	1554


Thomas Genet

Yann Salmon

Proving Reachability Properties on Term Rewriting Systems with Strategies

We aim at defining regular over-approximation of sets of reachable terms for term rewriting systems applied with a strategy. In this ongoing work, we focus on innermost strategies which are the evaluation strategy of most functional programming languages. Having an accurate over-approximation of reachable terms for functional programming languages would permit to prove richer unreachability properties, i.e. safety properties on such programs.

Introduction

Term rewriting systems [START_REF] Baader | Term Rewriting and All That[END_REF], TRS for short, are a convenient way of representing computer programs: a term represents the current stage of the computation and rewriting rules represent allowed steps from one stage to another. We are interested in computing the set of terms reachable by rewriting, i.e. the set R * (L 0 ) = term t ∃s ∈ L 0 , s → * R t , for a given finite term rewriting system R and a set of so-called initial terms L 0 . Reachability properties on the TRS can be proven using a computable representation of this set or of an approximation thereof. This technique can be applied to Java programs thanks to the translation in [START_REF] Boichut | Rewriting Approximations for Fast Prototyping of Static Analyzers[END_REF] and is used in [START_REF] Genet | Rewriting for Cryptographic Protocol Verification (extended version)[END_REF] to assess the security of some cryptographic systems. In this paper, we take much simpler examples for the sake of readability.

For example, using an appropriate signature Σ, let R be a term rewriting system defining the natural integers with constant 0 and successor S, the usual arithmetical operations sum and mult as well as the factorial. Let L 0 be the initial language, i.e. the set of ground terms that we consider as the starting point of our program. Continuing our example, let L 0 be the set of terms of the form factorial(S(S... S(0)...)). Verifying that the factorial of a natural is never zero using our formalism amounts to checking that the term 0 is not reachable from terms in L 0 by arbitrary applications of the rules in R, that is

R * (L 0 ) ∩ {0} = ∅.
The general TRS (un)reachability problem, "Does R * (L 0 ) ∩ L b = ∅?", where L b is a set of terms considered bad, is obviously not decidable, due to the Turing-completeness of the TRS formalism. Circumventing this is usually done by working with regular languages [START_REF] Comon | Tree Automata Techniques and Applications[END_REF], for which computing the intersection and checking emptiness can be done in polynomial time. Restricting to regular initial (L 0 ) and bad languages (L b ) is not enough: this does not ensure that R * (L 0 ) is regular. The regularity-preservation property of TRS is in turn undecidable [START_REF] Gilleron | Regular Tree Languages and Rewrite Systems[END_REF]; it has been proven true for some restricted classes of TRS. For instance, Réty [START_REF] Réty | Tree automata for rewrite strategies[END_REF] computes R * strat (L 0 ), the set of descendants of terms in L 0 obtained by applications of rules in R using the strategy strat, for the restricted class of TRS called constructor-based and several strat.

Instead of restricting the TRS classes, we focus on tree automaton completion, stemming form the work of [START_REF] Genet | Decidable Approximations of Sets of Descendants and Sets of Normal Forms[END_REF], and more precisely on equational completion [START_REF] Genet | Equational Tree Automata Completion[END_REF] (or just "completion" for short). This technique aims at computing a sufficiently precise regular over-approximation

K of R * (L 0 ). Since K ⊇ R * (L 0 ), from K ∩ L b = ∅ follows R * (L 0 ) ∩ L b = ∅.
This procedure can be applied to any left-linear TRS, but does not always terminate. Overapproximating eases termination, but it needs to be precise enough to prove unreachability properties: if K is too large then we may have

K ∩ L b ∅ though R * (L 0 ) ∩ L b = ∅.
Recently, many techniques for building accurate approximations have been studied: declarative language (equations) for defining approximations [START_REF] Genet | Equational Tree Automata Completion[END_REF] and automatic approximation refinement [START_REF] Bouajjani | Abstract Regular Tree Model Checking[END_REF][START_REF] Boichut | Fast Equational Abstraction Refinement for Regular Tree Model Checking[END_REF]. However, none of those approaches takes the strategy used to apply the rules of the TRS into account: they over-approximate R * (L 0 ) which is itself an overapproximation of R * strat (L 0 ). This causes imprecisions when over-approximating the set of reachable terms for functional programming languages, such as OCaml [START_REF] Leroy | The Objective Caml system release 3.12 -Documentation and user's manual[END_REF] or those used in proof assistants like Coq [START_REF] Bertot | Interactive Theorem Proving and Program Development. Coq'Art: The Calculus of Inductive Constructions[END_REF] or Isabelle/HOL [START_REF] Nipkow | Isabelle/HOL -A Proof Assistant for Higher-Order Logic[END_REF]. Such functional programs can be encoded by TRS applied with a leftmost innermost strategy. Our overall objective is to take into account strat in the over-approximation of R * strat (L 0 ). This work, which is a first step in this direction, aims at taking into account the innermost part of the strategy. We want to refine the equational completion procedure of [START_REF] Genet | Equational Tree Automata Completion[END_REF] in order to have a better precision in the overapproximation of R * in (L 0 ), the set of descendants of terms in L 0 obtained by applications of rules in R using an innermost strategy. At the end of the paper, we will see that the technique presented here is likely to be adapted to cover the leftmost part of the strategy, but this is ongoing work. A precise approximation of terms reachable by leftmost innermost rewriting would be a simple and elegant alternative to Higher Order Recursive Schemes used for the static analysis of functional programs [START_REF] Ong | Verifying higher-order functional programs with pattern-matching algebraic data types[END_REF].

Innermost strategies

In our example TRS R, the term mult(S(0), plus(S(0), S(0))) has more than one reducible expression, or redex: it can be rewritten in one step either to the term plus(mult(0, plus(S(0), S(0))), plus(S(0), S(0))), using the rule mult(S(x),y)→plus(mult(x, y), y) at the root, or to the term mult(S(0), S(plus(0, S(0)))), using the rule plus(S(x), y)→S(plus(x, y)) in the appropriate subterm plus(S(0), S(0)). To consistently decide which redex to reduce, implementations of TRS can use a strategy.

Innermost strategies consist in reducing a redex only when none of its strict subterms is a redex itself; in our example, this is the latter reduction. Due to some reductions being disallowed, R * in (L 0 ) ⊆ R * (L 0 ), and very often, R * in (L 0 ) ⊂ R * (L 0 ). Note that given a term t, checking that each subterm of t at depth 1 is R-irreducible is sufficient to ensure that a rewriting step may be applied to t under an innermost strategy.

We want to build a correct and reasonably precise over-approximation of R * in (L 0 ). As exposed later, the current equational completion procedure is not strategy-aware. This does not hinder correctness:

K ⊇ R * (L 0 ) implies K ⊇ R *
in (L 0 ). However, the process introduces a potentially great number of terms in K that are irrelevant when we are interested in R * in (L 0 ).

Usual completion procedure

Given a left linear TRS R over signature Σ, the automaton completion procedure takes an automaton A 0 recognising the initial language L 0 and iteratively adds transitions to it to incorporate R-descendants of already recognised terms. It stops when (if) a fixpoint is reached: the language recognised by the pro-

duced automaton A * , L (A * ) 1 , is a superset of L 0 and is R-closed, thus L (A * ) is a superset of R * (L 0 )
. Transitions, and possibly new states, are added to the automaton A i , where i is some step of the completion process, by resolving socalled critical pairs (CP ): a rule → r ∈ R instantiated into configurations of A i as σ → rσ , where σ is an arbitrary map from variables of Σ to states of A, extended to terms like a traditional substitution and A i recognises σ into a state q, but not rσ . The resolution amounts to adding valid (normalised) transitions and the needed states to let the completed automaton A i+1 recognise rσ into q as well.

The procedure does not always terminate, because resolution can create new critical pairs. Merging states of the automaton counters this at the cost of precision. This can be parametrised by linear equations between terms as in [START_REF] Genet | Equational Tree Automata Completion[END_REF]. An equation t = s instantiated into configurations of A as tσ = sσ is said to be applicable if there exist two distinct states q 1 and q 2 such that A recognises tσ into q 1 and sσ into q 2 . In this case, the states q 1 and q 2 are "merged". Therefore, the equational completion procedure takes as input not only R and A 0 , but a set E of such equations as well, and, in case of termination, outputs a fixpoint automaton A * R,E . For example, take signature Σ = {f : 1, g : 1, a : 0, b : 0, c : 0} and set of variables {x}, R = {f (x) → g(x), a → b}, L 0 = {f (a), f (c)} and E = ∅. Note that 1 Given an automaton A and a state q of A, we note L (A, q) the set of terms recognised by A into state q. g(a) ∈ R * (L 0 ) R * in (L 0 ). A reasonable automaton to recognise L 0 is A 0 consisting of states q a , q c , q f a , q f c and transitions a q a , c q c , f (q a ) q f a and f (q c ) q f c . We have a critical pair CP 1 = (f (x) → g(x), σ = {x → q a }, q f a ): A 0 recognises f (q a ) into q f a but not g(q a ). Resolving CP 1 builds a new automaton A 1 from A 0 by addition of state q 1 and transitions g(q a ) q 1 and q 1 q f a . This is shown in figure 1. The epsilon transition q 1 q f a reads no input and is oriented in this way to ensure that the right-hand side of the rule is recognised into the same state as the left-hand side was previously recognised. We also solve CP 2 = (a → b, σ = ∅, q a ) by adding q 2 and b q 2 , q 2 q a and CP 3 = (f (x) → g(x), σ = {x → q c }, q f c ) by adding q 3 and g(q c ) q 3 and q 3 q f c . In this example, there are no more critical pairs and the procedure terminates with A * R,E = A 3 . Assuming the same final states as in A 0 , we have indeed

L (A 3 ) = R * (L 0 ). (a) CP 1 f (q a ) g(q a ) q f a q 1 R A 0 * A 1 * A 1 (b) CP 2 a b q a q 2 R A 1 * A 2 * A 2 (c) CP 3 f (q c ) g(q c ) q f c q 3 R A 2 * A 3 * A 3

Fig. 1. Resolving critical pairs

The correctness theorem of [START_REF] Genet | Equational Tree Automata Completion[END_REF] states that under the aforementioned hypotheses, L (A * R,E ) ⊇ R * (L (A 0 )). The precision theorem of the same states that under the supplementary hypothesis that A 0 is consistent with R and E, which merely means that the language recognised in each state of A 0 is a subset of some equivalence class of the congruence relation induced by E, and has a common antecedent by R/E, the "R modulo E" rewrite relation, we have

L (A * R,E ) ⊆ (R/E) * (L (A 0 )).

Our current research aims at designing a procedure to build an automaton

A * R in ,E such that L (A * R in ,E ) ⊆ (R in /E) * (L (A 0 )).
Left-linearity of R is required for correctness: take Σ = {h : 2, g : 1, a : 0}, R = {h(x, x) → g(x)}, ie. a non left-linear TRS due to the presence of twice the same variable x in the left-hand side of a rule, and take A 0 with transitions a q 1 , a q 2 and h(q 1 , q 2 ) q f . This last transition should intuitively give rise to a critical pair, but does not because the possible instantiations σ of the only rule are h(q 1 , q 1 ), h(q 2 , q 2 ) and h(q f , q f ). A 0 is the fix-point of the completion procedure, but g(a) L (A 0 ) while g(a) ∈ R({f (a, a)}).

The completion of some critical pairs corresponds to rewriting steps that do not conform to innermost strategies. In the example of section 3, we do not want to solve CP 1 , at least not before CP 2 , and even when we do, we would like to distinguish between a and b being recognised into q a when dealing with g(q a ). How to determine with certainty that every term recognised in a given state is reducible by R? Indeed, if we abstain from solving a critical pair that involves a state representing at least one irreducible term, we risk missing some terms in R * in (L 0 ) and loosing correctness.

A first approach uses the fact that because R is left-linear, IRR(R), the set of R-normal forms, is regular [GT95, Theorem 4]. We define the fibre of a configuration c of automaton A,

F (A, c), inductively: if c is a state, F (A, c) = L (A, c); if c is a constant, F (A, c) = {c}; else c = f (c 1 , . . . , c k ) and F (A, c) = {f (α 1 , . . . , α k ) | ∀i ∈ 1 ; k , α i ∈ F (A, c i )}.
It is a regular language. We define a new notion of critical pair CP = ( → r, σ , q) by adding the following restriction: if σ is of the form f (c 1 , . . . , c k ) where c 1 , . . . , c k are configurations, then for all i ∈ 1 ; k , we must have F (A, c i )∩IRR(R) ∅. The fixpoint automaton that this new procedure produces (if any) recognises a R in -closed language which contains L 0 , and therefore contains R * in (L 0 ). The proof can be derived from the one of theorem 45 in [START_REF] Genet | Equational Tree Automata Completion[END_REF]: both are based on the ability to build a critical pair from any valid rewriting step.

However, since building an automaton recognising IRR(R) can be exponential in the size of R, we are also exploring a second approach that would not require IRR(R). The structure of the completed automaton can be used to distinguish between normal forms and reducible terms. On the previous example, we can infer from the automaton that a is not a normal form since it is recognised by q a and there is an epsilon transition q 2 q a . According to completion, this epsilon transition denotes that a is reducible and we can thus mark the path a q a as "forbidden" w.r.t. an innermost completion. It might be possible to check if a critical pair is innermost-compatible by carefully inspecting the recognising path of lσ q. In our example, the path a q a would be forbidden after completion of CP 2 . Since the path g(q a ) q 1 q f a results from the completion of some critical pair (CP 1 ), a q a would not be taken into account, thereby excluding g(a) from the recognised language and keeping g(b). On the other hand, the path f (q a ) q f a does not result from a completion step, so a q a would still be available in this case, causing f (a) to be recognised. This is not surprising, since it belongs to L 0 , a subset of R * in (L 0 ). Furthermore, if a state has only forbidden paths pointing thereto, it could be completely avoided as a value when enumerating the possible σ . This approach might be useful for leftmost-innermost strategies as well, where one only reduces an innermost redex when there is no redex at its left. With Σ = {h : 2, a : 0, b : 0, c : 0, d : 0}, R = {a → b, c → d}, A = {a q a , c q c , h(q a , q c ) q h }, usual completion adds epsilon transitions q b q a and q d q c that cause h(a, d) h(q a , d) h(q a , q d ) h(q a , q c ) q h . Indeed, h(a, d) ∈ R({h(a, c)}), but this stems from a non-leftmost rewriting. Marking a q a and c q c as "forbidden" like before would allow us to disregard the aforementioned derivation, because q a appears to the left of q c in the configuration and the paths leading to each of them are "forbidden". On the other hand, we would retain h(b, d) h(q b , d) h(q b , q d ) h(q b , q c ) q h because q b , appearing to the left of q c , has a non-forbidden path from b to it. This requires more investigation, though.

Conclusion and perspectives

We sketched a general way of refining equational completion to adapt it to innermost strategies. We have to give a precise and efficient algorithm to compute the fibre of a configuration that cleverly takes into account the fact that each completion step can modify the fibres. We also plan to assess whether our second approach is correct and to compare its efficiency with the first one, and maybe interleave them.

We have to quantify the gain in precision granted by our proposed procedure and balance it with its supplementary computational cost. It should also be noted that due to our proposed strategy-aware completion procedure resolving less critical pairs than the usual one, its termination is easier to achieve. We want to explore whether this gain is marginal or not.

Finally, we want to adapt the usual completion procedure to different and more expressive strategies so as to build precise over-approximation of reachable terms for other programming languages. Target strategies are the outermost strategy, used for example by Haskell [Has], and declarative strategies like the one used in Tom [START_REF] Balland | Tom: Piggybacking Rewriting on Java[END_REF].