Guillaume Maillard
email: guillaume.maillard@ens.fr

Sylvain Arlot
email: sylvain.arlot@math.u-psud.fr

Matthieu Lerasle
email: matthieu.lerasle@math.u-psud.fr

Cross-validation improved by aggregation: Agghoo

Cross-validation is widely used for selecting among a family of learning rules. This paper studies a related method, called aggregated hold-out (Agghoo), which mixes cross-validation with aggregation; Agghoo can also be related to bagging. According to numerical experiments, Agghoo can improve significantly cross-validation's prediction error, at the same computational cost; this makes it very promising as a general-purpose tool for prediction. We provide the first theoretical guarantees on Agghoo, in the supervised classification setting, ensuring that one can use it safely: at worse, Agghoo performs like the hold-out, up to a constant factor. We also prove a non-asymptotic oracle inequality, in binary classification under the margin condition, which is sharp enough to get (fast) minimax rates.

Introduction

Machine learning rules almost always depend on some hyperparameters, whose choice has a strong impact on the final performance. For instance, nearest-1 neighbor rules [START_REF] Biau | Lectures on the Nearest Neighbor Method[END_REF] depend on the number k of neighbors and on some distance measure over the feature space. Kernel methods [START_REF] Scholkopf | Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[END_REF] require to choose an appropriate kernel. A third example, among many others, is given by regularized empirical risk minimization rules, such as support vector machines [START_REF] Steinwart | Support vector machines[END_REF] or the Lasso [Tibshirani, 1996, Bühlmann and[START_REF] Bühlmann | Statistics for high-dimensional data[END_REF], which all depend on some regularization parameter. More generally, the problem of choosing from data among a family of learning rules is central to machine learning, including model selection [START_REF] Burnham | Model Selection and Multimodel Inference[END_REF]Anderson, 2002, Massart, 2007] and when one hesitates between different kinds of rules -for instance, support vector machines or random forests.

In supervised learning, cross-validation (CV) is a general, efficient and classical answer to this problem [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF]. It relies on the idea of splitting data into a training sample -used for training a predictor with each rule in competition-and a validation sample -used for assessing the performance of each predictor. This leads to an estimator of the risk -the hold-out estimator when data are split once, the CV estimator when an average is taken over several data splits-, which can be minimized for selecting among a family of competing rules.

A completely different strategy, called aggregation, is to combine the predictors obtained with all candidate rules [Nemirovski, 2000, Yang, 2001, Tsybakov, 2004]. A major interest of aggregation is that it builds a learning rule in a much larger set that the family of rules in competition; therefore, it can sometimes yield a better performance than the best of all rules. Aggregation is the keystone of ensemble methods [START_REF] Dietterich | Ensemble methods in machine learning[END_REF], among which we can mention bagging [START_REF] Breiman | Bagging predictors[END_REF], AdaBoost [START_REF] Freund | A decision-theoretic generalization of on-line learning and an application to boosting[END_REF] and random forests [Breiman, 2001, Biau and[START_REF] Biau | A random forest guided tour[END_REF].

This paper studies a mix of cross-validation and aggregation ideas, called aggregated hold-out (Agghoo). Data are split several times; for each split, the hold-out selects one predictor; then, the predictors obtained with the different splits are aggregated. This procedure is as general as cross-validation and it has the same computational cost. Moreover, it seems to be folklore knowledge among practicioners that Agghoo (or its variants) performs better than CV for prediction. Yet, Agghoo has never been properly studied in the literature, even experimentally, to the best of our knowledge. The closest results we found [START_REF] Jung | Efficient tuning parameter selection by cross-validated score in high dimensional models[END_REF]Hu, 2015, Jung, 2016] study other procedures, called ACV and EKCV, and prove weaker theoretical results than ours; we explain in Section 2.3 why Agghoo is more natural and should be preferred to ACV and EKCV in general.

