Claudia D ' Amato
email: claudia.damato@uniba.it

Andrea G B Tettamanzi
email: andrea.tettamanzi@unice.fr

Minh Tran Duc

Claudia D'amato

Tran Duc

Evolutionary Discovery of Multi-Relational Association Rules from Ontological Knowledge Bases

Keywords: Description Logics, Pattern Discovery, Evolutionary Algorithms

published or not. The documents may come

Introduction

The Semantic Web [START_REF] Berners-Lee | The semantic web[END_REF] is the new vision of the Web aiming at making Web contents machine readable besides of human readable. For the purpose, Web resources are semantically annotated with metadata referring to ontologies that are formal conceptualizations of domains of interest acting as shared vocabularies where the meaning of the annotations is formally defined. As such, annotated web resources represent the assertional knowledge given the intensional definitions provided with ontologies. Assertional and intensional ontological knowledge will be referred to as ontological knowledge base.

In the SW view, data, information, and knowledge are connected following best practices and exploiting standard Web technologies, e.g. HTTP, RDF and URIs. This allows to share and link information that can be read automatically by computers meanwhile creating a global space of resources semantically described.

The description of data/resources in terms of ontologies represents a key aspect in the SW. Interestingly, ontologies are also equipped with powerful deductive reasoning capabilities. However, due to the SW heterogeneous and distributed nature, ontological knowledge bases (KBs) 1 may turn out to be incomplete and noisy w.r.t. the domain of interest. Specifically, an ontology is incomplete when it is logically consistent (i.e., it contains no contradiction) but it lacks information (e.g., assertions, disjointness axioms, etc.) w.r.t. the domain of reference; while an ontology is noisy when it is logically consistent but it contains invalid information w.r.t. the reference domain. These situations may prevent the inference of relevant information or cause incorrect information to be derived.

However, by exploiting the evidence coming from the (assertional) knowledge, data mining techniques could be fruitfully exploited for discovering hidden knowledge patterns from ontological KBs, to be used for enriching an ontology both at terminological (schema) and assertional (facts) level, even in presence of incompleteness and/or noise. We present a method based on evolutionary algorithms, for discovering hidden knowledge patterns in the form of multi-relational association rules (ARs) coded in SWRL [START_REF] Horrocks | SWRL: A semantic web rule language combining OWL and RuleML[END_REF], which can be added to the ontology enriching its expressive power and increasing the assertional knowledge that can be derived. Additionally, discovered rules may suggest new axioms to be added to the ontology, such as transitivity and symmetry of a role, and/or concept/role inclusion axioms. Even if related work focussing on a similar goal can be found in the SW community (see [START_REF] Lisi | AL-QuIn: An onto-relational learning system for semantic web mining[END_REF][START_REF] Józefowska | The role of semantics in mining frequent patterns from knowledge bases in description logics with rules[END_REF][START_REF] Völker | Statistical schema induction[END_REF][START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF][START_REF] Galárraga | Fast rule mining in ontological knowledge bases with AMIE+[END_REF]) and in the ILP community (see [START_REF] Philip | Scaling up inductive logic programming: An evolutionary wrapper approach[END_REF][START_REF] Divina | Genetic Relational Search for Inductive Concept Learning: A Memetic Algorithm for ILP[END_REF][START_REF] Muggleton | QG/GA: a stochastic search for progol[END_REF]), to the best of our knowledge, our work represents the first proposal that is able to discover hidden knowledge patterns in ontological knowledge bases while taking into account the background/ontological knowledge and exploiting the efficiency of genetic algorithms jointly with reasoning capabilities.

Evolutionary algorithms (EAs) [START_REF] Dejong | Evolutionary Computation: A unified approach[END_REF][START_REF] Eiben | Introduction to Evolutionary Computing[END_REF] are bio-inspired stochastic optimization algorithms, which exploit two principles that allow populations of organisms to adapt to their surrounding environment: genetic inheritance and survival of the fittest. Each individual of the population represents a point in the space of the potential solutions for the considered problem. The evolution is obtained by iteratively applying a small set of stochastic operators, known as mutation, recombination, and selection. Mutation randomly perturbs a candidate solution; recombination decomposes two distinct solutions and then randomly mixes their parts to form novel solutions; selection replicates the most successful solutions found in a population at a rate proportional to their relative quality. The resulting process tends to find, given enough time, globally optimal solutions to the problem much in the same way as in nature populations of organisms tend to adapt to their surrounding environment.

We build on these ideas and we combine them with recent work on relational ARs discovery from populated KBs in the Semantic Web [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF][START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF] to propose an EA for the discovery of mulit-relational ARs. The rationale for using EAs as a meta-heuristic for ILP is to mitigate the combinatorial explosion generated by the inductive learning of rich representations, such as those used in description logics [START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF], while maintaining the quality of the results.

Our solution is experimentally evaluated and comparisons with the main state-of-the art systems are provided. In the next section, basics are illustrated; the proposed method for discovering multi-relational association rules from ontological KBs is presented in Sect. 3 while its experimental evaluation is illustrated and discussed in Sect. 5. The main characteristics and value added of our proposal with respect to the state of the art are analyzed in Sect. 4. Conclusions and future work directions are drawn in Sect. 6.

Basics

We refer to ontological KBs described in Description Logics (DLs) [START_REF] Baader | The Description Logic Handbook: Theory, Implementation, and Applications[END_REF] (being DLs the theoretical foundation of OWL), and we do not fix any specific DL. As usual in DLs, we will refer to a KB K= (T , A) defined by means of the set of the terminological axioms, namely the TBox T , and the set of assertional axioms, namely the ABox A and where the formal meaning of the axioms is given in terms of model-theoretic semantics. As for reasoning services, instance checking, which assesses if an individual is instance of a given concept, and concept subsumption, which consists in checking whether a concept (role) is subsumed by another concept (role), are exploited. Remind that DLs adopt the open-world assumption (OWA) which has consequences on answering to class-membership queries. Specifically, it may happen that an individual that cannot be proved to be instance of a certain concept is not necessarily a counterexample for it, rather it would be only interpreted as a case of insufficient (incomplete) knowledge for possibly proving the assertion. For more details concerning DLs see [START_REF] Baader | The Description Logic Handbook: Theory, Implementation, and Applications[END_REF].

In the following the general definition of relational AR for an ontological KB K is given. Hence, the problem we want to address is formally defined.

Definition 1 (Relational Association Rule). Given a populated ontological KB K= (T , A), a relational association rule r for K is a Horn-like clause of the form: body → head, where: (a) body is a generalization of a set of assertions in K co-occurring together; (b) head is a consequent that is induced from K and body Definition 2 (Problem Definition).

Given:

a populated ontological knowledge base K = (T , A); a minimum "frequency threshold", θ f ; a minimum "head coverage threshold", θ hc ; a minimum "confidence improvement threshold", θ ic ; Discover: all frequent hidden patterns w.r.t θ f , in the form of multi-relational ARs, that may induce new assertions for K.

Intuitively, a frequent hidden pattern is a generalization of a set of concept/role assertions co-occurring reasonably often (w.r.t. a fixed frequency threshold) together, showing an underlying form of correlation that is exploited for obtaining new assertions.

For representing the rules to be discovered (following Def. 2), the Semantic Web Rule Language (SWRL) [START_REF] Horrocks | SWRL: A semantic web rule language combining OWL and RuleML[END_REF] is adopted. It extends the set of OWL axioms of a given ontology with Horn-like rules. 2Definition 3 (SWRL Rule). Given a KB K, a SWRL rule is an implication between an antecedent (body) and a consequent (head) of the form:

B 1 ∧ B 2 ∧ . . . B n → H 1 ∧ . . . ∧ H m , where B 1 ∧ . . . ∧ B n is the rule body and H 1 ∧ . . . ∧ H m is the rule head. Each B 1 , . . . , B n , H 1 , . . . H m is called an atom.
An atom is a unary or binary predicate of the form P c (s), P r (s 1 , s 2 ), sameAs(s 1 , s 2 ) or differentFrom(s 1 , s 2 ), where the predicate symbol P c is a concept name in K, P r is a role name in K, s, s 1 , s 2 are terms. A term is either a variable (denoted by x, y, z) or a constant (denoted by a, b, c) standing for an individual name or data value.

The discovered rules can be generally called multi-relational rules since multiple binary predicates P r (s 1 , s 2 ) with different role names of K could appear in a rule. The intended meaning of a rule is: whenever the conditions in the antecedent hold, the conditions in the consequent must also hold. A rule having more than one atom in the head can be equivalently transformed, due to the safety condition (see Def. 4), into multiple rules, each one having the same body and a single atom in the head. We will consider, w.l.o.g., only SWRL rules (hereafter just "rules") with one atom in the head.

Fixing the Language Bias

In this section, the adopted language bias is specified. It consists of a set of constraints giving a tight specification of the patterns worth considering, thus allowing to reduce the search space. We manage rules having only atomic concepts and/or role names of K as predicate symbols, and individual names as constants. Only connected [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF] and nonredundant [START_REF] Józefowska | The role of semantics in mining frequent patterns from knowledge bases in description logics with rules[END_REF] rules satisfying the safety condition [START_REF] Horrocks | A proposal for an OWL rules language[END_REF] are considered. Additionally, to guarantee decidability, only DL-safe rules are managed [START_REF] Motik | Query answering for OWL-DL with rules[END_REF], that is rules interpreted under the DL-safety condition consisting in binding all variables in a rule only to explicitly named individuals in K. 3 In the following, notations and formal definitions for the listed properties are reported.

Given an atom A, let T (A) denote the set of all the terms occurring in A and let V (A) ⊆ T (A) denote the set of all the variables occurring in A e.g. V (C(x)) = {x} and V (R(x, y)) = {x, y}. Such notation may be extended to rules straightforwardly. Definition 4 (Safety Condition). Given a KB K and a rule r = B 1 ∧B 2 ∧. . . B n → H, r satisfies the safety condition if all variables appearing in the rule head also appear in the rule body; formally if:

V (H) ⊆ n i=1 V (B i ),
Definition 5 (Connected Rule). Given a KB K and a rule r = B 1 ∧B 2 ∧. . . B n → H, r is connected iff every atom in r is transitively connected to every other atom in r.

