在计算机科学领域，经典算法的严谨确定性与现代机器学习 (ML) 的概率性 (且往往混乱) 本质之间，长期存在着一道鸿沟。

经典的“在线算法”——比如在不知道会去滑几次雪的情况下决定是租滑雪板还是买滑雪板——旨在即使在最坏的情况下也能将成本降至最低。而机器学习则试图根据模式来预测未来。

近年来，一个名为带有预测的算法 (Algorithms with Predictions) 的新领域试图融合这两个世界。其理念很简单: 如果我们对未来有一个提示 (预测) ，我们能否打破最坏情况下的性能瓶颈？通常，答案是肯定的。但有一个问题: 我们在多大程度上信任这个提示?

大多数现有方法要么要求用户设定一个全局的“信任”参数，要么假设预测是一个没有上下文的单点数值。但现代神经网络不仅仅能给我们一个猜测；它们还能告诉我们它们有多自信。

在这篇文章中，我们将深入探讨 Shen 等人 (2025) 发表的论文 “Algorithms with Calibrated Machine Learning Predictions” 。 这项研究提出使用校准 (Calibration) ——一种统计属性，即模型预测的概率与现实世界的频率相匹配——来动态调整算法对 ML 建议的依赖程度。

我们将通过两个经典问题来探索这一机制: 滑雪板租赁问题 (Ski Rental Problem) 和 在线任务调度 (Online Job Scheduling) , 并了解为什么知道模型 有多 不确定与预测本身一样有价值。

核心概念: 什么是校准？

在修正算法之前，我们需要先了解我们的工具。在机器学习中，模型通常被视为输出分数的黑盒。但是 0.8 的分数是否意味着该事件有 80% 的发生概率？并不一定。许多现代深度学习模型往往是“过度自信”的。

如果预测器分配给事件的概率与其实际观察到的频率相匹配，则称该预测器是经过校准 (calibrated) 的。

校准的定义。

如上式所示，如果一个经过校准的预测器 \(f(X)\) 输出一个值 \(v\) (比如 0.7) ，那么目标 \(T(I)\) 的实际期望值确实应该是 \(v\) (即它在 70% 的时间里发生) 。

在现实世界中，完美的校准很少见。我们使用最大校准误差 (Max Calibration Error) 来衡量与完美状态的偏差，它观察的是在所有可能的预测值中，预测概率与实际结果之间的最坏情况下的差异。

最大校准误差方程。

研究人员认为，如果我们把这些经过校准的概率输入到在线算法中，算法就可以针对每个实例决定是信任 ML 的建议，还是回退到安全的、最坏情况下的策略。

案例研究 1: 滑雪板租赁问题

让我们从在线决策的典型问题开始: 滑雪板租赁 。

困境

你打算去滑雪。

  1. 租赁: 每天花费 $1。
  2. 购买: 花费 \(b\) 美元 (一次性费用) 。

问题在于？你不知道你会滑多少天 (\(z\)) 。如果你一直滑下去，买显然更划算。如果你只滑一次，租更划算。“盈亏平衡”点是 \(b\) 天。

如果你确切知道 \(z\)，最优成本 (\(OPT\)) 很简单:

\[ \min(z, b) \]

在不知道 \(z\) 的情况下，最好的确定性策略是租 \(b-1\) 天，然后在第 \(b\) 天买下。这保证了你支付的费用永远不会超过最优成本的两倍 (竞争比为 2) 。

加入经过校准的预测

现在，假设我们有一个 ML 模型。与其仅仅预测“你会滑 10 天”，我们经过校准的预测器输出一个概率 \(v \in [0, 1]\)，代表你会滑 超过 \(b\) 天 (盈亏平衡点) 的可能性。

\[ v \approx P(Z > b) \]

作者提出了 算法 1 (Algorithm 1) , 这是一种根据这个概率 \(v\) 改变策略的方法。

算法 1 逻辑，显示基于预测 v 的租赁策略。

上图中数学公式背后的直觉如下:

  1. 低置信度 (\(v\) 很小) : 如果模型认为你滑雪超过 \(b\) 天的可能性很小，或者概率处于相对于误差 \(\alpha\) 不确定性较高的“模糊”中间地带，算法就会采取安全策略。它实际上会忽略预测，默认为鲁棒策略 (租 \(b\) 天后再买) 。
  2. 高置信度: 如果模型很自信，算法会计算在购买之前需要租赁的具体天数 (\(k_*\)) 。这个计算根据预测 \(v\) 和校准误差 \(\alpha\) 平滑地对你的风险进行插值。

性能分析

为了证明这种方法有效，作者分析了竞争比 (Competitive Ratio, CR) , 它衡量的是算法相对于最优“上帝视角”解决方案的性能差多少。

预期竞争比方程。

该分析根据预测 \(v\) 和实际滑雪天数 \(z\) 将问题分解为不同的场景。下表总结了不同结果下的成本比率:

表 1 显示了不同场景下的目标值。

  • 行 (ii): 如果算法决定提前购买 (\(k(v) < z\)) ，但滑雪行程在那之后不久就结束了 (\(z \le b\)) ，算法就浪费了买滑雪板的钱。
  • 行 (iv): 如果算法等待太久才买 (\(z > k(v)\)) ，而滑雪还在继续 (\(z > b\)) ，算法就浪费了租赁费。

通过使用校准概率最小化这些比率的期望值，作者推导出了一个强有力的性能界限:

定理 3.3 关于预期竞争比的界限。

这个不等式告诉我们，算法的性能与模型的确定性 (\(v\)) 及其校准误差 (\(\alpha\)) 紧密相关。当模型完美校准 (\(\alpha=0\)) 且非常自信 (\(v\) 接近 0 或 1) 时，性能接近最优 (竞争比 \(\approx 1\)) 。

为什么不使用共形预测？

处理不确定性的另一种流行方法是共形预测 (Conformal Prediction) , 它输出一个区间 (例如，“滑雪天数将在 [5, 20] 之间”) ，并带有保证 (例如，“90% 的情况下，真实值在这个区间内”) 。

作者指出了共形预测在这个特定问题上的一个致命缺陷。如果数据具有高方差，共形区间可能会变得巨大——例如 \([0, \infty]\)。一个说“你会滑 0 到无穷多天”的区间提供不了任何可操作的信息。

相比之下，经过校准的预测器可能会说: “你有 60% 的几率滑雪超过 \(b\) 天。”即使 60% 不是确定的，它也是一个具体的概率权重，算法 1 可以利用数学方法利用这个权重来增加胜算。

案例研究 2: 在线任务调度

第二个应用是任务调度 , 具体的动机来自医疗分诊 (例如，处理诊断图像) 。

设定

  • 我们有 \(n\) 个任务 (病人/图像) 。
  • 每个任务都有优先级: 高 (\(y=1\)) 或低 (\(y=0\)) 。
  • 我们要优先处理高优先级的任务，以最小化“加权完成时间”。
  • 问题: 我们在处理完任务之后才知道优先级。

我们依靠 ML 模型来预测优先级。

二元分类的问题

以前的方法使用二元分类器: 预测任务是高还是低。

  • 如果模型预测“高”，把它放在前面。
  • 如果模型预测“低”，把它放在后面。

这这就产生了“桶 (buckets) ”。所有被预测为“高”的任务都被同等对待。但是，如果一个任务有 99% 的概率是高优先级，而另一个只有 51% 的概率呢？二元分类器对它们一视同仁，导致桶内的排序是随机的。

校准解决方案

作者提出使用原始的、经过校准的概率对任务进行排序。这创建了一个更细粒度的序列。

请看下面的 图 1 。 它直观地展示了粗略预测器 (像只是在阈值 \(\beta\) 处分割的二元分类器) 与细粒度校准预测器之间的区别。

