新上线今天0 投票
Bernstein-Schur核：通过草图调制与径向随机化实现随机特征
研究背景与挑战
核方法是机器学习的重要工具，但传统核方法在大规模数据上计算成本高昂。随机特征（Random Features）通过显式构造低维特征映射来近似核函数，从而加速计算。然而，现有随机特征技术主要针对两类核：平移不变核（如高斯核）和点积核（如多项式核）。前者依赖Bochner采样，后者依赖多项式草图。
Bernstein-Schur核是一类非平稳核，由有限特征核（具有显式有限维特征映射）与完全单调平移不变核的乘积构成。这类核介于平移不变核与点积核之间，因此无法直接应用Bochner采样或多项式草图。这为随机特征构造带来了独特挑战。
核心方法：双重随机化策略
研究提出了一种针对整个Bernstein-Schur核类的随机特征构造方法，核心思路是同时随机化两个因子：
- 草图化有限调制：对有限特征映射进行随机草图（sketch），降低维度。
- 随机化径向因子：利用完全单调核的Bernstein-Widder表示，将径向部分分解为单变量尺度参数的混合，然后通过一维采样结合高维高斯随机傅里叶特征来近似。
最终的特征维度为 (Dm)，其中 (m) 是草图大小，(D) 是径向采样次数。这一维度远低于精确调制特征的 (O(d^2)) 维度，显著降低了计算复杂度。
理论保证：从精确到草图化
研究分两步建立理论：
- 精确调制极限（(m \to \infty)）：当保持调制精确时，证明了估计的无偏性、推荐平坦估计器的精确方差、基于矩阵Bernstein不等式的算子范数界（由核与调制Gram矩阵的顶部特征值以及内在维度控制），以及确定性相对谱核岭稳定性结果。
- 双重随机化估计器：通过条件化于草图，估计器继承了内在维度算子范数保证，并额外添加一个可调草图项（独立于 (D)）。
实例应用：yat核族
论文重点展示了yat核 (k_{yat,b}(w,x) = (w^\top x + b)^2 / (|w-x|^2 + \varepsilon))，其中 (b \ge 0)。该核族通过有限差分在参数 (b) 上生成逆多二次核（Inverse Multiquadric, IMQ）。对于yat核，径向混合对应IMQ谱采样器，且在固定径向特征预算下，每个尺度仅需一个频率即可达到方差最优。
意义与展望
这项工作为处理非平稳核提供了新工具，拓展了随机特征的应用范围。理论上的内在维度控制避免了传统逐项界（(N \max_{ij})）的松散性，使得估计更高效。未来可进一步探索草图大小 (m) 与径向采样数 (D) 的自适应选择策略，以及在其他核族上的应用。