Jacques Alev

¸ois Dumas

ON ENVELOPING SKEW FIELDS OF SOME LIE SUPERALGEBRAS

Keywords: Mathematics Subject Classification. Primary 17B35; Secondary 16S30, 16S85, 16K40 Simple Lie superalgebra, enveloping algebra, Gelfand-Kirillov hypothesis, Weyl skew fields. 1

We determine the skew fields of fractions of the enveloping algebra of the Lie superalgebra osp(1, 2) and of some significant subsuperalgebras of the Lie superalgebra osp(1, 4). We compare the kinds of skew fields arising from this "super" context with the Weyl skew fields in the classical Gelfand-Kirillov property.

Introduction

This paper deals with the question of a possible analogue of the Gelfand-Kirillov property for the enveloping algebras of Lie superalgebras. Let us recall that a finite dimensional complex Lie algebra g satisfies the Gelfand-Kirillov property when its enveloping skew field, that is the skew field of fractions of the enveloping algebra U (g), is isomorphic to a Weyl skew field over a purely transcendental extension of C. A rich literature has developed on this topic from the seminal work [START_REF] Gelfand | Sur les corps liés aux algèbres enveloppantes des algèbres de Lie[END_REF] and we refer to the papers [START_REF] Alev | The Gelfand-Kirillov conjecture for Lie algebras of dimension at most eight[END_REF], [START_REF] Premet | Modular Lie algebras and the Gelfand-Kirillov conjecture[END_REF] and their bibliographies for an overview on it.

A natural starting point for the same problem for a finite dimensional complex Lie superalgebra g is the classification of the classical simple Lie superalgebras (see [START_REF] Kac | Lie superalgebras[END_REF], [START_REF] Musson | Lie superalgebras and enveloping algebras[END_REF]) and more precisely the study of the orthosymplectic Lie superalgebra osp (1, 2n) since this is the only case in the classification whose enveloping algebra is a domain (see [START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF], [START_REF] Gorelik | The annihilation theorem for the Lie superalgebra osp(1,2ℓ)[END_REF]). This topic is introduced and discussed by Musson in [START_REF] Musson | On the Goldie quotient ring of the enveloping algebra of a classical simple Lie superalgebra[END_REF] who proves in particular that Frac (U (osp(1, 2n))) is not isomorphic to a Weyl skew field over a purely transcendental extension of C when n = 1. We show here that the same is true for any n describing explicitely some classes of skew fields arising from this context. The even part g 0 of g = osp(1, 2n) is the Lie algebra sp(2n) of the symplectic group, for which the Gelfand-Kirillov property remains an open question (see [START_REF] Premet | Modular Lie algebras and the Gelfand-Kirillov conjecture[END_REF]). Therefore we concentrate in this exploratory paper on the case of osp(1, 2) and on some significant subsuperalgebras of osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF]. We consider in osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] the Lie subsuperalgebras n + , b + and p + which have as even parts respectively the nilpotent positive part, the associated Borel subalgebra and the associated parabolic subalgebra in the triangular decomposition of the even part g 0 = sp(4). Determining their enveloping skew fields is the content of sections 2 and 3 of the paper.

The skew fields appearing in this "super" context are skew fields of rational functions mixing classical Weyl relations xyyx = 1 and "fermionic" relations xy + yx = 1 (or equivalently xy = -yx up to rational equivalence) between the generators. A noteworthy fact is that these relations are braided and not necessarily pairwise separable up to isomorphism as in the case of the classical Weyl skew fields. The main properties of these skew fields, which already appeared in [START_REF] Alev | Corps de Weyl mixtes[END_REF] and [START_REF] Richard | Équivalence rationnelle d'algèbres polynomiales classiques et quantiques[END_REF], are given in section 1.

We end this introduction by a short reminder on the para-Bose definition of the Lie superalgebra osp(1, 2n) and its enveloping algebra (see [START_REF] Ch | A Lie superalgebraic interpretation of the para-Bose statistics[END_REF], [START_REF] Palev | The quantum superalgebra Uq[osp(1|2n)]: deformed para-Bose operators and root of unity representations[END_REF]). The basefield is C. We fix an integer n ≥ 1. We have osp(1, 2n) = g 0 ⊕ g 1 where the even part g 0 is the Lie algebra sp(2n) of the symplectic group and g 1 is a vector space of dimension 2n. As a Lie superalgebra, osp(1, 2n) is generated by the 2n elements b

± i (1 ≤ i ≤ n) of a basis of the odd part g 1 . The 2n 2 + n elements {b ± j , b ± k } (1 ≤ j ≤ k ≤ n) and {b + j , b - k } (1 ≤ j, k ≤ n) form a basis of g 0 . The dimension of the vector space osp(1, 2n) is 2n 2 + 3n.
The brackets are given by the so called "parabose" relations:

[{b ξ j , b η k }, b ǫ ℓ ] = (ǫ -ξ)δ jℓ b η k + (ǫ -η)δ kℓ b ξ j (1)
[{b ξ i , b η j }, {b ǫ k , b ϕ ℓ }] = (ǫ -η)δ jk {b ξ i , b ϕ ℓ } + (ǫ -ξ)δ ik {b η j , b ϕ ℓ } + (ϕ -η)δ jℓ {b ξ i , b ǫ k } + (ϕ -ξ)δ iℓ {b η j , b ǫ k }. (2)
By the PBW theorem (see [START_REF] Musson | Lie superalgebras and enveloping algebras[END_REF]), the enveloping algebra U (osp(1, 2n)) is generated by the 2n 2 + n elements:

b ± i , k i := 1 2 {b - i , b + i } for 1 ≤ i ≤ n, (3)
a ± ij := 1 2 {b ± i , b ± j }, s ij := 1 2 {b - i , b + j }, t ij := 1 2 {b + i , b - j } for 1 ≤ i < j ≤ n, (4)
with commutation relations deduced from (1) and (2) taking {x, y} = xy+yx if x, y ∈ g 1 , and [x, y] = xy-yx otherwise. The enveloping algebra U (sp(2n)) of the even part is the subalgebra of U (osp(1, 2n)) generated by the 2n

2 + n elements (b ± i ) 2 , k i for 1 ≤ i ≤ n, and a ± ij , s ij , t ij for 1 ≤ i < j ≤ n.
1. Some skew fields 1.1. Definitions and notations. We fix the basefield to be C. As usual A 1 is the Weyl algebra, that is the algebra generated over C by two generators x, y satisfying the commutation law xyyx = 1. We also define A 1 as the algebra generated over C by two generators u, v satisfying the commutation law uv + vu = 1. For any nonnegative integers r, s, we denote by A s r the C-algebra:

A s r = A 1 ⊗ A 1 ⊗ • • • ⊗ A 1 r factors ⊗ A 1 ⊗ A 1 ⊗ • • • ⊗ A 1 s factors
This is clearly a noetherian domain, so we can define D s r = Frac A s r . For any integer t ≥ 0, we consider the polynomial algebra C[z 1 , . . . , z t ], the noncommutative noetherian domain A s r,t = A s r ⊗ C[z 1 , . . . , z t ] and its skew field of fractions D s r,t = Frac A s r,t . In particular D s r = D s r,0 . If s = 0 and r ≥ 1, D 0 r,t is the classical Weyl skew field usually denoted by D r (C(z 1 , . . . , z t )) or D r,t (C). The following lemma asserts that the D s r,t are a particular case of the mixed Weyl skew fields considered in [START_REF] Alev | Corps de Weyl mixtes[END_REF].

1.2. Lemma. The skew field D s r,t is isomorphic to the skew field of fractions of the algebra A s r,t generated over C by 2r + 2s + t generators x 1 , . . . , x r , y 1 , . . . y r , u 1 , . . . , u s , w 1 , . . . , w s , z 1 , . . . , z t satisfying the commutation relations:

[x i , y i ] = 1, [x i , y j ] = [x i , x j ] = [y i , y j ] = 0 (1 ≤ i = j ≤ r), u i w i = -w i u i , [u i , w j ] = [u i , u j ] = [w i , w j ] = 0 (1 ≤ i = j ≤ s), [x i , u j ] = [x i , w j ] = [y i , u j ] = [y i , w j ] = 0 (1 ≤ i ≤ r, 1 ≤ j ≤ s) [x i , z k ] = [y i , z k ] = [u j , z k ] = [w j , z k ] = [z k , z ℓ ] = 0 (1 ≤ i ≤ r, 1 ≤ j ≤ s, 1 ≤ k, ℓ ≤ t).
Proof. For any 1 ≤ i ≤ s, let us consider the copy of A 1 generated by u i , v i with relation

u i v i + v i u i = 1. The element w i := u i v i -v i u i = 2u i v i -1 of A 1 satisfies w i u i = -u i w i and w i v i = -v i w i .
In the skew field of fractions, the subfield generated by u i , v i is isomorphic to the subfield generated by

u i , w i since v i = 1 2 u -1 i (w i + 1)
. Hence the proof is complete. We sum up in the following proposition some basic facts about the skew fields D s r,t . It shows in particular that for s = 0 the skew fields D s r,t are not isomorphic to classical Weyl skew fields. 1.3. Proposition. Let r, s, t be any nonnegative integers. Then:

(i) the Gelfand-Kirillov transcendence degree of D s r,t equals to 2r+2s+t; (ii) the center of D s r,t is C(u 2 1 , . . . , u 2 s , w 2 1 , . . . , w 2 s , z 1 , . . . , z t ), with the no- tations of lemma 1.2; (iii) D s r,t is isomorphic to a classical Weyl skew field D 0 r ′ ,t ′ if and only if s = 0, r = r ′ and t = t ′ .
Proof. The algebra A s r,t of lemma 1.2 is a particular case of the algebras S Λ n,r studied in [START_REF] Richard | Équivalence rationnelle d'algèbres polynomiales classiques et quantiques[END_REF]. Explicitly A s r = S Λ n,r for n = r + 2s + t and Λ = (λ ij ) the n × n matrix with entries in C defined by λ r+2k-1,r+2k = λ r+2k,r+2k-1 = -1 for any 1 ≤ k ≤ s, and λ i,j = 1 in any other case. Then points (i) and (ii) follow respectively from proposition 1.1.4 and proposition 3.3.1 of [START_REF] Richard | Équivalence rationnelle d'algèbres polynomiales classiques et quantiques[END_REF]. Suppose now that D s r,t is isomorphic to The argument used in the proof of point (iii) of the previous proposition allows to show the following proposition, as predicted in [START_REF] Musson | On the Goldie quotient ring of the enveloping algebra of a classical simple Lie superalgebra[END_REF]. 1.5. Proposition. For any integer n ≥ 1, Frac (U (osp(1, 2n))) is not isomorphic to a classical Weyl skew field D 0 r,t for any r ≥ 1, t ≥ 0. More generally, for any subsuperalgebra g of osp(1, 2n) containing the generators b + i and b - i for some

D 0 r ′ ,t ′ for some r ′ ≥ 1, t ′ ≥ 0. Denote G(L) = (L × ) ′ ∩ C × the
1 ≤ i ≤ n, Frac (U (g)) is not isomorphic to a classical Weyl skew field D 0 r,t for any r ≥ 1, t ≥ 0. Proof. If g contains b + i and b - i , it contains the element k i = 1 2 {b + i , b - i }. Then U (g) contains the element z i = b + i b - i -b - i b + i + 1 = 2b + i b - i -2k i + 1. Using relation (1), we have [k i , b + i ] = b + i . An obvious calculation gives z i b + i = -b + i z i . It follows that -1 ∈ G(Frac (U (g)))
; as at the end of the proof of proposition 1.3 we conclude that Frac (U (g)) cannot be isomorphic to a classical Weyl skew field.

The skew fields D s r,t are the most simple and natural way to mix classical Weyl skew fields D r,t (C) with "fermionic" relations uw = -wu. However we will see in the following that they are not sufficient to describe the rational equivalence of enveloping algebras of Lie superalgebras. Some "braided" versions of mixed skew fields are necessary. The low dimensional examples useful for the following results are introduced in [START_REF] Alev | Corps de Weyl mixtes[END_REF]. Their generalization in any dimension are the subject of a systematic study in the article [START_REF] Richard | Équivalence rationnelle d'algèbres polynomiales classiques et quantiques[END_REF]. We recall here their definitions and main properties.

1.6. Definitions and notations. Let S 3 be the algebra generated over C by three generators x, y, z satisfying:

xy -yx = 1, xz = -zx, yz = -zy.
Crossing two copies of S 3 , we define S 4 as the algebra generated over C by four generators x 1 , x 2 , y 1 , y 2 satisfying:

x 1 y 1 -y 1 x 1 = 1, x 1 y 2 = -y 2 x 1 , x 1 x 2 = -x 2 x 1 x 2 y 2 -y 2 x 2 = 1, x 2 y 1 = -y 1 x 2 , y 1 y 2 = -y 2 y 1 .
The algebras S 3 and S 4 are obviously noetherian domains. We denote F 3 = Frac S 3 and F 4 = Frac S 4 .

The algebra S 4 is the case n = 2 of the family of quantum Weyl algebras A q,Λ n introduced in [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF] when all nontrivial entries λ ij of Λ are equal to -1 and all entries q i of q are equal to 1. They have been intensively studied (we refer to [START_REF] Giaquinto | Quantum Weyl algebras[END_REF] and to section 1.3.3 of [START_REF] Richard | Hochschild homology and cohomology of some classical and quantum noncommutative polynomial algebras[END_REF] for a survey and references), are simple of center C and have the same Hochschild homology and cohomology as the classical Weyl algebra A n (C). A similar study for S 3 lies in sections 5 and 7 of [START_REF] Richard | Hochschild homology and cohomology of some classical and quantum noncommutative polynomial algebras[END_REF]. 1.7. Proposition. The following holds for the skew fields F 3 and F 4 :

(i) the Gelfand-Kirillov transcendence degrees of F 3 and F 4 are 3 and 4 respectively ; (ii) the center of F 3 is C(z 2 ), and the center of F 4 is C; (iii) F 3 and F 4 are not isomorphic to D s r,t , for any r, s, t ≥ 0.

Proof. These properties are proved under slightly different assumptions in section 3 of [START_REF] Alev | Corps de Weyl mixtes[END_REF]. With the notation of [START_REF] Richard | Équivalence rationnelle d'algèbres polynomiales classiques et quantiques[END_REF], we have S 3 = S Λ 2,1 and S 4 = S Λ 2,2

for Λ = 1 -1 -1 1 . Then points (i) and (ii) follow respectively from proposition 1.1.4 and proposition 3.3.1 of [START_REF] Richard | Équivalence rationnelle d'algèbres polynomiales classiques et quantiques[END_REF]. Suppose that F 3 is isomorphic to some D s r,t . Comparing the Gelfand-Kirillov transcendence degree, we necessarily have (r, s, t) = (0, 0, 3), (1, 0, 1) or (0, 1, 1). The first case is obviously excluded since F 3 is not commutative. The second case is impossible because, with the notation G(L) recalled in the proof of proposition 1.3, we know that G(D 0 1,1 ) = {1} by theorem 3.10 of [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF], while it is clear that -1 ∈ G(F 3 ). The third case is also impossible because, denoting E(L) = [L, L] ∩ C the trace on C of the subspace generated by the commutation brackets for any skew field L over C, we have E(D 1 0,1 ) = {0} by proposition 3.9 of [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF], and E(F 3 ) = C since D 1 (C) ⊂ F 3 . Suppose now that F 4 is isomorphic to D s r,t . Since the transcendence degree of the center of D s r,t is at least t, it follows from point (ii) that s = t = 0. Therefore F 4 would be isomorphic to the usual Weyl skew field D 0 2,0 . One more time this is impossible because G(D 0 2,0 ) = {1} and -1 ∈ G(F 4 ).

1.8. Remarks. Let us consider the algebra A s r,0 with the notations of lemma 1.2. If r ≥ 1 and s ≥ 1, the subfield of D s r generated by x 1 w 1 , y 1 w -1 1 and u 1 is isomorphic to F 3 . If r ≥ 2 and s ≥ 1, the subfield of D s r generated by

x 1 w 1 , y 1 w -1 1 , x 2 u 1 and y 2 u -1 1 is isomorphic to F 4 .
In other words, F 3 can be embedded in any D s r such that r ≥ 1, s ≥ 1 and F 4 can be embedded in any D s r such that r ≥ 2, s ≥ 1. More deeply it follows from proposition 5.3.3 of [START_REF] Richard | Équivalence rationnelle d'algèbres polynomiales classiques et quantiques[END_REF] that F 4 cannot be embedded in some D s r,t for r ≤ 1.

1.9. Illustration. We illustrate the definitions of the skew fields under consideration by the following graphs, stressing the particular nature of the relevant relations. The vertices are parametrized by some system of generators.

A directed edge a• / / • b between two generators a and b means that abba = 1, an undirected edge a•

• b means that ab = -ba, and no edge between two generators means that they commute.

D s r,t x 1 • • y 1 x 2 • • y 2 • • • xr • • yr u 1 • • w 1 u 2 • • w 2 • • • us • • ws z 1 • z 2 • • • • zt • F 3 •z x• / / •y F 4 x 1 • / / •y 1 x 2 • / / •y 2 2.
The enveloping skew field of the Lie superalgebra osp(1, 2)

2.1. Notations. Applying ( 1) and ( 3) for n = 1, the algebra U (osp(1, 2)) is generated by b + , b -, k with relations:

kb + -b + k = b + , kb --b -k = -b -, b -b + = -b + b -+ 2k. (5)
It is clearly an iterated Ore extension

U (osp(1, 2)) = C[b + ][k ; δ][b -; τ, d],
where δ is the derivation b Proof. By obvious calculations using (5), the element (i) With the notations used in the proof of the previous proposition, we have in U ′ the identities f = 1 4 e -1 (ω -k 2 +2k) and [ 1 2 e -1 k, e] = 1. Therefore Frac U (sl(2)) is the subfield of Frac U (osp(1, 2)) generated by e = 1 2 (b + ) 2 , y ′ := (b + ) -2 k = (b + ) -1 y and ω with relations y ′ eey ′ = 1, ωe = eω and ωy ′ = y ′ ω. We recover the well known Gelfand-Kirillov property that Frac U (sl(2)) is a classical Weyl skew field D 1 over a center C(ω) of transcendence degree one. With the conventions of 1.9, we can illustrate this skew fields embedding by:

+ ∂ b + in C[b + ], τ
z := b + b --b -b + + 1 = 2b + b --2k + 1 satisfies zb + = -b + z and zk = kz. Since b -= 1 2 (b + ) -1 (z + 2k -1) in the algebra U ′ := C(b + )[k ; δ][b -; τ, d], we have U ′ = C(b + )[k ; δ][z ; τ ′ ] with kb + -b + k = b + , zk = kz and zb + = -b + z. Set- ting y := (b + ) -1 k, we obtain U ′ = C(b + )[y; ∂ b + ][z ; τ ′ ] with yb + -b + y = 1, zb + = -b + z and zy = -yz. Hence Frac U ′ = Frac U (osp(1, 2)) is isomorphic to F 3 . 2.3. Remarks. We know that U (sl(2)) is the subalgebra of U (osp(1, 2
• ω y ′ • / / •e Frac (U(sl(2))) ⊂ •z y• / / •b + Frac (U(osp(1, 2)))
(ii) By previous proposition 2.2 and point (ii) of proposition 1.7, the center of Frac (U (osp(1, 2))) is C(z 2 ). The element z lying in U (osp(1, 2)), it follows that the center of U (osp(1, 2)) is C[z 2 ]. A straightforward calculation shows that z 2 = 4ω -2z + 3 = 4ω -2(z -1) + 1, or equivalently (z + 1) 2 = 4(ω + 1). Since z -1 = b + b -b -b + by definition of z, we recover the well known property, see [START_REF] Pinczon | The enveloping algebra of the Lie superalgebra osp(1,2)[END_REF], that the center of

U (osp(1, 2)) is C[θ] for θ the super Casimir operator θ := ω -1 2 (b + b --b -b + ), (6)
with ω the usual Casimir operator of the even part U (sl( 2)). On one hand the above expression of z 2 becomes z 2 = 4θ + 1. On the other hand, (6) implies z -1 = 2ω -2θ. We deduce that (2ω -2θ + 1) 2 = 4θ + 1, or equivalently:

ω 2 -(2θ -1)ω + θ(θ -2) = 0. ( 7
)
This relation of algebraic dependance between θ and ω is exactly the one given in proposition 1.2 of [START_REF] Pinczon | The enveloping algebra of the Lie superalgebra osp(1,2)[END_REF] up to a normalization of the coefficients.

3.

Enveloping skew fields of some Lie subsuperalgebras of osp(1, 4) 3.1. Definitions and notations. We apply for n = 2 the description of osp(1, 2n) recalled at the end of the introduction. We have osp(1, 4) = g 0 ⊕g 1 where g 1 is a vector space of dimension 4 with basis b

+ 1 , b + 2 , b - 1 , b - 2
and g 0 is the Lie algebra sp(4) of dimension 10 with basis:

c + 1 = 1 2 {b + 1 , b + 1 }, c + 2 = 1 2 {b + 2 , b + 2 }, c - 1 = 1 2 {b - 1 , b - 1 }, c - 2 = 1 2 {b - 2 , b - 2 }, a + = 1 2 {b + 1 , b + 2 }, a -= 1 2 {b - 1 , b - 2 }, s = 1 2 {b - 1 , b + 2 }, t = 1 2 {b + 1 , b - 2 }, k 1 = 1 2 {b - 1 , b + 1 }, k 2 = 1 2 {b - 2 , b + 2 }. (8)
The brackets between these 14 generators of osp(1, 4) are computed by the relations (1) et [START_REF] Alev | Corps de Weyl mixtes[END_REF]. By ( 3) and ( 4) the algebra U (osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF]) is generated to k 1 , k 2 , that is :

[k 1 , b + 1 ] = b + 1 , [k 1 , b + 2 ] = 0, [k 2 , b + 1 ] = 0, [k 2 , b + 2 ] = b + 2 , [k 1 , c + 1 ] = 2c + 1 , [k 1 , c + 2 ] = 0, [k 2 , c + 1 ] = 0, [k 2 , c + 2 ] = 2c + 2 , [k 1 , a + ] = a + , [k 1 , t] = t, [k 2 , a + ] = a + , [k 2 , t] = -t, [k 1 , k 2 ] = 0. (11)
It follows that b + is a Lie subsuperalgebra of osp(1, 4) and that b + 0 is a Lie subalgebra of g 0 containing as direct summands the nilpotent Lie subalgebra n + 0 and the abelian Lie subalgebra h. The change of basis [START_REF] Kac | Lie superalgebras[END_REF] in n + 0 and the change of basis

h 1 := k 2 , h 2 := k 1 -k 2 , (12)
in h allow to rewrite the action of h on n + 0 as:

[h 1 , x 1 ] = -x 1 , [h 1 , x 2 ] = 2x 2 , [h 1 , x 3 ] = x 3 , [h 1 , x 4 ] = 0, [h 2 , x 1 ] = 2x 1 , [h 2 , x 2 ] = -2x 2 , [h 2 , x 3 ] = 0, [h 2 , x 4 ] = 2x 4 . (13)
We conclude that in the Lie subsuperalgebra b + of g = osp(1, 4), the even part b + 0 is isomorphic to the positive Borel subalgebra in the triangular decomposition of g 0 = sp(4), and the abelian Lie subalgebra h is isomorphic to the corresponding Cartan subalgebra.

3.1.3. The parabolic subsuperalgebra p + . We introduce in the odd part g 1 of osp(1, 4) the subspace p + 1 := g + 1 ⊕ Cb - 2 = Cb + 1 ⊕ Cb + 2 ⊕ Cb - 2 and in the even part g 0 the subspace p + 0 := b + 0 ⊕ Cc - 2 = n + 0 ⊕ h ⊕ Cc - 2 . We define p + := p + 0 ⊕ p + 1 . We calculate in osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] the 48 brackets between the 10 generators of p + , adding to the 30 brackets of ( 9) and ( 11) the 18 brackets related to b - 2 , c - 2 , that is :