Two atoms B i and B j in r, with i = j, are connected if they share at least a variable or a constant i.e. if T (B i ) ∩ T (B j ) = ∅.

Two atoms B 1 and B k in r are transitively connected if there exist in r, atoms B 2 , . . . , B k-1 , with k ≤ n, such that, for all i, j ∈ {1, . . . , k}

with i = j, T (B i ) ∩ T (B j ) = ∅. Definition 6 (Non-redundant Rule). Given a KB K and a rule r = B 1 ∧ B 2 ∧ . . . B n → H, r is a non-redundant rule if no atom in r is entailed by other atoms in r wrt K, i.e., if, ∀i ∈ {0, 1, . . . , n}, with B 0 = H, results: j =i B j |= K B i , Example 1 (Redundant Rule). Given K with T = {Father
Parent} and the rule r = Father(x) ∧ Parent(x) → Human(x) where Human is a primitive concept, r is redundant since the atom Parent(x) is entailed by the atom Father(x) wrt K.

Metrics for Rule Evaluation

For determining the rules of interest for the goal in Def. 2, metrics for assessing the quality of a rule are necessary. In the following, the adopted metrics are summarized.

Given a rule r = B 1 ∧ . . . ∧ B n → H, let us denote:

-Σ H (r) the set of distinct bindings of the variables occurring in the head of r, formally: Σ H (r) = {binding V (H)} -E H (r) the set of distinct bindings of the variables occurring in the head of r provided that the body and the head of r are satisfied, formally:

E H (r) = {binding V (H) | ∃ binding V (B 1 ∧ . . . ∧ B n ) : B 1 ∧ . . . ∧ B n ∧ H}. Since rules are connected, V (H) ⊆ V (B 1 ∧ . . . ∧ B n ) -M H (
r) the set of distinct bindings of the variables occurring in the head of r also appearing as binding for the variables occurring in the body of r, formally:

M H (r) = {binding V (H) | ∃ binding V (B 1 ∧ . . . ∧ B n ) : B 1 ∧ . . . ∧ B n }
Following [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF][START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF], we recall a few basic definitions, modified from the classical ones (as given e.g. in [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF]) to ensure monotonicity when atoms are added to the body of a rule.

Definition 7 (Rule Support). Given a rule r = B 1 ∧ . . . ∧ B n → H, its support is given by the number of distinct bindings of the variables in the head, formally:

supp(r) = |E H (r)|. (1)
Definition 8 (Head Coverage for a Rule). Given a rule r = B 1 ∧ . . . ∧ B n → H, its head coverage is given by the proportion of the distinct variable bindings from the head of the rule that are covered by the predictions of the rule:

headCoverage(r) = |E H (r)|/|Σ H (r)|. (2)
Definition 9 (Rule Confidence). Given a rule r = B 1 ∧ . . . ∧ B n → H, its confidence is defined as the ratio of the number of distinct bindings of the predicting variables in the rule head and the number of their bindings in the rule body:

conf(r) = |E H (r)|/|M H (r)|. (3)
An issue with these definitions, and particularly Def. 9, is that an implicit closedworld assumption is made, since no distinction between false predictions, i.e., bindings σ matching r such that K |= ¬Hσ, and unknown predictions, i.e., bindings σ matching r such that both K |= Hσ and K |= ¬Hσ, is made. On the contrary, reasoning on ontologies is grounded on the open-world assumption. Additionally, our goal is to maximize correct predictions, not just describing the available data. To circumvent this limitation the following metric, generalizing the PCA Confidence [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF], is introduced.

Definition 10 (Rule Precision). Given a rule r = B 1 ∧ . . . ∧ B n → H, its precision is given by the ratio of the number of correct predictions made by r and the total number of correct and incorrect predictions (predictions logically contradicting K), leaving out the predictions with unknown truth value.

This metric expresses the ability of a rule to perform correct predictions, but it is not able to take into account the induced knowledge, that is the unknown predictions. For this reason, the metrics proposed for this purpose in [START_REF] Fanizzi | Learning with kernels in description logics[END_REF] are also considered for the evaluation in Sect. 5. They are recalled in the following:

match rate: number of predicted assertions in agreement with facts in the complete ontology, out of all predictions; commission error rate: number of predicted assertions contradicting facts in the full ontology, out of all predictions; induction rate: number of predicted assertions that are not known (i.e., for which there is no information) in the complete ontology, out of all predictions.

Evolutionary Discovery of Relational Association Rules

Given a populated ontological KB, our goal is to discover frequent hidden patterns in the form of multi-relational ARs to be exploited for making predictions of new assertions in the KB. The discovered rules are DL-Safe and expressed in SWRL (see Sect. 2). Hence, they can be integrated with the existing ontology, resulting in a KB with an enriched expressive power [START_REF] Horrocks | A proposal for an OWL rules language[END_REF][START_REF] Horrocks | SWRL: A semantic web rule language combining OWL and RuleML[END_REF].

To achieve this goal, we propose to search the space of the SWRL rules that respect the language bias defined in Section 2.1 using an EA. The algorithm maintains a population of patterns (the individuals) and makes it evolve by iteratively applying a number of genetic operators. A pattern is the genotype of an individual and the corresponding rule is its phenotype. Since, like [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF], our goal is to discover rules capable of making a large number of predictions, the fitness of a pattern is the head coverage (cf. Definition 8) of the rule constructed using the first atom of the pattern as the head and the remaining atoms as the body.

Algorithm 1 The CREATENEWPATTERN() Operator.

Input: a global variable A f : a list of frequent atoms; Output: r: a new, random pattern.

1: length ∼ U (2, MAX RULE LENGTH) 2: pick an atom a ∈ A f at random 3: r ← a 4: while r.SIZE() < length p do 5:

r ← SPECIALIZE(r) 6: return r
The approach we propose may be regarded as alternative and complementary to level-wise generate-and-test algorithms for discovering relational ARs from RDF datasets [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF] and, more specifically, recent proposals that take into account terminological axioms and deductive reasoning capabilities [START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF].

Representation

As in [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF][START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF], a pattern is represented as a list of atoms of the form C(x) or R(x, y), respecting the language bias, to be interpreted in conjunctive form. For each discovered frequent pattern, a multi-relational AR is constructed by considering the first atom in the list as the head of the rule and the remaining atoms as the rule body.

The genetic operators of initialization, recombination, and mutation, described in the following sections, are designed to enforce the language bias. An important consequence of the fact that patterns are intended to be transformed into rules for evaluation is that the order of atoms counts only insofar as one atom is in the head position (and, therefore, the head of the rule) or it is not (and, therefore, in the body of the rule). The relative position of atoms that are not in the head position is irrelevant.

Initialization

The initial population is seeded by n random patterns, randomly generated according to Alg. 1. This CREATENEWPATTERN() initialization operator requires a list A f of frequent atoms, which is computed once and for all before launching the evolutionary process, and returns a new random pattern. A frequent atom is a pattern r consisting of a single atom of the form C(x) or R(x, y), such that supp(r) ≥ θ f (cf. Def. 7). A new pattern is seeded with a frequent pattern picked at random from A f and a random target length between 2 and MAX RULE LENGTH is chosen; the specialization operator (detailed in Alg. 4), which adds a random atom to an existing pattern while respecting the language bias, is then called repeatedly, until the target length is attained.

Recombination

The recombination (or crossover) operator produces two offspring patterns from two parent patterns, by randomly exchanging their body atoms and fixing, if necessary, their variables so that they respect the language bias.

The operator, detailed in Algorithm 2, proceeds by creating a set L including all the atoms in the two input patterns and choosing a target length for the two offspring; then,

Algorithm 2 The Recombination Operator RECOMBINE(p, r).

Input: p, r: the two patterns to be recombined; Output: p , r : two patterns that are a recombination of the input patterns. fix a so that p ∧ a respects the language bias 8:

p ← p ∧ a 9: r ← 10: while r .SIZE() < length r do 11: pick an atom a ∈ L at random 12: fix a so that r ∧ a respects the language bias 13: r ← r ∧ a 14: return p , r

Algorithm 3 The Mutation Operator MUTATE(r).

Input: r: the pattern to be mutated; Output: r : the mutated pattern. 11: return r atoms are picked from L at random and added to either pattern until the target length is attained, possibly changing their variables to ensure the language bias is respected.

Recombination is performed with probability p cross .

Mutation

The mutation operator is based on the idea of specialization and generalization operators in inductive logic programming. Roughly speaking, a specialization operator appends a new atom to a pattern while preserving the language bias, whereas a generalization operator removes a body atom from a pattern while preserving the language bias. Mutation is applied to every child pattern (resulting from recombination or not) with a small probability p mut 1. Mutation, summarized in Algorithm 3, applies the specialization operator, if the head coverage of the rule corresponding to the pattern is above a given threshold θ mut , or the generalization operator, if its head coverage is below θ mut , to the pattern undergoing it.

The specialization operator is detailed in Algorithm 4. A specialization for a given pattern may be generated by applying one of the operators, defined in [START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF]:

Algorithm 4 The Specialization Operator SPECIALIZE().

Input: r: the pattern to be specialized; Output: r : the specialized pattern.

1: X ∼ U (0, 1) {Extract a uniform random number from [0, 1)} 2: if X < 1 11: return r -ADDCONCEPTATOM, which adds an atom whose predicate symbol is a concept name in the ontology and its variable argument already appears in the pattern to be specialized. The predicate symbol can already appear in the pattern, in that case, a different variable name has to be used; -ADDROLEATOMWITHFRESHVAR or WITHWITHALLVARSBOUND, which add an atom whose predicate symbol is a role name in the ontology and at least one of its variable arguments is shared with one or more atoms in the pattern while the other could be a shared or a new variable. The predicate symbol could be already existing in the pattern.

The operators are applied so that, at each step of the specialization process, rules in agreement with the language bias (see Sect. 2) are obtained. We refer the reader to [START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF] for a detailed description of these operators.

The generalization operator simply removes the last atom from a pattern. Given the way patterns are created and specialized, this guarantees that the resulting pattern respects the language bias.

Fitness and Selection

A pattern is evaluated by first constructing a rule from it, using the first atom of the pattern as its head and the remaining atoms as its body. Fitness is defined as the head coverage of the rule: f (r) = headCoverage(r).

