【論文紹介】Shapley Taylor interaction index 〜Taylor展開で交互作用を解釈する〜

はじめに

交互作用を考慮したSHAPである，SHAP-IQというライブラリの紹介記事が上がっていた．

https://nttdocomo-developers.jp/entry/2024/12/23/090000_2

記事中の参考論文を辿っていくと，Shapley Taylor interaction indexというものがあることがわかった．

https://proceedings.mlr.press/v119/sundararajan20a

このShapley Taylor interaction indexは，Shapley valueの拡張版であり，数学における関数のTaylor展開の考え方を使って交互作用を表現するという点が興味深かったので，本記事でまとめることとした．

準備

$n$ を自然数として $N = \{ 1, 2, \ldots , n \}$ とおく．その上で，関数 $F : 2^N \to \mathbb{R}$ を考える．（ $2^N$ は $N$ の部分集合全体からなる集合．）

$T \subseteq N$ に対して，それとは別の参加者 $S$ による $F$ の増分を

$$\delta_S F(T) = \sum_{W \subseteq S} (-1)^{w-s} F(T \cup W)$$

で定義する．

例　$S = \{i\}, \{i, j\}$ の場合は

$$\begin{align*} \delta_{\{i\}} F(T) &= F(T \cup \{i\}) - F(T), \\ \delta_{\{i, j\}} F(T) &= F(T \cup \{i, j\}) - F(T \cup \{i\}) - F(T \cup \{j\}) - F(T) \end{align*}$$

である．特に，$\delta_{\{i, j\}} F(T)$ は $F$ に $\delta_{\{i\}}$ を作用させた後に $\delta_{\{j\}}$ を作用させたものである．これらは微分のアナロジーになっている．

Shapley Taylor interaction index

説明次数を $k$ とし（ $1 \leq k \leq n$ を想定している），「 $k$ 以下の人数からなるメンバー $S$ が追加参加する際の $F$ の増分」を考える．

• $|S| < k$ の場合
  • $\delta_S F(\emptyset)$ と定める．つまり参加者ゼロから $S$ が参加した増分に等しい．
• $|S| = k$ の場合
  • 「 $S$ が参加する直前の状態→ $S$ が参加した直後の状態」の増分を，全ての参加順の組み合わせで計算し，平均する．

数式を用いて表そう．まず

$$\begin{align*} \mathcal{I}_{S, \pi}^k(F) := \begin{cases} \delta_S F(\emptyset), \quad |S| < k \\ \delta_S F(\pi^S), \quad |S| = k \end{cases} \end{align*}$$

と定める．ここで $\pi$ は $n$ 人の参加順を表す．（例えば $n=4$ なら $(1, 4, 2, 3)$ など．） $\pi^S$ は $S$ よりも前から参加しているプレイヤーである．（$S = \{3, 4\}$ なら $\pi = (1, 4, 2, 3)$ に対し $\pi^S = \{1\}$ となる．）各 $k$ に対し参加順 $\pi$ の組み合わせのすべてに関して平均をとったものがShapley Taylor Interaction Indexである：

$$\mathcal{I}_S^k(F) := \mathbb{E}_\pi \left[ \mathcal{I}_{S, \pi}^k(F) \right]$$

これらの準備のもと，関数 $F$ の出力の分解に関する重要な事実が成り立つ．

事実（efficiency公理）　任意の $F : 2^N \to \mathbb{R}$ はShapley Taylor interaction indexによって以下のように加法分解できる：

$$F(N) - F(\emptyset) = \sum_{ \emptyset \neq S \subseteq N, |S| \leq k} \mathcal{I}_S^k(F)$$

特に，$k=1$ の場合，Shapley値による分解に一致する．

のちに具体例でも見るが，興味深いのは $|S| = k$ の項である．この項はTaylor展開の（積分型）剰余項に対応する．

Taylor展開との関係

実際にTaylor展開との関連を見ていこう．概要は以下の通り．

• $F$ の多重線形拡張 $f$ を用意する（ちなみにこの線形拡張 $f$ は $x = (x_1, \ldots, x_n)$ の有限次多項式である）：

$$f(x) = f(x_1, \ldots, x_n) = \sum_{S \subseteq N} F(S) \prod_{i \in S} x_i \prod_{i \notin S} (1 - x_i).$$

• 次に1変数関数（多項式） $g(t) = f(t, t, \dots, t)$ を考える：

$$g(t) = \sum_{S \subseteq N} F(S) \cdot t^s (1 - t)^{n - s}.$$

• $g(t)$ のTaylor展開を行う．（これは任意次数 $k$ で行うことができる．）
  • つまり，関数を加法分解している．
