Aboudramane Guiro
email: aboudramane.guiro@univ-ouaga.bf

Abderrahman Iggidr
email: abderrahman.iggidr@inria.fr

Diène Ngom
email: dngom@univ-zig.sn

On the Stock Estimation for a Harvested Fish Population

Keywords: Discrete-time system, Stage structured population models, Estimation, Harvested Fish Population, Observers

.

Introduction

Overfishing has negatively affected the stock of renewable marine resources. Analyzing the catch data during the last decade, it can be noticed that catch fishing has considerably decreased in many countries and some species are threatened with extinction. The collapse of catch fishing and the extinction of species can be explained in most cases by a gap in management policies due partly to the complex problem of controlling the dynamic evolution of marine resources. To improve the efficiency of exploiting stock and preventing the collapse of key fishery, it is essential to well understand the stock evolution mechanism and to have a good estimate of the population stock state. To overcome these types of problems in fishery management, mathematical models are very often used to describe the dynamic evolution of some fish population. With these models it becomes easier to observe and hence to regulate the dynamics of a given fish population. In this paper, we are interested in the estimation problem of the unknown stock state of a harvested fish population whose dynamics are modeled by a discrete time system including a nonlinear stock recruitment relationship. As already mentioned in the abstract, the stock state estimation problem for a harvested fish population was first investigated [START_REF] Ngom | An Observer for a nonlinear Age-structured model of a Harvested Fish Population[END_REF] by considering an age-structured fishpopulation model. However determining the age for a fish population is a difficult task, it would be easier and more pertinent in practice to classify a fish population by other quantities that correlate with age such as size or weight. Moreover, most of the time the catch data that we have access to are generally evaluated in terms of size or weight. Hence a stage structured fish population model is more general and realistic than an age-structured one. The stage-structured fish model we consider here is the following (cf: [START_REF] Getz | Population harvesting. Demographic models of fish, forest, and animal resources[END_REF], page 84 and 35):

                         x 1 (k + 1) = (1 -p 1 )s 1 (k)x 1 (k) + s 0 f n i=1 b i x i (k)
x 2 (k + 1) = p 1 s 1 (k)x 1 (k) + (1 -p 2 )s 2 (k)x 2 (k) . . . . . .

x n-1 (k + 1) = p n-2 s n-2 (k)x n-2 (k) + (1 -p n-1 )s n-1 (k)x n-1 (k)

x n (k + 1) = p n-1 s n-1 (k)x n-1 (k) + s n (k)x n (k) (1)
where

• n is the number of stage-classes.

• x i (k) is the number of individuals in stage class i at time k.

• b i is the fecundity rate in stage class i.

• s 0 is the individual survival rate of newborn.

• s i (k) is the individual survival rate in the stage class i at time k: s i (k) = e -M i -q i E(k)τ (see Getz book: pp 221)

• M i is the natural mortality rate in stage class i.

• q i is the catchability coefficient of individuals in stage class i.

• E(k) is the fishing effort at time k.

