技術要約: ShaplEIG

問題提起

シャプレー値（SV）は、解釈可能な機械学習における原理的な属性量の尺度として機能するが、その正確な計算はしばしば困難である。計算上の負担は2つの要因から生じる。一つは、プレイヤー数 $p$ に対する提携（coalitions）の指数関数的な増加（$2^p$）であり、もう一つは、各提携に対する値関数 $\nu$ の評価コストの高さである。再学習に基づく特徴量の重要度、データの価値評価、ハイパーパラメータの重要度といったアプリケーションでは、値関数の評価にフルモデルの再学習や高コストな推論が含まれることがあり、これが評価予算を厳しく制限している。

カーネルSHAPや回帰ベースのMSR（Regression MSR）といった既存の近似手法は、通常、固定された非適応的なサンプリング分布に依存している。これは、特に低予算のレジームにおいて、過去の観測に基づいて評価すべき提携を適応的に選択することで、近似精度を向上させられるのではないか、という問いを提起する。ベイズ実験計画法（BED）は、期待情報利得（EIG）を用いた逐次的な設計のための枠組みを提供するが、EIGの閉形式の表現の欠如や、高次元離散空間におけるEIG推定の計算上の困難さにより、SV推定への採用は限定的であった。

手法

著者らは、シャプレー値に関する情報利得を最大化するように提携を適応的に選択する、ベイズ実験計画法アプローチであるShaplEIGを提案する。

1. ハミングカーネルを用いたガウス過程サロゲート

ShaplEIGは、値関数 $\nu$ をガウス過程（GP）サロゲートを用いてモデル化する。提携のバイナリ入力空間（インジケーターベクトル $z \in \{0, 1\}^p$ として表現される）を扱うために、本手法はハミング距離カーネルを採用する。このカーネルは、学習可能な長さスケール・ハイパーパラメータ $\xi$ を用いて、重み付きハミング距離に基づき提携間の類似性を定量化する。GPは、観測されたデータセット $D_t$ が与えられた下での、全 $2^p$ 個の提携にわたる値関数上の事後分布を提供する。

2. 線形性による一貫したSV推定

主要な理論的知見は、シャプレー値が値関数に対して線形であることである。SV $\phi$ は、値関数ベクトル $\nu$ の線形変換として表現できる：$\phi = A\nu$。ここで、$A$ はシャプレー公式から導出される既知の行列である。その結果、GPサロゲートの下でのSVの事後分布もまたガウス分布となり、閉形式で利用可能となる：
$$\phi | D_t \sim \mathcal{N}_p(A\mu_{\nu|D_t}, A\Sigma_{\nu|D_t}A^\top)$$
著者らは、事後平均 $\hat{\phi} = A\mu_{\nu|D_t}$ からSVの推定値を抽出する。極めて重要なことに、ノイズレス（または準ノイズレス）なGPにおいて、この推定器は**一貫性（consistent）**を持つ。すなわち、すべての $2^p$ 個の提例が評価されれば、推定値は真のシャプレー値に正確に収束する。

3. 閉形式の期待情報利得（EIG）