{b - 2 , b + 2 } = 2k 2 , [b - 2 , k 1 ] = 0, [b - 2 , a + ] = b + 1 , {b - 2 , b + 1 } = 2t, [b - 2 , k 2 ] = b - 2 , [b - 2 , t] = 0, [c - 2 , c + 2 ] = 4k 2 , [c - 2 , k 1 ] = 0, [c - 2 , a + ] = 2t, [c - 2 , c + 1 ] = 0, [c - 2 , k 2 ] = 2c - 2 , [c - 2 , t] = 0, [c - 2 , b + 1 ] = 0, [c - 2 , b + 2 ] = 2b - 2 , [c - 2 , b - 2 ] = 0, {b - 2 , b - 2 } = c - 2 , [b - 2 , c + 1 ] = 0. [b - 2 , c + 2 ] = 2b + 2 . ( 14
)
It follows that p + is a Lie subsuperalgebra of osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] and that p + 0 is a Lie subalgebra of g 0 containing as direct summands the Borel subalgebra b + 0 and the line Cc - 2 . The changes of basis [START_REF] Kac | Lie superalgebras[END_REF] and ( 12) allow to rewrite the

  trace on C × of the commutator subgroup of the group of nonzero elements of L for any skew field L over C. It follows from theorem 3.10 of[START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF] that G(D 0 r ′ ,t ′ ) = {1} while it is clear by lemma 1.2 that -1 ∈ G(D s r,t ) if s ≥ 1.Hence s = 0. Then comparing the centers we deduce t = t ′ and comparing the Gelfand-Kirillov transcendence degrees we conclude r = r ′ . 1.4. Remark. Each copy in D s r,t of the algebra A 1 generated over C by two generators u, w satisfying uw = -wu can be viewed as the enveloping algebra of the nilpotent Lie superalgebra f = f 0 ⊕ f 1 where f 0 = Cz ⊕ Ct and f 1 = Cu ⊕ Cw with brackets {u, u} = z, {w, w} = t, {u, w} = 0.

2 . 2 .

 22 is the automorphism of C[b + ][k ; δ] defined by τ (b + ) = -b + and τ (k) = k + 1, and d is the τ -derivation of C[b + ][k ; δ] defined by d(b + ) = 2k and d(k) = 0. Proposition. Frac U (osp(1, 2)) is isomorphic to F 3 .

1 2

 1 )) generated by (b + ) 2 , (b -) 2 and k. Actually up to a change of notations e := (b + ) 2 and f := -1 2 (b -) 2 it follows from (5) that [k, e] = 2e, [k, f ] = -2f et [e, f ] = k. We introduce ω := 4ef + k 2 -2k the usual Casimir in U (sl(2)).

Acknowledgements

We would like to thank Alfons Ooms for drawing our attention to the case of the second parabolic subalgebra considered in remark 3.11.

by the 10 elements b

a + , a -, s, t. The enveloping algebra U (sp(4)) of the even part of osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] is the subalgebra generated by (b + 1 ) 2 , (b + 2 ) 2 , (b - 1 ) 2 , (b - 2 ) 2 , k 1 , k 2 , a + , a -, s, t.

We describe now some subsuperalgebras of osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] whose enveloping skew field we study in the following. The even part of each of them satisfies the usual Gelfand-Kirillov property.

3.1.1. The nilpotent subsuperalgebra n + . We define in g 1 the subspace g + 1 := Cb + 1 ⊕ Cb + 2 and in g 0 the subspace n + 0 := Cc + 1 ⊕ Cc + 2 ⊕ Ca + ⊕ Ct. We denote n + := n + 0 ⊕ g + 1 . We calculate in osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] the 17 brackets between the 6 generators of n + :

It follows that n + is a Lie subsuperalgebra of osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] and that n + 0 is a Lie subalgebra of g 0 . Moreover setting

we rewrite the relations of the first two rows of (9) as:

which are the relations between the Chevalley generators in the enveloping algebra of the nilpotent positive part corresponding to the root system of type B 2 . We conclude that in the Lie subsuperalgebra n + of g = osp(1, 4), the even part n + 0 is isomorphic to the nilpotent positive part in the triangular decomposition of g 0 = sp(4).

We calculate in osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF] the 30 brackets between the 8 generators of b + , adding to the 17 brackets of (9) the 13 brackets related action of c - 2 on b + 0 as:

We conclude that in the Lie subsuperalgebra p + of g = osp(1, 4), the even part p + 0 is isomorphic to the positive parabolic subalgebra in the triangular decomposition of g 0 = sp(4).

3.1.4. Remark: the Levi subsuperalgebra l associated to p + . It follows from relations [START_REF] Musson | The enveloping algebra of the Lie superalgebra osp(1,2r)[END_REF] and ( 14) that the subspace l := l 0 ⊕ l 1 with l [START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF]. It is clear that l is isomorphic to osp(1, 2). The Lie algebra l 0 is the Levi subalgebra associated to p + 0 in g 0 and is isomorphic to sl(2).

This is a particular case of the more general theorem 2.1 of [START_REF] Musson | The enveloping algebra of the Lie superalgebra osp(1,2r)[END_REF]. In the algebra

, the elements:

satisfy

Hence by lemma 1.2 we conclude that Frac U (n

, a + , t with commutation relations coming from ( 9):

The element t ′ defined in [START_REF] Richard | Hochschild homology and cohomology of some classical and quantum noncommutative polynomial algebras[END_REF] lies in Frac U (n + 0 ) and the element y defined in (17) satisfies

is the subfield of Frac U (n + ) generated by (b + 1 ) 2 , y, a + , t ′ with more simple commutation relations:

We recover the well known Gelfand-Kirillov property that Frac

) with notations [START_REF] Kac | Lie superalgebras[END_REF]. Up to a normalization we recover the well known expressions for the generators of the center of U (n + 0 ) in terms of Chevalley generators.

The following theorem gives a decomposition of Frac U (b + ) into two commuting subfields respectively isomorphic to D 0 1 and F 4 .

)) by U (n + ) and U (h) with the commutation relations ( 16) and the action of k 1 and k 2 on b + 1 , b + 2 , a + , t coming from [START_REF] Musson | The enveloping algebra of the Lie superalgebra osp(1,2r)[END_REF]. Taking again the notations used in the proof of proposition 3.2, this action extends to

The change of variables:

gives:

We replace y by:

which satisfies:

We deduce with (20) that the subalgebra

We have now to formulate the commutation relations of the last generator t ′ with the generators of V. It is clear that

We try to replace t ′ by a generator of the form a + t ′ + p commuting with a + and k ′ 2 , with p ∈ W. A solution is given by p = -a + k ′ 2 . In other words, the

This relation becomes y ′ t ′′t ′′ y ′ = 1 with notation:

Since 2 and a + is isomorphic to the Weyl algebra A 1 , the subalgebra generated by k ′ 1 , b + 1 , y ′ and t ′′ is isomorphic to the algebra S 4 , each element of the first subalgebra commutes with each element of the second one, and Frac U (b + ) = Frac (A 1 ⊗ S 4 ). Hence the proof is complete.

Then Frac U (b + 0 ) is generated by k ′ 2 , a + , (b + 1 ) 2 , ℓ 1 , y ′′ , t ′′′ and the brackets between these generators are [k ′ 2 , a + ] = [ℓ 1 , (b + 1 ) 2 ] = [y ′′ , t ′′′ ] = 1 and 0 in all other cases. We recover the well known Gelfand-Kirillov property that Frac U (b + 0 ) is a classical Weyl skew field D 3 over a trivial center C.

The following theorem gives a decomposition of Frac U (p + ) into two commuting subfields respectively isomorphic to D 0 2 and F 3 .

Proof. By 3.1.3, U (p + ) is generated in U (osp [START_REF] Alev | Sur le corps de fractions de certaines algèbres quantiques[END_REF][START_REF] Aubry | Zero divisors in enveloping algebras of graded Lie algebras[END_REF]) by U (b + ) and b - 2 with commutation relations coming from ( 11), ( 14) and ( 16). We start replacing in Frac U (n + ) the generators t and a + by:

We define 25), the same is true for ℓ 2 . Moreover we compute:

)) and we apply the method used in proposition 2.2 setting:

To sum up, the subfield L of Frac U (p

We can replace the generator b + 1 by w

In the last step we look at the action of k 1 on L. Technical calculations using (24) and (26) show that, on one hand

As in lemma 4 of [START_REF] Alev | The Gelfand-Kirillov conjecture for Lie algebras of dimension at most eight[END_REF], the last change of variable k ′′ 1 := (k 1 + u 1 v 1 )w -1 1 doesn't change the first three relations and changes the last three into:

We conclude that in Frac U (p + ) the subalgebra generated by k ′′ 1 , w 1 is isomorphic to A 1 , the subalgebra generated by u 1 , v 1 is also isomorphic to A 1 , the subalgebra generated by u 2 , v 2 , z 2 is isomorphic to S 3 , and Frac U (p + ) is isomorphic to Frac (A 1 ⊗ A 1 ⊗ S 3 ).

Remark. The enveloping algebra

Computing the brackets between these generators we find exactly the table of the Lie algebra denoted by L 7,9 in [START_REF] Alev | The Gelfand-Kirillov conjecture for Lie algebras of dimension at most eight[END_REF] p. 565 up to the following change of variables:

It is proved in [START_REF] Alev | The Gelfand-Kirillov conjecture for Lie algebras of dimension at most eight[END_REF] that the Lie algebra p + 0 = L 7,9 satisfies the Gelfand-Kirillov property with Frac U (p + 0 ) = Frac (A 1 ⊗A 1 ⊗A 1 ⊗C[c]). The central generator c and the pairs of elements p i , q i (1 = 1, 2, 3) described in [START_REF] Alev | The Gelfand-Kirillov conjecture for Lie algebras of dimension at most eight[END_REF] as generators of each copy of A 1 correspond with our notations in the proof of theorem 3.6 to:

which gives an explicite description of the embedding:

3.8. Illustration. With the conventions of remark 1.9, proposition 3.2, theorem 3.4 and theorem 3.6 can be represented by the following pictures: Proof. Suppose that Frac U (b + ) is isomorphic to some skew field D s r,t . Comparing the Gelfand-Kirillov transcendence degrees and the centers, we have 2r + 2s + t = 6 and 2s + t = 0, hence Frac U (b + ) would be isomorphic to the usual Weyl skew field D 0 3,0 = D 3 (C) which is impossible because, as at the end of the proof of proposition 1.7, we have G(D 3 (C)) = {1} and -1 ∈ G(Frac U (b + )). Suppose now that Frac U (p + ) is isomorphic to some skew field D s r,t . We obtain 2r + 2s + t = 7 and 2s + t = 1, hence Frac U (p + ) would be isomorphic to D 0 3,1 , which is impossible by the same argument.

3.11. Remark. The Lie algebra sp(4) contains two non isomorphic parabolic subalgebras corresponding to the cases denoted by L 7,7 and L 7,9 in the classification of [START_REF] Alev | The Gelfand-Kirillov conjecture for Lie algebras of dimension at most eight[END_REF]. We have seen in 3.7 that the even part p + 0 of the parabolic subsuperalgebra p + is isomorphic to L 7,9 . But we can also define a subsuperalgebra q + of osp(1, 4) whose even part is the alternative parabolic subalgebra L 7,7 of sp(4). It is defined by q + = q + 0 ⊕ g + 1 with g + 1 = Cb + 1 ⊕ Cb + 2 and q + 0 = b + 0 ⊕ Cs, where s is defined in [START_REF] Giaquinto | Quantum Weyl algebras[END_REF]. A basis of q + 0 is {c + 1 , c + 2 , a + , t, k 1 , k 2 , s} and computing the brackets in osp(1, 4) we retrieve the table of L 7,7 in [START_REF] Alev | The Gelfand-Kirillov conjecture for Lie algebras of dimension at most eight[END_REF] up to the following change of notations: By a method similar to that of theorem 3.6, we can prove that Frac U (q + ) is also isomorphic to Frac (A 1 ⊗ A 1 ⊗ S 3 ).


Zhongwei Tang

Pascal Monasse

Jean-Michel Morel

ON THE MATCHING PRECISION OF SIFT

Keywords: Matching precision, localization precision, scale space, scale-invariant feature transform (SIFT)

Matching precision of scale-invariant feature transform (SIFT) is evaluated and improved in this paper. The aim of the paper is not to invent a new feature detector more invariant than the others. Instead, we focus on SIFT method and evaluate and improve the matching precision, defined as the root mean square error (RMSE) under ground truth geometric transform. Matching precision reflects to some extent the average relative localization precision between two images. For scale invariant feature detectors like SIFT, the matching precision decreases with the scale of features due to the sub-sampling in the scale space. We propose to cancel the sub-sampling to improve the matching precision. But in case of scale change, the improvement is marginal due to the coarse scale quantization in the scale space. One more sophisticated method is also proposed to improve the matching precision in case of scale change. These modifications can be easily extended to other scale invariant feature detectors.

INTRODUCTION

Recent years have seen the blossom of invariant feature detectors [??]. Even though they become more and more invariant to image geometric transform and illumination change, the matching precision has not been carefully studied. Matching precision seems similar to the repeatability, which is defined as the percentage of the repeatable features among all the matched features. One feature is considered repeatable if it and its matched feature are compatible with the ground truth transform within some loose precision threshold (1 pixels is chosen in [??]). However, matching precision directly measures the average residual error for all the correctly matched feature pairs with respect to the ground truth geometric transform. So even if a feature detector gives high repeatability, it does not necessarily mean that the matching precision is high.

The localization precision needs to be clarified here because it is a confusing concept with the matching precision.

Part of this work was supported by the Agence Nationale de la Recherche (ANR) project STEREO (program ASTRID 2012).

Localization precision is used to describe how close on average the position of detected feature is to the true position. In statistics terms, localization precision is called bias. A statistical ensemble is required to define the bias. In the case of feature detection, the underlying statistical ensemble can be interpreted as a collection of images, obtained by disturbing an ideal image by an underlying disturbance model, like noise model, blur model, illumination model, etc. Assume the true position of a feature point is known. The localization precision (bias) can be measured as the distance from the average position of the detected features by a particular feature detector on differently disturbed images to the true position. The localization precision is not uniform in the image domain, different from one feature point to another.

It is difficult to evaluate the localization precision in practice. The computation of localization precision first requires the ideal position of feature points, which is in fact ill-defined. Even if the ideal position of feature points is known, it is not clear what is an appropriate statistical ensemble, which can be deduced from an underlying noise model, a camera model or a model of lighting condition. So in practice, it is impossible to measure the localization precision. However, absolute localization precision is less interesting in computer vision tasks, where the correspondences are usually required. This motivates us to measure the matching precision instead of localization precision. In fact, matching precision reflects to some extent the localization precision. Given enough correspondences between two images, assume that all the feature points in one image are ideal and the ground truth transform between two images is known, then the matching precision is close to the localization precision under the hypothesis that the feature detector has the same localization precision on all the feature points in the other image and the local property of all the features composes an appropriate statistical ensemble. In reality feature points in both images are not ideal and their localization precision is different from point to point. So the matching precision measures the average relative localization precision of matchings between two images.

We first review SIFT method and improve its matching precision in Section 2. The improvement seems to be marginal in case of scale change between two images in the evaluation in Section 3, which motivates a more sophisticated improvement based on local filtering. The extension of the proposed improvement is briefly discussed in Section 4.

SIFT METHOD REVIEW AND IMPROVEMENT

The SIFT method [START_REF] David | Distinctive image features from scaleinvariant keypoints[END_REF] is a complete image comparison algorithm composed of scale-invariant feature detector, gradientbased descriptor and descriptor matching. The features are detected in the scale space of normalized Laplacian, approximated by the difference of Gaussian due to the computational efficiency:

D(x, y, σ) = G(x, y, kσ) -G(x, y, σ) ⊛ I(x, y) (1) ≈ (k -1)σ 2 ∆ G(x, y, σ) ⊛ I(x, y) G(•, •, σ)
is the Gaussian function with standard deviation σ and ⊛ is the convolution operation. Remark that the normalized Laplacian gives scale invariance to the Laplacian threshold in SIFT method. Images of same size with increasing Gaussian blur compose one octave in the scale space. And there is a 2-subsampling between two adjacent octaves to simulate the camera zoom (Fig. 1a). One octave contains N inter + 3 Gaussian blurred images of the same size which are used to compute N inter + 2 difference-of-Gaussian (DoG) images (N inter = 3 by default). The Gaussian blur is increased with the multiplicative factor 2 1/N inter . The 2-subsampling is performed on the image in octave which contains two times the blur of the initial image in the same octave. This convolution-subsampling procedure is repeated until the image is too small for feature detection. It is easy to see that the sampling with respect to the blur is the same for all octaves. So one image has the same nature as its counterparts in the other octaves. This process simulates camera zoom and explains why SIFT method is scale invariant.

Only local extrema with strong Laplacian value in N inter DoG images in the middle of each octave are detected as features. Once a feature is extracted, its 3D position (position and scale) is refined by a 3D interpolation, which makes SIFT points sub-pixel precise. Each feature is assigned a descriptor which is constructed by using the gradient information in the neighborhood. Finally, their 3D coordinate (location and scale) is projected back to the original image.

Remark that the principal error source in SIFT method is that the detected features in scale space are projected back to the original image. Assume a feature located at x with ideal position x 0 disturbed by the error ε: x = x 0 + ε. If this feature is detected in the i-th octave in SIFT scale space, then its final position is 2 i x = 2 i x 0 + 2 i ε. The error is increased by the factor 2 i . This inspires us to cancel the sub-sampling between octaves. The new schema is shown in Fig. 1b. Although this seems to be a one-step modification to SIFT method, there are some details to discuss. Fig. 1: 1a The scale space of SIFT. 1b The improved SIFT schema with sub-sampling canceled.

Blur

Blur plays a very important role in SIFT method because the scale invariance of SIFT is in fact blur invariance and is achieved by simulating the camera blur under different resolutions. SIFT method is based on the assumption that a Gaussian convolution can well approximate the blur introduced by camera system and gives an aliasing-free image subsampling. In fact, it is shown in [START_REF] Morel | On the consistency of the sift method[END_REF] that a well-sampled image should contain a Gaussian blur of standard deviation β = 0.8. Therefore an aliasing-free t-subsampling should be preceded by a Gaussian blur of about β × √ t 2 -1. However, if we cancel the sub-sampling between adjacent octaves, it is equivalent to up-sample images in the scale space and the following conditions should be satisfied:

∆ u( x 2 , y 2 ) = 1 4 (∆u) x 2 , y 2 and ∂ u x 2 , y 2 ∂ • = 1 2 ∂u ∂ • x 2 , y 2 (2)
which means that the Laplacian is 4 times smaller and the gradient is 2 times smaller if an image is up-sampled by 2. For digital images, the above relationships are valid only if the image u is smooth enough. Fig. 2 shows a test for a natural image. The image is first convolved by a Gaussian blur, then followed by an up-sampling by factor 2. The Laplacian and gradient module are computed on the original image and the up-sampled image respectively. Note m the ratio of Laplacian before and after 2-upsampling and n the ratio of gradient norm before and after 2-upsampling. By computing the average and standard deviation of m and n with respect to the added blur, it appears that the above conditions are satisfied only if the added Gaussian blur is bigger than 1.6. This makes the image blur equal to √ 1.6 2 + 0.8 2 ≈ 1.8 if the original image is assumed to already contain a blur 0.8. Similar results are obtained with another dozen of natural images. This experiment is complementary to the one dealing with aliasingfree sub-sampling in [START_REF] Morel | On the consistency of the sift method[END_REF]. Our conclusion is that a good image for feature analysis must contain at least a 1.8 Gaussian blur. There are two ways to achieve this quantity of blur: either we convolve the input image with enough Gaussian blur, or we pre-zoom the input image by 2 to increase the blur to be 1.6, close to 1.8 as required (if the initial image contains Gaussian blur 0.8). This step of pre-zoom is optional in original SIFT in order to increase the number of features.

Fig. 2: Image on the left is convolved by a Gaussian function with standard deviation σ before it is up-sampled by factor 2. The Laplacian value and gradient modulus before and after the up-sampling are compared. Middle: the average and standard deviation of ratio of the Laplacian value before and after 2-upsampling. Right: the average and standard deviation of ratio of gradient modulus before and after 2-upsampling.

3D refinement

Once the local extrema are extracted in 3D scale space, their position can be refined under the assumption that the DoG image can be locally approximated by a second order Taylor expansion. Given a local extrema located at x = (x, y, σ), the DoG function D(x) is expanded at x by: D(x + ∆x) = D(x)+∆x T ∂D ∂x +∆x T ∂ 2 D ∂x 2 ∆x. The peak of this function is attained when its derivative is set to be zero, which gives the offset ∆x = (∆x, ∆y, ∆σ)

T = ∂ 2 D ∂x 2
-1 ∂D ∂x . Sub-pixel precision is thus obtained and the final position is x + ∆x.

If the sub-sampling is canceled, blur between two adjacent scales in octaves increases also by factor 2, 4, 16, • • • . Thus the scale space is sampled more and more sparsely through octaves. This makes it more difficult for the 3D interpolation refinement to produce a precise result. In addition, the SIFT descriptor is constructed approximately on these sparse intervals without really interpolating a new interval. This makes descriptors less accurate. To compensate this effect, the number of intervals is increased with the same factor through octaves (see Fig. 1b). This means that the up-sampling is performed also in the scale direction, just as that in the x and y directions in image.

MATCHING PRECISION EVALUATION

Matching precision is evaluated on pairs of images under different geometric transforms: translation, rotation, zoom, affine transform. The translations are respectively (45, 32), (45.1, 32.1), (45.3, 32.3), (45.5, 32.5), (45.7, 32.7) and (45.9, 32.9). The rotations varies from 15 • to 85 • with the step of 10 • . The zooming factors are respectively 2 1/6 , 2 2/6 , 2 3/6 , 2 4/6 , 2 5/6 and 2 6/6 . The affine transform A is of the parametric form A = R 1 T t R 2 with R 1 and R 2 rotation of 24 • and 37 • respectively, and T t is the tilt in the x direction with compression factor t = 2 1/12 , 2 2/12 , 2 3/12 , 2 4/12 , 2 5/12 and 2 6/12 respectively. The reference image is fixed and the second image is synthesized from the reference one according to the transform by 7th-order spline interpolation to avoid the "ringing" artifact introduced by Fourier interpolation. The pre-zoom of SIFT method is activated and the number of octaves is fixed to be four (the octave index begins with -1). Only local extrema with strong Laplacian value are detected as features and are matched. A RANSAC-like algorithm is performed on the matchings of each octave respectively in order to remove the "outliers" and to estimate the geometric transform for each octave. The matching precision is then computed as the root mean square error (RMSE) on each octave with respect to the estimated transform respectively.

It is shown in Fig. 4 that the matching precision of original SIFT decreases through octaves. This is not surprising because all detected features are finally projected back to the original image. For improved SIFT, the matching precision is kept or even improved through octaves when there is no scale change between two images, namely translation and rotation. However, when a scale change is present, namely zoom and affine transform, the gain in precision is marginal. This is mainly due to the fact that the matched features are detected at different scales (blur) when the transform between two images contains a scale change. The 3D refinement being sensitive to blur, the precision of the refined position and scale for the matched features will be different. So the matching precision, which can be interpreted to some extent as the average relative localization precision, is lower than that in case of translation and rotation.

If we know in advance the transformation between two images is some parametric transform, the above problem of blur inconsistency can be solved to some extent by estimating then compensating the transform using the most precise matchings in the first octave. But in practice, the parametric form of the transformation between two images is unknown due to the 3D effect of scene. Here we concentrate on the cases where the transformation between two images is smooth and can be locally approximated by homography. Although this does not apply when the scene is really 3D, there are already many applications based on this assumption, like image stitching and camera calibration.

The main idea is to use the local filter by homography to increase the matching precision. We detect a dense set of SIFT matching between two images. To have enough matchings for natural images, we consider every pixel as a feature point in the first two octaves of improved SIFT scheme. Only a low Laplacian threshold is used to eliminate very unstable feature points. The matching process is accelerated by dividing the image domain into several blocks and the resulting matchings are pruned by vector filter to obtain reliable matchings. For each SIFT matching, 100 neighboring matchings around it are used to estimate the best local homography in the least-square sense. Then one point in each SIFT matching is adjusted according to its corresponding homography. We evaluate the whole procedure on the different geometric transformations as before. The matchings in octave -1 and 0 are mixed together to have dense matchings over image domain. The evaluation then gives the average matching error without distinguishing their octave index. In Fig. 5, without the local filtering, the matching precision of improved SIFT is coarse due to the relaxed criteria in feature detection. But the precision is largely improved with the local filtering. The default of this method is that not many features can be matched by SIFT under the transformations too "affine", even though almost each pixel is considered as a feature point. This will degrade the filtering performance of local homographies. This explains why the precision decreases in the case of affine transformation with the increase of the parameter from 2 1/12 to 2 6/12 . This is in fact not a problem because we can always make two images to be more similar by transforming one image using a coarse homography between them, even if the relation between both images is not a homography.

For real images, the matching precision is also affected by the noise in the image. To test the performance of the algorithm for real images, a Canon EOS 30D SLR camera with EFS 18 -55mm lens was used to take photos. Three pairs of images were tested (Fig. 6): the first pair for a planar abstract painting, the second pair for an infinite homography, the third pair for a distant wall with small camera motion. Ideally the underlying geometric transformation is a homog- raphy. But for real images, the homography cannot be used to measure the matching precision due to the lens distortion.

Even though the maximal focal length (55mm) was chosen to avoid the lens distortion as much as possible, there still exists small distortion. The bivariate polynomial model, an universal and practical distortion model, which is also consistent with a homography, was used here to evaluate the matching precision. The result is recapitulated in Fig. 7. It seems that the local filtering technique is very efficient to increase the matching precision even with noisy images.

CONCLUSION

The matching precision of SIFT method is reviewed and improved. We show that a simple canceling of sub-sampling in the scale space can improve the matching precision if there is no scale change between images. In the presence of scale change, we propose to improve the matching precision by local homography filtering if the image transform is smooth.

In the future work, we would like to improve the matching precision for more general transforms, including transforms induced by 3D scene. We also plan to extend the work to other feature detectors.

Fig. 3 :

 3 Fig. 3: Some images used in the experiments. The leftmost one is the reference image and the others are synthetized from it.

Fig. 4 :

 4 Fig. 4: The matching precision for the original SIFT and improved SIFT under different transforms. The x-axis is the octave index, from -1 to 2. The y-axis the average residual error (in pixels). Top row: original SIFT. Bottom row: improved SIFT.

Fig. 5 :

 5 Fig. 5: The matching precision of improved SIFT without/with local filter under different geometric transformations.

Fig. 6 :

 6 Fig. 6: Three pairs of images taken by Canon EOS 30D SLR camera with focal length 55mm.

Fig. 7 :

 7 Fig. 7: The matching precision of improved SIFT without/with local filter on real image pairs evaluated by a 10th-degree bivariate polynomial.


Mattias Gybels
email: mattias.gybels@lif.univ-mrs.fr

François Denis
email: francois.denis@lif.univ-mrs.fr

Amaury Habrard
email: amaury.habrard@univ-st-etienne.fr

Alexander Clark

Makoto Kanazawa

Ryo Yoshinaka

Some improvements of the spectral learning approach for probabilistic grammatical inference

Keywords: Probabilistic grammatical inference, Rational series, Machine Learning, Spectral learning, Structured low-rank approximation, Maximum-Likelihood, Baum-Welch Algorithm

Spectral methods propose new and elegant solutions in probabilistic grammatical inference. We propose two ways to improve them. We show how a linear representation, or equivalently a weighted automata, output by the spectral learning algorithm can be taken as an initial point for the Baum Welch algorithm, in order to increase the likelihood of the observation data. Secondly, we show how the inference problem can naturally be expressed in the framework of Structured Low-Rank Approximation. Both ideas are tested on a benchmark extracted from the PAutomaC challenge.

Introduction

One of the main tasks of probabilistic grammatical inference consists in learning probabilistic models of stochastic languages, i.e. probability distributions, from finite samples of strings or trees. This field has recently made huge advances with the emergence of spectral methods, which offer new and elegant solutions to this problem. The proposed algorithms are indeed consistent and efficient. Many approaches have been proposed to learn HMM or Probabilistic Finite Automata (PFA) [START_REF] Bailly | Grammatical inference as a principal component analysis problem[END_REF][START_REF] Hsu | A spectral algorithm for learning hidden markov models[END_REF][START_REF] Bailly | A spectral approach for probabilistic grammatical inference on trees[END_REF][START_REF] Balle | Spectral learning of general weighted automata via constrained matrix completion[END_REF]Balle et al., 2012[START_REF] Balle | Methods of moments for learning stochastic languages : Unified presentation and empirical comparison[END_REF], transducers [START_REF] Balle | A spectral learning algorithm for finite state transducers[END_REF] or graphical models [START_REF] Parikh | A spectral algorithm for latent tree graphical models[END_REF][START_REF] Luque | Spectral learning for non-deterministic dependency parsing[END_REF][START_REF] Anandkumar | A spectral algorithm for latent dirichlet allocation[END_REF][START_REF] Cohen | Experiments with spectral learning of latent-variable PCFGs[END_REF].

In this paper, we mainly focus on the following problem : given a finite sample of strings S independently and identically drawn (i.i.d.) according to an unknown distribution p, infer an approximation of p in the class of rational series. Rational series over a finite alphabet Σ are mappings from Σ * to R that can equivalently be defined by means of weighted automata, or linear representations. More precisely, a series r : Σ * → R is rational if there exists an integer k and a tuple A =< I, (M x ) x∈Σ , T >, where I, T ∈ R k and M x ∈ R k×k for any x ∈ Σ, such that r(x 1 . . . x n ) = I ⊤ M x 1 . . . M xn T . A is called a k-dimensional linear representation of r. The rank of r is the minimal dimension of a linear representation for r.

The spectral learning approach relies on the two following observations : -the Hankel matrix of a rational series r, i.e. the bi-infinite matrix indexed by Σ * × Σ * and defined by H[u, v] = r(uv), has a finite rank, equals to the rank of r ; -a linear representation of r can easily be obtained from the right singular vectors of H. The spectral learning scheme for probabilistic grammatical inference consists then in building the empirical Hankel matrix H S from S, performing a singular value decomposition (SVD) of H S and building a linear representation by using the k-first right singular vectors of H S , where the rank k is given or estimated by cross-validation or other methods. This main scheme admits several variants.

The spectral approach is consistent, elegant and simple to implement. However it should and can be improved. Indeed, considering the k-first right singular vectors of H S boils down to perform a rank-k truncated SVD of H S , i.e. to consider the rank-k matrix H S,k which is the closest to H S according to the Frobenius norm. But H S,k is not a Hankel matrix -we may have uv = u ′ v ′ and H S,k [u, v] = H S,k [u ′ , v ′ ] -and building a linear representation from the right singular vectors of H S,k takes away from the solution. Another way to express the same thing is to say that the Frobenius norm is maybe not the distance that we should minimize. For example, there is no reason that the output solution maximizes the likelihood of the observations. Hence, a first simple idea would be to modify the parameters of the solution output by the spectral learning algorithm so as to increase the likelihood of the learning set. Besides the fact that maximizing the likelihood of data is a hard-problem, we face a specific difficulty : the automaton output by the spectral algorithm is not probabilistic -it may contain negative coefficients, it is not normalized and the sum of the values computed on all strings may differ from 1. Therefore, standard ways to increase the likelihood of observation data, such as the Baum-Welch algorithm, cannot be directly applied. In this paper, we show how to transform the output representation into a representation whose negative coefficients can be made arbitrarily close to 0. Thus normalizing such a representation leads to an automaton which is probabilistic and that can be taken as an input by the Baum-Welch algorithm. The underlying idea is that, if the solution output by the spectral learning algorithm is good enough, taking it as an initial point for the Baum Welch algorithm should further improve the solution. This protocol is experimented on a benchmark made of 10 problems extracted from the PAutomaC Challenge [START_REF] Verwer | Results of the pautomac probabilistic automaton learning competition[END_REF]. The experiments confirm the expected results.

A second idea is to set out precisely from the criteria to be optimized and to design an algorithm able to achieve this optimization task : we look for a rank-k Hankel matrix being the closest to the empirical matrix H S . This optimization task can be expressed and solved within the Structured Low Rank Approximation framework (SLRA), a bunch of methods aiming at solving constrained low-rank approximation problem [START_REF] Markovsky | Structured low-rank approximation and its applications[END_REF][START_REF] Markovsky | Low Rank Approximation : Algorithms, Implementation, Applications[END_REF][START_REF] Markovsky | Software for weighted structured low-rank approximation[END_REF]. However the problem is non convex and the available algorithms and software can only deal with small dimensions matrices. Experiments on the same benchmark demonstrate the potentiality of this approach. However, the current algorithm cannot process high dimensional matrices and the global improvements are quite limited.

The paper is organized as follows. Section 2 introduces the preliminaries on the spectral learning approach and describes the PAutomaC Challenge data. Section 3 describes how the representation output by a spectral learning algorithm can be used as an initialization point for the Baum-Welch algorithm. Section 4 describes the SLRA approach. A conclusion ends the paper.

Preliminaries

Rational series and residuals

Let Σ be a finite alphabet and Σ * be the set of all strings defined on Σ. Let us denote by ≺ the quasi-lexicographical ordering on Σ * : strings are ordered first by length and then by lexicographical order. Let ǫ denote the empty string and |w| denote the length of w. For any n ∈ N, let Σ n = {w ∈ Σ * : |w| = n} and Σ ≤n = {w ∈ Σ * : |w| ≤ n}. For any w ∈ Σ * , let pref(w) = {u ∈ Σ * : ∃v ∈ Σ * , uv = w} and suff(w) = {u ∈ Σ * : ∃v ∈ Σ * , vu = w}. A set of strings P is a prefix set if and only if ∀w ∈ P, pref(w) ⊆ P . For any S ⊆ Σ * , let front(S) = {ux ∈ Σ * : u ∈ S, x ∈ Σ, ux / ∈ S}. A series r defined over Σ is a mapping r : Σ * → R. A series r is convergent if the sequence r(Σ ≤n ) = w∈Σ ≤n r(w) is convergent : the limit is denoted by r(Σ * ). A series r is absolutely convergent if the series |r| defined by |r|(w) = |r(w)| is convergent. The set of all absolutely convergent series is denoted by l 1 (Σ * ). A stochastic language p is a probability distribution defined on Σ * , ie a series that only takes non negative values and that converges to 1.

A series r over Σ is rational if there exists an integer k ≥ 1, I, T ∈ R k and matrices

M x ∈ R k×k for every x ∈ Σ, such that for all u = x 1 x 2 . . . x m ∈ Σ * , r(u) = I T M u T = I T M x 1 M x 2 . . . M xm T.
The triplet I, (M x ) x∈Σ , T is called a k-dimensional linear representation of r. The rank of a rational series r is the minimal dimension of a linear representation of r. Linear representation are equivalent to weighted automata where each coordinate corresponds to a state, I provides the initial weights, T , the terminal weights and each matrix M x , the x-labeled transition weights. If r ∈ l 1 (Σ * ) is rational and admits the minimal linear representation I, (M x ) x∈Σ , T , then r(Σ * ) = I T (I d -M Σ ) -1 T where I d is the rank d identity matrix and M Σ = x∈Σ M x . A probabilistic automaton (PA) can be defined by a linear representation whose coefficients are all non negative and such that

T ⊤ I = 1, I d -M Σ is invertible and (I d -M Σ ) -1 T = 1 where 1 = (1, . . . , 1) ∈ R k . A k-dimensional linear representation I, (M x ) x∈Σ , T is prefix if I = (1, 0, . . . , 0) ⊤ ∈ R k and if there exists a prefix set P = {u 1 , u 2 , . . . , u k } such that ∀i ∈ [k], ∀x ∈ Σ, ∃j ∈ [k] s.t. u i x = u j ⇒ ∀k = j, M x [i, k] = 0.
For any series r ∈ l 1 (Σ * ) and any u ∈ Σ * , let ur be the series defined by ur(v) = r(uv) : it is called the residual of r wrt u. If I, (M x ) x∈Σ , T is a linear representation of r, then M T u I, (M x ) x∈Σ , T is a linear representation of ur. Let res(r) be the set of all residuals of r and V r be the subspace of l 1 (Σ * ) spanned by res(r). The set of all series s ∈ V r for which s(Σ * ) = 1 forms a hyperplane H r of V r . The projection of any residual ur s.t. r(uΣ * ) = 0 on H r is denoted by u -1 r and defined by ∀v ∈ Σ * , u -1 r(v) = r(uv) r(uΣ * ) .

q 0 1 q 1 a : 1/6 b : 1/3 a : 1/2 1/4 a : 1/4 b : 1/4 b : 1/4 I = 1 0 T = 0 1/4 M a = 1/2 1/6 0 1/4 M b = 0 1/3 1/4 1/4
Figure 1: A probabilistic automaton and the equivalent linear representation.

Hankel matrix and spectral algorithm

The Hankel matrix H r of a series r is a bi-infinite matrix whose rows and columns are indexed by Σ * and defined by ∀u,

v ∈ Σ * , H r [u, v] = r(uv).

    

A series r is rational iff the rank of its Hankel matrix H r is finite, and in this case both ranks coincide. Let r be a rank-k rational series and let H r = LDR ⊤ be a singular values decomposition of H r with L, R ∈ R ∞×k the right and left singular vectors of H r , respectively and D ∈ R k×k be the diagonal matrix containing its singular values. The spectral approach in probabilistic grammatical inference is based on the following result :

-let

I = R[1, :] be the first row of the matrix R -let M x = R T T x R where T x is the constant matrix defined by T x [u, v] = δ v=ux , -let T = R T H[1, :] T then I, (M x ) x∈Σ , T is a linear representation of r.
The most basic learning algorithm derived from this result consists in plugging-in the empirical Hankel matrix H S instead of the unknown matrix H r .

Let S be a training set of strings i.i.d. from an unknown distribution p. Let H S be the empirical Hankel matrix built from S defined by H S [u, v] = p S (uv) where p S is the empirical distribution associated with S. Let U = ∪ w∈S pref(w) and

V = ∪ w∈S suff(w) : H S is indexed by U and V . Let H S ≈ L k D k R ⊤ k , a rank-k truncated SVD of H S : L k (resp. R k ) is composed of the k-first left (
resp. right) singular vectors and D k is the diagonal matrix composed of the k first singular values of H S . The matrices I, (M x ) x∈Σ and T are then computed as above, using R k instead of R and using H S [1, :] instead of H r [1, :]. Note that the choice of k is an important parameter of the spectral algorithm [START_REF] Kulesza | Low-rank spectral learning[END_REF] but it will not be discussed in this paper. Several variants of this basic algorithm have been studied (Balle et al., 2012[START_REF] Balle | Methods of moments for learning stochastic languages : Unified presentation and empirical comparison[END_REF][START_REF] Denis | Dimension-free concentration bounds on hankel matrices for spectral learning[END_REF].

PAutomaC

The Probabilistic Automata learning Competition (PAutomaC1 ), proposed in sidelines of the ICGI 2012 conference, is about the problem of learning probabilistic distributions from strings drawn from finite state automata.

The competition offers to solve a set of 48 problems provided in the forme of target models. These models can be of the four following types : Markov Chains, Determinist Probabilistic Finite Automata, Hidden Markov Models and Probabilistic Finite Automata. The participants have acces to training sets of strings i.i.d. from the target models and to test sets. The evaluation process involves making good approximations of the probabilities of the strings from the test set. The quality of the approximation is evaluated by the perplexity criterion defined as follows :

2 -( w∈T estSet p(w) * log(p(w)))
where p is the target series and p is the candidate series that is evaluated. Because models learned using spectral methods can return negative values, a trigram trained on S will be used for strings for which p outputs a negative value. In this paper, we focus on the 10 problems for which the rank of the target is the smallest, in order to use classical SVD decomposition software and the software from [START_REF] Markovsky | Low Rank Approximation : Algorithms, Implementation, Applications[END_REF] to compute low-rank approximation on small matrices as explained in Section 4. More details about PAutomaC can be found in [START_REF] Verwer | Results of the pautomac probabilistic automaton learning competition[END_REF].

Using spectral learning as Baum-Welch algorithm initialization

A classical and consistent way to solve our inference problem consists in finding a lowrank linear representation that maximizes the likelihood of the learning set. However, it is well known that this problem is NP-hard and approximation algorithms should be used in practical cases. The Baum-Welch algorithm (BW), a straightforward adaptation of the expectation-maximization (EM) algorithm for the framework of PAs, iteratively modifies the parameters of an initial model in order to increase the likelihood of the observation data. The Baum-Welch algorithm converges to a local optimum. A common strategy consists in running BW on a large number of randomly generated initial models and keeping the model which maximizes the likelihood of the learning set. However, the underlying space is strongly non-convex and this strategy is not efficient in high dimension.

On the other hand, spectral learning algorithms are designed to provide low-rank linear representations which are proved to be close to the target. But, as the underlying optimization criterion is of an algebraic nature, spectral learning algorithms are not tailored to maximize the likelihood of the observation data. A sound strategy should be to take the model r output by a spectral learning algorithm as an initialization model for the Baum-Welch algorithm. However, the representation of r has some characteristics that make the Baum-Welch algorithm impossible to be applied on : (i) it may include negative coefficients ; (ii) it may be not normalized, i.e. its components may be far from satisfying the syntactical properties of a PA : i I[i] = 1 and T [i] + j,x M x [i, j] = 1 for any index j.

We show below that given a minimal linear representation of a rational stochastic language p, we can build an equivalent prefix linear representation which is normalized. Moreover, we show that we can build equivalent normalized prefix linear representation where the magnitude of the negative coefficients is arbitrarily small. These techniques will allow us to compute normalized prefix linear representation arbitrarily close from r and on which, the Baum-Welch algorithm could be applied.

Normalized prefix linear representation and negative coefficients reduction

Let A =< I, (M x ) x∈Σ , T > be a rank-k minimum linear representation that computes the stochastic language p and let P = {u 1 , . . . , u k } ⊂ Σ * be a prefix set where i ≤ j ⇒ u i ≺ u j and such that { up :

u ∈ P } is a basis of V p . Then, let A ′ =< I ′ , (M ′
x ) x∈Σ , T ′ > be the linear representation defined by

1. I ′ = (1, 0, . . . , 0) ⊤ ∈ R k , 2. ∀i ∈ [k], T ′ [i] = p(u i ) p(u i Σ * ) , 3. ∀i, j ∈ [k], ∀x ∈ Σ, (a) u i x = u j ⇒ M ′ x [i, j] = p(u i xΣ * ) p(u i Σ * ) , (b) u i x ∈ f ront(P ) ⇒ M ′ x [i, j] = α j i,x p(u j Σ * ) p(u i Σ * )
, where u i xp = k j=1 α j i,x uj p Then, A ′ is a normalized prefix linear representation equivalent to A. See an example in Figure 2. Note that the conditions on P implies that u 1 = ǫ, that p(u i Σ * ) = 0 for any i ∈ [k] and that the coefficients α j i,x are uniquely determined. If we relax the conditions in such a way that the set { up : u ∈ P } spans V p but may be not linearly independent, then the equations u i xp = k j=1 α j i,x uj p may not determine the coefficients α j i,x . Additional constraints can be added in order to minimize the magnitude of negative coefficients. From now on, we will replace the conditions u

i xp = k j=1 α j i,x uj p with u i xp = k j=1 α j i,x uj p and k j=1 |α j i,x |p(u j Σ * ) minimal which is equivalent to demand that M ′ [i,j]<0 |M ′ [i, j]| be minimal since k j=1 α j i,x p(u j Σ * ) = p(u i xΣ * ) is a constant.
Not all rational stochastic languages can be computed by a PA [START_REF] Dharmadhikari | Sufficient conditions for a stationary process to be a function of a finite markov chain[END_REF][START_REF] Denis | On rational stochastic languages[END_REF]) (see Fig. 3).

q 0 λ q 1 q 2 λ √ 2 -ρ sin α ρ cos α 1 ρ sin α ρ cos α 1 ρ 1
Figure 3: For any α ∈ R and 0 < ρ < 1, there exists λ > 0 such that the automaton defines a stochastic language, which can be computed by a PA iff α/π ∈ Q.

However, it has been shown in [START_REF] Bailly | Absolute convergence of rational series is semi-decidable[END_REF]) that any rational stochastic language admits a normalized prefix linear representation where the total magnitude of the negative coefficients is arbitrarily small. See an example on Fig. 4.

