Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions Xiaojin Zhu
ZHUXJ@CS.CMU.EDU Zoubin Ghahramani
ZOUBIN@GATSBY.UCL.AC.UK John Lafferty
LAFFERTY@CS.CMU.EDU
School of Computer Science, Carnegie Mellon University, Pittsburgh PA 15213, USA
Gatsby Computational Neuroscience Unit, University College London, London WC1N 3AR, UK Abstract An approach to semi-supervised learning is pro- posed that is based on a Gaussian random field model. Labeled and unlabeled data are rep- resented as vertices in a weighted graph, with edge weights encoding the similarity between in- stances. The learning problem is then formulated in terms of a Gaussian random field on this graph, where the mean of the field is characterized in terms of harmonic functions, and is efficiently obtained using matrix methods or belief propa- gation. The resulting learning algorithms have intimate connections with random walks, elec- tric networks, and spectral graph theor
