Antoine Henrot

Michel Pierre

Mounir Rihani

Positivity of the shape Hessian and instability of some equilibrium shapes

Keywords: Shape Optimization, Domain Variations, Shape Hessian, Stability, Energy Functionals, Dirichlet Problem. Mathematics Subject Classification: 49Q10, 49K40, 49Q12, 35J25

published or not. The documents may come

Positivity of the shape Hessian and instability of some equilibrium shapes

Introduction

In this paper, we are interested in studying the positivity of the second derivative of some shape functionals at equilibrium shapes. We also exhibit some simple functionals for which strict positivity may not imply that these equilibria are local minima.

We mainly consider shape functionals involving at the same time geometric terms, like the perimeter or the measure of the shape, and also the solution of the Dirichlet problem on these shapes. We concentrate on minimization problems with prescribed measure (frequent in applications). Thus, we discuss the positivity of the second derivative of the following two-dimensional functional, defined on open subsets ω of 2 ω ⊂ 2 → E(ω) = J(ω) + τ P (ω) -ΛS(ω), (1.1) where τ > 0, Λ ∈ , S(ω) denotes the Lebesgue measure of ω, P (ω) denotes the perimeter of ω and J(ω) = ω 1 2 |∇u ω | 2 -f u ω is the Dirichlet energy associated with the solution of the Dirichlet problem

u ω ∈ H 1 0 (ω), -∆u ω = f in ω, (1.2)
and f : 2 → is a given function. Here, the constant Λ is to be understood as a Lagrange multiplier for the minimization of J(ω) + τ P (ω) among the sets with prescribed measure S(ω) = S 0 . Note that, according to (1.2)

J(ω) = - 1 2 ω |∇u ω | 2 = - 1 2 ω f u ω . (1.3)
We are interested in the positivity of the second derivative of E(•) around critical shapes, that is shapes Ω for which the solution of (1.2) satisfies also

1 2 |∇u Ω | 2 -τ C + Λ = 0 on ∂Ω, (1.4)
where C denotes the curvature of ∂Ω. This is the Euler-Lagrange equation of the considered minimization problem (see Section 2). We will prove that, under natural assumptions, any convex equilibrium is "stable" in the sense that its second derivative is strictly positive. This remains true for shapes close to convex shapes (see Section 3). Besides this kind of results, the study of the positivity of the second derivative is interesting for itself: it involves a peculiar quadratic form on a space of functions defined on the boundary of Ω (here H 1 (∂Ω)). Note that stability analysis had been made for this problem in the case τ = 0 ("no surface tension") in [START_REF] Descloux | Stability of the solutions of the bidimensional magnetic shaping problem in absence of surface tension[END_REF], [START_REF] Descloux | A stability result for the magnetic shaping problem[END_REF].

Unfortunately, in shape optimization, when positivity or "coercivity" occurs, it generally does in a weaker norm than the norm for which the functional is actually twice differentiable. In the examples above, coercivity occurs in H 1 while second order Taylor formulas are valid only in spaces like C 2 or even C 2,α . In general, this is not sufficient to guarantee that there is a local minimum, even in the stronger norm. However, for shape optimization of the type considered here, the situation is slightly better and, as proved in [START_REF] Dambrine | About stability of equilibrium shapes[END_REF], [START_REF] Dambrine | On variations of the shape Hessian and sufficient conditions for the stability of critical shapes[END_REF], positivity does imply existence of a strict local minimum with respect to the stronger norms of C 2 -type, whence the interest of studying positivity. It is likely that this minimum is local for a weaker norm, but it is not yet understood how much "weaker" this norm may be.

As a contribution to the latter question, we give next "bad" examples where positivity of the second derivative occurs while "small" perturbations may strictly decrease the energy. This is done for simple functionals of the form F (ω) = ω g(u ω ) and around circles. Perturbations, although "small", are rather irregular since they consist in modifying the circle into "close" annuli. In particular, they cannot be represented as normal perturbations to the circle. This says that the second classical shape derivative does not provide all information about existence of minima and should probably include extra information coming from the so-called topological derivative (see e.g. [START_REF] Nazarov | Asymptotic Analysis of shape functionals[END_REF]).

Section 2 is devoted to the computation of the second derivatives of the functionals of type (1.1). This is not a quite easy step in general. We mainly refer to [START_REF] Novruzi | Structure of shape derivatives[END_REF] where the structure of any second shape derivative is given. This a priori knowledge helps quite a lot for the computations. Section 3 concerns the study of the positivity of the second derivative of the functionals (1.1). Section 4 concerns the particular case where the equilibrium shape is a disk (in which case a more complete analysis may be made). Section 5 describes two examples where strict positivity does not imply existence of a local minimum.

Computation of the second derivative of E(•)

We consider the functional E(•) given by (1.1-1.2) and we assume that f is regular (to make it simple, we will assume that it is at least bounded and in C 1 ( 2 )). As proved in several places (see e.g. [START_REF] Descloux | A stability result for the magnetic shaping problem[END_REF], [START_REF] Descloux | Stability of the solutions of the bidimensional magnetic shaping problem in absence of surface tension[END_REF], [START_REF] Sokolowski | Introduction to shape optimization[END_REF], [START_REF] Murat | Sur le contrôle par un domaine géométrique[END_REF]), this functional is twice differentiable around regular enough shapes Ω. Sharp differentiability may be obtained in Hölder spaces of type C 2,α , α ∈ (0, 1). Since, we are mainly interested here in structures of derivatives, we will make it simple and work in C 3 -spaces. We denote by Θ 3 the space of functions θ ∈ C 3 ( 2 , 2 ) whose derivatives up the the third order are bounded. This space is equipped with its natural norm. Then the mapping

E : θ ∈ Θ 3 → E (I + θ)(Ω) , (2.1)
is twice differentiable at θ = 0 (here I denotes the identity in Θ 3 ). We will compute these derivatives around a regular shape Ω that we will assume to be a bounded open subset of 2 with regular boundary Γ = ∂Ω, say of class C 5 at least. For this, let us first recall the structure of the first and second (Fréchet) shape derivatives in general. It is well-known for first derivatives from the pioneer paper by Hadamard [START_REF] Hadamard | Mémoire sur le problème d'analyse relatif à l'équilibre des plaques élastiques encastrées[END_REF]. It may also be found for the second derivative under different forms in several papers (see [START_REF] Murat | Sur le contrôle par un domaine géométrique[END_REF], [START_REF] Simon | Differentiation with respect to the domain in boundary value problems[END_REF], [START_REF] Delfour | Velocity Method and Lagrangian Formulation for the Computation of the Shape Hessian[END_REF], [START_REF] Bucur | Anatomy of the Shape Hessian Via Lie Brackets[END_REF], [START_REF] Sokolowski | Introduction to shape optimization[END_REF], [START_REF] Novruzi | Structure of shape derivatives[END_REF]). Here, we use the notations and results of [START_REF] Novruzi | Structure of shape derivatives[END_REF], Theorem 2.1 and Corollaries 2.4,2.9. We state it for our functional E(•), but it is the same for any regular functional. We denote by ν the normal unit exterior derivative to Γ = ∂Ω. The Fréchet-derivatives of E(•) at θ = 0 will be described by their action on arbitrary regular displacements ξ, η ∈ Θ 3 . Lemma 2.1 There exists a continuous linear map l 1 from C 3 (Γ) into such that, for all ξ ∈ Θ 3 ,

E (0)(ξ) = l 1 (ξ • ν).
There exists a continuous bilinear symmetric map l 2 from C 3 (Γ) × C 3 (Γ) into such that for all ξ, η ∈ Θ 3 ,

