Introduction

Shapley Values (SVs), originally formulated in coalition game theory [1], are now widely used to generate post-hoc explanations for classifiers that assign discrete classes to unlabeled samples. In detail, SVs quantify the contribution of each input feature to a given classifier's prediction and, although they may not always accurately reflect feature importance [2], these contributions can be estimated on a per-sample basis (locally) or aggregated to provide insights into the overall behavior of the model (globally) [3].

When a model comprises multiple predictors, estimating the contributions of individual features becomes challenging, as each feature may influence each predictor differently. In some cases, certain predictors might entirely disregard features crucial to others. This implies that the performance provided by the various predictors can vary substantially, directly reflecting on the contributions made by the various features. Therefore, taking into account the contribution of each predictor makes the explanations robust to variability in the estimates (see Figure 2).

To model the variability of SVs across multiple predictors, we rely on the concept of Interval Shapley Values (ISVs) [4]. Derived from the field of cooperative interval games, they can be used to estimate SVs in the presence of uncertainty by encompassing different predictor outcomes, which are neglected in standard SVs. To ensure tractable and scalable computation on real data, we focus on Interval Shapley-Like Values (ISLVs), known to approximate ISVs [5,6].

HI-AI@KDD, Human-Interpretable AI Workshop at the KDD 2024, 26 𝑡ℎ of August 2024, Barcelona, Spain davide.napolitano@polito.it (D. Napolitano); luca.cagliero@polito.it (L. Cagliero)

Hereafter, we present a suite of algorithms adapted to explain combinations of predictors with ISLVs. They indicate the features' importance for the ensemble method's outcomes by explicitly indicating the reliability of such estimates. This is crucial to trust models' explanations and compare the outcomes of different estimators. The suite includes approaches to SVs estimation adapted to handle Interval-based scenarios successfully. Specifically, differently from the neural approaches proposed in [7], we focus on a linear regressor, a Monte Carlo sampling strategy, and an Exact estimator, aiming to incorporate all implementations in BONES [8] library. To allow end-users to explore and compare the outcomes of Interval-based approaches, the suite supports ad hoc performance metrics, extended from the standard SVs scenario to support interval-level evaluations. The metrics can be visualized to ease model comparisons and complexity analysis.

The remainder of this paper is organized as follows. Section 2 introduces the preliminary notions. Section 3 describes the suite of Interval-based approaches. Section 4 shows examples of outcomes and comparisons. Finally, Section 5 draws the conclusions of the work.

Preliminaries

In a cooperative game, the Shapley Value 𝜑 𝑖 represents the contribution of a single player 𝑖 to the total payoff of a group of player 𝑃 [9], where 𝜑 𝑖 is equal to the sum of the weighted marginal contributions of 𝑖 to 𝑃 over all possible player's coalitions 𝑆 ⊆ 𝑃 . Beyond explaining an individual sample 𝑥, Shapley Values can be leveraged to provide a global explanation of the dataset by averaging sample-level contributions [10,11].

Suppose to have the outcome 𝑝𝑟 𝑥 of an ensemble M of predictors on a sample 𝑥 with a confidence interval [𝑝𝑟 𝑥 , 𝑝𝑟 𝑥 ]. In compliance with [4], we define the Coalitional Interval Game [12,13] as a pair (𝑤, 𝑆), where 𝑤: 2 𝑃 → 𝐼(R)is a function that maps an arbitrary coalition 𝑆 ⊆ 𝑃 to the corresponding confidence interval 𝑤(𝑆): [𝑤(𝑆), 𝑤(𝑆)] = [𝑝𝑟(𝑆), 𝑝𝑟(𝑆)].

To explain ensemble methods we use the concept of Interval Shapley Values (ISVs) [4] associated with each Coalitional Interval Game (𝑤, 𝑃 ) to a payoff vector where each component is a compact interval of real numbers [14]. In a nutshell, ISVs capture the range of contributions of a feature 𝑝 by evaluating the interval values across all possible feature combinations. ISVs have to satisfy two notable properties:

• Partial Subtractor: given two intervals 𝐼 and 𝐽, the Partial Subtraction 𝐼 − 𝐽 is defined as

[𝐼 − 𝐽, 𝐼 − 𝐽] only if Δ 𝐼 ≥ Δ 𝐽 , where Δ is the interval width: 𝐼 = [𝐼, 𝐼] → Δ = 𝐼 − 𝐼.

• Size Monotonicity: ISVs can be defined only when the Coalitional Interval Game (𝑤, 𝑃 ) is size monotonic, i.e., when Δ𝑤(𝑆) ≤ Δ𝑤(𝑇 ) for all 𝑆, 𝑇 ∈ 2 𝑃 with 𝑆 ⊂ 𝑇 .

