Sylvain Ervedoza
email: §ervedoza@math.univ-toulouse.fr

Olivier Glass

Sergio Guerrero

Jean-Pierre Puel

Local exact controllability for the 1-d compressible Navier-Stokes equations *

Introduction

In this talk, I will present a recent result obtained in [START_REF] Ervedoza | Local exact controllability for the 1-D compressible Navier Stokes equation[END_REF] with O. Glass, S. Guerrero and J.-P. Puel on the local exact controllability of the 1-d compressible Navier-Stokes equations. The goal of these notes is to give an informal presentation of this article and we refer the reader to it for extensive details.

Setting. We consider the compressible Navier-Stokes equations in a bounded domain (0, L):

∂ t ρ S + ∂ x (ρ S u S ) = 0 in (0, T ) × (0, L), ρ S (∂ t u S + u S ∂ x u S ) -∂ xx u S + ∂ x p(ρ S ) = 0 in (0, T ) × (0, L).
(1.1)

Here ρ S is the density and u S the velocity. The pressure is given by the following law:

p(ρ S ) = c p ρ γ S , (1.2)
where c p > 0 and γ ≥ 1. Recall that this is the classical law when considering isentropic flows, in which case γ = 1.4 for perfect gases, or isothermal flows (γ = 1). At this point, let us also remark that actually the only assumption we are going to use is that p is a smooth increasing function of the density. The initial data are also given: (ρ S , u S ) |t=0 = (ρ 0 , u 0 ) in (0, L).

(1.3)

Note that the boundary conditions are not given explicitly. They actually are the controls and will not be written explicitly. If one really wants to make them explicit, they could for instance be expressed as follows:

• Dirichlet boundary conditions for u S : u S (t, 0) = v 0 (t) and u S (t, L) = v L (t);

• conditions on the density when the flux enters the domain, i.e.: ρ S (t, 0) = w 0 (t) if u S (t, 0) > 0 and ρ S (t, L) = w L (t) if u S (t, L) < 0.

We are going to present a local exact controllability result around a constant equilibrium state (ρ, u) with ρ > 0. To be more precise, we are going to study if there exist a norm • * and a constant κ > 0 such that if (ρ 0 , u 0 ) -(ρ, u) * ≤ κ there exists a trajectory (ρ S , u S ) solution of (1.1)-(1.3) satisfying (ρ S , u S )(T ) = (ρ, u) in (0, L).

(1.4)

Before going further, let us emphasize that the time T is a critical parameter in such problem and in particular because of the hyperbolic nature of the equation of the density. Actually, due to the structure of the equation of the density, if the velocity stays in a neighborhood of the target velocity u, the time

T u = L |u| (1.5)
is expected to be critical for the control properties of the equation of the density in (1.1).

According to this fact, it is already natural to conjecture that the linearized compressible Navier-Stokes equations around the constant state (ρ, u) = (ρ, 0) are not controllable. This is indeed the case since then the linearized equations reduce to ∂ t ρ + ρ∂ x u = 0 in (0, T ) × (0, L), ρ∂ t u -∂ xx u + p ′ (ρ)∂ x ρ = 0 in (0, T ) × (0, L), (1.6) which imply the following equation on u:

ρ∂ tt u -∂ xx ∂ t u -p ′ (ρ)ρ∂ xx u = 0 in (0, T ) × (0, L). (1.7)
This equation is a wave equation with structural damping. It turns out that the controllability properties of equation (1.7) have already been studied thoroughly in [START_REF] Rosier | On the controllability of a wave equation with structural damping[END_REF] (see also [START_REF] Chowdhury | Controllability and stabilizability of the linearized compressible Navier-Stokes in one dimension[END_REF]). Using the spectral decomposition of the solutions, the article [START_REF] Rosier | On the controllability of a wave equation with structural damping[END_REF] shows that the equation (1.7) indeed is not exactly controllable.

(They also show that this is approximately controllable, but this weaker notion of controllability will not be discussed further here.)

The situation therefore seems to indicate that positive controllability results for linearized compressible Navier-Stokes equation around constant states can be obtained only for non-trivial target velocities u = 0, as already indicated by the critical time (1.5). One could then try to show that the corresponding linear system is exactly controllable provided the time T is larger than T u defined in (1.5). Actually, this would lead to the system

∂ t ρ + u∂ x ρ + ρ∂ x u = 0 in (0, T ) × (0, L), ρ(∂ t u + u∂ x u) -∂ xx u + p ′ (ρ)∂ x ρ = 0 in (0, T ) × (0, L).
(1.8)

Again, this implies the following equation on u:

ρ ∂ tt u + (|u| 2 -p ′ (ρ))∂ xx u + 2u∂ t ∂ x u -∂ t ∂ xx u -u∂ xxx u = 0 in (0, T ) × (0, L).
And this equation corresponds to the one studied in [START_REF] Martin | Null-controllability of a structurally damped wave equation with moving point control[END_REF] when |u| 2 = p ′ (ρ), u = -1 and L = 2π, in which case it is exactly controllable in time T > 2π. We shall not follow here the approach of [START_REF] Martin | Null-controllability of a structurally damped wave equation with moving point control[END_REF], which is based on a spectral decomposition of the solutions and which is therefore not robust which respect to perturbations.

Main result. We are then in position to state our main result.

Theorem 1.1 ([6]). Let u ∈ R * and ρ ∈ R * + . Let T > 0 satisfy T > T u = L |u| . (1.9)
Then there exists κ > 0 such that, for any u 0 ∈ H 3 (0, L) and ρ 0 ∈ H 3 (0, L) such that

u 0 -u H 3 (0,L) + ρ 0 -ρ H 3 (0,L) < κ, (1.10)
there exists a solution (ρ S , u S ) of (1.1)-(1.3) satisfying (1.4). Besides, the controlled trajectory satisfies

ρ S ∈ H 1 ((0, T ) × (0, L)) and u S ∈ H 1 ((0, T ); L 2 (0, L)) ∩ L 2 ((0, T ); H 2 (0, L)).
Let us give some comments on this result: • We have proved a local exact controllability result around constant equilibria (ρ, u) when ρ > 0, which is a natural assumption, and when u = 0, which comes from the hyperbolic nature of the equation of the density, see the above discussion.

• Our result is very weak, since it states local exact controllability only around constant equilibria. It is very likely that one can prove local exact controllability around smooth enough (to be made precise) trajectories (ρ, u) of (1.1) under an additional geometric condition. Roughly speaking, we expect such result to be true provided the flow corresponding to the target velocity runs across the whole domain.

• The neighborhood of the initial data is an H 3 × H 3 neighborhood. It is very likely that this can be relaxed to H 1 × H 1 , but our strategy of proof does not work with such low regularity assumptions.

• Our approach is mainly linear and we should emphasize that conditions u = 0 and T > T u are natural when staying in a neighborhood of the target (ρ, u). But other strategies could apply and use the nonlinearities, see for instance the return method of J.-M. Coron [START_REF] Coron | On the controllability of 2-D incompressible perfect fluids[END_REF][START_REF] Coron | Control and nonlinearity[END_REF].

References. Theorem 1.1 seems to be the first result on the controllability of the compressible Navier-Stokes equations (1.1) except for the recent result by E. Amosova [START_REF] Amosova | Exact local controllability for the equations of viscous gas dynamics[END_REF], which states the local exact controllability of compressible viscous fluids in dimension 1 considered in Lagrangian coordinates and when the initial density exactly coincides with the density part of the target.

There are however several results concerning the controllability properties of the incompressible Navier-Stokes and Euler equations. For incompressible Navier-Stokes equations, the first result seems to be a local exact controllability result around smooth trajectories obtained by A. Fursikov and O. Imanuvilov in [START_REF] Fursikov | Controllability of evolution equations[END_REF] for boundary conditions on the normal velocity and the curl. It has then be extended by Imanuvilov in [START_REF] Imanuvilov | Remarks on exact controllability for the Navier-Stokes equations[END_REF] to the case of Dirichlet boundary conditions. Later on in [START_REF] Fernández-Cara | Local exact controllability of the Navier-Stokes system[END_REF], the regularity on the target trajectory was lowered. Since then, other strategies have been proposed, and in particular the one in [START_REF] González-Burgos | Local exact controllability to the trajectories of the Boussinesq system via a fictitious control on the divergence equation[END_REF] which consists in adding a fictitious control in the divergence and then do a lifting to absorb it. In the context of incompressible Euler equations, J.-M. Coron in [START_REF] Coron | On the controllability of 2-D incompressible perfect fluids[END_REF] obtained the global exact controllability in dimension 2 using the return method. Later in [START_REF] Glass | Exact boundary controllability of 3-D Euler equation[END_REF], O. Glass extended this result to the 3-dimensional setting. Based on these results, J.-M. Coron and A. Fursikov show in [START_REF] Coron | Global exact controllability of the 2D Navier-Stokes equations on a manifold without boundary[END_REF] the global exact controllability of the incompressible Navier-Stokes equations provided the control is exerted on the whole boundary. Except for this situation, the global exact controllability of Navier-Stokes equations still is an open problem. Partial answers to that question are available in [START_REF] Guerrero | Remarks on global controllability for the Burgers equation with two control forces[END_REF] and [START_REF] Imanuvilov | On global controllability of 2-D Burgers equation[END_REF]. Some controllability results for compressible Euler equations are also available. In [START_REF] Li | Exact boundary controllability for quasi-linear hyperbolic systems[END_REF], a local controllability result has been obtained for classical solutions. In the context of weak entropy solutions, we refer to the result of O. Glass in [START_REF] Glass | On the controllability of the 1-D isentropic Euler equation[END_REF]. Finally, let us also mention the approximate controllability result by H. Nersisyan [START_REF] Nersisyan | Controllability of the 3D compressible Euler system[END_REF] where the control is a force lying in a finite-dimensional space.

For the rest of the talk, we assume that u > 0.

This can be done without loss of generality by using the change of coordinates x → Lx.

Main strategy

The strategy for the proof of Theorem 1.1 relies on a fixed point argument.

First, as we will explain later in Section 3, it is convenient to look for a trajectory going from 0 to 0. This can be done as follows. We define (ρ in , u in ) such that (ρ + ρ in , u + u in ) is a solution of (1.1) on (0, T ) × R with initial data (ρ 0 , u 0 ) (this supposes that the initial data have been extended on R smoothly, which can of course be done easily). We then look for (ρ, u) = (ρ Sρ -Λρ in , u Su -Λu in ) where Λ : [0, T ] → [0, 1] is a suitable smooth cut-off function taking value 1 close to t = 0, say on [0, T 0 ] for some small T 0 > 0, and vanishing after the time 2T 0 .

We are then looking for a solution (ρ, u) of

∂ t ρ + (u + u + Λu in )∂ x ρ + ρ∂ x u + ρp ′ (ρ)ρ = f (ρ, u) in [0, T ] × (0, L), (2.1) (ρ + Λρ in )(∂ t u + u∂ x u) -∂ xx u = g(ρ, u) in [0, T ] × (0, L), (2.2)
where f (ρ, u) and g(ρ, u) are given as follows:

f (ρ, u) = -Λ ′ ρ in + (Λ -Λ 2 )∂ x (ρ in u in ) -Λ∂ x (ρ in u) -Λρ∂ x u in -ρ∂ x u + ρp ′ (ρ)ρ. (2.3) and g(ρ, u) = -(ρ + Λρ in )Λ ′ u in -(p ′ (ρ + Λρ in ) -p ′ (ρ + ρ in ))Λ∂ x ρ in + ρ in ∂ t u in (Λ -Λ 2 ) + ρ in u∂ x u in (Λ -Λ 2 ) + ρu in ∂ x u in (Λ -Λ 2 ) + ρ in u in ∂ x u in (Λ -Λ 3 ) (2.4) -Λ(ρ + Λρ in )∂ x (uu in ) -(ρ + Λρ in )u∂ x u -ρ(∂ t (Λu in + u) + (u + Λu in + u)∂ x (Λu in + u)) -(p ′ (ρ + Λρ in + ρ) -p ′ (ρ + Λρ in ))∂ x (Λρ in + ρ) -p ′ (ρ + Λρ in )∂ x ρ, satisfying ρ(0, •) = ρ(T, •) = 0 and u(0, •) = u(T, •) = 0. (2.5)
We thus introduce a function F : (ρ, û) → (ρ, u) defined as follows: • u solves the control problem

(ρ + Λρ in )(∂ t u + u∂ x u) -∂ xx u = g(ρ, û) in [0, T ] × (0, L), (2.6)
and

u(0, •) = u(T, •) = 0 in (0, L).
(2.7)

• ρ solves the equation

∂ t ρ + (u + u + Λu in )∂ x ρ + ρ∂ x u = f (ρ, û) in [0, T ] × (0, L), (2.8)
and satisfies

ρ(0, •) = ρ(T, •) = 0 in (0, L).
(2.9)

Before going further and explaining how these two control problems are solved, let us comment this fixed point approach.

• the source terms f and g both contains linear terms. Here, we do not consider the terms coming from the initial data (i.e. the terms involving components having a subscript "in") as linear ones since they will eventually be arbitrarily small. The linear term in g is the one coming from the pressure. The linear term in f is ρp ′ (ρ)ρ and is in both sides of the equations. This only is a fictitious term which helps when deriving estimates on ρ, see Section 4.

• the equation of ρ in (2.8) is linear in ρ but non-linear in the couple (ρ, u). Indeed, our arguments strongly use the fact that the function ρ travels along the characteristics of u + u + Λu in .

• we have to make precise what is the fixed point space, but this would be done later.

• we will need to estimate the terms coming from the initial data in f and g. This will be done using [START_REF] Matsumura | The initial value problem for the equations of motion of viscous and heat-conductive gases[END_REF] which yields a bound on

(ρ in , u in ) in L ∞ (W 2,∞ ) ∩ W 1,∞ (W 1,∞ ) × L ∞ (W 2,∞ ) ∩ W 1,∞ (L ∞ ) in terms of the H 3 × H 3 -norm of (ρ 0 -ρ, u 0 -u)
. This bound will be called R in in the sequel and is assumed to be small. Roughly speaking, R in is proportional to κ in (1.10).

The talk is organized as follows. In Section 3, we explain how to solve the control problem in u in (2.6)-(2.7). In Section 4, we solve the control problem (2.8)-(2.9) for the density. We then briefly explain in Section 5 how to conclude. We finally end up with some further comments.

3 Controlling u

Controlling parabolic equations: the classical approach

Before going further, let us briefly explain the strategy of A. Fursikov and O. Imanuvilov (see for instance [START_REF] Fursikov | Controllability of evolution equations[END_REF]) to control a parabolic equation.

The control problem. Let g ∈ L 2 ((0, T ) × (0, L)) and consider the following distributed control problem with a control supported in (a, b) ⊂ (0, L): Find a function v ∈ L 2 ((0, T ) × (a, b)) such that the solution u of ∂ t u -∂ xx u = g + v1 (a,b) in (0, T ) × (0, L), u(t, 0) = u(t, L) = 0. (3.1) with initial data u(0, •) = 0 in (0, L) (3.2) satisfies u(T, •) = 0 in (0, L). (3.3)
A dual problem. In order to solve the control problem (3.1)-(3.2)-(3.3), the idea is to introduce its weak formulation: v is an admissible control function if and only if for all smooth function z satisfying z(t, 0) = z(t, L) = 0,

T 0 L 0 gz + T 0 b a vz + T 0 L 0 u(∂ t z + ∂ xx z) = 0. (3.4)
This equivalent weak formulation of the control problem suggests to focus on the observability properties of the adjoint equation. This is precisely the goal of Carleman estimates.

A Carleman estimate for the adjoint equation. Based on the ideas above, A. Fursikov and O. Imanuvilov in [START_REF] Fursikov | Controllability of evolution equations[END_REF] prove a Carleman estimate for the adjoint system. This requires the introduction of several notations.

Let us first set

ψ ∈ C ∞ ([0, L]; R + ) such that 3 ≤ min [0,L] ψ ≤ max [0,L] ψ ≤ 4, max [b,L] ψ ′ < 0 and min [0,a] ψ ′ > 0. (3.5)
We then define the weight functions ϕ(t, x) and ξ(t, x), depending on a positive parameter λ ≥ 1, as follows:

ϕ(t, x) = 1 t(T -t) e 5λ -e λψ(x) , (t, x) ∈ (0, T ) × [0, L], (3.6)
ξ(t, x) = 1 t(T -t) e λψ(x) , (t, x) ∈ (0, T ) × [0, L]. (3.7)
Using these notations, A. Fursikov and O. Imanuvilov in [START_REF] Fursikov | Controllability of evolution equations[END_REF] prove the following Carleman estimate:

Theorem 3.1. There exist constants C > 0, s 0 ≥ 1 and λ 0 ≥ 1 such that for all λ ≥ λ 0 and s ≥ s 0 , for all smooth function z satisfying z(t, 0) = z(t, L) = 0,

s 3 λ 4 (0,T )×(0,L) ξ 3 e -2sϕ |z| 2 + sλ 2 (0,T )×(0,L) ξe -2sϕ |∂ x z| 2 + 1 s (0,T )×(0,L) 1 ξ e -2sϕ |∂ xx z| 2 + |∂ t z| 2 ≤ C (0,T )×(0,L) e -2sϕ ∂ t z + ∂ xx z 2 + Cs 3 λ 4 (0,T )×(a,b) ξ 3 e -2sϕ |z| 2 . (3.8)
Remark that this Carleman estimate is robust with respect to perturbations due to the freedom on the parameters s and λ which can be made arbitrarily large. In particular, one easily checks that the Carleman estimate (3.8) still holds when replacing the right-hand side of (3.8) by

C (0,T )×(0,L) e -2sϕ ∂ t z + ∂ xx z + a(t, x)∂ x z + b(t, x)z 2 + Cs 3 λ 4 (0,T )×(a,b) ξ 3 e -2sϕ |z| 2 , provided a and b belong to L ∞ ((0, T ) × (0, L)) and s ≥ s 1 ( a L ∞ , b L ∞ ) ≥ s 0 .
A Carleman based duality for solving the control problem. According to Theorem 3.1 and the weak formulation (3.4) of the control problem (3.1)-(3.2)-(3.3), it is natural to introduce the functional J defined by

