Fast online algorithms for Support Vector Machines

摘要

A novel online, i.e. stochastic gradient, learning algorithm in a primal domain is introduced and its performance is compared to the Sequential Minimal Optimization (SMO) based algorithm for training L1 Support Vector Machines (SVMs) implemented within MATLAB's SVM solver fitcsvm. Their performances are compared on both real and artificial datasets, which contain up to 15,000 samples. These datasets belong to the small and medium class of datasets today. We have shown that classic online learning algorithms implemented in the primal domain can be both extremely efficient and faster up to two orders of magnitude in respect to the SMO algorithm. In particular, unlike the SMO algorithm, our simulations show that the CPU time of OL SVM does not depend on SVM design parameters (penalty parameter C and Gaussian kernel shape parameter s or on the order of the polynomial kernel). This property is very beneficial for the SVMs' training faced with large and ultra-large datasets. Paper also compares OL SVM with the established stochastic gradient algorithms, Norma and a novel version of an online SVM training algorithm Pegasos dubbed here Pegaz.