Empirical Inference Conference Paper 2004

Learning from Labeled and Unlabeled Data Using Random Walks

We consider the general problem of learning from labeled and unlabeled data. Given a set of points, some of them are labeled, and the remaining points are unlabeled. The goal is to predict the labels of the unlabeled points. Any supervised learning algorithm can be applied to this problem, for instance, Support Vector Machines (SVMs). The problem of our interest is if we can implement a classifier which uses the unlabeled data information in some way and has higher accuracy than the classifiers which use the labeled data only. Recently we proposed a simple algorithm, which can substantially benefit from large amounts of unlabeled data and demonstrates clear superiority to supervised learning methods. In this paper we further investigate the algorithm using random walks and spectral graph theory, which shed light on the key steps in this algorithm.

Author(s): Zhou, D. and Schölkopf, B.
Journal: Pattern Recognition, Proceedings of the 26th DAGM Symposium
Pages: 237-244
Year: 2004
Day: 0
Editors: Rasmussen, C.E., H.H. B{\"u}lthoff, M.A. Giese and B. Sch{\"o}lkopf
Bibtex Type: Conference Paper (inproceedings)
Event Name: Pattern Recognition, Proceedings of the 26th DAGM Symposium
Digital: 0
Electronic Archiving: grant_archive
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik
Links:

BibTex

@inproceedings{2684,
  title = {Learning from Labeled and Unlabeled Data Using Random Walks},
  journal = {Pattern Recognition, Proceedings of the 26th DAGM Symposium},
  abstract = {We consider the general problem of learning from labeled and
  unlabeled data. Given a set of points, some of them are labeled,
  and the remaining points are unlabeled. The goal is to predict the
  labels of the unlabeled points.  Any supervised learning algorithm
  can be applied to this problem, for instance, Support Vector
  Machines (SVMs). The problem of our interest is if we can
  implement a classifier which uses the unlabeled data information
  in some way and has higher accuracy than the classifiers which use
  the labeled data only.  Recently we proposed a simple algorithm,
  which can substantially benefit from large amounts of unlabeled
  data and demonstrates clear superiority to supervised learning
  methods. In this paper we further investigate the algorithm using
  random walks and spectral graph theory, which shed light on the
  key steps in this algorithm.},
  pages = {237-244},
  editors = {Rasmussen, C.E., H.H. B{\"u}lthoff, M.A. Giese and B. Sch{\"o}lkopf},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  year = {2004},
  slug = {2684},
  author = {Zhou, D. and Sch{\"o}lkopf, B.}
}