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

Wang, Yinghui ; Lin, Peng ; Qin, Huashu

Kybernetika, Tome 53 (2017) no. 4, pp. 595-611

Abstract (VO)

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.

Détail

DOI : 10.14736/kyb-2017-4-0595

Classification : 68M15, 93A14
Keywords: nonlinear support vector machine; multi-agent system; distributed optimization; connectivity

Bibliographie

[1] Ali, R., Recht, B.: Random features for large-scale kernel machines. In: Advances in Neural Information Processing System, MIT Press, Massachusetts 2008, pp. 1177-1184.

[2] Bernhard, S., Smola, A. J.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Massachusetts 2002.

[3] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning 3 (2011), 1-122. | DOI

[4] Chang, C. C., Lin, C. J.: LIBSVM: a library for support vector machines. JACM Trans. Intell. Systems Technol. 2 (2011), 1-27. | DOI

[5] Chapelle, O.: Training a support vector machine in the primal. Neural Computation 19 (2007), 1155-1178. | DOI | MR

[6] Chapelle, O., Zien, A: Semi-supervised classification by low density separation. In: Proc. International Conference on Artificial Intelligence and Statistics, Barbados 2005.

[7] Cortes, C., Vapnik, V.: Support-vector networks. Machine Learning 20 (1995), 273-297. | DOI

[8] Drineas, P., Mahoney, M. W.: On the Nyström method for approximating a Gram matrix for improved kernel-based learning. J. Machine Learning Research 6 (2005), 2153-2175. | MR

[9] Fayyad, U. M., Piatetsky-Shapiro, G., Smyth, P., Uthurusamy, R.: Advances in Knowledge Discovery and Data Mining. AAAI Press, Menlo Park 1996.

[10] Flouri, K., Beferull-Lozano, B., Tsakalides, P.: Distributed consensus algorithms for SVM training in wireless sensor networks. In: 16th European Signal Processing Conference, Lausanne 2008. | DOI

[11] Forero, P A., Cano, A., Giannakis, G. B.: Consensus-based distributed support vector machines. J. Machine Learning Research 11 (2010), 1663-1707. | MR

[12] Franc, V., Sonnenburg, S.: Optimized cutting plane algorithm for support vector machines. In: Proc. 25th International Conference on Machine Learning, Helsinki 2008. | DOI | MR

[13] Hu, J.: On robust consensus of multi-agent systems with communication delays. Kybernetika 45 (2009), 768-784. | MR | Zbl

[14] Joachims, T., Finley, T., Yu, C. J.: Cutting-plane training of structural SVMs. Machine Learning 77 (2009), 27-59. | DOI

[15] Lee, S., Wright, S. J.: 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

[16] Lou, Y., Hong, Y., Wang, S.: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297. | DOI | MR | Zbl

[17] Lu, Y., Roychowdhury, V., Vandenberghe, L.: Distributed parallel support vector machines in strongly connected networks. IEEE Trans. Neural Networks 19 (2008), 1167-1178. | DOI

[18] Kim, W., Park, J., Yoo, J., Kim, H. J., Park, C. G.: Target localization using ensemble support vector regression in wireless sensor networks. IEEE Trans. Cybernetics 43 (2013), 1189-1198. | DOI

[19] Kim, W., Stanković, M. S., Johansson, K. H., Kim, H.J.: A distributed support vector machine learning over wireless sensor networks. IEEE Trans. Neural Cybernetics 45 (2015), 2599–2611. | DOI

[20] Nedic, A., Asuman, O.: Distributed sub-gradient methods for multi-agent optimization. IEEE Trans. Automatic Control 54 (2009), 48-61. | DOI | MR

[21] Platt, J. C.: Fast training of support vector machines using sequential minimal optimization. In: Advances in Kernel Methods, MIT Press, Massachusetts 1999, pp. 185-208.

[22] Polyak, B. T.: Introduction to Optimization. Springer, New York 1987. | MR

[23] Rifkin, R., Klautau, A.: In defense of one-vs-all classification. J. Machine Learning Research 5 (2004), 101-141. | MR

[24] Scardapane, S., Fierimonte, R., Lorenzo, P. D., Panella, M., Uncini, A.: Distributed semi-supervised support vector machines. Neural Networks 80 (2016), 43-52. | DOI

[25] Shalev-Shwartz, S., Singer, Y., Srebro, N.: Pegasos: Primal estimated sub-gradient solver for svm. In: Proc. 24th International Conference on Machine Learning, Oregon 2007. | DOI

[26] Sra, S., Nowozin, S., Wright, S. J.: Optimization for Machine Learning. MIT Press, Massachusetts 2012.

[27] Wang, X., Chen, Y.: Quantized distributed output regulation of multi-agent systems. Kybernetika 52 (2016), 427-440. | DOI | MR

[28] Weston, J., Watkins, C.: Support vector machines for multi-class pattern recognition. ESANN 99 (1999), 219-224.

[29] Yi, P., Hong, Y.: Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme. Control Theory Technol. 13 (2015), 333-347. | DOI | MR

[30] Yuan, D., Ho, D. W. C., Hong, Y.: On Convergence rate of distributed stochastic gradient algorithm for convex optimization with inequality constraints. SIAM J. Control Optim. 54 (2016), 2872-2892. | DOI | MR