Clément Chatelain

Sébastien Adam

Yves Lecourtier

Laurent Heutte

Thierry Paquet

Non-cost-sensitive SVM training using Multiple Model Selection

Keywords: ROC front, multi-model selection, multi-objective optimization, ROC curve, SVM

In this paper, we propose a multi-objective optimization framework for SVM hyperparameters tuning. The key idea is to manage a population of classifiers optimizing both False Positive (FP) and True Positive (TP) rates rather than a single classifier optimizing a scalar criterion. Hence, each classifier in teh population optimizes a particular trade-off between the objectives. Within the context of two-class classification problems, our work introduces the "ROC front concept" depicting a population of SVM classifiers as an alternative to the ROC curve representation. The comparison with a traditional scalar optimization technique based on an AUC criterion shows promising results on UCI datasets.

Introduction

Optimizing the hyperparameters of SVM classifiers is a complex challenge since it is well known that the choice of their values can dramatically affect the performance of the classification system. In the literature, many contributions in this field have focused on the computation of the model selection criterion, i.e. the value which is optimized with respect to the hyperparameters. These contributions have led to efficient scalar criteria and strategies used to estimate the expected generalization error. One can cite Xi-Alpha bound of [START_REF] Joachims | Making large-scale support vector machine learning practical[END_REF], the Generalized Approximate Cross-Validation of [START_REF] Wahba | The bias-variance tradeoff and the randomized gacv[END_REF], the empirical error estimate of [START_REF] Ayat | Automatic model selection for the optimization of svm kernels[END_REF], the radius-margin bound of [START_REF] Chapelle | Choosing multiple parameters for support vector machines[END_REF] or the maximal-discrepancy of [START_REF] Anguita | Hyperparameter design criteria for support vector classifiers[END_REF]. Based on these criteria, hyperparameters are usually chosen using a grid search, generally coupled with a cross-validation procedure. In order to decrease the computational cost of grid search, some authors suggest to use gradient-based techniques (e.g. [START_REF] Bengio | Gradient-based optimization of hyperparameters[END_REF], [START_REF] Keerthi | An efficient method for gradient-based adaptation of hyperparameters in svm models[END_REF]). In these works, the performance validation function is adapted in order to be differentiable with respect to the parameters to be optimized.

All the approaches mentioned above, though efficient, use a single criterion as the objective during the optimization process. Now, it is well known that a single criterion is not always a good performance indicator. Indeed, in many real-world pattern recognition problems (medical domain, road safety, biometry, etc...), the misclassification costs are (i) asymmetric as error consequences are class-dependant; (ii) difficult to estimate, for example when the classification process is embedded in a more complex system. In such cases, a single criterion might be a poor performance indicator.

One remedy to tackle this problem is to use as performance indicator the Receiver Operating Characteristics (ROC) curve which offers a synthetic representation of the trade-off between the True Positive rate (TP) and the False Positive rate (FP), also known as sensitivity vs. specificity trade-off. One way to take into account both FP and TP in the model selection process is to resume the ROC curve into a single criterion, such as the F-Measure (FM), the Break-Even Point (BEP) or the Area Under ROC Curve (AUC). However, we will show in the following that we can get more advantages in formulating the model selection problem as a true 2-D objective optimization task.

In this paper, our key idea is to turn the problem of the search for a global optimal SVM, (i.e. the best set of hyperparameters) using a single criterion or a resume of the ROC curve into the search for a pool of locally optimal SVM's (i.e. the pool of the best sets of hyperparameters) w.r.t. FP/TP rates. The best classifier among the pool can then be selected according to the needs of some practitioner. Consequently, the proposed framework can be viewed as a multiple model selection approach (rather than a model selection problem) and can naturally be expressed in a Multi-Objective Optimization (MOO) framework. Under particular conditions, we assume that such an approach could lead to better results than a more traditionnal single model selection approach based on a scalar optimization. Figure 1 depicts our overall multi-model selection process. The resulting output is a pool of classifiers, each one optimizing some FP/TP rate tradeoff. The set of trade-off values constitutes an optimal front we call "ROC front" by analogy with MOO field. The remainder of the paper is organized as follows. In section 2, we detail the rationale behind the ROC front concept and illustrate how our multi-model selection approach can outperform traditional approaches in a MOO framework. In section 3, the SVM multi-model selection problem is adressed. Then, section 4 shows that our method compares favourably with traditionnal model selection techniques on standard benchmarks (UCI datasets). Finally, a conclusion and future works are drawn in section 5.

The "ROC front" concept

As stated in the introduction, a model selection problem may be seen from a multiobjective point of view, turning thus into a multi-model selection approach. In the literature, some multi-model selection approaches have been proposed. However, these approaches aim at designing a single classifier and thus cannot be considered as real multi model selection approaches. Caruana for example proposes in [START_REF] Caruana | Ensemble selection from libraries of models[END_REF] an approach for constructing ensembles of classifiers, but this method aims at combining those classifiers in order to optimize a scalar criterion (accuracy, cross entropy, mean precision, AUC). Bagging, boosting or Errorcorrecting-output-codes (ECOC) ( [START_REF] Dietterich | Solving multiclass learning problems via errorcorrecting output codes[END_REF]) also aim at combining different classifiers of an ensemble in order to produce a single classifier efficient with respect to a scalar performance metric. In [START_REF] Lebrun | An ea multi-model selection for svm multiclass schemes[END_REF], an EA-based approach is applied to find the best hyperparameters of the set of binary SVM classifiers combined to produce a multiclass classifier.

The approach which is proposed in this paper is different since our aim is not to build a single classifier but a pool of classifiers using a real multi-objective framework. In such a context, let us recall that a problem arising when ROC curves are used to quantify classifier performance is their comparison in a 2-D objective space : a classifier may be better for one of the objectives (e.g. FP) and worse for the other one (e.g TP). Consequently, the strict order relation that can be used to compare classifiers when a single objective is considered become unusable and classical mono-objective optimization strategies can not be applied.

Usually, this problem is tackled using a reduction of the FP and TP rates into a single criterion such as the Area Under ROC Curve (AUC) ( [START_REF] Rakotomamonjy | Optimizing auc with support vector machine[END_REF]). However, such performance indicators are a resume of the ROC curve taken as a whole and do not consider the curve from a local point of view. The didactic example proposed in figure 2 illustrates this statement. One can see on this figure two synthetic ROC curves. The curve plotted as continuous line has a better AUC value, but the corresponding classifier is not better for any specific desired value of FP rate (resp. TP). Consequently, optimizing such a scalar criterion to find the best hyperparameters could lead to solutions that do not fit the practitioner needs in certain context. It seems a better idea to simultaneously optimizing FP and TP rates using a MOO framework and a dominance relation to compare classifier performance. Let us recall that the dominance concept has been proposed by Vilfredo Pareto in the 19th century. A decision vector -→ u is said to dominate another decision vector -→ v if -→ u is not worse than -→ v for any objective functions and if -→ u is better than -→ v for at least one objective function. This is denoted

-→ u ≺ -→ v .
More formally, in the case of the minimization of all the objectives, a vector

- → u = (u 1 , u 2 , . . . , u k ) dominates a vector -→ v = (v 1 , v 2 , . . . , v k ) if and only if: ∀i ∈ {1, . . . , k}, u i ≤ v i ∧ ∃j ∈ {1, . . . , k} : u j < v j
Using such a dominance concept, the objective of a Multi-Objective Optimization algorithm is to search for the Pareto Optimal Set (POS ), defined as the set of all non dominated solutions of the problem. Such a set is formally defined as the set :

P OS = -→ x ∈ ϑ/¬∃ -→ y ∈ ϑ, --→ f (x) ≺ --→ f (y)
where ϑ denotes the feasible region (i.e. the parameter space regions where the constraints are satisfied) and -→ f denotes the objective function vector. The corresponding values in the objective space constitute the so-called Pareto Front in the 2 dimension context.

From our model selection point of view, the POS corresponds to the pool of non-dominated classifiers (the pool of the best sets of hyperparameters). In this pool, each classifier optimizes a particular FP/TP trade-off. The resulting set of FP/TP points constitutes an optimal front we call "ROC front". This concept is illustrated with a didactic example as shown in figure 3: let us assume that ROC curves have been obtained from three distinct hyperparameter sets. This could lead to the three synthetic curves plotted as dashed lines. One can see on this example that none of the classifiers dominates the others on the whole range of FP/TP rates. An interesting solution for a practitioner is the "ROC front" (the red curve), which is made of non-dominated parts of a set of classifiers ROC curves. The method proposed in this paper aims at finding this "ROC front" (and the corresponding POS ), using an Evolutionnary Multi-Objective Optimization Algorithm called NSGA-II. This class of optimization algorithm has been chosen since Evolutionary Algorithms (EA's) are known to be wellsuited to search for multiple Pareto optimal solutions concurrently in a single run, through their implicit parallelism.

SVM multi-model selection

As explained in the preceding sections, the proposed framework aims at finding a pool of SVM classifiers, optimizing simultaneously FP and TP rates.

As stated in [START_REF] Osuna | Support vector machines: Training and applications[END_REF], classification problems with asymmetric and unknown misclassification costs can be tackled using SVM through the introduction of two distinct penalty parameters C -and C + . In such a case, given a set of m training examples x i in n belonging to the class y i :

(x 1 , y 1 ) . . . (x m , y m ), x i ∈ n , y i ∈ {-1, +1}
the maximisation of the dual lagrangian with respect to the α i becomes :

M ax α m i=1 α i - 1 2 m i,j=1 α i α j y i y j K(x i , x j )
subject to the constraints:

   0 ≤ α i ≤ C + f or y i = -1 0 ≤ α i ≤ C -f or y i = +1
m i=1 α i y i = 0 where α i denote the Lagrange multipliers and K(.) denotes the kernel. In the case of a Gaussian (RBF) kernel, K(.) is defined as :

K(x i , x j ) = exp -γ × x i -x j 2
Hence, in the case of asymmetric misclassification costs, three parameters have to be determined to perform an optimal learning of the SVM classifier:

-The kernel parameter of the SVM-rbf : γ.

-The penalty parameters introduced above : C -and C + .

In the following, the proposed framework (see figure 1 is used in order to tune these three hyper-parameters values. For that, two particular points have to be specified for the application of NSGA-II to SVM multi-model selection :

-the solution coding : as said before, three parameters are involved in the learning of SVM for classification problems with asymmetric misclassification costs : C + , C -and γ. These three parameters constitute the parameter space of our optimization problem. Consequently, each individual in NSGA-II has to encode these three real values. We have chosen to use a real coding of these parameters in order to be as precise as possible. -the evaluation procedure : each individual in the population corresponds to some given values of hyperparameters. In order to compute the performance associated to this individual, a classical SVM learning is performed using the encoded parameter values on a learning dataset. Then, this classifier is evaluated on a test dataset with the classical FP and TP rates as performance criteria.

Let us now present some experimental results on several UCI databases.

Experimental results on UCI datasets

In this subsection, the proposed multi-model selection approach based on the ROC front concept is evaluated and compared with other approaches on publicly available benchmark datasets. First, the experimental protocol of our tests is described. Then, the results are shown and compared with some reference works, and finally several comments on these results are proposed.

Our approach has been applied on several 2-class benchmark datasets publicly available in the UCI Machine Learning repository on which state-of-the-art results have been published. The number of samples and the number of attributes for each problem are reported in table 1.

As we propose a real multi objective approach, the result of our experiment is a pool of classifiers describing the ROC Front. Thus, the evaluation of our approach is not easy since as mentioned in the introduction, comparing some results in a multi-dimensional space is a difficult task. Nevertheless, there exists some dedicated measures such as the Set Coverage Metric proposed in [START_REF] Zitzler | Comparison of multiobjective evolutionary algorithms : Empirical results[END_REF]. However, to the best of our knowledge, the other methods in the literature always consider a single classifier as a solution for a classification problem, which makes it difficult to compare our results with those in the literature.

Thus, the only way to evaluate our approach is to reduce the ROC front to a scalar criterion. For that, an Area Under the ROC Front (AUF) is calculated and compared with the Area Under the ROC Curve (AUC) of several approaches in the literature. We know that this comparison is not theoretically correct since the best results of a pool of classifiers is compared with a curve obtained by varying the threshold of a unique classifier. However, the aim of this comparison is only to highlight the fact that more interesting trade-offs may be locally reached with the ROC front approach. This comparison may also be justified by the fact that finally, in both cases only one classifier with a unique threshold will be retained for a given problem. Note also that the results of our approach are compared with several works based on the optimization of a scalar criterion for various classifiers. We emphasize that our comparison is based on the selection for each database of the best results found in the literature up to now: [START_REF] Bostrm | Maximizing the area under the roc curve using incremental reduced error pruning[END_REF] (Decision lists and rules sets), [START_REF] Cortes | Auc optimization vs. error rate minimization[END_REF] (Rankboost), [START_REF] Ferri | Learning decision trees using the area under the roc curve[END_REF] (Decision trees), [START_REF] Rakotomamonjy | Optimizing auc with support vector machine[END_REF] (SVMs) and [START_REF] Wu | A scored auc metric for classifier evaluation and selection[END_REF] (five models : naive Bayes, logistic, decision tree, kstar, and voting feature interval). We refer to these papers for more explanation of the criterion and the model used.

Concerning the application of our multiobjective strategy, a cross validation procedure has been performed with 5 folds for each dataset. The results are presented in table 2, where the first column is the best AUC among the precited works based on the optimization of a scalar criterion, and the second one is the AUF of our approach.

As expected, one can see that for every dataset the ROC front yielded by the pool of classifiers leads to a higher area than the area under the ROC curve of the other single classifiers. As said before, it is important to emphasise that the AUF cannot theoretically be compared with AUC since the different operating points of the ROC front cannot be reached by a single classifier. However, this comparison with methods which explicitely optimize AUC clearly shows that our approach enables to reach very interesting local operating points which cannot be reached by the AUC-based classifiers. Hence, we claim that if the good model can be selected among the pool of classifiers, our approach can lead to better results than AUC-based methods. Let us also remark that compared with other EMOO approaches, the intrinsic parameters of the SVM classifiers (i.e. the position and weight of support vectors) are fixed using a mono-objective optimization algorithm well suited for such a task. Therefore, the EMOO concentrates on the choice of the hyperparameter values. This approach differs from other works using the EMOO to perform both intrinsic and hyperparameter setting. In the context of ROC curve optimization we can mention [START_REF] Kupinski | Multiobjective genetic optimization of diagnostic classifiers with implications for generating receiver operating characterisitic curves[END_REF][START_REF] Anastasio | Optimization and froc analysis of rule-based detection schemes using a multiobjective approach[END_REF][START_REF] Fieldsend | Roc optimisation of safety related systems. Proceedings of ROCAI[END_REF][START_REF] Everson | Multi-class roc analysis from a multi-objective optimisation perspective[END_REF]. All these works are limited to noncomplex classifiers (with a few number of intrinsic parameters) because EMOO algorithms rapidly become intractable when the size of the parameter space increases. Within a monoobjective context, such a limitation has been avoided by developping specific methods for specifics problems like the Lagrangian maximisation for the SVM. Therefore, using the Lagrangian method for the tuning of SVM intrinsic parameters enables the EMOO algorithm to concentrate on a small number of hyperparameters.

Computational issues Assume that o is the learning complexity of the classifier, the learning complexity of the proposed approach O is defined as:

O = M.N × o
where we recall that M stands for the number of generations of the evolutionary algorithm, and N is the population size. Although high, this complexity can be compared with that of a full search approach, which is O = K i D i ×o for a K-hyperparameter problem, where D i is the number of discrete values of each parameter. It is still higher than a gradient based approach, but as shown before leads to better results. Let us notice that the decision complexity of our approach is the same as the standard decision complexity of the involved classifier.

Conclusions

In this paper, we have presented a framework to tackle the problem of SVM model selection with unknown misclassification costs. The approach is based on a multi-model selection strategy in which a pool of SVM classifier is trained in order to depict an optimal ROC front. Using such a front, it is possible to choose the FP/TP trade-off that best fits the application constraints. An application of this strategy with Evolutionnary Multi-Objective Optimization have been proposed, with a validation on UCI datasets. Obtained result have shown that our approach compares favourably to a state-of-the-art approach based on the Area Under ROC Cure criterion since better operating points can be locally reached. As a conclusion, one can say that an AUC-based approach suit pattern recognition problems where the operating point may vary, whereas our approach better suits problems where the operating point is supposed to be static.

The proposed approach is simple and generic. It can be applied to other parametric classifiers (KNN, Neural network, etc.) with other optimization methods ( [START_REF] Souza | Multiclass svm model selection using particle swarm optimization[END_REF]). Moreover, it can be easily extended through the introduction of other parameters (kernel type) or objectives (number of support vectors, decision time). Note that a feature selection process can been included in the optimization method in order to provide a complete model selection approach. In our future works, we also plan to extend the approach to the multiclass problem.

Fig. 1 .

 1 Fig. 1. SVM Multi-model selection framework

Fig. 2 .

 2 Fig.2. Comparing ROC curves: the continuous ROC curve provides a better AUC than the dashed ROC curve, but is not locally optimal for a given range of specificity (False Positive Rate).

Fig. 3 .

 3 Fig. 3. Illustration of the ROC front concept : the ROC front depicts the FP/TP perfomance corresponding to the pool of non dominated operating points.

Table 1 .

 1 Number of samples and number of attributes of the considered 2-class UCI problems.

	problem # samples # attributes
	australian	690	14
	wdbc	569	30
	breast cancer	699	10
	ionosphere	351	34
	heart	270	13
	pima	768	8

Table 2 .

 2 Comparison of the Area Under the ROC Curve (AUC) in the literature with the Area Under the ROC Front (AUF).

	problem ref. AUC literature	AUF
	australian [21] 90.15 ± 0.53 96.91 ± 1.8
	wdbc	[12] 94.7 ± 4.6	99.82 ± 0.1
	breast cancer [5] 99.13	99.86 ± 0.1
	ionosphere [19] 98.7 ± 3.3	99.14 ± 1.2
	heart	[21] 92.60 ± 0.7	95.67 ± 1.5
	pima	[8] 84.80 ± 6.5	88.36 ± 3.1


Gilles Gasso

Batch and online learning algorithms for Nonconvex Neyman-Pearson classification

Keywords: I.5.2 [Pattern Recognition]: Classifier Design and evaluation Neyman-Pearson, Nonconvex SVM, DC algorithm, online learning Batch and online learning algorithms for Nonconvex Neyman-Pearson classification

We describe and evaluate two algorithms for Neyman-Pearson (NP) classification problem which has been recently shown to be of a particular importance for bipartite ranking problems. NP classification is a nonconvex problem involving a constraint on false negatives rate. We investigated batch algorithm based on DC programming and stochastic gradient method well suited for large scale datasets. Empirical evidences illustrate the potential of the proposed methods.

INTRODUCTION

Consider a binary classification problem with patterns x ∈ X and classes y = ±1 obeying an unknown probability distribution dP (x, y). The probabilities of non detection P nd and of false alarm P fa measure the two kinds of errors made by a discriminant function f :

P nd (f ) = P f (x) ≤ 0 | y = 1 , P fa (f ) = P f (x) ≥ 0 | y = -1
The statistical decision theory recognizes the need to associate different costs to these two types of errors. This leads us to searching a classifier f that minimizes the Asymmetric Cost (AC) formulation :

min f C + P nd (f ) + C -P fa (f ) .
(1)

Although C + and C -have a meaningful interpretation, it is often very difficult to specify these costs in real situations such as medical diagnosis or fraud detection. There are also cases where such costs have no meaningful interpretation, for (a) Gilles Gasso, gilles.gasso@insa-rouen.fr. (b) Aristidis Papaioannou, aristidis.papaioannou@gmail.com, was also affiliated with Ecole Polytechnique Fédérale de Lausanne, Switzerland. He is now with Google, Mountain View, CA.

(c) Marina Spivak, spivak.marina@gmail.com, was also affiliated with New York University. She is now in University of Washingtom, WA. (d) Léon Bottou, leon@bottou.org, is now with Microsoft, Bellevue, WA.

instance, as discussed in section 4, when one uses a classification framework to approach a false discovery problem.

In contrast, the Neyman-Pearson (NP) formulation,

min f P nd (f ) subject to P fa (f ) ≤ ρ (2)
requires only the specification of the maximal false alarm rate ρ and can be meaningfully applied to false discovery problems.

It is well known that the optimal decision function for both problems are obtained by thresholding the optimal ranking function

r * (x) = P y = +1 | x , (3)
that is

f * AC = r * (x) -C -/(C + + C -) , f * NP = r * (x)
-min{r such that P fa (r * -r) ≤ ρ} . Although this result suggests equivalent capabilities, it misses several important points. Firstly, when using a finite training set D = {(x 1 , y 1 ) . . . (x n , y n )} we must work with the empirical counterparts of P nd and P fa :

Pnd (f ) = 1 n+ i∈D + I f (x i )≤0 , Pfa (f ) = 1 n- i∈D - I f (x i )≥0
where D + and D -represent respectively the set of positives and negatives with cardinality n + and n -. We must also choose the decision function f within a restricted class H that is unlikely to contain the optimal decision function. This approach is supported by standard results in statistical learning theory [e.g. Vapnik 1998] and their extension to the Neyman-Pearson formulation [START_REF] Scott | A Neyman-Pearson approach to statistical learning[END_REF].

Secondly, the empirical counterparts of problems (1) and (2) involve the 0-1 loss function I y f (x)≤0 that is neither continuous nor convex. Replacing this 0-1 loss with the SVM Hinge loss has been studied for both the Asymmetric Cost [START_REF] Bach | Considering cost asymmetry in learning classifiers[END_REF]] and Neyman-Pearson [START_REF] Davenport | Tuning support vector machines for minimax and neyman-pearson classification[END_REF] formulations. This substitution introduces additional complexities. In particular, in order to hit the specified goals on P nd and P fa , one must use asymmetric costs that are different from C + and C -. Both works eventually rely on hyperparameter searches in the asymmetric cost space.

An alternative approach consists in first learning a scoring function that orders input patterns like the optimal ranking function (3). Both problems (1) and ( 2) are then reduced to the determination of a suitable threshold [e.g. [START_REF] Cortes | Auc optimization vs. error rate minimization[END_REF]]. However it is quite difficult to ensure that the ranking function is most accurate in the threshold area. Theoretical investigations of this problem conclude that Neyman-Pearson classification remains an important primitive for such focussed ranking algorithms [Clémençon and Vayatis 2007;2009].

This contribution proposes two practical and efficient algorithms for NP classification using nonconvex but continuous and mostly differentiable loss functions. In particular, these algorithms are shown to work using asymmetric costs that maintain a clear relation with the specified goals. The first algorithm leverages modern nonconvex optimization techniques [Tao and An 1998]. The second algorithm is a stochastic gradient algorithm suitable for very large datasets. Various experimental results illustrate their properties.

EMPIRICAL RISK NP FORMULATION

Our approach consists in replacing the 0-1 loss in Pnd and Pfa by a continuous nonconvex approximation such as the sigmoid loss

(z) = 1 1 + e ηz (4)
or the ramp loss

(z) = max 0, 1 2η (η -z) -max 0, - 1 2η (η + z) . (5)
The positive parameter η determines how close the nonconvex costs are to the 0-1 loss and those approximations tend toward the 0-1 loss as η tends to 0. Figure 1 illustrates such approximations. The selection of an optimization algorithm usually dictates the choice of an approximation. The differentiable sigmoid loss lends itself to gradient descent, whereas the ramp loss is attractive with dual optimization algorithms.

Following common practice, we also add a regularization term Ω(f ) to control the capacity of our classifiers. We therefore seek the solution of

min f ∈H Ω(f ) + C Pnd (f ) subject to Pfa (f ) ≤ ρ (6)
where C ∈ R + is the regularization parameter and

Pnd (f ) = 1 n+ i∈D + yif (xi) , Pfa (f ) = 1 n- i∈D - yif (xi) .
For instance, in the case of a Neyman-Pearson SVM (NP-SVM), the discriminant functions is f (x) = f 0 (x) + b with f 0 taken from a RKHS induced by a kernel k x, x , and the regularizer is Ω(f ) = f 0

The nonconvex optimization problem (6) comes with the usual caveats and benefits. We can only obtain a local minimum of (6). On the other hand, we can obtain a local minimum that is better than the solution of any convex relaxation of (6), simply by initializing the nonconvex search using the solution of the convex relaxation.

Previous work

The NP classification problem has been extensively studied. Past methods can be roughly divided in two categories: generative and discriminative.

One of the earliest attempts [START_REF] Streit | A neural network for optimum neyman-pearson classification[END_REF]] uses multi-layered neural network to estimate class-conditional distributions as mixture of Gaussians. The discriminant function is then inferred with a likelihood ratio test. In the same vein, recent methods [START_REF] Kim | Pareto optimal linear classification[END_REF]] assume the class-conditional distributions are Gaussian with means µ ± and covariances Σ ± , and consider a linear classifier f (x) = w, x + b. This amounts to solving (2) with the following definitions

