# A Novel Sparse Least Squares Support Vector Machines

Authors: Xiao-Lei Xia; Weidong Jiao; Kang Li; George Irwin
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The solution of a Least Squares Support Vector Machine (LS-SVM) suffers from the problem of nonsparseness. The Forward Least Squares Approximation (FLSA) is a greedy approximation algorithm with a least-squares loss function. This paper proposes a new Support Vector Machine for which the FLSA is the training algorithm—the Forward Least Squares Approximation SVM (FLSA-SVM). A major novelty of this new FLSA-SVM is that the number of support vectors is the regularization parameter for tuning the tradeoff between the generalization ability and the training cost. The FLSA-SVMs can also detect the linear dependencies in vectors of the input Gramian matrix. These attributes together contribute to its extreme sparseness. Experiments on benchmark datasets are presented which show that, compared to various SVM algorithms, the FLSA-SVM is extremely compact, while maintaining a competitive generalization ability.


---

## Body

## 1. Introduction

The last decade has seen widespread applications of Least Squares Support Vector Machines (LS-SVM) [1, 2] to a variety of classification problems. The LS-SVM involves finding a separating hyperplane of maximal margin and minimizing the empirical risk via a Least Squares loss function. Here the optimization is subject to equality constraints, as opposed to the inequality ones used with a standard SVM [3, 4]. Thus the LS-SVM successfully sidesteps the quadratic programming (QP) required for the training of the standard SVM. As a result, an LS-SVM classifier is equivalent to a set of linear algebraic equations, which are usually solved by the conjugate gradient (CG) method [5]. Empirical studies suggest that an LS-SVM possesses very competitive generalization abilities compared to a regular SVM [6]; improvement has been made to Suyken’s algorithm by Chu et al. [7] whose proposal is also based on CG method but with a reduced time complexity. Meanwhile Keerthi et al. advocated training an LS-SVM using the sequential minimal optimization (SMO) algorithm [8].While these algorithms have indeed made an LS-SVM more computationally attractive, the nonsparseness of its solution still remains a major, and as yet unsolved, bottleneck. Sparseness in solutions is essential for reducing the time required in predicting the class membership of unlabelled data. The general approach to addressing this issue for an LS-SVM is iterative shrinking of the training set. Here the importance of training samples is evaluated from the weights assigned to them after training. Samples of less importance are removed, and then the remainder forms a reduced training set to be learnt again. In view of the linear relationship between the approximation error and the support value for a training sample, a straightforward pruning strategy is to remove samples whose absolute support values are trivial [9]. A later paper recommended pruning a sample which introduces the smallest error if omitted [10]. However, this necessitates the inversion of the kernel matrix, which is indicative of high computation complexity. Zeng and Chen [11] suggested a pruning method based on the SMO formulation of an LS-SVM, which leads to faster retraining. Other authors [12] proposed solving the dual form of an LS-SVM by iterative addition of basis functions from the kernel dictionary either until all the training samples are traversed or until the approximation error is lower than a preset threshold. Despite the lower computation cost with the backfitting scheme adopted, Lagrangian multipliers associated with previously selected training samples were inherited into the next pass, which could compromise the generalization abilities of the resultant LS-SVM.This paper presents a new LS-SVM formulation called the Forward Least Squares Approximation SVMs (FLSA-SVM). It is trained by Forward Least Squares Approximation(FLSA) [13], a function approximation method using a Least Squares loss function. The FLSA-SVM loss function decreases monotonically with an increasing number of support vectors, allowing for the removal of slack variables from the equality constraints. Another novelty with the FLSA-SVM lies in the fact that it cleverly transforms the number of support vectors to be the regularization parameter, which indicates the tradeoff between generalization abilities and empirical risk. The FLSA-SVM builds a classifier by iteratively selecting a single basis function for the solution, which contributes the largest reduction to the quadratic cost function.The paper is organized as follows. Section2 briefly reviews Least Squares SVM principles. The new sparse LS-SVM—Forward Least Squares Approximation SVM (FLSA-SVM)—is introduced in Section 3. Experimental results are given in Section 4 and concluding remarks in Section 5.


## 2. Least Squares Support Vector Machines

For a classification problem ofℓ pairs of training samples (x1,y1),…,(xℓ,yℓ), where x∈ℝN and y∈{-1,1}, LS-SVM algorithms seek the optimal separating hyperplane with the orientation vector of the least L2 norm.To ensure the presence of the optimal hyperplane, the input data are translated into a reproducing kernel hilbert space (RKHS) by a mapping function denoted byϕ(x). To avoid the curse of dimensionality, the mapping is implemented implicitly by the introduction of “kernel trick.” Its idea is that dot products in the RKHS space can be represented by a Mercer kernel function in input space [14]:
(1)K(x,x′)=Φ(x)⊤Φ(x′).
Thus the linear discriminant function in the feature space can be formulated as
(2)f(x)=w⊤ϕ(x)+b,
where w is the orientation vector and b is the bias term.An LS-SVM finds the hyperplane parameterized by(w,b) by solving the following optimization problem [15]:
(3)minw,b,e12w⊤w+12γ∑i=1ℓ‍ei2,s.t.w⊤ϕ(xi)+b=yi-ei,i=1,…,ℓ,
where the slack variable ei denotes the deviation between the actual output f(x) of the LS-SVM on sample xi and its target value yi. γ is a parameter which imposes penalty on deviations.Introducing the Lagrange multipliersαi  (i=1,…,l) for each of the equality constraints gives
(4)ℒ(w,b,e,α)=12w⊤w+12γ∑i=1ℓ‍ei2-∑i=1ℓ‍αi[w⊤ϕ(xi)+b-yi+ei].Due to the equality constraints,αi can either be positive or negative according to the Karush-Kuhn-Tucker (KKT) conditions [16]:
(5)w=∑i=1ℓ‍αiϕ(xi),(6)∑i=1ℓ‍αi=0,(7)αi=γei,(8)w⊤ϕ(xi)+b=yi-ei.The linear equations can be further simplified to(9)[H+γ-1I1→1⊤→0][αb]=[y0],
where H∈ℝℓ×ℓ and Hij=K(xi,xj),  y=[y1,…,yℓ]⊤,  α=[α1,…,αℓ]⊤, I is unity matrix of rank n, and 1→ is a column vector of 1s of n length. The solution of an LS-SVM is a linear combination of basis function K(·,xi) whose associated αi is nonzero:
(10)f(x)=∑i‍αiK(x,xi)+b.It has been noted that the LS-SVM is almost equivalent to ridge regression [17] since the two methods corresponds to an identical optimization problem. Meanwhile, the equivalence between the LS-SVM and the Kernel Fisher Discriminant method [18] has also been established [19].