• すべての $i$ に対し $x_i = 1$ を代入することで，元の関数 $F(N)$ を以下のように表現できる．上記の「事実」の式を復元している：

$$F(N) = \sum_{S \subseteq N, |S| \leq k} \mathcal{I}_S^k(F)$$

数式で確認

$n$ は一般でよい．$g(t)$ の1階微分は

$$g'(t) = \frac{d}{dt} f(t, t, \dots, t) = [(\partial_1 + \cdots + \partial_n) f](\vec{t})$$

なので，高階の微分は多重指数を用いて

$$g^{(j)}(t) = [(\partial_1 + \cdots + \partial_n)^j f](\vec{t}) = \sum_{|\alpha| = j} \frac{j!}{\alpha !} \partial^\alpha f(\vec{t})$$

と表せる．ここで $\vec{t}$ で $(t, t, \dots, t)$ を略記した．

この $g(t)$ を点 $a$ 周りでTaylor展開する（剰余項は積分型で表現する）と

$$\begin{align*} g(t) &= \sum_{j = 0}^{k-1} \frac{g^{(j)}(a)}{j!} (t - a)^j + \int_a^t \frac{(t - u)^{k-1}}{(k-1)!} g^{(k)}(u) \, du \\ &= \sum_{j = 0}^{k-1} \frac{(t - a)^j}{j!} \sum_{|\alpha| = j} \frac{j!}{\alpha !} \partial^\alpha f(\vec{a}) + \int_a^t \frac{(t - u)^{k-1}}{(k-1)!} \sum_{|\alpha| = k} \frac{k!}{\alpha !} \partial^\alpha f(\vec{u}) \, du \\ &= \sum_{j = 0}^{k-1} (t - a)^j \sum_{|\alpha| = j} \frac{1}{\alpha !} \partial^\alpha f(\vec{a}) + \sum_{|\alpha| = k} \frac{1}{\alpha !} k \int_a^t (t - u)^{k-1} \partial^\alpha f(\vec{u}) \, du \end{align*}$$

である．$g(1) = F(N), g(0) = F(\emptyset)$ なので $t = 1, a = 0$ とすると

$$F(N) = \sum_{j = 0}^{k-1} \sum_{|\alpha| = j} \frac{1}{\alpha !} \partial^\alpha f(\vec{0}) + \sum_{|\alpha| = k} \frac{1}{\alpha !} k \int_0^1 (1 - u)^{k-1} \partial^\alpha f(\vec{u}) \, du$$

である．ここで $f$ はその作り方から各変数に関して1次式なので，同じ変数に関して2回以上微分すると $0$ である．よって残る項は多重指数 $\alpha$ の成分が $0$ か $1$ の項だけであることに注意すると，

$$\begin{align*} F(N) &= \sum_{j = 0}^{k-1} \sum_{|\alpha| = j, \alpha_i \leq 1} \partial^\alpha f(\vec{0}) + \sum_{|\alpha| = k, \alpha_i \leq 1} k \int_0^1 (1 - u)^{k-1} \partial^\alpha f(\vec{u}) \, du \\ &= \sum_{j = 0}^{k-1} \sum_{|\alpha| = j, \alpha_i \leq 1} \frac{\partial^j f}{\partial x_1^{\alpha_1} \cdots \partial x_n^{\alpha_n}}(\vec{0}) + \sum_{|\alpha| = k, \alpha_i \leq 1} k \int_0^1 (1 - u)^{k-1} \frac{\partial^k f}{\partial x_1^{\alpha_1} \cdots \partial x_n^{\alpha_n}}(\vec{u}) \, du \end{align*}$$

である．

ここで $|S| = j$ なる $S \subseteq N$ を $S = \{i_1, i_2, \ldots, i_j\}$ と表すとき（重複を排除するため $i_1 < i_2 < \cdots < i_j$ を仮定する），"$S$ の変数による微分"を

$$\Delta_S f = \frac{\partial^j f}{\partial x_{i_1} \cdots \partial x_{i_j}}$$

と表記すると

$$F(N) = \sum_{j = 0}^{k-1} \sum_{|S| = j} \Delta_S f(\vec{0}) + \sum_{|S| = k} k \int_0^1 (1 - u)^{k-1} \Delta_S f(\vec{u}) \, du$$

と表せる．

実は以下の事実が成り立つ．

事実（論文のTheorem 3.）　$k$ を一つ固定する．$|S| < k$ なる $S \subseteq N$ に対し $\Delta_S f(\vec{0}) = \mathcal{I}^k_S(F)$ である．さらに，$|S| = k$ なる $S \subseteq N$ に対し

