BELLA: Black-box model Explanations by Local Linear Approximations
Authors: Nedeljko Radulovic
Albert Bifet
Fabian M. Suchanek
Venue: Accepted by TMLR ()

Abstract: Understanding the decision-making process of black-box models has become not just a legal requirement, but also an additional way to assess their performance. However, the state of the art post-hoc explanation approaches for regression models rely on synthetic data generation, which introduces uncertainty and can hurt the reliability of the explanations. Furthermore, they tend to produce explanations that apply to only very few data points. In this paper, we present BELLA, a deterministic model-agnostic post-hoc approach for explaining the individual predictions of regression black-box models. BELLA provides explanations in the form of a linear model trained in the feature space. BELLA maximizes the size of the neighborhood to which the linear model applies so that the explanations are accurate, simple, general, and robust.

Published in Transactions on Machine Learning Research (08/2025)
BELLA: Black-box model Explanations by Local Linear Approximations
Nedeljko Radulovié Telecom Paris, Institut Polgtechnique de Paris, France
Albert Bifet
alberttbijeed@hcccccommppprrr
Telecom Paris, Institud Polgtechnique de Paris, France
Fabian M. Suchanek
Telecom Paris, Institut Polytechnique de Paris, France
Reviewed on OpenReview: https: // openreview. net/ formm? F9KV99K
Abstract
Understanding the decision-making process of black-box models has become not just a legal requirement, but also an additional way to assess their performance. However, the state of the art post-hoc explanation approaches for regression models rely on synthetic data generation, which introduces uncertainty and can hurt the reliability of the explanations. Furthermore, they tend to produce explanations that apply to only very few data points. In this paper, present BELLA, deterministic model-agnostic post-hoc approach for explaining the individual predictions of regression black-box models. BELLA provides ex- planations in the form of linear model trained in the feature space. BELLA maximizes the size of the neighborhood to which the linear model applies so that the explanations are accurate, simple, general, and robust.
1 Introduction
Machine Learning (ML) and Artificial Intelligence (AI) models have been employed to handle lasks in various domains, including justice, healthcare, finance, self-driving cars, and many more. Consequently, legislative regulations have been proposed to protect interested partios and control the usage of those models. One example the General Data Protection Regulation of the European Union (Goodman and Flaxman 2017). which stipulates the right to an explanation in situations where an AT system has been employed in a decision- making process. The Al act (European Parliament and Council of the EU 2024), too, has stipulated the transparency of AI models according to the level of risk they pose.
The main issue is that many ML. models are black-box models, i.c. one cannot easily understand how they arrive at decision. This has led to the emergence of explainable Artificial Intelligence (xAI), a research field that aims to make black-box models human-underss undnraaddddett..aaalll... In this paper, we are concerned with understanding regression models, i.e., models that make a numerical prediction. We are interested explaining a given prediction of such a model post-hoc, i.c., after has been produced. This usually done by building an interpretable surrogate-mode (e.g., decision tree) that mimics the black-box model and that can be used to understand the prediction.
Numcrous approaches have been proposed to build such surrogate models, in particular SHAP LLnddbegg and Lee 2017), LIME (Ribeiro el al. 2016), and MAPLE (Plumb et al. 22018). We review them in Section 2 To evaluate the surrogate models, several criteria have been proposed: we want the surrogate model to be accurate, i.c., to reflect the predictions of the black-box model; we want it to be simple, i.c., use few features; we want to be robust, ie., giving similar explanations to similar data points; and we want it to be general, ie., applicable to many data points. We survey these desiderata. in Section 3 We find that

---

Published in Transactions on Machine Learning Research (08/2025)
existing approaches tend to be good some of these criteria, but never excel on all of them. This is not surprising, as the desiderata stand in obvious conflict: A simple surrogate model, e.g., risks being not very accurate, because usually accurate predictions can be made only by the type of complex models that we wish to explain in the first place.
Our key idea (which we present in Section 4 to train a local linear model on the neighborhood of the data point that we wish to explain. This allows us to develop an approach called BELLA (Black-box model Explanations by Local Linear Approximations). We can show through extensive experiments (in Section 5 a dozen datasets that BELLA beats all existing approaches across nearly all desiderata.
2
Related Work
Explainable AI has received much attention in the scientific literature [Beaudouin et al. 2020 Guidotti et al.
2018 Adadi and Berrada, 2018: Murdoch et al. 2019 Burkart and Huber 2021] Hassija et al. 2024). In this paper, we are interested in post-hoc approaches, i.c., those that add interpretability to a given black-box
model. Some of these approaches have been developed specifically for a given type of learners (such as Gat et al. (022)) for neural models). However, are interested in model-agnostee approaches, i.., those that interpret any black-box model. Some model-agnostic approaches compute feature importance (Chen et al.
2018 Bang et al.] 2021). However, these approaches do not allow explaining unseen data points. Hence, we focus on approaches that build a surrogale model, i.e., a model that mimics the black-box model but that is interpretable by design (e.g., a decision tree). While global methods provide an interpretation of the black-box model behavior on the whole space, local models provide an interpretation for a single data point. In this paper, we are interested model-agnostic post-hoc local explanations for regression models, i..,, we aim to provide an explanation for a given real-valued decision by any type of model for a given data point. We are thus not interested in approaches that work for classification only (Vo et al. 2022 Mothilal et al. 2020
Bui et al. 2022 Vo et al. 2023).
One approach to deal with regression models is to adjust the methods for classification models (such as LORE (Guidotti et al. 2019)), e.g., by discretization or clustering. However, this loses information and may require domain knowledge. Therefore several approaches have been developed to natively support both classification and regression models: SHAP (Lundberg and Lee, 2017) introduces game theory approach to compute the contribution of cach feature. The explanation applics to single data point and it is given as a linear combination of the feature contributions. In order to improve computation time, AcME (Dandolo el al. 2023) computes feature contributions based on the perturbations based on data quantiles. LIME (Ribeiro ct al. 2016) generates synthetic data points by feature perturbations. This yiclds a weighted neighborhood that is used to train a linear model, whose coefficients are then used as an explanation. However, both LIME and SHAP compute feature contributions in a projected, binary, space, which does not correspond to the original feature space. MAPLE (Plumb et al. 2018) addresses this problem and uses Random Forests to assign weights to the training examples. In this way, it forms a weighted neighborhood on which the explanation applies. SHAP, LIME, and MAPL.E are direct competitors to our method BELLAA, and we will see in our experiments that BELLA outperforms all of them on the quality of the explanations.
DLIME Zafar and Khan 2019 is a deterministic variant of LIME that provides stable and consistent explanations. However, requires extensive manual input, as the user has to provide the number of clusters for the hicrarchical clustering step, the number of neighbors for the KNN stop of the method, and the length of the explanation. As such, DLIME is not well suited for regression tasks and was thus applied only to classification.
Another group of approaches computes counterfactual explanations. One such method White and Garcez, 2019) uses the idea of b-counterfactuals, i.e., the minimal change in the feature to gauge the prediction of the complex model. This method applies only to classification tasks. Another work (Dandl et al., 2020) uses Multi-Objective Optimization to compute counterfactual explanations, both for classification and regression. Another work (Redelmeier et al. 2021] uses Monte Carlo sampling for the same purpose. However, we focus factual explanations in this paper.
2

---

