On Kernels, Margins, and Low-Dimensional Mappings
On Kernels, Margins, and Low-Dimensional Mappings
复制标题
DOI：
10.1007/978-3-540-30215-5_16
复制
发表时间：
2004-10
期刊：
影响因子：
--
通讯作者：
Maria-Florina Balcan;Avrim Blum;S. Vempala
中科院分区：
文献类型：
--
作者：
Maria-Florina Balcan;Avrim Blum;S. Vempala
核函数通常被视为提供点到高维空间的隐式映射，如果数据在该空间中可通过较大的裕度γ分离，则能够获得该空间的大部分功率而不会产生高成本。然而，Johnson-Lindenstrauss引理表明，在存在大的裕度的情况下，核函数也可以被视为到低维空间的映射，仅是维度之一。在本文中，我们探讨的问题，是否可以有效地计算这样的隐式低维映射，只使用黑盒访问的核函数。如果我们的方法也被允许黑盒访问底层分布（即，未标记的示例）。我们还给出了一个下界，表明这是不可能的任意黑盒核函数，如果我们没有访问的分布。我们留下了开放的问题，是否可以有效地找到这样的映射，而不访问标准的核函数，如多项式kernel.Our积极的结果可以被看作是说，设计一个好的核函数很像设计一个好的特征空间的分布。给定一个核，通过在随机的未标记的样本上以黑盒的方式运行它，我们可以生成一个显式的特征集，使得如果数据在核下是线性可分的，那么它在这个新的特征空间中是近似可分的。
Kernel functions are typically viewed as providing an implicit mapping of points into a high-dimensional space, with the ability to gain much of the power of that space without incurring a high cost if data is separable in that space by a large marginγ. However, the Johnson-Lindenstrauss lemma suggests that in the presence of a large margin, a kernel function can also be viewed as a mapping to alow-dimensional space, one of dimension only. In this paper, we explore the question of whether one can efficiently compute such implicit low-dimensional mappings, using only black-box access to a kernel function. We answer this question in the affirmative if our method is also allowed black-box access to the underlying distribution (i.e., unlabeled examples). We also give a lower bound, showing this is not possible for an arbitrary black-box kernel function, if we do not have access to the distribution. We leave open the question of whether such mappings can be found efficiently without access to the distribution for standard kernel functions such as the polynomial kernel.Our positive result can be viewed as saying that designing a good kernel function is much like designing a good feature space. Given a kernel, by running it in a black-box manner on random unlabeled examples, we can generate an explicit set offeatures, such that if the data was linearly separable with marginγunder the kernel, then it is approximately separable in this new feature space.