Evaluating the Reliability of Shapley Value Estimates: An Interval-Based Approach

Abstract

Shapley Values (SVs) are concepts used in game theory that have recently found application in Artificial Intelligence. They are exploited to explain models by quantifying the separate features' contribution to the predictor estimates. However, the reliability of the estimated SVs is often not thoroughly assessed. In this context, we leverage Interval Shapley Values (ISVs) to evaluate the importance and reliability of features' contributions when the classifier consists of an ensemble method. This paper presents a suite of ISVs estimators based on exact estimation, linear regression, and Monte Carlo sampling. In detail, we adapt classical SVs estimators to ISV-like concepts to eficiently handle real tabular datasets. We also provide a set of ad hoc performance metrics and visualization techniques that can be used to explore models' results under multiple aspects.

Keywords

• eol>Explainable Artificial Intelligence
• Interval Shapley Values
• Feature Importance

1. 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 diferently. 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 diferent 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 ].

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 diferent estimators. The suite includes approaches to SVs estimation adapted to handle Interval-based scenarios successfully. Specifically, diferently 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.

2. Preliminaries

In a cooperative game, the Shapley Value represents the contribution of a single player to the total payof 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 payof 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 ] ofer a more eficient 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 (, ):

() = [ • Uncertain-Spread Game (, ): () + () () + ()

, 2 2 () = [ − Δ() , Δ() ], ∈ 2 2 2 ], ∈ 2 Hereafter, we focus on two ISLVs definitions based on the Median and Uncertain-Spread games: • Improved ISLVs [ 15 ]: • Reformulated ISLVs [ 6 ]: Φ () = Φ() ⊕ Φ () = Φ () ⊕

ΔΦ () ∑︀∈ ΔΦ () 1 | | ( ) ( ) (1) (2) (3) (4) where ⊕ is the Moore Addition ⊕ = [ − , − ].

3. Suite of Interval-based Approaches

Black-Box Model

Surrogate model

Evaluation & Visualization Explainers

Exact MonteCarlo KernelSHAP Unbiased KernelSHAP

Bar Plot

Coef.

Variance Distances

Times M!

M" M#

M$ M#% :1…||

:1…|| :1…|| !

!

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-VGraupplouTIMe-U-soEIntersnot-Tiuttiidiraittitriseervsati.-An-Interval-Based-Approach. m

A sketch of the suite is depicted in Figjukjre 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 payof for the ensemble method. As discussed in the Preliminaries, the standard formulations of both SVs and ISVs involve evaluating model contributions across diferent 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 UncertainSpread 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 diferent 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.

3.1. 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 eficiency of the estimators in terms of training and inference time. Whenever not otherwise specified, we use the Exact algorithm adaptation as reference ground truth.

3.2. 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 diferent algorithms; (2) A graph plotting the coeficient 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.

4. 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 eficiency. 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.

4.1. Examples of results and visualizations

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 diferent 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.

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.

4.2. Execution times

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 KernelSHAP method provides the best overall results, especially as the number of features in the dataset increases.

5. 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.

References

[1] L. S. Shapley , A value for n-person games , in: H. W. Kuhn, A. W. Tucker (Eds.), Contributions to the Theory of Games II , Princeton University Press, Princeton, 1953 , pp. 307 - 317 .

[2] X. Huang , J. Marques-Silva , The inadequacy of shapley values for explainability , arXiv preprint arXiv:2302.08160 ( 2023 ).

[3] W. Saeed , C. Omlin , Explainable ai (xai): A systematic meta-survey of current challenges and future opportunities , Knowledge-Based Systems 263 ( 2023 ) 110273 .

[4] S. Alparslan Gök , R. Branzei , S. Tijs, The interval shapley value: an axiomatization , Central European Journal of Operations Research 18 ( 2010 ) 131 - 140 .

[5] S. Ishihara , J. Shino, Some properties of interval shapley values: An axiomatic analysis , Games 14 ( 2023 ) 50 .

