核方法（七）：大规模核方法——Nystrom 近似与随机傅里叶特征

你想拿 RBF SVM 去跑一个百万规模的图像分类任务。Gram 矩阵是 $10^6 \times 10^6$ 的 double 数组，整整 8 TB。光是这一个数字——八个 TB 的内存，仅仅为了存那个核矩阵——就解释了为什么大部分在统计课上学过核方法的工程师，在真实生产环境里都默默不再碰它。核技巧用一次内积就送你一个无穷维特征空间；账单是在你有 $n^2$ 对数据时寄到。

本系列前六篇把核方法的故事从头讲到尾，但都没碰到扩展性这个问题：把数据抬进 RKHS（第 1 -3 篇）、按你的先验挑核（第 4 篇 ）、解凸优化跑 SVM（第 5 篇 ），或者用 GP 做精确贝叶斯推断（第 6 篇 ）。这一篇要介绍把核方法从 $n \lesssim 10^4$ 的小作坊里解放出来的两个工业级技巧：Nystrom 近似（Williams & Seeger 2001）和随机傅里叶特征 RFF（Rahimi & Recht 2007）。它们都把核方法降维成了在一个显式的低维特征映射上的线性方法，代价是用精度换内存——换那块能装进 16 GB 的内存。

为什么这两个想法这么晚才出现。 核 SVM 在 1995 年就有了，但近似算法等到 2001（Nystrom）、2007（RFF）才被认真做。原因是 2000 年前后数据规模才开始超过精确核能扛的红线——之前 $n < 10^4$ 没人觉得有问题。这两个工作的精彩之处不在数学本身（Bochner 1933、Nystrom 1928，都是上世纪上半叶的经典定理），而在"该用什么经典工具解决这个新问题"的眼力。后面会反复看到这个模式：可扩展核方法的每一步突破都是"把一个老的数学工具搬到一个新的工程瓶颈上"。

计算瓶颈：核方法的诅咒#

三个数字就讲完了核方法在 $n$ 个训练点上的故事。

1. 内存：$O(n^2).$ 你得把 Gram 矩阵 $K \in \mathbb{R}^{n \times n}$ 存下来——要么求逆（GP、核岭回归），要么分解（SVM 对偶），哪怕只是计算它作用在一个向量上。
2. 训练时间：$O(n^3).$ 对一个 $n \times n$ 稠密矩阵做求逆或 Cholesky 分解是三次复杂度。SVM 对偶用 SMO 这类算法每个 epoch 名义上是 $O(n^2),$ 但常数和 epoch 数加起来在难题上会把你拽回近似三次。
3. 每条查询的预测时间：$O(n \cdot d).$ 根据表示定理，解长这样：$f(x) = \sum_i \alpha_i K(x_i, x).$ 即使大部分 $\alpha_i = 0$ （SVM 里只有支持向量留下来），真实数据上你通常也有上千个，每个还得做一次 $d$ 维核评估。

严格说复杂度也分输入。 上面三个数字默认是稠密 $K$ 。如果你有任何结构能让 $K$ 稀疏或者结构化（核就是低秩、Kronecker、Toeplitz），那 $O(n^3)$ 可以压到 $O(n^2)$ 甚至更低。但在 ML 实际场景里这些结构很罕见——除非你专门选了一个会产生这种结构的核（比如周期核 + 单维网格化输入）。“任意 PD 核 + 任意输入"在没近似的前提下就是 $O(n^3)$ ，不能绕。

把数字铺开看：在 $n = 10^4$ 时，Gram 矩阵 800 MB，$K^{-1}$ 几秒搞定。$n = 10^5$ 时变成 80 GB——已经超过大多数工作站内存——求逆得算几个小时。$n = 10^6$ 时就是开头那个 8 TB，哪怕用顶级 GPU 也要几周；更现实的是你在某个 Cholesky 半路 OOM，连一次失败的尝试都跑不完。同时一个线性模型在同份数据上几分钟就能跑完，深度网络几个小时。所以一个不太愉快的事实是：在 2026 年，精确的核方法是个 $10^3$ –$10^4$ 量级的技术，再往上一切都是某种近似。

一个常被引用的对照表，把 $n$ 翻十倍带来的代价摊开：

读法：精确核每行 $n$ 翻 10 倍训练时间约翻 1000 倍（三次方），RFF 翻 10 倍（线性）。两条曲线在 $n \approx 10^4$ 交叉，越往右近似的回报越夸张。这就是过去十年随机特征/Nystrom 取代精确核成为默认的根本原因。

预测端同样窒息。 $n = 10^5$ 时 SVM 拍下来一半样本是支持向量并不少见；每来一条新输入要算 $5 \times 10^4$ 次 RBF 内积，单点延迟在毫秒级就已经躺在了在线系统的边缘。GP 更过分：预测均值要 $O(n)$ 评估再加一次 $K^{-1} y$ 预乘（一次性 $O(n^3)$ ，但每次要预测协方差时还要再做一次 $O(n^2)$ 的二次型）。真实部署里"训练扛得住，推理顶不住"的故事比反过来还常见。

显式特征空间维度的另一个视角。 RBF 核的 Mercer 展开里特征数是无穷的，但 有效维度（按谱值衰减算）通常远小于 $n$ 。具体来说，定义有效维度 $d_{\text{eff}}(\lambda) = \sum_k \lambda_k / (\lambda_k + \lambda)$ ，对常见数据集和合理的 $\lambda$ 它通常在 100 到 1000 之间。这就是为什么 $m = 500$ 的 Nystrom 或 $D = 1000$ 的 RFF 几乎总够用：你要近似的不是"无穷维特征空间”，而是一个有效维度只有几百的有效子空间。这条观察是 2010 年后整个"sketching for ML"理论的基础。

一个数字感受： 一台 8 卡 H100（约 80 GB HBM × 8 = 640 GB 显存）的工作站，能放下的最大稠密 RBF Gram 矩阵也就 $n \approx 2.8 \times 10^5$ ——这还没算优化器状态、梯度、损失函数中间值。对比同样硬件能训练 70B 参数的稠密 Transformer，这就是核方法 vs 神经网络在 2026 年的核心代差：参数线性扩展，核矩阵二次扩展。

两条路。 攻克 $O(n^2)$ 内存墙的策略本质上只有两条：

• 近似核矩阵。 把 $K$ 换成一个能廉价存储、廉价求逆的低秩或块结构矩阵。这就是 Nystrom 近似以及它的一大堆亲戚（随机采样、leverage score、带预条件子的共轭梯度、KISS-GP 这类结构化插值）。直觉：你信 $K$ 大部分能量集中在前几百个特征值，所以用一个秩 $m$ 的代理就行。
• 近似特征映射。 构造一个显式、有限维的 $\hat\phi(x) \in \mathbb{R}^D$ ，使得 $\hat\phi(x)^T \hat\phi(y) \approx K(x, y),$ 然后在 $\hat\phi(X)$ 上跑线性模型。这就是随机傅里叶特征（以及 Quasi-Random/Orthogonal RFF、Fastfood 等一打变种）。直觉：你不再用核技巧"隐式"工作，而是显式把数据抬进 $\mathbb{R}^D$ ，下游什么线性方法都能跑。

第一条是数据相关的：它看你的 $X$ ，挑出一组聪明的低秩基，所以能利用聚类结构和谱集中。第二条是数据无关的：它从核特有的分布里抽随机频率，作为一个通用的显式基，所以能流式处理、能塞进 SGD。两者都把核 SVM 或核岭回归压成 $D \ll n$ 的 $D$ 维线性问题，整场比赛就这个；剩下的全是数学和实操细节。第三类思路是多分辨率 / 层次方法（H-matrix、HODLR、KeOps），把 $K$ 当稀疏块矩阵处理；它们工程更重、理论更弱，目前仍是小众，本文不深入。

一个常被问的问题：为什么这两条路都是"线性方法"？ 因为正定核都可以写成 $K(x, y) = \langle \phi(x), \phi(y) \rangle_{\mathcal H}$ （Mercer / RKHS 那一套，见 第 3 篇 ）。Nystrom 用 $K_{mm}$ 的特征向量给出 $\phi$ 的一个 $m$ 维投影，RFF 用 Monte Carlo 给出 $\phi$ 的一个 $D$ 维采样近似——但两者本质上都是在算 $\phi$ ，然后在 $\phi(X)$ 上做线性模型。所谓"核方法的可扩展化"，几乎全是在变着花样估 $\phi$ 。

Nystrom 近似的核心思想#

