7.7. 核近似#

此子模块包含用于近似与特定核（例如在支持向量机中使用的核（参见 支持向量机））对应的特征映射的函数。以下特征函数对输入执行非线性转换，可以作为线性分类或其他算法的基础。

与利用隐式特征映射的核技巧相比，使用近似的显式特征映射的优势在于，显式映射更适合在线学习，并且可以显著降低处理非常大的数据集时的学习成本。标准核化 SVM 在处理大型数据集时扩展性不好，但使用近似核映射可以利用效率更高的线性 SVM。特别是，将核映射近似与 SGDClassifier 结合使用可以使在大型数据集上的非线性学习成为可能。

由于使用近似嵌入的经验性工作不多，建议在可能的情况下将结果与精确核方法进行比较。

另请参阅

有关精确多项式转换，请参阅多项式回归：使用基函数扩展线性模型。

7.7.1. 用于核近似的 Nystroem 方法#

Nystroem 方法（如在 Nystroem 中实现）是一种用于核的降秩近似的通用方法。它通过对评估核的数据进行无放回子采样行/列来实现。虽然精确方法的计算复杂度为 \(\mathcal{O}(n^3_{\text{samples}})\)，但近似的复杂度为 \(\mathcal{O}(n^2_{\text{components}} \cdot n_{\text{samples}})\)，其中可以设置 \(n_{\text{components}} \ll n_{\text{samples}}\) 而性能不会显著下降 [WS2001]。

我们可以根据数据的特征构建核矩阵 \(K\) 的特征分解，然后将其拆分为已采样和未采样的数据点。

\[\begin{split}K = U \Lambda U^T = \begin{bmatrix} U_1 \\ U_2\end{bmatrix} \Lambda \begin{bmatrix} U_1 \\ U_2 \end{bmatrix}^T = \begin{bmatrix} U_1 \Lambda U_1^T & U_1 \Lambda U_2^T \\ U_2 \Lambda U_1^T & U_2 \Lambda U_2^T \end{bmatrix} \equiv \begin{bmatrix} K_{11} & K_{12} \\ K_{21} & K_{22} \end{bmatrix}\end{split}\]

其中

  • \(U\) 是正交矩阵

  • \(\Lambda\) 是特征值对角矩阵

  • \(U_1\) 是被选中的样本的正交矩阵

  • \(U_2\) 是未被选中的样本的正交矩阵

鉴于 \(U_1 \Lambda U_1^T\) 可以通过对矩阵 \(K_{11}\) 进行正交化得到，并且 \(U_2 \Lambda U_1^T\) 可以被评估（以及其转置），唯一需要阐明的部分是 \(U_2 \Lambda U_2^T\)。为此，我们可以用已经评估过的矩阵来表示它

\[\begin{split}\begin{align} U_2 \Lambda U_2^T &= \left(K_{21} U_1 \Lambda^{-1}\right) \Lambda \left(K_{21} U_1 \Lambda^{-1}\right)^T \\&= K_{21} U_1 (\Lambda^{-1} \Lambda) \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} U_1 \Lambda^{-1} U_1^T K_{21}^T \\&= K_{21} K_{11}^{-1} K_{21}^T \\&= \left( K_{21} K_{11}^{-\frac12} \right) \left( K_{21} K_{11}^{-\frac12} \right)^T .\end{align}\end{split}\]

在 fit 期间，类 Nystroem 评估基 \(U_1\)，并计算归一化常数 \(K_{11}^{-\frac12}\)。稍后，在 transform 期间，确定基（由 components_ 属性给出）与新数据点 X 之间的核矩阵。然后将该矩阵乘以 normalization_ 矩阵以获得最终结果。

默认情况下，Nystroem 使用 rbf 核，但它可以使用任何核函数或预计算的核矩阵。使用的样本数量（这也是计算出的特征的维度）由参数 n_components 给出。

示例

7.7.2. 径向基函数核（Radial Basis Function Kernel）#

RBFSampler 构造了径向基函数核的近似映射，也称为 Random Kitchen Sinks [RR2007]。这种转换可用于显式建模核映射，然后再应用线性算法，例如线性 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(max_iter=5)
>>> clf.score(X_features, y)
1.0

该映射依赖于对核值的蒙特卡洛近似。fit 函数执行蒙特卡洛采样，而 transform 方法执行数据的映射。由于该过程固有的随机性，不同调用 fit 函数的结果可能会有所不同。

fit 函数接受两个参数：n_components，它是特征转换的目标维度；以及 gamma，它是 RBF 核的参数。更高的 n_components 会导致更好的核近似，并产生与核 SVM 产生的结果更相似的结果。请注意，“拟合”特征函数实际上并不依赖于提供给 fit 函数的数据。只使用了数据的维度。有关该方法的详细信息，请参阅 [RR2007]。

