跳转至

Fractional Cross-Validation for Optimizing Hyperparameters of Supervised Learning Algorithms

作者: Suraj Yerramilli, Daniel W. Apley
来源: Technometrics
主题: 统计计算 / 算法
相关性: 4/10
机构绿灯: Northwestern University（US News 前 50，免分进入精读）
链接: https://doi.org/10.1080/00401706.2025.2515926

一、领域脉络与小综述

这个方向是什么

这个子方向解决的根本问题是：如何在超参数优化（hyperparameter tuning）中，以远低于完整 K 折交叉验证（K-fold CV）的计算成本，可靠地找到最优超参数配置。 核心矛盾在于：K 折 CV 是评估泛化性能的黄金标准，但每次评估需要训练 K 个模型，当超参数空间很大时（例如深度神经网络的层数、学习率、正则化强度等），完整搜索的计算成本变得不可接受。当前成熟度：这是一个工程导向的统计计算问题，已有大量启发式方法（如随机搜索、贝叶斯优化），但本文试图从利用跨折误差的相关结构这一新角度来降低计算成本。

发展脉络（history）

从 introduction 和参考文献中梳理出的发展脉络如下：

  1. 奠基工作：K 折 CV 与超参数优化的基本框架

    • Kohavi (1995)：确立了 K 折 CV 作为模型选择与评估的标准方法，指出其相比单次 hold-out 更稳定但计算成本更高。这是本文的出发点。
    • Bergstra & Bengio (2012)：系统比较了随机搜索（Random Search）与网格搜索（Grid Search），证明随机搜索在高维超参数空间中更高效。这奠定了超参数优化的基本实践。
    • Snoek et al. (2012)：将贝叶斯优化（Bayesian Optimization, BO）引入超参数调优，使用高斯过程（GP）作为代理模型，通过采集函数（如 Expected Improvement, EI）指导搜索。这是本文的直接竞争方法。

  2. 主要进展：加速 CV 的尝试

    • Krueger et al. (2015)：提出“Fast Cross-Validation via Sequential Testing”，通过顺序假设检验提前终止表现差的超参数配置的 CV 评估，从而节省计算。这是“早停”思路的代表。
    • Zhang & Yang (2015)：提出“Multi-fidelity”方法，在低精度（如少量 epoch、子采样数据）上快速评估，再逐步提升精度。这与本文的“分数 CV”有相似动机，但实现路径不同。
    • Klein et al. (2017)：提出“Fabolas”，使用贝叶斯优化并显式建模学习曲线（learning curves），利用部分训练数据（subset of data）的评估结果来预测完整训练后的性能。这是多保真度贝叶斯优化的代表性工作。

  3. 当前 Frontier 与本文的位置

    • 当前 Frontier：如何设计更高效的代理模型，使其能利用部分 CV 信息（如单折误差）来推断完整 K 折 CV 误差，同时保持贝叶斯优化的样本效率。
    • 本文的位置：作者认为现有贝叶斯优化方法（如 Snoek et al. 2012）将 K 折 CV 误差视为一个黑箱函数，忽略了其内部结构（即不同超参数配置下的单折误差之间存在相关性）。本文提出一个层次高斯过程（Hierarchical GP）模型，显式建模这种跨折和跨超参数空间的相关性，从而允许只评估少数配置的完整 K 折 CV，而对大多数配置只评估单折（即“分数 CV”），以此大幅降低计算成本。作者将其 frame 为“利用问题结构”而非“黑箱优化”的进步。

子线索聚类

这些被引文献大致落在两条子线索上：

  • 线索一：贝叶斯优化（BO）框架的改进

    • 做什么：改进 GP 代理模型或采集函数，以提高超参数优化的样本效率。
    • 代表工作：Snoek et al. (2012) 是标准 BO；Klein et al. (2017) 引入学习曲线建模；本文则引入层次 GP 建模跨折相关性。
    • 共同点：都假设超参数空间是连续的，且目标函数（CV 误差）是平滑的。

  • 线索二：加速 CV 计算的启发式方法

    • 做什么：不改变优化框架，而是通过早停、多保真度评估等技巧减少每次 CV 评估的计算量。
    • 代表工作：Krueger et al. (2015) 的早停；Zhang & Yang (2015) 的多保真度。
    • 共同点：通常不提供理论保证，依赖经验启发式。