Selection is performed as in the breeder algorithm [START_REF] Mühlenbein | The science of breeding and its application to the breeder genetic algorithm (BGA)[END_REF] by truncation with parameter τ : the n patterns in the population are sorted by decreasing fitness and the τ n fittest individuals are selected for reproduction. The remaining individuals are replaced by the offspring of the selected individuals.

Consistency Check

Inconsistent rules, i.e., rules that are unsatisfiable when considered jointly with the ontology, are of no use for knowledge base enrichment and have thus to be discarded. 4Algorithm 5 Evolutionary algorithm for the discovery of multi-relational ARs from a populated ontological KB.

Input: K: ontological KB; θ f : frequency threshold; θ hc : head coverage threshold; Output: pop: set of frequent patterns discovered from K 1: Compute A f , a list of frequent atoms in K. 2: Initialize population pop of size n. 3: g ← 0 4: while g < MAX GENERATIONS do 5: for i = τ n , τ n + 2, . . . , n -2 do 9:

for i = 0, 1, . . . ,
pop[i] ← pop[i mod τ n ]
10:

pop[i + 1] ← pop[i + 1 mod τ n ]
11:

with probability pcross do RECOMBINE(pop[i], pop[i + 1])

12:

with probability pmut do MUTATE(pop[i])

13:

with probability pmut do MUTATE(pop[i + 1]) 14: g ← g + 1 15: Remove redundant and inconsistent rules from the final population pop 16: return pop Notice that this case should never occur if the ontological KB is consistent and noisefree. Nevertheless, since the proposed method can be also applied to noisy ontologies, it may happen that an unsatisfiable rule/pattern (when considered jointly with the ontology) is extracted, particularly if low frequency and Head Coverage thresholds (see Sect. 2.2 for details about the adopted metrics and related discussions) are considered.

Since checking rules for consistency may be very computationally expensive, we have decided not to check patterns for consistency during evolution. Instead, we defer this check and we apply it to the final population.

The satisfiability check is performed by calling an off-the-shelf OWL reasoner. Our current implementation is able to use two state-of-the-art OWL reasoners, namely Pellet [START_REF] Sirin | Pellet: A practical OWL-DL reasoner[END_REF] and Hermit [START_REF] Motik | Hypertableau reasoning for description logics[END_REF]. However, we have observed that both reasoners fail to give an answer within a reasonable time for some patterns. This happens relatively seldom and not necessarily with the same patterns for either reasoner; however, given the large number of pattern our algorithm generates, these cases have a high chance of occurring in every run. As a workaround, we have introduced a time-out, which is an additional parameter of the algorithm, after which the reasoner is interrupted. When this happens, we discard the problematic pattern, since we have observed that, in general, patterns that take too long to be checked are either inconsistent or uninteresting.

The overall flow of the EA may be summarized as in Alg. 5. The parameters of the algorithm are summarized in Table 1.

The rules corresponding to the patterns returned by the EA are straightforwardly obtained and coded in SWRL by considering, for each pattern, the first atom as the head of the rule and the remaining as the rule body.

Related Work

The exploitation of data mining methods for discovering hidden knowledge patterns is not new in the SW context. First proposals have been formalized in [START_REF] Lisi | AL-QuIn: An onto-relational learning system for semantic web mining[END_REF][START_REF] Józefowska | The role of semantics in mining frequent patterns from knowledge bases in description logics with rules[END_REF], where solutions for discovering frequent patterns in the form of, respectively, DATALOG clauses and conjunctive queries from hybrid sources of knowledge (i.e. a rule set and an ontology) have been presented. These methods are grounded on a notion of key, standing for the basic entity/attribute to be used for counting elements for building the frequent patterns. Unlike these methods, our solution focuses on an ontological KB and does not require any notion of key and as such it is able to discover any kind of frequently hidden knowledge patterns in the ontology. A method for learning ARs from RDF datasets, with the goal of inducing a schema ontology has been proposed in [START_REF] Völker | Statistical schema induction[END_REF], while a method for inducing new assertional knowledge from RDF datasets has been presented in [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF] and further optimized in [START_REF] Galárraga | Fast rule mining in ontological knowledge bases with AMIE+[END_REF]. Differently from our approach, these two methods do not take into account any background/ontological knowledge and do not exploit any reasoning capabilities. Furthermore, our solution allows to discover rules that can be directly added to the ontology, which is not the case for the existing methods.

As regards exploiting EAs in combinations with ILP, several started to appear in the literature at the beginning of the new millennium. An EA has been exploited as a wrapper around a population of ILP algorithms in [START_REF] Philip | Scaling up inductive logic programming: An evolutionary wrapper approach[END_REF]; alternatively, a hybrid approach combining an EA and ILP operators has been proposed in [START_REF] Divina | Evolutionary concept learning[END_REF][START_REF] Divina | Hybrid Genetic Relational Search for Inductive Learning[END_REF][START_REF] Divina | Genetic Relational Search for Inductive Concept Learning: A Memetic Algorithm for ILP[END_REF]. A similar idea is also followed by [START_REF] Tamaddoni | A genetic algorithms approach to ILP[END_REF][START_REF] Muggleton | QG/GA: a stochastic search for progol[END_REF], in which a genetic algorithm is used to evolve and recombine clauses generated by a stochastic bottom-up local search heuristic.

The rationale for using evolutionary algorithm as a meta-heuristic for ILP is to mitigate the combinatorial explosion generated by the inductive learning of rich representations, such as those used in description logics [START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF], while maintaining the quality of the results.

Experiments and Results

We tested our method on the same publicly available ontologies used in [START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF]: Financial, 5 describing the banking domain; Biological Pathways Exchange (BioPAX) Level 2 Ontology, 6 describing biological pathway data; and New Testament Names Ontology (NTN), 7 describing named things (people, places, and other classes) in the New Testament, as well as their attributes and relationships. Details on these ontologies are reported in Table 2. The first goal of our experiments consisted in assessing the ability of the discovered rules to predict new assertional knowledge for a considered ontological KB. For that purpose, different samples of each ontology have been built for learning multirelational ARs (as presented in Sect. 3) while the full ontology versions have been used as a test set. Specifically, for each ontology three samples have been built by randomly removing, respectively, 20%, 30%, and 40% of the concept assertions, according to a stratified sampling procedure.

We ran the evolutionary algorithm by repeating for each run the sampling procedure. We performed 10 runs for each ontology and parameter setting, using the following parameters setting: n = 1000, MAX GENERATIONS = 1000, MAX RULE LENGTH = 10, p cross = 0.6, p mut = 0.4, θ mut = 0.2, τ = 1 5 , θ f = 1, θ hc = 0.01, θ ic = 0.001. As for the reasoner time-out (T/O), after some preliminary tests, we concluded that 10 seconds were enough to reduce the number of discarded patterns to a minimum; nevertheless, in the experiments we have also considered time-outs of 20 and 30 seconds to be on the safe side. As a results, three sets of 10 runs were performed for each ontology, one for each combination of sample and time-out, and the final population of each run were filtered using three time-outs, yielding a total of nine sets of 10 results.

As in [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF], we applied the discovered rules to the full ontology versions and collected all predictions, that is the head atoms of the instantiated rules. All predictions already contained in the reduced ontology versions were discarded while the remaining predicted facts were considered. A prediction is assessed as correct if it is contained/entailed by the full ontology version and as incorrect if it is inconsistent with the full ontology version. Results (see Table 3) have been averaged over the different runs for each parameter setting and have been measured in terms of: precision (see Def. 10), match rate, commission error rate, and induction rate (see Sect. 2.2).

These results fully confirm the capability of the proposed approach to discover accurate rules (precision = 1 on all samples of all ontologies considered) and, which is even more relevant, to come up with rules that induce previously unknown facts (induction rate > 0), with a very large absolute number of predictions by the standards of alternative state-of-the art approaches.

It is thus interesting to compare the performance of the proposed evolutionary method to those of the two state-of-the-art level-wise generate-and-test algorithms which are closest to it in purpose, namely the multi-relational association rule discovery (RARD) method proposed by d'Amato et al. [START_REF] Amato | Ontology enrichment by discovering multi-relational association rules from ontological knowledge bases[END_REF] and AMIE [START_REF] Galárraga | AMIE: Association rule mining under incomplete evidence in ontological knowledge bases[END_REF]. The comparison is performed by considering the top m rules wrt. their match rate, with m equal to the number of rules discovered by AMIE, when few rules were discovered, or to 10 for the other cases. Averaged results are reported in Table 4, further corroborating the claim that the proposed

Conclusions

We presented an evolutionary method for discovering multi-relational ARs, coded in SWRL, from ontological KBs, to be used primarily for enriching assertional knowledge. The proposed approach has been experimentally evaluated through its application to publicly available ontologies and compared to the two most relevant state-of-the-art algorithms having the same goal. For the future, we intend to focus on two main aspects: 1) scalability, by considering experimenting our method on datasets from the Linked Data Cloud; 2) reducing the search space for discovering ARs by further exploiting the expressive power of the representation language by considering the presence of hierarchy of roles.

1: L ← p ∪ r 2 :

 2 length p ∼ U (2, MAX RULE LENGTH) 3: length r ∼ U (2, MAX RULE LENGTH) 4: p ← 5: while p .SIZE() < length p do 6: pick an atom a ∈ L at random 7:

2 then 3 :

 23 pick a concept name C ∈ N freq C at random 4: r ← ADDCONCEPTATOM(r, C) 5: else 6: pick a role name R ∈ N freq R

Table 1 .

 1 Parameters of the evolutionary algorithm.

	Parameter	Description
	n	Population size
	MAX GENERATIONS Maximum number of generations
	MAX RULE LENGTH Maximum pattern length
	pcross	Crossover rate
	pmut	Mutation rate
	θmut	Head coverage threshold for mutation
	τ	Truncation proportion
	T/O	Reasoner time-out

Table 2 .

 2 Key facts about the ontological KBs used.

	Ontology # Concepts # Roles # Indiv. # Declared # Decl.+Derived
					Assertions	Assertions
	Financial	59	16 1000	3359	3814
	BioPAX	40	33	323	904	1671
	NTMerged	47	27	695	4161	6863

