English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Distance-based classification with Lipschitz functions

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-DD9A-8 Version Permalink: https://hdl.handle.net/21.11116/0000-0005-7162-D
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
https://link.springer.com/content/pdf/10.1007%2F978-3-540-45167-9_24.pdf (Publisher version)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
von Luxburg, U1, 2, Author           
Bousquet, O1, 2, Author           
Affiliations:
1Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497795              
2Max Planck Institute for Biological Cybernetics, Max Planck Society, Spemannstrasse 38, 72076 Tübingen, DE, ou_1497794              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s):
 Dates: 2003-08
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: 2261
DOI: 10.1007/978-3-540-45167-9_24
 Degree: -

Event

show
hide
Title: 16th Annual Conference on Learning Theory and 7th Kernel Workshop (COLT/Kernel 2003)
Place of Event: Washington, DC, USA
Start-/End Date: 2003-08-24 - 2003-08-27

Legal Case

show

Project information

show

Source 1

show
hide
Title: 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
Source Genre: Proceedings
 Creator(s):
Schölkopf, B1, Editor           
Warmuth, MK, Editor
Affiliations:
1 Max Planck Institute for Biological Cybernetics, Max Planck Society, ou_1497794            
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 314 - 328 Identifier: ISBN: 978-3-540-40720-1

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2777 Sequence Number: - Start / End Page: - Identifier: -