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.

Key words： 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