×

Learning rates for regularized classifiers using multivariate polynomial kernels. (English) Zbl 1169.68043

Summary: Regularized classifiers (a leading example is support vector machine) are known to be a kind of kernel-based classification methods generated from Tikhonov regularization schemes, and the polynomial kernels are the original and also probably the most important kernels used in them. In this paper, we provide an error analysis for the regularized classifiers using multivariate polynomial kernels. We introduce Bernstein-Durrmeyer polynomials, whose reproducing kernel Hilbert space norms and approximation properties in \(L^{1}\) space play a key role in the analysis of regularization error. We also introduce the standard estimation of sample error, and derive explicit learning rates for these algorithms.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68T10 Pattern recognition, speech recognition
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aronszajn, N., Theory of reproducing kernels, Trans. Amer. Math. Soc., 68, 337-404 (1950) · Zbl 0037.20701
[2] Bartlett, P. L., The sample complexity of pattern classification with neural networks: The size of the weights is more import than the size of the network, IEEE Trans. Inform. Theory, 44, 525-536 (1998) · Zbl 0901.68177
[3] Berens, H.; Schmid, H. J.; Xu, Y., Bernstein-Durrmeyer polynomials on a simplex, J. Approx. Theory, 68, 247-261 (1992) · Zbl 0754.41005
[4] Berens, H.; Xu, Y., K-moduli, moduli of smoothness, and Bernstein polynomials on a simplex, Indag. Mathem. (N.S.), 2, 4, 411-421 (1991) · Zbl 0763.41016
[5] B.E. Boser, I. Guyon, V. Vapnik, A training algorithm for optimal margin classifiers, in: Proceedings of the Fifth Annual Workshop of Computational Learning Theory, vol. 5, 1992, pp. 144-152; B.E. Boser, I. Guyon, V. Vapnik, A training algorithm for optimal margin classifiers, in: Proceedings of the Fifth Annual Workshop of Computational Learning Theory, vol. 5, 1992, pp. 144-152
[6] Chen, D. R.; Wu, Q.; Ying, Y.; Zhou, D. X., Support vector machine soft margin classifiers: Error analysis, J. Mach. Learn. Res., 5, 1143-1175 (2004) · Zbl 1222.68167
[7] Cortes, C.; Vapnik, V., Support-vector networks, Mach. Learn., 20, 273-297 (1995) · Zbl 0831.68098
[8] Cristianini, N.; Shawe-Taylor, J., An Introduction to Support Vector Machines (2000), Cambridge University Press: Cambridge University Press Cambridge, MA
[9] Cucker, F.; Smale, S., On the mathematical foundations of learing theory, Bull. Amer. Math. Soc., 39, 1-49 (2001)
[10] Cucker, F.; Smale, S., Best choices for regularization parameters in learning theory: On the bias-variance problem, Found. Comput. Math., 2, 413-428 (2002) · Zbl 1057.68085
[11] Devroye, L.; Györfi, L.; Lugosi, G., A Probabilistic Theory of Pattern Recognition (1997), Springer-Verlag: Springer-Verlag New York
[12] Evgeniou, T.; Pontil, M.; Poggio, T., Regularization networks and support vector machines, Adv. Comput. Math., 13, 1-50 (2000) · Zbl 0939.68098
[13] Lin, Y., Support vector machines and the Bayes rule in classification, Data Min. and Knowl. Discov., 6, 259-275 (2002)
[14] C. Scovel, I. Steinwart, Fast rate for support vector machines, in: COLT, 2005; C. Scovel, I. Steinwart, Fast rate for support vector machines, in: COLT, 2005 · Zbl 1137.68564
[15] Suykens, J. A.K.; Vandewalle, J., Least squares support vector machine classifiers, Neural Process. Lett., 9, 293-300 (1999) · Zbl 0958.93042
[16] H.Z. Tong, D.R. Chen, L.Z. Peng, Analysis of support vector machines regression, Found. Comput. Math. (in press); H.Z. Tong, D.R. Chen, L.Z. Peng, Analysis of support vector machines regression, Found. Comput. Math. (in press) · Zbl 1185.68577
[17] Vapnik, V., Statistical Learning Theory (1998), John Wiley & Sons: John Wiley & Sons New York · Zbl 0935.62007
[18] Wu, Q.; Ying, Y.; Zhou, D. X., Learning rates of least-square regularized regression, Found. Comput. Math., 6, 171-192 (2006) · Zbl 1100.68100
[19] Wu, Q.; Ying, Y.; Zhou, D. X., Multi-kernel regularized classifiers, J. Complexity, 23, 108-134 (2007) · Zbl 1171.65043
[20] Wu, Q.; Zhou, D. X., SVM soft margin classifiers: Linear programming versus quadratic programming, Neural Comput., 17, 1160-1187 (2005) · Zbl 1108.90324
[21] Wu, Q.; Zhou, D. X., Analysis of support vector machine classification, J. Comput. Anal. Appl., 8, 99-119 (2006) · Zbl 1098.68680
[22] G.B. Ye, D.X. Zhou, Learning and approximation by Gaussians on Riemannian manifolds, Adv. Comput. Math. (in press); G.B. Ye, D.X. Zhou, Learning and approximation by Gaussians on Riemannian manifolds, Adv. Comput. Math. (in press) · Zbl 1156.68045
[23] Zhang, T., Statistical behavior and consistency of classification methods based on convex risk minimization, Ann. Statist., 32, 56-85 (2004) · Zbl 1105.62323
[24] Zhou, D. X.; Jetter, K., Approximation with polynomial kernels and SVM classifiers, Adv. Comput. Math., 25, 323-344 (2006) · Zbl 1095.68103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.