技術概要：Quadrature-TreeSHAP

問題定義

樹木アンサンブルモデル（例：XGBoost、Random Forests）の説明可能性は、シャプロン値に大きく依存しています。経路依存型 SHAP は効率性から標準的なアプローチとなっていますが、既存の手法は深度依存の実行時間、数値的安定性、および高次相互作用のサポートに関して重大なトレードオフに直面しています。

現在の最先端手法は特定の限界を示しています：

• TreeSHAPおよびGPUTreeSHAPは、$O(MTLD^2)$ の時間計算量で動作します（ここで $M$ はサンプル数、$T$ は木の数、$L$ は葉の数、$D$ は深度です）。
• FastTreeSHAP v2およびWoodelfは計算量を $O(MTLD)$ に削減しますが、深度に対して指数関数的な前処理ステップを導入するため、深い木には実用的ではありません。
• Linear TreeSHAPは $O(MTND)$ を達成しますが、単項式基底での演算により数値的不安定性に悩まされます。
• TreeGrad-Shapは勾配定式化を通じて安定性を向上させますが、1 次帰属に限定されます。
• TreeSHAP-IQは高次相互作用に拡張しますが、計算量は $O(MTLD \binom{F-1}{s-1})$ であり、特徴量の数（$F$）と相互作用次数（$s$）が増加するにつれて悪化します。

手法

著者は、ガウス・ルジャンドル求積法と重み付きバンザフ相互作用多項式に基づいた経路依存型 TreeSHAP の再定式化であるQuadrature-TreeSHAPを提案します。

1. 理論的基盤

この手法は、シャプロン値と重み付きバンザフ値の間の関係を利用します。

• 重み付きバンザフ多項式: 決定木の葉 $v$ に対して、包含確率 $p$ における特徴量部分集合 $S$ の経路依存型重み付きバンザフ相互作用値は、多項式 $B^{(S)}_{p,v}$ として表されます。この多項式は、葉の経路構造とエッジ重みから導出されます。
• 積分復元: シャプロン相互作用値は、これらのバンザフ多項式を参加確率 $p \in [0, 1]$ 上で積分することで復元されます：
  $$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$$
• 求積近似: 記号的積分の代わりに、著者はガウス・ルジャンドル求積法を用いてこの積分を評価します。積分は、固定されたノード $t_m$ において評価された多項式の重み付き和として近似されます：
  $$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$$

2. アルゴリズム実装

• 固定点定式化: アルゴリズムは、木に対して単一の深さ優先探索（DFS）を実行します。探索中に、記号的に多項式を展開するのではなく、ガウス・ルジャンドルノードの固定セット（通常 8 点）における経路多項式の値を伝播させます。
• 計算量の削減:
  • 理論的には、次数 $s$ の相互作用に対する被積分関数の次数は、経路上の最大固有特徴量数 $d$ に対して $d-s$ 以下です。
  • 実際には、著者は非常に深い木であっても8 点の固定求積点で浮動小数点数 32 ビット（float32）の機械精度に到達できることを実証しています。
  • これにより、内部計算から木深度 $d$ の依存性が除去され、1 次の場合の実効計算量が $O(MTN \lceil d/2 \rceil)$ から $O(MTN)$に、次数$s$の相互作用の場合には$O(MTN d^s)$から$O(MTN d^{s-1})$ に削減されます。
• ハードウェア加速: 計算はすべての経路に対して同じ固定点セットを評価するものであり、演算が規則的であるため、CPU 上では効率的なSIMD（単一命令複数データ）実行、GPU 上ではSIMT（単一命令複数スレッド）実行が可能となり、GPUTreeSHAP が必要としたビンパッキングやスケジューリングのオーバーヘッドを排除します。

主要な貢献

1. 任意次数相互作用アルゴリズム: 本論文は、TreeSHAP-IQ の最先端計算量を $O(MTLD \binom{F-1}{s-1})$ から $O(MTN d^s)$ に改善する、任意次数のシャプロン相互作用値を計算するアルゴリズムを提示します。特徴量数 $F$ が木深度 $D$（および $d$）を超える場合（$F > D \ge d$）、大幅な改善が得られます。
2. 求積法に基づく再定式化: 著者は、8 点のガウス・ルジャンドル点でシャプロン値および相互作用の機械精度に到達できることを理論的および実証的に分析し、実際には実行時間を木深度から実質的に切り離すことを示しました。
3. 数値的安定性: 単項式基底で係数を展開するのではなく、有界かつ正のノードで要約多項式を評価することで、この手法は大規模な相殺（catastrophic cancellation）を回避します。著者は、Quadrature-TreeSHAP が特に深いアンサンブルにおいて TreeSHAP よりも数値的に安定であると主張しています。
4. ハードウェア効率の高い実装: この手法は CPU 向けに C++ で実装され、GPU 向けに XGBoost に統合されています。ベクトル化（CPU で 4 点、GPU で 32 点）を活用することで、既存の実装と比較して大幅な高速化を実現しています。
5. オープンソース統合: 実装はオープンソース化され、XGBoost ライブラリに統合されています（TreeSHAP バックエンドを置換）。標準的な API 呼び出し（pred_contribs=True および pred_interactions=True）を通じてアクセス可能です。

実験結果

著者は、Quadrature-TreeSHAP を、小規模、大規模、疎な領域にわたる 12 の XGBoost ベンチマークアンサンブル（Adult、CalHousing、CovType、Fashion-MNIST）で評価しました。

• 1 次（シャプロン値）:
  • CPU: TreeSHAP より 1.06 倍から 10.59 倍高速（中央値 3.84 倍）。
  • GPU: GPUTreeSHAP より 1.84 倍から 6.95 倍高速。
• 2 次（ペアワイズ相互作用）:
  • CPU: TreeSHAP より 3.80 倍から 58.11 倍高速（中央値 12.86 倍）。
  • GPU: GPUTreeSHAP より最大 6.65 倍高速（ただし、特定の小深度ワークロードでは GPUTreeSHAP が競争力を持ちました）。
• 高次相互作用（Python ベンチマーク）:
  • 3 次相互作用において TreeSHAP-IQ と比較したところ、Quadrature-TreeSHAP は 18.73 倍から 26.49 倍高速でした。
  • CovType-sparse データセットでは、相互作用次数が増加するにつれて TreeSHAP-IQ に対する高速化率が上昇し、6 次で1209.37 倍に達しました。
• 数値的安定性:
  • 深度が増加する Fashion-MNIST-sparse ベンチマークにおいて、TreeSHAP は深度 32 を超えると不安定になりました。一方、Quadrature-TreeSHAP は安定しており、6〜8 点で高い精度を達成しました。

重要性

本論文は、Quadrature-TreeSHAP が経路依存型 SHAP の数値的に安定し、ハードウェア効率が高く、相互作用を認識する再定式化を提供すると主張しています。記号的な多項式演算から固定点求積法へ移行することで、この手法は深度依存性と数値的安定性の間のトレードオフを解決します。これにより、以前は先行手法の指数関数的な計算量や不安定性によって阻害されていた、深い木における高次相互作用の効率的な計算が可能になります。XGBoost への統合により、ライブラリ利用者および広範な shap パッケージのユーザーにとって、即座に実用的な価値が保証されます。