background image
6.2
Directions for Future Work
45
· Investigate efficient incremental support for non-linear kernels of the clas-
sifiers.
· Add incremental balancing mechanisms that can handle a class-wise unbal-
anced set of training examples.
· Add parallel support to any new features for the classifier algorithms.
· Investigate whether the linear systems involving symmetric positive def-
inite matrices used in the proposed classifiers can be transformed into a
Toeplitz-like (or Hankel-like) system. Introducing Toepliz-like systems can
potentially dramatically speed up the final matrix inversion or solution
of linear system that usually involves (n
3
) operations (where n is the
number of features of the classification examples). Due to the relation be-
tween matrix inversion and matrix multiplication (Cormen et al. [1990])
the matrix inversion process can potentially be reduced to (n
2.7
) opera-
tions using Strassen's method (Strassen [1969]) or even (n
2.36
) operations
using Winograd and Coppersmith's method (Coppersmith and Winograd
[1990]), these methods have unfortunately shown to be of little practical
use. For general complex and real matrices a lower bound for the size of
circuit any arithmetic circuit for the product of two matrices of (n
2
log n)
operations (Raz [2003]), so the question is: can the inverse or solution of
the linear system calculated faster than (n
2
log n) for the (non-general)
symmetric and positive definite matrices present in our proposed classifier
approaches. The requirement is probably that one can find a fast trans-
formation from symmetric positive definite matrix systems into a Toeplitz
system that can be solved in (n log n) operations, Chan and Ng [1996]. It
has been hypothesized that all matrices are equivalent to Toeplitz matrices
(Mackey et al. [1999]), counter examples falsifying that was presented by
Amdeberhan and Heinig [2003], but symmetric positive definite matrices
have not yet been proven to be different from Toeplitz matrices.

<< - < - > - >>