技術要約：線形説明器を用いた条件付きShapley値の高速な近似推定

問題提起

本論文は、共変量が依存関係にある場合の線形回帰モデルにおける、条件付きShapley値（conditional Shapley values）の推定に伴う計算上のボトルネックに対処するものである。Shapley値は、特定の予測に対する特徴量の寄与をゲーム理論的に分解するものであるが、条件付きShapley値を計算するには、あらゆる可能な特徴量の部分集合（連合）に対する期待モデル出力を推定する必要がある。

$p$ 個の予測変数を持つモデルには、$2^p$ 個の可能な連合が存在する。R言語の shapr パッケージにおける Sequential（逐次型）および Iterative（反復型）といった既存の手法は、以下の大きな課題に直面している：

1. Sequential Estimation（逐次推定）: $2^p$ 個の個別の回帰モデルを適合させる必要があり、これは $p$ が増加するにつれて計算量的に実行不可能になる。
2. Iterative Estimation（反復推定）: 収束基準を満たすまで連合をサンプリングする。少数の連合で十分な場合は高速であるが、困難なケースでは収束するために全 $2^p$ 個のうちかなりの割合の連合を必要とすることがあり、逐次法と同様に数時間に及ぶ長い実行時間につながる。
3. 特徴量の依存性: 周辺Shapley値とは異なり、条件付きShapley値は共変量間の依存構造を考慮する必要があるため、複雑な条件付き期待値の計算を必要とする。

著者らは、これらすべての $2^p$ 個のサブモデルの係数を、数学的構造の疎性を活用して、同時にかつ迅速に推定できる手法の開発を目指している。

手法

提案されたアプローチは、制約付きガウス・マルコフ・ランダム場（GMRF） 理論と疎行列代数を利用して、すべてのサブモデルの回帰係数を逐次的ではなく共同で推定する。著者らは、3つの異なるアルゴリズムを導出している。

1. 対角補正法（Diagonal Correction Method - 近似法）

この手法は、フルモデルの精度行列（$Q = X^T X$）を修正することで、制約付き回帰を近似する。

• メカニズム: 特定の係数をゼロにする（すなわち、その特徴量がサブモデルから除外される）という制約を課すために、精度行列の対応する対角要素に大きなスカラー値 $\kappa$ を加える。
• 理論的根拠: ウッドベリーの行列恒等式に基づき、$\kappa A^T A$（ここで $A$ は制約行列）を $Q$ に加えることで、$\kappa \to \infty$ のとき、条件付き共分散行列を近似する。
• 実装: 全 $2^p$ モデルのための結合制約行列 $A$ を構築する。この手法は、線形システム $(Q_F + \kappa A^T A)^{-1}m$ を解く。ここで $Q_F$ は、フルモデルの精度行列を $2^p$ 回繰り返したブロック対角行列である。
• チューニング: チューニングパラメータ $\kappa$ が必要であり、元の精度行列の最大固有値の $10^5$ 倍にすることが推奨される。

2. 投影法（Projection Method - 近似法）

この手法は、パラメータ空間を投影して制約付きパラメータを除去する。

• メカニズム: 投影行列 $Z = I - A^T A$ を精度行列に適用する。制約付きモデルは、内在的なGMRFとして扱われる。数値的安定性（正定値性）を確保するため、投影された精度行列の対角成分に小さなスカラー $\epsilon$ を加える（$Z Q Z + \epsilon I$）。
• 理論的根拠: $\epsilon \to 0^+$ のとき、解は正確な制約付き推定値に収束する。
• 実装: システム $Z(Z Q_F Z + \epsilon I)^{-1} Z m$ を解く。
• チューニング: 小さなチューニングパラメータ $\epsilon$（例：$10^{-5}$）が必要であり、これは $Q$ の最小固有 relatively よりも小さく、かつ安定したCholesky分解が可能である程度に大きく設定される。

3. 正確な変換法（Exact Transformation Method - 正確解）

この手法は、近似誤差やチューニングパラメータなしで、正確な解を提供する。

• メカニズム: パラメータをゼロに強制するのではなく、問題自体を、非ゼロのパラメータのみを含む低次元の空間へと変換する。
• 実装: アクティブなパラメータのみを選択するためのマッピング行列 $E$ を構築する。システムは $(E Q_F E^T)^{-1} E m$ として解かれる。
• 利点: 大きなペナルティ項（$\kappa$）や小さな正則化項（$\epsilon$）を用いる必要がなく、数値的不安定性や近似バイアスの原因を排除できる。