Since the ISVs constraints are computationally intractable [9,15], Interval Shapley-Like Values [15] offer a more efficient yet approximated approach to ISVs estimation. ISLVs adopt the Moore operators [16], in detail the Moore Subrtractor is used rather than the Partial Subtractor operator, i.e., given two intervals 𝐼 and 𝐽 the Moore subtraction is defined as 𝐼 ⊖𝐽 = [𝐼 −𝐽, 𝐼 − 𝐽]. To simplify the estimation [15], the Median and Uncertain-Spread games are introduced:

• Median Game (𝑤 𝑚 , 𝑃 ):

𝑤 𝑚 (𝑆) = [ 𝑤(𝑆) + 𝑤(𝑆) 2 , 𝑤(𝑆) + 𝑤(𝑆) 2 ], 𝑆 ∈ 2 𝑃(1)

• Uncertain-Spread Game (𝑤 𝑢 , 𝑃 ):

𝑤 𝑢 (𝑆) = [ −Δ𝑤(𝑆) 2 , Δ𝑤(𝑆) 2 ], 𝑆 ∈ 2 𝑃 (2)

Hereafter, we focus on two ISLVs definitions based on the Median and Uncertain-Spread games:

• Improved ISLVs [15]:

𝐼Φ 𝐼 𝑖 (𝑤) = Φ 𝐼 𝑝 (𝑤 𝑚 ) ⊕ ΔΦ 𝐼 𝑖 (𝑤 𝑢 ) ∑︀ 𝑝∈𝑃 ΔΦ 𝐼 𝑖 (𝑤 𝑢 ) 𝑤 𝑢 (𝑃 )(3)

• Reformulated ISLVs [6]:

𝑅Φ 𝐼 𝑖 (𝑤) = Φ 𝐼 𝑖 (𝑤 𝑚 ) ⊕ 1 |𝑃 | 𝑤 𝑢 (𝑃 )(4)

where

⊕ is the Moore Addition 𝐼 ⊕ 𝐽 = [𝐼 − 𝐽, 𝐼 − 𝐽].

Suite of Interval-based Approaches

Gruppo TIM -Uso Interno -Tutti i diritti riservati.

Evaluation & Visualization Explainers Surrogate model We present a suite of SVs estimators adapted to handle Interval-based estimations on tabular data. To successfully explain ensembles of predictors, the suite integrates adaptations of existing algorithms that produce Improved [15] and Reformulated [6] estimates of ISLVs instead of classical SVs. The suite is available for research at the link: https://github.com/DavideNapolitano/ Evaluating-the-Reliability-of-Shapley-Value-Estimates-An-Interval-Based-Approach.

M ! M " M # M $ M #%

A sketch of the suite is depicted in Figure 1.The black-box model M to be explained consists of an ensemble of 𝑁 independent predictors, which are all trained on a labeled relational dataset. For every instance 𝑥 to be classified, each predictor returns its corresponding per-class output probabilities, which are then used to compute the confidence interval to retrieve an interval payoff for the ensemble method. As discussed in the Preliminaries, the standard formulations of both SVs and ISVs involve evaluating model contributions across different subsets of features. Since most of the existing models do not support holding out subsets of features, similar to [7,17], we exploit a surrogate model to approximate the original model considering subsets of features, thus allowing the subsequent normalization of ISLVs similar to [11,18].

To adapt traditional SVs-based explainers to ISLVs, we leverage the Median and Uncertain-Spread games according to the Improved [15] and Reformulated [6] ISLVs formulations.

Median game

The ISLVs can be expressed as a single value since the characteristic function 𝑤 𝑚 is defined as an interval with equal interval endpoints. This approach allows the estimation to be performed using established methods. Subsequently, the interval can be reconstructed in the next step when defining the ISLVs.

Uncertain-Spread game Since the minimum and maximum values returned by the characteristic function 𝑤 𝑢 are opposites (i.e., same value, opposite sign), the ISLVs estimation can be simplified by applying the addition operation, rather than the subtraction, upon the single absolute value. This consideration is exemplified in Equation 5, where the subtraction is reconducted to the addition of the absolute values retrieved from different subsets 𝑆 applied on 𝑤 𝑢 .

𝑤 𝑢 (𝑆 1 , 𝑥) = [−𝑣 1 , 𝑣 1 ], 𝑤 𝑢 (𝑆 2 , 𝑥) = [−𝑣 2 , 𝑣 2 ] 𝑤 𝑢 (𝑆 1 , 𝑥) ⊖ 𝑤 𝑢 (𝑆 2 , 𝑥) = [−𝑣 1 − 𝑣 2 , 𝑣 1 + 𝑣 2 ] = [−(𝑣 1 + 𝑣 2 ), 𝑣 1 + 𝑣 2 ](5)

Therefore, since managing the computation with a single value, we can reconduct the estimation to the traditional SVs formulation. In this way, classical predictors can be directly exploited to retrieve the absolute values and, following, to reconstruct the desired Φ 𝐼 𝑖 (𝑤 𝑢 ). Based on the considerations above, we adapt the following algorithms to support ISLVs: the Exact explainer [11], Unbiased and Biased KernelSHAP [19] and Monte Carlo sampling [20]. For each algorithm, we separately implement adaptations based on Median and an Uncertain-Spread, namely the Improved [15] and Reformulated [6] versions.