t i = 1 -x,j M x [i, j].

Baum-Welch initialization

The spectral algorithm outputs linear representations that converge to the target distribution in ℓ 1 norm [START_REF] Bailly | Méthodes spectrales pour l'inférence grammaticale probabiliste de langages stochastiques rationnels[END_REF][START_REF] Hsu | A spectral algorithm for learning hidden markov models[END_REF] : so, it can be assumed that if the learning set is big enough, the output series r is absolutely convergent. But r is not a stochastic language : we can not assume that r(Σ * ) = 1 neither that ∀u ∈ Σ * , r(u) ≥ 0. We want to show that our approach -choosing r as the initial model for BW -improves the result of the spectral learning algorithm when the output representation is sufficiently close to the target.

Experiments on PAutomaC benchmark show that for most problems, the representation output by the spectral algorithm is such that r(Σ * ) is close to 1 and u∈S:r(u)<0 r(u) is small (cf. Figure 1). Thereby, given the rank-k series r output by the spectral learning algorithm, -We consider the series r ′ = r r(Σ * ) . -We choose an initial prefix set P of size k which maximizes the volume |Det({ ur :

u ∈ P })| and such that ∀u ∈ P , r ′ (uΣ * ) > 0. -We compute the normalized prefix linear representation A 0 = I (0) , (M (0 x ) x∈Σ , T (0) of r ′ , according to P . We then define a sequence of linear representations A m by : -Let m = 0.

-While there exists i, j ∈ [k] and x ∈ Σ such that M (m)

x [i, j] < 0 -let i ∈ [k] and x ∈ Σ such that j;M (m) x [i,j]<0 |M (m)
x [i, j]| is maximal ; let u ∈ P be the string corresponding to i ; P = P ∪ {ux} ; -let m = m + 1 and let A m be the normalized prefix linear representation of r ′ associated with P . Every linear representation A m is equivalent to r ′ and the global magnitude of the negative coefficients tends to 0 as m increases. A PA B m is computed from each A m by applying the following normalization procedure :

M x [i, j] = |M x [i, j]| k |M x [i, k]| + |T [i]|
and

T [i] = |T [i]| k |M x [i, k]| + |T [i]| .
If the global magnitude of the negative coefficients of A m is small and if r is close to the target, the series computed by the PA B m should be also close to the target. It can serve as an initial point for the Baum-Welch algorithm.

Experimentation on PAutomaC problems

In this section, we apply the method described in section 3.2 on 10 problems extracted from the PAutomaC challenge. Some descriptive elements can be found in Table 1. Each problem proposes a training set S (of 2 × 10 4 or 1 × 10 5 strings) drawn according to a target model p and a test set (of 1 × 10 3 strings) on which the perplexity of a candidate series will be evaluated.

Let H S be the empirical Hankel matrix of S indexed by the sets U and V with |U | ≤ 3000 (we constrain |U | in order to allow the use of standard SVD using NumPy and SciPy implementations). Let Â(k) be the rank-k representation learned from H S by using the spectral algorithm. A random sub-sampling validation -taking 25% of S as validation set -is performed to determine the best rank in term of likelihood : i.e.

k * = argmax k L( Â(k) ),
where L( Â(k) ) denotes the likelihood of the model Â(k) computed on the validation set. Let p be the series computed by Â(k * ) . Results are detailed in Table 1.

Then, we computed a sequence of m linear representations B (r) m for any given rank r and any m ∈ [0, 10] that can be used as starting point for the Baum-Welch algorithm. We denote

C (k)
m the linear representations obtained by applying the Baum-Welch algorithm on B

(k) m . Let (k * , m * ) = argmax k,m L( Ĉ(k) m ),
P AutomaC ranking C (k * ) m * Last 2 nd 4 th Last 3 rd Last Last Last 2 nd 2 nd
Table 2: Results given by the method described in Section 3.2 applied on the same PAu-tomaC problems.

For 6 problems out of the 10 studied, the method significantly improves the quality of the solution allowing 3 of them to be on the PAutomaC podium. Also, note that 3 of the problems that could not be improved were originally the ones giving the most negative values on the test set and that 2 of them where the ones with the highest remaining negative values in the prefix representation before applying on it a normalization procedure. This tends to confirm that the method proposed in this section is able to give good results when the quality of the initial model is close enough to the target solution.

Grammatical inference and Structured Low-Rank Approximation

In the previous section, we showed that when the spectral method is able to output a model close to the target, we can improve it by applying a likelihood maximization procedure. Having a good approximation of the target is then crucial and in this section we propose to consider Structured Low-Rank Approximation (SLRA) [START_REF] Markovsky | Structured low-rank approximation and its applications[END_REF][START_REF] Markovsky | Low Rank Approximation : Algorithms, Implementation, Applications[END_REF] methods for improving the output given by the spectral algorithm. Indeed, the core step of the spectral algorithm is based on a low-rank approximation of the empirical matrix H S given by a rank-k truncated singular values decomposition :

L k D k R T k = H Sk .
Note that H Sk is the best rank-k approximation of H S in term of Frobenius norm [START_REF] Stewart | On the early history of the singular value decomposition[END_REF]. However, H Sk is no longer a Hankel structured matrix. As a consequence, the reconstruction step of the spectral algorithm -building from H Sk the rank-k linear representation I, (M x ) x∈Σ , T defining the series p -can be seen as another matrix approximation between the unstructured H Sk and the expected Hankel structured H p. See Figure 5 for an illustration.

H S rank(Hs) >> k ❉ Hankel structured ❯ L k D k R T k = H Sk rank(H sk ) = k ❯ No structure ❉ < I, (M x ) x∈Σ , T > ⇔ H p rank(H p) = k ❯ Hankel structured ❯ approx.
approx.

truncated SVD reconstruction

Figure 5: Diagram summarizing the different approximation steps made by the spectral algorithm : The first one is done for obtaining the target rank without the correct matrix structure and the second one can be seen as a recovery the Hankel structure property.

SLRA corresponds to the problem of finding a low rank structure-preserving approximation of a given data matrix. In particular, the SLRA framework supports Hankel structured matrices. Let H slra be a low-rank approximation of H S obtained by SLRA. Since both rank and structure are correct, we can directly apply the procedure presented in Section 2.2 on H slra to build a rank-k linear representation computing the series p without an additional approximation, i.e. for any sets U and V indexing H S we have ∀u ∈ U and ∀v ∈ V , H slra [u, v] = p(uv).

In the next subsection, we introduce the SLRA framework in the context of our grammatical inference problem and evaluate its relevance on a small example. Basically, the SLRA framework can provide, in theory, a nice solution to the problem addressed by spectral methods. However, this framework is strongly non-convex and thus cannot be applied directly on large real problems. To deal with this drawback, we discuss, in a second step, some strategies to deal with big matrices and show some preliminary results on the PAutomaC challenge.

From grammatical inference to SLRA

Let S be a sample of strings i.i.d. from an unknown distribution p of rank k and H S ∈ R m×n be the empirical Hankel matrix built from S and indexed by a pair (U, V ) ⊆ Σ * × Σ * . Let p S = [p S (w 1 ), . . . , p S (w np )] ∈ R np be the vector that contains the empirical probabilities of each string w i of S without duplicates. The Hankel structure of H S can be modeled from p S by an affine structure defined by a mapping S : R np → R m×n such that :

H s = S (p S ) = np i=1 S i p S (w i ),
where matrices S i ∈ R m×n , indexed by the same pair (U ,V ), encode the Hankel structure such that ∀u ∈ U and ∀v ∈ V , S i [u, v] = 1 if w i = uv 0 otherwise. For example, considering the 3 strings sample S = {ǫ, ǫ, a} and taking U = V = {ǫ, a}, we have

H S = 1 0 0 0 × p S (ǫ) + 0 1 1 0 × p S (a) = 2/3 1/3 1/3 0 .
The SLRA outputs a Hankel structured matrix S (p S ) that is a rank-k approximation of H S by means of the following minimization problem :

minimize pS ∈R np ||p S -p S || subject to rank(S (p S )) ≤ r. (1)
The rank constraint rank(S (p S )) ≤ r is actually equivalent to find a matrix R ∈ R d×m , where d = m -r, such that rank(R) = d and RS (p S ) = 0 [START_REF] Usevich | Variable projection for affinely structured low-rank approximation in weighted 2-norms[END_REF]. Then, Problem (1) can be reformulated as a double minimization problem as follows :

minimize R:rank(R)=d f (R), where (2)
f (R) := min||p S -p S || 2 2 subject to RS (p S ) = 0 (3)
The inner minimization problem ( 3) is a least-norm problem and has a closed form solution. On the other hand, the outer problem (2) is by nature non convex making thus the SLRA formulation intractable on large problems. As shown below, the SLRA formulation applied on small problems is very appropriate for the probabilistic grammatical inference problem we consider. However, if some progress has been done recently [START_REF] Markovsky | Software for weighted structured low-rank approximation[END_REF], this non-convexity issue makes impossible to apply the SLRA approach on full empirical Hankel matrices. We provide at the end of the section a first attempt to deal with this drawback accompanied with an evaluation on PAutomaC.

Evaluation on a small problem

To evaluate the SLRA approach, we consider the rank-k linear representation of Figure 1, denoted by A, computing the series p and let S be a set of strings i.i.d. from p. In order to stand in a realizable case for SLRA, we consider a small sub-matrix H ′ S of H S following the approach from (Balle et al., 2012) to learn a model. The rank of the target model is k = 2 so for this example, this approach only needs the informations from a sub-matrix H ′ S ∈ R 5×5 to be applied. Let d quad denote the quadratic distance between two series, define by d quad (p 1 , p 2 ) = w∈Σ * (p 1 (w) -p 2 (w)) 2 1 2 . In order to evaluate the two methods, we used the following experimental setup. First, we consider different sizes of training set i.i.d. from p (from 500 to 50000 strings). For each sample, we fill the matrix H ′ S and apply the SLRA optimization problem to obtain a rank-2 approximation H ′ slra , from which we build a linear representation of the series pslra . We compare this approach to the method consisting in applying the spectral method on H ′ S giving the series pS . We repeat each experiment 100 times and we compare the quality of the different methods according to the following 2 measures :

-

d 1 (H ′ S , H ′ slra ) = ||H p -H ′ S || 2 -||H p -H ′ slra || 2 , -d 2 (p S , pslra ) = d quad (p S , p) -d quad (p slra , p).
The first one evaluates the quality of the low rank approximation with respect to the target matrix H p and the second one the quality of the inferred model in terms of quadratic distance to the target. A positive value indicates that the SLRA approach is better than the spectral one. The results are reported on Figure 6.

The two evaluation measures confirm that the solution found by the SLRA method is significantly better than the spectral approach. Moreover, using a one-tail Student t-test, the results are statistically significant with a p-value always lower than 10 -6 . This illustrates that SLRA is clearly able to provide good approximations to a target model when the problem is feasible. In the next section, we present a solution for larger problems.

Using SLRA on large problems

Due to its non-convexity, the SLRA formulation cannot be applied to real problems : If the matrix is big the problem is intractable and on the other hand if the matrix is too small we may face to a dramatic loss of information and even to an incapacity to obtain a sufficient rank, implying poor results. Another strategy is to use SLRA as a preprocess to improve the quality of the information in the empirical Hankel matrix before applying the spectral algorithm. The simple idea proposed here is to apply SLRA on a submatrix of the empirical Hankel matrix and to apply the spectral method on the Hankel matrix updated with the values returned by SLRA. Given a empirical matrix H S and a target rank, we propose the following procedure :

-Extract a small squared sub-matrix H ′ S from H S in order to maximize the quantity of information in H ′ S such that the rank of H ′ S is greater than the target rank and that the size is compatible with the computing resources in order to apply the SLRA problem.

-Apply the SLRA formulation on H ′ S with the desired rank to obtain H ′ slra . -Replace in the whole matrix H S each occurrence of the variables in H ′ S by their new values in H ′ slra to obtain a matrix H ′′ S . -Apply the spectral algorithm on H ′′ S . We have evaluated this strategy on 10 problems of the PAutomaC challenge and compared it to the classical spectral learning algorithm.

We used the following measures to assess the quality of the results : (i) the distance of the Hankel matrices from the target matrix

′ S -H ′ p || F 3.70e -3 5.98e -3 4.60e -3 1.54e -3 8.68e -3 3.77e -3 5.29e -3 2.43e -3 5.19e -3 4.47e -3 ||H ′ slra -H ′ p || F 3.30e -3 5.98e -3
4.60e -3 1.47e -3 8.24e -3 3.76e -3 5.25e -3 2.19e -3 5.16e -3 4.32e -3 d quad (p S , p) 2.24e -3 5.27e -3 4.07e -3 1.65e -3 5.05e -3 4.36e -3 4.17e -3 2.33e -3 3.98e -3 3.96e -3 d quad (p slra , p) 2.08e -3 5.28e -3 4.07e -3 1.62e -3 4.77e -3 4.36e -3 4.16e -3 2.06e -3 3.97e -3 3.92e quadratic distance of the learn series with the target series p ; (iii) the perplexity of the learn models over the test set. The results are reported on Table 3. First, we observe that, in terms of Frobenius norm, the SLRA-based approach is able to improve the quality of the information contained in the matrix H ′ S for 9 problems out of 10. Moreover, for 7 problems, models inferred from H ′′ S are better in term of quadratic distance than models inferred from H ′ S which means that we were able to move closer to the target and a gain in terms of perplexity is observed for 5 problems. This shows that SLRA can bring some valuable information to the empirical matrix which leads to produce better models. As a conclusion, these preliminary results show that SLRA can be a very relevant tool for learning low-rank linear representations.

Conclusion

In this paper, we have studied two possible directions for improving the solution output by spectral methods for learning linear representation of stochastic languages.

First, we provided an approach allowing one to maximize the likelihood of a sample from a model given by the spectral methods. This strategy is based on a renormalization of the model accompanied with an iterative procedure allowing one to reduce the magnitude of negative coefficients thanks to an extension of the model. Once the negative coefficients are eliminated, we obtain a starting point for the BW algorithm used afterwards to update the coefficients of the model in order to maximize the likelihood of the learning sample. Our experiments show that this approach can improve the spectral algorithm if the model output by this algorithm is sufficiently close to the target solution.

In a second step, we studied the Structured Low Rank Approximation methods in the context of our learning problem. This approach allows one to obtain a low-rank representation of a matrix while preserving its (Hankel) structure which corresponds exactly to the problem spectral methods aims at solving. We have illustrated the interest of this approach on a synthetic problem and its limitations on big Hankel matrices -coming with real applications-due to the non-convexity of its nature. We have proposed a preliminary approach consisting of applying the SLRA framework on a small feasible subpart of the full Hankel matrix. This strategy tends to improve the final output of the method but is not completely convincing since the SLRA is only modifying a relatively small amount of data of the Hankel matrix H S . As a consequence, the model obtained is still relatively close to the spectral solution and in our preliminary experiments, combining SLRA with the Baum-Welch procedure does not bring a significative gain.

A natural perspective of this work is to find new approaches for applying SLRA on a larger amount of data of the empirical matrix. For example, trying to use many SLRA on random sub-matrices or projections with a relevant combination of the results is a natural perspective.

  ) r(a) r(b) r(aa) . . . r(a) r(aa) r(ab) r(aaa) . . . r(b) r(ba) r(bb) r(baa) . . .

