# A Mahalanobis Hyperellipsoidal Learning Machine Class Incremental Learning Algorithm

Authors: Yuping Qin; Hamid Reza Karimi; Dan Li; Shuxian Lun; Aihua Zhang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

A Mahalanobis hyperellipsoidal learning machine class incremental learning algorithm is proposed. To each class sample, the hyperellipsoidal that encloses as many as possible and pushes the outlier samples away is trained in the feature space. In the process of incremental learning, only one subclassifier is trained with the new class samples. The old models of the classifier are not influenced and can be reused. In the process of classification, considering the information of sample’s distribution in the feature space, the Mahalanobis distances from the sample mapping to the center of each hyperellipsoidal are used to decide the classified sample class. The experimental results show that the proposed method has higher classification precision and classification speed.


---

## Body

## 1. Introduction

Incremental learning is an intelligent technology of data mining and knowledge discovery. There are already some key methods of incremental learning, such as KNN, principal component analysis, Bayesian network, and Boosting and support vector machines (SVM), and this idea in the control theory, such as data driven [1–5], promotes the development of control method. Among these methods, SVM has a good generalization performance, because it does not depend on all the training data, but a subset named support vector. The number of support vectors is very small compared with the training data set, so SVM is a powerful tool to the incremental learning.Many incremental learning algorithms based on SVM have been proposed, and they received better results, such as the incremental learning Batch SVM [6, 7], on-line recursive algorithm [8], divisional training SVM algorithm [9], fast incremental learning algorithm [10], and α-SVM algorithm [11]. However, these algorithms are only suitable to the case that the new incremental samples belong to old classes. When a new class was added to the classification system, the above methods could not be fully accommodated to this situation and the old models became useless. Reference [12] proposed a class incremental learning algorithm. The algorithm reuses the old models of the classifier and trains only one binary subclassifier when a new class comes. But it is not suitable to large data set, because all samples participate in the training in the process of each incremental learning. For the disadvantage, [13] proposed a class incremental learning algorithm based on hyper sphere support vector machine (HS-CIL), but the algorithm is only suitable to the case that the sample’s distribution is hyper sphere shaped and the density is higher. For the disadvantage, [14] proposed a hyperellipsoidal class incremental learning algorithm (HE-CIL), but the algorithm does not consider the influence of the outlier samples. Therefore, a Mahalanobis hyperellipsoidal learning machine class incremental learning algorithm (MHE-CIL) is proposed in this paper. To every class sample, the smallest hyperellipsoidal that encloses as much samples as possible and pushes the outlier samples away is trained in the feature space. Mahalanobis distances are used to confirm the classified sample class.The rest of this paper is organized as follows. In Section2, a brief review of Mahalanobis hyperellipsoidal learning machine is given. In Section 3, a new Mahalanobis hyperellipsoidal learning machine class incremental learning algorithm is discussed in detail. In Section 4, experimental results are given on Reuters 21578. Finally, conclusion is outlined in Section 5.


## 2. Mahalanobis Hyperellipsoidal Learning Machine

