# Different Testing Results on SVM with Double Penalty Parameters

Authors: Chengkuan Yao; Liyong Cao; Jianhua Xu; Mingya Yang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The Support Vector Machine proposed by Vapnik is a generalized linear classifier which makes binary classification of data based on the supervised learning. SVM has been rapidly developed and has derived a series of improved and extended algorithms, which have been applied in pattern recognition, image recognition, etc. Among the many improved algorithms, the technique of regulating the ratio of two penalty parameters according to the ratio of the sample quantities of the two classes has been widely accepted. However, the technique has not been verified in the way of rigorous mathematical proof. The experiments based on USPS sets in the study were designed to test the accuracy of the theory. The optimal parameters of the USPS sets were found through the grid-scanning method, which showed that the theory is not accurate in any case because there is absolutely no linear relationship between ratios of penalty parameters and sample sizes.


---

## Body

## 1. Introduction

In the mid-1990s, the research team led by Vapnik proposed the advanced Support Vector Machine (SVM) [1–3]. By using a nonlinear mapping from lower-dimensional space to higher-dimensional space, the SVM seeks a hyperplane with the best classifying performance. Based on statistical learning theory and empirical risk minimization, SVM solving the optimization problem with the dual theory has become a valuable algorithm in the field of artificial intelligence.The original SVM only had one penalty parameter. Cortes and Vapnik [3] proposed a new kind of SVM with two penalty parameters of C+ and C−. Chew et al. [4, 5] put forward a new idea that by using the quantities of two classes of samples to adjust C+ and C−, SVM has preferable classifying accuracy, which has been accepted widely. This theory, however, has not been proved mathematically. Furthermore the theory was derived from experiences described as “a rule of thumb” [4]. A number of experiments were designed to test the theory in this paper. The experiments were conducted on the dataset of USPS which is a standard handwriting database and comes from the United States Postal Service. The USPS contains ten categories of samples which are the 10 figures including 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The USPS is often used for testing in the field of machine learning.Through the way of grid scanning for parameters, the relationships between optimal parameters were revealed when SVM achieved the optimal performance. The experimental results did not show that the optimal parameters ofC+ and C− have the relationship with the class sizes, which was proposed and applied by Chew et al. [4, 5].


## 2. Support Vector Machine Algorithm

The initial SVM is to solve the quadratic programming as follows:(1)min12w2+C∑i=1lξis.t.yiw⋅xi+b≥1−ξi,ξi≥0,i=1,…,l,where C>0 is the penalty parameter and ξi≥0 is the slack variable for the i-th data vector and w and b are the normal vector and the bias of the hyperplane, respectively. Figure 1 shows the example of SVM in two dimensions.Figure 1
Example of SVM in two dimensions.The kernel functionk(xi, xj) was introduced into formula (1) to replace the inner product operation, and the dual form was obtained as follows [1]:(2)max∑i=1lαi−12∑i,j=1lαiαjyiyjkxi,xjs.t.∑i=1lαiyi=0,0≤αi≤C,i=1,…,l,where αi are the Lagrange multipliers. The SVM with high classification accuracy should have the most samples correctly classified with αi = 0; meanwhile, the SVM should have the least samples misclassified with αi > 0.All the training samples in Figure1 could be divided into three cases:(1)
Nonsupport vectors (NSVs), which could be correctly classified and not inH1 and H2, can satisfy the following formula:(3)yiw⋅xi+b−1+ξi>0,αi=0,μi=C,ξi=0.(2)
Support vectors (SVs), which could be correctly classified but located onH1 and H2, can satisfy the following formula:(4)yiw⋅xi+b−1+ξi=0,ξi=0,μi≠0,0<αi<C.(3)
Bounded support vectors (BSVs), which are misclassified, can satisfy the following formula:(5)yiw⋅xi+b−1+ξi=0,ξi≠0,μi=0,αi=C.


## 3. Improved SVM Algorithm

### 3.1. SVM with Double Penalty Parameters

