Graph-based semi-supervised learning

Abstract

The recent years have witnessed a surge of interests in graph-based semi-supervised learning (GBSSL). In this paper, we will introduce a series of works done by our group on this topic including: 1) a method called linear neighborhood propagation (LNP) which can automatically construct the optimal graph; 2) a novel multilevel scheme to make our algorithm scalable for large data sets; 3) a generalized point charge scheme for GBSSL; 4) a multilabel GBSSL method by solving a Sylvester equation; 5) an information fusion framework for GBSSL; and 6) an application of GBSSL on fMRI image segmentation.

Keywords

graph-based semi-supervised learning (GBSSL) / linear neighborhood propagation (LNP) / point charge model / fMRI image segmentation

References

[1] Chapelle O, Schölkopf B, Zien A. Semi-Supervised Learning. Cambridge: MIT Press, 2006

[2] Zhu X. Semi-supervised learning literature survey. Technical Report 1530, Univ. Wisconsin-Madison. 2005

[3] Graf E K, Evans J L, Alibali M W, Saffran J R. Can infants map meaning to newly segmented words? Statistical segmentation and word learning. Psychological Science, 2007, 18(3): 254-260

[4] Stromsten S B. Classification learning from both classified and unclassified examples. Dissertation for the Doctoral Degree. Palo Alto: Stanford University, 2002

[5] Zhu X, Rogers T, Qian R, Kalish C. Humans perform semisupervised classification too. In: Proceedings of the 22nd AAAI Conference on Artificial Intelligence. 2007, 864-869

[6] Zhou D, Bousquet O, Lal T N, Weston J, Schölkopf B. Learning with local and global consistency. In: Thrun S, Saul L, Schölkopf B, eds. Advances in Neural Information Processing Systems. 2004, 16: 321-328

[7] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2003, 15(6): 1373-1396

[8] Roweis S T, Saul L K. Noninear dimensionality reduction by locally linear embedding. Science, 2000, 290(5500): 2323-2326

[9] Seung H S, Lee D D. The manifold ways of perception. Science, 2000, 290(5500): 2268-2269

[10] Belkin M, Matveeva I, Niyogi P. Regularization and semisupervised learning on large graphs. In: Proceedings of the 17th Conference on Learning Theory. 2004, 624-638

[11] Wang F, Zhang C. Label propagation through linear neighborhoods. In: Proceedings of the 23rd International Conference on Machine Learning. 2006, 985-992

[12] Wang F, Zhang C. Label propagation through linear neigh borhoods. IEEE Transactions on Knowledge and Data Engineering, 2008, 20(1): 55-67

[13] Wang F, Zhang C. Semi-supervised learning based on generalized point charge models. IEEE Transactions on Neural Networks, 2008, 19(7): 1309-1311

[14] Chen G, Song Y,Wang F, Zhang C. Semi-supervised multilabel learning by solving a sylvester equation. In: Proceedings of the 8th SIAM Conference on Data Mining. 2008, 410-419

[15] Song Y, Zhang C. Content based information fusion for semi-supervised music genre classification. IEEE Transaction on Multimedia, 2008, 10(1): 145-152

[16] Song Y, Zhang C, Lee J, Wang F, Xiang S, Zhang D. Semisupervised discriminative classification with application to tumorous tissues segmentation of MR brain images. Pattern Analysis and Applications, 2009, 12(2): 99-115

[17] Wang F, Zhang C. Fast multilevel transduction on graphs. In: Proceedings of the 7th SIAM International Conference on Data Mining. 2007, 157-168

[18] Trottenberg U, Oosterlee C W, Schüler A. Multigrid. San Diego: Academic, 2001

[19] Brandt A, Ron D. Multigrid solvers and multilevel optimization strategies. In: Cong J, Shinnerl J R, eds. Multilevel Optimization and VLSICAD, 2002, 1-69

[20] Sharon E, Brandt A, Basri R. Fast multiscale image segmentation. In: Proceedings IEEE Conference on Computer Vision and Pattern Recognition. 2000, 1: 70-77

[21] Miah M A W. Fundamentals of Electromagnetics. New Delhi: Tata McGraw-Hill Publishing Co Ltd, 1982

[22] Zhu X. Semi-supervised learning with graphs. Dissertation for the Doctoral Degree. Pittsburgh: Carnegie Mellon University, 2005

[23] Chung F R K, Yau S T. Discrete green’s functions. Journal of Combinatorial Theory (A), 2000, 91(1): 191-214

[24] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 2006, 1(1): 1-48

[25] Williams C, Barber D. Bayesian classification with gaussian processes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1998, 20(12): 1342-1351

[26] Williams C K I, Seeger M. Using the Nyström method to speed up kernel machines. In: Proceedings of Advances in Neural Information Processing Systems, Cambridge: MIT Press, 2001: 682-688

[27] Fowlkes C, Belongie S, Chung F, Malik J. Spectral grouping using the Nyström method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 214-225

[28] Press W, Teukolsky S, Vetterling W, Flannery B. Numerical Recipes in C. 2nd ed. Cambridge: Cambridge University Press, 1992

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg