技術的サマリー：QuadraSHAP

問題定義

シャプレイ値は、協調ゲーム理論に基づく特徴量帰属を提供し、機械学習の予測を説明するための基礎的なツールである。しかし、正確な計算は一般的に非現実的であり、指数関数的に多い特徴量の連合（$2^{d-1}$）の評価を必要とする。モデル固有の手法（例：TreeSHAP、RKHS-SHAP）は構造的性質を利用して多項式時間での計算を実現するが、数値的安定性と計算効率の間の持続的なトレードオフに直面することが多い。

具体的には、多項式補間に基づく手法（Linear TreeSHAP など）は、Vandermonde 行列の逆行列の条件悪化により、多項式の次数（木の高さや特徴量数によって支配される）が増加するにつれて急速に数値的不安定に陥る。一方、代数的再帰手法（積カーネルモデルなど）は安定性を提供するが、実質的に高い算術コストを伴う。本論文は、乗法的構造を示す広範なモデルクラスに対して、同時に正確（または準正確）、数値的に安定、かつ計算効率的な手法の必要性に対処する。

手法

本論文は、積ゲーム（連合の価値がプレイヤーごとの項の積として因数分解される協調ゲーム、$v(S) = \prod_{j \in S} u_j$）に対するシャプレイ値を計算する手法QuadraSHAPを導入する。この構造は、木ベースのモデルや積カーネルを有するカーネル手法において自然に生じる。

1. 積分表現

核心的な理論的貢献は、$2^{d-1}$個の部分集合にわたる重み付き和から、シャプレイ値を正確な 1 次元積分へと再定式化することである。シャプレイ重みのベータ関数表現を利用することで、著者は以下の式を導出する：
$$\phi_i(v) = (u_i - 1) \int_0^1 \prod_{j \neq i} \left( (1-t) + t u_j \right) dt$$
この変換により、部分集合の列挙や補間に基づく係数の回復の必要性が排除される。

2. ガウス・ルジャンドル求積法

この積分はガウス・ルジャンドル求積法を用いて評価される。

• 正確性: 求積ノード数 $m_q$ が $m_q \ge \lceil d/2 \rceil$ を満たす場合、この手法は正確なシャプレイ値を回復する。
• 近似: $m_q < \lceil d/2 \rceil$ の場合、この手法は準正確な近似を提供する。誤差は $m_q$ に対して幾何学的に減衰することが証明されており、ベルンシュタイン楕円のパラメータ $\rho > 1$ に対して $O(\rho^{-2m_q})$ で有界である。実証的には、数千の特徴量であっても高精度な推定を得るために数百ノード程度で十分であり、理論的な正確性の閾値よりはるかに低い。

3. 数値的に安定かつ効率的な実装

実用的な計算課題に対処するため、著者は特定のアルゴリズム的最適化を提案する。

• 対数空間評価: 高次元におけるオーバフローとアンダフローを防ぐため、積を明示的な符号追跡を伴う対数空間で評価する。推定量は以下のように計算される：
  $$\hat{\phi}_i(v) = (u_i - 1) \sum_{q=1}^{m_q} \omega_q \cdot \text{sgn}(P_q)\text{sgn}(T_{q,i}) \exp\left( \log|P_q| - \log|T_{q,i}| \right)$$
  ここで、$P_q$ は項の完全な積、$T_{q,i}$ は特徴量 $i$ の項である。
• 共有計算: 各特徴量に対して「1 つ除外」の積を再計算するのではなく、完全な積を一度計算し、特徴量 $i$ 固有の因子で割る。これにより、計算複雑性が $O(d^2 m_q)$ から$O(d m_q)$に削減される。
• 並列化: 計算は、対数空間での縮約を$O(\log d)$の並列時間で計算するために、結合的スキャンプリミティブ（プレフィックス和）を利用する。

主要な貢献

1. 正確な積分定式化: 本論文は、積ゲームに対するシャプレイ値が正確な積分表現を許容することを確立し、ガウス・ルジャンドル求積法の利用を可能にする。
2. 安定性と効率性: QuadraSHAP は、安定性と効率性のトレードオフを解決する。補間ベースの手法（Linear TreeSHAP など）の数値的不安定性を回避しつつ、積カーネルモデルに対する代数的再帰手法よりも大幅に高速である。
3. 理論的保証: この手法は、$m_q \ge \lceil d/2 \rceil$ に対して証明可能な正確性を提供し、近似領域に対して幾何学的収束の境界を提供する。
4. スケーラブルなアルゴリズム: 著者は、$O(d m_q)$ の逐次作業と $O(\log d)$ の並列時間を有するアルゴリズムを導出し、この手法を高次元問題（数千の特徴量）にスケーラブルにする。

実験結果

著者は、合成データセットおよび実世界データセットにおいて、QuadraSHAP を最先端のベースライン（TreeSHAP、Linear TreeSHAP、FastTreeSHAP、shapiq、PKeX-Shapley）と比較評価した。

• アンサンブル木:
  • 速度: QuadraSHAP は、すべてのテスト構成において最速の数値的に安定した手法である。大規模なアンサンブル（$10^5$ 個のリーフ）において、TreeSHAP より 3–5 倍、FastTreeSHAP より 2–2.7 倍高速である。
  • 安定性: 深い木領域（深さ最大 100）において、Linear TreeSHAP や TreeSHAP などの競合手法は、シャプレイ効率公理の壊滅的な違反（誤差が $10^{186}$ 以上）を示す。QuadraSHAP は浮動小数点の限界レベル（$\sim 10^{-13}$）の精度を維持する。
• 積カーネル手法:
  • スケーラビリティ: 積カーネルを有するカーネルリッジ回帰において、QuadraSHAP は現在の正確なベースライン（PKeX-Shapley）よりも 1 桁高速である。
  • 高次元: 特徴量次元 $d \ge 2000$ において PKeX-Shapley がタイムアウト（300 秒制限）するのに対し、QuadraSHAP は数秒で説明を完了する（例：$d=5000$ で 7.6 秒）。
• 近似品質: 実験により、近似誤差がノード数 $m_q$ に対して幾何学的に減衰することが確認された。$d=5000$ の場合、正確性の閾値（2500）を大幅に下回る 400 ノードのみを使用しても、機械精度に近い精度が得られる。

意義と主張

本論文は、QuadraSHAP が乗法的構造を持つモデルにおける特徴量帰属のための統合された堅牢なフレームワークを提供すると主張する。積分表現とガウス・ルジャンドル求積法を活用することで、以下を実現する：

• 数値的堅牢性: 補間ベースの手法が失敗する高次元および深い木の設定においても安定性を維持する。
• 計算上の優位性: 正確性または制御された近似を維持しながら、既存の最速の手法と同等かそれ以上の速度を達成する。
• 汎用性: この定式化は、単一の計算パラダイムの下に木アンサンブルと積カーネル手法を統合する。

著者は、QuadraSHAP をこれらの特定のモデルクラスに対する最速の数値的に安定した手法として位置づけ、複雑で高次元の機械学習システムにおける説明可能性のための実用的な解決策を提供する。