$$k \int_0^1 (1 - u)^{k-1} \Delta_S f(\vec{u}) \, du = \mathcal{I}^k_S(F)$$

である．

これによって，任意の $1 \leq k \leq n$ に対し次の分解

$$F(N) = \sum_{j = 0}^{k-1} \sum_{|S| = j} \mathcal{I}^k_S(F) + \sum_{|S| = k} \mathcal{I}^k_S(F) = \sum_{S \subseteq N, |S| \leq k} \mathcal{I}^k_S(F)$$

が成り立つ．

$n=3$ での具体例

以上のことを $n = 3$ つまり $N = \{1, 2, 3\}$ の場合を具体例にとり，次数 $k=2$の確認をしていこう．

$F$ の線形拡張は

$$\begin{align*} f(x_1, x_2, x_3) &= % まとめ F(\emptyset) \\ &\phantom{{}={}} + \delta_{\{1\}} F(\emptyset) \cdot x_1 + \delta_{\{2\}} F(\emptyset) \cdot x_2 + \delta_{\{3\}} F(\emptyset) \cdot x_3 \\ &\phantom{{}={}} + \delta_{\{1, 2\}} F(\emptyset) \cdot x_1 x_2 + \delta_{\{2, 3\}} F(\emptyset) \cdot x_2 x_3 + \delta_{\{3, 1\}} F(\emptyset) \cdot x_3 x_1 \\ &\phantom{{}={}} + \delta_{\{1, 2, 3\}} F(\emptyset) \cdot x_1 x_2 x_3 \end{align*}$$

となる．

上記計算の詳細

$$\begin{align*} f(x_1, x_2, x_3) &= % 0次の項 F(\emptyset) \cdot (1 - x_1) (1 - x_2) (1 - x_3) \\ % 1次の項 &\phantom{{}={}} + F(\{1\}) \cdot x_1 (1 - x_2) (1 - x_3) \\ &\phantom{{}={}} + F(\{2\}) \cdot x_2 (1 - x_3) (1 - x_1) \\ &\phantom{{}={}} + F(\{3\}) \cdot x_3 (1 - x_1) (1 - x_2) \\ % 2次の項 &\phantom{{}={}} + F(\{1, 2\}) \cdot x_1 x_2 (1 - x_3) \\ &\phantom{{}={}} + F(\{2, 3\}) \cdot x_2 x_3 (1 - x_1) \\ &\phantom{{}={}} + F(\{3, 1\}) \cdot x_3 x_1 (1 - x_2) \\ % 3次の項 &\phantom{{}={}} + F(\{1, 2, 3\}) \cdot x_1 x_2 x_3 \\ &= % 0次の項 F(\emptyset) \\ % 1次の項 &\phantom{{}={}} + [ F(\{1\}) - F(\emptyset) ] \cdot x_1 \\ &\phantom{{}={}} + [ F(\{2\}) - F(\emptyset) ] \cdot x_2 \\ &\phantom{{}={}} + [ F(\{3\}) - F(\emptyset) ] \cdot x_3 \\ % 2次の項 &\phantom{{}={}} + [ F(\{1, 2\}) - F(\{1\}) - F(\{2\}) + F(\emptyset) ] \cdot x_1 x_2 \\ &\phantom{{}={}} + [ F(\{2, 3\}) - F(\{2\}) - F(\{3\}) + F(\emptyset) ] \cdot x_2 x_3 \\ &\phantom{{}={}} + [ F(\{3, 1\}) - F(\{3\}) - F(\{1\}) + F(\emptyset) ] \cdot x_3 x_1 \\ % 3次の項 &\phantom{{}={}} + [ F(\{1, 2, 3\}) - F(\{1, 2\}) - F(\{2, 3\}) - F(\{3, 1\}) \\ &\phantom{{}={} + []} + F(\{1\}) + F(\{2\}) + F(\{3\}) - F(\emptyset) ] \cdot x_1 x_2 x_3 \\ &= % まとめ F(\emptyset) \\ &\phantom{{}={}} + \delta_{\{1\}} F(\emptyset) \cdot x_1 + \delta_{\{2\}} F(\emptyset) \cdot x_2 + \delta_{\{3\}} F(\emptyset) \cdot x_3 \\ &\phantom{{}={}} + \delta_{\{1, 2\}} F(\emptyset) \cdot x_1 x_2 + \delta_{\{2, 3\}} F(\emptyset) \cdot x_2 x_3 + \delta_{\{3, 1\}} F(\emptyset) \cdot x_3 x_1 \\ &\phantom{{}={}} + \delta_{\{1, 2, 3\}} F(\emptyset) \cdot x_1 x_2 x_3 \end{align*}$$

