6.7. 核近似

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

与使用隐式特征映射的 核技巧 相比，使用近似显式特征映射的优势在于，显式映射更适合在线学习，并且可以显着降低使用非常大的数据集进行学习的成本。标准的核化支持向量机不能很好地扩展到大型数据集，但使用近似核映射，可以使用更高效的线性支持向量机。特别是，将核映射近似与 SGDClassifier 结合使用，可以使大型数据集上的非线性学习成为可能。

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

另请参阅

多项式回归：使用基函数扩展线性模型 用于精确的多项式变换。

6.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 给出。

示例

• 请参阅名为 与时间相关的特征工程 的示例，该示例展示了一个使用 Nystroem 核的有效机器学习管道。

6.7.2. 径向基函数核

RBFSampler 为径向基函数核构建一个近似映射，也称为随机厨房水槽 [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 计算成本更低，因此使用更大的特征空间更有效。

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

示例

• RBF 核的显式特征映射近似

6.7.3. 加性卡方核

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

此处使用的加性卡方核由下式给出

\[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]。

6.7.4. 偏斜卡方核

偏斜卡方核由下式给出

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

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

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

6.7.5. 通过张量草图进行多项式核近似

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

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

其中

• x, y 是输入向量

• d 是核度

直观地说，度为 d 的多项式核的特征空间包含输入特征之间所有可能的度为 d 的乘积，这使得使用此核的学习算法能够解释特征之间的相互作用。

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

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

示例

• 使用多项式核近似进行可扩展学习

6.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)\)，这避免了应用核或存储训练样本的需要。

参考文献

[WS2001]

“使用 Nyström 方法加速核机器” Williams, C.K.I.; Seeger, M. - 2001.

[RR2007] (1,2)

“用于大规模核机器的随机特征” Rahimi, A. and Recht, B. - Advances in neural information processing 2007,

[LS2010]

“偏斜乘法直方图核的随机傅里叶近似” Li, F., Ionescu, C., and Sminchisescu, C. - Pattern Recognition, DAGM 2010, Lecture Notes in Computer Science.

[VZ2010] (1,2)

“通过显式特征映射实现高效的加性核” Vedaldi, A. and Zisserman, A. - Computer Vision and Pattern Recognition 2010

[VVZ2010]

“用于高效检测的广义 RBF 特征映射” Vempati, S. and Vedaldi, A. and Zisserman, A. and Jawahar, CV - 2010

[PP2013]

“通过显式特征映射实现快速且可扩展的多项式核” Pham, N., & Pagh, R. - 2013

[CCF2002]

“在数据流中查找频繁项” Charikar, M., Chen, K., & Farach-Colton - 2002

[WIKICS]

“维基百科：计数草图”