什么是 Nyström 方法？
Nyström 方法是一种低秩 Kernel Approximation 技术，它选择 Landmark Sample，再根据对应 Kernel Column 与交叉矩阵重建完整 Positive-semidefinite Gram Matrix。
快速了解
| 创建时间 | Williams 与 Seeger 于 2000 年将其用于大规模 Kernel Approximation |
|---|---|
| 规范文档 | 官方规范 |
工作原理
从 Landmark Column 重建 Gram Matrix
选择 Landmark Index 后，可把 Kernel Matrix 分解为采样列 C 及其交叉块 W。使用 W 的 Inverse 或 Pseudoinverse，就能在数值过程和输入 Kernel 满足条件时得到 Positive-semidefinite Low-rank Reconstruction。
Williams 与 Seeger 的大规模 Kernel Approximation 论文分析了这种构造。无论原始 Feature Space 维度多大，有效 Rank 都不会超过 Landmark 数量与其 Numerical Rank。
选择 Landmark 并稳定保留的 Spectrum
Uniform Landmark Sampling 简单，但可能遗漏稀有区域、Minority Class 或 High-leverage Point。Stratified、Clustering-based、Leverage-score 与 Adaptive Selection 可以改善特定覆盖，同时增加成本与假设；选择过程只能使用训练协议允许的信息。
W 的较小 Eigenvalue 会让直接 Inverse 放大噪声。应采用有依据的 Eigentruncation、Pseudoinverse Tolerance 或 Regularization，并记录 Landmark Identity、Order、Preprocessing、Kernel 参数和 Factorization Setting。只有 Seed 未必能重现拟合基。
同时验证矩阵、特征与下游决策
Nyström Factor 可以为训练和未见样本提供 Explicit Feature，但推理必须对同一组 Landmark 计算 Kernel，并应用相同 Spectral Scaling。超出 Landmark Coverage 的新样本可能得到看似稳定却质量较差的表示。
当前 scikit-learn Nystroem 文档提供可复用 Feature Map。应对照 Exact-kernel Subset 与其他近似，评测 Relative Matrix Error、关键两两相似度、Spectral Subspace Error、任务指标、延迟、内存及跨 Landmark Seed 的表现。
主要特点
- 通过 Landmark Column 近似 Positive-semidefinite Kernel Matrix
- 所得 Rank 受 Landmark 数与保留 Spectrum 限制
- 使用绑定到选定训练样本的 Data-dependent Basis
- 在矩阵精度、少数区域覆盖与计算资源间权衡
- 只能通过冻结 Landmark Basis 转换未见输入
- 需要稳定处理 Landmark Block 的伪逆、截断或正则化
常见用途
- 把 Kernel Ridge Regression 或 Classification 扩展到更多样本
- 近似 Kernel PCA 与其他 Kernel Eigenspace
- 把 Spectral Graph Embedding 扩展到新观测
- 从昂贵 Kernel 构造可复用 Low-rank Feature
- 比较 Landmark Approximation、Exact Kernel 与 Random Fourier Baseline
示例
Loading code...常见问题
Nyström 方法如何近似 Kernel Matrix？
它选择 Landmark Column `C`，构造其交叉矩阵 `W`，再计算 `C W_dagger C^T`。结果 Rank 不超过保留的 Landmark Spectrum，并会优先匹配被采样的结构。
Nyström 方法需要多少 Landmark？
不存在通用数量。应逐步增加 Landmark，直到代表性切片上的 Matrix、Spectrum 与下游指标稳定，同时满足内存和延迟预算；还要重复 Landmark Selection，避免单次采样掩盖覆盖失败。
Nyström Landmark 应如何选择？
Uniform Sampling 是基线；数据不均衡或异质时，可比较 Stratification、Clustering Center、Leverage Score 或 Adaptive Scheme。选择过程必须遵守 Train-test Boundary 与部署期可用性。
Nyström 方法与 Random Fourier Features 有什么区别？
Nyström 从采样 Kernel Column 构造 Data-dependent Basis，可近似多类 Positive-semidefinite Kernel；经典 RFF 为 Shift-invariant Kernel 采样 Data-independent Spectral Map。两者支持范围、成本与失败模式不同。
Nyström Feature Map 能转换未见样本吗？
可以。对每个新样本计算它与已存 Landmark 的冻结 Kernel，再应用拟合时的 Spectral Normalization。推理时不能重新采样 Landmark 或重拟合缩放，还应监控超出 Landmark Coverage 的输入。