Two penalty parameters, namely,C+ and C−, were introduced by Osuna et al. [6]. The optimization problem is minimized, taking the form(6)min12w2+C+∑i:yi=+1ξi+C−∑i:yi=−1ξis.t.yiw⋅xi+b≥1−ξiξi≥0,i=1,…,l,where C+ and C− are the error penalties for the positive (yi = +1) and the negative (yi = −1) vectors, respectively. The dual form of (6) is(7)max∑i=1lαi−12∑i,j=1lαiαjyiyjkxi,xjs.t.∑i=1lαiyi=00≤αi≤C+,ifyi=+10≤αi≤C−,ifyi=−1.Chew et al. raised a point [4] that in order to avoid to overlearning of SVM, the BSVs should greatly outnumber the SVs in the SVM. That is to say, the misclassified samples should far exceed the samples on the boundary line. In other words, in the SVM with the best performance, there are enough BSVs to avoid overlearning and the SVs could be ignored because of their minuscule amount.In the view of Chew et al. [4], the error rates of the two classes of samples can be expressed as B+/N+ and B−/N−, where B+and B− are the numbers of the misclassified samples (BSVs) of the two classes and N+and N− are the numbers of samples of the two classes, respectively. Thus, the constraint in formula (7) can be repressed as(8)∑αi≈B+⋅C+,ifyi=+1,∑αi≈B−⋅C−,ifyi=−1,B+⋅C+≈B−⋅C−.Setting the ratios of the error rate between the positive class and the negative class,(9)B+N+:B−N−,1C+N+:1C−N−,C−N−:C+N+.When the following equation is true, the SVM has the best classification performance:(10)C+C−=N−N+.


### 3.2.υ-SVM

Schölkopf et al. [7] put forward the υ-SVM algorithm with the parameter υ to replace C and ξ′ in the original SVM. The υ-SVM is shown as follows:(11)min12w2−υρ+1l∑iξis.t.yiw⋅xi+b≥ρ−ξiξi≥0,i=1,…,l,ρ≥0,where ρ is the location of the margin and the 2ρ/w is the width of the margin. When minimizing the classifying error, the maximum width of the margin could be obtained. Chew et al. improved the υ-SVM [5] and made the same conclusion that the optimal parameters of υ-SVM satisfy the relationship of equation (10).Equation (10) has been widely recognized and put into use in the two-class sample sets, and the results have been shown with the optimal classification performance [8–10].


## 3.1. SVM with Double Penalty Parameters

Two penalty parameters, namely,C+ and C−, were introduced by Osuna et al. [6]. The optimization problem is minimized, taking the form(6)min12w2+C+∑i:yi=+1ξi+C−∑i:yi=−1ξis.t.yiw⋅xi+b≥1−ξiξi≥0,i=1,…,l,where C+ and C− are the error penalties for the positive (yi = +1) and the negative (yi = −1) vectors, respectively. The dual form of (6) is(7)max∑i=1lαi−12∑i,j=1lαiαjyiyjkxi,xjs.t.∑i=1lαiyi=00≤αi≤C+,ifyi=+10≤αi≤C−,ifyi=−1.Chew et al. raised a point [4] that in order to avoid to overlearning of SVM, the BSVs should greatly outnumber the SVs in the SVM. That is to say, the misclassified samples should far exceed the samples on the boundary line. In other words, in the SVM with the best performance, there are enough BSVs to avoid overlearning and the SVs could be ignored because of their minuscule amount.In the view of Chew et al. [4], the error rates of the two classes of samples can be expressed as B+/N+ and B−/N−, where B+and B− are the numbers of the misclassified samples (BSVs) of the two classes and N+and N− are the numbers of samples of the two classes, respectively. Thus, the constraint in formula (7) can be repressed as(8)∑αi≈B+⋅C+,ifyi=+1,∑αi≈B−⋅C−,ifyi=−1,B+⋅C+≈B−⋅C−.Setting the ratios of the error rate between the positive class and the negative class,(9)B+N+:B−N−,1C+N+:1C−N−,C−N−:C+N+.When the following equation is true, the SVM has the best classification performance:(10)C+C−=N−N+.


