最优确定性多校准与全预测

论文信息

标题: Optimal Deterministic Multicalibration and Omniprediction

作者: Georgy Noarov, Aaron Roth

发布日期: 2026-06-18

arXiv ID: 2606.20557v1

PDF 链接: 下载 PDF

背景与动机：当预测不再是 “碰运气”

在机器学习走向高风险决策领域（如金融授信、医疗诊断、司法判决）的今天，预测模型不仅要求整体准确，更要求对每一个细分子群体都做到无偏——这便是多校准（multicalibration）的核心思想。直观地说，一个模型如果宣称 “明天股市上涨概率是 60%”，那么在所有它给出 60% 预测的情景中，实际上涨的频率应当真的趋近 60%，并且这一性质在按种族、地区、账户类型等任意分组后依然成立。多校准已成为可信机器学习的基本要求之一。

与之紧密相关的概念是全预测（omniprediction）：训练一个单一预测器，只需简单后处理，就能在任意下游损失函数下与专门的基准模型竞争。这意味着一个预测器可以同时服务于回测、选股、风险控制等多种任务，而无需为每种损失函数重新训练。

然而，实现这些强性质通常需要随机预测器——即模型面对同一个输入可能输出不同预测值。随机性虽有助于达到理论限度，却在审计、可复现性、监管合规上带来了巨大麻烦。学术界逐渐形成一个关键问题：随机性是否是达到最优样本效率的必要代价？ 此前，所有已知的最小最大最优多校准算法均输出随机预测器，确定性预测器的样本复杂度要差得多（例如 $O(\varepsilon^{-6})$ 对比随机性的 $O(\varepsilon^{-3})$）。本文彻底解决了这一开放问题，证明确定性预测器同样可以达到最优样本复杂度，并将结论推广到全预测与结果不可区分性。

核心贡献

作者给出了首个确定性多校准算法，其样本复杂度为 $\widetilde{O}(\varepsilon^{-3})$，匹配了随机算法的已知下界。进一步，他们将这一框架推广到任意有限测试族的结果不可区分性（Outcome Indistinguishability, OI），进而得到确定性的全预测器，样本复杂度为 $\widetilde{O}(d/\varepsilon^2)$（其中 $d$ 为审计类复杂度），解决了由 Okoroafor 等人和 Balakrishnan 等人提出的开放问题。

技术精髓：从两原子上例到区间提示

随机性的幻觉：一个两元原子困境

考虑两个上下文 $x_1$ 和 $x_2$，各以概率 $1/2$ 出现，标签分别为 $y=0$ 和 $y=1$。一个随机预测器在 $x_1$ 上以 $2/3$ 概率输出 $1/3$，以 $1/3$ 概率输出 $2/3$；对 $x_2$ 则对称。计算可得，条件预测期望偏差为零，即完全校准。但若试图用任何确定性舍入（每个 $x_i$ 输出单个固定值），期望误差至少为 $1/6$。原因在于：随机性通过混合不同上下文来消除偏差，而一旦固定，这种微妙的混合就被破坏。这一简单示例揭示了去随机化的核心障碍——分布中的原子（atoms）。

最直观的解决思路是：将出现频率高的原子单独估计条件均值，低频原子则直接固定随机性。但计算表明，在目标样本量 $O(\varepsilon^{-3})$ 下，会出现一处 “真空地带”：原子质量既大到不能忽略舍入误差，又小到无法准确估计条件均值。论文的突破在于平滑地融合统计信息：不设置硬阈值，而是通过置信区间来 “提示” 随机预测器的容许输出范围。

区间提示与在线学习

算法将数据分为三份：信心样本（confidence sample）、在线学习样本（online-learning sample）和分区样本（partition sample）。利用信心样本，为每个上下文构建置信区间 $I_x$（覆盖真实的 $\mu(x)$）和容许预测值集合 $\Lambda_x$（$\gamma$-逼近 $I_x$）。上下文出现越频繁，区间就越窄；罕见或未出现的上下文则得到整个 $[0,1]$ 区间。这一设计保证了两点关键性质：

• 有效性：高概率下所有区间均包含真实条件均值。
• 半径预算：$\sum_x p_x^2 r_x^2 \le O(\varepsilon^2/L)$，其中 $r_x$ 是区间半径，$L$ 大致对应测试数量的对数。该不等式反映了频繁上下文对应窄区间，从而控制住了后续舍入时的方差。

接着，在在线学习阶段，采用指数加权算法维护对 “测试-符号” 组合的权重，并在每一轮根据当前上下文和容许集合求解一个线性规划：从 $\Lambda_x$ 中选择一个分布，使最坏情况（区间端点处）的期望校准误差最小。该在线算法保证多校准误差以 $O(\sqrt{L/T})$ 的速率收敛，而预测值始终限制在 $\Lambda_x$ 内。经过在线至批次的转化，得到一个随机预测器 $Q$，其多校准误差为 $O(\varepsilon)$，同时每个上下文的预测支持集都贴近真实条件均值。

原子舍入与词典序分区

确定性预测的最后一跃，是对随机预测器 $Q$ 进行舍入。论文采用 “每个舍入单元格一个随机种子” 的策略。关键是如何定义单元格，使得单元格的平方质量总和可控。对于在信心样本中出现过的原子，单独成格；未观测到的区域则借助分区样本构建：令样本点按词典序排序，相邻点之间的开区间加上样本点自身，构成单元格。利用可交换性论证，可证明未观测区域的 $\sum_{C} P_X(C)^2$ 以高概率被 $O(\varepsilon^2/L)$ 限制。这一界与原子半径预算共同支配了舍入后校准误差的增量。最终，通过为每个单元格独立抽取统一随机种子并应用逆 CDF，将 $Q$ 转化为确定性预测器 $h$，且保持多校准误差不变（仅增加 $O(\varepsilon)$）。

整个过程里，随机性仅用于训练阶段（例如在线权重更新和种子抽取），而预测阶段输出的是一个固定的函数。附录中进一步说明，训练阶段的随机性也可去除，仅带来对数级的样本增加。

从多校准到全预测

多校准的测试可表述为一族有符号测试：$(x,v) \mapsto g(x)\sigma(v)$。论文作者敏锐地指出，他们所用的所有技术都只依赖于这族测试的有限性和有界性，而并未用到其特殊结构。因此，直接将测试族替换为任意有限的结果不可区分性测试 $\mathcal{A}$，整个框架就能生成确定性的 OI 预测器，其误差以 $O(\sqrt{\log|\mathcal{A}|/T})$ 速率下降。全预测恰可通过阈值校准测试与损失衍生类多准确度测试来刻划，因此将 OI 定理实例化后，即可得到样本最优的确定性全预测器。

对理论与实践的影响

本文从理论上澄清了一个重要边界：对于多校准与全预测，随机性并不提供统计优势。这对于强调可审计性、可复现性的应用（如金融风控、医疗 AI）尤为重要——确定性模型不会因投掷不同硬币而对相同个体给出不同结果，从而更易满足公平性和解释性要求。

在实践中，文章提出的算法具有多项式运行时间，搜索和预测均可有效实现。建议从业者在构建公平性敏感的预测系统时，可采用确定性多校准或全预测算法代替随机版本，以在不牺牲准确性的前提下降低随机性带来的合规风险。在量化交易中，校准良好的预测器有助于组合优化和风险管理，而去随机化使得策略回测和实盘执行完全一致，增强了投资者信任。

值得指出的是，算法仍然基于独立同分布假设，且上下文空间被限定在 $[0,1]^d$ 内。对于分布随时间变化或存在非平稳性的在线场景，确定性最优多校准仍是一个开放方向。另外，如何将该方法扩展到高维复杂上下文（如图像、文本）并保持计算可行性，也是未来重要课题。

总结

这项研究为可信预测领域带来了一座里程碑：它一举证明了确定性预测器可以达到多校准与全预测的统计下限，彻底否定了 “随机性不可或缺” 的猜想。通过巧妙融合置信区间、在线博弈与词典序划分，作者给出了一个优雅且高效的解方，为理论和实践同时注入了确定性。正如论文所展示，有时候消除随机性，不是靠简化，而是靠更精细地利用数据中的信息。## 引言与背景

现代机器学习的许多高风险应用——从信用评分到医疗诊断——都要求预测模型不仅整体准确，更重要的是对不同子群体保持无偏性。多校准（multicalibration）正是为此而生：一个预测器给出 “上涨概率 60%” 时，在所有它曾预测 60% 的场景中，实际上涨的频率应当接近 60%，并且这一性质在按任何分组（如地区、行业、账户类型）划分后依然成立。更进一步，全预测（omniprediction）的概念旨在训练一个单一模型，仅需简单的后处理即可在众多下游损失函数上同时逼近最优基准，避免为每个任务重新训练模型。

长期以来，理论最优的算法均输出随机预测器——即对于同一个输入，可能给出不同的预测值。随机性虽然帮助算法达到最小样本复杂度，却带来审计困难、结果不可复现等问题。一个根本性的开放问题是：随机性是否是达到最优样本效率的必要代价？此前，最优多校准算法的样本复杂度为 $\widetilde{O}(\varepsilon^{-3})$，而确定性算法的已知结果则为 $\widetilde{O}(\varepsilon^{-6})$ 甚至更差。这篇由 Noarov 与 Roth 撰写的工作彻底改变了这一局面。

核心贡献

论文证明了确定性预测器可以达到多校准和全预测的极小极大最优样本复杂度。作者给出了一个确定性多校准算法，仅需 $\widetilde{O}(\varepsilon^{-3})$ 个样本即可达到 $\varepsilon$ 误差，匹配了随机算法的下界。进一步，他们将此技术推广到结果不可区分性（Outcome Indistinguishability）和全预测，解决了 Okoroafor 等人（2025）和 Balakrishnan 等人（2026）分别提出的开放问题。

技术方法解析

随机性的幻觉：两原子示例

去随机化的主要障碍是分布中的原子（即具有正概率的特定输入点）。考虑两个上下文 $x_1$ 和 $x_2$，各以 $1/2$ 概率出现，标签分别为 $0$ 和 $1$。一个随机预测器针对 $x_1$ 以 $2/3$ 概率预测 $1/3$、以 $1/3$ 概率预测 $2/3$，对 $x_2$ 则对称。这样，条件于预测值的偏差恰好抵消，实现了零校准误差。然而，任何舍入至单一预测值的确定性做法都会产生至少 $1/6$ 的误差。随机预测器通过混合不同上下文来 “消偏”，而确定性舍入则破坏了这一微妙平衡。

从硬分割到平滑提示

一个自然的想法是：对频率高的原子直接估计条件均值，对低频原子则固定随机性。但计算表明，在目标样本量 $O(\varepsilon^{-3})$ 下存在一个 “真空地带”——原子质量既大到不能忽略舍入方差，又小到无法准确估计其均值。论文的关键创新在于用置信区间算法平滑地融合统计信息。算法将数据分为三份，分别用于构建区间提示、在线学习和构建分区。利用信心样本，算法为每个上下文 $x$ 构造一个置信区间 $I_x$，使其以高概率包含真实条件均值 $\mu(x)$，并划定一个允许预测集 $\Lambda_x$（位于 $I_x$ 附近的网格点）。出现越频繁的原子，区间越窄；罕见或未观察到的上下文则获得整个 $[0,1]$。由此建立了一个关键不变量：

$$\sum_{x} p_x^2 \, r_x^2 \le O\!\left(\frac{\varepsilon^2}{L}\right),$$

其中 $r_x$ 为区间半径，$L$ 为对数测试数量。这保证了后续舍入带来的方差可控。

在线多校准与反随机化

在线学习阶段，算法以指数加权方式在测试空间上运行。每轮看到一个上下文 $x$ 后，求解一个微型线性规划：在 $\Lambda_x$ 内选择一个分布，使得最坏情况下（区间端点）的期望校准误差最小化。该在线算法保证误差以 $\sqrt{L/T}$ 速率收敛，且输出一个随机预测器 $Q$，其预测值始终被约束在 $\Lambda_x$ 内——这便是去随机化的 “安全网”。

最后的舍入步骤中，算法利用分区样本将未观测的上下文空间按词典序切分为有限个单元格。利用可交换性论证，这些单元格的平方质量总和被高概率限制在 $O(\varepsilon^2/L)$ 量级。随后，为每个单元格独立抽取一个随机种子，通过逆 CDF 将 $Q$ 转为确定性函数 $h$。由于原支持集贴近 $\mu(x)$ 且原子半径与单元格质量均已受控，舍入仅造成 $O(\varepsilon)$ 的额外多校准误差。整个过程保证了 $h$ 达到最优样本复杂度。

从多校准到全预测的泛化

多校准的有符号测试族本质上是一类有限的结果不可区分性测试。论文指出，他们整个工具链仅依赖测试族的有限性和有界性。用任意有限结果不可区分性测试族替换后，同一框架即产出确定性的 OI 预测器，其误差以 $O(\sqrt{\log|\mathcal{A}|/T})$ 衰减。全预测恰可分解为阈值校准与损失衍生类的多准确度测试，从而自然覆盖。

实践意义与应用建议

本研究的理论成果对工业级可信机器学习有直接启示。许多金融、医疗领域对模型的可复现性和可审计性要求极高，随机预测器往往难以通过合规审查。论文提供的确定性多校准算法，在保持最优统计性能的同时，可为每个输入输出固定的概率，增强了透明度和用户信任。实践者可考虑在如下场景应用这些原则：

• 量化交易与风险管理：预测资产收益或波动率时，需按市场板块、流动性等级等进行多校准，以确保不同群体间的公平预估。确定性输出使得回测与实盘策略完全一致。
• 人工智能公平性：在信贷审批或简历筛选中，要求预测器对受保护群体校准，本文算法可无随机性地满足该需求。
• 量子计算背景：尽管量子计算自身并非直接应用，但训练过程中可借助量子优化加速在线权重更新，未来或能降低训练时间。

未来方向

目前算法假设上下文空间为 $[0,1]^d$ 且数据独立同分布。在未来，将这一技术拓展到高维复杂结构（如文本、图像）下的可扩展计算，以及非平稳环境下的在线去随机化，将是有价值的方向。此外，如何利用结构化的约束（如因果推断中的不变性）进一步降低样本要求，也值得探索。

总结

Noarov 与 Roth 的这项工作为确定性预测理论树立了一座里程碑。它通过巧妙的置信区间平滑、在线博弈与词典序分区设计，一举消除了随机性在多校准和全预测中看似固有的统计优势。这项工作不仅深刻影响了理论理解，更为实践者提供了一个高可信度、可即刻部署的算法蓝图。