Learning to Defer in Non-Stationary Time Series via Switching State-Space Models

技術的概要：スイッチング状態空間モデルによる非定常時系列における学習遅延（Learning-to-Defer）

問題定式化
本論文は、ストリーミングかつ非定常な時系列環境における学習遅延（Learning-to-Defer: L2D）の課題に取り組む。すべての専門家の予測へのアクセスを仮定するオフライン L2D 設定や固定された内部予測器を前提とする従来の設定とは異なり、提案される設定は以下の要素を含む：

1. 非対称な部分フィードバック：各ラウンド $t$ において、システムはコンテキスト $x_t$ と利用可能な外部専門家の集合 $E_t$ を観測する。内部で予測する（アクション 0）か、外部専門家 $k \in E_t$ に遅延させるか（クエリコスト $\beta_k$ を発生させる）を選択しなければならない。重要なのは、真の出力 $y_t$ が決定後に明らかにされるため、内部残差（$e_{t,0} = \hat{y}_{t,0} - y_t$）は常に観測可能である点である。一方、外部残差は対応する専門家にクエリを送った場合のみ観測され、そうでない場合は検閲（censored）されたままとなる。
2. アクション結合型学習：内部予測器 $f_{\theta_t}$ はオンラインで訓練される。ルーティング決定は学習者の将来の状態に直接影響を与える。なぜなら、専門家にクエリを送ることは、内部モデルを更新できる追加の「教師」シグナル（$\hat{y}_{t,k}$）を提供するからである。
3. 非定常性と動的な専門性：環境は非定常であり、専門家の品質は潜在レジーム間で変化する。さらに、専門家プールは動的であり、専門家は時間とともに加入、離脱、または復帰する可能性がある。

目的は、即時の予測誤差とクエリコストのバランスを取りながら、内部学習者の改善とレジームシフトへの適応を同時に行い、期待累積ルーティングコストを最小化することである。

手法：L2D-SLDS
著者は、内部予測器とすべての潜在的な外部専門家の残差を、因数分解されたスイッチング線形ガウス状態空間モデル（SLDS）を用いて共同モデル化する、一段階のオンラインフレームワークであるL2D-SLDSを提案する。

• 生成モデル：モデルは、各専門家 $k$ の潜在信頼性を以下の 3 つの構成要素に分解する：

  1. 専門家間の相関を捉え、専門家プール全体に情報を転送する共有グローバル因子 $g_t$。
  2. 専門家固有の信頼性を捉える専門家ごとの固有状態 $u_{t,k}$。
  3. $M$ 個の線形ガウスダイナミクスから選択し、専門家パフォーマンスの構造的変化に適応することを可能にする離散レジーム変数 $z_t$。
     専門家 $k$ の残差は、信頼性ベクトル $\alpha_{t,k} = B_k g_t + u_{t,k}$ の線形ガウス放出としてモデル化される。

• オンライン推論：システムはIMM 風（Interacting Multiple Model）の 2 段階フィルタを採用する：

  1. 内部フェーズ：常に実行される。常に観測される内部残差 $e_{t,0}$ を取り込み、共有因子 $g_t$ とレジーム重みを更新する。これにより、外部専門家にクエリを送らない場合でも、共有因子を介して未クエリの専門家に関する信念を更新できる。
  2. 外部フェーズ：外部専門家にクエリを送った場合のみ実行される。観測された外部残差を取り込み、特定の専門家の状態とグローバル因子をさらに精緻化する。
  3. レジストリ管理：動的レジストリが専門家の誕生と死を処理する。古くなった専門家（$\Delta_{max}$ 期間利用不可能）は正確な周辺化によって剪定され、保持された専門家の予測分布に影響を与えることなく、計算効率とメモリ効率を確保する。

• 学習者認識型ルーティングスコア：ルーティング決定は、3 つの目的をバランスさせるスコア $S_t(k)$ によって駆動される：

  1. 活用（Exploitation）：内部予測器に対して専門家 $k$ にクエリを送る即時の超過コスト。
  2. 探索（情報獲得）：条件付き相互情報量 $I((z_t, g_t); e_{t,k} | e_{t,0})$。これは、内部残差が既に提供するものを超えて、クエリが潜在状態に関する不確実性をどの程度減少させるかを測定する。これは、共有因子に対しては閉形式項で、レジーム同定に対してはモンテカルロ項で近似される。
  3. 学習者の改善：専門家が内部予測器を上回る確率と、その改善の大きさに基づいた、内部学習者への期待 1 ステップ改善の見積もり。