Because of the aggregation step, Agghoo is an ensemble method, and it is particularly close to subagging -a variant of bagging where the bootstrap is replaced by subsampling- [START_REF] Bühlmann | Analyzing bagging[END_REF], since both combine subsampling with aggregation. However, Agghoo is not subagging applied to the hold-out selected predictor, in which the subsample itself is split into training and validation samples; see Section 2.3. Therefore, we cannot apply previous re-sults on subagging for analyzing Agghoo; new developments are required. Since bagging and subagging are well-known for their stabilizing effects [Breiman, 1996, Bühlmann and[START_REF] Bühlmann | Analyzing bagging[END_REF], we can expect Agghoo to behave similarly; in particular, it should improve much the prediction performance of CV when the hold-out selected predictor is unstable. The simulation experiments of Section 4 confirm this intuition.

Contributions The purpose of this paper is to investigate both theoretical and practical performances of Agghoo. As a first step, we focus on supervised classification with the 0-1 loss. First, Section 3 provides three theoretical results on the classification error of Agghoo. Proposition 3.1 is a general result -valid for any family of learning rules-proving that the excess risk of Agghoo is smaller than the excess risk of hold-out selection, multiplied by the number of classes. This ensures that Agghoo can be used safely: one cannot loose too much by preferring Agghoo to the hold-out. We then focus on binary classification under the margin condition [START_REF] Mammen | Smooth discrimination analysis[END_REF], which is well-known for allowing fast learning rates [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF][START_REF] Lecué | Optimal rates of aggregation in classification under low noise assumption[END_REF][START_REF] Audibert | Fast learning rates in statistical inference through aggregation[END_REF]. Theorem 3.2 is a non-asymptotic oracle inequality for Agghoo, showing that Agghoo performs almost as well as the best possible selection rule (called the oracle). We illustrate the sharpness of this oracle inequality by considering the setting of Audibert and Tsybakov [2007, Section 3]: Theorem 3.4 shows that Agghoo applied to a well-chosen family of classifiers yields a minimax-adaptive procedure -hence, optimal in worstcase. Finally, Section 4 is a numerical study of the performance of Agghoo, on synthetic and real data sets, with two different kinds of selection problems. It illustrates that Agghoo actually performs much better than hold-out, and even better than CV -provided its parameters are well-chosen. When choosing among decision trees, the prediction performance of Agghoo is much better than the one of CV -for the same computational cost-, which illustrates the strong interest of using Agghoo when the choice among competing learning rules is "unstable". Based upon our experiments, we also give in Section 4 some guidelines for choosing Agghoo's parameters: the training set size and the number of data splits.

Setting and definitions

Supervised classification

Consider the supervised classification problem where a sample (X 1 , Y 1 ), . . ., (X n , Y n ) ∈ X ×Y is given, with X any measurable space and Y = {0, . . . , M -1} for some integer M ≥ 2. The goal is to build a classifier -that is, a measurable map f : X → Ysuch that, for any new observation (X, Y ), f (X) is a good prediction for Y . Throughout the paper, (X 1 , Y 1 ), . . . , (X n , Y n ), (X, Y ) are assumed independent with the same distribution P . Let F denote the set of classifiers. The quality of any classifier f ∈ F is measured by its risk

R(f ) = P (X,Y )∼P Y = f (X)
and any optimal classifier f * ∈ argmin f ∈F R(f ) is called a Bayes classifier [START_REF] Devroye | A Probabilistic Theory of Pattern Recognition[END_REF]. We also define the excess risk of f ∈ F by ℓ(f

* , f ) = R(f ) -R(f * ) = R(f ) -inf f ∈F R(f ) ≥ 0.
Since we only have access to P through the data D n := (X i , Y i ) 1≤i≤n , a classifier is built from data, thanks to a classification rule G : ∪ k≥1 (X × Y) k → F , which maps a sample (of any size) into a classifier.

Selection of classification rules by cross-validation

A generic situation is when a family G of classification rules is given, and not only a single rule, so that we have to select one of them -or to combine their outputs. For instance, we can consider the family (G NN k ) k≥1 of nearest neighbors classifiers when X is a metric space -the parameter k denoting the number of neighbors-, or the family (G SVM λ ) λ∈[0,+∞) of support vector machine classifiers for a given kernel on X -λ denoting the regularization parameter.

A common answer to this problem is to select one of these rules from data, and cross-validation methods are a general tool for doing so. Let us briefly recall these methods here; we refer the reader to the survey by [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF] for details and references, and to the paper by [START_REF] Arlot | Choice of V for V -fold cross-validation in least-squares density estimation[END_REF] for the most recent results.

For any non-empty B ⊂ {1, . . . , n}, define the corresponding sample and empirical risk by Given a non-empty subset T of {1, . . . , n} and some classification rule G, the hold-out estimator of the risk of G is defined by HO T (G) := R T c ( f G,T ). A classifier f G,T is built from the training sample D T n , then its quality is assessed on the validation sample D T c n . Note that HO T (G) depends on the sample D n even if this does not appear in the notation. Then, hold-out can be used for selecting one rule among G, by minimizing HO T (G) over G ∈ G:

D B n := (X i , Y i ) i∈B and ∀f ∈ F , R B (f ) := 1 |B| i∈B 1 {f (Xi)
f ho G,T := G ho G,T (D T n ), where G ho G,T ∈ argmin G∈G HO T (G) . (1)
We call f ho G,T the hold-out classifier. Hold-out depends on the arbitrary choice of a training set T , and is known to be quite unstable, despite its good theoretical properties [Massart, 2007, Section 8.5.1]. Therefore, practicioners often prefer to use cross-validation instead, which considers several training sets. Given a family T = {T 1 , . . . , T V } of training sets, the cross-validation risk estimator of any classification rule G is defined by

CV T (G) = 1 V V j=1
HO Tj (G) , leading to the cross-validation classifier

f cv G,T := G cv G,T (D n ) where G cv G,T ∈ argmin G∈G CV T (G) . (2)
Depending on how T is chosen, this can lead to leave-one-out, leave-p-out, V -fold cross-validation or Monte-Carlo cross-validation, among others [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF].

Aggregated hold-out (Agghoo)

In this paper, we study another way to improve on the stability of hold-out classifiers, by aggregating the hold-out classifiers f ho G,Tj obtained from several training sets T 1 , . . . , T V . Formally, the aggregated hold-out classifer (Agghoo) is obtained by making a majority vote among them:

∀x ∈ X , f ag G,T (x) ∈ argmax y∈Y 1 V V j=1 1 f ho G,T j (x)=y . (3)
Compared to cross-validation classifiers defined by Eq. ( 2), we reverse the order between aggregation (majority vote or averaging) and minimization of the risk estimator. To the best of our knowledge, Agghoo has not appeared before in the literature. The closest procedures we found are "K-fold averaging crossvalidation" (ACV) proposed by [START_REF] Jung | A K-fold averaging cross-validation procedure[END_REF] for linear regression, and "efficient K-fold cross-validation" (EKCV) proposed by [START_REF] Jung | Efficient tuning parameter selection by cross-validated score in high dimensional models[END_REF] for highdimensional regression. The main difference with Agghoo is that ACV and EKCV average the chosen parameters -the models for ACV, the regularization parameters for EKCV-, whereas Agghoo averages the chosen classifiers. This leads to completely different procedures for learning rules that are not linear functions of their parameters. Even in the case of linear regression with ACV, where the estimator is a linear function of the projection matrix onto the model -which is the "parameter" averaged by ACV-, Agghoo would lead to a different procedure since it averages the G ho G,Tj (D

Tj n ) while ACV averages the G ho G,Tj (D n ).
In the general case, and in particular for classification, averaging the classifiers G ho G,Tj (D Tj n ), which have been selected for their good performance on the validation set T c j , is more natural than averaging the G ho G,Tj (D n ) whose performance has not been assessed on independent data.

Another related procedure -not explicitly studied in the literature-is subagging applied to hold-out selection D n → G ho G,T (D T n ), as defined by Eq. ( 1).

Denoting by T 1 , . . . , T V the subsample sets chosen by the subagging step, and by T ′ j the training set used by the hold-out applied to the subsample D Tj n , the subagged hold-out predictor is obtained by making a majority vote among

f G ho G,T ′ j (D T j n ) (D Tj n ) = G ho G,T ′ j (D Tj

Theoretical guarantees

In this section, we make the following two assumptions on the training sets:

T 1 , . . . , T V ⊂ {1, . . . , n} are independent of D n = (X i , Y i ) 1≤i≤n , (H1) |T 1 | = • • • = |T V | = n -p ∈ {1, . . . , n -1} . ( H2
)
These assumptions are satisfied for the most classical cross-validation methods, including leave-p-out, V -fold cross-validation (with p = n/V ) and Monte-Carlo cross-validation [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF].

General bound Our first theoretical result connects the performances of Agghoo and hold-out. (3) and the hold-out estimator defined by Eq. (1) satisfy:

E ℓ(f * , f ag G,T ) ≤ M E ℓ(f * , f ho G,T1 ) and E R( f ag G,T ) ≤ 2E R( f ho G,T1 ) .
Proposition 3.1 is proved in supplementary material. Up to the multiplicative constant M , the Agghoo predictor f ag G,T performs theoretically at least as well as the hold-out selected estimator. When the number of classes M is small -for instance, in the binary case-, this guarantees that Agghoo's prediction error cannot be too large. Let us now use this general bound to obtain oracle and minimax properties for Agghoo.

Oracle inequality in binary classification

From now on, we focus on the binary classification case, that is, M = 2. A classical assumption in this setting is the so-called margin assumption [START_REF] Mammen | Smooth discrimination analysis[END_REF], for some β ≥ 0 and c ≥ 1:

∀h > 0, P 2η(X) -1 ≤ h ≤ ch β where η(X) := P(Y = 1|X) ;
(MA) η is called the regression function. Agghoo satisfies the following non-asymptotic oracle inequality under (MA).

Theorem 3.2 Let G denote a collection of classification rules and T a collection of training sets satisfying (H1)-(H2). If β ≥ 0 and c ≥ 1 exist such that (MA) holds true, we have:

E ℓ(f * , f ag G,T ) ≤ 3E inf G∈G ℓ(f * , f G,T1 ) + 29c 1 β+2 log(e|G|) p β+1 β+2
.

Theorem 3.2 is proved in supplementary material. Note that the constant 3 in front of the oracle excess risk E[inf G∈G ℓ(f * , f G,T1 )] can be made as close as desired to 2, at the price of enlarging the constant 29 in the remainder term. Theorem 3.2 shows that Agghoo performs as well as the best classification rule in the collection G trained with np data (called the oracle classifier), provided that the remainder term O(log(e|G|)/p β+1 β+2 ) can be neglected. This is a strong result, since it shows that Agghoo attains the same learning rates as the oracle classifier. In comparison, the results proved by [START_REF] Jung | A K-fold averaging cross-validation procedure[END_REF] on ACV are much weaker, since they do not allow to derive any rate for ACV, except in the "parametric" setting.

Minimax rates We now address the main possible limitation of Theorem 3.2: is the remainder term negligible in front of the oracle excess risk in some "interesting" frameworks? To this end, we consider the setting of Audibert and Tsybakov [2007, Section 3], which is an example where fast minimax rates are known under the margin assumption. Let us briefly describe this setting. For any γ, L > 0, let Σ γ,L denote the class of functions with γ-Hölder semi-norm smaller than L (a formal definition is given in supplementary material). The classes of probability distributions that we'll be interested in is defined as follows.

Definition 3.3 For any γ, L > 0, β ≥ 0 and c ≥ 1, P γ,L,β,c denotes the set of probability distributions P on R d × {0, 1} such that (MA) holds true -with parameters β, c-, the regression function η ∈ Σ γ,L (R d ) and X has a density q with respect to the Lebesgue measure satisfying:

1 L 1 [0;1] d ≤ q(X) ≤ L1 [0;1] d almost surely.
By Audibert and Tsybakov [2007, Theorem 3.5], the minimax rate of conver-

gence over P γ,L,β,c is n -γ(1+β) 2γ+d if γβ ≤ d;
this result is recalled in supplementary material. When γβ < d, we have γ(1 + β)/(2γ + d) < (β + 1)/(β + 2), so the remainder term in Theorem 3.2 can be neglected in front of the minimax rate of convergence over P γ,L,β,c , if G is a polynomial collection -that is, |G| ≤ n α for some α ≥ 0-and if p ≥ δn with δ > 0.

As detailed by Audibert and Tsybakov [2007, Section 3], having γβ > d is a strong constraint on P , hence we can leave it aside in the following without losing too much. We can also remark that when L = +∞ -which removes the condition on the density q of X-, Audibert and Tsybakov [2007, Section 4] show that the minimax rate then is n -γ(1+β) γ(2+β)+d -even when γβ ≥ d-, and this rate is always larger than the remainder term in Theorem 3.2 if G and p are taken as previously.

Let us now explain how Agghoo can be used for building a minimax classifier, simultaneously over all classes P γ,L,β,c such that γβ < d. The construction relies on a family of classification rules proposed by Audibert and Tsybakov [2007, Definition 2.3]. For any ℓ ≥ 1 and h > 0, G LP ℓ,h is a plug-in classification rule based upon a local-polynomial Gaussian kernel estimator Q ℓ,h of η, where ℓ is the polynomial degree and h is the kernel bandwidth. Then, G LP ⌊γ⌋,hn(γ,d) is minimax over P γ,L,β,c , where h n (γ, d) is a well-chosen bandwidth. This result, and the full definition of G LP ℓ,h , are recalled in supplementary material. Its main limitation is that the minimax rule depends on γ which is unknown; in other words, it is not adaptive to the smoothness γ of the regression function. The next theorem shows that Agghoo is a simple way to get rid of this issue.

Theorem 3.4 Let τ ∈ (0, 1) be fixed. For any n ≥ 1, let T n = {T 1 , . . . , T V } be a collection of training sets satisfying (H1)-(H2) and |T 1 | = ⌊τ n⌋, for some V ≥ 1 (possibly depending on n), and let us define the collection

G LP n := G LP ℓ, 1 k 1≤ℓ≤n,1≤k≤n
of classification rules, where G LP l,h are defined above. Then, the Agghoo classifier f ag G LP n ,Tn defined by Eq. (3) is minimax over classes P γ,L,β,c simultaneously for all γ, L, β, c such that γβ < d.

Theorem 3.4 is proved in supplementary material. It shows that Agghoo applied to a well-chosen collection of local polynomial estimators defined by [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] yields a minimax adaptive classifier. Let us emphasize that minimax adaptivity is a strong theoretical property.

Of course, Agghoo is not the only way to obtain such an adaptivity result -for instance, hold-out selection is sufficient to get it, as can be seen by taking V = 1 in Theorem 3.4-, even if we have not found such a minimax-adaptive statement for this problem in the literature. The main goal of Theorem 3.4 is to illustrate that our oracle inequality (Theorem 3.2, from which the minimax adaptivity of Agghoo derives) is sharp, and that Agghoo can lead to optimal classifiers, in one non-trivial setting at least.

Numerical experiments

This section illustrates the performance of Agghoo and CV on synthetic and real data.

k-nearest neighbors classification

We first consider the collection G NN = (G NN k ) k≥1, k odd of nearest-neighbors classifiers -assuming k is odd for avoiding ties-on the following binary classification problem.

Experimental setup Data (X 1 , Y 1 ), . . . , (X n , Y n ) are independent, with X i uniformly distributed over X = [0, 1] 2 and

P(Y i = 1|X i ) = σ g(X i ) -b λ
where σ(u) = 1 1 + e -u , g(u, v) = e -(u 2 +v) 3 +u 2 +v 2 , b = 1.18 and λ = 0.05; the parameters have been chosen to get a challenging but feasible problem. The Bayes classifier is f * : x → 1 g(x)≥b and the Bayes risk, computed numerically using the scipy.integrate python library, is approximately equal to 0.242. Agghoo and CV are used with the collection G NN with training sets T 1 , . . . , T V that are chosen independently and uniformly among the subsets of {1, . . . , n} with cardinality ⌊τ n⌋, for different values of τ and V ; hence, CV corresponds to what is usually called "Monte-Carlo CV" [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF]. Each algorithm is run on 1000 independent samples of size n = 500, and independent test samples of size 1000 are used for estimating the 0-1 excess risks ℓ(f * , f ag G NN ,T ), ℓ(f * , f cv G NN ,T ) and the oracle excess risk inf G∈G NN ℓ(f * , G(D n )). Expectations of these quantities are estimated by taking an average over the 1000 samples; we also compute standard deviations for these estimates, which are not shown on Figure 1 since they are all smaller than 3.6% of the estimated value, so that all visible differences on the graph are significant.

Results are shown on Figure 1. The performance of Agghoo strongly depends on both parameters τ and V . Increasing V improves significantly the performance of the resulting estimator. However, most of the improvement seems to occur between V = 2 and V = 10, so that taking V much larger seems useless, a behaviour previously observed for CV [START_REF] Arlot | Choice of V for V -fold cross-validation in least-squares density estimation[END_REF]. As a function of τ , the performance of Agghoo is U-shaped although not symmetric around 1/2. It seems that τ ∈ [0.5, 0.8] yields better performances, while taking τ close to 0 or 1 should be avoided (at least for V ≤ 20). Taking V large enough, say V = 10, makes the choice of τ less crucial: a large region of values of τ yield (almost) optimal performance. Similar conclusions can be drawn for CV, with the major difference that its performance depends much less on V : only V = 2 appears to be significantly worse than V ≥ 5.

Let us now compare Agghoo with the hold-out (that is, V = 1) and CV. For a given τ , Agghoo and CV are much better than the hold-out; there is no surprise here, considering several data splits is always useful. For fixed (τ, V ), Agghoo does significantly better than CV if V ≥ 10, worse if V = 2, and they yield similar performance for V = 5. Overall, if we can afford the computational cost of V = 10 data splits, Agghoo with optimized parameters (V = 10, τ ∈ [0.5, 0.8]) clearly improves over CV with optimized parameters (V = 10, τ = 0.7). This advocates for the use of Agghoo instead of CV, unless we have to take V < 5 for computational reasons.

CART decision trees

In a second experiment, we consider the CART classification trees of [START_REF] Breiman | Classification and Regression Trees[END_REF].

Experimental setup Data samples of size n = 500 are generated, following an experiment of Genuer et al. [2010, Section 2]: Y ∼ B(0.5) and ε ∼ B(0.7) are independent Bernoulli variables, X = R d with d ≥ 6 and, given (Y, ε), the coordinates X (j) , j = 1, . . . , d of X are independent with the following distribution. When ε = 1, X (j) ∼ N (jY, 1) for j ∈ {1, 2, 3} and X (j) ∼ N (0, 1) otherwise. When ε = 1, X (j) ∼ N ((j -3)Y, 1) for j ∈ {4, 5, 6} and X (j) ∼ N (0, 1) otherwise. We estimate numerically that the Bayes risk is 0.041.

Agghoo and 10-fold CV are used with the family (G CART α ) α>0 of pruned CART classifiers, with training sets T j chosen as in Section 4.1. Let us detail how G CART α is defined. For any α > 0 and any sample D n , the α-pruned CART classifier G CART α (D n ) is defined as the partitioning classifier built on the tree

t α,n = argmin t⊂ t R( f t ) + α|L t | ,
where t denotes the fully grown CART tree, f t is the partitioning classifier associated with any tree t, R = R {1,...,n} is the empirical risk on the whole data set D n and |L t | is the number of leaves (terminal nodes) of the tree t. We also consider random forests (RF), which are a natural competitor to Agghoo applied on pruned CART trees, using the R package randomForest [START_REF] Liaw | Classification and regression by randomforest[END_REF] with default values for all parameters. Since RF typically build hundred of trees -500 by default-, whereas Agghoo only requires to build around V = 10 trees, we also consider RF with ntree = 10 trees (and default values for all other parameters). The rest of the experimental protocole is the same as in Section 4.1, in particular we consider 1000 samples of size n = 500, and risks are estimated with test samples of size 1000. Standard deviations of our risk estimations are not shown since they never exceed 2.5% of the excess risk.

Results are shown on Figure 2, with d = 7 (only one noise variable) and d = 50 (large majority of noise variables). Concerning Agghoo and CV, the conclusions are similar to the k-NN case, studied in Section 4.1. This is why we only report here their performances for V = 10. Let us only notice that Agghoo with τ = 0.8 and V = 10 performs almost as well as the oracle, which is a strong competitor since it uses the knowledge of data distribution P . The main novelty here is the comparison to RF: RF with 500 trees clearly outperform all other procedures (and the oracle!), whereas RF with 10 trees works well only for d = 7. We explain this fact by noticing that RF builds trees with more randomization than Agghoo (especially when many variables are pure noise, in the d = 50 case), so that individual trees (and small forests) perform worse than hold-out selected classifiers, whereas a large enough forest performs much better. Therefore, when such a specific algorithm is available, our advice is to 0.0 0.2 0.4 0.6 0.8 1.0 0.010 0.015 0.020 0.025 0.030 0.035 0.040 τ excès de risque 3.68 ± 0.04 RF (ntree = 500) 3.01 ± 0.03 prefer it to Agghoo; but in the general case, it might be difficult to add some randomization individual classifiers, so that Agghoo remains useful. Agghoo can also be interesting when we cannot afford to aggregate more than a few tens of classifiers.

VC agrégée VC sélection V = 1 (ho) V = 2 V = 5 V = 10 V = 20
Real-data experiment We also consider the same procedures on the breastcancer Wisconsin dataset from UCI Machine Learning Repository [START_REF] Lichman | UCI machine learning repository[END_REF], for which n = 699 and d = 10. We use samples of size 500 and the remaining 199 data as test samples. The split between sample and test sample is done 1000 times, so that we can provide error bars for the estimated risks reported in Table 1. The conclusion is similar to what has been obtained on synthetic data with d = 7, which confirms our interpretation: when most variables are relevant, RF's individual trees are less randomized so that RF can perform well even with a small number of trees.

Discussion

The theoretical and numerical results of the paper show that Agghoo can be used safely in supervised classification with the 0-1 loss, at least when its parameters are properly chosen -V ≥ 10 and τ ∈ [0.5, 0.8] seem to be safe choices. On the theoretical side, Agghoo performs at least as well as the hold-out and it satisfies some sharp oracle inequality. Experiments show that Agghoo actually performs much better, improving over cross-validation except when the number of data splits is strictly smaller than 5, especially when basis classifiers are unstable -like decision trees. Proving theoretically that Agghoo can improve over CV is an exciting, but challenging, open problem that we would like to address in future works.

So, for the same computational cost, Agghoo -with properly chosen parameters V, τ -should be preferred to CV, unless the final classifier has to be interpretable (which makes selection better than aggregation). Yet, Agghoo and CV only are general-purpose tools. For some specific families of classifiers, better procedures can be used. For instance, when one wants a classifier built upon decision trees, random forests -with sufficiently many trees if there are many irrelevant variables-certainly are a better choice, as shown by our experiments.

Our results can be extended in several ways. First, our theoretical bounds directly apply to subagging hold-out, since it also makes a majority vote among hold-out selected estimators. The difference is that in subagging the training set size is npq and the validation set size is q, for some q ∈ {1, . . . , np -1}, leading to slightly worse bounds than the ones we obtained for Agghoo (not much if q is well chosen). Oracle inequalities and minimax results can also be obtained for Agghoo in other settings; this paper focuses on two such results for length reasons only. Second, Agghoo can be extended to other learning problems, such as regression and density estimation, replacing the majority vote by an average. Proposition 3.1 then holds true with M replaced by 1 if the loss is convex -for instance, for the least-squares loss-, by Jensen's inequality. Then, Theorem 3.2 could be proved based upon the general results of Massart [2007, Section 8.5]. Third, Agghoo might be improved by weighting the votes of the different hold-out classifiers, as suggested by [START_REF] Jung | Efficient tuning parameter selection by cross-validated score in high dimensional models[END_REF].

B Proof of Theorem 3.2

The proof relies on a result by Massart [2007, Eq. (8.60), which is itself a consequence of Corollary 8.8], which holds true as soon as

∀f ∈ F , Var 1 {f (X) =Y } -1 {f * (X) =Y } ≤ w ℓ(f * , f ) 2 (4)
for some nonnegative and nondecreasing continuous function w on R + , such that x → w(x)/x is nonincreasing on (0, +∞) and w(1) ≥ 1.

Let us first prove that assumption (4) holds true. On one hand, for any f ∈ F ,

Var 1 {f (X) =Y } -1 {f * (X) =Y } ≤ E[|1 {f (X) =Y } -1 {f * (X) =Y } | 2 ] = E[1 {f (X) =f * (X)} ] = E |f (X) -f * (X)|] . (5)
On the other hand, since we consider binary classification with the 0-1 loss, for any f ∈ F and h > 0,

ℓ(f * , f ) = E |2η(X) -1| • |f (X) -f * (X)| by Devroye et al. [1996, Theorem 2.2] ≥ hE |f (X) -f * (X)|1 {|2η(X)-1|≥h} ≥ hE |f (X) -f * (X)| -1 {|2η(X)-1|<h} since |f -f * | ≤ 1 ≥ hE |f (X) -f * (X)| -ch β+1 by (MA).
This lower bound is maximized by taking

h = h * := E |f (X) -f * (X)| c(β + 1) 1 β , which belongs to [0, 1] since c ≥ 1 and E |f (X) -f * (X)| ≤ 1. Thus, we obtain ℓ(f * , f ) ≥ h * β β + 1 E |f (X) -f * (X)| = β (β + 1) (β+1)/β c 1/β E |f (X) -f * (X)| (β+1)/β hence Eq. (5) leads to Var 1 {f (X) =Y } -1 {f * (X) =Y } ≤ E |f (X) -f * (X)| ≤ β + 1 β β/(β+1) c 1 β+1 ℓ(f * , f ) β β+1 ≤ 2c 1 β+1 ℓ(f * , f ) β β+1 .
Therefore, Eq. ( 4) holds true with w(u) = √ c 1 u β β+1 and c 1 = 2c 1 β+1 , which statisfies the required conditions. So, by Massart [2007, Eq. (8.60)], for any θ ∈ (0, 1),

E ℓ(f * , f ho G,T ) | D T n ≤ 1 + θ 1 -θ inf G∈G ℓ(f * , f G,T ) + δ 2 * 1 -θ 2θ + log(e|G|) 1 3 + θ -1 (6)
where δ * is the positive solution of the fixed-point equation w

(δ * ) = √ pδ 2 * , that is δ 2 * = (c 1 /p) β+1 β+2
. Taking expectations with respect to the training data D T n , we obtain

E ℓ(f * , f ho G,T ) ≤ 1 + θ 1 -θ E inf G∈G ℓ(f * , f G,T ) + 2c 1 β+2 1 -θ 2θ + log(e|G|) 1 3 + θ -1 p β+1 β+2
. Now, by Proposition 3.1,

E ℓ(f * , f ag G,T ) ≤ 2E ℓ(f * , f ho G,T1 ) ≤ 2 1 + θ 1 -θ E inf G∈G ℓ(f * , f G,T ) + 4c 1 β+2 1 -θ 2θ + log(e|G|) 1 3 + θ -1 p β+1 β+2
.

Taking θ = 1/5 leads to the result.

C Proofs of minimax results

C.1 Formal framework and result

To begin with, let us recall the definition of minimax optimality.

Definition C.1 Let P be a class of probability distributions over X × Y. A classifier f n is said to be minimax over the class P when its maximal excess loss on P satisfies x ki i .

For any α ∈ N, any C α -function f and any point x ∈ R d , let

Q α x f (y) = k:|k|≤α D k f (x) k! (y -x) k .
The class of γ-smooth functions with constant L is defined as

Σ γ,L (R d ) = f ∈ C ⌊γ⌋ R d , R : ∀x, y ∈ R d , |f (y) -Q ⌊γ⌋ x (y)| ≤ L y -x γ .
Moreover, for δ < C 3 h γ n ,

nh d n δ 2 ≤ C 3 nh 2γ+d n ≤ C 3 b 2γ+d ,
therefore, inequality (7) holds for all δ > 0 and [Audibert and Tsybakov, 2007, Lemma 3.1] concludes the proof.

C.2 Proof of Theorem 3.4

Let k n = ⌊n 1 2γ+d ⌋ and h n = 1/k n . Then for n > d, the risk of the oracle is bounded from above by

E inf G∈G LP n ℓ(f * , f G,T1 ) ≤ inf G∈G LP n E[ℓ(f * , f G,T1 )] ≤ E ℓ(f * , f G LP ⌊γ⌋,hn ,T1 ) .
Moreover,

1 = ⌊n 1 2γ+d ⌋h n ≤ n 1 2γ+d h n ≤ (⌊n 1 2γ+d ⌋ + 1)h n ≤ 1 + h n ≤ 2 .
Therefore 1 ≤ n .

It follows from Eq. ( 8) that the Agghoo estimator is minimax.

  =Yi} , respectively. Then, for any classification rule G, f G,B := G(D B n ) is the (random) classifier obtained by training G on the subsample of D n indexed by B.

  n ). Compared to Agghoo, the main difference is that this aggregates predictors trained on a subsample of D Tj n -instead of the entire D Tj n .

  Proposition 3.1 Let G denote a collection of classification rules and T a collection of training sets satisfying (H1)-(H2). The aggregated hold-out estimator f ag G,T defined by Eq.

