Distance-based classification with Lipschitz functions

von Luxburg, U; Bousquet, O

doi:10.1007/978-3-540-45167-9_24

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Distance-based classification with Lipschitz functions

MPS-Authors

/persons/resource/persons76237

von Luxburg, U
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

/persons/resource/persons83824

Bousquet, O
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

External Resource

https://link.springer.com/content/pdf/10.1007%2F978-3-540-45167-9_24.pdf
(Publisher version)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

von Luxburg, U., & Bousquet, O. (2003). Distance-based classification with Lipschitz functions. In B. Schölkopf, & M. Warmuth (Eds.), Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003 (pp. 314-328). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0013-DD9A-8

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. Our approach leads to a general large margin
algorithm for classification in metric spaces. To analyze this
algorithm, we first prove a representer theorem. It states that there
exists a solution which can be expressed as linear combination of
distances to sets of training points. Then we analyze the Rademacher
complexity of some Lipschitz function classes. The generality of the
Lipschitz approach can be seen from the fact that several well-known
algorithms are special cases of the Lipschitz algorithm, among them
the support vector machine, the linear programming machine, and
the 1-nearest neighbor classifier.