Analysis of Spectral Kernel Design based Semi-supervised Learning

Abstract

We consider a framework for semi-supervised learning using spectral decomposition based un-supervised kernel design. This approach sub-sumes a class of previously proposed semi-supervised learning methods on data graphs. We examine various theoretical properties of such meth-ods. In particular, we derive a generalization performance bound, and obtain the optimal kernel design by minimizing the bound. Based on the theoretical analysis, we are able to demonstrate why spectral kernel design based methods can often improve the predictive performance. Ex-periments are used to illustrate the main consequences of our analysis. 1