この式から，例えば $\vec{0}$ における微分のデータは以下の通り計算できる：

$$% 一階微分 \partial_1 f(\vec{0}) = \delta_{\{1\}} F(\emptyset), \quad \partial_2 f(\vec{0}) = \delta_{\{2\}} F(\emptyset), \quad \partial_3 f(\vec{0}) = \delta_{\{3\}} F(\emptyset), \\ % 二階微分 \partial_1 \partial_2 f(\vec{0}) = \delta_{\{1, 2\}} F(\emptyset), \quad \partial_2 \partial_3 f(\vec{0}) = \delta_{\{2, 3\}} F(\emptyset), \quad \partial_3 \partial_1 f(\vec{0}) = \delta_{\{3, 1\}} F(\emptyset), \\ % 三階微分 \partial_1 \partial_2 \partial_3 f(\vec{0}) = \delta_{\{1, 2, 3\}} F(\emptyset)$$

これら以外の項は $0$ である．よって，$k=2$ だと

$$\begin{align*} F(N) &= \sum_{j = 0}^{k-1} \sum_{|\alpha| = j} \frac{1}{\alpha !} \partial^\alpha f(\vec{0}) + \sum_{|\alpha| = k, \alpha_i \leq 1} \frac{1}{\alpha !} k \int_0^1 (1 - u)^{k-1} \partial^\alpha f(\vec{u}) \, du \\ &= \sum_{j = 0}^{1} \sum_{|\alpha| = j} \frac{1}{\alpha !} \partial^\alpha f(\vec{0}) + \sum_{|\alpha| = 2, \alpha_i \leq 1} \frac{2}{\alpha !} \int_0^1 (1 - u) \partial^\alpha f(\vec{u}) \, du \\ &= \sum_{j = 0}^{1} \sum_{|\alpha| = j} \partial^\alpha f(\vec{0}) + \sum_{|\alpha| = 2, \alpha_i \leq 1} 2 \int_0^1 (1 - u) \partial^\alpha f(\vec{u}) \, du \\ &= f(\vec{0}) + \partial_1 f(\vec{0}) + \partial_2 f(\vec{0}) + \partial_3 f(\vec{0}) \\ &\phantom{{}={}} + 2 \int_0^1 (1 - u) \partial_1 \partial_2 f(\vec{u}) \, du \\ &\phantom{{}={}} + 2 \int_0^1 (1 - u) \partial_2 \partial_3 f(\vec{u}) \, du \\ &\phantom{{}={}} + 2 \int_0^1 (1 - u) \partial_3 \partial_1 f(\vec{u}) \, du \\ &= f(\vec{0}) + \delta_{\{1\}} F(\emptyset) + \delta_{\{2\}} F(\emptyset) + \delta_{\{3\}} F(\emptyset) \\ &\phantom{{}={}} + 2 \int_0^1 (1 - u) [\delta_{\{1, 2\}} F(\emptyset) + \delta_{\{1, 2, 3\}} F(\emptyset) u] \, du \\ &\phantom{{}={}} + 2 \int_0^1 (1 - u) [\delta_{\{2, 3\}} F(\emptyset) + \delta_{\{1, 2, 3\}} F(\emptyset) u] \, du \\ &\phantom{{}={}} + 2 \int_0^1 (1 - u) [\delta_{\{3, 1\}} F(\emptyset) + \delta_{\{1, 2, 3\}} F(\emptyset) u] \, du \\ &= f(\vec{0}) + \delta_{\{1\}} F(\emptyset) + \delta_{\{2\}} F(\emptyset) + \delta_{\{3\}} F(\emptyset) \\ &\phantom{{}={}} + \left[ \delta_{\{1, 2\}} F(\emptyset) + 2 \int_0^1 (1 - u) u \, du \times \delta_{\{1, 2, 3\}} F(\emptyset) \right] \\ &\phantom{{}={}} + \left[ \delta_{\{2, 3\}} F(\emptyset) + 2 \int_0^1 (1 - u) u \, du \times \delta_{\{1, 2, 3\}} F(\emptyset) \right] \\ &\phantom{{}={}} + \left[ \delta_{\{3, 1\}} F(\emptyset) + 2 \int_0^1 (1 - u) u \, du \times \delta_{\{1, 2, 3\}} F(\emptyset) \right] \\ &= F(\emptyset) + \delta_{\{1\}} F(\emptyset) + \delta_{\{2\}} F(\emptyset) + \delta_{\{3\}} F(\emptyset) \\ &\phantom{{}={}} + \left[ \delta_{\{1, 2\}} F(\emptyset) + \frac{1}{3} \delta_{\{1, 2, 3\}} F(\emptyset) \right] \\ &\phantom{{}={}} + \left[ \delta_{\{2, 3\}} F(\emptyset) + \frac{1}{3} \delta_{\{1, 2, 3\}} F(\emptyset) \right] \\ &\phantom{{}={}} + \left[ \delta_{\{3, 1\}} F(\emptyset) + \frac{1}{3} \delta_{\{1, 2, 3\}} F(\emptyset) \right] \\ &= % 0次の項 F(\emptyset) + % 1次の交互作用 \mathcal{I}^2_{\{1\}}(F) + \mathcal{I}^2_{\{2\}}(F) + \mathcal{I}^2_{\{3\}}(F) + % 2次の交互作用 \mathcal{I}^2_{\{1, 2\}}(F) + \mathcal{I}^2_{\{2, 3\}}(F) + \mathcal{I}^2_{\{3, 1\}}(F) \end{align*}$$