Figure 1 :

 1 Figure 1: Classification performance of Agghoo and CV for the k-NN family; the oracle excess risk is 0.0034 ± 0.0004

  ℓ(f * P , G(D n )))] . Any sequence u n such that u -1 n inf G sup P ∈P E P [ℓ(f * P , G(D n ))] is bounded and bounded away from 0 is called a minimax rate of convergence. We now define formally Σ γ,L . Definition C.2 For any k = (k 1 , ..., k d ) ∈ N d , any x = (x 1 , . . . , x d ) ∈ R d and any sufficiently smooth function f : R d → R, let |k| = 1 , ..., x d ), x k = d i=1

1.≤

  2γ+d h n ≤ 2 and, by Theorem C.4 and the fact that np ≥ τ n -1 ≥ τ n/2 for n ≥ 2/τ , there exist constants C • depending on various parameters indicated in subscript, but not on n such thatE[ℓ(f * , f G LP ⌊γ⌋,hn ,T1 )] ≤ C γ,L,β,c (np n ) -γ(1+β) 2γ+d ≤ C γ,L,β,c,τ n -γ(1+β) 2γ+dBy Theorem 3.2, there exists a constant C c,β such thatE ℓ(f * , f ag G LP n ,Tn ) ≤ C c,β   E ℓ(f * , f G LP ⌊γ⌋,hn ,T1 ) Since p n ≥ (1τ )n and |G LP n | = n 2 , it follows that E ℓ(f * , f ag G LP n ,Tn ) ≤ C γ,L,β,c,τ n -γ(1+β) 2γ+d + C cγβ < d, (β + 1)/(β + 2) > [γ(1 + β)]/[2γ + d], C β,γ,d n -γ(1+β)2γ+d

  A. B. Tsybakov. Optimal aggregation of classifiers in statistical learning.

	The Annals
	of Statistics, 32(1):135-166, 2004.
	Y. Yang. Adaptive regression by mixing. Journal of the American Statistical Associ-
	ation, 96(454):574-588, 2001.