Table 3 .

 3 Average (± standard deviation) performance metrics on each ontology. algorithm can substantially boost the performance of multi-relational AR discovery. The large number of predictions made, on average, by the rules discovered by the evolutionary algorithm, depends on our language bias, which allows open rules (such that V (B) \ V (H) = ∅): open rules may generate substantially larger number of predictions than closed rules.

	Ontology Sample T/O	Match Comm. Rate Rate	Ind. Precision Rate	Number of # Predictions
			10s 0.983 ± 0.017	0 0.017 ± 0.17	1.0	32,607 ± 39,099
		20%	20s 0.983 ± 0.017	0 0.017 ± 0.17	1.0	32,607 ± 39,099
			30s 0.983 ± 0.017	0 0.017 ± 0.17	1.0	32,607 ± 39,099
			10s 0.970 ± 0.034	0 0.030 ± 0.034	1.0	64,875 ± 60,514
	Financial	30%	20s 0.970 ± 0.034	0 0.030 ± 0.034	1.0	64,875 ± 60,514
			30s 0.970 ± 0.034	0 0.030 ± 0.034	1.0	64,875 ± 60,514
			10s 0.933 ± 0.105	0 0.067 ± 0.105	1.0	47,264 ± 49,700
		40%	20s 0.933 ± 0.105	0 0.067 ± 0.105	1.0	47,264 ± 49,700
			30s 0.933 ± 0.105	0 0.067 ± 0.105	1.0	47,264 ± 49,700
			10s 0.808 ± 0.087	0 0.192 ± 0.087	1.0	21,065 ± 8,914
		20%	20s 0.807 ± 0.085	0 0.193 ± 0.085	1.0	22,397 ± 8,737
			30s 0.807 ± 0.085	0 0.193 ± 0.085	1.0	22,397 ± 8,737
			10s 0.877 ± 0.056	0 0.123 ± 0.056	1.0	19,697 ± 8,846
	BioPAX	30%	20s 0.877 ± 0.056	0 0.123 ± 0.056	1.0	19,697 ± 8,847
			30s 0.877 ± 0.056	0 0.123 ± 0.056	1.0	19,697 ± 8,847
			10s 0.877 ± 0.056	0 0.113 ± 0.056	1.0	19,621 ± 12,811
		40%	20s 0.877 ± 0.056	0 0.113 ± 0.056	1.0	19,621 ± 12,811
			30s 0.877 ± 0.056	0 0.113 ± 0.056	1.0	19,621 ± 12,811
			10s 0.578 ± 0.118	0 0.422 ± 0.118	1.0 3,324,264 ± 891,161
		20%	20s 0.572 ± 0.119	0 0.428 ± 0.119	1.0 3,702,706 ± 826,273
			30s 0.571 ± 0.119	0 0.429 ± 0.119	1.0 3,748,387 ± 827,350
			10s 0.707 ± 0.080	0 0.293 ± 0.080	1.0 3,489,818 ± 1,089,094
	NTMerged	30%	20s 0.705 ± 0.081	0 0.295 ± 0.081	1.0 3,781,877 ± 1,415,805
			30s 0.705 ± 0.081	0 0.295 ± 0.081	1.0 3,790,930 ± 1,408,588
			10s 0.665 ± 0.131	0 0.335 ± 0.131	1.0 3,564,421 ± 1,290,532
		40%	20s 0.664 ± 0.131	0 0.336 ± 0.131	1.0 3,643,770 ± 1,320,093
			30s 0.662 ± 0.131	0 0.338 ± 0.131	1.0 3,708,683 ± 1,363,246

evolutionary

Table 4 .

 4 Comparison of EA vs. RARD and AMIE w.r.t. the number of rules discovered.

				# Rules			Top
	Ontology Samp. T/O	EA	RARD AMIE m	# Predictions EA RARD AMIE
			10s 94.1 ± 33.7				14,442 ± 17,280
		20%	20s 94.1 ± 33.7	177	2	2 14,442 ± 17,280	29	208
			30s 94.1 ± 33.7				14,442 ± 17,280
			10s	86 ± 32				29,890 ± 29,576
	Financial	30%	20s	86 ± 32	181	2	2 29,890 ± 29,576	57	197
			30s	86 ± 32				29,890 ± 29,576
			10s	78 ± 50				18,958 ± 21,954
		40%	20s	78 ± 50	180	2	2 18,958 ± 21,954	85	184
			30s	78 ± 50				18,958 ± 21,954
			10s 144.1 ± 46.2				1,902.3 ± 755.7
		20%	20s 144.4 ± 46.7	298	8	8 2,045.6 ± 740.9	25	2
			30s 144.4 ± 46.7				2,045.6 ± 740.9
			10s 188.2 ± 25.5				1,653.1 ± 779.1
	BioPax	30%	20s 188.2 ± 25.5	283	8	8 1,653.1 ± 779.1	34	2
			30s 188.2 ± 25.5				1,653.1 ± 779.1
			10s 159.3 ± 37.7				1,704.4 ± 1,437
		40%	20s 159.3 ± 37.7	272	0	8 1,704.4 ± 1,437	50	0
			30s 159.3 ± 37.7				1,704.4 ± 1,437
			10s 1,035.4 ± 588.7				85,457 ± 25,754
		20%	20s 1,044.4 ± 592.8 243 1,129 10 97,622 ± 24,878	620 420
			30s 1,045.9 ± 592.6				98,470 ± 25,261
			10s 942.4 ± 217.1				103,962 ± 32,449
	NTMerged	30%	20s 945.6 ± 218	225 1,022 10 114,940 ± 41,960 623 281
			30s 946.1 ± 218.4				11,940 ± 41,960
			10s 893.7 ± 473.5				101,102 ± 38,777
		40%	20s 895.6 ± 473.9 239 1,063 10 102,569 ± 38,828 625 332
			30s 897 ± 473.2				103,100.4 ± 38,903

By ontological knowledge base, we refer to a populated ontology, namely an ontology where both the schema and instance level are specified. The expression will be interchangeably used with the term ontology.

The results is a KB with an enriched expressive power. More complex relationships than subsumption can be expressed. For details see[START_REF] Horrocks | A proposal for an OWL rules language[END_REF].

[START_REF] Berners-Lee | The semantic web[END_REF] When added to an ontology, DL-safe rules are decidable and generate sound results but not necessarily complete.

As remarked in[START_REF] Józefowska | The role of semantics in mining frequent patterns from knowledge bases in description logics with rules[END_REF], the satisfiability check is useful only if disjointness axioms occur in the ontology. This check can be omitted (thus saving computational cost) if no disjointness axioms occur.

http://www.cs.put.poznan.pl/alawrynowicz/financial.owl.

http://www.biopax.org/release/biopax-level2.owl.

http://www.semanticbible.com/ntn/ntn-view.html.


Vadim Girardeau

Carolina Goloni

Olivier Jacquin

Olivier Hugon

Mehdi Inglebert

Eric Lacot
email: eric.lacot@univ-grenoble-alpes.fr

Non-linear laser dynamics induced by frequency shifted optical feedback: Application to vibration measurements

Nonlinear laser dynamics induced by frequency shifted optical feedback: application to vibration measurements

INTRODUCTION

Laser properties (power, polarization, coherence, dynamical behavior …) can be significantly affected and modified by optical feedback [START_REF] Lang | External optical feedback effects on semiconductor injection laser properties[END_REF][START_REF] Erneux | Non-linear dynamics of an injected quantum cascade laser[END_REF] which allows for the realization of non-conventional sensors. One potential application is Laser Feedback Interferometry (LFI), where the steady-state intensity of a laser is modified by coherent optical feedback from an external surface. With this phase sensitive technique the signal depends on the reflectivity, distance and motion of the target [START_REF] Taimre | Laser feedback interferometry: a tutorial on the self-mixing effect for coherent sensing[END_REF]. However, when the amount of re-injected light is very small, the interference contrast occurring inside the laser cavity is drastically reduced. To overcome this problem, one solution is to use the dynamical properties of the laser which can be several orders of magnitude more sensitive to optical feedback than the laser steadystate properties. Since the pioneering work of K. Otsuka on self-mixing modulation effect in a class-B laser [START_REF] Otsuka | Effects of external perturbations on LiNdP 4 0 12 Lasers[END_REF], the dynamical sensitivity of lasers to frequency shifted optical feedback has been used in metrology [START_REF] Otsuka | Self-Mixing Thin-Slice Solids-State Laser Metrology[END_REF], for example in self mixing Laser Doppler Velocimetry (LDV) [START_REF] Okamoto | Ultrahighly sensitive laser-Doppler velocity meter with a diode-pumped Nd:YVO4 microchip laser[END_REF][START_REF] Kawai | Ultrahigh-Sensitivity Self-Mixing Laser Doppler Velocimetry with Laser-Diode-Pumped Microchip LiNdP 4 O 12 Lasers[END_REF][START_REF] Suddo | Determination of velocity of self-mobile phytoplankton using a self thin-slice solidstate laser[END_REF] and in Laser Optical Feedback Imaging (LOFI) [START_REF] Lacot | Laser optical feedback tomography[END_REF][START_REF] Hugon | Coherent microscopy by laser optical feedback imaging (LOFI) technique[END_REF][START_REF] Glastre | Demonstration of a plenoptic microscope based on laser optical feedback imaging[END_REF]. Compared to conventional optical heterodyne detection, frequency shifted optical feedback allows for higher (several order of magnitude) intensity modulation contrast [START_REF] Lacot | Coherent laser detection by frequency-shifted optical feedback[END_REF][START_REF] Lacot | Comparative study of autodyne and heterodyne laser interferometry for imaging[END_REF][START_REF] Jacquin | Experimental comparison of autodyne and heterodyne laser interferometry using an Nd:YVO4 microchip laser[END_REF].