• p i is the proportion of individuals in stage class i that move to the next stage class i + 1 after the time interval [k, k + 1[.

• τ is the length of harvesting season.

• f is the stock-recruitment function.

The widely used recruitment functions [START_REF] Beverton | On the dynamics of exploited fish populations[END_REF][START_REF] Getz | Population harvesting. Demographic models of fish, forest, and animal resources[END_REF][START_REF] Magal | A fixed point theorem with application to a model of population dynamics[END_REF][START_REF] Ricker | Stock and recruitment[END_REF][START_REF] Shepherd | A family of general production curves for exploited populations[END_REF] are:

Beverton and Holt f (x 0 ) = αx 0 /(1 + βx 0 ) ;

Ricker f (x 0 ) = αx 0 e -βx 0 ; P owerf unction f (x 0 ) = αx 1-β 0 ; Shepherd f (x 0 ) = αx 0 /(1 + βx c 0 ) , (c > 0). Deriso -Schnute f (x 0 ) = αx 0 (1 -βx 0 ) 1/γ ; Saila -Lorda f (x 0 ) = αx γ 0 e -βx 0 .
Where α, β and γ are positive parameters and

x 0 = n i=1 b i x i is the number of newborns.
The recruitment function is very difficult to model because many factors such as water temperature, air speed and other natural phenomena can often perturb the growth of young individuals that are too vulnerable. One weakness of the model ( 1) is that most of the suggested mathematical expressions for the recruitment function are only valid for some restricted hypotheses. For example Beverton and Holt justified their recruitment function by making hypotheses on food competition whereas the Ricker recruitment function is based on eggs and juvenile predation. Hence the recruitment term in the first equation of model ( 1) is not well known and we can rewrite the model

     x 1 (k + 1)
x 2 (k + 1) . . .

x n (k + 1)      = A(k)      x 1 (k) x 2 (k) . . . x n (k)      +      r x(k) 0 . . . 0      (2)
where

A(k) =                 (1 -p 1 )s 1 (k) 0 . . . . . . 0 p 1 s 1 (k) . . . . . . . . . 0 p 2 s 2 (k) . . . . . . . . . . . . . . . . . . (1 -p n-1 )s n-1 (k) 0 0 . . . 0 p n-1 s n-1 (k) s n (k)                 Remark 1. Note that if p i = 1, for i = 1, .
. . , n we obtain the age-structured model for which we have built an observer in [START_REF] Ngom | An Observer for a nonlinear Age-structured model of a Harvested Fish Population[END_REF].

While we focus one analyzing a fish-population model subjected to fishing action, quantifying the number of fish catch has great importance for the synthesis of the estimator stock states.

Regarding the model we address above, the number of fish catch over the time period [k, k + 1[ in each stage class i is given by:

y i (k) = k+τ k q i E(k)x i (t)dt (3)
(cf: Getz book 's, page 146). The total fish catch number is then:

y(k) = n i=1 k+τ k q i E(k)x i (t)dt (4)
After few computations we can write

y(k) = n i=1 q i E(k) q i E(k) + M i 1 -e -M i -q i E(k) τ x i (k) (5) Let C i (k) = q i E(k) q i E(k) + M i 1 -e -M i -q i E(k) τ
, then y(k) can be written as:

y(k) = n i=1 C i (k)x i (k) (6)
To summarize, the model we consider in this work is:

x(k + 1) = A(k)x(k) + Dr(x) y(k) = C(k)x(k) (7)
where A(k) is defined above, C(k) = C 1 (k), . . . , C n (k) and D = 1, 0, . . . , 0 t . Now we assume that the model with unknown single input (2), which can be written as [START_REF] Bhattacharyya | Observer design for linear system with unknown inputs[END_REF], describes successfully the dynamics of the considered harvested fish population. To compute the state x(k) at time k, we need to know the value of the state x(k 0 ) at a given time k 0 < k. However the model does not give any information about the unknown state value x(k 0 ). The model only provides information about relation between two consecutive states x(k) and x(k + 1). The model also gives measure of captures over time interval [k, k + 1[. To make the model ( 2) useful, we have to find how to estimate the unknown value x(k). This is the main concern we will address in this paper. To achieve this goal, we will use a tool from control theory called observer. We construct another dynamical system whose state x will provide an estimate of the unknown state of the considered model and this will be true regardless of the initial condition of the observer. We briefly recall the definition of an observer in control theory. Let us consider the following dynamic system:

   x(k + 1) = F(x(k), u(k)) y(k) = H(x(k), u(k)). (8)
where x(k) ∈ IR n is the state of the system , u(k) ∈ U ⊂ IR m is the input or the control and y(k) ∈ IR q is the measurable output at time k.

Definition 1. An observer for the dynamical system ( 8) is another dynamical system Σ whose inputs are the inputs and the outputs of system (8) and whose state x(k) satisfies x(k) -x(k) tends to zero as time k goes to infinity and must remain small if it starts small. Σ is an exponential observer of (8) if there exists ρ < 1 in such a way that for all k ≥ 0 and for all initial conditions (x(0), x(0)), one has

| x(k) -x(k) |≤ ρ k | x(0) -x(0) | .
Usually, a candidate observer Σ for system (8) is given by

   z(k + 1) = G x(k), u(k), y(k) , x(k) = J (z(k), y(k)). (9)
More details on observer notions can be found in [START_REF] Iggidr | Controllability, observability and stability of mathematical models[END_REF][START_REF] Sontag | Mathematical control theory. Deterministic finite-dimensional systems[END_REF]. Observer theory for linear discrete-time system with known inputs is well established. For linear invariant-time systems, the synthesis of the observer is completely given by the Luenberger method [START_REF] Luenberger | An introduction to observers[END_REF]. For linear time varying systems, several robust algorithms have been developed, one can cite for instance [START_REF] Albertos | Block multirate Input-Output model for sampled-Data control systems[END_REF][START_REF] Anderson | Detectability and stabilizability of time-varying discretetime linear systems[END_REF][START_REF] Baras | Dynamic observers as asymptotic limits of recursive filters : special cases[END_REF][START_REF] Boutayeb | Observers design for linear time-varying systems[END_REF][START_REF] Kamen | Block form observers for linear time-varying discrete-time systems[END_REF][START_REF] Kamen | Study of linear time-varying discrete-time systems in terms of time-compressed models[END_REF]. In the special case of uncertain systems the synthesis of observers is still a very difficult task. The Kalman filter [START_REF] Anderson | Optimal filering[END_REF] is the most classical approach used to build observers for uncertain systems but the optimal filter require restricted hypothesis. Another approach which is based on dynamical interval analysis exists in the literature [START_REF] Corliss | Survey of interval algorithms for ordinary differential equations[END_REF][START_REF] Rihm | interval methods for initial value problems in ODEs[END_REF], the idea consist in computing an interval known as "interval observer" which contains the state variable we need to estimate. Several algorithms on the synthesis of "interval observer" has been proposed in the literature for continuous systems [START_REF] Kurzhanski | Ellipsoidal Calculus for Estimation and Control[END_REF][START_REF] Rapaport | Parallelotopic and practical observers for non-linear uncertain systems[END_REF] and for discrete-time system [START_REF] Jaulin | Guaranteed nonlinear estimation using constraint propagation on sets[END_REF][START_REF] Sheweppe | Recursive state estimation: Unknown but bounded errors and systems inputs[END_REF]. Some algorithms have also been developed to solve the estimation problem for some classes of system with unknown inputs [START_REF] Bhattacharyya | Observer design for linear system with unknown inputs[END_REF][START_REF] Darouach | Full-order observer for linear systems with unknown inputs[END_REF][START_REF] Hou | Disturbance decoupled observer design: A unified viewpoint[END_REF][START_REF] Hou | Design of observers for linear systems with unknown inputs[END_REF][START_REF] Hostetter | Observing systems with unmeasurable inputs[END_REF][START_REF] Jin | Time-delayed state and unknown input observation[END_REF][START_REF] Johnson | An observers for systems with unknown and inacessible inputs[END_REF][START_REF] Nikoukhah | Observer Design for General Linear Timeinvariant Systems[END_REF][START_REF] Sundaram | Delays observers for linear systems with unknown inputs[END_REF][START_REF] Valcher | State observers for discrete-time linear systems with unknown inputs[END_REF]. Some of these observers carry out only the system state estimation, while other observers allow the estimation of the states as well as the unknown inputs of the system. One of the techniques used for the synthesis of the observer that estimate the states and the unknown inputs of a system consists in regrouping the state vector and the unknown inputs of the system in an augmented state-vector and in building an estimator for this augmented system [START_REF] Hostetter | Observing systems with unmeasurable inputs[END_REF][START_REF] Johnson | An observers for systems with unknown and inacessible inputs[END_REF][START_REF] Yang | Observers for linear systems with unknown inputs[END_REF].

To construct an observer for system with unknown inputs, one can use an approach that consists in eliminating the unknowns inputs in the equations of the system [START_REF] Hou | Design of observers for linear systems with unknown inputs[END_REF]. However, most of the available results concern linear time invariant systems. Here we are interested in the design of a global observer for the fishery system (2) which is a linear time varying system with known input E(k) and unknown input r x(k) .

Observer for linear time varying systems with unknown inputs

We consider the following time-varying system:

x(k + 1) = Γ(k)x(k) + Λζ, y(k) = θ(k)x(k), (10)
where x(k) and y(k) are respectively the state and the measurable output at time k, Γ(k) and θ(k) are respectively time varying matrix, Λ is a column vector and ζ is a scalar unknown input. In [START_REF] Hou | Disturbance decoupled observer design: A unified viewpoint[END_REF] M. Hou and P.C. Muller have developed a technique to synthesize observers for linear continuous time-invariant systems with unknown inputs. We adapt this technique for linear discrete timevarying systems with unknown inputs of the form [START_REF] Darouach | Full-order observer for linear systems with unknown inputs[END_REF]. Let y(k) be the measurable output of the system (10), we have

y(k + 1) = θ(k + 1)x(k + 1) = θ(k + 1) Γ(k)x(k) + Λζ = θ(k + 1)Γ(k)x(k) + θ(k + 1)Λζ
Assume that θ(k + 1)Λ is invertible ∀k ≥ 0. Thus we obtain:

ζ = θ(k + 1)Λ -1 y(k + 1) -θ(k + 1)Γ(k)x(k)
Then we have:

x(k + 1) = Γ(k)x(k) + Λζ = Γ(k)x(k) + Λ θ(k + 1)Λ -1 y(k + 1) -θ(k + 1)Γ(k)x(k) = Γ(k)x(k) + Λ θ(k + 1)Λ -1 y(k + 1) -Λ θ(k + 1)Λ -1 θ(k + 1)Γ(k)x(k) = Γ(k) -Λ θ(k + 1)Λ -1 θ(k + 1)Γ(k) x(k) + Λ θ(k + 1)Λ -1 y(k + 1) = I n×n -Λ θ(k + 1)Λ -1 θ(k + 1) Γ(k)x(k) + Λ θ(k + 1)Λ -1 y(k + 1).
We define:

Γ(k) = I n×n -Λ θ(k + 1)Λ -1 θ(k + 1) Γ(k).
Thus we obtain:

x(k + 1) = Γ(k)x(k) + Λ θ(k + 1)Λ -1 y(k + 1)
A candidate observer for system [START_REF] Darouach | Full-order observer for linear systems with unknown inputs[END_REF] is then given by:

   z(k + 1) = Γ(k) -L(k)θ(k) z(k) + L(k) + Γ(k) -L(k)θ(k) Λ θ(k)Λ -1 y(k). x(k) = z(k) + Λ θ(k)Λ -1 y(k). (11)
Let e(k) = x(k) -x(k) the estimation error, the error dynamics are described by:

e(k + 1) = x(k + 1) -x(k + 1) = Γ(k)x(k) + Λ θ(k + 1)Λ -1 y(k + 1) -z(k + 1) -Λ θ(k + 1)Λ -1 y(k + 1) = Γ(k)x(k) -Γ(k) -L(k)θ(k) z(k) -L(k) + (Γ(k) -L(k)θ(k))Λ θ(k)Λ -1 y(k) = Γ(k) -L(k)θ(k) x(k) -Γ(k) -L(k)θ(k) z(k) -Γ(k) -L(k)θ(k) Λ θ(k)Λ -1 y(k) = Γ(k) -L(k)θ(k) x(k) -x(k) e(k + 1) = Γ(k) -L(k)θ(k) e(k)
To summarize, we have the following result Proposition 1. Assume that the matrix θ(k)Λ is invertible for all k. If there exists a matrix L(k) in such a way that the matrix 11) is a global exponential observer for system [START_REF] Darouach | Full-order observer for linear systems with unknown inputs[END_REF], i.e., the estimation error e(k) tends exponentially fast towards zero as k tends to +∞.

Γ(k) -L(k)θ(k) satisfies Γ(k) -L(k)θ(k) ≤ δ for some δ < 1 then system (
A sufficient condition for the existence of such a matrix L(k) is that the pair [Γ(k), θ(k)] is uniformly observable. We recall here what does uniform observability mean. Consider the system

x(k + 1) = Γ(k)x(k) with measurable output y(k) = θ(k)x(k). Let Ψ i,k for i ≥ k be the transition matrix for the system x(k + 1) = Γ(k)x(k), i.e. Ψ i,i = I n×n and Ψ i,k = Γ(i -1)Γ(i -2) . . . Γ(k) for i > k.
The observability Gramian for the system is defined as

G k+t,k = k+t i=k Ψ T i,k θ(i) T θ(i) Ψ i,k (where A T is the transpose matrix of A).
The pair [Γ(k), θ(k)] is uniformly observable if there exist a positive real β > 0 and a positive integer t > 0 such that one has for all k ≥ 0

G k+t,k ≥ βI n×n . (12)
If the pair [Γ(k), θ(k)] is uniformly observable and the matrices Γ(k), θ(k) are bounded above then a possible choice for the gain matrix L(k) that makes the error equation e(k + 1) = Γ(k) -L(k)θ(k) e(k) globally exponentially stable is given by the following formula (see [START_REF] Moore | Coping with singular transition matrices in estimation and control stability theory[END_REF] for instance):

L(k) = Γ(k) Ψ k,k-t-1 G -1 k,k-t-1 Ψ T k,k-t-1 θ(k) T (13)
3 Stock state estimation using an observer

In this section we shall apply the method developed in Section 2 in order to construct an observer that will provide an estimate of the state of system (2) using only the measurable output given by equation [START_REF] Baras | Dynamic observers as asymptotic limits of recursive filters : special cases[END_REF]. System [START_REF] Bhattacharyya | Observer design for linear system with unknown inputs[END_REF] has the same form as system [START_REF] Darouach | Full-order observer for linear systems with unknown inputs[END_REF] with:

Γ(k) = A(k), Λ = D, ζ = r x(k) and θ(k) = C(k)
We assume that q 1 = 0. Therefore C(k

)D = C 1 (k) = q 1 E(k) q 1 E(k) + M 1 1 -e -M 1 -q 1 E(k) τ = 0 for all k > 0, so that C(k)D is invertible for all k > 0.
As in Section 2 we define:

A(k) = I n×n -D C(k + 1)D -1 C(k + 1) A(k) = I n×n - 1 C 1 (k + 1) D C(k + 1) A(k).
Therefore a candidate observer for system (2) (or system [START_REF] Bhattacharyya | Observer design for linear system with unknown inputs[END_REF]) is given by:

   z(k + 1) = A(k) -L(k)C(k) z(k) + L(k) + A(k) -L(k)C(k) D C(k)D -1 y(k) x(k) = z(k) + D C(k)D -1 y(k) (14)
To compute the appropriate matrix gain L(k), one can uses the formula [START_REF] Hou | Disturbance decoupled observer design: A unified viewpoint[END_REF]. However, one has first to check the uniform observability of the pair [A(k), C(k)] which is not an easy task due to the large number of parameters and when the condition ( 12) is satisfied, the formula (13) gives a huge expression for the matrix L(k). These computations can be done when the parameter numerical values as well as the expression of the fishing effort are available. But here we prefer to give a simple expression for the observer, so, instead of computing L(k), we just choose L(k) = 0 and impose a weak condition on the fishing effort in such a way that the estimation error equation e(k + 1) = A(k) e(k) is exponentially stable. Therefore the candidate observer [START_REF] Hou | Design of observers for linear systems with unknown inputs[END_REF] becomes:

     z(k + 1) = A(k) z(k) + A(k) D C(k)D -1 y(k) = A(k) z(k) + A(k) D y(k) C 1 (k) x(k) = z(k) + D C(k)D -1 y(k) (15)
This can be written in a more detailed form:

                                                                     z 1 (k + 1) = - C 2 (k + 1)p 1 s 1 (k) C 1 (k + 1) z 1 (k) -n-1 i=2 p i s i (k) C i+1 (k+1) C 1 (k+1) + (1 -p i )s i (k) C i (k+1) C 1 (k+1) z i (k) - C n (k + 1)s n (k) C 1 (k + 1) z n (k) - C 2 (k + 1)p 1 s 1 (k) C 1 (k + 1)C 1 (k) y(k) z 2 (k + 1) = p 1 s 1 (k)z 1 (k) + (1 -p 2 )s 2 (k)z 2 (k) + p 1 s 1 (k) C 1 (k) y(k), z 3 (k + 1) = p 2 s 2 (k)z 2 (k) + (1 -p 3 )s 3 (k)z 3 (k), . . . . . . z n-1 (k + 1) = p n-2 s n-2 (k)z n-2 (k) + (1 -p n-1 )s n-1 (k)z n-1 (k), z n (k + 1) = p n-1 s n-1 (k)z n-1 (k) + s n (k)z n (k), x1 (k) = z 1 (k) + 1 C 1 (k) y(k), xi (k) = z i (k) for i = 2, . . . n. (16)
We define: E min ≤ E(k) ≤ E max for all k ≥ 0, q min ≤ q i ≤ q max and M min ≤ M i ≤ M max for all i = 1, . . . , n. Our main result can be written:

Proposition 2. Assume that q 1 = 0. There exists η > 0 such that if E min > η, then the system (15) (or system [START_REF] Iggidr | Controllability, observability and stability of mathematical models[END_REF]) is a global exponential observer for system (2): the estimation error

satisfies |x(k) -x(k)| ≤ δ k |x(0) -x(0)| for all k ≥ 0, with δ = δ(E min ) = Mmaxqmax q 1 1 M min +q min E min + 1 1-e -M min +q min E min τ + 1 e -M min +q min E min τ < 1 if E min > η.
Proof. See the Appendix A.

Remark 2. The convergence rate of the observer ( 16) is less or equal than δ(E min ). It can not be adjusted.

Remark 3. When the coefficients p i are all equal to 1, the model ( 2) is equivalent to the age structured fish model (see for instance [START_REF] Getz | Population harvesting. Demographic models of fish, forest, and animal resources[END_REF]) for which an observer has been built in [START_REF] Ngom | An Observer for a nonlinear Age-structured model of a Harvested Fish Population[END_REF].

Remark 4. When the natural mortality rates are all equal, it is possible to give a weaker condition on the minimal value of the fishing effort that ensures the convergence of the observer.

Proposition 3. Assume that q 1 ≤ q i ∀i = 2, ..., n, and moreover that the natural mortality coefficient is the same for all stages, that is, M 1 = M 2 = . . . = M n = M . Then, the system ( 16) is a global exponential observer for the system (2) if

E min > 1 q 1 1 τ Log q max q 1 + 1 -M .
Remark 5. The available catch data usually give the seasonal biomass yield, i.e., the total weight of the fishes caught during a season. If we denote w i the mean weight of individuals of stage i, m i (k) the biomass of stage i at time k and F i (k) = q i E(k) the fishing mortality rate for stage i, then the measurable output (seasonal biomass yield) can be expressed as follows:

Y (k) = n i=1 F i (k) M i +F i (k) (1 -e (-M i -F i (k))τ )w i x i (k) = n i=1 F i (k) M i +F i (k) (1 -e (-M i -F i (k))τ ) m i (k) = n i=1 C i (k) m i (k) (17)
The equation ( 16) of the observer can be modified in order to estimate the biomass m i (k) = w i x i (k) for each stage instead of the number of individuals in each stage by replacing in ( 16) y(k) by Y (k) and xi (k) by mi (k).

Numerical example

We now give some simulations to illustrate the efficiency of the observer [START_REF] Iggidr | Controllability, observability and stability of mathematical models[END_REF]. We suppose that the dynamics of a harvested population can be modeled by a three-stages model with a Ricker stock-recruitment function:

           x 1 (k + 1) = (1 -p 1 )s 1 (k)x 1 (k) + α 3 i=1 b i x i (k) e -β( 3 i=1 b i x i (k)) , x 2 (k + 1) = p 1 s 1 (k)x 1 (k) + (1 -p 2 )s 2 (k)x 2 (k), x 3 (k + 1) = p 2 s 2 (k)x 2 (k) + s 3 (k)x 3 (k). (18)
We assume that the biological parameter values as well as the fishing strategy are known and are given by: Parameters Recall that since the value of (x 1 (0), x 2 (0), x 3 (0)) is not known, one can not use system (18) to evaluate (x 1 (k), x 2 (k), x 3 (k)) for a given positive time k. It is reasonable to assume that the value of the total catch is available for each fishing season, that is, the value of the quantity y(k) =

3 i=1 q i E(k) q i E(k)+M i 1 -e -M i -q i E(k) τ x i (k) = 3 i=1 C i (k)x i (k) is known for each k.
Therefore the observer ( 16) which uses the value of the total catch can be used to give a dynamical estimation of the stock state because we have proved in Section 3 that its solutions will converge (quite rapidly) towards the solutions of the model ( 18) regardless of the value of the initial conditions. Moreover, this observer can be implemented without using the expression of the recruitment function. To summarize, if the value of the total catch is available for each season then a good estimate (x 1 (k), x2 (k), x3 (k)) of the stock state (x 1 (k), x 2 (k), x 3 (k)) can be obtained by choosing an arbitrary initial condition (z 1 (0), z 2 (0), z 3 (0)) and computing the solutions of the following observer:

                                               z 1 (k + 1) = - C 2 (k + 1)p 1 s 1 (k) C 1 (k + 1) z 1 (k) -p 2 s 2 (k) C 3 (k+1) C 1 (k+1) + (1 -p 2 )s 2 (k) C 2 (k+1) C 1 (k+1) z 2 (k) - C 3 (k + 1)s 3 (k) C 1 (k + 1) z 3 (k) - C 2 (k + 1)p 1 s 1 (k) C 1 (k + 1)C 1 (k) y(k) z 2 (k + 1) = p 1 s 1 (k)z 1 (k) + (1 -p 2 )s 2 (k)z 2 (k) + p 1 s 1 (k) C 1 (k) y(k), z 3 (k + 1) = p 2 s 2 (k)z 2 (k) + s 3 (k)z 3 (k), x1 (k) = z 1 (k) + 1 C 1 (k) y(k), xi (k) = z i (k) for i = 2, 3. (19)
We have plotted the solutions of systems ( 18) and ( 19) using arbitrary initial conditions. The Figures (1), ( 2) and (3) confirm the fact that the xi (k) (dashed curves) delivered by the observer [START_REF] Johnson | An observers for systems with unknown and inacessible inputs[END_REF] are good estimates of the states x i (k) of system [START_REF] Jin | Time-delayed state and unknown input observation[END_REF]. It can be noticed that the convergence of the state estimates xi (k) towards the real states x i (k) is quite fast. 5 Applications

Application using data from ICES

Now we shall illustrate how to use the the observer [START_REF] Iggidr | Controllability, observability and stability of mathematical models[END_REF] with real data assessed by the Advisory Committee on Fisheries Management (ACFM) of the International Council for the Exploration of the Sea (ICES). One of the major task of the ICES is to collect scientific information in order to give advice to decision makers about the question of fisheries conservation and protection of the marine environment. In this context, the Advisory Committee on Fisheries Management of ICES has published a report on the evolution of the stock of the Arctic cod in the Atlantic North East [START_REF] Anon | ): Report of the Arctic fisheries Working Group[END_REF] (see also [START_REF] Wikan | An Analysis of a Nonlinear Stage-Structured Cannibalism Model with Application to the Northeast Arctic Cod Stock[END_REF]) between 1946 and 2000. The annual stock for immature and mature of the considered fish population between 1946 and 2000 are estimated in this report. This report (Table 1) gives for each year:

• total catch of immature individuals (Y 1 (k));

• total catch of mature individuals (Y 2 (k));

• fishing mortality rate for immature (F 1 (k)) and for mature individuals (F 2 (k));

• the ICES annual stock estimates m 1 (k) for immature and m 2 (k) for mature.

In order to give an application of the proposed observer with these data we will consider the observer [START_REF] Iggidr | Controllability, observability and stability of mathematical models[END_REF] with two classes (n = 2): the class of immature and the class of mature individuals.

Using Table 1, we compute for each year k the measurable output y(k) which is the total catch of mature and immature individuals at year k, i.e., Y (k) = Y 1 (k) + Y 2 (k). Table 1 also gives the values of the fishing mortality rates F 1 (k) and F 2 (k). The ICES assumes a natural mortality rate M 1 = M 2 = M = 0.2 and τ = 1 (the length of harvesting season). The proportion p 1 of immature individuals that move into the mature stage class at time k + 1 has been chosen equal to p 1 = 0.1. Therefore, for all k, Table 1 allows to compute

Y (k), C i (k) = F i (k) M i +F i (k) (1 -e -(M i +F i (k)) ), and s i (k) = e -(M i +F i (k))
. Hence with all these data, it is possible to run the following observer (20) that will deliver stock estimates x1 (k) and x2 (k) for immature and mature individuals:

                           z 1 (k + 1) = - C 2 (k + 1)p 1 s 1 (k) C 1 (k + 1) z 1 (k) - C 2 (k + 1) C 1 (k + 1) s 2 (k)z 2 (k) - C 2 (k + 1)p 1 s 1 (k) C 1 (k + 1)C 1 (k) Y (k), z 2 (k + 1) = p 1 s 1 (k)z 1 (k) + s 2 (k)z 2 (k) + p 1 s 1 (k) C 1 (k) Y (k), m1 (k) = z 1 (k) + 1 C 1 (k) Y (k), m2 (k) = z 2 (k). ( 20
)
To compare our estimations with those of ICES Advisory Committee on fisheries Management, we represent in the same graphs 4 and 5 the two estimations. These graphs show that our estimations have the same behavior as those of the ICES Advisory Committee on fisheries Management. Our observer slightly overestimates the biomass state for immature class.

Application using FAO data

As we mentioned it in Remark 1, when all the parameters p i , i = 1, . . . , n are assumed to be equal to one, the model (2) becomes:

                     x 1 (k + 1) = r(x) x 2 (k + 1) = s 1 (k)x 1 (k) . . . . . . x n-1 (k + 1) = s n-2 (k)x n-2 (k) x n (k + 1) = s n-1 (k)x n-1 (k) + s n (k)x n (k) (21)
which is exactly the corresponding age structured model (see for instance [START_REF] Getz | Population harvesting. Demographic models of fish, forest, and animal resources[END_REF]), than the observer becomes:

                                                         z 1 (k + 1) = - C 2 (k + 1)s 1 (k) C 1 (k + 1) z 1 (k) - n-1 i=2 s i (k) C i+1 (k + 1) C 1 (k + 1) z i (k) - C n (k + 1)s n (k) C 1 (k + 1) z n (k) - C 2 (k)s 1 C 1 (k) 2 y(k) z 2 (k + 1) = s 1 (k)z 1 (k) + s 1 C 1 (k) y(k), . . . . . . z n-1 (k + 1) = s n-2 (k)z n-2 (k), z n (k + 1) = s n-1 (k)z n-1 (k) + s n (k)z n (k), x1 (k) = z 1 (k) + 1 C 1 (k) y(k), xi (k) = z i (k) for i = 2, . . . n. (22)
where

C i (k) = F i (k) F i (k) + M i 1 -e -M i -F i (k) τ and s i (k) = e -M i -F i (k) τ
As in the previous section we give an application of the observer ( 22) using data from the the United Nations Food and Agriculture Organization of (FAO). These data are presented in the report [START_REF] Fao | Rapport du deuxième groupe de travail AD HOC sur les Chinchards et les Maquereaux de la zone nord du COPACE[END_REF]. This report concerned the stock estimation of the chinchards Trachurus spp in the statistical division COPAGE 34.1.3 and 34.3.1 which is a part of the Atlantic Eastern central ocean. The chinchards Trachurus spp population is classified into eight age-classes (class 0 + , 1, 2, 3, 4, 5, 6, 7 + ) and the annual commercial catches y i (k) in each age-class between 1972 and 1985 are given in Table 2. Most of the the annual commercial catches of the age-class 0 + are null. So we assume that the age-class 1 is the recruitment class and hence the harvested fishes correspond to the age-classes 1, 2, 3, 4, 5, 6, 7 + . The natural mortality rates M i are assumed to be all equal to 0.5, the fishing mortality rates F i (k) for each age-class are given in Table 3.

Using the data contained in the Tables 2 and3 one can implement the observer [START_REF] Kurzhanski | Ellipsoidal Calculus for Estimation and Control[END_REF] and compare the estimates delivered by this observer with the FAO estimates given by Table 4. It should be noticed that we only need the value of the total catch which is easier to measure than the catch for each age-class. The observer is implemented with two arbitrary different initial conditions to show that this initial condition didn't impact the convergence of the observer toward the "real states" of the stock. In Figures 6, 7

Discussion

We have applied the observer (16 or 20) given by the stage-class structured model to a fish population structured in immature and mature classes. The observer is implemented with an arbitrary initial condition and delivers stock estimates for immature and mature classes for each year. These estimates are comparable to those of the ICES. However the observer [START_REF] Kamen | Block form observers for linear time-varying discrete-time systems[END_REF] slightly overestimates the biomass of the immature stage. This mild difference may be due to the difference between our estimation method and the ICES estimation method. It could also be due to the value we have used for the parameter p (the proportion of individuals in immature class that moves to the mature class after one year) which is not given in the ICES report, we have used p = 0.1. In spite of this, the observer gives a good information about the fluctuation of the stock for the two stages during the considered period.

We have also applied the observer [START_REF] Kurzhanski | Ellipsoidal Calculus for Estimation and Control[END_REF] to estimate the stock state for a harvested population structured in seven age-classes. The data corresponding to this population are given in a FAO report. We point out with simulations that even in choosing an initial condition of the observer very distant from the initial condition of the FAO estimates, the curve of the observer converges (quite rapidly) towards the curve of the FAO estimates. We also note that if we consider two different initial conditions of the observer, the two curves of the observer converge simultaneously toward the the graph of FAO estimates. Hence, in the absence of the FAO stock estimation, the states of the stock fish population are reached as soon as a curve of the observer reaches another curve of the observer with a different initial condition.

It must be noticed that for the applications with real data, we only need the value of the total catch for the whole population: the observer implementation does not require the knowledge of the captures for each stage.

When the analytic expression of the fishing effort as well as the the parameter numerical values are available it is possible to check the uniform observability condition and hence to compute the matrix gain L(k) in order to increase the convergence of the estimation error towards zero. We think that when the computation of such L(k) is possible, the convergence of the observer will be guaranteed without the condition of Proposition 2 concerning the minimal fishing effort value. A work in this direction is in progress.

Conclusion

We have built an observer for a stage-structured model of a harvested fish population. The model we have considered is a dynamical discrete-time system including a nonlinear recruitment relationship. We have shown how to use the catch data in order to give an estimate of the stock of each stage-class for the harvested fish population under consideration. The observer estimator has the particularity of not using the recruitment function which is very poorly known. It may be noticed that the observer we have built is easy to implement and it has been successfully tested by some real data from FAO and ICES Advisory Committee on fisheries Management. Historically, the tools and techniques of automatic control theory have been developed for artificial engineering systems but nowadays they are more and more applied to "natural systems". The work we address in this paper is an example showing how observer theory and computer sciences can be helpful for good policies in management fishery.

A(k) 1 = I n×n -D C(k + 1)D -1 C(k + 1) A(k) 1 = I n×n - 1 C 1 (k + 1) D C(k + 1) A(k) 1 A(k) 1 ≤ I n×n - 1 C 1 (k + 1) D C(k + 1) 1 A(k) 1
We have:

I n×n - 1 C 1 (k + 1) D C(k + 1) 1 = max j C j (k + 1) C 1 (k + 1) + 1 , and A(k) 1 = max j s j (k).
Hence:

A(k) 1 ≤ max j C j (k + 1) C 1 (k + 1) + 1 max j s j (k).
The remaining part of the proof is quite similar to the proof of the main result of [START_REF] Ngom | An Observer for a nonlinear Age-structured model of a Harvested Fish Population[END_REF]. We give it here in order to be self-contained.

For j = 1...n, Let:

γ j (k) = C j (k + 1) C 1 (k + 1
) .

ICES data

( 1 )

 1 by considering the recruitment function s 0 f n i=1 b i x i (k) as an unknown input r x(k) to obtain the linear model with unknown single input r x(k) :

of the Ricker function α = 1 ,

 1 effort E(k) = 3 + sin(k)

Figure 1 :

 1 Figure 1: State x 1 (solid line) and the corresponding estimate x1 (dashed line) delivered by the observer (19)

Figure 2 :

 2 Figure 2: State x 2 (solid line) and the corresponding estimate x2 (dashed line) delivered by the observer (19)

Figure 3 :

 3 Figure 3: State x 3 (solid line) and the corresponding estimate x3 (dashed line) delivered by the observer (19)

Figure 4 :

 4 Figure 4: ICES biomass estimates and observer biomass estimates for the immature class.

Figure 5 :

 5 Figure

Figure 6 :Figure 7 :Figure 8 :Figure 9 :Figure 10 :Figure 11 :Figure 12 :

 6789101112 Figure 6: FAO estimates and the observer estimates for age class 1

  ij (k)|. Using the construction of the matrix A(k), we can write

Table 1 :

 1 Table: Biomass and catch in million tonnes of the Arctic cod in the North-East between 1946 and 2000.

		These data are from the "ICES Advisory Committee on
		Fisheries Management" (Anon, 2001), table 3.7 (catch),
		table 3.19 (biomass) and table 3.23 (maturity).
	ICES Biomass		Catch	Fishing mortality
		estimates		(million tonnes)	rate
	(million tonnes)
	Year	Immature	Mature	Immature	Mature	Immature	Mature
	(k)	(m 1 (k))	(m 2 (k))	(y 1 (k))	(y 2 (k))	(F 1 (k))	(F 2 (k))
	1946	3.3866	1.1206	0.4222	0.2633	0.1247	0.2350
	1947	2.7283	1.1740	0.4959	0.4688	0.1818	0.3993
	1948	2.8562	1.0264	0.5176	0.3510	0.1812	0.3420
	1949	2.5528	0.7360	0.5503	0.2563	0.2156	0.3482
	1950	2.5292	0.6206	0.4284	0.2444	0.1694	0.3938
	1951	3.0474	0.5741	0.5263	0.1940	0.1727	0.3379
	1952	3.4114	0.5271	0.6951	0.2428	0.2038	0.4606
	1953	3.8533	0.4010	0.5209	0.1425	0.1352	0.3554
	1954	3.9139	0.4350	0.7196	0.1691	0.1839	0.3887
	1955	3.2905	0.3512	0.9268	0.1526	0.2817	0.4345
	1956	3.1074	0.3034	1.1425	0.1421	0.3677	0.4684
	1957	2.6487	0.2103	0.7023	0.0900	0.2651	0.4280
	1958	2.1979	0.1978	0.6019	0.0830	0.2739	0.4196
	1959	2.2912	0.4382	0.6197	0.1806	0.2705	0.4121
	1960	2.0169	0.3890	0.4343	0.1629	0.2153	0.4188

Acknowledgments

We thank the anonymous referees for their comments and suggestions that have allowed us to improve the presentation of this article.

Appendix A: Proof of proposition 2

We prove that system [START_REF] Hostetter | Observing systems with unmeasurable inputs[END_REF] is a global exponential observer for model [START_REF] Bhattacharyya | Observer design for linear system with unknown inputs[END_REF]. Let e(k) = x(k) -x(k) be the error estimation at time k. It satisfies the equation:

It's sufficient to prove that there exists δ such that A(k) ≤ δ < 1, for some matrix norm. Here we shall use the norm 1 defined by A(k) 1 = max We have:

Since q j q 1 E(k + 1)

< 1, we can write

The map x → 1 -e -xτ x is decreasing, hence:

1 -e -M j -q j E(k+1) τ M j + q j E(k + 1) ≤ 1 -e -M min -q min E min τ M min + q min E min So we obtain:

Since 0 < e -M j -q j E(k+1) τ ≤ 1, we have 1 -e -M j -q j E(k+1) τ ≤ 1. Therefore, we have for j = 1 . . . n -1,

1 -e -M min -q min E min τ .

23

Therefore,

1 -e -M min -q min E min τ , ∀ j = 1, ..., n.

Otherwise s i (k) ≤ e -M min -q min τ E min ≤ e -M min -q min E min τ , ∀ j = 1, ..., n. Hence:

1 -e -M min -q min E min τ

+ 1 e -M min -q min E min τ .

We denote:

1 -e -M min -q min E min τ

+ 1 e -M min -q min E min τ .

We will show now that there exists η > 0 in such a way that E min > η implies δ(E min ) < 1.

Let X = e -M min -q min E min τ and consider

One can remark that P (X) = δ(E min ) -1.

We have lim X→0 P (X) = -1 and lim X→1 -P (X) = +∞. So there exists x 1 ∈]0, 1[ such that P (x 1 ) = 0. Let x * = inf {x ∈]0, 1[/P (x) = 0} then we have P (X) < 0 for all X satisfying 0 < X < x * . Now, 0 < X < x * is equivalent to E min > -Log(x * ) q min τ -M min q min since X = e (-M min -q min E min )τ . It is then sufficient to choose η = -Log(x * ) q min τ -M min q min and this completes the proof of Proposition 2.

FAO data (from http://www.fao.org/DOCREP/003/S4882F/S4882F09.htm).


Montassar Ben Messaoud
email: benmessaoud.montassar@hotmail.fr

Philippe Leray
email: philippe.leray@univ-nantes.fr

Nahla Ben Amor
email: nahla.benamor@gmx.fr

SemCaDo: a serendipitous strategy for learning causal bayesian networks using ontologies

, few of them have taken into account the gain that can be expected when integrating additional knowledge during the learning process. In this paper, we present a new serendipitous strategy for learning CBNs using prior knowledge extracted from ontologies. The integration of such domain's semantic information can be very useful to reveal new causal relations and provide the necessary knowledge to anticipate the optimal choice of experimentations. Our strategy also supports the evolving character of the semantic background by reusing the causal discoveries in order to enrich the domain ontologies.

Introduction

Bayesian networks (BNs), first introduced by Pearl [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF], are compact graphical probabilistic models able to efficiently model uncertainty in real world problems.

One of the important properties relative to BNs is the Markov equivalence property which can be illustrated by the fact that the two networks X → Y and X ← Y are equivalent (i.e. encode the same joint probability distribution). Nevertheless, only one of them is a correct from causal point of view. In fact, in the first network X causes Y , then, manipulating the value of X affects the value of Y contrary to the second one where Y is a cause of X meaning that manipulating X will not affect Y . Thus a BN cannot be considered as a proper causal network but the contrary is always true. This means that given a Causal Bayesian Network (CBN) one can use it even to determine how the observation of specific values (evidence) affects the probabilities of query variable(s) or to predict the effect of an intervention on the remaining variables [START_REF] Pearl | Causality: models, reasoning, and inference[END_REF].

Contrary to the non-Gaussian learning methods (also called LiNGAM) which use pure observational data (D obs ), the causal discovery in CBNs often requires interventional data (D int ). In this work, we don't make use of LiNGAM methods since no suitable parametrization of the joint distribution can be established when working under the non-gaussianity assumption. This is the key reason for restricting our approach to only CBNs.

This paper provides a substantially extended version of our previous work [START_REF] Ben Messaoud | Integrating ontological knowledge for iterative causal discovery and visualization[END_REF] in which we introduce the preliminary findings for integrating a semantic distance calculus to choose the appropriate interventions. Further developments along this direction have been made in order to deploy more efficient strategies to integrate the semantic prior knowledge, improve the causal discovery process and reuse the new discovered information.

The remainder of this paper is arranged as follows: Section 2 gives the necessary background for both CBNs and ontologies and discusses some related works that combine the two formalisms. Section 3 sets out how to use the ontological knowledge to enhance the causal discovery and vice versa. In Section 4, we show simulation results to evaluate the performances of the proposed algorithm. Concluding remarks and future works are given in Section 5.

Basic concepts & background

Causal Bayesian Networks

A Causal Bayesian Network (CBN) is a Directed Acyclic Graph (DAG) where the set of nodes V represents discrete random variables X={X 1 , X 2 ,.., X n } and the set of edges E represents causal dependencies over V. We use D i to denote the finite domain associated with each variable X i and x i to denote any instance of X i . We denote by P a(X i ) the set of parents nodes for X i and N ei(X i ) the set of its neighboring variables.

In addition to the usual conditional independence interpretation, the CBN is also given a causal interpretation since each directed edge is traduced as that the source node is the direct cause of the target node. For this reason, CBNs are considered as proper bayesian networks (BNs) but the reverse is not necessarily true.

The main difference between the two formalisms lies in the nature of the data needed to learn the structure. In fact, contrary to BNs, when using only observational data, we may not have enough information to discover the true structure of the graph and the causal model will be restricted to the Completed Partially Directed Acyclic Graph (CPDAG). Thus we have to collect further information on causality via interventions (i.e. actions tentatively adopted without being sure of the outcome). Here, we should note that intervening on a system may be very expensive, time-consuming or even impossible to perform. For this reason, the choice of variables to experiment on can be vital when the number of interventions is restricted.

All those distinguishing features have motivated many researchers to develop a variety of techniques and algorithms to learn such models [START_REF] He | Active learning of causal networks with intervention experiments and optimal designs[END_REF][START_REF] Meganck | Learning causal bayesian networks from observations and experiments: A decision theoretic approach[END_REF][START_REF] Murphy | Active learning of causal bayes net structure[END_REF].

Ontologies

There are different definitions in the literature of what should be an ontology. The most notorious was given by Tom Gruber [START_REF] Gruber | Towards Principles for the Design of Ontologies Used for Knowledge Sharing[END_REF], stipulating that an ontology is an explicit specification of a conceptualization. The "conceptualization", here, refers to an abstract model of some phenomenon having real by identifying its relevant concepts. The word "explicit" means that all concepts used and the constraints on their use are explicitly defined.

In the simplest case, an ontology describes a hierarchy of concepts (i.e. classes) related by taxonomic relationships (is-a, part-of). In more sophisticated cases, an ontology describes domain classes, properties (or attributes) for each class, class instances (or individuals) and also the relationships that hold between class instances. It is also possible to add some logical axioms to constrain concept interpretation and express complex relationships between concepts.

Hence, more formally, an ontology can be defined as a set of labeled classes C={C 1 , ..., C n }, hierarchically ordered by the subclass relations (i.e. is-a, part-of relations). For each concept C i we identify k meaningful properties p j , where j ∈ [1, k]. We use H i to denote the finite domain of instance (i.e. concretizing the ontology concepts by setting their properties values) candidates with each concept C i and c i to denote any instance of C i . We also use R to represent the set of semantical (i.e non-hierarchical) relations between concepts and R c to represent the subset of causal ones. Finally, formal axioms or structural assertions <c i , c j , s> can be included, where s ∈ S is a constraint-relationship like "must, must not, should, should not, etc".

Practically speaking, the ontologies are often a very large and complex structure, requiring a great deal of effort and expertise to maintain and upgrade the existing knowledge. Such proposals can take several different forms such as a change in the domain, the diffusion of new discoveries or just an information received by some external source [START_REF] Flouris | Ontology change: classification and survey[END_REF].

There are many ways to change the ontology in response to the fast-changing environment. One possible direction is the ontology evolution which consists in taking the ontology from one consistent state to another by updating (adding or modifying) the concepts, their properties and the associated relations [START_REF] Khattak | Ontology Evolution: A Survey and Future Challenges[END_REF].

The ontology evolution can be of two types [START_REF] Khattak | Ontology Evolution: A Survey and Future Challenges[END_REF]:

-Ontology population: When new concept instances are added, the ontology is said to be populated. -Ontology enrichment: Which consists in updating (adding or modifying) concepts, properties and relations in a given ontology.

In order to establish the context in which the ontology evolution takes place, the principle of ontology continuity should be fulfilled [START_REF] Xuan | A versioning management model for ontology-based data warehouses[END_REF]. It supposes that the ontology evolution should not make false an axiom that was previously true. When changes do not fulfill the requirement of ontological continuity, it is not any more an evolution, it is rather an ontology revolution.

Related work

Recent studies have investigated some ways to combine both ontologies and BNs. The first line of research focused on how to integrate the power of BNs to enhance the potential of ontologies by supplementing it with the principle means of modeling uncertainty in ontologies. In this way, [START_REF] Yang | Ontobayes: An ontology-driven uncertainty model[END_REF] have proposed the OntoBayes approach, an ontology-driven Bayesian model for uncertain knowledge representation, to extend ontologies to probability-annotated OWL in decision making systems. [START_REF] Ding | A probabilistic extension to ontology language OWL[END_REF] also proposed an approach when they augment the OWL language to allow additional probabilistic markups so that probability values can be attached to individual concepts and properties. One of the main advantage of this probabilistic-extended ontology is that it can support common ontology-related reasoning tasks as probabilistic inferences.

On the other hand, other solutions were proposed in order to enhance the BN construction by integrating ontologies. For example, [START_REF] Jeon | Ontology-based semi-automatic construction of bayesian network models for diagnosing diseases in e-health applications[END_REF] developed a semiautomatic BN construction system based on e-health ontologies. Their framework enables probabilistic inferencing capability for various E-health applications and contributes to reduce the complexity of BN construction. A similar approach for BN construction using ontologies was proposed in [START_REF] Devitt | Constructing bayesian networks automatically using ontologies[END_REF]. Nevertheless, it presents an automatic solution, implemented in the context of an adaptive, self-configuring network management system in the telecommunication domain.

To our knowledge, we are the first to propose a real cooperation in both ways between ontologies and CBNs. Our previous work [START_REF] Ben Messaoud | Integrating ontological knowledge for iterative causal discovery and visualization[END_REF] focused on only one facet of the CBN-ontology combination by integrating the ontological knowledge to learn CBNs. Taking a further step in the same research direction, this work consists on designing a strategy that addresses issues to incorporate the second combination facet via reusing the causal discoveries to enrich the ontologies.

3 SemCaDo: a serendipitous causal discovery algorithm for ontology evolution

Generally, in the research area, scientific discoveries represent a payoff for years of well-planned works with clear objectives. This affirmation did not exclude the case of other important discoveries that are made while researchers were conducting their works in totally unrelated fields and the examples are abundant from Nobel's flash of inspiration while testing the effect of dynamite to Pasteur brainstorm when he accidentally discovered the role of attenuated microbes in immunization. In this way, we propose a new causal discovery algorithm which stimulates serendipitous discoveries when performing the experimentations using the following CBN-Ontology correspondences.

CBNs vs Ontologies

One of the main motivations when realizing this work is the similarities between CBNs and ontologies. This is particularly true when comparing the structure of the two models as shown in the following correspondences:

1. Nodes (V i ) ↔ Concepts (C i ):
The ontology concepts, which are relevant to the considered domain are traduced by the nodes of the CBN.

2. Random variables (X i ) ↔ Concept attributes (C i .p j ): All random variables in the CBN are represented as specific concept attributes in the ontology. 3. Causal dependencies (E) ↔ Semantic causal relations (R c ):

The correspondence between the two models in term of causality will be as follows:

-A causal relation between two concepts in the ontology will be traduced by a directed link between the corresponding CBN nodes. It is read as c Y .p j is the direct consequence of c X .p j , where p j is the concept attribute used to make the correspondence. -A causal dependency represented by a directed link in the CBN will be traduced by a specific causal relation between the appropriate concepts in the ontology.

4. Observational or experimental data (D obs,int ) ↔ Concept-attribute instances (c i .p j ): We make a correspondence between the observational (resp. interventional) data at our disposal and the instances of the domain ontology. Each observation (resp. intervention) can be viewed, in the ontological context, as a state instantiation of a given concept attribute.

SemCaDo Sketch

Our approach relies on extending the MyCaDo algorithm [START_REF] Meganck | Learning causal bayesian networks from observations and experiments: A decision theoretic approach[END_REF] in order to incorporate available knowledge from domain ontologies. The original character of the SemCaDo (Semantic Causal Discovery) algorithm is essentially its ability to make impressive discoveries and reuse the capitalized knowledge in CBNs.

The correspondences between CBNs and ontologies in SemCaDo must respect the following constraints:

-Only a single ontology should be specified for each causal discovery task.

-Each causal graph node must be modeled by a corresponding concept in the domain ontology. The concepts which are candidates to be a member of such correspondence have to share the same studied attribute p j . -The causal discoveries concern concepts sharing the same semantic type (e.g. direct transcriptional regulation between genes). This means that all concepts C i modeled in the CBN must belong to the same super-concept SC and the causal relationship under study R c should be defined for any element of SC to any other one. -The ontology evolution should be realized without introducing inconsistencies or admitting axiom violations.

In this way, we will adopt the same basic scenario as in MyCaDo and describe the possible interactions with the domain ontology.

The general overview of the SemCaDo algorithm is given in Figure 1. As inputs, SemCaDo needs an observational dataset and a corresponding domain ontology. Then it will proceed through three main phases: 1) Learning the initial structure using causal prior knowledge: The ontology in input may contain some causal relations in addition to hierarchical and semantic relations. Those causal relations should be integrated from the beginning in the structure learning process in order to reduce the task complexity and better the final output. Therefore, such direct cause to effect relations will be incorporated as constraints when using structure learning algorithms. Our main objective is to narrow the corresponding search space by introducing some restrictions that all elements in this space must satisfy.

In our context, the only constraint that will be defined is edge existence. But we could also imagine in future work that some axioms in the ontology also give us some information about forbidden edges. All these edge constraints can easily be incorporated in usual BN structure learning algorithm [START_REF] De Campos | Bayesian network learning algorithms using structural restrictions[END_REF]. Under some condition of consistency, these existence restrictions shall be fulfilled, in the sense that they are assumed to be true for the CBN representing the domain knowledge, and therefore all potential Partially Directed Acyclic Graph (PDAG) must necessarily satisfy them. Definition 1. Given a domain ontology O, let G=(C, R c ) be the DAG where R c : C i × C j represents the subset of semantic causal relations extracted from O. This subset included both direct and logically derivable semantic causal relations. Let H=(X, E h ) be a PDAG, where X is the set of the corresponding random variables and E h corresponds to the causal dependencies between them. H is consistent with the existence restrictions in G if and only if:

∀ C i , C j ∈ C, if C i →C j ∈ R c then X i →X j ∈ E h .
When we are specifying the set of existence restrictions to be used, it is necessary to make sure that these restrictions can indeed be satisfied. In fact, such causal integration may lead to possible conflicts between the two models. When this occurs, we have to maintain the initial causal information in the PDAG since we are supposed to use perfect observational data. On the other hand, we should ensure the consistency of the existence restrictions in such a way that no directed cycles are created in G.

2) Causal discovery process: Before delving into the details of our approach, we first review the principal idea of the causal discovery process in MyCaDo algorithm [START_REF] Meganck | Learning causal bayesian networks from observations and experiments: A decision theoretic approach[END_REF].

When performing an experimentation on X i , MyCaDo measure all neighboring variables and accordingly to the result direct all edges connecting X i and Nei(X i ). This edge orientation represents one instantiation (inst(A Xi )) among all possible instantiations. It is then possible to continue the edge orientation by using the Meek rules [START_REF] Meek | Causal inference and causal explanation with background knowledge[END_REF] to infer new causal relations.

Let inf erred(inst(A Xi )) be the number of inferred edges based on inst(A Xi ). MyCaDo proposes that the utility of an experiment is related to the number of edges directly oriented or inferred, weighted by the cost of experiment (cost(A Xi )) and measurement (cost(M Xi )):

U (X i ) = Card(N ei(X i )) + Card(inf erred(inst(A Xi ))) αcost(A Xi ) + βcost(M Xi ) (1)
where measures of importance α and β ∈ [0,1] and Card(M) represents the cardinality of any set M.

It seems obvious that the gained information of such utility function is essentially the node connectivity ( i.e. the number of undirected edges and those susceptible to be inferred) which serves to orient the maximal number of edges but not necessary the most informative ones.

To cope with this limitation, the strategy we propose in our approach makes use of a semantic distance calculus (e.g. Rada distance [START_REF] Rada | Development and application of a metric on semantic nets[END_REF]) provided by the ontology structure. So, for each node in the graph, SemCaDo gives a generalization of the node connectivity by introducing the semantic inertia, denoted by SemIn(X i ) and expressed as follows:

SemIn(X i ) = Xj ∈N ei(Xi)∪Xi dist Rada (mscs(N ei(X i ) ∪ X i ), X j ) Card(N ei(X i ) ∪ X i ) (2)
where:

mscs(C i , C j ): the most specific common subsumer of the two concepts C i and C j , where i = j. dist Rada (C i , C j ): the shortest path between C i and C j , where i = j, Moreover, the semantic inertia presents three major properties:

-When the experimented variable and all its neighbors lie at the same level in the concept hierarchy, the semantic inertia will be equal to the number of hierarchical levels needed to reach the mscs. -If the corresponding concepts belong to the same super-class then SemIn will be proportional to Card(Nei(.)). -It essentially depends on semantic distance between the studied concepts.

This means that the more this distance is important, the more the SemIn will be maximized.

By this way, we will accentuate the serendipitous aspect of the proposed strategy and investigate new and unexpected causal relations on the graph.

Further to these, we also integrate a semantic cumulus relative to the inferred edges denoted by Inf erred Gain in our utility function. For this purpose, we use I(X i ) to denote the set of nodes attached by inferred edges after performing an experimentation on X i . So, the Inf erred Gain formula is expressed as follows:

Inf erred Gain(X i ) = Xj ∈I(Xi) dist Rada (mscs(I(X i )), X j ) Card(I(X i )) (3)
Inf erred Gain also represents a generalization of Card(inferred(inst(.)) and depends on the semantic distance between the studied concepts. Note that we don't use here all the information provided by the ontology. We should also consider the axioms to check if any new relation could be inferred from the semantic point of view. Better interacting with the axioms is one of our perspectives for future work.

When using the two proposed terms, our utility function will be as follows:

U (X i ) = SemIn(X i ) + Inf erred Gain(X i ) αcost(A Xi ) + βcost(M Xi ) (4)
where measures of importance α, β ∈ [0,1].

This utility function will be of great importance to highlight the serendipitous character of SemCaDo algorithm by guiding the causal discovery process to investigate unexplored areas and conduct more informative experiments.

3) Edge orientation & ontology evolution: Once the specified intervention performed, we follow the same edge orientation strategy as in MyCaDo [START_REF] Meganck | Learning causal bayesian networks from observations and experiments: A decision theoretic approach[END_REF]. So if there are still some non-directed edges in the PDAG , we re-iterate over the second phase and so on, until no more causal discoveries can be made. Since certain experimentation can not be performed, either because of ethical reasons or simply because it is impossible to do it, the final causal graph can be either a CBN or a partially causal graph.

In both cases, the causal knowledge will be extracted and interpreted for an eventual ontology evolution. In this way, the causal relations will be traduced as semantic causal relations between the corresponding ontology concepts.

We note that, because of the priority given to the ontology axioms, only causal relations guaranteeing the consistency will be retained for the ontology evolution process.

Toy example

In the following example, we briefly illustrate the various steps we followed to construct a CBN when using SemCaDo algorithm. As noted above, we assume that all random variables under study are modeled in the corresponding ontology (See Figure 2) as distinctly blue-colored concepts. We note that in order to simplify the semantic analysis, we restricted the ontology to only taxonomic relations and causal ones. As first step, we use the graph in Figure 3 (a) to specify the existence restrictions to be satisfied. In our case, three causal relations (i.e. A42→B87, A40→A15 and D53→C65) extracted from the ontology in Figure 2 have to be modeled as directed arrows before learning the initial structure. Using this prior knowledge, Figure 3 (b) shows the resulting partially directed graph after performing a structure learning algorithm and applying the Meek rules [START_REF] Meek | Causal inference and causal explanation with background knowledge[END_REF] to infer edges.

When running the SemCaDo causal discovery process, the first best node to experiment on will be E71. This choice is strongly supported by the high semantic distance between E71 and its neighboring variables (i.e. E76 and A42) as well as the additional semantic cumulus relative to the edges susceptible to be inferred (i.e. E76-A40, A42-E76, A40-A42 and A40-E78). Thanks to this experimentation, we can investigate different causal relations between the more distant concepts in the ontology, in which we have not enough prior causal information (See Figure 2).

After finishing all the causal discovery step and learning the completed directed graph as shown in Figure 3

Experimental study

In the experimental evaluation, we will compare SemCaDo to MyCaDo algorithm [START_REF] Meganck | Learning causal bayesian networks from observations and experiments: A decision theoretic approach[END_REF] since both of them share the same assumptions and use the same input data. For this purpose, we randomly create a set of syntectic 50 and 200 node graphs and apply a DAG-to-CPDAG algorithm [START_REF] Chickering | Learning equivalence classes of bayesian-network structures[END_REF] on those CBNs in order to simulate the result of a structure learning algorithm working with a perfect infinite dataset. For each simulated graph, we automatically generate a corresponding concept hierarchy in which we integrate a varying percentage (10% to 40%) of the initial causal relations. As we do not dispose of a real system to intervene upon, we decide to simulate the experimentations directly in the previously generated CBNs as in [START_REF] Meganck | Learning causal bayesian networks from observations and experiments: A decision theoretic approach[END_REF].

Another point to consider in our experimental study concerns the calculation of the semantic gain. In fact, after each SemCaDo (resp. MyCaDo) iteration, we measure the sum of semantic distances (Rada's [START_REF] Rada | Development and application of a metric on semantic nets[END_REF] in these experiments) relative to the new directed edges in the graph and update a semantic cumulus. In both strategies, the two corresponding curves are increasing in, meaning that the higher is the number of experimented variables, the higher is the value of the semantic gain. Nevertheless the more the curve is increasing faster, the more the approach is converging to the best and most impressive experiments.

Figure 4 shows that, during the experimentation process, our approach comfortably outperforms the MyCaDo algorithm in term of semantic gain. This is essentially due to the initial causal knowledge integration and the causal discovery strategy when performing the experimentations. But if the two curves reach the same maxima when obtaining a fully directed graph, where is the evolutionary contribution of SemCaDo? Let us remember that we are approaching a decision problem which is subject to the experimentation costs and the budget allocation. Taking into account this constraint, the domination of SemCaDo will be extremely beneficial when the number of experiments is limited.

All these experimental results show how the SemCaDo algorithm can adopt a serendipitous attitude with the minimum expected cost and effort. This is indeed a new avenue of causal investigation, moving far away from traditional techniques.

Conclusions and Future Works

In this paper, we outlined our serendipitous and cyclic approach which aims to i) integrate the causal prior knowledge contained in the corresponding ontology when learning the initial structure from observational data, ii) use a semantic distance calculus to guide the iterative causal discovery process to the more surprising relationships and iii) capture the required causal discoveries to be applied to ontology evolution. The SemCaDo algorithm is an initial attempt towards a more ambitious framework exploiting the power of BNs and ontologies. Future works will be devoted to ontology revolution through better interactions with the axioms during the causal discovery process.

Fig. 1 .

 1 Fig. 1. SemCaDo: Extending MyCaDo to allow CBN-Ontology interactions

Fig. 2 .

 2 Fig. 2. An example of ontology: blue nodes denote the concepts under study, red relationships denote causal prior knowledge and black relationships are taxonomic relations.

  Figure 3 (b) shows the resulting partially directed graph after performing a structure learning algorithm and applying the Meek rules[START_REF] Meek | Causal inference and causal explanation with background knowledge[END_REF] to infer edges.When running the SemCaDo causal discovery process, the first best node to experiment on will be E71. This choice is strongly supported by the high semantic distance between E71 and its neighboring variables (i.e. E76 and A42) as well as the additional semantic cumulus relative to the edges susceptible to be inferred (i.e. E76-A40, A42-E76, A40-A42 and A40-E78). Thanks to this experimentation, we can investigate different causal relations between the more distant concepts in the ontology, in which we have not enough prior causal information (See Figure2).After finishing all the causal discovery step and learning the completed directed graph as shown in Figure3(c), the supplementary causal knowledge will be interpreted and reused in the corresponding ontology. The dashed lines in Figure 3 (d) indicate the ontology evolution (i.e. ontology enrichment) in response to SemCaDo discoveries.

Fig. 3 .

 3 Fig. 3. (a) Existence restriction graph extracted from the ontology in Figure 2, (b) PDAG obtained after structure learning phase using previous restriction graph, (c) the CBN obtained after performing experiments on (E71, B80 and A42) and (d) the enriched ontology.

Fig. 4 .

 4 Fig. 4. The semantic gain given the number of experiments using MyCaDo and Sem-CaDo on relatively small graphs (a) and bigger ones (b)


Montassar Ben
email: benmessaoud.montassar@hotmail.fr

Messaoud Larodec

Philippe Leray
email: philippe.leray@univ-nantes.fr

Nahla Ben Amor
email: nahla.benamor@gmx.fr.

SemCaDo: a serendipitous causal discovery algorithm for ontology evolution

With the rising need to reuse the existing knowledge when learning Causal Bayesian Networks (CBNs), the ontologies can supply valuable semantic information to make further interesting discoveries with the minimum expected cost and effort. In this paper, we propose a cyclic approach in which we make use of the ontology in an interchangeable way. The first direction involves the integration of semantic knowledge to anticipate the optimal choice of experimentations via a serendipitous causal discovery strategy. The second complementary direction concerns an enrichment process by which it will be possible to reuse these causal discoveries, support the evolving character of the semantic background and make an ontology evolution.

Introduction

Bayesian networks (BNs), first introduced by Pearl [START_REF] Pearl | Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF], are compact graphical probabilistic models that are capable of modeling domains comprising uncertainty. Due to the Markov equivalence property, when learning the Completed Partially Directed Acyclic Graph (CPDAG) from observational data and randomly choosing one possible complete instantiation in the equivalence space, we are not so sure if that graph reflects the true causal structure. For this reason, an extension of traditional BNs is introduced, where each edge is interpreted as a direct causal influence between a parent node and a child node, relative to the other nodes in the network [START_REF] Pearl | Judea Pearl. Causality: models, reasoning, and inference[END_REF].

This paper provides a substantially extended version of our previous work [Ben [START_REF] Messaoud | Integrating ontological knowledge for iterative causal discovery and visualization[END_REF] in which we introduce the preliminary findings for integrating a semantic distance calculus to choose the appropriate interventions. Further developments along this direction have been made in order to deploy more efficient strategies to integrate the semantic prior knowledge, improve the causal discovery process and reuse the new discovered information to support the ontology evolution.

The remainder of this paper is arranged as follows: Section 2 gives the necessary background for both CBNs and ontologies. Section 3 sets out how to use the ontological knowledge to enhance the causal discovery and vice versa. In Section 4, we show simulation results to evaluate the performances of the proposed algorithm. Concluding remarks and future works are given in Section 5.

Basic concepts & background 2.1 Ontologies

There are different definitions in the literature of what should be an ontology. The most notorious was given by Tom Gruber [Gruber, 1995], stipulating that an ontology is an explicit specification of a conceptualization. The "conceptualization", here, refers to an abstract model of some phenomenon having real by identifying its relevant concepts. The word "explicit" means that all concepts used and the constraints on their use are explicitly defined.

In the simplest case, an ontology describes a hierarchy of concepts (i.e. classes) related by taxonomic relationships (isa, part-of). In more sophisticated cases, an ontology describes domain classes, properties (or attributes) for each class, class instances (or individuals) and also the relationships that hold between class instances. It is also possible to add some logical axioms to constrain concept interpretation and express complex relationships between concepts.

Hence, more formally, an ontology can be defined as a set of labeled classes C={C 1 , ..., C n }, hierarchically ordered by the subclass relations (i.e. is-a, part-of relations). For each concept C i we identify k meaningful properties p j , where j ∈ [1, k]. We use H i to denote the finite domain of instance candidates with each concept C i and c i to denote any instance of C i . We also use R to represent the set of semantical (i.e nonhierarchical) relations between concepts and R c to represent the subset of causal ones. Finally, formal axioms or structural assertions <c i , c j , s> can be included, where s ∈ S is a constraint-relationship like "must, must not, should, should not, etc".

Practically speaking, the ontologies are often a very large and complex structure, requiring a great deal of effort and expertise to maintain and upgrade the existing knowledge. Such proposals can take several different forms such as a change in the domain, the diffusion of new discoveries or just an information received by some external source [START_REF] Flouris | [END_REF].

There are many ways to change the ontology in response to the fast-changing environment. One possible direction is the ontology evolution which consists in taking the ontology from one consistent state to another by updating (adding or modifying) the concepts, their properties and the associated relations [Khattak et al., 2009].

The ontology evolution can be of two types [Khattak et al., 2009]:

• Ontology population: When new concept instances are added, the ontology is said to be populated.

• Ontology enrichment: Which consists in updating (adding or modifying) concepts, properties and relations in a given ontology.

In order to establish the context in which the ontology evolution takes place, the principle of ontology continuity should be fulfilled [START_REF][END_REF]. It supposes that the ontology evolution should not make false an axiom that was previously true. When changes do not fulfill the requirement of ontological continuity, it is not any more an evolution, it is rather an ontology revolution.

Causal Bayesian Networks

A Causal Bayesian Network (CBN) is a Directed Acyclic Graph (DAG) where the set of nodes V represents discrete random variables X={X 1 , X 2 ,.., X n } and the set of edges E represents causal direct dependencies over V. We use D i to denote the finite domain associated with each variable X i and x i to denote any instance of X i . We denote by P a(X i ) the set of parents nodes for X i and N ei(X i ) the set of its neighboring variables.

To learn CBNs, the observational data don't contain enough information to discover the true structure of the graph, which will be restricted to the Completed Partially Directed Acyclic Graph (CPDAG). Thus we have to collect further information on causality via interventions (i.e. actions tentatively adopted without being sure of the outcome). Here, we should note that intervening on a system may be very expensive, time-consuming or even impossible to perform. For this reason, the choice of variables to experiment on can be vital when the number of interventions is restricted.

3 SemCaDo: a serendipitous causal discovery algorithm for ontology evolution

Generally, in the research area, scientific discoveries represent a payoff for years of well-planned works with clear objectives. This affirmation did not exclude the case of other important discoveries that are made while researchers were conducting their works in totally unrelated fields and the examples are abundant from Nobel's flash of inspiration while testing the effect of dynamite to Pasteur brainstorm when he accidentally discovered the role of attenuated microbes in immunization.

In this way, we propose a new causal discovery algorithm which stimulates serendipitous discoveries when performing the experimentations using the following CBN-Ontology correspondences.

CBNs vs Ontologies

One of the main motivations when realizing this work is the similarities between CBNs and ontologies. This is particularly true when comparing the structure of the two models as shown in the following correspondences:

1. Nodes (V i ) ↔ Concepts (C i ): The ontology concepts, which are relevant to the considered domain are represented by the nodes of the CBN. 2. Random variables (X i ) ↔ Concept attributes (C i .p j ):

All random variables in the CBN are represented as specific concept attributes in the ontology. 3. Causal dependencies (E) ↔ Semantic causal relations (R c ): The correspondence between the two models in term of causality will be as follows:

• A causal relation between two concepts in the ontology will be represented by a directed link between the corresponding CBN nodes. It is read as c Y .p j is the direct consequence of c X .p j , where p j is the concept attribute used to make the correspondence.

• A causal dependency represented by a directed link in the CBN will be represented by a specific causal relation between the appropriate concepts in the ontology.

4. Observational or experimental data (D obs,int ) ↔ Concept-attribute instances (c i .p j ): We make a correspondence between the observational (resp. interventional) data at our disposal and the instances of the domain ontology. Each observation (resp. intervention) can be viewed, in the ontological context, as a state instantiation of a given concept attribute.

SemCaDo Sketch

Our approach relies on extending the MyCaDo algorithm [START_REF] Meganck | [END_REF] in order to incorporate available knowledge from domain ontologies. The original character of the SemCaDo (Semantic Causal Discovery) algorithm is essentially its ability to make impressive discoveries and reuse the capitalized knowledge in CBNs.

The correspondences between CBNs and ontologies in SemCaDo must respect the following constraints:

• Only a single ontology should be specified for each causal discovery task. • Each causal graph node must be modeled by a corresponding concept in the domain ontology. The concepts which are candidates to be a member of such correspondence have to share the same studied attribute p j . • The causal discoveries concern concepts sharing the same semantic type (e.g. direct transcriptional regulation between genes). This means that all concepts C i modeled in the CBN must belong to the same superconcept SC and the causal relationship under study R c should be defined for any element of SC to any other one. • The ontology evolution should be realized without introducing inconsistencies or admitting axiom violations. The general overview of the SemCaDo algorithm is given in Figure 1. As inputs, SemCaDo needs an observational dataset and a corresponding domain ontology. Then it will proceed through three main phases:

1) Learning the initial structure using causal prior knowledge:

The ontology in input may contain some causal relations in addition to hierarchical and semantic relations. Those causal relations should be integrated from the beginning in the structure learning process in order to reduce the task complexity and better the final output. Therefore, such direct cause to effect relations will be incorporated as constraints when using structure learning algorithms. Our main objective is to narrow the corresponding search space by introducing some restrictions that all elements in this space must satisfy.

In our context, the only constraint that will be defined is edge existence. But we could also imagine in future work that some axioms in the ontology also give us some information about forbidden edges. All these edge constraints can easily be incorporated in usual BN structure learning algorithm [START_REF] De Campos | [END_REF]. Under some condition of consistency, these existence restrictions shall be fulfilled, in the sense that they are assumed to be true for the CBN representing the domain knowledge, and therefore all potential Partially Directed Acyclic Graph (PDAG) must necessarily satisfy them. Definition 1 Given a domain ontology O, let G=(C, R c ) be the DAG where R c : C i × C j represents the subset of semantic causal relations extracted from O. This subset included both direct and logically derivable semantic causal relations. Let H=(X, E h ) be a PDAG, where X is the set of the corresponding random variables and E h corresponds to the causal dependencies between them. H is consistent with the existence restrictions in G if and only if:

∀ C i , C j ∈ C, if C i →C j ∈ R c then X i →X j ∈ E h .
When we are specifying the set of existence restrictions to be used, it is necessary to make sure that these restrictions can indeed be satisfied. In fact, such causal integration may lead to possible conflicts between the two models. When this occurs, we have to maintain the initial causal information in the PDAG since we are supposed to use perfect observational data. On the other hand, we should ensure the consistency of the existence restrictions in such a way that no directed cycles are created in G.

2) Causal discovery process:

Before delving into the details of our approach, we first review the principal idea of the causal discovery process. When performing an experimentation on X i , we have to measure all neighboring variables and accordingly to the result direct all edges connecting X i and Nei(X i ). This edge orientation represents one instantiation among all possible instantiations. It is then possible to continue the edge orientation by using the Meek rules [Meek, 1995] to infer new causal relations.

The aim of this phase is to decide which experiment will be performed and hence also which variables will be altered and measured. For this purpose, the strategy we propose in our approach makes use of a semantic distance calculus (e.g. Rada distance [START_REF] Rada | [END_REF]) provided by the ontology structure. So, for each node in the graph, SemCaDo calculates its semantic inertia, denoted by SemIn(X i ) and expressed as follows:

SemIn(Xi)= X j ∈N ei(X i )∪X i dist Rada (mscs(N ei(Xi)∪Xi),Xj ) Card(N ei(Xi)∪Xi)
(1) where:

• mscs(c i , c j ): the most specific common subsumer of the two concepts c i and c j , where i = j. • dist Rada (c i , c j ): the shortest path between c i and c j , where i = j, • Card(M ): the cardinality of any set. Moreover, the semantic inertia presents the following properties:

• When the experimented variable and all its neighbors lie at the same level in the concept hierarchy, the semantic inertia will be equal to the number of hierarchical levels needed to reach the mscs.

• It essentially depends on semantic distance between the studied concepts. This means that the more this distance is important, the more the SemIn will be maximized. Further to these, we also integrate a semantic cumulus relative to inferred edges [Meek, 1995] denoted by Inf erred Gain in our utility function. For this purpose, we use I(X i ) to denote the set of nodes attached by inferred edges after performing an experimentation on X i . So, the Inf erred Gain formula is expressed as follows:

Inf erred Gain(Xi)= X j ∈I(X i ) dist Rada (mscs(I(Xi)),Xj ) Card(I(Xi))

(2)

Note that we don't use here all the information provided by the ontology. We should also consider the axioms to check if any new relation could be inferred from the semantic point of view. Better interacting with the axioms is one of our perspectives for future work.

When using the two proposed terms weighted by the cost of experiment (i.e. cost(A Xi )) and measurement (i.e. cost(M Xi )), our utility function will be as follows:

U (Xi)= SemIn(Xi)+Inf erred Gain(Xi) αcost(A X i )+βcost(M X i ) (3)
where measures of importance α, β ∈ [0,1].

This utility function will be of great importance to highlight the serendipitous character of SemCaDo algorithm by guiding the causal discovery process to investigate unexplored areas and conduct more informative experiments.

3) Edge orientation & ontology evolution:

