# Ensembles of Random SHAPs
## 4 Modifications of SHAP  
### Ensemble of Random SHAPs  
In spite of the many approaches to simplify SHAP, it is difficult to expect a significant simplification from the above modifications of SHAP. Therefore, a new approach is proposed for simplifying the SHAP method and for reducing computational expenses for calculating the Shapley values. A key idea behind the proposed approach is to apply a modification of the random subspace method [18] and to consider an ensemble of random SHAPs. The approach is very similar to the random forests when an ensemble of randomly built decision trees is used to obtain some average classification or regression measures. Suppose that instance \(\mathbf{x}\in\mathbb{R}^{m}\) has to be interpreted under condition that the black-box model has been trained on the dataset \(D=\{(\mathbf{x}_{1},y_{1}),\ldots,(\mathbf{x}_{n},y_{n})\}\). A general scheme of the first approach called ensemble of random SHAPs (ER-SHAP) for case \(N=3\) is illustrated in Figure 1. ER-SHAP is iteratively constructed by random selection of \(t\) different features \(N\) times. Value \(t\) is a training parameter. If we refer to random forests, then one of the heuristics is \(t\approx\sqrt{m}\). However, the optimal \(t\) is obtained by considering many of its values. Suppose that indices of selected features at the \(k\)-th iteration form the set \(J_{k}=(i_{1},\ldots,i_{t})\). The corresponding vector of \(t\) features is regarded as an instance \(\mathbf{z}_{k}=(x_{i_{1}},\ldots,x_{i_{t}})\in\mathbb{R}^{t}\). Subsets of selected features with indices \(J_{k}\) are shown in Figure 1 as successive features. However, this is only a schematic illustration. Features are randomly selected in accordance with the uniform distribution and can be located at arbitrary places of vector \(\mathbf{x}\). As a result, we have a set of \(N\) instances \(\mathbf{z}_{1},\ldots,\mathbf{z}_{N}\). The next step is to use the black-box model and SHAP to compute Shapley values for every instance such that the subset \(S_{k}=\{\phi_{i}^{(k)}:i\in J_{k}\}\) of the Shapley values \(\phi_{i}^{(k)}\) is produced for instance \(\mathbf{z}_{k}\). Repeating this procedure \(N\) times, we obtain a set \(\mathcal{S}=\{S_{1},\ldots,S_{N}\}\) of the Shapley values corresponding to all \(\mathbf{z}_{k}\), \(k=1,\ldots,N\), or all input subsets of features. Having set \(\mathcal{S}\), we can apply several combination rules to combining subsets \(S_{k}\) from \(\mathcal{S}\). One of the simplest rules is based on averaging of the Shapley values over all subsets \(S_{k}\):  
\[\phi_{i}=\frac{1}{N_{i}}\sum_{k:i\in J_{k}}\phi_{i}^{(k)},\ i=1,\ldots,m, \tag{4}\]  
where \(N_{i}\) is the number of the \(i\)-th feature selections among all iterations, i.e., \(N_{i}=\sum_{k:i\in J_{k}}1\). It should be noted that the input of the black-box model has to have \(m\) features. Therefore, for performing SHAPs with every \(\mathbf{z}_{k}\), average values of features over all dataset \(D\) are used to fill \(m-t\) remaining features, though other methods [13] can also be used to fill these features. Algorithm 1 can be viewed as a formal scheme implementing ER-SHAP. It is supposed that the black-box model has been already trained. Figure 1: A scheme of the ER-SHAP. ```
0: Training set \(D\); point of interest \(\mathbf{x}\); the number of iterations \(N\); the number of selected features \(t\); the black-box model for explaining \(f(\mathbf{x})\)
0: The Shapley values \(S=\{\phi_{1},\ldots,\phi_{m}\}\)
1:for\(k=1\), \(k\leq N\)do
2: Select randomly \(t\) features from \(\mathbf{x}\) and form the set \(J_{k}\) of indices of randomly selected features \(x_{i}\), \(i\in J_{k}\)
3: Use SHAP for computing \(\phi_{i}^{(k)}\), \(i\in J_{k}\) and form the set \(S_{k}=\{\phi_{i}^{(k)}:i\in J_{k}\}\)
4:endfor
5: Combine sets \(S_{k}\), \(k=1,\ldots,N\), to compute \(S\), for example, by using a simple averaging: \(\phi_{i}=N_{i}^{-1}\sum_{k:i\in J_{k}}\phi_{i}^{(k)}\), where \(N_{i}=\sum_{k:i\in J_{k}}1\).