Mahadi Ddamulira
email: mddamulira@tugraz.at

ON THE x-COORDINATES OF PELL EQUATIONS THAT ARE PRODUCTS OF TWO PADOVAN NUMBERS

Keywords: 2010 Mathematics Subject Classification. 11B39, 11D45, 11D61, 11J86 Padovan numbers, Pell equations, Linear forms in logarithms, Reduction method

Let {P n } n≥0 be the sequence of Padovan numbers defined by P 0 = 0, P 1 = P 2 = 1, and P n+3 = P n+1 + P n for all n ≥ 0. In this paper, we find all positive square-free integers d ≥ 2 such that the Pell equations x 2 -dy 2 = , where ∈ {±1, ±4}, have at least two positive integer solutions (x, y) and (x , y ) such that each of x and x is a product of two Padovan numbers.

Introduction

Let {P n } n≥0 be the sequence of Padovan numbers given by P 0 = 0, P 1 = 1, P 2 = 1, and P n+3 = P n+1 + P n for all n ≥ 0. This is sequence A000931 on the On-Line Encyclopedia of Integer Sequences (OEIS) [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]. The first few terms of this sequence are {P n } n≥0 = {0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, . . .}.

In this paper, we let U := {P n P m : n ≥ m ≥ 0} be the sequence of products of two Padovan numbers. The first few members of U are U = {0, 1, 2, 3, 4, [START_REF] Cohen | Number Theory. Volume I: Tools and Diophantine Equations[END_REF][START_REF] Ddamulira | On the x-coordinates of Pell equations as sums of two Padovan numbers[END_REF][START_REF] Ddamulira | On the x-coordinates of Pell equations that are products of two Lucas numbers[END_REF][START_REF] Ddamulira | On the x-coordinates of Pell equations which are k-generalized Fibonacci numbers[END_REF][START_REF] Ddamulira | The x-coordinates of Pell equations and sums of two Fibonacci numbers II[END_REF][START_REF] Dossavi-Yovo | On the X-coordinates of Pell equations which are rep-digits[END_REF][START_REF] Faye | On the X-coordinates of Pell equations which are repdigits[END_REF][START_REF] Kafle | On the x-coordinates of Pell equations which are products of two Fibonacci numbers[END_REF][START_REF] Kafle | On the x-coordinates of Pell equations which are Fibonacci numbers II[END_REF][START_REF] Kafle | x-Coordinates of Pell equations which are Tribonacci numbers II[END_REF][START_REF] Luca | On the x-coordinates of Pell equations which are Tribonacci numbers[END_REF][START_REF] Matveev | An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers II[END_REF][START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF]24,25,27,28,32,35,36,37,42,45, . . .}.

Let d ≥ 2 be a positive integer which is not a square. It is well known that the Pell equations

x 2 -dy 2 = , (1.1)
where ∈ {±1, ±4}, have infinitely many positive integer solutions (x, y). By putting (x 1 , y 1 ) for the smallest positive solution to (1.1), all solutions are of the form (x k , y k ) for some positive integer k, where

x k + y k √ d = (x 1 + y 1 √ d) k
for all k ≥ 1, and = ±1 and

x k + y k √ d 2 = x 1 + y 1 √ d 2 k
for all k ≥ 1, and = ±4.

Furthermore, the sequence {x k } k≥1 in both cases ∈ {±1, ±4} is binary recurrent. In fact, the following formulas

x k = (x 1 + y 1 √ d) k + (x 1 -y 1 √ d) k 2
, for = ±1, and

x k = x 1 + y 1 √ d 2 k + x 1 -y 1 √ d 2 k , for = ±4,
hold for all positive integers k.

Recently, Kafle et al. [START_REF] Kafle | On the x-coordinates of Pell equations which are products of two Fibonacci numbers[END_REF] studied the Diophantine equation

x l = F m F n , (1.2)
where x l are the x-coordinates of the solutions of the Pell equation (1.1) (in the case = ±1) for some positive integer l and {F n } n≥0 is the sequence of Fibonacci numbers given by F 0 = 0, F 1 = 1, and F n+2 = F n+1 + F n for all n ≥ 0. They proved that for each square free integer d ≥ 2, there is at most one positive integer l such that x l admits the representation (1.2) for some nonnegative integers 0 ≤ m ≤ n, except for d ∈ {2, 3, 5}. Furthermore, they explicitly stated all the solutions for these exceptional cases.

In the same spirit, Rihane et al. [START_REF] Rihane | The x-coordinates of Pell equations and Padovan numbers[END_REF] studied the Diophantine equation

x n = P m , (1.3)
where x n are the x-coordinates of the solutions of the Pell equations (1.1), for some positive integers n and {P m } m≥0 is the sequence of Padovan numbers. They proved that for each square free integer d ≥ 2, there is at most one positive integer x participating in the Pell equations (1.1), that is a Padovan number with a few exceptions of d that can be effectively computed. Furthermore, the exceptional cases in (1.3) were d ∈ {2, 3, 5, 6} (for the case = ±1) and d ∈ {5} (for the case = ±4). Several other related problems have been studied where x l belongs to some interesting positive integer sequences. For example, see [START_REF] Bravo | X-coordinates of Pell equations as sums of two Tribonacci numbers[END_REF][START_REF] Bravo | Correction to: X-coordinates of Pell equations as sums of two Tribonacci numbers[END_REF][START_REF] Ddamulira | On the x-coordinates of Pell equations as sums of two Padovan numbers[END_REF][START_REF] Ddamulira | On the x-coordinates of Pell equations that are products of two Lucas numbers[END_REF][START_REF] Ddamulira | On the x-coordinates of Pell equations which are k-generalized Fibonacci numbers[END_REF][START_REF] Ddamulira | The x-coordinates of Pell equations and sums of two Fibonacci numbers II[END_REF][START_REF] Dossavi-Yovo | On the X-coordinates of Pell equations which are rep-digits[END_REF][START_REF] Faye | On the X-coordinates of Pell equations which are repdigits[END_REF][START_REF] Kafle | On the x-coordinates of Pell equations which are Fibonacci numbers II[END_REF][START_REF] Kafle | x-Coordinates of Pell equations which are Tribonacci numbers II[END_REF][START_REF] Kafle | X-coordinates of Pell equations which are Lucas numbers[END_REF][START_REF] Luca | On the x-coordinates of Pell equations which are Tribonacci numbers[END_REF][START_REF] Luca | On the x-coordinates of Pell equations which are Fibonacci numbers[END_REF].

Main Results

In this paper, we study a problem related to that of Kafle et al. [START_REF] Kafle | On the x-coordinates of Pell equations which are products of two Fibonacci numbers[END_REF] but with the Padovan sequence instead of the Fibonacci sequence. We also extend the results from the Pell equation (1.1) in the case = ±1 to the case = ±4. In both cases we find that there are only finitely many solutions that we effectively compute.

Since P 1 = P 2 = P 3 = 1, we discard the situations when n = 1 and n = 2 and just count the solutions for n = 3. Similarly, P 4 = P 5 = 2, we discard the situation when n = 4 and just count the solutions for n = 5. The main aim of this paper is to prove the following results.

Theorem 2.1. For each integer d ≥ 2 which is square-free, there is at most one positive integer k such that

x k ∈ U with = ±1, except when d ∈ {3, 6} in the +1 case and d ∈ {2, 5} in the -1 case.
Theorem 2.2. For each integer d ≥ 2 which is square-free, there is at most one positive integer k such that

x k ∈ U with = ±4,
except when d ∈ {3, 5, 6, 77} in the +4 case and d ∈ {2, 5, 13, 29, 65, 257} in the -4 case.

For the exceptional values of d listed in Theorem 2.1 and Theorem 2.2, all solutions (k, n, m) are listed at the end of the proof of each result. The main tools used in this paper are the lower bounds for linear forms in logarithms of algebraic numbers and the Baker-Davenport reduction procedure, as well as the elementary properties of Padovan numbers and solutions to Pell equations. Computations are done with the help of a computer program in Mathematica.

Preliminary Results

3.1.

The Padovan sequence. Here, we recall some important properties of the Padovan sequence {P n } n≥0 . The characteristic equation

x 3 -x -1 = 0, has roots α, β, γ = β, where α = r 1 + r 2 6 , β = -(r 1 + r 2 ) + √ -3(r 1 -r 2 ) 12 , (3.1)
and

r 1 = 3 108 + 12 √ 69 and r 2 = 3 108 -12 √ 69. (3.2)
Furthermore, the Binet formula is given by

P n = aα n + bβ n + cγ n for all n ≥ 0, (3.3)
where

a = (1 -β)(1 -γ) (α -β)(α -γ) , b = (1 -α)(1 -γ) (β -α)(β -γ) , c = (1 -α)(1 -β) (γ -α)(γ -β) = b. (3.4)
Numerically, the following estimates hold: From (3.1), (3.2), and (3.5), it is easy to see that the contribution the complex conjugate roots β and γ, to the right-hand side of equation (3.3), is very small. In particular, setting e(n)

1.32 < α < 1.33, 0.86 < |β| = |γ| = α -1 2 < 0.
:= P n -aα n = bβ n + cγ n , we have |e(n)| < 1 α n/2 , (3.6)
holds for all n ≥ 1. Furthermore, by induction, one can prove that α n-2 ≤ P n ≤ α n-1 holds for all n ≥ 4.

(3.7)

3.2. Linear forms in logarithms. Let η be an algebraic number of degree d with minimal primitive polynomial over the integers

a 0 x d + a 1 x d-1 + • • • + a d = a 0 d i=1 (x -η (i) ),
where the leading coefficient a 0 is positive and the η (i) 's are the conjugates of η. Then the logarithmic height of η is given by

h(η) := 1 d log a 0 + d i=1 log max{|η (i) |, 1} .
In particular, if η = p/q is a rational number with gcd(p, q) = 1 and q > 0, then h(η) = log max{|p|, q}. The following are some of the properties of the logarithmic height function h(•), which will be used in the next sections of this paper without a reference:

h(η 1 ± η 2 ) ≤ h(η) + h(η 1 ) + log 2, h(η 1 η ±1 2 ) ≤ h(η 1 ) + h(η 2 ), h(η s ) = |s|h(η) (s ∈ Z). (3.8)
Here, we recall the result of Bugeaud, Mignotte, and Siksek ( [START_REF] Bugeaud | Classical and modular approaches to exponential Diophantine equations I. Fibonacci and Lucas perfect powers[END_REF], Theorem 9.4, pp. 989), which is a modified version of the result of Matveev [START_REF] Matveev | An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers II[END_REF]. This result is one of our main tools in this paper. Theorem 3.1 (Matveev according to Bugeaud, Mignotte, Siksek). Let η 1 , . . . , η t be positive real algebraic numbers in a real algebraic number field K ⊂ R of degree D, b 1 , . . . , b t be nonzero integers, and assume that

Λ := η b 1 1 • • • η bt t -1, is nonzero. Then log |Λ| > -1.4 × 30 t+3 × t 4.5 × D 2 (1 + log D)(1 + log B)A 1 • • • A t , where B ≥ max{|b 1 |, . . . , |b t |}, and
A i ≥ max{Dh(η i ), | log η i |, 0.16}, for all i = 1, . . . , t.
3.3. Reduction procedure. During the calculations, we get upper bounds on our variables which are too large, thus we need to reduce them. To do so, we use some results from the theory of continued fractions.

