Marisa Fernández

Manuel De León

Martín Saralegui

A six dimensional compact symplectic solvmanifold without Kähler structures *

Partially supported by DGICYT-Spain, Proyectos PB89-0571 and PB91-0142 1 complex structures. By using these manifolds it is possible to construct new examples of higher dimension, but we do not know whether any of these examples admit complex or Kähler structures. The problem is that the above results depend strongly on Kodaira's classification of surfaces.

. But it is amazing that the manifolds M 6 (k) have complex structures.

(3) In [6] Benson and Gordon have constructed two examples of non-nilpotent solvable Lie groups of dimension 8, each one of those satisfies one of the conditions (iv) or (v), but not the another.

 to show that non-abelian compact nilmanifolds are non formal fails for the solvable case.

 proved that every compact even dimensional Lie group possesses a left invariant complex structure. But the same is not true for non-compact Lie groups. In fact, since the manifold M 4 (k) does not admit complex structures then the corresponding Lie group G 4 (k) does not admit left invariant complex structures (see Cordero, Fernández and Gray [8]). In the same paper they have constructed a 6-dimensional nilpotent Lie group with no left invariant complex structure. Since we do not know whether the manifold M 6 admits complex structures or not, we can not use this method to decide whether G admits a left invariant complex structure. But from direct computations we prove, in the last section, that G has no left invariant complex structures.

The authors wish express their thanks to the referee for many valuable suggestions. In particular, to point us the observation of which are the compact Kähler solvmanifolds of (complex) dimension 2, as well as, the conjecture of which are the compact solvmanifolds of (real) dimension 2n with a Kähler structure.

Introduction

There are strong topological conditions for a compact manifold M of dimension 2n to admit a Kähler structure [START_REF] Weil | Introduction a l' étude des variétés kähleriennes[END_REF][START_REF] Deligne | Real homotopy theory of Kähler manifolds[END_REF]:

(i) the Betti numbers b 2i (M ) are non-zero for 1 ≤ i ≤ n;

(ii) the Betti numbers b 2i-1 (M ) are even;

(iii) b i (M ) ≥ b i-2 (M ) for 1 ≤ i ≤ n;

(iv) the Hard Lefschetz Theorem holds for M ; (v) the minimal model of M is formal (so in particular all Massey products of M vanish).

Gordon and Benson have proved that if a compact nilmanifold admits a Kähler structure then it is a torus [START_REF] Ch | Kähler and symplectic structures on nilmanifolds[END_REF]; more precisely they proved that the condition (iv) fails for any symplectic structure on a non-toral nilmanifold M . This result was independently proved by Hasegawa [START_REF] Hasegawa | Minimal models of nilmanifolds[END_REF] by showing that (v) fails for M .

For a compact solvmanifold M of dimension 4 it is known that M has a Kähler structure if and only if it is a complex torus or a hyperelliptic surface. In fact, Auslander and Szczarba in [START_REF] Auslander | Vector bundles over tori and noncompact solvmanifolds[END_REF] proved that if the first Betti number b 1 (M ) of M is 2, M is a fiber bundle over T 2 with fiber T 2 . Then by Ue [START_REF] Ue | Geometric 4-manifolds in the sense of Thurston and Seifert 4-manifolds I[END_REF] M has a complex structure only if it is a hyperelliptic surface or a primary Kodaira surface which is a compact nilmanifold. Thus, if M is a Kähler manifold, it must be a hyperelliptic surface. Since 1 ≤ b 1 (M ) ≤ 4, M can be a Kähler manifold only if it is a complex torus or a hyperelliptic surface. The fact that a hyperelliptic surface is a solvmanifold follows from Auslander [START_REF] Auslander | Some compact solvmanifolds and locally affine spaces[END_REF]. The above result may be generalized as the following conjecture: A compact solvmanifold has a Kähler structure if and only if it is a finite quotient of a complex torus.

In contrast to the case of compact nilmanifolds there are compact symplectic solvmanifolds which are not nilmanifolds that satisfy both conditions (iv) and (v) [START_REF] Ch | Kähler structures on solvmanifolds for completely solvable Lie groups[END_REF][START_REF] Fernández | Compact symplectic four dimensional solvmanifolds not admitting complex structures[END_REF][START_REF] Cordero | Compact symplectic four solvmanifolds without polarizations[END_REF][START_REF] De Andrés | Some six dimensional compact symplectic and complex solvmanifolds[END_REF]. More precisely:

(1) There is a family of 4-dimensional compact solvmanifolds M 4 (k) satisfying (i)-(v) which do not admit Kähler structures [START_REF] Fernández | Compact symplectic four dimensional solvmanifolds not admitting complex structures[END_REF][START_REF] Cordero | Compact symplectic four solvmanifolds without polarizations[END_REF]. In fact, M 4 (k) does not admit [START_REF] De Andrés | Some six dimensional compact symplectic and complex solvmanifolds[END_REF] The Lie group G Let G be the connected and solvable Lie group of dimension 6 consisting of matrices of the form

A =           e t 0 xe t 0 0 y 1 0 e -t 0 xe -t 0 y 2 0 0 e t 0 0 z 1 0 0 0 e -t 0 z 2 0 0 0 0 1 t 0 0 0 0 0 1           where t, x, y i , z i ∈ R, 1 ≤ i ≤ 2 .
Then, a global system of coordinates {t, x, y 1 , y 2 , z 1 , z 2 } for G is given by

t(A) = t , x(A) = x , y i (A) = y i , z i (A) = z i , 1 ≤ i ≤ 2 ;
and a standard computation shows that a basis for the left invariant 1-forms on G consists of

α = dt , β = dx , γ 1 = e -t dy 1 -xe -t dz 1 , γ 2 = e t dy 2 -xe t dz 1 , δ 1 = e -t dz 1 , δ 2 = e t dz 2 .
Then we have

dα = dβ = 0 , dγ 1 = -α ∧ γ 1 -β ∧ δ 1 , dγ 2 = α ∧ γ 2 -β ∧ δ 2 , dδ 1 = -α ∧ δ 1 , dδ 2 = α ∧ δ 2 . (2.1)
We denote by {T, X, Y 1 , Y 2 , Z 1 , Z 2 } the dual basis of left invariant vector fields. From (2.1) we obtain

[T, Y 1 ] = Y 1 , [T, Y 2 ] = -Y 2 , [T, Z 1 ] = Z 1 , [T, Z 2 ] = -Z 2 , [X, Z 1 ] = Y 1 , [X, Z 2 ] = Y 2 . (2.2)
and the other brackets being zero.

Let G be the Lie algebra of G. From (2.2) we compute the derived series of G:

D 0 G = G, D 1 G = [G, G] = Y 1 , Y 2 , Z 1 , Z 2 , D r G = 0, 2 ≤ r.
and the descending central series of G:

C 0 G = G, C 1 G = [G, G] = Y 1 , Y 2 , Z 1 , Z 2 , C r G = [G, C 1 G] = C 1 G, 2 ≤ r.
Then G is a non-nilpotent solvable Lie group. One says that a Lie group G with Lie algebra G is completely solvable if ad(X) : G -→ G has only real eigenvalues for each X ∈ G. Equivalently, G is isomorphic to a Lie subalgebra of the real upper triangular matrices in gl(n, R) for some n. A simple inspection shows that G is completely solvable.

Alternatively, G may be described as a semi-direct product G = R 2 ∝ φ R 4 , where φ(t, x) is the linear transformation of R 4 given by the matrix

     e t 0 xe t 0 0 e -t 0 xe -t 0 0 e t 0 0 0 0 e -t     
We notice that

     e t 0 xe t 0 0 e -t 0 xe -t 0 0 e t 0 0 0 0 e -t      =      e t 0 0 0 0 e -t 0 0 0 0 e t 0 0 0 0 e -t           1 0 x 0 0 1 0 x 0 0 1 0 0 0 0 1     
Thus the operation group in G is given by

(t, x, y 1 , y 2 , z 1 , z 2 )(t , x , y 1 , y 2 , z 1 , z 2 ) = (t + t , x + x , y 1 e t + xz 1 e t + y 1 , y 2 e -t + xz 2 e -t + y 2 , z 1 e t + z 1 , z 2 e -t + z 2 ) Then G = R 2 ∝ φ R 4
, where R 2 is a connected abelian subgroup and R 4 is the nilpotent commutator subgroup.

Remark 1 Let H be the connected Lie group of dimension 7 consisting of matrices of the form

A =           e t 0 x 1 e t 0 0 y 1 0 e -t 0 x 2 e -t 0 y 2 0 0 e t 0 0 z 1 0 0 0 e -t 0 z 2 0 0 0 0 1 t 0 0 0 0 0 1          
where t, x i , y i , z i ∈ R, 1 ≤ i ≤ 2. We notice that G is a closed subgroup of H. In fact, G is the Lie subgroup of the matrices A ∈ H such that x 1 = x 2 . As above H may be described as a semi-direct product

H = R 3 ∝ φ R 4
, where φ(t, x 1 , x 2 ) is the linear transformation of R 4 given by the matrix

     e t 0 x 1 e t 0 0 e -t 0 x 2 e -t 0 0 e t 0 0 0 0 e -t     
A direct computation shows that a basis for the left invariant 1-forms on H consists of

α = dt , β 1 = dx 1 , β 2 = dx 2 , γ 1 = e -t dy 1 -x 1 e -t dz 1 , γ 2 = e t dy 2 -x 2 e t dz 1 , δ 1 = e -t dz 1 , δ 2 = e t dz 2 .
Then we have

dα = 0 , dβ 1 = -α ∧ β 1 , dβ 2 = -α ∧ β 2 , dγ 1 = -α ∧ γ 1 -β ∧ δ 1 , dγ 2 = α ∧ γ 2 -β ∧ δ 2 , dδ 1 = -α ∧ δ 1 , dδ 2 = α ∧ δ 2 .
If we put G 2 = H × S 1 , then G 2 is the Lie group considered by Benson and Gordon [START_REF] Ch | Kähler structures on solvmanifolds for completely solvable Lie groups[END_REF].

3 The solvmanifold M 6 We shall construct a cocompact discrete subgroup Γ of G.

Let B ∈ SL(2, Z) be a unimodular matrix with integer entries and with distinct real eigenvalues, say λ and λ -1 . Take a 0 = log λ, i. e. e a 0 = λ. Then there exists a matrix P ∈ Gl(2, R) such that

P BP -1 = λ 0 0 λ -1
Consider the subgroup Γ 0 = (a 0 Z) × Z of R 2 . We can easily check that the lattice

L on R 4 defined by L = ((m 1 , m 2 )P t , (n 1 , n 2 )P t ),
where m 1 , m 2 , n 1 , n 2 ∈ Z and P t is the transpose of P , is invariant under the subgroup Γ 0 . Thus, Γ = Γ 0 ∝ φ L is a cocompact subgroup of G.

We denote by M 6 = G/Γ the compact quotient manifold. Then M 6 is a six dimensional non-nilpotent completely solvable manifold.

Remark 2 Alternatively, the manifold M 6 may be viewed as the total space of a T 4bundle over T 2 . In fact, let T 4 = R 4 /L be the 4-dimensional torus and ρ : Z 2 -→ Diff (T 4 ) the representation defined as follows: ρ(p, q) represents the transformation of T 4 covered by the linear transformation of R 4 given by the matrix

     e pa 0 0 qe pa 0 0 0 e -pa 0 0 qe -pa 0 0 0 e pa 0 0 0 0 0 e -pa 0     

This representation determines an action

A : Z 2 × (T 4 × R 2 ) -→ T 4 × R 2 defined by A((p, q), [y 1 , y 2 , z 1 , z 2 ], (r 1 , r 2 )) = (ρ(p, q)([y 1 , y 2 , z 1 , z 2 ]), (r 1 + p, r 2 + q)) .
Then π :

