Charanpal Dhanjal
email: charanpal.dhanjal@lip6.fr

Nicolas Baskiotis

Stéphan Clémençon

Nicolas Usunier

An Empirical Comparison of V -fold Penalisation and Cross Validation for Model Selection in Distribution-Free Regression

Model selection is a crucial issue in machinelearning and a wide variety of penalisation methods (with possibly data dependent complexity penalties) have recently been introduced for this purpose. However their empirical performance is generally not well documented in the literature. It is the goal of this paper to investigate to which extent such recent techniques can be successfully used for the tuning of both the regularisation and kernel parameters in support vector regression (SVR) and the complexity measure in regression trees (CART). This task is traditionally solved via V -fold crossvalidation (VFCV), which gives efficient results for a reasonable computational cost. A disadvantage however of VFCV is that the procedure is known to provide an asymptotically suboptimal risk estimate as the number of examples tends to infinity. Recently, a penalisation procedure called V -fold penalisation has been proposed to improve on VFCV, supported by theoretical arguments. Here we report on an extensive set of experiments comparing V -fold penalisation and VFCV for SVR/CART calibration on several benchmark datasets. We highlight cases in which VFCV and V -fold penalisation provide poor estimates of the risk respectively and introduce a modified penalisation technique to reduce the estimation error.

Introduction

Learning algorithms generally depend on a small number of real-valued or discrete parameters such as the size of a tree in hierarchical methods, the stopping criteria in boosting algorithms or explicit regularisation/smoothing parameters. These parameters naturally determine the complexity of the output function, and by doing so, also strongly influence generalisation ability. In a general sense the more "complex" the learnt function is, the more likely it is to overfit to the data. On the contrary, a simple predictor will be suboptimal if the data is informative with regard to the learning problem. From the model selection point of view the challenge consists in selecting values of the parameters of interest with a theoretical risk as small as possible. From a global perspective, there exist essentially two major approaches to model selection: methods related to data-splitting, with cross-validation [START_REF] Allen | The relationship between variable selection and data augmentation and a method for prediction[END_REF] and its variants, and methods related to penalisation of the empirical risk (that obtained on the training set), with in particular the Structural Risk Minimisation principle [START_REF] Vapnik | Ordered risk minimization[END_REF]. Penalisation-based approaches aim to approximate the ideal model by adding a penalty or complexitybased term to the empirical risk, generally based on theoretical arguments (i.e. on probabilistic distribution-free upper bounds for the excess of risk). V -fold cross-validation (VFCV in abbreviated from) is widely used in machine-learning practice due to its (relative) computational tractability and empirical evidence of its good behaviour. However, there is little theoretical justification concerning VFCV [START_REF] Arlot | A survey of cross-validation procedures for model selection[END_REF] and the question of an automatic choice of the parameter V remains widely open [START_REF] Breiman | Submodel Selection and Evaluation in Regression. The X-Random Case[END_REF]. On the other hand, penalisation procedures generally suffer from two possible drawbacks, despite the fact that they are theoretically wellfounded: either they are designed in a simplified framework and thus are not robust to complex situations (typically the case for Mallows' C p in regression [START_REF] Mallows | Some comments on C p[END_REF]), or they are of general purpose, as for instance the so-called Rademacher complexities [START_REF] Bartlett | Rademacher and gaussian complexities: risk bounds and structural results[END_REF], but are inaccurate in many cases. In order to refine Rademacher penalties, several authors proposed localisation techniques, giving rise to local Rademacher complexities [START_REF] Koltchinskii | Local Rademacher complexities and oracle inequalities in risk minimisation[END_REF], but these more accurate capacity functions are essentially of theoretical interest and cannot be used in practice due to the presence of unknown constants in their definition.

Combining both the robustness of crossvalidation estimates and theoretical guarantees of penalisation procedures, a new type of general purpose penalisation procedures, called V -fold penalisation, has been recently proposed [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. Both empirical and mathematical evidence of its efficiency have been shown in a heteroscedastic with random design regression framework, when considering the selection of finite-dimensional histogram models. While the selection of regressograms studied in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] is convenient for theory since it allows precise mathematical investigations and is however general enough to show some relevant complex phenomena, we investigate in this paper the behaviour of V -fold penalties, and compare it to VFCV, for the tuning of the hyperparameters involved in the Support Vector Regression algorithm (SVR, [START_REF] Drucker | Support vector regression machines[END_REF]) and Classification and Regression Trees (CART, [START_REF] Breiman | Classification and regression trees[END_REF]) for regression. Indeed, these algorithms are two of the most extensively used regression tools in a wide variety of areas and the choice of efficient hyperparameters is known to be a decisive step of the learning process to attain good generalisation performance. Model selection for SVR has been addressed by several authors and many attempts, theoretically well-founded, have been proposed to answer this problem, among which: estimation of the hyperparameters from the data and the level of noise [START_REF] Smola | Asymptotically Optimal Choice of ǫ-Loss for Support Vector Machines[END_REF][24] [START_REF] Cherkassky | Practical selection of SVM parameters and noise estimation for SVM regression[END_REF], leave-one-out bounds for SVR [START_REF] Chang | Leave-One-Out Bounds for Support Vector Regression Model Selection[END_REF]. However, methods based on resampling procedures for the evaluation of the risk of each model have been proven to be significantly better than most of the other proposed automatic procedures [START_REF] Cherkassky | Practical selection of SVM parameters and noise estimation for SVM regression[END_REF][START_REF] Ong | An improved algorithm for the solution of the regularization path of support vector machine[END_REF] and VFCV is generally the chosen method in practice [START_REF] Smola | A tutorial on support vector regression[END_REF]. For CART regression, the issue of model selection has not received as much attention, however [START_REF] Gey | Model selection for cart regression trees[END_REF] provides a theoretical validation of the standard CART pruning criterion. In this paper, our aim is to study V -fold penalisation for model selection and give insights into situations when one can improve on VFCV in practice. Particularly, the comparison of V -fold penalisation with VFCV on the problem of SVR and CART calibration takes importance, due to the highlighted relevance of VFCV in this central issue.

The remainder of this paper is organised as follows: Section 2 describes the statistical framework related to model selection for kernel SVR and CART. In Section 3 we recall VFCV and related works, we introduce in Section 4 V -fold penalisation and our improved penalisation approach. Experiments are addressed in Section 6, and conclusions are presented in Section 8.

Background and Preliminaries

As a first go, we outline the statistical setting of the model selection we shall subsequently study (generally referred to as the distribution-free regression setup). Here and throughout, a column vector is written in bold lowercase e.g. x. Let X × Y be a measurable space endowed with an unknown probability measure P , with Y = R. X is called the input space and is usually a compact subset of R d , d ≥ 1, and Y is the target space. We observe n i.i.d. labelled observations or examples S = {(x 1 , y 1 ) , . . . , (x n , y n )} ⊂ X × Y. Furthermore, (X, Y ) denotes a generic random variable, independent from the data S, drawn from P . Let S be the set of all measurable functions s : X → Y mapping from the input to target space. In the present paper, focus is on the mean absolute deviation:

L(s) = E[|s(X) -Y |].
The regression task can thus be rewritten in these notations as finding minimum of the so-called least absolute Bayes loss s * , defined by:

L(s * ) = min s:X →Y L(s).

Support Vector Regression

The SVR prediction function is of the form f (x) = w, x + b where w ∈ R d is a weight vector and b is a constant. In this case, one is interested in errors greater than a user-defined value ǫ ∈ R + (known as the ǫ-insensitive loss). Hence the optimisation task can be written as:

t = arg min w,b 1
2 w 2 + C n i=1 (ξ i + ξ * i ) s. t. y i -w, x i -b ≤ ǫ + ξ i w, x i -y i + b ≤ ǫ + ξ * i ξ i , ξ * i ≥ 0, (1)
where ξ i and ξ * i are slack variables, and C is a userdefined trade-off between minimising the norm of the weight vector w (which can be seen as regularisation) and penalising errors greater than ǫ. A high value of C thus corresponds to a low regularisation level and the objective becomes then closer to that of minimising the empirical risk. The value of ǫ affects the number of Support Vectors (SV's in short), with larger values resulting in fewer SV's. In a slight abuse of notation, minimum values of w and b form a prediction function t. The SVR algorithm is often performed using kernels to model non-linear functions, where a kernel function κ : X ×X →R is used to find the inner product of the transformation of the input space X into its associated Reproducing Kernel Hilbert Space (RKHS), denoted by H κ . Note that κ can be written in terms of a transformation φ from input to kernel space u, v Hκ = φ(u), φ(v) = κ(u, v). Kernels functions usually depend on one or a few hyperparameters, e.g. polynomial, Gaussian Radial Basis Function (RBF) and sigmoid kernels [START_REF] Schölkopf | Learning with kernels[END_REF]. The Gaussian RBF kernel is one of the most commonly used kernels and Boser, Guyon and Vapnik suggested its widespread use [START_REF] Boser | A training algorithm for[END_REF][19] [START_REF] Vapnik | The nature of statistical learning theory[END_REF]. In the experiments described in Section 6, we therefore consider the Gaussian RBF kernel,

κ γ (x, x ′ ) = exp(-γ x -x ′ 2 ),
which depends on one real-valued positive parameter γ. In the following we denote the Gaussian RBF kernel κ γ , γ ∈ R + . The optimal value of the regularisation parameter C can significantly change, and depends on the data. To ensure the performance in prediction of the SVR algorithm, the regularisation parameter, as well as the kernel, should thus be calibrated in each application. Formally, the question to be addressed is to find the best parameters (γ, C, ǫ) in terms of prediction. We thus aim at estimating the oracle, which is the model with the smallest risk, (where t (γ, C, ǫ) is the SVR learnt using parameters γ, C, ǫ), arg min

(γ,C,ǫ)∈R 3 + L (t (γ, C, ǫ)) ,
which is unknown since it depends on the law P of data and which optimises the least squares error.

CART Regression

Another important algorithm for regression is CART in which one learns a tree like the one exemplified in Figure 1. To regress a new example x, it is filtered down to a leaf node via a decision at each link and then assigned a real number target. In the illustration, if the first feature of x, x (1) ≤ θ 1 , for some threshold θ 1 , then it is labelled 0.0. Similarly, if x (1) > θ 1 and x (2) > θ 3 then the example is labelled -0.3. Regression trees have been successfully used in a variety of applications in such as vector quantisation [START_REF] Chou | Optimal pruning with applications to treestructured source coding and modeling. Information Theory[END_REF], meteorology [START_REF] Burrows | Cart regression models for predicting uv radiation at the ground in the presence of cloud and other environmental factors[END_REF] and medicine [START_REF] Wernecke | Validating classification trees[END_REF] for example, and have the crucial advantage of being easy to interpret and easy to compute. To construct a regression tree one starts with The optimal feature-threshold pair k * , θ * is found by minimising the squared error of the split, i.e. k * , θ * are found using:

arg min k,θ (x,y)∈SL (y -µ SL ) 2 + (x,y)∈SR (y -µ SR ) 2 s. t. S L = {(x, y) ∈ S 0 | x (k) ≤ θ} S R = {(x, y) ∈ S 0 | x (k) > θ},
where µ SL = 1 |SL| (x,y)∈SL y and µ SR = 1 |SR| (x,y)∈SR y are the mean labels for the left and right nodes and hence (y -µ S0 ) 2 is the squared error between y and the mean label. A simple way to solve this optimisation is to iterate through each feature and threshold and choose the one with the lowest objective value. After splitting on the root node, one recursively splits on the resulting child nodes until no more splits are possible, i.e. a node contains fewer examples than a user defined value ℓ. Following the growing phase, one prunes the resulting tree as smaller trees have been shown to improve generalisation error. In CART, one uses an approach called cost complexity pruning which generates a series of trees pruned from the original tree and then selects one of the trees in the sequence. For the ith node in the unpruned tree which contains examples S i , one computes the error if the tree was pruned at that node and compares it to the error if the subtree starting at that node R i is kept. The difference in these errors divided by the number of leaves of the subtree gives an indication of the error difference per leaf, i.e.

α i = L(S i , Ri ) -L(S i , R i ) |R i | l -| Ri | l , in which L(S i , R i ) is the squared error of a set of examples S i using subtree R i , Ri is the root of R i , and
|R i | l is the number of leaves in R i .
In simple terms, the higher the value of α i , the bigger the reduction in error of the subtree per leaf. One can compute α i for all nodes in the tree and hence, if we prune nodes with α i greater than a threshold σ ∈ {α 1 , . . . α |T | }, where |T | is the number of nodes in the tree, we obtain a sequence of trees which decrease in size as σ increases. Instead of choosing σ directly in the model selection stage, we pick a threshold t and choose the largest tree smaller or equal in size to t. Therefore, as before, the model selection task can be written in terms of search for the parameter t. We aim at estimating the oracle (where f (t) is the decision tree learnt using parameter t), arg min

t∈Z L (f (t)) ,
Estimating the oracle is a model selection task, each model being represented here by a fixed value of t, where penalisation is a natural way to proceed, as explained in Section 4 below. However, let us first briefly recall the method which is usually employed for model selection, namely V -fold cross-validation.

V -fold Cross Validation

The idea of cross-validation for model selection is to estimate the risk of the considered estimator on each model by using a repeated data-splitting scheme, and then to select the model that minimises these estimates of the risk. The fact that data-splitting strategies give accurate estimates of the risks only relies on the independence between each training and testing set. Consequently, the interest of CV is that it is based on a heuristic that can be applied with great universality. Many data-splitting rules have been proposed, such as leave-one-out (LOO, [START_REF] Allen | The relationship between variable selection and data augmentation and a method for prediction[END_REF]), leave-p-out (LPO, [START_REF] Shao | Linear model selection by cross-validation[END_REF]), balanced incomplete CV (BICV, [START_REF] Shao | Linear model selection by cross-validation[END_REF]), repeated learning-testing (RLT, [START_REF] Breiman | Classification and regression trees[END_REF]). V -fold cross-validation (VFCV) was introduced by Geisser [START_REF] Geisser | The predictive sample reuse method with applications[END_REF], see also [START_REF] Breiman | Classification and regression trees[END_REF] as a computationally efficient alternative to LOO cross validation. We will consider primarily VFCV, which is certainly the most commonly used crossvalidation rule in practice. Moreover, it is generally the procedure which is considered for the calibration of the SVR hyperparameters [35] [21]. In VFCV, the examples are partitioned into V subsamples of n/V examples each (with a maximal deviation of one) B 1 , . . . , B V . At the jth fold one trains on S \ B j and then evaluates the error on B j , and one averages the errors over all V folds. For model selection this is repeated over a grid of parameters in order to select those with the lowest error. Despite the generality of the heuristic underlying the procedure, there are two drawbacks in the V -fold cross-validation method for model selection. First, at a fixed V , the procedure is known to be asymptotically suboptimal in the sense that the risk of the selected estimator is not equivalent to the risk of the oracle when the number of data tends to infinity. More precisely, [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] shows in a heteroscedastic with random design regression framework, that VFCV with fixed V satisfies an oracle inequality with a constant A > 1 which relates the excess risk of the selected model to the excess risk of the oracle, and that this suboptimal constant cannot be improved asymptotically. The keystone of such a result is that at a fixed V , the VFCV criterion is biased compared to the true risk [9][31]. Indeed, since the validation sets are independent of their respective training sets, the expectation of the VFCV criterion can be related to the expectation of the true risk

E[crit VFCV s (Q)] for a learner s with parameter set Q ∈ Q as follows, E L (j) S s (-j) (Q) = E L s [-1] (Q) ,
where

s [-1] (Q) is the output of the learner trained with (1 -1/V ) n i.i.d. examples, s (-j)
is the learner trained with S \ B j , and L

S is the loss with respect to the partition B j of S. Since the true risk generally decreases with more data, it appears that the expectation of VFCV criterion roughly overestimates the expectation of the true risk, and that this bias should be decreasing whenever V increases. The previous observation suggests that, in order to mimic the oracle in terms of performance in prediction, one should take a V which is as large as possible. This is where appears the second drawback concerning VFCV: there is no rule in practice to choose the optimal V . Indeed, the best CV estimator of the risk is not necessarily the best model selection procedure, and [START_REF] Breiman | Submodel Selection and Evaluation in Regression. The X-Random Case[END_REF] highlight that LOO is the best estimator of the risk, whereas 10-fold cross-validation is more efficient for model selection purpose. This can be explained by the fact the bias in the VFCV estimation of the risk is actually an advantage for model selection with a few or medium number of examples, contrary to the asymptotic framework. Indeed, as claimed in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] a slightly over-pessimistic estimation of the risk, as in VFCV, gives for a fixed number of observations a more robust model selection procedure and roughly contradicts the bad effects of the variance of risk estimation.

V -fold Penalisation

Penalisation is a natural strategy for the task of estimating the oracle s (Q * ). Indeed, the definition of the oracle can be rewritten as the sum of the empirical loss and an unknown term, which is thus an ideal penalty in the sense that it allows one to recover the oracle:

arg min Q∈Q L S (s (Q)) + pen id (Q) ,
in which s(Q) is a function mapping from input to target space under hyperparameters Q, and the ideal penalty is as follows,

pen id (Q) = L (s (Q)) -L S (s (Q)) .
Hence, penalisation aims at mimicking the oracle by selecting, for a known penalty function the estimator arg min

Q ∈Q L S (s (Q)) + pen (Q) .
A good penalty in terms of prediction is one which gives an accurate estimate of the ideal penalty pen id . The central idea of V -fold penalties proposed in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] is to directly estimate the ideal penalty by a subsampled version of it. For some constant