For the treatment of linear forms homogeneous in two integer variables, we use the well-known classical result in the theory of Diophantine approximation. It is called the Legendre criterion. Lemma 3.1 (Legendre). Let τ be an irrational number, p 0 q 0 , p 1 q 1 , p 2 q 2 , . . . be all the convergents of the continued fraction of τ and M be a positive integer. Let N be a nonnegative integer such that q N > M . Then putting a(M ) := max{a i : i = 0, 1, 2, . . . , N }, the inequality

τ - r s > 1 (a(M ) + 2)s 2 ,
holds for all pairs (r, s) of positive integers with 0 < s < M .

For a nonhomogeneous linear form in two integer variables, we use a slight variation of a result due to Dujella and Pethő (see [START_REF] Dujella | A generalization of a theorem of Baker and Davenport[END_REF], Lemma 5a). For a real number X, we write ||X|| := min{|X -n| : n ∈ Z} for the distance from X to the nearest integer. Lemma 3.2 (Dujella, Pethő). Let M be a positive integer, p q be a convergent of the continued fraction of the irrational number τ such that q > 6M , and A, B, µ be some real numbers with A > 0 and B > 1. Furthermore, let ε := ||µq|| -M ||τ q||. If ε > 0, then there is no solution to the inequality 0 < |uτ -v + µ| < AB -w , in positive integers u, v, and w with u ≤ M and w ≥ log(Aq/ε) log B .

At various occasions, we need to find a lower bound for linear forms in logarithms with bounded integer coefficients in three variables. In this case we use the LLL algorithm that we describe below. Let τ 1 , τ 2 , . . . τ t ∈ R and the linear form

x 1 τ 1 + x 2 τ 2 + • • • + x t τ t with |x i | ≤ X i .
We put X := max{X i }, C > (tX) t and consider the integer lattice Ω generated by

b j := e j + Cτ j for 1 ≤ j ≤ t -1 and b t := Cτ t e t ,
where C is a sufficiently large positive constant.

Lemma 3.3 (LLL algortthm). Let X 1 , X 2 , . . . , X t be positive integers such that X := max{X i } and C > (tX) t be a fixed sufficiently large constant. With the above notation on the lattice Ω, we consider a reduced base {b i } to Ω and its associated Gram-Schmidt orthogonalization base {b * i }. We set

c 1 := max 1≤i≤t ||b 1 || ||b * i || , θ := ||b 1 || c 1 , Q := t-1 i=1 X 2 i , and R := 1 2 1 + t i=1 X i . If the integers x i are such that |x i | ≤ X i , for 1 ≤ i ≤ t and θ 2 ≥ Q + R 2 , then we have t i=1 x i τ i ≥ θ 2 -Q -R C .
For the proof and further details, we refer the reader to the book of Cohen, (Proposition 2.3.20 in [START_REF] Cohen | Number Theory. Volume I: Tools and Diophantine Equations[END_REF], pp. 58-63). Finally, the following Lemma is also useful. It is Lemma 7 in [START_REF] Sánchez | Linear combinations of factorials and s-units in a binary recurrence sequence[END_REF].

Lemma 3.4 (Gúzman Sánchez, Luca). Let H, L, and r be real numbers. If r ≥ 1, H > (4r 2 ) r , and H > L/(log L) r , then

L < 2 r H(log H) r .

Proof of Theorem 2.1

Let (x 1 , y 1 ) be the smallest positive integer solution to the Pell quation (1.1) in the case = ±1. We Put

δ := x 1 + y 1 √ d and σ := x 1 -y 1 √ d. (4.1)
From which we get that

δ • σ = x 2 1 -dy 2 1 =: , where ∈ {±1}. (4.2)
Then

x k = 1 2 (δ k + σ k ). (4.3) Since δ ≥ 1 + √ 2 > α 2 , it follows that the estimate δ k α 2 ≤ x k ≤ δ k α holds for all k ≥ 1. (4.4)
We assume that (k 1 , n 1 , m 1 ) and (k 2 , n 2 , m 2 ) are triples of integers such that

x k 1 = P n 1 P m 1 and x k 2 = P n 2 P m 2 (4.5)
We asuume that 1 ≤ k 1 < k 2 . We also assume that 3 ≤ m i < n i for i = 1, 2. We set (k, n, m) := (k i , n i , m i ), for i = 1, 2. Using the inequalities (3.7) and (4.4), we get from (4.5) that

δ k α 2 ≤ x k = P n P m ≤ α n+m-2 and α n+m-4 ≤ P n P m = x k ≤ δ k α . (4.6)
The above inequalities give

k log δ < (n + m) log α < k log δ + 3 log α.
Dividing through by log α and setting c 2 := 1/ log α, we get that

kc 2 log δ < n + m < kc 2 log δ + 3, (4.7)
and since α 3 > 2, we get

|n + m -c 2 k log δ| < 3. (4.8)
To fix ideas, we assume that

n ≥ m and k 1 < k 2 .
We also put

m 3 := min{m 1 , m 2 }, m 4 := max{m 1 , m 2 }, n 3 := min{n 1 , n 2 }, n 4 := max{n 1 , n 2 }.
Inequality (4.7) together with the fact that δ > α 2 ( so, c 2 log δ > 2), tells us that

2k 2 < c 2 k 2 log δ < 2n 2 ≤ 2n 4 , so k 1 < k 2 < n 4 . (4.9)
Besides, given that k 1 < k 2 , we have by (3.7) and (4.5) that

α n 1 -2 ≤ P n 1 ≤ P n 1 P m 1 = x k 1 < x k 2 = P n 2 P m 2 ≤ P 2 n 2 < α 2n 2 -2
. Thus, we get that

n 1 < 2n 2 .
(4.10)

4.1. An inequality for m, n, and k. Using the equations (3.3), (4.3), and (4.5), we get

1 2 (δ k + σ k ) = P n P m = (aα n + e(n))(aα m + e(m)) So, 1 2 δ k -a 2 α n+m = - 1 2 σ k + a(e(m)α n + e(n)α m ) + e(n)e(m),
and by (3.6), we have

δ k (2a 2 ) -1 α -(n+m) -1 ≤ 1 2δ k a 2 α n+m + |e(m)α n + e(n)α m | aα n+m + |e(n)e(m)| a 2 α n+m ≤ 1 2δ k a 2 α n+m + α n/2 + α m/2 aα n+m + 1 a 2 α 3(n+m)/2 ≤ 1 a 2 α (n+m)/2 1 2δ k α (n+m)/2 + a + 1 α n+m < 2 α (n+m)/2
. Thus, we have

δ k (2a 2 ) -1 α -(n+m) -1 < 2 α (n+m)/2 . (4.11) Put Λ 1 := δ k (2a 2 ) -1 α -(n+m) -1 and Γ 1 := k log δ -log(2a 2 ) -(n + m) log α.
We assume that n + m ≥ 10.

|Λ 1 | = |e Γ 1 -1| < 1 2
for n + m ≥ 10 (because 2/α 5 < 1/2), since the inequality |y| < 2|e y -1| holds for all y ∈ -1 2 , 1 2 , it follows that e |Γ 1 | < 2 and so

|Γ 1 | < e |Γ 1 | |e Γ 1 -1| < 4 α (n+m)/2 .
Thus, we get that

k log δ -log(2a 2 ) -(n + m) log α < 4 α (n+m)/2 .
(4.12)

We apply Theorem 3.1 on the left-hand side of (4.11) with the data:

t := 3, η 1 := δ, η 2 := 2a 2 , η 3 := α, b 1 := k, b 2 := -1, b 3 := -(n + m).
Furthermore, we take the number field K := Q( √ d, α) which has degree D := 6. Since max{1, k, n+ m} ≤ 2n, we take B := 2n. First, we note that the left-hand side of (4.11) is non-zero, since otherwise,

δ k = 2a 2 α n+m .
The left-hand side belongs to the quadratic field Q( √ d), while the right-hand side belongs to the cubic field Q(α). These fields only intersect when both sides are rational numbers. Since δ k is a positive algebraic integer and a unit, we get that to δ k = 1. Hence, k = 0, which is a contradiction. Thus, Λ 1 = 0. Now, we can apply Theorem 3.1.

We have h(η 1 ) = h(δ) = 1 2 log δ and h(η 3 ) = h(α) = 1 3 log α. Further,

a = α(α + 1) 3α 2 -1 ,
the mimimal polynomial of 2a 2 is 529x 3 -506x 2 -40x -8 and has roots 2a 2 , 2b 2 , 2c 2 . Since 2|b| 2 = 2|c| 2 < 1 (by (3.5)), then

h(η 2 ) = h(2a 2 ) = 1 3 (log 529 + log(2a 2 )).
Thus, we can take , We now return to the equation x k = P n P m and rewrite it as

