Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces |
| |
Authors: | Jürgen Forster Niels Schmitt Hans Ulrich Simon Thorsten Suttorp |
| |
Affiliation: | (1) Lehrstuhl Mathematik & Informatik, Fakultät für Mathematik, Ruhr-Universität Bochum, 44780 Bochum, Germany |
| |
Abstract: | Concept classes can canonically be represented by matrices with entries 1 and –1. We use the singular value decomposition of this matrix to determine the optimal margins of embeddings of the concept classes of singletons and of half intervals in homogeneous Euclidean half spaces. For these concept classes the singular value decomposition can be used to construct optimal embeddings and also to prove the corresponding best possible upper bounds on the margin. We show that the optimal margin for embedding n singletons is
and that the optimal margin for half intervals over {1,...,n} is
. For the upper bounds on the margins we generalize a bound by Forster (2001). We also determine the optimal margin of some concept classes defined by circulant matrices up to a small constant factor, and we discuss the concept classes of monomials to point out limitations of our approach. |
| |
Keywords: | maximal margins Euclidean half spaces singular value decomposition |
本文献已被 SpringerLink 等数据库收录! |