On Consistency of Graph-based Semi-supervised Learning

摘要

Graph-based semi-supervised learning is one of the most popular methods inmachine learning. Some of its theoretical properties such as bounds for thegeneralization error and the convergence of the graph Laplacian regularizerhave been studied in computer science and statistics literatures. However, afundamental statistical property, the consistency of the estimator from thismethod has not been proved. In this article, we study the consistency problemunder a non-parametric framework. We prove the consistency of graph-basedlearning in the case that the estimated scores are enforced to be equal to theobserved responses for the labeled data. The sample sizes of both labeled andunlabeled data are allowed to grow in this result. When the estimated scoresare not required to be equal to the observed responses, a tuning parameter isused to balance the loss function and the graph Laplacian regularizer. We givea counterexample demonstrating that the estimator for this case can beinconsistent. The theoretical findings are supported by numerical studies.