nips nips2007 nips2007-186 nips2007-186-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Larry Wasserman, John D. Lafferty
Abstract: Semi-supervised methods use unlabeled data in addition to labeled data to construct predictors. While existing semi-supervised methods have shown some promising empirical performance, their development has been based largely based on heuristics. In this paper we study semi-supervised learning from the viewpoint of minimax theory. Our first result shows that some common methods based on regularization using graph Laplacians do not lead to faster minimax rates of convergence. Thus, the estimators that use the unlabeled data do not have smaller risk than the estimators that use only labeled data. We then develop several new approaches that provably lead to improved performance. The statistical tools of minimax analysis are thus used to offer some new perspective on the problem of semi-supervised learning. 1
B ELKIN , M., N IYOGI , P. and S INDHWANI , V. (2005). On manifold regularization. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AISTAT 2005). B ICKEL , P. and L I , B. (2006). Local polynomial regression on unknown manifolds. Tech. rep., Department of Statistics, UC Berkeley. C ASTELLI , V. and C OVER , T. (1996). The relative value of labeled and unlabeled samples in pattern recognition with an unknown mixing parameter. IEEE Trans. on Info. Theory 42 2101–2117. C ORTES , C. and M OHRI , M. (2006). On transductive regression. In Advances in Neural Information Processing Systems (NIPS), vol. 19. FAN , J. (1993). Local linear regression smoothers and their minimax efficiencies. The Annals of Statistics 21 196–216. G IRARD , D. (1998). Asymptotic comparison of (partial) cross-validation, gcv and randomized gcv in nonparametric regression. Ann. Statist. 12 315–334. L EVINA , E. and B ICKEL , P. (2005). Maximum likelihood estimation of intrinsic dimension. In Advances in Neural Information Processing Systems (NIPS), vol. 17. N IYOGI , P. (2007). Manifold regularization and semi-supervised learning: Some theoretical analyses. Tech. rep., Departments of Computer Science and Statistics, University of Chicago. R IGOLLET, P. (2006). Generalization error bounds in semi-supervised classification under the cluster assumption. arxiv.org/math/0604233 . S INDHWANI , V., N IYOGI , P., B ELKIN , M. and K EERTHI , S. (2005). Linear manifold regularization for large scale semi-supervised learning. In Proc. of the 22nd ICML Workshop on Learning with Partially Classified Training Data. S MOLA , A. and KONDOR , R. (2003). Kernels and regularization on graphs. In Conference on Learning Theory, COLT/KW. T SANG , I. and K WOK , J. (2006). Large-scale sparsified manifold regularization. In Advances in Neural Information Processing Systems (NIPS), vol. 19. Z HOU , D., B OUSQUET, O., L AL , T., W ESTON , J. and S CHÖLKOPF, B. (2004). Learning with local and global consistency. In Advances in Neural Information Processing Systems (NIPS), vol. 16. Z HU , X. (2006). Semi-supervised learning literature review. Tech. rep., University of Wisconsin. Z HU , X., G HAHRAMANI , Z. and L AFFERTY, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. In ICML-03, 20th International Conference on Machine Learning. 8