## 3.2.υ-SVM

Schölkopf et al. [7] put forward the υ-SVM algorithm with the parameter υ to replace C and ξ′ in the original SVM. The υ-SVM is shown as follows:(11)min12w2−υρ+1l∑iξis.t.yiw⋅xi+b≥ρ−ξiξi≥0,i=1,…,l,ρ≥0,where ρ is the location of the margin and the 2ρ/w is the width of the margin. When minimizing the classifying error, the maximum width of the margin could be obtained. Chew et al. improved the υ-SVM [5] and made the same conclusion that the optimal parameters of υ-SVM satisfy the relationship of equation (10).Equation (10) has been widely recognized and put into use in the two-class sample sets, and the results have been shown with the optimal classification performance [8–10].


## 4. Hypothesis Testing

There is a lack of rigorous mathematical derivations and proofs for formula (10). Furthermore, the SVs which could be correctly classified (located on H1 and H2 in Figure 1) are ignored, which bring about the only usage of the symbol “≈” instead of “=” in formula (8). In addition, formula (10) only shows the ratio of C+/C− and not the absolute value of C+ and C− that actually should be specified.In the following experiment, it will be verified whether the optimal parameters of SVM satisfy equation (10).


### 4.1. Methods and Steps of the Testing

The experiment was divided into two main steps. In the first step, ten two-class data sets were constructed, which were tested by different parameters in the second part.


#### 4.1.1. Establishment of Two-Class Data Sets

The USPS handwritten digital dataset is often used for algorithm testing in the field of pattern recognition and machine learning. There are 10-class samples in the USPS, which are the 10 figures formed from 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The USPS has 256 attributions. The sample size of the training set and the testing set are 7291 and 2007, respectively [11].The USPS was transformed into 10 two-class data sets described as USPS-0, USPS-1, USPS-2, …, USPS-9. The USPS-0 set contains two class samples, which are the digitals of 0 and all the non-0 digitals formed from digitals of 1, 2, 3, 4, 5, 6, 7, 8, and 9. The USPS-1 set contains two class samples, which are the digitals of 1 and all the non-1 digitals formed from digitals of 0, 2, 3, 4, 5, 6, 7, 8, 9, …. The USPS-9 set contains two class samples, which are the digitals of 9 and all the non-9 digitals formed from digitals of 0, 1, 2, 3, 4, 5, 6, 7, and 8.


#### 4.1.2. Testing Procedure

The method of grid scanning for parameters was adopted to try to find out the optimal parameters of the ten two-class datasets. The polynomial kernel function was employed, and the software package of LIBSVM [12] was used to carry out the experiment.The steps are as follows:(1)
The order of the polynomiald = {2, 3, 4, 5, 6} was specified; in other words, there were five major cycles with five different values of order of the polynomial.(2)
The penalty parametersC+ and C− = [100 … 10000], and the step width was 100. To be more specific, the value of C+ was 100, 200, 300, …, 1000, 1100, …, 2000, 2100, …, 3000, and 3100, …, 10000 in order, so was the value of C−.(3)
We performed three rounds of cyclic scanning for the three parameters, namely,d, C+, and C−. That is to say, each of the ten two-class datasets was tested to get the testing precision more than 50,000 times with different combinations of the three parameters.When the highest accuracy was achieved, the parameter is the optimal parameter. If there were multiple optimal parameters, the following two rules should be abided to choose the optimal parameters:(1)
ChoosingminC++C−, which was the inflection point of parameters(2)
If there are still multiple equalminC++C−s, choosing mind which was the lowest order of polynomial


### 4.2. Testing Result

After performing grid scanning on the ten two-class data sets, the optimal parameters are obtained as shown in Table1. The first column on the left side in the table is the category identifier of the 10 data sets. In the first row, d is the order of polynomial; N+ and N− are the sizes of samples of the two classes, respectively; and C+ and C− are the penalty parameters of the two categories.Table 1
Sample sizes and the optimal parameters and accuracy of the 10 two-class data sets.
Category IdentifierdN+N−C+C−Classification accuracyUSPS-05644664712002000.9945USPS-1511946097260010000.9945USPS-24100562864002000.9965USPS-357316560280030000.9875USPS-4665866336002000.9910USPS-5365266393004000.9865USPS-6455667352001000.9895USPS-73664662726002000.9955USPS-85645664612008000.9940USPS-94542674917002000.9880In order to find whether the optimal parameters in Table1 satisfy formula (10) more intuitively, the histogram of C+/C− with N−/N+ is shown in Figure 2.Figure 2
Histogram of C+/C− and N−/N+.In Figure2, there are nine datasets satisfying the relationship of N−/N+>C+/C−. Meanwhile, only one dataset of USPS-7 meets the relationship of N−/N+<C+/C−. The experiment came to the conclusion that the relationship between the sample size and the optimal parameters does not satisfy formula (10); in other words, the following formula is true:(12)C+C−≠N−N+.Formula (10) has not been proved in the mathematical way rigorously, but a kind of reasoning based on experience. Also, formula (10) is too simple to reveal the internal relations between the sample size and the optimal parameters.The core of SVM is SVs [1–3] which could be correctly classified and located on H1 and H2 in Figure 1, and the classification hyperplane is mainly derived from the attributes of SVs. No matter the number of SVs is more or less, it cannot be ignored [4, 5] under any circumstances.In fact, the number of the correctly classified support vectors (SVs) should exceed the number of bounded support vectors (BSVs) in the SVM with preferable performance. Obviously, as seen from Figure1, the more the points on H1 and H2, the better the performance the SVM has. Meanwhile, the misclassified points should be as few as possible.


### 4.3. Analysis of the Means and Standard Deviation

In the grid scanning in Section4.1.2, there are still many parameters with the same optimal value. That is to say, the optimal value is obtained at many points. In order to further verify the relationship between penalty parameters and sample sizes, parameters with the same optimal classification accuracy were statistically analyzed.The means and the standard deviations ofC+/C−s with the same optimal value were calculated, which are shown in Table 2. The second column on the left is the number of the same optimal values, which is presented as N(opt. C+/C−). Meanwhile, the means and the standard deviations of the optimal C+/C−s are presented as E(opt. C+/C−) and σ in the third and the right column.Table 2
Means and the standard deviations of the same optimal values ofC+/C−s of the 10 two-class sets.
Category identifierNopt.C+/C−Eopt.C+/C−σUSPS-0404.042.38USPS-1980.452.26USPS-2310.273.59USPS-3702.011.40USPS-4223.982.74USPS-51450.563.45USPS-6510.312.89USPS-7962.772.98USPS-81551.691.84USPS-9573.142.13Based onN− > N+ in Table 1, the following inequality is true:(13)N−N+>1.If formula (10) is true, combined with formula (13), the following formula can be derived:(14)C+C−>1.However, there are fourE(opt. C+/C−)s in Table 2, namely, USPS-1, USPS-2, USPS-5, and USPS-6, satisfying the following inequality:(15)C+C−<1.In fact, formulas (14) and (15) contradict each other, which is another proof that formula (10) is not true at any condition.


## 4.1. Methods and Steps of the Testing

The experiment was divided into two main steps. In the first step, ten two-class data sets were constructed, which were tested by different parameters in the second part.


### 4.1.1. Establishment of Two-Class Data Sets

The USPS handwritten digital dataset is often used for algorithm testing in the field of pattern recognition and machine learning. There are 10-class samples in the USPS, which are the 10 figures formed from 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The USPS has 256 attributions. The sample size of the training set and the testing set are 7291 and 2007, respectively [11].The USPS was transformed into 10 two-class data sets described as USPS-0, USPS-1, USPS-2, …, USPS-9. The USPS-0 set contains two class samples, which are the digitals of 0 and all the non-0 digitals formed from digitals of 1, 2, 3, 4, 5, 6, 7, 8, and 9. The USPS-1 set contains two class samples, which are the digitals of 1 and all the non-1 digitals formed from digitals of 0, 2, 3, 4, 5, 6, 7, 8, 9, …. The USPS-9 set contains two class samples, which are the digitals of 9 and all the non-9 digitals formed from digitals of 0, 1, 2, 3, 4, 5, 6, 7, and 8.