Pnd = Φ   - b + w μ+ w Σ+w   , Pfa = Φ   b + w μ- w Σ-w   ,
where Φ is the cumulative distribution function of standard normal distribution and μ± and Σ± are empirical estimations. Since the Gaussian assumption proves too restrictive, some authors [START_REF] Huang | Imbalanced learning with a biased minimax probability machine[END_REF][START_REF] Kim | Pareto optimal linear classification[END_REF]] replace the cumulative Φ by a Chebyshev bound Ψ

(u) = [u] 2 + /(1 + [u] 2 + ), [u] + = max(0, u).
The scheme is extended to nonlinear discrimination using the kernel trick. A third flavor of generative approach addresses the estimation of class-condition distributions by Parzen window [START_REF] Bounsiar | General solution and learning method for binary classification with performance constraints[END_REF]]. These generative methods share the same drawbacks: (1) the final classifiers are derived from estimated distributions whose accuracy is questionable when the datasets are small, and (2) the kernel version of these models lacks sparsity because all the examples are involved in the model.

On the discriminative side, the Asymmetric Cost SVM [START_REF] Bach | Considering cost asymmetry in learning classifiers[END_REF][START_REF] Davenport | Tuning support vector machines for minimax and neyman-pearson classification[END_REF]. introduces costs C + and C -in the SVM formulation. As mentioned before, even if the true asymmetric costs were known, the benefits of the convex loss, such as the guaranteed convergence to global optimum, are balanced by the necessity of searching for different asymmetric costs to achieve the desired NP constraint [START_REF] Bach | Considering cost asymmetry in learning classifiers[END_REF]]. SVMPerf [START_REF] Joachims | A support vector method for multivariate performance measures[END_REF]] optimizes in polynomial time a convex upper bound of any performance measures computable from the confusion table. Since Pfa and Pnd can be computed from the confusion table, SVMPerf can address the Neyman-Pearson problem. Computing times grow very quickly with the number of examples n, typically with degree four for linear models, worse for nonlinear models. Finally, most similar to our approach, [START_REF] Mozer | Prodding the ROC curve: Constrained optimization of classifier performance[END_REF]] also consider sigmoid approximation of 0-1 loss. Compared to this work, our contributions are three-fold: we extend the nonconvex NP idea to SVM in order to benefit from off-the-shelf SVM solvers, we propose a stochastic approach to deal with large scale datasets, and we extend the potential of our approaches to related problems such as q-value optimization (section 4).

• 5

Algorithm 1 Uzawa Algorithm Set initial value for λ ≥ 0. Pick small gain ν > 0.

repeat f ← argmin f ∈H L(f, λ) λ ← max { 0, λ + ν ∇ λ L(f, λ) } until convergence

SOLVING NON-CONVEX NP PROBLEMS

The algorithms discussed in this paper find a local minimum of (6) by searching a local saddle point (f, λ) ∈ H × R + of the related Lagrangian

L(f, λ) = Ω(f ) + C Pnd (f ) + λ ( Pfa (f ) -ρ) . (7)
The appendix summarizes several results that apply to nonconvex optimization.

Local saddle points of the Lagrangian (7) are always feasible local minima of (6). Conversely, assuming differentiability, the local minima of ( 6) are always critical points of the Lagrangian.

Uzawa algorithm

The Uzawa algorithm [START_REF] Arrow | Studies in Nonlinear Programming[END_REF]] is a simple iterative procedure for finding a saddle point of the Lagrangian (7). Each iteration of the algorithm first computes a minimum f * λ of the Lagrangian for the current value of λ, and then performs a small gradient ascent step in λ (algorithm 1) with ∇ λ L = Pfa -ρ. The convergence of the Uzawa algorithm is not obvious because the function λ → L(f * λ , λ) can easily contain discontinuities. However a simple argument (see theorem 3 in the appendix) shows that Pfa (f * λ ) is a nonincreasing function of λ. Therefore the sign of the gradient ∇ λ L = Pfa -ρ correctly indicates whether λ is above or below its target value. In general we prefer using a multiplicative update λ ← λ(1+ν ∇ λ L) because it keeps the λ positive. This makes very little difference in practice: the key is to adjust λ in very small increments, for instance using a very small gain ν.

The two algorithms discussed in this paper are essentially derived from the Uzawa algorithm. They differ in the minimization step. The first algorithm uses the DC1 approach [Tao and An 1998] and is suitable for kernel machines. The second algorithm relies on a stochastic gradient approach [Tsypkin 1971;[START_REF] Andrieu | Stochastic Programming with Probability Constraints[END_REF]] suitable for processing large datasets.

Batch learning of NP-SVM

