# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Maximal Margin Classification for Metric Spaces

##### MPS-Authors

##### External Resource

https://www.sciencedirect.com/science/article/pii/S0022000004001412

(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

Hein, M., Bousquet, O., & Schölkopf, B. (2005). Maximal Margin Classification for
Metric Spaces.* Journal of Computer and System Sciences,* *71*(3),
333-359. doi:10.1016/j.jcss.2004.10.013.

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

##### Abstract

In order to apply the maximum margin method in arbitrary metric

spaces, we suggest to embed the metric space into a Banach or

Hilbert space and to perform linear classification in this space.

We propose several embeddings and recall that an isometric embedding

in a Banach space is always possible while an isometric embedding in

a Hilbert space is only possible for certain metric spaces. As a

result, we obtain a general maximum margin classification

algorithm for arbitrary metric spaces (whose solution is

approximated by an algorithm of Graepel.

Interestingly enough, the embedding approach, when applied to a metric

which can be embedded into a Hilbert space, yields the SVM

algorithm, which emphasizes the fact that its solution depends on

the metric and not on the kernel. Furthermore we give upper bounds

of the capacity of the function classes corresponding to both

embeddings in terms of Rademacher averages. Finally we compare the

capacities of these function classes directly.

spaces, we suggest to embed the metric space into a Banach or

Hilbert space and to perform linear classification in this space.

We propose several embeddings and recall that an isometric embedding

in a Banach space is always possible while an isometric embedding in

a Hilbert space is only possible for certain metric spaces. As a

result, we obtain a general maximum margin classification

algorithm for arbitrary metric spaces (whose solution is

approximated by an algorithm of Graepel.

Interestingly enough, the embedding approach, when applied to a metric

which can be embedded into a Hilbert space, yields the SVM

algorithm, which emphasizes the fact that its solution depends on

the metric and not on the kernel. Furthermore we give upper bounds

of the capacity of the function classes corresponding to both

embeddings in terms of Rademacher averages. Finally we compare the

capacities of these function classes directly.