Nystrom 方法（19 世纪用于积分方程数值求解的求积分技巧，2001 年 Williams 和 Seeger 把它搬进 ML）从一个观察出发：RBF 或 Matern 核的 Gram 矩阵在几乎所有真实数据上特征值都衰减得很快。RBF 核"无穷维特征空间"的说法没错，但在任何有限样本上，谱都是指数衰减的。通常前几百个特征值就吃掉 99% 的迹。一组具体数字：CIFAR-10 子集 $n = 10^4$ 的 RBF Gram 矩阵（$\gamma$ 用中位数启发），前 50 个特征值通常占迹的 90%，前 300 个占 99%；MNIST 衰减更快，前 100 个就接近 99%。这是 Nystrom 能在 $m = 500$ 时给出几乎和精确解一致精度的根本原因。

矩阵如果近似低秩，那么从中聪明地抽 $m \ll n$ 行 $m$ 列也应该能抓住绝大部分行为。这正是 Nystrom 在做的事。它和 SVD 的区别在于：SVD 给最佳秩 $m$ 近似但要看整个 $K$ ，开销 $O(n^3)$ ；Nystrom 只要看 $K_{nm}$ ，开销 $O(nm \cdot d + m^3),$ 代价是误差比最优近似多一个谱尾项。

其中 $K_{mn} = K_{nm}^T.$ 它至多是秩 $m$ 的，需要 $O(nm)$ 存储，$O(m^3)$ 求逆，并且在 $m \times m$ 这个块 $K_{mm}$ 上是精确的（验证一下：$\hat K_{II} = K_{mI} K_{mm}^{-1} K_{Im} = K_{II}$ ）。

直觉。 你在说"以后预测任何新点，我都让它先过一遍 landmark"。landmark 充当一组固定的基，所有其他点都通过它们来表达。$n = 10^6$ 配 $m = 1000$ 时这套构造的内存账：$K$ 本身 8 TB 装不下，$K_{nm}$ 是 $10^6 \times 10^3 \times 8$ 字节 $= 8$ GB，能装进单机；$K_{mm}^{-1}$ 是 $8$ MB，完全是零头。一千倍的内存压缩，是这条路最直接的回报。

和 SVD 的关系。 严格说，Nystrom 等价于先把 $K$ 的列空间投影到 $K_{nm}$ 张成的子空间，再在那个子空间里做完整的近似。如果你能直接对 $K$ 做秩 $m$ 截断 SVD（俗称 best rank-$m$ approximation），你拿到的是 $\|K - K_m\|_F$ 最小的近似——但代价是 $O(n^2 m)$ 。Nystrom 只看 $K_{nm}$ ，开销降到 $O(nm \cdot d)$ ，代价是误差比 SVD 多一个谱尾项 $\|K - K_r\|_F$ 。所以：“Nystrom = 廉价随机化的截断 SVD"是一个相当准确的心智模型。

和 CUR / 列采样的关系。 数值线性代数里有一个更老的"CUR 分解"族——选 $m$ 列、$m$ 行做近似 $A \approx CUR$ 。Nystrom 是 CUR 在对称半正定矩阵上的特例：$C = K_{nm} = R^T$ ，$U = K_{mm}^{-1}$ 。所以核方法的可扩展化和数值代数的稀疏化共享一套数学骨架；2018 年后的 randomised numerical linear algebra（RandNLA）综述里，Nystrom 几乎是标准入门例子。这条联系一旦看清，你就能从 NLA 文献里直接借用很多 sharp 的分析结果——比如 Cohen et al. 的"近似 leverage score 算法 + Nystrom"组合给出当前的紧界。

Nystrom 数学推导#

我把为什么 $\hat K = K_{nm} K_{mm}^{-1} K_{mn}$ 是正确的近似（而不是其他低秩猜测）讲清楚。两个推导：一个走 Nystrom 继承的积分方程，一个走特征分解。

所以 Nystrom 近似等价于用一个 $m$ 维的显式特征映射，这个映射本质上是在 landmark 子集上做了一次 kernel PCA。

这里就是关键：Nystrom 把你的核方法变成了 $\mathbb{R}^m$ 上的线性方法。 你只用算一次 $\Phi_n,$ 成本 $O(nm \cdot d + m^3),$ 然后在它上面跑线性 SVM / 线性岭回归，$O(nm^2)$ 时间，$O(nm)$ 内存。比起原来的 $O(n^3)$ 时间和 $O(n^2)$ 内存，只要 $m \ll n,$ 这就是巨大的胜利。把数字钉死：$n = 10^6, m = 10^3, d = 10^2,$ 训练阶段总开销大约 $10^{12}$ FLOP，单卡 GPU 几分钟跑完；同样数据精确核要 $10^{18}$ FLOP，差六个数量级。

$\Phi_n$ 也能用作下游模型的"通用嵌入”。 一次算好的 $\Phi_n$ 可以喂进任何下游线性算法——SVM、LR、岭回归、感知机、甚至 t-SNE 当输入。这一点是 Nystrom 相对精确核 SVM 的一个被低估的优势：精确 SVM 算出的 $\alpha_i$ 只能给那一个 SVM 用，换个下游模型要重训；Nystrom 的 $\Phi_n$ 是模型无关的"显式核特征"，存一份就够。MLOps 角度看，这把"训一次模型"变成了"训一次嵌入再多次接 head"，工程友好度大幅提升。

1928 年原版 Nystrom 用的是均匀求积；现代 ML 版本改用随机采样，因为经验测度长那样——一句话：用经验分布替换 Lebesgue 测度，把积分变成 Monte Carlo 和。这个翻译看似平凡，但它解释了一个常见的迷思：“Nystrom 为什么没有保证收敛到真核积分？“答案是：经验测度本身就只能弱收敛到真分布，所以你能拿到的最好结果就是"在经验分布下精确，在真分布下偏一点”。这跟所有的经验风险最小化共享同一个统计学瓶颈。

只要 $m \gtrsim r \log r / \epsilon^2.$ 核心结论：误差被谱尾 $\|K - K_r\|_F$ 主导。 如果你的核谱衰减快（光滑数据上的 RBF：是的），小 $m$ 就够；如果衰减慢（噪声大的高维数据上的 RBF：也许），你需要更大的 $m.$ 经验上对图像 / 文本嵌入 $m = 500$ 就能把测试精度做到精确解的 0.5% 以内，再翻倍换来的常常是统计意义不显著的小数点后两位。

这个界的两个潜台词。 第一，“高概率"是关于 landmark 采样的随机性而言；同一份数据不同 landmark 采样，单次实现的误差可能比平均值高几倍。所以小 $m$ 时多跑几个种子取最好的，这是免费的精度提升。第二，$\epsilon \cdot \mathrm{tr}(K)$ 这一项告诉你"绝对误差大致正比于 $\mathrm{tr}(K)$ "——如果你的核没归一化（$K(x, x) \neq 1$ ），这个项会和你期待的精度差量级出入很大。一个常见的修正：把核改成 $K(x, y) / \sqrt{K(x, x) K(y, y)}$ （即 cosine 归一化的核），让 $\mathrm{tr}(K) = n$ 是一个干净的数，绝对误差跟着 $\epsilon$ 走。

把这个界翻成可操作的话：先粗算 $K_{mm}$ 的特征值，看第 $m$ 个是不是已经远小于第一个的千分之一；是，就说明 $m$ 选大了，可以砍半再试；否，就把 $m$ 翻倍。一两次迭代基本就能定位到合适的预算。

数值陷阱。 当 landmark 之间靠得太近时，$K_{mm}$ 接近奇异，$K_{mm}^{-1}$ 就危险。实践中你用伪逆 $K_{mm}^+,$ 或者带正则的逆 $(K_{mm} + \mu I)^{-1}$ （$\mu > 0$ 很小），或者截断的特征分解，只保留阈值以上的 $\lambda_k.$ sklearn.kernel_approximation.Nystroem 默认就做截断。一个常被忽视的坑：如果你做了 K-means 选 landmark，又恰好两个聚类中心几乎重合（高维稀疏数据上很常见），$K_{mm}$ 的条件数可能瞬间炸到 $10^{14}$ ；这种情况打印一下 np.linalg.cond(K_mm)，超过 $10^{10}$ 就该加正则或减 $m$ 。

误差的几何直觉。 Nystrom 误差 $K - \hat K$ 是一个秩至少 $n - m$ 的半正定矩阵——所有"丢失的"信息都集中在与 landmark 子空间正交的那部分函数空间里。这意味着两类预测会被系统性地搞坏：(a) 测试点 $x^*$ 离所有 landmark 都很远（外推），核近似把它压向零；(b) 决策边界正好穿过 landmark 之间的"裂缝”，模型在那一片几何区域的分辨率就比该有的低。对策：要么加 landmark，要么换 K-means / leverage 让 landmark 更均匀覆盖支撑集。

Nystrom 实战：scikit-learn 配方#

用户侧的食谱简单到惊人。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

from sklearn.kernel_approximation import Nystroem
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import make_pipeline

pipe = make_pipeline(
    Nystroem(kernel="rbf", gamma=0.5, n_components=500, random_state=0),
    LogisticRegression(max_iter=2000, C=1.0),
)
pipe.fit(X_train, y_train)
print("test acc:", pipe.score(X_test, y_test))

完事。Nystroem 是一个特征映射转换器，输出上面推导里那个 $m$ 维 $\Phi_n;$ 下游全是普通线性模型机制。三个旋钮要心里有数：

• n_components（也就是 $m$ ）。 最重要的超参，一个就好。更大 $m$ = 更好的近似 = 更慢的训练。原型阶段从 $m = 256$ 开始；生产推到 500-2000；$m > 5000$ 边际精度提升通常不值得那个时间。把它和 $n$ 的比例钉一下：$m / n \approx 10^{-3}$ 到 $10^{-2}$ 是健康区间，再小近似垮，再大不划算。
• kernel 及其参数。 语法和 sklearn.metrics.pairwise.PAIRWISE_KERNEL_FUNCTIONS 一致："rbf"、"polynomial"、"sigmoid"、"laplacian"，或者一个 callable。RBF / Laplacian 的 gamma 跟 SVC(kernel='rbf') 一样调。
• random_state。 Nystroem 默认均匀随机挑 landmark。类别大致平衡时没问题；不平衡数据上你可能想要分层采样（手动挑 landmark），否则少数类的几何信息会被丢掉，下游分类器再怎么调也补不回来。

性能与 $m$ 的 sigmoid 形状。 把 Nystrom 在固定数据上跑一遍，$m$ 从 50 扫到 5000，画一条"测试精度 vs $m$ “曲线：你几乎总是看到经典的 sigmoid——前半段 $m$ 翻倍精度大涨，超过某个 $m^*$ 之后曲线趋平。$m^*$ 大致对应 $K$ 谱里"前 95% 能量"的截止点；CIFAR-10 这种数据 $m^* \approx 500$ ，SVHN 大约 $m^* \approx 1200$ ，Wiki 文本嵌入 $m^* \approx 2000$ 。第一次跑一个新数据，扫这条曲线只需 1-2 小时，能省下后续无穷无尽的”$m$ 是不是不够大"的争论。

Landmark 选取策略，按质量排序。 均匀随机是默认，但当你算得起的时候，四种替代方案通常更好。

1. 均匀随机。 $O(m)$ 开销。默认；平衡、行为良好的数据上 work。失败模式：当少数类占比 $\leq 1\%$ 时，$m = 500$ 大概率没采到任何少数类点。
2. K-means landmark。 在 $X$ 上跑 $k$ -means，把 $m$ 个聚类中心作为 landmark。$O(nm \cdot d)$ 开销（一次 $k$ -means pass）。几乎总比均匀随机精度高 10-30%；$k$ -means 聚类的几何结构镜像数据流形的几何结构，所以你把更多 landmark 花在数据密集的地方。这也意味着对噪声敏感：少数远离主流形的离群点很容易吃掉一个 landmark 配额。
3. Leverage score 采样。 以正比于 $\ell_i = [K K^{-1}]_{ii}$ （点 $i$ 的leverage score）的概率抽 landmark $i.$ 理论上这是任何基于采样的近似的最优分布（Alaoui & Mahoney 2014）；实践中精确计算很贵——你需要 $K^{-1}$ ，但 $K^{-1}$ 正是你想避开的东西——存在用一次低秩近似来估 leverage 的递归算法。
4. 贪心 / 行列式点过程（DPP）。 在 $m$ 个 landmark 的选择上最大化 $\det(K_{mm}).$ 给你最"散开"的 landmark 集合。贪心 $O(nm^2);$ 精确 DPP 是指数级。

一个我反复推荐的"懒人组合”： K-means 选 $0.8 m$ 个 landmark，再均匀随机抽 $0.2 m$ 个补上。前者保证主流形覆盖，后者保证尾部和离群区域不被完全忽略。开销基本和纯 K-means 一样，但 $m \in [200, 2000]$ 区间里我从没见过它输给纯策略。

按我的经验，K-means landmark 是合理的默认——多写两行代码，几秒跑完，$m \leq 1000$ 时对近似精度有实质提升。$m > 5000$ 时均匀随机会追上，因为谱尾本身已经主导误差。一个混合策略也常用：先 K-means 拿 80% 的 landmark，再均匀随机补 20%，对抗 K-means 在稀疏区域采样不足的弱点。

Nystrom vs RFF 的方差对比。 同样 $m = D = 500$ 的预算下，Nystrom 单次运行误差小但运行之间方差大（不同随机 landmark 集差异显著）；RFF 反过来，单次误差大但方差更可控。原因是 Nystrom 的误差由"landmark 是否能张成谱主子空间"这个离散事件主导，要么命中要么打偏；RFF 是连续的 Monte Carlo，集中不等式给的是 $1/\sqrt{D}$ 的稳态行为。实际部署时如果你要"一次跑成"，Nystrom 更可能给出最好结果；如果你要"反复部署都稳定"，RFF 安全感更强。

这条对比落到 A/B 测试上是怎样的。 团队 A 跑 Nystrom $m = 500$ + LR 拿到 98.7% 测试精度；团队 B 跑 RFF $D = 500$ + LR 拿到 98.5%。看起来 A 赢了。但 A 换种子重跑十次，精度区间是 [97.8%, 99.0%]；B 同样实验区间是 [98.3%, 98.7%]。这时谁赢就不明显了——B 更可预测，A 平均更好但下限更低。生产里我倾向 B（运维负担小），研究里我倾向 A（追求 best case）。这不是技术问题，是组织问题。

少有人提的"种子稳定性即模型稳定性"。 部署一个对种子敏感的模型意味着每次重训（哪怕数据没变）业务指标都会抖；下游的算法迭代、A/B 实验、监控告警的基线全部受影响。所以"种子方差 ≤ 0.3%“应该是上线门槛之一，不该到事后才补。具体做法很简单：固定数据，扫 5 个种子，看测试指标 std；超 0.3% 就把 $m$ 或 $D$ 翻倍直到达标。这条规则在过去三年我亲历过两次"模型上线一个月发现指标周期性抖动 ±2%“的事故，根因都是种子方差被忽视。

Nystrom 适用场景速写。 $n$ 在 $10^4$ 到 $10^6$ 之间；数据有清晰的几何结构（所以 K-means landmark 讲得通）；你想要一个模型，而不是在子样本上重复训练很多次；下游是标准线性模型任务（SVM、逻辑回归、岭回归、核 PCA 可视化）。明确不适用：数据是流式的、核非平稳、或者 $n > 10^7$ （这时候应该上 RFF 配 SGD，或者直接换 SVGP）。

与降维方法的对比。 一个常见误解：“Nystrom 不就是 kernel PCA 取前 $m$ 主成分吗？” 不是。Kernel PCA 用 $K$ 全部 $n$ 个特征向量的前 $m$ 个，要做完整 $O(n^3)$ 特征分解；Nystrom 只看 $K_{mm}$ 的特征向量再投影回去，开销是 $O(nm \cdot d + m^3)$ 。两者收敛到同一极限（都是秩 $m$ 近似），但路径不同：Kernel PCA 是"先看全再降维”，Nystrom 是"先采样再做线性代数”。可扩展性的差距就是这两条路的差距。

和 random projection / Johnson-Lindenstrauss 的关系。 JL 引理说：把 $n$ 个点用一个随机线性映射压到 $O(\log n / \epsilon^2)$ 维，成对距离能保到 $1 \pm \epsilon$ 。这跟 RFF 看起来很像（都是"随机降维"），但本质不同：JL 保的是欧氏距离，RFF 保的是核值；JL 的目标函数是 $L^2$ 几何，RFF 的目标函数是 RKHS 内积。两者在线性核上重合，在非线性核上分道扬镳。理解了这一点，“为什么 JL 没有取代 RFF"就有了干净答案——它们解决的根本不是同一个问题。

一个完整的 Nystrom + 核 PCA 例子。 把 Nystrom 当通用的"非线性嵌入器"也常用，下游接 t-SNE 或可视化：

1
2
3
4
5
6
7
8

from sklearn.kernel_approximation import Nystroem
from sklearn.decomposition import PCA
import numpy as np

# n=50000 的高维数据，想要 2D 可视化
nys = Nystroem(kernel="rbf", gamma=0.1, n_components=300, random_state=0)
Phi = nys.fit_transform(X)              # (50000, 300) 显式核特征
Z = PCA(n_components=2).fit_transform(Phi)   # 在显式空间里做线性 PCA = 核 PCA

