Exploring Data Reduction Techniques for Time Efficient Support Vector Machine Classifiers

摘要

Support Vector Machines [1] (SVMs) are regarded as powerful machine learning tool because of their inherent properties. However, one major challenge for using SVMs in real-world applications with large datasets is its high training time complexity. Over the years, many variants of SVM have been proposed to reduce the training time by either using algorithmic modifications (such as LS-SVM [3], GEP-SVM [4], TWSVM [5]) or training level speed-ups (such as SMO [6], SOR [2] and Stochastic Gradient Descent method [7]). However, these methods deal with the entire data for learning a classifier model, thus the space complexity could be a challenge. A more fitting approach is to use an Instance Selection method (IS) which selects a subset of data which is best representative of the underlying data distribution. Since SVMs by definition use the geometry of patterns for classification, this study explores the effects of different Instance Selection methods on different variants of SVM to check their effectiveness using their comparative performances in terms of training time and generalization ability. Various theoretical and experimental comparisons on standard datasets have been provided to validate the efficacy of different IS methods on SVM based classifiers.