Once the specified intervention performed, the meek rules [Meek, 1995] will be applied to infer new arcs until no more edges can be oriented. We note that these orientation rules are proven to be correct and complete subject to any additional background knowledge.

Since certain experimentation can not be performed, either because of ethical reasons or simply because it is impossible to do it, the final causal graph can be either a CBN or a partially causal graph. In both cases, the causal knowledge will be extracted and interpreted for an eventual ontology evolution.

In this way, the causal relations will be translated as semantic causal relations between the corresponding ontology concepts. For this purpose, SemCaDo algorithm uses a sixphases evolution process [Stojanovic et al., 2002]:

• Change capturing: The aim of this initial step in the ontology evolution process is to capture the new discovered causal relations on the current causal graph which are not actually modeled. It starts after finishing the structure learning step in order to treat all changes in a consistent and unified manner. • Change representation: In order to be correctly implemented, we have to represent these causal changes formally, explicitly and in a suitable format. In the context of SemCaDo algorithm, we only handle elementary changes (i.e. restricted to adding semantic causal relations) that cannot be decomposed into simpler ones.

• Semantics of change: The semantics of change is the phase that enables the resolution of ontology changes in a systematic manner by ensuring the consistency of the ontology. In our case, conflicting knowledge is highly possible to occur when deducing causal conclusions from the ontology axioms. Such inconsistencies should be handled by automated reasoning. This step also prevents the creation of new cycles in the ontology when integrating the causal discoveries. This consistency rule is maintained since the causal discovery step in SemCaDo avoid the creation of cycles during the structure learning. • Implementation: In order to avoid performing unwanted changes, a list of all consequences in the ontology and dependent artifacts should be generated and presented to the ontology engineer, who should then be able to accept the change or reject it. If the implementer agrees to add the new causal relationships, all actions to apply the change have to be performed. • Propagation: Pursuing and adopting the new causal discoveries can generate additional changes in the other parts of the ontology. These changes are called derived changes. That is why, during this step, it is necessary to determine the direct and indirect types of changes to be applied. In case of ambiguity, the ontology expert decide on the action to occur. A human intervention at this level is essential to remove the ambiguity and to make the final decision. • Validation: Change validation enables justification of performed changes and undoing them at user's request.