## 3. Least Squares Approximation Sparse SVM

Equation (3) shows that an LS-SVM can also be viewed as a ridge regression model. And the optimality conditions (7) indicate that the introduction of slack variable ei is the root of the nonsparseness problem, since in regression applications, most slack variables end as nonzero [20]. But the introduction of ei seems inevitable for the representation of training cost and thus the penalty parameter to indicate the tradeoff between training cost and generalization abilities.The section introduces a new formulation of Least Squares SVM, namely, Forward Least Squares Approximation SVM (FLSA-SVM). The proposed FLSA-SVM algorithm is motivated by the Least Squares “Forward Approximation & Backward Refinement” method for function approximation, which was first developed in the dynamic system identification community by Li et al.FLSA-SVM is rid of slack variables by employing an approximation function of Least Squares loss function which is Forward Least Squares Approximation (FLSA) algorithm. FLSA approximation function iteratively selects a basis function which causes the steepest reduction in the loss function. The features enable the number of support vectors (SVs), which equals to the number of basis functions, to be the tradeoff between training cost and generalization abilities. In FLSA-SVMs, the sparseness of its solution is ensured and confirmed by the experiments section in which FLSA-SVMs are more sparse than standard SVMs.In this section, a description of  “Forward Approximation” is given, from a machine learning perspective, as a preface to the introduction of LSA-SVM algorithm. The strategy to reduce the computation complexity of FLSA-SVMs is then presented.


### 3.1. Forward Least Squares Approximation [13]

Givenℓ values (y1,…,yℓ) of an unknown target function f in a Hilbert space at ℓ input data (x1,…,xl). A “dictionary” {φ1,…,φN} of N functions in the Hilbert space is also given in which φi  (i=1,…,N) is termed as a “basis function.” Forward Least Squares Approximation (FLSA) addresses the estimation of f with a linear combinations of m basis functions chosen from the dictionary:
(11)fm=∑i=1m‍θiϕi,
wheremis the number of basis functions which expand fm,{ϕ1,…,ϕm} is the set of selected basis functions, and(θ1,…,θm)∈ℝm is the associated weight vector,so that the squared norm of the residue vector, denoted byL, is minimized:
(12)L=(fm→-y)⊤(fm→-y),
where y=(y1,…,yℓ) and fm→=(fm(x1),…,fm(xℓ))⊤ is the output vector of fm on the ℓ input data:
(13)fm→=∑i=1m‍θiϕi=ΩΘ,
where ϕi=(ϕi(x1),…,ϕi(xℓ))⊤ is the vector of decision values of basis function ϕi on the input data and Ω=[ϕ1,…,ϕm]∈ℝℓ×m. Equation (13) suggests that FLSA can be understood as working entirely in the ℝℓ space.The weight vectorΘ that minimizes the loss function (12) is given as
(14)Θ=(Ω⊤Ω)-1Ω⊤y
for a matrix Ω which is of full column rank [21]. The resultant minimal loss function is
(15)L(Θ)=y⊤y-Θ⊤Ω⊤y=y⊤(I-Ω(Ω⊤Ω)-1Ω⊤)y).
Starting from (15), FLSA defines a set of residue matrices Ri∈ℝℓ×ℓ  (i=1,…,m) for the measurement of the contribution of each basis function to the reduction of loss function:
(16)Ri=I-Ωi(Ωi⊤Ωi)-1Ωi⊤,
where matrix Ωi=(ϕ1,…,ϕi) is full column rank and is composed of output vectors of i basis function. I is the unity matrix and set R0=I. Then, the following equation holds:
(17)(1)Riϕj=01≤j≤i,(18)(2)Ri⊤=Ri,Ri2=Ri.For aφi=(φi(x1),…,φi(xℓ))⊤  (1≤k≤N) which produces a full column rank (Ωi,φk), it is proved that Ri+1 has the following properties:
(19)(3)Ri+1=Ri-Riφkφk⊤Ri⊤φk⊤Riφk,(20)(4)RiRi+1=Ri+1Ri=Ri+1.Meanwhile, the introduction ofRi simplifies the formulation of Li which is the evaluation of loss function L at Ωi:
(21)Li=y⊤Riy.
And thus
(22)Li+1=y⊤Ri+1y=Li-y⊤Riφkφk⊤Ri⊤yφk⊤Riφk.The contribution, denoted byδLk, of a column vector φk makes the loss function Li can able to be explicitly expressed:
(23)δLk=y⊤Riφkφk⊤Ri⊤yφk⊤Riφk=[(Riφk)⊤(Riy)]2(Riφk)⊤(Riφk).FLSA algorithm proceeds in a greedy manner which selects one basis function per iteration. Theith iteration identifies the index of the ith basis function ϕi by solving the optimization problem:
(24)argmaxk=1,…,NδLk=[(φk(i-1))⊤y(i-1)]2(φk(i-1))⊤φk(i-1),
where φk(i-1)=Ri-1φk and y(i-1)=Ri-1y.Theith iteration of FLSA algorithm, in actual fact, establishes the following linear system whose solutions are the last m-i+1 elements of θ in (13):
(25)[ϕi(i-1)ϕi+1(i-1)⋯ϕm(i-1)][θiθi+1⋮θm]=y(i-1).Thus[ϕi(i-1)φj(i-1),ϕi(i-1)y(i-1)]  (φj∉{ϕ1,…,ϕi}) which represents a linear equation is stored for the ith iteration. Eventually, m iterations build up an upper triangle which represents a linear system of (26). The solution Θ can be computed by performing a back substitution procedure that is used by a typical Gaussian elimination process:
(26)[ϕ1⊤ϕ1ϕ1⊤ϕ2…ϕ1⊤ϕm0(ϕ2(1))⊤ϕ2(1)…(ϕ2(1))⊤ϕm(1)⋮⋮⋱⋮00…(ϕm(m-1))⊤ϕm(m-1)][θ1θ2⋮θm]=[ϕ1⊤y(ϕ2(1))⊤y(1)⋮(ϕm(m-1))⊤y(m-1)].The FLSA algorithm, in fact, is closely related to the Orthogonal Least Squares (OLS) method [22–24], which also allows for the explicit formulation of the contribution of a basis function made to the reduction of the squared error loss.


### 3.2. Forward Least Squares Approximation SVMs

