Bjarke Hammersholt
email: christian.eder@inria.fr

Signature Rewriting in Gröbner Basis Computation

Keywords: G.4 [Mathematical Software]: Algorithm design and analysis Gröbner basis, Syzygy Gröbner basis, Signature Gröbner basis, Signature rewriting, F5

We introduce the RB algorithm for Gröbner basis computation, a simpler yet equivalent algorithm to F5GEN. RB contains the original unmodified F5 algorithm as a special case, so it is possible to study and understand F5 by considering the simpler RB. We present simple yet complete proofs of this fact and of F5's termination and correctness.

RB is parametrized by a rewrite order and it contains many published algorithms as special cases, including SB. We prove that SB is the best possible instantiation of RB in the following sense. Let X be any instantiation of RB (such as F5). Then the S-pairs reduced by SB are always a subset of the S-pairs reduced by X and the basis computed by SB is always a subset of the basis computed by X.

INTRODUCTION

The F5 algorithm [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] is a significant development in Gröbner basis computation and the difficulty of understanding it is a widely cited concern. We address this problem in this paper by introducing RB, an algorithm simpler than yet equivalent to F5GEN [START_REF] Pan | The Termination of Algorithms for Computing Gröbner Bases[END_REF]. RB contains the original unmodified F5 as a special case [START_REF] Pan | The Termination of Algorithms for Computing Gröbner Bases[END_REF], so we can understand and prove statements about F5 by considering the simpler RB. In this way we present simplified proofs of the termination and correctness of F5. Much of the paper is concerned with showing exactly how to derive F5 as a special case of RB.

There are many publications that present signature-based algorithms for Gröbner basis computation. Seeing as these algorithms are based on signatures, they are all somehow related to F5, yet it is often not clear what the exact relationship is -is F5 a special case of the new algorithm? If not, what are the exact differences? Pan, Hu and Wang [START_REF] Pan | The Termination of Algorithms for Computing Gröbner Bases[END_REF] (PHW) addressed this problem by introducing the F5GEN algorithm. F5GEN contains many published algorithms as special cases which makes it possible to compare algorithms theoretically. PHW pose the open problem of which instantiation of F5GEN is faster: Moreover, with this proved F5GEN algorithm, researchers can shift their focus on the different variants of the F5GEN algorithm and find out the fastest one. --Pan, Hu, Wang [START_REF] Pan | The Termination of Algorithms for Computing Gröbner Bases[END_REF] We answer this open problem by proving that the SB algorithm [START_REF] Roune | Practical Gröbner basis computation[END_REF] is the best possible instantiation of RB (and hence F5GEN) in the following sense. Let X be any instantiation of RB (such as F5). Then the S-pairs reduced by SB are always a subset of the S-pairs reduced by X up to signature and the basis computed by SB is always a subset of the basis computed by X up to sig-lead pairs.

Roune and Stillman's algorithm SB [START_REF] Roune | Practical Gröbner basis computation[END_REF] is an improvement of Gao, Volny and Wang's algorithm GVW [START_REF] Gao | A new algorithm for computing Groebner bases[END_REF]. SB is equivalent to Arri and Perry's algorithm AP [START_REF] Arri | The F5 Criterion revised[END_REF] and also to the modification GVWHS [START_REF] Volny | New Algorithms for Computing Gröbner Bases[END_REF] of GVW, so all statements made about SB also apply to AP and GVWHS.

Section 2 introduces terminology and SB. Section 3 introduces RB and proves that SB is the best possible instantiation of RB. Section 4 introduces RB5, a special case of RB that is more similar to F5. Section 5 proves that F5 is a special case of RB5 (and hence RB). Section 6 proves termination of RB (and hence F5).