The most difficult step in the Uzawa algorithm is minimization of L over f for λ fixed. In the case of the SVM classifier, the Lagrangian (7) reads

L = 1 2 f 2 H + C+ i∈D + (yif (xi)) + C- i∈D - (yif (xi)) -λρ
where C + = C/n + , C -= λ/n -and (z) stands for the ramp loss (5). This amounts to solving a nonconvex asymmetric cost SVM [Collobert et al. 2006b]. Since the analytical expression of the ramp loss ( 5) is a difference 1 (z) -2 (z) of two convex functions, the full Lagrangian can also be expressed as the difference of two convex functions amenable to DC programming [Tao and An 1998]. Consider the nonconvex optimization problem min θ J 1 (θ) -J 2 (θ) where both J 1 and J 2 are convex functions. Each DC iteration solves the convex problem obtained by linearizing J 2 , that is,

θ t+1 = arg min θ { J 1 (θ) -∇ θ J 2 (θ t ), θ } , (8)
where ∇ θ J 2 (θ t ) denotes a subgradient of J 2 . One can easily see that the cost J 1 -J 2 decreases after each iteration by summing the following two inequalities resulting from (8) and from the convexity of J 2 .

J 1 (θ t+1 ) -∇ θ J 2 (θ t ), θ t+1 ≤ J 1 (θ t ) -∇ θ J 2 (θ t ), θ t -J 2 (θ t+1 ) ≤ -J 2 (θ t ) -∇ θ J 2 (θ t ), θ t+1 -θ t Following [Collobert et al. 2006b], we write L(f, λ) = J 1 (f ) -J 2 (f ) with J 1 (f ) = 1 2 f 2 H + i C yi 1 (y i f (x i )) , J 2 (f ) = i C yi 2 (y i f (x i )) ,
where notation C yi denotes either C + or C -. Observe that J 1 (f ) is the primal objective function of a standard convex SVM. Each DC iteration then reduces to solving the following convex problem

f t+1 = argmin f J 1 (f ) + 1 2η i C yi β i f (x i ) (9)
where

β i = I y i f t (x i ) < -η indicates whether 2 (y i f t (x i )) has a nonzero gra- dient.
Standard SVM techniques can be used to obtain the dual formulation of this problem. This dual formulation turns out to be similar to that of a standard SVM problem with shifted box constraints [Collobert et al. 2006a, appendix]. This derivation leads to algorithm 2. To summarize, applying the Uzawa algorithm (algorithm 1) to the NP-SVM results in repeatedly solving a nonconvex asymmetric cost SVM via algorithm 2 and updating λ by gradient ascent. This slow procedure requires solving many times a nonconvex SVM problem. Much faster convergence is observed by moving the gradient ascent step inside the DC iterations, leading to the Annealed NonConvex NP-SVM algorithm (algorithm 3). This algorithm departs from the Uzawa template because the Lagrange coefficient λ is updated after each iteration of the DC algorithm (9) instead of performing it in an additional loop surrounding the optimization of the nonconvex asymmetric cost SVM. Although we have no formal convergence guarantee for this algorithm, empirical evidence shows that it works as reliably and much faster than the plain Uzawa algorithm (see section 5.2.)

We pick an initial value for λ such that C/n + = λ/n -in order to balance the initial regularization parameters for positives and negatives. Since the DC

• 7 Algorithm 2 Asymmetric Nonconvex SVM with DC Set β ← 0. repeat • Compute α ← argmax α - 1 2 α K α + ηα 1 where Kij = y i y j k x i , x j , subject to    y α = 0 -β i C + ≤ 2ηα i ≤ (1 -β i )C + ∀i ∈ D + -β i C -≤ 2ηα i ≤ (1 -β i )C -∀i ∈ D - . • Form f (x) = n i=1 α i k x, x i + b with b such that y i f (x i ) = 1
for all i such that the inequality constraints above were not reached.

• Compute β i ← 1 if y i f (x i ) < -η 0 otherwise until convergence of β. Algorithm 3 Annealed Nonconvex NP-SVM Set β ← 0 and λ ← Cn -/n + repeat • Set C + = C/n + and C -= λ/n -. • Compute α ← argmax α - 1 2 α K α + ηα 1 where Kij = y i y j k x i , x j , subject to    y α = 0 -β i C + ≤ 2ηα i ≤ (1 -β i )C + ∀i ∈ D + -β i C -≤ 2ηα i ≤ (1 -β i )C -∀i ∈ D - . • Form f (x) = n i=1 α i k x, x i + b with b such that y i f (x i ) = 1
for all i such that the inequality constraints above were not reached.

• Compute β i ← 1 if y i f (x i ) < -η 0 otherwise • Update λ ← λ(1 + ν( Pfa -ρ)) until convergence.
iterations start with β = 0, the first iteration solves the classical asymmetric cost SVM problem whose solution is progressively improved by taking the nonconvexity into account and updating λ in order to achieve the target P fa . The algorithm is stopped when the NP constraint is satisfied with a predefined precision ε.

Stochastic learning for the NP problem

The computational cost of the batch learning algorithm discussed above increases quickly when the dataset size becomes large. Faster algorithms are therefore desirable.

w ← (1 -γ t λ c )w -γ t a t ∇ w (y t f (x t )) (11a) b ← b -γ t a t ∇ b (y t f (x t )) (11b) If y t = -1, set λ ← λ (1 + ν t ( (-f (x t )) -ρ)) (12) until convergence
Let vector w and the scalar bias b be the parameters of the discriminant function, λ c = 1/C, and reformulate problem (6) as

min f λ c 2 w 2 + Pnd (f ) subject to Pfa (f ) ≤ ρ .
Expanding Pnd and Pfa leads to the Lagrangian

L(f, λ) = 1 n n i=1 λ c 2 w 2 + a i (y i f (x i )) -λρ
with the coefficients

a i = n/n + ∀i ∈ D + λn/n -∀i ∈ D - (10)
Algorithm 4 is a stochastic variant of the Uzawa algorithm. Each iteration performs a stochastic gradient descent step for (w, b) and a stochastic ascent step for the Lagrange coefficient λ. Since the false alarm rate depends only on the negative examples, the update of λ only happens when sampling a negative example.

The convergence analysis of this stochastic descent/ascent procedure establishes how closely the updates (11-12) follow the trajectory described by the corresponding ordinary differential equation. Almost sure convergence to a local saddle point is guaranteed under mild conditions [Tsypkin 1971;[START_REF] Andrieu | Stochastic Programming with Probability Constraints[END_REF]]. Such direct results are in fact stronger than those available for the generic Uzawa approach.

Linear NP-SVM. Following [START_REF] Bottou | Learning with large datasets[END_REF]], when training a linear SVM (that is f (x) = w, x + b), we choose a learning rate γ t = γ 0 (1 + λ c t) -1 with an initial learning rate γ 0 chosen to ensure that the initial updates of w are compatible with its expected size. Choosing γ 0 = 0.1 works well when x i ≈ 1.

Empirical evidence, on the other hand, suggests that ν should be smaller than γ t in order to ensure that λ remain consistent. Otherwise the algorithm strongly enforces the false alarm rate constraint at the expense of the non detection rate. In our experimentations we always choose ν proportional to 1/n -.

Using the ramp loss makes the Lagrangian nondifferentiable when y t f (x t ) = ±η. In such cases, we simply consider that the gradient is zero and skip the stochastic update. On the other hand, using the sigmoid loss simply avoids the problem. Both approaches work well in practice.

• 9 Nonlinear extensions. Algorithm 4 extends naturally to nonlinear discriminant functions such as multilayer neural network. Gradients are easily computed using the standard back-propagation algorithm. The learning rate γ t must then be chosen using a trial and error approach.

Extending algorithm 4 to kernel representations is more complicated. The parameter w can be expressed with a kernel expansion w = n i=1 α i φ(x) where φ(x) is the mapping function associated with the kernel. Since f (x) = w, φ(x) + b we can plug the expression of the gradient ∇ w (y t f (x t )) = -y t φ(x t ) (y t f (x t )) into (11a), leading to the update

α i = (1 -γ t λ c ) α i + γ t y t (y t f (x t )) if t = i 0 otherwise
However the noise introduced by the stochastic procedure compromises the sparsity of α. The computation of the gradient then requires numerous kernel evaluations in order to compute f (x t ). Although kernel values can be cached, these problems reduce the appeal of the stochastic approach. We plan to investigate this issues more closely in a forthcoming work.

Imbalanced Dataset. When the dataset is highly imbalanced, for instance, when there are many negatives and just a few positives, considerable speedups are achieved by picking random training examples from each class with equal probability. Since this procedure oversamples the examples from the minority class, we must adjust the coefficients a i in algorithm 4 in proportion. The coefficients then become

a i = 1 ∀i ∈ D + λ ∀i ∈ D - .

Q-VALUE OPTIMIZATION

So far we have considered problems in fully supervised setting, with positive and negative labels assigned with equal confidence. The situation explored in this section is slightly different in the sense that we assume the labels of the negative class are confidently assigned and the goal of the classifier is to assign a confidence measure to labels of the first class. Such problems are often encountered in large-scale biological screening, where multiple independent events are tested against a null hypothesis to discriminate real biological effects from noisy data. In microarray experiments, the expression level of genes is tested against the background signal [ [START_REF] Storey | Statistical significance for genome-wide studies[END_REF]. In mass spectrometry protein screening, potentially positive matches between spectra and peptide sequences are tested for correctness against peptide-spectrum matches that are known to be negative because they were generated randomly [START_REF] Elias | Target-decoy search strategy for increased confidence in large-scale protein identifications by mass spectrometry[END_REF].

Given a scoring function for these events, a widely used approach, both in microarray and proteomic applications, is to assign to each event a statistical confidence measure, the q-value, defined as the proportion of higher scoring events that turn out to be known negatives. Events below a certain user-specified q-value threshold are considered statistically significant and are selected for further biological identification. In practical terms, a q-value threshold can be interpreted as the proportion of significant events that will turn out to be false leads [START_REF] Storey | Statistical significance for genome-wide studies[END_REF].

When such problems are addressed in classification framework, the goal is to discriminate the significant events from the nonsignificant ones. In this setup, the labels of the negatives are confidently assigned, while the labels of the positives are to be verified. In order to hit the user specified q-value threshold q, the classifier must satisfy the constraint q(1 -P nd ) = P fa .

Earlier works simply train a classifier using the available labels, without taking into account the uncertain nature of the positive labels. Then, they use the ordering induced by the classifier to assign q-values, and, finally, select a subset of examples with q-values below a desired threshold [START_REF] Käll | A semi-supervised machine learning technique for peptide identification from shotgun proteomics datasets[END_REF]]. This approach is equivalent to constructing an ROC curve of the classifier and taking a single point on the ROC curve.