Performance metrics

Given the algorithms' outcomes achieved on a relational dataset, the suite allows the quantitative evaluation of (1) The accuracy of the intervals estimated by each algorithm against a ground truth in terms of (a) the 𝐿2 distance between the mean points, or (b) the 𝐿2 distance between the interval widths, or (c) the Euclidean distance between the intervals [21]. (2) The efficiency of the estimators in terms of training and inference time. Whenever not otherwise specified, we use the Exact algorithm adaptation as reference ground truth.

Outcome visualizations

The suite supports the following graphical visualization of the experimental results achieved on a test dataset: (1) A bar plot showing the per-feature intervals, which may allow a direct comparison between different algorithms; (2) A graph plotting the coefficient of variation of the ISVs (width over mean point), which provides insights into the reliability of the generated estimated; (3) A plot showing the computational times for model training and inference by varying the dataset size and dimensionality.

Preliminary results

We show examples of outcomes achieved on four relational datasets taken from the UCI repository [22] namely Monks, Bank, Wisconsin Breast Cancer, and Diabetes. We explain a Random Forest Classifier with 100 predictor trees, implemented in the Scikit-learn library [23]. We generate the confidence interval (with confidence level 𝛾 = 0.95) from the prediction of each tree. Then, we approximate the predictions of the black-box model using a Multi-Layer Perceptron (MLP) as a surrogate model. Similar to [17,7], MLP consists of three linear layers, each one with a hidden size of 512 units, interspersed with Rectified Linear Unit (ReLU) activation functions, and with two final classification heads. The surrogate model was trained for up to 200 epochs using the Kullback-Leibler divergence loss function. The training utilized the AdamW optimizer [24], with a learning rate of 10 −4 , a batch size of 8, and a weight decay of 10 −2 .

Regarding the explainers implementation, the baselines of Median and Uncertain-Spread Exact explainers are trained on 100 samples. Concerning the Monte Carlo approach, the number of iterations is set to 1000. For the KernelSHAP-based methodologies, we adopt the marginal models' approach as outlined in [25]. Specifically, the Median marginal model was configured with 20 baseline samples, while the Uncertain-Spread marginal model was allocated 8 baseline samples. These sample sizes were carefully chosen to strike a balance between achieving accurate estimations and maintaining computational efficiency. Indeed, higher values lead to comparable results but with longer times, while lower values, although providing shorter times, give worse estimates. Moreover, regarding the iteration parameters of the two regression-based methods, the results are retrieved by testing all datasets with a threshold of 0.1 and a kernel iteration value of 128. In this section, we present a comparative analysis of the proposed models based on various metrics. In detail, the table results are shown as confidence intervals computed on 5 different runs with a machine equipped with an AMD Ryzen 7950X CPU. Table 1 illustrates the comparison of ISLVs with respect to the mean point and interval width. The results indicate that the outputs of Unbiased KernelSHAP and Monte Carlo Sampling best approximate the Exact model, with Unbiased KernelSHAP yielding superior results in terms of amplitude precision.

Examples of results and visualizations

Moreover, Table 1 reports the results exclusively for the Improved models (denoted with the prefix I-), as they share mean points with the Reformulated models (denoted with the prefix R-), and the interval amplitudes for the latter remain invariant regardless of the approach. Similar takeaways can be derived from examining the Euclidean distances of the intervals presented in Table 2, where the Improved and Reformulated approaches yield similar rankings.

Execution times

Table 3 compares the inference times per sample spent by all analyzed approaches separately for each tested dataset. The reported statistics show that the Reformulated ISLVs are overall faster compared to the Improved ones. Moreover, the results show that the Reformulated regression-based approach outperforms the other ones when the number of features increases. Summarizing the results, the Reformulated Unbiased KernelSHAP and Monte Carlo approaches yield comparable outcomes on the distances, with the former being favored for Improved ISLVs. Furthermore, considering inference times, the Reformulated Unbiased Ker-nelSHAP method provides the best overall results, especially as the number of features in the dataset increases.

Conclusions and future developments

The paper presented a suite of SVs estimators adapted to explain ensembles of predictors using ISVs. To estimate both importance and reliability of the features' contributions to the blackbox model estimates, we adapt three classical SV estimators to handle Intervals of Shapley Values by leveraging the concepts of Interval Shapley-Like Values. The suite allows researchers and practitioners to interact with Interval-based approaches and evaluate them using ad hoc performance metrics and visualizations.

In future work, we plan to investigate approaches not relying on surrogate models, to analyze new sampling techniques, and, most importantly, to extend this technique to other data modalities and in multimodal analyses, such as text and images combined.