# A New SVM Multiclass Incremental Learning Algorithm

Authors: Yuping Qin; Dan Li; Aihua Zhang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A new support vector machine (SVM) multiclass incremental learning algorithm is proposed. To each class training sample, the hyperellipsoidal classifier that includes as many samples as possible and pushes the outlier samples away is trained in the feature space. When the new samples are added to the classification system, the algorithm reuses the old classifiers that have nothing to do with the new sample classes. To be classified sample, the Mahalanobis distances are used to decide the class of classified sample. If the sample point is not surrounded by any hyperellipsoidal or is surrounded by more than one hyperellipsoidal, the membership is used to confirm its class. The experimental results show that the algorithm has higher performance in classification precision and classification speed.


---

## Body

## 1. Introduction

SVMs [1], as a new machine learning method based on statistical learning theory, deliver state-of-the-art performance in real world pattern recognition [2, 3] and data mining applications such as text categorization, hand-written character recognition, image classification, and bioinformatics, even into control field [4, 5]. However, the general training method of SVMs will not work when the amount of training samples is too large to be put into the RAM of computer. In order to solve this problem and improve the speed of training SVMs, the incremental learning algorithm has become one of the key techniques for training SVMs on large data sets, especially on multiclass problem.When using SVMs to deal with multiclassification problems, the most popular four approaches are one-against-one [6], one-against-rest [7], DAGSVM [8], and binary tree SVM [9–11]. Some incremental learning algorithms have been proposed, such as Batch SVM [12, 13], online recursive algorithm [14], divisional training SVMs algorithm [15], and fast incremental learning algorithm [16]. However, these multiclassification approaches are based on binary classifiers, when new samples were added to the classification system, the whole model of the classifier must be retrained. Reference [17] proposed a class-incremental learning algorithm. The algorithm reuses the old models of the classifier, and only one binary classifier is trained when a new class comes. But it is not suitable for large data set, and new sample set can not include the old class samples. Reference [18] proposed a multiclass incremental learning algorithm based on hypersphere SVMs (HSSVMIL). The algorithm reuses the old models of the classifier, and it is suitable to class-incremental learning and old class sample-incremental learning at the same time. But the distribution of every class sample must be hypersphere shape and the density of the samples is higher in the feature space. Otherwise, the precision of the algorithm is lower. For the disadvantage, [19] proposed a multiclass incremental learning algorithm based on hyper ellipsoidal (HEIL), but the algorithm does not consider the influence of the outlier samples.In this paper, a Mahalanobis hyperellipsoidal SVM multiclass incremental learning algorithm (MSVMIL) is proposed. To every class sample, the smallest hyperellipsoidal that contains as much samples as possible and pushes the outlier samples away is trained in the feature space. Mahalanobis distances are used to confirm the class of classified sample.This paper is organized as follows. In Section2, a review of hypersphere SVM is given. In Section 3, a new multiclass incremental learning algorithm is discussed in detail. In Section 4, experimental results are given on Reuters 21578. Finally, conclusion is outlined.


## 2. Hyperellipsoidal Support Vector Machine