这就是 Nystrom 给可视化流水线带来的好处：精确核 PCA 在 $n = 5 \times 10^4$ 上 OOM，Nystrom 版几秒搞定。同样的套路换成 Nystroem + UMAP / t-SNE 也成立，事实上 RAPIDS 的 cuML 库里 UMAP 实现就内部用了一个 Nystrom-like 的核近似来加速。这告诉你一件事：你以为是"可视化算法"的工具，背后往往也躺着 Nystrom 的影子。

这段例子里的一个细节。 n_components=300 不是随便选的——这个数据 50k 点的 RBF 谱，前 300 个特征值大致占 99% 的迹（用 np.linalg.eigvalsh(K[:1000, :1000]) 在子样上看）。如果你跳过这个谱检查直接拍 $m = 100$ ，可视化结果可能丢失大量的类别分离信息；拍 $m = 3000$ 又是浪费。“先看谱再选 $m$ “是从这条小例子能带走的最有价值的习惯。

随机傅里叶特征：用 Bochner 定理拿入场券#

Nystrom 方法是数据相关的：它要先看你的训练集再挑 landmark。随机傅里叶特征（RFF），Rahimi 和 Recht 2007 年在 NeurIPS 拿了 test-of-time 奖的工作，走的是相反路线——一个数据无关的随机特征映射，对任何平移不变核都 work。它的革命性在于：你不需要知道任何关于 $X$ 的事，就能写出一个固定维度的嵌入，使得标准线性 SVM 在嵌入上的解就近似等于 RBF 核 SVM 的解。

数学底层是调和分析里最漂亮的定理之一。

换句话说，每个平移不变 PD 核都是某个概率分布的特征函数（把 $p$ 归一化到积分为 1 之后）。核就是它谱密度的逆傅里叶变换。这一句话联通了两个看起来无关的领域：核方法（统计学习）和谐分析（数学物理），告诉你"什么核合法"和"什么分布合法"是同一个问题。

这定理为什么这么深。 正定性是核方法的入场券（第 2 篇 ），但直接验证一个候选 $k$ 是不是 PD 通常很难——你得对所有有限点集证 $K \succeq 0$ 。Bochner 把这个难题翻译成一个分析问题：检查 $k$ 的傅里叶变换是不是非负。对像 RBF、Laplacian 这种闭式核，这一步只需一行验算；对自定义的核（比如你想拼一个"周期 + 局部 + 长程"的复合核），Bochner 也给你一个干净的合法性检查器。核工程的整个上层建筑都站在它上面。

常见核的谱密度。

• RBF / 高斯 $k(\delta) = \exp(-\gamma \|\delta\|^2):$ 谱密度是高斯，$p(\omega) = (4\pi\gamma)^{-d/2} \exp(-\|\omega\|^2 / (4\gamma)).$ 抽样直接 np.random.normal，最容易实现。
• Laplacian $k(\delta) = \exp(-\|\delta\|_1 / \ell):$ 谱密度是 Cauchy-类。Cauchy 抽样要用逆变换法或拒绝采样，比高斯麻烦但不难。
• Matern-$\nu$ ： 谱密度是带 $\nu$ 自由度的 Student-$t$ 类。$\nu = 1/2$ 退化成 Laplacian，$\nu \to \infty$ 退化成 RBF；中间值（如 $\nu = 5/2$ ）是几何统计里最常用的，因为既有可控的光滑性又有有限阶导数。
• Cauchy 核 $k(\delta) = \prod_i (1 + \delta_i^2)^{-1}:$ 谱密度是 Laplace。

注意这个 trade-off：高度局部化的核（$\gamma$ 大、$k$ 窄）有宽的谱密度（高频成分多）。光滑、长距离相似的核有集中的谱密度（低频成分多）。这就是标准的傅里叶不确定性：空间窄 $\Leftrightarrow$ 频率宽。后果是：固定 $D$ 的 RFF 预算下，光滑核被近似得比尖锐核好，因为大部分 Monte Carlo 样本都落在能量集中的低频带；想用 RFF 近似 $\gamma = 10$ 的 RBF，$D$ 至少要比 $\gamma = 0.1$ 的情况大一个数量级。

这个不等式给出的实操建议。 如果你被迫用极尖锐的核（数据有非常局部的结构，比如自然语言里的字符级匹配），不要硬上 RFF——它的 Monte Carlo 误差会被高频尾巴拖垮。换 Nystrom（数据相关，能跟着尖锐区域走）或者换一组结构化随机特征（Orthogonal RFF 能把同 $D$ 下的方差再压一半）。反过来，光滑核（$\gamma$ 接近中位数启发）配 RFF 是真正的甜蜜区，$D = 1000$ 通常就足够把测试精度打到精确解的 0.3% 以内。

那么 $\hat\phi(x)^T \hat\phi(y) \to k(x - y)$ 当 $D \to \infty,$ 在每个点上方差是 $O(1/D).$ 这个方差是均匀的，跟 $x, y$ 离不离原点无关——这跟 Nystrom 形成对比，后者在 landmark 附近精度高、远处精度低。

一个让人豁然开朗的类比。 想象你想算 $\int f(\omega) d\omega$ ，最朴素的办法是蒙特卡洛——从 $p(\omega)$ 抽样、平均。Bochner 告诉你核就是一个积分，所以核估计也能蒙特卡洛。RFF 的全部新颖性就在”$f(\omega) = \cos(\omega^T (x - y))$ “这个特殊的被积函数上——它让单次抽样就给出 $\phi(x)^T \phi(y)$ 形式的"二次型分解”。其余都是标准的蒙特卡洛理论：$D$ 个样本，方差 $\sigma^2 / D$ 。RFF 不神秘，只是把数值积分套在了正确的对象上。

sklearn.kernel_approximation.RBFSampler 实现的就是这个。为什么 work？因为 $\mathbb{E}_b[\cos(\omega^T x + b)\cos(\omega^T y + b)] = \tfrac{1}{2}\cos(\omega^T (x - y))$ （对均匀相位求期望把交叉项杀掉），重新得到 Bochner（差一个常数）。代价是同样的 $D$ 维度下方差略大（约 1.5 倍），换来内存折半和实现简单。Rahimi 自己后来的代码也用这版。

RFF 算法 step-by-step#

对 RBF 核 $k(\delta) = \exp(-\gamma \|\delta\|^2),$ 谱密度是 $p(\omega) = \mathcal{N}(0, 2\gamma I_d).$ 完整算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import numpy as np

def rbf_rff_features(X, gamma, D, rng=None):
    """RFF for RBF kernel K(x, y) = exp(-gamma * ||x - y||^2)."""
    rng = np.random.default_rng(rng)
    n, d = X.shape
    # 第 1 步：从 N(0, 2*gamma * I) 抽 D 个频率
    W = rng.normal(scale=np.sqrt(2 * gamma), size=(d, D))
    # 第 2 步：从 Uniform[0, 2*pi] 抽 D 个相位
    b = rng.uniform(0, 2 * np.pi, size=D)
    # 第 3 步：算特征
    Phi = np.sqrt(2.0 / D) * np.cos(X @ W + b)
    return Phi, (W, b)  # 返回 W, b，测试集变换要用同一组

# 训练
Phi_train, params = rbf_rff_features(X_train, gamma=0.5, D=1024, rng=0)
# 用*同一组* W, b 变换测试集
W, b = params
Phi_test = np.sqrt(2.0 / 1024) * np.cos(X_test @ W + b)

三件事要刻在脑子里：

1. 频率 $W$ 在训练时采样一次，存起来。 转换测试数据时必须用同一组频率；否则内积不近似核。生产里这就意味着你需要把 $(W, b)$ 一起 pickle 进模型工件，而不是只存下游线性分类器的权重。
2. 每个点的开销：$O(D \cdot d).$ 跟一次线性模型评估一样。任何地方都没有 $n$ 的平方依赖。$n = 10^6, d = 784, D = 1024,$ 训练一次特征矩阵约 $8 \times 10^{11}$ FLOP，单卡几十秒。
3. 为什么是 $\sqrt{2/D}.$ 这是让 $\hat\phi^T \hat\phi$ 成为 $k$ 的无偏估计的归一化常数。少了这个你拿到的曲线形状对，但尺度错了，下游正则系数 $C$ 全要重新搜一遍。

第三件不那么显眼的事：数据要 standardize。 RFF 假设你的 $\gamma$ 选取和数据的典型距离尺度匹配。如果某一维特征的尺度比其他维大十倍，$\omega^T x$ 项被那一维支配，$\cos$ 在该维变化几个像素就绕完一周，整个核近似退化成噪声。StandardScaler 一行的事，但是几乎所有 RFF 初学者的第一次失败都源于忘了它。同理，类别变量必须 one-hot 编码到合理尺度，不能直接当 1, 2, 3 输入。

