Empirical comparison of cross-validation and internal metrics for tuning SVM hyperparameters

Highlights

• Compared cross validation with 5 internal metric to select SVM hyperparameters.

• Cross validation results in hyperparameters with better accuracy on new data.

• Distance between two classes (DBTC) is the second best algorithm.

• DBTC has the lowest execution time and is a very competitive alternative to 5-fold CV.

Abstract

Hyperparameter tuning is a mandatory step for building a support vector machine classifier. In this work, we study some methods based on metrics of the training set itself, and not the performance of the classifier on a different test set - the usual cross-validation approach. We compare cross-validation (5-fold) with Xi-alpha, radius-margin bound, generalized approximate cross validation, maximum discrepancy and distance between two classes on 110 public binary data sets. Cross validation is the method that resulted in the best selection of the hyper-parameters, but it is also the method with one of the highest execution time. Distance between two classes (DBTC) is the fastest and the second best ranked method. We discuss that DBTC is a reasonable alternative to cross validation when training/hyperparameter-selection times are an issue and that the loss in accuracy when using DBTC is reasonably small.

Introduction

Support Vector Machines (SVMs) are commonly used in classification problems with two or more classes. In its general formulation, SVM works by mapping input data (x) into a high-dimensional feature space (ϕ(x)), and building a hyperplane ($f\left(x\right)=w·\varphi \left(x\right)+b$) to separate examples from two classes. For a L1 soft-margin SVM, this hyperplane is defined by solving the primal problem:

$$\begin{array}{ccc}& & \text{min}\frac{1}{2}{\parallel w\parallel }^2+C\sum _{i=1}^n{\xi }_i\hfill \\ & & \text{subject}\text{to}{y}_i(w·\varphi \left(x_i\right)+b)\ge 1-{\xi }_i\hfill \\ & & \text{with}{\xi }_i\ge 0\text{and}1\le i\le n\hfill \end{array}$$

where x_i is a data example, and $y_i\in \{-1,1\}$ its label/class. Computationally this problem is solved on its dual form:

$$\begin{array}{ccc}& & \text{min}\frac{1}{2}{\alpha }^{T}K\alpha -e^T\alpha \hfill \\ & & \text{subject}\text{to}{y}^T\alpha =0\hfill \\ & & \text{with}0\le {\alpha }_i\le C\text{and}1\le i\le n\hfill \end{array}$$

where e is a vector of ones and $K_{ij}=k(x_i,x_j)=\varphi {\left(x_i\right)}^T·\varphi \left(x_j\right)$ is a kernel function that performs the ϕ mapping. The Gaussian Radial Basis Function (RBF) kernel is a common choice for the kernel function

$$k(x_i,x_j)=\text{exp}\left(-\gamma {\parallel x_i-x_j\parallel }^2\right).$$

The hyper-parameters C and γ must be defined before solving the minimization in Eq. (2) and must be carefully chosen to obtain a good accuracy. Choosing C and γ, known as hyper-parameter tuning or model selection, is usually done by performing a grid search over pairs of C and γ and testing each pair using some cross-validation procedure. Examples of cross validation procedures are: k-fold, repeated k-fold, bootstrap, leave one out, hold-out, among others.

Formally, if $\mathcal{D}$ is the data set, cross validation procedures will define a set of pairs of sets TR_i and TE_i, called train and test, such that:

$$\begin{array}{cc}\hfill T{R}_i\cap T{E}_i=& \varnothing \hfill \\ \hfill T{R}_i\cup T{E}_I\subseteq & \mathcal{D}\hfill \end{array}$$

Let us use the notation

$$\text{acc}\left(\mathcal{B}\right|\mathcal{A},C,\gamma )$$

to indicate the accuracy on a data set $\mathcal{B}$ of a SVM trained on data set $\mathcal{A}$ with hyperparameters C and γ.

Then the cross-validation of pair C, γ (for a data set $\mathcal{D}$ under some cross validation procedure) is:

$$ac{c}_{cv}(C,\gamma )={\text{mean}}_i\text{acc}\left(T{E}_i\right|T{R}_i,C,\gamma )$$

The best set of hyper-parameters, from a set of candidates S is:

$${\mathrm{argmax}}_{C,\gamma \in S}{\text{acc}}_{cv}(C,\gamma )$$

The expression C, γ ∈ S indicates that we are selecting the best C an γ from a pre-defined set of candidates (see Section 2.2).

This usual cross-validation procedure may be too costly, and there has been many proposals to consider measures of the training set itself as the ones that are maximized or minimized in order to select one or both hyper-parameters. We will call them internal metrics[9]; call them performance measures, [3] call then in-sample methods, [1] call them methods based on the Statistical Learning Theory.

If $\psi (\mathcal{D},C,\gamma )$ is one of these internal metrics, when applied to the set $\mathcal{D}$ with hyper-parameters C and γ, then Eq. (3) would be:

$${\text{argmax}}_{C,\gamma \in S}\psi (D,C,\gamma )$$

Again we are selecting the best hyperparameters from a pre-defined set of pairs S.

One of the ideas behind using internal metrics to select hyper-parameters is that the cost of selecting of hyper-parameters will probably be lower. For each pair of hyper-parameters, the cross-validation method has to learn a SVM for each of the TR_i sets, while the internal metrics method requires only one learning step, for the whole D. Furthermore, some of the internal metrics are convex functions on the hyper-parameters, and thus a gradient descent method can be used to select the hyper-parameters, instead of a grid search. This may also reduce the execution time of the whole learning process.

The aim of this paper is to replicate and update the works of [9] and [1] (discussed below), which tested some internal metric procedures against cross-validation procedures on a few data sets (5 and 13 respectively). We will perform a similar comparison of 6 internal metrics, one of which has not been used by the previous research, on 110 data sets. We will compare not only the quality of the hyper-parameter selection but also the execution time for such procedure.

Duan et al. [9] compare the following internal metrics:

• Xi-Alpha bound [12]

• Generalized approximate cross-validation [19]

• Approximate span bound [18]

• VC bound [17]

• Radius-margin bound [5]

• Modified radius-margin bound [7]

with a standard cross validation procedure to select hyper-parameters on 5 different data sets. Each data set was split into a training subset, with 400 to 1300 data points. The quality of the choice of hyper-parameters was the accuracy of the classifiers on the remaining test set.

Duan et al. [9] concluded that the cross validation procedures result in better classifiers. They also concluded that Xi-Alpha results in reasonable choices of the hyper-parameters in the sense that the resulting classifier had an accuracy close to that of the cross-validation classifier, but the choices of hyper-parameters were not close to the ones chosen by the cross-validation. They also concluded that approximate span and VC bound do not result in high accuracy classifiers, and that (unmodified) radius bound also do not result in good hyper-parameter selections. The two remaining methods, modified radius-margin and generalized approximate cross-validation result in choices worse than that of Xi-Alpha.

Anguita et al. [1] analyzed 5 cross-validation procedures (100 repetitions of bootstrap, 10 repetitions of bootstrap, 10-fold CV, leave-one-out, and 70%/30% split for training/test), and two internal metrics (compression bound [11] and maximal discrepancy [4]). They tested the procedures on 13 data sets, and discovered that all cross-validation procedures and maximal discrepancy metric were able to select appropriate hyper-parameters.

This research replicates those researches, but we use 110 binary data sets from the UCI; we do not test the VC bound, approximate span, and unmodified radius margin bounds, given the negative results of [9], and we include maximal discrepancy [4] and distance between two classes [16] as new internal metrics to be compared. We also compare the execution time of the procedures, since one of the intended goals of internal metrics methods is a faster selection procedure for hyper-parameters.

We must point out that this research does not cover all proposed internal metrics to select hyperparameters. As discussed above, we removed from consideration some of the older proposal that were shown by other experiments to perform worse than the others such as VC bounds, approximate span, and unmodified radius margin bounds. We also do not cover a recent internal metric proposed in [14] based on stability of the models[14]. show the efficacy of the metric in selecting hyperparameters in the cases where d ≫ n, that is, high dimensional data sets with few data points, which are not the cases tested in this paper. Another proposal not tested herein was the heuristics to select C and γ proposed in [13]: γ is selected based on the Euclidian distance (in the data space) between random samples of both classes, and C is selected from the distribution of values $\frac{1}{K(x_i,x_j)}$ for a small sample of data.

In the remaining of this paper we show a brief review of the methods in Section 2; the results are presented in Section 3 and conclusions in Section 4.