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.

Key words： support vector machine; message passing interface; distributed computing; parallel computing; convergence; speedup

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

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