Figure 2 :

 2 Figure 2: Normalized prefix representation of automaton from Figure 1 for P = {ǫ, a}.

Figure 4 :

 4 Figure 4: Given the automaton described in Fig. 3, with ρ = 0.5, α = arccos 0.6 and λ = 0.3040.., it defines a stochastic language. Let A n be the n-dimensional normalized prefix linear representation which minimizes the magnitude of the sum D n of the negative weights. We have D 3 = -1.793, D 4 = -0.358, D 5 = -0.082 and D 6 = -0.024. The figure shows A 6 and ∀i ∈ [n], t i = 1x,j M x [i, j].

Figure 6 :

 6 Figure 6: Comparison of the performances of the SLRA approach and the spectral one on the toy problem of Figure 1 according to different learning sample sizes. The results evaluated by the gain in terms of distance d 1 (2-norm) are presented on the left and those in terms of distance d 3 (quadratic distance to the target) are given on the right.

Table 1 :

 1 Results given by the spectral algorithm applied on 10 PAutomaC problems.

				where L(	Ĉ(k)
	Problem number		4	7	12	20	24	30	31	33	39	42
	|Σ|		4	13	13	18	5	10	5	15	14	9
	Target series rank		10	12	12	8	5	9	12	6	6	6
	perplexity target		80.818	51.224	21.655	90.972	38.729	22.926	41.214	31.865	10.002	16.004
	k *		11	12	13	9	5	10	13	7	7	7
	perplexity Â(k * )		80.868	51.308	21.772	95.770	38.763	23.041	41.527	32.399	10.042	16.028
	neg. values on test set	0.5 %	0.0 %	1.1 %	9.0%	0.0 %	3.8%	3.0%	1.1 %	1.0 %	0.7 %
	w∈Σ * p(w) P AutomaC ranking Â(k * )	1.007 Last	1.005 Last	0.889 Last	1.075 Last	0.969 Last	0.897 Last	0.978 Last	1.453 Last	0.831 Last	0.970 Last
	Problem number		4	7	12	20	24	30	31	33	39	42
	(k * , m * )		11, 2	12, 1	13, 3	9, 7	5, 7	9, 5	12, 3	4, 7	7, 1	7, 0
	perplexity L(C sum of neg. weights in B (k * ) m * )	(k * ) m *	81.408 51.251 21.700 184.459 38.736 23.459 0.821 0.012 1.850 4.728 0.007 2.566	42.710 32.050 10.003 16.006 6.276 0.379 3.500 0.394

m ) is computed on a validation set. Results are detailed in Table

2

.

Table 3 :

 3 Evaluation of SLRA used as a preprocess of the spectral method. The first line indicates the PAutomaC problems considered and the second the selected size of the sub-matrix on which the SLRA is applied. The following two lines shows the modifications made by SLRA on the Hankel matrices in term of || • || F . The next four lines show the modifications made by SLRA on the learned models in terms of d quad and perplexity. If SLRA has made an improvement over the classical method, the result is shown in bold.

c 2014 M. Gybels, F. Denis & A. Habrard.

http://ai.cs.umbc.edu/icgi2012/challenge/Pautomac/