A fast-convergence distributed support vector machine in small-scale strongly connected networks

doi:10.1007/s11460-011-0172-9

Front Elect Electr Eng

2012, Vol. 7

Issue (2) : 216-223 https://doi.org/10.1007/s11460-011-0172-9

RESEARCH ARTICLE

A fast-convergence distributed support vector machine in small-scale strongly connected networks

Hua XU(

), Yun WEN, Jixiong WANG

State Key Laboratory of Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

Download: PDF(216 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In this paper, a fast-convergence distributed support vector machine (FDSVM) algorithm is proposed, aiming at efficiently solving the problem of distributed SVM training. Rather than exchanging information only among immediate neighbor sites, the proposed FDSVM employs a deterministic gossip protocol-based communication policy to accelerate diffusing information around the network, in which each site communicates with others in a flooding and iterative manner. This communication policy significantly reduces the total number of iterations, thus further speeding up the convergence of the algorithm. In addition, the proposed algorithm is proved to converge to the global optimum in finite steps over an arbitrary strongly connected network (SCN). Experiments on various benchmark data sets show that the proposed FDSVM consistently outperforms the related state-of-the-art approach for most networks, especially in the ring network, in terms of the total training time.

Keywords support vector machine message passing interface distributed computing parallel computing convergence speedup

Corresponding Author(s): XU Hua,Email:xuhua@mail.tsinghua.edu.cn

Issue Date: 05 June 2012

Cite this article:

Hua XU,Yun WEN,Jixiong WANG. A fast-convergence distributed support vector machine in small-scale strongly connected networks[J]. Front Elect Electr Eng, 2012, 7(2): 216-223.

URL:

https://academic.hep.com.cn/fee/EN/10.1007/s11460-011-0172-9
https://academic.hep.com.cn/fee/EN/Y2012/V7/I2/216

1	Vapnik V N. The Nature of Statistical Learning Theory. 2nd ed. New York: Springer, 2000
2	Lee C H, Yang H C. Construction of supervised and unsupervised learning systems for multilingual text categorization.Expert Systems with Applications , 2009, 36(2, Part 1): 2400-2410 doi: 10.1016/j.eswa.2007.12.052
3	Kim S K, Park Y J, Toh K A, Lee S. SVM-based feature extraction for face recognition.Pattern Recognition , 2010, 43(8): 2871-2881 doi: 10.1016/j.patcog.2010.03.008
4	Yu X, Cao J, Cai Y, Shi T, Li Y. Predicting rRNA-, RNA-, and DNA-binding proteins from primary structure with support vector machines.Journal of Theoretical Biology , 2006, 240(2): 175-184 doi: 10.1016/j.jtbi.2005.09.018
5	Joachims T. Making large-scale support vector machine learning practical. In: Sch?lkopf B, Burges C J C,Smola A J, eds. Advances in Kernel Methods: Support Vector Learning. Cambridge . USA: MIT Press, 1999, 169-184
6	Osuna E, Freund R, Girosi F. Training support vector machines: An application to face detection. In: Proceedings of 1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition . 1997, 130-136
7	Platt J C. Fast training of support vector machines using sequential minimal optimization. In: Sch?lkopf B, Burges C J C, Smola A J, eds. Advances in Kernel Methods: Support Vector Learning. Cambridge . USA: MIT Press, 1999, 185-208
8	Cao L J, Keerthi S S, Ong C J, Uvaraj P, Fu X J, Lee H P. Developing parallel sequential minimal optimization for fast training support vector machine.Neurocomputing , 2006, 70(1-3): 93-104 doi: 10.1016/j.neucom.2006.05.007
9	Zanghirati G, Zanni L. A parallel solver for large quadratic programs in training support vector machines.Parallel Computing , 2003, 29(4): 535-551 doi: 10.1016/S0167-8191(03)00021-8
10	Keerthi S S, Shevade S K, Bhattacharyya C, Murthy K R K. Improvements to Platt’s SMO algorithm for SVM classifier design.Neural Computation , 2001, 13(3): 637-649 doi: 10.1162/089976601300014493
11	Dong J X, Krzyzak A, Suen C Y. A fast parallel optimization for training support vector machine. In: Proceedings of the 3rd International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM’03) . Berlin: Springer-Verlag, 2003, 96-105
12	Jayadeva, Khemchandani R, Chandra S. Fast and robust learning through fuzzy linear proximal support vector machines.Neurocomputing , 2004, 61: 401-411 doi: 10.1016/j.neucom.2004.02.004
13	Syed N A, Liu H, Sung K K. Handling concept drifts in incremental learning with support vector machines. In: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’99) . New York: ACM, 1999, 317-321
14	Graf H P, Cosatto E, Bottou L, Durdanovic I, Vapnik V. Parallel support vector machines: The cascade SVM. In: Advances in Neural Information Processing Systems . Cambridge: MIT Press, 2005, 521-528
15	Wang L, Jia H. A parallel training algorithm of support vector machines based on the MTC architecture. In: Proceedings of 2008 IEEE Conference on Cybernetics and Intelligent Systems . 2008, 274-278
16	Lu Y, Roychowdhury V, Vandenberghe L. Distributed parallel support vector machines in strongly connected networks.IEEE Transactions on Neural Networks , 2008, 19(7): 1167-1178 doi: 10.1109/TNN.2007.2000061
17	Wang D, Zheng J, Zhou Y, Li J. A scalable support vector machine for distributed classification in ad hoc sensor networks. Neurocomputing , 2010, 74(1-3): 394-400 doi: 10.1016/j.neucom.2010.03.016
18	Tanenbaum A S, van Steen M. Distributed Systems: Principles and Paradigms. Pearson Prentice Hall , 2007
19	Voulgaris S, van Steen M. An epidemic protocol for managing routing tables in very large peer-to-peer networks. In: Brunner M, Keller A, eds. Self-Managing Distributed Systems . Berlin: Springer, 2004, 299-308
20	Chen J Y, Pandurangan G. Optimal gossip-based aggregate computation. In: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’10) . New York: ACM, 2010, 124-133
21	Liben-Nowell D. Gossip is synteny: Incomplete gossip and an exact algorithm for syntenic distance. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’01). Philadelphia , USA: Society for Industrial and Applied Mathematics, 2001, 177-185
22	Shah D. Gossip algorithms.Foundations and Trends in Networking , 2009, 3(1): 1-125 doi: 10.1561/1300000014

[1]	Yafeng WANG, Fuchun SUN, Huaping LIU, Dongfang YANG. Maximal terminal region approach for MPC using subsets sequence[J]. Front Elect Electr Eng, 2012, 7(2): 270-278.
[2]	Kun ZHOU. GPU parallel computing: Programming language, debugging tools and data structures[J]. Front Elect Electr Eng, 2012, 7(1): 5-15.
[3]	Lubin WANG, Hui SHEN, Baojuan LI, Dewen HU. Classification of schizophrenic patients and healthy controls using multiple spatially independent components of structural MRI data[J]. Front Elect Electr Eng Chin, 2011, 6(2): 353-362.
[4]	Xiaobo CHEN, Jian YANG. Optimal locality preserving least square support vector machine[J]. Front Elect Electr Eng Chin, 2011, 6(2): 201-207.
[5]	Bao-Liang LU, Xiao-Lin WANG, Yang YANG, Hai ZHAO. Learning from imbalanced data sets with a Min-Max modular support vector machine[J]. Front Elect Electr Eng Chin, 2011, 6(1): 56-71.
[6]	Na SUN, Yajian ZHOU, Yixian YANG. Consistency of weighted feature set and polyspectral kernels in individual communication transmitter identification[J]. Front Elect Electr Eng Chin, 2010, 5(4): 488-492.
[7]	Huanjun LIU. Empty glass bottle inspection method based on fuzzy support vector machine neural network and machine vision[J]. Front Elect Electr Eng Chin, 2010, 5(4): 430-440.
[8]	Ying CAO, Xin HAO, Xiaoen ZHU, Shunren XIA, . An adaptive region growing algorithm for breast masses in mammograms[J]. Front. Electr. Electron. Eng., 2010, 5(2): 128-136.
[9]	Rongyan WANG, Gang LIU, Jun GUO, Yu FANG, . Multi-class classifier of non-speech audio based on Fisher kernel[J]. Front. Electr. Electron. Eng., 2010, 5(1): 72-76.
[10]	Chenjian RAN, Zili DENG, Guili TAO, Jinfang LIU, . Convergence analysis of self-tuning Riccati equation for systems with correlation noises[J]. Front. Electr. Electron. Eng., 2009, 4(4): 409-416.
[11]	SUN Xiaojun, ZHANG Peng, DENG Zili. Self-tuning decoupled fusion Kalman filter based on the Riccati equation[J]. Front. Electr. Electron. Eng., 2008, 3(4): 459-464.
[12]	WANG Ying, GAO Xinbo. Mass detection algorithm based on support vector machine and relevance feedback[J]. Front. Electr. Electron. Eng., 2008, 3(3): 267-273.
[13]	WANG Yuanxin, PAN Weiyan, ZHANG Hongqi, FAN Wensheng. Spherical harmonic series solution of fields excited by vertical electric dipole in earth-ionosphere cavity[J]. Front. Electr. Electron. Eng., 2008, 3(1): 61-69.
[14]	WANG Yuanxin, PAN Weiyan, ZHANG Hongqi, FAN Wensheng. Spherical harmonic series solution of fields excited by vertical electric dipole in earth-ionosphere cavity[J]. Front. Electr. Electron. Eng., 2008, 3(1): 0-0.
[15]	JIN Ronghong, YUAN Zhihao, GENG Junping, FAN Yu, LI Jiajing. Pattern synthesis of antennas based on a modified particle swarm optimization algorithm[J]. Front. Electr. Electron. Eng., 2007, 2(4): 454-458.

Viewed

Full text

Abstract

Cited

Shared

Discussed