2025-11-11T14:19:08.761279

Budgeted Multiple-Expert Deferral

DeSalvo, Mohri, Mohri et al.
Learning to defer uncertain predictions to costly experts offers a powerful strategy for improving the accuracy and efficiency of machine learning systems. However, standard training procedures for deferral algorithms typically require querying all experts for every training instance, an approach that becomes prohibitively expensive when expert queries incur significant computational or resource costs. This undermines the core goal of deferral: to limit unnecessary expert usage. To overcome this challenge, we introduce the budgeted deferral framework, which aims to train effective deferral algorithms while minimizing expert query costs during training. We propose new algorithms for both two-stage and single-stage multiple-expert deferral settings that selectively query only a subset of experts per training example. While inspired by active learning, our setting is fundamentally different: labels are already known, and the core challenge is to decide which experts to query in order to balance cost and predictive performance. We establish theoretical guarantees for both of our algorithms, including generalization bounds and label complexity analyses. Empirical results across several domains show that our algorithms substantially reduce training costs without sacrificing prediction accuracy, demonstrating the practical value of our budget-aware deferral algorithms.
academic

Budgeted Multiple-Expert Deferral

基本信息

  • 论文ID: 2510.26706
  • 标题: Budgeted Multiple-Expert Deferral
  • 作者: Giulia DeSalvo (Google DeepMind), Clara Mohri (Harvard University), Mehryar Mohri (Google Research & Courant Institute), Yutao Zhong (Google Research)
  • 分类: cs.LG, stat.ML
  • 发表时间: 2025年10月30日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.26706

摘要

学习将不确定的预测推迟给昂贵的专家是提高机器学习系统准确性和效率的强大策略。然而，标准的推迟算法训练程序通常需要为每个训练实例查询所有专家，当专家查询产生显著的计算或资源成本时，这种方法变得极其昂贵，违背了推迟的核心目标：限制不必要的专家使用。为了克服这一挑战，本文引入了预算推迟框架，旨在训练有效的推迟算法，同时最小化训练期间的专家查询成本。

研究背景与动机

问题定义

传统的多专家推迟学习（Learning to Defer）面临一个根本性矛盾：

  1. 核心目标：通过选择性地将预测任务推迟给专家来降低成本
  2. 训练现实：标准训练程序需要为每个训练样本查询所有专家的成本，总成本为 neT（专家数×训练样本数）
  3. 成本悖论：训练过程本身就违背了成本控制的初衷

研究重要性

  • 实际应用需求：在涉及大型语言模型、人类专家等昂贵资源的场景中，训练成本可能极其高昂
  • 可扩展性问题：随着专家数量增加，训练成本线性增长，限制了方法的实用性
  • 资源约束环境：在计算资源受限的环境中，现有方法难以部署

现有方法局限性

  1. 全查询假设：现有方法假设可以无成本地获取所有专家的预测和成本信息
  2. 理论与实践脱节：理论分析忽略了训练阶段的查询成本
  3. 扩展性差：无法有效处理大规模专家集合

核心贡献

  1. 提出预算推迟框架：首次系统性地研究训练期间的专家查询成本控制问题
  2. 双阶段算法设计：
    • 两阶段预算推迟算法（Section 3-5）
    • 单阶段预算推迟算法（Appendix E）
  3. 理论保证：
    • 泛化界限：与标准方法相当的性能保证
    • 标签复杂度：在可实现情况下从 O(T) 降至 Õ(√T)，进一步可达 O(log T)
  4. 实验验证：在多个数据集上实现40%以下的专家查询率，同时保持预测准确性

方法详解

任务定义

两阶段设置：

  • 输入空间：X，标签空间：Y = n
  • 专家集合：{g₁, ..., gₙₑ}，每个专家 gⱼ: X × Y → ℝ
  • 路由函数：r ∈ R，选择专家 r(x) = argmax_k r(x,k)
  • 成本函数：cₖ(x,y)，通常为 0-1 损失

目标：最小化两阶段推迟损失

L_def(r,x,y,c) = Σₖ cₖ(x,y)𝟙_{r(x)=k}

核心算法架构

Algorithm 1: 预算两阶段推迟算法

关键创新：将决策分解为两部分

  1. 专家选择：以概率 qₜ,ₖ 选择专家 k
  2. 查询决策：以概率 pₜ,ₖ 查询选定专家的成本

算法流程：

for t = 1 to T:
    接收 (xₜ, yₜ)
    计算查询概率向量 pₜ ← SAMPLING-PROBS(...)
    选择专家 kₜ ~ q_t
    以概率 pₜ,ₖₜ 查询成本 cₜ,ₖₜ
    更新训练集 Sₜ（带重要性权重 1/(qₜ,ₖₜpₜ,ₖₜ)）
    更新路由函数 rₜ

Algorithm 2: SAMPLING-PROBS 子程序

版本空间维护：

Rₜ₊₁ = {r ∈ Rₜ : Eₜ(r) ≤ E*ₜ + Δₜ}

查询概率计算：

pₜ,ₖ = max_{r,r'∈Rₜ} {ℓ(r,xₜ,k) - ℓ(r',xₜ,k)}

设计理念：优先查询在当前版本空间中分歧最大的专家-实例对

技术创新点

  1. 适应性查询策略：基于假设分歧动态调整查询概率
  2. 重要性加权估计：通过 1/(qₜ,ₖpₜ,ₖ) 权重保证无偏估计
  3. 版本空间剪枝：渐进式消除次优假设，聚焦高不确定性区域
  4. 理论工具扩展：
    • 斜率不对称性（Slope Asymmetry）
    • 假设距离度量
    • 广义分歧系数

