A Fast and Sparse Implementation of Multiclass Kernel Perceptron Algorithm.

Original multiclass kernel perceptron algorithm is time consuming in its training and discriminating procedures. In this paper, for each class its reduced kernel-based discriminant function is defined only by training samples from this class itself and a bias term, which means that except for bias terms the number of variables to be solved is always equal to the number of total training samples regardless of class number and the final discriminant functions are sparse. Such a strategy can speed up the training and discriminating procedures effectively. Further an additional iterative procedure with a decreasing learning rate is designed to improve the classification accuracy for the nonlinearly separable case. The experimental results on five benchmark datasets using ten-fold cross validation show that our modified training methods run at least two times and at most five times as fast as original algorithm does. [ABSTRACT FROM AUTHOR]