RFF + 神经网络的混合 trick。 在深度学习时代 RFF 还有一种用法：把它作为神经网络的第一层（学习 Fourier 特征），下游接全连接 / 卷积。NeRF（Mildenhall et al. 2020）就是用这招把 3D 坐标抬到高频空间，让网络学会高频细节而非全局光滑。这是"随机特征 → 学得的特征"的过渡形态，证明 Bochner 这套 1933 年的数学在 2020 年的神经渲染里仍然是核心引擎。和这条路平行的还有 Tancik et al. 2020 “Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains”——明确指出固定 $\gamma$ 的 RFF 嵌入是 NeRF 等坐标 MLP 成功的关键，去掉就退回到糊状结果。这条经验后来被无数 implicit neural representation 工作引用。

其中 $\sigma_p^2 = \mathbb{E}_{\omega \sim p}[\|\omega\|^2].$ 眯眼看一下：均匀误差大约 $1/\sqrt{D}$ ，对 $r$ 和 $d$ 是对数依赖。$D$ 翻倍，标准差减半。把数字带进去：想要 $\epsilon = 0.01$ 的均匀误差，$d = 100$ 的中等维度数据需要 $D \approx 10^5,$ 比"舒服"的 $D = 10^3$ 大整整两个数量级——这是 RFF 的一个常见盲区，论文里报的精度数字往往是在 $\epsilon \approx 0.1$ 的宽松约束下拿到的。

这个界是悲观的。 它给的是 $\sup_{x,y}$ ——最坏点对的误差。下游分类器只关心决策边界附近的几个关键点，那里实际误差通常比 sup 界小一个数量级。所以"理论上 $D$ 要 $10^5$ “和"实践中 $D = 10^3$ 就够"并不矛盾：前者保证最坏情况，后者只需平均情况。这条经验在 Sutherland & Schneider (2015) 里有更紧的"任务相关"误差界，结论是：分类任务 $D \sim O(\sqrt{n})$ 通常够，回归任务 $D \sim O(n^{1/3})$ 通常够，生成式任务才需要 sup 界那种 $O(n)$ 。

方差与偏差的分解。 RFF 是无偏的，所以所有近似误差都是方差；而 Nystrom 是有偏的（偏差由谱尾决定），方差由 landmark 选取的随机性决定。这给出一条经验：当你的核谱衰减极快（光滑数据上的 RBF），Nystrom 的偏差几乎可以忽略，它就是无偏估计的事实标准；当谱衰减慢（高频信号、Matern-1/2、Laplacian），RFF 的无偏性反而成了麻烦——它把那些尾部能量也试图近似，但 $D$ 不够时方差爆炸。所以"谱集中→Nystrom，谱分散→RFF"是一个粗略但有用的启发。

什么时候 RFF 失败得很惨。 三类情况要警惕。(1) 核非常尖锐（$\gamma$ 很大）：谱密度方差大，Monte Carlo 几乎不收敛，$D = 10^4$ 都可能近似得一塌糊涂。(2) $d$ 极高且数据不在低维流形上（很罕见，但确实出现在某些科学场景）：误差界里的对数因子开始咬人，$D$ 需求飙升。(3) 核不是平移不变的：Bochner 直接不适用，RFF 没办法套——这时只能 Nystrom，或者构造核特异的随机特征（如 polynomial 核的 TensorSketch）。

一个常被忽视的隐性偏差： RFF 是无偏的核估计，但它给出的不是无偏的函数估计。把 RFF 特征送进岭回归后，估出的函数 $\hat f$ 和精确核岭回归的 $f^*$ 之间存在依赖 $D$ 的偏差，这个偏差衰减比核近似的 $1/\sqrt{D}$ 慢——通常是 $1/D^{1/4}$ 量级。后果就是：核估得很准不代表下游模型估得很准；你想要"端到端无偏”，需要更激进地把 $D$ 推高。这个差距在最近的 RFF 理论里（Liu, Huang, et al. 2022 综述）被反复讨论。

RFF 实战：50k 样本的对比示例#

让我具体一点。MNIST 风格的题：50,000 张训练图、每张 784 像素（28 × 28）、二分类（数字 3 对数字 8）。三条流水线对比：

1. 精确 RBF SVM。 SVC(kernel='rbf', gamma=0.05)。精度的金标准；运行时间的灾难。
2. Nystrom + 逻辑回归。 Nystroem(n_components=500) + LogisticRegression。数据相关的低秩。
3. RFF + 逻辑回归。 RBFSampler(n_components=1000) + LogisticRegression。数据无关的随机特征。

这个题为什么选 3 vs 8。 MNIST 是十类分类问题，但精确 RBF SVM 默认走 OvO，要训 $\binom{10}{2} = 45$ 个二分类器；50k 数据上这就是个无法忍受的实验，做对比阐释问题不友好。挑 3 vs 8 是因为这是 MNIST 里最容易混淆的两个数字（笔画结构相近，决策边界非线性极强），所以核方法相对线性的优势最明显——线性 SVM 大约 96%，RBF 上到 99.2%，3.2% 的 gap 全是非线性带来的。

gamma=0.05 是怎么来的。 中位数启发对 MNIST 像素值的 $L^2$ 距离算出来 $\sigma \approx 3.2$ ，对应 $\gamma = 1 / (2 \sigma^2) \approx 0.05$ 。这是个能用、但不一定最优的起点；真做生产你会在 $\gamma \in [0.01, 0.2]$ 之间做对数网格搜，最优常落在 0.04-0.08 之间。值得提的是：三条流水线必须用同一个 $\gamma$ 才公平；不少 benchmark 报告里精确 SVM 用调优后的 $\gamma$ ，近似版用默认 $\gamma$ ，结论自然偏向精确，这是常见的"无意但糟糕"的实验设计。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

import time
import numpy as np
from sklearn.svm import SVC
from sklearn.kernel_approximation import Nystroem, RBFSampler
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import make_pipeline

GAMMA = 0.05

def time_and_score(pipe, X_tr, y_tr, X_te, y_te):
    t0 = time.time()
    pipe.fit(X_tr, y_tr)
    fit_t = time.time() - t0
    acc = pipe.score(X_te, y_te)
    return fit_t, acc

# 1) 精确 RBF SVM
svm = SVC(kernel='rbf', gamma=GAMMA, C=1.0)
# 2) Nystrom + 逻辑回归
nys = make_pipeline(
    Nystroem(kernel='rbf', gamma=GAMMA, n_components=500, random_state=0),
    LogisticRegression(max_iter=2000, C=1.0, solver='lbfgs'),
)
# 3) RFF + 逻辑回归
rff = make_pipeline(
    RBFSampler(gamma=GAMMA, n_components=1000, random_state=0),
    LogisticRegression(max_iter=2000, C=1.0, solver='lbfgs'),
)

2026 年代笔记本（8 核，32 GB RAM）上的参考墙钟时间：

你拿不到的精度可能就那么半个百分点，但训练快了大约 100 倍。在 50 万点上，精确 SVM 在普通硬件上根本跑不动，而两种近似都还停在分钟级别。这就是 2010 年代初整个领域集体决定接受的 trade-off；核方法没死，靠的是这个。把视角再拉远，$n = 10^7$ 时精确 SVM 的训练时间外推大约是 470 天（单机），而 RFF + SGD 配 $D = 2000$ 在同样硬件上是几个小时——这不是加速，这是从"不可能"到"工程问题"的相变。

为什么差距没有变成"近似比精确还好”？ 一个反直觉的事实：在中等噪声（label noise > 5%）的真实数据上，精确 SVM 和近似版本的泛化精度差距经常缩到统计意义不显著的程度，因为泛化误差被噪声主导，而非近似误差。换句话说：你担心 RFF 把核近似坏，但你的数据本身比近似引入的偏差脏得多。这条经验也解释了为什么深度学习配粗糙的近似（dropout、量化）还能横扫各种 benchmark——只要近似误差小于数据噪声，精度就不掉。

一个更激进的观察。 Belkin et al. 2018 注意到一个反例：当 $D$ 大于 $n$ 时（“过参数化的 RFF”），模型常常比经典核方法还要好——这是双下降现象在核方法里的一个早期端倪。背后的直觉是：在过参数化区间，模型有足够自由度同时拟合数据并保持平滑解，等价于一个隐式的零成本正则。这条线后来被 NTK 理论吸收，成为理解深度学习泛化的核心拼图之一。所以”$D$ 越大越好"不只是工程经验，也有理论支撑——前提是下游正则配得当。

几个 sklearn 实战注意。

