\section{Shapley Feature Importance}

\begin{frame}[c]
\Huge{\centerline{Shapley Feature Importance}}
\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Overview of SHAP: SHapley Additive exPlanations}

	\begin{itemize}
		\item \textbf{What:} SHAP values provide feature importance for a complex model, through numeric values that are easy for humans to understand. 
		\bigskip
		\item \textbf{Why:} SHAP is a unified framework that reveals the relationship between other published interpretability techniques [citations needed], as well as solutions to these techniques that are easier to interpret and satisfy the SHAP properties. 
		\bigskip
		\item\textbf{Examples:}  Interpretability methods that fall under the SHAP framework. \textit{Shapley Feature Importances} explicitly apply SHAP framework and satisfy its constraints, while \textit{LOCO} and \textit{Feature Importance} fall under the SHAP framework but are not designed to satisfy the SHAP Properties. 
	\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{SHAP: SHapley Additive exPlanations (Cont.)}

The following slides summarize and explain the work found in [\cite{shapley}].

\end{frame}
%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Explanation Models}

	\begin{itemize}
	\item \textbf{Explanation models:} a form of surrogate models, explanation models $h$ are designed to provide an interpretable approximation of a complex model. 
	\bigskip
	\item  \textbf{Simplified inputs:} a binary vector $\mathbf{x'}$, of interpretable values, that maps to a given training observation $\mathbf{x}$, through a mapping function $M_\mathbf{x}$ specific to $\mathbf{x}$, such that $\mathbf{x} = M_\mathbf{x}(\mathbf{x'})$.  
	\bigskip
	\item  \textbf{Local methods:} are techniques to explain a model's prediction for a specific observation, as oppose to observations in general.  When a local method works well, $h(\mathbf{z'}) \approx g(M_\mathbf{x}(\mathbf{z'}))$ whenever $\mathbf{z'} \approx \mathbf{x'}$.
	\end{itemize}
	
\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Additive Feature Attribution Methods}
Additive feature attribution methods sum up the feature attributions of an observation  $\mathbf{x}$ to approximate and thereby explain the prediction $g(\mathbf{x})$ corresponding to that observation. 
	\bigskip
	\begin{itemize}
	\item  \textbf{Definition 1}  additive feature attribution methods use an explanation model that is a linear function of binary variables:
	\end{itemize}

	\begin{equation}
	\begin{aligned}		
		h(\mathbf{z'})= \phi_0 + \sum_{j=1}^P \phi_j z'_j,
	\end{aligned}
	\end{equation}
	
	$\phi_j$: each feature's attributed impact, where $\phi_j \in \mathbb{R}$.\\
	$P$: the number of predictors. \\
	$\mathbf{z'}$: the binary vector where $\mathbf{z'} \in \{0,1\}^P$.
	
\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Review of Cooperative Game Theory's Shapley Number}
\begin{itemize}
	\item \textbf{Cooperative Games:} a game in which players benefit from teaming up rather than playing independently. 
	\bigskip
	\item \textbf{The Shapley Number:} a numeric value that determines how much a player should gain or lose, given the number of players and the value attributed to each if they were to play independently. 	\begin{itemize}
		\bigskip
		\item the Shapley Number is easy to calculate when there only a few players: it's the average value of all possible combinations for each player. 
	\end{itemize}
\end{itemize}
\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Shapley Number Axioms}
The Shapley Number calculation is based on the following three axioms:
\begin{itemize}
	\bigskip
	\item \textbf{Efficiency}: the sum of the amounts attributed to each player must equal the total amount attributed to the players when they play together.
	\bigskip
	\item \textbf{Symmetry}: changing the names of players doesn't affect the attributed importance of each player.
	\bigskip
	\item \textbf{Monotonicity:} If the total value of a game increases the value attributed to each player will not decrease. This axiom includes the linearity axiom - the sum of players playing individually has to equal the sum of them playing together - and the null effect axiom - players that don't participate don't contribute to the game. 
\end{itemize}

\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Game Theory Axiom Applied to Machine Learning}
The previous Shapley Number axioms can be applied as constraints to solve a SHAP explanation model. Below are the SHAP properties and their mapping to the Shapley axioms.
	\bigskip
\begin{itemize}
	\item Local Accuracy $\sim$ Efficiency Axiom
	\bigskip
	\item Missingness $\sim$ Null Effect Axiom - adapted to handle missing data
	\bigskip
	\item Consistency  $\sim$ Monotonicity Axiom

\end{itemize}


\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Local Accuracy Property}
To satisfy the local accuracy property, an explanation model $h$ should return the same prediction as the complex model $g$, given a simplified input $\mathbf{x'}$ that maps back to $\mathbf{x}$ via the mapping function $M_\mathbf{x}$. Specifically, 

	\begin{equation}
	\begin{aligned}		
		&\text{if } \mathbf{x} = M_\mathbf{x}(\mathbf{x'}), \phi_0 = g(M_\mathbf{x}(\mathbf{0})),\\
		&\text{and } h(\mathbf{x'})= \phi_0 + \sum_{j=1}^P \phi_j x'_j,\\
		&\text{then } g(\mathbf{x}) = g(M_\mathbf{x}(\mathbf{x'})) = h(\mathbf{x'}).
	\end{aligned}
	\end{equation}


\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Missingness Property}
If a feature value is missing during training, that implies it shouldn't have an attributed effect value. Remember that $x_j' = 0$ means the original input value $x_j$ is not present. 
 
	\begin{equation}
	\begin{aligned}	
		x_j' = 0 \implies \phi_j = 0
	\end{aligned}
	\end{equation}
	
\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Consistency Property}
If a model changes and the change causes a feature to have a larger impact on the model's predicted value for a simplified input (or keep it the same), the feature's new attributed value cannot decrease.\\
\vspace{\baselineskip}
Let $g_\mathbf{x}(\mathbf{z'}) = g(M_\mathbf{x}(\mathbf{z'}))$, and $\mathbf{z'} \: \backslash \: j$ denote setting $z_j' = 0$.\\
\vspace{\baselineskip}
Let  $g$ and $g'$ be any two models, if\\
	\begin{equation}
	\begin{aligned}	
		g_\mathbf{x}'(\mathbf{z'}) - g_\mathbf{x}'(\mathbf{z'} \: \backslash \: j) \geq g_\mathbf{x}(\mathbf{z'}) - g_\mathbf{x}(\mathbf{z'} \: \backslash \: j), \: \forall \: \mathbf{z'} \in \{0,1\}^P,\\
	\end{aligned}
	\end{equation}
then 
	\begin{equation}
	\begin{aligned}			
		\phi_j(g', \mathbf{x}) \geq  \phi_j(g, \mathbf{x})
	\end{aligned}
	\end{equation}



\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Inconsistency}

Several of the other attributed feature importance calculations (gain, permutation, etc) assign inconsistent attribution values, under different models:
	\begin{equation}
	\begin{aligned}	
		g_\mathbf{x}'(\mathbf{z'}) - g_\mathbf{x}'(\mathbf{z'} \: \backslash \: j) \geq g_\mathbf{x}(\mathbf{z'}) - g_\mathbf{x}(\mathbf{z'} \: \backslash \: j), \: \forall \: \mathbf{z'} \in \{0,1\}^P,\\
	\end{aligned}
	\end{equation}
and 
	\begin{equation}
	\begin{aligned}			
		\phi_j(g', \mathbf{x}) <  \phi_j(g, \mathbf{x})
	\end{aligned}
	\end{equation}

Even though the presence of $z_j' $ shows a larger difference for $g'$ then $g$, its attributed effect for the original input $\phi_j(g', \mathbf{x})$, is less. 

\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{SHAP Theorem 1}
\textbf{SHAP Theorem 1}: only one possible explanation model $h$ follows from SHAP Definition 1 and satisfied Properties 1-3:

	\begin{equation}
	\begin{aligned}	
		\phi_j(g,\mathbf{x}) = \sum_{\mathbf{z'} \subseteq \mathbf{x'} } \frac{\left\vert{\mathbf{z'}}\right\vert!(P-\left\vert{\mathbf{z'}}\right\vert-1)!}{P!} \left[g_\mathbf{x}(\mathbf{z'}) - g_\mathbf{x}(\mathbf{z'} \: \backslash \: j) \right]
	\end{aligned}
	\end{equation}

$\left\vert{\mathbf{z'}}\right\vert$: the number of non-zero entries in $\mathbf{z'}$\\
$\mathbf{z'} \subseteq \mathbf{x'}$: represents all $\mathbf{z'}$ vectors where the non-zero entries are a subset of the non-zero entries in $\mathbf{x'}$.
\bigskip
\begin{itemize}
	\item This theorem implies that methods which fall under the explanation model but are not solved in consideration of the Shapley values likely break the local accuracy and/or consistency properties.
\end{itemize}

\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{SHAP Values Overview}

As stated in [\cite{shapley}]: "SHAP values are the Shapley values of the complex model's conditional expectation function. This means that SHAP values attribute to each feature the change in the expected model prediction when conditioning on that feature."\\

\end{frame}


%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{SHAP Approximations}
SHAP values makes the following simplifications and approximations:\\
\bigskip
\begin{itemize}
\item Defined simplified input mapping:
	\begin{equation}
	\begin{aligned}	
		g(M_\mathbf{x}(\mathbf{z'})) = \mathbb{E}\left[ g(\mathbf{z})\right | \mathbf{z}_s ] =  \mathbb{E}_{\mathbf{z}_{\bar{s}} | \mathbf{z}_s }\left[ g(\mathbf{z})\right]
	\end{aligned}
	\end{equation}
	
\item Assumptions of feature independence:
	\begin{equation}
	\begin{aligned}	
		g(M_\mathbf{x}(\mathbf{z'})) \approx  \mathbb{E}_{\mathbf{z}_{\bar{s}}}\left[ g(\mathbf{z})\right]
	\end{aligned}
	\end{equation}
\item Assumptions of model linearity:
	\begin{equation}
	\begin{aligned}	
		g(M_\mathbf{x}(\mathbf{z'})) \approx  g(\left[ \mathbf{z}_s, \mathbb{E} \left[\mathbf{z}_{\bar{s}}\right] \right])
	\end{aligned}
	\end{equation}
\end{itemize}
Where $M_\mathbf{x}(\mathbf{z'}) = \mathbf{z_s}$, $S$ is the set of non-zero indexes in $\mathbf{z'}$, and $\bar{S}$ is the set of features not in $S$.

\end{frame}


%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{SHAP Values For Tree Ensemble Feature Attributions}

Given  
	\begin{equation}
		\begin{aligned}	
		g_\mathbf{x}(S) = g(M_{\mathbf{x}}(\mathbf{z'}))= \mathbb{E}\left[ g(\mathbf{x})\right | \mathbf{x}_s ]
		\end{aligned}
	\end{equation}

where $S$ is the set of non-zero indexes in $\mathbf{z'}$ and $ \mathbb{E}\left[ g(\mathbf{x})\right | \mathbf{x}_s ]$ is the expected value of the function conditioned on a subset of $S$ input features. We can calculate the attribute value $\phi_j$ of each feature:

\begin{equation}
	\begin{aligned}	
\phi_j(g,\mathbf{x}) = \sum_{S \subseteq P \: \backslash \: \{j\}} \frac{\left\vert{S}\right\vert!(P-\left\vert{S}\right\vert-1)!}{P!} \left[ g_\mathbf{x}(S \cup \{j\}) - g_\mathbf{x}(S) \right]
	\end{aligned}
	\end{equation}

again, $P$ is the set of all features, so $P \: \backslash \: \{j\}$ removes the $jth$ feature from the set.
\end{frame}

%----------------------------------------------------------------------------------------

\begin{frame}\frametitle{Some techniques that fall under Additive Feature Attribution Methods}
Each of the following interpretability techniques, are specific implementations of the SHAP explanation model. 
	\begin{itemize}
		\item LOCO
		\item Tree-Interpreter
		\item LIME
		\item DeepLIFT
		\item Layer-Wise Relevance Propagation
		\item Shapley Regression Values
		\item Shapley Sampling Values
		\item Quantitative Input Influence
	\end{itemize}
\end{frame}