As with standard SVMs, the formulation of LS-SVMs embodies the Structural Risk Minimization (SRM) principle which can be illustrated by Figure1, in which the dotted line represents the upper bound on the complexity term of function set from which solution is chosen and the dash line the empirical risk. SRM minimizes the upper bound on the expected risk (generalization error), for which the best tradeoff between the complexity term and the empirical risk is required to be found.Figure 1
Structural risk minimization (SRM) principle.To this end, a regularization term is introduced to indicate the tradeoff between the complexity term and the empirical risk, both of which LS-SVMs explicitly formulate. Model selection is performed in the domain ofℝ>0 in search for its optimal value.While in FLSA algorithm, it can be concluded from (22) that the training cost L monotonously decreases to the increase in the number of selected basis functions m. The training cost L can be then plotted against m into a curve similar to that of the empirical risk in Figure 1.This fact motivates the following two innovations to traditional formulation of LS-SVMs:(1) the employment of the parameter m as the regularization term; (2) the avoidance of the term to represent empirical risk by using the FLSA as the training algorithm, which minimizes the summed squared residues for any value of m. As a result, a new formulation of LS-SVMs—namely, Forward Least Squares Approximation Sparse SVM (FLSA-SVM), which is restricted to be trained by FLSA algorithm, is proposed:
(27)minw,b12(w⊤w+b2),(28)s.t.w⊤ϕ(xi)+b=yi,i=1,…,ℓ,(29)|Γ|=m,
where Γ=γ1,…,γm is composed of the indices of the support vectors and |Γ| is the cardinality of the set. The addition of term b2 to (27) is first introduced by [25].In an FLSA-SVM, the parameterm is interpreted as the number of nonzeros of Lagrangian multipliers, that is, the number of support vectors (SVs), which is seen more obviously in its Lagrangian by introducing the Lagrange multipliers αi  (i=1,…,ℓ) for each of the equality constraints giving
(30)ℒ(w,b,α)=12(w⊤w+b2)-∑i=1m‍αi[w⊤ϕ(xi)+b-yi]-β|Γ|.
The optimal point requires that
(31)w=∑i=1m‍αiϕ(xi),∑i=1m‍αi=b,w⊤ϕ(xi)+b=yi,|Γ|=m.The linear equations can be further simplified to(32)(K+1→)α=Dα=y,(33)|Γ|=m,
where K∈ℝℓ×ℓ and Kij=K(xi,xj),  y=[y1,…,yℓ]⊤,  α=[α1,…,αℓ]⊤, 1→ is a ℓ-by-ℓ matrix of 1s, and D∈ℝℓ×ℓ, where Dij=Kij+1.It is worth attention that, in this paper,D in (32) is also referred to as Dm as it has m support vectors. Thus, if all ℓ data samples are used as support vectors, then D becomes Dℓ.FLSA can be applied to train an FLSA-SVM using a kernel-based dictionaryDℓ={di=K(·,j)+1∣i=1,…,ℓ} of candidate basis functions. Since m is defined to be the number of SVs, it thus achieved a more direct control of the sparseness of its solution.


### 3.3. Automatic Detection of Linear Dependencies

Since the kernel matrixK in (32) is a semipositive definite, it is easy to prove the semipositive definiteness of the matrix D. Then it is likely the occurrence of linear dependencies among column vectors, each being evaluation of a basis function on the training data. Assume that columns (dγ1,dγ2,…,dγk) are selected iteratively and linearly independent, where γ1,…,k are their column indices in chronological sequence. Denote d to be any column which remains as available candidates in D and meanwhile can be expressed as a linear combination of (dγ1,dγ2,…,dγk). It is thus naturally desired to remove d as candidates in order to (1) ensure the sparseness of the solution; (2) avoid any undue computation concerning d
since(34)
d
=
α
1
d
γ
1
+
α
2
d
γ
2
+
⋯
+
α
k
d
γ
k
,
where α=[α1,…,αk]⊤≠0.With the introduction of the residue matrix at each iteration asRγi(i=1,…,k), the following property holds according to (18) and (20):
(35)Rγkd=α1Rγkdγ1+α2Rkdγ2+⋯+αkRγk-1dγk=α1Rγk(Rγ1dγ1)+α2Rγk(Rγ2dγ2)+⋯+0=0.
Thus updating the dictionary D by Rγk, the column vector(s) d becomes 0, that is, automatically pruned. Hence, at each iteration of the FLSA-SVM, any column vector(s) which can be represented by a linear combination of previously selected columns can be automatically pruned. This merit of the FLSA-SVM is one contributor to the sparseness of the resultant solution.Algorithm1 gives the pseudocode of the FLSA-SVM algorithm in detail.Algorithm 1:Forward Least Squares Approximation SVMs.
INPUT:
(i) The data set{(x1, y1),…, (xl, yl)}
(ii)m which is the number of support vectors desired in the expansion of the solution and
1≤m≤l
(iii) A dictionary ofl basis functions D0={d1,…,dl}
INITIALIZATION:
(i) Current residue vectory, current dictionary D which is initially a matrix of evaluations
ofl candidate basis functions on training data:
y⟵(y1⋮yl),D⟵(d1(x1)⋯dl(x1)⋮⋱⋮d1(xl)⋯dl(xl))
(ii) The matrixA and the vector b both starts as empty A is appended a row and b grows
by one extra element at each iteration, which in the end forms a linear system.
(iii) A variablen which is the count of candidate basis functions and a vector Γ={γ1,…,γl}
which contains the indices of basis functions. At the start,γi=i for 1≤i≤l and n=l.
FORi=1,…,m
k⟵arg maxk=i,…,n|D(·,γk)⊤y∥D(·,γk)∥|
(iv)γi is made a pointer to the current selected basis functions:
γk↔γi
bi⟵D(·,γi)⊤y∥D(·,γi)∥2
(v) The residue vector is reduced bybidγi as the target values for the next linear system of size l:
y⟵y-biD(·,γi)
(vi) Update the dictionary matrix and prune the candidate basis functions which can be
represented as a linear combinations of the previously selected ones:
FORj=i+1,…,n
βγj⟵D(·,γi)⊤D(·,γj)∥D(·,γi)∥2
D(·,γj)←D(·,γj)-βjD(·,γi)
IFD(·,γj)=0
γl↔γi
n←n-1
βγi←1
D(·,γj)←0
A←(β1,…,βlA)
b←(bib)⊤
(vii) If equationsi=n and m>n hold where i is the number of selected basis functions and
n the count of available candidates, it suggests that the initial value setting on m has
exceeded the rank ofD0. Terminate the loop and reset m:
m←n
BACK SUBSTITUTION:
(i)m basis functions are chosen whose indices {γ1,…,γm} are the first m elements of Γ. m1
columns of matrixA with the indices {γ1,…,γm} and b forms a linear system, on which
the process of back substitution is performed for the solution:
αm←bi
FORi=m-1,…,1
αi←bi-∑j=i+1mαjA(i,γj)
OUTPUT:
(i) The solution is defined byf(x)=∑i=1mαidγi(x)


### 3.4. Computation Complexity

As discussed in [26], for a single round of training, the computational complexity of FLSA-SVM is O(mℓ2) and space complexity for FLSA-SVM is O(ℓ2).


## 3.1. Forward Least Squares Approximation [13]

Givenℓ values (y1,…,yℓ) of an unknown target function f in a Hilbert space at ℓ input data (x1,…,xl). A “dictionary” {φ1,…,φN} of N functions in the Hilbert space is also given in which φi  (i=1,…,N) is termed as a “basis function.” Forward Least Squares Approximation (FLSA) addresses the estimation of f with a linear combinations of m basis functions chosen from the dictionary:
(11)fm=∑i=1m‍θiϕi,
wheremis the number of basis functions which expand fm,{ϕ1,…,ϕm} is the set of selected basis functions, and(θ1,…,θm)∈ℝm is the associated weight vector,so that the squared norm of the residue vector, denoted byL, is minimized:
(12)L=(fm→-y)⊤(fm→-y),
where y=(y1,…,yℓ) and fm→=(fm(x1),…,fm(xℓ))⊤ is the output vector of fm on the ℓ input data:
(13)fm→=∑i=1m‍θiϕi=ΩΘ,
where ϕi=(ϕi(x1),…,ϕi(xℓ))⊤ is the vector of decision values of basis function ϕi on the input data and Ω=[ϕ1,…,ϕm]∈ℝℓ×m. Equation (13) suggests that FLSA can be understood as working entirely in the ℝℓ space.The weight vectorΘ that minimizes the loss function (12) is given as
(14)Θ=(Ω⊤Ω)-1Ω⊤y
for a matrix Ω which is of full column rank [21]. The resultant minimal loss function is
(15)L(Θ)=y⊤y-Θ⊤Ω⊤y=y⊤(I-Ω(Ω⊤Ω)-1Ω⊤)y).
Starting from (15), FLSA defines a set of residue matrices Ri∈ℝℓ×ℓ  (i=1,…,m) for the measurement of the contribution of each basis function to the reduction of loss function:
(16)Ri=I-Ωi(Ωi⊤Ωi)-1Ωi⊤,
where matrix Ωi=(ϕ1,…,ϕi) is full column rank and is composed of output vectors of i basis function. I is the unity matrix and set R0=I. Then, the following equation holds:
(17)(1)Riϕj=01≤j≤i,(18)(2)Ri⊤=Ri,Ri2=Ri.For aφi=(φi(x1),…,φi(xℓ))⊤  (1≤k≤N) which produces a full column rank (Ωi,φk), it is proved that Ri+1 has the following properties:
(19)(3)Ri+1=Ri-Riφkφk⊤Ri⊤φk⊤Riφk,(20)(4)RiRi+1=Ri+1Ri=Ri+1.Meanwhile, the introduction ofRi simplifies the formulation of Li which is the evaluation of loss function L at Ωi:
(21)Li=y⊤Riy.
And thus
(22)Li+1=y⊤Ri+1y=Li-y⊤Riφkφk⊤Ri⊤yφk⊤Riφk.The contribution, denoted byδLk, of a column vector φk makes the loss function Li can able to be explicitly expressed:
(23)δLk=y⊤Riφkφk⊤Ri⊤yφk⊤Riφk=[(Riφk)⊤(Riy)]2(Riφk)⊤(Riφk).FLSA algorithm proceeds in a greedy manner which selects one basis function per iteration. Theith iteration identifies the index of the ith basis function ϕi by solving the optimization problem:
(24)argmaxk=1,…,NδLk=[(φk(i-1))⊤y(i-1)]2(φk(i-1))⊤φk(i-1),
where φk(i-1)=Ri-1φk and y(i-1)=Ri-1y.Theith iteration of FLSA algorithm, in actual fact, establishes the following linear system whose solutions are the last m-i+1 elements of θ in (13):
(25)[ϕi(i-1)ϕi+1(i-1)⋯ϕm(i-1)][θiθi+1⋮θm]=y(i-1).Thus[ϕi(i-1)φj(i-1),ϕi(i-1)y(i-1)]  (φj∉{ϕ1,…,ϕi}) which represents a linear equation is stored for the ith iteration. Eventually, m iterations build up an upper triangle which represents a linear system of (26). The solution Θ can be computed by performing a back substitution procedure that is used by a typical Gaussian elimination process:
(26)[ϕ1⊤ϕ1ϕ1⊤ϕ2…ϕ1⊤ϕm0(ϕ2(1))⊤ϕ2(1)…(ϕ2(1))⊤ϕm(1)⋮⋮⋱⋮00…(ϕm(m-1))⊤ϕm(m-1)][θ1θ2⋮θm]=[ϕ1⊤y(ϕ2(1))⊤y(1)⋮(ϕm(m-1))⊤y(m-1)].The FLSA algorithm, in fact, is closely related to the Orthogonal Least Squares (OLS) method [22–24], which also allows for the explicit formulation of the contribution of a basis function made to the reduction of the squared error loss.


## 3.2. Forward Least Squares Approximation SVMs