理论分析

泛化保证

Theorem 1（两阶段泛化界限）： 以至少 1-δ 的概率，学习到的假设 rₜ 满足：

E(rₜ) - E(r*) ≤ 2Δₜ₋₁

其中 Δₜ = √(q²·8/t·log(2t(t+1)|R|²/δ))，q = 1/q_min + 1

标签复杂度

Theorem 6（标签复杂度界限）： 期望查询次数上界为：

4θ·Kℓ·(E*ₜ + O((1/q_min + 1)√T log(|R|T/δ)))

关键改进：

  • 可实现情况：从 O(neT) 降至 Õ(√T)
  • 使用 Freedman 不等式可进一步达到 O(log T)

实验设置

数据集

使用 10 个基准数据集：

  • 二分类：cod-rna, covtype, HIGGS, phishing, shuttle, skin
  • 多分类：connect, dna, letter, pendigits

专家设置

  • 专家数量：等于类别数 n
  • 专家定义：专家 gₖ 在第 k 类上完全正确，其他类上随机预测
  • 成本函数：0-1 损失 cₖ(x,y) = 𝟙_{gₖ(x)≠y}

评价指标

  • 系统准确率：测试集上 1 - L_def(h,x,y) 的平均值
  • 查询效率：累积专家查询次数 vs. 可用查询次数

实现细节

  • 假设类：逻辑回归模型（L2 正则化）
  • 损失函数：多项式逻辑损失
  • 实验重复：每个数据集 5 次随机划分

实验结果

主要结果

查询效率：

  • 二分类数据集：查询率降至 35-40%
  • 多分类数据集：查询率降至 30% 以下
  • 专家数量效应：专家越多，效率提升越显著（letter数据集26个专家时效果最佳）

准确性保持：

  • 所有数据集上系统准确率与标准方法相当
  • 二分类数据集误差条极小，表明结果稳定
  • 多分类数据集有一定波动，但整体趋势一致

关键发现

  1. 可扩展性验证：随着专家数量增加，预算方法的优势更加明显
  2. 稳定性分析：在线学习过程中的"抖动"是算法随机性的正常表现
  3. 理论验证：实验结果支持理论分析中的关键组件（θ, Kℓ, E*）影响有限

相关工作

学习推迟领域

  • 单阶段方法：Mozannar & Sontag (2020), Verma & Nalisnick (2022)
  • 多阶段方法：Mao et al. (2023a), 一致性保证研究
  • 理论发展：H-一致性界限，Bayes一致性

主动学习

  • IWAL算法：Beygelzimer et al. (2009) 的重要性加权主动学习
  • 区域主动学习：Cortes et al. (2019a,b, 2020)

预算约束学习

  • Reid et al. (2024)：单专家情况下的上下文赌博机方法
  • 局限性：难以扩展到多专家，假设过于严格

结论与讨论

主要结论

  1. 可行性证明：在大幅降低训练成本的同时保持推迟算法性能是可能的
  2. 理论突破：首次为预算推迟问题提供了严格的理论保证
  3. 实用价值：使推迟策略在资源受限环境中更加可行

局限性

  1. 专家设置：实验中的专家设置相对简化，实际应用中专家可能更复杂
  2. 成本函数：主要考虑 0-1 损失，其他成本结构需要进一步验证
  3. 假设类限制：理论分析基于有限假设类，无穷假设类需要覆盖数分析

未来方向

  1. 自适应查询策略：利用训练样本间的结构信息
  2. 动态专家可用性：处理专家动态变化的场景
  3. 强化学习集成：用于序列或交互式决策场景

深度评价

优点

  1. 问题重要性：解决了推迟学习中的一个根本性实际问题
  2. 理论严谨性：提供了完整的理论分析框架，包括泛化界限和标签复杂度
  3. 算法创新：巧妙地将主动学习思想适配到推迟学习场景
  4. 实验充分性：在多个数据集上验证了方法的有效性

不足

  1. 实验设置局限：专家设置相对人工，与实际应用场景可能存在差距
  2. 对比基线单一：主要与标准推迟方法对比，缺少其他预算约束方法的比较
  3. 计算复杂度分析不足：未详细分析算法的计算开销

影响力

  1. 学术贡献：为推迟学习领域开辟了新的研究方向
  2. 实用价值：对涉及昂贵专家的实际应用具有重要意义
  3. 理论价值：扩展了主动学习理论到新的应用场景

适用场景

  1. 大型语言模型推迟：在不同规模的LLM间进行成本敏感的推迟决策
  2. 医疗诊断系统：在不同专科医生间分配诊断任务
  3. 传感器网络：在不同能力的传感器间进行数据收集决策

参考文献

本文引用了推迟学习、主动学习和多臂赌博机等领域的重要文献，特别是：

  • Mao et al. (2023a, 2024a): 多专家推迟的理论基础
  • Beygelzimer et al. (2009): IWAL算法的重要性加权思想
  • Reid et al. (2024): 预算约束推迟的先驱工作

总体评价：这是一篇高质量的机器学习理论论文，解决了推迟学习中的重要实际问题，提供了严谨的理论分析和有说服力的实验验证。论文的主要贡献在于首次系统性地研究了训练阶段的专家查询成本控制，为该领域的实际应用奠定了重要基础。