任务排序比较: 细粒度与粗粒度。

  • 底部 (粗粒度) : 预测器将工作分成两组。组内顺序是随机的。
  • 顶部 (细粒度) : 预测器根据每个任务独特的概率对其进行排名。这大大降低了“逆序” (在处理高优先级任务之前先处理低优先级任务) 的几率。

理论胜利

作者使用“逆序”来量化错误排序任务的成本。当低优先级任务在高优先级任务之前被处理时，就会发生逆序。

理论分析证明，随着预测器变得更加精细，逆序的预期数量会显著下降。

定理 4.3 关于逆序的界限。

虽然上图中的数学公式很密集，但重点在于 \(\kappa_1\) 和 \(\kappa_2\) 项。这些代表预测器的方差。二元预测器在其桶内的方差为零 (它认为桶内的所有东西都是一样的) 。经过校准的预测器利用实例之间的方差，将可能的高优先级任务推到最前面。

实验: 它在现实生活中有效吗？

研究人员在两个真实世界的数据集上测试了他们的理论。

1. Citi Bike (滑雪板租赁)

他们使用了纽约市的 Citi Bike 数据。

  • 租赁: 按分钟付费。
  • 购买: 购买一日通票。
  • 目标: 根据用户特征 (开始时间、位置等) 决定是否购买一日通票。

他们将他们的 经过校准 (Calibrated) 方法与标准的 盈亏平衡 (Breakeven) 算法 (确定性) 、二元 (Binary) 预测器方法和 共形 (Conformal) 预测方法进行了比较。

图表比较 Citi Bike 算法。

图 2 (上图) 显示了算法成本与最优成本的比率 (越低越好) 。

  • 红线 (校准) 始终紧贴图表底部。
  • 共形方法 (蓝色) 在盈亏平衡点变高 (意味着决策风险更大) 时表现挣扎，可能是因为预测区间变得太宽而无法使用。

有趣的是，有效性取决于数据特征的质量。当模型拥有“丰富信息 (Rich Info) ” (目的地的精确 GPS 坐标) 时，经过校准的模型表现得更加出色。

具有丰富特征的 XGBoost 性能。

如 图 6 (上图) 所示，特别是在具有“丰富信息”的面板 (c) 中，校准方法 (红色) 相比盈亏平衡策略 (绿色) 保持了巨大的领先优势。

2. 败血症分诊 (调度)

他们利用医院数据集来预测败血症 (一种危及生命的感染反应) 。目标是根据风险“安排”病人接受治疗。

  • 指标: 总加权延迟 (成本) 。
  • 比较: 标准二元分类器 vs. 经过校准的概率排名。

败血症分诊结果显示成本降低。

图 3 (上图) 展示了结果。Y 轴是成本 (归一化遗憾值) 。

  • 实线 (校准) 始终低于 虚线 (二元) 。
  • 这证实了理论: 将预测视为细粒度的概率而不是二元的桶，可以实现更好的排序，并减少危重病人的危险延误。

结论

论文 “Algorithms with Calibrated Machine Learning Predictions” 架起了理论计算机科学与实用机器学习之间的一座重要桥梁。

多年来，算法设计者要么将 ML 预测视为完美的预言机，要么视为不可信的噪声。这项工作提出了一条中间道路: 听取模型的意见，但也听取它的不确定性。

通过使用 校准 , 我们可以:

  1. 插值风险: 在滑雪板租赁中，我们不只是“租”或“买”；我们租赁的时长与我们的信心精确匹配。
  2. 改进排名: 在调度中，我们不再将紧急任务视为铁板一块，而是优先处理 最 可能的情况。

对于学生和从业者来说，结论很明确: 在构建学习增强系统时，不要只看准确率。还要看校准。一个知道自己何时“不知道”的模型，是实现鲁棒决策的强大工具。