A Load-Balancing Divide-and-Conquer SVM Solver
Authors:
Open Access
- 9 May 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 16 (3) , 1-10
Abstract
Scaling up kernel support vector machine (SVM) training has been an important topic in recent years. Despite its theoretical elegance, training kernel SVM is impractical when facing millions of data. The divide-and-conquer (DC) strategy is a natural framework of handling gigantic problems, and the divide-and-conquer solver for kernel SVM (DC-SVM) is able to train kernel SVM with millions of data with limited time cost. However, there are some drawbacks of the DC-SVM approach. First, it used an unsupervised clustering method to partition the whole problem, which is prone to construct singular subsets, and, second, it is hard to balance the computation load between sub-problems. To address these issues, this article proposed a load-balancing partition method for kernel SVM. First, it clusters sample from one class and then assigns data samples to the cluster centers by a distance measure and construct sub-problems; in this way, it is able to control the computation load and avoid singular problems. Experimental results show that the proposed method has better load-balancing performance than DC-SVM, which implies that it is suitable for distributed and embedding systems.Keywords
This publication has 9 references indexed in Scilit:
- CA-SVM: Communication-Avoiding Support Vector Machines on Distributed Systems2015
- Kernel methods match Deep Neural Networks on TIMIT2014
- Kernel Methods and Machine Learning2014
- LIBSVMACM Transactions on Intelligent Systems and Technology, 2011
- CombNET-III: A Support Vector Machine Based Large Scale Classifier with Probabilistic FrameworkIEICE Transactions on Information and Systems, 2006
- Approximating a Gram Matrix for Improved Kernel-Based Learning2005
- A Parallel Mixture of SVMs for Very Large Scale ProblemsNeural Computation, 2002
- Learning with Kernels2001
- Support-Vector NetworksMachine Learning, 1995