Given a set of training sample of a classX
=
x
i
i
=
1
N, where x
i
∈
R
d. Let M be a d
×
N sample matrix. Training a hyperellipsoidal E
(
a
,
R
) in the feature space, where a is the center of the hyperellipsoidal and R is the radius of the hyperellipsoidal. The hyperellipsoidal should contain most of the samples and the radius R is as small as possible. If there are not remote points, then the hyperellipsoidal will contain all samples. If there are remote points, then some samples outside the hyperellipsoidal are allowed, training the smallest hyperellipsoidal that contains most of the samples. When we are uncertain whether there are remote points, nonnegative slack variables ξ
i
(
i
=
1,2
,
…
,
N
) are introduced to allow some samples outside the hyperellipsoidal. Using the method is similar to finding optimal hyperplane to obtain the smallest hyperellipsoidal [19–21]. The formulation is as follows:(1)
m
i
n
a
,
R
,
ξ
i
R
2
+
C
∑
i
=
1
N
ξ
i
s
.
t
.
k
x
i
-
a
T
Σ
-
1
x
i
-
a
≤
R
2
+
ξ
i
k
ξ
i
≥
0
,
i
=
1,2
,
…
,
N
,where C is used to compromise the number of noises out of hyperellipsoidal and the radius of hyperellipsoidal, Σ is covariance matrix of the samples.To solve the optimization problem above, one can construct the Lagrange function as follows:(2)
L
R
,
a
,
β
,
γ
,
ξ
i
=
R
2
+
C
∑
i
=
1
N
ξ
i
-
∑
i
=
1
N
α
i
R
2
+
ξ
i
-
x
i
-
a
T
Σ
-
1
x
i
-
a
-
∑
i
=
1
N
β
i
ξ
i
,where α
i  (
α
i
≥
0
) and β
i  (
β
i
≥
0
) are the Lagrange multipliers.According to the Kuhn-Tucker Theorem (KKT) in optimization theory, the following conditions are satisfied:(3)
∂
L
∂
R
=
2
R
1
-
∑
i
=
1
N
α
i
=
0
⟹
∑
i
=
1
N
α
i
=
1
,
∂
L
∂
ξ
i
=
C
-
α
i
-
β
i
=
0
⟹
0
≤
α
i
≤
C
,
∂
L
∂
a
=
-
∑
i
=
1
N
2
α
i
x
i
-
a
=
0
⟹
a
=
∑
i
=
1
N
α
i
x
i
.Substituting (3) into (2), the dual optimal problem is obtained as follows:(4)
m
a
x
α
i
≥
0
∑
i
=
1
N
α
i
x
i
T
Σ
-
1
x
i
-
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
x
i
T
Σ
-
1
x
j
s
.
t
.
k
∑
i
=
1
N
α
i
=
1
0
≤
α
i
≤
C
,
i
=
1,2
,
…
,
N
.The kernel form of (4) is as follows:(5)
m
a
x
α
i
≥
0
∑
i
=
1
N
α
i
k
x
i
,
M
Q
T
Ω
-
2
Q
k
x
i
,
M
T
-
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
k
x
i
,
M
Q
T
Ω
-
2
Q
k
x
j
,
M
T
s
.
t
.
k
∑
i
=
1
N
α
i
=
1
0
≤
α
i
≤
C
,
i
=
1,2
,
…
,
N
,where K
(
·
) is kernel function, via K
x
i
,
x
j
=
g
(
x
i
)
T
g
(
x
j
).The examples that lie outside or on the margin are the correspondingα
i nonzero. These examples are called support vectors.The center of the smallest hyperellipsoidala can be obtained by (6). Consider(6)
a
=
∑
i
α
i
g
x
i
.The Mahalanobis distance from samplex to the center of hyperellipsoidal is as follows:(7)
m
d
x
,
a
=
g
x
-
a
T
Σ
-
1
g
x
-
a
=
N
k
x
,
M
-
∑
i
=
1
N
α
i
k
x
i
,
M
×
Q
T
Ω
-
2
Q
k
x
,
M
-
∑
i
=
1
N
α
i
k
x
i
,
M
1
/
2
.The radius of the smallest hyperellipsoidalR can be determined by (8), via KKT conditions. Consider(8)
m
d
x
,
a
<
R
α
i
=
0
,
m
d
x
,
a
=
R
0
<
α
i
<
C
,
m
d
x
,
a
>
R
α
i
=
C
.Remark 1.
Mahalanobis distance denotes the distance between a data point and multivariate space centroid, that is, overall mean value.


## 3. Multiclass Incremental Learning Algorithm