A Proof of Proposition 3.1

The proof immediately follows from the following convexity-type property of the majority vote, applied to ( f ho G,Tj ) 1≤j≤V , since E ℓ(f * , f ho G,Tj ) and E R( f ho G,Tj ) do not depend on j under assumptions (H1)-(H2) (they only depend on T j through its cardinality np).

Proposition A.1 Let ( f i ) 1≤i≤V denote a finite family of classifiers and let f mv be some majority vote rule: ∀x ∈ X ,

Proof For any y ∈ Y, define η y :

We now fix some x ∈ X and define

Integrating over x (with respect to the distribution of X) yields the first bound.

For the second bound, fix x ∈ X and define C x (y) and C x as above. Let y ∈ Y be such that f mv (x) = y. Since y occurs less often than

Hence, for any y ∈ Y,

Taking expectations with respect to (x, y) yields

Let us conclude this section with the definition of the minimax classification rules.

Estimators achieving the minimax rates over the classes P γ,L,β,c were obtained by [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF]. Let us recall this construction.

Definition C.3 Let ℓ ∈ N, h > 0 and let K denote the standard gaussian Kernel. For any polynomial Q, let

Denote by

if the minimum exists and is unique and Q ℓ,h,x = 0 otherwise. Let also B be the matrix (B s1,s2 ) |s1|,|s2|≤⌊γ⌋ where

The local polynomial rule with degree ℓ and bandwidth h is defined by

2γ+d is minimax over the classes P γ,L,β,c , for any β ≥ 0, γ > 0, L > 0, c ≥ 1 and γβ < d.

Furthermore, if n

Proof The lower bound is proved in [Audibert and Tsybakov, 2007, Theorem 3.5].

For the upper bound, we shall denote by C 1 , C 2 , C 3 functions of the parameters γ, L, a, b, d but neither h nor n which may vary from line to line. Eq (3.7) in [Audibert and Tsybakov, 2007, Theorem 3.2] implies that


Soufiene Jaffali
email: jaffali.soufiene@gmail.com

Salma Jamoussi
email: jamoussi@gmail.com

Abdelmajid Ben Hamadou
email: abdelmajid.benhamadou@gmail.com

Kamel Smaili
email: smaili@loria.fr

Grouping Like-Minded Users for Ratings' Prediction

Keywords: Rating prediction, Social recommendation, Grouping Like-Minded users

Regarding the huge amount of products, sites, information, etc., finding the appropriate need of a user is a very important task. Recommendation Systems (RS) guide users in a personalized way to objects of interest within a large space of possible options. This paper presents an algorithm for recommending movies. We break the recommendation task into two steps: (1) Grouping Like-Minded users, and (2) create model for each group to predict user-movie ratings. In the first step we use the Principal Component Analysis to retrieve latent groups of similar users. In the second step, we employ three different regression algorithms to build models and predict ratings. We evaluate our results against the SVD++ algorithm and validate the results by employing the MAE and RMSE measures. The obtained results show that the algorithm presented gives an improvement in the MAE of about 0.42 and 0.5201 in the RMSE.

Introduction

Given the huge amount of products to purchase or information to browse on the web, matching users with the most appropriate items becomes a very important task. Recently, the interest to the Recommendation Systems (RS) has increased considerably. Indeed, RS play an important role in the well noted web sites such as Netflix3 , Tripadvisor 4 , etc. The RS aim to provide suggestions for items to be of use to a user. An item refers to any object, it can be a music to listen, product to buy, film to watch, etc. In this scope, many algorithms and methods are proposed. Burke [START_REF] Burke | The adaptive web. chapter Hybrid Web Recommender Systems[END_REF] distinguishes six families of RS approaches (Content-Based, Collaborative Filtering, Demographic, Knowledge-Based, Community-Based and Hybrid Recommendation Systems). As one of the most representative categories, collaborative filtering (CF) is popular for its high performance and simple requirements. The principle of CF is to create patterns based on user preferences and use them to produce suggestions.

One of the emergent tasks in RS field is Movie Recommendation. The Netflix and MovieLens are the most popular Movie Recommendation tasks [START_REF] Koren | The bellkor solution to the netflix grand prize[END_REF][START_REF] Lu | A security-assured accuracy-maximised privacy preserving collaborative filtering recommendation algorithm[END_REF]. Those tasks attract many researchers and many algorithms are proposed in this topic. Most of the CF algorithms used for Movie Recommendation, handle the problem as a Partial Matrix Factorization, and aim to find the missing values in the matrix users × movies containing user-movie ratings [START_REF] Koren | Factorization meets the neighborhood: A multifaceted collaborative filtering model[END_REF]. The major problem with these solutions is the sparsity of data (given the huge number of users and movies, in one hand and the lack of stored users-movies ratings, in other hand). Furthermore, we cannot predict recommendations for a new movie or user that does not appear in the training data.

We propose a new algorithm to recommend movies based on the Like-Minded user groups (groups of users having similar cinimatographic tastes). The main idea of our algorithm is to infer user u rating on a movie m based on the stored ratings of the user u and users having similar interests. Such prediction can improve the recommendation accuracy and decrease the complexity of the prediction model, as it builds patterns for groups of homogeneous users. To retrieve Like-Minded users, we use the Principal Components Analysis (PCA). Thus, we reduce data dimensions and solve the sparsity problem that characterizes RS data. Also, the Like-Minded user groups are generated based on the tastes of users (genres of rated movies), without any knowledge about the social network relation between users. Thus, we remedy the limitation of community-Based RS.

The remaining of this paper is organized as follows. Section 2 gives an overview of the related work. In Section 3, we present our approach to estimate ratings. Then, we describe the data set and the baseline in Section 4. The experimental results are presented in Section 5, and we conclude in Section 6 by pointing out some future works.

Related Work

