🤖 machine learning

Bernstein-Schur Kernels: Random Features by Sketched Modulation and Radial Randomization

本文引入了 Bernstein-Schur 核，这是一类由有限特征分量与完全单调平移不变分量乘积构成的非平稳核，并提出了一种新颖的随机特征构造方法，该方法结合了用于有限调制部分的草图化技术（sketching）与用于平移不变部分的径向随机化技术，从而实现了算子范数界限仅依赖于内在维度而非环境维度的无偏近似。

原作者： Taha Bouhsine

发布于 2026-06-11

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Taha Bouhsine

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图构建一个超级智能的计算机程序，使其能够识别数据中的模式。为了实现这一目标，该程序使用了一种被称为“核函数”（kernel）的数学工具。你可以将核函数想象成一个相似度计算器：它观察两份数据，并告诉你它们有多少共同之处。

长期以来，这些计算器要么是：

基于距离的： “这两个点之间有多远？”（就像测量两个城市之间的直线距离）。
基于角度的： “这两个点指向的方向有多一致？”（就像检查两个箭头是否指向同一个方向）。

大多数现代人工智能技巧在处理这两类计算器时表现都很出色。但本文的作者发现了一种特殊的相似度计算器，它以一种非常特定且复杂的方式，将距离和方向结合在了一起。他们称之为 “偏置 $\Xi$ -核函数”（Biased $\Xi$ -kernel）。

问题所在：“不守规矩”的计算器

这个新出的计算器有点像个叛逆者。它不符合那些让 AI 运行快速的标准规则。

如果你尝试使用标准的“距离”技巧，它会失效。
如果你尝试使用标准的“方向”技巧，它也会失效。

通常，当一个计算器如此“不守规矩”时，使用它的唯一方法就是写下一张巨大的、难以处理的电子表格，记录每一次比较。如果你有一百万个数据点，这张表格的大小将超过地球的存储容量。

解决方案：“双层夹心”技巧

由 Taha Bouhsine 领导的作者们发现了一个聪明的办法，可以将这个不守规矩的计算器分解为两个更简单、更易处理的部分。他们意识到，这个计算器实际上只是两个东西相乘的结果：

“对齐”部分（The Alignment Piece）： 检查数据点是否指向相同的方向（这是一个多项式）。
“邻近”部分（The Proximity Piece）： 检查点与点之间有多接近（这是一个径向核函数）。

他们将这种方法称为 Bernstein–Schur 方法。你可以把它想象成制作一个复杂的三明治。与其试图一次性吞下整个三明治，不如将面包（对齐）与馅料（邻近）分开，分别处理它们，然后再把它们组合在一起。

如何实现快速化：“草图”与“采样器”

为了让它足够快以投入实际应用，他们使用了两个神奇的工具：

采样器（用于处理“邻近”部分）： 对于“有多近”的部分，他们使用了名为**随机傅里叶特征（Random Fourier Features）**的技术。想象一下，你想知道一个城市的平均气温。你不需要测量每一条街道，而是随机选取几个点进行测量，然后取其平均值。这能让你在不做全部工作的情况下，得到一个非常准确的估算。他们对计算器的距离部分应用了这一技术。
草图（用于处理“对齐”部分）： 对于“方向”部分，数学运算通常需要巨大的内存（具体来说，内存占用随特征数量的平方增长，这非常缓慢）。为了解决这个问题，他们使用了 TensorSketch。想象你有一幅巨大且细节丰富的画作，但你的空间只能容纳一个小草图。与其绘制每一个笔触，不如使用一种特殊的算法将画作压缩成一个小草图，同时仍保留主要的轮廓和色彩。这使得他们能够大幅度缩减内存占用。

通过将这两者结合，他们创造了一种名为 RAY（ $\Xi$ -核函数的随机近似）的新方法。

这为什么重要（研究结果）

论文证明，这种新方法与那种缓慢、庞大的电子表格法效果一样好，但它更快，且占用的内存更少。