For weak optical feedback, the laser dynamics is linear and the maximum of the modulation is reached when the shift frequency is resonant with the laser relaxation oscillation frequency. In this condition, an optical feedback level as low as -170 dB (i.e. 10 17 times weaker than the laser intra-cavity power) has been detected [START_REF] Okamoto | Ultrahighly sensitive laser-Doppler velocity meter with a diode-pumped Nd:YVO4 microchip laser[END_REF]. On the opposite, phase measurements (such as profilometry or vibrometry) with low noise necessitate to increase the amount of optical feedback reinjected inside the laser cavity [START_REF] Otsuka | Real-time nanometer vibration measurement with self-mixing microchip solid-state laser[END_REF][START_REF] Lacot | Phase-sensitive laser detection by frequencyshifted optical feedback[END_REF][START_REF] Muzet | Experimental comparison of shearography and laser optical feedback imaging for crack detection in concrete structures[END_REF]. For strong optical feedbacks, the laser dynamics becomes non-linear, making it difficult to obtain quantitative measurements. The main objective is to demonstrate the possibility to accurately measure very small vibration amplitudes (i.e. sub-wavelength), from the non-linear dynamics of a laser submitted to a strong frequencyshifted optical feedback. Experimentally, the use of a LOFI set up is motivated by the following reasons: i) the LOFI interferometer is always self-aligned because the laser simultaneously fulfils the functions of the source (i.e. photons-emitter) and of the photo-detector (i.e. photons-receptor); ii) the LOFI detection is shot noise limited (even with a low power laser) in a frequency range located near the relaxation oscillation frequency of the laser [START_REF] Lacot | Coherent laser detection by frequency-shifted optical feedback[END_REF][START_REF] Lacot | Comparative study of autodyne and heterodyne laser interferometry for imaging[END_REF][START_REF] Jacquin | Experimental comparison of autodyne and heterodyne laser interferometry using an Nd:YVO4 microchip laser[END_REF]. This article is organized as follows. In section 2, we firstly recall the equations governing the dynamics of a laser with a frequency-shifted optical reinjection back-scattered from a vibrating target. Then the signal processing to extract vibration measurements from the laser dynamics is explained. The end of this section is devoted to numerical simulations where we show typical examples of numerical vibration signals (harmonic and transient) extracted from the laser dynamic in both the linear and nonlinear regimes. These numerical simulations show that the gain of the laser dynamics needs to be compensated (and therefore to be known) to extract accurate (i.e. without bias) vibration amplitude. In section 3, a bifurcation analysis is made to obtain an asymptotic solution for the gain of the laser dynamics. Our calculations show that the carrier and the vibration signal are coupled through the non-linear laser dynamics and we demonstrate that the nonlinear amplification of the vibration spectrum is related to the amplitude of the carrier signal. Therefore, our calculation confirms that to obtain quantitative vibration measurements, the non-linear gain must be taken into account in the signal processing. Section 4 is devoted to the measurement of experimental vibrations with a LOFI (Laser Optical Feedback Imaging) setup. The theoretical predictions, confirmed by numerical simulations, are in good agreement with the experimental data. The final section is devoted to the general discussion of these results and to their prospective applications. ), the dynamical behavior of a laser with a frequency shifted ( e F ) optical feedback can be described by the following set of differential equations [START_REF] Lacot | Coherent laser detection by frequency-shifted optical feedback[END_REF]:

LASER WITH FREQUENCY-SHIFTED OPTICAL FEEDBACK A. Basic equations for vibrometry

( ) ( ) 2 cos c c e e e I dI BIN I R I t t F t dt γ γ   = - + Ω +Φ +   , (1a)
[ ]

1 0 dN N N BNI dt γ = -- , ( 1 b )
( ) 0

I F t = , ( 1 c )
( ) ( ) ( )

2 I I c F t F t I τ γ δ τ - = , ( 1d
)
where I and N are respectively the laser intensity (photon unit) and the population inversion (atom unit). 1 γ is the decay rate of the population inversion, c γ is the laser cavity decay rate, 1 0 N γ is the pumping rate and B is related to the Einstein coefficient (i.e. the laser transition cross section). Regarding the noise, the laser quantum fluctuations are described by the Langevin noise function ( ) I F t , with a zero mean value and a white noise type correlation function [START_REF] Peterman | Laser diode modulation and noise[END_REF][START_REF] Kolobov | Role of pumping statistics and dynamics of atomic polarization in quantum fluctuations of laser sources[END_REF].

In Eqs. (1), the cosine function expresses the coherent interaction (i.e. the beating at the angular frequency: In the absence of optical feedback (

0 e R = )
, the laser steady-state is given by the mean values of the population inversion and of the laser intensity:

S c N B γ = , ( 2 a )
[ ]

1 S s a t I I η = -, ( 2 b )
where

0 S N N η =
is the normalized pumping parameter and ( )

1 1 R c γ γ η Ω = -
and a damping rate

1 2 R γ η Γ = .
Experimentally, this transient dynamics is constantly excited by the laser quantum noise described by the Langevin force ( )

I F t .
In the presence of optical feedback (

0 e R ≠ )
, the laser intrinsic dynamics can be modified and the extent of changes in the laser dynamical properties depends on the feedback conditions ( , e e R Ω ). In this article, we call "strong feedback", the situation where the modulation frequency is nearly resonant ( e R Ω ≈ Ω ) and where the amount of optical feedback is high enough to induce non-linear dynamical behaviors in the laser output power modulation. The strong feedback situation is also characterized by a strong modification of the RF signal power spectrum of the laser [START_REF] Tan | Power spectral characteristic of a microchip Nd:YAG laser subjected to frequency-shifted optical feedback[END_REF][START_REF] Tan | Response of microchip solid state laser to external frequency-shifted feedback and its applications[END_REF]. In particular, the relaxation oscillations frequency can decrease, jointly with a modification of the shape of the RF noise power spectrum of the laser [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF]. In contrast, the "weak feedback" regime corresponds to the situation where the modulation frequency is far away from the resonance (

0 e R
Ω -Ω >> ) and where the amount of optical feedback ( e R ) is small enough to induce only linear dynamical behavior in the laser output power modulation. In this situation, the RF noise power spectrum of the laser, with and without optical feedback, is unchanged. Here, let us mentioned that the RF noise power spectrum is an image of the gain (i.e. of the modulation transfer function) of the laser dynamics [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF]. As explained in the following section, the knowledge of this gain is of paramount importance to extract accurate (i.e. without bias) vibration measurements from the laser dynamics of a reinjected laser.

B. Signal processing for vibrometry

The aim of the present paper is to explain how it is possible to extract the time dependence of the phase shift of the optical feedback, namely

( ) e t Φ (and consequently ( ) e d t ) from the laser dynamics, in both the weak and the strong feedback regimes. For a laser with frequency shifted optical feedback, the output power modulation of the laser is given by the convolution product (symbol ⊗ ) between the input modulation (i.e. the coherent beating at the carrier frequency) and the impulse response of the laser dynamics which is the is inverse of the Fourier transform (FT -1 ) of the gain of the laser dynamics ( )

Δ = -∝ ×     Ω Ω ⊗ Ω +Φ +         . (3)
In Eq. ( 3), one can notice that the gain of the laser dynamics ( )

, , Principally in the strong feedback regime.

To extract the temporal evolution of the phase induced by the vibration (

( )

e t Φ
), the different steps of the signal processing are given by the set of Eqs. (4a-f):

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) (
)

e e e e e FT I t R G R FT i t R G R FT i t δ δ Δ ∝         Ω Ω             × +Φ ⊗ Ω-Ω              Ω Ω     +         × -Φ ⊗ Ω+Ω             , (4a) ( ) ( ) ( ) ( ) ( ) ,
R G R FT i t δ ΔΩ Δ ∝       Ω Ω         × +Φ ⊗ Ω-Ω         , (4b) ( ) ( ) ( ) ( ) ( ) { }
R R FT i t δ ΔΩ Δ     ∝ Ω Ω     + Φ ⊗ Ω -Ω     , (4c) ( ) ( ) ( ) ( ) ( )
G R R i t i t ΔΩ -  Δ     ∝   Ω Ω     + Φ + Ω , (4d) ( ) ( ) ( ) ( ) ( ) {
    Δ       -Ω ∝   Ω Ω         + Φ , (4e) ( ) ( ) ( ) (
        Δ       -Ω = Φ   Ω Ω             . (4f)
Fisrtly [Eq. (4a)], the Fourier Transform of the time evolution of the laser output power is calculated. Then [Eq. (4b)], the Fourier spectrum is filtered using a bandpass filter with a central frequency e Ω and a bandwidth e ΔΩ . The bandwidth is adapted to the frequency range of the vibration spectrum. Thirdly [Eq. (4c)], the distortion of the vibration spectrum induced by the laser dynamics (i.e. the amplification gain) is compensated. Then, coming back to the temporal space [Eq. (4d)], the signal is demodulated [Eq. (4e)] and finally [Eq. (4f)], the temporal evolution of the phase is extracted from the complex signal. In this signal processing, it can be noticed that the multiplication, by any real constant number, of the input signal (i.e. the laser output power modulation) , has no impact on the extraction of output signal, which is a phase signal. So, the gain can be multiplied by any real constant. Therefore, for the experimental measurement of vibrations, the absolute knowledge of the amplitude of the gain is not necessary (i.e. only the complex frequency shape is important). This is due to the fact that, for vibration measurements, only the relative ratio between the amplitudes of the spectral components is important.

C. Compensation of the gain of the laser dynamics

To demonstrate how different kinds of vibrations can be extracted from the laser dynamics, we have numerically solved the set of differential equations given by (1).

Numerical harmonics vibrations

Fig. 1 shows examples of the calculations of a harmonic vibration:

( ) ( ) sin e a a t t Φ =Φ Ω , ( 5 )
with an acoustic angular frequency Ω ± Ω ). When the feedback is weak (

9 10 e R - =
), one can see in Fig. 1a, that the complex gain adjusted on the noise power spectrum exhibits only one resonance (i.e. is linear). On the other hand, when the feedback is strong (

7 10 e R - =
), the gain, which becomes non-linear, exhibits two resonances symmetrically located on both sides of the carrier frequency (Fig. 1b) [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF]. As already mentioned the RF noise power spectrum is an image of the gain (i.e. of the modulation transfer function) of the laser dynamics [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF] and therefore helps to obtain it as it is explained in the theoretical section (i.e. section III).

In both cases, the middle row (Figs. 1c and1d) show a comparison between the exact vibration motion and the vibration obtained after the signal processing, but without the gain compensation (i.e. without the signal processing step given by Eq. (4c)). One can see that neither the amplitude nor the phase of the detected vibration is good. In the weak feedback case, the carrier signal, which is near the resonance, is amplified much more than the vibration sidebands and thus the vibration amplitude is lower than the real one. In the strong feedback case the opposite situation occurs. The vibration sidebands which are near the resonances are much more amplified than the carrier signal, and therefore the detected vibration amplitude is larger than the real one. In both cases, one can also notice a π phase-shift induced by the resonance.

Finally, the lower traces (Figs 1e and1f) show that the accurate vibration is recovered in both cases (weak or strong feedback) if the complex gain compensation (i.e. if the division by ( )

, , e e G R Ω Ω ) is
made in the signal processing. So, Fig. 1 clearly shows that the gain compensation (linear or non-linear) is necessary to obtain accurate (i.e. without bias) quantitative vibration measurements (amplitude and phase) from the reinjected laser dynamics.

The comparison of Figs. 1e and 1f also shows that the vibration amplitude is better recovered when the amount of optical feedback increases. This effect is principally due to the increase of all the vibration components relatively to the noise baseline. So, even if for a strong optical feedback, the laser dynamics becomes non-linear (i.e. much more complicated), the compensation of the non-linear amplification allows to restore vibration measurement with an improved accuracy. Indeed, the standard deviation of the difference between the exact vibration and the extracted vibration is equal to 0.02 rad ( ) ).