Alternatively, [START_REF] Spivak | Improvments to the percolator algorithm for peptide identification form shotgun proteomics data sets[END_REF] propose an algorithm that directly optimizes the classifier for a single specified q-value threshold or a set of such thresholds. Their approach is equivalent to optimizing the ROC curve in the vicinity of the point corresponding to the q-value threshold q. A precise formulation of this objective leads to a formulation that is strikingly similar to NP classification. Indeed, maximizing true positives rate while keeping the user-specified q-value amounts to solving min

f ∈H Ω(f ) + C Pnd subject to Pfa ≤ q(1 -Pnd ).
The machinery of the section 3 is easily adaptable with the new Lagrangian

L(f, λ) = Ω(f ) + (C + λq) Pnd + λ( Pfa -q) . ( 13
)
This Lagrangian is obviously related to (7) and therefore is amenable to similar algorithms. Adapting the stochastic algorithm requires some ingenuity because the λ update depends on both the positive and negative examples. We have modified algorithm 4 to pick at each iteration both a random positive example x + t and a random negative example x - t . We update the model parameters w using the gradient of the Lagrangian (13) restricted to these two randomly picked examples. Finally we update the Lagrange parameter λ with

λ ← λ 1 + ν t (-f (x - t )) -q 1 -(f (+x + t )
) .

EXPERIMENTS

This section reports experimental results obtained with the various algorithms discussed in this paper. Subsection 5.1 presents the various datasets used in our experiments. Subsections 5.2 and 5.3 present exploratory results characterizing the performance of the Annealed NonConvex NP-SVM algorithm. Subsections 5.4 and 5.5 present Neyman-Pearson classification results obtained using Gaussian Kernel SVMs on small-scale and medium-scale datasets and Linear SVMs on mediumscale and large-scale datasets. Finally, subsection 5.6 reports on a real life q-value Batch and online learning algorithms for Nonconvex Neyman-Pearson classification

• 11 optimization problem using both a Gaussian Kernel SVM and a nonlinear multilayer network as classifiers (subsection 5.6.)

Datasets

Table I summarizes the main characteristics of our datasets. Some exploratory results reported in sections 5.2 were obtained using synthetic data inspired from [START_REF] Bach | Considering cost asymmetry in learning classifiers[END_REF]]. The dataset consists of 2500 two-dimensional points. An equal number of of positives and negatives points are drawn from two gaussian distributions shown in figure 2. The q-value optimization experiments were carried out using a proteomics dataset consisting of 139410 samples with positive and negative samples equally represented [START_REF] Spivak | Improvments to the percolator algorithm for peptide identification form shotgun proteomics data sets[END_REF]].

Speedups achieved by the Annealed NonConvex NP-SVM algorithm

This section compares the performance of the Annealed NonConvex NP-SVM (algorithm 3) with the performance of a more direct implementation of the Uzawa algorithm consisting of using algorithm 2 as the minimization step of the Uzawa algorithm 1.

Our first experiments trains a Gaussian Kernel SVM on the Synthetic dataset. We formed a set of 20 pairs (C + , σ) ∈ [10 -2 , 10 -2 ]×[10 -2 , 10 -2 ] where σ is the bandwidth of the kernel and C + the cost assigned to positive samples. Both algorithms were tested with these hyperparameters for values of ρ in {0.01, 0.05, 0.1, 0.2}. The algorithms were implemented in C++ using a SMO optimizer [START_REF] Platt | Fast training of support vector machines using sequential minimal optimization[END_REF]] and a kernel cache. The cache vastly speeds up the algorithms because kernel matrix coefficients computed during the earlier iterations can be used during the later iterations.

Table II reports results averaged on all values of the hyperparameters (C + , σ). The Annealed NonConvex NP-SVM algorithm considerably accelerates the convergence. The table also shows the P fa and P nd differences evaluated by directly sampling test examples from the Gaussian distributions. These differences are statistically insignificant according to a Wilcoxson signed rank test with p-value threshold 10 -3 .

Table III reports the speedup factors achieved by repeating this experiment on the medium size dataset Spambase. We do not report on the final P fa and P nd because the differences were similarly insignificant.

Both tables reveal that the Annealed NonConvex N-SVM speedup is higher for small values ρ. This probably happens because such values of ρ lead to extreme ratios between the quantities C + and C -= λ/n -and penalize the computing times of the Asymmetric NonConvex SVM solver called during the minimization step of the Uzawa algorithm.

• 13

Table II. Comparison of the Annealed NonConvex NP-SVM solver (algorithm 3) with the pure Uzawa approach (algorithms 1 and 2) on the Synthetic dataset. The second column reports the speedup factor. The remaining columns report the differences in final P fa and P nd test errors. These differences are not statistically different.

Initialization of the Annealed NonConvex NP-SVM algorithm

This section investigates the influence of the initialization on the solution computed by the Annealed NonConvex NP-SVM solver (algorithm 3). For the sake of simplicity, we only consider a linear SVM trained on the Spambase dataset. Besides the initialization β = 0, which corresponds to training a plain SVM during the first iteration, we run the algorithm using 24 randomly generated initial vectors β and measure the error probabilities Pnd and Pfa achieved at convergence on the training set. The experiment was repeated for different values of C.

Figure 3 reports the results. Unsurprisingly, since the NP problem is intrinsically nonconvex, the initializations impact the solutions. The simplest initialization β = 0 does not always lead to the best solution. However all the results are empirically very close to those achieved by using β = 0.

Neyman-Pearson classification using Gaussian Kernel SVMs

This section compares Gaussian Kernel SVMs trained on the small-scale and mediumscale datasets using the Annealed NonConvex NP-SVM algorithm (NP-SVM, algorithm 3), the convex cost-sensitive SVM (AC-SVM) [START_REF] Davenport | Tuning support vector machines for minimax and neyman-pearson classification[END_REF], and the generative approach (GEN) [START_REF] Huang | Imbalanced learning with a biased minimax probability machine[END_REF]]. We only report the best GEN results achieved using Chebychev bound Ψ(u) to model probabilities of error (see section 2.1). We do not report results using the Stochastic NP optimizer (algorithm 4) because it is not suited to kernel machines. We do not report results obtained with SVMPerf [START_REF] Joachims | A support vector method for multivariate performance measures[END_REF]] because, running the algorithm for plain kernel machines is "painfully slow", according to the SVMPerf web site.

The hyperparameters of the different methods were determined by cross-validation. Different algorithms have different model selection requirements: GEN only requires choosing a kernel bandwidth σ, whereas NP-SVM requires finding a pair (C, σ), and AC-SVM requires finding the best triplet (C + , C -, σ). The best classifier for each method was selected using the validation criterion [START_REF] Davenport | Tuning support vector machines for minimax and neyman-pearson classification[END_REF]:

J val = P nd + max(0, P fa -ρ)/ρ .
• Gasso et al. This criterion has the property to enforce strongly the false alarm rate constraint for small values of ρ. All reported results were of course measured on the testing set after completing all the model selection procedure using a validation set or using 4-fold cross-validation, as explained in subsection 5.1. Following [START_REF] Davenport | Tuning support vector machines for minimax and neyman-pearson classification[END_REF], for each parameter, 10 logarithmically spaced values in the range 10 -2 , 10 2 were explored. This means that 10 3 triplets (C + , C -, σ) were tested for AC-SVM while only 100 pairs (C, σ) and 10 parameters σ were respectively tested for NP-SVM and GEN. We used a C++ implementation of the SVM solvers with Torch4 bindings, and a Matlab implementation of the generative approach5 .

Figure 4 reports the final classification errors P nd and P fa , and the corresponding computation time achieved for several values of ρ.

As expected, NP-SVM tightly satisfies the false alarm constraint. NP-SVM achieves P nd misclassification rates similar or slightly better than AC-SVM on the Spambase, Breast, and Pima datasets. AC-SVM seems to perform better on PageBlocks. The reason could be related to the small number of negative samples available for the latter dataset. Indeed, according to the experimental protocol and Table I, when running NP-SVM for ρ = 0.01, one seeks a classifier with solely two misclassified negatives. NP-SVM strives to fullfill the constraint and overfits. On the other hand, on GammaTelescope, the number of examples is significantly higher, and NP-SVM reaches a better P nd than the competing techniques.

Except for Spambase and Breast, GEN was not able to attain P nd results competitive with NP-SVM or AC-SVM. GEN achieves a better P nd on PageBlock at the price of violating the P fa constraint. Despite its Matlab implementation, GEN • Gasso et al.

appears to be the fastest method on the small size datasets. However, GEN slows down as soon as the size of the data grows, because its lack of sparsity results in expensive manipulations of the full kernel matrix. NP-SVM is very competitive with AC-SVM in terms of computation time, and even runs twice faster on Spambase6 . The computational load of NP-SVM is high for small ρs and decreases when ρ increases. This phenomenon could be explained as follows: for small ρs, NP-SVM sets λ at high values during training, leading to highly skewed asymmetry. The SVM solver is then driven into extreme situations and runs slowly.

Neyman-Pearson classification using Linear SVMs