• RBFSampler 用的是带相位 cos 形式。 所以输出是 $D$ 维而非 $2D$ 维。你想要显式 sin/cos 对的版本，自己写一遍（10 行就够）。两种形式精度可比，但显式 sin/cos 在小 $D$ （$\leq 200$ ）时方差略低。
• SkewedChi2Sampler 和 AdditiveChi2Sampler 在 sklearn.kernel_approximation 里是给计算机视觉里直方图比较核（非平移不变）用的 RFF 类映射。冷门，但确实存在；它们用的不是 Bochner 而是一组针对具体核手工推出来的展开。
• 配 SGDClassifier 做流式训练。 RFF 特征是固定维度的嵌入，直接塞进 SGD。RFF + SGD 能扩到 $n = 10^8.$
• 特征映射之后做归一化。 Nystrom 和 RFF 都可能产出动态范围很大的特征；下游配一个 StandardScaler，或者 LogisticRegression(... solver='lbfgs') 配合合适的 C。
• 预算配比经验。 一个万能起点：$D = 4 \sqrt{n}.$ $n = 10^4$ 配 $D = 400,$ $n = 10^6$ 配 $D = 4000.$ 不是理论最优，但实践里很难错得离谱。
• 种子敏感性自检。 跑两个不同 random_state 的同样配置，看测试精度是否波动超过 0.5%；超了说明 $D$ 不够大，需要翻倍。这是几乎不需要写代码的最便宜的近似质量诊断。
• 不要复用 $W$ 跨核。 一组 $W$ 是为特定 $\gamma$ 服务的；想换 $\gamma$ 就重抽。这条规则在做 grid search $\gamma$ 时尤其重要——很多人会无意识地用同一个 random_state 覆盖所有 $\gamma$ ，得到的不是公平比较。
• GPU 上 RFF 比 sklearn 实现快得多。 PyTorch / JAX 两三行就能写一个 GPU 版 RFF：torch.cos(X @ W + b)，A100 上单层 $D = 4096$ 处理 $10^7$ 点约 100 毫秒；sklearn 的 CPU 实现同等数据要分钟级。所以如果你已经在 GPU 上做下游，不要把数据搬到 CPU 跑 RFF 再搬回来——重写那十行代码。

Nystrom vs RFF：什么时候选哪个#

现在你手上有两件工具，都能把 $O(n^3)$ 的核方法压成 $O(n)$ 的线性方法。该选哪个？老实说就一句"两个都试"，但下面是先验。

用 Nystrom 当：

• 你的核不是平移不变。RFF 需要 Bochner 定理，需要 $k(x, y) = k(x - y).$ 多项式核、字符串核、大部分图核都不是平移不变；Nystrom 对任何 PD 核都 work。
• 数据有清晰的聚类结构，K-means landmark 讲得通。Nystrom 是数据相关的，能利用这一点；RFF 不能。
• 你想要确定性的近似。固定 landmark 集，Nystrom 映射是确定的；固定 $W, b,$ RFF 也是确定的，但"好随机种子"效应在小 $D$ 时对 RFF 影响明显大得多。
• 你需要在中等 $m \approx 100$ -$500$ 下拿到很高精度。经验上 Nystrom 在这个区间压制 RFF，因为谱截断误差界比蒙特卡洛误差界更紧——前者是 $O(\lambda_{m+1})$ 谱依赖的速率，后者是 $O(1/\sqrt{m})$ 的统计速率。
• 你能花一次性的开销换长期收益。Nystrom 的 landmark 一旦选定就反复使用；如果你的核超参不变、数据不变，那个 $\Phi_n$ 可以缓存，比 RFF 每次都要重算 $\cos(XW + b)$ 更优。
• 你做多任务学习共享底层核。同一组 landmark 给多个下游任务用，每个任务只学 $m$ 维线性头，下游可以是分类、回归、排序——共享 $\Phi_n$ 是非常自然的多任务底座。

用 RFF 当：

• 核是平移不变的（RBF、Laplacian、Matern、Cauchy）。这种场景下 RFF 是教科书选择。
• 你想做流式训练。RFF 的特征只取决于一次性抽的 $W, b,$ 你可以让 $X$ 流过它们，送进 SGD 分类器。Nystrom 需要预先有 landmark 集。
• 你想要超参最少。RFF 实质就一个旋钮 $D;$ Nystrom 有两个（$m$ 和 landmark 策略）。
• 你在 GPU 上想要易于批处理。RFF 是一次矩阵乘加一次 cos；trivially 批处理、能 JIT。Nystrom 的特征映射涉及一次 $K_{mm}^{-1/2}$ ，做完一次后倒也能做矩阵乘，但前置开销让它在频繁重训时不如 RFF。
• 你需要可解释的方差边界。RFF 的 $1/\sqrt{D}$ 收敛是分布无关的，你给一个 $D$ 就能写出 ε-confidence；Nystrom 的误差依赖谱衰减，事前很难给出非平凡的界。
• 你打算在多设备上分布式训练。RFF 的 $W$ 一次广播到所有 worker，剩下全是 embarrassingly parallel；Nystrom 要么所有 worker 用同一组 landmark（瓶颈在主节点），要么每个 worker 自己采 landmark 再合并（统计上更复杂）。

和层次方法的对比。 H-matrix / HODLR 这一族做法把 $K$ 看成一棵层次树，远场块用低秩近似，近场块保持稠密，给出 $O(n \log n)$ 的矩阵-向量乘。理论上比 Nystrom 和 RFF 更紧——它能逼近的不只是低秩而是层次低秩——但工程实现复杂（KeOps、HODLRlib 是几千行 C++），且对核必须光滑、低维。我的经验是：低维（$d \leq 5$ ）几何数据（地球物理、流体仿真）上 H-matrix 是赢家；中高维数据（图像、文本嵌入）Nystrom 和 RFF 简单到无脑用就行。

三者复杂度速查：

读法：Nystrom 用偏差换内存，RFF 用方差换简洁，H-matrix 用工程复杂度换理论紧度。三者没有 dominating 关系，选哪个取决于你最不能放弃哪个维度。

一条元规则。 2026 年监督学习配平移不变核，RFF + SGD 是阻力最小的路径。非平移不变核或者你打算反复重调核超参（你想让 landmark 结构携带信息），Nystrom + L-BFGS 是对的。贝叶斯 / 概率模型上这两个都不太对——见下一节。

一个常被问的问题：能不能同时用 Nystrom 和 RFF？ 能，叫 双重随机特征（doubly stochastic）。思路是先用 Nystrom 把 $K$ 压成 $\hat K = K_{nm} K_{mm}^{-1} K_{mn}$ ，然后对 $K_{mm}^{-1}$ 也用一组 RFF 近似——本质是嵌套两层近似。理论上更紧（两层误差可控），实践中调参噩梦（两个 $m, D$ 同时调）。我没见过谁在生产里用，更多是论文示意；除非你在做 sketching 理论研究，否则跳过。

大规模 GP：稀疏近似一瞥#

Nystrom 和 RFF 最初是给频率派核方法设计的——SVM、核岭回归、核 PCA。GP 回归同样掉进相同的扩展性悬崖：GP 推断要做 $K + \sigma^2 I$ 的 Cholesky，$O(n^3).$ 围绕把 GP 扩展到大 $n,$ 长出了一整个子领域，主流家族是稀疏 / 诱导点 GP。鸟瞰：

FITC（Fully Independent Training Conditional，Snelson 和 Ghahramani 2005）。 最早。定义 $m$ 个诱导输入 $Z \in \mathbb{R}^{m \times d},$ 把训练集先验 $K_{nn}$ 换成 Nystrom 近似 $K_{nm} K_{mm}^{-1} K_{mn}$ ——和经典 Nystrom 一样的矩阵——再加一个对角修正修正边际方差。推断变成 $O(nm^2),$ 复杂度和 Nystrom + 线性一样。容易在没见过的区域低估不确定性——这个失败模式很危险，因为 GP 卖的就是不确定性。

为什么 FITC 会低估外推不确定性。 Nystrom 近似在远离 landmark 的地方把 $K$ 压向零，FITC 直接把这个事实信成"真实先验方差"，于是远处的方差比真 GP 算出来的小。在主动学习 / 贝叶斯优化里这是致命的：算法会因为"这里方差小所以不需要采样"而错过整片未探索区域。VFE 和 SVGP 因为额外有变分校正项，这个问题缓解很多，但完全消除要等到 deep kernel 或 Bayesian neural network 给出真正的"外推时膨胀"的不确定性建模。

其中 $Q_{nn} = K_{nm} K_{mm}^{-1} K_{mn}.$ 第一项是低秩 GP 的常规边际似然；第二项是正则项，把诱导输入往 Nystrom 近似精确的位置拽。VFE 是 gpytorch 和 GPflow 现在的默认。

