nips nips2008 nips2008-245 nips2008-245-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Aarti Singh, Robert Nowak, Xiaojin Zhu
Abstract: Empirical evidence shows that in favorable situations semi-supervised learning (SSL) algorithms can capitalize on the abundance of unlabeled training data to improve the performance of a learning task, in the sense that fewer labeled training data are needed to achieve a target error bound. However, in other situations unlabeled data do not seem to help. Recent attempts at theoretically characterizing SSL gains only provide a partial and sometimes apparently conflicting explanations of whether, and to what extent, unlabeled data can help. In this paper, we attempt to bridge the gap between the practice and theory of semi-supervised learning. We develop a finite sample analysis that characterizes the value of unlabeled data and quantifies the performance improvement of SSL compared to supervised learning. We show that there are large classes of problems for which SSL can significantly outperform supervised learning, in finite sample regimes and sometimes also in terms of error convergence rates.
[1] Balcan, M.F., Blum, A.: A PAC-style model for learning from labeled and unlabeled data. In: 18th Annual Conference on Learning Theory, COLT. (2005)
[2] K¨ ari¨ inen, M.: Generalization error bounds using unlabeled data. In: 18th Annual Conference on a¨ a Learning Theory, COLT. (2005)
[3] Rigollet, P.: Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research 8 (2007) 1369–1392
[4] Lafferty, J., Wasserman, L.: Statistical analysis of semi-supervised regression. In: Advances in Neural Information Processing Systems 21, NIPS. (2007) 801–808
[5] Ben-David, S., Lu, T., Pal, D.: Does unlabeled data provably help? worst-case analysis of the sample complexity of semi-supervised learning. In: 21st Annual Conference on Learning Theory, COLT. (2008)
[6] Niyogi, P.: Manifold regularization and semi-supervised learning: Some theoretical analyses. Technical Report TR-2008-01, Computer Science Department, University of Chicago. URL http://people.cs.uchicago.edu/∼niyogi/papersps/ssminimax2.pdf (2008)
[7] Seeger, M.: Learning with labeled and unlabeled data. Technical report, Institute for ANC, Edinburgh, UK. URL http://www.dai.ed.ac.uk/∼seeger/papers.html (2000)
[8] Castelli, V., Cover, T.M.: On the exponential value of labeled samples. Pattern Recognition Letters 16(1) (1995) 105–111
[9] Castelli, V., Cover, T.M.: The relative value of labeled and unlabeled samples in pattern recognition. IEEE Transactions on Information Theory 42(6) (1996) 2102–2117
[10] Bickel, P.J., Li, B.: Local polynomial regression on unknown manifolds. In: IMS Lecture NotesMonograph Series, Complex Datasets and Inverse Problems: Tomography, Networks and Beyond. Volume 54. (2007) 177–186
[11] Korostelev, A.P., Tsybakov, A.B.: Minimax Theory of Image Reconstruction. Springer, NY (1993)
[12] Castro, R., Willett, R., Nowak, R.: Faster rates in regression via active learning. Technical Report ECE-05-03, ECE Department, University of Wisconsin - Madison. URL http://www.ece.wisc.edu/∼nowak/ECE-05-03.pdf (2005)
[13] Singh, A., Nowak, R., Zhu, X.: Finite sample analysis of semi-supervised learning. Technical Report ECE-08-03, ECE Department, University of Wisconsin - Madison. URL http://www.ece.wisc.edu/∼nowak/SSL TR.pdf (2008)
[14] Korostelev, A., Nussbaum, M.: The asymptotic minimax constant for sup-norm loss in nonparametric density estimation. Bernoulli 5(6) (1999) 1099–1118
[15] Chapelle, O., Zien, A.: Semi-supervised classification by low density separation. In: Tenth International Workshop on Artificial Intelligence and Statistics. (2005) 57–64
[16] Tsybakov, A.B.: Introduction a l’estimation non-parametrique. Springer, Berlin Heidelberg (2004)
[17] Stone, C.J.: Optimal rates of convergence for nonparametric estimators. The Annals of Statistics 8(6) (1980) 1348–1360 8