Given a set of training samplesX
=
x
i
,
T
i
i
=
1
l and kernel function K
·. Where l is the number of samples, x
i
∈
R
n,  T
i
∈
{
1,2
,
…
,
N
},  N is the number of classes. K
· corresponds to inner product in feature space, namely, K
x
i
,
x
j
=
g
(
x
i
)
T
g
(
x
j
).Assume thatX
m  (
m
=
1,2
,
…
,
N
) is a subset of A, and all samples in X
m belong to the mth class. For every subset X
m, train the smallest hyperellipsoidal E
a
m
,
R
m in feature space, where a
m is the center of the hyperellipsoidal, R
m is the radius of the hyperellipsoidal. S
V
m is the support vector set.If there is a new sample setN
X is added to the old classification system, where N
X
m  (
m
=
1,2
,
…
,
N
,
N
+
1
,
…
,
N
N
) is a subset of N
X and all samples of N
X
m belong to the mth class. The multiclass incremental learning algorithm based on hyperellipsoidal SVM is described in detail as follows.Step 1.
For every subsetN
X
m  (
m
=
N
+
1
,
N
+
2
,
…
,
N
N
), let X
m
=
N
X
m, training the smallest hyperellipsoidal E
a
m
,
R
m with X
m in the feature space and saving support vectors to S
V
m.Step 2.
For every subsetN
X
m  (
q
=
1,2
,
…
,
N
), if N
X
m
≠
Φ, then X
m
=
N
X
m
+
S
V
m, retraining the hyperellipsoidal E
a
m
,
R
m with X
m in the feature space and refining S
V
m.For the classified samplex, compute the Mahalanobis distances m
d
(
x
,
a
m
)  (
m
=
1,2
,
…
,
N
N
) according to (7) in the feature space.If there is not hyperellipsoidal containing the sample point, viam
d
(
x
,
a
m
)
>
R
m  (
m
=
1,2
,
…
,
N
N
), then compute the membership that the sample belongs to the mth class according to (9) and then confirm the class of the sample according to (10). Consider(9)
r
m
=
R
m
m
d
x
,
a
m
,
(10)
c
l
a
s
s
=
a
r
g
m
i
n
i
r
i
.If there are no less than two hyperellipsoidals containing the sample point, compute the membership that the sample belongs to themth class according to (11) for m
d
(
x
,
a
m
)
≤
R
m firstly and then confirm the class of the sample according to (10). One has(11)
r
m
=
1
-
m
d
x
,
a
m
R
m
.For the classified amplex, the multiclass classification algorithm is described as follows.Step 1.
Computem
d
(
x
,
a
m
)  (
m
=
1,2
,
…
,
N
N
) according to (7).Step 2.
If the sample point is contained by only one hyperellipsoidalE
a
m
,
R
m, the sample belongs to the mth class; go to Step 5. Otherwise, go to Step 3.Step 3.
If the sample point is not contained by any hyperellipsoidal, compute the membership that the sample belongs to themth (
m
=
1,2
,
…
,
N
N
) class according to (9) and then confirm the class of the sample according to (10); go to Step 5; otherwise, go to Step 4.Step 4.
If the sample point is contained by no less than two hyperellipsoidalsE
a
m
,
R
m  (
m
∈
1,2
,
…
,
N
N
), then compute the membership that the sample belongs to themth class according to (11) and then confirm the class of the sample according to (10); go to Step 5.Step 5.
End.


## 4. Experiments