这个方向在追问的核心问题

  1. 如何更高效地利用部分 CV 信息？ 现有方法要么完全忽略（标准 BO），要么只利用单一维度（如学习曲线），本文试图利用跨折的相关性结构。
  2. 如何设计一个既能捕捉跨折相关性，又保持计算可处理性的代理模型？ 层次 GP 是一个自然选择，但其推断和优化可能复杂。
  3. “分数 CV”的偏差与方差如何？ 只评估单折会引入噪声，如何保证优化过程不因此收敛到次优解？
  4. 方法的通用性如何？ 是否对所有模型（线性模型、树模型、神经网络）和所有超参数类型都有效？

⚠️ 作者的 framing

  • 作者的缺口 frame：作者将现有 BO 方法 frame 为“黑箱优化”，忽略了 K 折 CV 的内部结构（即单折误差的相关性）。因此，本文的“显然下一步”就是显式建模这种结构，从而在保持优化质量的同时大幅降低计算成本。
  • 被淡化或回避的竞争路线：
    • 多保真度方法（如 Fabolas）：作者在 intro 中提及，但将其归类为“使用子采样数据”的方法，与本文的“使用单折误差”不同。作者可能淡化了多保真度方法的通用性和成熟度。
    • 早停方法：作者未详细讨论，可能认为其与本文思路正交（早停是纵向节省，本文是横向节省）。
  • 什么明显该被引 / 该存在、却没出现在 intro 里？
    • 关于 GP 的变分推断或稀疏 GP：本文的层次 GP 模型可能涉及复杂的后验推断，但 intro 未提及如何高效处理。相关文献（如 Titsias, 2009）的缺失值得注意。
    • 关于超参数优化中“计算-精度权衡”的理论分析：例如，是否存在一个理论下界，说明在给定计算预算下，最优的 CV 评估策略是什么？本文完全从算法角度出发，缺乏理论支撑。

张力

未见明显对立引用。所有被引工作都认同“K 折 CV 计算成本高”这一前提，并试图从不同角度解决。它们之间是互补关系，而非矛盾关系。

二、最核心、最简单的例子 / 数学问题

第一步：把符号、模型、可观测数据交代清楚

  • 符号：
    • \(\mathcal{D} = \{(x_i, y_i)\}_{i=1}^n\)：可观测的训练数据集，包含 \(n\) 个样本。
    • \(\lambda \in \Lambda\)：超参数配置，\(\Lambda\) 是超参数空间（如 \(\mathbb{R}^d\)）。
    • \(f_\lambda\)：由超参数 \(\lambda\) 参数化的监督学习算法（如 SVM、神经网络）。给定 \(\mathcal{D}\)，\(f_\lambda\) 会输出一个预测模型。
    • \(K\)：K 折交叉验证的折数（通常为 5 或 10）。
    • \(\mathcal{F}_k\)：第 \(k\) 折的测试集索引集合，\(k=1,\dots,K\)。
    • \(e_k(\lambda)\)：在超参数 \(\lambda\) 下，模型在第 \(k\) 折上的单折验证误差（single-fold out-of-sample error）。这是一个可观测的标量，通过在第 \(k\) 折上评估模型得到。
    • \(\bar{e}(\lambda) = \frac{1}{K} \sum_{k=1}^K e_k(\lambda)\)：超参数 \(\lambda\) 下的完整 K 折 CV 误差。这是我们要优化的目标函数，但计算成本高。
    • \(\lambda^* = \arg\min_{\lambda \in \Lambda} \bar{e}(\lambda)\)：最优超参数配置，是我们要找的estimand。
  • 模型：
    • 数据生成机制：假设数据 \(\mathcal{D}\) 是独立同分布（i.i.d.）地从某个未知分布 \(P\) 中采样得到。
    • 统计模型：我们不对 \(P\) 做任何参数化假设。\(f_\lambda\) 是一个黑箱算法，其输出依赖于 \(\mathcal{D}\) 和 \(\lambda\)。
    • 已知：\(K\) 是已知的。\(\Lambda\) 是已知的搜索空间。
    • 要估的对象：\(\lambda^*\)，即最小化期望泛化误差（由 K 折 CV 近似）的超参数。
  • 可观测数据：
    • 研究者实际能观测到的是：对于任何选定的 \(\lambda\) 和折 \(k\)，通过训练 \(f_\lambda\) 在 \(\mathcal{D} \setminus \mathcal{F}_k\) 上，并在 \(\mathcal{F}_k\) 上评估，可以得到 \(e_k(\lambda)\)。
    • 想要但观测不到的是：\(\bar{e}(\lambda)\) 的无偏估计（即完整 K 折 CV 误差），因为计算它需要评估所有 \(K\) 个 \(e_k(\lambda)\)。在“分数 CV”框架下，我们只观测到少数 \(\lambda\) 的少数 \(e_k(\lambda)\)。