A 1 := 3 log δ, A 2 := 2(log 529 + log(2a 2 )), A 3 := 2 log α. Now, Theorem 3.1 tells us that log |Λ 1 | > -1.4 × 30 6 × 3 4.5 × 6 2 (1 + log 6)(1 + log(2n))(3 log δ) ×(2(log 529 + log(2a 2 ))(2 log α) > -1.
1 2 δ k -aP m α n = - 1 2 σ k + e(n)P m ,
we obtain

δ k (2aP m ) -1 α -n -1 ≤ 1 aα n 1 + 1 δ k α n < 8 α n . (4.15) Put Λ 2 := δ k (2aP m ) -1 α -n -1, Γ 2 := k log δ -log(2aP m ) -n log α.
We assume for technical reasons that n ≥ 10. So |e Λ 2 -1| < 1 2 . It follows that

|k log δ -log(2aP m ) -n log α| = |Γ 2 | < e |Λ 2 | |e Λ 2 -1| < 16 α n . (4.16)
Furthermore, Λ 2 = 0 (so Γ 2 = 0), since δ k ∈ Q(α) by the previous argument. We now apply Theorem 3.1 to the left-hand side of (4.15) with the data

t := 3, η 1 := δ, η 2 := 2aP m , η 3 := α, b 1 := k, b 2 := -1, b 3 := -n. Since 2a = 2α(α + 1) 3α 2 -1 ,
has minimum polynomial 23x This was obtained under the assumption that n ≥ 10, but if n < 10, then the inequality also holds as well.

We record what we have proved so far. 4.2. Absolute bounds. We recall that (k, n, m) = (k i , n i , m i ), where 3 ≤ m i < n i , for i = 1, 2 and 1 ≤ k 1 < k 2 . Further, n i ≥ 4 for i = 1, 2. We return to (4.12) and rewrite

Γ (i) 1 := k i log δ -log(2a 2 ) -(n i + m i ) log α < 4 α (n i +m i )/2 , for i = 1, 2.
We do a suitable cross product between Γ

(1) 1 , Γ (2)
1 and k 1 , k 2 to eliminate the term involving log δ in the above linear forms in logarithms:

|Γ 3 | : = |(k 1 -k 2 ) log(2a 2 ) + (k 1 (n 2 + m 2 ) -k 2 (n 1 + m 1 )) log α| = |k 2 Γ (1) 1 -k 1 Γ (2) 1 | ≤ k 2 |Γ (1) 1 | + k 1 |Γ (2) 1 | ≤ 4k 2 α (n 1 +m 1 )/2 + 4k 1 α (n 2 +m 2 )/2 ≤ 8n 4 α λ , (4.18)
where λ := min

1≤i≤2 n i + m i 2 .
We need to find an upper bound for λ. If 8n 4 /α λ > 1/2, we then get

λ < log(16n 4 ) log α < 4 log(16n 4 ). (4.19) Otherwise, |Γ 3 | < 1 2 . So, e Γ 3 -1 = (2a 2 ) k 1 -k 2 α k 1 (n 2 +m 2 )-k 2 (n 1 +m 1 ) -1 < 2|Γ 3 | < 16n 4 α λ . (4.20)
We apply Theorem 3.1 with the data:

t := 2, η 1 := 2a 2 , η 2 := α, b 1 := k 1 -k 2 , b 2 := k 1 (n 2 + m 2 ) -k 2 (n 1 + m 1 ).
We take the number field K := Q(α) and D := 3. We begin by checking that e Γ 3 -1 = 0 (so Γ 3 = 0). This is true because α and 2a 2 are multiplicatively independent, since α is a unit in the ring of integers Q(α) while the norm of 2a 2 is 8/529. We note that |k 1 -k 2 | < k 2 < n 4 . Further, from (4.18), we have

|k 2 (n 1 + m 1 ) -k 1 (n 2 + m 1 )| < (k 2 -k 1 ) | log(2a 2 )| log α + 4k 2 α m 3 log α < 25k 2 < 25n 4
given that m 3 ≥ 1. So, we can take B := 25n 4 . By Theorem 3.1, with the same A 1 := log 529 + log(2a 2 ) and A 2 := log α, we have that log |e Γ 3 -1| > -5.5 × 10 11 (log n 4 )(log α). We set {i, j} = {1, 2} and return to (4.12) to replace (k, n, m) = (k i , n i , m i ):

By comparing this

|Γ (i) 1 | = k i log δ -log(2a 2 ) -(n i + m i ) log α < 4 α (n i +m i )/2 , (4.22)
and also return to (4.16), replacing with (k, n, m) = (k j , n j , m j ):

|Γ (j) 2 | = k j log δ -log(2aP m j ) -n j log α < 16 α n j . (4.23)
We perform a cross product on (4.22) and (4.23) in order to eliminate the term on log δ:

|Γ 4 | := k j log(2a 2 ) -k i log(2aP m j ) + (k i n j -k j (n i + m i )) log α ≤ |(k j -k i ) log(2a) + (k j (n i + m i + 1) -k i (n j + m j -1)) log α| ≤ k i Γ (j) 2 -k j Γ (i) 1 ≤ k i Γ (j) 2 + k j Γ (i) 1 < 16k i α n j + 4k j α (n i +m i )/2 < 20n 4 α ν , (4.24)
where ν := min 1≤i,j≤2

n i + m i 2 , n j .
As before, we need to find an upper bound on ν. If 20n In order to apply Theorem 3.1, first we check if e Γ 4 = 1, we obtain

(2a) k i -k j = α k j (n i +m i +1)-k i (n j +m j -1) .
Since α is a unit, the right-hand side in above is an algebraic integer. This is a contradiction because k 1 < k 2 so k i -k j = 0, and neither (2a) nor (2a) -1 are algebraic intgers. Hence e Γ 4 = 1. By assuming that ν ≥ 100, we apply Theorem 3.1 with the data: t := 2,

η 1 := 2a, η 2 := α, b 1 := k j -k i , b 2 := k j (n i + m i + 1) -k i (n j + m j -1),
and the inequalities (4.21) and (4.26). We get

ν := min 1≤i,j≤2 n i + m i 2 , n j < 7.2 × 10 14 λ log n 4 < 4.1 × 10 25 (log n 4 ) 2 .
The above inequality also holds when ν < 100. Further, it also holds when the inequality (4.25) holds. So the above inequality holds in all cases. Note that the case {i, j} = {2, 1} leads to n 1 < 2n 2 ≤ 2n 4 whereas {i, j} = {1, 2} lead to ν = min{(n 1 + m 1 )/2, n 2 }. Hence, either the minimum is (n 1 + m 1 )/2, so We record what we have proved.

n 1 ≤ n 1 + m 1 2 < 1.
Lemma 4.2. Let (k i , n i , m i ) be a solution to

x k i = P n i P m i , with 3 ≤ m i < n i for i ∈ {1, 2} and 1 ≤ k 1 < k 2 , then max{k 1 , m 1 } < n 1 < 10 30 and max{k 2 , m 2 } < n 2 < 10 96 .

5.

Reducing the bounds for n 1 and n 2

In this section, we reduce the upper bounds for n 1 and n 2 given in Lemma 4.2 reasonably enough so that these can be treated computationally. For this, we return to the inequalities for Γ 3 , Γ 4 , and Γ 5 .

5.1. The first reduction. We divide both sides of the inequality (4.18) by (k 2 -k 1 ) log α. We get that

log(2a 2 ) log α - k 2 (n 1 + m 1 ) -k 1 (n 2 + m 2 ) k 2 -k 1 < 8n 2 α λ (k 2 -k 1 ) log α . (5.1)
We assume that λ ≥ 10. Below we apply Lemma 3.1. We put τ := log(2a 2 ) log α is irrational. We compute its continued fraction expansion [a 0 , a 1 , a 2 , . . .] = [1, 23, 3, 2, 1, 1, 2, 1, 2, 3, 1, 1, 8, 1, 1, 3, 1, 2, 3, 7, 5, 48, 2, 3, 1, 2, 18, . . .] and its convergents

p 0 q 0 , p 1 q 1 , p 2 q 2 , . . . =
q 182 > M > n 2 > k 2 -k 1 and a(M ) := max{a i : 0 ≤ i ≤ 182} = a 144 = 204.
Thus, by Lemma 3.1, we have that

τ - k 2 (n 1 + m 1 ) -k 1 (n 2 + m 2 ) k 2 -k 1 > 1 206(k 2 -k 1 ) 2 .
(5.2)

Hence, combining the inequalities (5.1) and (5.2), we obtain 10 194 , so λ ≤ 1573. This was obtained under the assumption that λ ≥ 10, Otherwise, λ < 10 < 1573 holds as well. Now, for each

α λ < 722n 2 (k 2 -k 1 ) < 7.22 ×
m j ≤ n i + m i 2 = λ ∈ [1, 1573] we estimate a lower bound |Γ 4 |, with |Γ 4 | := k j log(2a 2 ) -k i log(2aP m j ) + (k i n j -k j (n i + m i )) log α (5.3)
given in the inequality (4.24), via the procedure described in Subsection 3.3 (LLL algorithm). We recall that Γ 4 = 0. We apply Lemma 3.3 with the data:

t := 3, τ 1 := log(2a 2 ), τ 2 := log(2aP m j ), τ 3 := log α, x 1 := k j , x 2 := -k i , x 3 := k i n j -k j (n i + m i ).
We set X := 25 × 10 96 as an upper bound to |x i | < 25n 2 for all i = 1, 2, 3, and C := (5X) An application of Lemma 3.4 with the data r = 2, H := 5.42 × 10 35 , and L := n 2 , gives that n 2 < 1.5 × 10 40 . We note that the upper bound for n 2 represents a very good reduction of the bound given in Lemma 4.2. Hence, it is expected that if we start our reduction cycle with the new bound on n 2 , then we even get a better bound on n 1 . Indeed, returning to (5.1), we take M := 1.5 × 10 40 and computationally verify that q 77 > M > n 2 > k 2 -k 1 and a(M ) := max{a i : 0 ≤ i ≤ 77} = a 13 = 149, from which it follows that λ ≤ 666. We now return to (5.3), where putting X := 3.75 × 10 41 and C := (5X) 5 , we apply the LLL algorithm to λ ∈ [START_REF] Baker | Logarithmic forms and Diophantine geometry[END_REF]666]. In this case we get that

x k = 1 2 (δ k + σ k ) = 1 2 x 1 + y 1 √ d k + x 1 -y 1 √ d k = 1 2 x 1 + x 2 1 ∓ 1 k + x 1 -x 2 1 ∓ 1 k := Q ± k (x 1 ).
Thus, we return to the Diophantine equation x k 1 = P n 1 P m 1 and consider the equations

Q + k 1 (x 1 ) = P n 1 P m 1 and Q - k 1 (x 1 ) = P n 1 P m 1 , (5.4)
with

k 1 ∈ [1, 1487], m 1 ∈ [3, 1487],
and

n 1 ∈ [m 1 + 1, 1487].
Besides the trivial case k 1 = 1, with the help of a computer search in Mathematica on the above equations in (5.4), we list the only nontrivial solutions in Table 1.

Q + k 1 (x 1 ) k 1 x 1 y 1 d δ 2 2 1 3 2 + √ 3 2 5 2 6 5 + 2 √ 6 2 23 4 33 23 + 4 √ 33 Q - k 1 (x 1 ) k 1 x 1 y 1 d δ 2 1 1 2 1 + √ 2 2 2 1 5 2 + √ 5 Table 1. Solutions to Q ± k 1 (x 1 ) = P n 1 P m 1
From the above tables, we set each δ := δ t for t = 1, 2, . . . 5. We then work on the linear forms in logarithms Γ 1 and Γ 2 , in order to reduce the bound on n 2 given in Lemma 5.1. From the inequality (4.12), for (k, n, m) := (k 2 , n 2 , m 2 ), we write

k 2 log δ t log α -(n 2 + m 2 ) + log(2a 2 ) log(α -1 ) < 4 log α α -(n 2 +m 2 )/2 , (5.5)
for t = 1, 2, . . . 5. We put

τ t := log δ t log α , µ t := log(2a 2 ) log(α -1 )
, and (A t , B t ) := 4 log α , α .

We note that τ t is transcendental by the Gelfond-Schneider's Theorem (See [START_REF] Baker | Logarithmic forms and Diophantine geometry[END_REF], Theorem 2.1, pp. 25). Thus, τ t is irrational. We can rewrite the above inequality, 5.5 as

0 < |k 2 τ t -(n 2 + m 2 ) + µ t | < A t B -(n 2 +m 2 )/2 t
, for t = 1, 2, . . . , 5.

(5.6)

We take M := 1.66 × 10 35 which is the upper bound on n 2 according to Lemma 5.1 and apply Lemma 3.2 to the inequality (5.6). As before, for each τ t with t = 1, 2, . . . , 17, we compute its continued fraction [a

(t) 0 , a (t) 1 , a (t)
2 , . . .] and its convergents p

(t) 0 /q (t) 0 , p (t) 1 /q (t) 1 , p (t)
2 /q (t) 2 , . . .. For each case, by means of a computer search in Mathematica, we find an integer s t such that q (t) st > 9.96 × 10 35 = 6M and t := µ t q (t) -M τ t q (t) > 0.

