We present an approximation scheme for support vector machine models that use an RBF kernel. A second-order Maclaurin series approximation is used for exponentials of inner products between support vectors and test instances. The approximation is applicable to all kernel methods featuring sums of kernel evaluations and makes no assumptions regarding data normalization. The prediction speed of approximated models no longer relates to the amount of support vectors but is quadratic in terms of the number of input dimensions. If the number of input dimensions is small compared to the amount of support vectors, the approximated model is significantly faster in prediction and has a smaller memory footprint. An optimized C++ implementation was made to assess the gain in prediction speed in a set of practical tests. We additionally provide a method to verify the approximation accuracy, prior to training models or during run-time, to ensure the loss in accuracy remains acceptable and within known bounds.
Support vector machine (SVM) classifiers often contain many SVs, which lead to high computational cost at runtime and potential overfitting. In this paper, a practical and effective method of pruning SVM classifiers is systematically developed. The kernel row vectors, with one-to-one correspondence to the SVs, are first organized into clusters. The pruning work is divided into two phases. In the first phase, orthogonal projections (OPs) are performed to find kernel row vectors that can be approximated by the others. In the second phase, the previously found vectors are removed, and crosswise propagations, which simply utilize the coefficients of OPs, are implemented within each cluster. The method circumvents the problem of explicitly discerning SVs in the high-dimensional feature space as the SVM formulation does, and does not involve local minima. With different parameters, 3000 experiments were run on the LibSVM software platform. After pruning 42 of the SVs, the average change in classification accuracy was only - 0.7 , and the average computation time for removing one SV was 0.006 of the training time. In some scenarios, over 90 of the SVs were pruned with less than 0.1 reduction in classification accuracy. The experiments demonstrate the existence of large numbers of superabundant SVs in trained SVMs, and suggest a synergistic use of training and pruning in practice. Many SVMs already used in applications could be upgraded by pruning nearly half of their SVs. Kernel-based learning methods provide their solutions as expansions in terms of a kernel. We consider the problem of reducing the computational complexity of evaluating these expansions by approximating them using fewer terms. As a by-product, we point out a connection between clustering and approximation in reproducing kernel Hilbert spaces generated by a particular class of kernels. Least Squares Support Vector Machines (LS-SVM) is aproven method for classification and function approximation. In comparison to the standard Support Vector Machines (SVM) it only requires solving a linear system, but it lacks sparseness in the number of solution terms. Pruning can therefore be applied. Standard ways of pruning the LS-SVM consist of recursively solving the approximation problem and subsequently omitting data that have a small error in the previous pass and are based on support values. We suggest a slightly adapted variant that improves the performance significantly. We assess the relative regression performance of these pruning schemes in a comparison with two (for pruning adapted) subset selection schemes, -one based on the QR decomposition (supervised), one that searches the most representative feature vector span (unsupervised)-, random omission and backward selection on independent test sets in some benchmark experiments. Least squares support vector machines (LS-SVM) is an SVM version which involves equality instead of inequality constraints and works with a least squares cost function. In this way, the solution follows from a linear Karush–Kuhn–Tucker system instead of a quadratic programming problem. However, sparseness is lost in the LS-SVM case and the estimation of the support values is only optimal in the case of a Gaussian distribution of the error variables. In this paper, we discuss a method which can overcome these two drawbacks. We show how to obtain robust estimates for regression by applying a weighted version of LS-SVM. We also discuss a sparse approximation procedure for weighted and unweighted LS-SVM. It is basically a pruning method which is able to do pruning based upon the physical meaning of the sorted support values, while pruning procedures for classical multilayer perceptrons require the computation of a Hessian matrix or its inverse. The methods of this paper are illustrated for RBF kernels and demonstrate how to obtain robust estimates with selection of an appropriate number of hidden units, in the case of outliers or non-Gaussian error distributions with heavy tails. c 2002 Elsevier Science B.V. All rights reserved.