技术摘要：顺序预测中的真实性校准度量

问题陈述

本文探讨了在顺序概率预测背景下，**真实性（truthfulness）与完备性（completeness）及稳健性（soundness）**这两类统计保证之间的根本冲突。

• 校准度（Calibration）： 如果对于每一个报告的概率 $p$，事件发生的经验频率近似于 $p$，则称预测器是经过校准的。校准度度量通过为一系列报告和结果分配一个数值误差，来量化失校准程度。
• 设计要求（Desiderata）：
  • 完备性（Completeness）： 如果报告是由一个真正经过校准的分布生成的，那么期望校准误差应随着样本量 $T \to \infty$ 而趋于零。
  • 稳健性（Soundness）： 如果报告是由一个失校准的分布生成的，那么期望误差应在 $T \to \infty$ 时保持远离零。
  • 真实性（Truthfulness）： 如果一个校准度度量满足：无论数据生成分布如何，报告下一个结果的真实条件概率的策略都能使期望校用误差最小化，则称该度量是真实的。

虽然在批处理（batch）设置中（即所有数据同时可用）存在完美的真实校准度度量，但本文研究了在顺序（sequential）设置中（即基于过去的输出逐一进行预测）是否存在这样的度量。Haghtalab 等人 [14] 最近的工作提出了一种在顺序设置下近似真实的度量，这留下了一个悬而未决的问题：精确真实性是否能与完备性和稳健性兼容。

方法论与技术路径

本文采用混合论证（hybrid argument）来建立不可能结果，并使用构造性归约（constructive reductions）来实现近似真实性。

1. 精确真实性的不可能实现

核心的不可能结果依赖于利用问题的顺序特性所进行的混合论证。

• 设定： 作者考虑了两个关于预测-结果对的离线分布：一个校准分布 $D_q$（预测器报告 $q$，且结果的均值为 $q$）和一个失校准分布 $D'_q$（预测器仅在结果为 0 时报告 $q$，而在结果为 1 时报告 1）。
• 混合构造： 他们构造了一个混合分布序列 $H_0, \dots, H_T$，其中 $H_m$ 由前 $m$ 个样本从失校准分布 $D'_q$ 中抽取，剩余的 $T-m$ 个样本从校准分布 $D_q$ 中抽取。
• 逻辑： 由于校准度度量必须能够区分完全失校准的 $H_T$ 和完全校准的 $H_0$（基于稳健性和完备性），因此必然存在一个“切换点” $m$，使得期望误差在 $H_{m-1}$ 和 $H_m$ 之间发生显著变化。
• 偏差： 这种局部差异意味着，在给定特定的（罕见的）输出前缀条件下，策略性预测器可以通过在第 $m$ 步偏离真实的报告，来降低其期望校准误差。具体而言，如果前缀使得历史记录看起来是失校准的，预测器可以通过在未来进行错误报告来“修复”校准，即使底层数据是由乘积分布（独立输出）生成的。
• 核心洞察： 精确真实性要求预测器即使在历史记录看起来严重失校准的罕见情况下，也要报告真实的均值。然而，完备性和稳健性会奖励那些看起来经过校准的历史记录。策略性预测器可以利用这一点，通过在罕见历史上进行错误报告，使历史记录看起来是经过校准的，从而降低期望误差。

2. 定量下界

本文量化了真实报告与策略性报告之间的差距。研究表明，策略性预测器获得的优势是关于 $T$ 指数级微小的（具体而言，与 $(1-q)^{T-1}$ 成正比）。这种微小的优势之所以存在，是因为策略性偏差仅在混合论证所选出的罕见前缀实现中才有效。

3. 近似真实性的归约

意识到精确真实性是不可能的，作者提出了一个两阶段归约过程，旨在从任何满足一致完备性（uniform completeness）（一种确保真实误差被采样误差一致约束的属性）的稳健且完备的基础度量中，构造出近似真实的度量。

• 第一阶段：加性近似（Additive Approximation）。
  作者通过从基础度量中减去一个消失的采样误差阈值 $\tau_T$ 并截断在零，定义了一个新度量：
  $$\text{Cal}^{\text{add}}_T(r, y) = (\text{Err}_T(r, y) - \tau_T)_+$$
  这种构造是加性近似真实的，这意味着真实策略的误差最多比任何策略性策略的误差高出 $\beta_T$，其中 $\beta_T \to 0$。

• 第二阶段：乘性近似（Multiplicative Approximation）。
  为了获得更强的保证，他们在加性度量中加入了一个归一化的平方损失项：
  $$\text{Cal}^{\text{mult}}_T(r, y) = \text{Cal}^{\text{add}}_T(r, y) + \lambda_T \cdot \frac{1}{T} \sum_{t=1}^T (r_t - y_t)^2$$
  平方损失项提供了一个关于期望误差的通用下界（与内在方差相关），从而使得比较可以基于乘性。这产生了一个 $(1 + \eta_T)$-乘性真实的度量，其中 $\eta_T \to 0$。

主要结果

1. 不可能定理： 在顺序预测设置中，不存在能同时满足精确真实、完备和稳健的校准度量序列，即使是在独立（乘积分布）的情况下也是如此。即使对于弱定义的稳健性和完备性，这一结论依然成立。
2. 定量差距： 本文建立了策略性优势的下界，表明该优势随时间跨度 $T$ 指数级减小。这意味着虽然精确真实性是不可能的，但对于较大的 $T$，偏离真实性的动机是微乎其微的。
3. 近似构造：
   • 作者提供了一个通用的归约方法，可以将任何一致完备的基础度量转换为加性近似真实的度量。
   • 他们进一步将其改进为乘性近似真实的度量。
   • 通过将此方法应用于平滑校准误差（smooth calibration error）（一种连续度量），他们构造了一个对于任何 $0 < \varepsilon < 1$，均为 $(1 + \exp(-\frac{1}{2}T^{(1-\varepsilon)/2}))$-乘性真实的度量。这改进了 Haghtalab 等人 [14] 提供的近似保证。
4. 属性保留： 归约步骤保留了基础校准度量的完备性和稳健性。

意义与主张

本文声称解决了关于顺序设置中精确真实性与统计校准保证之间兼容性的基本开放问题。

• 负面结果： 它明确回答了在顺序预测中实现精确真实性是否可能，答案是否定的。这种不兼容性源于顺序设置允许策略性预测器利用罕见的历史实现情况来“修复”表观上的失校准，而这种机制在批处理设置中是无法实现的。
• 正面结果： 它证明了这种不可能实现仅针对精确真实性。通过放宽要求至近似真实性，本文提供了一个通用框架，可以构造出在保持完备性和稳健性等基本统计属性的同时，在逻辑上任意接近真实的度量。
• 改进： 所提出的乘性归约提供了一个比以往工作更强的近似保证，随着 $T$ 的增加，真实策略的表现会无限接近最优策略的表现。

作者指出，Dewasurendra [7, 8] 的独立工作也展示了顺序预测的不可能结果，尽管其对真实性和稳健性的定义略有不同（特别是关于所考虑的数据生成分布的类别）。本文的不可能结果即使在更弱的乘积分布假设下依然成立。