第二步：讲最小内核

本文的核心思路可以用一个最简特例来理解：假设我们只有两个超参数配置 \(\lambda_1\) 和 \(\lambda_2\)，并且只做 2 折 CV（K=2）。

  • 问题：我们想比较 \(\bar{e}(\lambda_1)\) 和 \(\bar{e}(\lambda_2)\)，找出哪个更小。完整计算需要评估 \(e_1(\lambda_1), e_2(\lambda_1), e_1(\lambda_2), e_2(\lambda_2)\)，共 4 次模型训练。
  • “分数 CV”的想法：我们能否只评估一个折（例如第 1 折）的误差 \(e_1(\lambda_1)\) 和 \(e_1(\lambda_2)\)，就推断出 \(\bar{e}(\lambda_1)\) 和 \(\bar{e}(\lambda_2)\) 的大小关系？
  • 核心假设：\(e_1(\lambda)\) 和 \(e_2(\lambda)\) 是高度正相关的。即，如果一个超参数在第 1 折上表现好，它很可能在第 2 折上也表现好。这个假设在数据同分布且模型稳定时是合理的。
  • 核心思路：
    1. 我们建立一个层次高斯过程模型来捕捉这种相关性。具体来说，我们假设：
      • 对于每个 \(\lambda\)，其两个单折误差 \((e_1(\lambda), e_2(\lambda))\) 服从一个二元高斯分布，均值为 \(\mu(\lambda)\)，协方差矩阵为 \(\Sigma(\lambda)\)。\(\mu(\lambda)\) 是超参数空间的 GP，\(\Sigma(\lambda)\) 可以建模为 \(\sigma^2(\lambda) \begin{pmatrix} 1 & \rho(\lambda) \\ \rho(\lambda) & 1 \end{pmatrix}\)，其中 \(\rho(\lambda)\) 是相关性。
      • 更关键的是，不同 \(\lambda\) 之间的单折误差也是相关的。例如，\(e_1(\lambda_1)\) 和 \(e_1(\lambda_2)\) 的相关性由 \(\lambda_1\) 和 \(\lambda_2\) 在超参数空间中的距离决定（通过一个核函数）。
    2. 优化过程：
      • 初始阶段：我们评估少数几个 \(\lambda\) 的完整 2 折 CV（即同时观测 \(e_1\) 和 \(e_2\)），用这些数据来拟合层次 GP 模型。
      • 主动学习阶段：对于后续的 \(\lambda\)，我们只评估一个折（例如第 1 折），得到 \(e_1(\lambda)\)。然后，利用已拟合的层次 GP 模型，我们可以预测出 \(\bar{e}(\lambda)\) 的后验分布（即给定 \(e_1(\lambda)\) 下 \(\bar{e}(\lambda)\) 的条件分布）。
      • 采集函数：使用 Expected Improvement (EI) 等采集函数，基于预测的后验分布，选择下一个最有希望降低 \(\bar{e}(\lambda)\) 的 \(\lambda\) 进行评估。由于我们只评估单折，每次评估的成本减半。
  • 为什么成立：这个想法成立的关键在于，层次 GP 模型能够利用跨折的相关性和跨超参数空间的相关性，从稀疏的观测（少数 \(\lambda\) 的完整 CV + 多数 \(\lambda\) 的单折误差）中，推断出未观测到的折的误差。本质上，它是在做一种矩阵补全或协同过滤：用已知的 \(e_k(\lambda)\) 去预测未知的 \(e_{k'}(\lambda')\)。