2
The left column (a, c, e) corresponds to a weak optical feedback (

1.2 η = , 5 1 1 10 c γ γ - = × , 4 2.251 10 R c F γ - = × .

Numerical transient vibrations

To verify that our signal processing can be applied to any kinds of vibrations, we have numerically simulated transient vibrations:

( )

2 1 a e a t t τ τ Φ Φ =   - +     , (6)
with a half time width Firstly, one can notice on the left column, that the non-linear gain used for the gain compensation in the signal processing, is always the same and is also identical to the one used in Fig. 1 (right column) for the calculation of harmonic vibration. This is due to the fact that the feedback conditions are the same and consequently the gain of the laser dynamics

( )

, ,

e e G R Ω
Ω is the same for all these vibration calculations. Secondly, the right column shows that impulse vibration with an accurate amplitude and an accurate time delay can be extracted from the non-linear laser dynamics (Figs. 2b , 2d, and2f). Thirdly, the impulse shape is recovered regardless of the vibration amplitude, even when the vibration amplitude is large (see Figs. 2a andb) and when the RF power spectrum is strongly perturbed by nonlinear dynamical effects of higher order. Finally, on Fig. 2f, an amplitude of

1 0.2 1000 a d n m λ = ± ≈
is detected, showing the high potential of this measurement method for the detection of small vibration amplitudes at relatively high frequencies. It must be noted that the SNR of the order of 5 has been obtained with a filtering process (see Eq. 4b) adapted to the width of the vibration spectrum (

1.5 e R a ΔΩ = Ω ≈ ΔΩ ).
For a narrower bandwidth ( e a ΔΩ < ΔΩ ) the noise (i.e. the fluctuation at the base of the impulse vibration) is lower, but the vibration spectrum is truncated. Consequently, the shape (amplitude and width) of the reconstructed vibration pulse is not the good one.

Conversely if the bandwidth is wider ( e a ΔΩ > ΔΩ ), the noise increases, without any significant improvement of the reconstructed pulse shape. Therefore, with the non-linear gain compensation, the detection of very small vibration amplitudes (

2 500 a π Φ =
) seems to be possible with a reinjected laser. In Fig. 3, the transient vibration is again a short impulse vibration with a wide spectral bandwidth (

1.8 a R ΔΩ = Ω
) and with a small vibration amplitude (

2 50 a π Φ =
), but now the calculations have been made for a strong feedback reflectivity (

Ω Ω =

).

The left column shows how the non-linear gain (adjusted on the noise power spectrum) is modified when the carrier frequency approaches the intrinsic laser relaxation frequency (i.e. when

1 e R
Ω Ω → ). As already mentioned, the modification of the non-linear gain is induced by the modification of the carrier amplitude [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF].

One can observe on the left column that the frequency distance between the two maxima (located symmetrically on both sides of the carrier frequency) decreases. Secondly, one can also observe that the amplitude of the maximum located on the right side of the carrier frequency increases in agreement with [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF].

The right column of Fig. 3 shows that regardless of the shape of the non-linear gain (i.e. of the frequency shift e Ω ) the impulse vibration is recovered with an accurate amplitude and an accurate time delay. Nevertheless, one can notice a small degradation of the signal to noise ratio (roughly by a factor 2) when

1.01

e R Ω = Ω . In Fig. 3f, the higher noise, which is visible at the base of the feet of the impulse vibration, can be attributed to the fact that the adjustment of the noise power spectrum by the non-linear gain is not always perfect and that the amount of noise initially present (i.e. before the gain compensation) inside the bandwidth filter increases when

1 e R
Ω Ω → (see Fig. 3e).

GAIN OF THE NONLINEAR LASER DYNAMICS

As explained in the previous section, accurate (i.e. without bias) vibration measurements are possible with frequency shifted optical feedback in laser, if the gain compensation is applied in the signal processing. So the gain of the laser dynamics needs to be known. The aim of the present section is to obtain an analytic expression of the complex gain ( )

, , e e G R Ω Ω , whatever the feedback condition (weak or strong) is and therefore whatever the laser dynamics (linear or nonlinear) is.

A. Asymptotic solution for the nonlinear gain

To analytically study the dynamical response of a laser subjected to frequency-shifted optical feedback ( 0 e R ≠ ), we have used the asymptotic equation given in [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF][START_REF] Schwartz | Subharmonic hysteresis and period doubling bifurcations for periodically driven laser[END_REF][START_REF] Witomski | Parametric amplification of frequency-shifted optical feedback[END_REF]:

[ ] ( ) 2 * 1 e x p 6 2 4 e e e dA A A i A i A i i ds δ ηε σ = - - - - + Φ , ( 7
)
where A is the complex amplitude of the small periodic oscillation and where For our microchip laser,

3 1 10 R ε γ - = Ω ≈
is a small quantity, which allows the use of the asymptotic analysis detailed in [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF][START_REF] Schwartz | Subharmonic hysteresis and period doubling bifurcations for periodically driven laser[END_REF][START_REF] Witomski | Parametric amplification of frequency-shifted optical feedback[END_REF]. In Eq. ( 7), the optical feedback is described by To obtain the gain (i.e. the modulation transfer function) of the laser dynamic, we now investigate the solutions of Eq. ( 7), in the particular situation of a vibrating target with a harmonic oscillation:

( ) Φ an additional phase shift corresponding to the mean distance between the laser and the vibrating target. Without loss of generality, we assume:

( ) 0 sin e a a a s s σ φ Φ =Φ +Φ + , (8)
0 2 m π Φ =
, where m is an integer.

In the case of sub-wavelength vibration amplitudes (i.e.

2 a π Φ << ),
Eq. ( 7) can be rewritten:

[ ] ( ) ( ) ( ) ( ) ( ) 2 * 0 1 1 1 2 6 exp 4 exp e a e a a a a a a dA A A i A A i ds J i J i s J i s ηε σ δ σ φ σ φ - = - - - -   Φ     + + Φ +       + Φ - -         , (9)
where ( )

n a
J Φ is the Bessel function of the first kind and of order n with: ( )

0 1 a J Φ ≈ , ( ) 1 2 a a J Φ ≈ Φ and ( ) ( ) 1 1 a a J J -Φ = -Φ .
In the present study, the key term is the cubic one ( ) The solution of Eq. ( 9) can be written as:

( ) ( ) ( ) ( ) exp exp e R a a a a a a A s C T s R i s L i s σ φ σ φ = + + + + - +         , (10)
where e C is the stationary modulation amplitude at the carrier frequency, ( ) R T s is the transient dynamics of random excitations (due to quantum noise) around the stationary solution, while a R and a L are respectively the amplitudes of the right and left sidebands of the acoustic vibration. One can notice that in Eq. ( 10), the carrier signal ( e C ) has already be studied in [23] and more particularly the hysteresis phenomenon induced by the periodic modulation, while the noise power spectrum ( ) R T and more particularly the shift of the laser relaxation frequency has already been studied in [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF]. The aim of the present paper is focused on the study the complex vibration sidebands ( a R and a L ) and how they are amplified by the laser dynamics, in order to be able to restore accurate vibration measurements.

In the forthcoming study, we assume that the carrier signal is much stronger than the laser quantum noise and the vibration sidebands (i.e.

( ) , ,

e R a a

C T s R L >>

). Keeping only the first order non-linear terms, Eq. [START_REF] Hugon | Coherent microscopy by laser optical feedback imaging (LOFI) technique[END_REF]

A A C C C C C T C C T C C R C C L i s C C L C C R i s σ φ σ φ ≈ + +   + + + +         + + - +       . ( 11
)
Inserting Eqs.( 10) and ( 11) into Eq. ( 9) gives the following equalities:

( ) ( ) 2
  = - + -+ -     , (12b) ( ) ( ) *
C C C C R i i i L i i J ηε σ σ δ     + + -+ +         = Φ , (12c) ( ) ( ) *
C R i L i i i i J ηε σ σ δ -     + - + -+         = Φ . ( 12d
)
Eqs. (12a-b) have been already studied in [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF][START_REF] Schwartz | Subharmonic hysteresis and period doubling bifurcations for periodically driven laser[END_REF]. Let us recall that the analytical resolution of Eq. (12a) shows that the power spectrum of the output power modulation at the carrier frequency (

C δ σ versus e σ ) exhibits hysteresis in the strong feedback situation and that the extent of the hysteresis zone increases with the amount of optical feedback e δ [22, 23, 25, 26]. Jointly, the study of the transient dynamics [Eq. (12b)] allows to determine the noise power spectrum of the laser submitted to frequency shifted optical feedback. Let us recall that the noise power spectrum is composed of two resonant curves with a resonant width ηε and with resonance frequencies symmetrically located on both sides of the carrier frequency [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF]:

( ) ( ) , , R e e e R e e σ δ σ σ δ δ σ ± = ± , (13a)
with the detuning:

( ) ( ) ( ) 2 2 2 2 , , , 1 3 6
=         -+ -         . ( 13b
)
Eq. ( 13) shows that the modification of the noise power spectrum is linked to the strength of the optical feedback ( e δ , e σ ) principally through its dependence on the non-linear modulation amplitude

C i J i i i i J i C C C i i i i i i σ δ σ δ σ δ σ δ δ ηε σ σ δ σ δ σ δ σ ηε ηε σ σ σ σ - =         Φ - + -+ - Φ                       + + -+ - + -+ -           , (14a) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) * 2 2 *
i i i i J i C C C i i i i i i σ δ σ δ σ δ σ δ δ ηε σ σ δ σ δ σ δ σ ηε ηε σ σ σ σ - =         Φ + + -+ - Φ                       - + -+ + + -+ -           . ( 14b
)
The aim of the following section is to explain why it is possible to extract an accurate (i.e. without a bias) value of a Φ (and, finally, of the vibration amplitude a d ) from the measurement of the two vibration sidebands ( a R and a L ) conjointly with the carrier modulation ( e C ).

