Online Conformal Prediction Beyond Feedback

問題定式化：フィードバックを超えたオンライン・コンフォーマル予測

不確実性の定量化は、安全性が極めて重要なアプリケーションに機械学習を導入する上で不可欠です。オンライン・コンフォーマル予測（OCP）は、非i.i.d.なデータストリームやブラックボックス分類器に対しても、ユーザーが指定した頻度で真のラベルが含まれることを保証する予測集合を生成するための、理論的に確立された枠組みを提供します。しかし、標準的なOCP手法はフィードバックループに依存しています。すなわち、予測集合を発行した後、アルゴリズムは過去の未カバーを補償するために、将来の集合を調整するためのフィードバック（真のラベルまたはカバー率に関する信号）を受け取ります。

本論文は、このようなフィードバックが利用できない、あるいは禁止されている設定に対処します。LLM（大規模言語モデル）の潜在的なプローブ（探針）のような、多くの安全性が重要なシナリオでは、アルゴリズムは入力を安全性カテゴリに分類する必要があります。もしプローブが棄権（人間またはより強力なシステムに問い合わせる）した場合、ラベルは最終的に利用可能になるかもしれません。しかし、プローブが展開された決定を下した入力については、ラベルは決して観測されません。これは「フィードバックを超えた」シナリオを生み出します。学習者は、予測集合を出力するか、正しいラベルを問い合わせるかの選択を迫られますが、その両方を同時に行うことはできません。その結果、学習者は展開された予測集合が正しかったかどうかを観察できず、既存のOCP手法で使用されている標準的な補償メカニズムが機能しなくなります。

手法：クエリを伴うOCP (OCPQ)

著者らは、この「フィードバックを超えた」プロトコル向けに設計された手法である、**クエリを伴うオンライン・コンフォーマル予測（OCPQ）**を提案しています。このアプローチは、主に以下の2つのステップで進行します。

1. 部分的モニタリングへの還元: この問題は、有限の部分的モニタリングゲームへと還元されます。このゲームの「腕（アーム）」は、有限の予測閾値集合 $M \subset [0, 1]$ と、独立したクエリアクションで構成されます。

   • 予測アクション: 閾値 $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の報酬をもたらします。この構造は、学習者がカバー率を維持しつつ、タイトな（小さい）閾値を選択するように動機付けます。

2. アルゴリズム設計: OCPQは、Cesa-Bianchi, Lugosi, and Stoltz (2004) によるラベル効率的な指数加重フォアキャスターを適応させたものです。

   • 各ラウンド $t$ において、アルゴリズムは固定確率 $\epsilon$ でクエリを実行します。
   • クエリが行われた場合、真のラベル $y_t$ が観測されます。アルゴリズムはその後、逆確率重み付けスキームを用いて、すべての 閾値 $m \in M$ に対する累積報酬推定値 $\hat{Z}_{m,t}$ を更新します。これは、もし予測が行われていた場合に得られたであろう報酬を事実上再構築するプロセスです。
   • クエリが行われなかった場合、アルゴリズムは現在の推定値 $\hat{Z}_{m,t}$ に基づく指数加重分布から閾値 $m_t$ をサンプリングし、対応する予測集合を出力します。このとき、フィードバックは受け取りません。

理論的結果

本論文は、長さ $T$ の無知な敵対的データストリームの下でのOCPQに関する有限期間の保証を確立しています。

• 後悔（Regret）: 事後的に最適な固定閾値に対する期待後悔は $O(T^{2/3})$ です。具体的には、$\epsilon = T^{-1/3}$ および $\eta = T^{-2/3}\sqrt{\ln|M|}$ のとき、後悔は $T^{2/3}(2\sqrt{\ln|M|} + 1)$ によって抑えられます。著者らは、このレートがこの種の部分的モニタリングゲームにおいて漸近的に最適であると述べています。
• カバー率: 期待カバー率 $p_{cover}$ は次を満たします：
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  これにより、カバー率が $T$ の増加とともにユーザー定義のターゲット $\beta$ に近づくことが保証されます。
• クエリ率: アルゴリズムは、期待される $T^{-1/3}$ の割合のラウンドでのみラベルをクエリします。
• 高確率境界: 本論文は、後悔とカバー率の両方について高確率境界も導出し、アルゴリズムの性能の分散が制御されており、病的な挙動を示さないことを証明しています。

実験結果

提案手法を検証するために、実世界のデータセットを用いた実験が行われました。

• 分布シフト: OCPQは、訓練分布がテスト分布と異なる（例：MNISTからUSPS、またはMNISTからMNIST-C）標準的なベンチマーク（MNIST, CIF-10, CIF-100）でテストされました。結果は、パラメータ $\beta$ を通じてカバー率と効率性のトレードオフを制御できることを示しました。経験的なカバー率は、理論的な下限を一貫して上回りました。
• LLM安全性モニタリング: 本手法は、バニラおよび敵対的に書き換えられたプロンプトを含むWildGuardMixデータセットを用い、LLMプロンプトの安全性モニタリングに適用されました。ベースとなる分類器の精度は敵対的なプロンプトに対して大幅に低下しましたが、OCPQは予測集合を情報量の多い状態に保ちつつ、理論的境界を上回るカバー率を維持しました。
• 比較: フルフィードバックを想定するAdaptive Conformal Inference (ACI) と比較して、OCPQは、はるかに少ない情報（わずか約5%のラウンドをクエリするのみ）を使用しながらも、同等のカバー率・効率性のフロンティアを達成しました。

意義と貢献

本論文は、以下の貢献を主張しています。

1. 新しいプロトコル: 展開された予測が決して評価されない（ラベルは棄権されたクエリに対してのみ利用可能である）という、「フィードバックを超えた」設定におけるOCを定式化しました。これは、安全性が重要なアプリケーションにおいて一般的なシナリオです。
2. アルゴリズム的還元: この問題を部分的モニタリングゲームへと還元し、ラベル効率的な敵対的学習技術を適応させました。具体的には、クエリを予測に続くものではなく、予測に代わる独立したアクションとして扱うようにフォアキャスターを修正しました。
3. 理論的保証: この設定におけるOCの有限期間の期待後悔およびカバー率の保証を提供し、$O(T^{-1/3})$ のラベルクエリのみで有効な不確実性定量化が可能であることを示しました。
4. 実用的な有効性: 希薄な監督（ランダムなクエリ）であっても、展開された予測からのフィードバックを必要とせずに、有用なカバー率と効率性のトレードオフを維持するのに十分であることを、実験を通じて示しました。

著者らは、本手法は保守的である（経験的なカバー率がしばしば境界を上回る）と述べていますが、これは部分的モニタリングゲームの定式化に求められる弱い仮定の結果であるとしています。今後の課題としては、より保守的でない手法や、適応的な敵対者への拡張が挙げられます。