nips nips2006 nips2006-117 nips2006-117-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Rie K. Ando, Tong Zhang
Abstract: We consider a general form of transductive learning on graphs with Laplacian regularization, and derive margin-based generalization bounds using appropriate geometric properties of the graph. We use this analysis to obtain a better understanding of the role of normalization of the graph Laplacian matrix as well as the effect of dimension reduction. The results suggest a limitation of the standard degree-based normalization. We propose a remedy from our analysis and demonstrate empirically that the remedy leads to improved classification performance.
[1] M. Belkin and P. Niyogi. Semi-supervised learning on Riemannian manifolds. Machine Learning, Special Issue on Clustering:209–239, 2004.
[2] F. R. Chung. Spectral Graph Theory. Regional Conference Series in Mathematics. American Mathematical Society, Rhode Island, 1998.
[3] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849–856, 2001.
[4] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell, 22:888–905, 2000.
[5] M. Szummer and T. Jaakkola. Partially labeled classification with Markov random walks. In NIPS 2001, 2002.
[6] T. Zhang and R. K. Ando. Analysis of spectral kernel design based semi-supervised learning. In NIPS, 2006.
[7] D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Schlkopf. Learning with local and global consistency. In NIPS 2003, pages 321–328, 2004.
[8] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In ICML 2003, 2003.