4.7. 核逼近(Kernel Approximation)¶
该子模块包含一些函数,这些函数逼近(approximate)某些内核对应的特征映射,例如在支持向量机中使用(请看 支持向量机(Support Vector Machines))。 下列特征函数(feature functions)对输入进行非线性变换,可作为线性分类或其他算法的基(basis)。
与隐式使用特征映射的内核技巧(kernel trick)相比,
使用近似显式特征映射的优点是 显式映射(explicit mappings)更适合在线学习,并且可以显著降低大数据集上的学习成本。
标准的核化支持向量机(Standard kernelized SVMs)不能很好地扩展到大型数据集,但是使用近似的内核映射(approximate kernel map)
可以使用效率更高的线性支持向量机(linear SVMs)。特别是,核映射逼近与 SGDClassifier
的结合可以使大型数据集上的非线性学习成为可能。
由于使用近似嵌入(approximate embeddings)的经验工作不多,所以最好在可能的情况下将结果与精确的核方法(exact kernel methods)进行比较。
See also
多项式回归:用基函数展开线性模型 进行精确的多项式变换。
4.7.1. 核逼近的Nystroem方法¶
在 Nystroem
类中实现的Nystroem方法是求解 核的低秩近似(low-rank approximations of kernels) 的一种通用方法。
它实际上是 通过对评估内核的数据进行二次采样(subsampling) 来实现这一点的。默认情况下,Nystroem
使用 rbf
核,
但它可以使用任何核函数(kernel function)或预先计算的核矩阵(kernel matrix)。
使用的样本数,也就是所计算的特征的维数由参数 n_components
给出。
4.7.2. 径向基函数核¶
RBFSampler
类构造了径向基函数核(radial basis function kernel)的近似映射,也被称为 Random Kitchen Sinks [RR2007]。
此转换可用于显式地建模内核映射,在应用线性算法之前,比如 linear SVM
>>> from sklearn.kernel_approximation import RBFSampler
>>> from sklearn.linear_model import SGDClassifier
>>> X = [[0, 0], [1, 1], [1, 0], [0, 1]]
>>> y = [0, 0, 1, 1]
>>> rbf_feature = RBFSampler(gamma=1, random_state=1)
>>> X_features = rbf_feature.fit_transform(X)
>>> clf = SGDClassifier(max_iter=5)
>>> clf.fit(X_features, y)
SGDClassifier(alpha=0.0001, average=False, class_weight=None,
early_stopping=False, epsilon=0.1, eta0=0.0, fit_intercept=True,
l1_ratio=0.15, learning_rate='optimal', loss='hinge', max_iter=5,
n_iter=None, n_iter_no_change=5, n_jobs=None, penalty='l2',
power_t=0.5, random_state=None, shuffle=True, tol=None,
validation_fraction=0.1, verbose=0, warm_start=False)
>>> clf.score(X_features, y)
1.0
该映射依赖于对核值的蒙特卡洛近似(Monte Carlo approximation)。 fit
函数执行蒙特卡洛采样,而 transform
方法执行数据映射。
由于过程本身的随机性,对 fit
函数的不同调用可能会导致不同的结果。
fit
函数有两个参数:n_components
是特征变换的目标维数; gamma
是RBF-kernel的参数。
更高的 n_components
会使核逼近更好,得到的结果与核支持向量机产生的结果更相似。
请注意,“拟合”特征函数实际上并不取决于提供给 fit
函数的数据,只使用数据的维数。有关此方法的详细信息,请参阅 [RR2007].
对于 n_components
的给定值,RBFSampler
通常不像 Nystroem
那样精确。不过,RBFSampler
使用更大的特征空间更高效,计算成本更低。
案例:
4.7.3. 加性 Chi Squared 核¶
The additive chi squared kernel 是一个在直方图上的内核, 经常在计算机视觉中使用。
The additive chi squared kernel 由下式给出:
这和 sklearn.metrics.additive_chi2_kernel
函数不完全一样。
文献 [VZ2010] 的作者们比较喜欢上面这种形式,因为它总是正定的(positive definite)。
由于内核是加性的,因此可以单独处理所有分量 \(x_i\) 以进行嵌入。
这样就可以在规则的区间内对傅里叶变换进行采样,而不是用蒙特卡罗抽样进行近似。
类 AdditiveChi2Sampler
实现了这种按分量进行的确定性采样(component wise deterministic sampling)。
每个分量被采样 \(n\) 次,每个输入维(两者的乘积来源于傅里叶变换的实部和复部) 产生 \(2n+1\) 维 。
在文献中,\(n\) 通常被选择为1或2,把数据集的size变为 n_samples * 5 * n_features
(在 \(n=2\) 的情况下)。
由 AdditiveChi2Sampler
类提供的近似特征映射 可以与 RBFSampler
类提供的近似特征映射 组合在一起
去产生一个用于 指数化chi squared kernel 的近似特征映射。
请看文献 [VZ2010] 获得更多详情 ,在 [VVZ2010] 中介绍了 AdditiveChi2Sampler
与 RBFSampler
的组合方法。
4.7.4. Skewed Chi Squared Kernel¶
The skewed chi squared kernel 由下式给出:
它具有与计算机视觉中常用的 exponentiated chi squared kernel 相似的性质,但允许特征映射的简单蒙特卡罗近似。
SkewedChi2Sampler
类的用法与上面介绍的 RBFSampler
类的用法是一样的。
唯一的区别在自由参数, 被称之为 \(c\) 。 关于此映射的各种详细信息,请参考文献 [LS2010].
4.7.5. 数学方面的细节¶
核方法,如支持向量机或核化PCA,依赖于再生核Hilbert空间的性质。 对于任何正定核函数 \(k\) (一个所谓的Mercer核),保证存在一个映射 \(\phi\) 到Hilbert空间 \(\mathcal{H}\),这样
其中 \(\langle \cdot, \cdot \rangle\) 表示Hilbert空间中的内积。
如果算法(如linear SVM或PCA)仅依赖于数据点 \(x_i\) 的标量乘积,则可以使用 \(k(x_i, x_j)\) 的值, 这相当于将该算法应用于映射得到的数据点 \(\phi(x_i)\) 。 使用 \(k\) 的优点是,不必显式计算映射 \(\phi\),从而允许任意大的特征(甚至无限)。
内核方法的一个缺点是,在优化过程中可能需要存储许多内核值 \(k(x_i, x_j)\) 。 如果将核化分类器应用于新的数据 \(y_j\) ,则需要计算 \(k(x_i, y_j)\) 来作出预测, 可能对训练集中的许多不同的 \(x_i\) 进行预测。
该子模块中的类允许近似 嵌入 \(\phi\) ,从而显式地使用表示形式 \(\phi(x_i)\) , 从而避免了应用内核或存储训练样例的需要。
参考文献:
[RR2007] | (1, 2) “Random features for large-scale kernel machines” Rahimi, A. and Recht, B. - Advances in neural information processing 2007, |
[LS2010] | “Random Fourier approximations for skewed multiplicative histogram kernels” Random Fourier approximations for skewed multiplicative histogram kernels - Lecture Notes for Computer Sciencd (DAGM) |
[VZ2010] | (1, 2) “Efficient additive kernels via explicit feature maps” Vedaldi, A. and Zisserman, A. - Computer Vision and Pattern Recognition 2010 |
[VVZ2010] | “Generalized RBF feature maps for Efficient Detection” Vempati, S. and Vedaldi, A. and Zisserman, A. and Jawahar, CV - 2010 |