We finally compute all the values of b t := log(A t q (t) We take t,m 2 := ||µ t q (t,m 2 ) || -M ||τ t q (t,m 2 ) || > 0, and b t = b t,m 2 := log(A t q (t,m 2 ) st / t,m 2 )/ log B t .

st / t )/
With the help of Mathematica, we obtain the results in Table 3. Thus, max{b t,n 2 -m 2 : t = 1, 2, . . . , 5 and m 2 = 1, 2, . . . b t } ≤ 351. Thus, by Lemma 3.2, we have that n 2 ≤ 351, for all t = 1, 2, . . . , 5, and by the inequality (4.10) we have that n 1 ≤ 2n 2 . From the fact that δ k ≤ α n+m , we can conclude that k 1 < k 2 ≤ 194. Collecting everything together, our problem is reduced to search for the solutions for (4.5) in the following range: After a computer search on the equation (4.5) on the above ranges, we obtained the following solutions, which are the only solutions for the exceptional d cases we have stated in Theorem 2.1.

t
1 ≤ k 1 < k 2 ≤ 194, 3 ≤ m 1 < n 1 ∈ [3,
For the +1 case:

(d = 3) x 1 = 2 = P 5 P 3 , x 2 = 7 = P 9 P 3 ; (d = 6)

x 1 = 5 = P 8 P 3 , x 2 = 49 = P 16 P 3 = P 9 P 9 .

For the -1 case:

(d = 2) x 1 = 1 = P 3 P 3 , x 2 = 3 = P 6 P 3 , x 3 = 7 = P 9 P 3 ; (d = 5)

x 1 = 2 = P 5 P 3 , x 2 = 9 = P 10 P 3 = P 6 P 6 .

This completes the proof of Theorem 2.1.

Proof of Theorem 2.2

The proof of Theorem 2.2 follows similar arguments as in the proof of Theorem 2.1. So, we do not give the details here. We leave it as an easy exersise to the reader.

Below, we give the exceptional d cases we have stated in Theorem 2.

  87, 0.72 < a < 0.73, 0.24 < |b| = |c| < 0.25.(3.5)

Lemma 4 . 1 .

 41 If x k ∈ U, then m < 1.08 × 10 15 log n log δ, k < 6.16 × 10 14 log n, n < 1.80 × 10 29 (log n) 2 (log δ) 2 .

  351], and 3 ≤ m 2 < n 2 ∈ [3, 351].

2 . 5 .

 25 For the +4 case: (d = 3) x 1 = 4 = P 7 P 3 = P 5 P 5 , x 2 = 14 = P 9 P 5 ; (d = 5) x 1 = 3 = P 6 P 3 , x 2 = 7 = P 9 P 3 , x 3 = 18 = P 10 P 5 ; (d = 6) x 1 = 10 = P 8 P 5 , x 2 = 98 = P 16 P 5 ; (d = 77) x 1 = 9 = P 1 0P 3 = P 6 P 6 , x 3 = 702 = P 23 P For the -4 case: (d = 2) x 1 = 2 = P 5 P 3 , x 2 = 6 = P 6 P 5 , x 3 = 14 = P 9 P 5 ; (d = 5) x 1 = 1 = P 3 P 3 , x 2 = 3 = P 6 P 3 , x 3 = 4 = P 7 P 3 = P 5 P 5 , x 4 = 7 = P 9 P 3 , x 6 = 18 = P 10 P 5 ; (d = 13) x 1 = 3 = P 6 P 3 , x 2 = 36 = P 11 P 6 = P 10 P 7 ; (d = 29) x 1 = 5 = P 8 P 3 , x 2 = 27 = P 10 P 6 , x 3 = 140 = P 14 P 8 ; (d = 65) x 1 = 16 = P 12 P 3 = P 7 P 7 , x 2 = 258 = P 18 P 6 ; (d = 257) x 1 = 32 = P 12 P 5 , x 2 = 1026 = P 19 P 10 .

  06 × 10 15 log n log δ.

	Comparing the above inequality with (4.11), we get

n + m 2 log α -log 4 < 1.06 × 10 15 log n log δ. Hence, we get that m ≤ n + m 2 < 1.08 × 10 15 log n log δ. (4.13) Since δ k ≤ α n+m (by (4.6)), we get that k log δ ≤ (n + m) log α, (4.14) which together with estimate (4.13) gives k < 6.16 × 10 14 log n.

  2 /α ν > 1/2, then we get

	ν <	log(40n 4 ) log α	< 4 log(40n 4 ).	(4.25)
	Otherwise, |Γ 4 | < 1/2, so we have
	e Γ 4 -1 ≤ 2|Γ 4 | <	40n 4 α ν .	(4.26)

  36 × 10 25 (log n 4 ) 2 ,

		(4.27)
	or the minimum is n j and from the inequality (4.21) we get that
	n 3 := min 1≤j≤2 {n j } < 4.1 × 10 25 (log n 4 ) 2 .	(4.28)
	By the inequality (4.7),

log δ ≤ k 1 log δ ≤ 2n 1 log α < 2.33 × 10 25 (log n 4 ) 2 .

By substituting this into Lemma 4.1, we get n 4 < 9.77 × 10 79 (log n 4 )

6

. Also, by Lemma 3.4, with the data r := 6, H := 9.77 × 10 79 , and L := n 4 , we get that n 2 ≤ n 4 < 2.44 × 10 95 . This immediately gives that n 1 ≤ n 3 < 6.56 × 10 29 and m 1 ≤ m 3 < 6.50 × 10 29 .

  < 20n 2 α -ν , with ν := min n i + m i 2 , n j which leads to ν ≤ 3043. As we have noted before, ν = n 1 (so n 1 ≤ 3043). But we also know that log δ ≤ (n 1 + m 1 ) log α ≤ 2 n 1 + m 1 2 log α < 1735. Substituting for log δ in the inequality involving n in Lemma 4.1, we get that n 2 < 5.42 × 10 35 (log n 2 ) 2 .

5

. A computer in Mathematica search allows us to conclude, together with the inequality (4.24), that

2 × 10 -280 < min 1≤λ≤1573 |Γ 4 |

2

  × 10 -142 < min 1≤λ≤666 |Γ 4 | < 20n 2 α -ν , with ν := min n i + m i 2 , n j , which implies that ν ≤ 1487. Thus n 1 ≤ 1487. Also, log δ < 848. By a similar substitution in Lemma 4.2 for log δ for the inequality involving n, we get that n 2 < 8.18 × 10 30 (log n 2 ) 2 . By Lemma 3.4, we have that n 2 < 1.66 × 10 35 , a better bound than that obtained in the previous step of the reduction cycle. We record what we have proved. Lemma 5.1. Let (k i , n i , m i ) be a solution to x k i = P n i P m i , with 3 ≤ m i < n i for i = 1, 2 and 1 ≤ k 1 < k 2 , then k 1 < m 1 < n 1 ≤ 1487 and k 2 < m 2 < n 2 ≤ 1.66 × 10 35 .

	5.2. The final reduction. Returning back to (4.1) and (4.3) and using the fact that (x 1 , y 1 ) is
	the smallest positive solution to the Pell equation (1.1), we obtain

Table 2 .

 2 log B t . The values of b t correspond to the upper bounds on m 2 ≤ n 2 + m 2 2 , for each t = 1, 2, . . . , 5, according to Lemma 3.2. The results of the computation for each t are recorded in Table 2. First reduction computation results By replacing (k, n, m) with (k 2 , n 2 , m 2 ) in the inequality (4.16), we can write

		t δ t 1 2 + 2 5 + 2 √ √ 3 6 3 23 + 4 √ 33 83 2.65107 × 10 36 0.181168 314 s t q st t > b t 81 2.32528 × 10 36 0.118103 316 67 1.11311 × 10 37 0.128740 320 4 1 + √ 2 64 1.35690 × 10 37 0.009827 330 5 2 + √ 5 79 1.35905 × 10 36 0.073971 312
		k 2	log δ t log α	-n 2 +	log(2aP m 2 ) log(α -1 )	<	16 log α	α -n 2 ,	(5.7)
	for t = 1, 2, . . . , 5.
	We now put
	τ t :=	log δ t log α	, µ t,m 2 :=	log(2aP m 2 ) log(α -1 )	, and (A t , B t ) :=	16 log α	, α .

With the above notations, we can rewrite (5.7) as

0 < |k 2 τ t -n 2 + µ t,m 2 | < A t B -n 2 t

, for t = 1, 2, . . . 5.

(5.8)

We again apply Lemma 3.2 to the above inequality (5.8), for t = 1, 2, . . . , 5, m 2 = 1, 2, . . . , b t , with M := 1.66 × 10 35 .

Table 3 .

 3 Final reduction computation results

	1	2	3	4	5
	b t,m 2 330 351 336 345 332

Acknowledgements

The author thanks for referee for the careful reading of the manuscript and the useful comments and recommendations that greatly improved the presentation of the current paper. The author was supported by the Austrian Science Fund (FWF) projects: F5510-N26 -Part of the special research program (SFB), "Quasi-Monte Carlo Methods: Theory and Applications" and W1230 -"Doctoral Program Discrete Mathematics".

This research was supported by the Austrian Science Fund (FWF) projects: F5510-N26 -Part of the special research program (SFB), "Quasi-Monte Carlo Methods: Theory and Applications" and W1230 -"Doctoral Program Discrete Mathematics".


Amaury L'huillier
email: amaury.lhuillier@loria.fr

Sylvain Castagnos
email: sylvain.castagnos@loria.fr

Anne Boyer
email: anne.boyer@loria.fr

Are Item A ributes a Good Alternative to Context Elicitation in Recommender Systems?

Keywords: Context-Aware Recommender System, Context Elicitation, User Study

Context-aware recommendation became a major topic of interest within the recommender systems community as the context is crucial to provide the right items at the right moment. Many studies aim at developing complex models to include contextual factors in the recommendation process. Despite a real improvement on the recommendations quality, such contextual factors face users' privacy and data collection issues. We support the idea that context could be expressed in term of item a ributes rather than contextual factors. To investigate that hypothesis, we designed an online experiment where 174 users were asked to describe the context in which they would listen the proposed songs for which we collected 12 musical a ributes. We make available all the material collected during this study for research purposes and non-commercial use.

INTRODUCTION

Since it has been demonstrated that recommendations quality is not only about precision relatively to users preferences, current recommendation algorithms aim at integrating human factors in the recommendation process. Among them, context which is used to provide the right recommendations at the right moment is one of the most studied factors and its bene ts no longer have to be demonstrated [START_REF] Adomavicius | Context-aware Recommender Systems[END_REF]. For example, context is crucial to recommende the right genre of music to a user in harmony with his activity or mood, or to recommend exhibits in a museum according to user's timeframe and people accompanying him.

Traditional Context-Aware Recommender Systems (CARS) collect and exploit information about the user situation (individuality, activity, location, time, and relations). Such information can be collected in several ways, by using sensors of the devices (GPS, temperature, light,. . . ) or by cross-checking information gathered from other sources (e.g. inferring the weather from the geolocalization) [START_REF] Adomavicius | Context-aware Recommender Systems[END_REF]. A system can also directly question users about their Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro t or commercial advantage and that copies bear this notice and the full citation on the rst page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). UMAP '17, July 09-12, 2017, Bratislava, Slovakia © 2017 Copyright held by the owner/author(s). 978-1-4503-4635-1/17/07. DOI: h p://dx.doi.org/10.1145/3079628.3079651 context 1 . Once contextual factors are de ned, several methods are used to exploit them as matrix factorization [START_REF] Baltrunas | Matrix Factorization Techniques for Context Aware Recommendation[END_REF], tensors [5] or graph-based approaches [START_REF] Wu | Context-Aware Recommendation via Graph-Based Contextual Modeling and Post ltering[END_REF]. Despite unquestionable bene ts in term of recommendation quality, such approaches face many issues. First, collecting such information is intrusive, some researches have demonstrated that collecting personal data becomes less and less desirable [START_REF] Faith | Hey, at's Personal! In User Modeling[END_REF] and could lead to mistrust [START_REF] Knijnenburg | Making Decisions About Privacy: Information Disclosure in Context-Aware Recommender Systems[END_REF]. Second, context is known to be a very dynamic dimension and changes of one contextual factors can lead to a completely di erent context. Such models then require a non-stop tracking to detect any change of contextual dimension in order to adapt their recommendations and this point supports the previous discussed limitation.

