Online Conformal Prediction Beyond Feedback

问题定义：超越反馈的在线符合预测

不确定性量化对于在安全关键型应用中部署机器学习至关重要。在线符合预测（Online Conformal Prediction, OCP）提供了一个具有理论原则的框架，用于生成预测集，即使在非独立同分布（non-i.i.d.）的数据流和黑盒分类器的情况下，也能保证真实标签以用户指定的频率被包含在内。然而，标准的 OCP 方法依赖于一个反馈循环：在发布预测集后，算法接收反馈（即真实的标签或覆盖信号）以调整未来的集合，从而补偿过去的未覆盖情况。

本文针对这种反馈不可用或难以获取的情况进行了研究。在许多安全关键场景中，例如大语言模型（LLM）的潜在探测器（latent probes），算法需要将输入分类为安全类别。如果探测器选择弃权（向人类或更强的系统查询），则标签最终可能变得可用。然而，对于那些探测器做出已部署决策的输入，标签永远不会被观测到。这创造了一个“超越反馈”的场景：学习者必须在输出预测集或查询正确标签之间做出选择，但两者不能兼得。因此，学习者永远无法观测到已部署的预测集是否正确，从而阻碍了现有 OCP 方法中使用的标准补偿机制。

方法论：带查询的在线符合预测 (OCPQ)

作者提出了带查询的在线符合预测（Online Conformal Prediction with Queries, OCPQ），这是一种专为这种超越反馈协议设计的算法。该方法分为两个主要步骤：

1. 归约为部分监测（Partial Monitoring）： 该问题被归约为一个有限的部分监测博弈。博弈的“动作臂”（arms）由一组有限的预测阈值 $M \subset [0, 1]$ 和一个独立的**查询（query）**动作组成。

   • 预测动作： 选择一个阈值 $m \in M$ 会基于黑盒分类器 $C$ 生成一个预测集 $\Gamma_C(x_t, m)$。该动作不产生观测值（空反馈 $\perp$）且没有直接奖励。
   • 查询动作： 选择查询动作会揭示真实标签 $y_t$，但不会产生预测集且收益为零。
   • 奖励结构： 算法定义了一个辅助奖励函数 $R(m, t)$。如果真实标签被预测集覆盖（即 $y_t \in \Gamma_C(x_t, m)$），奖励为 $1 - m(1-\beta)$，其中 $\beta$ 是一个控制覆盖率与效率之间权衡的用户定义参数。如果标签未被覆盖，奖励为 0。查询动作始终产生 0 奖励。这种结构激励学习者在保持覆盖率的同时选择紧凑的阈值（较小的 $m$）。

2. 算法设计： OCPQ 改编了 Cesa-Bianchi, Lugosi, 和 Stoltz (2004) 的标签高效指数加权预报器（label-efficient exponentially weighted forecaster）。

   • 在每一轮 $t$，算法以固定概率 $\epsilon$ 进行一次查询。
   • 如果进行了查询，则观测到真实标签 $y_t$。算法随后使用逆概率加权方案更新所有阈值 $m \in M$ 的累积奖励估计值 $\hat{Z}_{m,t}$，从而有效地重建出如果进行了预测本应获得的奖励。
   • 如果没有进行查询，算法则根据当前的估计值 $\hat{Z}_{m,t}$ 从指数加权分布中采样一个阈值 $m_t$，并输出相应的预测集。此时不会收到任何反馈。

理论结果

本文建立了 OCPQ 在长度为 $T$ 的无知对手（oblivious adversarial）数据流下的有限时界保证：

• 遗憾度（Regret）： 相对于事后最佳固定阈值的期望遗憾度为 $O(T^{2/3})$。具体而言，当 $\epsilon = T^{-1/3}$ 且 $\eta = T^{-2/3}\sqrt{\ln|M|}$ 时，遗憾度被限制在 $T^{2/3}(2\sqrt{\ln|M|} + 1)$ 以内。作者指出，对于此类部分监测博弈，该速率在渐近意义上是最优的。
• 覆盖率（Coverage）： 期望覆盖率 $p_{cover}$ 满足：
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  这保证了随着 $T$ 的增加，覆盖率会趋近于用户定义的设定目标 $\beta$。
• 查询率（Query Rate）： 算法在期望的 $T^{-1/3}$ 比例的轮次中进行标签查询。
• 高概率界限（High-Probability Bounds）： 文中还推导了关于遗憾度和覆盖率的高概率界限，证明了算法性能的方差是受控的，且不会表现出病态行为。

实验结果

通过在现实世界数据集上的实验验证了该方法：

• 分布偏移（Distribution Shift）： OCPQ 在标准基准测试（MNIST, CIFAR-10, CIFAR-100）中进行了测试，其中训练分布与测试分布不同（例如，从 MNIST 到 USPS，或从 MNIST 到 MNIST-C）。结果表明，可以通过参数 $\beta$ 控制覆盖率与效率之间的权衡。经验覆盖率始终超过了理论下界。
• LLM 安全监测： 该方法被应用于使用 WildGuardMix 数据集的 LLM 提示词安全监测，该数据集包含原始提示词和对抗性重写的提示词。尽管基类分类器在对抗性提示词上的准确率显著下降，但 OCPQ 在保持预测集具有信息量的同时，仍能将覆盖率维持在理论界限之上。
• 对比： 与假设具有全反馈的自适应符合推理（Adaptive Conformal Inference, ACI）相比，OCPQ 在使用显著更少信息（仅查询约 5% 的轮次）的情况下，实现了相当的覆盖率-效率前沿。

意义与贡献

作者声称其贡献如下：

1. 新协议： 它将 OCP 形式化为一个“超越反馈”的场景，即在部署的预测永远不会被评估的情况下，这在安全关键型应用中很常见，因为在这种情况下，标签仅在弃权查询时才可用。
2. 算法归约： 它将此问题归约为一个部分监测博弈，并改编了标签高效的对抗学习技术来解决它，具体是通过修改预报器，使查询成为一种替代而非跟随预测的独立动作。
3. 理论保证： 它为该设定下的 OCP 提供了有限时界的期望遗憾度和覆盖率保证，表明仅需 $O(T^{-1/3})$ 次标签查询即可实现有效的确定性量化。
4. 实际有效性： 实验表明，稀疏监督（随机查询）足以在无需获取已部署预测反馈的情况下，在对抗性分布偏移下维持有用的覆盖率和效率权衡。

作者指出，虽然该方法较为保守（经验覆盖率通常高于界限），但这是由于部分监测博弈公式所需的弱假设所致。未来的工作可以探索更不保守的方法或向自适应对手的扩展。