In this section, we review a small set of Collaborative Filtering (CF) researches. We can find two major groups of CF methods, namely: Neighborhood and Latent-Model-Based methods. In the case of Neighborhood methods, the user-item ratings stored in the system are used to predict ratings for other items directly. The prediction is done either by the user-based or the item-based way. In the first case, for a given user u and an item i, Heckmann et al. [START_REF] Heckmann | Gumo -the general user model ontology[END_REF] use the stored ratings of i, given by users which are similar to u (called neighbors) to infer R ui (the interest of the user u to the item i). In the item-based case, Khabbaz and Lakshmanan [START_REF] Khabbaz | Toprecs: Top-k algorithms for item-based collaborative filtering[END_REF] use the ratings of u for items similar to i to predict R ui . The methods used in Neighborhood CF can be grouped into two main approaches:

1. Dimensionality reduction such as Latent Semantic Indexation (LSI) [START_REF] Sarwar | Application of dimensionality reduction in recommender system -a case study[END_REF] and Singular Value Decomposition (SVD) [START_REF] Koren | Factorization meets the neighborhood: A multifaceted collaborative filtering model[END_REF]. 2. Graph-based such as Random Walk [START_REF] Fouss | Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[END_REF].

The major problem of Neighborhood methods is the limited space of predicted items. As the system recommends only items similar to those rated by the user or by his neighbors, it is hard to cover the huge number of items in the system, such as products in the Amazon.com5 or films on IMDB 6 .

The Latent-Model-Based methods use the stored ratings to learn a model. The main idea is to model the user-item interactions using factors representing latent characteristics of both users and items within the system. This model is learnt using available data and then utilized to predict user ratings on new items. In this context, many technics are used, such as Bayesian clustering [START_REF] Breese | Empirical analysis of predictive algorithm for collaborative filtering[END_REF], probabilistic Latent Semantic Analysis (pLSA) [START_REF] Hofmann | Latent semantic models for collaborative filtering[END_REF], Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF], SVD [START_REF] Koren | Advances in collaborative filtering[END_REF], etc.

Thanks to its accuracy and scalability, the SVD technic is deeply used in CF [START_REF] Paterek | Improving regularized singular value decomposition for collaborative filtering[END_REF][START_REF] Salakhutdinov | Restricted boltzmann machines for collaborative filtering[END_REF]. Most of the recent researches and recommendation tools (LingPipe7 , pyrsvd8 ) are based on the basic model or improved models of SVD like SVD++ [START_REF] Kumar | Article: Social popularity based svd++ recommender system[END_REF] and timeSVD++ [START_REF] Koren | Advances in collaborative filtering[END_REF].

Although it is a very prevalent Matrix Factorization (MF) method, just a few works use Principal Component Analysis (PCA) in RS field. Goldberg et al. [START_REF] Goldberg | Eigentaste: A constant time collaborative filtering algorithm[END_REF] propose Eigentaste, a CF algorithm to recommend jokes. The proposed algorithm starts by creating M , an n×m matrix, containing the ratings given by n users to m items. In the second step, the algorithm extracts the two eigenvectors having the highest eigenvalues of the correlation matrix of M . Then, it projects data in the eigenvectors plan. Finally, it uses Recursive Rectangular Clustering to create clusters of neighbors. Those clusters are used to predict users' preferences.

With the growth of social networks, a new kind of RS referred to as Social Recommender Systems (also known as Community Recommender Systems) gained popularity. The main idea is that users tend to trust more the recommendations from their friends than an anonymous user or seller [START_REF] Yang | A Survey of Collaborative Filtering Based Social Recommender Systems[END_REF]. FilmTrust [START_REF] Golbeck | Filmtrust: movie recommendations using trust in webbased social networks[END_REF] is the ideal example, it combines a movie rating and review system with a trust network (A social network expressing how much the members of the community trust each others). Yang et al. [START_REF] Yang | A Survey of Collaborative Filtering Based Social Recommender Systems[END_REF] present a deep review of collaborative filtering based social recommender systems. As the Community RS are based on link information only, they are limited to the user firends recommendations. Furthermore, given the big amount of items to recommend, and the fact that the egocentric network9 is very small compared to the the whole social network, by looking only in the egocentric network, a considerable part of items are ignored. Also, the social network is not available in all RS.

The GLER Algorithm

In this section, we describe our algorithm GLER (Grouping Like-minded users to Estimate Ratings). GLER algorithm aims to create groups of Like-Minded people, in order to estimate future user-movie ratings, based on the stored ratings of that user and those having similar cinimatic tastes. Such a prediction leads to triple improvements:

1. Enhancing the training base of the predictor, as we exploit Like-Minded users' experiences. 2. Facilitating the deployment of the recommendation algorithm, by creating groups based on the interest centers and not on the information about social network links, which are not available in all RS. 3. Improving the accuracy of the predictor by dividing the training base into sub-bases containing homogeneous entries.

To create groups of Like-Minded users, we use PCA, which proved its effectiveness in this area [START_REF] Jaffali | Clustering and classification of like-minded people from their tweets[END_REF][START_REF] Jaffali | Glio: A new method for grouping like-minded users[END_REF]. Once created, we use these groups to train the RS, and so, to build a model for each group. To estimate a new user-movie rating for an existing user, we use the model corresponding to the group that the user belongs to. For a new user, we calculate the distance between this user and the users of each group, and we use the model of the closest group. Figure 1 presents the proposed method. In the remainder of this section, we detail the steps of our algorithm.

Grouping Similar Users

Create the Matrix of Users' Interests Most of the RS algorithms use a n × m matrix of raw ratings from n users and m items. The matrix is partial (several rating are missed). Those algorithms aim to infer the missing ratings using a matrix factorization algorithm, such as SVD or LSI. In our work, we create a matrix representing users interests, and then use this matrix to retrieve the latent common interest centers. We start by creating a vector U for each user.

The vector U contains the averages of user ratings per movie genre (Section 6). Next, we group users' vectors into a matrix M . Then, we normalize the matrix M to produce the matrix N . For the normalization, we use two methods. The first consists of normalizing all values in the matrix M as fllows:

n ij = max j -m ij max j -min j (1)
Where max j and min j present respectively the maximum and minimum values in the column j of the matrix M . m ij is the average of ratings by the user i of the movie genre j. In the second normalization method, we divide each value by the standard deviation of each column.

n ij = m ij σ m kj ; with k = 1..n (2)
With n is the number of users. In the remainder of this article, we use N orm 1 and N orm 2 to refer to the first and the second normalization methods respectively.

Retrieve Latent Factors In this step, we seek the latent factors to model users using PCA which is a popular matrix factorization method, generally used to reduce the data dimensions or to retrieve the latent centers where the data is concentrated [START_REF] Jaffali | Principal component analysis neural network for textual document categorization and dimension reduction[END_REF]. In our work, we use PCA for both reasons:

1. Reduce the data dimensions, and so reduce the sparseness and data noise.

2. Retrieve the latent axes where the data is concentrated which represent the users' interest centers.

To find the latent interest centers and reduce the data dimensons using PCA, we start by calculating the covariance matrix C, given by:

C = 1 n -1 N T N ( 3
)
With N is the normalized form of the Users' Interests matrix, created in the previous step. Then, we retrieve the matrices Λ and E by solving the equations ( 4) and ( 5):

C = E T ΛE (4)
ECE T = Λ (5)
The columns of the matrix E correspond to the eigenvectors of C. Λ is a diagonal matrix whose elements correspond to the eigenvalues of C.

As the principal components correspond to the axis around which the data is concentrated, we can say that those axis present the groups of users where the correlation is maximal. We use the retrieved eigenvalues to determine the number of eigenvectors to retain, and the number of user groups [START_REF] Jaffali | Glio: A new method for grouping like-minded users[END_REF].

To retrieve the number of eigenvectors to retain and user groups from eigenvalues, we adopt the Scree Test Acceleration Factor proposed in [START_REF] Rache | Non-graphical solutions for cattells scree test[END_REF]. Finally, we project our data in the space of the retained eigenvectors:

N = N E T v ( 6
)
Where v is the number of eigenvectors to retain, E v is the matrix formed by the retained eigenvectors, and N is the reduced form of the matrix N .

Create Groups Many algorithms can be used to cluster users. In this work, we adopt the K-Means algorithm to group the similar users, for its simplicity and effectiveness. As inputs, K-Means takes the set of data N and the number of groups to be identified k. In our work, we set k = v, as the number of eigenvectors to retain reflects the number of interest centers within the input data. At the end of this step, we obtain v clusters of users. Each cluster presents a group of users having similar proprieties and tastes.

Predict Ratings

Predicting a user rating could be treated as both a regression and a classification problem. If the ratings are in the form of classes or labels, the prediction is treated as a classification problem. In revange, the prediction is considered as a regression issue, if the ratings are discrete numerical values (such as the five star evaluation in the MovieLens RS). In this work, we adopt three regression algorithms using Weka10 . The adopted regression algorithms are:

M5P M5P is a reconstruction of Quinlan's M5 algorithm [START_REF] Quinlan | Learning with continuous classes[END_REF] for inducing trees of regression models. It builds regression trees whose nodes are chosen over the attribute that maximizes the expected error reduction, and the node leaves are composed of multivariate linear models.

Multi-Layer Perceptron (MLP) An MLP can be viewed as a logistic regression classifier where the input is first transformed using a learnt non-linear transformation Φ. This transformation projects the input data into a space where it becomes linearly separable. Hornik et al. [START_REF] Hornik | Multilayer feedforward networks are universal approximators[END_REF] prove that three-layer perceptron networks are theoretically universal approximators.

Support Vector Regression (SVR) Support Vector Machines (SVM) can also be used as a regression method, maintaining all the main features that characterize the algorithm (maximal margin). The SVR uses the same principles as the SVM for classification, with the introduction of an alternative loss function. The loss function must be modified to include a distance measure. In Weka, there are two alternatives of SVR, namely: ε-SVR [START_REF] Vapnik | Statistical Learning Theory[END_REF] and ν-SVR [START_REF] Schölkopf | New support vector algorithms[END_REF].

For each user group produced in the previous step, we use the stored users ratings to learn the regression algorithm. Once learnt, the system is able to infer user ratings in this group. For a new user -who is not included in the learn set -we assign him to the nearest group, based on the cosine distance between the new user vector and the average of uesrs vectors in each group.

Dataset and Baseline

Dataset