これら3つの手法はすべて、多数のモデルを効率的に共同推定するために、疎行列代数（具体的にはCholesky分解）を利用している。結合精度行列は、各モデルが独立しているため（ブロック対角構造）、非常に疎である。また、非対角成分のゼロは条件付き独立性を示している。

主な貢献

1. 3つの新しいアルゴリズム: 線形回帰におけるすべてのサブモデルの共同推定のための、2つの近似手法（対角補正法、投影法）と1つの正確な手法（正確な変換法）を導入した。
2. 収束の証明: 近似手法が、それぞれのチューニングパラメータ（$\kappa \to \infty$ および $\epsilon \to 0^+$）に従って真の条件付き推定値に収束することを実証する数学的証明を提供した。
3. 計算効率: 疎性と共同推定を活用することで、計算時間を（shapr のような）数時間から、秒単位または分単位へと短縮した。これは、$2^p$ 個のすべての連合を列挙する場合でも同様である。
4. 実証的検証: 3つのデータセット（Adult Income、シミュレーションされたガウス・データセット、WHO Life Expectancy データセット）を用いて、新手法を shapr パッケージ（Sequential および Iterative バージョン）と比較する広範な数値研究を行った。

結果

数値的なケーススタディから、以下の知見が得られた。

• 精度: 新手法によって生成されたShapley値の推定値は、完全な列挙のためのグラウンドトゥルースとして使用された shapr のSequential法と事実上同一であった。
  • Adultデータセット ($p=11$) では、新手法とSequential法との中央絶対誤差（MedAE）は $10^{-9}$ のオーダーであった。
  • シミュレーション・データセット ($p=21$) では、MedAEは $10^{-7}$ から $10^{-5}$ のオーダーであった。
  • WHOデータセット ($p=16$) では、MedAEは $10^{-6}$ のオーダーであった。
• 速度:
  • Adultデータセット: 新手法は 2.5〜9秒 で動作したが、shapr（Sequential および Iterative）は 17〜19分 を要した。
  • シミュレーション・データセット: 新手法は、約210万個（$2^{21} \approx 2.1$ million）のモデルをすべて推定するのに 1.4〜2.5分 かかった。shapr のIterative法は（6.48秒と）より早かったが、これは全集合ではなく200個の連合のみを推定した結果である。
  • WHOデータセット: 新手法は 1.1〜1.2分 かかった。shapr のSequential法は 131分（2.2時間）、Iterative法は並列実行で 16分、逐次実行で 36分 を要した。
• スケーラビリティ: 本手法は、シミュレーション研究において200万を超えるサブモデルを数分以内に推定することに成功した。特定された主な制限は、標準的なハードウェアにおいて $p$ が約21を超える場合のメモリ制約（次元の呪い）であるが、著者らはこれはより多くのRAMや特化した疎行列パッケージによって緩和可能であると述べている。

重要性と主張

本論文は、提案された手法が、精度を損なうことなく、条件付きShapley値の推定における計算効率を大幅に向上させることを主張している。

• 完全列挙における優位性: shapr のIterative法が収束のために大量の連合を必要とする場合（AdultおよびWHOデータセットで見られたケース）、新手法は「同等またはより高い精度」を維持しながら、「大幅に高速」である。
• 包括的な列挙: サンプリングによって連合を抽出する反復的アプローチとは異なり、新手法はすべての $2^p$ 個のサブモデルの完全な列挙を提供するため、サンプリング誤差による情報の損失がない。
• 推奨事項: 著者らは実用的な使用において Exact Transformation Method（正確な変換法） を推奨している。3つの手法はいずれも同等の結果をもたらすが、Exact法はチューニングパラメータを必要としないため、ハイパーパラメータ選択の必要性や近似誤差の要因を排除できる。
• 将来の可能性: 著者らは、この手法をスプライン（例：rms パッケージの）にも拡張可能であること、および並列化（例：OpenMP）によって実行時間をさらに短縮できることを示唆している。ただし、現在の実装は、並列化された shapr パッケージとの公平な比較のために、逐次実行に依存している。

結論として、これらの手法は、従来は計算量的に不可能であったシナリオにおいても、混合型の共変量を持つ線形モデルに対する条件付きShapley値の正確な計算を可能にするものである。