Kybernetika 53 no. 4, 595-611, 2017

Distributed classification learning based on nonlinear vector support machines for switching networks

Yinghui Wang, Peng Lin and Huashu QinDOI: 10.14736/kyb-2017-4-0595

Abstract:

In this paper, we discuss the distributed design for binary classification based on the nonlinear support vector machine in a time-varying multi-agent network when the training data sets are distributedly located and unavailable to all agents. In particular, the aim is to find a global large margin classifier and then enable each agent to classify any new input data into one of the two labels in the binary classification without sharing its all local data with other agents. We formulate the support vector machine problem into a distributed optimization problem in approximation and employ a distributed algorithm in a time-varying network to solve it. Our algorithm is a stochastic one with the high convergence rate and the low communication cost. With the jointly-connected connectivity condition, we analyze the consensus rate and the convergence rate of the given algorithm. Then some experimental results on various classification training data sets are also provided to illustrate the effectiveness of the given algorithm.

Keywords:

multi-agent system, distributed optimization, nonlinear support vector machine, connectivity

Classification:

68M15, 93A14

paper.pdf

References:

  1. R. Ali and B. Recht: Random features for large-scale kernel machines. In: Advances in Neural Information Processing System, MIT Press, Massachusetts 2008, pp. 1177-1184.   CrossRef
  2. S. Bernhard and A. J. Smola: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Massachusetts 2002.   CrossRef
  3. S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends{\textregistered} in Machine Learning 3 (2011), 1-122.   DOI:10.1561/2200000016
  4. C. C. Chang and C. J. Lin: LIBSVM: a library for support vector machines. JACM Trans. Intell. Systems Technol. 2 (2011), 1-27.   DOI:10.1145/1961189.1961199
  5. O. Chapelle: Training a support vector machine in the primal. Neural Computation 19 (2007), 1155-1178.   DOI:10.1162/neco.2007.19.5.1155
  6. O. Chapelle and A Zien: Semi-supervised classification by low density separation. In: Proc. International Conference on Artificial Intelligence and Statistics, Barbados 2005.   CrossRef
  7. C. Cortes and V. Vapnik: Support-vector networks. Machine Learning 20 (1995), 273-297.   DOI:10.1007/bf00994018
  8. P. Drineas and M. W. Mahoney: On the Nystr{ö}m method for approximating a Gram matrix for improved kernel-based learning. J. Machine Learning Research 6 (2005), 2153-2175.   CrossRef
  9. U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth and R. Uthurusamy: Advances in Knowledge Discovery and Data Mining. AAAI Press, Menlo Park 1996.   CrossRef
  10. K. Flouri, B. Beferull-Lozano and P. Tsakalides: Distributed consensus algorithms for SVM training in wireless sensor networks. In: 16th European Signal Processing Conference, Lausanne 2008.   DOI:10.1109/icdsp.2009.5201180
  11. P A. Forero, A. Cano and G. B. Giannakis: Consensus-based distributed support vector machines. J. Machine Learning Research 11 (2010), 1663-1707.   CrossRef
  12. V. Franc and S. Sonnenburg: Optimized cutting plane algorithm for support vector machines. In: Proc. 25th International Conference on Machine Learning, Helsinki 2008.   DOI:10.1145/1390156.1390197
  13. J. Hu: On robust consensus of multi-agent systems with communication delays. Kybernetika 45 (2009), 768-784.   CrossRef
  14. T. Joachims, T. Finley and C. J. Yu: Cutting-plane training of structural SVMs. Machine Learning 77 (2009), 27-59.   DOI:10.1007/s10994-009-5108-8
  15. S. Lee and S. J. Wright: Approximate Stochastic Sub-gradient Estimation Training for Support Vector Machines. In: Mathematical Methodologies in Pattern Recognition and Machine Learning, Springer, New York 2011, pp. 67-82.   DOI:10.1007/978-1-4614-5076-4_5
  16. Y. Lou, Y. Hong and S. Wang: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297.   DOI:10.1016/j.automatica.2016.02.019
  17. Y. Lu, V. Roychowdhury and L. Vandenberghe: Distributed parallel support vector machines in strongly connected networks. IEEE Trans. Neural Networks 19 (2008), 1167-1178.   DOI:10.1109/tnn.2007.2000061
  18. W. Kim, J. Park, J. Yoo, H. J. Kim and C. G. Park: Target localization using ensemble support vector regression in wireless sensor networks. IEEE Trans. Cybernetics 43 (2013), 1189-1198.   DOI:10.1109/tsmcb.2012.2226151
  19. W, Kim, M. S. Stankovi{ć}, K. H. Johansson and H.J. Kim:     CrossRef
  20. A. Nedic and O. Asuman: Distributed sub-gradient methods for multi-agent optimization. IEEE Trans. Automatic Control 54 (2009), 48-61.   DOI:10.1109/tac.2008.2009515
  21. J. C. Platt: Fast training of support vector machines using sequential minimal optimization. In: Advances in Kernel Methods, MIT Press, Massachusetts 1999, pp. 185-208.   CrossRef
  22. B. T. Polyak: Introduction to Optimization. Springer, New York 1987.   CrossRef
  23. R. Rifkin and A. Klautau: In defense of one-vs-all classification. J. Machine Learning Research 5 (2004), 101-141.   CrossRef
  24. S. Scardapane, R. Fierimonte, P. D. Lorenzo, M. Panella and A. Uncini: Distributed semi-supervised support vector machines. Neural Networks 80 (2016), 43-52.   DOI:10.1016/j.neunet.2016.04.007
  25. S. Shalev-Shwartz, Y. Singer and N. Srebro: Pegasos: Primal estimated sub-gradient solver for svm. In: Proc. 24th International Conference on Machine Learning, Oregon 2007.   DOI:10.1145/1273496.1273598
  26. S. Sra, S. Nowozin and S. J. Wright: Optimization for Machine Learning. MIT Press, Massachusetts 2012.   CrossRef
  27. X. Wang and Y. Chen: Quantized distributed output regulation of multi-agent systems. Kybernetika 52 (2016), 427-440.   DOI:10.14736/kyb-2016-3-0427
  28. J. Weston and C. Watkins: Support vector machines for multi-class pattern recognition. ESANN 99 (1999), 219-224.   CrossRef
  29. P. Yi and Y. Hong: Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme. Control Theory Technol. 13 (2015), 333-347.   DOI:10.1007/s11768-015-5100-8
  30. D. Yuan, D. W. C. Ho and Y. Hong: On Convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints. SIAM J. Control Optim. 54 (2016), 2872-2892.   DOI:10.1137/15m1048896