Training Support Vector Machines Using Greedy Stagewise Algorithm


Hard margin support vector machines (HM-SVMs) have a risk of getting overfitting in the presence of the noise. Soft margin SVMs deal with this problem by the introduction of the capacity control term and obtain the state of the art performance. However, this disposal leads to a relatively high computational cost. In this paper, an alternative method, greedy stagewise algorithm, named GS-SVMs is presented to deal with the overfitting of HM-SVMs without the introduction of capacity control term. The most attractive property of GS-SVMs is that its computational complexity scales quadratically with the size of training samples in the worst case. Extensive empirical comparisons confirm the feasibility and validity GS-SVMs. 

Introduction

Hard margin support vector machines have a risk of getting overfitting in the presence of the noise [1]. To deal with this problem, soft margin SVMs [2] introduce the capacity control parameter that allows a little training error to obtain the large margin. This is a highly effective mechanism for avoiding overfitting, which leads to good generalization performance. Though very successful, we can identify some shortages of soft margin SVMs: 
① The training procedure of soft margin SVMs amounts to solving a constrained quadratic programming. Although the training problem is, in principle, solvable, in practice it is intractable by the classical optimization techniques, e.g. interior point method because their computational complexity usually scales cubically with the size of training samples. 
② Capacity control parameter depends on the task at hand; hence there is no fool- proof method for determining it before training. Usually, we have to resort to a cross validation procedure, which is wasteful in computation [3]. 
In the past few years, a lot of fast iterative algorithms were presented for tackling the problem ①. Probably, the most famous method among them is sequential minimization optimization algorithm (SMO), which is proposed by Platt [4] and further improved by Keerthi [5]. Some other examples include SVM light [6], SimpleSVM [7], 
SVMTorch [8], and so on. These algorithms proved to be effective and boosted the development of SVMs. 
In this paper, an alternative method, greedy stagewise algorithm, named GS-SVMs is presented to deal with the overfitting of HM-SVMs. Instead of employing the capacity control term, GS-SVMs attempts to control the capacity of hypothesis space by algorithm itself. In summary, the proposed algorithms possess the following two attractive properties: 
① The computational complexity of GS-SVMs is ( ) O nl , where l and n are the size of training samples and support vectors, respectively. Even in the worst situation that all the training samples are the support vectors, the computational complexity of GS-SVMs is only ( ) 
2 O l .
② No extra capacity control parameter is required. 

Greedy Stagewise Algorithm for SVMs

The Wolfe dual of hard margin SVMs ( ) 
, 1 1 1 min , 2 . . 0 1, , , l l i j i j i j i i j i i y y K s t i l α α α α = = ⎛ ⎞ - ⎜ ⎟ ⎝ ⎠ ≤ = ∑ ∑ x x L (1) 
can be regarded as a loss function induced by reproducing kernel Hilbert space norm. This allows us to approximate it using greedy algorithm. Due to the room limitation, the detailed interpretation is ignored and the interested reader can refer to [9]. Though HM-SVM is, in principle, solvable by the classical optimization technique, in practice it suffers from two serious problems: (1) their computational complexity usually scales cubically with the size of training samples; (2) there often is a risk of getting overfitting due to no capacity control term. Here, we will deal with the two problems by greedy stagewise algorithm, which attempts to approximate (1) quickly while avoids the overfitting. Greedy stagewise algorithm [10] can be described as the following. For 1, 2, 
m l = L , ( ) ( ) ( ) ( ) 1 , 1 , argmin , , . . 1,2, 1 l 
m m i m i i w i j w Lyf w K s t j m β β β β β - = ⎛ ⎞ = + ⎜ ⎟ ⎝ ⎠ ≠ = - ∑ x x x L (2) 
and then 
( ) 1 , m m m m f f w K β - = + x x . ( 3 
)
where ( ) L denotes loss function, 0 0 f ≡ and the constraint terms guarantee that each basis function is used once at most. For SVMs, w takes the form , 0 y β α α ≥ . Using the loss function (1) we have 
( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 , 2 1 1 , 2 , argmin 1 , , 2 . . 0 1, 2, 1 i j i j i j i i i j m m m i j i m m m i j y y K y y K K s t j m β β β β β β β α β β β β β β β β α α α α β α α α α α β β - - - = = = - = ⎛ ⎞ - + ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ + - ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ≥ ≠ = - ∑∑ ∑ ∑ x x x x x x L . ( 4 
)
Note that the first two terms of ( 4) can be ignored. Define the gradient vector ( ) 
1 1 0 , 1 1 j j j m m j if m y y K i f m β β β β β β α = - = ⎧ ⎪ = ⎨ - ≥ ⎪ ⎩ ∑ g x x . ( 5 
)
We can reformulate (4) as 
( ) ( ) 2 1 , 1 , argmin , 2 . 
. 0 
1, 2, 1 m m m j K s t j m β β β α β α β α α α β β - ⎛ ⎞ = + ⎜ ⎟ ⎝ ⎠ ≥ ≠ = - x x g L . (6) 
(6) can be solved in two steps. In the first step, we fix β and compute the minimal 
( ) 2 1 1 min , 2 . . 0 m K s t β β β α α α α - ⎛ ⎞ + ⎜ ⎟ ⎝ ⎠ ≥ x x g (7) 
Since ( 7) is a single variable quadratic programming, we can give its analytical solution, i.e. 
1 1 1 ( , ), ( , ) 0 0, ( , ) 0 m m m K i f K if K β β β β β β β β β β α - - - ⎧- - > ⎪ = ⎨ - ≤ ⎪ ⎩ g x x g x x g x x . ( 8 
)
According to the positive definite property of kernel function, we have ( ) 
, 0 K β β > x x
. Thus (8) can be further simplified as 
1 1 1 ( , ), 0 0, 0 m m m K i f if β β β β β β α - - - ⎧- < ⎪ = ⎨ ≥ ⎪ ⎩ g x x g g . (9) 
Combining ( 7) and ( 9), we get 
( ) ( ) ( ) 2 1 1 1 2 1 0 1 2 , , 0 1 min , 2 0, 0 m m m m m K i f h K if β β β β β β β β α β α α - - - - ≥ - ⎧ - < ⎪ ⎛ ⎞ = + = ⎨ ⎜ ⎟ ⎝ ⎠ ≥ ⎪ ⎩ g x x g x x g g . (10) 
In GS-SVMs, each basis function corresponds to a specified training sample and vice versa. Hence, if the basis function ( ) , K β x x does not appear in m f , we say its corresponding training sample β x unused. From (10), we can derive that if the gradients of all the unused training samples are larger than zero, the loss function (1) will stop decreasing. Hence we will terminate the algorithm if the above condition is satisfied. 
Considering ( 9) and ( 10), we can obtain the parameter pairs ( ) 
, m m
α β by the following equations ( ) 
1 arg min m m Q h β β β - ∈ = . ( 11 
) ( ) 1 , m m m m m K β β β α - = -g x x . ( 12 
)
Thus the greedy stagewise algorithm for SVMs (GS-SVMs) can be described as ( ) 
Algorithm 1: GS-SVMs 1. Set 0 ( ) 0 f = x , α = 0 , 0 = - g 1, 0 = - h 1, { 1,2, } Q l = L , P = ∅ ;
1 arg min m m Q h β β β - ∈ = , ( ) 
1 , m m m m m K β β β α - = -g x x ; 5. { } m P P β = ∪ , { } m Q Q β = - ; 6. ( ) 1 , , m m m m m y y K Q β β β β β β β β - = + ∈ g g x x ; 7. Update 1 , m h Q β β -
∈ according to (4.9); 8. 
( ) 
1 ( ) ( ) , m m m m m f f y K β β α - = + x x xx ;
9. End For 10. End Algorithm 

Empirical Comparison

In all the experiments, the kernel matrix is constructed by Gaussian kernel 
( ) ( ) 2 , exp i j i j K θ = - - x x x x
. Following [4], we compare the number of kernel evaluations of GS-SVMs and SMO, which is an effective measure of the algorithm's speed. For the sake of fair comparison, we use the same data sets and kernel parameter as in [4]. Note that the number of kernel evaluations of SMO in Table 1. denotes the average number under the different capacity control parameters. From Table 1, we can see that GS-SVMs obtain the speedup range from 10 to 30 on the different data sets. In order to validate the performance of GS-SVMs, we compare it with hard magin and Soft margin SVMs on the fifteen benchmark data sets that are from UCI machine learning repository [11]. One-against-one method is used to extend binary classifiers to multi-class classifiers. 
On each data set, ten-fold cross validation is run. The average accuracy of ten-fold cross validation is reported in Table 2. For each training-test pair, ten-fold cross validation is performed on training set for tuning free parameters. The detailed experiment setup is the following: The two-tailed t-tests also indicate that GS-SVMs are significantly better than SVMs on Glass and worse than SVMs on Liver. As for the remaining data sets, GS-SVMs and SVMs obtain the similar performance. Hence we have the conclusion that GS-SVMs are significantly better in speed than SMO and comparable in performance with SMO. 

Conclusion

This paper proposes a greedy stagewise algorithm, named GS-SVMs to deal with the overfitting of HM-SVMs. Empirical comparisons confirm the feasibility and validity of GS-SVMs. 

-

  of(6) with respect to α . In the second step, we compute m β by minimizing 1 m h β -with respect to β , and then compute m α in terms of m β . Fixing β , we have the subproblem 


Fig. 1 .

 1 Fig. 1. Pseudo code of GS-SVMs 


.

  (a) For soft margin SVMs, Kernel width and capacity control parameter are chosen from intervals enough for our problems. The number of trainings on each training-test pair needed by this method is 10 17 12 2040 × × = . (b) For GS-SVMs and HM-SVMs, Kernel width is chosen from interval The number of trainings on each training-test pair needed by this method is 10 17 170 × = . 


Table 1 .

 1 Number of kernel evaluations of GS-SVMs and SMO.Each unit corresponds to6 


	10

Tabel 2 .

 2 Accuracy of GS-SVMs, HM-SVMs and SVMs 


	Problems	Size	Dim	Class	GS-SVMs	HM-SVMs	SVMs
	Australian	690	15	2	84.93	78.55	84.49
	German	1000	20	2	74.20	69.30	75.40
	Glass	214	9	6	71.54	68.66	66.81
	Heart	270	13	2	83.70	76.67	83.23
	Ionosphere	351	34	2	94.00	94.00	94.02
	Iris	150	4	3	95.33	92.00	96.00
	Liver	345	6	2	66.03	61.69	71.29
	Page	5473	10	4	96.45	96.50	96.93
	Diabetes	768	8	2	77.21	70.55	77.08
	Segment	2310	18	7	97.32	96.84	97.01
	Splice	3175	60	3	96.72	96.31	96.25
	Vowel	528	10	11	98.29	99.05	99.05
	WDBC	569	30	2	97.72	96.49	97.54
	Wine	178	13	3	98.89	96.64	98.89
	Zoo	101	10	7	97.09	96.09	96.09
	Mean	/	/	/	88.63	85.96	88.67
Liefeng Bo, Ling Wang, Licheng Jiao
Training Support Vector Machines Using Greedy Stagewise Algorithm