TR-2008-01
Manifold Regularization and Semi-supervised Learning: Some Theoretical Analyses
Partha Niyogi. 23 January, 2008.
Communicated by Partha Niyogi.
Abstract
Manifold regularization (Belkin, Niyogi, Sindhwani, 2004) is a geometrically motivated framework for machine learning within which several semi-supervised algorithms have been constructed. Here we try to provide some theoretical understanding of this approach. Our main result is to expose the natural structure of a class of problems on which manifold regularization methods are helpful. We show that for such problems, no supervised learner can learn effectively. On the other hand, a manifold based learner (that knows the manifold or ``learns'' it from unlabeled examples) can learn with relatively few labeled examples. Our analysis follows a minimax style with an emphasis on finite sample results (in terms of $n$: the number of labeled examples). These results allow us to properly interpret manifold regularization and related spectral and geometric algorithms in terms of their potential use in semi-supervised learning.Original Document
The original document is available in PDF (uploaded 23 January, 2008 by Partha Niyogi).