Maximal Margin Classification for Metric Spaces
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 arbitrarymetric spaces (whose solution is approximated by an algorithmofGraepel et al. (International ConferenceonArtificialNeuralNetworks1999,pp. 304–309)). Interestinglyenough, theembeddingapproach,when applied to ametric which can be embedded into aHilbert space, yields the support vectormachine (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. © 2004 Elsevier Inc. All rights reserved.