### 4.1.2. Testing Procedure

The method of grid scanning for parameters was adopted to try to find out the optimal parameters of the ten two-class datasets. The polynomial kernel function was employed, and the software package of LIBSVM [12] was used to carry out the experiment.The steps are as follows:(1)
The order of the polynomiald = {2, 3, 4, 5, 6} was specified; in other words, there were five major cycles with five different values of order of the polynomial.(2)
The penalty parametersC+ and C− = [100 … 10000], and the step width was 100. To be more specific, the value of C+ was 100, 200, 300, …, 1000, 1100, …, 2000, 2100, …, 3000, and 3100, …, 10000 in order, so was the value of C−.(3)
We performed three rounds of cyclic scanning for the three parameters, namely,d, C+, and C−. That is to say, each of the ten two-class datasets was tested to get the testing precision more than 50,000 times with different combinations of the three parameters.When the highest accuracy was achieved, the parameter is the optimal parameter. If there were multiple optimal parameters, the following two rules should be abided to choose the optimal parameters:(1)
ChoosingminC++C−, which was the inflection point of parameters(2)
If there are still multiple equalminC++C−s, choosing mind which was the lowest order of polynomial


## 4.1.1. Establishment of Two-Class Data Sets

The USPS handwritten digital dataset is often used for algorithm testing in the field of pattern recognition and machine learning. There are 10-class samples in the USPS, which are the 10 figures formed from 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The USPS has 256 attributions. The sample size of the training set and the testing set are 7291 and 2007, respectively [11].The USPS was transformed into 10 two-class data sets described as USPS-0, USPS-1, USPS-2, …, USPS-9. The USPS-0 set contains two class samples, which are the digitals of 0 and all the non-0 digitals formed from digitals of 1, 2, 3, 4, 5, 6, 7, 8, and 9. The USPS-1 set contains two class samples, which are the digitals of 1 and all the non-1 digitals formed from digitals of 0, 2, 3, 4, 5, 6, 7, 8, 9, …. The USPS-9 set contains two class samples, which are the digitals of 9 and all the non-9 digitals formed from digitals of 0, 1, 2, 3, 4, 5, 6, 7, and 8.


## 4.1.2. Testing Procedure

The method of grid scanning for parameters was adopted to try to find out the optimal parameters of the ten two-class datasets. The polynomial kernel function was employed, and the software package of LIBSVM [12] was used to carry out the experiment.The steps are as follows:(1)
The order of the polynomiald = {2, 3, 4, 5, 6} was specified; in other words, there were five major cycles with five different values of order of the polynomial.(2)
The penalty parametersC+ and C− = [100 … 10000], and the step width was 100. To be more specific, the value of C+ was 100, 200, 300, …, 1000, 1100, …, 2000, 2100, …, 3000, and 3100, …, 10000 in order, so was the value of C−.(3)
We performed three rounds of cyclic scanning for the three parameters, namely,d, C+, and C−. That is to say, each of the ten two-class datasets was tested to get the testing precision more than 50,000 times with different combinations of the three parameters.When the highest accuracy was achieved, the parameter is the optimal parameter. If there were multiple optimal parameters, the following two rules should be abided to choose the optimal parameters:(1)
ChoosingminC++C−, which was the inflection point of parameters(2)
If there are still multiple equalminC++C−s, choosing mind which was the lowest order of polynomial


## 4.2. Testing Result