To evaluate the accuracy of the proposed algorithm, we use the MovieLens-100K data sets 11 . The data set was collected by the GroupLens Research Project, through the MovieLens web site 12 during the seven-month period from September 19th, 1997 through April 22nd, 1998. This data has been cleaned up -users who had less than 20 ratings or did not have complete demographic information were removed from this data set. This data set consists of 100,000 ratings [START_REF] Blei | Latent dirichlet allocation[END_REF][START_REF] Breese | Empirical analysis of predictive algorithm for collaborative filtering[END_REF][START_REF] Burke | The adaptive web. chapter Hybrid Web Recommender Systems[END_REF][START_REF] Fouss | Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[END_REF][START_REF] Golbeck | Filmtrust: movie recommendations using trust in webbased social networks[END_REF] from 943 users on 1,682 movies. Demographic information about the users are: age, gender, occupation and zip code. The information about a movie in the dataset are: movie title, release date, video release date, IMDB URL and 19 binary values corresponding to the 19 movie genre. Those values indicate if the movie is or is not of the corresponding genre. The data is distributed over 5 dataset. Each dataset contains a train and test data. The train and test sets contain respectively 80,000 and 20,000 entries. Each entry is in the form: "user id" | "item id" | "rating" | "timestamp".

Baseline

We use SVD++ to evaluate and position our new algorithm. SVD++ is a popular Matrix Factorization RS. Matrix factorization models map both users and items to a joint latent factor space of dimensionality f , such that user-item interactions are modeled as inner products in that space. The latent space tries to explain the ratings by characterizing both products and users on factors automatically inferred from user feedback [START_REF] Koren | Advances in collaborative filtering[END_REF]. Accordingly, each item i is associated to a vector q i ∈ R f , and each user u is associated to a vector p u ∈ R f . For a given item i, the elements of q i measure the extent to which the item possesses those factors. For a given user u, the elements of p u measure the extent of interest the user has in items that are high on the corresponding factors. In the movie RS context, the elements of q i express the extent to which the movie i belongs to movie genres, and the elements of p u measure the extent of interest the user u has in movies of corresponding genres. The resulting dot product, q T i p u captures the interaction between the user u and the movie i. Let b i and b u denote the observed deviations of user u and item i, respectively, from the average µ (the overall average rating). For example, if the average of the observed ratings µ = 2.5, and the average of the stored ratings on the item i is 3, and the average of the ratings of the user u is 2, then b i = 3 -µ = 0.5 and b u = 2 -µ = -0.5. The prediction rule of the basic SVD recommender is given by adding the product q T i p u to the sum of the three parameters µ, b i and b u :

rui = µ + b i + b u + q T i p u (7)
To improve the basic SVD recommender by adding implicit feedback, Koren [START_REF] Koren | Factorization meets the neighborhood: A multifaceted collaborative filtering model[END_REF] adds a second set of item factors, relating each item i to a factor vector y i ∈ R f . Those new item factors are used to characterize the users based on the set of items that they rated. The new rule to predict ratings is given by:

rui = µ + b i + b u + q T i   p u + |R(u)| -1 2 j∈R(u) y j   (8)
Where R(u) contains the items rated by the user u. Thus, the user u is represented by p u + |R(u)| -1 2 j∈R(u) y j , insteed of p u . Thus, the user representation in the equation 7 is enhanced, by adding the perspective of implicit feedback.

Accuracy Measures

Typically, the rating dataset is split into a training set R train and a test set R test . R train is used to generate models and tune the recommender system parameters. R test is used to evaluate the recommender system. Let Ru,i the predicted ratings, and R u,i the recorded ratings. To assess the recommender system accuracy, we use two prevalent measures of accuracy, namely: Root Mean Squared Error and Mean Absolute Error. Root Mean Squared Error (RMSE) RMSE is one of the most popular metric used in evaluating the accuracy of predicted ratings. RMSE between known and predicted ratings is given by:

RM SE = (u,i)∈Rtest (r ui -r ui ) 2 |R test |
RMSE disproportionately penalizes large errors. For example, given a test set with four hidden items, RMSE would prefer a system that makes an error of 2 on three ratings and 0 on the fourth to one that makes an error of 3 on one rating and 0 on all three others. Mean Absolute Error (MAE) MAE is a popular alternative of RMSE, given by:

M AE = (u,i)∈Rtest (r ui -r ui ) 2 |R test |
Unlike RMSE, MAE prefers systems that make the least number of errors. In the previous example, MAE would prefer the system that makes an error of 3 on one rating and 0 on all three others.

Results and Discussion

To evaluate our algorithm on the the MovieLens-100k dataset, we start by creating the input matrix, as mentionned in the section 3.1. Thus, we create a user vector U x = {age, gend, occ, zip, year, rg 1 , ..., rg 19 }, where "age", "gend", "occ", and "zip" represent respectively the age, gender, occupation and zipcode of the user x. "year" is the average of rated movies release years. "rg i " is the average of ratings that the user x assigns to movies belonging to the genre i. Thus, the vector U presents a user not only by his personal information (age, gender, etc.), but also by his interest to movies genre and release year. Then, we gather user vectors to create the matrix M . Thereafter, we normalize M to obtain the matrix N , and retrieve the eigenvalues and eigenvectors of the covariance matrix of N . The obtained eigenvectors correspond to the latent centers where the users interests are concentrated. Using those centers, we form groups of like-minded users. Finally, we divide the training base into several dataset according to the users' groups, and learn the regression algorithm to build a model for each group. Once learnt, we use these models to estimate ratings for users of the corresponding group.

As we use four different regression algorithms, we designate by GLER M 5P (respectively GLER M LP , GLER ε-SV R and GLER ν-SV R ) the GLER using M5P algorithm (respectively MLP, ε-SVR and ν-SVR). We applied the proposed method and the baseline algorithm (SVD++) on the MovieLens-100k dataset, and we calculate the accuracy using MAE and RMSE. Tables 1 and2 illustrate the accuracy of the four alternatives of GLER on the MovieLens-100k five bases, using the N orm 1 and N orm 2 respectively.

We remark that the GLER algorithm provides MAE values lower than 0.31 and RMSE values lower than 0.44 for all the tests. Using the SVR regression algorithms (GLER ν-SV R and GLER ε-SV R ), we obtain the best predictions, compared to GLER M 5P and GLER M LP . We can conclude that the predicted ratings using GLER ε-SV R are most of the time close from the right ones, and GLER ν-SV R provides more exact ratings but the errors are larger than those in ε -SV R case. This is can be explained by the fact that the ε -SV R tends to control the amount of error in the model and go for the best performance without control of the support vectors in the resulting model, unlike the ν -SV R algorithm. 3 presents the MAE and RMSE of GLER and the baseline algorithm on the five bases of the MovieLens-100k dataset. The results show that the performances of our algorithm GLER exceed those of the baseline, and we obtain an improvement in the MAE of about 0.42 and a drop from 0.9065 to 0.3864 in the RMSE values. Thanks to the PCA used in our algorithm, we overcome the sparsity problem which characterizes RS data, and reduce the data dimension, which is very important and helpful for building the prediction model. Creating Like-Minded user groups based on their tastes leads to a better performance. Indeed, the prediction will be based, not only on the user's rating history, but also on users having the same cinematographic tastes. Furthermore, following the rule of "divide and conquer", creating similar-user groups facilitates the task of the regression algorithms. In fact, creating a model for a smaller number of homogeneous users is more easier and improves the prediction accuracy. In this work we presented the GLER algorithm for recommending movies. Our algorithm creates Like-minded user groups based on the user-movie ratings. Then, it uses those groups to build patterns and predict user-movie ratings. Experimenting on the MovieLens-100k dataset, we showed that GLER achieves better results than the SVD++ algorithm. This improvement manifests in the decrease of MAE and RMSE values of about 0.42 and 0.5201 respectively.

In our algorithm we used four regression algorithms to build recommendation model and infer ratings. The experimentations show that the GLER ν-SV R and GLER ε-SV R have the highest accuracy.

Our algorithm uses explicit feedback (user ratings) to build the recommendation model. Also, the training and test experimentation are done offline. In future research, we plan to enhance our algorithm by including users' implicit feedback, and handle the online recommendation.

Fig. 1 .

 1 Fig. 1. The proposed method steps: (1) Use the stroed user-movie ratings to create the matrix M . (2) Retrieve the latent interest centers using PCA. (3) Project the matrix M into the eigenvectors space. (4) Group like-minded users according to their interest centers. (5) Use the regression algorithm to build a model for each group. (6) Predict user-movie rating using the model corresponding to his group.

Table 1 .

 1 Ratings prediction accuracy using N orm1

		MAE RMSE
	GLERM5P	0.3083 0.4312
	GLERMLP	0.2969 0.4198
	GLERε-SV R 0.306 0.3909
	GLERν-SV R 0.2869 0.3972

Table 2 .

 2 Ratings prediction accuracy using N orm2

		MAE RMSE
	GLERM5P	0.3057 0.4322
	GLERMLP	0.2902 0.4228
	GLERε-SV R 0.301 0.3864
	GLERν-SV R 0.2809 0.3928
	Table

Table 3 .

 3 Comparison with the baseline accuracy

			MAE RMSE
	Baseline	0.7135 0.9065
	GLERM5P	norm1 0.3083 0.4312
		norm2 0.3057 0.4322
	GLERMLP norm1 0.2969 0.4198
		norm2 0.2902 0.4228
	GLERε-SV R norm1 0.306 0.3909
		norm2 0.30102 0.3864
	GLERν-SV R norm1 0.2869 0.3972
		norm2 0.2809 0.3928

https://www.netflix.com/

https://www.tripadvisor.com/

http://www.amazon.fr

http://www.imdb.com

http://alias-i.com/lingpipe/index.html

https://code.google.com/p/pyrsvd/

The network around a single node (ego)

http://www.cs.waikato.ac.nz/ml/weka/

http://grouplens.org/datasets/movielens/


Douib Ameur
email: ameur.douib@inria.fr

Langlois David
email: david.langlois@loria.fr

Smaïli Kamel
email: kamel.smaili@loria.fr

Genetic-based Decoder for Statistical Machine Translation

We propose a new algorithm for decoding on machine translation process. This approach is based on an evolutionary algorithm. We hope that this new method will constitute an alternative to Moses's decoder which is based on a beam search algorithm while the one we propose is based on the optimisation of a total solution. The results achieved are very encouraging in terms of measures and the proposed translations themselves are well built.