最後の式変形についての参考

$\mathcal{I}^2_{\{1, 2\}}(F)$ だけ計算する．他も同様である．

$\pi$ は $3! =6$ 通り考える．

$$\begin{align*} % 1 \mathcal{I}^2_{\{1, 2\}, (1, 2, 3)}(F) &= \delta_{\{1, 2\}} F((1, 2, 3)^{\{1, 2\}}) = \delta_{\{1, 2\}} F(\emptyset) \\ % 2 \mathcal{I}^2_{\{1, 2\}, (1, 3, 2)}(F) &= \delta_{\{1, 2\}} F((1, 3, 2)^{\{1, 2\}}) = \delta_{\{1, 2\}} F(\emptyset) \\ % 3 \mathcal{I}^2_{\{1, 2\}, (2, 1, 3)}(F) &= \delta_{\{1, 2\}} F((2, 1, 3)^{\{1, 2\}}) = \delta_{\{1, 2\}} F(\emptyset) \\ % 4 \mathcal{I}^2_{\{1, 2\}, (2, 3, 1)}(F) &= \delta_{\{1, 2\}} F((2, 3, 1)^{\{1, 2\}}) = \delta_{\{1, 2\}} F(\emptyset) \\ % 5 \mathcal{I}^2_{\{1, 2\}, (3, 1, 2)}(F) &= \delta_{\{1, 2\}} F((3, 1, 2)^{\{1, 2\}}) = \delta_{\{1, 2\}} F(\{3\}) \\ % 6 \mathcal{I}^2_{\{1, 2\}, (3, 2, 1)}(F) &= \delta_{\{1, 2\}} F((3, 2, 1)^{\{1, 2\}}) = \delta_{\{1, 2\}} F(\{3\}) \end{align*}$$

を平均することで，

$$\begin{align*} \mathcal{I}^2_{\{1, 2\}}(F) &= \frac{2}{3} \times \delta_{\{1, 2\}} F(\emptyset) + \frac{1}{3} \times \delta_{\{1, 2\}} F(\{3\}) \\ &= \delta_{\{1, 2\}} F(\emptyset) + \frac{1}{3} \times \left[ \delta_{\{1, 2\}} F(\{3\}) - \delta_{\{1, 2\}} F(\emptyset) \right] \\ &= \delta_{\{1, 2\}} F(\emptyset) + \frac{1}{3} \delta_{\{1, 2, 3\}} F(\emptyset) \end{align*}$$

を得る．

となってefficiency公理をきちんと復元している．

まとめ

交互作用とTaylor展開を関連づけたShapley Taylor interaction indexは理論的に見通しがよいと感じた．

一方，ここで行った加法分解の議論はあくまで有限集合上の関数 $F$ に対してのものであったため，機械学習モデル $\hat{f}$ への適用については，SHAPと同様に，例えば$S = \{1, 2\}$の場合には

$$F(S) = F(\{1, 2\}) = \mathbb{E}_{X_{\setminus 1, 2}} \left[ \hat{f}(x_1, x_2, X_{\setminus 1, 2}) \right]$$

と周辺化して翻訳するなどの工夫が必要なのだろうと感じた．この辺りについては，SHAP-IQのライブラリにはすでに実装されていると思われるので，気になる方はドキュメントを参照すると良いかもしれない．

参考文献

https://proceedings.mlr.press/v119/sundararajan20a

https://nttdocomo-developers.jp/entry/2024/12/23/090000_2

https://gihyo.jp/book/2021/978-4-297-12226-3