T 4 × Z 2 R 2 -→ T 2 is a T 4 -bundle where the projection π is given by π[[y 1 , y 2 , z 1 , z 2 ], (r 1 , r 2 )] = [(r 1 , r 2 )] .
In fact, this bundle is the suspension of the representation ρ (see [START_REF] Hector | Introduction to the Geometry of Foliations, Part A, Aspects of Math[END_REF]). Then it is clear that T 4 × Z 2 R 2 may be canonically identified with M 6 .

Next, we shall compute the real cohomology of M 6 . Since M 6 is completely solvable we can use a theorem of Hattori [START_REF] Hattori | Spectral sequence in the de Rham cohomology of fibre bundles[END_REF] which asserts that the de Rham cohomology ring H * (M 6 , R) is isomorphic with the cohomology ring H * (G) of the Lie algebra G of G. For simplicity we denote the left invariant forms {α, β, γ 1 , γ 2 , δ 1 , δ 2 } and their projections onto M 6 by the same symbols. Thus, we obtain:

H 0 (M 6 , R) = {1} , H 1 (M 6 , R) = {[α], [β]} , H 2 (M 6 , R) = {[α ∧ β], [δ 1 ∧ δ 2 ], [γ 1 ∧ δ 2 + γ 2 ∧ δ 1 ]} , H 3 (M 6 , R) = {[α ∧ δ 1 ∧ δ 2 ], [β ∧ γ 1 ∧ γ 2 ], [β ∧ γ 1 ∧ δ 2 ], [α ∧ γ 1 ∧ δ 2 + α ∧ γ 2 ∧ δ 1 ]} , H 4 (M 6 , R) = {[α ∧ β ∧ γ 1 ∧ γ 2 ], [α ∧ β ∧ γ 1 ∧ δ 2 ], [γ 1 ∧ γ 2 ∧ δ 1 ∧ δ 2 ]} , H 5 (M 6 , R) = {[α ∧ γ 1 ∧ γ 2 ∧ δ 1 ∧ δ 2 ], [β ∧ γ 1 ∧ γ 2 ∧ δ 1 ∧ δ 2 ]} , H 6 (M 6 , R) = {[α ∧ β ∧ γ 1 ∧ γ 2 ∧ δ 1 ∧ δ 2 ]} . Thus, b 0 (M 6 ) = b 6 (M 6 ) = 1 , b 1 (M 6 ) = b 5 (M 6 ) = 2 , b 2 (M 6 ) = b 4 (M 6 ) = 3 , b 3 (M 6 ) = 4 .
Hence M 6 satisfies conditions (i)-(iii). Now let ω be the 2-form on M 6 given by

ω = a(α ∧ β) + b(δ 1 ∧ δ 2 ) + c(γ 1 ∧ δ 2 + γ 2 ∧ δ 1 ) , (3.1)
where a, b, c ∈ R. A simple computation shows that dω = 0 and that

ω 3 = 4ac 2 (α ∧ β ∧ γ 1 ∧ γ 2 ∧ δ 1 ∧ δ 2 ) .
Hence ω 3 = 0 if and only if a = 0, c = 0. This proves the following Proposition 3.1 M 6 is a compact symplectic manifold. Let ω be a 2-form on M 6 given by (3.1), where a, b, c ∈ R and a = 0, c = 0. Then ω is a symplectic form.

A compact Kähler manifold satisfies the Hard Lefschetz Theorem. In order to continue the analysis of the manifold M 6 we introduce the following Definition Let (M 2n , ω) be a compact symplectic manifold. We say that (M 2n , ω) satisfies the Hard Lefschetz Theorem if the mappings

∧ω n-p : H p (M 2n , R) -→ H 2n-p (M 2n , R) are all isomorphisms, 0 ≤ p ≤ n.
(We notice that in [START_REF] Mcduff | The moment map for circle actions on symplectic manifolds[END_REF], McDuff calls (M 2n , ω) a Lefschetz manifold when the mapping ∧ω n-1 : H 1 (M 2n , R) -→ H 2n-1 (M 2n , R) is an isomorphism. Our present definition is more restrictive.) Theorem 3.1 M 6 does not satisfy the Hard Lefschetz Theorem.

Proof: Let us compute the morphism

∧[ω] : H 2 (M 6 , R) -→ H 4 (M 6 , R) .
We obtain

∧[ω]([α ∧ β]) = 2c[α ∧ β ∧ γ 1 ∧ δ 2 ] , ∧[ω]([δ 1 ∧ δ 2 ]) = 0 , ∧[ω]([γ 1 ∧ δ 2 + γ 2 ∧ δ 1 ]) = 2a[α ∧ β ∧ γ 1 ∧ δ 2 ] + 2c[γ 1 ∧ γ 2 ∧ δ 1 ∧ δ 2 ] . This implies that ∧[ω] : H 2 (M 6 , R) -→ H 4 (M 6 , R) is not an isomorphism.
.

Corollary 1

The compact symplectic solvmanifold M 6 does not admit Kähler structures.

We note that a straightforward computation shows that all the (triple) Massey products of M 6 vanish. However we have the following Theorem 3.2 The minimal model of M 6 is not formal.

Proof: It is sufficient to exhibit a (quadruple) non-trivial Massey product. For this we recall that if there are cohomology classes

[λ 1 ] ∈ H p (M 6 , R), [λ 2 ] ∈ H q (M 6 , R), [λ 3 ] ∈ H r (M 6 , R) and [λ 4 ] ∈ H s (M 6 ,
∈ Ω p+q-1 (M 6 ), f 2 ∈ Ω q+r-1 (M 6 ), f 3 ∈ Ω r+s-1 (M 6 ), µ 1 ∈ Ω p+q+r-2 (M 6 ) and µ 2 ∈ Ω q+r+s-2 (M 6 ) satisfying: (1) λ 1 ∧ λ 2 = df 1 , (2) λ 2 ∧ λ 3 = df 2 , (3) λ 3 ∧ λ 4 = df 3 , (4) λ 1 ∧ f 2 + (-1) p+1 f 1 ∧ λ 3 = dµ 1 , (5) λ 2 ∧ f 3 + (-1) q+1 f 2 ∧ λ 4 = dµ 2 , (6) the cohomology class [(-1) p+1 λ 1 ∧ µ 2 + (-1) q+1 µ 1 ∧ λ 4 + f 1 ∧ f 3 ] is zero in H p+q+r+s-2 (M 6 , R).
Now, because all the (triple) Massey products on M 6 are zero, it is defined the (quadruple

) Massey product [δ 1 ∧ δ 2 ], [β], [β], [β] . We shall prove that is non-zero. Let us suppose that [δ 1 ∧ δ 2 ], [β], [β], [β] = 0. Then, there exist differential forms f 2 , f 3 , µ 2 ∈ Ω 1 (M 6 ) and f 1 , µ 1 ∈ Ω 2 (M 6 ) satisfying (1') δ 1 ∧ δ 2 ∧ β = df 1 , (2') 0 = df 2 , (3') 0 = df 3 , (4') δ 1 ∧ δ 2 ∧ f 2 -f 1 ∧ β = dµ 1 , (5') β ∧ f 3 + f 2 ∧ β = dµ 2 , (6') [-δ 1 ∧ δ 2 ∧ µ 2 + µ 1 ∧ β + f 1 ∧ f 3 ] = 0. Since δ 1 ∧ δ 2 ∧ β = d(-γ 1 ∧ δ 2 ), from (1'
) we get a differential form f 1 with df 1 = 0 and such that [START_REF] Cordero | Compact symplectic manifolds not admitting positive definite Kähler metrics[END_REF] 8) and ( 9) we obtain

