Header logo is

Discrete Regularization


Book Chapter


Many real-world machine learning problems are situated on finite discrete sets, including dimensionality reduction, clustering, and transductive inference. A variety of approaches for learning from finite sets has been proposed from different motivations and for different problems. In most of those approaches, a finite set is modeled as a graph, in which the edges encode pairwise relationships among the objects in the set. Consequently many concepts and methods from graph theory are adopted. In particular, the graph Laplacian is widely used. In this chapter we present a systemic framework for learning from a finite set represented as a graph. We develop discrete analogues of a number of differential operators, and then construct a discrete analogue of classical regularization theory based on those discrete differential operators. The graph Laplacian based approaches are special cases of this general discrete regularization framework. An important thing implied in this framework is that we have a wide choices of regularization on graph in addition to the widely-used graph Laplacian based one.

Author(s): Zhou, D. and Schölkopf, B.
Book Title: Semi-supervised Learning
Pages: 237-250
Year: 2006
Month: November
Day: 0

Series: Adaptive computation and machine learning
Editors: O Chapelle and B Sch{\"o}lkopf and A Zien
Publisher: MIT Press

Department(s): Empirical Inference
Bibtex Type: Book Chapter (inbook)

Address: Cambridge, MA, USA
Digital: 0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {Discrete Regularization},
  author = {Zhou, D. and Sch{\"o}lkopf, B.},
  booktitle = {Semi-supervised Learning},
  pages = {237-250},
  series = {Adaptive computation and machine learning},
  editors = {O Chapelle and B Sch{\"o}lkopf and A Zien},
  publisher = {MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = nov,
  year = {2006},
  month_numeric = {11}