Given a set of training samples of a class{
x
i
}
i
=
1
N, where x
i
∈
R
d and N is the number of samples, let X be a d
×
N sample matrix. Training a Mahalanobis 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 encloses most of the mappings of sample and the radius R is as small as possible. If there are no remote points, then the hyperellipsoidal will enclose all the mappings of sample. If there are remote points, allowing part of the samples outside of the superellipsoid, and searching for the smallest superellipsoid which can surround the most samples. When we are uncertain whether there are remote points, nonnegative slack variables ξ
i
(
i
=
1,2
,
…
,
N
) are introduced to allow some of the mappings of sample outside the hyperellipsoidal. Using the method that is similar to finding optimal hyperplane of SVM to obtain the smallest hyperellipsoidal [15–17], the formulation is as follows:
(1)
min
⁡
a
,
R
,
ξ
i
R
2
+
C
∑
i
=
1
N
ξ
i
s
.
t
.
(
x
i
-
a
)
T
Σ
-
1
(
x
i
-
a
)
≤
R
2
+
ξ
i
f
f
f
f
f
f
f
f
f
f
f
i
f
ξ
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 and Σ
-
1 is the inverse of the covariance matrix Σ.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
≥
0 and β
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)
max
⁡
α
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
.
∑
i
=
1
N
α
i
=
1
0
≤
α
i
≤
C
,
i
=
1,2
,
…
,
N
.The kernel form of (4) is as follows:
(5)
max
⁡
α
i
≥
0
∑
i
=
1
N
α
i
k
(
x
i
,
X
)
Q
T
Ω
-
2
Q
k
(
x
i
,
X
)
T
-
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
k
(
x
i
,
X
)
Q
T
Ω
-
2
Q
k
(
x
j
,
X
)
T
s
.
t
.
∑
i
=
1
N
α
i
=
1
0
≤
α
i
≤
C
,
i
=
1,2
,
…
,
N
,
where K
(
·
) is kernel function and 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 as follows:
(6)
a
=
∑
i
α
i
g
(
x
i
)
.The square kernel Mahalanobis distance from the mappingg
(
x
) of sample x to the center a of the hyperellipsoidal in the feature space is defined as follows:
(7)
d
2
(
g
(
x
)
,
a
)
=
(
g
(
x
)
-
a
)
T
Σ
-
1
(
g
(
x
)
-
a
)
=
N
(
k
(
x
,
X
)
-
∑
i
=
1
N
α
i
k
(
x
i
,
X
)
)
Q
T
Ω
-
2
×
Q
(
k
(
x
,
X
)
-
∑
i
=
1
N
α
i
k
(
x
i
,
X
)
)
.The radius of the smallest hyperellipsoidalR can be determined by (7), via KKT conditions as follows:
(8)
d
2
(
x
,
a
)
<
R
2
α
i
=
0
,
d
2
(
x
,
a
)
=
R
2
0
<
α
i
<
C
,
d
2
(
x
,
a
)
>
R
2
α
i
=
C
.


## 3. Incremental Learning Algorithm

We give a set of training samplesA
=
{
x
i
,
E
i
}
i
=
1
l and kernel function K
(
·
), where x
i
∈
R
n, E
i
∈
{
1,2
,
…
,
N
}, N is the number of class of the training set A, l is the number of training samples, and K corresponds to inner product in feature space, namely, K
(
x
i
,
x
j
)
=
g
(
x
i
)
T
g
(
x
j
).Assume thatA
m is a subset of training samples A, where all the samples of the subset A
m belong to the mth class (
m
=
1,2
,
…
,
N
). For every subset A
m, the smallest hyperellipsoidal E
(
a
m
,
R
m
) is trained in feature space, where a
m is the center of the hyperellipsoidal and R
m is the radius of the hyperellipsoidal.If a new class, which definedB, is generated, training the smallest hyper ellipsoidal E
(
a
N
+
1
,
R
N
+
1
) in the feature space, and adding the classifier to old models. One time incremental learning is finished.For the samplex to be classified, compute the Mahalanobis distance from the mapping g
(
x
) of the sample x to the center a
m of the hyperellipsoidal according to (7).If alld
m
(
g
(
x
)
,
a
m
) satisfy d
m
(
g
(
x
)
,
a
m
)
>
R
m
(
m
=
1,2
,
…
,
N
), and there is no hyperellipsoidal that encloses the mapping g
(
x
) of the sample x, then compute the membership that the sample x belongs to the mth class according to (9) and then confirm the class of sample x as follows:
(9)
r
m
=
R
m
d
m
(
g
(
x
)
,
a
m
)
,
(10)
class
=
arg
max
⁡
i
r
i
.If there are no less than twod
m
(
g
(
x
)
,
a
m
)
(
m
∈
{
1,2
,
…
,
N
}
) that satisfy d
m
(
g
(
x
)
,
a
m
)
≤
R
m, then compute the membership that the sample x belongs to the mth class according to (11) and then confirm the class of sample x as follows:
(11)
r
i
=
1
-
d
(
g
(
x
)
,
a
m
)
R
m
.For the samplex to be classified, the classification algorithm is described in detail as follows.Step 1.
Computingd
m
(
g
(
x
)
,
a
m
)
(
m
=
1,2
,
…
,
N
) according to (7).Step 2.
If only oned
m
(
g
(
x
)
,
a
m
)
(
m
∈
{
1,2
,
…
,
N
}
) satisfies d
m
(
g
(
x
)
,
a
m
)
≤
R
m, then the sample belongs to the mth class; go to Step 5; otherwise go to Step 3.Step 3.
If alld
m
(
g
(
x
)
,
a
m
)
(
m
=
1,2
,
…
,
N
) satisfy d
m
(
g
(
x
)
,
a
m
)
>
R
m, then compute the membership that the sample x belongs to the mth class according to (9) and then confirm the class of sample x by (10) and go to Step 5; otherwise go to Step 4.Step 4.
If more than oned
m
(
g
(
x
)
,
a
m
)
(
m
∈
{
1,2
,
…
,
N
}
) satisfies d
m
(
g
(
x
)
,
a
m
)
≤
R
m, then compute the membership that the sample x belongs to the mth class according to (11) and then confirm the class of sample x by (10).Step 5.
End.