This section compares Linear SVMs trained on the medium-scale and large-scale datasets using the batch Annealed NonConvex NP-SVM solver (BNP-SVM, algorithm 3), the online Stochastic NP optimizer (ONP-SVM, algorithm 4), the convex cost-sensitive SVM (AC-SVM) [START_REF] Davenport | Tuning support vector machines for minimax and neyman-pearson classification[END_REF], the generative approach (GEN) [START_REF] Huang | Imbalanced learning with a biased minimax probability machine[END_REF], and the SVMPerf algorithm (SVMPerf) [START_REF] Joachims | A support vector method for multivariate performance measures[END_REF]].

In the case of ONP-SVM, the hyperparameter selection searches the regularization parameter λ c in the set {0.0001, 0.0005, 0.001, 0.005, 0.01, 0.05, 0.1}. The learning rate γ was sougth as τ /n -with τ ∈ {0.1, 1, 5, 10, 50, 100}. The algorithm was run for 100 epochs on the medium-scale datasets and 50 epochs on the large-scale datasets.

In the case of AC-SVM, 15×15 values of (C + , C -) were searched in the hyperbox [0.001, 1000] 2 for Pageblocks and [0.01, 100] 2 for the other datasets. The search for BNP-SVM only explores 25 values of C for Pageblocks and 15 values of C for the other datasets. The generative approach GEN is parameter free.

The SVMPerf results were obtained by adapting the SVMPerf program7 to solve the Neyman-Pearson problem by exploiting its Precision/Recall@k mode. In this mode, SVMPerf computes a classifier yielding exactly k positive instances on the training set. Therefore the algorithm requires the specification of C and k. The hyperparameter C was searched as for the other SVM algorithm. Meanwhile, we explore ten values of k linearly spaced in the interval (1/n + , 1) and select value that most closely achieved the target P fa on the validation set. However the reported SVMPerf training times exclude the time required to search parameter k. We simply report the running time associated with the final value of k because it would theoretically have been possible, but far from easy, to modify the intricate SVMPerf loops to do this automatically.

Experiments on the large scale datasets Covertype and RCV1-V2 were carried out using a number of speed optimizations. The SVM solver for AC-SVM was replaced by LIBLINEAR which is one of the most efficient solvers for linear SVM [START_REF] Hsieh | A dual coordinate descent method for large-scale linear SVM[END_REF]]. For the ONP-SVM experiments on RCV1-V2, we modified the stochastic gradient code of [START_REF] Bottou | Learning with large datasets[END_REF]] because it handles sparse vectors more efficiently than our baseline code.

• 17 of ρ. It is really fast, especially for Gammatelescope where the computation gains compared to BNP-SVM and AC-SVM are respectively around 12 and 20. Moreover, the performances of ONP-SVM in terms of P fa and P nd are similar to those of batch methods. Interestingly, P nd for ONP-SVM on Pageblocks is slightly better than its counterpart for the other algorithms, suggesting that ONP-SVM overcomes the lack of robustness of BNP-SVM in this regime. For GammaTelescope, our proposed approaches clearly outperform AC-SVM and GEN. The performances for AC-SVM could be improved using a finer grid search for C + and C -or using a regularization path procedure [Yu et al. 2009]. However, this would increase the computing times. In particular the regularization path approach, in worst case scenario, has to visit an exponential number of kinks [START_REF] Gärtner | An exponential lower bound on the complexity of regularization paths[END_REF]]. SVMPerf matches the speed and the accuracy of ONP-SVM on the Spambase and Pageblocks datasets. It remains competitive in speed on the GammaTelescope dataset, but shows poor accuracies for small values of ρ. Enlarging the search interval for C or sampling k more finely did not provide any improvement. A possible explanation may lie with the fact that SVMPerf optimizes a convex upper bound of the target criterion, instead of the intrinsically nonconvex Neyman-Pearson objective. The scalability issues of SVMPerf become apparent on the Covertype dataset (figure 6). Although the performances of SVMPerf could be improved by exploring more hyper-parameters, its very long training time discourages such a search.

The RCV1-V2 results shown in of the Stochastic NP Optimizer (ONP-SVM). Each run of ONP-SVM takes 30.44 seconds on average, whereas each call to the LIBLINEAR solver in AC-SVM takes 79.50 sec. As we tested 100 pairs of parameters (C + , C -) for AC-SVM and only 36 pairs (γ, ν) for ONP-SVM, the computing time gain is highly appreciable.

Illustration of q-value optimization on proteomics dataset

This subsection experimentally evaluates the q-value algorithms described in section 4 using the proteomics dataset described in [START_REF] Spivak | Improvments to the percolator algorithm for peptide identification form shotgun proteomics data sets[END_REF]. Following [START_REF] Spivak | Improvments to the percolator algorithm for peptide identification form shotgun proteomics data sets[END_REF]], the performances was measured in terms of number of true positives correctly ranked over false positives. Table V summarizes the outcome of training a Gaussian Kernel SVM using of batch annealed nonconvex approach (qSVMOpt), and training a neural network using a stochastic gradient approach (qNNOpt). The neural network replicates the structure of the state-of-the-art model (qRanker) [START_REF] Spivak | Improvments to the percolator algorithm for peptide identification form shotgun proteomics data sets[END_REF]] with a single hidden layer with 5 units. We use a sigmoid loss for qNNOpt and a ramp loss for qSVMOpt. Clearly our methods achieve the best generalization results, mainly for small q values which are of great importance in practice. The performance gain is greater than 10%. Let also mention that for qSV-MOpt the computation time to solve for only one pair (C, σ) is about 41h while the neural network takes only 1h for 100 epochs. This illustrates the efficiency of the stochastic algorithm.

CONCLUSION

We have proposed a batch approach suited for kernel machines and online learning strategy for large datasets to tackle non-convex Neyman-Pearson classification problem. Experimental evaluations clearly illustrate the improvments achieved when dealing with non-convex NP problem. The stochastic gradient method was shown to be fast and interestingly efficient in generalisation. The approach was extended succesfully to solve q-value optimization problem in mass spectrometry protein screening applications. Interesting perspectives concern the extension of the online approach to kernel case or application of our NP solver to address bipartite ranking problem [Clémençon and Vayatis 2007].

• Gasso et al.

We now consider problem 14 with a single inequality constraint, min x∈R n f (x) subject to g(x) ≤ 0 , and its Lagrangian L(x, λ) = f (x) + λg(x). Let x * λ and x * λ be local minima of the Lagrangian for the fixed values λ and λ . We can assume that our local minima satisfy the following inequalities L(x * λ , λ) ≤ L(x * λ , λ) and L(x * λ , λ ) ≥ L(x * λ , λ ) . ( 16)

Assume for instance that the first inequality above is not satisfied. This would mean that x * λ is a better local minimum of L(•, λ) than x * λ . We could simply pick the best minimum instead of the inferior one. Proof. The inequalities ( 16) can be rewritten as:

λ (g(x * λ ) -g(x * λ )) ≤ f (x * λ ) -f (x * λ ) ≤ λ(g(x * λ ) -g(x * λ )
) . If λ > λ > 0, we must have g(x * λ ) -g(x * λ ) ≤ 0 to ensure that the lower bound is smaller than the upper bound. Therefore g(x * λ ) ≤ g(x * λ ) and f (x * λ ) ≥ f (x * λ ). Therefore, under the assumption ( 16), the Uzawa algorithm (algorithm 1) amounts to searching the correct Lagrange coefficient in the nonincreasing sequence Pfa (f * λ ). The sign of the derivative ∇ λ L(f * λ , λ) = Pfa (f * λ ) -ρ truthfully indicates whether λ is above or below the correct value. Furthermore observe that assumption (16) can be realized by initializing each minimization with the local optimum obtained for the previous value of the Lagrange coefficient λ.

Fig. 1 .

 1 Fig. 1. Approximations of 0-1 loss. atan(z) = 1/2+arctan(-βz)/π and erf (z) = 1/2+erf(-βz)/2. Definitions of the other cost functions are detailed in the text.

Fig. 2 .

 2 Fig. 2. Synthetic data for section 5.2.

Fig. 3 .

 3 Fig. 3. Influence of the initialization on the Annealed NonConvex NP-SVM solver. The red star represents the initialization β = 0. The yellow squares correspond to 24 random initializations.

Fig. 4 .

 4 Fig. 4. Performance comparison for a Gaussian Kernel SVMs on different datasets (row-wise plots). Left: P fa . Middle: P nd . Right: total training time, including model selection. Results are averaged over 10 runs for GammaTelescope and 25 runs for the other datasets. In the left column, the cyan dash-dotted line represents the curve P fa = ρ.

Figure 5 Fig. 5 .Fig. 6 .

 556 Figure5reports the results obtained on all datasets but RCV1-V2. For readability, the SVMPerf results on Covertype are shown separately in figure6. The RCV1-V2 results are shown separately in table IV.

Theorem 3 .

 3 Consider a family of local minima { x * λ : λ ∈ Λ ⊂ R * + } satisfying the inequalities (16) for any pair of Lagrange coefficients λ, λ ∈ Λ. Then f (x * λ ) and g(x * λ ) are respectively nondecreasing and nonincreasing functions of λ.

Table I .

 I Dataset summary

	Dataset	Sections	Features	n+	n-
	Synthetic	5.2	2	1250	1250
	Breast	5.4	30	357	212
	Pima	5.4	8	500	268
	Spambase	5.2,5.3,5.4,5.5	57	2788	1813
	Pageblocks	5.4, 5.5	10	4913	560
	GammaTelescope	5.4, 5.5	10	12332	6688
	Covertype	5.5	54	211840	20510
	RCV1-V2	5.5	47152	684494 119920
	Proteomics	5.6	17	69705	69705

  TableIII. Comparison of the Annealed NonConvex NP-SVM solver (algorithm 3) with the pure Uzawa approach (algorithms 1 and 2) on the Spambase dataset. Speedup factor 6.45 ± 7.81 4.31 ± 5.12 3.96 ± 4.81 3.19 ± 3.58

	ρ	Speedup factor P annealedDC fa	-P fullUzawa fa	P annealedDC nd	-P fullUzawa nd
	0.01	3.96 ± 2.74	(20 ± 71) × 10 -5	(-3.6 ± 31.5) × 10 -4
	0.05	3.86 ± 3.30	(37 ± 88) × 10 -5	(-7.3 ± 18.2) × 10 -4
	0.1	2.32 ± 1.51	(24 ± 90) × 10 -5	(-7.4 ± 24.7) × 10 -4
	0.2	2.71 ± 1.78	(36 ± 72) × 10 -5	(-6.5 ± 14.8) × 10 -4
		ρ	0.01	0.05	0.1	0.2