Remark 1. The F5 paper [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero F5[END_REF] requires that the input polynomials form a homogeneous regular sequence. Faugère must have known of an algorithm without these restrictions since the F5 paper contains benchmarks on ideals that do not meet the restrictions. In this paper, the term F5 refers exclusively to F5 exactly as described in the F5 paper [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero F5[END_REF] including the restriction to homogeneous regular sequences.

THE SIGNATURE BASIS ALGORITHM

We briefly introduce SB in this section. We refer to [START_REF] Roune | Practical Gröbner basis computation[END_REF] for a full treatment of SB with proofs. If we consider a polynomial ring R then the main differences between SB and the classic Buchberger algorithm is that everything is lifted from R to R m , that polynomial reduction is constrained in that some reduction steps are not allowed and that the S-pair elimination criteria are more powerful. It is not actually necessary to represent polynomials in R m when implementing SB on a computer (see Remark 2).

Notation and Terminology

Let R be a polynomial ring over a field κ. All polynomials f ∈ R can be uniquely written as a finite sum f = cx v ∈M cx v where c ∈ κ, x v is a polynomial with exactly one term. A monomial with a coefficient of 1 is monic. Neither monomials nor terms of polynomials are necessarily monic. We write f ≃ g for f, g ∈ R if there exists a non-zero s ∈ κ such that f = sg.

Let R m be a free R-module and let e1, . . . , em be the standard basis of unit vectors in R m . All module elements α ∈ R m can be uniquely written as a finite sum α = ae i ∈M aei where the a are monomials and M is minimal. The elements of M are the terms of α. A module monomial is an element of R m with exactly one term. A module monomial with a coefficient of 1 is monic. Neither module monomials nor terms of module elements are necessarily monic. Let α ≃ β for α, β ∈ R m if α = sβ for some non-zero s ∈ κ.

Let ≤ denote two different orders -one for R m and one for R. The order for R is a monomial order, which means that it is a well-order on the set of monomials in R such that a ≤ b implies ca ≤ cb for all monomials a, b, c ∈ R. The order for R m is a module monomial order which means that it is a well-order on the set of module monomials in R m such that L ≤ T implies cL ≤ cT for all module monomials L, T ∈ R m and monomials c ∈ R. We require the two orders to be compatible in the sense that a ≤ b if and only if aei ≤ bei for all monomials a, b ∈ R and i = 1, . . . , m.

Consider a finite sequence of polynomials g1, . . . , gm ∈ R that we call the input polynomials. Define the homomor-

phism α → α from R m to R by α . .= m i=1 αigi. α ∈ R m is a syzygy if α = 0.
Let the lead term lt (f ) be the ≤-maximal term of f ∈ R \ {0}. Let the signature s (α) be the ≤-maximal term of α ∈ R m \ {0}. In this way every non-syzygy module element α ∈ R m has two main associated characteristics -the signature s (α) ∈ R m and the lead term lt (α) ∈ R of its image α in R. Lead terms and signatures include a coefficient for mathematical convenience, though an implementation of SB need not store the signature coefficients. If aei = s (α) then ind (α) .

.= i is the index of signature of α. Let G ⊆ R m be finite and assume that s (α) ≃ s (β) ⇒ α = β for α, β ∈ G. α, β ∈ R m are equal up to sig-poly pairs if s (α) = s (sβ) and α = sβ for some non-zero s ∈ κ.

Consider the unique extension of the module monomial order < to module monomials that may have negative exponents such that aei < bej ⇔ caei < cbej for all monomials a, b, c ∈ R. The sig-lead ratio of α ∈ R m is rα . .= s(α) lt(α) . This notation is the SB notation [START_REF] Roune | Practical signature Gröbner basis computation[END_REF], which is improved from the notation of the preceding paper [START_REF] Roune | Practical Gröbner basis computation[END_REF]. In particular, there is no module R n and no function φ : R n → R m . Remark 2. The SB notation using module elements differs from the standard notation which considers sig-poly pairs (s (α) , α) in place of α ∈ R m . SB can also use sig-poly pairs (see Section 5.1). We believe that the SB notation makes signature algorithms easier to understand and reason about.

Reduction With Signatures

Both SB and the classic Buchberger algorithm are based on reducing S-pairs. We first describe classic polynomial reduction and then describe SB's reduction in similar terms.

Classic polynomial reduction

Let f ∈ R and let t be a term of f . Then we can reduce t by g ∈ R if lt (g) |t or equivalently if

• there exists a monomial b such that lt (bg) = t.

The outcome of the reduction step is then f -bg and g is the reducer. It holds that lt (bg) ≤ lt (f ), but that is not listed as a requirement since it is implied. If lt (bg) ≃ lt (f ) then the reduction step is a top reduction step and otherwise it is a tail reduction step.

The result of classic polynomial reduction of f ∈ R is a polynomial h ∈ R that has been calculated from f through a sequence of reduction steps such that h cannot be further reduced. The reduction is a tail reduction if only tail reduction steps are allowed and it is a top reduction if only top reduction steps are allowed.

The implied condition that lt (bg) ≤ lt (f ) is equivalent to lt (fbg) ≤ lt (f ) so during classic polynomial reduction it is not allowed to increase the leading term. For tail reduction we perform only those reduction steps that do not change the leading term at all.

Signature reduction

Let α ∈ R m and let t be a term of α. Then we can s-reduce

t by β ∈ R m if
• there exists a monomial b such that lt bβ = t and

• s (bβ) ≤ s (α).
The outcome of the s-reduction step is then αbβ and β is the s-reducer. The second condition is analogous to the implied condition lt (bg) ≤ lt (f ) from classic polynomial reduction, the condition is just lifted to R m so that it involves signatures. When β s-reduces t we also say for convenience that bβ s-reduces α. That way b is introduced implicitly instead of having to repeat the equation lt bβ = t.

Just as for classic polynomial reduction, if lt bβ ≃ lt (α) then the s-reduction step is a top s-reduction step and otherwise it is a tail s-reduction step. We need words for the analogous distinction for signatures, so if s (bβ) ≃ s (α) then the reduction step is a singular s-reduction step and otherwise it is a regular s-reduction step.

The result of s-reduction of α ∈ R m is a γ ∈ R m that has been calculated from α through a sequence of s-reduction steps such that γ cannot be further s-reduced. The reduction is a tail s-reduction if only tail s-reduction steps are allowed and it is a top s-reduction if only top s-reduction steps are allowed. The reduction is a regular s-reduction if only regular s-reduction steps are allowed. A module element α ∈ R m is s-reducible if it can be s-reduced. If α sreduces to γ and γ is a syzygy then we say that α s-reduces to zero even if γ = 0.

As for classic polynomial reduction, the implied condition lt bβ ≤ lt (α) is equivalent to lt αbβ ≤ lt (α), so during s-reduction it is not allowed to increase the leading term. For tail s-reduction we perform only those s-reduction steps that do not change the leading term at all. Analogously, the condition s (bβ) ≤ s (α) is equivalent to s (αbβ) ≤ s (α), so during s-reduction it is not allowed to increase the signature. For regular s-reduction, we perform only those s-reduction steps that do not change the signature at all.

Classic reduction is always with respect to a finite basis B ⊆ R. The reducers in classic polynomial reduction are chosen from the basis B. Analogously, s-reduction is always with respect to a finite basis G ⊆ R m . The s-reducers in s-reduction are chosen from the basis G.

G is a signature Gröbner basis in signature T if all α ∈ R m with s (α) = T s-reduce to zero. G is a signature Gröbner basis up to signature T if G is a signature Gröbner basis in all signatures L such that L < T . G is a signature Gröbner basis if it is a signature Gröbner basis in all signatures.

SB computes a signature Gröbner basis. If G is a signature Gröbner basis then {α |α ∈ G } is a Gröbner basis of g1, . . . , gm , so we can use SB to compute Gröbner bases.

S-pairs and Syzygies

Let f, g ∈ R and let c .

.= gcd(lt (f ) , lt (g)) be the monic greatest common divisor of lt (f ) and lt (g). In the classic Buchberger algorithm the S-polynomial between f and g is

lt (g) c f - lt (f ) c g.
The classic Buchberger algorithm proceeds by reducing Spolynomials. If an S-polynomial reduces to h = 0 then h is added to the basis so that the S-polynomial now reduces to zero by this larger basis. The classic Buchberger algorithm terminates once all S-polynomials between elements of the basis reduce to zero. The SB algorithm works the same way except that these computations are lifted from R to R m in the following way. Let α, β ∈ R m and let c . .= gcd(lt (α) , lt β ) be the monic greatest common divisor of lt (α) and lt β . The S-pair between α and β is

S (α, β) . .= lt β c α - lt (α) c β. If s lt(β) c α ≃ s lt(α)
c β then the S-pair is singular and otherwise it is regular. By "S-pair" we always mean "regular S-pair". Observe that S (α, β) ∈ R m and that S (α, β) is the S-polynomial between α and β. SB proceeds by s-reducing S-pairs. If an S-pair s-reduces to γ and γ is not zero then γ is added to the basis. Theorem 3 implies that if all S-pairs and all ei s-reduce to zero then the basis is a signature Gröbner basis. A signature Gröbner basis is minimal if no basis element top s-reduces any other basis element. Theorem 5 implies that the minimal signature Gröbner basis is unique and is contained in all signature Gröbner bases up to sig-lead pairs. SB computes a minimal signature Gröbner basis.

Theorem 5. Let A be a minimal signature Gröbner basis and let B be a signature Gröbner basis of g1, . . . , gm. Then SimpleSignatureBasisAlgorithm({g1, . . . , gm} ⊆ R)

G ← ∅ (G will be the signature Gröbner basis) P ← {e1, . . . , em} (P is the set of pending reductions) H ← 0 ⊆ R m (H will be the initial module of syzygies) while P = ∅ do p ← an element of P with ≤-minimal signature it holds for all α ∈ A that there exists a non-zero scalar c ∈ κ and a β ∈ B such that s (α) = c s (β) and lt (α) = c lt β .

P ← P \ {p} p ′ ← result of regular s-reducing p if p ′ = 0 then H ← H + s (p ′ ) else if p ′ is not singular top reducible then P ← P ∪ {S (α, p ′ ) |α ∈ G and S (α, p ′ ) is regular } G ← G ∪ {p ′ } end if end while return (G, H)
We can extract a Gröbner basis from a signature Gröbner basis, but that is not the only reason to be interested in signature Gröbner bases. It is also possible to extract a Gröbner basis of the syzygy module of the input basis {g1, . . . , gm} from a signature Gröbner basis. Note that this is the syzygy module of the input basis rather than the syzygy module of a Gröbner basis of the same ideal. The former is in general much harder to compute than the latter.

The key to computing the syzygy module is Theorem 6 which implies that we can determine the initial module of the module of syzygies from looking at those S-pairs and ei that regular s-reduce to zero. If we are computing with full elements of R m (as opposed to sig-poly pairs) and we have stored the syzygies that were computed (as opposed to storing just their signatures) then those syzygies will form the minimal Gröbner basis of the syzygy module. Theorem 6. Let α ∈ R m be a syzygy and let G be a signature Gröbner basis up to signature s (α). Then there exists a β ∈ R m with s (β) | s (α) such that β is an S-pair or has the form ei and such that β regular s-reduces to zero.

Figure 1 contains pseudo code for a simple version of SB that returns a signature Gröbner basis G and and also the initial submodule H of the syzygy module of g1, . . . , gm. This pseudo code is intended to succinctly state the essence of SB without getting bogged down in any of the complexities of implementation on a computer. Among many other things, a reasonable implementation would use criteria to eliminate S-pairs (see Section 2.4) and use the sig-poly pair optimization (see Remark 2).

We stated that SB proceeds by s-reducing S-pairs and then adding the s-reduced result to the basis if it is not a syzygy. In Figure 1 we regular s-reduce the S-pair p and then add the regular s-reduced result p ′ to the basis if it is not a syzygy and not singular s-reducible. The reason for this is that if p ′ is singular s-reducible then s-reduction of p ′ is going to s-reduce p ′ to zero anyway so we might as well not spend the time on doing that s-reduction.

S-Pair Elimination

Three things can happen when SB regular s-reduces an S-pair in signature T and gets a result γ ∈ R m .

Syzygy If γ is a syzygy then T is recorded in H.
Singular If γ is singular top s-reducible then γ s-reduces to zero so γ is discarded.

Basis Otherwise γ is recorded in G as a new basis element.

For these three cases T is respectively a syzygy, singular or basis signature. This is well defined due to Lemma 4.

If L is a syzygy signature and L|T then T is also a syzygy signature. SB eliminates an S-pair p by the signature criterion if s (p) ∈ H since then s (p) is syzygy.

The Koszul syzygy between α, β ∈ G is K (α, β) . .= βααβ. If s βα ≃ s (αβ) then the Koszul syzygy is regular. By "Koszul syzygy" we always mean "regular Koszul syzygy". SB eliminates an S-pair p by the Koszul criterion if there exists a Koszul syzygy σ such that s (p) = s (σ). In this case s (p) is recorded in H since s (p) is syzygy.

A signature T is predictably syzygy if s (p) = s (σ) for a Koszul syzygy σ or if there exists a syzygy σ ∈ R m such that s (σ) < T and s (σ) |T . The combined effect of the signature criterion and the Koszul criterion is to eliminate all S-pairs in predictably syzygy signatures.

If there are two or more S-pairs in the same signature T , then we only have to regular s-reduce one of them as they all regular s-reduce to the same thing by Lemma 4. Since s-reduction proceeds by decreasing the lead term, we can speed up the process by choosing an S-pair p in signature T whose lead term lt (p) is minimal. If s (S (α, β)) = s (aα), then we get the same result from regular s-reducing S (α, β) as for regular s-reducing aα. So we should choose the aα ∈ M with minimal lead term lt (aα), where M is the set {aα |α ∈ G, a is a monomial and s (aα) = T } .

Note that α might not be involved in any S-pair in signature T . If aα is not regular top s-reducible, then T is a singular signature. In this case RB eliminates all the S-pairs in signature T by the singular criterion. The effect of the singular criterion is to eliminate all S-pairs in singular signatures.

THE REWRITE BASIS ALGORITHM

In this section we introduce the RB algorithm, which is simpler than yet equivalent to F5GEN [START_REF] Pan | The Termination of Algorithms for Computing Gröbner Bases[END_REF]. Our motivation for studying RB is that it contains many published algorithms as special cases including SB and F5.

The difference between RB and SB is that RB uses the concept of rewriting instead of the concept of singular sreduction. This has two main consequences. First, RB uses a different criterion for eliminating S-pairs. Second, RB adds a regular s-reduced α ∈ R m to the basis even if α is singular top s-reducible. SB does not add such α to the basis because such α s-reduce to zero anyway. RB must add such α to the basis because rewriting requires it.

RB is parametrized by a rewrite order. Despite the differences between RB and SB, PHW [START_REF] Pan | The Termination of Algorithms for Computing Gröbner Bases[END_REF] show that GVWHS (and hence SB) is an instantiation of F5GEN (and hence RB). We simplify their proof in the setting of SB and RB and extend the result to say that SB is the best possible instantiation of RB in the sense of Theorem 13.

Figure 2

Rewriting and S-pair Elimination

Let be a rewrite order, which means that is a total order on G such that s (α) | s (β) ⇒ α β. Such an order always exists due to our assumption that s (α) ≃ s (β) ⇒ α = β. A basis element α ∈ G is a rewriter in signature T if s (α) |T . If s (aα) = T for a monomial a we also say for convenience that aα is a rewriter of T . The -maximal rewriter in signature T is the canonical rewriter. A basis element multiple aα is rewritable if α is not the canonical rewriter of s (aα). An S-pair aαbβ is eliminated by RB if aα is predictably syzygy or rewritable, or if bβ is predictably syzygy or rewritable.

Note that RB's S-pair elimination criterion applies equally to both components aα and bβ of an S-pair aαbβ. No criterion in SB can eliminate an S-pair based on s (bβ) where s (aα) > s (bβ). Can RB eliminate some S-pairs that RB cannot due to this difference? Since both SB and RB regular s-reduce at most one S-pair in any given signature, what matters is the ability to eliminate all S-pairs in a signature. We will prove that SB has a stronger S-pair elimination criterion than RB does in the sense that if SB must regular s-reduce an S-pair in a signature then so must RB.

Rewrite bases

G is a rewrite basis in signature T if the canonical rewriter in signature T is not regular top s-reducible or if T is a syzygy signature. G is a rewrite basis up to signature T if G is a rewrite basis for all signatures L such that L < T . G is a rewrite basis if it is a rewrite basis in all signatures. We prove Theorem 7 later in this section.

Theorem 7. RB computes a rewrite basis.

Lemma 8. If G is a rewrite basis up to signature T then G is also a signature Gröbner basis up to signature T .

Proof. Suppose to get a contradiction that G is a rewrite basis up to signature T but that it is not a signature Gröbner basis up to signature T . Since the monomial order is a well-order there exists an α ∈ R m with minimal signature s (α) < T such that α does not s-reduce to zero. Then G is a signature basis up to signature s (α) and it is a rewrite basis in signature s (α).

Let β be the result of regular s-reducing α and let cγ be the canonical rewriter in signature s (α). Then s (cγ) = s (β) and both cγ and β are not regular top s-reducible, so lt (cγ) = lt β by Lemma 4. Perform the singular sreduction step βcγ. Since s (βcγ) < s (α) and G is a signature Gröbner basis up to signature s (α) we then get that βcγ s-reduces to zero. Hence α s-reduces to zero which is a contradiction.

SB computes a minimal signature Gröbner basis so the SB basis is a subset of the RB basis up to sig-poly pairs. Both SB and RB have to perform a regular s-reduction in all syzygy signatures that are not predictably syzygy, so there are no differences between the two algorithms in terms of how many S-pairs are reduced to zero. For non-syzygy signatures T , both algorithms will add an element to the basis with signature T if and only if they reduce an S-pair in signature T . 1 This implies that if SB regular s-reduces an S-pair in signature T then so does RB. In other words, the Spairs reduced by SB form a subset of the S-pairs reduced by RB up to signature. If A is the basis computed by SB and B is the basis computed by RB, then RB regular s-reduced |B| -|A| ≥ 0 more S-pairs than SB did. If |A| = |B| then SB and RB reduced the same S-pairs up to signature.

Our proof of Theorem 7 is based on the following series of lemmas. Lemma 10 connects S-pairs to rewrite bases. Lemma 11 is an important technical lemma that we use here to construct S-pairs and which we use again in Section 4.1. Lemma 12 gives a precise criterion for when RB regular s-reduces an S-pair in a signature. Lemma 9. Let G be a rewrite basis up to signature T . Let aα be the canonical rewriter in signature T and let bβ be a regular top s-reducer of aα. Then S (α, β) = aαbβ and s (S (α, β)) = T .

Proof. If g .

.= gcd(a, b) then aαbβ = gS (α, β). Suppose to get a contradiction that g = 1. Let cγ be the canonical rewriter in signature T g . Then γ α since a g α is a rewriter in signature T g . Also γ α since gcγ is a rewriter in signature T . Hence α = γ. This is a contradiction since then b g β is a regular top s-reducer of a g α = cγ but cγ is not regular top s-reducible.

Lemma 10. G is a rewrite basis up to signature T if G is a rewrite basis in all signatures s (p) < T where p is an S-pair or p = ei.

Proof. Suppose to get a contradiction that G is not a rewrite basis up to signature T . Since the module monomial order < is a well-order there exists a minimal non-syzygy signature L < T such that G is not a rewrite basis in signature L. Then G is a rewrite basis up to signature L. Then there exists an S-pair with signature L by Lemma 9 so G is a rewrite basis in signature L which is a contradiction. Lemma 11. Let α ∈ R m , let G be a rewrite basis up to signature s (α) and let t be a regular s-reducible term of α. Let M be the set of cγ that regular s-reduce t. Let bβ be the canonical rewriter in signature L . .= mincγ∈M s (cγ). Then • bβ is a regular s-reducer of t,

• bβ is not regular top s-reducible,

• bβ is not rewritable and • s (bβ) is not syzygy.

Proof. bβ is the canonical rewriter in signature L < s (α) and G is a rewrite basis up to signature s (α), which establishes the two middle statements.

bβ ∈ M : Let cγ ∈ M such that s (cγ) = L. Suppose to get a contradiction that dδ regular top s-reduces cγ. Then lt dδ = lt (cγ) = t and s (dδ) < s (cγ) < s (α), so dδ ∈ M and s (dδ) < L which is a contradiction. Then lt bβ = lt (cγ) = t by Lemma 4 so bβ ∈ M . s (bβ) is not syzygy: Suppose to get a contradiction that there exists a syzygy σ such that s (σ) = s (bβ). Since s (bβσ) < s (α) there exists a top s-reducer cγ of bβσ. Then s (cγ) ≤ s (bβσ) < s (bβ) so cγ is a regular top s-reducer of bβ but bβ is not regular top s-reducible.

Lemma 12. Let G be a rewrite basis up to signature T . Let aα be the canonical rewriter in signature T . Then RB s -reduces an S-pair in signature T if and only if aα is regular top s-reducible and T is not predictably syzygy.

Proof. if: Let bβ be the regular top s-reducer of aα from Lemma 11 so that bβ is not rewritable and s (bβ) is not predictably syzygy. Then S (α, β) = aαbβ by Lemma 9 and this S-pair is not eliminated by RB.

only if: Let S (α, β) = aαbβ such that T = s (aα) > s (bβ) and such that RB does not eliminate S (α, β). The latter implies that aα is the canonical rewriter in signature T and that T is not predictably syzygy. Observe that aα is regular top s-reducible since bβ regular top s-reduces it.

Proof of Theorem 7. Suppose that RB has terminated with the basis G. Suppose to get a contradiction that p is an S-pair such that G is not a rewrite basis in signature s (p). Let aα be the canonical rewriter in signature s (p). Then aα is regular top s-reducible and s (aα) = s (p) is not syzygy, so RB has reduced an S-pair in signature s (p) by Lemma 12. Then RB has also added a basis element β with signature s (p) whereby β = aα is the canonical reducer in signature s (p). This is a contradiction since β is not regular top s-reducible. Then G is a rewrite basis by Lemma 10.

SB is the Best Possible Instantiation of RB

Let the sig-lead ratio order r be the order on G such that α r β if rα ≤ r β or if rα = r β and s (α) ≤ s (β).

Theorem 13. RB is equivalent to SB when using the sig-lead ratio rewrite order. If RB uses any other rewrite order, then SB computes a basis that is a subset of the basis computed by RB up to sig-poly pairs and SB regular s-reduces a subset of the S-pairs regular s-reduced by RB up to signature.

Proof. Let RB use r for rewriting and let G be the minimal signature Gröbner basis. We will prove that r is a rewrite order and that G is a rewrite basis. Then RB computes G as it only regular s-reduces an S-pair in a non-syzygy signature T if the basis is not already a rewrite basis in signature T . Thus SB and RB compute the same basis and then the result follows from the statements in Section 3.2.

r is a rewrite order: If s (α) | s (β) then rα ≤ r β by Lemma 14 and s (α) ≤ s (β) so α r β.

G is a rewrite basis: Let aα be a canonical rewriter. We need to prove that aα is not regular top s-reducible. Let γ be the result of regular s-reducing aα. G is a signature Gröbner basis, so there exists a bβ that singular top s-reduces γ. Then rα ≤ r β by Lemma 14 so α = β.

Lemma 14. Let G be a signature Gröbner basis up to signature s (aα) = s (bβ) where α, β ∈ G and a, b are monomials. If bβ is not regular top s-reducible then rα ≤ r β .

Proof. Let γ be the result of regular s-reducing aα. bβ and γ are not regular top s-reducible so lt (aα) ≥ lt (γ) = lt bβ by Lemma 4. Also s (γ) = s (aα) = s (bβ), so

rα = s (aα) lt (aα) ≤ s (γ) lt (γ) = s (bβ) lt bβ = r β .

RB5 -BRINGING RB CLOSER TO F5

In this section we define RB5, which is a special case of RB. RB5 is more similar to F5 than RB is. We will show why the differences between RB5 and RB are not significant, except for the fact that RB is more general. In Section 5 we resolve the differences between RB5 and F5, which completes our proof that F5 is a special case of RB.

RB5 is specialized from RB in three main ways. First, the module monomial order must be position-first, which means that if i < j then aei < bej for all monomials a, b ∈ R. Second, the input basis elements g1, . . . , gm must form a regular sequence. Third, the rewrite order must be the F5 rewrite order 5. Let aei .

.= s (α) and s (bej) . .= β. Then α 5 β if i < j or if i = j and total degree of a is strictly smaller than the total degree of b. Break ties arbitrarily.

Reduction in RB5

Let α ∈ R m and let t be a term of α. We can r-reduce t by a basis element β ∈ G if

• there exists a monomial b such that lt bβ = t,

• s (bβ) < s (α),

• s (bβ) is not syzygy and

• bβ is not rewritable.
The outcome of the r-reduction step is then αbβ and β is the r-reducer. When β r-reduces a term of α we also say for convenience that bβ r-reduces α. If t = lt (α) then the r-reduction step is a top r-reduction step.

The first condition on r-reducers is the same as for sreduction. The second condition requires < where s-reduction requires only ≤, so r-reduction is implicitly regular. The final two conditions are not used by RB. In Section 5.3 we motivate these extra conditions in terms of S-pair elimination. All r-reducers are regular s-reducers but not vice versa.

Lemma 15. Let α ∈ R m , let t be a term of α and let G be a rewrite basis up to signature s (α). Then t is regular s-reducible if and only if t is r-reducible

Proof. If t is regular s-reducible then by Lemma 11 there exists a regular s-reducer bβ of t such that s (bβ) is not syzygy and bβ is not rewritable. So bβ is an r-reducer.

During regular s-reduction there can be a choice of which regular s-reducer to use. Lemma 15 shows that the effect of the extra conditions imposed on r-reducers is to exclude some of the s-reducers from consideration, but it is never the case that all of the s-reducers are excluded. The outcome of regular s-reduction does not depend on the choice of sreducer up to sig-poly pairs, which proves Corollary 16.

Corollary 16. Let α ∈ R m and let G be a rewrite basis up to signature s (α). Let αs be the result of regular s-reducing α and let αr be the result of r-reducing α. Then s (αs) = s (αr) and αs = αr.

S-pair elimination in RB5

Due to the extra assumptions on the input, RB5 can eliminate all S-pairs that reduce to zero by considering only the Koszul syzygies. This is stated already in the F5 paper [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero F5[END_REF]. RB uses condition (2) of Theorem 17 while RB5 uses condition (4). Theorem 17 implies that these two are equivalent.

Theorem 17. Let G be a signature Gröbner basis up to signature ei. Assume that the input basis element gi is not a zero divisor of R/ g1, . . . , gi-1 . Assume that the module monomial order < on R m has the property that bej < aei < ce k for all j, k such that j < i < k and for all monomials a, b, c ∈ R. Then the following statements are equivalent for all monomials a ∈ R.

1. The signature aei is syzygy.

2. The signature aei is predictably syzygy.

3. ∃α ∈ G : ind (α) < i and s (K (ei, α)) |aei. .= g1, . . . , gi-1 . That (3) ⇒ (2) ⇒ (1) is immediate. G is a Gröbner basis of F : If α ∈ G then αj = 0 for j ≥ i so it is immediate that G ⊆ g1, . . . , gi-1 . To prove the other inclusion, let f ∈ F . We need to prove that f reduces to zero on classic polynomial reduction by G.

There exists an α ∈ R m such that f = α and αj = 0 for j ≥ i. Then ind (α) < i so s (α) < ei whereby α s-reduces to zero when s-reducing by G. All the s-reducers γ ∈ G in that s-reduction must have s (γ) ≤ s (α) whereby ind (γ) < i. Thus α also s-reduces to zero when s-reducing by G. Then α = f reduces to zero on classic polynomial reduction by G.

(1) ⇒ (4): Let β ∈ R m be a syzygy such that s (β) = aei. Then βj = 0 for all j > i whereby βigi ∈ F since

0 = β = m j=1 βjgj = βigi + i-1 j=1 βjgj.
Hence βi ∈ F as gi is not a zero divisor. As G is a Gröbner basis of F there exists an α ∈ G such that lt (α) | lt (βi) = a.

(4) ⇒ (3): Let α ∈ G such that ind (α) < i and lt (α) |a. By definition K (ei, α) = αei-giα. As lt (α) ei > lt (gi) s (α) we see that s (K (ei, α)) = lt (α) ei|aei.

φi ∈ G reduced from lt φi s (φi)

φ1 e1 y 3 e1 φ2 e2 xyz e2 φ3 y 2 φ2 -xzφ1 = S (φ2, φ1) x 3 z 2 y 2 e2 φ4 e3 yz 2 e3 φ5 xφ3 -zφ2 = S (φ3, φ2) xz 3 xe3 φ6 y 2 φ3 -z 2 φ1 = S (φ3, φ1) x 2 z 3 y 2 e3 φ7 yφ5 -z 2 φ2 = S (φ5, φ2) x 2 y 2 t xye3 φ8
xφ5 -φ6 = S (φ5, φ6) z 5

x 2 e3 φ9 xφ6 -zφ3 = S (φ6, φ3) x 4 zt xy 2 e3 φ10 yφ8z 3 φ4 = S (φ8, φ4) x 3 y 2 t x 2 ye3 φ11

x 3 φ4 -yφ3 = S (φ4, φ3) x 4 yt x 3 e3 φ12 zφ11x 3 φ2 = S (φ11, φ2)

x 3 zt 3 x 3 ze3 φ13 yφ10x 3 φ1 = S (φ10, φ1)

x 5 zt x 2 y 2 e3 φ14 xφ12 -φ9 = S (φ12, φ9) x 4 t 4 x 4 ze3

Examples

Example 18 shows a homogeneous ideal where RB5 (and hence F5) computes a larger basis than SB does. Example 19 shows details of how RB5 computes a basis.

Example 18. Consider the homogenized Eco-6 ideal using the graded reverse lexicographic monomial order. Here RB5 computes a basis with 100 elements while SB computes a basis with 87 elements. Both RB5 and SB compute a basis element α with s (α) = x0x2e5. RB5 additionally computes basis elements β and γ with s (β) = x0x2x 2 3 e5 and s (γ) = x0x2x3x4e5. As β and γ are not necessary to have a signature Gröbner basis, we can replacing them with a single element with signature x0x2x3e5 and thus get a rewrite basis that contains fewer elements than the basis computed by RB5. Furthermore, the basis computed by SB is not a rewrite basis with respect to the F5 rewrite order.

Example 19. Let κ be the finite field with 13 elements and let R .

.= κ[x, y, z, t]. Let < be the graded reverse lexicographic monomial order. Consider the three input elements g1 .

.= -2y 3x 2 z -2x 2 t -3y 2 t, g2 . .= 3xyz + 2xyt, g3 .

.= 2xyz -2yz 2 + 2z 3 + 4yzt. Figure 3 shows the r-reductions performed by RB5 to compute the rewrite basis {φ1, . . . , φ14}. SB regular s-reduce the same S-pairs except for the ones that lead to φ10 and φ13, so the basis computed by SB contains 12 elements. The S-pair S (φ8, φ4) leads to φ10 and it is eliminated by the singular criterion since s (xφ7) = s (S (φ8, φ4)) and xφ7 is not regular top s-reducible. The S-pair S (φ10, φ1) leads to φ13 and it is not considered by SB since φ10 is not part of SB's basis.

F5 IS EQUIVALENT TO RB5

The F5 paper [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero F5[END_REF] assumes that the input basis elements g1, . . . , gm are homogeneous. In this section we show that F5 and RB5 become the same algorithm with this assumption.

The Sig-Poly Pair Optimization

The notation for RB5 concerns elements α ∈ R m while the F5 paper uses notation based on sig-poly pairs (s (α) , α). We believe that the SB notation makes signature computations easier to understand and reason about. However, the cost in time and space for computations on elements of R m is higher than for sig-poly pairs.

Consider that RB5 never performs singular s-reduction steps, so we never need to know any of the terms in R m other than the leading one -the signature. The singular s-reduction steps appear only in theorems and proofs. So it is possible to apply the sig-poly pair optimization when implementing RB5 (and RB and SB), which involves replacing α ∈ R m with the sig-poly pair (s (α) , α). In F5 this idea is used in the notation while in RB5 we present it as an optimization. The outcome is the same.

F5 maintains a list of rewriting rules

The F5 paper [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero F5[END_REF] does not contain the phrases "canonical rewriter" and "rewrite order". Instead, there is a pseudo code function named Rewritten that takes a signature as a parameter and returns the canonical rewriter in that signature. The concept of the canonical rewriter is thus represented implicitly in the F5 paper as that thing which Rewritten returns. We do not specify how the F5 rewrite order breaks ties since F5's implicit rule for this seems more an arbitrary outcome of how the pseudo code was written than an intentional choice (it is not a function of signature).

In F5 there is a list of rewriting rules. A rewriting rule is added to the front of the list when an S-polynomial is calculated. When Rewritten is called, it goes through the rewriting rules and returns the first rewriter it finds. The first rewriter found is also the rewriter that was most recently added to the basis. S-polynomials are only calculated for S-pairs whose signature has the current index and the current total degree, so the rewriting rules are added to the front of the list first in order of index of the signature and then in order of total degree of the signature. This proves that F5 is indeed implicitly using what we have called the F5 rewrite order.

The only exception to this description is that F5 does not record α ∈ G into the list of rewriters if s (α) ≃ ei. However, this does not change whether a basis element multiple is rewritable, so this difference does not change the algorithm.

F5 is written to resemble F4 reduction

F4 is an algorithm that speeds up classic polynomial reduction by using a symbolic preprocessing step to turn the reduction of many polynomials into row reduction of a single matrix [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF]. The more reductions in the same homogeneous degree that can be done at the same time, the larger the matrix becomes and the more of a speed up there is from using F4 over using classic polynomial reduction. Albrecht and Perry describe a variation of F5 that uses F4 reduction [1].

The pseudo code in the F5 paper is written without F4 reduction. However, it is still written in a way that heavily suggests how to adapt the symbolic preprocessing step from F4 to F5. For example, the F5 pseudo code is written to process all S-pairs in a homogeneous degree at the same time, which is important when using F4. This is done by having a set P of all S-pairs in the current homogeneous degree. In F4 r-reduction of all the S-pairs in P would then be carried out simultaneously within one big matrix.

The above scheme for r-reducing all S-pairs in a homogeneous degree does not succeed in getting all of the S-pairs in that homogeneous degree. When reducing an S-pair to a new basis element α, it is possible that α can form an S-pair in the same homogeneous degree with another basis element.

Since F5 requires the input ideal to be homogeneous, this happens if and only if there is another basis element β such that bβ would top r-reduce α except that s (bβ) > s (α). Call such an S-pair S (β, α) a late S-pair. The late S-pairs will not initially be included in P since they only appear after some r-reductions have already been carried out. This is unfortunate when using F4 r-reduction because for F4 r-reduction we want to identify all of the S-pairs in each homogeneous degree up front -including the late ones.

In F5 there is a mechanism for discovering late S-pairs while r-reducing another S-pair. The mechanism is that F5 allows reducers to increase the signature of the reduction. In that case F5 will split the r-reduction into two r-reductions -one r-reduction in the old signature that continues to be carried out and another r-reduction in the new signature that is recorded in P . These higher signature r-reductions are precisely the late S-pairs and this mechanism would allow an F4 version of F5 to get all the S-pairs in a degree before doing any r-reduction. Note that it is possible for such a variant of F5 to detect more late S-pairs than actually exist because the symbolic preprocessing step does not take account of cancellations.

We have seen that the only effect of F5's higher signature reducers is to indicate how to translate F5 into a variant that uses F4 reduction. The pseudo code for reduction in F5 looks different from r-reduction because that pseudo code is not just doing r-reduction -it is also constructing late Spairs. This also explains the purpose of the extra conditions on r-reducers -they are S-pair elimination criteria. So what F5 is doing remains equivalent to r-reduction, which proves that F5 is a special case of RB5 despite F5's highersignature reducers and its multiple results of reduction.

TERMINATION OF RB AND HENCE F5

The proof of termination in the F5 paper [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero F5[END_REF] is incorrect. Proving termination of F5 had been an open problem for a decade before it was settled by Galkin [START_REF] Galkin | Termination of original F5[END_REF]. PHW later proved that F5GEN (and hence RB) terminates [START_REF] Pan | The Termination of Algorithms for Computing Gröbner Bases[END_REF], which implies that F5 terminates. Our proof of termination is similar to but significantly simpler than Galkin's and PHW's.

Theorem 20. The RB algorithm terminates.

Proof. Let φ1, φ2, . . . be the sequence of basis elements computed by RB and let G .

.= {φ1, φ2, . . .}. RB processes Spairs in increasing order of signature so s (φ1) < s (φ2) < • • • . Partition G into sets Rr . .= {φi |r φ i = r }. We prove that there are only finitely many non-empty sets Rr and that each Rr is finite. Hence G is finite whereby RB terminates.

Only finitely many Rr are non-empty: If α ∈ G then Gα .

.= {β ∈ G |s (β) < s (α) } is a signature Gröbner basis up to signature s (α). Call α ∈ G minimal if there is no other β ∈ G such that s (β) | s (α) and lt β | lt (α). It follows from Lemma 21 that a non-minimal α ∈ G is top s-reducible by Gα. No basis element in RB is regular top s-reducible, so if α ∈ G is non-minimal, then α must be singular top s-reducible by Gα. Thus there exists a β ∈ Gα and a monomial m ≃ 1 such that s (mβ) = s (α) and lt mβ = lt (α) whereby α and β lie in the same set Rr. This shows that there are exactly as many non-empty sets Rr as there are minimal basis elements in G. Both R and R m are Noetherian, so there are only finitely many minimal basis elements. Hence there are also only finitely many non-empty sets Rr.

Each Rr is finite: We prove by induction on the finitely many non-empty sets Rr that each Rr is finite. Assume by induction that all sets R r ′ with r ′ < r are finite. We need to prove that Rr is finite. The base case is immediate.

Let γ ∈ Rr and let S (α, β) = aαbβ be the S-pair that RB regular s-reduced to get γ where s (aα) > s (bβ). Let c be the monic greatest common divisor of lt (α) and lt β . Then 1 c lt β s (α) = s (aα) > s (bβ) = 1 c lt (α) s (β) so rα > r β . Also lt (γ) < lt (aα) and s (γ) = s (aα) so

Hence α ∈ R r ′ and β ∈ R r ′′ where r ′ , r ′′ < r, so Rr contains at most as many elements as there are pairs of elements in the set ∪ r ′ <r R r ′ which is finite by induction. There may also be one more element with signature ei since those elements do not come from S-pairs. So by induction Rr is finite.

Lemma 21 (Eder and Perry [START_REF] Eder | Signature-based Algorithms to Compute Gröbner Bases[END_REF]). Let α ∈ R m and let G be a signature Gröbner basis up to signature s (α). If there exists a β ∈ G such that lt β | lt (α) and s (β) | s (α) then α is top s-reducible by G.

Theorem 3 .Lemma 4 .

 34 Let T be a module monomial of R m and let G ⊆ R m be a finite basis. Assume that all S-pairs p . .= S (α, β) with α, β ∈ G and s (p) < T s-reduce to zero and all ei with ei < T s-reduce to zero. Then G is a signature Gröbner basis up to signature T . The outcome of classic polynomial reduction depends on the choice of reducer, so the choice of reducer can change what the intermediate bases are in the classic Buchberger algorithm. Lemma 4 implies that all S-pairs with the same signature yield the same regular s-reduced result as long as we process S-pairs in order of increasing signature. Let α, β ∈ R m and let G be a signature Gröbner basis up to signature s (α) = s (β). If α and β are both regular top s-reduced then lt (α) = lt β or α = β = 0. If α and β are both regular s-reduced then α = β.

Figure 1 :

 1 Figure 1: Pseudo code for a simple version of SB.

Figure 2 :

 2 Figure 2: Pseudo code for a simple version of RB.

4 .

 4 ∃α ∈ G : ind (α) < i and lt (α) |a. Proof. Let G . .= {α ∈ G |ind (α) < i }, G . .= {α |α ∈ G } and F .

Figure 3 :

 3 Figure 3: Computations for RB5 in Example 19.

  contains pseudo code for a simple version of RB. SimpleRewriteBasisAlgorithm({g1, . . . , gm} ⊆ R) G ← ∅ (G will be the rewrite basis) P ← {e1, . . . , em} (P is the set of pending reductions) H ← 0 ⊆ R m (H will be the initial module of syzygies) while P = ∅ do p ← an element of P with ≤-minimal signature P ← P \ {p} if not RBEliminated(p) then p ′ ← result of regular s-reducing p if p ′ = 0 then H ← H + s (p ′ ) else P ← P ∪ {S (α, p ′ ) |α ∈ G and S (α, p ′ ) is regular } G ← G ∪ {p ′ } (insert p ′ into the basis even when p ′ RBEliminated(S-pair aαbβ ∈ R m ) if aα is rewritable or aα is predictably syzygy then return true (eliminate S-pair) end if if bβ is rewritable or bβ is predictably syzygy then return true (eliminate S-pair) end if return false (do not eliminate S-pair)

	is singular top s-reducible)
	end if
	end if
	end while
	return (G, H)

If an S-pair p regular s-reduces to p ′ then it is true that SB will not add p ′ to the basis if p ′ is singular top s-reducible. However, the singular criterion always eliminates such Spairs p before the regular s-reduction happens.


Sonia Ben Ticha
email: sonia.benticha@loria.fr

Azim Roussanaly
email: azim.roussanaly@loria.fr

Anne Boyer
email: anne.boyer@loria.fr

Khaled Bsaïes
email: khaled.bsaies@fst.rnu.tn

Feature Frequency Inverse User Frequency for Dependant Attribute to Enhance Recommendations

Keywords: hybrid recommender system, collaborative filtering, TF-IDF

Recommender system provides relevant items to users from huge catalogue. Collaborative filtering and contentbased filtering are the most widely used techniques in personalized recommender systems. Collaborative filtering uses only the user-ratings data to make predictions, while content-based filtering relies on semantic information of items for recommendation. The aim of this work is to introduce the semantic aspect of items in a collaborative filtering process in order to enhance recommendations. Many works have addressed this problem by proposing hybrid solutions. In this paper, we present another hybridization technique that predicts users preferences for items based on their inferred preferences for semantic information of items. For this, we propose a new approach to build user semantic model by using TF-IDF measure and we provide solution to reduce the dimension of data. Applying our approach to real data, the MoviesLens 1M dataset, significant improvement can be noticed compared to usage only approach, Content only approach and hybrid algorithm.

I. INTRODUCTION

Recommender Systems (RS) provide relevant items to users from a large number of choices. Several recommendations techniques exist in the literature. Among these techniques, there are those that provide personalized recommendations by defining a profile for each user. In this work, we are interested in personalized recommender systems where the user model is based on an analysis of usage. This model is usually described by a user-item ratings matrix, which is extremely sparse (≥ 90% of missing data).

Collaborative Filtering (CF) and Content-Based (CB) filtering are the most widely used techniques in RS. The fundamental assumption of CF is that if users X and Y rate n items similarly and hence will rate or act on other items similarly [START_REF] Su | A survey of collaborative filtering techniques[END_REF]. CB filtering assumes that each user operates independently and user will be recommended items similar to the ones he preferred in the past [START_REF] Lops | Content-based recommender systems: State of the art and trends[END_REF]. The major difference between CF and CB recommender systems is that CF uses only the useritem ratings data to make predictions and recommendations, while CB relies on item content (semantic information) for recommendations. However, CF and CB techniques must face many challenges like the data sparsity problem, the scalability problem for large datasets with the increasing numbers of users.

To overcome the disadvantages of both techniques and benefit from their strengths, hybrid solutions have emerged. In this paper, we present a new approach taking into account the semantic information of items in a CF system. In our approach, we design a new hybridization technique, which predicts user preferences for items based on their inferred preferences for item content; and presents a solution to the sparsity and scalability problems. Our system consists of two components: the first builds a new user model, the user semantic model, by inferring user preferences for item content; the second computes predictions and provides recommendations by using the user semantic model in a user-based CF algorithm to calculate the similarity between users. The originality of this work is in the building of the user semantic model. Indeed, assuming that items are represented by structured data in which each item is described by a same set of attributes, we build a user semantic attribute model for each relevant attribute. With this aim, we define two classes of attributes: dependent and non dependent and we propose a suited algorithm for each class. User semantic model is then deducted from the horizontal concatenation of all user semantic attribute model. In previous works [START_REF] Ben Ticha | User semantic preferences for collaborative recommendations[END_REF], [START_REF] Ben Ticha | User Semantic Model for Hybrid Recommender Systems[END_REF] we have presented solutions based on machine learning algorithm to build a user semantic attribute model for non dependent attribute. In this work, we present a new approach for building a user semantic attribute model for dependent attribute based on TF/IDF measure. Due to the high number of attribute values, and to reduce the expensiveness of user similarity computing, we propose also a solution to reduce the size of the user semantic attribute model. We compare our results to the standards user-based CF, item-based CF, CB and hybrid algorithms. Our approach results in an overall improvement in prediction accuracy.

The rest of paper is organized as follows: Section II summarizes the related work. User semantic model is described in Section III. Section IV describes our approach to build user semantic attribute model for non dependent attribute. Section V describes the recommendation component of our system. Experimental results are presented and discussed in Section VI. Finally, we conclude with a summary of our findings and some directions for future work.

II. RELATED WORK

RS have become an independent research area in the middle 1990s. CF is the most widespread used technique in RS, it was the subject of several researches [START_REF] Resnick | Grouplens: an open architecture for collaborative filtering of netnews[END_REF], [START_REF] Sarwar | Item-based collaborative filtering recommendation algorithms[END_REF]. In CF, user will be recommended items that people with similar tastes and preferences liked in the past [START_REF] Adomavicius | Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[END_REF]. CB is another important technique; it uses techniques developed in information filtering research [START_REF] Pazzani | Content-based recommendation systems[END_REF]. CB assumes that each user operates independently and recommends items similar to the ones he preferred in the past. To overcome the disadvantages of both techniques and benefit from their strengths, several RS use a hybrid approach by combining CF and CB techniques. The Fab System [START_REF] Balabanovic | Fab: Content-based, collaborative recommendation[END_REF] counts among the first hybrid RS. Many systems have been developed since [START_REF] Burke | Hybrid web recommender systems[END_REF]. Most of these hybrid systems do not distinguish between attributes and treat their values in a same way. Moreover, because of the huge number of items and users, calculating the similarity between users in CF algorithm became very expensive in time computing. Dimension reduction of data is one of the solution to reduce the expensiveness of users similarity computing. Mobasher et al. [START_REF] Mobasher | Semantically enhanced collaborative filtering on the web[END_REF] combine values of all attributes and then apply a Latent Semantic Analysis (LSA) to reduce dimension of data. Sen et al. [START_REF] Sen | Tagommenders: connecting users to items through tags[END_REF] are inferring user preferences for only one attribute, the item' tags, without reducing dimension. Manzato [START_REF] Manzato | Discovering latent factors from movies genres for enhanced recommendation[END_REF] computes a user semantic model for only the movie genre attribute and applies a Singular Value Decomposition (SVD) to reduce the dimension of data. In our approach, we compute a user semantic attribute model for each relevant attribute and we propose a low cost solution to reduce the data dimension.

III. USER SEMANTIC MODEL

Pazzani et al. [START_REF] Pazzani | Content-based recommendation systems[END_REF] have identified three alternative item representations. Item can be represented by structured data in which there is a small number of attributes, each item is described by the same set of attributes, and there is a known set of values that each attribute may have, for instance, the attributes of a movie can be title, genres, actors and director; unstructured data such as news articles, abstract of movie, description of restaurant, is an unrestricted text in which there are no attribute names with well-defined values; or semistructured data in which there are some attributes with a set of restricted values and some free-text. In this paper, we are interested only to items described by structured data. The others representations will be addressed in future work. In the following, we will use the term feature to refer to an attribute value, for instance Documentary, Musical and Thriller are features of movie genre attribute.

A. Dependent and non Dependent attribute

In structured representation, each attribute has a set of restricted features. However, the number of features can be related or not to the number of items. That is why we have defined two classes of attributes:

• Dependent attribute: attribute, which having very variable number of features. This number is closely related to the number of items. So, when the number of items is increasing, the number of features is increasing also. For example: directors and actors of movies, user tags.

• Non dependent attribute: attribute, which having a very few variable number of features, and this number is not related to the number of items. Thus, the increasing number of items has no effect on the number of features. For example: movie genres, movie origin and cuisine of restaurants.

In addition, all attributes do not have the same degrees of importance to users. There are attributes more relevant than others. For instance, the movie genre can be more significant, in the evaluation criteria of user, than the origin. Experiments that we have conducted (see Section VI) confirmed this hypothesis. In this paper, we assume that relevant attributes will be provided by a human expert. Therefore, for each relevant attribute A, we build a user semantic attribute model that predicts the users preferences for its features. This model is described by a matrix Q A (users in lines and features of A in columns). In our approach, we design a suited algorithm for building the user semantic attribute model for each class of attribute. For non dependent attribute, due to the low number of features, we have used a clustering algorithm. Section III-B briefly described the operating principle of our solution that have been addressed in previous works [START_REF] Ben Ticha | User semantic preferences for collaborative recommendations[END_REF], [START_REF] Ben Ticha | User Semantic Model for Hybrid Recommender Systems[END_REF]. For dependent attribute, we have explored techniques issues from retrieval and information filtering research, Section IV presents our solution for building the user semantic attribute model for dependent attribute that is the aim of this paper. The user semantic model for all relevant attributes, described by the matrix Q, is the result of the horizontal concatenation of all user semantic attribute models Q A .

B. User semantic model for non dependent attribute

Let us denote by S the set of items, U the set of users, s a given item ∈ S, u a given user ∈ U and a rating value r ∈ {1, 2, ..., 5} ≡ R. U s the set of users that rating the item s, then we define the rating function for item s by δ s : u ∈ U s -→ δ s (u) ∈ R. We denote also by F A the set of features of attribute A, f a given feature ∈ F A and S f the set of items associated to feature f . For instance if we consider the movie genre attribute, S action is the set of all action movies. An item s is represented by its usage profile vector

s up = (δ s (u) -δ u ) (u=1..|U |)
, where δ u is the average rating of all rated items by user u. The idea is to partition all items described by their usage profile in K clusters, each cluster is labeled by a feature f ∈ F A (or a set of features).

The number K of clusters and the initial center of each cluster is computed by the initialization step of the clustering algorithm. In initial step, each cluster C k consists of items in f labeling C k S f and labeled by the set of corresponding features; so its center is the mean of its items described by their usage profile vector s up . Moreover, an attribute can be mono valued or multivalued depending on the number of features that can be associated to a given item s. For example, the attribute movie genre is multivalued because a movie can have several genres while movie origin is a mono valued attribute because a movie has only one origin. Thus, if an attribute is multivalued, s can belong to several clusters C k , while for mono valued attribute, an item should belong only to one cluster. Therefore, for multivalued attribute, the clustering algorithm should provide non disjointed clusters (a fuzzy clustering), whereas, for mono valued attribute, the clustering algorithm should provide disjointed clusters.

After running the clustering algorithm, we obtain K cluster centers; each center k is described by a vector c k = (q k,u ) (u=1..|U |) . Thus, the user semantic attribute model is described by the matrix

Q A = (q u,k ) (u=1..|U |, k=1..K) .
With non dependent attribute, the number of associated features is low, this is why the clustering is suitable. More-over, the user semantic attribute model allows an important reduction of dimension and so reduce the expensiveness of user similarity computing. In [START_REF] Ben Ticha | User Semantic Model for Hybrid Recommender Systems[END_REF], we have used the Fuzzy CMean Algorithm on the movie genre attribute, we have obtained good performance because the user semantic attribute model has no missing values and all similarities between users were able to be computed. In [START_REF] Ben Ticha | User semantic preferences for collaborative recommendations[END_REF], we have used the KMean clustering algorithm on the movie origin attribute. Because of the missing values in the user item rating matrix, we have proposed an algorithm for the initialization step of the KMean clustering using a movie origin ontology. We obtained good results compared to user-based CF but not as good as the genre attribute.

IV. USER SEMANTIC MODEL FOR DEPENDENT ATTRIBUTE

For a dependent attribute A, the set F A of its features can be important and it augments with the increasing of the set of items S. In this paper, we present our solution to compute a user semantic attribute model for dependent attribute. Due to the high number of attribute features in this case, and with the aim to reduce the expensiveness of user similarity computing, we propose also a solution to reduce the dimension based on features selection.

In addition to the formalism used in Section III-B, we denote by F As the set of features f ∈ F A associated to item s and by S u the set of items s ∈ S rated by user u. We define the feature function for item s ∈ S as β s : f ∈ F A → 1 if f ∈ F As (f associated to item s), 0 otherwise, the item-feature matrix is so equal to (β s (f )) s∈S and f ∈F A . We denote also, the rating function of user u as δ u : s ∈ S u → δ u (s) ∈ R; and the user frequency function as f req u : f ∈ F A → f req u (f ) ∈ N. The frequency matrix F = (f req u (f )) u∈U and f ∈F A is provided by computing f req u (f ) for all users u ∈ U and all features f ∈ F A . In the following sections, we propose 4 methods for computing the frequency function f req u .

A. Computing the frequency function for all items

In this case, the frequency function f req u (f ) consists of counting the number of times, the user u rated an item associated to feature f . The formula is given by [START_REF] Su | A survey of collaborative filtering techniques[END_REF].

f req u (f ) = s∈Su β s (f ) (1)

B. Computing the weighted frequency function for all items

In (1), all items are treated in a identical way. In this case, we introduce the evaluation of item by user in the frequency function. Thus, the feature function is weighted by the user rating function δ u . For instance, if δ u (s1) = 4, β s1 (f ) = 1 and δ u (s2) = 2, β s2 (f ) = 1 the frequency of feature f for user u is 5 in this case and 2 in [START_REF] Su | A survey of collaborative filtering techniques[END_REF].

f req u (f ) = s∈Su β s (f ) × δ u (s) (2)

C. Computing the frequency function for relevant items

In this case, we consider only relevant items for user u. Let us denote S u relevant = s ∈ S u / δ u (s) ≥ δ u the set of relevant items for user u and δ u is average rating function of user u over all items in S u . The use of the average rating function instead of a threshold offers two advantages: first, it avoids adding a new parameter, the threshold value. Secondly, it allows a personalized frequency, because it takes into account the variation between users ratings.

f req u (f ) = s∈Su relevant β s (f ) (3)

D. Computing the weighted frequency function for relevant items

In this case, the feature function is weighted by the rating of only relevant items s ∈ S u relevant .

f req u (f ) = s∈Su relevant β s (f ) × δ u (s) (4)

E. Reduction of dimension of data

For dependent attribute, the number of feature is correlated to the number of items, and so it can be very elevated and even higher than the number of items. Thus, the semantic user attribute model can have dimension greater than the user rating matrix thereby aggravating the scalability problem. In order to reduce the dimension of the user semantic attribute model, we propose a reduction method based on selecting a subset of relevant features from the original set F A . We choose to reduce the number of features without using an expensive algorithm like LSA or SVD, but by selecting features having a number of ratings greater than a given threshold µ.

So, we define the number of feature ratings function η as:

η : f ∈ F A → u∈U s∈Su β s (f )
η(f ) provides the number of ratings associated to f . F Aµ = {f ∈ F A / η(f ) ≥ µ} is the set of selected features for attribute A having a number of ratings greater than µ. Thus, only features in F Aµ are used to compute the frequency matrix F .

F. User semantic attribute model

One of the best-known measures for specifying keyword weights in Information Retrieval is the TF-IDF (Term Frequency/Inverse Document Frequency) [START_REF] Salton | Automatic Text Processing[END_REF]. It is a numerical statistic, which reflects how important a word is to a document in a corpus. In our case, we replace document by user and term by feature, so we obtain a Feature Frequency Inverse User Frequency(FF-IUF) that is defined as:

F F (f, u) = f req u (f ) max j f req u (j) (5)
where the maximum is computed over the f req u (j) of all feature j ∈ F Aµ assigned to user u.

The measure of Inverse User Frequency IUF is usually defined as:

IU F (f ) = log |U | U f (6)
where U f is the number of users assigned to feature f (ie f req u (f ) = 0). Thus, the FF-IUF weight of feature f for user u is defined as:

ω(u, f ) = F F (f, u) × IU F (f ) (7)
In summary, for building the user semantic attribute matrix Q A for a dependent attribute A; first, we define the selected set of features F Aµ to reduce the dimension; second, we compute the frequency matrix F over features ∈ F Aµ by using one of the formula from (1) to (4); third, we compute the FF-IUF on this matrix to obtain the matrix Q A . In Section VI, we will study the performance of each solution. For reasons of clarity, we have called the algorithm using the formula in (1) as FFIUF-NW-NR (no weighted no relevant), in (2) as FFIUF-W-NR (weighted and no relevant), in (3) as FFIUF-NW-R and in (4) as FFIUF-W-R.

V. RECOMMENDATION

To compute predictions for the active user u a , we use the user-based CF algorithm [START_REF] Resnick | Grouplens: an open architecture for collaborative filtering of netnews[END_REF]. User-Based CF predicts the rating value of active user u a on non rated item s ∈ S, it is based on the k-Nearest-Neighbors algorithm. A subset of nearest neighbors of u a are chosen based on their similarity with him or her, and a weighted aggregate of their ratings is used to generate predictions for u a . Equation 8provides formula for computing predictions.

p(u a , s) = δ ua + L v∈V sim(u a , v)(δ v (s) -δ v ) (8)
where L = 1 v∈V |sim(ua,v)| and V is the set of the nearest neighbors (most similar users) to u a that have rated item s. V can range anywhere from 1 to the number of all users.

sim ( u, v) = k (q u,k -q u )(q v,k -q v ) k (q u,k -q u ) 2 k (q v,k -q v ) 2 (9)
The function sim(u, v) provides the similarity between users u and v and is computed by using the Pearson Correlation [START_REF] Balabanovic | Fab: Content-based, collaborative recommendation[END_REF].

In the standard user-based CF algorithm, the users-items rating matrix (δ u (s) (u∈U, s∈S) ) is used to compute users' similarities.

In our algorithm for computing the similarities between users we use instead the user semantic matrix Q. As we have already mentioned, the matrix Q is the horizontal concatenation of user semantic attribute model of each relevant attribute.

Although we apply a user-based CF for recommendation, our approach is also a model-based method because it is based on a new user model to provide ratings of active user on non rated items. Our approach resolves the scalability problem for several reasons. First, the building process of user semantic model is fully parallelizable (because the computing of user semantic attribute model is done in independent way for each other) and can be done off line. Second, this model allows a dimension reduction since the number of columns in the user semantic model is much lower than those of user item rating matrix, so, the computing of similarities between user is less expensive than in the standard user-based CF. In addition, our approach allows inferring similarity between two users even when they have any co-rated items because the users-semantic matrix has less missing values than user item ratings matrix. Thus, our approach provides solution to the neighbor transitivity problem emanates from the sparse nature of the underlying data sets. In this problem, users with similar preferences may not be identifies as such if they haven't any items rated in common.

VI. PERFORMANCE STUDY

In this section, we study the performance of our algorithm, User Semantic Collaborative Filtering (USCF in plots), against the standards CF algorithms: User-Based CF(UBCF), and Item-Based CF(IBCF); standard CB algorithm and an hybrid algorithm. We evaluate these algorithms in terms of predictions accuracy by using the Mean Absolute Error (MAE) [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF], which is the most widely used metric in CF research literature. It computes the average of the absolute difference between the predictions and true ratings in the test data set, lower the MAE is, better is the prediction. When comparing results to CB algorithm, we use instead the F1 metric (2 × Recall × P recion/Recall + P recision) [START_REF] Herlocker | Evaluating collaborative filtering recommender systems[END_REF] because CB doesn't provide prediction.

We have experimented our approach on real data from the MovieLens1M dataset of the MovieLens recommender system [16]. The MovieLens1M provides the usage data set and contains 1,000,209 explicit ratings of approximately 3,900 movies made by 6,040 users. For the semantic information of items, we use the HetRec 2011 dataset [START_REF] Hetrec | 2nd Int Workshop on Information Heterogeneity and Fusion in Recommender Systems. The 5th ACM Conf. RecSys[END_REF] that links the movies of MovieLens dataset with their corresponding web pages at Internet Movie Database (IMDb) and Rotten Tomatoes movie review systems. We use movie genre and movie origin as non dependent attributes, movie director and movie actor as dependent attributes.

We have filtered the data by maintaining only users with at least 20 ratings, and available features for all movies. After the filtering process, we obtain a data set with 6020 users, 3552 movies, 19 genres, 44 origins, 1825 directors and 4237 actors. The usage data set has been sorted by the timestamps, in ascending order, and has been divided into a training set (including the first 80% of all ratings) and a test set (the last 20% of all ratings). Thus, ratings of each user in test set have been assigned after those of training set. It should be noted that the building of user semantic attribute model for the non dependent attributes genre and origin have been addressed respectively in previous works [START_REF] Ben Ticha | User semantic preferences for collaborative recommendations[END_REF], [START_REF] Ben Ticha | User Semantic Model for Hybrid Recommender Systems[END_REF]. Therefore, we will not detail the experiments conducted for these attributes in this paper. If it is not specified, the number of nearest neighbors is equal to 60 because it provides the best results.

A. Performance Evaluation of the four methods for computing the frequency function

In Figure 1, the MAE has been plotted with respect to the µ threshold parameter (the minimum number of ratings associated to a feature). It compares the 4 algorithms described in Section IV for computing the frequency function, on director (Figure 1(a)) and actor (Figure 1(b)) attributes. In both case, the plots have the same look, the MAE decreases until a specific value of the number of selected features |F Aµ | and then grows up; however, FFIUF-W-R algorithm results in an overall improvement in accuracy. We note for both figures, that the reduction of dimension has a slightly effect on improving the accuracy. Indeed, for the director attribute the MAE without reduction (1825 features) is equal to 0.7113 while the best value is equal to 0.7098 obtained by 601 features, so a reduction about 67%. Although the improvement of accuracy isn't elevated, the reduction of dimension is considerable and so allows to reduce the cost of users similarity computing. When analyzing this figure we note first, that Average algorithm provides, for all attributes, the worst performance compared to all other algorithms. Second, if we applied the FFIUF-W-R algorithm to non dependent attribute the performance compares unfavorably against the dependent attribute, while the best performance is attained by FuzzyCM algorithm on genre attribute and the difference is important (0.7079 for FuzzyCM and 0.7268 for FFIUF-W-R). This allows to deduct that, using a suited algorithm for each attribute class provides best performance than applying the same algorithm for all attributes. Third, the origin attribute has the worst performance compared to the other three attributes and this for all algorithms; this is confirm our hypothesis that all attributes don't have the same relevance to users.

B. Impact of attributes classes on prediction accuracy

The attribute origin can be less significant in the choice of users than the genre, actor or director, which is intuitively understandable. Pure CB algorithm exploits information derived only from item features. Thus, we create an item-item similarity matrix based on Cosinus similarity applied on item-feature matrix computed on corresponding attribute shown in the plot. In Figure 3(a), recommendations are computed for 60 nearest neighbors. We note that our algorithm USCF results in an overall improvement in accuracy against CB, and this for all combinations of attributes. In Figure 3(b), MAE has been plotted with respect to the number of neighbors (similar users) in the k-nearest-neighbor algorithm. In all cases, the MAE converges between 50 and 60 neighbors, however, USCF results in an overall improvement in accuracy. In addition, the best performance is achieved by the combination genredirector-actor. This improvement can be explained by many reasons. First, taking into account the semantic profile of items in a CF recommendation process. Second, for non dependent attribute, user semantic model is built according to a collaborative principle; ratings of all users are used to compute the semantic profile of each user. It is not the case of the Average algorithm; this may explain its results despite taking into account the semantic aspect. Third, the choice of the attribute can have significant influence on improving the accuracy. Lastly, users semantic model Q has few missing values, so, it allows inferring similarity between two given users even when they have any items rated in common.

C. Comparative results of USCF against CF and CB recommender system

VII. CONCLUSION AND FUTURE WORK

The approach presented in this paper is a component of a global work, which the aim, is to introduce the semantic aspect of items in a CF process in order to enhance recommendations and to resolve the scalability problem by reducing the dimension. For this purpose, we have designed a new hybridization technique, which predicts users' preferences for items based on their inferred preferences for semantic information. We have defined two classes of attributes: dependent and non dependent attribute, and presented a suited algorithm for each class for building user semantic attribute model. The aim of this paper is to present our approach for building user semantic attribute model for dependent attribute. We have defined an algorithm based on the TF-IDF measure and have proposed a solution to reduce a dimension by selecting the most relevant features. Our approach provides solutions to the scalability problem, and alleviates the data sparsity problem by reducing the dimensionality of data. The experimental results show that USCF algorithm improves the prediction accuracy compared to usage only approach (UBCF and IBCF), Content only approach (CB) and hybrid algorithm (Average). In addition, we have shown that applying FFIUF on non dependent attribute, decreases significantly the prediction accuracy compared to results obtained with machine learning algorithms. Furthermore, we have experimentally shown that all attributes don't have the same importance to users. Finally, experiments have shown that the combination of relevant attributes enhances the recommendations.

An interesting area of future work is to use machine learning techniques to infer relevant attributes. We will also further study the extension of the user semantic model to non structured data when items are described by free text. Lastly, study how our approach can provide solution to the cold start problem in which new user has few ratings and CF cannot provide recommendation because similarities with others users cannot be computed.

Fig. 1

 1 Fig. 1 Performance evaluation of the four FFIUF algorithms for director (a) and actor (b) attributes.

Fig. 2 .

 2 Fig. 2. Impact of user semantic attribute building algorithm on prediction accuracy.

Figure 2

 2 Figure2compares algorithms for building user semantic attribute model in term of MAE. The Average algorithm (Average in plot) is building user semantic attribute model by computing the average of user ratings by feature (q (u,f ) = AV G {δ u (s)/s ∈ S u and f ∈ F As }); Fuzzy C Mean algorithm (FuzzyCM in plot) is a fuzzy clustering used for non dependent and multivalued attribute (here genre) and KMean algorithm (KMean in plot) is used on non dependent and mono valued attribute (here origin). When analyzing this figure we note first, that Average algorithm provides, for all attributes, the worst performance compared to all other algorithms. Second, if we applied the FFIUF-W-R algorithm to non dependent attribute the performance compares unfavorably against the dependent attribute, while the best performance is attained by FuzzyCM algorithm on genre attribute and the difference is important (0.7079 for FuzzyCM and 0.7268 for FFIUF-W-R). This allows to deduct that, using a suited algorithm for each attribute class provides best performance than applying the same algorithm for all attributes. Third, the origin attribute has the worst performance compared to the other three attributes and this for all algorithms; this is confirm our hypothesis that all attributes don't have the same relevance to users.

Figure 3

 3 Figure 3 depicts the recommendation accuracy of USCF in contrast to those produced by pure CB (CB in plots) recommender system (Figure 3(a)) using the F 1 metrics to measure the recommendation accuracy; and standard Item-Based CF (IBCF) and User-Based CF (UBCF) (Figure 3(b)).Pure CB algorithm exploits information derived only from item features. Thus, we create an item-item similarity matrix based on Cosinus similarity applied on item-feature matrix computed on corresponding attribute shown in the plot. In Figure3(a), recommendations are computed for 60 nearest neighbors. We note that our algorithm USCF results in an overall improvement in accuracy against CB, and this for all combinations of attributes. In Figure3(b), MAE has been plotted with respect to the number of neighbors (similar users) in the k-nearest-neighbor algorithm. In all cases, the MAE converges between 50 and 60 neighbors, however, USCF results in an overall improvement in accuracy. In addition, the best performance is achieved by the combination genredirector-actor. This improvement can be explained by many reasons. First, taking into account the semantic profile of items in a CF recommendation process. Second, for non dependent attribute, user semantic model is built according to a collaborative principle; ratings of all users are used to compute the semantic profile of each user. It is not the case of the Average algorithm; this may explain its results despite taking into account the semantic aspect. Third, the choice of the attribute can have significant influence on improving the accuracy. Lastly, users semantic model Q has few missing values, so, it allows inferring similarity between two given users even when they have any items rated in common.

Fig. 3

 3 Fig. 3 Evaluation of USCF against CB in terms of F1 (a) against standards CF in terms of MAE (b).

Copyright (c) IARIA, 2013. ISBN: 978-1-61208-312-4 SOTICS 2013 : The Third International Conference on Social Eco-Informatics