## 4. Experiments

Experiments are made on Reuters 21578, in which five categories and 896 texts are used. 598 texts are used as training set, and the rest 298 texts 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.
Sample
Wheat
Corn
Coffee
Soybean
Cocoa
Class code
1
2
3
4
5
Training set
204
168
97
79
50
Texting set
101
84
48
40
25To verify the efficiency of the proposed method, the same tasks are realized by using HS-CIL, HE-CIL, and MHE-CIL methods. The computational experiments were done on a Pentium 1.6 G with 512 MB memory. Liner kernel function is used for all the experiments. System parameterC
=
10, v
=
0.01.The macroaverage precision (MAAP), macro average recall (MAAR), and macroaverageF
1 (MAAF) [18] are used to evaluate the classification performance of the algorithm.In experiments, the original sample set includes two class samples (wheat and corn). Three times class incremental learning is done; the first time increment is the third class sample (coffee), the second time increment is the forth class sample (soybean), and the third time increment is the fifth class sample (cocoa). The macroaverage precision, macroaverage recall, and macroaverageF
1 value of three algorithms are given in Table 2. The training time and testing time of three algorithms are given in Table 3.Table 2
The comparison of MAAP, MAAR, and MAAF.
Learning
Algorithm
MAAP (%)
MAAR (%)
MAAF (%)
Original
HS-CIL
72.76
72.84
72.79
HE-CIL
76.92
74.52
75.18
MHE-CIL
78.76
76.64
77.82
1st increment
HS-CIL
79.75
78.09
78.85
HE-CIL
80.00
78.53
79.26
MHE-CIL
81.75
79.73
80.39
2nd increment
HS-CIL
74.97
71.53
73.21
HE-CIL
82.56
78.72
80.11
MHE-CIL
83.72
79.63
81.66
3rd increment
HS-CIL
76.64
73.47
75.02
HE-CIL
81.41
76.61
78.40
MHE-CIL
83.56
78.31
81.84Table 3
The comparison of training time and testing time.
Learning
Algorithm
Training times (ms)
Testing times (ms)
Original
HS-CIL
110
94
HE-CIL
126
83
MHE-CIL
112
88
1st increment
HS-CIL
15
140
HE-CIL
33
132
MHE-CIL
16
135
2nd increment
HS-CIL
32
157
HE-CIL
36
161
MHE-CIL
33
158
3rd increment
HS-CIL
31
204
HE-CIL
48
185
MHE-CIL
32
187The experimental results show the precision, the recall, and theF
1 value of MHE-CIL method which are obviously higher than the other two methods. The key reasons are that MHE-CIL method reduces the space that hyperellipsoidal encloses by pushing the outlier samples away, and the information of sample’s distribution is considered by using Mahalanobis distance. The training time of MHE-CIL method is faster compared with HE-CIL method, and it is nearly the same as HS-CIL method. The classification speed of MHE-CIL method is faster compared with HE-CIL method, and it is nearly the same as HE-CIL method.


## 5. Conclusion

A novel class incremental learning algorithm is proposed. In the process of class incremental learning, only the new class samples participate in training and the old models of the classifier can be reused. In the process of classification, the Mahalanobis distance is used to confirm the class of classified sample, and the information of the sample’s distribution in the feature space is considered. The experimental results show that the proposed algorithm not only improves classification accuracy obviously, but also ensures training speed and classification speed. How to use kernel function theory to increase the density of the samples would be our research work in the future.



---

*Source: 894246-2014-02-11.xml*