Previous |  Up |  Next


nonlinear support vector machine; multi-agent system; distributed optimization; connectivity
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.
[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 10.1561/2200000016
[4] Chang, C. C., Lin, C. J.: LIBSVM: a library for support vector machines. JACM Trans. Intell. Systems Technol. 2 (2011), 1-27. DOI 10.1145/1961189.1961199
[5] Chapelle, O.: Training a support vector machine in the primal. Neural Computation 19 (2007), 1155-1178. DOI 10.1162/neco.2007.19.5.1155 | MR 2309267
[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 10.1007/bf00994018
[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 2249884
[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 10.1109/icdsp.2009.5201180
[11] Forero, P A., Cano, A., Giannakis, G. B.: Consensus-based distributed support vector machines. J. Machine Learning Research 11 (2010), 1663-1707. MR 2653352
[12] Franc, V., Sonnenburg, S.: Optimized cutting plane algorithm for support vector machines. In: Proc. 25th International Conference on Machine Learning, Helsinki 2008. DOI 10.1145/1390156.1390197 | MR 2563979
[13] Hu, J.: On robust consensus of multi-agent systems with communication delays. Kybernetika 45 (2009), 768-784. MR 2599111 | Zbl 1190.93003
[14] Joachims, T., Finley, T., Yu, C. J.: Cutting-plane training of structural SVMs. Machine Learning 77 (2009), 27-59. DOI 10.1007/s10994-009-5108-8
[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 10.1007/978-1-4614-5076-4_5
[16] Lou, Y., Hong, Y., Wang, S.: Distributed continuous-time approximate projection protocols for shortest distance optimization problems. Automatica 69 (2016), 289-297. DOI 10.1016/j.automatica.2016.02.019 | MR 3500113 | Zbl 1338.93026
[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 10.1109/tnn.2007.2000061
[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 10.1109/tsmcb.2012.2226151
[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 10.1109/TCYB.2014.2377123
[20] Nedic, A., Asuman, O.: Distributed sub-gradient methods for multi-agent optimization. IEEE Trans. Automatic Control 54 (2009), 48-61. DOI 10.1109/tac.2008.2009515 | MR 2478070
[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 1099605
[23] Rifkin, R., Klautau, A.: In defense of one-vs-all classification. J. Machine Learning Research 5 (2004), 101-141. MR 2247975
[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 10.1016/j.neunet.2016.04.007
[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 10.1145/1273496.1273598
[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 10.14736/kyb-2016-3-0427 | MR 3532515
[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 10.1007/s11768-015-5100-8 | MR 3435158
[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 10.1137/15m1048896 | MR 3561770
Partner of
EuDML logo