Estimating the Leave-One-Out Error for Classification Learning with SVMs
Arthur Gretton, Ralf Herbrich, Olivier Chapelle, Schoelkopf, B, Pjw Rayner · 2001
Abstract Three estimates of the leave-one-out error for *-support vector (SV) machine binary classifiers are presented. Two of the estimates are based on the geometrical concept of the span, which was introduced in the context of bounding the leave-one-out error for C-SV machine binary classifiers, while the third is based on optimisation over the criterion used to train the *-support vector classifier. It is shown that the estimates presented herein provide informative and efficient approximations of the generalisation behaviour, in both a toy example and benchmark data sets. The proof strategies in the *-SV context are also compared with those used to derive leave-one-out error estimates in the C-SV case 1 1 Introduction The estimation of the generalisation performance of support vector machine classifiers is an important and ongoing area of research. In the absence of a large body of data to be used for validation, it becomes necessary to estimate generalisation error using approximations that depend in some way on the training data. One such estimate is the leave-one-out error. In this case, a single point is excluded from the training set, and the classifier is trained using the remaining points. It is then determined whether this new classifier correctly labels the point that was excluded. The process is repeated over the entire training set, and the leave-one-out error is computed by taking the average over these trials; this provides an almost unbiased estimate of the generalisation error. One shortcoming of the leave-one-out method is that it is highly inefficient. To estimate the error, it is necessary to re-train the classifier over every support vector in the training set (non-support vectors do not contribute to the form of the final classifier, and can be excluded with impunity). Even assuming that the classifier is sparse in the training data, the computational overhead remains substantial. Thus methods are sought to speed calculation of the leave-one-out error, or bound it with an easily computed quantity.