Table IV .

 IV Performance comparison for a Linear SVM on the RCV1-V2 dataset. Top row: ρ = 0.1% (left) and ρ = 0.5% (right). Bottom Row: ρ = 5% (left) and ρ = 10% (right).

		ONP-SVM AC-SVM		ONP-SVM AC-SVM
	Pfa	0.029%	0%	Pfa	0.31%	0.145%
	Pnd	76.8%	93.26%	Pnd	60%	59.35%
		ONP-SVM AC-SVM		ONP-SVM AC-SVM
	Pfa	4.69%	5.01%	Pfa	10%	8.3%
	Pnd	11.84%	9.53%	Pnd	4.63%	7.9%

Table V .

 V table IV again comfirm the good performance Batch and online learning algorithms for Nonconvex Neyman-Pearson classification• 19 Performance comparisons for q-value optimization measured as the number of true positives correctly identified on the testing set.

	q	qRanker qSVMOpt qNNOpt
	0.0025	4449	4947	5005
	0.01	5462	5666	5707
	0.1	7473	7954	7491

ACM Journal Name, Vol. V, No. N, Month 20YY, Pages 1-0??.

ACM Journal Name, Vol. V, No. N, Month 20YY.

The acronym DC stands for "Difference of Convex functions". ACM Journal Name, Vol. V, No. N, Month

20YY.

http://archive.ics.uci.edu/ml/ ACM Journal Name, Vol. V, No. N, Month 20YY.

http://jmlr.csail.mit.edu/papers/volume5/lewis04a/lyrl2004_rcv1v2_README.htm ACM Journal Name, Vol. V, No. N, Month 20YY.

See http://torch5.sourceforge.net/

See http://appsrv.cse.cuhk.edu.hk/ ~miplab/mempm_toolbox/index.htm ACM Journal Name, Vol. V, No. N, Month 20YY.

During experiments carried out on other UCI small-scale datasets (Liver and Ionosphere), AC-SVM runs up to 1.5 times faster than NP-SVM. However, the computation time in question is about 25 seconds.

7 http://www.cs.cornell.edu/People/tj/svm_light/svm_perf.html ACM Journal Name, Vol. V, No. N, Month 20YY.

A. NONCONVEX CONSTRAINED OPTIMIZATION

This appendix summarizes known results about the constrained optimization of nonconvex functions. We consider the problem

and its Lagrangian

The sufficiency result needs no additional assumption:

Proof. From inequality (i) in ( 15), (µ i -λ i )g i (x) ≤ 0. We see that x is feasible, that is, g i (x) ≤ 0, by letting each µ i go to +∞. Therefore λ i g i (x) ≤ 0. On the other hand, setting µ = 0 gives λ i g i (x) ≥ 0. Therefore λ i g i (x) = 0. Combining with inequality (ii), for all y ∈ V(x) such that g i (y) ≤ 0 for i = 1 . . . m, we have g(x) = L(x, λ) ≤ L(y, λ) ≤ g(y) . Therefore x is a local minimum of problem ( 14).

Necessity results are more complicated because they involve delicate aspects of the Karush-Kuhn-Tucker (KKT) theory. But it is important to note that convexity is not required to establish that the KKT conditions are necessary:

Theorem 2 [START_REF] Ciarlet | Introduction to Numerical Linear Algebra and Optimisation[END_REF]]. Let x be a local minimum of problem (14) and let I = { i; g i (x) = 0 }. If the function f is differentiable in x, the functions g i are differentiable in x for all i ∈ I, the functions g i are continuous in x for all i / ∈ I, and the constraints are KKT-qualified in x, then there exist λ ∈ R m + such that λ i g i (x) = 0 and ∇ x L(x, λ) = 0.

The Neyman-Pearson problem involves a single inequality constraint that is trivially KKT-qualified via the linear independence constraint qualification criterion. On the other hand, this theorem does not apply when we use the ramp loss because the minimum is likely to be achieved on a non differentiable point. But even in that case, theorem 1 ensures that any saddle point discovered by our algorithms is a feasible local minimum.


Melanie Dulong

Rosnay Fellow

Check Your Data Freedom: A Taxonomy to Assess Life Science Database Openness

Keywords: Life science data, open access, bioinformatics, copyright law, database, taxonomy, Science

Molecular biology data are subject to terms of use that vary widely between databases and curating institutions. This research presents a taxonomy of contractual and technical restrictions applicable to databases in life science. It builds upon research led by Science Commons demonstrating why open data and the freedom to integrate facilitate innovation and how this openness can be achieved. The taxonomy describes technical and legal restrictions applicable to life science databases, and its metadata have been used to assess terms of use of databases hosted by Life Science Resource Name (LSRN) Schema. While a few public domain policies are standardized, most terms of use are not harmonized, difficult to understand and impose controls that prevent others from effectively reusing data. Identifying a small number of restrictions allows one to quickly appreciate which databases are open. A checklist for data openness is proposed in order to assist database curators who wish to make their data more open to make sure they do so.

Introduction

This work is being developed under the auspices of the Science Commons Data project and builds upon the Science Commons Open Access Data Protocol proposing requirements for interoperability of scientific data. Legal simplicity and predictability can be achieved by waiving copyright and other contractual restrictions, allowing data integrators to reuse, modify and redistribute large datasets, towards the freedom to integrate [START_REF]Literature Board on Life Sciences (BLS), Sharing Publication-Related Data and Materials: Responsibilities of Authorship in the Life Sciences[END_REF] . Legal accessibility issues are not the only hurdle to data integration. Technical accessibility 2 should be ensured in order to allow scientists to download data easily and use them in any way, including ways that the initial creators had not considered.

The objective of this research is to assess the accessibility of databases by analysing their access interfaces and their reuse policies. After presenting the rationale for sharing data in life science, we will qualify databases openness by analyzing a set of technical access interfaces and legal terms of use. A taxonomy of technical and legal restrictions will be presented and used to assess a sample of databases. Based on these criteria, we will propose a set of questions for database curators to assess their own data technical and legal openness.

The context of data sharing

The Human Genome project developed standards for rapid data sharing, allowing the scientific community to access and reuse data in other ways than the team at the origin of the first sequencing of the data. According to NIH-DOE Guidelines for Access to Mapping and Sequencing Data and Material Resources, "a key issue for the HGP (Human Genome Project) is how to promote and encourage the rapid sharing of material and data that are produced, especially information that has not yet been published or may never be published in its entirety. Such sharing is essential for progress toward the goals of the program and to avoid unnecessary duplication. It is also desirable to make the fruits of genome research available to the scientific community as a whole as soon as possible to expedite research in other areas."

Methodology

This research started with analyzing terms of use of databases from the Molecular Biology Database hosted by the Nucleic Acids Research Journal, and assessing them regarding open access criteria as described in the Science Commons Open Data Protocol. A policies sample has been retrieved and analyzed. The next step has been to identify barriers to open access and reuse of data from these database policies, and to build a taxonomy of restrictions. These restrictions can be of legal or contractual nature, but they can also be technical, e.g. the impossibility of downloading the whole database if its results can be accessed only through a field-based search. A systematic analysis of more database policies hosted by the Life Science Resource Name (LSRN) Schema registry allowed us to confirm this taxonomy and to refine it by adding other terms.

In this section, we will define technical and legal accessibility conditions and restriction values. The purpose of identifying controls and restrictions applicable to databases is twofold. First, it will allow us to understand terms of use and other requirements governing the access to molecular biology databases and especially which control prevent the free sharing of data Second, these restrictions will be clustered into classes, making it possible to systematize the analysis of databases and to easily identify the data that are in the public domain and therefore can be reused by the scientific community.

The design of a taxonomy

Two types of control can be exercised on databases: technical restrictions embedded in the design of the database, and legal restrictions expressed in the terms of use.

Technical restrictions affect databases that cannot be searched or processed in any possible way. Technical openness is ensured by the possibility of downloading the whole dataset and reusing and integrating data, in the same way the Science Commons Neurocommons project provides a datamining platform allowing machine-readable representation and interpretation of data, or that Basic Local Alignment Search Tool (BLAST) finds similarities between sequences. Semantic web processing applyed to scientific data should improve the way science is performed and allow network effects by connecting knowledge from various datasets. Databases that require registration before access, or offer only a batch processing or a query-based mechanism to retrieve data after a specific search, do not comply with the technical requirements necessary to make data open.

Terms of use, licenses or access policies are legal texts describing authorized and unauthorized usages. Those legal rules are expressed by the entity distributing a product such as software or scientific data. The infringement of those self-declared rights can lead to lawsuits. Terms of use can be difficult to understand, even for lawyers, while scientists need to know quickly whether they can use a dataset. Therefore, a set of questions has been designed to understand whether databases are, in fact, in the public domain and whether the data can be reused, redistributed and integrated.

Technical accessibility

Downloadability

Is there a link to download the whole database? YES or NO If YES, include the URL Batch Is it possible to access the data through a batch feature? YES or NO Query Is it possible to access the data through a query-based system? YES or NO Registration Finally, is registration compulsory before downloading or accessing data in the ways described above? YES or NO

Legal accessibility

Terms of use Does the database have a policy? YES or NO If YES, include the URL and assess whether the policy authorize reuse, redistribution, integration Are there any restrictions on the right to reformatting and redistributing? If NO If YES, which restrictions? Fields to describe restrictions are Attribution Contractual Requirements Non Derivative Use Non Commercial Use Share Alike Others (to be described).

Fig. 1. Set of questions to process databases