If the output of SemCaDo causal discovery step is a partially directed graph, it is possible to restart the cycle when there sufficient budget to make further discoveries. In the experimental evaluation, we will compare our approach to a random causal discovery strategy.

Experimental study

For this purpose, we randomly create a set of syntectic 50 and 200 node graphs and simulate the result of a structure learning algorithm working with a perfect infinite dataset. For each simulated graph, we automatically generate a corresponding concept hierarchy in which we integrate a varying percentage (10% to 40%) of the initial causal relations. As we do not dispose of a real system to intervene upon, we decide to simulate the experimentations directly in the previously generated CBNs.

Another point to consider in our experimental study concerns the calculation of the semantic gain. In fact, after each SemCaDo (resp. Random) iteration, we measure the sum of semantic distances [START_REF] Rada | [END_REF] in these experiments) relative to the new directed edges in the graph and update a semantic cumulus. In both strategies, the two corresponding curves are increasing in, meaning that the higher is the number of experimented variables, the higher is the value of the semantic gain. Nevertheless the more the curve is increasing faster, the more the approach is converging to the best and most impressive experiments.

Figure 2 shows that, during the experimentation process, SemCaDo comfortably outperforms the random approach in term of semantic gain. This is essentially due to the initial causal knowledge integration and the causal discovery strategy when performing the experimentations. But if the two curves reach the same maxima when obtaining a fully directed graph, where is the evolutionary contribution of Sem-CaDo? Let us remember that we are approaching a decision problem which is subject to the experimentation costs and the budget allocation. Taking into account this constraint, the semantic domination of SemCaDo will be extremely beneficial when the number of experiments is limited.

All these experimental results show how the SemCaDo algorithm can adopt a serendipitous attitude with the minimum expected cost and effort. This is indeed a new avenue of causal investigation, moving far away from traditional techniques.

Conclusions and Future Works

In this paper, we outlined our serendipitous and cyclic approach which aims to: i) Integrate the causal prior knowledge contained in the domain ontology when learning the structure of the partially directed graph from observational data. ii) Use the semantic distance calculus to guide the iterative causal discovery process and investigate unexpected causal relations. iii) Capture the required causal discoveries to be applied to ontology evolution.

The SemCaDo algorithm is an initial attempt towards a more ambitious framework exploiting the power of CBNs and ontologies. Future works will detail how to revolutionize the ontologies by adding new axioms and ignoring others when incorporating causal discoveries.

Figure 1 :

 1 Figure 1: The SemCaDo Algorithm

Figure 2 :

 2 Figure 2: The semantic gain given the number of experiments using SemCaDo and random approach on relatively small graphs (a) and bigger ones (b).