×

Density-sensitive semisupervised inference. (English) Zbl 1267.62057

Summary: Semisupervised methods are techniques for using labeled data \((X_{1},Y_{1}),\dots,(X_{n},Y_{n})\) together with unlabeled data \(X_{n+1},\dots,X_{N}\) to make predictions. These methods invoke some assumptions that link the marginal distribution \(P_{X}\) of \(X\) to the regression function \(f(x)\). For example, it is common to assume that \(f\) is very smooth over high density regions of \(P_{X}\). Many of the methods are ad hoc and have been shown to work in specific examples but are lacking a theoretical foundation. We provide a minimax framework for analyzing semisupervised methods. In particular, we study methods based on metrics that are sensitive to the distribution \(P_{X}\). Our model includes a parameter \(\alpha\) that controls the strength of the semisupervised assumption. We then use the data to adapt to \(\alpha\).

MSC:

62G08 Nonparametric regression and quantile regression
62G07 Density estimation
62G15 Nonparametric tolerance and confidence regions

Software:

spa
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Azizyan, M., Singh, A. and Wasserman, L. (2013). Supplement to “Density-sensitive semisupervised inference.” . · Zbl 1267.62057
[2] Belkin, M. and Niyogi, P. (2004). Semi-supervised learning on Riemannian manifolds. Machine Learning 56 209-239. · Zbl 1089.68086 · doi:10.1023/B:MACH.0000033120.25363.1e
[3] Ben-David, S., Lu, T. and Pal, D. (2008). Does unlabeled data provably help? Worst-case analysis of the sample complexity of semi-supervised learning. In 21 st Annual Conference on Learning Theory ( COLT ). Available at .
[4] Bijral, A., Ratliff, N. and Srebro, N. (2011). Semi-supervised learning with density based distances. In 27 th Conference on Uncertainty in Artificial Intelligence . Available at .
[5] Bousquet, O., Chapelle, O. and Hein, M. (2004). Measure based regularization. In Advances in Neural Information Processing Systems 16 . MIT Press, Cambridge, MA.
[6] Castelli, V. and Cover, T. M. (1995). On the exponential value of labeled samples. Pattern Recognition Letters 16 105-111.
[7] Castelli, V. and Cover, T. M. (1996). The relative value of labeled and unlabeled samples in pattern recognition with an unknown mixing parameter. IEEE Trans. Inform. Theory 42 2102-2117. · Zbl 0873.68185 · doi:10.1109/18.556600
[8] Craig, C. C. (1933). On the Tchebychef inequality of Bernstein. Ann. Math. Statist. 4 94-102. · Zbl 0007.02303 · doi:10.1214/aoms/1177732803
[9] Culp, M. (2011a). On propagated scoring for semisupervised additive models. J. Amer. Statist. Assoc. 106 248-259. · Zbl 1396.62128 · doi:10.1198/jasa.2011.tm09316
[10] Culp, M. (2011b). spa: Semi-supervised semi-parametric graph-based estimation in R. Journal of Statistical Software 40 1-29.
[11] Culp, M. and Michailidis, G. (2008). An iterative algorithm for extending learners to a semi-supervised setting. J. Comput. Graph. Statist. 17 545-571. · doi:10.1198/106186008X344748
[12] Györfi, L., Kohler, M., Krzyżak, A. and Walk, H. (2002). A Distribution-Free Theory of Nonparametric Regression . Springer, New York. · Zbl 1021.62024
[13] Haupt, J. and Nowak, R. (2006). Signal reconstruction from noisy random projections. IEEE Trans. Inform. Theory 52 4036-4048. · Zbl 1323.94046 · doi:10.1109/TIT.2006.880031
[14] Kpotufe, S. (2011). \(k\)-NN regression adapts to local intrinsic dimension. In Advances in Neural Information Processing Systems 24 729-737. MIT Press, Cambridge, MA.
[15] Lafferty, J. and Wasserman, L. (2007). Statistical analysis of semi-supervised regression. In Advances in Neural Information Processing Systems 20 801-808. MIT Press, Cambridge, MA.
[16] Lee, A. B. and Wasserman, L. (2008). Spectral connectivity analysis. Preprint. Available at . · Zbl 1390.62062 · doi:10.1198/jasa.2010.tm09754
[17] Liang, F., Mukherjee, S. and West, M. (2007). The use of unlabeled data in predictive modeling. Statist. Sci. 22 189-205. · Zbl 1246.62157 · doi:10.1214/088342307000000032
[18] Nadler, B., Srebro, N. and Zhou, X. (2009). Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data. In Advances in Neural Information Processing Systems 22 1330-1338. MIT Press, Cambridge, MA.
[19] Niyogi, P. (2008). Manifold regularization and semi-supervised learning: Some theoretical analyses. Technical Report TR-2008-01, Computer Science Dept., Univ. Chicago. Available at . · Zbl 1317.68178
[20] Ratsaby, J. and Venkatesh, S. S. (1995). Learning from a mixture of labeled and unlabeled examples with parametric side information. In Proceedings of the Eighth Annual Conference on Computational Learning Theory 412-417. ACM, New York.
[21] Rigollet, P. (2007). Generalized error bounds in semi-supervised classification under the cluster assumption. J. Mach. Learn. Res. 8 1369-1392. · Zbl 1222.68288
[22] Sajama andOrlitsky, A. (2005). Estimating and computing density based distance metrics. In Proceedings of the 22 nd International Conference on Machine Learning. ICML 2005 760-767. ACM, New York.
[23] Singh, A., Nowak, R. D. and Zhu, X. (2008). Unlabeled data: Now it helps, now it doesn’t. Technical report, ECE Dept., Univ. Wisconsin-Madison. Available at .
[24] Sinha, K. and Belkin, M. (2009). Semi-supervised learning using sparse eigenfunction bases. In Advances in Neural Information Processing Systems 22 (Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams and A. Culotta, eds.) 1687-1695. MIT Press, Cambridge, MA.
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.