Using the two vibration sidebands given by Eqs (14a-b), we define the nonlinear gain of the laser dynamics by the following equation:

( ) ( ) ( ) ( ) ( )
R if J R G L if J R σ σ δ σ σ σ σ δ σ σ σ δ σ σ σ - ≥ Φ = - < Φ .( 15
)
Like the noise power spectrum, this gain exhibits two resonance frequencies symmetrically located on both sides of the carrier frequency [Eqs (13a-b)]. This double resonance is due to the cross coupling between the vibration sidebands. The frequency distance and the amplitude ratio between the two maxima depend on the feedback conditions and are roughly given by [START_REF] Lacot | Non linear modification of the laser noise power spectrum induced by frequency-shifted optical feedback[END_REF]:

( ) ( ) 2 , 2 , 2 1 3 e e e R
e e e C δ σ δ δ σ σ C δ σ << , leading to the conventional LOFI linear gain, with only one resonance frequency ( R Ω ) [12-14]:

    ≈ -+     , ( 16a
) ( ) ( ) ( ) ( ) 2 , , , 6 2 ,
( ) ( ) ( ) ( ) ( ) 2 2 0 2 2 2 1 4 , , 1 2 4 2 e e e v e e L v C v c L v v R R G G G δ σ δ σ σ ηε σ γ ηγ → ==   -+     Ω =   Ω -Ω +     ≈ . ( 17
)
At this point, one can notice that the linear gain depends only on the intrinsic dynamical parameters of the laser ( 1 γ , c γ andη ), while the non-linear gain also depends on the feedback conditions ( e R and e Ω ).

In agreement with the results shown on Figs. 3a, 3c and 3e, Eqs. (16ab) allows explaining why the frequency distances between the two maxima decreases and why the amplitude of the maximum located on the right side of the carrier frequency increases, when

1 e e R σ = Ω Ω → .

C. Gain compensation for vibration measurement

Using Eqs. (12a), ( 14) and ( 15), one also obtains:

( ) ( ) ( ) 0 , , , e e e v e e e a e C G J R δ σ σ σ δ σ = = Φ . ( 18
)
Eqs. ( 15) and ( 18) clearly show that an accurate measurement of the vibration can be extracted from the non-linear laser dynamics ( e C , a R

, and a L ), if the non-linear amplification (via G ) is compensated: Fig. 6 shows, that quantitative vibration measurements can be experimentally extracted from the non-linear laser dynamics. The left column shows how the gain is modified when the amount of optical feedback increases (i.e. when e δ ↑ ). As already mentioned the modification of the non-linear gain is induced by the modification of the carrier amplitude ( ( )

( ) ( ) ( ) ( ) ( ) ( ) 1
C G σ δ σ σ σ δ σ δ σ σ σ σ δ σ Φ = = Φ = + , ( 19a
) ( ) ( ) ( ) ( ) ( ) ( ) 1 0 , , , , , , ,
, e e e C δ σ ). Starting with a linear gain (Fig. 6a), the gain becomes more and more non-linear when e δ ↑ (Figs. 6b- c). In agreement with Eq. (16a), one can observe for the non-linear gain (Figs 6c and6e) that the frequency distance between the two maxima (located symmetrically on both sides of the carrier frequency) increases. Secondly, in agreement with Eq. (16b), one can also observe that the amplitude of the maximum located on the right side of the carrier frequency increases. The left column allows to show that the modulation amplitude at the carrier frequency can saturate when the optical feedback becomes too strong. Indeed, Figs. 6c and 6e show a roughly constant amplitude of the carrier, although the amount of optical feedback is increased (

7.1 × ).
Despite this saturation, the right column of Fig. 6 shows that regardless of the shape of the gain (i.e. linear or non-linear) the transientharmonic vibration is recovered with an accurate time delay, characterized by the trigger trace superimposed. It should be noted that the presented time traces are an average on ten acquisitions. By looking more precisely near the rising and falling edges, one can also observe the transient time response of the PZT.

When the amount of optical feedback increases, one can observe a small increase of the mean value of the stationary vibration amplitude ( 21nm , 25 nm and 28 nm ) , while one can observe a small decrease of the vibration noise ( 6 nm , 3 nm and 1 nm ). The amplitude of the vibration noise has been determined during the starting time delay (i.e. before the starting of the harmonic vibrations). For a given detection bandwidth, this reduction of the vibration noise could be qualitatively explained by the increase of the carrier signal, coupled simultaneously with a modification of the laser noise power spectrum induced by the optical feedback, in the vibration frequency range.

For comparison, the vibration amplitude value measured at low frequency (150 Hz) with a lock-in amplifier gives 28 nm . So, taking into account the noise, the obtained results are in relative good agreement and one can notice the value is obtained for the strongest feedback ( 28 1 nm ±

) where the non-linear gain compensation is necessary.

CONCLUSIONS AND PERSPECTIVES

The main motivation of this study is the understanding of the nonlinear response of a LOFI sensor for quantitative phase measurements of small vibrations. The use of a LOFI set up is motivated by the following reasons: i) the LOFI interferometer is always self-aligned because the laser simultaneously fulfils the functions of the source (i.e. photons-emitter) and of the photo-detector (i.e. photons-receptor); ii) the LOFI detection is shot noise limited (even with a low power laser) in a frequency range located near the relaxation oscillation frequency of the laser. For small vibrations, the amplitude of the modulation at the carrier frequency is several order of magnitude higher than the amplitude of vibration sidebands at the acoustic frequency. Consequently, the optical feedback needs to be strong to be able to observe the small vibration sidebands and under these conditions the laser dynamics becomes non-linear. In this paper we have demonstrated (analytically, numerically and experimentally) how quantitative vibration measurements (harmonic or transient) can be extracted from the nonlinear dynamics of a laser submitted to frequency shifted optical feedback. By using a multiscale analysis, we have analytically studied the non-linear dynamics of a laser subjected to frequency shifted optical reinjection coming back from a vibrating target. More specifically, we have studied the non-linear dynamical coupling between the modulation at the carrier frequency and the modulation of the vibration sidebands at the acoustic frequency. We have shown how the non-linear amplification of the vibration spectrum by the laser dynamics is related to the strength of the optical feedback (and therefore of the amplitude of the carrier) and how it can be compensated to obtain accurate (i.e. without bias) vibration measurements in the nanometer range at relatively high frequency (of the order of several hundred of kHz). The theoretical predictions, confirmed by numerical simulations, are in good agreement with the experimental data for both transient and harmonic vibrations. Of course, the compensation effect is more important and therefore more necessary when the vibration spectrum is in the vicinity of the resonance frequency of the laser dynamics and therefore is strongly deformed. This nearly resonant situation corresponds to the conventional use of a LOFI setup to obtain a shot noise limited detection of the optical feedback.

Encouraged by these preliminary results, the sensitivity and performances of the non-linear LOFI device will be tested (in a near future) for the optical detection (with a shot-noise sensitivity) of acoustics waves induced by a photo-acoustic effect [START_REF] Li | Photoacoustic tomography and sensing in biomedicine[END_REF][START_REF] Carp | Optoacoustic imaging based on the interferometric measurement of surface displacement[END_REF].

