Distance-Based Classification with Lipschitz Functions
Ulrike von Luxburg, Olivier Bousquet; 5(Jun):669--695, 2004.
Abstract
The goal of this article is to develop a framework for large margin
classification in metric spaces. We want to find a generalization of
linear decision functions for metric spaces and define a corresponding
notion of margin such that the decision function separates the
training points with a large margin. It will turn out that using
Lipschitz functions as decision functions, the inverse of the
Lipschitz constant can be interpreted as the size of a margin. In
order to construct a clean mathematical setup we isometrically embed
the given metric space into a Banach space and the space of Lipschitz
functions into its dual space. To analyze the resulting algorithm, we
prove several representer theorems. They state that there always
exist solutions of the Lipschitz classifier which can be expressed in
terms of distance functions to training points. We provide
generalization bounds for Lipschitz classifiers in terms of the
Rademacher complexities of some Lipschitz function classes. The
generality of our approach can be seen from the fact that several
well-known algorithms are special cases of the Lipschitz classifier,
among them the support vector machine, the linear programming machine,
and the 1-nearest neighbor classifier.
[abs][pdf][ps.gz][ps]