Online Learning-to-Defer with Varying Experts

問題定式化
学習による遅延（Learning-to-Defer: L2D）は、予測モデルと外部の専門家（人間または自動化されたもの）を統合し、不確実性が高いまたはリスクの高い入力をより有能なエージェントへルーティングすることで、システムの信頼性を高めるように設計されたフレームワークです。既存の L2D 研究は主に、固定された専門家プールと完全な教師あり学習（訓練中にすべての専門家の予測を観測する）を用いたバッチ設定で動作していますが、実世界の展開では重大な課題に直面します：データは逐次到来し、専門家の利用可能性は（シフトやリソース制約などにより）変動し、専門家の信頼性は時間とともにドリフトする可能性があります。さらに、実用的なシステムはしばしばバンディットフィードバック下で動作し、学習者は真の正解や利用可能なすべての専門家のパフォーマンスではなく、選択した行動（予測または特定の専門家への問い合わせ）の結果のみを観測します。本論文は、古典的な L2D の仮定とこれらの動的かつオンラインな現実との間のギャップに対処し、バンディットフィードバックと動的に変化する専門家プールを備えた多クラス分類のための初のオンライン L2D フレームワークを導入します。

手法
著者は、各ラウンド $t$ で、特徴ベクトル $x_t$ と利用可能な専門家の集合 $A_t$ からなる拡張入力 $(x_t, A_t)$ が提示される一般的なフレームワークを提案します。学習者は、クラスラベルを予測するか、$A_t$ に含まれる利用可能な専門家のいずれかに遅延するかを決定しなければなりません。この相互作用は半敵対的設定に従います：入力は敵対的に選択される可能性がありますが、ラベルは入力に条件付けられた固定（ただし未知）の分布から引き出されます。

核心的な手法上の貢献は以下の通りです：

1. 真の遅延損失と代理関数：著者は、誤分類コストと専門家問い合わせコストを考慮する真の遅延損失 $\ell_{def}$ を定義します。この損失は微分不可能であるため、制約付きヒンジ損失などの標準的なスコアベースの代理関数を、オンラインかつ変動する専門家設定に拡張する凸代理損失 $\Phi_{def}$ を導入します。この代理関数は、利用できない専門家のスコアの影響を受けないように設計されています。
2. オンライン学習のための H-整合性境界：重要な理論的ステップは、バッチ学習からオンライン設定への $H$-整合性境界の拡張です。著者は、基礎となる代理関数がゼロワン損失に関して $H$-整合性境界を持つ場合、オンラインフレームワークにおける代理遅延後悔の最小化が、真の遅延後悔の有界性を保証することを証明します。
3. アルゴリズム設計：提案されたアルゴリズム（アルゴリズム 1）は、射影勾配を用いたオンライン勾配降下（OGD）を利用します。利用可能なラベルのスコアの和がゼロでなければならないという制約（制約付きヒンジ損失に必要）を処理するために、アルゴリズムは重み行列を、現在の利用可能な専門家セットに固有の実行可能部分空間 $K_{A_t}$ へ射影します。この射影は、利用可能なラベルセットに対する仮説の予測を保持します。アルゴリズムはバンディットフィードバックを処理するために探索率 $\gamma_t$ を組み込み、サンプリングされた行動の観測結果に基づいて損失関数を推定します。

主要な貢献
本論文は、4 つの主要な貢献を主張します：

1. 初のオンライン L2D フレームワーク：データ分布と専門家のプールの両方が時間とともに変化する、バンディットフィードバック下でのオンライン学習による遅延のための初のフレームワークを導入します。
2. 理論的拡張：$H$-整合性境界の概念をオンライン設定に拡張します。この性質は以前、バッチ学習分析に限定されていました。
3. 後悔保証：提案されたアルゴリズムは、一般ケースにおいて $O((n + n_e)T^{2/3})$ の後悔境界を達成します。ここで、$n$ はクラス数、$n_e$ は観測された異なる専門家の数です。低ノイズ（ほぼ実現可能）の仮定の下では、これは $O((n + n_e)\sqrt{T})$ に改善されます。
4. 実証的検証：このアプローチは、合成データと実世界データセット（Reuters4 および CIFAR10H）の両方で検証され、変動する専門家の利用可能性とドリフトする専門性への適応能力を実証しました。

結果
実験は、複雑さが増す 3 つのレジーム下で行われました：(1) 固定された利用可能性と専門性、(2) 変動する利用可能性と固定された専門性、(3) 変動する利用可能性と変動する専門性の両方を備えた完全な動的設定。

• 合成データ：アルゴリズムは、予測と遅延の間の最適な境界を成功裡に学習し、入力を常に最も有能な利用可能な専門家へルーティングしました。専門家の有能領域が時間とともにシフトしても、低い遅延損失と高い精度を維持しました。
• 実世界データ（Reuters4）：最も困難な設定（変動する利用可能性と専門性）において、この手法は移動する専門家の有能領域を効果的に追跡しました。現在有能な専門家への遅延を高い頻度で行い、安定した較正を維持しつつ、固定された専門性を基準としたベースラインと同等のタスク精度を達成しました。
• CIFAR10H：WideResNet 予測器と人間による注釈付き専門家を用いて、この手法は均一にランダムに遅延する信頼性ベースのベースラインを上回りました。学習された方策は、低い遅延損失と高い精度を達成し、無差別に遅延するのではなく、例を最も適切な専門家へルーティングすることを学習したことを示しています。

重要性
本論文は、学習による遅延システムを実世界の非定常環境で実用的にするための基礎的なステップとして位置づけています。固定された専門家プールと完全な教師あり学習という仮定を超えて進むことで、著者は、一貫した代理関数ベースの手法を、敵対的環境や変動する専門家の信頼性に対して堅牢にできることを実証しています。オンライン設定における $H$-整合性の理論的確立は、代理損失の最小化が真の遅延後悔の最小化につながることを厳密に保証し、理論的な L2D の保証と、ストリーミングデータおよび動的専門家システムの実用的な要件との間の重要なギャップを埋めます。