技術要約：テンソルネットワークによる扱いやすいシャプレイ値と相互作用の計算

問題提起

機械学習の予測をシャプレイ値およびその高次一般化（シャプレイ相互作用指数、SII）を用いて説明することは、意思決定支援と解釈可能性において極めて重要である。しかし、これらの指数を計算することは、特徴量数 $n$ に対して指数関数的な計算量を要するため、従来の手法では困難であった。具体的には、$O(2^n)$ の提携（coalition）を列挙する必要がある。既存の解決策は、以下のような重大なトレードオフに直面している：

• 構造的仮定： TreeSHAPや一般化加法モデル（GAM）向けのメソッドは、特定のアーキテクチャ（例：決定木、線形モデル）に対してのみ厳密な計算が可能である。
• サンプリングベースの近似： KernelSHAPやSHAP-IQなどのアプローチは、大規模なサンプリングに依存しており、繊細な分散チューニングが必要であり、膨大な計算コストなしには高次の相互作用へのスケールアップが困難である。
• 償却推定（Amortized Estimation）： 補助モデルを訓練する手法は、大幅な訓練オーバーヘッドが発生する場合があり、説明の忠実性に関する理論的な保証を欠くことがある。

核心となる課題は、指数関数的な列挙や過度なサンプリングを行うことなく、一般的な予測関数に対してシャプレイ値と相互作用を（正確に、あるいは制御された誤差範囲内で）計算することである。

手法：TN-SHAP

著者らは、網羅的な提携列挙の代わりに、テンソルネットワーク（TN）サロゲート上での少数の評価スキームを用いる手法である TN-SHAP を提案する。このアプローチは、複雑性を $O(2^n)$ から $O(n \cdot \text{poly}(\chi))$ （ここで $\chi$ はテンソルネットワークの最大ボンド次元）へと削減するために、3つの主要な知見を活用している。

1. 多項式表現と係数抽出

本手法は、予測関数 $f$ が、リフトされた特徴空間における多項式関数 $g$ によって良好に近似できると仮定する。多項式展開において、$f(x) = \sum_{T \subseteq N} c_T \prod_{j \in T} x_j$ と表されるとき、提携の値はテンソル係数の線形結合に対応する。極めて重要な点は、シャプレイ値は特定の提携の構成メンバーシップではなく、サイズ集約された限界寄与（サイズ $s$ の提和における寄与の総和）にのみ依存するということである。

2. 対角セレクターと多項式補間

提携を $2^n$ 回クエリする代わりに、TN-SHAPは、リフトされた特徴 $\tilde{x}_r = [\phi(x_r), 1]^\top$ に対して適用される対角セレクター行列 $S_r(t) = \text{Diag}(t, 1)$ を使用する。

• 特徴量がパラメータ $t$ によってスケーリングされた点においてサロゲート $g$ を評価することで、本手法はすべてのサイズ $s$ の提和を、結果として得られる多項式 $P(t)$ の $t^s$ の係数へと集約する。
• 具体的には、ターゲットとなる特徴 $i$ に対して、他の特徴のすべての部分集合における限界寄与を孤立させるためのプローブ関数 $G_i(t)$ が構築される。
• これにより、組合せ論的な問題を多項式補間へと変換する。$n$ 個の異なる点（例：チェビシェフ＝ガウス・ノード）で $G_i(t)$ を評価することで、システムはサイズ集約された限界寄与 $\{m_s^{(i)}\}$ を回収するためのヴァンデルモンド連立一次方程式を解く。
• シャプレイ値は、これら回収された係数の重み付き和として計算される。

3. テンソルネットワーク・サロゲート

大規模なスケールで多項式写像の評価を扱いやすくするために、係数テンソルはテンソルネットワーク（TN）（例：テンソルトレインや階層型ツリー）を用いて、ボンド次元 $\chi$ を持つ形で因子分解される。