Introduction

In Statistical machine translation (SMT) [START_REF] Brown | The mathematics of statistical machine translation: parameter estimation[END_REF] given a source sentence f , the system produces a translation e in the target language, which maximises the probability P (e|f ). SMT can be divided into three parts. The language model (LM), which estimates the fluency of the translation e in the target language. The translation model (TM), which estimates the quality of the translation (accuracy) e, given the source f . The last part of SMT system is the decoder, for which, the machine translation process can be considered as an optimisation issue, where it takes, in input, the source sentence f and uses the LM and the TM to produce the best possible translation e, from all possible translations. Many algorithms are proposed to handle the issue of decoding. The first proposals used a word-based translation system [START_REF] Berger | The candide system for machine translation[END_REF][START_REF] Germann | Fast Decoding and Optimal Decoding for Machine Translation[END_REF], where the alignment is between words. Nowadays, decoders use a phrase-based system [START_REF] Koehn | Statistical phrase-based translation[END_REF], where the alignment is between phrases. MOSES is the most popular open source decoder used by the community [START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF]. It is based on a beam-search algorithm, where it builds incrementally a set of complete translations from partial translations and starting with the empty one. In the building process, new phrases are added for each partial translation hypothesis to produce new hypotheses. Consequently, a large number of hypotheses are produced. To reduce this number, a pruning process is applied, where the n-best hypotheses are retained for the next step according to a score given by the LM and the TM. Finally, from the set of complete translation hypotheses, the one which has the highest score is chosen as the final translation e. This algorithm gives good results [START_REF] Koehn | A Beam Search Decoder for Phrase-Based Statistical Machine Translation Models[END_REF], but presents at least two drawbacks. The first one concerns the fact that it is impossible to challenge a previous decision of translation. That is why it is possible to miss a partial solution which could lead to the best final translation. The second one concerns the decision making. At each step, MOSES keeps some translation hypotheses and eliminates others, according to the scores of the partial translations. The final solution is made up on a series of decisions what we would like to challenge in our method. Using a complete translation hypothesis from the beginning of the translation process can reduce the impact of these problems. With complete translation hypothesis, it is possible to visit each part of the research space and modify it if necessary. In the literature, works have been proposed in order to achieve translations from a complete translation. In [START_REF] Langlais | A greedy decoder for phrasebased statistical machine translation[END_REF] the decoder starts with a complete translation and applies iteratively heuristics until it reaches the best solution. In each iteration, the neighbour translations are produced by applying some neighbour functions [START_REF] Langlais | A greedy decoder for phrasebased statistical machine translation[END_REF], which modify phrases and lead to new propositions of translation. This work gives good results but do not outperforms the state-of-the-art system. In this paper, we propose a new decoder for SMT based on evolutionary algorithms, and more particularly those based on genetic principle [START_REF] Binitha | A Survey of Bio inspired Optimization Algorithms[END_REF][START_REF] Črepinšek | Exploration and exploitation in evolutionary algorithms: a survey[END_REF]. The advantage of the genetic algorithm is to use, not just one complete translation as in [START_REF] Langlais | A greedy decoder for phrasebased statistical machine translation[END_REF], but a population of complete translations. The combination of these translations, using crossover and mutation functions, produces more information allowing to take better decisions. The genetic algorithm is one of the most performant optimization algorithms [START_REF] Binitha | A Survey of Bio inspired Optimization Algorithms[END_REF], especially when the space search is huge. In previous works, the genetic algorithm was proposed to handle some parts of the automatic translation. In [START_REF] Echizen-Ya | Machine translation method using inductive learning with genetic algorithms[END_REF] a genetic algorithm was used in a learning process to generate new translation examples, but for an example-based machine translation system and not for SMT. Another work [START_REF] Zogheib | Genetic Algorithm-based Multi-Word Automatic Language Translation[END_REF] proposed an algorithm to generate a multi-word-based Translation Model, and to evaluate this model, a basic genetic algorithm was used as a translator. In this paper, we show the feasibility of using a genetic algorithm as a decoder for SMT. Also, we give a detailed adaptation of each component of the genetic algorithm. In section 2, we define the Statistical Machine Translation problem. In section 3, we present a description of our genetic decoder. We present the corpus data and some comparative results in section 4. Finally, in section 5, we give the conclusion with the perspectives for future works.

Phrase-based statistical machine translation system

In phrase-based SMT the system takes a source sentence f =<f 1 ,f 2 ,...,f |f | > in input, and the decoder produces the best possible translation e=<e 1 ,e 2 ,...,e |e| > in the target language, where f i (respectively e i ) is the i th word in f (respectively e). The translation process segments f into phrases, translates each phrase into the target language, and reorder target phrases.

The links between the source and target phrases define the alignment (a).

The translation e must maximise the conditional probability P (a, e|f ) [START_REF] Zens | Phrase-Based Statistical Machine Translation[END_REF]. So, the problem is considered as an optimization issue:

ê = argmax a,e [P (e) × P (f |a, e)] (1)
In equation [START_REF] Berger | The candide system for machine translation[END_REF] we distinguish the language model P (e) and the phrasebased translation model P (f |e). The decoder uses these two models as features, to evaluate the translations and finds the best one. Other features can be added to improve the evaluation.

Genetic algorithm for SMT

The basic idea of the genetic algorithm [START_REF] Binitha | A Survey of Bio inspired Optimization Algorithms[END_REF][START_REF] Črepinšek | Exploration and exploitation in evolutionary algorithms: a survey[END_REF] is to start with an initial population of solutions (chromosomes) and to produce iteratively new chromosomes using the crossover and the mutation functions. At the end of each iteration (generation) some chromosomes are selected from the population and kept for the next generation. This process ensures the evolution of the population towards a good solution (see Figure 1). An adequate representation of chromosomes and a good function to evaluate the chromosomes (fitness) are required to guarantee this evolution. Many parameters (population length, crossover and mutation rate, end process conditions, etc.) have to be fixed depending on the problem. In the next sections, we present how we adapt the genetic algorithm as a decoder for the SMT problem and we describe all the functions needed. We call our decoder GAMaT for Genetic Algorithm for Machine Translation.

Chromosome representation

A chromosome is composed of a serie of genes. A gene is an item of the translation hypothesis. As we use a phrase-based SMT, each gene will be associated to a phrase. This encoding makes easier the application of crossover and mutation functions at the phrase level. So, each chromosome c contains -An alignment a between the source and target phrases.

To simplify the notation for the next sections, we define a chromosome c=<f, e, f , e, a>, where f is the phrase segmentation of f , e is the phrase segmentation of e, and a the alignment between the source and target phrases. We denote f j i (respectively e j i ) a phrase from f (respectively e) starting at position i and ending at position j. a i is the position of the target phrase in e aligned with f i . When a i = i for every i, the alignment is monotone.

Initialisation functions

Five functions are used to produce the first population of chromosomes. All these functions, from the input sentence f , produce a phrase segmentation f . After that, they take the best translation (target phrase) of each source phrase determined by the previous segmentation and add it to e. We use the Translation Table (T T ) to select the target phrases. T T contains all information obtained from the training process, applied on a bilingual corpus [START_REF] Och | A systematic comparison of various statistical alignment models[END_REF]. The first three functions produce the initial population by promoting longer phrases, this is useful since long phrases tend to cover more lexical and syntactic relationships between the different items of a solution. With these three functions, we produce three chromosomes. The two other functions use a random segmentation and have the objective to produce more chromosomes. For all the functions the alignment is monotone. Before applying any function, we retrieve all possible phrases from f using T T , and save phrases' length information in the vector P H =< ph 1 , ..., ph n > (Table 1), where ph i is the length of the longest phrase in f starting at position i. We describe the initialization functions in the next sections.

A left-to-right segmentation based on the maximum length of phrases

For this function, the source sentence f is segmented from left to right. The first phrase (segment) is the longest prefix of f that is present in T T . The remaining of f is processed using the same heuristic until f is entirely segmented. For each segment in f , we select from T T the English phrase with the highest probability. Then we concatenate these English phrases in order to obtain the initial translation. Figure 2 shows the result of this function applied to the example of Table 1. Contrary to the first function, here the segmentation is done from right to left. So, the first phrase is the longest suffix of f that is present in T T . The same process is applied until f is entirely segmented. The translation e is generated in the same way as for the first function. Figure 3 shows the result of this initialization for the same example.

A global segmentation based on the maximum length of phrases

In this function non constraint is imposed to the direction of the segmentation. The main idea is to produce a segmentation with the minimum number of phrases. To produce this segmentation, we start by choosing the longest phrase f i in f using the phrases' length information saved in P H. Then we apply recursively the same process for the left and right part of f i until exhaustion of all items f . The Figure 4 shows the result of this segmentation using the P H.

A left-to-right random segmentation

Like for the first function, the source sentence f is segmented from left to right. But, we select randomly from T T a phrase which is considered as a prefix of f . We apply the same process iteratively on the remaining of f . To produce the target sentence e we proceed in the same way as the previous functions. As this function takes random decisions, we use it to produce several chromosomes, one for each produced segmentation.

Crossover function

A crossover operation consists in the following steps:

-Select randomly two chromosomes c1 and c2.

-Select randomly a subpart sp from f respecting some constraints: the first word of sp must be the first word of a segment from c1.f and c2.f , and the last word of sp must be the last word of a segment from c1.f and c2.f . In Figure 5, the chosen segment is "présidence a proclamé le résultat du vote". This segment is a good candidate for crossover because "présidence" is the first word of c1.f 3 and c2.f 2 , and "vote" is the last word of c1.f 4 and c2.f 4 .

-Build c3 by taking sp from c2 (with its segmentation, its English counterpart, and the corresponding alignement). Complete c3 with the left and the right parts from c1.

-Build c4 by taking sp from c1 (with its segmentation, its English counterpart, and the corresponding alignement). Complete c4 with the left and the right parts from c2.

Mutation functions

We use five mutation functions, which modify the aspect of an existing chromosome and allow consequently to produce a new one. These functions are presented below.

Replace-Phrase

