Abstract
Semi-supervised learning is an emerging computational paradigm for machine learning, that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance. While various methods have been proposed based on different intuitions, the crucial issue of generalization performance is still poorly understood. In this paper, we investigate the convergence property of the Laplacian regularized least squares regression, a semi-supervised learning algorithm based on manifold regularization. Moreover, the improvement of error bounds in terms of the number of labeled and unlabeled data is presented for the first time as far as we know. The convergence rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers. Some new techniques are exploited for the analysis since an extra regularizer is introduced.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aronszajn N. Theory of reproducing kernels. Trans Amer Math Soc, 1950, 68: 337–404
Belkin M, Niyogi P. Semi-supervised learning on riemannian manifolds. Machine Learning, 2004, 56: 209–239
Belkin M, Niyogi P. Towards a theoretical foundation for Laplacian-based manifold methods. J Comput System Sci, 2008, 74: 1289–1308
Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J Mach Learn Res, 2006, 7: 2399–2434
Blum A, Chawla S. Learning from labeled and unlabeled data using graph mincuts. In: Proceedings of the 18th International Conference on Machine Learning. Waltham: Morgan Kaufmann Publishers Inc., 2001, 19–26
Blum A, Mitchell T. Combining labeled and unlabeled data with co-training. In: Proceedings of the 11th Annual Conference on Computational Learning Theory. New York: ACM, 1998, 92–100
Cao Y, Chen D-R. Consistency of regularized spectral clustering. Appl Comput Harmon Anal, 2010, 30: 319–336
Cucker F, Smale S. On the mathematical foundations of learning. Bull Amer Math Soc, 2002, 39: 1–50
Cucker F, Zhou D-X. Learning Theory: An Approximation Theory Viewpoint. Cambridge: Cambridge University Press, 2007
Johnson R, Zhang T. On the effectiveness of Laplacian normalization for graph semi-supervised learning. J Mach Learn Res, 2007, 8: 1489–1517
Johnson R, Zhang T. Graph-based semi-supervised learning and spectral kernel design. IEEE Trans Inform Theory, 2008, 54: 275–288
Luxburg Von U, Belkin M, Bousquet O. Consistency of spectral clustering. Ann Statist, 2008, 36: 555–586
Rigollet P. Generalization error bounds in semi-supervised classification under the cluster assumption. J Mach Learn Res, 2007, 8: 1369–1392
Rosenberg D. Semi-supervised learning with multiple views. Ph.D. Thesis, California: University of California, 2008
Rosenberg D, Sindhwani V, Bartlett P, et al. Multiview point cloud kernels for semisupervised learning [lecture notes]. IEEE Signal Processing Magazine, 2009, 26: 145–150
Sindhwani V, Niyogi P, Belkin M. Beyond the point cloud: from transductive to semi-supervised learning. In: Proceedings of the 22nd International Conference on Machine Learning. New York: ACM, 2005, 824–831
Smale S, Zhou D-X. Estimating the approximation error in learning theory. Anal Appl, 2003, 1: 17–41
Smale S, Zhou D-X. Shannon sampling ii: Connections to learning theory. Appl Comput Harmon Anal, 2005, 19: 285–302
Smale S, Zhou D-X. Geometry on probability spaces. Constr Approx, 2009, 30: 311–323
Szummer M, Jaakkola T. Partially labeled classification with markov random walks. Ad Neural Inform Proc Syst, 2002, 2: 945–952
Vapnik V. Statistical Learning Theory. New York: Wiley-Interscience, 1998
Wu Q, Ying Y, Zhou D-X. Learning rates of least-square regularized regression. Found Comput Math, 2006, 6: 171–192
Zhou D, Bousquet O, Lal T, et al. Learning with local and global consistency. Adv Neural Inform Processing Syst, 2004, 16: 321–328
Zhou D-X. The covering number in learning theory. J Complexity, 2002, 18: 739–767
Zhou D-X. Capacity of reproducing kernel spaces in learning theory. IEEE Trans Inform Theory, 2003, 49: 1743–1752
Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using gaussian fields and harmonic functions. In: Proceedings of the 20th International Conference on Machine Learning. California: AAAI Press, 2003
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cao, Y., Chen, D. Generalization errors of Laplacian regularized least squares regression. Sci. China Math. 55, 1859–1868 (2012). https://doi.org/10.1007/s11425-012-4438-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11425-012-4438-3