对于给定的 n_components 值，RBFSampler 通常不如 Nystroem 准确。然而，RBFSampler 的计算成本更低，因此使用更大的特征空间效率更高。

../_images/sphx_glr_plot_kernel_approximation_002.png

比较精确 RBF 核（左）和近似（右）#

示例

7.7.3. Additive Chi Squared Kernel（可加卡方核）#

可加卡方核是直方图上的核，常用于计算机视觉。

这里使用的可加卡方核由以下公式给出

\[k(x, y) = \sum_i \frac{2x_iy_i}{x_i+y_i}\]

这与 sklearn.metrics.pairwise.additive_chi2_kernel 并不完全相同。[VZ2010] 的作者更喜欢上面的版本，因为它总是正定的。由于核是可加的，可以对所有分量 \(x_i\) 分别进行嵌入。这使得可以在规则间隔对傅里叶变换进行采样，而不是使用蒙特卡洛采样进行近似。

类 AdditiveChi2Sampler 实现了这种分量式的确定性采样。每个分量采样 \(n\) 次，每输入维度产生 \(2n+1\) 个维度（乘以二是因为傅里叶变换的实部和复部）。在文献中，\(n\) 通常选择为 1 或 2，将数据集转换为大小 n_samples * 5 * n_features（在 \(n=2\) 的情况下）。

AdditiveChi2Sampler 提供的近似特征映射可以与 RBFSampler 提供的近似特征映射结合使用，以产生指数卡方核的近似特征映射。有关详细信息，请参阅 [VZ2010]，有关与 RBFSampler 结合的详细信息，请参阅 [VVZ2010]。

7.7.4. Skewed Chi Squared Kernel（偏态卡方核）#

偏态卡方核由以下公式给出

\[k(x,y) = \prod_i \frac{2\sqrt{x_i+c}\sqrt{y_i+c}}{x_i + y_i + 2c}\]

它具有与计算机视觉中常用的指数卡方核相似的属性，但允许对特征映射进行简单的蒙特卡洛近似。

SkewedChi2Sampler 的用法与上面描述的 RBFSampler 的用法相同。唯一的区别在于自由参数，称为 \(c\)。有关此映射的动机和数学细节，请参阅 [LS2010]。

7.7.5. 通过张量草图（Tensor Sketch）进行多项式核近似#

多项式核 是一种流行的核函数类型，由以下公式给出

\[k(x, y) = (\gamma x^\top y +c_0)^d\]

其中

  • x, y 是输入向量

  • d 是核的度

直观地看，度为 d 的多项式核的特征空间由输入特征之间所有可能的度为 d 的乘积组成，这使得使用此核的学习算法能够考虑特征之间的交互作用。

张量草图（TensorSketch）[PP2013] 方法（如在 PolynomialCountSketch 中实现）是一种可扩展的、与输入数据无关的多项式核近似方法。它基于 Count sketch [WIKICS] [CCF2002] 的概念，这是一种类似于特征哈希（feature hashing）的降维技术，但使用了几个独立的哈希函数。张量草图获取两个向量（或向量与自身）的外积的 Count Sketch，这可以用作多项式核特征空间的近似。特别是，张量草图不显式计算外积，而是计算向量的 Count Sketch，然后通过快速傅里叶变换进行多项式乘法来计算其外积的 Count Sketch。

方便的是，张量草图的训练阶段仅包括初始化一些随机变量。因此，它独立于输入数据，即它仅依赖于输入特征的数量，而不依赖于数据值。此外，此方法可以在 \(\mathcal{O}(n_{\text{samples}}(n_{\text{features}} + n_{\text{components}} \log(n_{\text{components}})))\) 时间内转换样本，其中 \(n_{\text{components}}\) 是所需输出维度，由 n_components 确定。

示例

7.7.6. 数学细节#

像支持向量机或核化 PCA 这样的核方法依赖于再生核希尔伯特空间的特性。对于任何正定核函数 \(k\)（所谓的 Mercer 核），保证存在一个映射 \(\phi\) 到希尔伯特空间 \(\mathcal{H}\)，使得

\[k(x,y) = \langle \phi(x), \phi(y) \rangle\]

其中 \(\langle \cdot, \cdot \rangle\) 表示希尔伯特空间中的内积。

如果一个算法（例如线性支持向量机或 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)\)，从而无需应用核或存储训练样本。

References

[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” Li, F., Ionescu, C., and Sminchisescu, C. - Pattern Recognition, DAGM 2010, Lecture Notes in Computer Science.

[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

[CCF2002]

“Finding frequent items in data streams” Charikar, M., Chen, K., & Farach-Colton - 2002