As with standard SVMs, the formulation of LS-SVMs embodies the Structural Risk Minimization (SRM) principle which can be illustrated by Figure1, in which the dotted line represents the upper bound on the complexity term of function set from which solution is chosen and the dash line the empirical risk. SRM minimizes the upper bound on the expected risk (generalization error), for which the best tradeoff between the complexity term and the empirical risk is required to be found.Figure 1
Structural risk minimization (SRM) principle.To this end, a regularization term is introduced to indicate the tradeoff between the complexity term and the empirical risk, both of which LS-SVMs explicitly formulate. Model selection is performed in the domain ofℝ>0 in search for its optimal value.While in FLSA algorithm, it can be concluded from (22) that the training cost L monotonously decreases to the increase in the number of selected basis functions m. The training cost L can be then plotted against m into a curve similar to that of the empirical risk in Figure 1.This fact motivates the following two innovations to traditional formulation of LS-SVMs:(1) the employment of the parameter m as the regularization term; (2) the avoidance of the term to represent empirical risk by using the FLSA as the training algorithm, which minimizes the summed squared residues for any value of m. As a result, a new formulation of LS-SVMs—namely, Forward Least Squares Approximation Sparse SVM (FLSA-SVM), which is restricted to be trained by FLSA algorithm, is proposed:
(27)minw,b12(w⊤w+b2),(28)s.t.w⊤ϕ(xi)+b=yi,i=1,…,ℓ,(29)|Γ|=m,
where Γ=γ1,…,γm is composed of the indices of the support vectors and |Γ| is the cardinality of the set. The addition of term b2 to (27) is first introduced by [25].In an FLSA-SVM, the parameterm is interpreted as the number of nonzeros of Lagrangian multipliers, that is, the number of support vectors (SVs), which is seen more obviously in its Lagrangian by introducing the Lagrange multipliers αi  (i=1,…,ℓ) for each of the equality constraints giving
(30)ℒ(w,b,α)=12(w⊤w+b2)-∑i=1m‍αi[w⊤ϕ(xi)+b-yi]-β|Γ|.
The optimal point requires that
(31)w=∑i=1m‍αiϕ(xi),∑i=1m‍αi=b,w⊤ϕ(xi)+b=yi,|Γ|=m.The linear equations can be further simplified to(32)(K+1→)α=Dα=y,(33)|Γ|=m,
where K∈ℝℓ×ℓ and Kij=K(xi,xj),  y=[y1,…,yℓ]⊤,  α=[α1,…,αℓ]⊤, 1→ is a ℓ-by-ℓ matrix of 1s, and D∈ℝℓ×ℓ, where Dij=Kij+1.It is worth attention that, in this paper,D in (32) is also referred to as Dm as it has m support vectors. Thus, if all ℓ data samples are used as support vectors, then D becomes Dℓ.FLSA can be applied to train an FLSA-SVM using a kernel-based dictionaryDℓ={di=K(·,j)+1∣i=1,…,ℓ} of candidate basis functions. Since m is defined to be the number of SVs, it thus achieved a more direct control of the sparseness of its solution.


## 3.3. Automatic Detection of Linear Dependencies

Since the kernel matrixK in (32) is a semipositive definite, it is easy to prove the semipositive definiteness of the matrix D. Then it is likely the occurrence of linear dependencies among column vectors, each being evaluation of a basis function on the training data. Assume that columns (dγ1,dγ2,…,dγk) are selected iteratively and linearly independent, where γ1,…,k are their column indices in chronological sequence. Denote d to be any column which remains as available candidates in D and meanwhile can be expressed as a linear combination of (dγ1,dγ2,…,dγk). It is thus naturally desired to remove d as candidates in order to (1) ensure the sparseness of the solution; (2) avoid any undue computation concerning d
since(34)
d
=
α
1
d
γ
1
+
α
2
d
γ
2
+
⋯
+
α
k
d
γ
k
,
where α=[α1,…,αk]⊤≠0.With the introduction of the residue matrix at each iteration asRγi(i=1,…,k), the following property holds according to (18) and (20):
(35)Rγkd=α1Rγkdγ1+α2Rkdγ2+⋯+αkRγk-1dγk=α1Rγk(Rγ1dγ1)+α2Rγk(Rγ2dγ2)+⋯+0=0.
Thus updating the dictionary D by Rγk, the column vector(s) d becomes 0, that is, automatically pruned. Hence, at each iteration of the FLSA-SVM, any column vector(s) which can be represented by a linear combination of previously selected columns can be automatically pruned. This merit of the FLSA-SVM is one contributor to the sparseness of the resultant solution.Algorithm1 gives the pseudocode of the FLSA-SVM algorithm in detail.Algorithm 1:Forward Least Squares Approximation SVMs.
INPUT:
(i) The data set{(x1, y1),…, (xl, yl)}
(ii)m which is the number of support vectors desired in the expansion of the solution and
1≤m≤l
(iii) A dictionary ofl basis functions D0={d1,…,dl}
INITIALIZATION:
(i) Current residue vectory, current dictionary D which is initially a matrix of evaluations
ofl candidate basis functions on training data:
y⟵(y1⋮yl),D⟵(d1(x1)⋯dl(x1)⋮⋱⋮d1(xl)⋯dl(xl))
(ii) The matrixA and the vector b both starts as empty A is appended a row and b grows
by one extra element at each iteration, which in the end forms a linear system.
(iii) A variablen which is the count of candidate basis functions and a vector Γ={γ1,…,γl}
which contains the indices of basis functions. At the start,γi=i for 1≤i≤l and n=l.
FORi=1,…,m
k⟵arg maxk=i,…,n|D(·,γk)⊤y∥D(·,γk)∥|
(iv)γi is made a pointer to the current selected basis functions:
γk↔γi
bi⟵D(·,γi)⊤y∥D(·,γi)∥2
(v) The residue vector is reduced bybidγi as the target values for the next linear system of size l:
y⟵y-biD(·,γi)
(vi) Update the dictionary matrix and prune the candidate basis functions which can be
represented as a linear combinations of the previously selected ones:
FORj=i+1,…,n
βγj⟵D(·,γi)⊤D(·,γj)∥D(·,γi)∥2
D(·,γj)←D(·,γj)-βjD(·,γi)
IFD(·,γj)=0
γl↔γi
n←n-1
βγi←1
D(·,γj)←0
A←(β1,…,βlA)
b←(bib)⊤
(vii) If equationsi=n and m>n hold where i is the number of selected basis functions and
n the count of available candidates, it suggests that the initial value setting on m has
exceeded the rank ofD0. Terminate the loop and reset m:
m←n
BACK SUBSTITUTION:
(i)m basis functions are chosen whose indices {γ1,…,γm} are the first m elements of Γ. m1
columns of matrixA with the indices {γ1,…,γm} and b forms a linear system, on which
the process of back substitution is performed for the solution:
αm←bi
FORi=m-1,…,1
αi←bi-∑j=i+1mαjA(i,γj)
OUTPUT:
(i) The solution is defined byf(x)=∑i=1mαidγi(x)


## 3.4. Computation Complexity

As discussed in [26], for a single round of training, the computational complexity of FLSA-SVM is O(mℓ2) and space complexity for FLSA-SVM is O(ℓ2).


## 4. Experimental Results

A set of experiments were performed to evaluate the performance of the proposed FLSA-SVM algorithm. The FLSA-SVMs were first applied to the two-spiral benchmark [27] for an illustrative view of their generalization abilities. The following Gaussian kernel function was used for the experiments in this paper:
(36)K(Xi,Xj)=e-λ∥Xi-Xj∥2.
The standard SVMs were implemented by LIBSVM [28]. The LS-SVM trained by CG method was implemented by the toolbox of LS-SVMlab [29] and all experiments were run on a Pentium 4 3.2 GHz processor under Windows XP with 2 GB of RAM.


### 4.1. Experiments on Two-Spiral Dataset

The 2D “two-spiral” benchmark is known to be difficult for pattern recognition algorithms and poses great challenges to neural networks [30]. The training set consists of 194 points of the X-Y plane, half of which has a target value of +1 output and half a target value of −1. These training points describe two intertwining spirals that go around the origin three times, as shown in Figure 2, where the two categories are marked, respectively, by “+” and “o.”Figure 2
Two-spiral dataset.For the FLSA-SVM, the parameter setting of Gaussian kernel wasλ=1 as in (36). With a feasible range of [85,193], the optimal regularization parameter was found to be 134 which gave a leave-one-out cross-validation (LOOCV) accuracy of 97.94%. With standard SVMs, the parameter setting was C=32 and λ=0.5, whose LOOCV accuracy is 98.97%. The SVM classifier was required in 164 support vectors (SVs). The graphical outputs of the FLSA-SVM and the SVM were given by Figure 3. It showed that generally both SVM and FLSA-SVM algorithms recognized the pattern successfully, outputting “two-spiral” in a very smooth and regular manner. But at the area around the coordinate of [0,0], the FLSA-SVM showed better performance than the conventional SVM whose decision hyperplane was biased towards the “o” class.Comparison between standard SVMs and FLSA-SVMs: (a) two-spiral pattern recognized by the FLSA-SVM trained on 134 data points withλ=1 in (36); (b) two-spiral pattern recognized by the standard SVM trained on 164 data points. The penalty constant C=32 and σ=0.5.
(a)
(b)Despite the reduction in the number of SVs which is very notable for such a “hard” classification problem, the FLSA-SVMs are comparatively superior to the following two aspects. In SVMs, it often occurred that given a fixed kernel parameter, the optimal CV accuracy can be obtained from multiple value settings on the regularization parameter. The “two-spiral” problem is a case in point. For the best LOOCV accuracy, with a fixedλ=0.5, the value of C can also opt for (26,27,28,29,210) beyond 25. There is no specific rule as to which option is the best, and normally the smallest is chosen for a scaled-down feasible region. While in FLSA-SVMs, the setting for the value of the regularization term m is more tractable since different options correspond to different learning errors which can be easily tracked with (23). For multiple values of m which produce the same optimal CV accuracy, the largest m is chosen for a smaller learning error.In fact, form∈[160,193], the LOOCV accuracy remained stable at 96.91%. Thus an FLSA-SVM was also trained with the parameter settings of m=193 which was depicted in Figure 4(a). For comparisons, an LS-SVM was trained whose parameter settings are γ=173.7427 and λ=5.4899 for Gaussian RBF. The solution was parameterized by the entire 194 points and illustrated in Figure 4(b). The decision boundaries of both of the LS-SVM and the FLSA-SVM were generally smooth and followed the pattern satisfactorily, despite the slightly biased segments around the coordinates of [1.5,1.5] and [-1.5,-1.5]. But still the FLSA-SVM performed much better at the origin area than the LS-SVM.Comparison between LS-SVMs and FLSA-SVMs: (a) two-spiral pattern recognized by the conventional LS-SVM trained on 194 data points with the penalty parameterγ=173.7427 and λ=5.4899 for Gaussian RBF; (b) two-spiral pattern recognized by the FLSA-SVM trained on 180 data points with λ=1 in (36).
(a)
(b)Table1 also compares the time cost of 10-fold cross-validation (CV) on the regularization parameter by FLSA-SVMs, SVMs and LS-SVMs. For FLSA-SVMs, the regularization term m was assigned 21 integers evenly with an interval of 10 within the range of (1,194). For SVMs and LS-SVMs, the parameter C was sequentially increased from 2-10 to 210 in multiple of 2. Each fold was split into a training set and a validation set, with a division pattern of 176 training versus 18 validation or 174 training versus 20 validation. The total computation time of the 21 classifiers on various folds for each algorithm was reported in Table 1. The time cost of the 10-fold altogether was given in the last row entry of Table 1. It was clearly shown that the 10-fold cross-validation (CV) of FLSA-SVMs is over 4 times faster than SVMs. The time complexity of FLSA-SVMs remained competitive to that of LS-SVMs using the SMO algorithm and much more reduced than LS-SVMs using the CG method.Table 1
Time cost of 10-fold cross-validation on two-spiral data by FLSA-SVMS, SVMs, and LS-SVMs with fixed kernel parameters:λ=1 for FLSA-SVMs, λ=0.5 for SVMs, and λ=5.4899 for LS-SVMs.
No. of  folds
FLSA-SVMs
SVMs
LS-SVMsσ2=1
λ
=
1
λ
=
0.5
SMO
CG
1
0.218
0.843
0.125
2.915
2
0.203
0.766
0.141
2.832
3
0.219
0.859
0.125
2.815
4
0.219
0.735
0.140
2.916
5
0.203
0.703
0.125
2.821
6
0.219
0.890
0.125
2.861
7
0.219
0.954
0.141
2.941
8
0.218
1.000
0.125
2.842
9
0.219
0.968
0.125
2.847
10
0.219
0.907
0.125
2.847
∑
2.156
8.625
1.297
28.637These comparisons prove that the FLSA-SVM is very promising in easing the nonsparseness problem of an LS-SVM, in addition to its outstanding generalization performance. And it can obtain a solution whose sparseness is competitive, or even superior, to that of a standard SVM.


### 4.2. More Benchmark Problems

