A Load-Balancing Divide-and-Conquer SVM Solver

作者：Chen, Xiaogang^*; Wang, Z. Jane; Ji, Xiangyang

来源：ACM Transactions on Embedded Computing Systems, 2017, 16(3): 74.

DOI：10.1145/3005347

• Kernel support vector machine
• divide-and-conquer solver
• load balancing

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 divideand-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.

• 出版日期2017-7
• 单位清华大学