ird, required pieces of information are sometimes partially or non observable by the system due to technical or privacy preservation issues (as an example, users may have blocked the geolocalization on their smartphone making them obsolete). For all these reasons, we proposed in 2015 a new de nition of context based on the sol basis of consumed item a ributes [START_REF] Sylvain Castagnos | Toward a Robust Diversity-Based Model to Detect Changes of Context[END_REF]. Our model was based on a ributes diversity evolution over time and was used to isolate sequences of consultations sharing similar attributes called Implicit Context. us, context was no more de ned by user situation description but according to item a ributes values and their evolutions. Rather than nding items consumed in similar context to provide recommendations, our model could be used to extract the dimensions (a ributes) that characterize the current implicit context. Adapting recommendations to these implicit context could be a new way to provide contextualized recommendations. However, no existing relations between the set of features discribing an item and explicit context characteristics were shown. With the study proposed in this paper, we intend to provide a real dataset to investigate the potential links between context features and item a ributes. More speci cally, we wonder how users associate items with explicit contexts in an online music service. We used a musical dataset in our study as listening contexts are numerous, can easily be made explicit, and nding item a ributes does not constitute an obstacle. Such study could also t e-learning, museum or e-commerce scenarii.

EXPERIMENT SETUP

For the purpose of our experiment, we created an online survey2 to collect users' point of view as regards the context in which they would listen to tracks.

ese la er were selected on the basis of their preferred genres. Our goal was not to nd the most suitable tracks for each user but to nd a way to collect information on how users assign context dimensions to tracks.

MATERIALS

Users were recruited using mailing lists and the average duration to complete the study was about twenty ve minutes.

e track dataset used contains 360 tracks randomly selected from a Last.fm3 dataset collected from 28 June 2005 to 18 December 2014. We choose to randomly select tracks in a large dataset (more that 170,000 tracks) to avoid bias due to popularity. 30 tracks were selected for each of the following genre: rock, pop, rap, country, punk, jazz, hip-hop, classical, folk, metal, electronic, blues.

e only selection criteria were to have only one track per artist for all the selected tracks and to ensure that every a ributes could be retrieved through the Spotify API 4 . We then gathered 12 a ributes for each track (10 a ributes tracks, and 2 for artists).

•

: acousticness, danceability, duration, energy, instrumentalness, liveness, loudness, speechiness, tempo, valence;

•

: genre, popularity.

In the rst part of the survey, users were asked to give some demographic information (age, gender, socio-professional category) and some information about their listening habits (preferred genre, favorite place to listen to music, listening time per day, how they chose their music). e second part of the survey consisted in presenting 15 tracks to each user according to their prefered genres and ask them to assign adapted contexts to these tracks (see Table 1).

RESULTS

In order to reduce bias due to non conscientious responses, we decided to discard users who did not nished the study and obtained a nal dataset of 172 users. By discarding records for tracks which were disliked (it is meaningless to ask users to specify the context for a track they will not listen to), we got a dataset of 1,507 tracks annotated (see Figure 1 for repartition).

Table 1 :

 1 Context dimensions and conditions collected

	Context dimensions Context conditions
		relaxing, cleaning-up, cooking, driving,
	Activity	partying, reading, exercising, thinking,
		traveling, waking up, walking, working
	Day	morning, day, evening, night
	Energy	quiet, normal, energetic
	Environment	personal, professional
	Place	indoors, outdoors
	Season	spring, summer, fall, winter
	Social	alone, family, friends, couple
	Weather	sunny, rainy, snowy, cloudy
	Week	week, week-end

h ps://www.spotify.com/, h ps://play.google.com/music/

h p://movit.tv/

h p://www.last.fm/fr/api

h ps://developer.spotify.com/web-api/

Number of annotations Number of tracks

CONCLUSION

Implicit context appears to be a promising alternative to explicit context as it could be used to de ne user context while preserving his privacy and prevent data acquisition issues. In order to do so, overlaps between implicit and explicit context have to be highlighted and the data collected throught this study can be used to achieve this goal. We provide all the material collected during this study to encourage the research communtity to investigate relations between item a ributes and explicit contexts.

Link to the data: https://github.com/teamKiwi/umap2017 is project has received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No 693150.


Maël Beuget

Sylvain Castagnos

Christophe Luxembourger

Anne Boyer

Eye Gaze Sequence Analysis to Model Memory in E-education

Keywords: Eye-tracking study, memory, gaze behavior, e-education

come   L'archive ouverte pluridisciplinaire

Introduction

The introduction of digital technologies in the society during the past decades impacts inevitably many aspects of our lives. Education is one of them, and the way numeric tools can improve the quality of learning is nowadays a fullfledged research field. Intelligent Tutoring Systems (ITS) are pieces of software that help students at mastering courses. They provide them with some lessons, incorporate knowledge assessment tools, allow instant and personalized feedback, and eventually propose students to train on their specific academic deficiencies. However, estimating accurately a user state of knowledge remains a difficult task. It is quite impossible to cover every aspect of the lesson through an exam, as the evaluation process should not be too much time consuming. In some cases, students may also provide randomly correct answers. An imprecise or incomplete user model may impact the feedback quality and the relevance of the recommendations provided by ITS. To overcome this problem, we are wondering if it is possible to infer more precisely what the user remembers by collecting implicit traces of interactions. The latter are not conscientiously indicated by the user, and could be for example action logs, facial expressions or eye movements. Gaze data interests us more specifically as it has been reported that the gaze behavior could reflect some cognitive processes [START_REF] Bondareva | Inferring learning from gaze data during interaction with an environment to support self-regulated learning[END_REF][START_REF] Marchal | First attempt to predict user memory from gaze data[END_REF]. Our goal is to analyze if it could exist correlations between gaze characteristics and the fact to remember some courses items. To do so, we designed a pilot study where 22 students had to learn a short lesson about Esperanto while wearing eye-tracking glasses. After the learning phase, they were asked to pass an exam. We then compared the gaze data with their grade on the exam. Results show that fixation durations, scanpath length and scanpath angles are good predictors of what have been recalled. As a perspective, eye-trackers are thus promising tools to model users' memory in real time when they are reading their lessons.

2 Related work

A brief history of the memory models

It exists not only one but several forms of memories, and the way we can model these forms of memories is not unanimous among psychologists. The most widely accepted models are those proposed by Atkinson-Shiffrin [START_REF] Shiffrin | Storage and retrieval processes in long-term memory[END_REF], Baddeley [START_REF] Baddeley | The episodic buffer: a new component of working memory?[END_REF] and Miyake et al. [START_REF] Miyake | The unity and diversity of executive functions and their contributions to complex frontal lobe tasks: A latent variable analysis[END_REF]. In each of them, memory refers to the ability to encode, store and retrieve past experiences. It is composed of several memory modules. The sensory register allows the incoming information to be encoded for treatment. The short-term memory holds a small amount of information in mind in an active readily available state for a few seconds. The working memory manages and handles the information required to carry out complex tasks such as comprehension, reasoning, and learning. The differences between the models of Atkinson-Shiffrin, Baddeley and Miyake mainly focus on the distinction and overlap between short-term memory and working memory [START_REF] Aben | About the distinction between working memory and short-term memory[END_REF]. Finally, the longterm memory stores information for an extended period of time, consciously or not [START_REF] Squire | Conscious and unconscious memory systems[END_REF]. In our case, we take an interest in the working memory since it is the one involved in the learning process.

In parallel with this segmentation of the different forms of memory, researchers distinguish recognition and recall. The recognition process is the fact to remember something when the stimuli is present, whereas the recall involves to remember a stimulus which is not physically present [START_REF] Clariana | The effects of recognition and recall study tasks with feedback in a computer-based vocabulary lesson[END_REF]. In the context of e-education, we assume that learning a lesson correctly consists in storing the information in the recall memory.

Linking cognitive processes and eye movements

According to Just and Carpenter, what a person is looking at is assumed to indicate the on top of the stack thought of cognitive processes [START_REF] Just | Eye fixations and cognitive processes[END_REF]. More recently, Steichen et al. aimed at identifying gaze patterns [START_REF] Steichen | Hi: Eye gaze sequence analysis for informing user-adaptive information visualizations[END_REF], while Bondareva et al. use the gaze data of users while they interact with an intelligent tutoring system to predict in real time the efficiency of the users learning process [START_REF] Bondareva | Inferring learning from gaze data during interaction with an environment to support self-regulated learning[END_REF]. However, they did not investigate the possibility to infer memory. Let us note that memorized items are the results of the learning process. Predicting the quality of learning therefore amounts to predicting the amount of information stored, without however knowing how to distinguish the forgotten pieces of information from the remembered ones. Regarding the link between memory and gaze data, Hanula et al. have established the ability to predict recognition through a user study where the stimuli proposed to users were faces of people [START_REF] Hannula | The eyes have it: Hippocampal activity predicts expression of memory in eye movements[END_REF]. Several studies also tried to exploit gaze characteristics to predict memorability [START_REF] Borkin | Beyond Memorability: Visualization Recognition and Recall[END_REF] and recall [START_REF] Marchal | First attempt to predict user memory from gaze data[END_REF] of images. To our knowledge, no study has sought to establish this link between gaze and recall in a context closer to e-education, i.e. with multimedia content (text and images). This is what drives our research project. Our purpose is to verify if a link could exists between the recall process and some gaze metrics, to later potentially infer a user state of memories.

To analyze gaze data the first step is to transform the eye-tracker's sampled signal into a scanpath composed by fixations and saccades. Fixations are points of gaze where the fovea is concentrated for a short period of about 200ms, whereas saccades are the eye movement that link two consecutive fixations. Many algorithms are described in the literature to transform the sampled signal into a scanpath [START_REF] Salvucci | Identifying fixations and saccades in eye-tracking protocols[END_REF][START_REF] Komogortsev | Standardization of automated analyses of oculomotor fixation and saccadic behaviors[END_REF][START_REF] Komogortsev | Qualitative and quantitative scoring and evaluation of the eye movement classification algorithms[END_REF]. In our study we used the IV-T algorithm provided by the Tobii Pro lab software. The way we can extract metrics and information from scanpath has also been widely documented [START_REF] Holland | Biometric identification via eye movement scanpaths in reading[END_REF][START_REF] Bylinskii | Eye fixation metrics for large scale evaluation and comparison of information visualizations[END_REF][START_REF] Sharafi | Eye-tracking metrics in software engineering[END_REF][START_REF] Marchal | First attempt to predict user memory from gaze data[END_REF].

User study

