takes (1) time, giving a total for line 3 of (1) time per iteration of idx. idx is
iterated m
inc
times, giving a total of (m
inc
) time.
Algorithm 3 calcB Memo(E
inc
, d
inc
, E
inc
E
inc
)
Require: E
inc
R
m
inc
×(n+1)
, d
inc
{0, . . . , c - 1}
m
inc
and n, m
inc
N
Ensure: B R
(n+1)xc
, F R
(n+1)
1: classMap = buildClassMap(d
inc
)
2: for all classId in {0, . . . , c - 1} do
3:
B[classId, ] = E
inc
E
inc
[n]
4:
for all idx in classMap[classId, ] do
5:
B[idx, classId, ] = B[idx, classId, ] + 2 ·
n
j=0
E
inc
[idx , j]
6:
end for
7: end for
8: return B
Theorem 3. The running time complexity of Algorithm 3 is (n(c + m
inc
).
Proof. Calculation of classMap (line 1) takes (m
inc
) time (from Theorem 2).
Line 3 takes (n + 1) time per iteration of classId, giving a total of (c(n + 1)).
Because classMap provides a complete indexing (|
c-1
u=0
classMap[u]| = m
inc
) of
the class labels in d
inc
, and because there are no repeated occurrences of idx for
different classId s (
c-1
u=0
classMap[u] = ), line 5 will run a total of m
inc
times.
This gives a total running time of
(m
inc
+ (n + 1)m
inc
+ c(n + 1) + m
inc
)
= (n(c + m
inc
)) .
Corollary 1. Algorithms 1 and 3 calculate the same B if provided with the same
input.
4
Empirical Results
In order to test and compare the computational performance of the incremental
multicategory proximal SVMs with the naive and lazy algorithms, we have used
three main types of data:
1. Forest cover type, 580012 training examples, 7 classes and 54 features (from
UCI KDD Archive [7])
2. Synthetic datasets with a large number of classes (up to 1000 classes) and
30 features
112
Incremental Multicategory PSVM Classifiers