zbMATH — the first resource for mathematics

A note on label propagation for semi-supervised learning. (English) Zbl 1334.68178
Summary: Semi-supervised learning has become an important and thoroughly studied subdomain of machine learning in the past few years, because gathering large unlabeled data is almost costless, and the costly human labeling process can be minimized by semi-supervision. Label propagation is a transductive semi-supervised learning method that operates on the – most of the time undirected – data graph. It was introduced in [X. Zhu and Z. Ghahramani, Learning from labeled and unlabeled data with label propagation. Techn. Rep., Carnegie Mellon Univ. (2002)] and since many variants were proposed. However, the base algorithm has two variants: the first variant presented in [loc. cit.] and its slightly modified version used afterwards, e.g. in [X. Zhu, Semi-supervised learning with graphs. Pittsburgh, PA: Carnegie Mellon University (PhD Thesis) (2005)]. This paper presents and compares the two algorithms – both theoretically and experimentally – and also tries to make a recommendation which variant to use.
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI
[1] O. Chapelle, B. Schölkopf, A. Zien, Semi-Supervised Learning, The MIT Press, Cambridge, 2006. ⇒18, 19, 25
[2] F. Chung, Spectral Graph Theory, volume 92 of Regional Conference Series in Mathematics, AMS, Philadelphia, 1997. ⇒22 · Zbl 0867.05046
[3] J. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., 7, 1 (1956) 48-50. ⇒26 · Zbl 0070.18404
[4] H. Lütkepohl, Handbook of Matrices, John Wiley & Sons, Chichester, 1996. ⇒24 · Zbl 0856.15001
[5] U. von Luxburg, A tutorial on spectral clustering, Stat. Comput., 17, 4 (2007) 395-416. ⇒21, 22, 25
[6] M. W. Trosset, An Introduction to Statistical Inference and Its Applications with R, Chapman & Hall/CRC Texts in Statistical Science, CRC Press, Boca Raton, 2009. ⇒26
[7] X. Zhu, Semi-supervised learning with graphs, PhD thesis, Carnegie Mellon University, Pittsburgh, USA, 2005. ⇒18, 19, 22
[8] X. Zhu, Z. Ghahramani, Learning from labeled and unlabeled data with label propagation, Technical Report CMU-CALD-02-107, Carnegie Mellon University, 2002. ⇒18, 19, 20, 26
[9] X. Zhu, Z. Ghahramani, J. D. Lafferty, Semi-supervised learning using gaussian fields and harmonic functions, Proc. 20th ICML, 2003. pp. 912-919. ⇒28
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.