J(z) = s 3 λ 4 2 (0,T )×(a,b) ξ 3 e -2sϕ |z| 2 + 1 2 (0,T )×(0,L) e -2sϕ ∂ t z + ∂ xx z 2 + T 0 L 0 gz, (3.9)
and the norm • obs defined by

z 2 obs = s 3 λ 4 (0,T )×(a,b) ξ 3 e -2sϕ |z| 2 + (0,T )×(0,L) e -2sϕ ∂ t z + ∂ xx z 2
for smooth function z with boundary conditions z(t, 0) = z(t, L) = 0. Note that this defines a norm according to (3.8) and one has an explicit quantification of weighted L 2 (L 2 ), H 1 (L 2 ) and L 2 (H 2 ) norms of z in terms of z obs .

Of course, the set of functions z in C 2 ([0, T ] × [0, L]) satisfying homogeneous Dirichlet boundary conditions is not complete with respect to that norm, and we shall introduce the completion X obs of the set of functions in C 2 ([0, T ] × [0, L]) satisfying homogeneous Dirichlet boundary conditions with respect to • obs .

According to (3.8), the functional J in (3.9) can then be extended continuously on X obs provided

T 0 L 0 ξ -3 e 2sϕ |g| 2 dxdt < ∞. (3.10)
In this case, the functional J is continuous, strictly convex and coercive on X obs . Therefore it admits a unique minimizer Z ∈ X obs and, writing down the corresponding Euler-Lagrange equation, setting Besides, since J(Z) ≤ J(0) = 0, the Carleman estimate (3.8) yields that