The questions in Figure 1 allow the processing of databases. A subsequent database has been developed with information describing databases technical and legal accessibility.

Five answers can be provided to these questions and constitute a taxonomy to assess technical and legal openness, as presented in Figure 2 below.

DOWNLOADABILITY

The website provides a file transfer protocol or a link to download the whole dataset without registration. The ability to download the whole dataset without registration constitute the double requirement to be considered as technically accessible.

2. TECHNICAL RESTRICTION: the database can be accessed only through registration, batch or query-based system. Technical accessibility is not achieved.

3. PUBLIC DOMAIN POLICY: the website provides simple and clear terms of use informing users that the data are in the public domain. Data are thus free to integrate. Legal accessibility is achieved.

4. NO POLICY: the website does not provide terms of use. Legal accessibility is not achieved. 5. LEGAL RESTRICTIONS: the terms of use impose contractual restrictions, such as heavy contractual requirements for attribution, limitation to non-commercial usages, prohibition to modify data, or other constraints on their redistribution or modification. Legal accessibility is not achieved. The data are not free to integrate.

Databases analysis according to the taxonomy

Samples of the Nucleic Acids Research (NAR) Molecular Biology Database Collection MBDC and Life Science Resource Name (LSRN) Schemas databases have been analyzed to define the taxonomy. Then one third of the LSRN databases (60 databases) have been systematically analyzed. A subsequent database has been created, gathering for each of these databases: -The name and URL of the database, -URL of the download page and URL of the terms of use, -Extracts of the terms of use for further review and comments, -Values for technical accessibility and legal accessibility features as described in Figure 1.

Technical openness

Four values have been identified to assess technical accessibility: Downloadability, Batch features, Query-based system and Registration.

The only combination qualifying the database as technically open is the ability to download without registration. Indeed, registration before access and the possibility to perform only batch or query-based searches prevents automated data mining. However, it can be useful to have access to several systems to retrieve and analyze data. Therefore, the database indicates whether it is possible to retrieve data also through batch and query in addition to download.

Another technical restriction that hasn't been analyzed is the presence of standardized annotations or comments allowing users to understand data collected by others. This feature has been disregarded because of a lack of expertise to assess the relevance and quality of annotation for external reuse. A user rating process to evaluate the freshness of the data will be part of the second stage of the project.

Legal openness

Values have been used to define legal accessibility are the following: Policy Available, Public Domain Policy, Attribution Contractual Requirements, Non Derivative Use, Non Commercial Use, Share Alike and Others to be described.

In order to be open, a database must have a policy, and this policy must equal to the Public Domain.

The absence of any terms of use or policy on the database website could imply that, in the absence of any expressed restrictions, data are free. But rights unknown to the user might be applicable by default. Indeed, the Protocol states that « any implementation MUST affirmatively declare that contractual constraints do not apply to the database. » Policies should be clear and have only one possible legal interpretation. The absence of a clear and understandable policy is equivalent to the absence of a policy because it leads to legal uncertainty.

Any restriction to the redistribution and the modification of data will prevent the qualification of the policy as Public Domain policy. Legal restrictions to redistribute and modify of data can be diverse. Four values have been identified, corresponding to Creative Commons licenses options: Attribution Contractual Requirements, Non Derivative Use, Non Commercial Use, Share Alike. However, the definition for these legal restrictions in the context of this research is broader than the Creative Commons definitions. The Attribution requirement may constitute a restriction on the reuse of data. Instead of strong contractually binding requirements on how data should be attributed, a request of acknowledgment according to scientific norms should be sufficient. According to the Protocol, "any implementation SHOULD define a non-legally binding set of citation norms in clear, lay-readable language". Furthermore, "Community standards for sharing publicationrelated data and materials should flow from the general principle that the publication of scientific information is intended to move science forward. More specifically, the act of publishing is a quid pro quo in which authors receive credit and acknowledgment in exchange for disclosure of their scientific findings. An author's obligation is not only to release data and materials to enable others to verify or replicate published findings (as journals already implicitly or explicitly require) but also to provide them in a form on which other scientists can build with further research."3 The Non Commercial and Non Derivative requirements prevent many types of data use. They are defined as restrictions based on the commercial nature of the user or of the usage, and as restrictions on the distribution of modified versions of the database. The Share Alike requirement is present in the original taxonomy: this option requests modifications to be offered under the same open terms and should gather all copyleft policies.

No policy in the analyzed sample contains this requirement. A field should be foreseen for other possible restrictions that may affect terms of use but haven't been identified in the initial subsets. For instance, an embargo on publishing before the data producer, the existence of patents and the absence of warranties against third-party rights are legal restrictions which have not been taken into account in this first analysis. They deserve a subsequent analysis within the scope of databases legal context and issues preventing the freedom to integrate.

In many cases, the database is offered with no restrictions placed by the database curator, but without warranties on the legal status of the data submitted by contributors. Data may contain elements protected by copyright or any applicable right. The database curator did not clear the rights, or did not request from the contributors a rights waiver or no rights assertion before data upload, or does not want to be held liable in case the previously described processes would present a failure. This warranties disclaimer can be seen as a hurdle to the usage of these data. Both uncertainty for the end-user and absence of responsibility for the curator could be avoided by proposing to contributors a data sharing agreement prior to submission, seamlessly integrated in the upload process. Although this procedure might disincentivize some contributors, the burden of checking the legal status of data and avoiding possible claims by third parties should not rely on the data user, forcing her to hire a lawyer. Besides, these disclaimers do not identify which data are free and which parts of the database might be copyrighted or covered by other rights.

Results

Databases which can be considered legally and technically open, and compliant with the Science Commons Open Data Protocol are those that are downloadable without prior registration, under a public domain simple policy. Databases available only through batch or query interfaces are not considered technically open, but those offering these features in addition to downloadability will be compliant.

Besides databases created by the National Center for Biotechnology Information (NCBI) and the European Bioinformatics Institute (EBI), only a couple of databases among the 60 first schemas of the LCRN registry analyzed sample can be considered as both technically and legally open, without restrictions. These are almost exclusively governmental databases.

NCBI is part of the US National Institutes of Health and the EBI is part of European Molecular Biology Laboratory (EMBL), funded by its 20 member states, as well as the European Commission, Wellcome Trust, US National Institutes of Health, UK Research Councils, our industry partners and the UK Department of Trade and Industry. Not only these institutions are pioneers in bioinformatics and genetics, but also in setting Open Access policies. Indeed, the NIH Public Access Policy requires "scientists to submit journal final peer-reviewed manuscripts that arise from NIH funds to the digital archive PubMed Central (…) to help advance science and improve human health". The European Research Council Scientific Council Guidelines for Open Access also "requires that all peer-reviewed publications from ERC-funded research projects be deposited on publication into an appropriate research repository", but only "considers essential that primary data -which in the life sciences for example could comprise data such as nucleotide/protein sequences, macromolecular atomic coordinates and anonymized epidemiological data -are deposited to the relevant databases."

It seems that the next challenge for Open Access will be to analyze barriers and incentives to the deposit of scientific data in open repositories.

A checklist to assess databases openness

We propose a checklist to assist data curators in opening their data, and to make sure that the database design and terms of use will allow others to access, reuse and build upon their data. All answers should be positive.

A. Check your database technical accessibility

Conclusion

This article presents technical and legal restrictions typically applied to life science databases based on the analysis of two samples of terms of use. Most of these terms of use impose legal restrictions on the redistribution of data. The absence of policy, or of clear and understandable terms, also prevents reuse by the lack of legal certainty. Besides legal restrictions, many databases impose technical constraints on their users. The impossibility or the difficulty of downloading and reformatting the dataset does not fulfill technical accessibility requirements. Databases available only through batch or query interfaces are not considered technically open, but those offering these features in addition to downloadability will be compliant. Databases that can be considered legally and technically open, and compliant with the Science Commons Open Data Protocol are those that are downloadable without prior registration, under a public domain simple policy.

Future work

A user interface has been built to host the dataset assessing databases technical and legal accessibility. A search function allows the classification of databases according to their accessibility status and the identification of those that are compliant with the protocol. The dataset analyzing databases' terms of use with regard to the taxonomy can now be opened to other contributors in order to gather more results and assess the level of restrictions of more databases in the field. Statistical analysis may be performed on those data to assess the degree of openness on a given databases sregistry. It would also be interesting to know whether the taxonomy can be extended to other disciplines. This dataset of legal and technical controls can also serve as a repository for commenting on databases policies. The taxonomy allows search according to technical and legal restrictions, and this can provide researchers clear information on what they can and cannot do. It is also possible to implement these restrictions into metadata expressed with the ccREL standard, and turn the taxonomy into a formalized ontology of database freedoms. It is also possible to develop the website into a repository similar to OAKlist or the Sherpa/Romeo archiving scientific publishers copyright self-archiving policies. Classifying databases according to their access and reuse policy status may help scientists and open access scholars understand and appreciate which databases are really open without having to read all the policies, and maybe databases curators to further open their data.

Figure

  Figure 2. Databases qualification

A. 1 .

 1 Figure 3. Database openness checklist

Board on Life Sciences (BLS), Sharing Publication-Related Data and Materials: Responsibilities of Authorship in the Life Sciences (2003). http://books.nap.edu/books/0309088593/html/R1.html

Acknowledgments

This work has been developed within the Science Commons Data project during my 2007-2008 fellowship at Science Commons. I thank John Wilbanks for inspiration and support, and Shirley Fung for designing and developing the user interface hosting the database. I am also grateful to Carolina Rossini for analyzing some databases with me. I was expecting that two opinions on the terms of use would serve as a review of the categorization according to the taxonomy legal accessibility values. However, this experience proved to be more difficult than expected, demonstrating that if terms of use are not uniformely understood and categorized by two persons with legal expertise, they cannot be considered clear policies. Each one of them should all be thanked for reviewing the taxonomy and the paper at different stages of the project. Thinh Nguyen, Jonathan Rees and Victoria Stodden should also be thanked for their comments. Finally, this work would not have been possible without the database curated by Life Science Resource Name (LSRN).