# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Distance-based classification with Lipschitz functions

##### 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 (*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.

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.