Elissar Nasreddine
email: elissar.nasreddine@math.univ-toulouse.fr

Two-dimensional individual clustering model

. In this paper we give a detailed proof of existence of global solution.

Introduction

In the present work, we deal with a model of individual dispersing of individual with an additional aggregation mechanism introduced in [START_REF] Grindrod | Models of individual aggregation or clustering in single and multi-species communities[END_REF]. Given a sufficiently smooth function E, parameters δ ∈ (0, 1), ε ≥ 0 and r ≥ 0, the equations take the form

∂ t u = δ ∆u -∇ • (u ω) + r u E(u), x ∈ Ω, t > 0 -ε ∆ω + ω = ∇E(u),
x ∈ Ω, t > 0 [START_REF] Amann | Linear and quasilinear parabolic problems[END_REF] in an open bounded domain Ω ⊂ R 2 , where u(t, x) > 0, ω(t, x) ∈ R 2 and E denote the population density, the average velocity of dispersing individuals, and the individual net reproduction rate, respectively. In this model, the individuals are assumed to disperse randomly in space (δ ∆u) with a bias -∇ • (u ω) in the direction of increasing reproduction rate, the term ε ∆ω acting as a mollifier to smooth out any sharp local variation in ∇E(u).

In [START_REF] Grindrod | Models of individual aggregation or clustering in single and multi-species communities[END_REF], we supplement [START_REF] Amann | Linear and quasilinear parabolic problems[END_REF] with no-flux boundary conditions

∂ n u = n • ω = 0, x ∈ ∂Ω, t ≥ 0, ( 2
)
where n is the outward unit normal of ∂Ω and ∂ n u = n • ∇u. However, to guarantee the well-posedness of the elliptic system for ω in two space dimensions, we should append the following condition given in [START_REF] Dias | A simplified variational model for the bidimensional coupled evolution equations of a nematic liquid crystal[END_REF][START_REF] Dias | Un problème aux limites pour un système d'équations non linéaires tridimensionnel[END_REF][START_REF] Schoenauer | Quelques résultats de régularité pour un système elliptique avec conditions aux limites couplées[END_REF]]

∂ n ω × n = 0, x ∈ ∂Ω, t ≥ 0, (3)
where

∂ n ω = (∂ n ω 1 , ∂ n ω 2 ) = (n • ∇ω 1 , n • ∇ω 2 )
for the vector field ω = (ω 1 , ω 2 ). in other words, [START_REF] Dias | A simplified variational model for the bidimensional coupled evolution equations of a nematic liquid crystal[END_REF] means that ∂ n ω is parallel to n, where v

× u = v 1 u 2 -u 1 v 2 .
Given q > 2, and an initial condition u 0 ∈ W 1,q (Ω), the existence and uniqueness of a nonnegative and maximal solution of (1), ( 2) and (3) have been shown in [START_REF] Nasreddine | Well-posedness for a model of individual clustering[END_REF], and the purpose of this paper is to prove the global existence of solution when E(u) has the two specific forms suggested in [START_REF] Grindrod | Models of individual aggregation or clustering in single and multi-species communities[END_REF], namely

E(u) = (1 -u) (u -a) (4)
for some a ∈ (0, 1), or

E(u) = 1 -u. (5)
For these choices of reproduction rates, global existence has been shown in [START_REF] Nasreddine | Well-posedness for a model of individual clustering[END_REF] in one space dimension and the purpose of this work is to prove that the solutions are global as well in two space dimensions. As in the one-dimensional case, the starting point of the analysis is an L ∞ (L 2 ) estimate on u and an L 2 estimate on ∇ • ω. Combining the latter with Gagliardo-Nirenberg inequality gives L ∞ (L p ) estimates on u for any p > 2. This then allow us to obtain an L ∞ (L 2 ) bound on ∇u which in turn gives an L ∞ bound on ω by elliptic regularity.

The paper is organized as follows. In section 2, we state the global existence results, and focus on the two specific forms of E: The "bistable case" (4) see Theorem 2.2, and the "monostable case" [START_REF] Grindrod | Models of individual aggregation or clustering in single and multi-species communities[END_REF], see Theorem 2.3. In section 3, we recall the local existence result obtained in [START_REF] Nasreddine | Well-posedness for a model of individual clustering[END_REF] and we give some properties of the elliptic system for ω. In section 4, we turn to the global existence issue in the bistable case. The proof starts from the L ∞ (L 2 ) estimate for u, an L 2 estimate for ω and an L 2 estimate on ∇ • ω obtained from a suitable cancellation between the coupling terms in the u and ω equations, then, for p > 2, we derive an L ∞ (L p ) estimate for u. Then we use Lemma A.1 of [START_REF] Tao | Boundedness in a quasilinear parabolic-parabolic Keller-Segel system with subcritical sensitivity[END_REF] to derive an L ∞ estimate of u and we end the proof by an L ∞ (L q ) estimate on ∇u. This ensures global existence. In section 5, we prove the global existence in the monostable case. The proof is quite similar to that of the previous case, except for the first estimate.

Main result

We first define the notion of solution to (1)-(3) to be used in this paper. Definition 2.1. Let T > 0, q > 2, and an initial condition u 0 ∈ W 1,q (Ω) . A strong solution of (1)-(3) on [0, T ) is a function

u ∈ C [0, T ), W 1,q (Ω) ∩ C (0, T ), W 2,q (Ω) , such that    ∂ t u = δ ∆u -∇ • (u ω) + r u E(u), a.e. in [0, T ) × Ω u(0, x) = u 0 (x), a.e. in Ω ∂ n u = 0, a.e. on [0, T ) × ∂Ω, (6)
where, for all t ∈ [0, T ), ω(t) is the unique solution in W 2,q (Ω) of

-ε∆ω(t) + ω(t) = ∇E(u(t)) a.e. in Ω ω(t) • n = ∂ n ω(t) × n = 0 a.e. on ∂Ω (7)
In the following theorem we give the global existence of solution to (1)-(3) in the bistable case, that is when E(u) = (1 -u)(u -a), for some a ∈ (0, 1). Theorem 2.2. Let q > 2, and assume that u 0 is a nonnegative function in W 1,q (Ω), and E(u) = (1 -u)(u -a) for some a ∈ (0, 1). Then The proof starts with a suitable cancellation of the coupling terms in the two equations which gives an estimate for u in L ∞ (L 2 ) and for ∇•ω in L 2 . Using the Gagliardo-Nirenberg inequality (13) we derive, for p > 2 an L ∞ (L p ) estimate for u. Then by the regularity properties of the second equation in [START_REF] Amann | Linear and quasilinear parabolic problems[END_REF] we obtain an L ∞ bound of ω. Combining these estimates and Lemma A.1 of [START_REF] Tao | Boundedness in a quasilinear parabolic-parabolic Keller-Segel system with subcritical sensitivity[END_REF] provide us with an L ∞ estimate for u which is used to show an L ∞ (L q ) estimate for ∇u. This proves that the solution cannot explode in finite time.

Next, we turn to the global existence issue in the monostable case, that is when

E(u) = 1 -u.
Theorem 2.3. Let q > 2, and assume that u 0 is a nonnegative function in W 1,q (Ω), and E(u) = (1 -u). Then (1)-( 3) has a global nonnegative solution u in the sense of Definition 2.1.

The proof of the previous theorem follows the same lines as that of Theorem 2.2. As in the bistable case, there is a cancellation between the two equations which provide us an L ∞ (L log L) bound on u and an L 2 bound for ∇ • ω as a starting point.

Well-posedness

Throughout this paper and unless otherwise stated, we assume that

δ ∈ (0, 1), ε > 0, r ≥ 0.
We first recall some properties of the strong solution of the following system,

   -ε ∆ω + ω = f, in Ω, ω • n = 0, on ∂Ω, ∂ n ω × n = 0, on ∂Ω, (8)
where f ∈ (L p (Ω)) 2 and p > 1. The strong solutions of ( 8) is solving (8) a.e. in Ω. In this direction the existence and uniqueness of the strong solution to (8) are proved in [START_REF] Schoenauer | Quelques résultats de régularité pour un système elliptique avec conditions aux limites couplées[END_REF]:

Theorem 3.1. For f ∈ (L p (Ω)) 2 with 1 < p < ∞, (8) has a unique solution in (W 2,p (Ω)) 2 such that ||ω|| W 2,p ≤ K(p) ε ||f || p , (9)
where

K(p) = K(p, Ω).
In other words, the strong solution has the same regularity as elliptic equations with classical boundary conditions.

