Kernels as features: On kernels, margins, and low-dimensional mappings
Kernels as features: On kernels, margins, and low-dimensional mappings
复制标题
DOI：
10.1007/s10994-006-7550-1
复制
发表时间：
2006-10
期刊：
影响因子：
7.5
通讯作者：
Maria-Florina Balcan;Avrim Blum;S. Vempala
中科院分区：
文献类型：
--
作者：
Maria-Florina Balcan;Avrim Blum;S. Vempala
核函数通常被视为提供了一个隐式的点映射到一个高维空间，如果结果是线性可分的，那么它能够获得该空间的大部分功能而不会产生高成本。然而，Johnson-Lindenstrauss引理表明，在存在较大余量的情况下，核函数也可以被视为到低维空间的映射，只有一个维度。在本文中，我们探讨了一个问题，是否可以有效地产生这样的低维映射，只使用黑盒访问核函数。也就是说，给定一个程序，根据我们选择的输入x计算（x,y），我们能有效地构建一个显式（小）特征集，有效地捕捉隐式高维空间的力量吗？如果我们的方法也允许对底层数据分布（即未标记的示例）进行黑盒访问，那么我们可以肯定地回答这个问题。我们还给出了一个下界，表明如果我们无法访问分布，那么对于任意黑盒核函数这是不可能的；然而，对于标准核函数（如多项式核函数）是否可以这样做，我们留下一个开放的问题。我们的积极结果可以看作是说设计一个好的核函数就像设计一个好的特征空间一样。给定一个核，通过在随机的未标记示例上以黑盒方式运行它，我们可以有效地生成一组显式特征，这样，如果数据在核下是线性可分的，并且边界为γ，那么它在这个新的特征空间中是近似可分的。
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 the result is linearly-separable 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 produce such low-dimensional mappings, using only black-box access to a kernel function. That is, given just a program that computesK(x,y) on inputsx,yof our choosing, can we efficiently construct an explicit (small) set of features that effectively capture the power of the implicit high-dimensional space? We answer this question in the affirmative if our method is also allowed black-box access to the underlying data distribution (i.e., unlabeled examples). We also give a lower bound, showing that if we do not have access to the distribution, then this is not possible for anarbitraryblack-box kernel function; we leave as an open problem, however, whether this can be done 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 canefficientlygenerate 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.