Least-squares support-vector machine

Least-squares support-vector machines (LS-SVM) are least-squares versions of support-vector machines (SVM), which are a set of related supervised learning methods that analyze data and recognize patterns, and which are used for classification and regression analysis. In this version one finds the solution by solving a set of linear equations instead of a convex quadratic programming (QP) problem for classical SVMs. Least-squares SVM classifiers were proposed by Suykens and Vandewalle. LS-SVMs are a class of kernel-based learning methods.
From support-vector machine to least-squares support-vector machine.
Given a training set formula_1 with input data formula_2 and corresponding binary class labels formula_3, the SVM classifier, according to Vapnik's original formulation, satisfies the following conditions:
which is equivalent to
where formula_6 is the nonlinear map from original space to the high- or infinite-dimensional space.
Inseparable data.
In case such a separating hyperplane does not exist, we introduce so-called slack variables formula_7 such that
According to the structural risk minimization principle, the risk bound is minimized by the following minimization problem:
To solve this problem, we could construct the Lagrangian function:
where formula_12 are the Lagrangian multipliers. The optimal point will be in the saddle point of the Lagrangian function, and then we obtain
By substituting formula_14 by its expression in the Lagrangian formed from the appropriate objective and constraints, we will get the following quadratic programming problem:
where formula_16 is called the kernel function. Solving this QP problem subject to constraints in (8), we will get the hyperplane in the high-dimensional space and hence the classifier in the original space.
Least-squares SVM formulation.
The least-squares version of the SVM classifier is obtained by reformulating the minimization problem as
subject to the equality constraints
The least-squares SVM (LS-SVM) classifier formulation above implicitly corresponds to a regression interpretation with binary targets formula_19.
Using formula_20, we have
with formula_22 Notice, that this error would also make sense for least-squares data fitting, so that the same end results holds for the regression case.
Hence the LS-SVM classifier formulation is equivalent to
with formula_24 and formula_25
Both formula_26 and formula_27 should be considered as hyperparameters to tune the amount of regularization versus the sum squared error. The solution does only depend on the ratio formula_28, therefore the original formulation uses only formula_29 as tuning parameter. We use both formula_26 and formula_27 as parameters in order to provide a Bayesian interpretation to LS-SVM.
The solution of LS-SVM regressor will be obtained after we construct the Lagrangian function:
where formula_33 are the Lagrange multipliers. The conditions for optimality are
Elimination of formula_14 and formula_36 will yield a linear system instead of a quadratic programming problem:
with formula_38, formula_39 and formula_40. Here, formula_41 is an formula_42 identity matrix, and formula_43 is the kernel matrix defined by formula_44.
Kernel function "K".
For the kernel function "K"(•, •) one typically has the following choices:
where formula_46, formula_51, formula_52, formula_53 and formula_54 are constants. Notice that the Mercer condition holds for all formula_55 and formula_56 values in the polynomial and RBF case, but not for all possible choices of formula_53 and formula_54 in the MLP case. The scale parameters formula_51, formula_52 and formula_53 determine the scaling of the inputs in the polynomial, RBF and MLP kernel function. This scaling is related to the bandwidth of the kernel in statistics, where it is shown that the bandwidth is an important parameter of the generalization behavior of a kernel method.
Bayesian interpretation for LS-SVM.
A Bayesian interpretation of the SVM has been proposed by Smola et al. They showed that the use of different kernels in SVM can be regarded as defining different prior probability distributions on the functional space, as formula_62. Here formula_63 is a constant and formula_64 is the regularization operator corresponding to the selected kernel.
A general Bayesian evidence framework was developed by MacKay, and MacKay has used it to the problem of regression, forward neural network and classification network. Provided data set formula_65, a model formula_66 with parameter vector formula_14 and a so-called hyperparameter or regularization parameter formula_68, Bayesian inference is constructed with 3 levels of inference:
We can see that Bayesian evidence framework is a unified theory for learning the model and model selection.
Kwok used the Bayesian evidence framework to interpret the formulation of SVM and model selection. And he also applied Bayesian evidence framework to support vector regression.
Now, given the data points formula_75 and the hyperparameters formula_26 and formula_27 of the model formula_66, the model parameters formula_14 and formula_80 are estimated by maximizing the posterior formula_81. Applying Bayes’ rule, we obtain
where formula_83 is a normalizing constant such the integral over all possible formula_14 and formula_80 is equal to 1.
We assume formula_14 and formula_80 are independent of the hyperparameter formula_27, and are conditional independent, i.e., we assume
When formula_90, the distribution of formula_80 will approximate a uniform distribution. Furthermore, we assume formula_14 and formula_80 are Gaussian distribution, so we obtain the a priori distribution of formula_14 and formula_80 with formula_90 to be
Here formula_98 is the dimensionality of the feature space, same as the dimensionality of formula_14.
The probability of formula_100 is assumed to depend only on formula_101 and formula_66. We assume that the data points are independently identically distributed (i.i.d.), so that:
In order to obtain the least square cost function, it is assumed that the probability of a data point is proportional to:
A Gaussian distribution is taken for the errors formula_105 as:
It is assumed that the formula_14 and formula_80 are determined in such a way that the class centers formula_109 and formula_110 are mapped onto the target -1 and +1, respectively. The projections formula_111 of the class elements formula_6 follow a multivariate Gaussian distribution, which have variance formula_113.
Combining the preceding expressions, and neglecting all constants, Bayes’ rule becomes
The maximum posterior density estimates formula_115 and formula_116 are then obtained by minimizing the negative logarithm of (26), so we arrive (10).