U = (∂ t Z + ∂ xx Z)e -2sϕ , V = s 3 λ 4 ξ 3 1 (a,b) Ze -2sϕ , (3.11
s 3 λ 4 Z 2 obs ≤ C T 0 L 0 ξ -3 e 2sϕ |f | 2 dxdt.
Using the identities in (3.11), this implies

s 3 λ 4 T 0 L 0 e 2sϕ |U | 2 + T 0 b a ξ -3 e 2sϕ |V | 2 ≤ C T 0 L 0 ξ -3 e 2sϕ |f | 2 .
Then, using weighted energy estimates on the solution U of (3.1), we can furthermore get weighted estimates on higher norms of U , namely:

s 3 λ 4 T 0 L 0 e 2sϕ |U | 2 + sλ 2 T 0 L 0 ξ -2 e 2sϕ |∂ x U | 2 + 1 s T 0 L 0 ξ -4 e 2sϕ (|∂ t U | 2 + |∂ xx U | 2 ) + T 0 b a ξ -3 e 2sϕ |V | 2 ≤ C T 0 L 0 ξ -3 e 2sϕ |g| 2 . (3.12)
Comments. The above strategy is very useful when dealing with semilinear parabolic type equations. In this case indeed, the strategy consists of doing a fixed point argument, as in our case, which consists of a map û → u in which u solves a control problem corresponding to a source term which is the semi-linear term for û. This is for instance the strategy used for controlling Burgers equations in 1-d, see [START_REF] Fursikov | Controllability of evolution equations[END_REF].

In this case, the main difficulty is to show that the fixed point argument works, and in particular that the map û → u defined that way maps a ball into itself. In order to do this, according to the estimates in (3.12), the natural balls have the following form:

s 3 λ 4 T 0 L 0 e 2sϕ |U | 2 + sλ 2 T 0 L 0 ξ -2 e 2sϕ |∂ x U | 2 + 1 s T 0 L 0 ξ -4 e 2sϕ (|∂ t U | 2 + |∂ xx U | 2 ) ≤ R 2 . (3.13)
Of course, the difficulty then is to get suitable estimates on the source term g in the corresponding weighted space, i.e. on

T 0 L 0 ξ -3 e 2sϕ |g| 2 .
But, due to the form of the weight function exp(sϕ), which blows up exponentially as t → 0 and t → T , even the finiteness of this integral is not at all obvious. Basically, this works fine when the function g contains only quadratic terms in u, but it is more subtle when g contains linear terms, in which case the powers in s and λ may be of particular relevance.

Moreover, the fact that this weight function blows up as t → 0 makes difficult to handle initial data directly by letting in the same time the parameters s and λ free, thus bringing a difficulty to handle semilinearities which contains linear terms. It is then nicer to modify the control problem by introducing an additional source term taking into account the initial data so that the problem reduces to go from 0 to 0. This is precisely what we have done in Section 2 with the introduction of the variables (ρ in , u in ).

In our control problem (2.6)-(2.7), the source term g(ρ, û) contains the linear term ∂ x ρ. We should therefore be very careful to keep the dependence in the parameters s and λ and to get a suitable estimate on

T 0 L 0 ξ -3 e 2sϕ |∂ x ρ| 2 .
But ρ is a solution of an hyperbolic equation which travels along the characteristics of u + u + Λu in , which essentially are the ones of u. We will therefore construct a weight function which follows the characteristics t → x 0 + ut.

Revisiting the approach of A. Fursikov and O. Imanuvilov

The idea is to modify the original approach of A. Fursikov and O. Imanuvilov to solve the control problem (2.6)-(2.7) by taking into account the hyperbolic nature of the equation of the density.

Extension of the domain for the control problem. Our original control problem is given by (2.6)-(2.7). We first extend the spatial domain to (-4uT, L) in order to reformulate the problem with a distributed control localized in (-4uT, -uT ).

The new control problem is then as follows: given a source term g ∈ L 2 ((0, T ) × (0, L)), find a control function v ∈ L 2 ((0, T ) × (-4uT, -uT )) such that the solution u of

(ρ + Λρ in )(∂ t u + u∂ x u) -∂ xx u = g1 (0,L) + v1 (-4uT,-uT ) in [0, T ] × (-4uT, L), (3.14)
with the additional boundary conditions

u(t, -4uT ) = u(t, L) = 0 in (0, T ) (3.15) satisfies u(0, •) = u(T, •) = 0 in (-4uT, L). ( 3

.16)

A new Carleman estimate for the adjoint equation. In order to solve the above control problem, we are going to choose a function (t, x) → ψ(xut) which "follows" the flow. To be more precise, we set ψ ∈ C ∞ (R; R + ) such that

3 ≤ min [-5uT,L] ψ ≤ max [-5uT,L] ψ ≤ 4, max [-3uT,L] ψ ′ < 0 and min [-5uT,-4uT ] ψ ′ > 0. (3.17)
Then, let θ = θ(t) ∈ C 2 ([0, T ]; R + ) be defined by

θ(t) =    t in [0, 2T 0 ] 1 in [3T 0 , T -3T 0 ] T -t in [T -2T 0 , T ], (3.18)
and being such that θ is increasing on [0, 3T 0 ] and decreasing on [T -3T 0 , T ].

We then define ϕ(t, x) and ξ(t, x) as follows:

ϕ(t, x) = 1 θ(t) e 5λ -e λψ(x-ut) , (t, x) ∈ (0, T ) × R (λ > 0), (3.19)
ξ(t, x) = 1 θ(t) e λψ(x-ut) , (t, x) ∈ (0, T ) × R (λ > 0). (3.20)
Note that the critical points of the function ψ in (3.17) belong to (-4uT, -3uT ) and then, for all t ∈ [0, T ], the critical points of the function x → ψ(xut) belong to (-4uT, -2uT ). This is of particular relevance to obtain the following Carleman estimate, whose proof closely follows the one of Theorem 3.1:

Theorem 3.2. Assume that Λρ in is bounded in W 1,∞ ((0, T ) × (-4uT, L)) and that inf (-4uT,L) (ρ + Λρ in ) > 0. Let ψ, θ, ϕ and ξ be defined as in (3.17

19)-(3.20).

There exist s 0 ≥ 1, λ 0 ≥ 1 and C > 0 such that for all s ≥ s 0 and λ ≥ λ 0 , for all smooth function z :

[0, T ] × [-4uT, L] → R satisfying z(t, -4uT ) = z(t, L) = 0, s 3 λ 4 (0,T )×(-4uT,L) ξ 3 e -2sϕ |z| 2 + sλ 2 (0,T )×(-4uT,L) ξe -2sϕ |∂ x z| 2 + 1 s (0,T )×(-4uT,L) 1 ξ e -2sϕ |∂ xx z| 2 + |∂ t z| 2 ≤ C (0,T )×(-4uT,L) e -2sϕ ∂ t ((ρ + Λρ in )z) + ∂ t ((ρ + Λρ in )z) + ∂ xx z 2 + Cs 3 λ 4 (0,T )×(-4uT,-uT ) ξ 3 e -2sϕ
s 3 λ 4 T 0 L -4uT e 2sϕ |U | 2 + sλ 2 T 0 L -4uT ξ -2 e 2sϕ |∂ x U | 2 + 1 s T 0 L -4uT ξ -4 e 2sϕ (|∂ t U | 2 + |∂ xx U | 2 ) + T 0 uT -4uT ξ -3 e 2sϕ |V | 2 ≤ C T 0 L 0 ξ -3 e 2sϕ |ĝ| 2 . (3.23)
Besides, easy multiplier identities yield estimates on the traces of the controlled solution U at x = 0 and x = L:

s 2 λ 3 T 0 ξ -1 e 2sϕ(t,0) |U (t, 0)| 2 dt + λ T 0 ξ -3 e 2sϕ(t,0) |∂ x U (t, 0)| 2 dt + λ T 0 ξ -3 e 2sϕ(t,L) |∂ x U (t, L)| 2 dt ≤ C T 0 L 0 ξ -3 e 2sϕ |ĝ| 2 . (3.24)
We are now in position to introduce the convex set in which u will be looked for:

Y s,λ,Ru = {u such that u(t, L) = 0, t ∈ (0, T ), e sϕ u ∈ L 2 ((0, T ) × (0, L)) with s 3/2 λ 2 e sϕ u L 2 ((0,T )×(0,L)) ≤ R u , ξ -1 e sϕ ∂ x u ∈ L 2 ((0, T ) × (0, L)) with s 1/2 λξ -1 e sϕ ∂ x u L 2 ((0,T )×(0,L)) ≤ R u , ξ -2 e sϕ ∂ xx u ∈ L 2 ((0, T ) × (0, L)) with s -1/2 ξ -2 e sϕ ∂ xx u L 2 ((0,T )×(0,L)) ≤ R u , ξ -2 e sϕ ∂ t u ∈ L 2 ((0, T ) × (0, L)) with s -1/2 ξ -2 e sϕ ∂ t u L 2 ((0,T )×(0,L)) ≤ R u .        , (3.25)
where ϕ and ξ are the weight functions defined in (3.19)-(3.20). Here, R u > 0 is the size of the ball. It will eventually be small enough.

4 Controlling the density

Constructing ρ

Here we explain a natural way to solve the control problem in (2.8)-(2.9).

In order to do that, we assume that u has been constructed as in Section 3 and belongs to some Y s,λ,Ru . Note that R u > 0 will be chosen to be small at the end, so that we can think of u as being small. This in particular implies that the flow

∂ t X(t, τ, a) = u + u(t, X(t, τ, a)) + Λu in (t, X(t, τ, a)), X(τ, τ, a) = a (4.1)
is close to a + (tτ )u.

It follows that t → X(t, 0, 0) runs across the whole domain [0, L] before the time T since T > T u = L/u. Based on this fact we are going to introduce a forward ρ, denoted by ρ f , which takes into account the source term and the initial condition ρ f (0, •) = 0 in [0, L], and a backward ρ, denoted by ρ b , which imposes the goal ρ b (T,

•) = 0 in [0, L].
To be more precise, setting f = f (ρ, û), we define ρ f as the solution of

   ∂ t ρ f + (u + u + Λu in )∂ x ρ f + ρ∂ x u + ρp ′ (ρ)ρ f = f in [0, T ] × (0, L), ρ f (0, x) = 0 in (0, L), ρ f (t, 0) = 0 in (0, T ), (4.2)
and ρ b as the solution of

   ∂ t ρ b + (u + u + Λu in )∂ x ρ b + ρ∂ x u + ρp ′ (ρ)ρ b = f in [0, T ] × (0, L), ρ b (T, x) = 0 in (0, L), ρ b (t, L) = 0 in (0, T ). (4.3)
We then choose T 0 > 0 small enough such that (T -8T 0 )u = L and a small interval (t 1 , t 2 ) ⊂ [3T 0 , 5T 0 ] such that the trajectories t → X(t, t 1 , 0) and t → X(t, t 2 , 0) reach the boundary x = L in times smaller than T -3T 0 , see Figure 1. Note that the choice of (t 1 , t 2 ) can be done independently of R u small enough since R u also bounds the L ∞ -norm of u by classical Sobolev's embedding.

T ρ b ρ f L T -3T0 3T0 t t2 t1
x 0 Figure 1: The geometric configuration. Here, the lines represent the characteristics associate to u starting from t = t 1 , x = 0 and from t = t 2 , x = 0.

We then introduce η the solution of

   ∂ t η + (u + u + Λu in )∂ x η = 0 in [0, T ] × [0, L], η(0, •) = 0 in [0, L], η(t, 0) = η(t) in [0, T ], (4.4)
where η(t) is a smooth function satisfying

η(t) = 0 if t < t 1 , 1 if t > t 2 ,
and we glue ρ f and ρ b along the characteristics using the function η:

ρ(t, x) = ρ f (t, x)(1 -η(t, x)) + ρ b (t, x)η(t, x). (4.5)
By construction, this ρ solves the control problem (2.8)-(2.9).

Getting estimates

The main difficulty then is to get suitable estimates for ρ. Recall that the source term g in the equation of u contains a term of the form ∂ x ρ. According to Section 3, we should show that

T 0 L 0 ξ -3 e 2sϕ |∂ x ρ| 2 < ∞
and give an explicit bound on this quantity. This suggests to consider the equation of ∂ x ρ:

∂ t ∂ x ρ + (u + u + Λu in )∂ x (∂ x ρ) + ∂ x (u + Λu in )∂ x ρ + ρ∂ xx u + ρp ′ (ρ)∂ x ρ = ∂ x f .
Here, assuming that the source term and boundary term will not create any difficulties, we may get bounds on ∂ x ρ in terms of ∂ xx u. But this latter term is too singular to run the fixed point argument since it has the same strength as the principal part of the parabolic operator. This statement can be made more precise by checking that an estimate in ξ -2 e 2sϕ ∂ xx u L 2 given by Section 3 is not sufficient to yield a suitable estimate on ξ -3/2 e 2sϕ ∂ x ρ L 2 to run the fixed point argument.

It is therefore natural to try to get rid of this term ∂ xx u. Remarking that this term also appears in the equation of u, we then combine these two equations and introduce the new variables

µ f (t, x) = u + 1 ρ 2 ∂ x ρ f , µ b (t, x) = u + 1 ρ 2 ∂ x ρ b , (4.6)
which both solve

∂ t µ + (u + u + Λu in )∂ x µ + kµ = h, (4.7)
where the functions h and k can be computed explicitly:

ρh := 1 ρ ∂ x f + ĝ -Λρ in (∂ t u + u∂ x u) + ρ∂ x [u(u + Λu in )] + p ′ (ρ)ρ 2 u, (4.8)
k := p ′ (ρ)ρ + ∂ x (u + Λu in ).
Of course, to determine µ f and µ b completely, we shall also make precise the boundary conditions in space-time: µ f (0, x) = 0 for x ∈ (0, L), µ b (T, x) = 0 for x ∈ (0, L), (4.9)

µ f (t, 0) = m f (t) := u(t, 0) + 1 ρ 2 1 u + u(t, 0) + Λu in (t, 0) f (t, 0) -ρ ∂ x u(t, 0) , (4.10)
µ b (t, L) = m b (t) := 1 ρ 2 1 u + Λu in (t, L) f (t, L) -ρ ∂ x u(t, L) , (4.11)
The equation (4.7) is nicer than the one of ∂ x ρ since the source term h is much less singular than ∂ xx u. Let us also point out that the term ρp ′ (ρ)ρ in f = f (ρ, û) (recall (2.3)) is the one needed so that ∂ x f /ρ + ĝ does not contain any linear term in ∂ x ρ. This explains our perhaps surprising choice of writing the equation (2.1) with the addition in both sides of the equation of the linear term ρp ′ (ρ)ρ.

But one should still be careful when doing the estimates since the boundary conditions contain terms of the form ∂ x u(t, 0) and ∂ x u(t, L).

Also note that the boundary conditions ρ f (t, 0) = ρ b (t, L) = 0 allow to recover ρ f , ρ b directly from the knowledge of µ f , µ b :

ρ f (t, x) := ρ 2 x 0 (µ f -u)(t, y) dy, ρ b (t, x) := -ρ 2 L x (µ b -u)(t, y) dy.
(4.12)

The main difficulty then reduces to get estimates on µ f and µ b .

We now have to get estimates on the solution of a transport equation with a source term, see (4.7). We thus explicitly write the solution µ f (of course, the same can be done with µ b ):

• if x ≥ X(t, 0, 0): h(τ , X(τ , t, x))e -τ t * (t,x) k(τ,X(τ,t,x)) dτ dτ . (4.14)

µ f (t, x) = t 0 h(τ , X(τ , t, x))e -τ 0 k(τ,
We then use the following facts: • the flow X corresponding to the velocity field u + u + Λu in is close to the one corresponding to u:

|X(t, τ, x) -(x + (t -τ )u)| ≤ C|t -τ | u + Λu in L ∞ ,
• the Carleman weight ϕ in (3.19) decreases along the characteristics of the flow corresponding to u while t < T -3T 0 : for all 0 < τ < t < T -3T 0 and x ∈ [0, Lu(tτ )],

ϕ(τ, x) ≥ ϕ(t, x + (t -τ )u).
(This estimate is needed to estimate µ f .)

• the Carleman weight ϕ in (3.19) increases along the characteristics of the flow corresponding to u while t > 3T 0 : for all 3T 0 < τ < t < T and x ∈ [0, Lu(tτ )],

ϕ(τ, x) ≤ ϕ(t, x + (t -τ )u).
(This estimate is needed to estimate µ b .) Note that the two last points should both be true on (3T 0 , T -3T 0 ). This imposes that θ(t) in the Carleman weight function, defined in (3.18), should be constant on (3T 0 , T -3T 0 ).

Other technical estimates (especially one on the Jacobian of the change of variable x → X(t, τ, x)) are also needed that we do not report here but are precisely done in [START_REF] Ervedoza | Local exact controllability for the 1-D compressible Navier Stokes equation[END_REF].

Accordingly, based on the explicit formula (4.13)-(4.14), we can show that And such estimates allow to obtain bounds on e sϕ ξ -3/2 ∂ x ρ f from the ones on u in (3.23) and the fact that û ∈ Y s,λ,Ru . Here, we emphasize that the worst term in (4.15) is the one coming from the boundary m f (t), and more precisely to ∂ x u(t, 0), see (4.10). But there is a gain of λ in the spatial derivative at x = 0 in estimates (3.24), which makes the fixed point strategy work. Also note that, for u ∈ Y s,λ,Ru , e C0sλe 4λ u+Λuin L ∞ ≤ e C0sλe 4λ Rue -inf{ϕ}s/2 e C0sλe 4λ Rin .

sup [0,T -3T0] L 0 |µ f (t, x)| 2 e 2sϕ(t,x) ξ 3 (t, x) dx ≤ Ce C0sλe 4λ u+Λuin L ∞ T -3T0 0 |m f (τ )| 2 e 2sϕ(τ,0) ξ 3 (τ, 0) dτ + Ce C0sλe 4λ u+Λuin L ∞ T -3T0 0
Thus, the first term in the right-hand side is bounded uniformly for R u ∈ (0, 1) and s, λ ≥ 1. Hence there exists a constant C 1 such that for s, λ ≥ 1 and R u ∈ (0, 1), for all u ∈ Y s,λ,Ru ,

e C0sλe 4λ u+Λuin L ∞ ≤ C 1 (1 + O s,λ (R in )), (4.16)
where O s,λ (R in ) is a function which for any s, λ, can be made arbitrarily small by taking R in small enough. Of course, this will impose an order in the choice of the parameters at the end, but this does not prevent the fixed point approach from working.

Remark 4.1. The rigorous proof of Theorem 1.1, though relying exactly on the above ideas, requires a slightly improved form of the estimate (4.15). Indeed, there are quadratic terms in h coming from the initial data, for instance Λρ in ∂ t u (see (4.8)), which are too singular in time and cannot be handled directly as in (4.15). These terms, which we called h 1 in [START_REF] Ervedoza | Local exact controllability for the 1-D compressible Navier Stokes equation[END_REF] and given by ρh

1 (t, x) = - 1 ρ Λρ in ∂ xx û -Λρ in ∂ x û,
require a special treatment based on the following remarks:

• There exists a constant C such that

e sϕ ξ -3/2 t 0 h 1 (τ , X(τ , t, x))e -τ 0 k(τ,X(τ,t,x)) dτ dτ L 2 ≤ Ce C0sλe 4λ u+Λuin L ∞ e 2λ e sϕ ξ -2 h 1 L 2 .
• If u belongs to Y s,λ,Ru , using (4.16) and the explicit form of h 1 ,

Ce C0sλe 4λ u+Λuin L ∞ e 2λ e sϕ ξ -2 h 1 L 2 ≤ C 1 (1 + O s,λ (R in ))e 2λ R u R in ≤ C 2 R u O s,λ (R in ).
• R in will be chosen after the parameters s and λ.

Let us finally remark that this discussion is not needed when getting estimate on µ b on (3T 0 , T ) since h 1 there vanishes.

Getting further in the estimates on ρ can then be done using these estimates on ∂ x ρ and the formula (4.12). We do not give the details of these tedious computations that can be found in [START_REF] Ervedoza | Local exact controllability for the 1-D compressible Navier Stokes equation[END_REF]. We only indicate the set in which ρ will be looking for to run the fixed point argument:

X s,λ,Rρ = {ρ such that ξ -1 e sϕ ρ ∈ L 2 ((0, T ) × (0, L)) with ξ -1 e sϕ ρ L 2 ((0,T )×(0,L)) ≤ R ρ , ξ -3/2 e sϕ ∂ x ρ ∈ L 2 ((0, T ) × (0, L)) with ξ -3/2 e sϕ ∂ x ρ L 2 ((0,T )×(0,L)) ≤ R ρ , ∂ t ρ ∈ L 2 ((0, T ) × (0, L)) with ∂ t ρ L 2 ((0,T )×(0,L)) ≤ R ρ , e s φ/2 ρ ∈ L ∞ ((0, T ) × (0, L)) with e s φ/2 ρ L ∞ ((0,T )×(0,L)) ≤ R ρ , e s φ/2 ∂ x ρ ∈ L ∞ ((0, T ); L 2 (0, L)) with e s φ/2 ∂ x ρ L ∞ ((0,T );L 2 (0,L)) ≤ R ρ , (ξ -3/2 e sϕ ρ)(•, 0) ∈ L 2 (0, T ) with λ 1/2 [ξ -3/2 e sϕ ρ](•, 0) L 2 (0,T ) ≤ R ρ , (ξ -3/2 e sϕ ρ)(•, L) ∈ L 2 (0, T )
with λ 1/2 [ξ -3/2 e sϕ ρ](•, L) L 2 (0,T ) ≤ R ρ ,

                   (4.

The fixed point argument

Of course, everything has been done to guarantee that the fixed point argument runs smoothly. But still, one has to check that for (ρ, û) ∈ X s,λ,Rρ × Y s,λ,Ru , (ρ, u) = F (ρ, û), which is defined as the solutions of the control problems (2.6)-(2.7) for u and (2.8)-(2.9) on ρ, belongs to X s,λ,Rρ × Y s,λ,Ru . Tedious computations (for instance, one should get a bound on the L 2 -norm of e sϕ ξ -3/2 g(ρ, û)) show that this is indeed the case provided R ρ = αR u , where α > 0 is small enough, R u is small enough, the parameters s and λ are large enough and the parameter R in is small enough, see [START_REF] Ervedoza | Local exact controllability for the 1-D compressible Navier Stokes equation[END_REF]. (As indicated above in Section 4 (see also Remark 4.1), this parameter R in , which comes from the initial data, is chosen last.)

We then use Schauder's fixed point theorem. In order to do that, we endow the set X s,λ,Rρ × Y s,λ,Ru with the topology of L 2 ((0, T ) × (0, L)) 2 and show that the map F is continuous on X s,λ,Rρ × Y s,λ,Ru endowed with that topology. Besides, one easily checks that this set is convex, closed, and compact with respect to that topology.

Schauder's fixed point theorem then applies and yields the result. Details can be found in [START_REF] Ervedoza | Local exact controllability for the 1-D compressible Navier Stokes equation[END_REF].

Conclusion

Several questions remain open:

• The initial data in Theorem 1.1 should be in an H 3 × H 3 -neighborhood of the target equilibrium. This regularity is surprising and seems to be a consequence of the fact that the Carleman weight blows up as t → 0. We are currently working on getting Carleman weights for the heat equation with a weight which does not blow up at time t = 0.

• Getting a local exact controllability result around smooth target trajectory should be possible under a suitable geometric condition. A possible way to do that is to include the target flow in the Carleman weight itself. This issue is currently under investigation.

• Our approach is based on the linearized compressible Navier-Stokes equation and consider the nonlinear effects as a perturbation. Of course, another way to proceed would be to think all the way around by using the non-linear effects to control the fluid. This is the idea beyond the return method of J.-M.

Coron [START_REF] Coron | On the controllability of 2-D incompressible perfect fluids[END_REF][START_REF] Coron | Control and nonlinearity[END_REF], which has already been used several times in the control theory of fluid flows. Whether or not these ideas can be applied in the context of compressible Navier Stokes equation is an interesting open problem.

• Our result applies in the 1d case only. Indeed, our method fails to provide estimates on the density in higher dimension. In particular, we did not find so far a quantity similar to µ in (4.6), which we strongly use to get suitable estimates on ∂ x ρ.

• Other controllability issues can be considered. For instance, as far as we know, approximate controllability for such system is completely open.

  ) (U, V ) solves the weak formulation (3.4) of the control problem (3.1)-(3.2)-(3.3). By uniqueness of the solutions of the heat equation in the sense of transposition, (U, V ) solves the control problem (3.1)-(3.2)-(3.3).

  )-(3.18)-(3.

|z| 2 .

 2 (3.21) Solving the control problem. Based on the Carleman estimate (3.21) and following the strategy given in Subsection 3.1, provided g = ĝ := g(ρ, û) satisfies T 0 L 0 ξ -3 e 2sϕ |ĝ| 2 < ∞, (3.22) we get a solution (U, V ) of the control problem (3.14)-(3.15)-(3.16) such that

  , y)| 2 e 2sϕ(τ,y) ξ 3 (τ, y) dτ dy. (4.15)

17

 17

  )where φ(t) := minx∈[0,L] ϕ(t, x) = ϕ(t, 0), t ∈ (0, T )(4.18)and ϕ and ξ are the weight functions given by (3.19)-(3.20).

  X(τ,t,x)) dτ dτ . (4.13)• if x ≤ X(t, 0, 0): in this case, there exists a unique t * (t, x) ∈ [0, t] such that X(t, t * (t, x), 0) = x andµ f (t, x) = m f (t * (t, x))e

	-t t * (t,x) k(τ,X(τ,t,x)) dτ
	t
	+
	t * (t,x)


Ahmad Mazyad

Fabien Teytaud

Cyril Fonlupt

Generating Term Weighting Schemes through Genetic Programming

Term-Weighting Scheme (TWS) is an important step in text classification. It determines how documents are represented in Vector Space Model (VSM). Even though state-of-the-art TWSs exhibit good behaviors, a large number of new works propose new approaches and new TWSs that improve performances. Furthermore, it is still difficult to tell which TWS is well suited for a specific problem. In this paper, we are interested in automatically generating new TWSs with the help of evolutionary algorithms and especially genetic programming (GP). GP evolves and combines different statistical information and generates a new TWS based on the performance of the learning method. We experience the generated TWSs on three well-known benchmarks. Our study shows that even early generated formulas are quite competitive with the state-of-the-art TWSs and even in some cases outperform them.

Introduction

Text Classification (TC) aims to automatically assign a set of predefined categories to a text document based on their content. TC is an important machine learning problem that has been applied to numerous applications such as spam filtering [START_REF] Tretyakov | Machine learning techniques in spam filtering[END_REF], language identification [START_REF] Zissman | Comparison of four approaches to automatic language identification of telephone speech[END_REF], and so on. Generally, the TC approach is to learn an inductive classifier from a set of predefined categories. This approach requires that documents are represented in a suitable format such as the Vector Space Model (VSM) representation [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF].

In a VSM, a document d j is represented by a term vector d j = (w 1,j , w 2,j , ..., w t,j ) where each term is associated with a weight w k,j .

The weight represents how much a term contributes to the semantics of a document. The method which assigns a weight to a term is called Term Weighting Scheme (TWS).

Numerous TWSs exist and we introduce the most famous in Section 2. They are generated according to human a priori and mathematical rules. TWSs are usually simple mathematical expressions. Unfortunately, depending on the application, it is not easy to know a priori which TWS will be effective.

As expression discovery may naturally be addressed by genetic programming [START_REF] Cazenave | Nested monte-carlo expression discovery[END_REF], we are interested in this paper to study the effectiveness of Genetic Programming (GP) generated formulas for term-weighting and their aspects. We are also interested to know if a stochastic evolutionary process with no information about the complexity, the shape and the size of the expression can find at least competitive discriminative TWS.

The paper is organized as follows: Section 2 presents the TWSs and related works. In section 3 we present Genetic Programming and how it is applied to TWS. Section 4 presents the experiments and the results, and then we conclude in section 5.

Term Weighting Schemes

TC is a supervised learning task. Hence, the training data consists of a set of labeled documents D = ((d 1 , l 1 ), ..., (d N , l N )), such that d j is the term vector of j-th document, l j is its label and N is the total number of training documents. As in VSM representation, a document d j is represented by a term vector d j = (w 1,j , w 2,j , ..., w m,j ) where w i,j is a weight assigned to the i-th term of the vocubulary t i of the document d j and determined by the TWS.

Statistical Information

Generally, a multi-labeled classification task is turned into several distinct singlelabel binary task, one for each label, using the binary relevance (BR) transformation strategy. That is, given the list of labels L = {l 1 , l 2 , ..., l m }, the original data set is transformed into m different data sets D = {D 1 , D 2 , ..., D m }. For each data set D k , documents having the label l k will be tagged as the positive category c k , and the rest as the negative category c k . Weights are then computed independently for each binary data set.

Based on the BR transformation, given a term t i and a category c k , TWS could be expressed using statistical information a, b, c and d obtained from the training data:

• a is the number of documents that contain the term t i and belong to the positive category c k .

• b is the number of documents that don't contain t i and belong to c k .

• c is the number of documents that contain t i and don't belong to c k .

• d is the number of documents that don't contain t i and don't belong to c k .

Besides the statistics described above, Table 1 shows different statistical information that could be extracted from the training data.

or log(2 + a * d b * c ) rf log(2 + a max(1,c) ) icf log( C Ct ) ig ( a N × log a×N (a+b)(a+c) ) +( c N × log c×N (c+d)(a+c) ) +( b N × log b×N (a+b)(b+d) ) +( d N × log d×N (c+d)(b+d) )

Term Weighting Schemes

Generally, TWSs combines two of three factors pointed out by Salton et al. in [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF] that are believed to improve both recall and precision:

• Term Frequency (TF) factor : The TF factor is used to capture the relative importance of terms in a document.

• Collection Frequency (CF) factor : Also called term discrimination. The importance of words in a document (TF factor) does not provide enough discrimination ability. A common word like 'The' is frequent in almost all documents, and then it could not separate a group of documents from the remainder of the collection. Hence a discrimination factor is needed to favor those terms that are concentrated in a few documents of the collection. Main known CF factors are presented in Table 2.

TWSs could be divided into two sets depending on whether they make use of available information on document membership (Supervised TWSs) or not (Unsupervised TWSs).

Unsupervised TWSs are generally borrowed from Information Retrieval domain [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF] and adopted for TC [START_REF] Mazyad | A comparative study on term weighting schemes for text classification[END_REF][START_REF] Debole | Supervised term weighting for automated text categorization[END_REF][START_REF] Mazyad | Information gain based term weighting method for multi-label text classification task[END_REF].

Term Frequency-Inverse Document Frequency (TF-IDF) is the most famous term weighting method. This method combines the TF factor and the CF factor and can be formally defined as w i,j = tf i,j × log N Nt where w i,j is the weight of the term t i in the document d j , tf i,j = f i,j is the term frequency represented by the raw count of t i in d j , and log N Nt is the inverse document frequency (idf). Besides the raw count (f t,d ) representation of tf , there exist numerous other variants such as binary representation (w i,j = 1 if the term t i occurs in the document d j and 0 otherwise), log(f i,j ) + 1, f i,j / t ∈d f t ,d . All these variants are also used as TWS on their own [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF][START_REF] Mazyad | A comparative study on term weighting schemes for text classification[END_REF][START_REF] Debole | Supervised term weighting for automated text categorization[END_REF][START_REF] Deng | A comparative study on feature weight in text categorization[END_REF]. The inverse document frequency has also a number of variants such as log(N/N t ) + 1, log((N -N t )/N t ) [START_REF] Salton | Term-weighting approaches in automatic text retrieval[END_REF].

Supervised TWSs makes use of available information on the membership of training documents by replacing the unsupervised idf component in TF-IDF by another supervised component. Debole et al. and Deng et al. in [8,[START_REF] Debole | Supervised term weighting for automated text categorization[END_REF] are the first to take advantage of such information by combining the unsupervised TF component with different supervised term discrimination component: χ 2 (TF-CHI), which makes a test of independence between a term and a category. χ 2 alongside with other supervised feature selection metrics, has been tested in several papers, as a term weighting methods for text categorization. For example, Deng et al. in [START_REF] Deng | A comparative study on feature weight in text categorization[END_REF], replaces the idf factor with χ 2 factor, claiming that TF-CHI is more efficient than TF-IDF. In contrast, in a similar test, Debole et al. in [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF], compare TF-IDF with three supervised term weightings, namely, TF-CHI, Odds Ratio (TF-OR) and Information Gain (TF-IG). The authors have found no consistent superiority of these new term weighting methods over TF-IDF; Information Gain TF-IG [START_REF] Cover | Elements of information theory[END_REF] which measures the amount of information obtained for category prediction by knowing the presence or absence of a term in a document [START_REF] Yang | A comparative study on feature selection in text categorization[END_REF][START_REF] Debole | Supervised term weighting for automated text categorization[END_REF][START_REF] Deng | A comparative study on feature weight in text categorization[END_REF]; Gain Ratio (TF-GR) first used in a feature selection method defined as the ratio between the information gain of two variables and the entropy of one of them [START_REF] Debole | Supervised term weighting for automated text categorization[END_REF]; Odds Ratio (TF-OR) was first used as a feature selection method by Mladeni'c et al. [START_REF] Mladeni'c | Feature selection for classification based on text hierarchy[END_REF]. It is a measure that describes the strength of association between two random variables. A comparative study on term-weighting for TC is made by Deng et al. in [START_REF] Deng | A comparative study on feature weight in text categorization[END_REF]. The study shows a good performance of TF-OR but is outperformed by TF-GR; Relevance frequency (TF-RF) proposed in [START_REF] Lan | Supervised and traditional term weighting methods for automatic text categorization[END_REF], measures the distribution of a term between the positive and the negative category, and favors those terms that are more concentrated in positive category than in negative categories; Inverse Category Frequency (TF-ICF) is a new supervised TWS proposed by Wang et al. in [START_REF] Wang | Inverse category frequency based supervised term weighting scheme for text categorization[END_REF]. The measure aims to favor those terms that appear in fewer categories. More similar methods have appeared in [START_REF] Guru | A novel term class relevance measure for text categorization[END_REF][START_REF] Ibrahim | Term frequency with average term occurrences for textual information retrieval[END_REF][START_REF] Kadhim | Statistical computation and term weighting for feature extraction on twitter[END_REF]. Several comparative studies on these TWSs for both term-weighting and feature selection has been reported in [START_REF] Yang | A comparative study on feature selection in text categorization[END_REF][START_REF] Mladeni'c | Feature selection for classification based on text hierarchy[END_REF][START_REF] Deng | A comparative study on feature weight in text categorization[END_REF][START_REF] Mazyad | A comparative study on term weighting schemes for text classification[END_REF]. A new approach for term-weighting based on (TF-IG) have been proposed for multi-labeled classification task in [START_REF] Mazyad | Information gain based term weighting method for multi-label text classification task[END_REF]. The method computes a score based on all categories and then subtracts it from the original TF-IG weight. The idea is to take into consideration the weights of terms not only in terms of positive and negative categories but also in terms of every single category. Similar approaches have been proposed to learn TWSs via GP in [START_REF] Cummins | Evolving general term-weighting schemes for information retrieval: Tests on larger collections[END_REF][START_REF] Cummins | Evolving local and global weighting schemes in information retrieval[END_REF][START_REF] Cummins | Evolved term-weighting schemes in information retrieval: an analysis of the solution space[END_REF][START_REF] Trotman | Learning to rank[END_REF][START_REF] Oren | Reexamining tf. idf based information retrieval with genetic programming[END_REF][START_REF] Fan | The effects of fitness functions on genetic programming-based ranking discovery for web search[END_REF], however, these studies have focused on information retrieval problem. For TC, a similar approach proposed by Escalante et al. in [START_REF] Escalante | Term-weighting learning via genetic programming for text classification[END_REF]. However our study differs in two ways: first, Escalante et al. try to generate new TWSs by combining existing TWS, and secondly, they learn a single TWS for each data set whereas we learn a TWS for each category in a data set. In our work, we generate TWSs by combining statistical information at a microscopic level to evolve new TWSs. We also extend the study on the thematic TC. We hope this leads into more robust non human based TWSs.

Genetic Programming

Evolutionary computing is based on Darwin's theory of "survival of the fittest". The main scheme of evolutionary algorithms is to evolve a population of individuals that are randomly generated. Each individual represents a candidate solution that undergoes a set of genetic operators that allow to mix and alter partial solutions. One of the key features of evolutionary algorithms is that they are stochastic schemes.

Introduction

GP belongs to the family of evolutionary algorithms. It was first proposed by Cramer [START_REF] Cramer | A representation for the adaptive generation of simple sequential programs[END_REF] and then popularized by Koza [START_REF] Koza | Genetic programming: on the programming of computers by means of natural selection[END_REF]. Unlike genetic algorithms where the aim is to discover a solution, the goal of GP is to find out a computer program that is able to solve a problem.

In GP, a set of random expressions that usually represent computer programs are generated. As in all evolutionary computation algorithms, this set of programs will evolve and change dynamically during the evolution. What makes GP suitable for a number of different applications is that these computer programs can represent many different structures, such as mathematical expressions for symbolic regression [START_REF] Searson | Gptips: an open source genetic programming toolbox for multigene symbolic regression[END_REF], decision trees [START_REF] Koza | Concept formation and decision tree induction using the genetic programming paradigm[END_REF], programs that control a robot [START_REF] Koza | Genetic Programming II, Automatic Discovery of Reusable Subprograms[END_REF][START_REF] Lewis | Genetic programming approach to the construction of a neural network for control of a walking robot[END_REF] to fulfill a certain task or programs that are able to predict defibrillation success in patients and so on.

The quality of a candidate solution (i.e. a program) is usually assessed by confronting it with a set of fitness cases. This step is usually the most time-consuming step as the programs may get huge and several thousands of candidate programs are usually evaluated at each generation. These computer programs will undergo one or several evolutionary operators that will alter in a hopefully beneficial way. The most classical evolutionary operators are usually the crossover operator that allows the exchange of genetic material (in our case subtrees) and the mutation operator that allows a small alteration to the program.

In the most conventional GP approach, programs are usually depicted by trees. In GP terminology, the set of nodes are split into two sets, inner nodes of the tree are drawn from a set of functions while the terminal nodes (leaves) are drawn from a so-called terminal set. Depending on the problem, the set of functions can be mathematical functions, boolean functions, control flow functions (if,...), or any functions that may be suitable to solve the given problem. The terminal set is usually the set of inputs of the problem, e.g., parameters and constants for symbolic regression problems, sensors for robot planning, etc.

When the stopping criterion is reached, the best individual is returned, otherwise, the loop continues and the best individuals are selected (according to their fitness). There exist numerous ways for selecting the population, the mutation and the crossover operators. This is beyond the scope of this paper and the reader can refer to [START_REF] Koza | Genetic programming: on the programming of computers by means of natural selection[END_REF][START_REF] Karakus | Function identification for the intrinsic strength and elastic properties of granitic rocks via genetic programming (gp)[END_REF] for more information.

Evolving Term Weighting Scheme using Genetic Programming

A CF factor is a combination of statistical information. It is intended to measure the discriminative power of a term, i.e. it tells how much a term is related to a certain category. These statistics combined by means of mathematical operators and functions. We are interested in automatically evolving a CF factor (an individual) using GP. In our approach, the learned CF factor combined to the TF factor forms a term weighting method.

In our context of automatically evolving term weighting methods, an individual is a combination of the function set that is built with simple arithmetical operators (+,-,*,/,log,...) and the terminal set (constant values and inputs to our problem).

Table 1 shows the statistical information used as terminal set for generating formulas which represent CF factors. As it can be seen, the function set is made of very simple arithmetical functions while the terminal set includes to the best of our knowledge all the statistical information used to build a TWS.

As previously mentioned, programs (generated TWS) are depicted as trees. In this problem, the terminal nodes consist of statistical information extracted from training data, while the inner nodes are a set of defined operators that combines the statistical information to form a new TWS.

Terminals and Function Set

In this study, we try to generate new TWS by evolving the CF factor and then combines it with the TF factor. The CF factor is a combination of constants, statistical information (N , N t ,...), and mathematical operators. Hence we define the terminals as the statistical information shown in Table 1. Regarding the mathematical operators, they are defined as one of the following (+, -, /, * , √ x, log1(x) = log(1 + x) and log2(x) = log(2 + x)).

We should note that the statistical information has different types (single value, vector, and matrix). For instance, the number of documents in the training data N is a constant (single value), the number of documents that contains a term t is a vector containing the number of documents for each term and finally, the number of documents that belongs to a category cat and contains a term t is a matrix. Operations on these different types of statistical information are taken care of by Eigen1 library using element-wise transformations.

Genetic Operators

In GP, a set of individuals is initialized and then evolved according to a set of genetic operators. At first, we randomly generate a random size individuals with a max size of twenty genes (the max size could be overpassed during the cross-over operation). As for genetic operators, we use the elite selection and reinsertion, a subtree crossover with a probability of 0.85 and one point mutation with a probability of 1/size of the individual.

Fitness Function

Generally, the performance of a TWS is assessed on known benchmarks by evaluating a classification model on VSM representation of this TWS. Numerous evaluation metrics exist that evaluate the classification model such as f 1 measure. Evaluating the classification model is a vital step that affects the performance of the GP. However, it could be very time-consuming. Hence, it is important to choose a good and fast machine learning algorithm. LibLinear [START_REF] Fan | Liblinear: A library for large linear classification[END_REF] is an open source library for large-scale linear classification. It supports linear support vector machines.

In our study, once a new individual is generated, we perform a 3-fold crossvalidation on the training data which generates three disjoint subsets. We use two subsets as the training set and one subset as the test set. The process is repeated three times using each time different subset for testing. The performance is measured using the f 1 measure. The average classification performance is used as the fitness function. The f 1 measure considers both precision p (true positive over true positive plus false positive) and recall r (true positive over true positive plus false negative) and can be formally defined as f 1 (p, r) = 2rp r+p .

Experiments and Results

This section presents an empirical evaluation of the proposed approach. The goal of this study is to assess the effectiveness of the generated TWSs and compare their performances to standard TWSs. The souce code of the implentation needed for our experiments could be found in a public repository2 .

Experimental setup

In our experiments, we have used three widely well-known benchmarks in TC: Reuters-21578 Benchmark Corpus3 , Oshumed Benchmark Corpus 2 and the 4

Universities data set also called Webkb4 . The Reuters-21578 data set is one of the most used test collection for TC research. We use the well-known "Apte-Mod" split [START_REF] Joachims | Text categorization with support vector machines: Learning with many relevant features[END_REF]. This version of the data set contains ninety categories, however, in our experiments, we report results only for the largest ten categories. Oshumed dataset is extracted from the Oshumed 1 collection compiled by William Hersh. It includes 13,929 medical abstracts from the MeSH categories of the year 1991. Each document in this data set belongs to one or more categories from 23 cardiovascular diseases categories. Webkb data set contains WWW-pages collected from computer science departments of various universities in January 1997 by the World Wide Knowledge Base (Webkb) project of the CMU text learning group. In this experiment, we kept only the four largest categories ("student", "faculty", "course" and "project"), and we split it into three random folds where two folds are used for the training set and one fold for the test set. For all three data sets considered in the experiments, a default list of stop words, punctuation and numbers are removed, lower case transformation and Porter's stemming are performed.

Furthermore, for each experiment, a binary transformation is applied. That leads to multiple distinct single-label binary task, one for each label (see Section 2.1). Each task could be treated as an independent experiment with its own data set.

As mentioned above, each data set has been split into training and test subsets. Table 4 shows, for each data set, the number of documents in the training and test subsets, the number of classes, the number of terms, the size of smallest category and the size of the largest category. TWSs are evolved using the training subset (see Section 3.2.3). Finally, the test subset is used to evaluate the performance of the generated TWS. And finally, for each data set, we report the f 1 measure (see Section 3.2.3).

In order to obtain more reliable results, we have performed 20 runs on each task. After having evaluated the generated TWSs, we report the performance average and standard deviation over the 20 runs. In addition, we report the maximum and minimum f 1 score obtained across the 20 runs (for each run, only the last generated TWS is taken into account).

Tables 5,6 and 7 show the results obtained by the generated TWSs and the best baseline using linearSVM. Table 8 shows the average classification performance of the generated TWSs on the test subset of the training data (Validation) and the performance on the test data (Test). The goal of this experiment is to assess the learning ability and to warn us of eventual overfitting. Table 9 shows the average classification performance of a random learned TWS for a singlelabel binary task on the complete data set. This is important in order to know whether our GP-Based TWS has good generalization performances.

Results

First, a fast study of the Tables 5,6 and 7 shows that the best baseline TWS is different for each binary task. Therefore, a multi-labeled task requires different TWSs for each category. Using different TWSs could lead to better results. However, the problem is to recognize the best TWS for a specific task. Finding the TWS by cross-validation does not mandatory return the best TWS.

Regarding Reuters-21578, the generated TWSs and the baseline schemes have similar performances. However, on Oshumed and Webkb data sets, the GP-Based TWSs outperform the best baseline schemes. Reuters-21578 is one of the most studied data-set in TC for TWS making the task of finding better TWS harder. Moreover, it is the most unbalanced data set in the study which makes generalization harder. From Table 8 , we can see that the performance of generated TWSs on the test subset of the training data during the cross-validation (See Section 3.2.3) is very similar to the performance on the test data. In addition, the standard TWSs have different results. This is interesting as it suggests that there is no overfitting and that further learning can improve the performance. 9, we can see that the average performance (macro-f 1 ) of the generated TWSs outperforms the best baseline on the three corpora which means that the three learned TWS have good generalization performance.

Finally, compared to the results obtained in [START_REF] Escalante | Term-weighting learning via genetic programming for text classification[END_REF] on Reuters-21578 and Webkb, we have similar results. Note that, in [START_REF] Escalante | Term-weighting learning via genetic programming for text classification[END_REF], they used Reuters-10 data set which contains only documents from the top 10 categories of the Reuters-21578 data set, whereas we use Reuters-21578 "ModApte" split which contains documents from 90 categories.

Conclusion

In this paper, we have studied the benefits of using genetic programming for generating term-weighting schemes for text categorization. Unlike previous studies, we generate formulas by combining statistical information at a microscopic level. This kind of generation is new, and we can conclude that :

• Different data sets require different formulas. This means that having a good generic formula is really hard to find.

• Within a corpus, it is even better to use a different formula for each category. The hard task is to find out the best for each one.

• Genetic programming is able to find very good formulas which outperform standard formulas given by experts in the literature.

• Eventually, even if the generated formula is specific to a given category, results show that the best formula for one category is generic enough to be good (but not best) for other categories.

χ 2 N

 2 * (a * d-b * c) * (a * d-b * c) (a+c) * (b+d) * (a+b) * (c+d)

Table 1 :

 1 Statistical information (Terminals) used to evolve a TWS. Label Description N # documents C # categories C t # categories that contain the term t N t # doc that contain t N t # doc that do not contain t N cat # doc in the positive category cat N cat # doc that do not belong to cat

Table 2 :

 2 Six traditional CF factors. CF Defined by

Table 3 :

 3 Parameters used in our genetic program.

	Parameter	Value
	Population Size	100
	Initial Individual Size	20
	Number of generations 100 Function set +, -, /, * ,	√ x, log1(x), log2(x)
	Terminal set	a, b, c, d, N , Nt, Nt, Ncat, Ncat, C, Ct
	Mutation	OnePointMutation (P = 1/individual size)
	CrossOver	SubtreeCrossover (P = 0.85)

Table 4 :

 4 Statistics on the selected data sets used for our experiments (training/test).

		Reuters	Oshumed	Webkb
	number of documents	7769/3019 6286/7643 2803/1396
	number of classes	90	23	4
	number of terms	26000	30198	7890
	size of the smallest category 1/1	65/70	336/168
	size of the largest category	2877/1087 1799/2153 1097/544

Table 5 :

 5 Classification performance on top 10 categories of Reuters-21578 obtained with the generated TWSs and the best standard TWS.

	Best results are

Table 6 :

 6 Classification performance on Oshumed data set obtained with the generated TWSs and the best baseline of the standard TWSs.

			GP		Best TWS
	L	f1	Min	Max	f1	TWS
	C01 68.19±1.00 65.91 70.71 64.36	tf.or
	C02 41.28±1.20 38.45 43.51 36.38	tf.or
	C03 76.54±3.28	72.03 81.21 78.23 tf.or
	C04 80.06±1.48	77.67 81.72 80.06 tf.chi
	C05 59.48±0.20 59.05 60.59 52.85	tf.or
	C06 73.99±1.29 71.49 75.76 71.44	tf.or
	C07 41.40±3.35 34.86 47.45 32.6	tf.or
	C08 63.97±2.51 59.13 67.69 61.34	tf.or
	C09 53.75±2.63 50.85 58.43 48.00	tf.or
	C10 57.00±2.33 51.05 59.53 50.2	tf.rf
	C11 67.78±1.06 65.52 69.23 66.67	tf.or
	C12 76.72±1.10 73.52 78.25 72.86	tf.or
			GP		Best TWS
	L	f1	Min	Max	f1	TWS
	C13 66.48±0.47 64.72 67.92 63.70	tf.or
	C14 80.08±0.39 79.22 80.55 77.11	tf.idf
	C15 65.98±0.71 64.16 67.20 61.53	tf.chi
	C16 33.54±0.89 31.14 35.41 28.00	tf.or
	C17 64.85±0.90 61.87 66.87 59.24	tf.chi
	C18 61.21±1.50	57.50 65.12 61.22 tf.or
	C19 41.60±2.04 38.23 45.01 39.84	tf.or
	C20 71.61±0.28 70.96 72.07 69.62	tf.or
	C21 65.55±0.32 64.18 67.56 64.37	tf.chi
	C22 10.31±0.12 8.33	14.37 4.21	tf.or
	C23 46.77±0.08 45.59 47.20 46.15	tf.idf
	Avg 59.48±1.26 56.76 61.89 56.08
	From Table

Table 7 :

 7 Classification performance on Webkb data set obtained with the generated TWSs and the best baseline of the standard TWSs. 29±0.5 89.05 90.90 90.11 tf.rf faculty 86.62±0.1 85.69 87.81 86.21 tf.rf project 80.82±0.6 77.48 81.76 80.25 tf.rf course 94.47±0.3 93.86 96.08 93.56 tf.rf Avg 88.05±0.4 86.52 89.14 87.53

			GP		Best TWS
	L	f1	Min	Max	f1	TWS
	student 90.

Table 8 :

 8 Average classification performance for validation phase and test phase.

		Validation Test
	Reuters	89.15±0.4 87.48±0.7
	Oshumed 59.74±0.9 59.48±1.3
	Webkb	87.74±0.3 88.05±0.4

Table 9 :

 9 Average classification performance of random TWS learned for a singlelabel task on its corresponding data set and the best baseline. The selected TWS is randomly chosen between the best generated TWSs for each category. Best Reuters * * C * //acN log2c C C * C * ( a c * N * log(2 + c)) 86.88 85.92 tf.rf Oshumed /d/ + N t log2 C t a

			GP-Based		Baseline
	Data Set Prefixed formula	TWS	f 1	f 1
			a d * (Nt+log(2+Ct))	60.30 57.10 tf.chi
	Webkb	log1 log2 a	log(1 + log(2 + a))	88.43 87.53 tf.rf

http://eigen.tuxfamily.org/

https://bitbucket.org/mazyad/eigennlp

http://disi.unitn.it/moschitti/corpora.htm

http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/