Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-25T09:14:54.694Z Has data issue: false hasContentIssue false
  • English
  • Français

A STUDY ON THE ERROR OF DISTRIBUTED ALGORITHMS FOR BIG DATA CLASSIFICATION WITH SVM

Part of: Artificial intelligence (68Txx)

Published online by Cambridge University Press:  07 March 2017

CHENG WANG Open the ORCID record for CHENG WANG [Opens in a new window]  and
FEILONG CAO Open the ORCID record for FEILONG CAO [Opens in a new window]
CHENG WANG
Affiliation:
Applied Mathematics Department of China Jiliang University, China email [email protected], [email protected]
FEILONG CAO*
Affiliation:
Applied Mathematics Department of China Jiliang University, China email [email protected], [email protected]
*
✉[email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The error of a distributed algorithm for big data classification with a support vector machine (SVM) is analysed in this paper. First, the given big data sets are divided into small subsets, on which the classical SVM with Gaussian kernels is used. Then, the classification error of the SVM for each subset is analysed based on the Tsybakov exponent, geometric noise, and width of the Gaussian kernels. Finally, the whole error of the distributed algorithm is estimated in terms of the error of each subset.

Keywords

distributed algorithmbig datasupport vector machineTsybakov exponentgeometric noise exponent

MSC classification

Primary: 68T05: Learning and adaptive systems
Type
Research Article
Information
The ANZIAM Journal , Volume 58 , Issue 3-4 , April 2017 , pp. 231 - 237
Copyright
© 2017 Australian Mathematical Society 

References

Bartlett, P. L., Jordan, M. I. and McAuliffe, J. D., “Convexity, classification, and risk bounds”, J. Amer. Statist. Assoc. 101 (2006) 138–156; doi:10.1198/016214505000000907.Google Scholar
Cristianini, N. and Shawe-Taylor, J., An introduction to support vector machines (Cambridge University Press, Cambridge, 2000) http://dl.acm.org/citation.cfm?id=345662.Google Scholar
Cucker, F. and Zhou, D. X., Learning theory: an approximation theory viewpoint (Cambridge University Press, Cambridge, 2007); doi:10.1017/CBO9780511618796.Google Scholar
DeVito, E., Caponnetto, A. and Rosasco, L., “Model selection for regularized least-squares algorithm in learning theory”, Found. Comput. Math. 5 (2006) 59–85; doi:10.1007/s10208-004-0134-1.Google Scholar
Kleiner, A., Talwalkar, A., Sarkar, P. and Jordan, M., “The big data bootstrap”, in: Proc. 29th Inter. Conf. Mach. Lear. (Omnipress, Madison, WI, USA, 2012) 1759–1766; https://arxiv.org/ftp/arxiv/papers/1206/1206.6415.pdf.Google Scholar
McDonald, R., Hall, K. and Mann, G., “Distributed training strategies for the structured perceptron”, in: Proc. HLT ’10 Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (Association for Computational Linguistics Stroudsburg, PA, USA, 2010) 456–464; http://aclweb.org/anthology/N/N10/N10-1069.pdf.Google Scholar
Steinwart, I. and Scovel, C., “Fast rates for support vector machines using Gaussian kernels”, Ann. Statist. 35 (2007) 575–607; doi:10.1214/009053606000001226.Google Scholar
Xiang, D. H. and Zhou, D. X., “Classification with Gaussians and convex loss”, J. Mach. Learn. Res. 10 (2009) 1147–1468; doi:10.1007/s11425-010-4043-2.Google Scholar
Zhang, Y., Duchi, J. C. and Wainwright, M. J., “Communication-efficient algorithms for statistical optimization”, J. Mach. Learn. Res. 14 (2013) 3321–3363; doi:10.1109/CDC.2012.6426691.Google Scholar
Zhang, Y., Duchi, J. and Wainwright, M., “Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates”, J. Mach. Learn. Res. 30 (2013) 592–617; https://arxiv.org/pdf/1305.5029v2.pdf.Google Scholar