Alternative Methods to SHAP Derived from Properties of Kernels: A Note on Theoretical Analysis

In the field of machine learning, Explainable Artificial Intelligence (XAI) refers to techniques and methods that make the decisions and predictions of machine learning models easier to understand. Among them, AFA (Additive Feature Attribution) is a method that decomposes a model’s prediction into the contributions of individual features. Notably, SHAP (SHapley Additive exPlanations), proposed by [5], which is based on the Shapley value [8] in cooperative game theory, is well-known in this context. Recently, research on SHAP has been rapidly expanding ([4]). To reduce the computational cost of SHAP, various methods such as Tree-SHAP[5] and Fast SHAP [3] have been proposed and applied to actual data (for example, [2]). As an alternative to SHAP, [1] considers ES (Equal Surplus) and FESP (Fair Efficient Symmetric Perturbation), both of which are based on solution concepts in cooperative game theory.

In this study, we investigate the relationship between AFA and the kernel in LIME (Local Interpretable Model-agnostic Explanations) as proposed by [6]. [5] characterizes SHAP in terms of the kernel (Kernel SHAP) and derive the expression of SHAP kernel explicitly. Intriguingly, the properties of the SHAP kernel seem different from those that the LIME kernel is expected to have. More specifically, in LIME, the kernel attaches a large weight as a perturbed sample gets closer to the instance being explained, which is different for that of SHAP. In this note, we first provide a general framework to relate an AFA with its associated kernel by deriving an analytical expression of an AFA in terms of its kernel. Then, we propose some new AFAs that have reasonable properties of kernels or that coincide with the LS prenucleolus in cooperative game theory. We also revisit existing AFAs such as SHAP (SHapley Additive exPlanations) and reexamine the properties of their kernels.

Let t and $n$ be the number of the instances and the number of features, respectively. Suppose $N=\{1,...,n\}$, $T=\{1,...,t\}$. The feature input is a $t\times n$ matrix $X=(X_{1},...X_{j},...,X_{n})$. The $j$th feature vector is $X_{j}=(x_{1,j},...,x_{t,j})^{\prime}$ and, for the $\tau$th instance of interest, the vector of features is $x_{\tau}=(x_{\tau,1},...,x_{\tau,j},...,x_{\tau,n})$. Let $f$ be the original prediction model which takes $x_{\tau}$ and produces a prediction.

For an element of the power set of $N$, which is called a coalition in the cooperative game theory, $S\in 2^{N}$, define $x_{\tau,S}=\{x_{\tau,j}|j\in S\}$. $x_{\tau,S}$ is a vector that consists of features in $S$ at $\tau$th instance. Similarly, for $S\in 2^{N}$, define $X_{S}=\{X_{j}|j\in S\}$.

In cooperative game theory, a characteristic function form game is expressed as $(N,v)$ where $N=\{1,...,n\}$ is the set of players and $v$ is a real-valued function on the power set $2^{N}$. For the $\tau$th instance and any coalition $S\in 2^{N}$, when we define $v_{\tau}:2^{N}\longrightarrow\mathbb{R}$ as in (1), a characteristic function form game $(N,v_{\tau})$ is specified for $\tau$:

$v_{\tau}(S)$ is interpreted as the prediction that $f$ produces for the $\tau$th instance, when (i) features $x_{\tau,j}$ where $j\in S$ are known but (ii) features $x_{\tau,k}$ where $k\in N\setminus S$ are unknown. Note that $v_{\tau}(N)=E\left[\hat{f}(x_{\tau,1},...,x_{\tau,n})\right]=\hat{f}(x_{\tau,1},...,x_{\tau,n})$ and $v_{\tau}(\emptyset)=E\left[\hat{f}(X_{1},...,X_{n})\right]=E\left[\hat{f}(X)\right]$, where the former is the prediction when all features at $\tau$th instances are known and the latter is the prediction when none of the features are known. It should be noted that, while standard cooperative game theory assumes that $v(\emptyset)=0$, this is not necessarily satisfied under this machine learning (ML) setting.

With this setup, Additive Feature attribution (AFA) is the method to decompose $v_{\tau}(N)-v_{\tau}(\emptyset)$ into features at $\tau$, depending on their “contributions.” More precisely, for a characteristic function form game $(N,v_{\tau})$ associated with the $\tau$th instance and for the feature (player) $j$, define a real-valued function $\Psi_{\tau}(j):N\longrightarrow\mathbb{R}$. We hereafter use $\Psi_{\tau}(j)$ and $\Psi_{\tau,j}$ interchangeably and let $\Psi_{\tau}=(\Psi_{\tau,1},...,\Psi_{\tau,n})$. When $\Psi_{\tau}$ satisfies $\sum_{j\in N}\Psi_{\tau,j}=v_{\tau}(N)-v_{\tau}(\emptyset)$, then $\Psi_{\tau}$ is called Additive Feature Attribution (AFA), denoted by $\Psi_{\tau}^{AFA}$.

Here we review [5] and [6], specifically the parts concerning the relationship between LIME and SHAP. In their notation, $x$ is the original representation of an instance being explained and $z$ is a perturbed sample from $x$. They use a binary vector $x^{\prime}$ and a mapping $x=h_{x}(x^{\prime})$, but in this study, just for simplicity, $x=x^{\prime}$ and $z=z^{\prime}$ i.e., the original instances are simplified ([5]), interpretable ([6]) or binary from the beginning.

[5] considers the following minimization problem (LIME, proposed by [6]).

• •

  $f$: the original prediction model.

• •

  $g$: the explanation model defined as $g(z)=\phi_{0}+\sum_{i=1}^{n}\phi_{i}z_{i}$, where $\phi_{i}\in\mathbb{R}$ and $n$ is the number of the features. Let $G$ be the set of all $g$s and let $\phi=(\phi_{1},...,\phi_{n})\in\mathbb{R}^{n}$.

• •

  $x$: instance being explained.

• •

  $z$: perturbed sample from $x$. Let $Z$ be the set of all $z$s, including $x$.

• •

  $\pi_{x}$: local kernel.

and $L$ is the loss function of the minimization problem and $\Omega(g)$ is a measure of complexity of $g$ (a more complex $g$ is penalized). Note that, regarding the kernel $\pi_{x}$, [6] assumes it increases as the distance between $x$ and $z$ decreases, that is, as $z$ gets closer to $x$, a larger weight is attached to $z$.

Based on this setup, [5] assumes $\Omega(g)=0$ and $L(f,g,\pi_{x})=\sum_{z\in Z}\left[f(z)-g(z)\right]^{2}\pi_{x}(z)$. Therefore, the minimization problem of (2) is:

Now recall $z$ is perturbed sample from $x$ and $x\in Z$. Therefore, summation over $Z$ in (2) coincides with the summation over $2^{N}$ under our notation, and the summation of $\sum_{i=1}^{n}\phi_{i}z_{i}$ coincides with $\sum_{i\in S}\phi_{i}$. Therefore, under our notation, (2) falls into the following:

Furthermore, [5] impose a local accuracy condition (or called efficiency) on this optimization problem: $f(x)=g(x)=\phi_{0}+\sum_{i=1}^{n}\phi_{i}x_{i}$ for $x$. We also impose this condition, so (3) becomes:

For the following analysis, we consider 4 to examine relationship between SHAP and other AFAs alternatives to SHAP and the associated kernel $\pi_{x_{\tau}}(S)$.

In this study, we first derive an analytical and general expression of an AFA as a function of its associated kernel. Next, we compute several AFAs based on representations of several different specific kernels. Among the existing AFAs, we show that for SHAP, by slightly modifying the kernel into an appropriate form, the generated AFA coincides with SHAP. Additionally, for ES and FESP, we derive the representations of the corresponding kernels. The last three kernels and the AFAs generated from them are proposed for the first time in this study. $\Psi_{\tau}^{PNucl}$ has a kernel that is not concave and coincides with the notion of the LS prenucleolus in the cooperative game theory. $\Psi_{\tau}^{LnK}$ and $\Psi_{\tau}^{ExK}$ are generated as AFAs from kernels that have desirable properties and consistent with the idea from [6] that the kernel assigns a large weight as a perturbed sample gets closer to the instance being explained.

The extent to which these AFAs show different decomposition patterns in experiments using actual data is an empirical question of great importance and one that should be addressed promptly. Another important theme is how the newly presented $\Psi_{\tau,j}^{LnK}$ and $\Psi_{\tau,j}^{ExK}$ in this study can be characterized from the perspective of cooperative game theory, for example, whether they can be axiomatized, is also worth investigating.