Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces
Estimating the Optimal Margins of Embeddings in Euclidean Half Spaces
复制标题
估计欧几里得半空间中嵌入的最佳边距
DOI：
10.1023/a:1022905618164
复制
发表时间：
2001
期刊：
影响因子：
7.5
通讯作者：
T. Suttorp
中科院分区：
文献类型：
--
作者：
J. Forster;N. Schmitt;H. Simon;T. Suttorp
AbstractConcept 类可以规范地由条目为 1 和 -1 的矩阵表示。我们使用该矩阵的奇异值分解来确定单例概念类和齐次欧几里德半空间中半间隔的嵌入的最佳边距。对于这些概念类，奇异值分解可用于构造最佳嵌入，并可证明相应的最佳可能上限。我们证明嵌入 n 个单例的最佳边距是
$$\tfrac{n}{{3n - 4}}$$
并且 {1,...,n} 上半个间隔的最佳余量为
$$\tfrac{\pi }{{2\ln n}} + \Theta (\tfrac{1}{{(\ln n)^2 }})$$
。对于边缘的上限，我们概括了 Forster (2001) 的界限。我们还确定了由循环矩阵定义的一些概念类的最佳边际，直到一个小的常数因子，并且我们讨论了单项式的概念类以指出我们方法的局限性。
AbstractConcept 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
$$\tfrac{n}{{3n - 4}}$$
and that the optimal margin for half intervals over {1,...,n} is
$$\tfrac{\pi }{{2\ln n}} + \Theta (\tfrac{1}{{(\ln n)^2 }})$$
. 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.