• 特徴マップ： 非線形な実世界のデータを扱うため、スカラー特徴量は、TNに入る前に学習済みまたは手作りの写像 $\phi_i: \mathbb{R} \to \mathbb{R}^{d_i-1}$ を通じてリフトされる。これにより、元の入力空間における非線形性をサロゲートがモデル化することを可能にしつつ、リフトされた空間における多項式性を維持する。
• 効率性： TNを通じた各フォワードパスのコストは $O(\text{poly}(\chi))$ である。補間のために必要な評価回数は $O(n)$ であるため、次数 $k$ の相互作用を計算するための総計算量は $n$ に関して多項式時間となる。

主な貢献

1. 統一されたプローブ・補間スキーム： $O(2^n)$ のクエリを回避し、わずか $O(n)$ 回の構造化されたフォワードパスを用いて、多項式 TN サロゲート上でシャプレイ値と $k$ 次相互作用を計算する厳密なアルゴリズム。
2. 特徴マップ強化型サロゲート： 学習された特徴リフトがいかにして多項式性を保持しながら、非線形モデルに対するサロゲートの忠実度を向上させ、厳密な計算を可能にするかを示すフレームワーク。
3. 理論的保証：
   • 厳密性： 本手法は、適合された多項式サロゲート上でシャプレイ値を正確に計算する。
   • 近似誤差： 元のモデルに対する誤差は、サロゲートの最悪の提和近似誤差（$\epsilon$）によって抑えられる。シャプレイ値については、$|\phi^g_i - \phi^f_i| \leq 2\epsilon$ となる。
   • 計算可能性： 指数関数的な時間から、多項式時間 $O(n \cdot \text{poly}(\chi) + n^2)$ への削減を証明。

実験結果

著者らは、合成多項式関数およびMLP（多層パーセプトロン）を教師モデルとした実世界のUCI回帰データセット（Concrete, Diabetes, Energy）を用いて、TN-SHAPを評価した。

• 合成検証： 正確な多項式関数において、TN-SHAPは理論的な厳密性を達成し、実行時間はミリ秒単位であり、KernelSHAP-IQを数桁上回る性能を示した（例：$n=10$ で 3.5ms 対 18.7ms、$n=50$ で 19.7ms 対 447.3ms）。
• 実世界での精度： MLP教師を用いたUCIデータセットにおいて：
  • TN-SHAPは、同等の精度においてKernelSHAP-IQに対して25〜1000倍の壁時計時間（wall-clock）の高速化を達成した。
  • 一次（$k=1$）の属性（attributions）について、TN-SHAPは真値との極めて高い余弦類似度（0.994）を達成した。
  • 高次の相互作用（$k=2, 3$）においても、TN-SHAPは競争力のある精度を維持したが、サンプリングベースのベースラインは、分散の問題に直面するか、同等の忠実度に達するために大幅に多くの計算時間を必要とした。
• ランク・アブレーション： 実験により、教師のランクが16である場合、学生となるTNのランク $r=5-6$ であれば、すべての相互作用の次数を $R^2 > 0.99$ で回収するのに十分であることが示された。低いランクでは高次の相互作用の再現が不足する。
• 高次元における安定性： 高次元の合成設定（$D=50, 100$）において、TN-SHAPは線形コストのクエリ予算内で高いサロゲート忠実度（$R^2 > 0.95$）と強力な Top-$k$ 特徴回収を維持した。

意義と主張

本論文は、TN-SHAPが、シャプレイ値の厳密な計算という理論的な厳格さと、実用的な効率性の必要性ととの間の溝を埋めるものであると主張している。テンソルネットワークの代数的構造と効率性を活用することで、本手法は以下を実現する：

• 指数関数的な列挙問題を、少数の構造化された評価へと変える。
• LIMEのような制約のない局所的サロゲートメソッドに共通する忠実性の問題に対処する、構造的保証（ランク境界による）を提供する。
• 局所的なシャプレイ値の説明と、グローバルな加法的構造（GAM）を統一する。次数 $k$ のサロゲートを適合させることで、対応するGAM項と一致する厳密な $k$-SII係数が得られる。
• サンプリングベースの手法、特にサンプリングの分散が通常高くなる高次の相互作用において、スケーラブルな代替手段を提供する。

著者らは、本手法の性能はTNサロゲートの適合精度と特徴マップの選択に依存すると述べているが、実験結果は、適度な特徴リフトとテンソルランクであっても、実用的な複雑な提和構造を捉えるのに十分であることを示唆している。