Thanks to [START_REF] Nasreddine | Well-posedness for a model of individual clustering[END_REF] we recall the existence and uniqueness result of the maximal solution of (1)-(3). Theorem 3.2. We assume that E ∈ C 2 (R), let p > 2 and a nonnegative function u 0 ∈ W 1,p (Ω). Then, for some T max ∈ (0, ∞], there is a unique nonnegative maximal solution

u ∈ C [0, T max ), W 1,p (Ω) ∩ C (0, T max ), W 2,p (Ω) (10)
to (1)-( 3) in the sense of Definition 2.1. Moreover, if for each T > 0, there is

C(T ) such that ||u(t)|| W 1,p ≤ C(T ), for all t ∈ [0, T ] ∩ [0, T max ), then T max = ∞. In addition, u satisfies u(t, x) = e t(δ ∆) u 0 (x) + t 0 e (t-s)(δ ∆) [-∇ • (u ω) + r u E(u)] (s, x) ds, (11)
for (t, x) ∈ [0, T max ] × Ω
, where e t (δ ∆) denotes the semigroup generated in L p (Ω) by δ ∆ with homogeneous Neumann boundary conditions.

We recall that there is C > 0 such that

||e t (δ ∆) v|| W 1,p ≤ C ||v|| W 1,p , and ||∇e t (δ ∆) v|| p ≤ C δ -1 2 t -1 2 ||v|| p . ( 12
)
Also in several places we shall need the following Gagliardo-Nirenberg inequality

||u|| p ≤ C ||u|| θ W 1,2 ||u|| 1-θ q , with θ = p -q p , u ∈ W 1,2 (Ω) (13)
which holds for all p ≥ 1 and q ∈ [1, p]. Also we use the following singular Gronwall lemma (see [START_REF] Amann | Linear and quasilinear parabolic problems[END_REF]Theorem 3.3.1]).

Lemma 3.3. Given α, β ∈ [0, 1) , there exists a positive constant c := c(α, β) such that the following is true:

If f : (0, T ) -→ R satisfies t → t β f (t) ∈ L ∞ loc ((0, T ), R), (14)
and

f (t) ≤ A t -β + B t 0 1 (t -s) α f (s) ds, a.a.t ∈ (0, T ), ( 15
)
where A and B are positive constants, then f (t) ≤ C(T ), for all t ∈ (0, T ), where C depends only on T, α, β, and γ.

4 Global existence 4.1 The bistable case:

E(u) = (1 -u)(u -a)
We recall the system

       ∂ t u = δ ∆u -∇ • (u ω) + r u (1 -u) (u -a), x ∈ Ω, t > 0 -ε ∆ω + ω = [-2 u + (a + 1)] ∇u, x ∈ Ω, t > 0 ∂ n u = 0 , ω • n = ∂ n ω × n = 0, x ∈ ∂Ω, t > 0 u(0, x) = u 0 (x), x ∈ Ω. ( 16
)
for a some a ∈ (0, 1), and u 0 ∈ W 1,q (Ω) for some q > 2.

Since E ∈ C 2 (R), Theorem 3.2 ensures that there is a maximal solution of (16) in C [0, T max ), W 1,q (Ω) ∩ C (0, T max ), W 2,q (Ω) for q > 2.

We begin the proof by the following lemmas which gives some estimates on u and ω. Lemma 4.1. Let the same assumptions as that of Theorem 2.2 hold, and u be the nonnegative maximal solution of (16). Then for all T > 0 there exists C 1 (T ) > 0, such that u and ω satisfy the following estimates

||u(t)|| 2 2 + t 0 ||∇u(s)|| 2 2 ds ≤ C 1 (T ), for all t ∈ [0, T ] ∩ [0, T max ), ( 17
)
and t 0 ||∇ • ω(s)|| 2 2 + ||ω(s)|| 2 2 ds ≤ C 1 (T ) for all t ∈ [0, T ] ∩ [0, T max ). ( 18
)
Proof. We multiply the first equation in ( 16) by 2 u and integrate it over Ω, to obtain

d dt Ω |u| 2 dx = -2 δ Ω |∇u| 2 dx + 2 Ω u ω • ∇u dx + 2 r Ω u 2 E(u) dx. ( 19
)
We multiply now the second equation in ( 16) by ω and integrate it over Ω. We note that the boundary conditions for ω guarantee that ω is tangent to ∂Ω while ∂ n ω is normal to ∂Ω. Consequently, ∂ n ω • ω = 0 on ∂Ω and it follows from an integration by parts that

-ε Ω ∆ω • ω dx = ε Ω |∇ • ω| 2 dx -ε ∂Ω [ (∇ω 1 • n) ω 1 + (∇ω 2 • n) ω 2 ] dσ = ε Ω |∇ • ω| 2 dx.
We thus obtain

ε Ω |∇ • ω| 2 dx + Ω |ω| 2 dx = -2 Ω u ω • ∇u dx + (a + 1) Ω ω • ∇u dx. (20)
At this point we notice that the cubic terms on the right hand side of ( 19) and (20) cancel one with the other, and summing (20) and ( 19) we obtain

d dt ||u|| 2 2 + ε ||∇ • ω|| 2 2 + ||ω|| 2 2 + 2 δ ||∇u|| 2 2 = 2 r Ω u 2 E(u) dx + (a + 1) Ω ω • ∇u dx.
We integrate by parts and use Cauchy-Schwarz inequality to obtain (a + 1)

Ω ω • ∇u dx = -(a + 1) Ω u ∇ • ω dx ≤ (a + 1) 2 2 ε ||u|| 2 2 + ε 2 ||∇ • ω|| 2 2 .
On the other hand,

u 2 E(u) ≤ 0 if u / ∈ (a, 1) so that Ω u 2 E(u) dx ≤ |Ω| (1 -a).
The previous inequalities give

d dt ||u|| 2 2 + ε 2 ||∇ • ω|| 2 2 + ||ω|| 2 2 + 2 δ ||∇u|| 2 2 ≤ (a + 1) 2 2 ε ||u|| 2 2 + 2 |Ω| r (1 -a).
Therefore, for all T > 0 there exists C 1 (T ) such that (17) and (18) hold.

Lemma 4.2. Let the same assumptions as that of Theorem 2.2 hold, and u be the nonnegative maximal solution of (16). Then for all T > 0 there exists C 2 (T, p) > 0, such that for p ≥ 2 Using the Gagliardo-Nirenberg inequality (13) we have

||u(t)|| p ≤ C 2 (T, p) for all t ∈ [0, T ] ∩ [0, T max ), (21)
||u p 2 || 4 ≤ C ||u p 2 || 1 2 W 1,2 ||u p 2 || 1 2 2 . ( 24
)
Substituting ( 24) in ( 23), and by Young inequality we obtain

d dt ||u|| p p ≤ -4 δ (p -1) p ||∇u p 2 || 2 2 + C (p -1) ||∇ • ω|| 2 ||u p 2 || W 1,2 ||u p 2 || 2 + r p (1 -a) |Ω| ≤ -4 δ (p -1) p ||∇u p 2 || 2 2 + 2 δ (p -1) p ||u p 2 || 2 W 1,2 + C(p) ||∇ • ω|| 2 2 ||u p 2 || 2 2 + C(p) ≤ -2 δ (p -1) p ||∇u p 2 || 2 2 + C(p) ||u|| p p + C(p) ||∇ • ω|| 2 2 ||u|| p p + C(p).
Next, integrating the above inequality in time, and using (18) yield that there exists C 2 (T, p) such that (21) and ( 22) hold.

Lemma 4.3. Let the same assumptions as that of Theorem 2.2 hold, and u be the nonnegative maximal solution of (16). Then for all T > 0 there exists

C 3 (T ) > 0, such that ||∇u(t)|| 2 ≤ C 3 (T ) for all t ∈ [0, T ] ∩ [0, T max ). ( 25
)
Proof. We multiply the first equation in ( 16) by -∆u, integrate over Ω, and use Cauchy-Schwarz, and Young inequalities and (21) to obtain

1 2 d dt ||∇u|| 2 2 = -δ ||∆u|| 2 2 + Ω (∇u • ω + ∇ • ω u) ∆u dx -r Ω u (1 -u) (u -a) ∆u dx ≤ -δ ||∆u|| 2 2 + δ 2 ||∆u|| 2 2 + C Ω |∇u| 2 |ω| 2 dx + C Ω |∇ • ω| 2 |u| 2 dx + C r ||u (1 -u) (u -a)|| 2 2 + δ 4 ||∆u|| 2 2 ≤ - δ 4 ||∆u|| 2 2 + C Ω |∇u| 2 |ω| 2 dx + C Ω |∇ • ω| 2 |u| 2 dx + C(T ). ( 26
)
To go further requires to improve the estimate on ω and ∇ • ω. For that purpose, we use Lemma 4.1 and Lemma 4.2 for p = 4 to obtain for all T > 0

t 0 ||∇E(u)(s)|| 2 2 ds ≤ (a + 1) 2 t 0 ||∇u(s)|| 2 2 ds + 4 t 0 ||u ∇u(s)|| 2 2 ds ≤ C 2 (T ), (27)
for all t ∈ [0, T ] ∩ [0, T max ). Consequently, ∇E(u) is bounded in L 2 ((0, t) × Ω). By Theorem 3.1 and the continuous embedding of W 2,2 (Ω) in W 1,4 (Ω), and W 1,4 (Ω) in L ∞ (Ω), we have

||ω|| ∞ + ||∇ • ω|| 4 ≤ C ||ω|| W 1,4 ≤ C ||ω(s)|| W 2,2 ≤ C ||∇E(u)|| 2 ,
which together with (27) implies that

t 0 ||ω(s)|| 2 ∞ + ||∇ • ω(s)|| 2 4 ds ≤ C t 0 ||∇E(u)(s)|| 2 2 ds ≤ C 2 (T ), (28)
for all t ∈ [0, T ] ∩ [0, T max ). Using Hölder Inequality , (26) becomes

1 2 d dt ||∇u|| 2 2 ≤ - δ 4 ||∆u|| 2 2 + C ||ω|| 2 ∞ Ω |∇u| 2 dx + C ||∇ • ω|| 2 4 ||u|| 2 4 + C(T ).
Next we integrate the above inequality in time, and use (21) for p = 4, and (28) to obtain

||∇u(t)|| 2 2 ≤ ||∇u 0 || 2 2 + C t 0 ||ω(s)|| 2 ∞ ||∇u(s)|| 2 2 ds + C(T ), using (28)
again, we have thus proved (25).

Lemma 4.4. Let the same assumptions as that of Theorem 2.2 hold, and u be the nonnegative maximal solution of (16). Then for all T > 0 there exists

C 4 (T ) > 0, such that ||ω(t)|| ∞ ≤ C 4 (T ), for all t ∈ [0, T ] ∩ [0, T max ). (29)
Proof. It follows from ( 21), (25) and Hölder inequality, that there exists

C(T ) > 0 such that ||(-2u + a + 1) ∇u|| 3 2 ≤ C(T ) || -2 u + a + 1|| 6 ||∇u|| 2 ≤ C(T ).
Consequently, Theorem 3.1 ensures that ||ω||

W 2, 3 2 ≤ C ||[-2 u + a + 1] ∇u|| 3 2 ≤ C(T ), for all t ∈ [0, T ] ∩ [0, T max ).
Using the continuous embedding of W 2, 3 2 (Ω) in L ∞ (Ω) we have thus proved (29).

Next, thanks to lemma A.1 in [START_REF] Tao | Boundedness in a quasilinear parabolic-parabolic Keller-Segel system with subcritical sensitivity[END_REF] we can derive a uniform bound for u.

Lemma 4.5. Let the same assumptions as that of Theorem 2.2 hold, and u be the nonnegative maximal solution of (16). Then for all T > 0 there exists

C 5 (T ) > 0, such that ||u(t)|| ∞ ≤ C 5 (T ), for all t ∈ [0, T ] ∩ [0, T max ). ( 30
)
Proof. We can see that the function u solves

   ∂ t u = ∇ • (δ ∇u) + ∇ • f + g, a.e. in [0, T max ) × Ω u(0, x) = u 0 (x), a.e. in Ω ∂ n u = 0, a.e. on [0, T max ) × ∂Ω, (31)
where f = -u ω and g = r u E(u).

By the regularity (10) of u, and by the continuous embeddings of W 1,p (Ω) in C( Ω) and of W 2,p (Ω) in C( Ω) for p > 2 we obtain that f = -u ω ∈ C (0, T max ); C( Ω) and ∇f ∈ C (0, T max ); C( Ω) . Using (10) and the continuous embeddings of W 1,p (Ω) in C( Ω) for p > 2 again, we see that g = r u E(u) ∈ C (0, T max ) × Ω . On the other hand, f • n = -u ω • n = 0 on ∂Ω × (0, T max ).

Thanks to (21), we have

||u(t)|| p 0 ≤ C(T ), for all t ∈ [0, T ] ∩ [0, T max )
where p 0 = 9, while (21) and (29) yield

||f (t)|| q 1 ≤ C(T ) and ||g|| q 2 ≤ C(T ), for all t ∈ [0, T ] ∩ [0, T max )
where q 1 > 4 and q 2 = 3 > 2. Since p 0 > 1 -3q 1 -4 q 1 -3 and p 0 = 9 > 0, we can apply lemma A.1 in [START_REF] Tao | Boundedness in a quasilinear parabolic-parabolic Keller-Segel system with subcritical sensitivity[END_REF], and the estimate (30) holds. Lemma 4.6. Let the same assumptions as that of Theorem 2.2 hold, and u be the nonnegative maximal solution of (16). Then for all T > 0 there exists

C 6 (T ) > 0, such that ||∇u(t)|| q ≤ C 6 (T ), for all t ∈ [0, T ] ∩ [0, T max ). (32)
Proof. Using (11),( 12), ( 30) and (29) we have for q > 2

||∇u(t)|| q ≤ C ||u 0 || W 1,q + C 1 t 0 (t -s) -1 2 ||∇ • (u ω)(s)|| q ds + r C 1 t 0 ||∇(u E(u))(s)|| q ds ≤ C ||u 0 || W 1,q + C 1 t 0 (t -s) -1 2 ||u(s)|| ∞ ||∇ • ω(s)|| q ds + C 1 t 0 (t -s) -1 2 ||ω(s)|| ∞ ||∇u(s)|| q ds (33) + r C 1 t 0 ||(-3 u 2 + 2 (a + 1) u -a)(s)|| ∞ ||∇u(s)|| q ds. ≤ C(T ) 1 + t 0 (t -s) -1 2 (||∇ • ω(s)|| q + ||∇u(s)|| q ) ds + t 0 ||∇u(s)|| q ds .
By Theorem 3.1 we have

||∇ • ω(s)|| q ≤ ||ω(s)|| W 2,q ≤ K(q) ||(-2u + a + 1)(s)|| ∞ ||∇u(s)|| q . (34)
Substituting (34) into (33) and using (30) we obtain

||∇u(t)|| q ≤ C(T ) 1 + t 0 (t -s) -1 2 ||∇u(s)|| q ds + t 0 ||∇u(s)|| q ds .
Now, we obtain (32) by applying Lemma 3.3 with β = 0, and α = 1 2 .

Thanks to these lemmas we can now prove the main Theorem 2.2

Proof of Theorem 2.2. For all T > 0, Lemma 4.2 and Lemma 4.5 ensure that for q > 2 ||u(t)|| W 1,q ≤ C(T ), for all t ∈ [0, T ] ∩ [0, T max ) which guarantees that u cannot explode in W 1,q (Ω) in finite time and thus that T max = ∞.

Monostable case

For this choice of E, system (1)-( 3) now reads

       ∂ t u = δ ∆u -∇ • (u ω) + r u (1 -u), x ∈ Ω, t > 0 -ε ∆ω + ω = -∇u, x ∈ Ω, t > 0 ∂ n u = 0 , ω • n = ∂ n ω × n = 0, x ∈ ∂Ω, t > 0 u(0, x) = u 0 (x), x ∈ Ω, (35)
when u 0 ∈ W 1,q (Ω) for some q > 2. Since E ∈ C 2 (R), Theorem 3.2 ensures that there is a maximal solution of (35) in C [0, T max ), W 1,q (Ω) ∩ C (0, T max ), W 2,q (Ω) for q > 2.

To prove Theorem 2.3 we need to prove the following lemma

Finally, (36) is obtained by a time integration of (39).

Proof of Theorem 2. Thus, the maximal solution u of (35) cannot explode in finite time.

  (1)-(3) has a global nonnegative solution u in the sense of Definition 2.1.