We choose randomly a source phrase, and replace its associated target phrase in e by another using T T . The new target phrase must have the highest probability of translation among all the possible translations excluding obviously the one we would like to mutate. Source phrase f i is selectedand randomely and segmented into a left and a right part. These parts must be present in T T . Then, we look for the segmentation of the target phrase aligned with f i such that the target left (respectively right) part can be aligned with the source left (respectively right) part of f i . If it is possible, we build a new chromosome with the updated segmentation and alignement. If not, the left and right parts of f i are translated using the most probable translations in T T . In Figure 6, the segmented source phrase is c1.f 3 .

No translations are present in T T for "a proclamé le résultat" and "du vote .", which exist separately in the aligned target phrase c1.e a 3 . So, we choose new translation for each source phrase from T T .

Merge-Two-Phrases

We choose randomly two adjacent phrases f i and f i+1 , where their aligned target phrases are also adjacent in the target sentence. The achieved phrase after merging f i and f i+1 must exist in T T . If these conditions are met, we merge the selected source phrases into one phrase f i . We do the same process for the target phrases, if the result of this merging exists in T T as a translation of the new source phrase. Otherwise, we choose from the translation table a new target phrase e a i which has the highest translation probability. Finally, we update the segmentation and the alignment in the chromosome.

Merge-Two-Phrases-and-Replace

This function has the same logic as Merge-Two-Phrases, except that we translate directly the new generated phrase using T T , without any verification.

Swap-Two-Phrases

This last function selects randomly two adjacent source phrases f i and f i+1 . After that, we exchange the positions of e a i and e a i+1 in the translation e. This mutation produces a non-monotone alignment.

Evaluation function : log-linear Model

Given a chromosome c =< f, e, f , e, a >, the log-linear approach is used to estimate the quality of the chromosome (translation). In this approach we calculate the logarithmic sum of a set of features functions h m (c), where m is the id of a feature. The result of this logarithmic sum represents the score of the chromosome.

Score(c) = m λ m × log(h m (e, f , a)) (2)
Where λ m is the weight of h m . The value of each weight defines the influence of the corresponding feature in the final score. With this approach, we can add new features, to estimate better the translation. GAMaT uses the following features, which are the same for MOSES [START_REF] Koehn | Moses: Open Source Toolkit for Statistical Machine Translation[END_REF]: As we handle complete translations, the use of the word penalty in the same way as in Moses, the produced translations are shorter than the references. That is why, we define a new word penalty score, using a length translation model. In this model we define a length probability P l (e, f ) for each pair of source and target sentence, which is estimated from the bilingual training corpus as follows:

P l (e, f ) = count(|f |, |e|) count(|e|) (3)
Where count(|f |, |e|) is the number of times that source sentences of length |f | has been translated by target translations of length |e|. count(|e|) is the number of translations of length |e| in the target corpus.

Selection process

The selection process is used in two cases, the first one, to define an elite set from which we will pick chromosomes as parents, to perform genetic manipulations. The elite set contains the k (k < n) best chromosomes of the population. The second selection is applied to select the n best chromosomes, which are kept for the next generation. The selection is based on the score of chromosomes.

Results and comparisons 4.1 Corpora

For our experiments, we use the 9 t h task workshop on Statistical Machine Translation (2014) [START_REF] Bojar | Findings of the 2014 Workshop on Statistical Machine Translation[END_REF]. We take the French-English corpus to evaluate GAMaT and MOSES. The corpus contains 2,000,000 pairs of sentences. After a classical step of corpus preprocessing, we define the following three sentences sets: T rain set that contains 1,323,382 pairs of sentences for the training process. Dev set, that contains 165,422 pairs of sentences for the development process. Finally, T est set which contains 1,000 pairs of sentences to evaluate the decoders. We use GIZA++ [START_REF] Och | A systematic comparison of various statistical alignment models[END_REF] to generate the translation model, and SRILM [START_REF] Stolcke | SRILM at Sixteen: Update and Outlook[END_REF] for language model. MERT [START_REF] Bertoldi | Improved minimum error rate training in Moses[END_REF] is launched on the baseline system (MOSES) then we use the same weights in GAMaT since almost all the probability parameters are calculated by the tools associated to MOSES.

GAMaT parameters

In a genetic algorithm we have four important parameters: the number of chromosomes in the population (n), the number of chromosomes in the elite set, the crossover and mutation rates. We optimized n by varying its value and we found that 120 chromosomes in the population gives the best translation results. The elite set contains the best 75% chromosomes in the population. The crossover rate and the mutation rate fix the number of times which the crossover and mutation functions are applied in each generation. We optimized the crossover and mutation rates empirically. So, in the presented results the mutation and the crossover operations are applied at each iteration to 20% and 40% of the population respectively.

Comparative results

In this section, we present the performance of GAMaT, and we compare them to MOSES. To evaluate the quality of the translations achieved by the two decoders, we use BLEU [START_REF] Papineni | BLEU: a method for automatic evaluation of machine translation[END_REF] and TER [START_REF] Snover | A study of translation edit rate with targeted human annotation[END_REF] metrics. The first one calculates the number of n-gram which exists in the hypothesis and the reference translation at the same time. The second one, TER, calculates a cost of the modifications that we have to apply on hypothesis to obtain the reference translation. In Table 2, we present the BLEU and TER scores for GAMaT and MOSES, where GAMaT-LtM represents GAMaT with the translation length probabilty as feature, and GAMaT-WPS is GAMaT using the word penalty as feature. In the GAMaT+1-MOSES, we add the best translation of MOSES in the initialisation, as a chromosome. The underlying idea is to test if the 1-bets of MOSES can help GAMaT to produce better results. The results show that there is a significant difference between GAMaT and MOSES, in terms of BLEU, however in terms of TER there, the two systems are equivalent. By studying the results, we mean the translations themselves achieved by both systems we found that GAMaT gives, in general, good translations compared to the source sentences. The main problem for GAMaT is the reordering. For some sentences, it has difficulties to apply the good permutations to find the best reordering in the target. Adding the best translation of MOSES in the initialisation process does not improve significantly the result in terms of BLEU, however it outperforms MOSES in terms of TER which is very encouraging. It means that we have to improve the selection process in order to achieve more diversity in the population. So, improvement of the quality of the first population insures the improvement of the final translation. Table 3 shows the number of translations that are better for a system than the other, in terms of TER. We can see that the two decoders give the same translation quality for 287 sentences from 1000. MOSES is better for 366 and GAMaT is better for 347 among them. From this result, we can deduce that each system manages to solve some translation problems better than the other. In the following, we will analyze certain functions of GAMaT in order to understand how to improve it. In Figure 7, we plot the evolution of the population in terms of BLEU. Each curve represents the evolution for one translation. The curves show clearly, that there is no stability in the evolution for the first iterations. This is normal because the population contains a large variety of chromosomes. But, after some iterations the population stabilizes and progresses until convergence. This evolution is a normal evolution for any genetic algorithm, and proves that the decoder manages to increase the quality of translation from an initial population. 4 represent the number of times that these functions were used in the evolution of the best translations. We see that the crossover function is the most used function, with 67%, because this function is the main operation in any genetic algorithm, also because the fixed rate to apply the crossover function is 40%, compared with 20% for all the mutation functions. Also, we can see that the substitution of phrases is the most used mutation, through the Replace-phrase and Merge-Two-Phrases-and-Replace functions. The less used functions are Split-Phrase and Swap-two-Phrases, which is normal for the French-English pair, because the reordering can be covered by long segments. In order to fix the problem of reordering we tried to force GAMaT to use more the Swap-two-phrases function, but the results were not better.

Conclusion and perspectives

In this paper, we presented GAMaT, a new decoder for the SMT. This decoder is based on a genetic algorithm which allows to use a set of complete translations. The obtained performance for the French-English pair are promising but not yet better than MOSES in terms of BLEU but they are equivalent in terms of TER. However, GAMaT succeeds to propose better translations in 34.7% of cases and gives identical results in 28,7% of cases.

Analysing the produced translations, we noticed that GAMaT suffers from the mismanagement of the reordering process.

To outperform MOSES, we will mainly optimize the feature's weights independently from MOSES. In fact, we use exactly the same weights produced by MOSES, we have to set up them, for instance by an evolutionary algorithm. The confidence measures [START_REF] Raybaud | Detecting errors in machine-translated sentences[END_REF] also will be used in order to guide better the genetic operations.

Figure 1 -

 1 Figure 1 -Genetic Algorithm for SMT

Figure 2 -

 2 Figure 2 -Example of the left-to-right segmentation based on the maximum length of phrases

Figure 3 -

 3 Figure 3 -Example of the right-to-left segmentation based on the maximum length of phrases

Figure 4 -

 4 Figure 4 -Example of the global segmentation based on the maximum length of phrases

3. 2 . 5 A

 25 right-to-left random segmentation This second random segmentation function proceeds from right to left contrary to the previous one. Iteratively we choose a random suffix of f in the not yet segmented part of f as a new phrase, and which exists in T T . Like for the previous function, we use this function to generate several chromosomes.

Figure 5 -

 5 Figure 5 -Crossover function

Figure 6 -

 6 Figure 6 -Split mutation example

-h 1 :

 1 Language model probability -h 2 : Direct translation probability -h 3 : Inverse translation probability -h 4 : Direct lexical weighting probability -h 5 : Inverse Lexical weighting probability -h 6 : Phrase penalty -h 7 : Word penalty -h 8 : Reordering model

Figure 7 -

 7 Figure 7 -Evolution of the population, using BLEU, for 3 different sentences

Table 1 -

 1 Length phrases table

	madame	la président	,	la prśidence	a proclamé	le résultat	du vote	.
	5	4	2	2 5	3	7	3	5	4	3	2	1

Table 2 -

 2 GAMaT and MOSES performances using BLEU, TER

	Decoder	BLEU TER
	MOSES	29.32 53.02
	GAMaT-WPS	26.13	53.34
	GAMaT-LtM	27.15 53.08
	GAMaT+1-MOSES 27.22	52.81

Table 3 -

 3 Comparison between GAMaT and MOSES for each sentence, using

	TER
		Nbr-setences	%
	Equal	287	28.70
	MOSES better	366	36.60
	GAMaT better	347	34.70

Table 4 -

 4 Influence of crossover and mutation functions on final translations

	Function	Nbr	%
	Crossover	4491 67,92
	M-Replace	858 12,98
	M-Swap	345	5,22
	M-Split	334	5,05
	M-Merge	584	8,83
	M-Merge+Replace 593	8,97