本研究の核心的な貢献は、SVに関する候補提携 $z^{(i)}$ のEIGに関する閉形式の表現を導出したことである。逐次的選択を、SVを線形な最終目標とするベイズ線形逆問題として定式化することで、EIGは観測値 $y(x)$ ではなく、事後共分散の $\nu$ にのみ依存することが示される：
$$\text{EIG}^{(t)}_{\phi}(z^{(i)}) \propto -\log \det \left( A \Sigma_{\nu|\nu'(z^{(i)}), D_t} A^\top \right) + C$$
これにより、EIGが実験デザイン（選択された提携）のみに依存し、特定の出力 $y(x)$ に依存しないため、BEDで通常必要とされる入れ子の期待値計算を回避できる。

4. 基本対称多項式による効率的な計算

EIGの直接的な計算は、$2^p \times 2^p$ サイズの行列操作を伴い、指数関数的な複雑さをもたらす。著者らは、ハミングカーネルの乗法的構造を利用することで、計算量を多項式時間（$O(p^4 + t^3)$）に削減する効率的な計算スキームを提案する。

• EIGに必要な項（具体的には $A\Sigma_{\nu|D_t}e_i$ および $A\Sigma_{\nu|D_t}A^\top$）は、カーネル評価の加重和として書き換えられる。
• これらの和は、**スケーリングされた基本対称多項式（ESP）**と同一視される。
• これらの多項式を（動的計画法と接頭辞/接尾辞テーブルを用いて）効率的に計算することで、提携の明示的な列挙を回避する。

5. アルゴリズム

アルゴリズムは貪欲法（greedy）で進行する：

1. 小規模なデザイン（例：レバレッジスコアサンプリング）で初期化する。
2. GPサロゲートを適合させ、ハイパーパラメータを最適化する。
3. 効率的な多項式スキームを用いて、すべての候補提携に対するEIGを計算する。
4. EIGを最大にする提携を選択し、値関数を評価して、データセットを更新する。
5. 予算が尽きるまで繰り返す。

主な貢献

1. ShaplEIGフレームワーク： ハミングカーネルを用いたGPサロゲートを使用し、EIGに基づいて適応的に提携を選択する、SV推定のための新しいBEDベースの手法を導入した。
2. 閉形式のEIG： SVが値関数に対して線形であることを利用し、GPサロゲートの下でEIGが閉形式の表現を持つことを示した。
3. 多項式計算量： 基本対称多項式を用いることで、EIGの計算量をプレイヤー数 $p$ に対して指数関数的から多項式的なものへと削減する、効率的な計算スキームを提案した。
4. 一貫した推定： すべての提携が評価されたときに真の値に収束する、一貫したSV推定器を提供した。これは、追加の調整ステップを必要とする一部のツリーベースのサロゲート手法とは対照的である。

実験結果

著者らは、小規模から中規模のゲーム（$8 \le p \le 101$）を含む多様で高コストなアプリケーションにおいてShaplEIGを評価した：

• タスク： グローバルな特徴量の重要度（TabPFN）、データの価値評価（Random Forest, Gradient Boosting）、ハイパーパラメータの重要度（XGBoost, LCBench）、およびローカルな説明（ResNet, ViT, Random Forest）。
• ベースライン： Kernel SHAP、Leverage SHAP、Permutation Sampling、および最新の回帰MSR（XGBoostと結合したもの）と比較。
• アブレーション解析： 同様のGPサロゲートを使用しているが、異なる選択戦略（Random, Uncertainty Sampling, Leverage Score Sampling）を用いたバリアントとの比較。

知見：

• サンプル効率： ShaplEIGは、ほとんどのタスクにおいて、低予算レジームにおいて一貫して最高の全体的な精度（最小の平均二乗誤差）を達成した。特に、プレイヤー間の相互作用が不均一な非対称ゲームにおいて、競合手法を厳密に圧倒することが多い。
• アブレーションからの洞察： 強力なパフォーマンスは、主にGPサロゲートの使用ではなく、EIGベースの選択戦略に起因している。Uncertainty Sampling（US）はランダムサンプリングよりも性能が低いことが多く、これは周辺分散の最大化が、線形変換されたSVに関する情報の最大化と等価ではないことを強調している。
• スケーラビリティ： より大きなゲーム（$p > 16$）に対しても、ハイパーパラメータの再適合を毎ステップではなくスケジュールに基づいて行うことで、本手法は有効性を維持する。
• 計算コスト： EIGの計算自体は効率的（数秒）であるが、ハイパーパラメータの適合は $p$ が大きい場合（$p \approx 100$ まで）にボトルネックとなる可能性がある。著者らは、ハイパーパラメータの適合に最大25分かかることを指摘しており、ShaplEIGは値関数の評価が真に高コストである場合に最も適切であると述べている。

意義と主張

本論文は、ShaplEIGが高コストなゲームにおけるSV推定のサンプル効率を向上させるための、原理的な枠組みを提供すると主張している。閉形式のEIGを導出し、基本対称多項式を用いた効率的な多項式時間の計算スキームを実現することで、著者らはこの領域におけるベイズ実験計画法の適用における主要な障壁を克服した。

著者らは、本手法が繰り返しのGP最適化による計算オーバーヘッドを伴うことを控えめに述べているが、評価予算が限られている場合に、推定精度の面で大幅な利点が得られるとしている。非常に大規模なゲームや、より低コストな値関数に対しては、このオーバーヘッドが過大になる可能性があることを認めており、手法の適用範囲を広げるためにはさらなる計算上の改善に焦ニ点を当てるべきであるとしている。本研究は、あらゆるシナリオのSV推定を解決することを目的としているのではなく、適応的な選択が極めて重要となる「高コストな値関数」のレジームを明確にターゲットとしている。