After performing grid scanning on the ten two-class data sets, the optimal parameters are obtained as shown in Table1. The first column on the left side in the table is the category identifier of the 10 data sets. In the first row, d is the order of polynomial; N+ and N− are the sizes of samples of the two classes, respectively; and C+ and C− are the penalty parameters of the two categories.Table 1
Sample sizes and the optimal parameters and accuracy of the 10 two-class data sets.
Category IdentifierdN+N−C+C−Classification accuracyUSPS-05644664712002000.9945USPS-1511946097260010000.9945USPS-24100562864002000.9965USPS-357316560280030000.9875USPS-4665866336002000.9910USPS-5365266393004000.9865USPS-6455667352001000.9895USPS-73664662726002000.9955USPS-85645664612008000.9940USPS-94542674917002000.9880In order to find whether the optimal parameters in Table1 satisfy formula (10) more intuitively, the histogram of C+/C− with N−/N+ is shown in Figure 2.Figure 2
Histogram of C+/C− and N−/N+.In Figure2, there are nine datasets satisfying the relationship of N−/N+>C+/C−. Meanwhile, only one dataset of USPS-7 meets the relationship of N−/N+<C+/C−. The experiment came to the conclusion that the relationship between the sample size and the optimal parameters does not satisfy formula (10); in other words, the following formula is true:(12)C+C−≠N−N+.Formula (10) has not been proved in the mathematical way rigorously, but a kind of reasoning based on experience. Also, formula (10) is too simple to reveal the internal relations between the sample size and the optimal parameters.The core of SVM is SVs [1–3] which could be correctly classified and located on H1 and H2 in Figure 1, and the classification hyperplane is mainly derived from the attributes of SVs. No matter the number of SVs is more or less, it cannot be ignored [4, 5] under any circumstances.In fact, the number of the correctly classified support vectors (SVs) should exceed the number of bounded support vectors (BSVs) in the SVM with preferable performance. Obviously, as seen from Figure1, the more the points on H1 and H2, the better the performance the SVM has. Meanwhile, the misclassified points should be as few as possible.


## 4.3. Analysis of the Means and Standard Deviation

In the grid scanning in Section4.1.2, there are still many parameters with the same optimal value. That is to say, the optimal value is obtained at many points. In order to further verify the relationship between penalty parameters and sample sizes, parameters with the same optimal classification accuracy were statistically analyzed.The means and the standard deviations ofC+/C−s with the same optimal value were calculated, which are shown in Table 2. The second column on the left is the number of the same optimal values, which is presented as N(opt. C+/C−). Meanwhile, the means and the standard deviations of the optimal C+/C−s are presented as E(opt. C+/C−) and σ in the third and the right column.Table 2
Means and the standard deviations of the same optimal values ofC+/C−s of the 10 two-class sets.
Category identifierNopt.C+/C−Eopt.C+/C−σUSPS-0404.042.38USPS-1980.452.26USPS-2310.273.59USPS-3702.011.40USPS-4223.982.74USPS-51450.563.45USPS-6510.312.89USPS-7962.772.98USPS-81551.691.84USPS-9573.142.13Based onN− > N+ in Table 1, the following inequality is true:(13)N−N+>1.If formula (10) is true, combined with formula (13), the following formula can be derived:(14)C+C−>1.However, there are fourE(opt. C+/C−)s in Table 2, namely, USPS-1, USPS-2, USPS-5, and USPS-6, satisfying the following inequality:(15)C+C−<1.In fact, formulas (14) and (15) contradict each other, which is another proof that formula (10) is not true at any condition.


## 5. Conclusion

The method of grid scanning for parameters was employed to find the optimal values, which was designed to reveal the relationship between the optimal parameters and the sample sizes. Since the parameters are infinite, it is impossible to test all of the parameter possibilities. Also, the optimal parameters were tested in a very wide range of thresholds, which used much more time.From the results of the study, it is believed that the optimal parameters ofC+ and C− by no means rely on the size of samples. To be more exact, there is absolutely no linear relationship between ratios of penalty parameters and sample sizes.At present, all parameter optimization in machine learning is local optimization and the study in the paper is no exception. Optimization algorithms, such as gradient descent, Newton’s method, and Quasi-Newton methods, could be used to find out the optimal parameters of SVM, which is an iterative process and certainly takes a lot of time. Therefore, finding the optimal parameters in limited and acceptable time must be very valuable, which is the new research direction worth exploring.



---

*Source: 4031626-2021-12-18.xml*