Published in Transactions on Machine Learning Research (08/2025)
3 Preliminaries
Goal. We are given tabular dataset T C x.....x x Fn, where each F; is a set of feature values. For example, a feature for a real estate dataset could be the size of the lot in square meters, and the set of feature values would then be Rt. We are also given a function Y : T + R that yields, for each æ E T, a label (x) E R. In our example, the labels can be the prices of the houses. These labels may, e.g., have been produced by a black-box model, in which case the label prediction. Consider now one data point x E T with its label (ar). We aim to compute explanation in the following sense (Das and Rad 2020):
Definition 1 An explonation is additional meta-informati generated by an external algorithum or by the machine learning model itself, to describe the feature importance or relevance of on input instance towards parlicular oulpul classisication.
If the label was produced by a black-box model, we cannot be sure post-hoc that the features we identify really contributed the computation of the label (the model may just as well have thrown a dice, independently of any feature values). However, if several data points with these similar feature values produce similar use abductive reasoning to infer that these features may have contributed to the prediction, and that, hence, the fcatures constitute an explanation. This is in fact common in the litcrature (Ribeiro
prediction,
et al. 2016 Lundberg and Lee 2017 Radulovic et al. 2021 Ignatiey et al. 2019
Quality measures. Several properties of "good" explanations have been proposed. Some of them, such as plausibility and accordance with prior beliefs, require huraan evaluation. Among the criteria that do not, we commonly find (Miller 2019
Guidotti et al. 2018 Burkart and Huber 2021 Molnar 2018):
Fidelity: we want the value that the surrogate model explains to be close to value that the black-box model predicts.
2. Simplicity: we want the explanation to contain few features.
3. Robustness: we want similar data points to have similar explanations.
In addition, users tend to favor explanations that apply to many data points (Radulovic et al. 2021). This we aim to explain only single data point, no maller the others. And yet, it
appears counter-intuilive, is easy to see that an explanation such as "You have high risk of diabetes because your body mass index is 27, your A1C level is 7%, and your blood sugar level is 210mg/dL is little satisfactory, as it allows no generalization. More helpful is to know that, generally, people with a body mass index larger than 25, an ATC level above 6.5%, and a blood sugar level of 200 mg/dl. have a high risk of diabetes (Mayo-Clinis 2023 We would thus like to have:
4. Generality: we want the number of data points to which an explanation applies to be large.
Additional desiderata. In addition to the above scalar quality measures, there are also criteria in the literature that either apply or don't apply to a given method of explanation. For example, several methods for post-hoc explainability use randomization to probe the black-box model. However, this entails that the same data lead to different explanations, which introduces uncertainty for the user (Zhang et al. 2019: We thus have as desidcratum:
Slack et al. 2020).
Determinism: the avoidance of randomization steps
Furthermore, some methods (Plumb et al. 2018) propose explanations that take the form of a linear equation, which allows computing the predicted value from the feature values. This very attractive property, as the user can toy with the explanation and apply it also to neighboring data points. We thus have desideratum that we call
6. Verifiability: the possibility to compute the predicted value from the feature values
3

---

