正如您所提到的，存储内核矩阵需要与数据点数量成二次方比例的内存。传统 SVM 算法的训练时间也与数据点的数量呈超线性关系。因此，这些算法对于大型数据集是不可行的。

一种可能的技巧是将核化 SVM 重新表述为线性 SVM。每个元素$K_{ij}$核矩阵的 表示数据点之间的点积$x_i$和$x_j$在将它们（可能是非线性的）映射到特征空间之后：$K_{ij} = \Phi(x_i) \cdot \Phi(x_j)$. 特征空间映射$\Phi$由核函数隐式定义，核化 SVM 不会显式计算特征空间表示。这对于中小型数据集的计算效率很高，因为特征空间可以是非常高维的，甚至是无限维的。但是，如上所述，这对于大型数据集变得不可行。相反，我们可以显式地将数据非线性地映射到特征空间，然后在特征空间表示上有效地训练线性 SVM。可以构造特征空间映射以逼近给定的核函数，但使用比“完整”特征空间映射更少的维度。对于大型数据集，这仍然可以为我们提供丰富的特征空间表示，但维度比数据点少得多。

核近似的一种方法是使用 Nyström 近似（Williams and Seeger 2001）。这是一种使用较小的子矩阵来近似大矩阵的特征值/特征向量的方法。另一种方法使用随机特征，有时称为“随机厨房水槽”（Rahimi 和 Recht 2007）。

在大型数据集上训练 SVM 的另一个技巧是用一组较小的子问题来近似优化问题。例如，在原始问题上使用随机梯度下降是一种方法（在许多其他方法中）。在优化方面已经做了很多工作。Menon (2009) 给出了很好的调查。

参考

威廉姆斯和西格 (2001)。使用 Nystroem 方法加速内核机器。

拉希米和雷赫特 (2007)。大型内核机器的随机特征。

梅农（2009）。大规模支持向量机：算法和理论。