C V ≥ V -1, the V -fold penalty pen VF (Q) is C V V V j=1 L S (s (-j) (Q)) -L (-j) S (s (-j) (Q)) ,
and so the corresponding selected hyperparameters are given by arg min

Q∈D L S (s (Q)) + pen VF (Q) ,
where D is a discrete grid upon the set Q. The V -fold penalty indeed mimics the structure of the ideal penalty, in such a way that the quantities related to the unknown law of data P (respectively to the empirical measure P S ) are replaced by quantities related to the empirical measure P S (respectively to the subsampling measures P (-j) S

), in the same analytic manner. The design of the V -fold penalties is thus an adaptation of Efron's resampling heuristics [START_REF] Efron | Bootstrap methods: another look at the jackknife[END_REF] to the subsampling scheme of the V -fold procedure. It has been shown in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] by considering the selection of regressograms in a heteroscedastic regression framework, that V -fold penalisation with C V = V -1 is asymptotically optimal for a fixed V , whereas in this case, VFCV is asymptotically suboptimal, due to its bias on the estimation of the risk. Moreover, the choice of C V = V -1 in the definition of the V -fold penalty corresponds to the Burman's corrected VFCV criterion [START_REF] Burman | A comparative study of ordinary cross-validation, v-fold cross-validation and the repeated learning-testing methods[END_REF]. Therefore, we use in our experiments C V = V -1 although we also explore different values. Another advantage, highlighted in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF], of V -fold penalisation, compared to VFCV, is that it seems to be more regular with respect to the choice of V . At a heuristic level, this can be explained by observing that since V -fold penalisation corrects the bias of VFCV, it is only variability of V -fold estimates that matters here, a variability which is smaller for a larger V . Finally, it should be noted that the constant C V in the definition of the V -fold penalty can be viewed as a degree of freedom, which potentially allows to deal with the bias of the proposed risk estimation, without varying the value of V , contrary to VFCV where only V fixes simultaneously and in a tricky manner, the bias and variance of the risk estimation. In [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] it is shown that choosing C V to overpenalise (i.e. pen VF is larger than pen id even in expectation) can improve prediction performance when the signal to noise ratio is small. The choice is a difficult one however, and according to empirical results on synthetic datasets, it depends on the sample size, noise level and smoothness of the regression function.

A Complexity-Based Selection of C V

In practice, as we shall later see, for a fixed training set and V , the approximate penalty as given by pen VF often poorly approximates the ideal penalty and it cannot be improved by varying the penalisation constant C V . To study the cause of the problem we analyse the pen VF criterion relative to the ideal penalty. Consider the first term in the sum of pen VF , L S s (-j) (Q) , and write it in terms of the loss on the training and test set:

1 n i∈S (-j) ℓ i (s (-j) (Q)) + 1 n i∈S (j) ℓ i (s (-j) (Q)) = V -1 V L (-j) S (s (-j) (Q) + 1 V L (j) S (s (-j) (Q),
in which ℓ i (•) is the loss for the ith example. The link between the lines can be seen by noting that

L (-j) S (s (-j) (Q) = V (V -1)n i∈S (-j) ℓ i (s (-j) (Q)).
When we put the above form of L S s (-j) (Q) into pen VF we obtain

CV V 1 V V j=1 L (j) S s (-j) (Q) -L (-j) S s (-j) (Q) ,
and the term inside the square brackets is the empirical expectation of the error on the test set minus the error on the training set. One can say that this an approximation of the ideal penalty using (V -1)n/V examples since the loss term on the right side is computed over S \ B j . A variety of error bounds have the penalty proportional to a complexity measure and inversely proportional to the number of examples to some power of a learning rate β(Q) (see [START_REF] Liang | On the interaction between norm and dimensionality: Multiple regimes in learning[END_REF] for example). In other words, for a learner s with parameters Q we consider the following form of the penalty:

pen V (Q) = C V V D(Q) (n(V -1)/V ) β(Q) (2)
where D(Q) is the complexity of s(Q) and β(Q) is a learning rate, and we have replaced the square bracketed term in pen VF with D(Q)/(n(V -1)/V ) β(Q) . A learning rate of 0 implies a large penalty and that we have overfitted the data and hence, for a fixed V and sample size we do not learn anything (in other words one predicts on a test set randomly). As the sample size increases one continues to overfit and hence the penalty term is C V D(Q)/V regardless of the sample size. In contrast when β(Q) = 1 the penalty is small, and rapidly decreases with the sample size, and also with V . A limit of 1 for β(Q) is natural for the learning rate since this is the bound often used in complexity bounds. The ideal penalty has the form

D(Q)/n β(Q)
for n examples and hence we would like to choose C V above so that

C V V D(Q) (n(V -1)/V ) β(Q) = D(Q) n β(Q) , (3)
and solving gives

C V = (V -1) β(Q) /V β(Q)-1
. A learning rate of 0 which occurs with complex models (e.g. large decision trees) implies C V = V and similarly for small models where β(Q) = 1 we have C V = V -1 as suggested asymptotically above. In this latter case we recover exactly the value of C V suggested in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF]. On the whole, pen V (Q) is an estimation of the ideal penalty using pen VF and the model complexity D(Q). It remains to consider how one computes the learning rate. We equate Eq. ( 2) with pen VF and then taking logs results in log(pen

V F (Q)/C V ) equal to -log(V ) -β(Q) log(n(V -1)/V ) + log(D(Q)).
One finds the gradient of log(pen V F (Q)/C V ) + log(V ) versus log(n(V -1)/V ) for a selection of different V values whilst fixing Q and n, in order to find the learning rate β(Q).

Experimental Setup

We study the behaviour of VFCV and V -fold penalisation on a collection of benchmark datasets. The scikit-learn library in Python [START_REF] Pedregosa | Scikit-learn: Machine Learning in Python[END_REF] is used to generate the output of the RBF SVR and CART algorithms.

In total, 10 datasets from the UCI machine learning repository [START_REF] Frank | UCI Machine Learning Repository[END_REF] and DELVE [START_REF] Neal | Assessing Relevance Determination Methods Using DELVE[END_REF] are used. Each dataset is split into 100 training and test realisations/sets after being processed so that the examples and labels have zero mean and unit standard deviation. Details are provided in Table 1. When comparing model selection algorithms, a statistically significant improvement of one method over another is such that the mean error is greater and by using a paired t-test. For the t-test we take the sample of errors over all realisations for 2 methods, then compute a p value and reject the null hypothesis, that the means are equal, if p < 0.1. In all experiments we use the mean absolute error, i.e. for a prediction function f : X → Y, the error is

1 n n i=1 f (x i ) -y i 1 .

Dataset

Model Selection

In all of the following experiments we use a grid to approximate the set of hyperparameters. The SVR penalty is chosen as C {2 -10 , 2 -8 , . . . , 2 12 }, the kernel width as γ ∈ {2 -10 , 2 -8 , . . . , 2 2 }, and ǫ ∈ {2 -4 , 2 -3 }. More sophisticated ways of searching in the hyperparameter space actually exist, such as the iterative process derived from the socalled active sets method and used in [START_REF] Hastie | The entire regularization path for the support vector machine[END_REF][START_REF] Cherkassky | Practical selection of SVM parameters and noise estimation for SVM regression[END_REF][START_REF] Ong | An improved algorithm for the solution of the regularization path of support vector machine[END_REF] to walk along the entire path of the SVR: γ is fixed and all values of C are considered. Others heuristics involve e.g. genetic algorithms [START_REF] He | Model optimizing and feature selecting for support vector regression in time series forecasting[END_REF], local search methods [START_REF] Momma | A pattern search method for model selection of support vector regression[END_REF]. However, some degeneracies can occur and so, a search on a grid should be more stable. Moreover, the grid-search has also the advantage of being easily parallelised, because each value of (γ, C, ǫ) is independent from the others. In the case of CART regression, we pick the bound on the tree size t from {2 1 -1, round(2 1.5 -1), . . . , 2 7 -1}.

An important characterisation of the model picked during the selection phase is its complexity. In all of the model selection techniques we choose a set of parameters over n(V -1)/V examples however the final predictor is training using all n examples. Ideally, we would like the complexity to be identical in both model selection and whilst training using all examples, since the penalty is a function of complexity (Equation 2). For the SVR the norm of the weight vector is the measure of complexity used in error bounds (see [START_REF] Smola | A tutorial on support vector regression[END_REF]). For this reason, we compute the mean norm of the SVR weight vector w , for each value of C, γ, ǫ used in model selection and store w * , the norm corresponding to the lowest error, as well as the corresponding values γ * , ǫ * . When we train using all n examples, we again compute w 's corresponding to each value of C, for γ * , ǫ * , and choose C with corresponding norm closest to w * . In the case of CART trees, we can be slightly more direct: for the optimal bound on the tree size, t * , we compute the real mean tree size found during model selection and round to the nearest integer t. The value of t is then used to train over all n examples.

Primary Setup

In order to test the model selection techniques we take random training subsamples of either 50, 100 or 200 examples of the learning sets to observe model selection on a limited number of examples. Furthermore, we test using 2, 4, . . . , 12 folds. Model selection is performed using each subsample and then SVR or CART is trained using the optimal parameters and the entire subsample. This is repeated for each realisation and results are averaged over the entire set of realisations. As well as recording the error obtained using model selection over the realisations, we also store the difference between the "ideal" and approximated penalty. This former quantity is computed simply as the difference between the V -fold penalty and the penalty as computed using the test set. All results for Vfold penalisation are evaluated with C V = (V -1)α with α ∈ {0.6, 1.2, . . . , 1.6} being the multiplier for the penalisation. We denote the types of model selection methods as: VFCV, V -fold penalisation (PenVF) and V -fold penalisation using a learning rate (PenVF+).

For the PenVF+ method one needs to compute learning rates for each model (set of parameters). We use the same training sets as above and vary V from the set {2, 3, . . . , 12}. The quantities log(pen V (Q)) + log(V ) versus log(n(V -1)/V ) are computed and the gradient, found using linear regression, provides β(Q) which in turn is used to calculate C V = (V -1) β(Q) /V β(Q)-1 . As this estimation of β(Q) can be unstable especially with small training sets we clip its value to lie within the valid range [0, 1].

Experimental Results

Comparison of Penalisation and

VFCV with V = 2

We start by studying the SVR results in Table 2 which shows errors for all datasets when V = 2, α = 1.0. We consider V = 2 in this case since it provides the greatest distinction between the model selection methods. For PenVF+ many of the results are comparable to VFCV when we also consider the standard deviations.

As the same time, PenVF+ does not always improve upon PenVF. In contrast PenVF can perform significantly worse than both VFCV and PenVF+, for example with abalone, winequality-red and winequality-white. Also of note is that the difference in error between VFCV and PenVF does not improve with m = 200 with abalone for example: it is 0.08, 0.089, 0.089 with m = 50, 100, 200. Also shown at the bottom of Table 2 is the equivalent CART results. It is evident that error rates are generally worse than the SVR with the exception of pumadyn-32nh. Also, we see that penalisation provides a larger advantage relative to VFCV in this case. One explanation is that CART is more sensitive to its hyperparameters. We observe that PenVF+ is equivalent or improves over VFCV in nearly every case, and there are 5, 7, 7 wins for m = 50, 100, 200 respectively. Again we see that PenVF performs poorly with abalone, winequality-red and winequality-white.

Paired t-test Comparison with VFCV

Table 3 shows the results of the paired t-tests to compare PenVF with α = 1.0 and PenVF+ with VFCV. Consider first the SVR results. Here we see that as one might expect, there are few statistically significant differences between 10-fold CV and PenVF. Indeed, results indicate that as V increases the penalisation methods and VFCV become more similar. In particular we see that PenVF+ is identical to VFCV in all but one or two cases, with the main exception being 5 draws with m = 200 and V = 2, in which there are 2 improvements and 3 losses (abalone, pumadyn-32nh and winequality-red). PenVF fares worse against VFCV: we see more wins but at the same time more Table 2: Error rates (with standard deviations in parentheses) for cross validation with the SVR (top) and CART (bottom) and penalisation for V = 2, α = 1.0. Statistically significant improvements over VFCF are in bold. With the SVR, PenVF+ is generally comparable to VFCV and PenVF is more variable. With CART, the penalisation methods both improve over VFCV a number of times. losses. Our later analysis will shed light on why this is the case. We also compared the "ideal" model, in which the test set is used during model selection, with VFCV and found that one can generally gain improvements except in the case of sliceloc, which has a large number of features. In every case the ideal model selector can improve over 2-fold CV.

The CART results at the bottom of Table 3 show that for V > 4 penalisation is identical to VFCV. Clearly the bias with low values of V in conjunction with VFCV is more prominent in this case. We have already examined the V = 2 case and with V = 4 we see improvements in one case for PenVF+ for m = 50, 200. With the ideal errors we see that with more of the datasets compared to SVR, performance cannot be improved by using the test realisation and furthermore as m increases improvements over VFCV are increasingly difficult except for the 2-fold case.

Optimal Penalisation Constant is Dataset Dependent

To discover the effect of overpenalisation, observe Figure 2 which shows the errors on 2 datasets as α varies when V = 10. The effect of α is clearly dataset dependent: on abalone observe that the error tends to decrease with the SVR with more penalisation, and hence a slight amount of overpenalisation (α = 1.2) is recommended. In contrast, overpenalisation increases the error with slice-loc.

In total, 5 of the datasets benefited from overpenalisation and 3 improved with underpenalisation.

With pumadyn and parkinsons-total, a value of α = 1.0 as predicted by the theory gave optimal results. Results were similar with CART except that 7 of the datasets benefit from underpenalisation. Notice that as sample size m increases the choice of α becomes less important since estimates of error for each model are more reliable and the penalty terms become small. We noticed that with Table 3: Number of statistically significant losses (left block), draws (middle block) and wins (right block) against standard errors for CV and across different numbers of folds using α = 1.0. The sample size m is 50 (top), 100 (middle), and 200 (bottom). As V increases the penalisation methods become more similar to VFCV. In particular for CART, when V > 4 penalisation is identical to VFCV.

CART, VFCV consistently underestimates the tree size whereas PenVF chooses larger sizes in general and this can be an advantage or disadvantage depending on the variation of error with t. Also observed is that as expected VFCV provides a pessimistic error compared to the ideal case and PenVF is generally more accurate than VFCV, however, as in model selection since we pick the model with the lowest error, this does not always translate into the best predictor.

On the Estimation of the Ideal Penalty

Next we study the approximated penalty and how it differs from the "ideal" penalty in the case of CART with V = 2, see Figure 3. Notice that the curves for PenVF and PenVF+ are shorter than the ones for the "ideal" penalty since only half the examples are used for training, limiting the tree size. The PenVF method diverges from the ideal case when we grow large trees, but is close to the ideal case for small trees. This change occurs with relatively small trees: size 4 with m = 50 and size 11 with m = 100. This pattern was observed with most of the datasets. When we looked at a greater number of folds, PenVF was close to the ideal penalty. In contrast, PenVF+ does not diverge as the tree size increases, however it seems to slightly overestimate the penalty.

The question remains about which cases PenVF improves over VFCV for low values of V for CART. Figure 4 demonstrates that the error estimation for PenVF is generally optimistic as model size increases. With abalone example the optimal tree was of size 7 nodes, however PenVF chooses one of size 22. In contrast, on some datasets large trees did not overfit the test set and hence in these cases PenVF can perform better than VFCV. This also sheds some light on Figure 2 where we see that overpenalisation helps in some cases but not in others. PenVF+ provides the best estimate of the error in general, however it also results in a larger tree size that the ideal case.

Extended Setup

In this final set of experiments we explore further the distinction between penalisation and VFCV with CART by considering m = 500 and using the same set of folds as in the original setup, see Table 4. The interesting figures in this case are those corresponding to 2 and 4 folds in which we see that PenVF+ wins for 8 and 2 datasets respectively. In fact, since in the ideal case one can only win 8 times with V = 2 this certainly demonstrates the effectiveness of PenVF+ and bias in VFCV in this case.

Key Points

Our experimental analysis has painted a detailed picture of penalisation versus cross validation for model selection. The bias in VFCV is evident with small values of V and small training sets, and we observed that as V and the training set sizes increase the model selection methods become more similar. With the SVR, PenVF makes a number of loses relative to VFCV and these losses are nearly all corrected with our modified penalisation PenVF+. Penalisation is more effective in general with CART: when V > 4 both PenVF and PenVF+ are not statistically significantly different to VFCV, and for V = 2, PenVF+ is at least as good as VFCV or improves over it in nearly every case, winning 5, 7, 7 times for m = 50, 100, 200 examples. In contrast PenVF is more variable in comparison to VFCV and one reason for this is that it underestimates the penalty to a large degree with large models. On some datasets larger trees did not increase the error and hence in these cases PenVF performs well. In general PenVF+ provides a much better approximation of the ideal penalty compared to PenVF. The most striking results were with CART and V = 2 in which we saw that PenVF+ improves over VFCV in 8 out of 10 cases with m = 500 examples.

Conclusions

Model selection is a critical part of machine learning as it can dramatically affect generalisation performance. In practice, cross validation over a grid of parameter values is often used, and it has been shown to be very effective in a variety of cases. We studied V -fold penalisation which is a general purpose penalisation procedure that aims at improving on VFCV by correcting its bias and is proved in [START_REF] Arlot | V -fold cross-validation improved: V -fold penalization[END_REF] to be asymptotically optimal in a histogram regression setting. V -fold penalisation is simple to implement and the penalised error can be computed using the same predictions as cross validation and hence at negligible additional computational cost. Furthermore, we propose an improvement of penalisation, called PenVF+, which takes into account learning rates in order to correct under-penalisation with large models.

We conducted an extensive empirical investigation into VFCV and V-fold penalisation over a collection of 10 well known benchmark datasets using an SVR with the RBF kernel and CART. With low values of V , penalisation can provide an advantage over VFCV but this advantage rapidly diminishes as V increases. Furthermore, in some cases penalisation fared worse than cross validation. When we compare the penalty with the "ideal" penalty, we observed that PenVF underestimates the penalty with large models and PenVF+ improves penalty estimation in these cases. Hence, there is no fixed overpenalisation constant even for a particular dataset, but rather the penalisation should vary with model complexity as with PenVF+.

Figure 1 :

 1 Figure 1: An example of a decision tree. the root node which contains all of the training examples S 0 = S. One then decides how to split the examples based on a feature k and a threshold θ.

Table 4 :

 4 Wins, draws and losses for CART using m = 500. Note that PenVF+ wins 8 times for V = 2 and 2 times for V = 4. optimal margin classifiers. In Proceedings of the 5th Annual Conference on Computational Learning Theory, pages 144-152, New York, NY, USA, 1992. ACM Press. SVR, abalone (top) and slice-loc (bottom) CART, winequality-white (top) and slice-loc (bottom)

Figure 2 :

 2 Figure2: The variation in error with α for some sample datasets with V = 10. The plots are ordered from top to bottom: m = 50, 100, 200, for example for winequality-white and CART the respective curves are dotted, solid with crosses and solid with pluses. With abalone and the SVR, and winequality-white with CART overpenalisation improves results, however it makes them worse with slice-loc for both the SVR and CART.

Figure 3 :

 3 Figure3: The variation in penalty for CART in the "ideal" case relative to PenVF α = 1.0, and PenVF+ with V = 2 and abalone. PenVF+ estimates the ideal error well across a range of t's, whereas PenVF underestimates it for large t.

Figure 4 :

 4 Figure 4: The error for CART in the "ideal" case relative to PenVF α = 1.0, and PenVF+ with V = 2 and abalone, m = 50. PenVF provides a poor estimation of the error for large values of t. PenVF+ gives better error estimates but results in the selection of larger trees than VFCV.

Table 1 :

 1 Information on the benchmark datasets used. There are 100 learn/test splits for each dataset.

		Learn Test	d	Abrv.
	abalone	835	3342 8	ab
	add10	2937 6855 10 ad
	comp-activ	2457 5735 22 ca
	concrete	309	721	8	cc
	parkinsons-motor 2937 2938 20 pm
	parkinsons-total	2937 2938 20 pt
	pumadyn-32nh	3276 4916 32 pd
	slice-loc	26750 26750 385 sl
	winequality-red	1066 533	11 wr
	winequality-white 3265 1633 11 ww

  .024) .116 (.025) .114 (.024) .092 (.012) .092 (.013) .090 (.014) .080 (.009) .078 (.009) .078 (.010) pd .814 (.032) .813 (.037) .806 (.026) .796 (.021) .797 (.028) .793 (.015) .778 (.014) .783 (.018) .779 (.015) sl .423 (.037) .427 (.043) .415 (.037) .341 (.023) .346 (.022) .334 (.020) .290 (.012) .292 (.018) .279 (.009) wr .712 (.064) .709 (.062) .745 (.057) .660 (.034) .667 (.041) .710 (.048) .637 (.021) .643 (.030) .704 (.037) ww .728 (.028) .734 (.039) .752 (.034) .704 (.025) .710 (.035) .731 (.034) .680 (.025) .679 (.023) .707 (.031) CART ab .699 (.057) .696 (.065) .713 (.065) .665 (.044) .667 (.049) .691 (.052) .633 (.028) .632 (.040) .661 (.036) ad .750 (.063) .725 (.066) .720 (.072) .637 (.055) .616 (.048) .624 (.040) .567 (.036) .556 (.027) .571 (.030) ca .330 (.116) .305 (.100) .303 (.099) .220 (.052) .215 (.051) .215 (.050) .186 (.031) .180 (.023) .182 (.023) cc .681 (.084) .642 (.068) .624 (.056) .569 (.069) .535 (.051) .526 (.045) .459 (.037) .444 (.030) .438 (.029) pm .348 (.055) .331 (.038) .323 (.036) .282 (.037) .268 (.028) .262 (.027) .210 (.025) .204 (.022) .202 (.021) pt .268 (.160) .259 (.161) .257 (.161) .213 (.077) .198 (.044) .198 (.045) .161 (.020) .158 (.020) .157 (.020) pd .812 (.036) .821 (.054) 1.039 (.089) .796 (.014) .794 (.048) .947 (.104) .751 (.051) .694 (.057) .808 (.077) sl .679 (.128) .604 (.105) .594 (.102) .484 (.088) .453 (.071) .444 (.069) .362 (.048) .344 (.032) .340 (.030) wr .812 (.067) .797 (.065) .799 (.072) .776 (.059) .756 (.061) .765 (.066) .738 (.045) .721 (.044) .730 (.048) ww .789 (.052) .786 (.065) .807 (.072) .771 (.040) .762 (.041) .782 (.059) .760 (.035) .744 (.038) .768 (.053)

		m = 50		m = 100		m = 200
	VFCV	PenVF+ PenVF	VFCV	PenVF+ PenVF	VFCV	PenVF+ PenVF
				SVR
	ab .544 (.031) .549 (.033) .624 (.036) .514 (.017) .519 (.027) .603 (.026) .497 (.013) .501 (.019) .584 (.012)
	ad .471 (.037) .471 (.031) .473 (.036) .409 (.020) .401 (.022) .404 (.023) .330 (.021) .320 (.016) .320 (.013)
	ca .236 (.052) .227 (.055) .220 (.060) .172 (.051) .165 (.048) .165 (.048) .130 (.026) .127 (.021) .128 (.021)
	cc .472 (.046) .478 (.050) .485 (.050) .413 (.025) .415 (.031) .430 (.036) .366 (.021) .350 (.021) .366 (.020)
	pm .272 (.030) .274 (.030) .282 (.032) .237 (.012) .240 (.017) .254 (.024) .217 (.009) .215 (.010) .219 (.010)
	pt .116 (


Ayoub Elghanaoui
email: faouzi-ayoub.elghanaoui@ens.univ-evry.fr

Nefissa Khiari Hili
email: nefissa.khiari-hili@ibisc.univ-evry.fr

Christophe Montagne
email: cmontagne@iup.univ-evry.fr

Sylvie Lelandais
email: s.lelandais@iut.univ-evry.fr

Bio-Inspired Face Authentication using Multiscale LBP

Keywords: Face recognition, Local Binary Pattern, Bio Inspired processing, Difference Of Gaussian decomposition

INTRODUCTION

Human face recognition remains one of the most active areas in security and surveillance applications since it is non-invasive and requires less user cooperation. Most classical approaches for face recognition are holistic appearance-based ones such as Eigenfaces and Fisherfaces [START_REF] Belhumeur | Eigenfaces vs fisherfaces: Recognition using class specific linear projection[END_REF]. On another hand, local feature-based approaches, like Gabor [START_REF] Li | Handbook of Face Recognition[END_REF] are believed to achieve high accuracy. Both of them perform well in controlled environments; however, their performances drastically drop when variability like quality, pose and illumination occur. Therefore, new solutions are being suggested to overcome these challenges. Many of them were based on combining conventional algorithms and brought quite good results [START_REF] Mellakh | 2D Face Recognition in the IV² Evaluation Campaign[END_REF][START_REF] Zhang | Face Recognition Based on Steerable Feature and Random Subspace LDA[END_REF][START_REF] Su | Hierarchical ensemble of global and local classifers for face recognition[END_REF]). Since around 2005, a lot of studies in the field of face recognition used successfully the "Local Binary Patterns (LBP)" [START_REF] Huang | Local Binary Patterns and Its Application to Facial Image Analysis: A Survey[END_REF]. Now, results of face recognition algorithms are almost around the same values. Improving these results is the goal of new methods. So we propose to explore the work of some psychologists to help the development of automatic algorithm based on textural and multispectral analysis.

The rest of the paper is organized as follows. In a first part we present the bio-inspired work on which we were based to build our method. Then we give some indications about the data and the evaluation protocol we use to evaluate the proposed algorithm. The third part describes the proposed bio-inspired face authentication. Experimentations and comparative results are reported in the fourth part. Finally, we conclude and give some ideas for future works.

WHY A BIO-INSPIRED APPROACH?

Recently Sinha et al. proposed to take into account the knowledge about the ways people recognize each other [START_REF] Sinha | Face Recognition by humans: Nineteen results all computer vision researchers should know about[END_REF]. They detailed nineteen important results regarding face recognition by human. In former studies, Gosselin and Schyns proposed a bio-inspired technique called "Bubbles" to reveal the use of information in recognition tasks [START_REF] Gosselin | Bubbles: a technique to reveal the use of information in recognition tasks[END_REF]. To this end, they run a set of experiments on participants (human observers) that had to identify or categorize a set of faces based only on randomly revealed portions of these face images.

To build the stimuli presented to the observers, Gosselin et al. started by using a Laplacien Pyramid that decomposes an image into six frequency bands in the Fourier domain leading to six scales in the spatial domain (figure 1b). Revealed portions of faces were then obtained by randomly sampling the filtered images with gaussian functions, called Bubbles. After all the observers have answered to the stimuli that were present during the experiment, it was possible to analyze where the information leading observers to give a correct answer was. Figure 1c shows, for each scale, these areas. Then in figure 1d, we see what parts of the face have been useful, at each scale, for the recognition task. Figure 1e is a reconstruction of the five scales of figure 1d. [START_REF] Gosselin | Bubbles: a technique to reveal the use of information in recognition tasks[END_REF] To revel which frequency bands were the most discriminative for face recognition (achieving at least 75% of successful recognition by observers), Schyns et al. [START_REF] Schyns | SHOW ME THE FEATURES! Understanding Recognition from the Use of Visual Information[END_REF] run a study on the proportions of face area that was efficient in each of the five frequency bands already sampled by Bubbles (Figure 2). Results demonstrated that the third scale was the most discriminative followed narrowly by the fourth one. It also has been noticed that the fifth scale did not contribute in any of the identification nor the categorization tasks.

Furthermore, experiment results confirmed that most of the face regions were important for recognition. Specifically, the region of eyes was the most important one as it is present in all scales, followed by the mouth then the nose.

THE IV² DATABASE AND THE EVALUATION PROTOCOL

In biometric studies, it is very crucial to have a big set of data on which the efficiency of proposed algorithms can be evaluated. Some databases are available but they don't offer enough data either in number or in variability. The IV² database was designed with the aim of proposing multiple test situations to allow evaluation with regard to variability well known to be critical for the biometric systems performance, such as pose, expression, illumination and quality (Figure 3). The IV² database has been realized during the Techno Vision program and has been supported by the French Research Ministry in collaboration with the French Ministry of Defense.

The publicly available IV² database (http://lsc.univ-evry.fr/techno/iv2/PageWeb-IV2.html) allows monomodal and multimodal experiments using face data (2D and 3D face images, 2D stereoscopic face images and infrared iris images). It contains 315 subjects with one session data where 77 of them also participated to a second session. From this database, a subset of 52 subjects, distributed as a development set, constitutes also the training set.

As a closing stage of the IV² project, an evaluation campaign was performed involving iris recognition, 2D and 3D-face recognition and also multimodal recognition. In the 2D-Face evaluation (Petrovska, 2008), the strategy of having "one variability" at a time was adopted in order to evaluate how challenging variability -related to illumination, expression, quality or multi-session images -can be for the biometric systems.

In this evaluation campaign a set of more than 15000 images were tested through four experiments. The first three experiments are monosession (all images were collected in a unique session). Experiment 1 includes neutral faces and small expression variations. Experiment 2 tests illumination variations and Experiment 3 tests quality variation. Whereas Experiment 4 includes multi-session images, that were collected in three different sessions. Five appearance based methods were evaluated on the IV² database. Details about the algorithms are given in [START_REF] Mellakh | 2D Face Recognition in the IV² Evaluation Campaign[END_REF] and comparative results are shown in Table 4.

PROPOSED METHOD

The proposed method is based on four steps. First, wavelet decomposition is performed. Then, Regions Of Interest (ROIs) are selected on each scale, related to Gosselin's analysis [START_REF] Gosselin | Bubbles: a technique to reveal the use of information in recognition tasks[END_REF]. Then LBP operator is computed on each filtered image. Finally, matching is performed by computing a weighted distance between request and stored images. Weighting coefficients were set according to the importance of scales and areas. In the next, theoretical background is presented before detailing the proposed approach.

Difference Of Gaussians (DOG)

Rodieck and Stone showed that the responses of the retinal ganglion cells could be modeled by a Difference Of Gaussians function (DOGs) [START_REF] Rodieck | Analysis of receptive fields of cat retinal ganglion cells[END_REF] To go in the same direction and, at the same time, explore Gosselin and Schyns results we used a DOGs filter instead of Laplacien Pyramid. The DOG's filter formula in image plane is given by (1) :

ሺ, ሻ = ି ା - ି ା (1)
with C 1 , C 2 , σ and a are fixed constants following psycho-visual experiments (C 1 =1.8, C 2 =0.8, σ²=2.25) as shown by Schor et al. [START_REF] Schor | Disparity range for local stereopsis as a function of luminance spatial frequencies[END_REF]; a is the scale of the DOG.

Local Binary Patterns (LBP)

The original LBP operator was first used in texture analysis in 1999 [START_REF] Pietikäinen | Nonparametric texture analysis with simple spatial operators[END_REF]. It is a simple yet effective non parametric descriptor that labels the pixels of an image by thresholding a 3×3 neighborhood of each pixel with the center value and considering the results as a binary number called Local Binary Pattern (see figure 4). Ojala et al. later made an extension of the original operator to allow any radius and any number of pixels in the neighborhood [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF]. The notation LBP P,R denotes an LBP with a neighborhood of P equally spaced sampling points on a circle of radius R. It can be expressed in decimal form for a given pixel at (x c , y c ) as:

, ሺ , ሻ = ሺ -ሻ ି ୀ (2)
where i runs over the P neighbours of the central pixel, g c and g i are the gray-level values of the central pixel and the surrounding pixel. g i is of coordinates ((-Rsin(2πi/P), Rcos(2πi/P)) if the coordinates of g c are (0,0). δ(x) is 1 if x > 0 and 0 otherwise. Figure 4 shows an example of an original LBP 8,1 .

After labeling an image with an LBP operator, the histogram of the labeled image is computed giving an LBP operator which can be exploited as a texture descriptor. The LBP P,R produces 2 P different binary patterns that can be formed by the P pixels in the neighbor set. This leads to 256 patterns for LBP 8,1 .

Some variations of the original LBP have been developped. The most known of them are the rotation invariance LBP RI [START_REF] Pietikäinen | Rotationinvariant texture classification using feature distributions[END_REF], the uniform pattern LBP U2 [START_REF] Mäenpää | Robust texture classification by subsets of local binary patterns[END_REF] and the rotation invariant uniform pattern LBP RIU2 [START_REF] Ojala | Multiresolution gray-scale and rotation invariant texture classification with local binary patterns[END_REF]. Recent studies [START_REF] Huang | Local Binary Patterns and Its Application to Facial Image Analysis: A Survey[END_REF] demonstrated that more than 90% of the discriminative patterns for representing faces were uniform.

Chi-Square distance (χ χ χ χ2)

To measure similarity between two LBP histograms H 1 and H 2 of two images I 1 and I 2 , we use Chi-Square distance that has been widely used in face recognition [START_REF] Huang | Local Binary Patterns and Its Application to Facial Image Analysis: A Survey[END_REF], given by the following formula:

ሺ , ሻ = ሺ -ሻ ሺ + ሻ (3)
i is the elements' index of H 1 and H 2 .

Implementation

Here are given the different steps of the proposed method, starting by feature extraction from 128×128 normalized face images through DOG filtering, then LBP calculation on ROIs subdivided into blocks and finally ending by matching by means of weighted Chi-square distance.

DOG filtering

In this work, wavelets are performed through a direct calculation in Fourier plane using the analytic formula of the DOG (Eq. 1): each image is decomposed at the input of the algorithm into four frequency bands, each containing one octave. Figure 5b presents the results of such a decomposition performed on the original image 5a. The four scales used are equal to 1, 2, 4 and 8.

Regions of interest selection (ROIs)

The first application of the bio-inspired approach in the proposed method consists in focusing only on the discriminant regions of each scale, based on the results found by Gosselin et al. [START_REF] Gosselin | Bubbles: a technique to reveal the use of information in recognition tasks[END_REF].

In fact, their studies state that for the first scale, participants focused only on the eyes and mouth regions; for the second scale, they added the nose; while for the third and fourth scales they used all the face regions in the recognition task. The ROIs selection is illustrated in Figure 5c.

LBP application on ROIs

Once the regions are chosen, they are labeled with an LBP operator then subdivided into non overlapping sub-blocks. Histograms of the labeled blocks are then calculated and concatenated into a single histogram constituting the final feature vector. This representation allows capturing both local texture (LBP, sub-block division) and global shape (histogram concatenation) of face. Figure 5d shows an example of a 128×128 face image where the ROIs of each scale are subdivided into 16×16 blocks leading to a total of 182 blocks where LBP histograms (of size 59 in case of LBP U2 ) are computed then concatenated into a single feature vector (of size 10738 in case of LBP U2 ) as illustrated in Figure 5e.

Matching by weighting ROIs and scales

The second application of the bio-inspired approach in the proposed method consists in considering the importance of each ROI and each scale in the recognition task realized by observers in Schyns et al. work (Schyns, 2002). To this end, weighting coefficients were introduced in the Chisquare formula given by Equation 4:

χ χ χ χ ሺ , ሻ = χ χ χ χ ሺ , ሻ (4)
where w r and w s are, respectively, the weighting coefficient of each region r and of each scale s.

The assignment of weights was guided by the findings in [START_REF] Schyns | SHOW ME THE FEATURES! Understanding Recognition from the Use of Visual Information[END_REF]. These findings state that, according to regions, the eyes were the most important followed by the mouth than the nose; while according to scale, the third scale was the most discriminative one, followed narrowly by the fourth one; the first and second scales having less influence on the recognition task.

RESULTS AND DISCUSSION

In this section, the influence of a non exhaustive list of parameters related to the proposed bio-inspired method is firstly presented. Then, a comparison with other algorithms performed on IV² project is brought. The results are reported with the Equal Error Rate percentage (EER).

Choice of LBP variant

A first set of experiments has been conducted to see which LBP variant was the most discriminant in the face authentication task. Three extensions of LBP operator were tested on the four IV² experiments, besides the original LBP. Results in table 1 are in favor of LBP U2 as stated in many works in the literature [START_REF] Huang | Local Binary Patterns and Its Application to Facial Image Analysis: A Survey[END_REF].

Choice of block size and ROIs

A second set of tests was carried out to see whether it was better to keep the filtered images at their entirety as an input for LBP U2 histograms computation or to split it into blocks. Different block sizes were tested in this Only the three best configurations are shown in Table 2, i.e.: entire image, 16×16 blocks and 32×32 blocks. It can be seen, that splitting the filtered images into blocks improves the results sensitively.

Another set of tests was run to prove the importance of the bio-inspired approach based on ROIs rather than the totality of blocks on each scale. Results of the last two configurations in Table 2 show that significant improvements were provided by using only blocks of ROIs. The gain in terms of EER goes up to 8.5% in case of Experiment 3 which deals with quality variation, when using 32×32 blocks.

Improvements by weighting ROIs and scales

Four strategies of weighting in the Chi-square distance were tested. Weights were attributed empirically with reference to Schyns et al. studies. The kept weighting coefficients are as follows:

• According to regions: 0.6 for the eyes, 0.2 for the mouth, 0.12 for the nose and 0.08 for the rest of regions. • According to scales: 0.05 for first scale, 0.1 for second scale, 0.45 for third scale and 0.4 for fourth scale.

Table 3: Influence of the weighting strategy.

Table 3 shows that weighting both scales and regions achieved the best results for almost all the experiments, especially for Experiment 3 (quality variation) where enhancement reaches 4.5% of EER when compared to unweighted strategy.

To summarize, the optimum parameters of the proposed bio-inspired method are to filter the normalized 128×128 face images by a 4-scale DOG. Then, compute LBP U2 histograms on each 32×32 block of the Regions Of Interest and concatenate them into a single feature vector. Afterward, perform matching using Chi-square distance weighting both scales and regions.

Comparison with IV² evaluation campaign

To evaluate the efficiency of the proposed algorithm, comparison with five other algorithms using the same IV² database and protocol is presented in Table 4 [START_REF] Mellakh | 2D Face Recognition in the IV² Evaluation Campaign[END_REF]. According to these results, proposed algorithm provides the best results in Experiment1 including small expression variation. It occupies the second place in Experiments 2 and 3 involving illumination and quality variations; and it is 4.9 (±0.7) 16.0 (±1.2) 20.8 (±1.6) 16.5 (±1.4) LBP RIU2 5.9 (±0.8) 18.5 (±1.3) 23.0 (±1.7) 16.9 (±1.5) No weighting 4.0 (±0.6) 15.8 (±1.5) 17.3 (±1.5) 17.1 (±1.5)

Weighting scales 4.0 (±0.6) 16.1 (±1.2) 18.1 (±1.4) 17.6 (±1.5)

Weighting ROI 4.1 (±0.7) 15.6 (±1.2) 15.7 (±1.4) On the other hand, it is true that both bio-inspired LBP and LDA/Gabor are multiscale and based on combining But it has to be underlined that, unlike the bio-inspired LBP algorithm, which does not include any pretreatment for the face images nor any pretreatment phase, the LDA/Gabor algorithm performs an anisotropic smoothing on images, before features extraction, which proved to be very efficient face to variabilities such as illumination, quality and multisessions. Also it includes a learning phase to get the projection space (Fisherfaces) used afterwards in the test phase. That explains why LDA/Gabor achieves the best results for Experiments 2, 3 and 4.

CONCLUSION AND FUTURE WORK

Through this work, a bio-inspired approach based on psychovisual studies has been introduced for 2Dface authentication. The approach combines LBP U2 with multiscale DOGs. It has been proved that considering only relevant regions and weighting both regions and scales brought sensitive improvements. Proposed method showed to be robust not only in controlled environment but also face to illumination and quality variations.

Future works are intended to investigate pretreatment before feature extraction. Further research would consider a learning stage to enhance performance.

Algorithms Exp1 Exp2

Exp3 Exp4 PCA1 6.7 (±0.8) 20.7 (±1.3) 20.1 (±1.6) 22.2 (±1.6) PCA2 7.3 (±0.8) 21.6 (±1.4) 13.6 (±1.4) 16.3 (±1.4) mod PCA 5.3 (±0.7) 20.7 (±1.4) 19.5 (±1.6) 20.5 (±1.5) LDA 3.7 (±0.6) 22.5 (±1.4) 21.7 (±1.7) 19.7 (±1.5)

Proposed method

Bio-inspired LBP u2 3.7 (±0.6) 15.2 (±1.2) 12.8 (±1.3) 16.7 (±1.4) 12.0 (±1.1) 8.3 (±1.1) 11.3 (±1.2) LDA/ Gabor Previous Tests IV² 4.2 (±0.6)

Figure 1 :

 1 Figure 1: Application of Bubbles; a) Initial image; b) Five different scales of a) ; c) Bubbles applied to each scale; d) Revealed information of b) by the bubbles of c). e) Stimulus resulting by integrating pictures in d)[START_REF] Gosselin | Bubbles: a technique to reveal the use of information in recognition tasks[END_REF]

Figure 2 :

 2 Figure 2: Left: Significant regions for recognition task. Right: bars indicate the proportion of significant pixels in the four first scales (Schyns 2002).

  Figure.3. Examples of variability related to (1.a-c) expression, (2.a-c) illumination and (3.a-b) quality.

Figure 4 :

 4 Figure 4: An example of LBP operator (P=8, R=1).

Figure 5 :

 5 Figure 5: Different steps of proposed method. a) Initial image b) Result of DOG application into four scales c) ROIs of each scale d) Application of LBP and subdivision into blocks e) Histogram computation on each block and concatenation of all histograms to get the final vector.

Table 1 :

 1 Comparison between LBP variants. Application on 4-scale DOG filtered ROIs divided into 16×16 blocks.

Table 2 :

 2 Results of five configurations of LBP U2 application, including block size variation and ROIs selection.

Table 4 :

 4 Comparative results between proposed algorithm (green) and IV² first evaluation campaign ones (black).

			16.6 (±1.4)
	Weighting scales + ROI	3.7 (±0.6) 15.2 (±1.2) 12.8 (±1.3)	16.7 (±1.4)