Published in Transactions on Machine Learning Research (08/2025)
Given this number of quality measures and desiderata, it is not surprising that no existing method (inchuding our own) can satisly all of them perfectly. However, we can at least show that our method ticks all desiderata, and outperforms existing methods across nearly all quality measures.
4 BELLA
We are given a tabular dataset T, real-valued labels Y T - compute an explanation for the label (x). Note that, different from other methods such as LIME and SHAP, we need as input only the dataset and the labels Y on T. and not in addition also the model that generated the labels Y. This means that, different from SHAP and LIME, our method can explain any labeled dataset, whether the labels were produced by a model source (e.g,, housing prices from real estate data). If BELLA is to explain model, first run the model on the training dataset. We then use as labels Y not the ground truth from the training dataset, but the predictions of the model.
- IR, and a data point I E T, and we aim to
whether they come from any other
To explain the label Y (xx), our idea to find a linear equation Y(x) R wi I1 + W2 T2 + + wi 24 + Wi: where wi are real-valued regression coefficients and 2; are feature values of in T. Such an equation tells the user (1) what the important features are and (2) how they can be used to compute the predicted value. To find this equation, BELLA proceeds in three steps (Algorithm 1
1. Compule the distance of x to the other points in T.
Conduct a linear search find the best neighborhood of æ, according a defined metric.
3. Train a sparse linear model on that neighborhood, and propose this model as an explanation.
Algorithm BELLA
Input: Dataset T with labels
Labeled data point
d ComputeDissannes((:: T)
L,N NeighborhooddSeacch(t, d,
return L, N
Step 1: Computing the distances. To compute the neighborhood of the input data point, we need distance measure. A good starting point is to have all numerical features the same scale so that each feature contributes to the distance measure in the same range. Therefore, we first standardize all numerical features to have a mean of 0 and a standard-deviation of 1.
To compute the distances, we employ the generalized distance function (Harikumar and Surya 2015), which consists of three separate distance measures to account for numerical, categorical, and binary data types, as follows:
me W-ln Σ
d(x, xx)
Σ iml
d (Ii, vi)
x1),
do(22,,21 241
(1)
8 www.-----mmm.... +
Here, Moam: me and my are the number of numerical, categorical, and binary features, respectively. The distance measure for the numerical attributes drum the L1 norm (x, x') |r x'), which is preferred over L2, as it more robust to outliers (Hopcroft and Kannan 2014). For categorical features, de is the distance measure (Ahmad and Dey] 2007), which takes into account the distribution of values and their
4

---

Published in Transactions on Machine Learning Research (08/2025)
Figure 1: Left: an explanation for a data point a that is too specific, applying only to a very small neigh- borhood. Right: An explanation that applics to a larger neighborhood, which what we aim at.
co-occurrence with values of other attributes. The distance between two values and a' of an attribute A, with respect to attribute Aj is given by:
(a,a'') = P(A, E E| a) P(A, & w|A, d')
Here, P(A, E EW|A, = a) is the conditional probability that attribute A will take a value from the set w given that the attribute A; takes the value a. is a subset of all possible values of attribute Aj that maximizes the sum of the probabilities. Since both probabilities can take values from [0, 1], we subtract in order to arrive at dz(xx (x,x²) [0, 1]. Lastly, for binary features, x = x', and zero otherwise. In Line 1 of Algorithm [ the function ComputeDistances returns the distances by Equation ! Note that our distance measure does not take the label into account. This is because there can be data points with different feature values and a similar prediction. In such cases, BELLA provides the explanation for the "correct" local neighborhood.
use the Hamming distance: dx,zx²)) 1 if
Step 2: Neighborhood Search. After computing the distances, we proceed with the exploration of the neighborhood of the input data point x. The goal is to find set of points, closest to according to the distance measure, that will serve could be considered to that end, including kNN, K-Mcans, and other distance-baser clustering methods. In our case, however, we aim to find a neighborhood such that a linear regression model trained on that neighborhood represents an accurate local approximation of the black-box model. Hence, the quality of the neighborhood is proportional to the quality of the performance of the linear model fitted on it. Common drawbacks of regression evaluation metries are missing interpretability, sensitivity to outliers and near-zero values, divisions by zero, missing bounds, and missing symmetry. We find that the Berry-Mielke universal R value R (Berry and Mielke Jr. 1988) avoids most of these pitfalls. R represents the measure of agroement between raters and it is general generalization
training set for local surrogate model. Several common techniques
lization of Cohen's 's kappa (Cohen 1960). R measures how much better the model is compared to a naive one (e.g., to a random predictor). R takes values from the range [0, 1], and it can be interpreted casily: If R is equal to O, the model performance is equal to the one of the random model and if it is 1, then the model has perfect performance. R defined as R = 1 fo where ö and μ are defined as:
1 N
1 N
8
(...)),
P
(0g, V.)-
(2)
Here, N is the number of samples, ys is the actual label, 0r is the predicted value, and A(-) represents the distance function between the true and the predicted value. The original work by (Berry and Mielke Jr. 1988) uses the Euclidean distance, but later works [Janson and Olsson 2001 2004) propose to use the squared Euclidean distance instead, because this distance is equivalent to the variance of the variable, which further improves the interpretability of R. We follow this argumentation, and use A(a, (a 6)2. This definition implics that A is in fact equal to the Mean Squared Error (MSE). Thus, by optimizing R, we are actually optimizing the accuracy of the local model.
However, to avoid explanations that are too specific, ie., explanations that apply to very small neighbor- hoods, as in Figure (left), (left), we wish optimize not just the accuracy, but also the generality of the surrogate model. Therefore, we include the size of the neighborhood in the optimization function, aim for explana- tions that are the same time accurate and general (Figure I (right)). One way to do this is to maximize
5

---

Published in Transactions on Machine Learning Research (08/2025)
the lower bound of the confidence interval of R. The lower and upper bounds for the confidence interval of R are given by (Berry and Mielke Jr
1988):
Cla = R MOEE = 8 MOEs
(3)
Here, MOE stands for the Margin of Error. From Equation B it follows that computing the lower bound of R is analogous to computing the upper bound of 8. Therefore, we can compute the margin of error for 8 as MOE, ' where is the standard deviation of the sample, N the sample size and represents the critical value from the t-distribution. We use the t-distribution because it is adapted for small sample sizes, which is what we encounter when we grow the neighborhood. The distribution converges to the normal distribution as the sample size increases.
Due to the non-monotonic nature of the R value, we have to explore the whole space maximize its lower bound. We employ linear search algorithm (Algorithm 2 to this end.
Algorithm Neighborhood Search
Input: Labeled data point x E Datasot T with labels Y
Distances d:T++ R of the data points to x
Sort T by ascending d
< number of features in T 3: marRy + 0, best.V t O, bestL + 0
4: for = min(2n, (71) to (T) do
5:
- TraiioooaaurrrgtteeoolllTC i]) (L) > maxRas then marRy-+ + Ry,LL,, bestN- bestL t- L
end if end for 10: return besth. T(0:bestN]
The algorithm receives as input a labeled data point that is to be explained, labeled training T, and vector of distances between x and each point in the training set T. We sort the training set by increasing distance to x, train linear model the first data points for increasing i, and return the set of neighbors for which the lower bound of R is maximal. As the neighborhood is very small in the beginning, the training easily leads to overfitting. Therefore, we consider at least 2n data points for our neighborhood, where n is the number of features. This ensures that the cstimation of regression coefficients exhibits less than 10% relative bias (Austin and Steyerberg 2015
Algorithm 3 Train Local Surrogate Model
Input: Neighborhood of data points A
1: F the set of all features in N
2: F' " F A VIF(J) < 10.0)
3: FeaturesLasso +- Lasso(cu- = 5, features = F*)
4: return OLS (FLtueaaures)
Building local surrogate model. We build our local surrogate model on the neighborhood we have found. To obtain model with few parameters (i.c., simple model), we use rogularization. In terms of fealure selection, L1 regularization (e.g. Lasso (Hastie el al. 2009)) is able to select a nearly perfect subset of variables a wide range of situations. The only condition for this to work is that there are no highly collinear variables (Candès and Plan 2009), which can significantly reduce the precision of estimated regression coefficients. To remove highly collinear features, we compute the variance inflation factor (VIF), and, following rule of thumb (Stine 1995). adopt 10 the cut-off value for the VIF.
Step 3:

---

Published in Transactions on Machine Learning Research (08/2025)
Figure Explanation example.
900
900
-102.91 age
800
800
480.08 freqsms
700
700
190.27 seconds
600
600
-17.71 x distnums
Explained value: 557.68
500
500
Base value: 458.47
400
400
The value predicted by the model is 551 and the explained value is 557. This explanation applies to 476 other instances.
After removing highly collinear features, the next step is to train a linear model with Lasso regularization. Lasso regularization adds penalty term in the form of the sum of absolute values of the regression coeffi- cients. The objective function minser= (lly 1| (|[B11i,, where À is the shrinkage parameter. This provides sparse model, by forcing some coefficients to be zero. Removing some features ensures better generalization, and results in simpler, and thus more comprehensible explanations. On the other hand, coefficients obtained by minimizing the Lasso objective function are biased towards zero. Therefore, Lasso is preferred for model selection rather than for prediction. The common strategy is to train an Ordinary Least Squares (OLS) linear model on the subset of variables selected by Lasso. This corresponds to a special variation of the relaxed Lasso [Meinshausen, 2007). with e =.
To determine the value of the shrinkage coefficient X, we 5-fold cross-validation (CV). To preserve the deterministic nature, we perform CV adjacent slices of the datasct, without random shuffles. CV selects the best model in terms of the prediction error. Since the goal of this step is model selection, we wani to avoid choosing À too small, and hence we apply the common one-standard error rule. According to this rule, the most parsimonious model is the one whose error is no more than one standard crror above the error of the best model (Hastie et al. 2009
Once we have obtained the most parsimonious model, i.e., the best of features, train the final local surrogate model 3 and returns local linear model. The method is designed to maximize the robustness of our explanations: the Lasso regularization makes our results less brittle. Also, our target metric increases the number of data points, making the result more general and thus more robust.
OLS model using the features selected by Lasso. This procedure is described in
Algorithm
Providing an explanation. As the final result, BELLA outputs the OLS model computed by Algorithm 3 together with the size of the neighborhood. As an example, consider the Tranian Churn dataset (Jafari- Marandi et al. 2020). It contains the (anonymized) customers of telecommunication company, with their age, subscription length, satisfaction with the service, etc. The goal is to predict the commercial value of the customer to the company (in dollars). Let us now consider given customer, for whom black-box model predicted commercial value of $551. The explanation that BELLA can provide for this prediction is shown in Figure 2 All nunerical features have been standardized to have a mean value equal to 0 and a standard deviation equal to 1. (Thus, a customer has a "negative age" if they are younger than the average customer.) In the explanation, the base value the output of the model when all inputs are set zero (i.c. their mean value). Each bar shows the total contribution of each feature the predicted value positive contributions are the blue upward arrows, and negative contributions the red downward arrows. The

---

Published in Transactions on Machine Learning Research (08/2025)
more the customer phones (variable seconds), the more revenue the company generates. The age (which is below average for this particular customer), likewise, has small positive impact. The number of SMS, in contrast, (variable freqSMS) impacts the revenue negatively. Finally, the number of distinct phone numbers called (variable distnum) has a small negative impact. These sizes the bars are easy to interpret: The size of each bar is equal the value of the feature multiplied by the weight computed by our method. Their sum then directly equivalent the explained value:
y 458.47 190.27 seconds 102.91 age 480.08 freqSMS 17.71 distNums
This computation applies to all data points in the neighborhood of the input data point (to the current instance and 476 others in our example). We thus see that BELLA's 's explanations they take the form of a linear equation), deterministic (because BELLA does not use any randomized steps), simple (because we applied regularization), generul (because we maximized the neighborhood), and accurate (because we optimized the lincar model on the local neighborhood), In addition, BELLA does not probe the black-box model. This means that, unlike many of its competitors, BELLA can explain not just the decisions of a black-box model, but any numerical variable tabular dataset even if that variable was not generated by model at all but mercly observed in reality.
verifiable (because
5 Experiments
Datasets. We performed experiments datasets from two standard repositories (Dua and Graff 2017 Romano et al., 2021) (shown in Table I. Among them is also high-dimensional dataset, Superconductivity, with 81 features. All categorical features have been one-hot encoded and all numerical features have been standardized. We draw a random 10% of each dataset as testing data. To show that BELLA works with different familics of models, we trained random forest (with 100 trees), and a neural network (with one hidden layer with 500 nodes) as black-box models. Since the results not differ much, we show only experiments with the neural network here, while the experiments with the random forest in Appendix A
BELLA. Our method is implemented in Python. We set the step size to 10%. For the black-box models, we use the implementations of scikit-learn (Pedregosa et al. 2011). All experiments are run on Fedora Linux (release 38) computer with an Inte((R) Xeon(R) v4 & 2.20GHz CPU, a memory of 64 GB, and Python 3.9. All code and the data for BELLA and the experiments is available on Github (URL masked for anonymity).
Table 1: Regression Datasots
Dataset
Features
Numerical
Categorical
Instances
Auto MPG
7
1
392
Bike
3
8760
Concrete
1030
Servo
4 167
Electrical
12
12
0 10000
Superconduetivity
81
81
0
21262
White Wine Quality
11
11
0
4898
Real Estate Valuation
5
0
414
Wind
14
14
0
6574
CPU activity
12
8192
Echocardiogram
17496
Iranian Churn
11
3150 3
8

---

Published in Transactions on Machine Learning Research (08/2025)
Table Fidelity comparison (RMSE smaller better)
Dataset
LIME
MAPLE
BELLA
SHAP
Auto MPG
2.99
0.86 20.270
1.45
0.00
Bike
579.76#224
75.42 46.710
204.70
0.00
Concrete
10.61 21.40
2.13 20.200
4.87:20.70
0.00
Servo
00.300
0.21 100100
0.59 200.20
0.00
Electrical
0.02=0.002
0.01 +:0.000
0.02 0022=0.000
0.00
Supercond.
23.17
1.05 :0 029
14.24 00-434
0.00
White Wine
0.36=2.030
0.17 0.177:0.000 =200010
0.29 000000
0.00
Real Estate
1.170
1.48 ::0 540
2.01
0.00
Wind
2.52 #0.382
1.15 #0.173
1.69 400247
0.00
CPU Activity
16.30 1.620
0.81 $0.000
0.00
Echocard.
3.02
1.82 110 031
2.84
0.00
Tranian Churn
172. =22.52
4.04 20.970
24.40
0.00
Norm. avg.
0.10
0.02
0.05
0.00
Competitors. We compare BELLA to LIME (Ribeiro al. 2016). SHAP (Luddbeg and Lee 2017) and We do not compare to
MAPLE (Plumb et al. 2018 We use the implementations by the authors Mi methods that are designed for classification tasks, or that can provide only counterfactual explanations and not factual ones (see again Section
5.1 Experimental results
We compare BELLA's performance against the competitors the quality measures from Section 3 All tables show the average performance on the test set of cach method with confidence intervals at 95%.
Fidelity is measured by the Root Mean Squared Error (RMSE) of the local surrogate models wrt. the predictions of the black-box models (Table 2 with a min-max normalized average). SHAP always has an error of 0. This is because provides exact explanations that apply only a single data point. Among the methods that apply to neighborhood of points, MAPLE is constantly the best, followed closely by BELLA LIME comes last.
Generality is measured by the number of data points to which the explanation applies (as a percentage of all data points in the training set). One could give a hypercube for the size of the neighborhood, but it is arguably the number of data points (and not the size of a potentially sparse hypercube) that conveys the significance of the explanation. Thus, for BELLA, we simply return the size the neighborhood. For MAPLE we return the number of data points that have weights larger than For LIME, an explanation comes with the range of values for each feature. We count the number of data points that fall into this range, The results shown in Table 8 For SHAP, the size of the neighborhood is always 0. This is because SHAP provides feature contributions that are specific for the given data point, and there is no way to apply these explanations to other data points. LIME's explanations are more general, and MAPLE's explanations even more. Still, they are vastly less general than the explanations of BELLA.
Simplicity is most commonly measured by the number of features that an explanation contains (Table 4 LIME has the same size of explanations as BELLA. This is bocause LIME takes this parameter as input and we set it to the size of the explanation provided by BELLA. SHAP and MAPLE constantly provide longer
"The fidelity of BELLA could be improved by giving weight to the explained examples, MAPLE docs, but this would compromise the advantage BELLA providing a linear explanation that valid for the whole neighborhood with the same error margin.
9

---

Published in Transactions on Machine Learning Research (08/2025)
Table 3: Generality comparison (% larger is better)
Dataset
LIME
SHAP
MAPLE
BFL.AA
Auto MPG
2..12
0.00
60.09
23.210
Bike
1.34+0..140
0.00
6.35 60.076
45.08 22.020
Concrete
1.10
0.00
32.05
34.02 14.140
Servo
13.43 25,040
0.00
76. 76.23 16,330
75.28 133.11
Electrical
0.02 #0.010
0.00
8.44 +0.390
31.84 20.654
Supercond.
1.01 #0.071
0.00
4.39 20.070
52.78 20.124
White Wine
0.97=0
0.00
33.63 #3.076
Real Estate
3.43
0.00
47.89 13,790
39.37=11.0
Wind
0.78 60,190
0.00
12.46 60.540
100.0 +00000
CPU Activity
0.79
0.00
90.215
30.36 21778
Echocard.
0.06620.008
0.00
9.19 10,060
77.11 27,270
Tranian Churn
1.83
0.00
12.17 20.410
30.21 22.800
Average 2.82
0.00
24.59
49.50 =4.199
Table 4: Simplicity comparison (smaller values better). LIME requires the explanation size as input, and we give it the size of the explanation computed by BELLA.
Dataset
SHAP
MAPLE
BELLA/LIME
Auto MPG
9.00
8.93 10.090
3.90 10.300
Bike
11.54
13.44
8.47 #0.110
Concrete
8.00
8.00 20.000
6.24
Servo
12.47
17.88
17.88=20111 70
5.65 1.160
Electrical
12.00
12.00 20.000
9.40 1:.184
Supercond.
70.29 40.221
81.00 #0.000
14.19 #0.182
White Wine
11.00
11.00=0.00m
7.58 #0.200
Roal Estate
5.00
5.00=20.00
4.10 E0,320
Wind
13.05
14.00
9.32
CPU Activity
12.00
12.00 #0.000
9.56 00.190
Echocardiogram
7.33 00.100
8.49
7.07=
Iranian Churn
9.14:0.000
10.52:2.00m
4.76 0..160
Norm. Avg.
0.8940.004
0.96
0.59 20.023
explanations than BELLA. MAPLE has higher complexity than SHAP, even though it comes with lower accuracy.
One could consider tuning the simplicity of LIME until LIME beats BELLA fidelity, tune fidelity until LIME beats BELLA on simplicity. To compare the two methods, however, one has to fix one parameter and compare the other. This is what our experiments do: at the same simplicity, BELLA beats LIME on fidelity (Table 2h. It follows that, to achieve the same fidelity as BELLA, LIME necessarily has to decrease its simplicity. Thus, BELLA beats LIME in both cases.
Robustness judges how similar the explanations for close data points are. We measure robustness as:
lw W2s
robustness 7 Wisl + 122
(4)
Here, n is the number of features, and Wi and w2y are the weights of feature i in the first and second explanation, respectively. Robustness in the range of [0, 1], with indicating that two explanations are identical. We compute explanations for each data point in the test set, and compute robustness wrt. smaller set of 5 closest neighbors, and larger set of 20 closest neighbors (Table 5). As expected, all methods are
10

---

Published in Transactions on Machine Learning Research (08/2025)
Table Robust comparison (0 to larger better)
Dataset
Number of Neighbors = 5
Number of Neighbors 20
LIME
SHAP
MAPLE
BELLA
LIME
SHAP
MAPLE
BELLA
Auto MPG
0.89 -0.00
0.74
0.73
0.91 s0.00
0.82 +0.05s
0.69.a..sa
0.66
0.85 =0.077
Bike
0.78 con
0.00.00000
0.52
0.82
20.027
0.63
0.52
0.81 2.80
Concrete
0.79..o.om
0.81 Loosso
0.68 10.0s0
0.74 2ourr
0.63 10.0so
0.70
3.64
2..4
Servo
0.85 _.00
0.46Lo.0z Lo.020
0.53 1o.330
0.76 Loooru
0.88 L0.330
0.42
0.55 1o.1e
0.78 Lo.8
Electrical
0,65=0.029
0.58 0.58
0,60
0.83=0.08
0. 0.62 +0.015
0.55
0.74
0.83=0.022
Supercond.
0.91-0.017
0. 8.800s
0.60eeo.re
0.91 =0.000
0.90 0..000
0.74+0.044
0.49 0.49000001
0.92
White Wine
0.72
0.64 0.0
0.7 0.71. 1000000
0. 200070
0.59
2.54
1.64
0.67
Real Estate
0.77
0.75
0.78
0.78 g0.000
0.67 0.0006
0.65
0.62
0.77
Wind
0.68..o.om
0.66 2o.0zs
0.99 200007
0. E000ss
2.56
0.62
0.98 20.018
CPU Activity
0,53 oee
0.73 000
0. 7.70as..0 .40
0.82=0.000
0. 1.42++000s
0.71=0.000
0.75+0.026
0,81 080
Echocardiogram
0.77=0.081
0.6450.0ss
0.61+0.041
0.92=0.00
0.7 76
0.63000006
0.57=0.088
0,84=0.070
Tranian Churn
0.71 Loocen
Lo.mo
0.67 Lo.000
0.89 LovoG0
0.64go.05
0.50
0.60 Looos
0.86_0.00
[86__.000
Average
0.75 000
0.69
0.66
0.85 20.00a
0.71 20.005
2.64
0.62
0.81 500005
Table 6: Execution time comparison (in seconds lower is better)
Datasct
LIME
SHAP
MAPLE
BELLA
Auto MPG
2.21 20.043
0.04
0.02
1.40
Bike
1.84 +0,001
0.10
0.01 +0,033
2.70 +0.000
Concrete
2.1040.034
0.02
0.02:10.001
0.92
Servo
1.34
0.17
0.02:10.00
2.99
Electrical
3.27 #0.00s
Do.000
0.01 +-0,000
2.27 +0.001
Superconductors
21.9
0.17
0.02 1.0001
242.00
White Wine
#0.003
0.16#b.002
0.02 1.02+t0.011
1.66##.011
Real Estate
1.74
0.01
0.01
0.72:0.032
Wind
3.77 #0.004
0.13
0.01 +.0000
1.53
CPU Activity
1.00
0.11
0.01++0.000
1.36+0.001
Echocardiogram
1.83+0.00s
0.01
0.01
3.35+to.0uz
Tranian Churn
2.83 20.077
0.04
0.02
1.30
Median
2. 2.16
0.11
0.02+o.001
1.640.019
Average 3.97:0.024
0.09
0.02:1..01
21.86.0.010
bit less robust when the set of neighbors is larger, but otherwise the results are very similar: LIME samples 5000 data points to create synthetic neighborhood. Thus, LIME can perform better than our approach on datasets that have fewer observations. However, in the vast majority of cases, as well as on average, BELLA outperforms LIME. BELLA also outperforms SHAP by a wide margin. This is because SHAP's explanations are tailored for single data point. BELLA also outperforms MAPLE. This is because the crisp neighborhood of BELLA provides much more robust explanations than MAPLE's weighted neighborhood.
From Tables 2 g and 5 we can see that at the same level of simplicity, BELLA provides more general, more robust,, and more accurate explanations than LIME. BELLA provides less accurate explanations than SHAP and MAPLE, but the same time, BELLA's explanations are more general, more robust, and vastly simpler. The results when the black-box model is random forest are shown in Appendix A and they do not differ much.
Runtime of all methods is shown in Table i On average, MAPLE and SHAP are extraordinarily fast, and LIME is slower. BELLA is, on average, 5x slower than LIME. This is due mainly to a single dataset, Superconductivityy which has a very large number of features, and on which BELLA is 11x slower than LIME. This is because, different from our competitors, BELLA is deterministic. Our method thus has to explore the whole local space. At the same time, BELLA runs in the same order of magnitude of time as LIME on average, and it remains thus competitive. On the median, BELLA is even faster than LIME.
11

---

Published in Transactions on Machine Learning Research (08/2025)
0.
0.-
seterds
ego
Fequn
charge
Figure Top features of linear model on the Iranian Churn dataset, and percentage of data points whose BELLA explanation uses cach feature.
The other desiderata outlined in Section were determinism and verifiability (the possibility to compute the explained value from the feature values). SHAP offers none of these. Neither does LIME. While both SHAP and LIME compute linear models with feature weights, these models are not verifiable in our sense: There is no way that the user can insert the feature values of a neighboring point into these models and obtain an explained value. This is because the linear models do not operate in the original input feature space. Only MAPLE offers this verifiability. However, it relies on randomization. BELLA is thus the only approach that delivers deterministic, and verifiable explanations.
Verification an interpretable model. To confirm that the explanations provided by BELLA represent what the black-box model has learned, we evaluate them with regard to already interpretable model. Instead of a black-box model, we train an Ordinary Least Square linear regression model and consider the 5 most important features. We then compute the explanations for each data point in the test set with our method. BELLA was able to recover on average 85.12% of the original top-5 features across all datasets. Figure shows an example of the most important features the Tranian Churn datasel, as extracted by the linear model, and the percentage of data points for which BELLA gives an explanation with these features. This shows that our method provides explanations that generally agree with prior beliefs, as encoded in an interpretable model.
6 Limitations
BELLA is dlomain-independeet. method to produce deterministic post-hoe local explanations of tabular regression datasets. This scope entails some inherent limitations: First, as generalist method, BELLA does not take into account domain-specific peculiaritics, such as domain-specific weighting, dynamic scaling of feature distances, domain-specific distance functions. Second, BELLA aims at simple and verifiable (and ultimately linear) explanations. With this, BELLA may fail to capture intricate, higher-order interactions of features. This problem is part of the intrinsic trade-off between simplicity and accuracy, which any post-hoc explainability approach finds itself in. Third, BELLA has to explore the whole neighborhood space without sampling, because is deterministic. This incurs high algorithmic cost, as our experiments show. This mcans that BELLA does not scale well a large number of fcatures, and the speed optimization of BELLA is left for future work.
There are also number of ethical considerations: First, BELLA does not correct for biases in the data or the model. If the data contains biased samples, discriminating features, or an otherwise unprofessional selection of feal or data points, these characteristics will be mirrored in BELLA's explanations. We believe, however, that this a feature rather than a bug: BELLA's explanations make such biases visible the user. It would be disastrous correct them and thus convey the impression that the model does not have them. A second concern is the problem of overtrust, where users mistakenly take BELLA's local explanation for global correlation. That is an issue inherent to all local approaches, which would have to
12

---

Published in Transactions on Machine Learning Research (08/2025)
be countered by educating the user before using the approach. Finally, BELLA measures generality by the number of training examples that were considered to compute the explanation. While BELLA minimized the average error on this set of datapoints, it is possible that some examples of this neighborhood are not well explained.
For all of these reasons, BELLA, as any explainability method, gains from being combined with frameworks for fairness, transparency, and accountability, as well domain-specific adaptations.
7 Conclusion
We have presented BELLA, deterministic approach to provide post-hoc local explanations for any regression black-box model, indeed any static tabular dataset with numeric variable to be explained. BELLA's objective function ensures accurate, general, robust, and simple explanations. Detailed experiments show that BELLA outperforms state-of-the-art approaches on these desiderata, often by a wide margin.
Future work could investigate methods to improve the speed of BELLA. One possibility is to use other data structures speed up the neighborhood search. Another possibility is to give up determinism and resort to sampling to further speed up the algorithm. Finally, one could investigate even if BELLA could replace black box models for making prediction in the first place, following positive experiences with linear models elsewhere [ssmail et al. 2022). We hope that work open the door to research along this line and others, and ultimately make machine learning models more interpretable.
References
Bryce Goodman and Seth Flaxman. European union regulations on algorithmic decision-making and a "right to explanation". Al magazine, 38(3), 2017.
Europcan Parliament and Council of the EU. Regulation (eu) 2024/168 of the european parliament and of the council of 13 june 2024 laying down harmonised rules on artificial intelligence and amending regulations (ec) no 300/2008, (eu) no 167 167/2013, (eu) no 168/2013, (eu) 2018/855 (eu) 2018/1 1139 and (eu) 2019/2144 and directives 2014/90/eu, (eu) 2016/797 and (eu) 2020/1828 (artificial intelligence act), 2024.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In NEURIPS, 2017.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Why should trust you? - explaining the predictions of any classifier. In SIGKDD, 2016.
Gregory Plumb, Denali Molitor, and Ameet S Talwalkar. Model agnostic supervised local explanations. NewrIPS, 31, 2018.
Valérie Beaudouin, Isabelle Bloch, David Bounie, Stéphan Clémengon, Florence d' Alché Bue, James Fagan, Winston Maxwell, Pavlo Mozharovskyi, and Jayneel Parekh. Flexible and context-specific ai explainability; a multidisciplinary approach. SSRN, 3559477, 2020.
Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. A survey of methods for explaining black box models. ACM computing surveys, 51(5), 2018.
Amina Adadi and Mohammed Berrada. Peeking inside the black-box: A survey on explainable artificial intelligence (xai). Access, 6, 2018.
W James Murdoch, Chandan Singh, Karl Kumbier, Reza Abbasi-Asl, and Bin Yu. Interpretable machine learning: definitions, methods, and applications. arXie preprint, 10X442190..4459,, 2019.
Nadia Burkart and Marco F Huber. survey on the explainability of supervised machine learning. JAIR, 70:245 317, 2021.
Vikas Hassija, Vinay Chamola, Atmesh Mahapatra, Abhinandan Singal, Divyansh Goel, Kaizhu Huang, Simone Scardapane, Indro Spinelli, Mufti Mahnud, and Amir Hussain. Interpreting black- box models: a review explainable artificial intelligence. Cognâtive Compulation, 16(1):45 74, 2024.
13

---

Published in Transactions on Machine Learning Research (08/2025)
Itai Gat, Nitay Calderon, Roi Reichart, and Tamir Hazan. A functional information perspective model interpretation. In International Conference on Machine Learning, pages 7266-7278. PMTR, 2022.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information- theoretic perspective on model interpretation. In International conference on machine learning, pages 883 892. PMLR, 2018.
Scojin Bang, Pengtao Xie, Hecwook Lee, Wei Wu, and Eric Xing. Explaining a black-box by using a deep variational information bottleneck approach. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 19964, 2021.
Vy Vo, Van Nguyen, Trung Le, Quan Hung Tran, Gholamreza Haffari, Seyit Camtepe, and Dinh Phung. An additive instance-wise approach to multi-class model interpretation. ar preprint or arXi:22007.0311 2022.
Ramaravind Mothilal, Amit Sharma, and Chenhao Tan. Explaining machine learning classifiers through diverse counterfactual explanations. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pages 607 617, 2020.
Ngoe Bui, Duy Nguyen, and Viet Anh Nguyen. Counterfactual plans under distributional ambiguity. arxiv preprinl Xiv:22200 12487, 2022.
Vy Vo, Trung Le, Van Nguyen, He Zhao, Edwin V Bonilla, Gholamreza Haffari, and Dinh Phung, Feature- based learning for diverse and privacy-preserving counterfactual explanations. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2211-2222, 2023.
Riccardo Guidotti, Anna Monreale, Fosca Giannotti, Dino Pedreschi, Salvatore Ruggieri, and Franco Turini. Factual and counterfactual explanations for black box decision making. IEEE Intelligent Systems, 34(6):
14-23, 2019.
David Dandolo, Chiara Masiero, Mattia Carletti, Davide Dalle Pezze, and Gian Antonio Susto. accelerate model-agnostic explanations: Fast whitening of the machine-learning black box. Expert Systems with Applications, 214:119115, 2023.
Muhammad Rehman Zafar and Naimul Mefraz Khan. Dlime: A deterministic local interpretable model- agnostic explanations approach for computer-aided diagnosis systems. arXiv preprint, arXiv:1906.1022 2019.
Adam White and Artur d'Avila Garcez. Measurable counterfactual local explanations for any classifier. arXiv preprint, arXiv:1908.0300 2019.
Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl. Multi-objective counterfactual expla- nations. In International Conference on Parallel Problem Solving from Nature, pages 448 469, Springer, 2020.
Annabelle Redelmeier, Martin Jullum, Kjersti Aas, and Anders Loland. Moce: Monte carlo sampling of realistic counterfactual explanations. arXiv preprint orXiw:2111.09790, 2021.
Arun Das and Paul Rad. Opportunities and challenges in explainable artificial intelligence (xai): A survey. arXiv preprint, arXiv:2006.1137 2020.
Nedeljko Radulovic, Albert Bifet, and Fabian Suchanek. Confident interpretations of black box classifiers. In (IJCNN, pages 8. IEEE, 2021.
Alexcy Ignaticv, Nina Narodytska, and Joao Marques-Silva Abduction-based explanations for machine learning models. In AAAI, volume 33-01, pages 1511 1519, 2019.
Tim Miller, Explanation in artificial intelligence: Insights from the social sciences. Artificial intelligence, 267:1-36 38, 2019.
14

---

Published in Transactions on Machine Learning Research (08/2025)
Christoph Molnar. A guide for making black box models explainable. iofinteryrelabbiem---boe 2:3, 2018.
URL: https://christopphm. github
Mayo-Clinic. Diabetes, 2023. URL http:///wwwwa.........c//aaaaaaa
Yujia Zhang, Kuangyan Song, Yiming Sun, Sarah Tan, and Madeleine Udell. why should you trust my explanation?" understanding uncertainty in lime explanations. arXiv preprint, arXiv:1904.1299, 2019.
Dylan Slack, Sophie Hilgard, Emily Jia, Sameer Singh, and Himabindu Lakkaraju. Fooling lime and shap: Adversarial attacks on post hoc explanation methods. In AAAI/ACM Conference on AI, Ethics, and Society, pages 180-186, 2020.
Sandhya Harikumar and PV Surya. K-medoid clustering for heterogeneous datasets. Procedia Computer Science, 70:226 237, 2015.
John Hopcroft and Ravi Kannan. Foundations of data science. Cambridge University Press;, 2014.
Amir Ahmad and Lipika Dey. A k-mean clustering algorithm for mixed numeric and categorical data. Dala & Knowledge Engincering, 63(2):503-522 527, 2007.
Kenneth J Berry and Paul W Mielke Jr. A generalization of cohen's s kappa agreement measure to interval measurement and multiple raters. Educational and Psychological Measurement, 48(4):921-98) 933, 1988.
Jacob Cohen. A coefficient of agreement for nominal scales. Educational and psychological measurement, 20 (1):37 46, 1960.
Harald Janson and Ulf Olsson. A measure of agreement for interval nominal multivariate observations. Educational and Psychological Measurement, (2))2777-289, 2001.
Harald Janson and Ulf Olsson. A measure of agreement for interval nominal multivariate observations by different sets of judges. Educational and Psychological Measurement, 64(1):62 70, 2004.
Peter C Austin and Ewout W Steyerberg. The number of subjects per variable required in linear regression analyses. Journal of clinical epidemiology. 686))627, 2015.
Trevor Hastic, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
Emmanuel J Candès and Yaniv Plan. Near-ideal model selection by minimization. The Annals of Statistics, 37(5A):214522177, 2009.
Robert A Stinc. Graphical interpretation of variance inflation factors. The American Statistician, 49(1): 53 56, 1995.
Nicolai Meinshausen. Relaxed lasso. Computational Statistics & Data Analysis, 52(1):374 393, 2007.
Ruholla Jafari-Marandi: Joshua Denton, Adnan Idris, Brian K Smith, and Abbas Keramati. Optimum profit- driven churn decision making: innovative artificial neural networks in telccom industry. Neural Computing and Applications, 32:14929 14962, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://archive.iii ics. uci. edu/
1
Joseph D Romano, Trang T Le, William La Cava, John T Gregg, Daniel J Goldberg, Praneel Chakraborty, Natasha I. Ray, Daniel Himmelstein, Weixuan Fu, and Jason H Moore. Pmlb v1.0: an open source dataset collection for benchmarking machine learning methods. arXiv preprint, arXiv:2012.00058V, 2021.
F. Pedregosa, G. Varoquaux, Gramfort, et al. Scikit-learm: Machine learning in Python. JMLR, 12, 2011.
Aya Abdelsalam Ismail, Sercan Ô Arik, Jinsung Yoon, Ankur Taly, Soheil Feizi, and Tomas Pfister. Inter- pretable mixture of experts. XrXiv preprint Sft:2206.02100 2022.
15

---

Published in Transactions on Machine Learning Research (08/2025)
A Experiments with Random Forest as black-box box model
In the main paper, presented experiments using ncural network as a black-box model. Here, we show the results of experiments using a random forest of 100 trees as a black-box model. The results are shown in Tables 7 and 11 They do not differ much from the results on the neural network black-box model.
Table 7: Fidelity comparison for Random Forest as black-box model
Dataset
LIME
MAPLE
BELLA
SHAP
Auto MPG
L.57
0.95 20.272
1.52 80.412
0.00
Bike
338, 20.92
61.23 15.580
228. 14.44.
0.00
Concrete
5.78 #0.84
2.22 #0.341
5.11 +0.0811
0.00
Servo
0.45
0.18 1..12
0.45:10.211
0.00
Electrical
0.01 0..1100.002
0.00 1:0. 001
0.01 1:0. 002
0.00
Supercond.
30.68 41.087
0.96
15.52
0.00
White Wine
0.30
0.17 #100014
0.28
0.00
Real Estate
5.19 1.292
2.55 #00.982
5.04
0.00
Wind
1.40=00199 197
0.70 100.18
1.17 1:01144
0.00
CPU Activity
12.57 11.110
0.63 #0.070
1.26 +0.010
0.00
Echocard.
3.31 :0.500
1.64 20.246
3.21 5.0.33
0.00
Iranian Churn
141.57 #20.44
9.46 7.878
17.39 922992
0.00
Norm. avg.
0.07
0.02 400004
0.05 6-0.008
0.00
16

---

Published in Transactions on Machine Learning Research (08/2025)
Table 8: Generality comparison (% larger is better)
Dataset
LIME
SHAP
MAPLE
BELLA
Auto MPG
8.35
0.00
45.41 +3.423
72.08 E4.082
Bike
2.247
0.00
6.3620.250
50.96.2.344
Concrete
0.23
0.00
30.13
42.24 14,038
Servo
11.03
0.00
73. 73.24
84.03 112.123
Electrical
0.01+
0.00
7.23 +0,370
33 24 H6.040
Supercond.
0.0022.002
0.00
3.47
67. 111.66 #13.67
White Wine
2.18:00.200
0.00
18.48 10,373
72.24 122439
Real Estate
2.43
0.00
47.32 #3.987
83.38 #7.320
Wind
t0.013
0.00
12.46 +0.440
100.0 E0.000
CPU Activity
0.47::0.014
0.00
L.94
50.43 E1.430
Echocard.
2.11:
0.00
5.98
88. 22 15.620
Iranian Churn
1.78 +0.336
0.00
11.97 +0,325
28.43 11.893
Average
2.53 10.444
0.00
22.67 11.3610
64.39 133605
Table 9: Simplicity comparison (smaller values better)
Dataset
SHAP
MAPLE
BELLA/LIME
Auto MPG
9.00
8.85 #0.210
3.65 #0.170
Bike
12.22 #0.099
13.43=20.88
7.94 10.103
Concrete
8.000
8.00 20.000
Servo
10.16+1.668
14.88 20.250
6.47:11.20
Electrical
12.00 0..000
12.00 10.000
8.06
Supercond.
34.14
81.00 20.000
12.57=0.000
White Wine
11.00
11.00
6.02 #0.212
Real Estate
5.0000
5.00 00.00
3.95 00007
Wind
13.63 10.048
13.00=0.00m 000000
7.82 10.15
CPU Activity
12.00 +6.000
12.00 20.000
9.50 10.190
Rchocardiogram
7.36
8.43 20.009
5.23 10.101
Iranian Churn
9.151
10.51 10.0661
4.87 10.161
Norm. Avg.
0.85
0.94=0..0m
0.53::0.020
17

---

Published in Transactions on Machine Learning Research (08/2025)
Table 10: Execution time comparison (in seconds lower is better)
Dataset
LIME
SHAP
MAPLE
BELLA
Auto MPG
2.32
0.06=0.000
0.01 #0.000
1.35=0.0m
Bike
1.42 +0.014
00.001
0.01 t0.000
3.24-0
Conerete
20.000
0.0420.000
0.02 20.000
0.92=0.010
Servo
1.42
0.18 0.0001
0.02 100000
3.03
Electrical
+..00
0.11
0.01 00.000
1.95=0.000
Supercond.
21.65
0.27
0.02::0000
243.51
White Wine
3.92
0.20
0.02
1.70=0.012
Real Estate
10.04
0.02
0.01
0.77=0.030
Wind
2.24 +0.001
0.13 80.001
0.01 +0.000
1.45=0.000
CPU Activity
10.010
0.1220.001
0.01 #0.000
1. 1.66=0.021
Echocardiogram
1.17:0.001
0.02 0.0001
0.01 10.001
2.57 0.553
Tranian Churn
2000
0.08 20.000000 001
0.02
1.40=0.012
Table 11: Robustness comparison (0 to - larger is better)
Dutaset
Number of Neighbours
Number of Neighbours 20
LIME
SHAP
MAPLE
BELLA
LIME
SHAP
MAPLE
BELLA
Auto MPG
0.90
0.68s0.08. 053
0.70
0.96=0.0m 020
0.83g0.024
0.58
0.65
0.93 00.3.
Bike
0.63
0.47
0.83 _o.0m
0.67 10.047
0.62
0.48
0.85 L0.00s
Concrete
0.81
0.73.
0.761n.0m
0.79_oo.m
0.67 1o.067
0.581o.m0
0.65
0.73
Servo
0.85=0.050
0.46+0.040
0.63
0.74-0.040
0.80=0.08
0.50
00.24
0.76=0.1947
Electrical
0.82+0.054
0.55
0.62+0.946
0.88
0.76-
0.50=0.022
0.58
0.88
Superoond.
0188 013
0.69 044
0.68
0.94
0.86.20.07
0.73
0.68 018
20.007
White Wine
0.74 07o
0.58
0.62:s0.07
0.87 =00000
0.66:20.00
0.46
0.53 043
0.83 0.83:20.08
Real Estate
Lu.no
0.70.am.om
0.76g...0
0.94
Lo.omm
0.66 Lo.022
0.64 10.oss
0.67.10.m0 1..00
0,82 100000
Wind
0.61 Lo.o0s
0..6.
0.99
_o.00M
0.68 Lo.05o
0.61 1..01.0.0s
0.61 L0.025
0.99 Lo.00s
CPU Activity
0.58 -8.-0.00
0.73
0.67=0..70 =00000
0.82 =0.000
1,55=00.00
0.66=0.052
0.62+00.00
0.79 =0.044
Rchocardiogram
0.83 use
0.59 10.00
0.52.
0.97_00016
0.80 10.03s
0.57 2.0 1.0.0a
0.45..0.00
0.96 go.00o
Tranian Churn
0.77 06.00
0.83 000
0.70
0.86
0.76.go.0 05.
0.77
0.62 oos
0.84
Average
0.77.1
0.65
0.65.00.00
0.88 .0.04m
0.73
0.61an.04
0.60
0.86 10.055
18


Reviews:
[{"review_id": "conNoly7WJ", "reviewer": "Reviewer_PVm6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have noted the changes made by authors in their revision and most of my concerns are addressed. I am leaning towards acceptance of the revised submission.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Since this is a paper reviewed previously, I don't have anything different in the summary to add.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "(None)", "broader_impact_concerns": "(None)", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sXMW4WdWfK", "reviewer": "Reviewer_Aekk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n\n- The paper remains well motivated and clearly written\n- The quality measures for explanation methods are well-defined and comprehensive\n- BELLA satisfies multiple desiderata simultaneously, particularly determinism and verifiability\n- The method now focuses solely on factual explanations (counterfactual explanations have been removed from this version)\n- The authors have addressed several notation and clarity issues from previous reviews\n- The removal of counterfactual explanations has simplified the method and addressed some of the previous concerns about insufficient experimental validation of counterfactuals.\n\n## Weaknesses\n\n- **Fundamental conceptual issue:** The most significant limitation of BELLA is that it explains datasets rather than models. This is fundamentally different from true black-box explanation methods like LIME, SHAP, and MAPLE. Different models trained on the same dataset can produce vastly different predictions for the same input, yet BELLA would provide identical explanations since it only considers the training data patterns. This limitation becomes especially problematic when models are given points far from the training distribution - in such cases, the model's behavior cannot be explained by the training distribution patterns anymore, so BELLA can offer very misleading explanations that are not faithful to the underlying model's actual decision-making process. This makes BELLA more of a \"dataset explanation method\" rather than a \"black-box model explanation method.\" While dataset explanations can be useful, they may not accurately reflect the decision-making process of the specific model being explained.\n\n- **Computational complexity and scalability:** These issues remain, however in this version of the paper the authors acknowledge and highlight these limitations more explicitly, particularly mentioning the difference between BELLA and other methods in terms of computational cost. The trade-off between determinism and efficiency is now better articulated, though it still raises questions about practical applicability to modern ML scenarios with hundreds or thousands of features.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes Black-box model Explanations by Local Linear Approximations (BELLA), a post-hoc explanation method for tabular data regression models. The paper aims to create an explanation method that satisfies the following criteria: Accurate (fidelity), Simple, Robust, General, Deterministic, and Verifiable. \n\n## Method:\nThe method remains largely unchanged from the previous submission. BELLA has 3 main steps:\n\n1. Compute the distance of the target point to other points in the training dataset\n\n2. Neighborhood Search to find samples in the training dataset closest to the input\n\n3. Building a local surrogate model using linear regression with Lasso regularization\n## Experiments:\nThe experimental setup and results are consistent with the previous version, showing that BELLA performs competitively across the defined desiderata compared to LIME, SHAP, and MAPLE.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The authors should explicitly acknowledge and discuss the fundamental difference between dataset explanation and model explanation in the main text\n- Provide clearer discussion of when BELLA's approach (dataset-based explanations) might be appropriate versus when model-specific explanations are needed\n- Consider renaming the method to better reflect its dataset-centric nature rather than claiming to explain \"black-box models\"", "broader_impact_concerns": "The fundamental mismatch between what BELLA actually explains (dataset patterns) and what users might expect (model behavior) could lead to misinterpretation of explanations in high-stakes applications. Users might incorrectly assume the explanations reflect the specific model's decision process when they actually reflect general patterns in the training data", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AYpSQAsmKv", "reviewer": "Reviewer_XTSG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As before, the related work is appropriately studied. The desired properties of post-hoc explainability techniques are clearly identified and make sense. The proposed method is sound and well described. The removal of the counterfactual-related experiments, and the insertion of additional explanations/contents in several places, both make the experimental section more convincing and pleasant to read. The new section on limitations is also interesting (although there is a mention of \"BELLA's counterfactual explanations\" which is now unclear since they have been removed). Maybe a mention of the following point could be worth it:\n- generality is measured as the number of training examples that were considered to compute the explanation. However, it is possible that some example belonging to the considered neighbourhood is not well explained, hence making this notion of generality a bit weaker (although still totally acceptable).\n\nMy concerns regarding notation were almost entirely addressed by the revision, with only minor concerns remaining (which are not crucial, but could enhance understanding), including:\n- local indices are still used to index different things (in particular, $i$ and $j$ are used both to index attributes (e.g., Equation (1)) and examples (e.g., Equation (2)). While it is not rigorously wrong since these are just local indices, and since in some contexts it might be clear, I won't argue for that, but note that a consistent use of local indices can enhance comprehension -- for instance, my next bullet might not be \n- I still find it a bit unclear to let $n$ (or $F$) denote different things in different places. For instance, based on Equation (2) on page 5, $n$ is the number of examples. Now, a \"dataset\" T is defined previously on page 2 as: \"$T \\subset F_1 \\times F_2 \\times \\ldots \\times F_n$ where each $F_i$ is a set of feature values\". This sentence is still unclear to me, as well as these notations. What does $F_i$ stand for ? An example (since there are $n$ such \"set of feature values\") ? If so, why not call it $x_i$ as in the remaining of the paper ? Since $F$ is not really useful in the remaining of the paper, I would recommend simplifying this notation. Also, Algorithm 3 (and the text afterwards) defines $F$ as the \"set of all features [...]\", which is not consistent. Algorithm 2 (and the text afterwards) still defines $n$ as the \"number of features in $T$. Similarly in page 10 (Equation (4)), $n$ is defined as the number of features. \n- In page 10 (Equation (4)), instead of $\\beta$, $w$ could be used to denote the coefficients' values, to meet the notation of Section 4", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces BELLA, a method to generate factual explanations of a black-box model's output. I have reviewed its first submission as Reviewer QUGn.\n\nIn a nutshell, given an example $x$ with some output value to be explained, the proposed approach first sorts the remaining training examples in terms of a given distance metric with respect to $x$. Then, with increasing neighbourhood size, it compute different local approximations of the black-box model around $x$, and evaluates them in terms of (i) size of the neighbourhood (for generality) and (ii) surrogate performance (for explanation accuracy). Then, it fits a local surrogate for the chosen neighbourhood.\n\nI appreciate the authors' efforts to take into account the first round of reviews, and in my opinion, the paper complements well the literature on post-hoc explanations, even though linear surrogates are not totally novel. Apart from a few remarks regarding notation, the paper has really benefited the performed changes and all my concerns were addressed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- (optional) short discussion on the notion of generality (and the fact that the examples it counts may not be well explained despite the fact that they were considered to fit the local surrogate) in the Limitations section\n\n- (optional) fix of the very few remaining notation inconsistencies", "broader_impact_concerns": "N/A: Impact concerns are appropriately discussed in a dedicated Limitations section.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)