We designed a pilot study where subjects were asked to learn a short lesson (5 printed static pages from an online course) and had to report their knowledge during an exam. Documents were not allowed during this exam. We have chosen to work in the context of language learning. So as to avoid the bias of languages already learned, we based our lesson on the Esperanto language. The latter has been created in 1887 with the ambition to become a vehicular language, and has been built by combining several existing languages. It is one of the less taught language, so few people studied Esperanto. We had 22 participants (10 females / 12 males) aged from 11 to 16 year old. Our eye-tracker was a Tobii Pro Glasses 2 (100Hz frequency rate). The experiment is divided in 5 parts and lasts about 1 hour (see Figure 1): the first part is the vocabularys WISC subtest, the second part is about to learn the Esperanto lesson, the third part is the codes WISC subtest, the forth part is a quiz about the lesson, and the last part is the letter-number sequencings WISC subtest. WISC stands for Wechsler Intelligence Scale for Children and is the most widely used IQ test for children (especially in the US, Canada, and Europe). It is composed by several subtests, each of them estimating precise cognitive abilities. The vocabulary subtest estimates the verbal comprehension, fluency and word-knowing, the code part estimates a learning factor and the non-verbal working memory speed, and the letter-number sequencing subtest estimates the verbal auditory recall (working memory). The second and forth part of the experiment (lesson + exam) are about to estimate a learning factor and the recall memory. The participants are evaluated on the translation of words and sentences, on the differences between the two alphabets, and on some elements of the grammar. We chose to use the WISC subtests at distracting tasks to limit the primacy-recency bias.

Analysis

Many variables have been collected through our experiment: the WISC subtests score, the gaze data, the results of the exam. We studied the distribution of the gaze data with the Shapiro-Wilk test, and found that some gaze characteristics do not follow the theoretical normal distribution. We thus chose to use an ANOVA permutation test as it is a non-parametric test. We considered 21 global gaze metrics including the normalized sum, mean and standard deviation of fixation duration, saccade horizontal amplitude, vertical amplitude, vectorial amplitude, absolute and relative angles, and pupil dilatation as defined in [START_REF] Holland | Biometric identification via eye movement scanpaths in reading[END_REF][START_REF] Marchal | First attempt to predict user memory from gaze data[END_REF]. We used the aovp() R function from the lmperm package to perform our tests. We tried to explain the Esperanto test score or the WISC subtest scores by finding an interesting combination of factors (gaze metrics). Due to the combinatorial complexity we tested up to 6 factors at the same time and saved the models when all the factors were significant (p-value < 0.05). Figure 2 shows an example of gaze features that are highly correlated to the global exam score.

Conclusion

Regarding our preliminary results in Figure 2, it seems that a link exists between some gaze metrics and the global score obtained at the Esperanto exam. These metrics are promising to predict the global learning quality. However, we found out that other combinations of gaze characteristics actually explain this variable. As a perspective, our ambition is to identify, map and order all gaze parameters based on their ability to predict the quality of the recall memory. In addition, beyond the global memorization score, we aim at developing a machine learning technique that can accurately distinguish what is learned from what is forgotten. We plan to extend this pilot study by passing our study to entire classes in our academy, so as to increase the statistic power of our tests. We hope that these preliminary study is a first step toward recommender systems based on the memory of users.

Fig. 1 .

 1 Fig. 1. The 5 parts of our experiment: blue ones are recorded with the eye-tracker.


Pierre-Edouard Osche
email: pierre-edouard.osche@loria.fr

Sylvain Castagnos
email: sylvain.castagnos@loria.fr

Anne Boyer
email: anne.boyer@loria.fr

AntRS: Recommending Lists through a Multi-Objective Ant Colony System

Keywords: Recommender systems, Multi-agent Systems, Multi-agent reinforcement learning

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Recommending an appropriate list or sequence of items to a specic user can be seen as a multi-objective problem. Let us illustrate this with a use case: Imagine a user who enjoys listening to music while doing sport through a mobile app. Such an online service should generate a playlist that is adapted to her preferences (precision). The tempo and the energy of the proposed songs should t the context (similarity). The playlist should oer an appropriate level of diversity to avoid boredom. It could also bring novelty and serendipity according to her desires. The scientic challenge thus consists in taking into account dierent constraints that are contextualized and potentially not compatible.

In this paper, we propose a new multi-objective recommender system, called AntRS. Our model relies on a Multi-Agent System. The environment is a graph whose nodes are the items in the item set and whose edges connect items that have been co-consulted by several users. An Ant Colony Optimization algorithm allows to explore this environment until the target state is reached for each objective. Our model is generic since it is possible to add as many colonies as the domain context requires. The paths generated by the dierent colonies are then merged to oer a good compromise between the objectives. We have validated our approach by choosing 4 objectives which can be antagonist (similarity vs. diversity, preferences vs. novelty). We relied on a music dataset made of 180,000 songs and 500 users, and compared our approach to 4 state-of-the-art algorithms. We measured the performances using several metrics (accuracy, novelty, diversity, coverage...). Results show that AntRS achieves a better accuracy than others, while oering a better compromise to users on other objectives. This paper is organized as follows: Section 2 presents the related work on multi-objective recommenders and the principle of the Ant Colony Systems from which our system took inspiration. Section 3 describes our AntRS model. Sections 4 and 5 respectively describe the experiments carried out and the results obtained. Finally Section 6 concludes this paper and presents our perspectives.

2 Related Work

Multi-Objective Recommender Systems

A recommender system can either propose a list of independent items at each time step, or it can propose a sequence of items [START_REF] Quadrana | Sequence-aware recommender systems[END_REF]. In Sequence-Aware Recommender Systems, one can both consider the importance of the order of the past events (by looking for co-occurrence patterns [START_REF] Bonnin | Automated generation of music playlists: Survey and experiments[END_REF] or for sequential patterns [START_REF] Hariri | Context-aware music recommendation based on latenttopic sequential patterns[END_REF] in past sessions) and the expected order of the future recommendations (e.g. continuation in playlists [START_REF] Jannach | Beyond hitting the hits: Generating coherent music playlist continuations with the right tracks[END_REF] or transitions between items [START_REF] Maillet | Steerable playlist generation by learning song similarity from radio station playlists[END_REF]). In this paper, we based our experiment on a music dataset. As recent research has found little evidence that the exact order of songs actually matters to users [START_REF] Tintarev | Sequences of diverse song recommendations: An exploratory study in a commercial system[END_REF], we limited our state-of-the-art to the recommendations of lists. Transversely a recommender system can be mono-objective or multi-objective.

Most recommenders solely focus on the accuracy (precision and recall) [START_REF] Ricci | Recommender Systems Handbook[END_REF]. Others attempt to nd a compromise between precision, serendipity and novelty [START_REF] Kaminskas | Diversity, serendipity, novelty, and coverage: A survey and empirical analysis of beyond-accuracy objectives in recommender systems[END_REF], or between precision and diversity [START_REF] Ziegler | Improving recommendation lists through topic diversication[END_REF][START_REF] L'huillier | Understanding usages by modeling diversity over time[END_REF] for example. There are several ways to address a multi-objective optimization problem. One can either look for a set of Pareto solutions, considering that a solution is optimal if it is not possible to make any objective better o, without making at least one objective worse o [START_REF] Zuo | Personalized recommendation based on evolutionary multi-objective optimization [research frontier[END_REF]. In that case, recommender systems aim at producing as many solutions as possible in order to cover as much as possible of the problem's Pareto front.

Or one can rank the items in a single list by aggregating or reordering the results of each single objective [START_REF] Ribeiro | Pareto-ecient hybridization for multi-objective recommender systems[END_REF]. This list can be produced in one stage [START_REF] Guimarães | Guard: A genetic unied approach for recommendation[END_REF], or come out of a 2-step process consisting in generating several lists of candidate items for the active user and in merging them [START_REF] Geng | Nnia-rs: A multi-objective optimization based recommender system[END_REF]2729,[START_REF] Ribeiro | Multiobjective pareto-ecient approaches for recommender systems[END_REF][START_REF] Fortes | User-oriented objective prioritization meta-featured multi-objective recommender systems[END_REF]. Recommending several Pareto solutions oers the advantage to leave the choice to the active user. It can be interesting in some application domains such as e-commerce where an explicit validation process from the user is mandatory. However, in the context of online music services, it is not conceivable to request a user decision at each timestep.

The songs must come one after another without disturbing the user in his/her main current task. For this reason, we focused this paper on recommenders which produce only one solution (i.e. only one list of recommendations).

The existing multi-objective single-list recommenders suer from several limitations: they are dependent from the application domain (any change in the set of objectives has a drastic impact on the implementation of the model) and they are very time-consuming. To bypass these diculties, we propose a new approach relying on a Multi-Agent System (MAS), and more precisely on an Ant Colony System explained below. MAS have multiple advantages in our context: they have a relatively low computational complexity; they are ecient at tackling multi-objective problems [START_REF] Ariyasingha | Performance analysis of the multi-objective ant colony optimization algorithms for the traveling salesman problem[END_REF][START_REF] Barán | A multiobjective ant colony system for vehicle routing problem with time windows[END_REF]; they can easily be adapted to new congurations and are resilient to changes.

Ant Colony Systems

The Ant system algorithm (AS) is inspired by the foraging behavior of ants, specically the pheromone communication between ants, to nd shortest paths in an environment between a starting node and a target node. Dorigo proposed a few dierent versions of this AS model [START_REF] Dorigo | Ant colony optimization[END_REF]. Our model took inspiration from one of those variants, the Ant Colony System (ACS) algorithm. In comparison to the classic AS model, ACS proposes a dierent way for the ants to deposit pheromones. Instead of having all the ants deposit their pheromones at the end of one iteration (i.e. after all the ants have nished their tour), only the ant that found the best path can deposit pheromones. Furthermore, ants perform a so called local pheromone update where, after each construction step, they deposit some pheromone on the last edge they visited. In other words, each time an ant takes an edge, it deposits some pheromones along its way, regardless of the quality of the path. As explained by Dorigo, this version of the ACO algorithms is known to diversify the search performed by subsequent ants during an iteration: by decreasing the pheromone concentration on the traversed edges, ants encourage subsequent ants to choose other edges and, hence, to produce dierent solutions. This makes it less likely that several ants produce identical solutions during one iteration. As our search space is large (there are millions of songs on an online music service) and as we promote not only the precision but other characteristics in the recommended lists, we chose the ACS algorithm.

In the rest of this subsection, we explain the main formulas of the ACS.

State transition rule -The state transition rule uses the pseudo-random proportional rule where a random variable q ∈ [0; 1] is compared to a parameter q 0 to decide if the ant will explore the graph or if it will exploit the knowledge collected by previous ants. q 0 = 0 is equivalent to the AS model where ants only explore the graph while q 0 = 1 refers to a pure reinforcement behavior with no exploration. The Equation 1 let the algorithm decide between knowledge exploitation and biased exploration of the graph.

Exploitation (Equation 2) if q ≤ q 0 Biased exploration (Equation 3) if q ≥ q 0 (1)

The Equation 2 represents the direct exploitation of the knowledge in the graph where the best edge is always chosen.

arg max l∈Vi {τ α il • η β il }, (2)
where V i is the set of available nodes from the node i, τ il ∈ [0; 1] is the amount of pheromones left on an edge (i, l) by previous ants, η il is the heuristic information on an edge (i, l), α and β are two parameters representing respectively the weight of the pheromones and the weight of the heuristic.