Lemma 4 . 7 . 0 ||ω(s)|| 2 2 +u| 2

 47022 Let the same assumptions as that of Theorem 2.3 hold, and let u be the maximal solution of (35). Then for all T > 0, there exists C 7 (T ) > 0 such thatt ||∇ • ω(s)|| 2 2 ds ≤ C 7 (T ), for all t ∈ [0, T ] ∩ [0, T max ).(36)Proof. The proof goes as follows. On the one hand, we multiply the first equation in (35) by (log u+ 1) and integrate it over Ω, the boundary terms vanish. Since u (1-u) log u ≤ 0 and u (1-u) ≤ 1, d dt Ω u log u dx = -Ω (δ ∇u -u ω) • ( 1 u ∇u) dx + r Ω u (1 -u) (log u + 1) dx ≤ -Ω δ u |∇u| 2 dx + Ω ω • ∇u dx + |Ω| r.(37)On the other hand, we multiply the second equation in (35) by ω, integrate it over Ω. We note that the boundary conditions for ω guarantee that ω is tangent to ∂Ω while ∂ n ω is normal to ∂Ω. Consequently, ∂ n ω • ω = 0 on ∂Ω and it follows from an integration by parts that dx + |Ω| r.

3 .

 3 Thanks to (36), we now argue as in the proof of Lemma 4.2, Lemma 4.3, Lemma 4.4, Lemma 4.5 and Lemma 4.6 to get that for q > 2 ||u(t)|| ∞ + ||∇u(t)|| q ≤ C(T ), for all t ∈ [0, T ] ∩ [0, T max ).

  We multiply the first equation in (16) by p u p-1 , integrate with respect to x, and integrate by parts. The boundary terms vanish and we obtain

	d dt	||u|| p p ≤	-4 δ (p -1) p	||∇u	p 2 || 2 2 -(p -1)	Ω	∇ • ω u p dx
			+ r p	u p-1 E(u) dx.
				Ω
	By Cauchy-Schwarz inequality we obtain
	d dt	||u|| p p ≤	-4 δ (p -1) p	||∇u	p 2 || 2 2 + (p -1) ||∇ • ω|| 2 ||u	p 2 || 2 4	(23)
			+ r p (1 -a) |Ω|.

t 0 ||∇u p 2 (s)|| 2 2 ds ≤ C 2 (T, p) for all t ∈ [0, T ] ∩ [0, T max ). (

22

)

Proof.

Acknowledgment

I thank Philippe Laurençot for fruitful discussion.


Tim Van De Cruys
email: tim.vandecruys@irit.fr

Laura Rimell
email: laura.rimell@cl.cam.ac.uk

Thierry Poibeau
email: thierry.poibeau@ens.fr

Anna Korhonen
email: anna.korhonen@cl.cam.ac.uk

Multi-way Tensor Factorization for Unsupervised Lexical Acquisition

This paper introduces a novel method for joint unsupervised aquisition of verb subcategorization frame (SCF) and selectional preference (SP) information. Treating SCF and SP induction as a multi-way co-occurrence problem, we use multi-way tensor factorization to cluster frequent verbs from a large corpus according to their syntactic and semantic behaviour. The method extends previous tensor factorization approaches by predicting whether a syntactic argument is likely to occur with a verb lemma (SCF) as well as which lexical items are likely to occur in the argument slot (SP), and integrates a variety of lexical and syntactic features, including co-occurrence information on grammatical relations not explicitly represented in the SCFs. The SCF lexicon that emerges from the clusters achieves an F-score of 68.7 against a gold standard, while the SP model achieves an accuracy of 77.8 in a novel evaluation that considers all of a verb's arguments simultaneously.

Introduction

