Abstract
The semi-supervised learning paradigm allows that a large amount of unlabeled data be classified using just a few labeled data. To account for the minimal a priori label knowledge, the information provided by the unlabeled data is also used in the classification process. This paper describes a semi-supervised technique that uses random walk limiting probabilities to propagate label information. Each label is propagated through a network of unlabeled instances via a biased random walk. The probability of a vertex receiving a label is expressed in terms of the limiting conditions of the walk process. Simulations show that the proposed technique is competitive with benchmarked techniques.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Chapelle, O., Schölkopf, B., Zien, A. (eds.): Semi-Supervised Learning. MIT Press, Cambridge (2006)
Wechsler, H., Kidode, M.: A random walk procedure for texture discrimination. IEEE Transactions on Pattern Analysis and Machine Intelligence 1(3), 272–280 (1979)
Wechsler, H., Citron, T.: Feature extraction for texture classification. Pattern Recognition 12(5), 301–311 (1980)
Grady, L.: Random walks for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 28(11), 1768–1783 (2006)
Bul, S.R., Rabbi, M., Pelillo, M.: Content-based image retrieval with relevance feedback using random walks. Pattern Recognition 44(9), 2109–2122 (2011)
Schll, J., Schll-Paschinger, E.: Classification by restricted random walks. Pattern Recognition 36(6), 1279–1290 (2003)
Zhou, D., Schölkopf, B.: Learning from labeled and unlabeled data using random walks. In: Rasmussen, C.E., Bülthoff, H.H., Schölkopf, B., Giese, M.A. (eds.) DAGM 2004. LNCS, vol. 3175, pp. 237–244. Springer, Heidelberg (2004)
Szummer, M., Jaakkola, T.: Partially labeled classification with markov random walks. In: Advances in Neural Information Processing Systems, pp. 945–952. MIT Press (2001)
Gallager, R.G.: Discrete Stochastic Processes, 1st edn. Springer (1996)
Çinlar, E.: Introduction to stochastic processes. Prentice Hall (1975)
Duin, R., Juszczak, P., Paclik, P., Pekalska, E., de Ridder, D., Tax, D., Verzakov, S.: Prtools4.1, a matlab toolbox for pattern recognition (2007)
Zhou, D., Bousquet, O., Lal, T.N., Weston, J., Schlkopf, B.: Learning with local and global consistency. In: Advances in Neural Information Processing Systems 16, vol. 16, pp. 321–328. MIT Press (2004)
Wang, F., Zhang, C.: Label propagation through linear neighborhoods. IEEE Transactions on Knowledge and Data Engineering 20(1), 55–67 (2008)
Sun, J., Boyd, S., Xiao, L., Diaconis, P.: The fastest mixing markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Review 48(4), 681–699 (2006)
Belkin, M., Niyogi, P.: Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation 15(6), 1373–1396 (2003)
Delalleau, O., Bengio, Y., Roux, N.L.: Nonparametric function induction in semi-supervised learning. In: Workshop Artif. Intell. Stat. (2005)
Zhou, D., Schölkopf, B.: Adaptive computation and machine learning. In: Discrete Regularization, pp. 237–250. MIT Press, Cambridge (2006)
Chapelle, O., Zien, A.: Semi–supervised classification by low density separation. In: Proceedings of the International Workshop on Artificial Intelligence and Statistics, pp. 57–64 (2005)
Joachims, T.: Transductive learning via spectral graph partitioning. In: Proc. Int. Conf. Mach. Learn., pp. 290–297 (2003)
Chapelle, O., Weston, J., Schölkopf, B.: Cluster Kernels for Semi-Supervised Learning. In: NIPS 2002, vol. 15, pp. 585–592. MIT Press, Cambridge (2003)
Corduneanu, A., Jaakkola, T.: Adaptive computation and machine learning. In: Data-dependent Regularization, pp. 163–190. MIT Press, Cambridge (2006)
Sindhwani, V., Niyogi, P.: Beyond the point cloud: from transductive to semi-supervised learning. In: Proc. 22nd Int. Conf. Mach. Learn., pp. 824–831 (2005)
Burges, C.J.C., Platt, J.C.: Adaptive computation and machine learning. In: Semi-supervised Learning with Conditional Harmonic Mixing, pp. 251–273. MIT Press, Cambridge (2006)
Zhu, X., Ghahramani, Z.: Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, School Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, Tech. Rep (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cupertino, T.H., Zhao, L. (2013). Semi-Supervised Learning Using Random Walk Limiting Probabilities. In: Guo, C., Hou, ZG., Zeng, Z. (eds) Advances in Neural Networks – ISNN 2013. ISNN 2013. Lecture Notes in Computer Science, vol 7952. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39068-5_48
Download citation
DOI: https://doi.org/10.1007/978-3-642-39068-5_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39067-8
Online ISBN: 978-3-642-39068-5
eBook Packages: Computer ScienceComputer Science (R0)