[6] W. Feng , W. Han, Z. Pan , A reformulated shapley-like value for cooperative games with interval payofs , Operations Research Letters 48 ( 2020 ) 758 - 762 .

[7] D. Napolitano , L. Vaiani , L. Cagliero, Eficient neural network-based estimation of interval shapley values , IEEE Transactions on Knowledge and Data Engineering ( 2024 ).

[8] D. Napolitano , L. Cagliero, Bones: a benchmark for neural estimation of shapley values , 2024 . URL: https://arxiv.org/abs/2407.16482. arXiv: 2407 . 16482 .

[9] L. S. Shapley , Notes on the N-Person Game II : The Value of an N-Person Game , RAND Corporation, Santa Monica, CA, 1951 .

[10] C. Frye , C. Rowat , I. Feige , Asymmetric shapley values: incorporating causal knowledge into model-agnostic explainability , arXiv preprint arXiv: 1910 . 06358 ( 2019 ).

[11] S. M. Lundberg , S.-I. Lee , A unified approach to interpreting model predictions , in: Advances in Neural Information Processing Systems , Curran Associates, Inc., 2017 , pp. 4765 - 4774 .

[12] S. Alparslan Gök , R. Branzei , S. Tijs , Convex interval games , Journal of Applied Mathematics and Decision Sciences 2009 ( 2009 ).

[13] S. Z. Alparslan Gök , Cooperative interval games ( 2009 ).

[14] L. Carpente , B. Casas-Méndez , I. García-Jurado , A. van den Nouweland , Coalitional interval games for strategic games in which players cooperate , Theory and Decision ( 2008 ) 253 - 269 .

[15] W. Han , H. Sun , G. Xu , A new approach of cooperative interval games: The interval core and shapley value revisited , Operations Research Letters 40 ( 2012 ) 462 - 468 .

[16] R. E. Moore , Methods and applications of interval analysis , SIAM , 1979 .

[17] D. Napolitano , L. Vaiani , L. Cagliero , et al., Learning confidence intervals for feature importance: A fast shapley-based approach , in: Workshop Proceedings of the EDBT/ICDT 2023 Joint Conference (March 28-March 31 , 2023 , Ioannina, Greece), 2023 .

[18] N. Jethani , M. Sudarshan , I. C. Covert , S. Lee , R. Ranganath , Fastshap: Real-time shapley value estimation , in: The Tenth International Conference on Learning Representations, ICLR 2022 , Virtual Event , April 25-29 , 2022 , OpenReview.net, 2022 .

[19] I. Covert , S.-I. Lee , Improving kernelshap: Practical shapley value estimation via linear regression , arXiv preprint arXiv: 2012 . 01536 ( 2020 ).

[20] E. Strumbelj , I. Kononenko, Explaining prediction models and individual predictions with feature contributions , Knowledge and Information Systems 41 ( 2014 ) 647 - 665 .

[21] O. Kosheleva , V. Kreinovich , Euclidean distance between intervals is the only representation-invariant one ( 2020 ).

[22] K. Bache , M. Lichman, UCI machine learning repository , 2013 .

[23] F. Pedregosa , G. Varoquaux , A. Gramfort , V. Michel , B. Thirion , O. Grisel , M. Blondel , P. Prettenhofer , R. Weiss , V. Dubourg , J. Vanderplas , A. Passos , D. Cournapeau , M. Brucher , M. Perrot , E. Duchesnay, Scikit-learn: Machine learning in Python , Journal of Machine Learning Research 12 ( 2011 ) 2825 - 2830 .

[24] I. Loshchilov , F. Hutter , Decoupled weight decay regularization , arXiv preprint arXiv:1711.05101 ( 2017 ).

[25] I. Covert , C. Kim , S.-I. Lee , Learning to estimate shapley values with vision transformers , 2023 . arXiv: 2206 . 05282 .