Research Group of Prof. Dr. M. Griebel
Institute for Numerical Simulation
[1] J. Garcke and M. Griebel. Semi-supervised learning with sparse grids. In M.-R. Amini, O. Chapelle, and R. Ghani, editors, Proceedings of ICML, Workshop on Learning with Partially Classified Training Data, pages 19-28, 2005.
bib | .ps.gz 1 | .pdf 1 ]
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.