Adaptive Conformal Inference through the Lens of Blackwell Approachability

技術要約：ブラックウェル接近可能性の観点から見た適応的共形推論

問題提起
GibbsとCandès (2021) によって導入された適応的共形推論（Adaptive Conformal Inference; ACI）は、時系列予測などの逐次的または時間依存的な設定においてしばしば破綻する「交換可能性（exchangeability）」の仮定に依存する標準的な共形推論の限界に対処するものである。ACIは、任意のデータ列に対して経験的な被覆率が所望の水準 $1-\alpha$ に収束するように、予測セットを逐次的に構築することを目指している。既存のACI戦略は妥当性（validity）（経験的被覆率 $\geq 1-\alpha$）は保証するものの、一般に効率性（efficiency）（予測区間の平均的な長さ）に関する同時的な理論的保証を欠いている。敵対的な設定においては、追加の仮定なしには非自明な効率性の保証は不可能であるが、交換可能な設定においては、既存の手法はしばしば劣った区間長をもたらす。核心となる課題は、任意のデータ列に対して妥当性を保証しつつ、データの確率的な性質の度合いに応じて効率性を適応させる統一的な戦略を設計することである。

手法
著者らは、ACIをベクトル値の利得を持つ反復的な2人プレイヤー有限ゲームとして再定式化している。

1. 学習者の行動: キャリブレーション集合の順序統計量から導出された有限のグリッド $A$ から、誤被覆レベル $a_t \in A$ を選択する。これにより、予測セット $C_{1-a_t}(x_t)$ が決定される。
2. 相手方の行動: 結果 $y_t$ を選択する。これは、$y_t$ を含む最もタイトな共形集合を表す離散的な行動 $b_t \in B$ にマッピングされる。
3. 利得ベクトル: 学習者は、誤被覆インジケーター（妥当性）と区間長（効率性）をエンコードした利得ベクトル $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$ を受け取る。
4. 接近可能性の枠組み:
   • 目的は、平均利得ベクトル $m_T$ をターゲット集合 $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$ へと導くことである。
   • ターゲット集合は、相手方のプレイを制限する制約 $Q \subseteq \Delta(B)$ に依存する。ここで $Q$ は、相手方の行動が漸近的に従う分布の集合を表す。
   • 機会主義的接近可能性（Opportunistic Approachability）: 著者らは、ブラックウェル接近可能性（Blackwell approachability）とその拡張である機会主義的接近可能性を利用している。この枠組みにより、学習者は相手方のプレイが特定の集合 $Q$ に制限されている場合、学習者が $Q$ を事前に知ることなく、より効率的な小さなターゲット集合へと接近することが可能になる。
5. アルゴリズム (BO-ACI):
   • 提案される戦略であるブラックウェル機会主義的適応的共形推論（BO-ACI）は、補助的なキャリブレーション・フォアキャスター（calibrated forecaster） $F$ を利用する。
   • 各ラウンドにおいて、$F$ は相手方の次の行動 $b_t$ の分布を予測する。
   • 学習者は、予測された分布に対する妥当性の制約を満たしつつ（応答関数 $p^*$ を介して）、期待される長さを最小化する行動 $a_t$ を決定論的に選択する。

主な貢献

1. ゲーム理論的再定式化: 本論文は、ACIをベクトル値の利得を持つ反復有限ゲームとして定式化し、妥当性と効率性をマルチオブジェクティブな接近可能性問題へと明示的に結びつけた新しい定式化を確立した。
2. 統一的戦略 (BO-ACI): 機会主義的接近可能性に基づく戦略を導入することで、任意のデータ列（確率的または敵対的）に対して妥当性を保証しつつ、データの未知の確率的性質に適応する効率性の保証を提供する。
3. 「ベスト・オブ・メニー・ワールズ（多くの世界の最善）」の保証: この戦略は、以下の統一された一連の保証を実現する：
   • 交換可能な設定: 最適な効率性の保証 $L(C_{1-\alpha})$ を回復し、理想的な条件下での標準的な共形予測の性能と一致する。
   • 敵対的な設定: 妥当性は保証するが、自明な効率性の境界（区間長 $2L$）を受け入れる。これは完全な敵対的設定における不可能性の結果と一致する。
   • 中間的な設定: 単一の分布シフトや「ほぼ交換可能」なデータ（例：弱い依存関係を持つ時系列）などのシナリオに対して、意味のある効率性の保証を提供する。ここでは、区間長が非交換性の度合いに応じて適応する。

結果

• 理論的収束: 定理19は、BO-ACI戦略の下で、相手方のプレイを制限する凸集合 $Q$ に対して、平均利得ベクトル $m_T$ がほとんど確実にターゲット集合 $C_{\alpha, Q}$ に収束することを証明している。
• 具体的なシナリオ:
  • 交換可能なデータ: 相手方が一様分布 $q_{unif}$ に制限されている場合、平均区間長は $L(C_{1-\alpha})$ に収束する。
  • 単一の分布シフト: テストスコアがキャリブレーション分布 $S$ とは異なる分布 $V$ に従う場合、戦略は長さ $L(C_{1-a_{S,V}})$ に収束する（ここで $a_{S,V}$ はシフトした分布に対する最適な誤被覆レベルである）。
  • $\epsilon$-交換可能／時系列: 全変動距離（Total Variation）またはコルモゴロフ距離によって測定される交換可能性からの偏差が小さいデータに対して、戦略は最適な交換可能長に近い長さを達成し、偏差が増大するにつれて緩やかに劣化する。
  • 敵対的: 制約がない場合（$Q = \Delta(B)$）、戦略は妥当性を確保するが、自明な境界よりも優れた効率性を保証することはできない。これは、非自明な効率性の保証には $Q$ による制限が必要であることを裏付けている。
• $\epsilon$-キャリブレーション: 結果は $\epsilon$-キャリブレーションされたフォアキャスターを使用する戦略（定理34）にも拡張されており、$\epsilon$ に依存する収束境界を提供している。

意義と主張
本論文は、妥当性と効率性の間の緊張関係を解決する、適応的共形推論のための統一的な理論的枠組みを提供すると主張している。ブラックウェル接近可能性を活用することで、以下の特性を持つ単一のアルゴリズムを設計できることを示している：

1. データの生成メカニズムに関わらず、妥当性を保証する。
2. 効率を最大化するために、データの「確率的な性質の度合い」に自動的に適応する。
3. 極端なケース（交換可能および敵対的）において既知の最適結果を回復しつつ、従来のメソッドでは理論的裏付けが欠けていた中間的な現実的シナリオ（時系列予測など）において、新たな意味のある保証を提供する。

著者らは、この研究を「ベスト・オブ・メニー・ワールズ（多くの世界の最善）」のソリューションとして位置づけており、戦略が特定の $Q$ 制約を認識することなく、もし存在すればそれを活用するため、データの分布に基づいてハイパーパラメータを調整する必要がないことを強調している。また、完全に敵対的な設定の限界を浮き彫りにし、効率性の保証にはデータの構造的な仮定が必要であることを再確認している。