The Equation 3 represents the biased exploration where best edges have more chances to be picked and p ij is the probability for an ant at the node i to choose the edge (i, j).

p ij =          τ α ij • η β ij l∈Vi τ α il • η β il , if j ∈ V i , 0, otherwise, (3)
Global pheromone update -After each iteration, only the ant who found the best tour is allowed to update the pheromone level τ ij :

τ ij = (1 -ρ) • τ ij + ρ • ∆τ ij if (i, j) belongs to best tour, τ ij otherwise, (4)
where ρ is the evaporation rate of the pheromones and ∆τ ij = 1/L best where L best is the length of the best tour.

Local pheromone update -Another addition of the ACS model over the AS model is the local pheromone update performed after each step by each ant described in Equation 5.

τ ij = (1 -ρ) • τ ij + ρ • τ 0 , (5)
where τ 0 is the pheromone level set on every edge at the initialization.

Heuristic information -the heuristic information η ij represents the information that ants possess a priori on an edge (i, j). In ACS, the heuristic information is computed based on the distance between the two nodes of the edge: the farther both nodes are from each other and the lower η ij will be.

η ij = 1 d ij
, where d ij is the distance between nodes i and j.

3 Our model: AntRS

As previously stated, AntRS has been built with several goals in mind: (1) be as generic as possible; (2) be able to include several competing objectives in a single list; (3) be resilient to changes in the environment (new items, new preferences,. . . ). Our model takes inspiration from the ACS algorithm because the latter gathers all the quality needed to satisfy those objectives. However, we want to point out the dierences between the classic ACS as described in Section 2.2 and our model AntRS. First of all, we had to develop our own method to create a graph to model as best as possible the large environment we were working in without hindering the execution time of the system. In Subsection 3.1 we present our graph creation method. Secondly, we wanted to optimize many objectives while the ACS optimizes only one attribute which is usually the distance. In Subsection 3.2 we introduce more formally the objectives used in our model.

Thirdly, as we are generating several paths during the algorithm execution, a merging procedure has to be executed at one point to be able to propose the best possible recommendation list for each user. The Subsection 3.3 explains two tactics we used to do so.

Graph creation

The rst step of our model is the creation of the graph. This is often an overlooked part in the literature as the datasets used are usually small and/or the links between nodes of the graph are manually picked by a eld expert. One of the main dierences between ACO simulations and real ants is the denition of the search space. Real ants are evolving in a continuous search space without any landmarks (or vertices) and are free to go everywhere whereas agents are released in a discrete environment and have to follow predetermined paths (or edges) between set landmarks. One of the ways to be as close as possible to real ants' behavior would be to compute distances between each and every node of the graph to build a complete graph. It is nonetheless an unpractical solution for more than a few thousands vertices as the number of edges depends on the number of vertices n with |E| = n(n-1)

2

. As our goal is to use our model in a realistic situation with many potential items represented by vertices, we decided to nd a workaround without sacricing the quality in the solutions found. To do so, we needed to select a few best edges between each vertex. At this point, we formulated two hypotheses to help us construct the graph: (1) past sequences created by previous users represent useful domain knowledge which should be exploited; (2) past sequences done by previous users are not always the best possible ones and could have been improved with clever recommendations.

To take into account those two hypotheses, we rst computed the number of transitions (i.e. co-consultations) between each pair of items in our dataset and we added (1) all the transitions above a specic threshold, and (2) only some of those below this threshold as edges. Finally, if a given connectivity degree was not reached, we added new edges between items who were not connected in our dataset to allow our model to discover new potential interesting paths not known by users. The process of creating an edge is shown in Equation 7.

e ij =          if t ij ≥ m
or if t ij < m and q < t ij where q ∈ [min t il ; log(max t il )]

or if t ij = 0 and if deg(i) < d then pick a random transition until deg(i) = d (7)
where e ij is the presence of an edge between vertices i and j, t ij is the number of transitions performed from item i to item j by the users in the dataset, m is the threshold where transitions are not directly added to the graph as edges, q ∈ [min t il ; log(max t il )] is a random variable uniformly distributed, min t il is the minimal number of transitions between the item i and all the others items l ∈ V i where at least one transition has been found, deg(i) is the current degree of the node i in the graph and d is a parameter specifying the minimal degree each vertex must have in the nal graph.

Objectives

It is now widely admitted that the sole precision is not sucient to produce good recommendations to users. We thus propose to dene a set of 4 concurrent objectives that have to often be considered in the literature while recommending a list of items. The objectives we considered are all transposable in dierent application domains, guaranteeing the genericity of our approach. Furthermore, the ability to add, to modulate the importance or to remove objectives on the y was essential for having an adaptive model. To address this issue, we chose to integer as many colonies as objectives in our model, and each colony is specialized in maximizing its own objective. To do so, we modied the way the ACS model computes the distance d between two nodes of the graph while the calculation of the heuristic η ij was left untouched. The rest of this Section describes the equations used to compute the distance for each colony.

Similarity -This is one of the main factor considered by nearly all the recommender systems. The main goal of a recommender system is to propose items similar to what the user liked before. Even if similarity is a well-known and widely used characteristic, we think that a good recommender system cannot overlook it. We also do consider that similarity should not be the cornerstone of each and every recommender system anymore. The goal of this colony is to nd a list with items as similar as possible of what the user previously viewed or is currently viewing. A lot of methods exist to compute the similarity of two vectors and, based on our dataset and on the metadata available, we decided to use a cosine similarity measure [START_REF] Su | A survey of collaborative ltering techniques[END_REF]. To compute the distance value on the edges of the graph, we simply computed the cosine similarity between the two items represented by the vertices. More formally, for an edge (i, j), its associated distance d ij is computed with the cosine similarity between the vectors of the descriptive characteristics of the items i and j.

d ij = 1 sim(C i , C j ) (8)
where C i are the characteristics of the item i. The item characteristics depend obviously on the dataset and on the meta-information available but, we can formalize that each item of the dataset is described by n characteristics as follow C i = {c 1 , c 2 , . . . , c n }. We used the multiplicative inverse to transform the similarity metric sim ∈ [0; 1] into a distance d ∈ [1; +∞]. Therefore, a distance value near 1 on an edge (i, j) means that the two items i and j are similar.

Diversity -This characteristic and the similarity are often described together as they are both related to the distance/correlation between the items liked by the user and his/her recommendations. But unlike similarity, diversity depicts how dissimilar two items are relatively to each other. Similarity and diversity are complementing each other in the sense that they are both needed to adapt the system to the needs of dierent users [START_REF] Jones | User Perceived Qualities and Acceptance of Recommender Systems: The Role of Diversity[END_REF]. To compute this objective, we chose to apply one of the classic diversity metric which is obtained by computing the inverse of the similarity between two items, as shown in Equation 9.

As for the similarity, we used the multiplicative inverse of the diversity to obtain

a distance d ∈ [1; +∞]. d ij = 1 1 -sim(C i , C j ) (9)
Novelty -This characteristic represents the items that are not yet known by the user. It could be new items recently added to the system or old but not so popular items that the user missed. Novelty should not be confused with diversity, since novel items could be either similar or dissimilar to what the user usually likes. Novelty is an important characteristic of a recommender system to avoid a potential lack of interest of users due to too much foreseeability in the recommended items [START_REF] Vargas | Rank and relevance in novelty and diversity metrics for recommender systems[END_REF].

To determine if an item is novel or not relatively to a specic user, we used the work of Zhang [START_REF] Zhang | The denition of novelty in recommendation system[END_REF] who dened the novelty as a notion composed of three characteristics: (1) Unknown: the item is unknown to the user; (2) Satisfactory: the item is liked by the user; (3) Dissimilarity: the item is dissimilar to the other items known by the user. The author proposed to evaluate the novelty of the item i for the user u as follow: novelty(i, u) = p(i|unknown, u) • dis(i, pref u ) • p(i|like, u) [START_REF] Guimarães | Guard: A genetic unied approach for recommendation[END_REF] where p(i|unknown, u) is the probability that the user u does not know the item i, dis(i, pref u ) is the dissimilarity between i and the set of items in the users' prole and p(i|like, u) is the probability that u will like i. However, the dissimilarity and the satisfaction of the user relatively to i are closely related to other objectives in our model, respectively maximized by the diversity colony and by both the preferences and the similarity colonies. Hence we decided to trim down the Equation 10 to the probability p(i|unknown, u) only (see Equation 11).

p(i|unknown, u) = -log(1-pop i ), where pop i is the popularity of item i. [START_REF] Guo | Librec: A java library for recommender systems[END_REF] Preferences -The preferences characteristic corresponds to what the user really likes. It intersects with the similarity notion but, again as with diversity and novelty, we think that preferences express another aspect of a good recommendation for a user. The similarity characteristic allows the recommender to propose items that are similar to the preferences of the user, but it is not guaranteed that he will like those items. It is for example perfectly common to both like and dislike some songs coming from the same album and artist, yet those songs will probably be treated as very similar relative to each other. The preferences characteristic favors items that are known to be liked by the user.

The goal for this colony is to nd a sequence in the graph prioritizing items that are already known to be liked by the user. Thereby, items must have criteria conveying how the user like an item or not. This can be done either with explicit feedback (e.g. item rating,. . . ), with implicit feedback (e.g. number of times the user viewed an item,. . . ) or with a combination of both. The nature of the feedback will heavily depends on the domain, but we can formalize that each collected information concerning the behavior of a user on an item must be taken into account. Let C u be the set of criteria representing all the actions that a user u may perform on the items of the system, thus c u,i is the sum of all interactions specic to a single criterion c that a user u performed on an item i (e.g. the number of times a user u viewed i). To aggregate all the dierent interactions possible in a single value, we use the presumed interest formula proposed by Castagnos et al. in [START_REF] Castagnos | A client/server user-based collaborative ltering algorithm: Model and implementation[END_REF] and described in the Equation 12.

presumed interest u,i = v min + c∈C (w(c) • c(u, i)) c∈C w(c) • (v max -v min ) c max (12)
where c(u, i) corresponds to normalized values given to the item i by the user u to each criterion c, w(c) is the weight of the criterion c, v min and v max are the minimal and maximal expected values for the presumed interest and c max is the maximal value that c(u, i) can take regardless of the criteria. In our case, we considered the following criteria for each song: number of consultations, number of skips, number of bans (when the user do not want to listen to the song ever again) and number of likes.

Merging tactics

In the previous section, we described four objectives that could provide suitable recommendations for users. Each of these four objectives is associated to a specic ant colony in our model. Thus, after this step, we are left with as many lists of recommendations as colonies, where each one should represent a part of the nal recommended list. In order to build it, we needed a tactic to merge all the colonies' lists into one. To do so, we propose two techniques described below.

Merging colony -The rst merging tactic relies once more on the ACS algorithm but with one additional colony that we called merging colony. Starting from the set of items found by the other colonies (step 1), the merging colony considers all the objectives at once with a weighted sum to calculate the distances on the graph's edges (step 2), as shown in Equation 13.