f 1 = -γ 1 ∧ δ 2 + f 1 . Substituting (7) in (4') we have (8) δ 1 ∧ δ 2 ∧ f 2 + γ 1 ∧ δ 2 ∧ β + f 1 ∧ β = dµ 1 . From (8) and (2') it follows that the cohomology class [δ 1 ∧ δ 2 ] ∧ [f 2 ] belongs to [β]H * (M 6 , R); and so (9) f 2 = tβ for some t ∈ R. Moreover, because the cohomology class [δ 1 ∧ δ 2 ∧ β] is zero, from (
[β ∧ γ 1 ∧ δ 2 ] = [β] ∧ [f 1 ]
, and then we have [START_REF] Deligne | Real homotopy theory of Kähler manifolds[END_REF]

f 1 = 1 2 (γ 1 ∧ δ 2 + γ 2 ∧ δ 1 ) + pα ∧ β + qδ 1 ∧ δ 2 ,
for some p, q ∈ R. Now, from ( 7) and [START_REF] Deligne | Real homotopy theory of Kähler manifolds[END_REF] we get [START_REF] Fernández | Compact symplectic four dimensional solvmanifolds not admitting complex structures[END_REF]

f 1 = 1 2 (γ 2 ∧ δ 1 -γ 1 ∧ δ 2 ) + pα ∧ β + qδ 1 ∧ δ 2 .
On the other hand, from ( 9), (3') and (5') we obtain f 2 -f 3 = sβ for some s ∈ R, and so (12) f 3 = (t -s)β. From ( 9) and ( 12), condition (5') becomes:

(5") dµ 2 = 0. It is easy to get: [START_REF] Hattori | Spectral sequence in the de Rham cohomology of fibre bundles[END_REF]

f 1 ∧ f 3 = d((t -s)γ 2 ∧ (qδ 1 -1 2 γ 1 )
). From ( 9), [START_REF] Fernández | Compact symplectic four dimensional solvmanifolds not admitting complex structures[END_REF], (5") and [START_REF] Hattori | Spectral sequence in the de Rham cohomology of fibre bundles[END_REF], conditions (4') and (6') become

(4") (t + q)β ∧ δ 1 ∧ δ 2 -1 2 β ∧ (γ 2 ∧ δ 1 -γ 1 ∧ δ 2 ) = dµ 1 , (6") -[δ 1 ∧ δ 2 ] ∧ [µ 2 ] + [µ 1 ∧ β] = 0. But, we can check that β ∧ δ 1 ∧ δ 2 = d(-γ 1 ∧ δ 2 ) and β ∧ (γ 2 ∧ δ 1 -γ 1 ∧ δ 2 ) = d(γ 1 ∧ γ 2 ).
These equations and (4") imply that there is a closed differential form µ 1 such that

µ 1 = -(t + q)γ 1 ∧ δ 2 -1 2 γ 1 ∧ γ 2 + µ 1 , and thus [µ 1 ∧ β] = -(t + q)[γ 1 ∧ δ 2 ∧ β] -1 2 [γ 1 ∧ γ 2 ∧ β] + [µ 1 ] ∧ [β]. Then, condition (6") becomes: -[δ 1 ∧ δ 2 ] ∧ [µ 2 ] -(t + q)[γ 1 ∧ δ 2 ∧ β] -1 2 [γ 1 ∧ γ 2 ∧ β] + [µ 1 ] ∧ [β] = 0. So, the cohomology class [γ 1 ∧ γ 2 ∧ β] belongs to [β]H 2 (M 6 , R) + [δ 1 ∧ δ 2 ]H 1 (M 6 , R), which is generated by {[β ∧ γ 1 ∧ δ 2 ], [α ∧ δ 1 ∧ δ 2 ]}. This is impossible because the family {[γ 1 ∧ γ 2 ∧ β], [β ∧ γ 1 ∧ δ 2 ], [α ∧ δ 1 ∧ δ 2 ]} is free.
Remark 3 Theorem 3.2 also proves that M 6 does not admit Kähler structures.

Next, we shall prove that the minimal model of the complex of left invariant differential forms of G 2 (G 2 = H × S 1 , where H is the Lie group of dimension 7 constructed in Remark 1) is formal, but it does not verify the Hard Lefschetz Theorem (see [START_REF] Ch | Kähler structures on solvmanifolds for completely solvable Lie groups[END_REF]).

Then a compact manifold of the form Γ/G 2 could not be Kähler. Unfortunately we do not know if G 2 admits a cocompact subgroup. We first recall the structure of (ΛG * 2 , d 2 ) and H * (G 2 , R) (cf. [START_REF] Ch | Kähler structures on solvmanifolds for completely solvable Lie groups[END_REF]). A basis of G * 2 is the family {α, β, µ 1 , ν 1 , ξ 1 , µ 2 , ν 2 , ξ 2 } and the differential operator d is given by dα = 0

dβ = 0 dµ 1 = -α ∧ µ 1 , dµ 2 = α ∧ µ 2 , dν 1 = 2α ∧ ν 1 , dν 2 = -2α ∧ ν 2 , dξ 1 = α ∧ ξ 1 -µ 1 ∧ ν 1 , dξ 2 = -α ∧ ξ 2 -µ 2 ∧ ν 2 ,
On the other hand, the cohomology of G 2 can be written as a product Λ{[α], [β]} ⊗ A where A is the following gca: [START_REF] Halperin | Obstructions to Homotopy Equivalences[END_REF]). A straightforward calculation gives (j,k,l) any permutation of (2, 3, 4), and

A 0 = {1} , A 2 = {[µ 1 ∧ µ 2 ] , [ν 1 ∧ ν 2 ] , [µ 1 ∧ ξ 1 ] , [µ 2 ∧ ξ 2 ]} , A 4 = {[ν 1 ∧ ν 2 ∧ ξ 1 ∧ ξ 2 ] , [µ 1 ∧ ξ 1 ∧ ν 1 ∧ ν 2 ] , [ν 1 ∧ ν 2 ∧ µ 2 ∧ ξ 2 ] , [µ 1 ∧ ξ 1 ∧ µ 2 ∧ ξ 2 ]} , A 6 = {[ν 1 ∧ ν 2 ∧ µ 1 ∧ ξ 1 ∧ µ 2 ∧ ξ 2 ]} , and A 1 = A 3 = A 5 = 0. Consider ϕ: (ΛZ, d) -→ A the bigraded model of A (cf.
Z 6 0 = {0} Z 5 1 = {f } Z 5 0 = {0} Z 4 2 = {x i , y j , z j } Z 4 1 = {h j } Z 4 0 = {e} Z 3 3 = {0} Z 3 2 = {0} Z 3 1 = {c i , g j } Z 3 0 = {0} Z 2 4 = {0} Z 2 3 = {0} Z 2 2 = {0} Z 2 1 = {0} Z 2 0 = {b i } Z 1 5 = {0} Z 1 4 = {0} Z 1 3 = {0} Z 1 2 = {0} Z 1 1 = {0} Z 1 0 = {0} with db i = de = 0 , dc i = b 2 i , dg j = b 1 b j , dh j = eb j , df = b 2 b 3 b 4 -eb 1 , dx i = b 1 c i -b i g i , dy j = b j c 1 -b 1 g j , dz j = b k g l -b l g k , 1 ≤ i ≤ 4,
ϕ(b 1 ) = [µ 1 ∧ µ 2 ] , ϕ(b 2 ) = [µ 1 ∧ ξ 1 ] , ϕ(b 3 ) = [µ 2 ∧ ξ 2 ] , ϕ(b 4 ) = [ν 1 ∧ ν 2 ] , ϕ(e) = [ν 1 ∧ ν 2 ∧ ξ 1 ∧ ξ 2 ] ;
We construct a d.g.c.a.-morphism ψ: Λ({α, β}, 0) ⊗ (ΛZ, d) -→ (ΛG * 2 , d) inducing an isomorphism in cohomology. This will end the proof. Put

ψ(α) = α , ψ(β) = β , ψ(b 1 ) = µ 1 ∧ µ 2 , ψ(b 2 ) = µ 1 ∧ ξ 1 , ψ(b 3 ) = µ 2 ∧ ξ 2 , ψ(b 4 ) = ν 1 ∧ ν 2 , ψ(e) = ν 1 ∧ ν 2 ∧ ξ 1 ∧ ξ 2 , ψ(g 4 ) = µ 1 ∧ ν 1 ∧ ξ 2 , ψ( other genarators ) = 0.
This map extends naturally to a g.c.a.-morphism ψ: (Λ{α, β}, 0)⊗(ΛZ, d) -→ (ΛG * 2 , d). It remains to prove that ψ is a differential operator and that ψ * is an isomorphism.

• A direct calculation shows that ψ(dx) = dψ(x) for x = α, β and for each generator

x ∈ p+q≤6 (ΛZ) p q . Consider x ∈ Z p q a generator with p + q > 6; by definition of ψ we have ψ(x) = 0. Since dZ p q ⊂ (ΛZ) p+1 q-1 the writing of dx does not contain any of the following monomials:

b i , e, g 4 , b 1 e, b 1 b 4 , b 2 b 4 , b 3 b 4 .
By construction the operator ψ vanishes when evaluated on the other monomials of Z. We conclude that ψ(dx) is 0.

• ψ * is an isomorphism because ψ * [α] = [α] , ψ * [β] = [β] , ψ * [b 1 ] = [µ 1 ∧ µ 2 ] , ψ * [b 2 ] = [µ 1 ∧ ξ 1 ] , ψ * [b 3 ] = [µ 2 ∧ ξ 2 ] , ψ * [b 4 ] = [ν 1 ∧ ν 2 ] , ψ * [e] = [ν 1 ∧ ν 2 ∧ ξ 1 ∧ ξ 2 ] .
4 The moduli space of complex structures on M 6 First, let us recall the following lemma [START_REF] De Andrés | Moduli spaces of complex structures on compact four dimensional nilmanifolds[END_REF]: Lemma 4.1 Let G be a (real) Lie group of (real) dimension 2n. Then the space of left invariant almost complex structures on G has dimension 2n 2 .

In our case the space of left invariant almost complex structures on G has dimension 18. This lemma gives no information about left invariant complex structures, but since G has a canonical parallelization, it is extremely easy to determine when a left invariant almost complex structure is integrable.

We set

E 1 = T, E 2 = X, E 3 = Y 1 , E 4 = Y 2 , E 5 = Z 1 , E 6 = Z 2 .
Let J be a left invariant almost complex structure on G. Then J has constant coefficients with respect to the basis

{E 1 , E 2 , E 3 , E 4 , E 5 , E 6 }. Write JE j = 6 k=1 a jk E k ,
where the a jk are constants. The Nijenhuis tensor N J of J is defined by

N J (U, V ) = [JU, JV ] -J[JU, V ] -J[U, JV ] -[U, V ],
for all vector fields U, V on G. Proposition 4.1 G has no left invariant complex structures. Equivalently, the manifold M 6 has no complex structures with constant coefficients with respect to the canonical parallelization {E 1 , E 2 , E 3 , E 4 , E 5 , E 6 }.

Proof: Let J be a left invariant integrable almost complex structure on G. Below, we shall prove that the matrix of J with respect to the basis {E i , 1 ≤ i ≤ 6} must have the form Finally we shall give a proof of (4.1): For this we shall show: (I) a 41 = 0, (II) a 31 = 0, (III) a 61 = 0, (IV) a 42 = 0, (V) a 51 = 0, (VI) a 32 = 0, (VII) a 52 = 0, and (VIII) a 62 = 0. ¿From (2.2) we have 0 = N J (E

J =           a 11 a
= N J (E 2 , E 4 ) = a 46 (a 22 -a 44 )E 4 -a 2 46 E 6 .
This identity implies that a 46 = 0. Then, from (I) and (4.18) we obtain JE 4 = a 44 E 4 which is not possible.

To prove (III), we suppose that a 61 = 0. Then, from (I) and (II) we obtain that the coefficient of E 1 in N J (E To prove (IV), we compute the coefficient of E 2 in N J (E 4 , E 6 ) and we obtain -a 2 42 E 2 = 0, from which we deduce (IV).

To prove (V), let us suppose that a 51 = 0. Then from (IV) we deduce that the coefficient of E 1 in N J (E 2 , E 5 ) is -a 21 a 51 , from which we deduce a 21 = 0 . Because a 32 = 0, (4.27) implies a 43 = 0 and a 2 44 = -1. But it is not possible. Thus, it must be a 32 = 0. From this identity, (4.26), and equating to zero the coefficient of E 2 in N J (E 1 , E 2 ), we get a 26 a 62 = 0 . (4.28) Thus, if a 51 = 0, from (I)-(IV), (4.24), (4.25), (4.26) and a 32 = 0, it follows that the matrix of J is of the form . ¿From (4.28) and J 2 = -Id we obtain a 2 22 = -1, which is not possible. Thus, we have (V).

J =         
To prove (VI) we compute the coefficients of E 2 and E 5 in N J (E 3 , E 5 ). They are -(a 2 32 + a 35 a 52 ) and -a 32 a 35 , respectively. Then we deduce (VI).

To prove (VII), let us suppose that a 52 = 0. If we compute the coefficient of E 2 in N J (E 2 , E 5 ), then we obtain -a 21 a 52 = 0, which implies that a 21 = 0. Thus, if a 52 = 0, according (I)-(VI), the matrix of J would be: and, since J 2 = -Id, we obtain a 2 11 = -1, which is a contradiction. This proves (VII). Finally, to prove (VIII), let us suppose that a 62 = 0. If we compute the coefficient of E 2 in N J (E 2 , E 6 ), then we obtain a 21 a 62 = 0, which implies that a 21 = 0. Then, if a 62 = 0, the matrix of J is of the form (4.29). Again we have a contradiction. This proves (VIII), and the proof of (4.1) is completed.

J =         

  R) (represented by differential forms λ 1 , λ 2 , λ 3 and λ 4 ) such that the (triple) Massey products [λ 1 ], [λ 2 ], [λ 3 ] and [λ 2 ], [λ 3 ], [λ 4 ] are zero, then there exists the (quadruple) Massey product [λ 1 ], [λ 2 ], [λ 3 ], [λ 4 ] . Moreover, it is zero if and only if there are differential forms f 1

Proposition 3 . 2

 32 The complex of the left invariant differential forms of G 2 is formal. Proof: We need to show that the d.g.c.a. (ΛG * 2 , d 2 ), made up of the left invariant differential forms of G 2 , and the d.g.c.a. (H * (G 2 , R), 0) have the same minimal model.

  (4.24) Moreover we have that the coefficient of E 1 in N J (E 1 , E 6 ) and in N J (E 1 , E 3 ) is -a 51 a 65 and -a 35 a 51 , respectively, from which we geta 35 = a 65 = 0 . (4.25) Also we have that the coefficient of E 1 in N J (E 1 , E 2 ) is -a 25 a 51 ,and that the coefficient of E 5 in N J (E 4 , E 5 ) is -2a 45 a 51 , from which we obtain a 25 = a 45 = 0 . (4.26) Now, from (I), (II) and (4.26), we obtain 0= N J (E 3 , E 4 ) = a 32 a 46 E 4 ,and so a 32 a 46 = 0. Suppose that a 32 = 0 and a 46 = 0. Then JE 4 = a 43 E 3 + a 44 E 4 , and since J 2 = -Id, we find a 43 a 32 = 0 , a 43 a 34 + a 2 44 = -1 . (4.27)

  12 a 13 a 14 a 15 a 16 a 21 a 22 a 23 a 24 a 25 a 26 0 0 a 33 a 34 a 35 a 36 0 0 a 43 a 44 a 45 a 46 0 0 a 53 a 54 a 55 a 56 0 0 a 63 a 64 a 65 a 66 Let us suppose (4.1). Since J 2 = -I, we obtain a 2 11 + a 12 a 21 = a 2 22 + a 12 a 21 = -1 , (4.2) a 12 (a 11 + a 22 ) = a 21 (a 11 + a 22 ) = 0 , (4.3) and so a 12 , a 21 are non-zero, and a 11 + a 22 = 0. Moreover, we have 0 = N J (E 2 , E 3 ) = (a 22 a 35 -a 33 a 35 -a 36 a 43 )E 3 + (-2a 21 a 34 + a 22 a 36 -a 34 a 35 -a 36 a 44 )E 4 -(a 2 35 + a 36 a 45 )E 5 -a 36 (2a 21 + a 35 + a 46 )E 6 , 0 = N J (E 2 , E 4 ) = (2a 21 a 43 + a 22 a 45 -a 33 a 45 -a 43 a 46 )E 3 + (a 22 a 46 -a 34 a 45 -a 44 a 46 )E 4 +a 45 (2a 21 -a 35 -a 46 )E 5 -(a 2 46 + a 36 a 45 )E 6 . Assume that a 46 = -a 35 . Since a 21 = 0, then (4.5) and (4.7) imply a 36 = a 45 = 0. Again (4.4) and (4.8) imply a 35 = a 46 = 0. Now, from (4.6) it follows that a 43 = 0; and so JE 4 = a 44 E 4 . This implies a 2 44 = -1, which is a contradiction. Thus, (4.9) must be 36 a 21 = -a 36 a 35 , a 45 a 21 = a 35 a 45 . -a 36 a 45 a 35 = a 21 a 36 a 45 = a 35 a 36 a 45 = -a 3 35 , that is a 35 = 0. Thus a 46 = 0. But a 21 = 0 (4.12) imply a 36 = a 45 = 0. Now, a 21 = 0 and (4.6) imply a 43 = 0, and hence JE 4 = a 44 E 4 , which is not possible. Therefore, G carries no left invariant integrable almost complex structures.

	¿From (4.4) and (4.8) we obtain
	(4.9)	a 46 = ±a 35 .
	(4.10)	a 46 = a 35 .
	¿From (4.10), (4.5) and (4.7) we have
		a 36 (a 21 + a 35 ) = 0 ,
	(4.11)	a 45 (a 21 -a 35 ) = 0 ,	
	or equivalently (4.1) a (4.12)	        
	Then, from (4.4) and (4.12) we obtain
	a 3 35 =
	These equations imply
	(4.4)	a 2 35 = -a 36 a 45 ,
	(4.5)	0 = a 36 (2a 21 + a 35 + a 46 ) ,
	(4.6)	a 45 (a 22 -a 33 ) = a 43 (a 46 -2a 21 ) ,
	(4.7)	0 = a 45 (2a 21 -a 35 -a 46 ) ,
	(4.8)	a 2 46 = -a 36 a 45 .

  3 , E 4 ) = 2a 31 a 41 E 1 + (a 31 a 42 + a 32 a 41 )E 2 + (2a 31 a 43 + a 32 a 45 -a 35 a 42 )E 3 + (2a 34 a 41 + a 32 a 46 -a 36 a 42 )E 4 + 2a 31 a 45 E 5 + 2a 36 a 41 E 6 . (4.13) To prove (I), let us suppose that a 41 = 0. Then from (4.13), equating to zero the coefficients of E 1 , E 2 , E 6 and E 4 , it followsa 31 = a 32 = a 34 = a 36 = 0 . (4.14) Also, from (4.13) we have a 35 a 42 = 0. If a 35 = 0, then JE 3 = a 33 E 3 , and so Since J 2 = -Id and JE 3 = a 33 E 3 + a 35 E 5 we have a 51 = a 52 = a 54 = a 56 = a 12 = a 33 + a 55 = 0 . J (E 2 , E 5 ) = {a 22 (a 55 -a 33 ) -a 33 a 55 -1}E 3 -a 35 (a 22 + a 55 )E 5 . (4.17) Since a 35 = 0, from (4.16) and (4.17) we get a 22 + a 55 = 0 and 2a 22 a 55 + a 2 55 -1 = 0 . Let us suppose that a 31 = 0. Then from (4.13) and (I) we obtain a 42 = a 43 = a 45 = 0 .

	(4.16)
	¿From (4.14) and (4.16) we obtain
	0 = N These equations imply a 2 55 = -1, which is a contradiction. This proves (I).
	(II) (4.18)
	¿From (I), (2.2) and (4.18) it follows that
	0
	a 2 33 = -1, which is a contradiction. Thus, we get
	(4.15)	a 35 = 0 and a 42 = 0 .

  5 , E 6 ) is 2a 51 a 61 , and hence, we get II) and (4.[START_REF] Ue | Geometric 4-manifolds in the sense of Thurston and Seifert 4-manifolds I[END_REF] we deduce that the coefficient of E 1 in N J (E 2 , E 6 ) and in N J (E 1 , E 3 ) is a 21 a 61 and -a 36 a 61 , respectively. Thus, we havea 21 = a 36 = 0 . (4.20) ¿From (4.20) we conclude that the coefficient of E 5 in N J (E 2 , E 3 ) is -a 2 II) and (4.21) we deduce that the coefficient of E 2 in N J (E 3 , E 5 ) is J (E 3 , E 6 ) = 2a 34 a 61 E 4 .Now, from (I), (II) and (4.20)-(4.23) we have JE 3 = a 33 E 3 , which is not possible; and we obtain (III).

	(4.19)	a 51 = 0 .
	¿From (I), (35 . Thus,
	we get
	(4.21)	a 35 = 0 .
	¿From (I), (-a 2 32 . Thus, we get
	(4.22)	a 32 = 0 .
	¿From (4.22) we have
	0 = N This equation implies that
	(4.23)	a 34 = 0 .

   a 11 a 12 a 13 a 14 a 15 a 16 0 a 22 a 23 a 24 0 a 26 0 0 a 33 a 34 0 a 36 0 0 a 43 a 44 0 a 46 a 51 a 52 a 53 a 54 a 55 a 56 0 a 62 a 63 a 64 0 a 66

	
	        

   a 11 a 12 a 13 a 14 a 15 a 16 0 a 22 a 23 a 24 a 25 a 26 0 0 a 33 a 34 a 35 a 36 0 0 a 43 a 44 a 45 a 46 0 a 52 a 53 a 54 a 55 a 56 0 a 62 a 63 a 64 a 65 a 66

		
	(4.29)	       	,
		


Transveral Differential Evolution overview

Vitaliy Feoktistov, Stefan Janaqi

To cite this version:

Vitaliy Feoktistov, Stefan Janaqi. Transveral Differential Evolution overview. 5e Conférence Francophone de MOdélisation et SIMulation, Sep 2004, Nantes, France. hal-00366061


Esteban Marquer
email: esteban.marquer@loria.fr

Safa Alsaidi

Amandine Decker

Pierre-Alexandre Murena
email: pierre-alexandre.murena@aalto.fi

Miguel Couceiro
email: miguel.couceiro@loria.fr

A Deep Learning Approach to Solving Morphological Analogies ⋆

Keywords: Analogy solving, Neural networks, Retrieval, Morphological word embeddings

Analogical proportions are statements of the form "A is to B as C is to D". They support analogical inference and provide a logical framework to address learning, transfer, and explainability concerns. This logical framework finds useful applications in AI and natural language processing (NLP). In this paper, we address the problem of solving morphological analogies using a retrieval approach named ANNr. Our deep learning framework encodes structural properties of analogical proportions and relies on a specifically designed embedding model capturing morphological characteristics of words. We demonstrate that ANNr outperforms the state of the art on 11 languages. We analyze ANNr results for Navajo and Georgian, languages on which the model performs worst and best, to explore potential correlations between the mistakes of ANNr and linguistic properties.

Introduction

An analogy, or analogical proportion, is a relation between four elements A, B, C, and D meaning "A is to B as C is to D", often written as A : B :: C : D. For example, cat : kitten :: dog : puppy and cat : cats :: dog : dogs are two analogies between words. Notice that the transformation between cat and kitten is a semantic one (kitten is a young cat) while the one between cat and cats is morphological (cats is the plural of cat, obtained with the suffix "-s"). We call the first example a semantic analogy and the second a morphological analogy. It can be argued that morphological analogies are covered by semantic analogies, but morphological analogies can be manipulated even without knowledge about the semantics of a word. For example, cat : cats :: Balrog : Balrogs is understandable even without knowing what a Balrog is.

There are two main tasks associated with analogical proportions. One is analogy detection that refers to task of deciding whether a quadruple A, B, C, D forms a valid analogy A : B :: C : D. The other is analogy solving that refers to the task of finding possible values x for which A : B :: C : x constitutes a valid analogy. Expressions A : B :: C : x for an indeterminate x are referred to as analogical equations. We further detail the two tasks and related approaches to tackle them in Section 2.

Analogy solving can be seen as a form of case-based reasoning (CBR) [START_REF] Lieber | When Revision-Based Case Adaptation Meets Analogical Extrapolation[END_REF]. Indeed, in CBR the goal is to find a solution s t to a problem p t using a set of problems P , a set of solutions S, and cases (p, s) ∈ P × S associating a problem p with one of its solutions s. The first step, called retrieval 3 , is to select k cases in the case base according to some criteria related to p t . The k retrieved cases are then used to propose a target solution s t , this is the adaptation step. When k = 1, we can formulate the adaptation step as solving the analogical equation p 1 : s 1 :: p t : x, with s t one of the equation's solution. There are other ways to relate analogies and CBR, albeit less related to this paper. For example, if k = 3 one can look at cases where p 1 : p 2 :: p 3 : p t is valid and s 1 : s 2 :: s 3 : x is solvable in S [START_REF] Lieber | When Revision-Based Case Adaptation Meets Analogical Extrapolation[END_REF]. Like above, s t would be solution to the equation.

As mentioned in the first paragraph, analogies can subsume relations of different nature (semantic or morphological in the example, but one could build syntactic analogies on sentences or geometric analogies on numbers or images). In this article, we focus on solving morphological analogies. While recent approaches to tackle this problem using symbolic methods achieve state of the art performance on analogy solving [START_REF] Fam | Tools for the production of analogical grids and a resource of n-gram analogical grids in 11 languages[END_REF][START_REF] Langlais | Improvements in analogical learning: Application to translating multi-terms of the medical domain[END_REF][START_REF] Murena | Solving analogies on words based on minimal complexity transformation[END_REF], they are inherently restricted to a subset of morphology as they are not able to account for "irregular" cases like cat : cats :: child : children. We use deep learning to learn morphological features of words to address this issue. Following a similar idea, Lim et al. [START_REF] Lim | Solving word analogies: A machine learning perspective[END_REF] proposed a deep learning model to tackle semantic analogies on words, based on the analogical framework of Miclet et al. [START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF] and Prade and Richard [START_REF] Prade | A short introduction to computational trends in analogical reasoning[END_REF]. Unlike previous works in deep learning, the architecture integrates the characteristics of analogies by design and relies heavily on pretrained GloVe embeddings [START_REF] Pennington | Glove: Global vectors for word representation[END_REF] to compute word representations. We argue that their approach, which already deals with analogies on words, can be applied to morphological analogies. As mentioned in our previous work [START_REF] Alsaidi | A neural approach for detecting morphological analogies[END_REF], although the embedding model used by Lim et al. is well suited for semantic analogies, it results in lower performance on the morphological counterpart. In our previous work [START_REF] Alsaidi | A neural approach for detecting morphological analogies[END_REF] we addressed morphological analogy detection by proposing an embedding model targeting word morphology, and we extend those results for analogy solving in the present work.

To summarize, the main contributions of this paper are the following: (i ) we demonstrate the importance of well suited embedding space for analogy manipulation, and provide empirical evidence that analogy detection is helpful in obtaining a well suited embedding model for analogy solving, and (ii ) we pro-pose a deep learning framework that outperforms state of the art approaches to solve analogies that capture morphological features.

In the remainder of this paper we first introduce the problem of morphological analogies with a brief state of the art in Section 2. We describe the three components of our retrieval approach (ANNc, ANNr and the morphological embedding model) in Section 3, and detail our experiments in Section 4. First, we describe the dataset used in Subsection 4.1, then compare performance with different training procedures and against baselines in Subsections 4.2 to 4.4. Finally, in Subsection 4.5, we explore mistakes made by ANNr on Navajo and Georgian to get insight on the behavior and flaws of our approach. As per tradition, we conclude our paper and offer perspectives on some key aspects in Section 5.

The Problem of Morphological Analogy

An analogical proportion is a 4-ary relation denoted by A : B :: C : D and interpreted as "A is to B as C is to D". In this paper, we focus on morphological analogies, i.e., analogies on words A, B, C, and D that capture morphological transformations of words (e.g., conjugation or declension).

Analogical proportions. The importance of analogy in morphology has been long known [START_REF] De Saussure | Cours de linguistique générale[END_REF], and it has been mathematically formalized following the early works of Lepage [START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF][START_REF] Lepage | Saussurian analogy: a theoretical account and its application[END_REF]. These works paved the way towards the current view of analogical proportions [START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF][START_REF] Prade | A short introduction to computational trends in analogical reasoning[END_REF] Analogy detection. The analogy detection task corresponds to classifying quadruples ⟨A, B, C, D⟩ into valid or invalid analogies. In particular, in the context of semantic analogies, Bayoudh et al. [START_REF] Bayoudh | Evaluation of analogical proportions through kolmogorov complexity[END_REF] proposed to use Kolmogorov complexity as a distance measure between words in order to define a conceptually significant analogical proportion and to classify quadruples as valid or invalid analogies. A data-driven alternative was implemented by Lim et al. [START_REF] Lim | Solving word analogies: A machine learning perspective[END_REF], by learning the classifier directly as a neural network. In particular, analogy detection has been used in the context of analogical grids [START_REF] Fam | Tools for the production of analogical grids and a resource of n-gram analogical grids in 11 languages[END_REF], i.e., matrices of transformations of various words, similar to paradigm tables in linguistics [START_REF] Fam | Morphological predictability of unseen words using computational analogy[END_REF].

Analogy solving. The analogy solving task corresponds to inferring the fourth term that makes an analogy valid. This task is by far the most investigated in the analogy literature and several methodologies have been proposed to solve it. The approaches in the next paragraph generate the fourth element to solve the analogy, but it is also possible to leverage a list of candidates and retrieve the most fitting fourth term to solve the analogy. Many approaches in embedding spaces, including ours, use the latter method as generation from an embedding space can be challenging. In our case the candidates are the set of all the words in the dataset, called the vocabulary.

In the context of solving morphological analogies, the main trend follows the seminal work of Lepage and Ando [START_REF] Lepage | Saussurian analogy: a theoretical account and its application[END_REF] by exploiting the aforementioned postulates of analogical proportions. For instance, Lepage [START_REF] Lepage | Character-position arithmetic for analogy questions between word forms[END_REF] uses these postulates to address multiple characteristics of words, such as their length, the occurrence of letters and of patterns. Following the results of Yvon [START_REF] Yvon | Finite-state transducers solving analogies on words[END_REF] about closed form solutions, the Alea algorithm [START_REF] Langlais | Improvements in analogical learning: Application to translating multi-terms of the medical domain[END_REF] proposes a Monte-Carlo estimation of the solutions of an analogical equation by sampling among multiple sub-transformations. Recently, a more empirical approach was proposed by Murena et al. [START_REF] Murena | Solving analogies on words based on minimal complexity transformation[END_REF], which does not rely on the axioms of analogical proportions. Their method consists in finding the simplest among all possible transformations from A to B which could also apply to C, using the Kolmogorov complexity of the transformations. We provide more details on the latter two approaches in Subsection 4.3.

Analogy in embedding spaces. A particular and noteworthy form of analogical proportions in vector spaces is the parallelogram rule that states that four vectors e A , e B , e C , and e D are in analogical proportion if e D -e C = e B -e A . This relation has been used since the first works on analogy [START_REF] Rumelhart | A model for analogical reasoning[END_REF], and it is a key element in the methodology employed by the recent neural-based approaches [START_REF] Drozd | Word embeddings, analogies, and machine learning: Beyond kingman + woman = queen[END_REF][START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF]. In this setting, the parallelogram rule is applied in some learned embedding space, with e A , e B , e C , and e D being the embeddings of four elements A, B, C, and D. We detail two of the most used methods for solving analogies in embedding spaces, namely 3CosAdd [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] and 3CosMul [START_REF] Levy | Dependency-based word embeddings[END_REF], in Subsection 4.3. These two approaches implicitly generate a solution e x and retrieve the closest candidate from the vocabulary. However, Chen et al. [START_REF] Chen | Evaluating vector-space models of analogy[END_REF] argue that the latter two methods significantly differ from human performance. Nonetheless, frameworks based on analogy datasets like those mentioned in [START_REF] Lim | Solving word analogies: A machine learning perspective[END_REF] appear to bridge this gap in performance. Similarly to the method of Lim et al. [START_REF] Lim | Solving word analogies: A machine learning perspective[END_REF], ours learns a model for both the analogy detection and solving tasks in morphology. This approach models analogy as described by the analogy data, unlike 3CosAdd and 3CosMul that rely on fixed formulas and on the expected properties of the embedding space.

Proposed Approach

In this section we present the approach we use, illustrated in Figure 1. There are 3 components in our framework, and they are described in Subsection 3.1: a classification model (ANNc) and a retrieval model (ANNr), both taking as input embeddings computed by a morphological embedding model. We then detail our training and evaluation procedures in Subsection 3.2. Additional information about the parameters of our model are given in Subsection 4.2.

Fig. 1: Morphological embedding model, data augmentation, analogy classification (ANNc) and analogy retrieval (ANNr) models.

Classification, Retrieval and Embedding Models

The models described in this subsection follow the structure of the ones proposed in [START_REF] Alsaidi | A neural approach for detecting morphological analogies[END_REF][START_REF] Lim | Solving word analogies: A machine learning perspective[END_REF] and are schematized in Figure 1.

Classification. The neural network classifier follows the idea that an analogy A : B :: C : D is valid if A and B differ in the same way as C and D. We call this model Analogy Neural Network for classification (ANNc). Technical details on this model can be found in our previous works [START_REF] Alsaidi | A neural approach for detecting morphological analogies[END_REF][START_REF] Alsaidi | On the Transferability of Neural Models of Morphological Analogies[END_REF].

Retrieval. An approach to solving A : B :: C : x is to find how e B differs from e A and to generate an e x that differs from e C in the same way. Central permutation (see Section 2) allows us to apply the same operations on A : C :: B : x, to obtain e x from e B using the difference between e A and e C .

Following this intuition, the model applies two separate fully connected layers with ReLU activation to determine the relation between e A and e B on the one side (fully connected layer 1 in Figure 1) and the one between e A and e C on the other side (fully connected layer 2 ). Those layers also encode the necessary information from e B and e C , respectively, while taking e A into account. Finally, fully connected layer 3 (with no activation function) generates e x the embedding of the predicted x from all the extracted information. We refer to this model as the Analogy Neural Network for retrieval (ANNr).

Embedding model. Most deep learning methodologies rely on real-valued vector representations of the data called embeddings. For many applications, there are embedding models available and that have been pretrained on large amounts of data, as it saves users the cost of fully training them. It is commonly accepted that the quality of such representations, which corresponds to the amount and nature of the encoded information as well as the properties of the embedding space, is a key factor to achieve higher performance. In our previous work [START_REF] Alsaidi | A neural approach for detecting morphological analogies[END_REF] and early experiments with pretrained word embeddings models (fasttext [START_REF] Bojanowski | Enriching word vectors with subword information[END_REF], GloVe [START_REF] Pennington | Glove: Global vectors for word representation[END_REF], Bert Multilingual [START_REF] Devlin | BERT: pre-training of deep bidirectional transformers for language understanding[END_REF] and word2vec [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF]) ANNc performed poorly. Note that fasttext, which uses sub-words instead of words and is thus closer to morphology, produced better results. Such general-purpose embedding models, oriented towards the distributional semantics of words, seem ill-suited to manipulate morphological analogies. We thus proposed in [START_REF] Alsaidi | A neural approach for detecting morphological analogies[END_REF] a word embedding model inspired from the work of Vania [START_REF] Vania | On understanding character-level models for representing morphology[END_REF], that is more suited to morphological tasks.

As schematized in Figure 1, the inputs of our embedding model are the characters of a word, which are embedded into vectors of size m using a learned embedding matrix. Multiple CNN filters go over the character embeddings, spanning over the full embeddings of 2 to 6 characters, and resulting in filter sizes between 2 by m and 6 by m. For each filter, the model computes the maximum output to serve as a component of the word embedding. This last operation keeps only salient patterns detected by each of the filters, and forces each CNN filter to specialize in identifying a specific pattern of characters. As we use character embeddings to encode character features, the model can capture patterns such as "-ing" but also "vowel-vowel-consonant". This flexibility is useful to deal with phenomena like euphony which is, in very simple terms, a change of sound to make a word easier to pronounce (e.g., far becomes further when adding the suffix -ther ). These character patterns correspond to morphemes, which are the minimal units of morphology. For further details see [START_REF] Alsaidi | A neural approach for detecting morphological analogies[END_REF].

Training and Evaluation

Data augmentation. The postulates of analogical proportions described in Section 2 enable the generation multiple analogies from each quadruple in our analogy dataset. We refer to this process as data augmentation. It extends the amount of data available, but also makes the models learn how to fit the formal postulates of analogy.

We follow a similar intuition for two losses based on the L 2 distance or Mean Squared Error (MSE):

M SE(e D , e D ) = 1 n i∈[1,n] (e D,i -e D,i ) 2 (3)
A second option is to normalize with regards to some random embedding e z :

L norm. random = 1 + M SE(e D , e D ) 1 + M SE(e z , e D ) (5)
As the model is trained with batches of randomly selected samples, we associate each prediction with an unrelated embedding e z by permuting e D along the batch dimension. Finally, we consider the sum of all the above loss terms, in order to determine whether their combination overcomes the limitations of each:

L all = L CEL + L norm. other + L norm. random (6)
Inference and evaluation. The output of ANNr is a real-valued vector in the embedding space, but not necessarily the exact embedding of a word. As the model is not equipped with a decoder for the embedding space, we do not have direct access to the word corresponding to a generated embedding. Instead, we use cosine distance 5 to retrieve the closest embeddings among the embeddings of the whole vocabulary as the model prediction. To evaluate the performance we use top-k retrieval accuracy.

Experiments

In this section, we describe some of our experiments on the retrieval model.

The code can be found on GitHub Lightning, and were carried out using computational clusters equipped with GPUs from the Grid'5000 testbed (grele and grue clusters, see https://www. grid5000.fr).

Data

For our experiments, we used the analogies from 11 languages available in the Siganalogies dataset [START_REF] Marquer | Siganalogies -morphological analogies from Sigmorphon 2016 and 2019[END_REF]: Spanish, German, Finnish, Russian, Turkish, Georgian, Navajo, Arabic (Romanized), Hungarian, and Maltese extracted from Sigmor-phon2016 [START_REF] Cotterell | The sigmorphon 2016 shared task-morphological reinflection[END_REF], and Japanese from the Japanese Bigger Analogy Test Set [START_REF] Karpinska | Subcharacter information in japanese embeddings: when is it worth it?[END_REF]. It is noteworthy that we use the data of the original Sigmorphon2016 dataset, which produces a different set of analogies than the one used by [START_REF] Fam | Tools for the production of analogical grids and a resource of n-gram analogical grids in 11 languages[END_REF][START_REF] Murena | Solving analogies on words based on minimal complexity transformation[END_REF]. In particular, Siganalogies contains analogies that are hard to solve for a non-data-driven approach (e.g., "be : was :: go : went").

For training and evaluation we use the original split of the Sigmorphon2016 [6] dataset, from which we extract the analogies independently. For the Japanese Bigger Analogy Test Set [START_REF] Karpinska | Subcharacter information in japanese embeddings: when is it worth it?[END_REF] however, no such split is available and so we split7 the extracted analogies into 70% for the training, 5% for the development, and 25% for the test set. To maintain reasonable training and evaluation times, we used up to 50000 analogies of each set, randomly selected when loading the data.

Refining the Training Procedure

We experiment with the four losses mentioned in Subsection 3.2. We also consider two training procedures: we transfer the embedding model learned in the 1.

We use a character embedding size (m in Figure 1) of 64 and 16 × 5 filters spanning over 2 to 6 input characters, resulting in embeddings of 80 dimensions. We use 128 filters for ANNc (n in Figure 1). We use Adam [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF] with the recommended learning rate of 10 -3 . For retrieval, we use a learning rate of 10 -5 for the embedding model which produced better results experimentally in both transfer and non-transfer settings.

8 By freezing we mean that the parameters of the model are not updated. 9 By convergence we mean that there is no improvement in the development set loss.

Transferring embeddings from ANNc significantly improves ANNr performance.

A first conclusion from the results in Table 1 is that reusing the embedding model from ANNc significantly improves the final performance, in addition to reducing the convergence time, which is expected when performing transfer learning between closely related tasks. When training the embedding from scratch, we observe low performance as shown in Table 1. Removing the limit on the total training time does not significantly improve those results. This indicates that ANNr is not suited to learning the embedding model and requires a pretrained embedding. ANNc seems suitable for this task.

Normalized MSE performs better than Cosine Embedding Loss. A second effect we observe in Table 1 is that even though we use cosine similarity to retrieve the solution, L CEL is by far the worst performing criterion. In most cases when performing transfer, using L norm. random performs better than or comparably to L norm. other and L all . L all only performs better than the other criteria on Russian. Based on these observations, we only report the results for L norm. random afterwards, but results with L norm. other and L all follow similar trends.

Performance Comparison with State of the Art Methods

We use two state of the art methods mentioned in Section 2 as baselines: the models of [START_REF] Langlais | Improvements in analogical learning: Application to translating multi-terms of the medical domain[END_REF] and [START_REF] Murena | Solving analogies on words based on minimal complexity transformation[END_REF], that we respectively refer to as Alea and Kolmo. We also report the performance of standard arithmetic methods for analogies in embedding spaces, namely, 3CosAdd [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] and 3CosMul [START_REF] Levy | Dependency-based word embeddings[END_REF] described below.

Alea [START_REF] Langlais | Improvements in analogical learning: Application to translating multi-terms of the medical domain[END_REF]. The Alea algorithm implements a Monte-Carlo estimation of the solutions of an analogy, by sampling among multiple sub-transformations. Those sub-transformations are obtained by considering the words as bags of characters and generating permutations of characters that are present in B but not in A on one side, and characters of C on the other. Intuitively, if we consider bag(A) the bag of characters in A, Alea considers bag(D) = (bag(B) -bag(A)) + bag(C) and thus D is a permutation of the characters of bag(D). For each quadruple A : B :: C : D, we generate ρ = 100 potential solutions for A : B :: C : x and select the most frequent one.

Kolmo [START_REF] Murena | Solving analogies on words based on minimal complexity transformation[END_REF]. The generation model proposed by Murena et al. considers some transformation f such that B = f (A) and f (C) is computable. The simplest transformation f is usually the one human use to solve analogies [START_REF] Murena | Solving analogies on words based on minimal complexity transformation[END_REF], and is found by minimizing the Kolmogorov complexity of f . This complexity is estimated by first expressing f using a language of operations (insertion, deletion, etc.), and computing the length of the resulting program. Unlike Alea, Kolmo is able to handle mechanisms like reduplication (repeating part of a word).

Arithmetic on embeddings. 3CosAdd [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] and 3CosMul [START_REF] Levy | Dependency-based word embeddings[END_REF] are standard methods to retrieve the fourth element of an analogy within an embedding space, Table 2: Top-1 accuracy (in %) of ANNr using L norm. random against the baselines. We report mean ± std. over 10 random seeds for our models, and when relevant the timeout rate for the baselines.

Arithmetic on ANNc emb.

Symbolic baselines Timeout (%) ANNr 3CosAdd [START_REF] Mikolov | Efficient estimation of word representations in vector space[END_REF] 3CosMul [START_REF] Levy | Dependency-based word embeddings[END_REF] Alea [START_REF] Langlais | Improvements in analogical learning: Application to translating multi-terms of the medical domain[END_REF] Kolmo [START_REF] Murena | Solving analogies on words based on minimal complexity transformation[END_REF] and are still used even if their limitations are known. In Table 2, we report results of 3CosAdd and 3CosMul applied on the embeddings trained with ANNc to measure the improvement brought by ANNr. 3CosAdd ( 7) can be seen as the parallelogram rule (D = B -A+C) with a cosine similarity to recover the closest existing solution. As 3CosMul ( 8) is harder to describe intuitively, we refer the reader to [START_REF] Levy | Dependency-based word embeddings[END_REF] for a detailed description. To avoid a 0 denominator, a ε (small) is added in [START_REF] Drozd | Word embeddings, analogies, and machine learning: Beyond kingman + woman = queen[END_REF].

Timeout on Alea and Kolmo. On a small portion of the dataset, Alea and Kolmo can take a significantly longer time to compute the results (more than 10 seconds against usually less than a second). For practical purposes, we interrupt the resolutions that take longer than 10 seconds and consider that the baseline failed to solve the analogy. Details of the portion of such cases on the test data are reported in Table 2, and it can be seen that this technical shortcut does not have a major impact on the measured baseline performance.

Performance against the baseline. As can be seen in with larger differences in Japanese and Russian (+13%), followed by Turkish (+10%), German (+9%), Navajo and Arabic (+7%). The largest increase with regards to symbolic baselines can be observed on Japanese. Symbolic methods based on characters are expected to have trouble handling complex modification of the characters themselves, while methods using character embeddings have more leeway. All approaches perform poorly on Navajo which is a language with complex verb morphology [START_REF] Eddington | A Computational Analysis of Navajo Verb Stems[END_REF] (further details in Subsection 4.5).

Distance of the Expected Result

While for some languages (mainly Navajo but also Russian and Arabic) ANNr struggles to reach a high overall accuracy, further analysis of the results indicates that the expected solution can be found in the close vicinity of the prediction. Notably, some analogical equations can have multiple viable solutions (e.g., sing : sing :: am : x for which am and are are viable). For such cases, finding a particular solution as the top candidate is less likely as other viable solutions could be preferred, which can explain part of the increase of performance. Indeed, as can be seen in Table 3, looking at the top 3 solutions increases the accuracy of the Navajo models from 52% to 78% in average, from 73% to 89% for Arabic and from 72% to 95% for Russian. Increasing the margin to the top 10 brings the accuracy of all models to at least 98%, except for Arabic and Navajo which are at 95% and 92% respectively. Compared to the size of the vocabulary of each language, a margin of 3 or even 10 is very small, yet enough to find the correct solution in most cases.

Case Analysis: Navajo and Georgian

To get further insight on the behavior of the model, we perform a more detailed analysis of where the model makes mistakes for Navajo and Georgian, the languages on which ANNr performs worst and best respectively. To be able to analyze more in-depth, we consider only one of the 10 models trained in the transfer setting with L norm. random .

Overall, there is no significant predominance of a particular permutation nor of a particular postulate (symmetry, central permutation, nor any usual combination of both) in the mistakes on either Navajo or Georgian. Additionally, less than 0.3% of mistakes on Navajo involve expected cases of reflexivity (i.e., forms like A : B :: A : B or A : A :: B : B), and no such case was observed for Georgian, indicating that reflexivity is well handled by ANNr.

Violations of stronger versions of reflexivity. We notice that 47.49% of all mistakes in Georgian are cases where either: (i ) A = B but C ̸ = D and the model predicts D = C or, similarly, by central permutation (41.06% of all mistakes), or (ii ) A ̸ = B but C = D and the model predicts D ̸ = C, or A ̸ = C but B = D and the model predicts D ̸ = B (6.42% of all mistakes). For example for (i ), ˜ox˚a : ˜ox˚a :: gonieri : x expects gonierma but gonieri is predicted. In English, a similar situation would be sing : sing :: am : x, in which expecting x = are is counter-intuitive if the underlying transformation from A to B ("pos=V, per=1, num=SG" to "pos=V, per=1, num=PL") is not provided. It is interesting to note that the model makes more mistakes when presented with an apparent instance of identity (sing : sing :: am : x) than when the expected answer is the same as one of the elements (am : are :: sing : x). This corresponds to the behavior of humans, who would prefer a simpler relation (identity is simpler that any morphological transformation) while being able to transfer from a complex case to a simpler one. This matches the data augmentation process for ANNc, A : A :: B : C is invalid while A : B :: C : C is not generated.

The permutations described in (i ) above correspond to violations of stronger versions of reflexivity, introduced in [START_REF] Lepage | De l'analogie rendant compte de la commutation en linguistique[END_REF]: strong inner reflexivity (A : A :: B : x → x = B) and strong reflexivity (A : B :: A : x → x = B). ANNr appears to implicitly learn the above properties. However, we can see in Table 3 that the expected answer is usually very close to the predicted e x , including cases when it violates strong inner reflexivity and strong reflexivity.

Complex morphology of Navajo verbs. Verbs correspond to 73.79% of all mistakes in Navajo (75.35% if we exclude cases described in the previous paragraph). Navajo is originally an oral language of the Native-American languages, and according to Eddington and Lachler [START_REF] Eddington | A Computational Analysis of Navajo Verb Stems[END_REF] "Verb stem inflectional patterns in Navajo are arguably one of the most intractable problems in modern Athabaskan linguist studies". They also refer to a work by Leer [15] which states that this complexity can be attributed to "analogical innovation, which is thus quite difficult to analyze synchronically". This could explain why symbolic baselines have a low performance on Navajo even if ANNr reaches above 92% of accuracy using the 10 most likely solutions.

The remaining mistakes in Navajo are composed of 21.11% of nouns in the first or second person of singular, both mixing prefixing and alternation but including variations which are hard to predict from the A, B, and C alone (e.g., ajáád : shijáád :: atsoo' : sitsoo' ach'íí' : nich'íí' :: sáanii : nizáanii).

Conclusion and Perspectives

In conclusion, we propose ANNr and a fitting training procedure for morphological analogies. Our approach outperforms state of the art symbolic baselines as well as more traditional methods on embedding spaces. We demonstrate the added value of ANNr compared to 3CosAdd and 3CosMul and provide in-depth analysis of results for two languages, displaying interesting properties of our framework on morphology. We provide ad hoc explanations of the behaviour of ANNr using mistakes made by the model, and explain why some unexpected predictions made by the model could be desirable, like the fact that our model prevents violations of strong reflexivity and strong inner reflexivity.

We think that the ANNc/ANNr framework can generalize to analogies on a wide range of data types and applications. In that direction, our work defines a more general framework for analogy solving by proposing a generic pipeline: we propose to pretrain an embedding model using ANNc and use it as a basis for ANNr. This makes training analogy solving from analogical data possible even without standard pretrained embedding models like GloVe as long as analogical data is available. Our framework could be expanded by using ANNc to check ANNr predictions. Our preliminary experiments confirm that mistakes can be detected that way. In practice, this could also determine viable solutions among the retrieval results, in cases where more than one solution is possible (e.g., sing : sing :: am : x for which am and are are viable solutions).

A key challenge in the future will be unsupervised analogy discovery, which would complement our framework and allow analogy solving without the need of manually labeled data. Another useful extension is complementing ANNr with a model to generate solutions from predicted embeddings as was done in [START_REF] Wang | Vector-to-sequence models for sentence analogies[END_REF], as it would enable analogical innovation and bridge the gap with symbolic approaches.

  as a 4-ary relation that verifies the following postulates for all A, B, C, and D: reflexivity (A : B :: A : B), symmetry (A : B :: C : D → C : D :: A : B), and central permutation (A : B :: C : D → A : C :: B : D). It is not difficult to verify that other equivalent forms can be derived using symmetry and central permutation: D : B :: C : A, C : A :: D : B, B : A :: D : C, D : C :: B : A and B : D :: A : C. The two main trends in the research on analogies, namely analogy detection and analogy solving, are described below.

  Given a valid analogy A : B :: C : D, we generate 7 more valid analogies, namely, A : C :: B : D, D : B :: C : A, C : A :: D : B, C : D :: A : B, B : A :: D : C, D : C :: B : A, B : D :: A : C. In practice, data augmentation is applied after the embedding model as shown in Figure 1. Further details on the training of the classifier can be found in [1]. Training criterion. As in previous works [1,2,21], we use the Binary Cross-Entropy (BCE) loss to train the classification model. For the retrieval model (to solve analogies), we experiment with multiple training objectives designed to avoid a collapse of the embedding space when training the embedding model 4 . Our first loss is based on the Cosine Embedding Loss (CEL): CEL(e D , e D , y) = 1 -cos(e D , e D ), if y = 1 max(0, cos(e D , e D )), if y = -1 (1) where e D is the embedding of D and e D a prediction for e D . Here, y = 1 if e D and e D are to be close, and y = -1 otherwise. Given an analogy A : B :: C : D, we encourage e D to be close to the actual e D and far from e A , e B , and e C the embeddings of A, B, and C by using the sum: L CEL = CEL(e A , e D , -1) + CEL(e B , e D , -1) + CEL(e C , e D , -1) + CEL(e D , e D , 1)

  where e D,i is the i-th component of e D and n is the number of dimensions of the embeddings. We encourage e D to be close to the actual e D and far from other embeddings by normalizing MSE(e D , e D ) based on distances between other embeddings. Normalizing using the full distribution of distances between embeddings would be very accurate, but computing embeddings of the full vocabulary for each training step would be computationally heavy.Instead, we experiment with two smaller-scale normalization. A first option is to normalize with regards to the possible pairs of elements in the quadruple: L norm. other = 1 + 6 × M SE(e D , e D ) 1 + a,b∈{(A,B),(A,C),(A,D),(B,C),(B,D),(C,D)} M SE(e a , e b )

  3CosAdd = argmax e D cos(e D , e B -e A + e C ) (7) 3CosMul = argmax e D cos(e D , e B )cos(e D , e C ) cos(e D , e A ) + ε

  6 . In Subsection 4.1, we briefly describe the dataset used and explain our choice of training procedure in Subsection 4.2. The performance of our model is compared with state of the art baselines in Subsection 4.3, and we explore how far the model prediction is from the expected output in Subsection 4.4. Model mistakes on Navajo and Georgian are studied in Subsection 4.5. Our experiments are implemented in PyTorch and PyTorch

Table 1 :

 1 Top-1 accuracy (i.e., precision, in %) of ANNr when training for 50 epochs with the embedding from ANNc and from scratch. We report mean ± std. over 10 random seeds. Boldface results are the best for each language.ANNc task, and we compare the results with training the embedding model from scratch with ANNr to confirm the benefits of transferring. When transferring, we obtained the best results by first freezing 8 the embedding model and training until ANNr converges9 , then unfreezing the embedding model and resuming training. We limited the total training time to 50 epochs for ANNr, and 20 for ANNc. For Japanese which has less than 50, 000 training analogies (18, 487), we limit ANNr training to 150 epochs. In average, half of the training epochs are needed to converge with the embedding frozen, but this varies between runs and ranges between 11 and 42 epochs out of 50 (18 and 68 for Japanese). Comparative results are reported in Table

		LCEL	Lnorm. other Lnorm. random	Lall
	Arabic (from scratch)	8.53 ± 0.89 16.01 ± 4.20 27.90 ± 4.66 16.45 ± 4.35
	Arabic (transfer)	6.86 ± 1.08 68.84 ± 5.54 73.08 ± 4.19 68.59 ± 3.17
	Finnish (from scratch)	21.31 ± 2.31 64.14 ± 7.07 47.25 ± 9.82 57.35 ± 5.46
	Finnish (transfer)	6.23 ± 1.27 87.37 ± 2.11 90.15 ± 1.42 89.90 ± 1.61
	Georgian (from scratch) 34.14 ± 3.44 76.33 ± 7.92 68.56 ± 9.85 77.66 ± 5.42
	Georgian (transfer)	16.82 ± 3.33 95.64 ± 1.12 97.12 ± 0.26 95.09 ± 0.65
	German (from scratch)	29.31 ± 3.42 64.05 ± 11.12 51.95 ± 11.21 54.91 ± 8.81
	German (transfer)	14.17 ± 2.02 90.66 ± 0.66 91.47 ± 0.55 91.52 ± 0.62
	Hungarian (from scratch) 24.35 ± 1.64 50.11 ± 4.72 41.25 ± 9.39 55.54 ± 4.46
	Hungarian (transfer)	11.61 ± 1.93 89.85 ± 1.52 89.42 ± 1.43 88.79 ± 1.78
	Japanese (from scratch)	23.33 ± 2.71 9.76 ± 2.52	34.00 ± 8.54 11.46 ± 3.54
	Japanese (transfer)	26.89 ± 1.66 83.10 ± 0.92 86.12 ± 0.76 74.14 ± 1.09
	Maltese (from scratch)	5.70 ± 0.88 48.21 ± 9.24 72.74 ± 3.52 51.82 ± 10.22
	Maltese (transfer)	5.63 ± 0.84 95.94 ± 0.73 97.16 ± 0.30 91.69 ± 1.55

Navajo (from scratch) 6.81 ± 0.69 19.36 ± 3.07 23.66 ± 2.99 24.69 ± 2.49 Navajo (transfer) 6.34 ± 0.64 53.73 ± 1.58 52.22 ± 1.18 52.45 ± 1.97 Russian (from scratch) 12.21 ± 1.72 38.46 ± 4.77 36.80 ± 3.84 41.04 ± 4.00 Russian (transfer) 4.47 ± 0.68 74.08 ± 1.24 71.66 ± 0.76 76.12 ± 1.11 Spanish (from scratch) 26.76 ± 1.70 84.26 ± 2.93 78.31 ± 5.91 81.76 ± 4.19 Spanish (transfer) 20.67 ± 4.32 91.03 ± 1.63 92.63 ± 1.25 91.12 ± 1.65 Turkish (from scratch) 13.30 ± 1.07 31.71 ± 4.40 42.82 ± 5.49 39.16 ± 6.82 Turkish (transfer) 7.41 ± 1.63 86.17 ± 1.66 88.36 ± 1.17 88.45 ± 1.12

Table 2

 2

	, ANNr signif-

Table 3 :

 3 Top-k accuracy (in %) of ANNr using L norm. random for k ∈ {1, 3, 5, 10}. We report mean ± std. over 10 random seeds.

		Top-1	Top-3	Top-5	Top-10
	Arabic	73.08 ± 4.19 89.05 ± 2.43 92.68 ± 1.74 95.69 ± 1.04
	Finnish	90.15 ± 1.42 96.73 ± 0.87 97.57 ± 0.63 98.28 ± 0.40
	Georgian 97.12 ± 0.26 98.86 ± 0.16 99.25 ± 0.16 99.58 ± 0.10
	German	91.47 ± 0.55 96.99 ± 0.41 97.84 ± 0.39 98.50 ± 0.31
	Hungarian 89.42 ± 1.43 97.48 ± 0.73 98.57 ± 0.54 99.15 ± 0.34
	Japanese	86.12 ± 0.76 98.48 ± 0.19 99.70 ± 0.15 99.88 ± 0.09
	Maltese	97.16 ± 0.30 99.50 ± 0.11 99.75 ± 0.08 99.89 ± 0.04
	Navajo	52.22 ± 1.18 77.67 ± 1.13 85.89 ± 0.90 92.87 ± 0.80
	Russian	71.66 ± 0.76 95.18 ± 0.54 97.24 ± 0.44 98.18 ± 0.29
	Spanish	92.63 ± 1.25 97.54 ± 0.43 98.19 ± 0.32 98.65 ± 0.26
	Turkish	88.36 ± 1.17 97.88 ± 0.55 98.79 ± 0.40 99.29 ± 0.25

An example of embedding space collapse: moving all the embeddings in a smaller area of the embedding space by multiplying them by 10

minimizes MSE(eD, eD) but does not improve retrieval performance, as the relative distance between embeddings does not change.

We experimented with both Euclidean and cosine distance, the former giving slightly better results in most cases, even though the difference is not significant.

https://github.com/EMarquer/nn-morpho-analogy-iccbr

The samples were randomly selected using a fixed random seed.

⋆ This research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation program under GA No 952215, and the Inria Project Lab "Hybrid Approaches for Interpretable AI" (HyAIAI).


Vitaliy Feoktistov
email: vitaliy.feoktistov@ema.fr

Stefan Janaqi
email: stefan.janaqi@ema.fr

Hybridization of Differential Evolution with Least-Square Support Vector Machine

Introduction

In this article we give a hybrid method for choosing "good" individuals for the next generation of Differential Evolution (DE). Keeping DE to work as is, we add the Least-Square Support Vector Machine (LS-SVM) approximation in the end of each generation cycle. Such approximation uses a subset of selected individuals of the population. As a SVM core we choose a second order polynomial kernel function. The next individual is the optimum of the SVM approximation function which can be computed analytically as a solution of a system of linear equations. This method leads us to the improvement of algorithm convergence.

Differential Evolution

Differential Evolution is a recently invented global optimization technique [START_REF] Storn | Differential evolution -a simple and efficient adaptive scheme for global optimization over continuous spaces[END_REF]. It can be classified as an iterative stochastic method. Enlarging the Evolutionary Algorithms' group, DE turns out to be one of the best population-based optimizers [START_REF] Storn | Minimizing the real functions of the ICEC'96 contest by differential evolution[END_REF]. In the following lines we give a brief description of DE algorithm.

An optimization problem is represented by a set of variables. Let these variables form a D-dimensional vector in continuous space X = (x 1 , . . . , x D ) ∈ IR D . And let there is some criterion of optimization f (X) : IR D → IR, usually named either fitness or cost function. Then, the goal of optimization is to find the values of the variables that minimize the criterion, i.e. to find

X * : f (X * ) = min X f (X) (1)
Often, the variables satisfy boundary constraints

L ≤ X ≤ H : L, H ∈ IR D (2)
As all Evolutionary Algorithms, DE deals with a population of solutions. The population IP of a generation g has N P vectors, so-called individuals of population. Each such individual represents a potential optimal solution.

IP g = X g i , i = 1, . . . , N P (3)
In turn, the individual contains D variables, so called genes.

X g i = x g i,j , j = 1, . . . , D (4)
The population is initialized by randomly generating individuals within the boundary constraints,

IP 0 = x 0 i,j = rand i,j • (h j -l j ) + l j (5)
where rand function generates values uniformly in the interval [0, 1].

Then, for each generation the individuals of a population are updated by means of a reproduction scheme. Thereto for each individual ind a set of other individuals π is randomly extracted from a population. To produce a new one the operations of Differentiation and Recombination are applied one after another. Next, the Selection is used to choose the best. Now briefly consider these operations.

Here, we show a typical model of the Differentiation, others can be found in [START_REF] Storn | Differential evolution -a simple and efficient adaptive scheme for global optimization over continuous spaces[END_REF]. For that three different individuals π = {ξ 1 , ξ 2 , ξ 3 } are randomly extracted from a population. So, the result, a trial individual, is

τ = ξ 3 + F • (ξ 2 -ξ 1 ) , (6)
where F > 0 is the constant of differentiation.

After, the trial individual τ is recombined with updated one ind. The Recombination represents a typical case of a genes' exchange. The trial one inherits genes with some probability. Thus,

ω j = τ j if rand j < Cr ind j otherwise (7)
where j = 1, . . . , D and Cr ∈ [0, 1) is the constant of recombination.

The Selection is realized by comparing the cost function values of updated and trial individuals. If the trial individual better minimizes the cost function, then it replaces the updated one.

ind = ω if f (ω) ≤ f (ind) ind otherwise (8)
Notice that there are only three control parameters in this algorithm. These are N P -population size, F and Cr -constants of differentiation and recombination accordingly. As for the terminal conditions, one can either fix the number of generations g max or a desirable precision of a solution V T R (value to reach).

The pattern of DE algorithm is presented in the following way :

Algorithm 1 Differential Evolution Require: F, Cr, N P -control parameters initialize IP 0 ← {ind 1 , . . . , ind N P } evaluate f (IP 0 ) while (stop condition) do for all ind ∈ IP g do

IP g → π = {ξ 1 , ξ 2 , . . . , ξ n } τ ← Dif f erentiate(π, F ) ω ← Recombine(τ, Cr) ind ← Select(ω, ind) g ← g + 1 end for end while
3 Least Squares Support Vector Machine method

Support vector machine (SVM) was proposed as a method of classification and nonlinear function estimation [START_REF] Vapnik | The nature of statistical learning theory[END_REF]. The idea is to map data into higher dimensional space, where an optimal separating hyperplane can be easily constructed. The mapping fulfils by means of kernel functions, which is constructed applying the Mercer's condition. The prin-cipal examples of kernels are polynomials, radial basis functions, multilayer perceptrons and others. In comparison with neural network methods SVM's gives a global solution obtained from resolving a quadratic programming problem, whereas those techniques suffer from the existence of many local minima.

The least squares version of SVM's (LS-SVM) has been recently introduced [START_REF] Suykens | Least Squares Support Vector Machines[END_REF][START_REF] Suykens | Least squares support vector machines classifiers[END_REF]. There, the solution is found by solving a linear system of equations instead of quadratic programming. It results from using equality constraints in place of inequality ones. Such linear systems were named as Karush-Kuhn-Tucker (KKT) or augmented systems.

Nevertheless, it remains the problem of matrix storage for large-scale tasks. In order to avoid it an iterative solution based on the conjugate gradient method has been proposed. Its computational complexity is O(r 2 ), where r is rank of matrix. We mention briefly LS-SVM's applied to function approximation problem.

The LS-SVM model is represented in the feature space as

y(X) = υ, φ(X) + b , (9)
with X ∈ IR D , y ∈ IR and φ(•) : IR D → IR n h is a nonlinear mapping to higher dimensional feature space.

For given training set {X k , y k } n k=1 the optimization problem is formulated as

min υ, Υ(υ, ) = 1 2 υ, υ + γ 1 2 n k=1 2 k (10)
subject to equality constraints,

y k = υ, φ(X k ) + b + k (11)
where k = 1, . . . , n. So Lagrangian is

L = Υ - n k=1 α k { υ, φ(X k ) + b + k -y k } (12)
where α k are Lagrange multipliers. By applying the Karush-Kuhn-Tucker conditions of optimality [START_REF] Fletcher | Practical methods of optimisation[END_REF][START_REF] Fletcher | Practical methods of optimisation, volume 2 : Constrained Optimization[END_REF])

∂L ∂υ = ∂L ∂b = ∂L ∂ k = ∂L ∂α k = 0 (13)
the result can be transformed in matrix form

0 1 T 1 Ω + γ -1 I b α = 0 y (14) where y = [y 1 . . . y n ], 1 = [1 . . . 1], α = [α 1 . . . α n ] and Mercer's condition Ω ij = φ(X i ), φ(X j ) = K(X i , X j ) ( 15
)
with i, j = 1, . . . , n.

Then by solving the linear system ( 14) the approximating function ( 9) is

y(X) = n k=1 α k K(X k , X) + b . ( 16
)
4 Principle of hybridization

The idea of DE's hybridization with LS-SVM lies in the approximation of the cost function at the end of each generation. For that, n best individuals are chosen from the population by means of a sort procedure. The LS-SVM approximation ( 16) is constructed on basis of these individuals. Then, by solving a linear system of D variables the optimum of such approximation can be easily found. Next, if its cost function is better (lower in case of minimization) than that of the worst individual, the obtained optimum replaces the worst one in the population. It is shown on the figure 1. Now we'll discuss it in more detail. Let the cost function f (X) be a nonlinear (perhaps epistatic, non differentiable and multimodal) function. Generally, there is no winning approach to calculate the global optimum by deterministic methods. Instead, heuristics give positive results, but they may converge quite slowly. Here we show one of the methods applied to iterative population-based technique, which allows to increase the convergence rate. By way of illustration we chose the Differential Evolution algorithm. The proposed hybridization does not touch the algorithm itself, but only incorporate one extra function at the end of each iteration. We consider this procedure in four steps.

Firstly, n best individuals (circles on the figure 1) are picked out from the population {ind k , f (ind k )} n k=1 . The selection criterion is the n best values of individuals' cost function f (ind k ). Thereto a sort procedure is used. For providing a good approximation it is necessary to balance n between the dimension of individuals D and the population size N P taking into consideration the properties of cost function. Our choice of inferior limit for n is n > D + 1. The LS-SVM support values α k are proportional to the errors at the data points [START_REF] Suykens | Least Squares Support Vector Machines[END_REF]. Moreover, a "big" n also increases the numerical errors (nearly singular matrix α min αmax → 0) on solving the system (21). The superior limit n ≤ N P is obvious. It is always necessary to keep in mind : the less is n the less iterations are needed to find the support values α k .

Secondly, these individuals represent support vectors (17) for the LS-SVM approximation model (9) and we find their support values α k . Such type of SVM's is preferable due to its rapidity ([(n + 1) × (n + 1)] system solving) and the possibility of handling a great number of training data (a Hestenes-Stiefel conjugate gradient method).

{ind k , f (ind k )} n k=1 ⇔ {X k , y k } n k=1 (17)
Thirdly, in particular case it is easily to find the optimum of this approximation (triangle on the figure 1). Let ( 16) is a model for function approximation, where n is a number of support vectors (depth of approximation) and K(X k , X) is a second order polynomial kernel function

K(X k , X) = ( X k , X + 1) 2 , ( 18
)
with X, X k ∈ IR D . Such a kernel was chosen to provide the convexity of the approximation function and the facility to find its optimum analytically. This optimum X * can be found from the following condition of optimality :

dy(X) dX = ∂y(X) ∂X(ξ) = 0 , (19)
where X(ξ), ξ = 1, . . . , D are components of a vector X.

The extremum condition ( 19) gives the system of D linear equations :

∂y(X) ∂X(ξ) = n k=1 α k • ∂K(X k , X) ∂X(ξ) = = 2 n k=1 α k ( X k , X + 1) X k (ξ) ≡ 0 ⇔ n k=1 α k X k (ξ) D ϕ=1 X k (ϕ)X(ϕ) = D ϕ=1 X(ϕ) • n k=1 α k X k (ξ)X k (ϕ) = = - n k=1 α k X k (ξ) (20)
Or alternatively, in the matrix form

A • X = B , (21)
where

A = a(ξ, ϕ) = n k=1 α k X k (ξ)X k (ϕ) B = b(ξ) = - n k=1 α k X k (ξ) ( 22
)
The optimum is found by solving this system. Fourthly, we compare calculated from (21) optimum X * (square on the figure 1) with the worst individual in the population ind * (the highest black point on figure 1). The better one takes place in the population.

ind * = X * if f (X * ) ≤ f (ind * ) ind * otherwise ( 23
)
where

ind * : f (ind * ) = max 1≤i≤N P f (ind i ). ( 24
)
Thus, at each new generation we refresh the population with an approximated optimum in the hope that it falls near to the real one, or at least it replaces the worst individual of the population.

Comparison of results

In order to test our approach we chose three test functions (25) from a standard test suite for Evolutionary Algorithms [START_REF] Whitley | Evaluating evolutionary algorithms[END_REF]. The first function, Rotated Ellipsoid f 1 , is a true quadratic non separable optimization problem. The next two functions, Rastrigin's f 2 and Ackley's f 3 , are an example of highly multimodal functions. They contain millions of local optima in the interval of consideration.

f 1 (X) = 20 i=1   i j=1 x j   2 f 2 (X) = 20 i=1 [x 2 i -10cos(2πx i ) + 10] f 3 (X) = -20 exp   -0.2 1 30 30 i=1 x 2 i   - -exp 1 30 30 i=1 cos(2πx i ) + 20 + exp (25)
The simulation of the algorithms have been made in the MATLAB environment with using of LS-SVMlab Toolbox [START_REF] Pelckmans | LS-SVMlab Toolbox User's Guide[END_REF].

We fixed the control parameters of DE, the same for all functions : N P = 100 and F = 0.5. The constant of recombination Cr = 0 (there is no recombination) in order to make the DE algorithm rotationally invariant [START_REF] Salomon | Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions : A survey of some theoretical and practical aspects of genetic algorithms[END_REF][START_REF] Price | New Ideas in Optimization, Part 2 : Differential Evolution[END_REF]. The maximal number of generations g max is selected for each function separately in order to provide a good visual illustration of the convergence. n = N P -the depth of approximation. The average results of 10 runs are summarized in the table 1. The convergence dynamics of these test functions is shown on the figures 2-4.

As we can see such hybridization gives positive results, the algorithm converges much more quickly. But it is also clear that it consume much more time now. So the next question arise : is the algorithm really effective ? May be during Nevertheless, as may be seen from the table 2, the hybrid DE algorithm converges better. Thus, after these comparisons we can confirm that such hybridization is quite promising.

f i D g max η

Remarks

However, in spite of the demonstrated potency of our approach its efficiency of approximation is far from ideal. To estimate it a efficiency measure η have been introduced. η evaluates the percentage of successful approximation, i.e. when the approximated optimum replaces the worst individual.

The average efficiency values is roughly 20%. In others words only 1/5 of iterations with LS-SVM is effective. Moreover, these are the first iterations. So, the rest of iterations do not need such hybridization. It is only loss of computational time.

As the analyse shows this problem is caused by numerical inaccuracies during solving the system (21). When the cost function approaches to its optimum (zero in our case) this numerical effect appears.

We are looking for other methods in order to improve the optimum approximation as well as the numerical solving of our systems.

As an example a very simple approximation could be proposed. Let calculate, for instance, a barycenter of n best individuals.

X * = 1 n n i=1 Xi ( 26
)
In comparison with LS-SVM method there are several advantages : -no numerical peculiarities ; -no inferior limits on n : 2 ≤ n ≤ N P ; -very fast ; -more efficient : η 70%.

On the other side, its convergence is not as rapid as in the case of LS-SVM's one, but it remains faster than in the classical DE.

To confirm it numerically 10 runs have also been made. The depth of approximation n = 10 have been fixed. The results are summarized in the table 3. The convergence dynamics is illustrated on the figures 5-7. It is clear that such a simple idea already increases the convergence rate.

Conclusion

Hybridization of an iterative populationbased stochastic heuristics with approximation techniques presents a rather promising trend. The main idea consists in finding the best solution(s) on basis of selected potentially good individuals, which replace the worth one(s). Such iterative refreshment of population leads to increasing of algorithm convergence. By the example of Differential Evolution an obvious convergence amelioration have been established. Further work is necessary in order to improve numerical performances of our method.

Fig. 1 -

 1 Fig. 1 -DE's hybridization with LS-SVM.

  Tab. 2 -Comparison of DE * and DE h , the algorithm time is fixed.

Fig. 2 -

 2 Fig. 2 -Rotated Ellipsoid function.

Fig. 3 -

 3 Fig. 3 -Rastrigin's function.

Fig. 4 -

 4 Fig. 4 -Ackley's function.

  Tab. 3 -Comparison of the classical DE and the barycenter approximation DE b approaches.

Fig. 5 -

 5 Fig. 5 -Example of barycenter approximation, Rotated Ellipsoid function.

Fig. 6 -

 6 Fig. 6 -Example of barycenter approximation, Rastrigin's function.

Fig. 7 -

 7 Fig. 7 -Example of barycenter approximation, Ackley's function.

  , % Tab. 1 -Comparison of DE and DE h approaches, the number of generations is fixed. D -dimension of test function. η -efficiency of approximation. DE and DE h -the optimal values of the cost (test) function for classical and hybrid (LS-SVM) scheme accordingly.this time the classical DE could arrive at better, more optimal value ? To answer on this question we increased the maximal number of generations g * max in the classical DE so, that the algorithms work roughly the same time in both cases t DE * t DE h . The table 2 summarizes the obtained results.

	DE	DE h
	1 20 100 22.1 1.070e+2	4.246e-4
	2 20 300 11.6 1.170e+2 2.618e+1
	3 30 100 18.8 7.713e+0	1.019e-1