For weak optical feedback ( 1 eR

 1 << ) and a short round trip time delay (

  lasing and the feedback electric field. The optical reinjection back-scattered from a vibrating target is characterized by the effective power reflectivity e R and the time dependent optical phase shift the laser and the vibrating target. c λ is the laser wavelength.

  by damped relaxation oscillations of the laser output power with a relaxation angular frequency

  Figs 1a-b show the signal is principally composed of one peak at the carrier frequency ( e Ω ) and two peaks for the vibration sidebands (

Fig. 1 :

 1 Fig. 1: Numerical simulation. Calculations of a harmonic vibration ( 3.5 a R Ω = Ω

  right one (b, d, f) corresponds to a strong optical feedback ( top row (a, b) shows the laser power spectrum where the resonance gain (bold line) is adjusted on the noise spectrum. The calculations are made with vertical lines). The middle row (c, d) shows a comparison between the exact vibration motion (solid line) and the vibration obtained after the signal processing (line of circles), but without the gain compensation. The bottom row (e, f) shows the same comparison when the gain compensation has been applied. Laser parameters:

.Fig. 2 :

 2 Fig. 2: Numerical simulation. Calculations of a transient vibration with a half time width ( 1.8 a R F

Fig. 3 :

 3 Fig. 3: Numerical simulation. Calculations of a transient vibration with a full time width 1.8 a R F

  and the time normalized by the relaxation frequency.

φ

  the modulation phase shift and 0

  of the modulation at the carrier frequency ( e Ω )with the vibration amplitudes at the acoustic sideband frequencies (

  resolution of Eqs (12c-d) is straightforward and gives the following solutions for the modulation amplitude of the two sidebands:

  In agreement with the results shown on Figs. 1a-b, Eq. (16b) explains that the amplitudes of the two maxima (located symmetrically on both sides of the carrier frequency) are of the same order of magnitude for strong optical feedback (i.e when

  Fig am nu do th R Ω Am fre Fig G sid Fig

. 8

 8 µW for the t s 6c-d), and 14.9 respond to a rel e R ) by a factor of 7.1 between the c vibration gene harmonic oscil

  }

	FT	-	1	FT G ΔΩ	e	, , e I t e R	exp	e it
				e R	exp	i	e	t

  )

	arg	FT	1 -	FT G ΔΩ	e	, , e I t e R	exp	e it	e	t

) within a time gate of 3.3 ms duration (i.e. 600 cycles) starting after a time delay of 2.0 ms . The total recording time is 6.6 ms with a sampling rate of


Michel Buffa
email: buffa@i3s.unice.fr

Maxime Demetrio
email: maxime.demetrio@gmail.com

Nouriel Azria
email: azria.nouriel@gmail.com

Guitar pedal board using WebAudio

The proposed demo is a guitar pedal board coded from scratch and inspired by the Guitar FX Chrome Application 1 . The demo is functional and proposes a graph based GUI for assembling effects such as: guitar amplifier emulation, Auto Wah, Delay, Distortion/Overdrive, Reverb, Chorus, etc. It includes a preset management system and saves incrementally, client side, any change in the parameters of the current preset. The latency is system and browser-dependent, but on a Mac Book Pro / Google Chrome the latency is as low as 14ms, making it playable in real time. The MVVC design is interesting for modularity and makes easy adding new effects. During the demo a guitar will be plugged into a computer using an external sound card, and the pedal board will process the sound in real-time. Lots of efforts have been put on the GUI and ease of use of the application, as well as on the core effect: the guitar amplifier simulation. The project is called "Guitar Processor" and is open source 2 .

Introduction and State of the Art

Some applications showed that Web Audio could be used for processing real time input. Chris Wilson's "Input Effects" demo was one of the first to propose real time sound processing effects written with Web Audio, and proposed implementations of famous effects such as Delay, Distortion, Wah, etc. This webapp did not allow to chain effects but proved that low latency processing could be achieved. However, getting close to the sound of a real guitar amplifier is a real challenge that Chris Wilson's example did not address.

Many papers have been written about vacuum-tube guitar amplifiers modeling [1, 6], and about the particularities of linear and non-linear distortion effects suited for guitar [2, 3, 4, 5]. Some works such as James J. Clark "Advanced programming techniques for modular synthesizers" book, are not focused on guitar but cover in deep the different approaches for achieving a distortion effect on a signal. Wikipedia gives a rather good description of the high-level design of a guitar amplifier: "Typically, guitar amplifiers have two amplifying circuit stages and in addition frequently have toneshaping electric circuits, which usually include at least bass and treble controls, which function similarly to the equivalent controls on a home hifi. More expensive amplifiers typically have more controls for other frequency ranges, such as one or two "midrange" controls and a "presence" control for very high frequencies. Some guitar amplifiers have a graphic equalizer, which uses vertical fader controls, which can control many frequency bands. The first amplifier stage is a preamplifier stage (there may be more than one), which amplifies the guitar signal to a level that can drive the power stage. The power amplifier or output stage produces a high current signal to drive a loudspeaker to produce sound that the guitarist and audience can hear."

When we started the project of writing a guitar pedal board, we began with the amplifier simulation, that is the "master effect". We discovered that many authors of native guitar amplifier plugins (VSTs, etc.), including famous makers such as IK Multimedia (creators of the Amplitube guitar amp plugin), or Lepou (author of many guitar amp simulators) chose to use the "analog simulation" approach, as stated by an engineer 3 : "The way we do it at IK Multimedia is a bit different. We do not rely on just schematics. Our engineers acquire every piece of gear they model, and take precise measurements of every component and every interaction. Then they custom build dynamic, non-linear algorithms to replicate every nuance of the behaviors. And finally, with the help of our co-branding partners such as Fender, [START_REF] Pakarinen | A review of digital techniques for modeling vacuum-tube guitar amplifiers[END_REF] Guitar FX Chrome Application : https://chrome.google.com/webstore/detail/guitarfx/nbjaofogegcpkeobcnpdkkpdioogeajj 2 Guitar Processor : https://bitbucket.org/Felours/ntdp-projet_stage_guitarfx [START_REF] Cheng-Hao | A Guitar Overdrive/Distortion Effect of Digital Signal Processing[END_REF] Forum "guitar amp modeling": http://www.guitarampmodeling.com/viewtopic.php?f=51&t=7006&start=125 Orange, Soldano, and Ampeg, to name a few, we fine tune everything by ear until our models sound identical to the original hardware at the same settings."

For this project we did not have time nor ambition to go to such a level of accuracy, and we used an approach based on Wave Shapers [START_REF] Macak | Real-time guitar tube amplifier simulation using an approximation of differential equations[END_REF] . This approach changes an audio signal by mapping an input signal to the output signal by applying a fixed or variable mathematical function, called the shaping function or transfer function. The Web Audio specification proposes such a function that has been copied and pasted in most of the examples published that use the WaveShaper node. The problem is that the sound obtained is not rich enough for a demanding guitarist. Further work is needed. As stated by Lepou, who wrote many guitar amp plugins: "Of course an amp shapes the incoming wave and can thus be seen as a waveshaper. However, the waveshaping function can not be applied to all the frequencies and intensities of the incoming signal…tubes cannot be treated as simple waveshapers. I think the important word is SIMPLE. In my opinion, a tube is a waveshaper but when put in a complete circuit the shaping function changes with frequency and intensity of the incoming signal. That's why a tube gain stage cannot be considered as a SIMPLE waveshaper ». In his book, James J. Clark describes the quadrafuzz circuit5 that addresses in a simple way the fact that we need to shape differently the input signal depending on frequencies: we can split the signal into separate paths using simple filters (a low pass filter, two band pass filters and a high pass filter). We reproduced this part of the preamp using a set of Web Audio BiquadFilter nodes. The dynamic part of the behavior of the vacuum tubes has been simulated using an analyzer node for guessing the intensity of the signal that in turn is used for adjusting the amount of distortion in the waveshaper nodes. The signal is pre-filtered using a high and a low pass filter in order to cut the frequency at the extremities of the spectrum (< 20Hz and > 10.000 Khz).

The four biquad filters that split the signal have been pre-adjusted to some frequency ranges ([lowpass 70-300Hz], [bandpass 300-1200Hz],

[bandpass 1200-3500Hz], and ([highpass 3500-7000Hz]), but can be tweaked, as well as the Q parameter of the filters, in order to "sculpt" the sound. Usually, such settings are not available to the end users of a real guitar amplifier, they are part of the DNA of the sound of some music brands such as Fender, Marshall, etc. (other parameters will play a role of course, speakers, for example).

The gain at the end of the preamp stage can be seen as the "master volume" of a real amplifier. In order to get clean sounds, our experience showed that we need to have 1) low values for the distortion parameter of the WaveShaper nodes, as well as 2) a very low master volume (< 0.1). In order to get a distorted sound, raise the master volume and lower the main volume. Like with a real amplifier.

The main volume is a simple gain node located right before the speaker simulator. We also inserted a reverb in our amplifier simulation, before the main volume (where the effect insertion loop is usually located, in real amplifiers). Reverb and speaker simulations are achieved using a convolver node and impulse files.

Figure 4 shows the GUI of the first prototype (with many parameters not suited for an end user, but usueful for understanding how amplifiers' tones are created).

Latency and Web Audio problems

The getUserMedia API enables to use any sound input [START_REF] Cohen | Real-time simulation of a guitar power amplifier[END_REF] . However by default, some browsers, such as Google Chrome implement an automatic gain adjustment algorithm 7 that is not suited for music applications. This option can be switched off using a constraint passed to the navigator.getUserMedia function (set the echoCancellation property to false). However, when we used this constraint, in the current implementations, it has not been possible to switch inputs (we reported the bug).

The second problem is latency. The intrinsic latency of a system (browser / OS / Sound Card) can be measured using Stephen Band's sound.io/latency [START_REF] Clark | Advanced programming techniques for modular synthesizers[END_REF] Web application, that measures the output-to-input latency (making a sound and listening for it), and results vary deeply from one configuration to another. Google Chrome/Mac OS x gives 9ms, where Firefox on the same computer gives 140ms. A "good latency" for playing real time an instrument is noticeable above 10ms. Add to this all the processing in our amp simulation and effects. So we did our best to avoid using the Web Audio nodes that involve additional latency. Unfortunately, this information is not specified, nor the nodes expose in a way or another their latency. Some APIs like JUCE propose some methods with its components 9 for "guessing the latency". In an interesting thread on stack overflow 10 , it appears that only specific Web Audio nodes could involve latency overheads. They are: the WaveShaper node when set in oversampling mode (avoid oversampling!), as it has to look ahead a few samples to make some mean computations, the Delay (of course!), and the convolver node with large impulses (use small impulses!).

In our guitar amp simulator, we followed these good practices and manage to get a very low latency processing time, nearly unnoticeable, on Mac OS/Google Chrome. We measured the latency (make a sound and listen to it) and we got 15ms of latency (30ms round trip).

Pedal board application

Finally, in parallel to the work conducted in order to play with the "core sound" of a guitar amplifier, fixing latency and sound quality problems, we developed a graph based GUI for designing a chain of effects. Most of the effects are based on examples found on the Web; small improvements have been done to suit our ears.

This application uses the jsPlumb JavaScript library for managing graphically the graph, for connecting nodes, etc. When a user clicks on an effect, a set of controllers (knobs, switches, preset menus) appears, enabling fine-tuning of the effects. The current state of the effects is saved incrementally in IndexedDB each time a user interacts with the application. In addition we developed a complete preset manager interface. The GUI has been inspired by the Guitar FX Chrome Application (which is not open source). The guitar amplifier presented previously comes this time with a simplified GUI with "classic" knobs and EQ, making it easier to use.

Figure 1 :

 1 Figure 1: a typical, single channel, guitar amplifier.

Figure 2 :

 2 Figure 2: transfer function on the left, and on the right, the source (sinusoidal) signal, and the transformed signal.

Figure 3 :

 3 Figure 3: pre-amplification stage, notice the filters at the beginning for cutting too low and too high frequencies. The signal is then split into 4 frequency ranges, then shaped. The WaveShaper distortion parameters are adjusted depending on the intensity of the signal (detected by an analyzer node not presented here).

Figure 4 :

 4 Figure 4: the first prototype of the guitar amp simulator

https://en.wikipedia.org/wiki/Waveshaper

The quadrafuzz is a famous distorsion VST plugin edited by Steinberg, based on some real circuiry from the 70's.