Abstract
Recent years have witnessed a surge of interest in graph-based semi-supervised learning. However, two of the major problems in graph-based semi-supervised learning are: (1) how to set the hyperparameter in the Gaussian similarity; and (2) how to make the algorithm scalable. In this article, we introduce a general framework for graphbased learning. First, we propose a method called linear neighborhood propagation, which can automatically construct the optimal graph. Then we introduce a novel multilevel scheme to make our algorithm scalable for large data sets. The applications of our algorithm to various real-world problems are also demonstrated.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Chapelle O, Schölkopf B, Zien A (eds) (2006) Semi-supervised learning. MIT Press, Cambridge
Zhu X (2005) Semi-supervised learning literature survey. Technical Report 1530, University of Wisconsin-Madison
Graf Estes K, Evans JL, Alibali MW, et al (2006) Can infants map meaning to newly segmented words? Statistical segmentation and word learning. Psychol Sci 18(3):254–260
Stromsten SB (2002) Classification learning from both classified and unclassified examples. PhD Dissertation, Stanford
Zhu X, Rogers T, Qian R, et al (2007) Humans perform semisupervised classification too. Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), Vancouver, British Columbia, Canada. AAAI Press, pp 864–869
Zhou D, Bousquet O, Lal TN, et al (2004) Learning with local and global consistency. Adv Neural Inform Process Syst 16:321–328
Belkin M, Niyogi P (2003) Laplacian eigenmaps for dimensionality reduction and data representation. Neural Comput 15(6):1373–1396
Roweis ST, Saul LK (2000) Nonlinear dimensionality reduction by locally linear embedding. Science 290:2323–2326
Seung HS, Lee DD (2000) The manifold ways of perception. Science 290:2268–2269
Belkin M, Matveeva I, Niyogi P (2004) Regularization and semisupervised learning on large graphs. Proceedings of the 17th Conference on Learning Theory vol. 3120, Banff, Canada. Lecture notes in computer science, Springer, pp 624–638
Wang F, Zhang C (2006) Label propagation through linear neighborhoods. Proceedings of the 23rd International Conference on Machine Learning Pittsburgh, PN, ACM, pp 985–992
Wang F, Zhang C (2007) Fast multilevel transduction on graphs. 7th SIAM International Conference on Data Mining, Minneapolis, MN, SIAM
Trottenberg U, Oosterlee CW, Schler A (2001) Multigrid. (With guest contributions from Brandt A, Oswald P, and Sten K) Academic Press, San Diego, London
Sharon E, Brandt A, Basri R (2000) Fast multiscale image segmentation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, South Carolina, Hilton Head Island, SC, USA, IEEE, pp I:70–77
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was presented in part at the 14th International Symposium on Artificial Life and Robotics, Oita, Japan, February 5–7, 2009
About this article
Cite this article
Zhang, C., Wang, F. Graph-based semi-supervised learning. Artif Life Robotics 14, 445–448 (2009). https://doi.org/10.1007/s10015-009-0719-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10015-009-0719-5