The FLSA-SVM algorithm was applied to 3 small-scale binary problems: Banana, Image, and Splice which are accessible athttp://theoval.cmp.uea.ac.uk/matlab/#benchmarks/. Among all the realizations for each benchmark, the first one of them was used. Experiments were also performed on Banana dataset [31], which is a medium-scale binary learning problem. The detailed information of the datasets was given in Table 2.Table 2
Benchmark information.
No. of trainings
No. of tests
No. of features
Banana
400
4900
2
Splice
1000
2175
60
Image
1300
1010
18
Ringnorm
3000
4400
20FLSA-SVMs were compared with SVMs, LS-SVMs, the fast sparse approximation scheme for LS-SVM (FSALS-SVM), and its variant, called PFSALS-SVM, both of which were proposed by Jiao et al. [12]. The parameter ϵ of FSALS-SVMs and PFSALS-SVMs was uniformly set to be 0.5 which was empirically proved to work well with most datasets [12]. Comparisons were also made against D-optimality orthogonal forward regression (D-OFR) [32] which is a technique for nonlinear function estimation, promised to yield sparse solutions. The parameters, which were the penalty constant and λ in (36), were tuned by tenfold cross-validation (CV).Table3 presented the classification accuracy of the SVM algorithms. The best results among the four SVM algorithms were highlighted. It can be seen that the FLSA-SVM achieved comparable classification accuracy to the standard SVM, the conventional SVM, FSAL-SVM, PFSALS-SVM, and D-optimality OFR.Table 3
Test correctness (%).
FLSA-SVM
SVM
LS-SVM
FSALS-SVM
PFSALS-SVM
D-OFR
(
m
,
λ
)
(
C
,
λ
)
(
γ
,
λ
)
(
γ
,
λ
)
(
γ
,
λ
)
(
γ
,
λ
)
Banana
89.33 (20,1)
89.33 (25,2-1)
88.92 (23,0.6369)
89.14 (25,2-1)
89.12 (23,2-1)
89.10 (40,2-2)
Splice
89.98 (220,2-6)
89.75 (23,2-7)
89.84 (23,0.0135)
89.93 (23,2-6)
89.93 (28,2-6)
89.33 (380,2-6)
Image
97.92 (180,2-5)
97.82 (27,2-3)
97.92 (27,0.0135)
98.32 (24,2-2)
98.02 (25,2-2)
97.92 (480,2-3)
Ringnorm
98.66 (27,2-5)
98.68 (2-6,2-5)
97.07 (29,0.1192)
98.70 (2-4,2-5)
98.70 (2-5,2-5)
98.59 (47,2-5)The numbers of SVs were compared in Table4. For all the learning problems, the FLSA-SVM required much less SVs than the SVM and the conventional SVM. In particular, the reduction in SVs reached over 98% and 80%, respectively, on Ringnorm and Banana datasets compared with the SVM. FLSA-SVM has maintained its edges over FSAL-SVM and PFSALS-SVM, particularly with the Ringnorm and Banana datasets. Although the D-OFR method falls into the category of unsupervised learning algorithms, FLSA-SVM, mathematically, has the closest link with the D-OFR method. The results in Table 3 demonstrated that the D-OFR method remained competitive compared with FLSA-SVM on Ringnorm and Banana datasets. However, on the Splice and Image datasets, the D-OFR method failed to achieve any sparse solutions.Table 4
Number of support vectors (best in bold).
FLSA-SVM
SVM
LS-SVM
FSALS-SVM
PFSALS-SVM
D-OFR
Banana
20
94
400
145
141
40
Splice
220
595
1000
507
539
380
Image
180
221
1300
272
278
480
Ringnorm
27
1624
3000
556
575
47


## 4.1. Experiments on Two-Spiral Dataset

The 2D “two-spiral” benchmark is known to be difficult for pattern recognition algorithms and poses great challenges to neural networks [30]. The training set consists of 194 points of the X-Y plane, half of which has a target value of +1 output and half a target value of −1. These training points describe two intertwining spirals that go around the origin three times, as shown in Figure 2, where the two categories are marked, respectively, by “+” and “o.”Figure 2
Two-spiral dataset.For the FLSA-SVM, the parameter setting of Gaussian kernel wasλ=1 as in (36). With a feasible range of [85,193], the optimal regularization parameter was found to be 134 which gave a leave-one-out cross-validation (LOOCV) accuracy of 97.94%. With standard SVMs, the parameter setting was C=32 and λ=0.5, whose LOOCV accuracy is 98.97%. The SVM classifier was required in 164 support vectors (SVs). The graphical outputs of the FLSA-SVM and the SVM were given by Figure 3. It showed that generally both SVM and FLSA-SVM algorithms recognized the pattern successfully, outputting “two-spiral” in a very smooth and regular manner. But at the area around the coordinate of [0,0], the FLSA-SVM showed better performance than the conventional SVM whose decision hyperplane was biased towards the “o” class.Comparison between standard SVMs and FLSA-SVMs: (a) two-spiral pattern recognized by the FLSA-SVM trained on 134 data points withλ=1 in (36); (b) two-spiral pattern recognized by the standard SVM trained on 164 data points. The penalty constant C=32 and σ=0.5.
(a)
(b)Despite the reduction in the number of SVs which is very notable for such a “hard” classification problem, the FLSA-SVMs are comparatively superior to the following two aspects. In SVMs, it often occurred that given a fixed kernel parameter, the optimal CV accuracy can be obtained from multiple value settings on the regularization parameter. The “two-spiral” problem is a case in point. For the best LOOCV accuracy, with a fixedλ=0.5, the value of C can also opt for (26,27,28,29,210) beyond 25. There is no specific rule as to which option is the best, and normally the smallest is chosen for a scaled-down feasible region. While in FLSA-SVMs, the setting for the value of the regularization term m is more tractable since different options correspond to different learning errors which can be easily tracked with (23). For multiple values of m which produce the same optimal CV accuracy, the largest m is chosen for a smaller learning error.In fact, form∈[160,193], the LOOCV accuracy remained stable at 96.91%. Thus an FLSA-SVM was also trained with the parameter settings of m=193 which was depicted in Figure 4(a). For comparisons, an LS-SVM was trained whose parameter settings are γ=173.7427 and λ=5.4899 for Gaussian RBF. The solution was parameterized by the entire 194 points and illustrated in Figure 4(b). The decision boundaries of both of the LS-SVM and the FLSA-SVM were generally smooth and followed the pattern satisfactorily, despite the slightly biased segments around the coordinates of [1.5,1.5] and [-1.5,-1.5]. But still the FLSA-SVM performed much better at the origin area than the LS-SVM.Comparison between LS-SVMs and FLSA-SVMs: (a) two-spiral pattern recognized by the conventional LS-SVM trained on 194 data points with the penalty parameterγ=173.7427 and λ=5.4899 for Gaussian RBF; (b) two-spiral pattern recognized by the FLSA-SVM trained on 180 data points with λ=1 in (36).
(a)
(b)Table1 also compares the time cost of 10-fold cross-validation (CV) on the regularization parameter by FLSA-SVMs, SVMs and LS-SVMs. For FLSA-SVMs, the regularization term m was assigned 21 integers evenly with an interval of 10 within the range of (1,194). For SVMs and LS-SVMs, the parameter C was sequentially increased from 2-10 to 210 in multiple of 2. Each fold was split into a training set and a validation set, with a division pattern of 176 training versus 18 validation or 174 training versus 20 validation. The total computation time of the 21 classifiers on various folds for each algorithm was reported in Table 1. The time cost of the 10-fold altogether was given in the last row entry of Table 1. It was clearly shown that the 10-fold cross-validation (CV) of FLSA-SVMs is over 4 times faster than SVMs. The time complexity of FLSA-SVMs remained competitive to that of LS-SVMs using the SMO algorithm and much more reduced than LS-SVMs using the CG method.Table 1
Time cost of 10-fold cross-validation on two-spiral data by FLSA-SVMS, SVMs, and LS-SVMs with fixed kernel parameters:λ=1 for FLSA-SVMs, λ=0.5 for SVMs, and λ=5.4899 for LS-SVMs.
No. of  folds
FLSA-SVMs
SVMs
LS-SVMsσ2=1
λ
=
1
λ
=
0.5
SMO
CG
1
0.218
0.843
0.125
2.915
2
0.203
0.766
0.141
2.832
3
0.219
0.859
0.125
2.815
4
0.219
0.735
0.140
2.916
5
0.203
0.703
0.125
2.821
6
0.219
0.890
0.125
2.861
7
0.219
0.954
0.141
2.941
8
0.218
1.000
0.125
2.842
9
0.219
0.968
0.125
2.847
10
0.219
0.907
0.125
2.847
∑
2.156
8.625
1.297
28.637These comparisons prove that the FLSA-SVM is very promising in easing the nonsparseness problem of an LS-SVM, in addition to its outstanding generalization performance. And it can obtain a solution whose sparseness is competitive, or even superior, to that of a standard SVM.


## 4.2. More Benchmark Problems

The FLSA-SVM algorithm was applied to 3 small-scale binary problems: Banana, Image, and Splice which are accessible athttp://theoval.cmp.uea.ac.uk/matlab/#benchmarks/. Among all the realizations for each benchmark, the first one of them was used. Experiments were also performed on Banana dataset [31], which is a medium-scale binary learning problem. The detailed information of the datasets was given in Table 2.Table 2
Benchmark information.
No. of trainings
No. of tests
No. of features
Banana
400
4900
2
Splice
1000
2175
60
Image
1300
1010
18
Ringnorm
3000
4400
20FLSA-SVMs were compared with SVMs, LS-SVMs, the fast sparse approximation scheme for LS-SVM (FSALS-SVM), and its variant, called PFSALS-SVM, both of which were proposed by Jiao et al. [12]. The parameter ϵ of FSALS-SVMs and PFSALS-SVMs was uniformly set to be 0.5 which was empirically proved to work well with most datasets [12]. Comparisons were also made against D-optimality orthogonal forward regression (D-OFR) [32] which is a technique for nonlinear function estimation, promised to yield sparse solutions. The parameters, which were the penalty constant and λ in (36), were tuned by tenfold cross-validation (CV).Table3 presented the classification accuracy of the SVM algorithms. The best results among the four SVM algorithms were highlighted. It can be seen that the FLSA-SVM achieved comparable classification accuracy to the standard SVM, the conventional SVM, FSAL-SVM, PFSALS-SVM, and D-optimality OFR.Table 3
Test correctness (%).
FLSA-SVM
SVM
LS-SVM
FSALS-SVM
PFSALS-SVM
D-OFR
(
m
,
λ
)
(
C
,
λ
)
(
γ
,
λ
)
(
γ
,
λ
)
(
γ
,
λ
)
(
γ
,
λ
)
Banana
89.33 (20,1)
89.33 (25,2-1)
88.92 (23,0.6369)
89.14 (25,2-1)
89.12 (23,2-1)
89.10 (40,2-2)
Splice
89.98 (220,2-6)
89.75 (23,2-7)
89.84 (23,0.0135)
89.93 (23,2-6)
89.93 (28,2-6)
89.33 (380,2-6)
Image
97.92 (180,2-5)
97.82 (27,2-3)
97.92 (27,0.0135)
98.32 (24,2-2)
98.02 (25,2-2)
97.92 (480,2-3)
Ringnorm
98.66 (27,2-5)
98.68 (2-6,2-5)
97.07 (29,0.1192)
98.70 (2-4,2-5)
98.70 (2-5,2-5)
98.59 (47,2-5)The numbers of SVs were compared in Table4. For all the learning problems, the FLSA-SVM required much less SVs than the SVM and the conventional SVM. In particular, the reduction in SVs reached over 98% and 80%, respectively, on Ringnorm and Banana datasets compared with the SVM. FLSA-SVM has maintained its edges over FSAL-SVM and PFSALS-SVM, particularly with the Ringnorm and Banana datasets. Although the D-OFR method falls into the category of unsupervised learning algorithms, FLSA-SVM, mathematically, has the closest link with the D-OFR method. The results in Table 3 demonstrated that the D-OFR method remained competitive compared with FLSA-SVM on Ringnorm and Banana datasets. However, on the Splice and Image datasets, the D-OFR method failed to achieve any sparse solutions.Table 4
Number of support vectors (best in bold).
FLSA-SVM
SVM
LS-SVM
FSALS-SVM
PFSALS-SVM
D-OFR
Banana
20
94
400
145
141
40
Splice
220
595
1000
507
539
380
Image
180
221
1300
272
278
480
Ringnorm
27
1624
3000
556
575
47


## 5. Conclusions

The paper proposed a new LS-SVM algorithm—the FLSA-SVM which is trained specifically by the FLSA method of minimized squared error loss. The FLSA-SVM iteratively selects an optimal basis function which is associated with a specific training example into the solution. The algorithm cleverly adapts the number of SVs into the regularization term as the tradeoff between generalization abilities and training cost. As a result, the solution of the FLSA-SVMs is extremely sparse compared to LS-SVMs. Experiments showed that the FLSA-SVM algorithm maintained a comparable accuracy compared to the standard SVM, the LS-SVM and a number of recently developed sparse learning algorithms. Yet the FLSA-SVM showed definite advantages to its counterparts regarding the sparseness of the solution. On small datasets like the two-spiral benchmark, the FLSA-SVM training algorithm also proved to be more efficient than the CG method.



---

*Source: 602341-2013-02-07.xml*