K-Times Markov Sampling for SVMC

Support vector machine (SVM) is one of the most widely used learning algorithms for classification problems. Although SVM has good performance in practical applications, it has high algorithmic complexity as the size of training samples is large. In this paper, we introduce SVM classification (SVMC) algorithm based on k-times Markov sampling and present the numerical studies on the learning performance of SVMC with k-times Markov sampling for benchmark data sets. The experimental results show that the SVMC algorithm with k-times Markov sampling not only have smaller misclassification rates, less time of sampling and training, but also the obtained classifier is more sparse compared with the classical SVMC and the previously known SVMC algorithm based on Markov sampling. We also give some discussions on the performance of SVMC with k-times Markov sampling for the case of unbalanced training samples and large-scale training samples.