Least-squares support vector machine

Least-squares support-vector machines (LS-SVM) for statistics and in statistical modeling, 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 Johan Suykens and Joos 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

{

x

i

,

y

i

}

i

=

1

N

{\displaystyle \{x_{i},y_{i}\}_{i=1}^{N}}

with input data

x

i

∈

R

n

{\displaystyle x_{i}\in \mathbb {R} ^{n}}

and corresponding binary class labels

y

i

∈

{

−

1

,

+

1

}

{\displaystyle y_{i}\in \{-1,+1\}}

, the SVM classifier, according to Vapnik's original formulation, satisfies the following conditions:

{

w

T

ϕ

(

x

i

)

+

b

≥

1

,

if

y

i

=

+

1

,

w

T

ϕ

(

x

i

)

+

b

≤

−

1

,

if

y

i

=

−

1

,

{\displaystyle {\begin{cases}w^{T}\phi (x_{i})+b\geq 1,&{\text{if }}\quad y_{i}=+1,\\w^{T}\phi (x_{i})+b\leq -1,&{\text{if }}\quad y_{i}=-1,\end{cases}}}

which is equivalent to

y

i

[

w

T

ϕ

(

x

i

)

+

b

]

≥

1

,

i

=

1

,

…

,

N

,

{\displaystyle y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1,\quad i=1,\ldots ,N,}

where

ϕ

(

x

)

{\displaystyle \phi (x)}

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

ξ

i

{\displaystyle \xi _{i}}

such that

{

y

i

[

w

T

ϕ

(

x

i

)

+

b

]

≥

1

−

ξ

i

,

i

=

1

,

…

,

N

,

ξ

i

≥

0

,

i

=

1

,

…

,

N

.

{\displaystyle {\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N.\end{cases}}}

According to the structural risk minimization principle, the risk bound is minimized by the following minimization problem:

min

J

1

(

w

,

ξ

)

=

1

2

w

T

w

+

c

∑

i

=

1

N

ξ

i

,

{\displaystyle \min J_{1}(w,\xi )={\frac {1}{2}}w^{T}w+c\sum \limits _{i=1}^{N}\xi _{i},}

Subject to

{

y

i

[

w

T

ϕ

(

x

i

)

+

b

]

≥

1

−

ξ

i

,

i

=

1

,

…

,

N

,

ξ

i

≥

0

,

i

=

1

,

…

,

N

,

{\displaystyle {\text{Subject to }}{\begin{cases}y_{i}\left[{w^{T}\phi (x_{i})+b}\right]\geq 1-\xi _{i},&i=1,\ldots ,N,\\\xi _{i}\geq 0,&i=1,\ldots ,N,\end{cases}}}

To solve this problem, we could construct the Lagrangian function:

L

1

(

w

,

b

,

ξ

,

α

,

β

)

=

1

2

w

T

w

+

c

∑

i

=

1

N

ξ

i

−

∑

i

=

1

N

α

i

{

y

i

[

w

T

ϕ

(

x

i

)

+

b

]

−

1

+

ξ

i

}

−

∑

i

=

1

N

β

i

ξ

i

,

{\displaystyle 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},}

where

α

i

≥

0

,

β

i

≥

0

(

i

=

1

,

…

,

N

)

{\displaystyle \alpha _{i}\geq 0,\ \beta _{i}\geq 0\ (i=1,\ldots ,N)}

are the Lagrangian multipliers. The optimal point will be in the saddle point of the Lagrangian function, and then we obtain

By substituting

w

{\displaystyle w}

by its expression in the Lagrangian formed from the appropriate objective and constraints, we will get the following quadratic programming problem:

max

Q

1

(

α

)

=

−

1

2

∑

i

,

j

=

1

N

α

i

α

j

y

i

y

j

K

(

x

i

,

x

j

)

+

∑

i

=

1

N

α

i

,

{\displaystyle \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},}

where

K

(

x

i

,

x

j

)

=

⟨

ϕ

(

x

i

)

,

ϕ

(

x

j

)

⟩

{\displaystyle K(x_{i},x_{j})=\left\langle \phi (x_{i}),\phi (x_{j})\right\rangle }

is called the kernel function. Solving this QP problem subject to constraints in (1), 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

min

J

2

(

w

,

b

,

e

)

=

μ

2

w

T

w

+

ζ

2

∑

i

=

1

N

e

i

2

,

{\displaystyle \min J_{2}(w,b,e)={\frac {\mu }{2}}w^{T}w+{\frac {\zeta }{2}}\sum \limits _{i=1}^{N}e_{i}^{2},}

subject to the equality constraints

y

i

[

w

T

ϕ

(

x

i

)

+

b

]

=

1

−

e

i

,

i

=

1

,

…

,

N

.