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

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

References

[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

[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

[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

[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

[9] Zanghirati G, Zanni L. A parallel solver for large quadratic programs in training support vector machines.Parallel Computing, 2003, 29(4): 535-551

[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

[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

[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

[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

[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

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 60875073 and 61175110), the National Key Technology R&D Program of China (Grant No. 2009BAG12A08), and the National S&T Major Projects of China (Grant No. 2009ZX02001, 2011ZX02101).

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg