View source for Least-squares support vector machine

{{Technical|date=December 2021}}
'''Least-squares support-vector machines (LS-SVM)''' for [[statistics]] and in [[statistical model]]ing, are [[least-squares]] versions of [[support-vector machine]]s (SVM), which are a set of related [[supervised learning]] methods that analyze data and recognize patterns, and which are used for [[statistical classification|classification]] and [[regression analysis]].  In this version one finds the solution by solving a set of [[linear equation]]s instead of a convex [[quadratic programming]] (QP) problem for classical SVMs. Least-squares SVM classifiers were proposed by [[Johan Suykens]] and Joos Vandewalle.<ref>Suykens, J. A. K.; Vandewalle, J. (1999) "Least squares support vector machine classifiers", ''Neural Processing Letters'', 9 (3), 293–300.</ref> LS-SVMs are a class of [[Kernel methods|kernel-based learning methods]].
==From support-vector machine to least-squares support-vector machine==
Given a training set <math> \{ x_i ,y_i \}_{i = 1}^N</math> with input data <math> x_i \in \mathbb{R}^n</math> and corresponding binary class labels <math>y_i \in \{ -1, +1 \}</math>, the [[Support-vector machine|SVM]]<ref>Vapnik, V. The nature of statistical learning theory. Springer-Verlag, New York, 1995.</ref> classifier, according to [[Vapnik]]'s original formulation, satisfies the following conditions:
[[File:Data spiral.png|thumb|right|250px|The spiral data: <math>y_i = 1</math> for blue data point, <math>y_i = -1</math> for red data point]]
: <math>
\begin{cases}
w^T \phi (x_i ) + b \ge 1, & \text{if } \quad y_i  =  +1, \\
w^T \phi (x_i ) + b \le  - 1, & \text{if } \quad y_i  =  -1,
\end{cases}</math>
which is equivalent to
: <math>y_i \left[ {w^T \phi (x_i ) + b} \right] \ge 1,\quad i = 1, \ldots, N,</math>
where <math>\phi(x)</math> 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 <math>\xi_i</math> such that
: <math> \begin{cases}
y_i \left[ {w^T \phi (x_i ) + b} \right] \ge 1 - \xi _i , & i = 1, \ldots, N, \\
\xi _i  \ge 0, & i = 1, \ldots, N.
\end{cases}</math>
[[File:Data spiral svm.png|thumb|right|250px|The result of the SVM classifier]]
According to the [[structural risk minimization]] principle, the risk bound is minimized by the following minimization problem:
: <math>\min J_1 (w,\xi )=\frac{1}{2}w^T w + c\sum\limits_{i = 1}^N \xi_i ,</math>
: <math>\text{Subject to } \begin{cases}
y_i \left[ {w^T \phi (x_i ) + b} \right] \ge 1 - \xi _i , & i = 1, \ldots, N, \\
\xi _i  \ge 0, & i = 1, \ldots ,N ,
\end{cases}</math>
To solve this problem, we could construct the [[Lagrange multipliers|Lagrangian function]]:
:<math> L_1(w,b,\xi,\alpha,\beta)=\frac{1}{2}w^T w + c\sum\limits_{i = 1}^N {\xi _i } - \sum\limits_{i=1}^N \alpha_i \left\{ y_i \left[ {w^T \phi (x_i ) + b} \right] - 1 + \xi _i \right\} - \sum\limits_{i=1}^N \beta_i \xi_i, </math>
where <math>\alpha_i \ge 0,\ \beta _i \ge 0\ (i = 1, \ldots, N)</math> are the [[Lagrangian multipliers]]. The optimal point will be in the [[saddle point]] of the Lagrangian function, and then we obtain
{{NumBlk|::|<math> \begin{cases}
\frac{ \partial L_1 }{\partial w} = 0\quad  \to \quad w = \sum\limits_{i = 1}^N \alpha _i y_i \phi (x_i )  ,\\
\frac{\partial L_1 }{\partial b} = 0\quad  \to \quad \sum\limits_{i = 1}^N \alpha _i y_i = 0 ,\\
\frac{\partial L_1 }{\partial \xi _i } = 0\quad  \to \quad \alpha _i +\beta_i = c,\;i = 1, \ldots ,N \quad  \to \quad 0 \le \alpha _i \le c,\;i = 1, \ldots ,N.
\end{cases} </math>|{{EquationRef|1}}}}
By substituting <math>w</math> by its expression in the Lagrangian formed from the appropriate objective and constraints, we will get the following quadratic programming problem:
: <math> \max Q_1(\alpha) = -\frac{1}{2}\sum\limits_{i,j = 1}^N {\alpha _i \alpha _j y_i y_j K(x_i ,x_j )}  + \sum\limits_{i = 1}^N \alpha_i, </math>
where <math>K(x_i ,x_j ) = \left\langle \phi (x_i ), \phi (x_j) \right\rangle</math> is called the [[kernel function]]. Solving this QP problem subject to constraints in ({{EquationNote|1}}), we will get the [[hyperplane]] in the high-dimensional space and hence the [[Hierarchical classifier|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
: <math>\min J_2(w,b,e) = \frac{\mu}{2} w^T w + \frac{\zeta}{2}\sum\limits_{i = 1}^N e_i^2,</math>
subject to the equality constraints
: <math>y_i \left[ {w^T \phi (x_i ) + b} \right] = 1 - e_{i} ,\quad i = 1, \ldots ,N .</math>
The least-squares SVM (LS-SVM) classifier formulation above implicitly corresponds to a [[Regression analysis|regression]] interpretation with binary targets <math>y_i = \pm 1</math>.
Using <math>y_i^2 = 1</math>, we have
: <math>\sum\limits_{i = 1}^N e_i^2 = \sum\limits_{i = 1}^N (y_i e_i)^2 = \sum\limits_{i = 1}^N e_i^2 = \sum\limits_{i = 1}^N \left( y_i - (w^T \phi(x_i) + b) \right)^2,</math>
with <math> e_i = y_i - (w^T \phi(x_i) + b).</math> 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
: <math>J_2(w,b,e) = \mu E_W + \zeta E_D</math>
with <math>E_W = \frac{1}{2} w^T w</math> and <math>E_D = \frac{1}{2} \sum\limits_{i = 1}^N e_i^2 = \frac{1}{2} \sum\limits_{i = 1}^N \left(y_i - (w^T \phi(x_i) + b) \right)^2.</math>
[[File:Data spiral lssvm.png|thumb|right|250px|The result of the LS-SVM classifier]]
Both <math>\mu</math> and <math>\zeta</math> should be considered as hyperparameters to tune the amount of regularization versus the sum squared error. The solution does only depend on the ratio <math>\gamma = \zeta / \mu</math>, therefore the original formulation uses only <math>\gamma</math> as tuning parameter. We use both <math>\mu</math> and <math>\zeta</math> 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 [[Lagrange multipliers|Lagrangian function]]:
: <math>\begin{cases}
L_2 (w,b,e,\alpha )\; = J_2 (w,e) - \sum\limits_{i = 1}^N \alpha _i \left\{ { \left[ {w^T \phi (x_i ) + b} \right] + e_i - y_i } \right\}  ,\\
\quad \quad \quad \quad \quad \; = \frac{1}{2}w^T w + \frac{\gamma }{2} \sum\limits_{i = 1}^N e_i^2 - \sum\limits_{i = 1}^N \alpha _i \left\{ \left[ w^T \phi (x_i ) + b \right] + e_i -y_i \right\} ,
\end{cases}</math>
where <math>\alpha_i \in \mathbb{R}</math> are the Lagrange multipliers. The conditions for optimality are
: <math> \begin{cases}
\frac{\partial L_2 }{\partial w} = 0\quad  \to \quad w = \sum\limits_{i = 1}^N \alpha _i \phi (x_i ) , \\
\frac{\partial L_2 }{\partial b} = 0\quad  \to \quad \sum\limits_{i = 1}^N \alpha _i   = 0 ,\\
\frac{\partial L_2 }{\partial e_i } = 0\quad  \to \quad \alpha _i  =  \gamma e_i ,\;i = 1, \ldots ,N ,\\
\frac{\partial L_2 }{\partial \alpha _i } = 0\quad  \to \quad y_i  = w^T \phi (x_i ) + b + e_i ,\,i = 1, \ldots ,N .
\end{cases} </math>
Elimination of <math>w</math> and <math>e</math> will yield a [[linear system]] instead of a [[quadratic programming]] problem:
: <math> \left[ \begin{matrix}
0 & 1_N^T  \\
1_N & \Omega  + \gamma ^{ - 1} I_N
\end{matrix} \right] \left[ \begin{matrix}
b  \\
\alpha
\end{matrix} \right] = \left[ \begin{matrix}
0  \\
Y
\end{matrix} \right] ,</math>
with <math>Y = [y_1 , \ldots ,y_N ]^T</math>, <math>1_N  = [1, \ldots ,1]^T</math> and <math>\alpha  = [\alpha _1 , \ldots ,\alpha _N ]^T</math>. Here, <math>I_N</math> is an <math>N \times N</math> [[identity matrix]], and <math>\Omega  \in \mathbb{R}^{N \times N}</math> is the kernel matrix defined by <math>\Omega _{ij}  = \phi (x_i )^T \phi (x_j ) = K(x_i ,x_j )</math>.
===Kernel function ''K''===
For the kernel function ''K''(•, •) one typically has the following choices:
* [[Linear]] kernel : <math>K(x,x_i ) = x_i^T x,</math>
* [[Polynomial]] kernel of degree <math>d</math>: <math>K(x,x_i ) = \left( {1 + x_i^T x/c} \right)^d ,</math>
* [[Radial basis function]] RBF kernel : <math>K(x,x_i ) = \exp \left( { - \left\| {x - x_i } \right\|^2 /\sigma ^2 } \right),</math>
* MLP kernel : <math>K(x,x_i ) = \tanh \left( {k\,x_i^T x + \theta } \right),</math>
where <math>d</math>, <math>c</math>, <math>\sigma</math>, <math>k</math> and <math>\theta</math> are constants. Notice that the Mercer condition holds for all <math>c, \sigma \in \mathbb{R}^+</math> and <math>d \in N</math> values in the [[polynomial]] and RBF case, but not for all possible choices of <math>k</math> and <math>\theta</math> in the MLP case. The scale parameters <math>c</math>, <math>\sigma</math> and <math>k</math> 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 probability|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 <math>P[f] \propto \exp \left( { - \beta \left\| {\hat Pf} \right\|^2 } \right)</math>. Here <math>\beta>0</math> is a constant and <math>\hat{P}</math> is the regularization operator corresponding to the selected kernel.
A general Bayesian evidence framework was developed by MacKay,<ref>MacKay, D. J. C. Bayesian Interpolation. Neural Computation, 4(3): 415–447, May 1992.</ref><ref>MacKay, D. J. C. A practical Bayesian framework for backpropagation networks. Neural Computation, 4(3): 448–472, May 1992.</ref><ref>MacKay, D. J. C. The evidence framework applied to classification networks. Neural Computation, 4(5): 720–736, Sep. 1992.</ref> and MacKay has used it to the problem of regression, forward [[neural network]] and classification network. Provided data set <math>D</math>, a model <math>\mathbb{M}</math> with parameter vector <math>w</math> and a so-called hyperparameter or regularization parameter <math>\lambda</math>, [[Bayesian inference]] is constructed with 3 levels of inference:
* In level 1, for a given value of <math>\lambda</math>, the first level of inference infers the posterior distribution of <math>w</math> by Bayesian rule
::<math>p(w|D,\lambda ,\mathbb{M}) \propto p(D|w,\mathbb{M})p(w|\lambda ,\mathbb{M}).</math>
* The second level of inference determines the value of <math>\lambda</math>, by maximizing
::<math>p(\lambda |D,\mathbb{M}) \propto p(D|\lambda ,\mathbb{M})p(\lambda |\mathbb{M}).</math>
* The third level of inference in the evidence framework ranks different models by examining their posterior probabilities
::<math>p(\mathbb{M}|D) \propto p(D|\mathbb{M})p(\mathbb{M}).</math>
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 <math> \{ x_i ,y_i \} _{i = 1}^N</math> and the hyperparameters <math>\mu</math> and <math>\zeta</math> of the model <math>\mathbb{M}</math>, the model parameters <math>w</math> and <math>b</math> are estimated by maximizing the posterior <math>p(w,b|D,\log \mu ,\log \zeta ,\mathbb{M})</math>. Applying Bayes’ rule, we obtain
:<math>p(w,b|D,\log \mu ,\log \zeta ,\mathbb{M}) = \frac{{p(D|w,b,\log \mu ,\log \zeta ,\mathbb{M})p(w,b|\log \mu ,\log \zeta ,\mathbb{M})}}{{p(D|\log \mu ,\log \zeta ,\mathbb{M})}},
</math>
where <math>p(D|\log \mu ,\log \zeta ,\mathbb{M})</math> is a normalizing constant such the integral over all possible <math>w</math> and <math>b</math> is equal to 1.
We assume <math>w</math> and <math>b</math> are independent of the hyperparameter <math>\zeta</math>, and are conditional independent, i.e., we assume
:<math>p(w,b|\log \mu ,\log \zeta ,\mathbb{M}) = p(w|\log \mu ,\mathbb{M})p(b|\log \sigma _b ,\mathbb{M}).
</math>
When <math>\sigma _b  \to \infty</math>, the distribution of <math>b</math> will approximate a uniform distribution. Furthermore, we assume <math>w</math> and <math>b</math> are Gaussian distribution, so we obtain the a priori distribution of <math>w</math> and <math>b</math> with <math>\sigma _b  \to \infty</math> to be
: <math>\begin{array}{l}
p(w,b|\log \mu ,) = \left( {\frac{\mu }{{2\pi }}} \right)^{\frac{{n_f }}{2}} \exp \left( { - \frac{\mu }{2}w^T w} \right)\frac{1}{{\sqrt {2\pi \sigma _b } }}\exp \left( { - \frac{{b^2 }}{{2\sigma _b }}} \right) \\
\quad \quad \quad \quad \quad \quad \quad  \propto \left( {\frac{\mu }{{2\pi }}} \right)^{\frac{{n_f }}{2}} \exp \left( { - \frac{\mu }{2}w^T w} \right)
\end{array} .</math>
Here <math>n_f</math> is the dimensionality of the feature space, same as the dimensionality of <math>w</math>.
The probability of <math>p(D|w,b,\log \mu ,\log \zeta ,\mathbb{M})</math> is assumed to depend only on <math>w,b,\zeta</math> and <math>\mathbb{M}</math>. We assume that the data points are independently identically distributed (i.i.d.), so that:
: <math>p(D|w,b,\log \zeta ,\mathbb{M}) = \prod\limits_{i = 1}^N {p(x_i ,y_i |w,b,\log \zeta ,\mathbb{M})} .</math>
In order to obtain the least square cost function, it is assumed that the probability of a data point is proportional to:
: <math>p(x_i ,y_i |w,b,\log \zeta ,\mathbb{M}) \propto p(e_i |w,b,\log \zeta ,\mathbb{M}) .</math>
A Gaussian distribution is taken for the errors <math>e_i  = y_i  - (w^T \phi (x_i ) + b)</math> as:
: <math>p(e_i |w,b,\log \zeta ,\mathbb{M}) = \sqrt {\frac{\zeta }{{2\pi }}} \exp \left( { - \frac{{\zeta e_i^2 }}{2}} \right) .</math>
It is assumed that the <math>w</math> and <math>b</math> are determined in such a way that the class centers <math>\hat m_ - </math> and <math>\hat m_ +</math> are mapped onto the target -1 and +1, respectively. The projections <math>w^T \phi (x) + b</math> of the class elements <math>\phi(x)</math> follow a multivariate Gaussian distribution, which have variance <math>1/ \zeta</math>.
Combining the preceding expressions, and neglecting all constants, Bayes’ rule becomes
: <math>p(w,b|D,\log \mu ,\log \zeta ,\mathbb{M}) \propto \exp ( - \frac{\mu }{2}w^T w - \frac{\zeta }{2}\sum\limits_{i = 1}^N {e_i^2 } ) = \exp ( - J_2 (w,b)) .</math>
The maximum posterior density estimates <math>w_{MP}</math> and <math>b_{MP}</math> are then obtained by minimizing the negative logarithm of (26), so we arrive (10).
==References==
<references />
==Bibliography==
* J. A. K. Suykens, T. Van Gestel, J. De Brabanter, B. De Moor, J. Vandewalle, Least Squares Support Vector Machines, World Scientific Pub. Co., Singapore, 2002. {{ISBN|981-238-151-1}}
* Suykens J. A. K., Vandewalle J., Least squares support vector machine classifiers, ''Neural Processing Letters'', vol. 9, no. 3, Jun. 1999, pp.&nbsp;293–300.
* Vladimir Vapnik. ''The Nature of Statistical Learning Theory''. Springer-Verlag, 1995. {{ISBN|0-387-98780-0}}
* MacKay, D. J. C., Probable networks and plausible predictions—A review of practical Bayesian methods for supervised neural networks. ''Network: Computation in Neural Systems'', vol. 6, 1995, pp.&nbsp;469–505.
==External links==
* [https://web.archive.org/web/20150513103825/http://www.esat.kuleuven.be/sista/lssvmlab/ www.esat.kuleuven.be/sista/lssvmlab/] "Least squares support vector machine Lab (LS-SVMlab) toolbox contains Matlab/C implementations for a number of LS-SVM algorithms".
* [http://www.kernel-machines.org www.kernel-machines.org] "Support Vector Machines and Kernel based methods (Smola & Schölkopf)".
* [http://www.gaussianprocess.org/ www.gaussianprocess.org] "Gaussian Processes: Data modeling using Gaussian Process priors over functions for regression and classification (MacKay, Williams)".
* [https://web.archive.org/web/20180627015707/https://www.support-vector.net/ www.support-vector.net] "Support Vector Machines and kernel based methods (Cristianini)".
* [http://dlib.net/ml.html#krr_trainer dlib]: Contains a least-squares SVM implementation for large-scale datasets.
[[Category:Support vector machines]]
[[Category:Classification algorithms]]
[[Category:Statistical classification]]
[[Category:Least squares]]