E (0)(ξ, η) = l 2 (ξ • ν, η • ν) -l 1 (ξ τ • D τ ν η τ + ν • D τ ξ η τ + ν • D τ η ξ τ ),
where ξ τ = ξ -(ξ • ν)ν denotes the tangential component of ξ and where D τ ξ = D(ξ τ ) denotes the matrix of the derivatives of ξ τ .

If Ω is a critical shape, that is l 1 = 0, then the second derivative depends only on l 2 and on the normal components of the displacements of ξ, η at the boundary Γ. It is also the case for any Ω if ξ, η are normal to Γ (since ξ τ = η τ = 0). As a consequence of this structure theorem, to obtain full information on derivatives, it is sufficient to identify l 1 , l 2 . This may be done by using specific variations of the form t → E(Ω t ) where t tends to 0 and where the Ω t 's are well-chosen perturbations of Ω (chosen to allow as simple computations as possible).

One may for instance choose Ω t = T t (Ω) where T t : 2 → 2 is defined as follows and based on displacements which are normal to Γ: For any regular function h : Γ → , we denote by h a regular extension of h to 2 and by ν a regular unitary extension of ν to 2 (see e.g. [START_REF] Gilbarg | Elliptic Partial Differential Equations of Second Order[END_REF] for details). Now set ∀x ∈ 2 , ∀t ≥ 0 :

T t x = x + t h(x) ν(x), Ω t = T t (Ω), e(t) = E(T t (Ω)) = E(Ω t ).
(2.2)

Then, since e(t) = E(t h ν), by the chain rule and Lemma 2.1, we obtain

e (0) = l 1 (h), e (0) = l 2 (h, h). (2.3)
Now, we can describe explicitly e (0), e (0) in our case. We use the following notations:

u = u Ω , β = ∇u • ν = ∂u/∂ν.
We denote by h the derivative with respect to the length parameter on Γ and by D is the pseudo-differential operator on Γ which, to each regular function h : Γ → , associates the trace on Γ of ∂H/∂ν where H is the harmonic extension of h to Ω. In particular, we have

Γ hDh = Ω |∇H| 2 . (2.4)
It easily follows from this identity that D extends to a continuous operator from H 1/2 (Γ) into H -1/2 (Γ). Recall also that C denotes the curvature of Γ seen from inside Ω.

Theorem 2.2 e (0) = l 1 (h) = Γ (- 1 2 β 2 + τ C -Λ)h, (2.5)
e (0) = l 2 (h, h) = Γ βhD(βh) + (Cβ 2 /2 -ΛC + f β)h 2 + τ h 2 . (2.6) Remark 2.1
If Ω is a critical shape for ω → J(ω) + τ P (ω) (see 1.1) under the constraint S(ω) = S 0 , then there exists a real number Λ such that l 1 ≡ 0, that is

- 1 2 β 2 + τ C -Λ = 0 on Γ, (2.7)
which is the relation (1.4) announced in the introduction (note that, since u = 0 on Γ, then |∇u| = |∂u/∂ν| = |β|). In (2.6), we may replace β by its expression given in (2.7). As a consequence, around an equilibrium, the expression of e (0) depends only on the geometry of Ω, on Λ and on the data τ, f .

The result of Theorem 2.2 will be obtained by differentiating each of the three terms in the total energy E. Most of the needed computations are available in the literature under various forms. We will mainly refer to [START_REF] Novruzi | Structure of shape derivatives[END_REF] where the three terms of our functional E(•) are considered and we will indicate the necessary additional information.

Proof of Theorem 2.2: According to Lemma 2.1, let us denote by l S i , l P i , l M i , i = 1, 2 the linear and bilinear forms respectively describing the first and second derivatives of each of the functionals

Ω → S(Ω), P (Ω), Ω |∇u Ω | 2 .
Note that, by (1.1), (1.3), for i = 1, 2

l i = -Γ |∇u| 2 h, l M 2 (h, h) = Γ -2ω(h) ∂ω(h) ∂ν + h 2 [2 ∂u ∂ν ∂ 2 u ∂ν 2 + C( ∂u ∂ν ) 2 ],
where ω(h) is the solution of

∆ω(h) = 0 in Ω, ω(h) = -h ∂u ∂ν on Γ.
(2.10) Formula (2.5) follows from these expressions together with (2.8), as well as formula (2.6) with the extra help of the following technical lemma:

Lemma 2.3 |∇ τ h| 2 = h 2 , (2.11
)

ω(h) ∂ω(h) ∂ν = βhD(βh), (2.12
)

∂u ∂ν ∂ 2 u ∂ν 2 = -Cβ 2 -f β. (2.

13)

Proof: To obtain (2.11), recall that the tangential gradient is given by

∇ τ h = ∇ h -(∇ h • ν) ν.
Let s → X(s) be a parametrization of Γ in terms of the length parameter s.

Then, X (s) is a unit vector tangent to Γ at X(s) so that

∇ τ h • X (s) = ∇ h • X (s) = d d s h(X(s)) = d d s h(X(s)),
and

|∇ τ h| 2 = |∇ τ h • X (s)| 2 = h (s) 2 if we simply set h(s) = h(X(s)).
For (2.12), we introduce the solution u t of the Dirichlet problem:

-∆u t = f in Ω t , u t = 0 on ∂Ω t or u t (T t (x)) = 0 on Γ. (2.14)
By differentiating this system with respect to t at t = 0, we obtain

∆(∂ t |t=0 u t ) = 0 in Ω , ∂ t |t=0 u t = -h ∂u ∂ν on Γ. (2.15)
It follows that:

∂ t |t=0 u t = ω(h)
and ∂ω(h)/∂ν = D(-βh), whence (2.12).