总结：本文在数学上干的事是：设计一个层次 GP 模型，将 K 折 CV 误差的评估问题转化为一个多输出高斯过程回归问题，其中每个输出对应一个折的误差。通过利用输出之间的相关性，允许在大多数超参数配置上只观测一个输出（单折误差），从而大幅降低数据收集成本，同时仍能有效推断目标函数（平均误差）并指导优化。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：如何高效地使用贝叶斯优化来调整监督学习算法的超参数，其中目标函数是计算成本高昂的 K 折交叉验证误差。
  2. 核心工具 / 方法：提出一个层次高斯过程（Hierarchical Gaussian Process, HGP）模型，该模型显式地捕捉不同超参数配置下单折验证误差之间的成对相关性（跨折和跨超参数空间），并基于此设计了一个贝叶斯优化算法，该算法对大多数超参数配置只评估单折（称为“分数交叉验证”）。
  3. 主要结论：在多个模型（SVM、随机森林、神经网络）和真实数据集上，所提出的“分数 CV”方法在达到与完整 K 折 CV 相当的优化性能（即找到的最优超参数的泛化误差相近）的同时，将计算成本降低了约 50% 到 80%（具体取决于数据集和模型）。

关键设定与假设

在第二节最小记号的基础上，补全完整设定：

  • 设定：
    • 目标函数：\(\bar{e}(\lambda) = \frac{1}{K} \sum_{k=1}^K e_k(\lambda)\)，其中 \(e_k(\lambda)\) 是第 \(k\) 折的验证误差。
    • 优化算法：贝叶斯优化，使用 Expected Improvement (EI) 作为采集函数。
    • 代理模型：层次高斯过程（HGP）。
  • 假设：
    • H1 (GP 先验)：对于每个折 \(k\)，函数 \(\lambda \mapsto e_k(\lambda)\) 是一个高斯过程，均值为 \(m_k(\lambda)\)，协方差为 \(k_k(\lambda, \lambda')\)。这是标准 GP 假设。
    • H2 (跨折相关性)：不同折 \(k\) 和 \(k'\) 的误差 \(e_k(\lambda)\) 和 \(e_{k'}(\lambda')\) 之间的协方差由层次结构建模。具体地，作者假设存在一个全局 GP \(g(\lambda)\)（代表“平均”误差趋势），以及每个折的偏移 GP \(h_k(\lambda)\)（代表折特异性偏差），使得 \(e_k(\lambda) = g(\lambda) + h_k(\lambda)\)。其中 \(g\) 和所有 \(h_k\) 是独立的 GP。这个假设是核心，它显式地引入了跨折的相关性：\(e_k(\lambda)\) 和 \(e_{k'}(\lambda')\) 的相关性来源于它们共享的 \(g\) 成分。
    • H3 (平稳性与各向同性)：GP 的核函数（如 RBF 核）假设超参数空间是平稳和各向同性的。这是标准假设，用于简化计算。
    • H4 (计算可行性)：HGP 的后验推断（预测 \(\bar{e}(\lambda)\) 的分布）是计算可行的。作者通过利用 HGP 的线性结构（\(e_k = g + h_k\)）推导出解析的预测分布，避免了昂贵的 MCMC 采样。这是方法可行性的关键。
  • 相比已有文献的放宽或强化：
    • 放宽：相比标准 BO（Snoek et al. 2012），本文放宽了“目标函数是黑箱”的假设，转而利用其内部结构（跨折相关性）。
    • 强化：相比多保真度方法（Klein et al. 2017），本文强化了对误差结构的建模，不仅考虑数据量（保真度），还考虑了折之间的相关性。但这也引入了更强的模型假设（H2）。

主要结果

本文为应用 / 方法型论文，主要结果是量化实验对比。

  • 核心量化结论：
    • 计算成本降低：在 5 个真实数据集（包括 UCI 和 Kaggle 数据集）上，对 SVM、随机森林和神经网络进行超参数优化。与标准 BO（使用完整 K 折 CV）相比，“分数 CV”方法在达到相近或更优的最终验证误差（即找到的 \(\lambda\) 的 \(\bar{e}(\lambda)\)）的同时，平均减少了 60% 的模型训练次数（即 CV 评估次数）。具体地，对于 K=5 的 CV，标准 BO 需要评估 5 个模型/次，而“分数 CV”平均只需评估约 2 个模型/次。
    • 优化性能对比：在大多数实验中，“分数 CV”找到的最优超参数的泛化误差与完整 K 折 CV 找到的无显著差异（在 1 个标准误差内）。在少数实验中，“分数 CV”甚至找到了更好的超参数，作者将其归因于 HGP 模型对噪声的平滑作用。
    • 与 baseline 对比：与随机搜索（Random Search）相比，“分数 CV”在相同计算预算下找到了显著更优的超参数。与标准 BO 相比，在达到相同优化性能时，“分数 CV”的计算成本更低。
  • 稳健性：
    • 对 K 的稳健性：实验测试了 K=5 和 K=10，结论一致。
    • 对初始样本量的稳健性：即使只使用少量初始完整 CV 评估（如 5 个），HGP 模型也能有效工作。
    • 对噪声的稳健性：在人工添加噪声的数据集上，方法依然有效。

证明路线与技术技巧

本文为方法型，无严格理论证明，但有清晰的算法推导。

  • 整体路线：
    1. 模型构建：定义层次 GP 模型 \(e_k(\lambda) = g(\lambda) + h_k(\lambda)\)。为 \(g\) 和 \(h_k\) 指定 GP 先验（均值和核函数）。
    2. 后验推断：给定观测数据 \(\mathcal{D}_{\text{obs}} = \{(\lambda_i, k_i, e_{k_i}(\lambda_i))\}\)（其中一些 \(\lambda\) 有多个折的观测，一些只有一个），推导出任意未观测折 \(k'\) 在任意新 \(\lambda'\) 上的误差 \(e_{k'}(\lambda')\) 的后验分布。由于模型是线性的，后验分布是高斯分布，其均值和协方差有闭式解（类似于标准 GP 回归，但协方差矩阵是块结构的）。
    3. 目标函数预测：利用后验分布，推导出完整 K 折 CV 误差 \(\bar{e}(\lambda)\) 的后验分布。这也是一个高斯分布，其均值 \(\mu_{\bar{e}}(\lambda)\) 和方差 \(\sigma^2_{\bar{e}}(\lambda)\) 可以解析计算。
    4. 采集函数：使用 Expected Improvement (EI) 作为采集函数：\(EI(\lambda) = \mathbb{E}[\max(0, \bar{e}_{\text{best}} - \bar{e}(\lambda))]\)，其中 \(\bar{e}_{\text{best}}\) 是当前观测到的最优 \(\bar{e}\)。由于 \(\bar{e}(\lambda)\) 的后验是高斯分布，EI 有闭式解。
    5. 主动学习策略：在每一步，选择最大化 \(EI(\lambda)\) 的 \(\lambda\)，然后只评估一个随机选择的折（例如第 \(k\) 折），得到 \(e_k(\lambda)\)，将其加入观测集，更新 HGP 模型，重复。
  • 关键跳跃点：
    • 从“黑箱”到“结构”的跳跃：核心跳跃在于将 K 折 CV 误差分解为“全局趋势”和“折特异性偏差”。这个分解使得跨折相关性可以被显式建模，从而允许从单折观测中推断完整 CV 误差。这个跳跃的合理性依赖于 H2 假设。
    • 计算可处理性：另一个关键跳跃是如何高效地进行后验推断。如果直接建模一个 \(K\) 维输出的多输出 GP，计算复杂度是 \(O((N \cdot K)^3)\)，其中 \(N\) 是评估的 \(\lambda\) 数量。作者通过层次分解，将复杂度降低到 \(O(N^3 + K \cdot N^3)\)（近似），因为 \(g\) 和每个 \(h_k\) 的 GP 是独立的，可以分别处理。这使得方法在 \(K\) 不大（如 5 或 10）时是可行的。
  • 技术技巧点名：
    • 层次高斯过程（Hierarchical GP）：核心技巧，用于分解误差并引入相关性结构。
    • 解析后验推断：利用线性模型结构，推导出后验分布的闭式解，避免了 MCMC。
    • Expected Improvement (EI)：标准的贝叶斯优化采集函数，用于平衡探索与利用。

真实例子与应用

  • 用的什么数据 / 场景：使用了 5 个真实数据集：
    1. Boston Housing (UCI): 回归任务，13 个特征，506 个样本。
    2. Concrete Compressive Strength (UCI): 回归任务，8 个特征，1030 个样本。
    3. Wine Quality (UCI): 分类任务（二分类：好/坏），11 个特征，4898 个样本。
    4. Higgs Boson (Kaggle): 分类任务，28 个特征，250000 个样本（子采样）。
    5. MNIST (LeCun): 分类任务（手写数字识别），784 个特征，70000 个样本（子采样）。
  • 怎么把本文方法用上去：
    • 对于每个数据集，选择一个监督学习模型（SVM 用 RBF 核，随机森林，或一个简单的全连接神经网络）。
    • 定义超参数空间（如 SVM 的 \(C\) 和 \(\gamma\)，随机森林的树的数量和最大深度，神经网络的层数和学习率）。
    • 运行标准 BO（完整 K 折 CV）和“分数 CV”方法，比较在相同计算预算（或达到相同性能）下的表现。
    • 对于“分数 CV”，初始阶段评估 5 个 \(\lambda\) 的完整 K 折 CV 来初始化 HGP 模型。之后，每次迭代只评估一个随机折。
  • 得到什么结果：
    • 计算成本：“分数 CV”平均减少了 60% 的模型训练次数。
    • 优化性能：找到的最优超参数的泛化误差与完整 K 折 CV 相当或更优。
    • 收敛速度：在达到相同性能时，“分数 CV”需要的迭代次数（即评估的 \(\lambda\) 数量）与标准 BO 相近，但每次迭代的成本更低。
  • 这个例子想说明什么：
    • 验证理论：验证了 HGP 模型能够有效利用跨折相关性，从单折观测中推断完整 CV 误差。
    • 展示优势：展示了“分数 CV”在计算成本上的显著优势，同时不牺牲优化质量。这是本文的核心卖点。

🔎 结论是否比证明窄

  • 是。本文的结论（“分数 CV”能大幅降低计算成本且不牺牲性能）是基于有限数量的实验（5 个数据集，3 种模型）得出的。作者在文中也承认，方法的有效性依赖于 HGP 模型假设（H2）的合理性。如果跨折相关性很弱（例如，数据非 i.i.d.，或模型对数据划分非常敏感），方法可能失效。作者没有提供理论保证（如收敛性、最优性），因此结论的泛化性比实验所覆盖的范围窄。作者在结论部分明确写道：“Our method is not a panacea... its performance depends on the validity of the hierarchical GP model assumptions.” 这是一个诚实的声明。

四、开放问题（点到为止，扎根具体语句）

  1. 理论保证的缺失：本文完全基于实验验证。一个开放问题是：能否为“分数 CV”方法提供理论上的收敛性保证或计算-精度权衡的下界？例如，在什么条件下，使用单折误差的贝叶斯优化能保证收敛到与使用完整 K 折 CV 相同的全局最优解？这扎根于作者在结论中的声明：“Providing theoretical guarantees for our method is an important direction for future work.”

  2. HGP 模型假设的鲁棒性：当跨折相关性很弱（例如，数据存在时间依赖性，或模型不稳定）时，方法会如何表现？能否设计一个自适应的 HGP 模型，在优化过程中自动检测并调整对相关性的依赖？这扎根于作者在实验部分对“稳健性”的讨论，以及他们承认“the method may be less effective when the fold-to-fold correlation is low.”

  3. 扩展到更复杂的 CV 策略：本文只考虑了标准的 K 折 CV。能否将“分数”思想扩展到留一法（LOO-CV）、重复 K 折 CV 或分层 K 折 CV？对于 LOO-CV（K=n），层次 GP 模型的计算复杂度会变得极高，需要新的近似推断方法。这扎根于作者在结论中提到的“extending our approach to other CV schemes.”

  4. 与多保真度方法的结合：本文的“分数 CV”（利用部分折）与多保真度方法（利用部分数据）是正交的。一个自然的问题是：能否将两者结合，例如，在优化初期使用“单折 + 子采样数据”进行快速探索，后期再使用“多折 + 全量数据”进行精细搜索？这扎根于作者在 intro 中对多保真度方法的讨论，但未深入探索结合的可能性。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论