d ij = col∈colonies w(col) • d ij (col) (13)
where w(col) is the weight representing the expected importance of the colony's objective in the nal recommendation. To estimate those weights, we calculated the average values of each objective (similarity, diversity, novelty and preferences) on the last n sessions processed of the user. This gave us the general importance of each objective while taking into account contextual information and recent tendencies in the user's behavior. We also built a new graph for this path of the algorithm. To construct it, we used all the items in the lists found by the other colonies as vertices, we added edges to each consecutive pair of items in the lists and nally we added random edges in the same way that is described in the last part of the Equation 7to give the possibility of new paths to be found and chosen by the merging colony's agents.

Lists merging -For the second merging tactic, we calculated the weight w(col) of each objective in the same way that for the merging colony (see above).

We then built the list step by step by considering all the items found by the dierent colonies. We iterated through all the available items for each step of the list construction and we added to the nal recommended list the item which yield the best amelioration towards the expected values. This process was stopped either when the remaining items degraded the list's metrics, when there was no items left or when the last item of the initial listened session was found.

Experimentation

Comparison algorithms

We compared the performances of AntRS with four state-of-the-art algorithms capable of producing lists of items in the same conditions than our model. The rst three are classical techniques spanning most of the work in the recommender systems domain: (1) UserKNN [START_REF] Breese | Empirical analysis of predictive algorithms for collaborative ltering[END_REF]; (2) TrustMF [START_REF] Yang | Social collaborative ltering by trust[END_REF] and (3) SVD++ [START_REF] Koren | Factorization meets the neighborhood: a multifaceted collaborative ltering model[END_REF]. Those three algorithms were implemented using the Java library librec [START_REF] Guo | Librec: A java library for recommender systems[END_REF]. We also implemented a fourth hybrid multi-objective model named PEH described in [START_REF] Ribeiro | Multiobjective pareto-ecient approaches for recommender systems[END_REF] to be able to compare AntRS to a state-of-the-art multi-objective recommender system. We used the three algorithms described above in the hybridization process. Furthermore, we also ran several version of AntRS to assess the strenghts and the weaknesses of our model.

Dataset

For our experimentations, we decided to use a dataset from Deezer as they oer the possibility to get metadata and information on listened tracks with their API. Our dataset spans one month of listenings starting from 5th Dec. 2016.

We split the dataset in listening sessions which corresponded to a listening with a break not longer than 900+track_duration seconds. Among all 1,871,919 consultations, we were able to determine 91,468 unique sessions with a mean length of 18.3 tracks each. The full dataset contains 3,561 unique users, 178,910 unique songs, and 1,871,919 listenings. However, as the PEH algorithm is not highly scalable (similarly to most of multi-objective algorithms) and so as to compare all algorithms in the same conditions, we limited the experiment to 500 randomly chosen users.

Each track is described by a number of metadata provided by Deezer, including song name, artist name, album name, music genre, related artists and some numerical values like acousticness, danceability, energy, instrumentalness, liveness, loudness, speechiness, tempo and valence. We used those characteristics to implement the metrics of the four dierent colonies described in Section 3.2.

Finally, so as to transform consultations (more precisely metadata such as duration, frequency or recency of consultations) into ratings usable by collaborative ltering algorithms (UserKNN, TrustMF, SVD++), we used the Formula 12

proposed by [START_REF] Castagnos | A client/server user-based collaborative ltering algorithm: Model and implementation[END_REF]. We recall that this same formula was also used by our model for the objective of preferences, taking no advantage on other algorithms.

Experimental protocol

We performed several evaluations of our model in diverse congurations to measure its performance relatively to itself and to other models. To guarantee a fair chance for each model and conguration, we set the same starting and stopping conditions and we used the same data for all the experiments we did. For each listening session of the test base users, each algorithm produced one recommended list and its performance was measured in comparison to the initial listening session. The rst item of each session was given to the algorithm as starting point for the recommended list. The last item was not given but, if the algorithm reached it during the recommendation process then it was stopped.

A minimum size was set for the recommended list which was half of the size of the initial listened session. After the recommendation, the initial listened session was added to the training base to simulate a real-case scenario where a system rst has no information on a new user and then gather more and more data on him as he interacts with the system. Finally, all the tests were performed on a cross-validation dataset with a training base of 400 users and a test base of 100 users each time. For each listening session composed of 5 items or more in the test base, a recommended session was produced. The users of the training base had listened to 10,621 sessions while there were 2,569 sessions in the test base.

We used dierent metrics capturing all the aspects of what we consider a good recommendation: Precision, Recall and F-measure [START_REF] Baeza-Yates | Modern information retrieval[END_REF], Similarity and Intralist Similarity [START_REF] Ziegler | Improving recommendation lists through topic diversication[END_REF], Diversity and Relative diversity [START_REF] Mcginty | On the role of diversity in conversational recommender systems[END_REF][START_REF] Vargas | Rank and relevance in novelty and diversity metrics for recommender systems[END_REF]. We also used the preferences and the novelty metrics of Equations 11 and 12 as well as in [START_REF] Vargas | Rank and relevance in novelty and diversity metrics for recommender systems[END_REF]. We empirically xed the meta-parameters values of the baseline algorithm described in 2.2 as follows: q 0 = 0.3, α = 0.1, β = 0.9, ρ 0 = 0.2, τ 0 = 0.1.

Results

Single-objective AntRS

We rst wanted to see how each of our objective performed alone. As our model allows us to change the number of objectives on the y, we performed four different tests for the four dierent objectives without any merging step and we measured how each of the tests performed considering the metrics described above. The Table 1 presents those results. We measured the statistical significance of the score of the colony that was supposed to perform best on each metric in comparison with the results obtained by the other colonies. Thus, the similarity and the intra-list similarity of the similarity colony were compared to the similarity and intra-list similarity of the 3 others colonies and so on. As the Shapiro-Wilk test revealed that our data did not follow a normal distribution, we used the non-parametric Wilcoxon test which allowed us to compare the means of two related samples (same users with dierent algorithms). As expected, we can see that each of our colonies produce lists that are specialized in a single objective. Thus, the similarity colony produces lists that are the most similar relatively to all the other colonies; the novelty colony produces lists that are the most novel, and so on. Those experiments showed that our model was working as intended and that we could combine the four objectives together.

Multi-objective AntRS

In Table 2, we present the summary of the results obtained for all the models tested and their variations. We also measured the statistical signicance of the results of our best performing model, AntRS with the lists merging, in comparison with the results of all the other models. As for the previous subsection, the statistical test used was Wilcoxon signed-rank test.

As explained in Section 3.3, we proposed and tested two merging tactics to combine the results of our four objectives. We also tested to run the merging colony alone, without the step 1 in the rst merging tactic of Section 3.3: in that scenario, the merging colony operates on the whole graph, rather than on the subgraph of items recommended by the four colonies. We hypothesize that running directly the merging colony without the step 1 will degrade the quality of the nal solutions found. This rst step with the four colonies gave our model the ability to nd very specialized lists of items, which are associated to optimal solutions in a Pareto front, and this process was supposed to help the merging colony to nd a better compromise between those solutions. This hypothesis has been conrmed in Table 2 since the two variants of AntRS with the 4 colonies got better results than the sole merging colony on each metric, except for the similarity, thus oering a better deal. The rst merging tactic of our model outperforms the second one in terms of precision, but the latter obtains the best relative diversity of all the AntRS variants.

We can also see that both AntRS variations obtain the best precision (up to +78.23%), recall (up to +29.05%) and F-measure (up to +31.28%) of all the models tested, which means that our model was the best to capture the preferences from the lists initially listened by the users in the training set. AntRS Diversity, Novelty vs. Preferences), which makes the task harder for the multiobjective algorithms (AntRS and PEH) compared to others. Despite a lower diversity, AntRS oers a better compromise between all the objectives than PEH, and in a much shorter execution time. Within the frame of this experiment, we considered that all the objectives had an equal importance. However, it would be easy to weight the dierent objectives in AntRS according to user expectations, like they did in [START_REF] Fortes | User-oriented objective prioritization meta-featured multi-objective recommender systems[END_REF]. Finally, we can notice that AntRS and PEH got a much better coverage compared to other algorithms.

Conclusion and Perspectives

In this paper, we showed that our model, AntRS, is able to generate lists with a higher precision than other methods, while still oering a good compromise between similarity, diversity, novelty and preferences. AntRS oers many advantages compared to the state-of-the-art models: (1) the multi-agents part of our model guarantees that it is highly adaptable to changes in the environment, (2) the objective-oriented colonies can be added or removed on the y, (3) it is generic enough to be adapted in all the domains where a list recommender is relevant, and (4) it is highly parallelizable and resilient to the cold-start problem.

We have some interesting ideas on how to pursue our work in the future. First, we would like to improve the quality of the recommended lists by personalizing the construction of the graph. At the moment, a unique graph is created for all the users while the distances on the edges are recalculated for each user. We would like to improve the personalization by creating a unique graph for each user, and even a unique graph for each colony.

Secondly, we would like to work on the notion of sequence. Instead of recommending simple lists to user, we think that oering a coherent sequence of items with a start, an end and a good progressivity could be benecial in other domains (a path in a museum, a sequence of courses for a student. . . ). This could be achieved by adding a colony dedicated to the progressivity.

  *** 0.118 *** 0.141 *** 0.953 *** 0.93 *** 0.047 *** 0.068 0.324 *** 0.389 *** 96.92% UserKNN 0.224 *** 0.138 0.162 *** 0.95 *** 0.905 *** 0.05 *** 0.081 *** 0.68 *** 0.541 61.39% TrustMF 0.195 *** 0.117 *** 0.14 *** 0.95 *** 0.894 *** 0.058 *** 0.09 *** 0.697 *** 0.458 *** 68.17% SVD++ 0.195 *** 0.12 *** 0.14 *** 0.941 *** 0.892 *** 0.06 *** 0.093 *** 0.70 *** 0.455 *** 68.17% PEH 0.193 *** 0.118 *** 0.14 *** 0.941 *** 0.892 *** 0.059 *** 0.096 *** 0.697 *** 0.452 *** 97,52% Signicance codes (compared to AntRS with 4 colonies + lists merging): 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1 also outperformed the other models for the preferences and the novelty metrics, while still managing to maintain a correct level of similarity and diversity. Let us remind that we deliberately chose non-compatible objectives (Similarity vs.

Table 1 .

 1 Experimentations with AntRS as a single-objective model

	Precision Recall F-measure Similarity 0.317 0.126 0.165 0.952 0.923 0.048 *** 0.049 *** 0.72 *** 0.447 *** ILS Diversity RD Novelty Preferences 0.211 0.104 0.127 0.862 *** 0.77 *** 0.138 0.19 0.806 *** 0.393 *** 0.132 0.112 0.114 0.895 *** 0.837 *** 0.105 *** 0.144 *** 0.909 0.379 *** Preferences colony 0.296 0.159 Similarity colony Diversity colony Novelty colony 0.191 0.946 *** 0.91 *** 0.054 *** 0.08 *** 0.695 *** 0.804
	Signicance codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

Table 2 .

 2 Experimentations with AntRS as a multi-objective model

	AntRS (4 colonies + lists merging) AntRS (4 colonies + merging colony)	Precision Recall F-measure Similarity 0.344 0.131 0.1838 0.947 0.908 0.053 0.069 0.741 0.61 96.92% ILS Diversity RD Novelty Preferences Coverage 0.288 *** 0.151 *** 0.1836 ** 0.945 0.905 *** 0.055 0.082 *** 0.702 *** 0.612 ** 96.92%