X =
w
=
I
+ E E + (E
i
) E
i
- (E
d
) E
d
-1
E d + (E
i
) d
i
- (E
d
) d
d
,
(4)
where
d = De .
3
Incremental Proximal SVM for Multiple Classes
In the multicategorical classification case, the (incremental) class label vector d
i
consists of m
i
numeric labels in the range {0, . . . , c - 1}, where c is the number
of classes, as shown in (5).
X =
w
0
. . . w
c-1
0
. . .
c-1
= A
-1
B
(5)
3.1
The Naive approach
In order to apply the proximal SVM classifier in a "one-against-the-rest" manner,
the class labels must be transformed into vectors with +1 for the positive class
and -1 for the rest of the classes, that is, (cm
i
) operations in total, and later
(cm
i
n) for calculating (E
i
) d for each class. The latter (column) vectors are
collected in a matrix B R
(n+1)c
. Because the training features represented by
E
i
are the same for all the classes, it is enough to calculate A R
(n+1)
2
once,
giving (m
i
(n + 1)
2
+ (n + 1)
2
) operations for calculating (E
i
) E
i
and adding
it to
I
+ E E. The specifics are shown in shown in Algorithm 1.
Theorem 1. The running time complexity of Algorithm 1 is (cm
inc
n).
Proof. The conditional statement in lines 37 takes (1) time and is performed
m
inc
times (inner loop, lines 28) per iteration of classId (outer loop, line 1
10). Calculation of the matrix-vector product B[classId, ] in line 9 takes ((n +
1)m
inc
) per iteration of classId. This gives a total running time of
(c · (m
inc
+ m
inc
(n + 1))) = (cm
inc
n) .
110
Incremental Multicategory PSVM Classifiers