Verb subcategorization lexicons and selectional preference models capture two related aspects of verbal predicate-argument structure, with subcategorization describing the syntactic arguments taken by a verb, and selectional preferences describing the semantic preferences verbs have for their arguments. Each type of information can support NLP tasks requiring information about predicate-argument structure. For example, subcategorization has proved useful for parsing [START_REF] Carroll | The automatic acquisition of verb subcategorisations and their impact on the performance of an HPSG parser[END_REF][START_REF] Arun | Lexicalization in crosslinguistic probabilistic parsing: The case of french[END_REF][START_REF] Cholakov | Using unknown word techniques to learn known words[END_REF], semantic role labeling [START_REF] Bharati | Inferring semantic roles using subcategorization frames and maximum entropy model[END_REF][START_REF] Moschitti | Verb subcategorization kernels for automatic semantic labeling[END_REF], verb clustering, (Schulte im [START_REF] Schulte Im Walde | Experiments on the automatic induction of german semantic verb classes[END_REF][START_REF] Sun | Hierarchical verb clustering using graph factorization[END_REF] and machine translation [START_REF] Han | Handling structural divergences and recovering dropped arguments in a korean/english machine translation system[END_REF][START_REF] Hajič | Natural language generation in the context of machine translation[END_REF], while selectional preferences have benefited parsing [START_REF] Zhou | Exploiting web-derived selectional preference to improve statistical dependency parsing[END_REF], semantic role labeling [START_REF] Gildea | Automatic labeling of semantic roles[END_REF][START_REF] Zapirain | Generalizing over lexical features: Selectional preferences for semantic role classification[END_REF], and word sense disambiguation [START_REF] Resnik | Selectional preference and sense disambiguation[END_REF][START_REF] Thater | Contextualizing semantic representations using syntactically enriched vector models[END_REF][START_REF] Seaghdha | Probabilistic models of similarity in syntactic context[END_REF].

Verb subcategorization frame (SCF) induction involves identifying the arguments of a verb lemma in a corpus, and generalizing about the frames taken by the verb, where each frame includes a number of arguments and their syntactic types. Consider e.g. sentence (1), where the verb show takes the frame SUBJ-DOBJ-CCOMP (subject, direct object, and clausal complement).

(1)

[Our October review] SUBJ comprehensively [shows] VERB [you] DOBJ [what's in store in next month's magazine] CCOMP .

Predicting the set of SCFs for a verb can be viewed as a multi-way co-occurrence problem of a verb and its different arguments. One of the main challenges is distinguishing arguments from adjuncts (e.g. temporal, locative, or manner modifiers). Most SCF induction work to date considers only the co-occurrences of verb lemmas with different grammatical relation types (subject, object, prepositional phrase, etc.). Taking SCF acquisition to the next level requires consideration of the lexical fillers of potential argument slots for more accurate argumentadjunct discrimination.

Selectional preference (SP) induction involves predicting the likelihood of a given lexical item occurring in an argument slot, and generalizing about the lexical classes which occur in the slot, which may be dependent on the SCF. In sentence (2), for example, the verb show takes the frame SUBJ-DOBJ, and the direct object of show in this frame is likely to be inanimate.

(2)

[Stalin] SUBJ , who must have been well informed through his network of spies, [showed] VERB [no emotion] DOBJ . Most SP induction work to date has focused on discovering lexical preferences within the direct object slot alone, or at most three-way co-occurrences between verb, subject, and direct object, and has not considered the full range of potential argument slots for which verbs subcategorize, thus losing some of the contextual information which may be helpful in learning SPs. Moreover, the ability of SP acquisition methods to model the full range of verbal arguments, including e.g. clausal complements, has not been tested.

As the two types of lexical information -SCFs and SPs -are closely interlinked and can complement each other, it would make sense to acquire them jointly. However, to the best of our knowledge, no previous work has developed a model for their joint acquisition.

Unsupervised machine learning is attractive for lexical acquisition because it works where little labeled data is available, and ports easily between tasks and languages. Increasingly sophisticated techniques have been applied to SP induction [START_REF] Rooth | Inducing a semantically annotated lexicon via em-based clustering[END_REF][START_REF] Van De Cruys | A non-negative tensor factorization model for selectional preference induction[END_REF][START_REF] Séaghdha | Latent variable models of selectional preference[END_REF][START_REF] Ritter | A latent dirichlet allocation method for selectional preferences[END_REF][START_REF] Reisinger | Crosscutting models of lexical semantics[END_REF] while work on unsupervised SCF acquisition has been limited [START_REF] Carroll | Valence induction with a head-lexicalized pcfg[END_REF]. In this paper we present a largely unsupervised method for the joint acquisition of SCFs and SPs, adapting a method that has been successfully used for SP induction (Van de Cruys, 2009) so that it learns whether a verb subcategorizes for a particular argument slot together with which lexical items occur in the slot.

Our method uses a co-occurrence model augmented with a factorization algorithm to cluster verbs from a large corpus. Specifically, we use non-negative tensor factorization (NTF) [START_REF] Shashua | Non-negative tensor factorization with applications to statistics and computer vision[END_REF], a generalization of matrix factorization that enables us to capture latent structure from multi-way co-occurrence frequencies. The factors that emerge represent clusters of verbs that share similar syntactic and semantic behaviour. To evaluate the performance on SCF acquisition, we identify the syntactic behaviour of each cluster. The SCF lexicon that emerges from the clusters achieves a promising F-score of 68.7 against a gold standard. We further introduce a novel SP evaluation in which we investigate the model's ability to induce preferences for the co-occurrence of a particular verb lemma and all of its arguments at the same time. The model achieves a high accuracy of 77.8 on this new evaluation. We also perform a qualitative evaluation which shows that the joint model is capable of learning rich lexical information about both syntactic and semantic aspects of verb behaviour in data.

Related Work

Recent SCF acquisition approaches use the output of an unlexicalized parser to generate SCF hypotheses, followed by statistical filtering and/or smoothing to remove noise. [START_REF] Briscoe | Automatic extraction of subcategorization from corpora[END_REF]; [START_REF] Korhonen | Semantically motivated subcategorization acquisition[END_REF]; [START_REF] Preiss | A system for large-scale acquisition of verbal, nominal and adjectival subcategorization frames from corpora[END_REF] use handcrafted rules to match parser output to a pre-defined set of SCFs, achieving an F-measure of about 70 against a manually annotated gold standard, while O' Donovan et al. (2005); [START_REF] Chesley | Automatic extraction of subcategorization frames for french[END_REF]; [START_REF] Ienco | Automatic extraction of subcategorization frames for italian[END_REF]; [START_REF] Messiant | ASSCI: A subcategorization frames acquisition system for French verbs[END_REF]; [START_REF] Lenci | Unsupervised acquisition of verb subcategorization frames from shallow-parsed corpora[END_REF]; Altamirano and Alonso i Alemany (2010); [START_REF] Kawahara | Acquiring reliable predicate-argument structures from raw corpora for case frame compilation[END_REF] induce the inventory of SCFs from parsed corpus data. Candidate frames are identified by grammatical relation (GR) co-occurrences, often aided by language-specific heuristics. Statistical filtering or empirically-tuned thresholds are used to select frames for the final lexicon. These 'inductive' approaches have achieved respectable accuracy (60-70 F-measure against a dictionary) and are more portable than earlier methods. However, their ability to improve in accuracy is limited by their inability to incorporate information beyond the GR co-occurrences and heuristics that identify candidate SCFs on a per-sentence basis. Such cues provide no capacity for learning further from the data, e.g. from the lexical content of verbal arguments or from other GRs which are not part of the SCF.

Unsupervised machine learning has been applied to tasks where portability is equally important [START_REF] Blei | Latent dirichlet allocation[END_REF][START_REF] Dinu | Measuring distributional similarity in context[END_REF] but its application to SCF acquisition remains limited. [START_REF] Carroll | Valence induction with a head-lexicalized pcfg[END_REF] combined a head-lexicalized context-free grammar with an expectation-maximization (EM) algorithm to acquire an SCF lexicon. [START_REF] Dębowski | Valence extraction using EM selection and co-occurrence matrices[END_REF] used a filtering method based on the point-wise co-occurrence of arguments in parsed data to acquire a Polish SCF lexicon, but this method does not take the semantics of the verb's arguments into account. [START_REF] Lippincott | Learning syntactic verb frames using graphical models[END_REF] developed a graphical model for inducing verb frames in corpus data. The model identifies argument types of verbs but not sets of SCFs taken by a verb, as full scale SCF systems do.

Recent SP acquisition approaches use latent semantic information to model SPs, making use of probabilistic models, such as latent Dirichlet allocation (LDA) [START_REF] Séaghdha | Latent variable models of selectional preference[END_REF][START_REF] Ritter | A latent dirichlet allocation method for selectional preferences[END_REF][START_REF] Reisinger | Crosscutting models of lexical semantics[END_REF], or non-negative tensor factorization (NTF) [START_REF] Van De Cruys | A non-negative tensor factorization model for selectional preference induction[END_REF]. Other approaches solely make use of distributional similarity methods [START_REF] Bhagat | Ledir: An unsupervised algorithm for learning directionality of inference rules[END_REF][START_REF] Basili | Learning selectional preferences for entailment or paraphrasing rules[END_REF][START_REF] Erk | A simple, similarity-based model for selectional preferences[END_REF]. All approaches model two-way verbargument co-occurrences, with the exception of [START_REF] Van De Cruys | A non-negative tensor factorization model for selectional preference induction[END_REF] which models three-way verb-subject-object co-occurrences.

To our knowledge, no previous method has learned SCFs and SPs jointly. [START_REF] Scheible | An evaluation of predicate argument clustering using pseudodisambiguation[END_REF] used SCFs as features in a Predicate-Argument Clustering (Schulte im [START_REF] Schulte Im Walde | Combining EM training and the MDL principle for an automatic verb classification incorporating selectional preferences[END_REF] approach to SP acquisition, but did not evaluate the resulting clusters for SCFs and found that the SP method did not outperform previous methods. [START_REF] Abend | Unsupervised argument identification for semantic role labeling[END_REF] used co-occurrence measures to perform unsupervised argument-adjunct discrimination for PPs, but not full SCFs.

Our method makes use of non-negative tensor factorization (NTF) [START_REF] Shashua | Non-negative tensor factorization with applications to statistics and computer vision[END_REF]. Tensor factorization is the multilinear generalization of matrix factorization. It has been extensively studied in the field of statistics [START_REF] Kolda | Tensor decompositions and applications[END_REF], and has yielded promising results on SP acquisition ( [START_REF] Van De Cruys | A non-negative tensor factorization model for selectional preference induction[END_REF]. We introduce a novel way of considering SCFs with an arbitrary number of arguments, and SPs as multi-way co-occurrences in the context of these larger SCFs. The resulting model provides an ideal framework for joint acquisition of SCF and SP information. The only form of supervision in the model is parameter estimation and choice of the best feature set via cross-validation.

Subcategorization Frame Inventory

To facilitate thorough qualitative evaluation (Section 5.6), we defined our SCFs in terms of syntactic slots, and in the form of common GRs. Finer-grained inventories including lexicalized elements and semantic interpretation were left for future work (see Section 7).

We use the GR types produced by the RASP parser [START_REF] Briscoe | Robust accurate statistical annotation of general text[END_REF]. Altogether we experimented with combinations of nine GR types out of the 131 which can be headed by verbs, selected on the basis of their frequency in the parsed BNC corpus and relevance for subcategorization. For this initial experiment, we focused on higher-frequency arguments since they will have the greatest impact on downstream applications.

Our first eight basic GR types are as follows. In subject position we included non-clausal subjects (SUBJ)2 , ignoring sentences with clausal subjects, which are much less frequent. Since objects are key arguments for subcategorization, we included all three object types -direct objects (DOBJ), second objects of ditransitive constructions (OBJ2), and prepositional arguments (IOBJ). Although OBJ2 is less frequent than other objects, it is important for identifying ditransitive frames. We included both types of clausal complements -XCOMP (infinitival/unsaturated) and CCOMP (finite/saturated) -and also PCOMP, which often signifies a wh-object of a preposition. We also included particles (PRT). Together, these eight GR types account for 62% of the GRs in the parsed BNC corpus. Using these GRs, there are 23 SCFs in our gold standard (see Section 5.1), of which the 15 with the highest type frequency are shown in Table 1.

Although modifiers are generally not included in SCFs (and are also excluded from our gold standard) we experimented with using them as features, to determine whether their distribution could help reach a better generalization. We focused on non-clausal modifiers (NCMOD). Counting them, the nine GR types account for 95% of the GRs in the BNC corpus.

Methodology

Non-negative tensor factorization

Distributional co-occurrence data is usually represented in the form of a matrix. Matrices are perfectly suited for the representation of two-way co-occurrence data, but are unable to cope with multi-way co-occurrence data. We therefore make use of the generalization of a matrix, which is called a tensor. Tensor objects are able to encode co-occurrence data beyond two modes. Figure 1 shows a graphical comparison of a matrix and a tensor with three modes. Note that a tensor need not be restricted to three modes; in fact, our model requires tensors of up to 12 modes. Such tensors are difficult to represent visually, but the mathematical machinery remains unchanged. In order to create a succinct and generalized model of the extracted data, a statistical factorization technique called non-negative tensor factorization (NTF) is applied to the data. The NTF model is similar to parallel factor (PARAFAC) analysis -popular in areas such as psychology and bio-chemistry -with the constraint that all data needs to be non-negative (i.e. ≥ 0).

PARAFAC is a multilinear analogue of the singular value decomposition (SVD), used e.g. in latent semantic analysis [START_REF] Landauer | A solution to Plato's problem: The Latent Semantic Analysis theory of the acquisition, induction, and representation of knowledge[END_REF]. The key idea is to minimize the sum of squares between the original tensor and the factorized model of the tensor. For an N -mode tensor T ∈ R D 1 ×D 2 ×...×D N this gives objective function (1), where k is the number of dimensions in the factorized model and • denotes the outer product. min

x i ∈R D 1 , y i ∈R D 2 ,...,z i ∈R D N T - k i=1 x i • y i • . . . • z i 2 F (1)
2707 With non-negative tensor factorization, the non-negativity constraint is enforced, which yields a model with objective function (2). min

x i ∈R D 1 ≥0 , y i ∈R D 2 ≥0 ,...,z i ∈R D N ≥0 T - k i=1 x i • y i • . . . • z i 2 F (2)
The algorithm results in N matrices, indicating the loadings of each mode on the factorized dimensions. The model for the three-mode case is represented graphically in figure 2, visualizing the fact that the NTF decomposition consists of the summation over the outer products of N (in this case three) vectors. Computationally, the NTF model is fitted by applying an alternating least-squares algorithm. In each iteration, two of the modes are fixed and the third one is fitted in a least squares sense. This process is repeated until convergence.3

Construction of verb-argument tensors

In order to discover SCFs and SPs, we construct a tensor that contains the multi-way cooccurrences of a verb and its different arguments.

Corpus data

We used a subset of the corpus of [START_REF] Korhonen | A large subcategorization lexicon for natural language processing applications[END_REF], which consists of up to 10,000 sentences for each of approximately 6400 verbs, with data taken from five large British and American cross-domain corpora. To ensure sufficient data for each verb, we included verbs with at least 500 occurrences, yielding a total of 1993 verbs. The corpus data was tokenized, POS-tagged, lemmatized, and parsed with the RASP system [START_REF] Briscoe | Robust accurate statistical annotation of general text[END_REF]. RASP uses a tag-sequence grammar, and is unlexicalized, so that the parser's lexicon does not interfere with SCF acquisition. RASP produces output in the form of GRs. Passive sentences and those with clausal subjects were ignored.

Tensor construction

The corpus data is used to construct an N -mode tensor, where N represents the number of GRs. Each mode contains a different GR to the verb. Given the eight GRs from Section 3 plus the verb itself, this yields a 9-mode tensor (up to 12-mode when modifiers and split clausal modifiers are included; see Section 4.2.3).

For any particular verb instance (i.e. sentence), not every GR type will be instantiated. However, to model the multi-way co-occurrences in a tensor framework, each instance must have a feature for every mode to be incorporated into the tensor. Previous applications of non-negative tensor factorization in NLP have not needed a representation for the non-instantiation of a mode. We introduce an empty, void (-) feature when a particular mode is not instantiated. For example, sentence (1) from Section 1 would be encoded as the tuple in (3):

(3) 〈show V , review N , you P , -, -, -, be V , -, -〉 indicating that the VERB, NCSUBJ, DOBJ, and CCOMP slots are filled with respectively show V , review N , you P , and be V , and that the remaining slots (IOBJ, OBJ2, PCOMP, XCOMP, PRT) are empty.

(See Section 4.2.3 for alternative feature sets for each mode.)

Our final tensor then records how many times the tuple is attested in the corpus (i.e. how many times these particular features for the various grammatical relations occur together with the verb in question). The constructed tensor is then factorized to a limited number of latent dimensions, minimizing objective function (2). We normalize the factorization matrices to 1, to ensure a proper probability distribution.

Initially, we experimented with the number of latent dimensions of the factorization model (in the range 50-200). In further experiments, we retained the number of 150 dimensions, as this gave us the best results, and the model did not improve beyond 150 dimensions.

Feature sets

We constructed the feature sets for each mode in a number of different ways. Our base model uses the POS tag of the argument and no other features. We then experimented with a variety of additional features, based on linguistic intuitions about SCFs and SPs, as follows.

head The lexical head of the argument as well as the POS tag is used;

extpp PPs are extended to include the head of the PP's object, e.g. to_London N (for the head models) or to_N (for the POS models) instead of simply to;

split both XCOMP and CCOMP are split up into two different modes to differentiate between null and lexicalized complementizers (e.g. for CCOMP, whether the complementizer is null or that); mod modifiers (NCMOD) are included as an extra mode in the tensor.

Only the models with head features are relevant for SP acquisition. The head features also test how sensitive the learning of SCFs is to lexical-semantic as opposed to purely syntactic generalizations. The extended PP features provide additional lexical-semantic information. The clausal complement subtypes are available in the RASP output and offer a finer-grained syntactic analysis of these GRs. Finally, we used modifiers to test whether modifier co-occurrences, although (by definition) not part of the SCFs, might still be helpful in generalizing about subcategorization (i.e., maybe verbs taking similar frames also take similar modifiers). For each mode, we included the features that occurred with frequency ≥ 500 in the corpus, to maintain tractability.

For example, sentence (1) from Section 1 would be encoded as the tuple in (4) in the base POS-only model, and the tuple in (5) in the model with head and modifier features.

(4) 〈show V , N, P, -, -, -, V, -, -〉

(5) 〈show V , review N , you P , -, -, -, be V , -, -, comprehensively R 〉 5 Experiment 1: SCF Induction

Evaluation method

SCF lexicons are traditionally evaluated against gold standards. We took the gold standard of [START_REF] Korhonen | A large subcategorization lexicon for natural language processing applications[END_REF], which is a superset of SCFs in large dictionaries, and created a version using our eight basic GR types to define the SCFs. The resulting gold standard contains 183 general language verbs, with an average of 7.4 SCFs per verb. No attempt is made to distinguish between multiple senses of polysemous verbs; SCFs belonging to all senses are included for each lemma in the gold standard.

We evaluated the acquired SCF lexicons using type precision (percentage of SCF types that the system proposes which are correct), type recall (percentage of SCF types in the gold standard that the system proposes), and F-measure (the harmonic mean of type precision and recall).

We have two baselines. For baseline 1, we adopt the baseline of O'Donovan et al. ( 2005) which uniformly assigns to all verbs the two SCFs known to be most frequent in general language, transitive (SUBJ-DOBJ) and intransitive (SUBJ). This is a challenging baseline for SCF acquisition because of the Zipfian nature of SCF distributions: a small number of frequent SCFs are taken by the majority of verbs. For baseline 2, as described in Section 4.2.3, we use the base model with only POS features and none of the additional lexical or modifier features.

Mapping latent dimensions to SCFs

In order to evaluate this technique for SCF acquisition, we need to characterize each latent dimension according to its syntactic behaviour, i.e. map each dimension to a characteristic SCF.

Each latent dimension z is represented by a set of N vectors, indicating the loadings of each mode on z. Because the loadings were normalized, each vector contains a probability distribution, over verbs or features. For a dimension z and a given mode (i.e. GR slot) we use the probability p(-|z) of a void appearing in that slot to decide whether that slot is characteristically empty or filled for that dimension. For the verb mode, we use the probability p(v|z) to decide whether a verb v takes that dimension's characteristic SCF.

The mapping thus has two parameters. The first, θ verb , represents the minimum p(v|z) for v to be assigned the characteristic SCF of z. Based on early experiments, we chose to test three values for θ verb , 0.001, 0.002, and 0.003.

The second parameter, θ void , represents the maximum value of p(-|z) at which the argument slot will be considered part of the SCF of z. For example, if p(-|z) > θ void in the vector representing the DOBJ mode for z, then the characteristic SCF of z does not include a direct object. We did not apply the θ void threshold to subjects, but rather assumed that all characteristic SCFs include subjects; early experiments showed that subjects were otherwise sometimes erroneously excluded from the SCFs because the data contained high numbers of subjectless embedded clauses. For all other modes, we tested θ void values from 0.1 to 0.8 in increments of 0.1.

The mapping process can be thought of as labeling the clusters produced by the tensor factorization. E.g. for a latent dimension z with a void value below θ void for the DOBJ and IOBJ modes, its label is simply SUBJ-DOBJ-IOBJ. This label is assigned as an SCF to all the verbs with probabilities over θ verb in z.

If a dimension's characteristic SCF does not correspond to an SCF in the gold standard, that Note that multiple dimensions may be mapped to each SCF, because we chose the number of latent dimensions to be greater than the number of SCFs in the inventory. This decision allows the system to detect semantic structure in the data at a finer-grained level, which we hypothesized would improve overall accuracy on subcategorization acquisition, and to discover multiple lexical classes within a single argument slot. The relationship between number of dimensions mapping to an SCF and the frequency of the SCF is somewhat complex.

To the extent that different verbs appear in different clusters, we expect that a larger number of dimensions mapping to an SCF roughly corresponds to higher type frequency of the SCF. However, some clusters contain more verbs than others; also, more clusters may indicate more semantic variability in argument slot fillers, without corresponding to higher frequency. A general relationship between type frequency and number of dimensions can be seen in Table 2, although note the high number of clusters mapped to the clausal complement frames SUBJ-XCOMP and SUBJ-CCOMP, possibly because these relations are semantically variable and used for adjuncts as well as arguments.

Tuning parameters

We used ten-fold cross-validation to tune the parameters θ verb and θ void , as well as to select the best feature combination (see Section 4.2.3). We randomly divided our test verbs into ten sets, each containing either 18 or 19 verbs. For each fold, we selected the parameters that gave the highest accuracy on the remaining nine-tenths of the verbs agaist the gold standard, and used those settings to acquire the lexicon for the 18 or 19 verbs in the fold.

For all ten folds, the best result was achieved with θ verb = 0.001 and θ void = 0.4, and with modifier features, but without extended PPs or split clause types. For seven of the folds, the best result was achieved with POS features, and for the other three with head features.

Results

Table 3 shows the results for our system after tuning with cross-validation. The parameters are: θ verb = 0.001, θ void = 0.4, POS and modifier features. Precision and recall are averaged over the ten folds. The standard deviation for precision was 4.3 and for recall 5.9. The final system achieves an F-measure of 68.7, well above the baseline 1 F-measure of 36.9, and nearly four Table 3: Results of cross-validation experiment. Precision and recall averaged over ten folds. F-score calculated as harmonic mean of the average P and R.

points better than the baseline 2 F-measure of 64.8. All of the improvement over baseline 2 is in precision, which shows that adding features beyond simple GR co-occurrences is beneficial to accurate SCF acquisition. Because of the Zipfian nature of SCF distributions, the system does not match the precision of baseline 1.

Direct comparison against previous unsupervised SCF acquisition methods on English was not possible because of the use of different data and frame inventories. However, best current methods involving handcrafted rules have reached a ceiling at an F-measure of about 70 [START_REF] Korhonen | A large subcategorization lexicon for natural language processing applications[END_REF][START_REF] Preiss | A system for large-scale acquisition of verbal, nominal and adjectival subcategorization frames from corpora[END_REF]. Our results are promising considering the challenges of less supervised lexical acquisition.

Investigation of features

We also investigated the contribution of the different feature sets on the entire gold standard, using the values for θ verb and θ void which emerged from the cross-validation. The results of the different models are shown in Table 4 (note that the best result is slightly different from that in Table 3 because it is on the entire gold standard, not averaged over folds).

• • • • 63.3 † † 52.6 † † 57.5 † † 181
Table 4: Results for each feature set, with 150 dimensions, θ verb = 0.001, θ void = 0.4. * * significant difference from next row with p < 0.01, * with p < 0.05. † † significant difference from baseline (row 14) with p < 0.01, † with p < 0.05.

The differences in F-measure between the top few models are rather small, but the models show wide variance in precision and recall. Using the head words of the arguments as features seems to favor precision (rows 2, 3, 9, 15, 16), while using POS tags favors recall. This is probably because evidence for different arguments is less sparse using POS tags, making less frequent frames easier to identify, but finer-grained distinctions more difficult. The highest F-scores are achieved with modifier features (rows 1, 2); however, these models strongly favor recall over precision, suggesting that the general applicability of modifiers to many verb classes interferes with accurate identification of SCFs. More balanced models have head features and split clausal complement types (row 3), or head features, extended PPs, and split clausal types (row 9), without losing out on F-score. This suggests that lexical-semantic features are valuable for SCF acquisition. Another trend is towards more accurate models with fewer additional features; individual features and pairs of features seem to provide the most improvement (rows 1-7) over the base model (row 14), but the model with all additional features (row 16) has markedly worse performance, which may indicate a data sparsity problem.

We carried out significance tests for the mentioned model differences using stratified shuffling [START_REF] Yeh | More accurate tests for the statistical significance of result differences[END_REF]. These tests indicate that most of the models (rows 1-11) have significantly higher F-score than the baseline, and most show significant pairwise differences in precision and recall.

Parameter tuning with cross-validation resulted in a θ void of 0.4 (though exploration of the models in Table 4 showed that some models performed better with even lower values). This means that the model only needs to assign a relatively low confidence score to the void feature to infer that a slot is not part of an SCF. This is probably because adjuncts and other noise in the data means that these slots are filled some of the time. We observed many cases of void probabilities nearly equal to 1 in various dimensions -most verbs never occur with an OBJ2, for example. However, void probabilities tend to be fairly low for CCOMP and XCOMP.

Qualitative evaluation

Table 5 shows the accuracy by SCF for the fifteen most frequent frames, using the final model that resulted from cross-validation. The system performs very well on a number of SCFs, especially the most frequent ones such as SUBJ-DOBJ, SUBJ-DOBJ-IOBJ, and SUBJ, but also on some SCFs involving the semantically important particle verbs, such as SUBJ-DOBJ-PRT and SUBJ-IOBJ-PRT.

Precision is lower on frames involving clausal complements (XCOMP and CCOMP), possibly because these GRs are used frequently for adjuncts. Accuracy is also poor on SUBJ-PCOMP and SUBJ-DOBJ-OBJ2. These GRs are rarer and may be subject to parser errors (e.g. OBJ2).

6 Experiment 2: SP Induction

Introduction

Our second experiment looks at the model's ability to induce SPs. We investigate the model's ability to induce multi-way SPs, i.e. the preference of the model for the co-occurrence of a particular verb and all of its particular arguments at the same time.

The calculation of a SP value according to our NTF model is fairly straightforward. Recall that our model yields probabilities p(v|z), i.e. the probability of a verb given a latent dimension, and, for each argument to the verb, p(g|z), i.e. the probability of an argument given a latent dimension. The final SP value SP(v, GR) for a particular verb v and a list of arguments GR then amounts to calculating the product of the probabilities of the verb and the various GRs given a particular latent dimension, and summing over all dimensions (equation 3).

We evaluate our method's ability to induce SPs using the lexicalized (HEAD) model that achieves the best score in our first experiment, i.e. model 2 in Table 4.

Evaluation method

To evaluate the results of the NTF model with regard to SPs, we make use of a pseudodisambiguation task (similar to the one used by [START_REF] Rooth | Inducing a semantically annotated lexicon via em-based clustering[END_REF]). The task allows us to evaluate the generalization capabilities of the model. For a particular tuple (viz. a verb and its various arguments) that appears in a held-out test corpus, we generate random instances in which one or several arguments are substituted by random instantiations. We exhaustively substitute every individual argument, as well as the various random combinations. 4 For the sentence in (1), this yields instances like:

(6) 〈show V , rabbit N , you P , -, -, -, be V , -, -〉 (7) 〈show V , consumption N , tunnel N , -, -, -, dream V , -, -〉 We then calculate SP values according to our model, both for the corpus instance and the random instances. A tuple is considered correct if our model prefers the corpus instance over all random instances. Accuracy is then calculated by averaging over all instances that are part of the test corpus.

We compare our NTF model to a simple non-negative matrix factorization (NMF) model, comparable to the unsupervised model presented by [START_REF] Rooth | Inducing a semantically annotated lexicon via em-based clustering[END_REF]. For this model, a matrix was constructed that contains the pairwise co-occurrence frequencies of verbs and their various arguments. As noted before, a matrix is only able to represent two modes; hence, the first mode consists of the verbs, while the second mode contains the concatenated list of the different argument features. We used the same number of features as with the NTF model, and also factorized to 150 dimensions. According to the NMF model, a tuple is considered correct if, for each argument to the verb, the model prefers the verb-argument pair containing the attested argument over the verb-argument pair containing the random substitute. As a baseline, we include an uninformed random model, which makes a random choice among the various possibilities. 5The models are evaluated using ten-fold cross-validation: the corpus is divided into 10 equal parts; in each fold, models are trained on nine tenths of the corpus, and tested on the remaining tenth.

Results

The results of the ten-fold cross-validation are shown in table 6. The NTF model clearly outperforms the matrix factorization model with regard to the reconstruction of SPs, with the NTF model reaching a score about 10% higher than its NMF counterpart. These results indicate that the use of multi-way data leads to a richer and more accurate representation of SPs. For comparison, (Van de Cruys, 2009) achieved accuracy of 90.89 on a three-way pseudo-disambiguation task, which is less complex than our eight-way task. The results presented here indicate that our model is able to capture syntactic as well as semantic properties. On a coarse-grained level, our model is able to induce a verb's different SCF frames. When we zoom in to the level of individual clusters, we notice that these clusters are often semantically cohesive, expressing the selectional preferences of the verb's argument slots.

The ability to capture both syntax and semantics is an important advantage of our method.

Conclusion

We have presented a novel method for joint unsupervised SCF and SP acquisition which allows the incorporation of a range of features (syntactic, lexical and semantic) in the acquisition process. Although SCFs and SPs are closely related and can complement each other, to the best of our knowledge, no previous work has proposed a joint model for them.

Applying NTF to the multi-way co-occurrence tensor of verbs and their arguments, we are able to cluster verbs from a large corpus according to their syntactic and semantic behaviour. The SCF lexicon that emerges from the clusters yields an F-score of 68.7 against a gold standard, outperforming lexicons produced by our baseline methods. This performance is promising for a largely unsupervised method. The model yields an accuracy of 77.8 on a new pseudodisambiguation evaluation for SPs, in which all arguments of the verb are considered at once, clearly outperforming a matrix factorization model. Our qualitative evaluation reveals that the method is indeed capable of learning rich lexical information about both syntactic and semantic aspects of verb behaviour in corpus data.

In the future, we plan to improve our approach in several directions. In addition to improving the detection of low accuracy SCFs through the use of lexical features that may help to distinguish arguments from adjuncts in clausal complements, we plan to improve precision by using e.g. statistical filtering. We also plan to extend the model to acquire finer-grained SCFs for English. This will involve e.g. refining SCFs with lexicalized elements and including semantically-based SCFs in the inventory, making use of the factorization method's ability to induce latent structure, as demonstrated by the SP evaluation. Finally, we intend to improve our SP acquisition through the use of a more extensive feature set.

A key advantage of this approach is that it is able to combine syntactic SCF and semantic SP acquisition. In the future, we plan to explore the joint induction of verb syntax and semantics in greater depth and look into modelling additional information about semantic verb classes which tend to capture similar SCF and SP behaviour. This could facilitate inducing a more comprehensive lexical resource that supplements the SCFs and SPs with a verb classification -in the style of VerbNet (Kipper-Schuler, 2005) -providing generalizations that can be useful for a wider range of NLP tasks.

Figure 1 :

 1 Figure 1: Matrix representation vs. tensor representation.

Figure 2 :

 2 Figure 2: Graphical representation of the NTF as the sum of outer products.

Frame

Table 2 :

 2 SCFs in order of type frequency in gold standard, with number of latent dimensions mapped to them (model features: POS, modifiers).cluster is excluded from the evaluation. This typically happens with high values of θ void because too many argument slots are simultaneously included in the SCF.

Table 5 :

 5 Results by SCF for fifteen most frequent frames in gold standard with best-performing model.

	Frame	P	R	F Frame	P	R	F
	SUBJ-DOBJ	95.4 98.8 97.0 SUBJ-XCOMP	44.0	98.6 60.9
	SUBJ-DOBJ-IOBJ	89.6 88.5 89.0 SUBJ-DOBJ-XCOMP	45.9	79.4 58.1
	SUBJ	82.7 98.7 90.0 SUBJ-DOBJ-IOBJ-PRT	0.0	0.0	0.0
	SUBJ-IOBJ	80.6 91.5 85.7 SUBJ-CCOMP	35.9 100.0 52.8
	SUBJ-PRT	75.2 87.1 80.7 SUBJ-DOBJ-CCOMP	33.3	71.1 45.4
	SUBJ-DOBJ-PRT	72.8 83.0 77.6 SUBJ-DOBJ-OBJ2	20.0	90.3 32.8
	SUBJ-PCOMP	56.9 45.7 50.7 SUBJ-IOBJ-XCOMP	0.0	0.0	0.0
	SUBJ-IOBJ-PRT	71.9 83.1 77.1
				k
			SP(v, GR) =	i=1	p(v|z i )

g∈GR p(g|z i )

  The three different transitive SCFs clearly exhibit different semantic properties. Dimension 29 seems to represent a general 'trading' dimension, in which the DOBJ argument contains inanimate objects, largely goods. The DOBJ argument has nouns such as thing, material, food,. . . as its top features. Dimension 38, on the other hand, is a transitive frame where the DOBJ argument takes animate objects. The last dimension 44 represents a transitive frame in which the DOBJ argument takes abstract objects.Among the dimensions that map to the SUBJ-IO SCF, i.e. a single PP argument, there are also some interesting semantic and syntactic distinctions. Dimension 91 clearly represents a 'travel' cluster with a location complement; the IO slot for this dimension is mostly PPs lexicalized with to. Dimension 122 is a 'communication' cluster, and again most of the prepositions in the IO slot are to. Dimension 123 consists of verbs that occur with at, largely vision and non-verbal communication verbs. Finally, dimension 134 is interesting, because there is no clear semantic cohesion, but it represents cluster of verbs that take PP for. This indicates that the model is learning both semantic and syntactic regularities.dim91 go, come, return, move, walk, get, run, rush, travel, fly dim 122 talk, speak, listen, write, belong, happen, appeal, come, say, lie dim 123 look, stare, smile, laugh, shout, gaze, glance, glare, grin, scream dim 134 wait, pay, look, care, work, ask, vote, call, prepare, apply

		accuracy (%)
	baseline NMF NTF	29.21 ± .08 69.71 ± .28 77.78 ± .17
	Table 6: Selectional preference accuracy using ten-fold cross-validation (mean accuracy and
	standard deviation)
	6.4 Qualitative evaluation
	Additionally, we performed a qualitative evaluation of the 150 latent dimensions yielded by our
	NTF model. This evaluation shows that our model is indeed able to capture semantic information
	from the data. Recall from Section 5.2 that multiple dimensions map to a single SCF. Our cluster
	analysis shows that such dimensions reflect semantic information. Below are three example
	dimensions (denoted by the top 10 verbs with highest value on each dimension) that all map to
	a simple transitive SCF.

dim 29 buy, sell, use, collect, produce, handle, remove, purchase, obtain, eat dim 38 kill, love, see, like, marry, know, meet, visit, help, say dim 44 examine, identify, see, consider, assess, investigate, discuss, study, determine, explore

Cet article présente une méthode originale pour l'acquisition simultanée de cadres de souscatégorisation (subcategorization frames) et de restrictions de sélection (selectional preferences) appliquée au lexique verbal. L'induction simultanée de ces deux types d'information est vue comme un problème de cooccurrence à plusieurs dimensions. On introduit donc une méthode de factorisation de tenseurs, afin de classer les verbes fréquents d'un grand corpus suivant leur comportement syntaxique. L'approche est fondée sur un ensemble de traits de nature syntaxique et lexicale, y compris des informations de cooccurrence au sein des relations grammaticales qui ne sont pas explicitement représentées dans les schémas de sous-catégorisation. Le dictionnaire de sous-catégorisation produit par la méthode de classification obtient une F-mesure de 68,7 lors de l'évaluation face à un dictionnaire de référence tandis que les restrictions de sélection ont une exactitude (accuracy) de 77,8 en tenant compte de tous les arguments simultanément. KEYWORDS: subcategorization frames, selectional preferences, lexical acquisition, tensor factorization, unsupervised machine learning. KEYWORDS IN FRENCH: cadre de sous-catégorisation, restriction de sélection, acquisition lexicale, factorisation de tenseurs, apprentissage non supervisé.

We count particles (here PRT) as a separate type, though RASP classifies them as a subtype of non-clausal modifiers.

NCSUBJ in RASP.

The algorithm has been implemented in MATLAB, using the Tensor Toolbox for sparse tensor calculations[START_REF] Bader | Matlab tensor toolbox version 2[END_REF].

We do not substitute empty argument slots with lexical arguments; neither do we substitute filled arguments slots with void values. This experiment solely focuses on the induction of selectional preferences; the induction of SCFs is evaluated in experiment 1.

Note that the number of possibilities for both tensor and matrix model is exactly the same.

Acknowledgements

The work in this paper was funded by the Royal Society (UK), the Isaac Newton Trust (Cambridge, UK), EPSRC grant EP/G051070/1 (UK) and EU grant 7FP-ITC-248064 'PANACEA'.

Frame

Example sentence

Frame Example sentence

SUBJ-DOBJ

Susan found the book.

SUBJ-XCOMP

Susan wanted to find the book. Susan picked up the book.

SUBJ-DOBJ-OBJ2

Susan gave Betty a book.

SUBJ-PCOMP

Susan thought about whether she wanted to go.

SUBJ-IOBJ-XCOMP

Susan appeared to Peter to be worried.

SUBJ-IOBJ-PRT

Susan gave up on the project.

Table 1: Fifteen SCFs with highest type frequency in our gold standard, with example sentences.