它能在他人失败的地方奏效： 他们在并非处于完美球体（如球体）上的数据上进行了测试。在这些“非球体”数据上，旧的方法（如 Nyström 方法）会随着数据变得复杂而性能下降。而 RAY 依然保持强劲且准确。
它是“流式”的： 由于它不需要存储巨大的电子表格，它可以随着数据的到来，逐一处理数据。这对于 AI 中的注意力机制（Attention mechanisms）（现代聊天机器人背后的技术）至关重要，因为这类系统需要在不耗尽内存的情况下处理长序列的单词。
“耦合”效应： 论文表明，这种特定的计算器在需要同时兼顾方向和距离的任务中具有独特优势。如果任务只关心其中之一，简单的计算器就足够了；但对于这种需要两者兼顾的复杂任务，这种新方法才是赢家。

总结

作者们将一个过于复杂且缓慢的数学工具进行了拆解，将其转化为两个更简单的部分，并对每一部分应用了不同的“压缩”技巧。其结果是一种快速、内存高效的方法，可以利用一种强大的新型相似度计算器，这种计算器能够处理以往方法难以应对的复杂现实世界数据。他们通过使用这种方法来加速 AI 注意力机制，并在以前无法处理的大规模数据集上训练模型，从而证明了其有效性。

技术摘要：通过草图调制与径向随机化实现的 Bernstein–Schur 核

1. 问题陈述

核方法（例如 SVM、核岭回归、高斯过程和 Transformer 注意力层）依赖于 $N \times N$ 的 Gram 矩阵 $K_{ij} = k(x_i, x_j)$ 。将这些方法扩展到大规模数据集（ $N > 10^5$ ）受限于 $O(N^2)$ 的存储和 $O(N^3)$ 的分解成本。随机特征映射通过低维的 $z$ 来近似 $k(x, w) \approx z(x)^\top z(w)$ ，提供了 $O(NM)$ 的替代方案。

然而，现有的随机特征构造在结构上存在局限性：

随机傅里叶特征 (RFF) 适用于通过 Bochner 定理定义的平移不变核。
多项式草图（如 TensorSketch）适用于点积核。
Nyström 方法依赖于快速的谱衰减且具有数据依赖性。

本文研究的是有偏 $\mathcal{T}$ -核：
$k_{\mathcal{T},b}(w, x) = \frac{(w^\top x + b)^2}{\|w - x\|^2 + \varepsilon}, \quad b \ge 0, \varepsilon > 0$
该核耦合了对齐（分子中的平方内积）与接近度（分母中的反平方距离）。至关重要的是，它既不是平移不变核，也不是点积核（除非在单位球面上距离与内积是双射关系）。因此，标准的 RFF 和多项式草图无法直接应用于完整的核，迫使人们回归到计算精确值时难以处理的 $O(N^2)$ Gram 矩阵。

2. 方法论：Bernstein–Schur 随机特征

作者提出了 RAY（ $\mathcal{T}$ -核的随机近似），这是一种针对更广泛的 Bernstein–Schur 核类的随机特征构造。这些核被定义为有限特征核与完全单调平移不变核的 Schur 积（逐元素积）。

该方法论将 $\mathcal{T}$ -核分解为两个可处理的因子：

多项式调制： $p_b(w, x) = (w^\top x + b)^2$ 。它具有一个精确的、有限维度的特征映射 $p_b(x) \in \mathbb{R}^{d^2+d+1}$ 。
径向因子： $h_\varepsilon(w, x) = (\|w - x\|^2 + \varepsilon)^{-1}$ 。它在 $\|w-x\|^2$ 上是完全单调的，并可以作为单个尺度参数 $t \sim \text{Exp}(\varepsilon)$ 下高斯核的混合进行 Bernstein–Widder 表示。

构造步骤：

分解： 将 $k_{\mathcal{T},b}$ 表示为 $p_b \cdot h_\varepsilon$ 。
径向采样： 采样尺度参数 $t_j \sim \text{Exp}(\varepsilon)$ 。
高斯 RFF： 对于每个 $t_j$ ，对生成的高斯核 $e^{-t_j \|x-w\|^2}$ 应用随机傅里叶特征。
调制草图化： 不再使用精确的 $O(d^2)$ 多项式特征 $p_b(x)$ ，而是应用 TensorSketch（二阶）将调制压缩到维度 $m$ 。
张量积： 最终的特征映射 $z(x)$ 是草图化调制与径向 RFFs 的张量积的拼接。

生成的特征维度为 $D \times m$ ，其中 $D$ 是径向抽样次数， $m$ 是草图大小。该维度摆脱了与精确多项式特征相关的 $O(d^2)$ 维度下限。

