Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation

  author = {J.~Garcke and M.~Griebel},
  title = {Semi-supervised learning with sparse grids},
  booktitle = {Proceedings of ICML, Workshop on Learning with Partially
		  Classified Training Data},
  editor = {M.-R. Amini and O. Chapelle and R. Ghani},
  pages = {19--28},
  year = {2005},
  ps = { 1},
  pdf = { 1},
  annote = {series,data},
  abstract = {Sparse grids were recently introduced for classication and
		  regression problems. In this article we apply the sparse
		  grid approach to semi-supervised classication. We formulate
		  the semi-supervised learning problem by a regularization
		  approach. Here, besides a regression formulation for the
		  labeled data, an additional term is involved which is based
		  on the graph Laplacian for an adjacency graph of all,
		  labeled and unlabeled data points. It re ects the intrinsic
		  geometric structure of the data distribution. We discretize
		  the resulting problem in function space by the sparse grid
		  method and solve the arising equations using the so-called
		  combination technique. In contrast to recently proposed
		  kernel based methods which currently scale cubic in regard
		  to the number of overall data, our method scales only
		  linear, provided that a sparse graph Laplacian is used.
		  This allows to deal with huge data sets which involve
		  millions of points. We show experimental results with the
		  new approach.}