jmlr jmlr2010 jmlr2010-26 jmlr2010-26-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Pedro A. Forero, Alfonso Cano, Georgios B. Giannakis
Abstract: This paper develops algorithms to train support vector machines when training data are distributed across different nodes, and their communication to a centralized processing unit is prohibited due to, for example, communication complexity, scalability, or privacy reasons. To accomplish this goal, the centralized linear SVM problem is cast as a set of decentralized convex optimization subproblems (one per node) with consensus constraints on the wanted classifier parameters. Using the alternating direction method of multipliers, fully distributed training algorithms are obtained without exchanging training data among nodes. Different from existing incremental approaches, the overhead associated with inter-node communications is fixed and solely dependent on the network topology rather than the size of the training sets available per node. Important generalizations to train nonlinear SVMs in a distributed fashion are also developed along with sequential variants capable of online processing. Simulated tests illustrate the performance of the novel algorithms.1 Keywords: support vector machine, distributed optimization, distributed data mining, distributed learning, sensor networks
I. F. Akyildiz, D. Pompili, and T. Melodia. Underwater acoustic sensor networks: Research challenges. Ad Hoc Networks (Elsevier), 3(3):257–279, Mar. 2005. A. Asuncion and D.J. Newman. UCI machine learning repository, 2007. http://www.ics.uci.edu/∼mlearn/MLRepository.html. D. P. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd ed., 1999. 1705 URL F ORERO , C ANO AND G IANNAKIS D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, 1997. A. Bordes, S. Ertekin, J. Weston, and L. Bottou. Fast kernel classifiers with online and active learning. Journal of Machine Learning Research, 6:1579–1619, Mar. 2005. G. Cauwenberghs and T. Poggio. Incremental and decremental support vector machine learning. In Proc. of Neural Info. Processing Systems Conf., pages 409–415, Denver, CO, USA, Nov. 2000. E. Y. Chang, K. Zhu, H. Wang, H. Bai, J. Li, Z. Qiu, and H. Cui. PSVM: Parallelizing support vector machines on distributed computers. In 21st Neural Info. Processing Systems Conf., Vancouver, Canada, Dec. 3-6, 2007. K. Chaudhuri and C. Monteleoni. Privacy-preserving logistic regression. In Advances in Neural Information Processing Systems, 2008. T. Do and F. Poulet. Classifying one billion data with a new distributed SVM algorithm. In Proc. of International Conf. on Research, Innovation and Vision for the Future, pages 59–66, Ho Chi Minh City, Vietnam, Feb. 12-16, 2006. R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. Wiley, 2nd edition, 2002. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of 3rd Theory of Cryptography Conference, pages 265–284, New York, NY, USA, Mar. 4-7, 2006. I. El-Naqa, Y. Yang, M.N. Wernick, N.P. Galatsanos, and R.M. Nishikawa. A support vector machine approach for detection of microcalcifications. IEEE Tran. on Medical Imaging, 21(12): 1552–1563, Dec. 2002. K. Flouri, B. Beferull-Lozano, and P. Tsakalides. Training a support-vector machine-based classifier in distributed sensor networks. In Proc. of 14th European Signal Processing Conf., Florence, Italy, Sep. 4-8, 2006. K. Flouri, B. Beferull-Lozano, and P. Tsakalides. Distributed consensus algorithms for SVM training in wireless sensor networks. In Proc. of 16th European Signal Processing Conf., Laussane, Switzerland, Aug. 25-29, 2008. G. Fung and O. L. Mangasarian. Incremental support vector machine classification. In Proc. of the SIAM Intl. Conf. on Data Mining, pages 247–260, Arlington, VA, USA, Apr. 11-13, 2002. A. Ganapathiraju, J.E. Hamaker, and J. Picone. Applications of support vector machines to speech recognition. IEEE Tran. on Signal Processing, 52(8):2348–2355, Aug. 2004. G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, 3rd edition, 1996. H. P. Graf, E. Cosatto, L. Bottou, I. Dourdanovic, and V. Vapnik. Parallel support vector machines: The cascade SVM. In Advances in Neural Information Processing Systems, volume 17. MIT Press, 2005. 1706 C ONSENSUS -BASED D ISTRIBUTED S UPPORT V ECTOR M ACHINES T. Hastie, R. Tishbiranie, and J. Friedman. The Elements of Statistical Learning. Spinger, 2nd edition, 2009. R. Klinkenberg and T. Joachims. Detecting concept drift with support vector machines. In Proc. of the Seventeenth International Conf. on Machine Learning, pages 487–494, Stanford, CA, USA, Jun. 29 - Jul. 2, 2000. K. Langendoen and N. Reijers. Distributed localization in wireless sensor networks: a quantitative comparison. Comput. Netw., 43(4):499–518, 2003. Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, 86(11):2278–2324, Nov. 1998. F. F. Li. Estimation of intelligibility from received arbitrary speech signals with support vector machine. In Proc. of International Conference on Machine Learning and Cybernetics, volume 6, pages 3755–3760, Guangzhou, China, Aug. 2005. Y. Liang, M.L. Reyes, and J.D. Lee. Real-time detection of driver cognitive distraction using support vector machines. IEEE Tran. on Intelligent Transportation Systems, 8(2):340–350, Jun. 2007. Y. Lu, V. Roychowdhury, and L. Vandenberghe. Distributed parallel support vector machines in strongly connected networks. IEEE Tran. on Neural Networks, 19(7):1167–1178, Jul. 2008. U. Markowska-Kaczmar and P. Kubacki. Support vector machines in handwritten digits classification. In Proc. of 5th International Conference on Intelligent Systems Design and Applications, pages 406–411, Wroclaw, Poland, Sep. 8-11, 2005. A. Navia-Vazquez, D. Gutierrez-Gonzalez, E. Parrado-Hernandez, and J. J. Navarro-Abellan. Distributed support vector machines. IEEE Tran. on Neural Networks, 17(4):1091–1097, Jul. 2006. C. H. Papadimitriou, Computational Complexity. Addison- Wesley, 1993. J. B. Predd, S. R. Kulkarni, and H. V. Poor. Distributed kernel regression: An algorithm for training collaboratively. IEEE Trans. on Information Theory, 55(4):1856–1871, Apr. 2009. B. Sch¨ lkopf and A. Smola. Learning with Kernels. Support Vector Machines, Regularization, o Optimization, and Beyond. MIT Press, 2002. V. Vapnik. Statistical Learning Theory. Wiley, 1st edition, 1998. G. Wahba. Spline Models for Observational Data, volume 59 of CBMS-NSF Regional Conf. Series in Applied Mathematics. SIAM, Philadelphia, PA, USA, 1990. J. Weston, A. Elisseeff, G. BakIr, and F. Sinz. The spider machine learning toolbox, 2006. URL http://www.kyb.tuebingen.mpg.de/bs/people/spider/. H. Zhu, G. B. Giannakis, and A. Cano. Distributed in-network channel decoding. IEEE Trans. on Signal Processing, 57(10):3970–3983, Oct. 2009. 1707