• アクション結合型更新：専門家にクエリを送った場合、内部学習者は教師正則化目的関数を用いて更新される。教師シグナルの重みは適応的であり、専門家の予測信頼性、実現された有用性、および学習者との不一致に基づいて更新をゲートする。

主要な貢献

1. 定式化：非対称部分フィードバック、アクション結合型内部学習、動的な専門家利用可能性、および相談コストを明示的に処理する、非定常時系列に対する一段階オンライン L2D を定式化した。
2. アルゴリズム：検閲下でのスケーラブルな推論と専門家間情報転送を可能にする因数分解型スイッチング線形ガウスモデルである L2D-SLDS を導入した。保持された専門家の周辺分布を保存するレジストリ剪定機構を含む。
3. ルーティング戦略：単純なコスト最小化や純粋な探索を超えて、潜在状態の情報獲得と期待学習者改善を組み合わせた、新しい学習者認識型クエリスコアを提案した。
4. 理論的保証：著者は、時間変化する学習・遅延比較対象に対するオラクル後悔分解を証明した。後悔は、クエリボーナス予算、SLDS 予測コスト誤差項（$E_{SLDS}$）、および内部学習者の区間動的後悔に分解される。特定の条件（部分線形な $E_{SLDS}$ と認証された内部学習者）の下で、実現後悔率の部分線形性を確立した。
5. 実証的性能：合成データおよび実世界ベンチマーク（メルボルン、イェーナ、デリー）における広範な実験により、L2D-SLDS がコンテキストおよび非定常バンディトベースラインを上回り、実データシナリオでは 2% 未満のラウンドで遅延を行うことが示された。

結果

• 合成データ：L2D-SLDS は、最良のバンディトベースライン（0.427）と比較して、最低のルーティングコスト（0.336）を達成した。アブレーション研究により、共有因子 $g_t$ が情報転送に不可欠であることが確認された。これを除去すると性能が低下した。
• 実世界ベンチマーク：
  • メルボルン：L2D-SLDS は 0.8% の遅延率でコスト 5.914 を達成し、すべてのバンディトベースライン（6.047 から 6.302 の範囲で、より高い遅延率を有する）を上回った。
  • イェーナ：L2D-SLDS は 0.22% の遅延率で 3.293 を達成した。注目すべきは、遅延を行わない内部予測器（3.297）を改善した適応型手法はこれだけであり、すべてのバンディトベースラインは遅延を行わないベースラインよりも性能が悪かったことである。
  • デリー（24 人の専門家）：L2D-SLDS は 1.70% の遅延率で 2.528 を達成した。最強力なバンディトベースライン（SharedLinUCB+0）は 2.542 を達成したが、34.8% の遅延率を必要とした。これは、L2D-SLDS が高価値の遅延を選択する際の効率性を浮き彫りにしている。
• アブレーション：共有因子を除去するか、情報指向スコアをトンプソンサンプリングに置き換えると、性能が大幅に低下するかクエリ率が上昇し、モデルおよびスコアリングメカニズムの特定の設計選択が妥当であることを検証した。

意義と主張
本論文は、非対称フィードバック、潜在レジームスイッチ、および動的専門家レジストリの下で、内部学習者と外部専門家へのルーティングをオンラインで共同訓練する最初の研究であると主張する。意義は、非定常環境における専門家のフィードバックの「検閲された」性質を、残差の確率モデルが効果的に処理できることを示し、共有潜在構造を通じて未クエリの専門家について学習することを可能にすることにある。著者は、標準的なバンディトアプローチと比較して劇的に低いクエリ率で競争力のある、あるいは優れた性能を達成しており、遅延が高コストとなる高リスクまたはコスト感受性のアプリケーションに適していると強調している。理論的後悔分解は、探索、予測誤差、および学習者適応のトレードオフを理解するためのモジュール化された枠組みを提供する。