## 3 Background
### Shapley Additive Explanations  
Other widespread feature importance model-agnostic approaches in addition to PI and MDA is SHAP. SHAP is a ML interpretability method that uses Shapley values, a concept originally introduced by [PERSON] [39] in game theory to solve the problem of establishing each player contribution in cooperative games. Essentially, given a certain game scenario, the Shapley value is the average expected marginal contribution (MC) of a player after all possible combinations have been considered. For ML, SHAP determines the contribution of the available features of the model by assessing their every possible combination and by quantifying their importance. The total possible combinations can be represented through a power set. For example, in the case of three features, \(PowerSet\{x,y,z\}\) the power set is \(\{\{\O\},\{x\},\{y\},\{z\},\{x,y\},\{x,z\},\{y,z\},\{x,y,z\}\}\). Furthermore, Figure 1 illustrates the relationships between the elements in the power set.  
SHAP trains a ML model for each of the vertices shown in Figure 1. Therefore, there are \(2^{\text{number of features}}=2^{3}=8\) models trained to estimate the contribution of each feature. The number of models needed to estimate feature importance using SHAP increases exponentially with the number of features. However, there are tools, such as the _Python_ library _SHAP_[40] to accelerate the process through approximations and sampling. The MC of a feature can be calculated by traversing the graph in Figure 1 and by summing up the changes in output where the feature is previously absent from the combinations. For example, to calculate the contribution of feature \(\{x\}\), we can calculate the weighted average of the change in the output from \(\{\O\}\) to \(\{x\}\), \(\{y\}\) to \(\{x,y\}\), \(\{z\}\) to \(\{x,z\}\), and \(\{y,z\}\) to \(\{x,y,z\}\). The MC of a feature \(x\) from \(\{\O\}\) to \(\{x\}\) is as follows:  
\[MC_{x,(\O,x)}(i_{0})=Output_{x}(i_{0})-Output_{\O}(i_{0}) \tag{1}\]  
where the \(Output\) is the output of a ML model, and following Equation (1), we calculate the SHAP value of feature \(x\) of an instance \(i_{0}\), as follows:  
\[\begin{split} SHAP_{x}(i_{0})=& w_{1}*MC_{x,(\O,x) }(i_{0})+\\ & w_{2}*MC_{x,(x,y)}(i_{0})+\\ & w_{3}*MC_{x,(x,z)}(i_{0})+\\ & w_{4}*MC_{x,(x,y,z)}(i_{0})+\\ \end{split} \tag{2}\]  
The process is repeated for each feature to obtain the feature importance. The weights \((w_{1},w_{2},w_{3},\) and \(w_{4})\) in Equation (2) sum to \(1\). The weights are calculated by taking the reciprocals of the number of possible combinations of MC for each row in Figure 1. For example, the weight of \(w_{1}\) is \(\binom{3}{1}^{-1}\). To calculate the global importance of a feature, the absolute SHAP values are averaged across all instances.  
Another approach is the model-agnostic feature importance method called local interpretable model-agnostic explanations (LIME) [41]. We did not choose LIME as a model interpretation method because it does not have a good global approximation of feature importance and it is only able to provide feature importance for individual instances. Furthermore, LIME is sensitive to small perturbations in the input, leading to different feature importance for similar input data [42].