Fast SVM Trained by Divide-and-Conquer Anchors

Fast SVM Trained by Divide-and-Conquer Anchors

Meng Liu, Chang Xu, Chao Xu, Dacheng Tao

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 2322-2328. https://doi.org/10.24963/ijcai.2017/323

Supporting vector machine (SVM) is the most frequently used classifier for machine learning tasks. However, its training time could become cumbersome when the size of training data is very large. Thus, many kinds of representative subsets are chosen from the original dataset to reduce the training complexity. In this paper, we propose to choose the representative points which are noted as anchors obtained from non-negative matrix factorization (NMF) in a divide-and-conquer framework, and then use the anchors to train an approximate SVM. Our theoretical analysis shows that the solving the DCA-SVM can yield an approximate solution close to the primal SVM. Experimental results on multiple datasets demonstrate that our DCA-SVM is faster than the state-of-the-art algorithms without notably decreasing the accuracy of classification results.
Keywords:
Machine Learning: Classification
Machine Learning: Machine Learning