3. 核心贡献

本文在理论和实证方面做出了以下贡献：

一种新的核类 (Bernstein–Schur)： 作者定义了一类由有限特征核与完全单调径向核构成的核。他们为整个此类核（而非仅 $\mathcal{T}$ -核）提供了一个统一的随机特征估计器。
无偏性与方差分析：
- 证明了该估计器是无偏的（ $E[z(x)^\top z(w)] = k(x, w)$ ）。
- 推导了“平坦”估计器（每个尺度一个频率）的精确方差公式，表明其方差随 $(R^2 + b)^4 / (D\varepsilon^2)$ 缩放。
- 证明了在层次预算内，使用每个尺度一个频率（ $D'=1$ ）是方差最优的。
算子范数保证：
- 建立了 Gram 矩阵近似的期望矩阵-Bernstein 算子范数界限。不同于随 $N$ 缩放的粗略逐元素界限，该界限取决于内在维度以及核与调制 Gram 矩阵的特征值。
- 证明了在该近似下，核岭回归 (KRR) 具有确定性的相对谱稳定性。
双重随机化估计器 (RAY)：
- 引入了调制因子的草图化。理论分析表明，以草图化为条件保留了内在维度的算子范数保证，仅增加了一个受草图大小 $m$ 控制的可调加性误差项。
- 证明了这种方法消除了 $O(d^2)$ 的特征维度障碍，使方法具备高维可扩展性。
误差分解： 提供了调制–径向误差分解，显示径向噪声被对齐因子调制，而调制误差则被径向接近度局部化。这解释了为什么即使在调制被压缩时，乘积仍然有效。

4. 实验结果

实验主要在非球面机制（具有不同范数的有界球体）中进行，在此机制下 $\mathcal{T}$ -核是真正的非点积核。

非球面性能： 在具有变化范数的有界球体上，无论维度 $d$ 如何变化，RAY 均保持 $O(1/\sqrt{D})$ 的收敛速率。相比之下，即使在匹配的 landmark 数量下，均匀采样和 k-means Nyström 方法也会随着 $d$ 的增加而显著退化。
成本匹配比较： 在匹配表示成本的情况下，自适应 Nyström 方法（数据依赖型）在适中的 $N$ 时可能比 RAY 更准确。然而，RAY 提供的是数据无关、无偏且流式的特征，这是 Nyström 无法提供的。
耦合目标偏好： 在需要同时具备对齐与接近度的合成目标控制测试中， $\mathcal{T}$ -核（由 RAY 近似）的表现优于仅建模单一因子的核（如高斯、IMQ 或仅多项式核）。这验证了该核的归纳偏置。
线性时间注意力： 将 RAY 应用为线性时间注意力原语。它成功近似了精确的 $\mathcal{T}$ -注意力，其中值误差随特征维度 $M$ 的增加而减小，同时保持了 $O(NM)$ 的内存占用，并支持因果、流式解码（这对于基于 landmark 的方法是不可能的）。
大规模训练： 在 HIGGS 数据集（1100 万个样本）上，RAY 实现了流式环境下的原始训练（Primal Training），在这种环境下 Gram 矩阵无法存储，且其表现优于在匹配预算下的精确调制限制。

5. 重要性与主张

本文在三个主要领域提出了其重要性：

弥合结构性差距： 它通过将核分解为易于处理的组件（草图化与 RFF），首次为既非平移不变也非点积的核提供了随机特征构造方法。
无需数据依赖的可扩展性： 它为非平稳核提供了一种流式的、数据无关的 Nyström 方法替代方案，同时避免了 $O(N^2)$ 的 Gram 矩阵和 $O(d^2)$ 的特征维度障碍。
理论严谨性： 其分析超越了简单的逐元素界限，提供了受内在维度控制的算子范数保证，从而对结构化核的近似误差提供了更细致的理解。

作者谦虚地指出，虽然 RAY 在流式和大规模设置中非常有效，但在适合固定预算、中等规模 $N$ 的问题中，自适应 Nyström 方法可能仍然更优，因为后者接受数据依赖性。该方法要求输入具有有界范数以确保稳定性，且由于多项式因子的存在，其方差常数高于标准 RFF。