《Neurocomputing》：Comparative analysis of kernel approximation methods and their ensemble architectures
编辑推荐：
为应对核方法在处理大规模数据时面临的二次计算复杂度挑战，本研究首次系统比较了四种主流的核近似方法——Nystr?m、随机傅里叶特征(RFF)、Kernel Thinning (KT)及本研究提出的新型神经正交随机特征(NORF)——在支持向量机(KSVM)框架下的性能。研究发现，Nystr?m在综合性能和集成潜力上表现最佳，NORF则能显著增加预测多样性，不依赖预定义核。这些方法构成的集成模型在性能上与标准KSVM相近，但训练时间大幅缩短，为解决核方法的可扩展性问题提供了高效、实用的新思路。
在机器学习领域，核方法一直以其强大的非线性建模能力而著称，尤其在支持向量机(SVM)中表现出色。然而，其“阿喀琉斯之踵”在于计算效率：传统的核支持向量机(KSVM)在训练时通常面临至少O(n2)的时间复杂度，其中n是数据点的数量。这意味着，当数据量呈爆炸式增长的今天，经典的核方法在处理现实世界的大规模数据集时变得步履维艰，甚至是不可行的。为了“治愈”这个痛点，研究人员们提出了各种“快进”方案——核近似方法。它们像一个个高效的“压缩算法”，试图在保持核方法优异性能的同时，大幅削减其计算成本。随机傅里叶特征(RFF)和Nystr?m方法便是其中的佼佼者，通过不同的方式对原特征空间进行随机采样和映射，实现了计算复杂度的降低。近年来，Kernel Thinning (KT)作为一种新颖的分布压缩技术也被提出，但其在真实SVM场景下的表现还是个未知数。与此同时，一个根本性问题依然悬而未决：这些不同的近似方法，到底谁更胜一筹？它们各自的优势和短板是什么？如果我们把多个这样的近似模型组合起来（即构建集成模型），是否能产生“1+1>2”的效果，获得比单个模型更稳定、更强大的预测能力？为了回答这些问题，来自西班牙马德里自治大学的研究团队开展了一项深入的比较研究，并引入了一个全新的“选手”——神经正交随机特征(NORF)。他们的研究成果最终发表在了计算智能领域的知名期刊《Neurocomputing》上。
为了开展这项研究，研究人员采用了一套严谨的实验方法论。他们从UCI机器学习仓库和Scikit-learn中选取了32个具有不同规模、类别数和分布特征的公开分类数据集，构成了一个全面的评估基准。研究核心是比较RFF、Nystr?m、KT以及新提出的NORF这四种方法。所有方法都被用于构建一个“近似特征映射+线性SVM”的流水线，以确保公平对比。其中，NORF是一种创新方法，它受“神经塌缩”(Neural Collapse)现象启发，旨在让神经网络学习将不同类别的样本映射到高维空间中的一组正交向量上，从而诱导出一个最优的几何结构。为了量化模型性能，研究评估了平衡准确率、Brier分数（衡量概率预测准确性的指标）、训练时间以及用于评估集成多样性的多个指标（如ALR相关性、JS散度、误差相关性）。在技术实现上，研究者使用了贝叶斯优化（通过Optuna框架）为每个模型-数据集对自动寻找最优超参数，并采用5折交叉验证来稳健地评估模型。对于RFF和Nystr?m，他们使用了Scikit-learn中的RBF_sampler和Nystroem类来实现特征映射。KT的实现则针对分类问题进行了改良，对每个类别单独应用KT后再合并，以保证类别覆盖。NORF则通过一个单隐藏层的神经网络来学习特征映射。所有实验均在严格单核的公平环境下进行，代码已开源。
3.1. 数据集和预处理
研究人员收集了32个来自UCI和Scikit-learn的数据集，涵盖了从简单到复杂、从二分类到多分类（最多26类）的各种任务。表1详细列出了这些数据集的ID、名称、特征维度、类别数及类别分布。数据预处理包括标签统一、分类特征独热编码、按7:3比例进行分层划分训练/测试集（随机种子固定为42）以及标准化，且标准化过程不会引入测试集信息。
3.2. 实验方法
本研究的实验旨在评估模型在Brier分数、平衡准确率、训练时间和多样性度量上的表现。核心方法是：首先使用贝叶斯优化（50次试验）为每个模型-数据集组合寻找最优超参数（优化目标为最小化5折交叉验证的平均Brier分数）；然后，使用最优配置但不同的随机种子训练每个模型15次，记录各项性能指标的平均值。对于RFF和Nystr?m，其近似特征映射的维度d固定为训练集大小的1%（即d = ceil(0.01n)），以控制计算成本并便于与KT比较。KT的“稀释”参数δ固定为1.0，以在理论复杂度与数据集缩减程度之间取得平衡。NORF的输出维度则被设定为大于类别数c，以确保正交目标的存在。
3.3. 个体Brier分数和平衡准确率
表2和表3分别展示了各个模型在所有数据集上的平均测试Brier分数和平衡准确率。从统计摘要来看，标准的KSVM在绝大多数数据集上取得了最佳（排名第1）的Brier分数和准确率，这在意料之中，因为它是精确的核方法。在四种近似方法中，Nystr?m整体表现最好，其Brier分数的中位数（14.0%）和平均排名（2.7）均优于RFF（15.8%， 2.6）、KT（17.1%， 3.3）和NORF（21.9%， 4.1）。Nystr?m在3个数据集上取得了最佳Brier分数，在12个数据集上位列第二。RFF紧随其后，在6个数据集上最佳，10个数据集上次佳。KT在少数特定数据集（如ID 519、27、468）上表现突出，甚至偶尔能超越Nystr?m和RFF。NORF虽然平均性能不占优，但在个别数据集（如ID 327、59）上展现出了竞争力，并且其预测多样性较高（后续分析）。从平衡准确率看，结论类似，KSVM领先，Nystr?m在近似方法中表现最稳定。
3.4. 训练时间
图1（文档中提及但未提供具体内容）显示了各方法的训练时间。由于实现语言不同（scikit-learn为优化C/C++代码，KT为Python），时间对比需谨慎解读。但趋势显示，所有核近似方法（Nystr?m, RFF, KT, NORF）的训练时间都显著低于标准的KSVM，特别是在大规模数据集上。这验证了核近似方法在提升计算效率方面的核心价值。
3.5. 集成性能
研究进一步利用各近似方法固有的随机性，构建了软投票集成模型。他们评估了同质集成（如多个Nystr?m模型）和异质集成（混合不同方法）。关键发现是：集成策略能够稳定地提升所有单一近似方法的性能，减少由于随机性带来的方差。其中，基于Nystr?m的集成表现最为出色，其性能提升潜力最大。尽管这些集成模型在绝对性能上仍未超越标准的KSVM，但它们之间的差距在统计上并不显著。更重要的是，集成模型在保持与KSVM相近性能的同时，其训练时间有了数量级的降低。这为解决“效率与性能不可兼得”的困境提供了一个非常有吸引力的折中方案。
3.6. 预测多样性
多样性是集成学习成功的关键。研究通过ALR相关性、JS散度和误差相关性三个指标来衡量不同模型预测之间的差异。分析表明，NORF产生的预测与其他方法（RFF, Nystr?m）的相关性通常最低，即多样性最高。KT也表现出一定的多样性。而RFF和Nystr?m之间的预测则具有较高的相关性。高多样性意味着将这些方法组合进集成模型时，可能获得更大的性能提升，这为构建高效的异质集成指明了方向。
本研究对四种主流核近似方法（Nystr?m, RFF, KT, NORF）在监督分类任务中进行了迄今为止最全面的实证比较与集成分析。核心结论如下：首先，在单一模型性能上，Nystr?m方法是综合表现最佳的核近似方案，它在大多数数据集上提供了最接近标准KSVM的准确率。其次，集成策略被证明是放大核近似方法价值的有效手段。通过简单聚合多个基于随机性的近似模型，可以显著提升预测的稳健性，且基于Nystr?m的集成展现了最大的性能增益潜力。尽管这些集成模型在峰值准确率上未能超越精确的KSVM，但它们在统计性能相当的前提下，实现了训练时间的大幅缩减，这对大规模应用至关重要。最后，本研究提出的NORF方法虽然平均准确率不占优势，但其核心贡献在于提供了一种不依赖于预定义核函数、且能产生高多样性预测的全新思路，这对于需要模型差异性的集成系统或探索性特征学习具有独特意义。讨论部分指出，未来的工作可以探索更精细的集成构建策略（如基于多样性度量的选择性集成）、将NORF与更深的网络结构结合，以及将这些方法应用于更大规模或流式数据场景。总之，这项研究不仅为从业者根据具体任务（重精度还是重效率）选择核近似方法提供了清晰的指南，也通过集成和新型NORF方法的引入，为突破核方法 scalability瓶颈开辟了新的、实用的技术路径。
