Part of Advances in Neural Information Processing Systems 18 (NIPS 2005)
Tong Zhang, Rie Kubota Ando
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.