## 2 Theoretical Background
### Shapley Values  
The Shapley values [92] were introduced to assign pay-outs to players depending on their contribution towards the total playout, but they can be effectively used to measure the global importance of a feature. Shapley values can be explained by using the game theory as follows: given a cooperative game with \(d\) players aiming at maximising a payoff and letting \(S\subseteq M=\{1,\ldots,d\}\) be a subset of \(|S|\) players, the contribution function \(\
u(S)\), which maps a subset of players to the real number, called the contribution of coalition \(S\), describes the total expected sum of payoffs that the member of \(S\) can obtain by cooperation. Thus, Shapley values embody a method to distribute the total gains to players. The amount that player \(j\) earns is given by Equation (13) [53]:  
\[\phi_{j}(\
u)=\phi_{j}=\sum_{S\subseteq M\setminus\{j\}}\frac{|S|!(d-|S|-1)!}{ d!}(\
u(S\cup\{j\})-\
u(S)),\;\;j=1,\ldots,d \tag{13}\]  
This expression is a weighted mean over the contribution functions differences for all subsets \(S\) of players not containing player \(j\). The algorithm also accounts for the non-distributed gain \(\phi_{0}=\
u(\varnothing)\). In the ML theory, single predictions take the place of a pay-out, and features become the players. The main properties of the Shapley values can be summarised as follows [93]. * _Efficiency_: the total gain is distributed \(\sum\limits_{j=0}^{d}\phi_{j}=\
u(M)\);
* _Symmetry_: if \(i\) and \(j\) are two players that contribute equally to all coalitions, then their Shapley value is the same \(\
u(S\cup\{i\})=\
u(S\cup\{j\})\rightarrow\phi_{i}=\phi_{j}\);
* _Dummy player_: if a player does not contribute to any coalitions, then his Shapley value is zero \(\phi_{j}=0\);
* _Monotonicity_: if two games \(v\) and \(v^{\prime}\) and a player always makes a greater contribution to \(v\) than to \(v^{\prime}\) for all S, then the gain for \(v\) will be greater than that for \(v^{\prime}\)\(\
u(S\cup\{i\})-\
u(S)\geq\
u^{(S\cup\{i\})}-\
u^{(S)}\;\forall S\; \rightarrow\;\phi_{i}(v)\geq\phi_{i}(v^{\prime})\);
* _Linearity_: if two coalition games described by the gain functions \(v\) and \(w\) are combined, the distributed gain is the sum of the two gains is \(\phi_{j}(v+w)=\phi_{j}(v)+\phi_{j}(w)\). This is valid also for a multiplication by a constant value \(\alpha\), \(\phi_{j}(\alpha\;v)=\alpha\;\phi_{j}(v)\). Given a training set of \(N\) labelled samples \(D=\{(\mathbf{x}_{1},y_{1}),\ldots,(\mathbf{x}_{N},y_{N})\}\) used to train a predictive ML model \(f(\mathbf{x})\) whose outcome should be as close as possible to label \(y\), Shapley values can be used to explain the prediction \(y^{*}=f(\mathbf{x}^{*})\) for a specific feature vector \(\mathbf{x}=\mathbf{x}^{*}\). The prediction can be written as reported in Equation (14):  
\[f(\mathbf{x}^{*})=\phi_{0}+\sum\limits_{j=1}^{d}\phi_{j}^{*} \tag{14}\]where \(\phi_{0}=\mathbb{E}[f(x)]\) and \(\phi_{j}^{*}\) is the \(\phi_{j}\) for \(x=x^{*}\). Therefore, Shapley values explain the difference between the prediction \(y^{*}=f(x^{*})\) and the global average prediction. For the computation of the Shapley values for a prediction explanation, the contribution \(v(S)\) for a certain subset \(S\) must be defined. This function should take values similar to \(f(x^{*})\) when only the value of the subset S of these features is known. As cited by [PERSON] [47], the expected output of the predictive model of Equation (15), conditional to the feature values \(x_{S}=x_{S}^{*}\) of this subset, can be used:  
\[v(S)=E[f(x)|x_{S}=x_{S}^{*}] \tag{15}\]  
Thus, the conditional expectation summarises the whole probability distribution and, if it is considered the prediction for \(f(x^{*})\), it is also the minimiser of the squared error loss function. There are two main algorithms for the computation of the Shapley: the KernelSHAP and the extension to the KernelSHAP method.