To obtain (2.13), we may argue as in [START_REF] Descloux | Stability of the solutions of the bidimensional magnetic shaping problem in absence of surface tension[END_REF], [START_REF] Descloux | A stability result for the magnetic shaping problem[END_REF]) using local coordinates. Assume that (0, 0) ∈ Γ and Γ is defined as the graph of a regular fonction θ : ] -η, η[→ satisfying θ(0) = θ (0) = 0. Moreover, Ω is locally below the graph of θ (so that ∂/∂ν = ∂/∂y). Then, differentiating twice u(x, θ(x)) = 0 with respect to x, we obtain:

u x (x, θ(x)) + u y (x, θ(x))θ (x) = 0, u xx (x, θ(x)) + 2 u xy (x, θ(x))θ (x) + u yy (x, θ(x))θ 2 (x) + u y (x, θ(x))θ (x) = 0.
We deduce that at x = 0 (recall that u is at least C 2 ) u xx (0, 0) + u y (0, 0)θ (0) = 0 which, together with -∆u = f on Ω implies that, on the boundary

∂u ∂ν ∂ 2 u ∂ν 2 = u y u yy = u y (-u xx -f ) = (u y ) 2 θ (0) -f u y .
Since C is the curvature of Γ seen from below, we have C = -θ (0) at the origin, whence (2.13).

Positivity of second derivative

We use here the notations of Section 2. Let (Ω, u = u Ω ) be a regular equilibrium (or a critical shape) for the minimization of

ω → J(ω) + τ P (ω) = - 1 2 ω |∇u ω | 2 + τ P (ω)
under the constraint S(ω) = S 0 where S 0 is given. This means that there exists a real number Λ (a Lagrange multiplier) such that the derivative of E(•) = J(•) + τ P (•) -ΛS(•) vanishes at Ω. With the previous notations and definitions (1.1,2.1), we have E (0) = 0: according to Section 2, this means that (2.7) holds on Γ = ∂Ω, that is

β 2 = 2(τ C -Λ).
A necessary second order condition: Assume now that J(•) + τ P (•) has a local minimum at Ω among the regular domains ω satisfying the measure constraint S(ω) = S 0 . Then θ ∈ Θ 3 → (J + τ P )((I + θ)(Ω)) has a minimum at θ = 0 on the manifold of θ's such that S (I + θ)(Ω) = S(Ω). As a consequence, the second derivative of the full Lagrangian θ → (J + τ P -ΛS) (I + θ)(Ω) is nonnegative on the hyperplane of linearized constraints, that is on {ξ ∈ Θ 3 ; Γ ξ• ν = 0}. This means that, for all h ∈ C 3 (Γ) such that Γ h = 0, the quadratic form

Q(h) = Γ βhD(βh) + (τ C -2Λ)Ch 2 + f βh 2 + τ h 2 (3.1)
is nonnegative.

Remark 3.1 Since Ω is bounded and regular, we may assume that its boundary is the union of disjoint regular Jordan curves Γ i , i = 1, ...p (a Jordan curve is, by definition, the one-to-one continuous image of the unit circle; in particular, it is a closed curve). Choosing in (3.1) test-functions h vanishing on all Γ i but one, we obtain that, for all i = 1, ...p and for all h ∈ C 3 (Γ i ) with Γi h = 0, we have

Q i (h) = Γi βhD(βh) + (τ C -2Λ)Ch 2 + f βh 2 + τ h 2 ≥ 0. (3.2)
Remark 3.2 In the expression of Q i , we must remember that the operator D depends on the set Ω and not only on Γ i . Note that, by (2.4) and classical Poincaré inequality, there exists δ > 0, depending only on Ω, such that

∀ h ∈ Z 1 0 (Γ), Γ h Dh = Γ |∇H| 2 ≥ δ h 2 L 2 (Γ) . (3.3)
Therefore, the contribution of the term h Dh helps making Q positive in any case.

The coercivity question: We will now concentrate on the study of the positivity of the quadratic form h → Q(h) for functions h satisfying Γ h = 0 when Γ is a regular Jordan curve. Then Ω is the simply connected interior of Γ. Obviously, Q(•) is continuous on the functional space H 1 (Γ) and the H 1norm clearly appears as the "optimal" one for this continuity and also for the question of positivity or "coercivity". Therefore, the natural question is to decide whether or not Q(•) is coercive on the space

Z 1 0 (Γ) = {u ∈ H 1 (Γ) : Γ h = 0} that is ∃η > 0; ∀h ∈ Z 1 0 (Γ), Q(h) ≥ η h 2 H 1 (Γ) . (3.4)
As explained in the introduction, if H 1 -coercivity holds, then the functional J(•) has a strict local minimum at Ω at least in a C 2,α -topology, i.e. among C 2,α -perturbations of Ω preserving the volume.

We will mainly concentrate on the case where S {x ∈ 2 ; u Ω (x) = 0 a.e. } = S(Ω) = S 0 , f is compactly supported in Ω, Γ is a regular Jordan curve with interior Ω.

   (3.5)
The first condition is just a way to say that the constraint S(Ω) = S 0 is "saturated", otherwise we would work with the smaller open subset Ω = {x ∈ 2 ; u Ω (x) = 0}. The second condition is natural in applications (see [START_REF] Henrot | Un problème inverse en formage de métaux liquides[END_REF], [START_REF] Descloux | Stability of the solutions of the bidimensional magnetic shaping problem in absence of surface tension[END_REF], [START_REF] Descloux | A stability result for the magnetic shaping problem[END_REF], [START_REF] Crouzeix | Variational approach of a magnetic shaping problem[END_REF]). More comments will be made later on the case where f does not vanish around Γ (see Remark 3.7).

Two families of situations: It turns out that there will be two rather different families of situations: indeed, the equilibrium condition (2.7) writes

τ C -Λ = 1 2 |∇u| 2 ≥ 0 on Γ, (3.6)
so that, if

C m := min Γ C, then τ C m ≥ Λ.
But the situation will be different depending on whether this inequality is strict or not. If there exists a point of Γ at which ∇u = 0, then necessarily τ C m = Λ. This is necessarily the case if, for instance, Ω f = 0 (Γ being a Jordan curve). Indeed, if ∇u did not vanish on Γ, then, we would have

Γ |∇u| = | Γ ∇u • ν| = | Ω ∆u| = | Ω f | = 0,
which would be a contradiction with ∇u = 0 on Γ. In some applications, like the shaping of liquid metals by electromagnetic devices, this case τ C m = Λ turns out to be more "physical" since, in two-dimensional models, it is natural to assume that the distribution of currents f satisfies Ω f = 0 (see [START_REF] Descloux | Stability of the solutions of the bidimensional magnetic shaping problem in absence of surface tension[END_REF], [START_REF] Descloux | A stability result for the magnetic shaping problem[END_REF], [START_REF] Henrot | Un problème inverse en formage de métaux liquides[END_REF]).

A first case: τ C m = Λ (and (3.5) ). Then, the form Q writes

Q(h) = τ Γ γhD(γh) + (C -2C m )Ch 2 + h 2 , (3.7)
where

γ 2 = 2(C -C m ).
A main remark is that, in this situation, the positivity of Q, and consequently the stability of Ω, depend only on the geometry of the boundary Γ.

Positivity may be obtained in the following case. We denote by L(Γ) the length of Γ. We recall that C denotes the curvature of the Jordan curve Γ seen from inside Ω.

C m > -2π/L(Γ), (3.8)
then, H 1 -coercivity condition (3.4) holds.

Remark 3.3

The case where Γ is a circle will be considered in Section 4. Note that, under the above assumptions, Γ cannot be a circle. Indeed,

β 2 = 2(τ C -Λ) = 0, C ≡ C m , τ C m -Λ = 0,
imply that 0 ≡ β = ∂u/∂ν on Γ. But the three conditions "u = 0, ∇u = 0 on Γ and ∆u = 0 in a neighborhood of Γ" (see (3.5)) would imply that u be identically equal to 0 in a neighborhood of Γ which is not the case by (3.5).

Remark 3.4 Recall that, since Γ is a Jordan curve and since C is its curvature seen from inside Γ, then Γ C = 2π. This implies

2π = Γ C ≥ L(Γ)C m . (3.9)
Here, this inequality is strict since Γ is not a circle. Therefore, under the assumptions of above Theorem, we even have

C 2 m < 4π 2 /L 2 (Γ). (3.10)
To prove Theorem 3.1, we use the following lemma:

Lemma 3.2 ∀h ∈ Z 1 0 (Γ), Γ h 2 ≥ 4π 2 L 2 (Γ) Γ h 2 .
(3.11)

Proof: Let λ = inf{ Γ h 2 ; h ∈ H 1 (Γ), Γ h = 0, Γ h 2 = 1}.
By compactness of the embedding of H 1 (Γ) into L 2 (Γ), a minimizing subsequence in above definition converges to u ∈ Z 1 0 (Γ) realizing the infimum. Differentiating 2 , at t = 0 leads, in a classical way, to the fact that λ is the smallest positive eigenvalue of u → -u on [0, L(Γ)] with periodic conditions. We easily check that corresponding eigenfunctions are cos 2πs/L(Γ), sin 2πs/L(Γ), so that λ = 4π 2 /L 2 (Γ). Assertion (3.11) follows.

t → Γ (u + th ) 2 Γ (u + th)
Proof of Theorem 3.1: By (3.7,3.3), we have

Q(h) ≥ τ Γ [2δ(C -C m ) + (C -2C m )C] h 2 + h 2 . Since the function x → 2δ(x -C m ) + (x -2C m )x is increasing on [C m , +∞[, this implies Q(h) ≥ τ Γ h 2 -C 2 m h 2 .
(3.12)

According to (3.10), let > 0 such that (1 -)(2π/L) 2 = C 2 m . Then, by (3.12) and Lemma 3.2

Q(h) ≥ τ Γ h 2 = τ h 2 H 1 (Γ) .
Second case: τ C m > Λ (and (3.5)).

Theorem 3.3 Assume τ C m > Λ. If Γ is a convex Jordan curve, or more generally if C m > -min{δ, 2 π/L(Γ)}, (3.13)
then H 1 -coercivity condition (3.4) holds.

Proof of Theorem 3.3 Set δ = min{δ, 2 π/L(Γ)} (recall that δ is defined in (3.3)). Then, using (3.1), (3.3) and (3.6), we have

Q(h) ≥ Γ [2 δ(τ C -Λ) + (τ C -2Λ)C]h 2 + τ h 2 . (3.14)
The function x → ψ(x) = 2 δ(τ x -Λ) + (τ x -2Λ)x + τ δ2 is stricly increasing on [Λ/τ, +∞[. Note that ψ(-δ) = 0. Let > 0 be such that C m ≥ -δ and let ˆ be so that ψ( -δ) = ˆ τ δ2 (> 0). By Lemma 3.2 and the various definitions δ, , ˆ , we have

Q(h) ≥ Γ [2 δ(τ C -Λ) + (τ C -2Λ)C + τ (1 -ˆ ) δ2 ]h 2 + ˆ τ h 2 ≥ Γ ˆ τ h 2 .
Remark 3. [START_REF] Dambrine | About stability of equilibrium shapes[END_REF] The assumption (3.13) in Theorem 3.3 is probably not optimal to obtain positivity. However, if Γ is too far from a convex curve, then positivity may fail.

Proposition 3.4 There exist non convex analytic Jordan curves Γ for which the associated quadratic form Q has directions of instability when τ is small enough.

Proof: Assume that Γ is not convex so that C m and Λ are strictly negative

(0 > τ C m > Λ). The function β = {2(τ C -Λ)} 1/2 converges in C 1 to the constant function (2|Λ|) 1/2 as τ tends to 0. As a consequence, for h ∈ H 1/2 (Γ), βh tends to (2|Λ|) 1/2 h in H 1/2 (Γ) and D(βh) tends to (2|Λ|) 1/2 Dh in H -1/2 (Γ). Then, Q(h) tends to Q 0 (h) given by Q 0 (h) = 2|Λ| Γ hDh + Ch 2 .
To conclude, it is sufficient to prove that we may choose Γ and h ∈ H 1/2 (Γ) with Γ h = 0 and such that Q 0 (h) < 0.

We identify 2 with the complex plane ¡ . Let Φ be a conformal mapping from the unit disk Ω 0 onto Ω which sends the unit circle Γ 0 on Γ in a one-to-one way. Since Γ is analytic, Φ extends to a very regular function on Γ. If we denote by D 0 the operator D when Γ is replaced by Γ 0 , and if h := h • Φ, then

D 0 h = [Dh • Φ]|Φ |, so that Q 0 (h) = 2|Λ| Γ0 hD 0 h + [C • Φ]|Φ |h 2 .
It is sufficient to prove that we may choose the function [C • Φ]|Φ | (i.e. Γ) in such a way that the above expression for Q 0 becomes negative for some h.

Choose for instance Φ (z) = e -az 2 . It can be checked that, for 0 < a < 2.478, Φ is one-to-one from the unit disk into its image (since Φ is locally injective and the image of the unit circle has no double point). For θ ∈ [0, 2π], C Φ(e iθ ) |Φ (e iθ | is given as the real part of 1 + e iθ Φ (e iθ )/Φ (e iθ ) = 1 -2a cos 2θ.

For this choice, since D 0 (cos θ) = cos θ, we find

Q 0 (cos(•)) = 2|Λ| 2π 0 cos 2 θ[2 -2cos θ] = 2|Λ|π(2 -a).
Therefore, any value a ∈ (2, 2.478) gives the desired example.

Remark 3.6 From the analysis in [START_REF] Henrot | Un problème inverse en formage de métaux liquides[END_REF], we prove that, for a given analytic closed Jordan curve, and for τ, Λ given such that 0 < τ, Λ < τ C m , we may find a function f compactly supported inside Γ such that Γ be an equilibrium shape for the corresponding functional E(•). Therefore, it makes sense to analyze the stability of the given analytic Jordan curve Γ in terms of the parameters τ, Λ. Remark 3.7 About the influence of f : From the previous remark, we see that the case of f being compactly supported in Ω is actually very general. Now that we have analyzed the form Q without the term in f , we might want to understand the influence of adding it: it writes Γ f βh 2 where β = ∂u/∂ν. If, for instance, f ≥ 0, then u ≥ 0 so that β ≤ 0 and Γ f βh 2 ≤ 0. This suggests that the presence of f makes Q "less positive". We could state results involving the respective values of C m and f , but, in any case, a convex curve will not be stable for all f 's. A very detailed analysis of this is made in the next Section where Γ is a disk, in which case precise explicit computations can be made. Remark 3.8 If ∂Ω is the disjoint union of convex Jordan curves (which indeed happens in applications), then stability condition (3.4) holds.

The particular case of the disk

We assume in all this section that the equilibrium shape Ω is the unit disk. We are able to precisely study the positivity of the second derivative through the use of Fourier series expansions. Note that, if the solution u Ω is radial (u = u(r)), then the disk is indeed an equilibrium shape since we then have on the boundary Γ:

|∇u| 2 = u (1) 2 = constant,
so that by setting Λ = τ -u (1) 2 /2, we do have the equilibrium condition (2.7).

Here

β = u (1), β 2 = 2(τ -Λ).
Note that u is radial as soon as f is itself radial: this will be assumed in this section: f = f (r).

The second derivative writes (see (3.1))

Q(h) = Γ β 2 hD(h) + [τ -2Λ + βf (1)]h 2 + τ h 2 . (4.1)
For h given in Z 1 0 (Γ), we introduce its Fourier's series expansion

h = h(θ) = n≥1 (a n cos nθ + b n sin nθ) (4.2)
(Here a 0 = 0 since Γ h = 0).

Lemma 4.1

Q(h) = π n≥1 [τ n 2 + β 2 n + (τ -2Λ + βf (1))](a 2 n + b 2 n ), (4.3)
where β = -1 0 rf (r)dr, β 2 = 2(τ -Λ).

Proof: By direct integration, we obtain r u (r) = -r 0 sf (s) ds, whence the expression of β.

To compute Dh, we first note that the harmonic extension of h on the disk is given by n≥1 r n (a n cos nθ + b n sin nθ) so that

Dh(θ) = n≥1 n(a n cos nθ + b n sin nθ).

Easy computations lead to

Γ hD(h) = π n≥1 n(a 2 n + b 2 n ), Γ h 2 = π n≥1 (a 2 n + b 2 n ), Γ h 2 = π n≥1 n 2 (a 2 n + b 2 n ).
We combine these equalities according to (4.1) to obtain (4.3).

To state the positivity result, we introduce the expression

σ = 2 1 0 rf (r) dr 2 -f (1) 1 0 rf (r) dr.
According to the expression of l L 1 , the disk Ω is a critical shape of L(•) when we choose Λ := g( 1 4 ) and therefore a critical shape of ω → ω g(u ω ) under the constraint S(ω) = S(Ω).

We will denote Q(h) = l L 2 (h, h). A main remark is that Q vanishes on the subspace spanned by {cosθ, sinθ} (i.e such that a 1 = b 1 = 0). This comes from the fact that the minimization problem is invariant by translations (here f ≡ 1).

It is clear on the expression (5.2) that Q is continuous for the norm of H 1/2 (Γ). Thus the optimal space to look for the coercivity of Q is here

Z 1/2 00 = {h ∈ H 1/2 (Γ); Γ h = 0, Γ h cosθ = 0, Γ h sinθ = 0}.
Note that by the results in [START_REF] Dambrine | About stability of equilibrium shapes[END_REF], [START_REF] Dambrine | On variations of the shape Hessian and sufficient conditions for the stability of critical shapes[END_REF], this coercivity implies the existence of a local minimum for regular (e.g. C 3 ) perturbations of Ω preserving the volume and the barycentre.

We will also look at an example where coercivity occurs only for the L 2 norm.

For a ∈ (0, 1), we introduce the sets

Ω a = Ω\{(x, y) ∈ 2 ; x 2 + y 2 = a 2 }.
Obviously, Ω a has the same Lebesgue measure and the same center as the disk Ω itself. We will look at variations of a → Ωa g(u Ωa ) for a close to 1 and for a close to 0: in these cases, the Ω a 's are "close" to Ω but, obviously are not "regular" perturbations of Ω.

Theorem 5.2 There exists a function g and η > 0 such that

∀h ∈ Z 1/2 00 , Q(h) ≥ η h 2 L 2 (Γ)
and such that, for a ∈ (0, 1) close enough to 1

L(Ω a ) < L(Ω).
There exists a function g and η > 0 such that

∀h ∈ Z 1/2 00 , Q(h) ≥ η h 2 H 1/2 (Γ)
and such that, for a ∈ (0, 1) close enough to 0 L(Ω a ) < L(Ω).

Remark 5.1 As announced in the introduction, these examples prove that, although the second shape derivative at the unit disk is strictly positive, there are open subsets, "close" to the unit disk (in some sense) and satisfying the constraints, for which the functional is strictly less than for the disk.

The second example is somehow more satisfactory since the coercivity holds in the natural space H 1/2 . But, in this case, even the first derivative is pathological: note that the functional is not differentiable with respect to the parameter a at a = 0, although the classical first shape derivative does vanish for the disk. This shows that the so-called "topological" derivative should be also taken into account to decide about the existence of a true minimum.

The first example is more regular in a way, since the first derivative with respect to a does exist and vanishes at a = 1. Here again, the classical derivative turns out to be insufficient to decide about minima.

∈]0, 1[: u a (r) =      a 2 -r 2 4 if 0 ≤ r < a, 1 -r 2 4 + C a ln r if a < r ≤ 1. and u 1 (r) = (1 -r 2 )/4, ∀r ∈ [0, 1]. First example: Let c ∈ and g(x) = -x 2 + cx. By (5.2), Q(h) = - π 2 n≥2 1 2n + 2 -c + n(c - 1 4 ) (a 2 n + b 2 n ). ( 5.3)
An explicit computation of J(u 1 ) and J(u a ) gives

1 2π [J(u 1 ) -J(u a )] = (1 -a 2 )C a 4 (c - 3(1 + a 2 ) 8 + C a ), (5.4)
so that, as a tends to 1, if c = 1/4,

J(u 1 ) -J(u a ) ∼ π 2 (1 -a)(c - 1 4
).

Let us precisely choose c = 1/4. Then,

Q(h) = π 2 n≥2 ( 1 4 - 1 2n + 2 )(a 2 n + b 2 n ) ≥ π 24 n≥2 (a 2 n + b 2 n ).
On the other hand, from (5.4), we see that, as a tend to 1

J(u 1 ) -J(u a ) ∼ π(1 -a) 2 /8,
so that J(u 1 ) > J(u a ) when a is close to 1.

Second example: Note first that, for all choice of g, we have (5.5)

d da J(u a ) = π
The second example consists in choosing g in such a way that g(0) = 0 and 1 0 g (u 0 )r ln rdr < 0,

1 0 g (u 0 )r 2n-1 dr -2g( 1 4
) ≥ η > 0, ∀n ≥ 2. (5.6)

For this, we choose α > 0, b ∈ (0, 1/4) such that

α b > 1, 1 4b > α 4 -1 > -1 ln(1 -4b) , (5.7)
(this is for instance realized by α = 10, b = 1/8), and we set g(0) = 0 and

g (s) =    -α if 0 ≤ s ≤ b, 4(αb -1)/(1 -4b) if b ≤ s ≤ 1 4 .
We check that the sequence

n ≥ 1 → α n = 1 2n [(α -4)(1 -4b) (n-1) -α],
is stricly increasing and that ∀n ≥ 2, We verify that assumption (5.7) implies (5.6). Since g in only Lipschitz continuous, we may approximate g by C ∞ -functions g p converging uniformly on (0, 1/4) to g as p → +∞ and such that g p is uniformly bounded and converges a.e. to g . Then, inequalities (5.6) are satisfied by g p for p large enough. Proof of Lemma 5.1: We use the same normal deformations as in (2.2) which are of the form

T t x = x + tξ(x), ξ τ = 0, ξ • ν = h, Ω t = T t (Ω).
Then, if l(t) = L(Ω t ), we have (see (2.3)) l L 1 (h) = l (0), l L 2 (h, h) = l (0).

Since, we already know the derivatives of S(•), we only have to compute e (0), e (0) where e(t) = Ωt g(u t ) and u t is solution of -∆u t = 1 in Ω t , u t = 0 on ∂Ω t .

(5.8)

We have u 0 (r) = u(r) = (1 -r (5.12)

In particular, e Now, the first part of Lemma 5.1 follows from (5.13,5.15,5.14,5.9,2.9). Differentiating (5.12) at t = 0 leads to

e (0) = Ω g (u)(∂ t |t=0 u t ) 2 + Ω g (u)∂

Theorem 3 . 1

 31 Assume τ C m = Λ. Then, if Γ is a convex Jordan curve (i.e. C m ≥ 0), or, more generally, if Γ is a Jordan curve satisfying

Remark 5 . 2

 52 It is easy see that we may perturb the first example to obtain a similar counterexample with an annulus close to the disk Ω and of the formΩ a,b,c = {x ∈ 2 ; |x| ∈ [0, a) ∪ (b, c)},where a, b, c are close to 1, a < b < c and c 2 -b 2 + a 2 = 1. Note that Ω a,b,c are then even C ∞ shapes! Proof: Let C a = (a 2 -1)/4 ln a. Then u a = u Ωa is given by ∀a

a 0 g 1 ag 1 0g

 011 (u a )a r dr + 2πC a (u a )r ln r dr, so that, as a tends to 0 d da J(u a ) ∼ π 2a(ln a) 2 (u 0 )r ln r dr.

1 0g 1 0g 4 - 1 )

 1141 (u 0 )r 2n-1 dr = α n , 2 g(1/4) = α 1 = -2, (u 0 )r ln rdr = ( α ln(1 -4b) + 1.

1 0

 1 = Ω g (u)∂ t |t=0 u t + g(0) the solution p of the adjoint problem -∆p = g (u) in Ω, p = 0 on Γ, which satisfies p (1) = -rg ((1 -r 2 )/4) dr = 2[g(0) -g(1/4)].(5.14)We haveΩ g (u)∂ t |t=0 u t = -Ω ∆p(∂ t |t=0 u t ) = -Γ (∂ t |t=0 u t )p (1).(5.15)

  (ξ • Π(t)) = -Dξ ξ: I 4 = Γ ν • [g (0)ξ∂ t | t=0 u t -g(0)Dξ ξ] + h∇ • (g(u)ξ).

  2 )/4, ∇u = -ν/2 on Γ. Note that ∂ t |t=0 u t is solution of∆(∂ t |t=0 u t ) = 0 in Ω, ∂ t |t=0 u t =Thus, with the notation of Lemma 5.1, ∂ t |t=0 u t =1 2 H(h). Differentiating twice at the boundary leads also toWe will repeatedly use the following classical derivation formula which is valid for regular f : [0, 1] × 2 →

								1 2	h on Γ.	(5.9)
	∂ 2 tt |t=0 u t = -2h	∂(∂ t |t=0 u t ) ∂ν	+	1 2	h 2 = -hD(h) + h 2 /2 on Γ.	(5.10)
	d dt Ωt	f =	Ωt	[	∂f ∂t	(t) + ∇ • (f (t)ξ • Π(t))]	(5.11)

where Π(t) := (I + tξ) -1 . We apply it to e(t).

e (t) = Ωt g (u t )∂ t u t + Ωt ∇ • (g(u t )ξ • Π(t)).

  For the last integral I 4 of (5.16), we obtain by using(5.11), integration by parts and ∂ t | t=0

				2 tt |t=0 u(t)
	+	Γ	hg (u)∂ t |t=0 u t +	d dt |t=0 Ωt	∇ • (g(u t )ξ • Π(t)). (5.16)

l M i + τ l P i -Λl S i . (2.8)By[START_REF] Novruzi | Structure of shape derivatives[END_REF], Proposition 5.1, we havel S 1 (h) = Γ h, l S 2 (h, h) = Γ Ch 2 ,(2.9)l P 1 (h) = Γ Ch, l P 2 (h, h) = Γ |∇ τ h| 2where ∇ τ denotes the tangential gradient,l M 1 (h) =

Theorem 4.2 If σ > 0, H 1 -coercivity (3.4) holds and more precisely

If σ < 0, the disk is unstable. If σ = 0, then Q in nonnegative on Z 1 0 (Γ); moreover, there exists δ > 0 such that, for all h ∈ Z 1 0 (Γ) with a 1 = b 1 = 0, we have

Remark 4.1 When f is constant, since the functional E(•) is invariant by translations, one cannot expect coercivity in the directions of translations, i.e, on the subspace of Z 1 0 (Γ) spanned by {cosθ, sinθ}. We check that, in this case, σ = 0. However, above theorem says that H 1 -stability nevertheless holds for deformations leaving invariant the center of the disk (a 1 = 0, b 1 = 0). Remark 4.2 If f is compactly supported in the disk, then f (1) = 0 and σ ≥ 0; since it cannot be 0 (see Remark 3.3), the disk is always stable, no matter the radial distribution of "charges" (or "current") inside the disk. On the other hand, if f (1) is large compared to 1 0 rf (r) dr, then instabilities appear. If we refer to the underlying application arising in the electromagnetic shaping of liquid metals, having f (1) = 0 means that we have inductors touching the liquid metal at its boundary. We do believe that this may create instabilities. Remark 4.3 Note that σ depends only on f . Therefore, if σ > 0, stability holds no matter the value of τ > 0. If τ = 0, then coercivity still occurs, but only in the norm H 1/2 (Γ) (see the expression of R(n) in the following proof). We refer to [START_REF] Descloux | A stability result for the magnetic shaping problem[END_REF], [START_REF] Descloux | Stability of the solutions of the bidimensional magnetic shaping problem in absence of surface tension[END_REF], [START_REF] Dambrine | About stability of equilibrium shapes[END_REF] for results in this case.

Proof of Theorem 4.2: Note that τ -2Λ = -τ + β 2 . The sequence

is increasing, so that R(n) > 0 for any n ≥ 1 as soon as R(1) > 0, that is when

More precisely, since the mapping

is increasing, we even have

which proves coercivity of Q for the H 1 -norm in Z 1 0 (Γ). On the other hand, if σ < 0, R(1) < 0, so that instability occurs at least in the direction of the subspace spanned by {cosθ, sinθ}.

This proves the coercivity of Q for the H 1 -norm on the subspace of h ∈ Z 1 0 (Γ) such that a 1 = b 1 = 0.

Some counterexamples

Let g : → be a function of class C 2 . We consider the shape functional ω → ω g(u ω ) under the constraint S(ω) = S 0 , where u = u ω is simply the so-called stress function, solution of -∆u = 1 in ω, u = 0 on ∂ω.

We introduce the corresponding Lagrangian

where Λ is the Lagrange multiplier. According to the structure Theorem 2.1, we denote by l L 1 , l L 2 the forms defining the first and second derivatives of L at the unit disk Ω with its boundary Γ. We denote u = u Ω . Lemma 5.1 For all h ∈ C 3 (Γ),

)

) -g(0)]hD(h),

where D(h) is defined as in the previous sections and H(h) denotes the harmonic extension of h to the unit disk Ω. If moreover Ω is an equilibrium shape (i.e.l L 1 ≡ 0) and if h is given by

)] .

(5.2)

We postpone the proof of this lemma which requires some serious computations (as often for second shape derivatives). We will give all necessary details even if similar computations may be found here and there in the literature (see e.g. [START_REF] Belov | Symmetry and sufficient condition of optimality in a domain optimization problem[END_REF], [START_REF] Fuji | Sufficient conditions for optimality in shape optimization[END_REF], [START_REF] Eppler | Second derivatives and sufficient optimality conditions for shape functionals[END_REF], [START_REF] Eppler | Sufficient conditions for a class of optimal shape design problems[END_REF]).

But, recall that ξ = hν where the norm of ν is equal to 1, so that, on Γ

Adding everything yields

(5.17)

For the third integral of (5.16), we have

(5.18)

For the second integral of (5.16), by double integration by parts and using (5.10,5.14), we obtain

Using (5.16), the expressions of the three integrals above and (2.9), we obtain the second statement of Lemma 5.1.

If now h is given by its Fourier series expansion (5.1), we have that We deduce (5.2) (note that the term associed to n = 1 vanishes).


Rania Othman
email: rania.othman@gmx.com

Rami Belkaroui
email: rami.belkaroui@gmail.com

Rim Faiz
email: rim.faiz@ihec.rnu.tn

Improving Opinion Target Identification through Twitter Using Public Conversations

Keywords: Twitter, Conversations, Opinion targets, Anaphora, User interactions

In this paper, we propose a new method for opinion target identification based on twitter conversations rather than simple individual tweets. We employ conversation interactions to effectively extract the different target features using a product review corpus involving smartphones and other electronics products. Experimental evaluations show that our proposed method is efficient and contributes to improving system performance.

Introduction

Twitter is currently one of the most popular micro-blogs which has grown at an unprecedented rate to reach over 320 million monthly active users 3 . Twitter is both a micro-blogging service and a conversational environment that enables people to interact, engage in daily chatter, join conversations, report news and share information. Conversations are key element in such service. Almost a quarter of Twitter users hold conversations with other users through this platform [START_REF] Java | Why we twitter: understanding microblogging usage and communities[END_REF] and huge percentage of Twitter posts are conversational [START_REF] Ritter | Unsupervised modeling of twitter conversations[END_REF]. The huge volume of conversations produced everyday makes them an interesting information source and valuable tool to discover new trends and exchange opinions and feedbacks towards products, news and stories. A large number of the messages are carriers of opinions and feelings [START_REF] Jmal | Customer review summarization approach using twitter and sentiwordnet[END_REF]. One major field that took advantage of this potential is e-reputation. It has become a common practice for business owners to allow their customers to review their products through public web sites (e.g. epinions.com, amazon.com). This enables businesses to have general overview on their consumer satisfaction and attitudes about the product or the service offered. While conversations are very rich source of information, retrieving relevant information remains challenging. The large number of messages involved in these conversations makes it hard for users to cope with rate of messages involving a lot of noise and redundancy. Thus, applying automated systems that aim to retrieve individual opinion words or phrases and what they are about, referred to as the opinion target or opinion topic, could be quite useful for business owners.

In this paper, we propose a new method for opinion target identification based on Twitter conversations. To date, little research has been adressed to tackle conversations despite their prevalence in social streams. Most existing works on opinion analysis through Twitter, have so far focused on handling simple individual tweets rather than considering the whole conversations [START_REF] Meng | Entity-centric topic-oriented opinion summarization in twitter[END_REF][START_REF] Bora | Summarizing public opinions in tweets[END_REF][START_REF] Bahrainian | Sentiment analysis and summarization of twitter data[END_REF]. As tweets are limited to 140 characters and usually written in an informal way involving a lot of abbreviations, typos and slangs, it is frequently hard to detect the exact meaning of a tweet when taken separately. Also, a large number of features are generally referenced by anaphoric pronouns in major succeeding replies of a conversation message. Anaphora can be defined as the use of an expression the interpretation of which depends specifically upon a previous expression [START_REF] Steinberger | Two uses of anaphora resolution in summarization[END_REF]. Consider this example sentence:"It is fantastic.". If one wants to extract what the opinion in this sentence is about, previous replies must be analysed. Frequently, while handling conversations, a large amount of messages are left unnoticed due to their vague and unclear aspect. Therefore, we adopt a conversation-based method that employs conversation interactions, notably reply links, to effectively extract the target product features involved in the messages. To the best of our knowledge, this is the first research employing twitter conversations in the opinion target identification task.

The rest of this paper is organized as follows. Section 2 overviews the related work on opinion target identification. In section 3, we introduce our new approach for opinion target identification on Twitter conversations. Section 4 reports the experiment results. Finally, Section 5 concludes this paper with some perspectives.

RELATED WORK

Opinion target extraction is crucial for opinion mining (OM) and summarization especially given that this task provides the foundation for opinion summarization [START_REF] Feldman | Extracting product comparisons from discussion boards[END_REF]. Opinion target can be defined as the entity ( i.e., person, object, feature, event or topic) about which the user expresses his opinion. Extensive approaches and techniques have been addressed to mine opinion components or targets from unstructured reviews. These works can be very broadly divided into two main categories supervised and unsupervised. Other works have also employed the semi-supervised approach. In the supervised learning approaches, a machine-learning model is trained on manually labeled data to extract and classify the feature set in the reviews. Although these techniques provide good results for opinion target extraction, they require extensive manual work for the training set preparation, they are also time consuming, and sometimes domain dependent. The most common techniques employed in supervised approaches are decision tree, support vector machine (SVM), K-nearest neighbor (KNN), nave Bayesian classifier and neural network [START_REF] Jakob | Using anaphora resolution to improve opinion target identification in movie reviews[END_REF][START_REF] Kessler | Targeting sentiment expressions through supervised ranking of linguistic configurations[END_REF][START_REF] Toh | Nlangp: Supervised machine learning system for aspect category classification and opinion target extraction[END_REF]. On the other hand, unsupervised approaches automatically extract product features using syntactic and contextual patterns without the need of labeled data [START_REF] Hu | Mining and summarizing customer reviews[END_REF][START_REF] Jmal | Customer review summarization approach using twitter and sentiwordnet[END_REF]. A challenge which is frequently encountered in the opinion target extraction task is, that entities can be sometimes implicit and therefore hard to find. In the case of explicit target identification, we generally employ noun phrases with syntactic rules [START_REF] Hu | Mining and summarizing customer reviews[END_REF][START_REF] Popescu | Extracting product features and opinions from reviews[END_REF] . While for implicit targets, context dependency or distribution similarity are employed. To the best of our knowledge, there is currently only two systems that integrate coreference information and apply anaphora resolution (AR) in OM. Stoyanov and Cardie [START_REF] Stoyanov | Topic identification for fine-grained opinion analysis[END_REF] develop an algorithm that identifies coreferring targets in newspaper articles. They rely on manually annotated targets thus, a candidate selection phase for the opinion targets is not required. The authors focus only on the coreference resolution but they do not resolve pronominal anaphora in order to achieve this purpose. For their part, [START_REF] Jakob | Using anaphora resolution to improve opinion target identification in movie reviews[END_REF] adapt the rule based AR algorithm CogNIAC to extract opinion targets on a movie review corpus. They have shown that extending an OM algorithm with AR for opinion target extraction can achieve significant improvements. In this paper, we apply AR to extract opinion targets ( i.e., product features) from Twitter conversations. To the best of our knowledge, this is the first research employing twitter conversations and AR for the feature extraction task.

PROPOSED APPROACH

In our work, we aim to extract product features reviewed by users in our tweet collection based on Twitter conversations. Our approach is based on three main modules namely, pre-processing, conversation retrieval and opinion target identification. Figure 1 presents an overview of the proposed approach. Given a tweet Fig. 1. Overview of our proposed approach corpus on electronic products, we clean our collection via the pre-processing phase, than we proceed to retrieve conversations from the collection of separate tweets. The final step consists on extracting opinion targets commented by users through the conversation collection. The three modules are illustrated in details in the following subsections.

Pre-processing

The collection of tweets is preprocessed before the conversation retrieval module. First of all, the URL in each message is analyzed. While different shortened URLs might redirect to the same end URL, it is necessary to replace them with the real URLs they redirect. Thereafter, we employ an API service 4 for HTML text extraction which removes comments, links, ads, and other unrelated parts of a web page and returns key contents in plain text. Then, we proceed to the second step of the processing involving the text analysis. In this step, both the text content of the tweet and the text retrieved from the URLs are taken into account. We cleaned the text by removing ASCII characters, numbers, punctuation, and stop words. In the end, we convert the text to lower case and we tokenize it. The remaining tweet features such as the ID of the author and other social information are also extracted from the API and stored. We indexed the collection of tweets with Apache Lucene5 which is full-featured text search engine library written entirely in Java.

Conversation Retrieval Module

In this section, we describe the process of constructing conversations from a collection of tweets. We consider the conversation definition presented by [START_REF] Belkaroui | Conversation analysis on social networking sites[END_REF]. They defined a conversation as a set of short text messages posted by a set of users at specific timestamps on the same topic. This messages can be directly replied to other users by using "@username" or indirectly by liking, retweeting, commenting and other possible interactions. We apply the same method developed by [START_REF] Belkaroui | Conversation analysis on social networking sites[END_REF] who proposed a user-based tree model for retrieving conversations from microblogs. They do not only retrieve direct messages based on reply links but also consider indirect messages that can be related to the conversation via other links such as retweet and mention interactions. To avoid bias related to features existing with a very small number, we cleaned our collection of conversations by filtering out the conversations that involve less than 3 participants and containing less than 7 tweets.

Opinion Target Identification Module

In this stage, we aim to extract the opinion targets or features customers expressed their opinions on. For example, if we want to generate an OM about iPod, some of the common features are "battery life", "sound quality" and "ease of use". Given a conversation collection, our system splits the reviews into sentences, then, it converts them to lower case and remove the non literal characters at the beginning and the end of each word (e.g. "#IPhone#" becomes "iphone"). Steinberger et al. [START_REF] Steinberger | Two uses of anaphora resolution in summarization[END_REF] reveal that noun and noun phrases in the sentence are likely to be the features customers expressed their opinions on. We therefore perform the Part-of-Speech (POS) tagging of the whole document to identify the grammatical class of each word using TreeTagger6 . We extract nouns from the reviews and we move on to the feature decider step. We construct our stop word list and we filter out the extracted nouns existing in the stop word list. Then, we construct noun phrases which are composed of two successive nouns (e.g. Click wheel, Battery Life). We extract all noun phrases but we only keep those appearing together at least 3 times in the reviews. We remove sentence redundancy, if a noun appears more than one time in the same sentence, we consider as if it appears one time. We then compute frequency of occurrences in the reviews for the whole set of extracted nouns and we only keep those whose frequency is greater than 0.02.

To decide if the noun phrases we collected are meaningful, we apply a similarity measure called point-wise mutual information (PMI-IR) [START_REF] Turney | Mining the web for synonyms: PMI-IR versus LSA on TOEFL[END_REF] that uses page counts returned by a web search engine to recognize synonyms. Like [START_REF] Jmal | Customer review summarization approach using twitter and sentiwordnet[END_REF], we detect the compactness of a noun phrase using the number of tweets concerning a given product instead of the search engine page counts. We prune noun phrases having PMI < 0.

Having our feature list, we proceed to the next step which aims to affect each review (or post/message) in our corpus to the feature the author comment on in his post. To do so, we apply our proposed Target Identification Algorithm based on conversation interactions notably the reply-links. Indeed, a large number of features appearing as noun phrases and even simple nouns in reviews are generally referenced by anaphoric pronouns in major succeeding sentences of a review document [START_REF] Kamal | Statistical features identification for sentiment analysis using machine learning techniques[END_REF][START_REF] Jakob | Using anaphora resolution to improve opinion target identification in movie reviews[END_REF]. The anaphoric term is called an anaphor. For example, in the sentence: "I'm so glad with my new iPhone 5, it's just amazing", the pronoun "it" is an anaphor, referring back to the antecedent "my new iPhone 5". Actually, the overwhelming majority of the opinion targets ( i.e., product features) are pronouns in the datasets [START_REF] Kamal | Statistical features identification for sentiment analysis using machine learning techniques[END_REF]. Thus, AR is crucial for binding feature-review pairs, otherwise a very big number of opinion reviews will be left unnoticed due to their ambiguous aspect. In order to identify the associations of such reviews with correct features, a conversation-interactions based algorithm has been developed. To the best of our knowledge, this is the first such algorithm that employs conversation interactions notably reply-links for effective binding of feature-review pairs. Our algorithm proceeds as follows, for a tweet t i,l , that does not contain any feature words existing in the feature list but involves opinionated words ( i.e., adjectives and adverbs) along with some pronouns, all anaphora pronouns present in this sentence that require mapping are extracted, and a set of anaphora P={p 1 , p 2 , p 3 , ..., p n } is compiled for proper context determination. We employ a backtracking mechanism in which review documents are accessed in reverse order based on reply-links to extract precedent sentences t i-1,j that t i,l replies on. For each anaphora pronoun p i P, proper context is determined to compile a set A={a k,1 , a k,2 , a k,3 , ..., a q,m } consisting of candidate antecedents. The best antecedent a k,t A is selected for binding with a o using CogNIAC algorithm [START_REF] Baldwin | Cogniac: high precision coreference with limited knowledge and linguistic resources[END_REF], a publically available algorithm for AR that employs a rule based approach for antecedent identification. This approach can be an adequate strategy for our OM task, since in our corpus, a small pourcentage of the total number of pronouns are actual product features (only 6%). We denote the l th tweet at iteration i t i,l while the j th tweet at iteration i is denoted t i,j . As each anaphora pronoun is replaced by the selected antecedent, backtracking process terminates with the iteration i-1 for each sentence. At the end of this phase, we obtain a set of opinionated sentences and each sentence is associated to the corresponding target feature that the user commented on.

EXPERIMENTS AND RESULTS

Dataset Description

Due to the lack of test collections for Twitter conversations, we have created our own collection. We crawled 221 663 English tweets using Twitter Application Programmable Interface (API) 7 . The Twitter API allows developers around the world to have free and open access to Twitter's database. The tweet collection was crawled over a period of 4 months from April 25th 2015 to July 25th 2015.

We only search popular tweets talking about a given product involving character description, promotion information and comments about new products. After removing the repeated ones, 211 350 tweets remained. From our collection of tweets, we have constructed 8 720 conversations involving 64 370 tweets and 13 827 bloggers. We employ statuses/lookup.json files accessed through Twitter API, which contain all information related to the tweets. Table 1 outlines some statistics on our Conversation collection. As shown, there exist over 120K pronouns and roughly 11.13 % of the opinion targets are referred to by pronouns.

Evaluation Results

We implement our approach using java language and we conducted our experiments using the Twitter conversations of five electronics products: 2 digital cameras and 3 smartphones. As our work evaluation requires substantial human effort to identify product features and subjective reviews, we reduced the set of 8K conversations to just 4K. For each product, we extract the first 800 conversations. After preprocessing, our system is applied to perform opinion summarization. For evaluation, we manually read all the extracted conversations. For each tweet, if it involves user opinions, all the features on which the author has expressed his opinion are tagged. For each product, we manually produced a feature list. Column "Nbr of features" in Table 2 shows the number of manual features for each product. The features generated by our system are compared with the manually tagged results. In this subtask, we used precision and recall which are among the main evaluation measures employed in the feature selection task. In our case, TP is the number of relevant features identified, TP+TN represent the number of relevant features and TP+FP gives the number of features identified. Table 2 shows the evaluation results for the 5 products obtained in the feature identification phase. The highest values reached by our system are 77.81% precision and 82.62% recall. Our system presents high precision and recall scores. The recall value is higher than precision indicating that the majority of correct features were correctly recognized by the system. This can show the efficacity of the use of converation interactions in extracting product features that have been commented by users. The precision value is lower than recall indicating that some identified features are not correct. This can be justified since most of the reviewers do not follow grammatical rules strictly while writing tweets due to which the parser fails to assign correct POS tag and thereby correct dependency relations between words. On analysis, we observed that, when a pronoun to be resolved has more than two or three candidate antecedents, the occurrence of noisy anaphora-antecedent pairs increases. This leaves scope for enhancing our method for detecting features to reach better precision level. To further illustrate the effectiveness of our feature identification phase, we compared the features generated using our method with features found by the same method applied to the same set of tweets taken separately rather than extracting conversations and without the use of AR between messages. This method is closely similar to the feature detection process employed by [START_REF] Jmal | Customer review summarization approach using twitter and sentiwordnet[END_REF] which extract product features from customer reviews based on product reviews collected via electronic commerce websites and Twitter. The average recall of opinion sentence extraction is nearly 63% while the average precision is around 57%. We observe that both the average recall and precision of the second method are significantly lower than those of our method. On analysis, we observed that, in testing dataset, a total of 13 824 anaphoric pronouns are present, in which 886 pronouns correctly refer to product features. By applying the second method, almost 60% of pronouns are left unnoticed or erroneously extracted. Comparing the results in Table 2, we can clearly see that the proposed method is much more effective for our task.

Conclusion

In this paper, we proposed a new method for opinion target identification that handles twitter conversations rather than single tweets. We employ conversation interactions, notably reply links, to effectively extract the target product features from customer reviews. Our experimental results indicate that the proposed method is very promising in performing its task. In particular, we have proved that incorporating conversation structure in the opinion target identification task contributes to improving system performance.

In our future work, we plan to further experiment it with other entities not only products. We will also look into employing our approach on other customer opinion ressources rather than Twitter. We also intend to enhance the AR process.

Table 1 .

 1 Corpus size statistics

	Tweets	64 370
	Tokens	2 568 160
	Target + Opinion Pairs	7 960
	Targets which are Pronouns 886
	Pronouns	> 120 350

Table 2 .

 2 Evaluation results for the feature detection phase

		Nbr of Feature identificationFeature identification
	Product	features on individual tweets on conversations
					(this research)
			Precision(%)	Recall(%)	Precision(%)	Recall(%)
	Digital camera 1 27	68.33	62.13	75.26	79.61
	Digital camera 2 31	63.52	64.40	76.78	77.98
	Smartphone 1	52	55.97	51.83	75.22	78.23
	Smartphone 2	25	71.54	57.74	69.46	82.62
	Smartphone 3	43	57.88	53.73	77.81	81.73
	Average		63.44	57.96	74.90	80.03

https://about.twitter.com/company

http://www.alchemyapi.com/

https://lucene.apache.org/

http://www.cis.uni-muenchen.de/ schmid/tools/TreeTagger/

https://dev.twitter.com/overview/api