Experiments are made on Reuters 21578, in which five categories and 2302 texts are used. 1536 texts are used as training set, and the rest are used as testing set (see Table1). Information gain is used to reduce feature dimension and the weight of every word is computed according to TF-IDF.Table 1
Training set and testing set.
Class
Acq
Eran
Grain
Crude
Trade
Class code
1
2
3
4
5
Original
Training
403
134
0
0
0
Testing
201
67
0
0
0
1st increment
Training
200
98
82
0
0
Testing
100
49
41
0
0
2nd increment
Training
101
68
44
55
0
Testing
51
34
22
31
0
3rd increment
Training
100
42
0
33
50
Testing
50
21
0
11
25To verify the efficiency of the proposed method, the same task is realized by using HSSVMIL, HEIL, and MSVMIL. The computational experiments were done on a Pentium 1.6 G with 512 MB memory. Kernel function is radial basis function (RBF)K
(
x
,
y
)
=
e
-
γ
x
-
y
2, where γ
=
0.01. Penalty parameter of MSVMIL C
=
100. System parameter of HSSVMIL v
=
0.1.The macroaverage precision (MAAP), macroaverage recall (MAAR), and macroaverageF
1 (MAAF) are used to evaluate the classification performance of the algorithms. Defined as follows:(12)
M
a
c
r
o
A
v
e
r
a
g
e
P
r
e
c
i
s
i
o
n
M
A
A
P
=
∑
i
=
1
N
P
i
N
,
M
a
c
r
o
A
v
e
r
a
g
e
R
e
c
a
l
l
M
I
A
R
=
∑
i
=
1
N
R
i
N
,
M
a
c
r
o
A
v
e
r
a
g
e
F
1
M
A
A
F
=
∑
i
=
1
N
F
1
i
N
,where N is the number of classes, P
i is the precision of the ith class sample, R
i is the recall of ith class sample, and F
1
i is the F
1 value of ith class sample.In experiments, the original dataset includes two class samples (Acq and Eran), and three times incremental learning are done. The first incremental samples include three classes (Acq, Eran, and Grain). The second incremental samples include four class samples (Acq, Eran, Grain, and Crude). The third incremental samples include four class samples (Acq, Eran, Crude, and Trade). The Macroaverage precision, macroaverage recall, and macroaverageF
1 of three algorithms are given in Table 2. The training time and testing time of three algorithms are given in Table 3.Table 2
MAAP, MAAR, and MAAF OF three algorithms.
Learning
Algorithm
MAAP (%)
MAAR (%)
MAAF (%)
Original
SSVMIL
79.41
80.23
79.54
HEIL
81.58
83.44
82.79
MSVMIL
84.73
85.62
85.57
1st increment
SSVMIL
82.86
77.77
80.32
HEIL
84.73
82.86
83.41
MSVMIL
86.82
85.78
85.61
2nd increment
SSVMIL
80.46
78.85
79.60
HEIL
82.62
81.58
82.12
MSVMIL
86.30
86.81
86.44
3rd increment
SSVMIL
81.28
79.83
80.79
HEIL
84.53
82.64
83.71
MSVMIL
86.29
85.75
85.85Table 3
Training time and testing time of three algorithms.
Learning
Algorithm
Training time (ms)
Testing time (ms)
Original
SSVMIL
157
187
HEIL
166
154
MSVMIL
159
162
1st increment
SSVMIL
141
129
HEIL
167
115
MSVMIL
143
118
2nd increment
SSVMIL
140
125
HEIL
158
102
MSVMIL
142
104
3rd increment
SSVMIL
156
127
HEIL
179
112
MSVMIL
158
114The experimental results show that the classification precision and recall of MSVMIL are higher than HEIL and MSVMIL. The main reasons are that MSVMIL reduced the volume that surrounds sample points by pushing the outlier samples away and considered the distribution of samples by using Mahalanobis distance. The classification speed of MSVMIL is faster than SSVMIL and is equal basically to HEIL. The training speed of MSVMIL is faster than HEIL and is equal basically to SSVMIL.


## 5. Conclusion

To solve SVM multiclass incremental learning problem, a novel algorithm based on Mahalanobis hyperellipsoidal SVM is proposed. In the process of incremental learning, only the new samples and the old class support vectors that its class exist in the new samples take part in the training. The history classifiers that have nothing to do with the new samples are reused. In the process of classification, the Mahalanobis distance is used to confirm the classified sample class. The experimental results show, compared with HEIL and SSVMIL, the proposed algorithm has a higher performance in classification precision and classification speed. In fact, data driven [22, 23] is another worth-thinking method, and this idea would be presented in the further work.



---

*Source: 745815-2015-05-21.xml*