FITC vs VFE 的一句话区别。 FITC 是"先近似先验再做精确推断"，VFE 是"对精确模型做变分推断"。两者的预测均值往往相似，但 VFE 的预测方差校准得多——后者直接由"$\mathrm{tr}(K_{nn} - Q_{nn})$ 该惩罚多少"这一项控制，前者只能靠对角修正补救。如果你只看 MSE，FITC 和 VFE 差不多；如果你看负对数似然或者 calibration curve，VFE 几乎总是赢。我的默认是任何新项目都从 VFE 起步，除非有具体理由切别的。

一个更深的对比：FITC 是退化的 VFE。 Bauer, van der Wilk, Rasmussen 2016 证明，当你把 VFE 的迹惩罚项乘以 0，恰好还原 FITC 的目标函数。所以 FITC = VFE - 校准项。这把"FITC 为何不可靠"的非正式经验变成了精确陈述：它丢了校准。理论上，VFE 几乎没有理由比 FITC 差，所以 FITC 在 2020 年后基本被弃用，gpytorch 默认 VFE / SVGP 一族。

其中 $q(u) = \mathcal{N}(u; \mu, \Sigma)$ 是诱导值上的多元高斯变分分布，$q(f_i) = \int p(f_i | u) q(u)\, du$ 是隐含的第 $i$ 个函数值边际。第一项的和按数据点分解，允许 minibatch；KL 项是两个 $m$ 维高斯之间的 KL，每次梯度步算一次。

SVGP 给出了什么 FITC/VFE 给不出的东西？ 三件事。(a) 真正的 mini-batch 训练，让 $n$ 突破 $10^6$ ；FITC/VFE 必须一次看全数据。(b) 变分参数 $\mu, \Sigma$ 可学，让诱导值的后验形状不再被 Nystrom 形式强行限定；这在似然非高斯时尤其重要（比如 GP 分类）。(c) 任意似然：泊松、Bernoulli、Student-t 都能套进去，只要把 $\mathbb{E}_{q(f_i)}[\log p(y_i | f_i)]$ 算得出来（必要时用一维高斯求积）。FITC 几乎只能做高斯回归。这三件事加起来让 SVGP 成了 gpytorch / GPflow / Pyro 里"大规模 GP"的事实标准接口。

实践上的分界大致是：

• $n \leq 10^4$ ： 精确 GP。用 gpytorch.models.ExactGP。不需要近似。
• $10^4 \leq n \leq 10^5$ ： FITC 或 VFE，$m = 100$ -$500$ 诱导点。两者都是"单批"的——每步梯度用全部数据。
• $10^5 \leq n \leq 10^7$ ： SVGP，$m = 500$ -$2000$ 诱导点，mini-batch 约 1024 点。2026 年大规模 GP 的主力。
• $n > 10^7$ ： 抉择时刻。要么进一步近似（KISS-GP、结构化核插值），要么彻底切到深度学习（Part 8 会聊）。

一个 SVGP 的常见陷阱：诱导点初始化。 把 $Z$ 初始化成 K-means 中心几乎总比随机抽样好；初始化成均匀网格在低维（$d \leq 3$ ）也 work，但 $d \geq 5$ 网格点数指数爆炸，没法用。VAE 风格的"用 encoder 网络生成诱导点"在最近几年被提出（latent SVGP），效果不错但额外引入一组神经网络参数，超出了"经典 GP"的范畴。

SVGP 调参快速清单。 三件事按重要性排序：(1) 诱导点数量 $m$ ：从 $m = 500$ 起步，看 ELBO 是否还在涨，没涨就够了；涨着就翻倍。(2) 学习率：诱导值变分参数 $(\mu, \Sigma)$ 学习率通常要比核超参的学习率大 5-10 倍——前者是无约束的高维参数空间，后者只是几个标量。直接给两组优化器，gpytorch 支持。(3) mini-batch 大小：太小（< 256）梯度噪声大、ELBO 抖动剧烈；太大（> 8192）每步开销重、收敛慢。1024 是个安全的默认。这三个调好后 SVGP 在大多数任务上离 SOTA 就一两个百分点。

和频率派近似的关系。 FITC 的预测均值公式等价于 Nystrom + 岭回归（取一致的正则参数），只是 GP 多了一层概率封装；SVGP 的均值公式则等价于 RFF + 岭回归在 $D \to \infty$ 的极限。这不是巧合：所有可扩展核方法的核心数学骨架都是一样的，只是统计学派把它包成贝叶斯、机器学习派包成 ERM。理解了这一点，你在不同库（gpytorch、sklearn、JAX）之间迁移时就不会觉得在学新概念。

老实说，精确 GP 比 精确 SVM 还要受限——它必须做完整 Gram-加-噪声矩阵的 Cholesky，没法像 SVM 那样接受同样的偷懒技巧。所以稀疏 GP 是比"Nystrom-for-SVM"更关键的研究领域。2026 年如果你在真实数据上用 GP，你用的不管知不知道都是 SVGP。一个有时被忽视的点：诱导点 $Z$ 是可学习的连续参数，反向传播会把它们推到对似然贡献最大的位置——这就让 SVGP 在统计上严格优于"先随机选 landmark，再求逆"的固定 Nystrom，代价是优化更难（landmark 优化是非凸的）。

统一图景#

回头看看我们走到了哪里。Nystrom 和 RFF 都把核方法压成 $D \ll n$ 的 $\mathbb{R}^D$ 特征映射上的线性方法。两者误差率类似：RFF 是 $1/\sqrt{D}$ （蒙特卡洛），Nystrom 是 $K$ 的谱尾（数据相关）。两者现在在 scikit-learn 里都是三十行的实现。整个 2007 到 2015 年"可扩展核方法"的研究前沿，本质上都是这两个想法的变种：

• Fastfood（Le、Sarlos、Smola 2013）。 RFF，但随机矩阵 $W$ 替换成结构化的 Hadamard-高斯-对角乘积，乘法变成 $O(D \log d)$ 而非 $O(Dd).$ $d$ 巨大时有用，常数因子也明显小。
• Quasi-Random Fourier Features。 把 iid $\omega \sim p$ 换成低差异（Sobol、Halton）序列。误差在有利区间里以 $1/D$ 而非 $1/\sqrt{D}$ 衰减。
• Orthogonal Random Features（Yu et al. 2016）。 强制 $W$ 的行正交。严格优于原版 RFF，无额外成本——这是少见的"免费午餐"。
• 结构化 Spinner 和 Hadamard 技巧。 各种让 $W$ 拥有低存储 / 快乘法结构的办法。
• Nystrom + leverage scores（Alaoui 和 Mahoney 2014）。 按岭 leverage score 概率抽 landmark；匹配任何基于采样的近似的下界。
• Doubly stochastic kernel methods（Dai et al. 2014）。 同时在数据和特征上做随机化，把 RFF 推到 $n = 10^9$ 量级。这条线的核心 trick 是把 RFF 的 $W$ 也按 mini-batch 抽——每次只看一小部分频率，配合下游 SGD，让单步开销从 $O(D d)$ 降到 $O(b d)$ （$b \ll D$ 是频率 batch）。理论上仍然收敛到精确核解，工程上可扩到 $10^9$ 数据点 + $10^5$ 频率。这是 RFF 这条路能走到的极限工程化。
• EigenPro（Ma & Belkin 2017）。 用预条件 SGD 直接求解核岭回归，绕过显式低秩近似，在 GPU 上能跑到 $n \approx 10^7$ 。它和 Nystrom 不互斥：先 Nystrom 算预条件子再 SGD 求解，是当前最快的 KRR 配方之一。这条思路有时被称为"GPU-native kernel methods"，强调把所有运算限制在矩阵乘和元素 wise 操作上，最大化 GPU 利用率。
• Falkon（Rudi, Carratino, Rosasco 2017）。 Nystrom 配共轭梯度配预条件子的工程化集大成，目前是大规模 KRR 的 SOTA 库。它的关键技术是 $K_{mm}^{-1/2}$ 当预条件子做 CG——避免显式求逆同时保证收敛快，单机 GPU 上能跑到 $n = 10^7, m = 5 \times 10^4$ 的核岭回归在几小时内完成。这是 Nystrom 这条路能走到的极限工程化。如果你的项目本质上就是个核岭回归，直接用 Falkon 库，比自己拼 sklearn 强出几个量级。

2026 年从业者共识栈：RFF 当核平移不变且想要简单时，Nystrom 当非平移不变或想手调 landmark，SVGP 当模型是概率的，深度学习当数据形态太复杂以至于没有固定核能抓住。 系列第 8 篇 就是最后这个点——为什么深度学习吃了核方法的午饭，以及在哪些地方核视角又回头反噬现代深度网络（想想：NTK）。

最后一个观察：随机特征的回归。 2020 年后随机特征思想在 Transformer 里复活了——Performers（Choromanski et al. 2021）用 FAVOR+ 把 softmax 注意力的 $O(n^2)$ 压成 $O(n)$ ，核心就是把 $\exp(q^T k / \sqrt d)$ 写成 RFF 形式。这是核方法理论回头喂养深度学习的一个干净例子：Bochner 1933 → Rahimi-Recht 2007 → Performers 2021，一脉相承。下一篇会更系统地谈这条线。

类似的复活清单。 Linformer、Linear Attention、Reformer、Nyströmformer——名字里直接带 Nyström——这一组工作都是 2020-2022 年间用核近似把 attention 从平方降到线性。每一个都本质上是把 attention 矩阵当成一个 PD 核矩阵来近似。这意味着 Transformer 的"长上下文革命"本质上是核方法可扩展性研究的应用——一个 2007 年的统计学工具，十几年后变成大模型架构的核心。这条传承链如果你只看深度学习论文是不会感觉到的，但如果你从核方法的视角往后看，整个故事就连贯了。

收尾的一条心智模型。 把整个核方法系列压缩成一句话：核技巧让你用一个内积（$K(x, y)$ ）在无穷维空间里做线性方法；但天下没有免费的内积，账单是 $O(n^2)$ 的 Gram 矩阵。Nystrom 用"看一部分"省钱（数据相关），RFF 用"抽样"省钱（数据无关），SVGP 用"变分分解"省钱（概率视角）。三种省钱方式背后是同一个事实：核方法在大数据时代必须近似，且近似的代价远小于精度损失。理解了这一点，你就理解了"为什么 2007 年到 2015 年那么多论文都是 Nystrom 和 RFF 的变种"——它们都在回答同一个问题，只是从不同方向回答。

给从业者的两条简短建议。 第一，先选对家族再调参：核非平移不变→Nystrom，平移不变 + 流式→RFF，需要不确定性→SVGP。任何把这三件事搞错的工程都救不回来，无论后面 grid search 多狠。第二，总是和线性基线比：在 $n > 10^5$ 的数据上，一个调好的 logistic regression 加一组手工特征往往离 RFF + logistic 只差一两个百分点，而前者训练快十倍、解释性强十倍。核方法值得用，但不要因为"它高级"就用——只在线性模型实在做不到时用。这条规则适用 2007 年，也适用 2026 年。

第三条加在这里：先用上述近似版做原型，再决定要不要花钱跑精确。 工业项目里有个常见反模式是"先花一周训精确 SVM 看是不是有救，发现没救再扔掉"。正确顺序反过来：先 30 秒跑 RFF + LR 看精度天花板大致在哪，再决定是不是值得花一周。近似版几乎不会比精确版差超过 1-2 个百分点，所以它是个非常便宜的可行性探针。这条流程能省下大量的"理论上能 work 但实际上 ROI 太低"的项目时间。

两条容易被遗忘的工程实践。 第一，近似版的超参不能直接搬精确版的。精确 RBF SVM 调好的 $C, \gamma$ 给到 Nystrom + LR 上往往不是最优——下游线性头的容量和正则尺度都变了，必须重新 grid search。第二，近似带来的方差要进 CV 报告：固定 $m$ 跑 5 个不同 random_state 报均值±标准差，而不是只跑一个。在小 $m$ 区间这个标准差经常是 0.5%-1.5%，比你下游算法版本之间的差距还大；不报方差，你的 ablation 全是噪声。

第三条常忘的实践：留一组 holdout 给"近似 vs 精确"对比，不要全用 CV。 标准做法是用 train/val 调超参、test 看泛化；引入近似后还需要一个"sanity"holdout——在小子集（$n_{\text{sanity}} = 5000$ ）上跑精确核作为 oracle，比较近似版的预测和它有多接近。如果近似版在 sanity 上偏差超过 1%，说明 $m / D$ 不够，不要直接上大规模。这条流程在做新数据集时能省下大量"上线后发现模型废了"的事故。

最后一个工程细节：增量学习。 Nystrom 严格说不支持在线学习——新数据来了，landmark 还是旧的，特征映射 $\Phi_n$ 部分能复用但下游模型要重训。RFF 支持，因为 $W, b$ 一次抽完后就不动，新数据流过 $\cos(X W + b)$ 即可。所以"模型每天滚动更新"的场景，RFF 是几乎唯一选择；想要 Nystrom 在这种场景下也好用，要走 streaming Nystrom 这条更新的、还在迭代的研究方向。

写在跳到第 8 篇之前。 这一篇的核心是 scale：当 $n$ 大到核方法的精确解算不动时，怎么办。下一篇换一个轴：当 函数空间 本身复杂到没有任何固定核能描述时，怎么办。前者答案是"近似核"，后者答案是"学习核"——也就是深度核学习、神经网络与核的双向桥接。两个问题看似无关，其实是一个连续谱的两端：固定核 + 大数据（本篇）vs 学得的核 + 大模型（下篇）。中间所有的混合形态——固定底层核 + 学得的上层组合、固定上层 head + 学得的底层嵌入——都是这个谱上的中间点。

两个问题之间的桥。 一个有趣的桥梁：Nystrom 的诱导点 $Z$ 可以变成可学习参数（这就是 SVGP 在做的），那么再进一步——能不能让"诱导特征映射"也变成可学习的神经网络？答案是肯定的，那就是 deep kernel learning（Wilson et al. 2016）：神经网络当作 $\phi(x)$ ，外面套一个 RBF 核，再用 SVGP 做推断。这条路把"近似核"和"学习核"接上了，是下一篇的核心母题之一。所以本篇结束的地方正是下一篇开始的地方——可扩展性的最后一公里通向学习性的第一公里。

这条桥也解释了为什么 NTK / NNGP 这套"无穷宽神经网络等价于 GP"的理论在 2018 年突然爆发：当宽度趋无穷时，神经网络的输出协方差收敛到一个解析可写的核——这个核就是 NTK。深度学习被翻译成核方法之后，所有 30 年的核理论工具（表示定理、收敛分析、谱分解）都重新可用。下一篇会拆开这个桥的每一根钢梁。

对核方法这个学科的整体看法。 Nystrom 和 RFF 标志着一个时代的结束：1995-2010 是"精确核+小数据"的黄金期，2010 之后核方法没有消失，但它退化成了一种"风格"——它的思想（特征空间、表示定理、谱视角）渗透进神经网络（NTK、attention 作为核）、生成模型（MMD、kernel score）、强化学习（kernel Bellman 算子）和因果推断（kernel conditional independence）。下一篇会专门聊这条路——但要点先抛在这里：核方法没有输给深度学习，它变成了深度学习的一部分。

一个偏私人的小结。 我在这一系列写到第七篇时，发现自己对"近似"这个词的态度变了。十年前我觉得近似是退而求其次，是不得已；现在我觉得近似才是正路，精确反而是个奢侈品——只有当数据小到精确还划算时，精确才该是默认。Nystrom 和 RFF 教会的是：与其追问"我能不能精确地解这个问题"，不如问"我能不能在我关心的精度下廉价地解这个问题"。这个问句的转换是机器学习从学术到工程的一次根本成熟。

一个常被引用的反思。 Rahimi 自己在 2017 年 NeurIPS 拿 test-of-time 奖时讲过一段话：他担心"alchemy"——很多深度学习的工程进展跑得太快，理论解释跟不上。RFF 是一个反例：它在 2007 年提出时数学就完全清楚（Bochner 1933 + Monte Carlo），所以才能十年不衰、被无数后续工作引用。这条路的教训是：你能把一个想法的数学骨架讲到三页纸，它就有十年的生命；你只能说"实验上 work"，它就只有两年。本系列从头到尾偏数学叙事而非工程叙事，部分原因就在这里——核方法的价值就在它的数学骨架，把骨架理解清楚，剩下的工程都是水到渠成。

接下来#

第 8 篇 （系列终章）讨论深度核学习 vs 深度学习：为什么 2012 年起神经网络在经验上赢了，深度学习的核视角（NTK、NNGP、无限宽度下等价于 GP）揭示了网络真正在做什么，以及把核重新塞进神经流水线的混合方法（深度核、高斯过程层、kernel 化注意力）。我们用一个诚实的问题收尾：2026 年，到底什么时候应该用核方法而不是深度模型？

本文是 核方法 系列的第 7 篇，共 8 篇。 上一篇: 第 6 篇 — 高斯过程 · 下一篇: 第 8 篇 — 深度核学习 vs 深度学习