=Paper=
{{Paper
|id=Vol-3841/Paper8
|storemode=property
|title=GLEAMS: Bridging the Gap Between Local and Global Explanations
|pdfUrl=https://ceur-ws.org/Vol-3841/Paper8.pdf
|volume=Vol-3841
|authors=Giorgio Visani,Vincenzo Stanzione,Damien Garreau
|dblpUrl=https://dblp.org/rec/conf/hi-ai/VisaniSG24
}}
==GLEAMS: Bridging the Gap Between Local and Global Explanations==
https://ceur-ws.org/Vol-3841/Paper8.pdf
GLEAMS: Bridging the Gap Between Local and Global
Explanations
Giorgio Visani1,* , Vincenzo Stanzione2 and Damien Garreau3
1
Leithà S.r.l. - Unipol Group, via Stalingrado 53, Bologna, Italy
2
Computer Science Department, Bologna University
3
Julius-Maximilians-Universität Würzburg, Germany
Abstract
The explainability of machine learning algorithms is crucial, and numerous methods have emerged
recently. Local, post-hoc methods assign an attribution score to each feature, indicating its importance
for the prediction. However, these methods require recalculating explanations for each example. On the
other side, while there exist global approaches they often produce explanations that are either overly
simplistic and unreliable or excessively complex. To bridge this gap, we propose GLEAMS, a novel
method that partitions the input space and learns an interpretable model within each sub-region, thereby
providing both faithful local and global surrogates. We demonstrate GLEAMS’ effectiveness on both
synthetic and real-world data, highlighting its desirable properties and human-understandable insights.
Keywords
Explainable AI, Global / local, Partition-based machine learning
1. Introduction
In numerous applications, the data present themselves as large arrays—tabular data, where each
line corresponds to a data point and each column to a feature. In this setting, deep learning is
becoming as popular as it already is for more structured data types, and deep neural networks
achieve state-of-the-art in many scenarios [1]. A caveat of this approach is the difficulty to
obtain insights on a specific prediction: the intricate architectures and the sheer number of
parameters prevent the user of getting a clear picture of what is actually important to the model.
Since getting such explanations is desirable in many applications, and could even become
mandated by law in certain regions [2], many interpretability methods have been proposed.
Without getting into details (we refer to the recent surveys [3] and [4] for this purpose), we
want to make two distinctions clear. First, it is challenging for interpretable models to have
the same accuracy as non-interpretable ones. As a consequence, many explainability methods
rely on a post hoc approach, i.e., producing explanations in a second step, exploiting already
trained black-box models. This is the road we take, since post-hoc methods allow us to deal with
any given model and not being dependent on a specific architecture. Second, the explanations
can either be local (related to a specific example), or global (for all the input space). A problem
HI-AI@KDD, Human-Interpretable AI Workshop at the KDD 2024, 26𝑡ℎ of August 2024, Barcelona, Spain
*
Corresponding author.
$ giorgio.visani@leitha.eu (G. Visani); v.m.stanzione@gmail.com (V. Stanzione);
damien.garreau@uni-wuerzburg.de (D. Garreau)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
with local explanations is that they have to be computed individually for each new example,
which can be time-consuming. For instance, LIME [5] generates 5, 000 new datapoints for each
example to explain. The black-box model then has to be queried on each of these points.
In this paper, we propose GLEAMS (Global & Local ExplainAbility of black-box Models
through Space partitioning), a post hoc interpretability method providing both global and local
explanations. Our goal is to build a global surrogate 𝑓^ of 𝑓 that shares the global shape of the
black-box model 𝑓 but, at the same time, has a simple local structure. Our main motivation
in doing so is to extract simultaneously from 𝑓^ : i) local explanations for any instance; ii)
overall importance of the features. Secondary objectives are the production of “what-if”-type
explanations, and visual summaries. In more details, the core idea of GLEAMS is to recursively
split the input space in rectangular cells on which the black-box model can be well-approximated
by linear models. We describe the method in Section 2. The local explanations are then simply
given by the feature coefficients of these local surrogate models, while global indicators can be
readily computed from those, without querying 𝑓 model further. We describe how to obtain
the other indicators in Section 2.4, and show experimentally that GLEAMS compares favorably
with existing methods in Section 3. GLEAMS code as well as the experiments for this paper are
publicly available.1 Related work can be found in Appendix A.
4
2 2
2
0 0
0
−2 −2 −2
−4 −4 −4
−6 −6 −6
−8
−8 −8
−10
Figure 1: Overview of the global surrogate model construction. Left panel: the black-box model maps
the input space (here 𝒳 = [0, 1]2 ) to R, which we can visualize as a surface. Middle panel: we generate 𝑁
Sobol points on 𝒳 , giving rise to 𝑁 measurement points on the surface (in blue). Right panel: we fit a
piecewise-linear global surrogate model 𝑓^ on the measurement points by recursively splitting 𝒳 .
2. Description of the method
We consider the following general setting: 𝑓 is a mapping from the input space 𝒳 to the output
space 𝒴. This corresponds to the usual situation in machine learning, where 𝑦 = 𝑓 (𝑥) is a good
prediction of the true label of 𝑥. In this paper, we assume that 𝒴 ⊆ R. We want to stress that
this can correspond both to the classification and regression setting. In the regression setting, for
any input 𝑥 ∈ 𝒳 , 𝑓 (𝑥) is simply a real-valued quantity of interest, whereas in the classification
case 𝑓 (𝑥) corresponds to the pseudo-probability to fall into a given class.
The construction of the global surrogate on which GLEAMS relies to provide explanations is
a two-step process. The first step is to sample 𝑁 points 𝑥1 , . . . , 𝑥𝑁 , evenly spread in 𝒳 . For
1
https://github.com/giorgiovisani/GLEAMS
each of these points, we query 𝑓 to obtain 𝑦𝑖 = 𝑓 (𝑥𝑖 ). Thus we effectively create a dataset
(𝑥𝑖 , 𝑦𝑖 ), which we call measurement points.
Subsequently, the idea is to recursively split the input space 𝒳 and to approximate the model 𝑓
by a linear model on each cell of the partition until the linear model in each rectangular leaf
fits the measurement points with a sufficiently good accuracy. This process is summarized in
Figure 1. Once this global surrogate constructed, GLEAMS can provide both local and global
explanations for any new example to explain. Intuitively, given a partition with not too many
cells, it is convenient for the user to look at individual features and to visualize globally the
model as a piecewise-linear function. Concurrently, any new example to explain will fall into a
cell, and the user can get a local explanation solely by looking at the coefficients of the local
linear model. We now give more details on each of these steps.
2.1. Measurement points
Our main assumption, going into the description of the method, is the following:
Assumption 1. The input space 𝒳 is a hyper-rectangle
∏︀𝑑 of R𝑑 . That is, there exist reals numbers
𝑎𝑗 , 𝑏𝑗 ∈ R for any 𝑗 ∈ [𝑑] such that 𝒳 = 𝑗=1 [𝑎𝑗 , 𝑏𝑗 ].
Intuitively, this corresponds to a situation where each variable has a prescribed range (for
instance, age takes values in [0, 120]). In particular, we assume that further examples to explain
all fall within this range. If they do not, we attribute to these points the explanations corre-
sponding to the projection of these points on 𝒳 . Note that we do not assume normalized data:
𝑎𝑗 and 𝑏𝑗 can be arbitrary. In practice, the boundaries are either inferred from a training set, or
directly provided by the user.
A consequence of Assumption 1 is that we can easily find a set of points covering 𝒳 efficiently.
To achieve this, we use Sobol sequences [6]. In a nutshell, a Sobol sequence is a quasi-random
sequence of points 𝑥1 , . . . , 𝑥𝑁 filling the unit cube [0, 1]𝑑 as 𝑁 grows. We use Sobol sequences
because (a) we want to be able to provide explanations for the whole input space 𝒳 , thus the
measurement points should cover 𝒳 as 𝑁 grows; and (b) the decision surface of the black-box
model can be quite irregular, thus we want low discrepancy.
2.2. Splitting criterion
A very convenient way to partition the input space is to recursively split 𝒳 , cutting a cell if
some numerical criterion is satisfied. Additionally, we consider splits that are parallel to the
axes. The main reason for doing so is the tree structure that emerges, allowing later on for fast
query time of new inputs (linear in the depth of the final tree). In this section, we describe the
criterion used by GLEAMS.
A popular approach is to fit a constant model on each cell [7, CART]. We see two problems
with constant fits. First, this tends to produce large and thus hard to interpret trees (see, e.g.,
Chan and Loh [8]). Second, the local interpretability would be lost, since the local models would
not depend on the features in that case. Thus we prefer to fit linear models on each leaf, and
our numerical criterion should indicate, on any given leaf, if such simple model is a good fit
for 𝑓 . GLEAMS relies on a variant of model-based recursive partitioning [9, MOB] based on
score computations, described in detail in Appendix B.
2.3. Global surrogate model
To build the global surrogate model 𝑓^ , starting from the hyper-rectangle 𝒳 , we iteratively
split along the best dimension. This process is stopped once one of two criteria is met: i)
leaves have 𝑅2 higher than 0.95 (chosen empirically) or ii) number of points in the leaf is less
than 𝑛min threshold, set to 𝑛min = min(20, 𝑑 + 1). This recursive procedure is described in
Algorithm 2, in Appendix B. 𝑓^ is then achieved by sampling Sobol points on 𝒳 , computing the
value of the black-box model at these points, and then using Algorithm 2, Appendix B.
2.4. GLEAMS
Let us now assume that we computed the global surrogate model 𝑓^ , that is, a piecewise-linear
model based on a partition of 𝒳 . At query time, each new example to explain 𝜉 ∈ 𝒳 is rooted
to the corresponding hyper-rectangle 𝑅 in the tree structure, and thus associated to a linear
model 𝛽^ 𝜉 . From this local linear model, we can directly get different sorts of explanations.
Local explanations. Simply looking at the coefficient 𝛽 ^ 𝜉 tells us how important feature 𝑗 is to
𝑗
predict 𝑓 (𝜉), locally. The intuition here is that 𝑓 is well-approximated by 𝑥 ↦→ (𝛽 ^ 𝜉 )⊤ 𝑥 on the cell
𝑅, thus local variations of the model along specific axes are well-described by the coefficients of
^ 𝜉 . These local explanations can be obtained in constant time, without re-sampling and querying
𝛽
the model. Moreover, we have precise insights regarding the scale of these explanations, which
is given by the size of 𝑅. We see this as an advantage of using GLEAMS: the portion of space
on which the black-box model is locally approximated is well-identified and accessible to the
user. This is not the case with other methods such as LIME.
Global explanations. We define the global importance of feature 𝑗 as the aggregation of
the local importance of feature 𝑗 on all cells of the partition 𝒫 of 𝒳 . There are several ways
to aggregate those, GLEAMS outputs the weighted average of the absolute value of the local
importance. More precisely, let us define 𝛽^ 𝑅 the local model on hyper-rectangle 𝑅 ∈ 𝒫, then
the global importance of feature 𝑗 is given by
1 ∑︁ ⃒ 𝑅⃒
⃒^ ⃒
𝐼𝑗 := 𝒱(𝑅) ⃒𝛽 𝑗 ⃒ , (1)
𝒱(𝒳 )
𝑅∈𝒫
where 𝒱(𝐸) denotes the 𝑑-dimensional volume of 𝐸. The motivation for weighting by the cells’
volume in Eq. (1) is to take into account the fact that even though feature 𝑗 is very important
in a tiny region of the space, if it is not on all other cells then it is not globally important.
We take the absolute value to take into account the possible sign variations: if feature 𝑗 is
positively important on many cells but negatively important on a similar number of cells, then
simply taking the average would tell us that the feature is not globally important. Such global
attributions provide a faithful variables ranking, based on the impact they show on 𝑓 predictions.
positive
sqft_living positive
negative
grade
variables
sqft_living15
yr_built
long
−0.4 −0.2 0 0.2 0.4 0.6
coef
Figure 2: Gleams explanations consist of both: i) Local importance (feature attribution) and ii) coun-
terfactuals, i.e., answering what-if questions. On the left feature importance for a regressor trained on
the house sell dataset (Section 3), while figure on the right answers to “What if my house was bigger?”
Moving along feature sqft_living, for a given example (yellow dot), we can visualize specific values
of 𝑓 (Sobol points in blue) as well as the GLEAMS linear approximations (in green).
𝜉
Counterfactual explanations. Querying this new model 𝑓^ 𝑗 at different values of 𝑥𝑗 , we can
answer to the question “what would be the decision if we changed feature 𝑗 by this amount?”
More precisely, for a given example 𝜉 and a feature 𝑗, we can look at the evolution of 𝑓^ when all
coordinates of the input are fixed to 𝜉, except the 𝑗th: it suffices to travel in the cells intersecting
the line of equation 𝑥𝑗 = 𝜉𝑗 and to read the coefficients of the associated linear models. To be
precise, we compute
𝑊𝑗 (𝑥) := 𝑓^ (𝜉1 , . . . , 𝜉𝑗−1 , 𝑥, 𝜉𝑗+1 , . . . , 𝜉𝑑 ) . (2)
This can be computed quickly, since, again, there is no sampling and further calls to 𝑓 . This
allows us to present the user with a cursor which can be moved to set the feature value and
present explanations in real time (see Figure 2).
3. Experiments on real data
Our goal here is to show that GLEAMS provides explanations whose quality is comparable
to that of other attribution approaches, while providing these attributions in constant time
and additional insights. We benchmark the various methods on the Wine dataset [10], House
sell dataset2 and Parkinson telemonitoring dataset [11]. We refer to Appendix D for more
experiments.
Models. We considered two different models, trained similarly across all datasets. The first is
an XGBoost model [12]. XGBoost iteratively aggregates base regressors greedily minimizing
a proxy loss. Following Friedman [13] prescriptions, we employ simple CART trees with
maximum depth 2 as base regressors, learning rate of 0.05, and early stopping rounds set to
100. The second is a multi-layer perceptron (MLP), composed by two hidden dense layers of 264
neurons each, trained by adaptive stochastic gradient descent [14, ADAM] and early stopping on
a hold-out validation set. Both these models achieve state-of-the-art accuracy in many settings
and are not inherently interpretable.
2
available at https://www.openml.org/search?type=data&status=active&id=42092
Table 1
Experimental results (higher is better), 5th and 95th confidence intervals are to be found in brackets.
GLEAMS is on par with state-of-the-art explanation methods in terms of reliability of explanations.
dataset evaluation LIME SHAP PDP GLEAMS
XGB MLP XGB MLP XGB MLP XGB MLP
wine local 0.38 0.51 0.40 0.53 0.56 0.84 0.51 0.77
[-0.09, 0.77] [0.19, 0.84] [-0.08, 0.76] [0.22, 0.78] [0.23, 0.83] [0.69, 0.95] [0.15, 0.78] [0.7, 0.86]
wine global 0.24 0.74 0.27 0.78 0.70 0.89 0.36 0.85
[-0.27, 0.66] [0.53, 0.9] [-0.19, 0.65] [0.53, 0.93] [0.44, 0.9] [0.78, 0.97] [-0.19, 0.79] [0.69, 0.95]
recall
wine 0.89 0.80 1.0 0.87 0.50 0.50 0.77 0.75
(6 true features)
[0.67, 1.0] [0.67, 1.0] [1.0, 1.0] [0.83, 1.0] [0.5, 0.5] [0.5, 0.5] [0.5, 0.83] [0.5, 1.0]
house local 0.05 0.63 0.52 0.82 0.51 0.83 0.37 -0.19
[-0.25, 0.32] [0.37, 0.81] [0.22, 0.79] [0.73, 0.89] [0.73, 0.9] [0.74, 0.9] [0.26, 0.47] [-0.3, -0.05]
house global 0.23 0.63 0.37 0.81 0.38 0.82 0.47 0.24
[-0.09, 0.55] [0.36, 0.1] [0.07, 0.64] [0.69, 0.87] [0.26, 0.54] [0.71, 0.9] [0.07, 0.72] [-0.02, 0.57]
recall
house 0.85 0.74 0.99 0.69 0.40 0.40 0.61 0.58
(10 true features)
[0.7, 1.0] [0.6, 0.8] [0.9, 1.0] [0.5, 0.8] [0.4, 0.4] [0.4,0.4] [0.4, 0.7] [0.4,0.7]
Parkinson local 0.10 0.26 0.47 0.55 0.28 0.49 0.50 0.01
[-0.11, 0.41] [-0.04, 0.59] [0.3, 0.66] [0.28, 0.76] [0.16, 0.34] [0.26, 0.76] [0.36, 0.6] [-0.2, 0.23]
Parkinson global 0.31 0.46 0.41 0.71 0.52 0.66 0.30 0.36
[0.02, 0.59] [0.16, 0.71] [0.08, 0.71] [0.47, 0.88] [0.29, 0.71] [0.43, 0.83] [-0.06, 0.63] [0.01, 0.68]
recall
Parkinson 0.86 0.77 0.97 0.80 0.40 0.40 0.50 0.60
(10 true features)
[0.7, 1.0] [0.5, 0.8] [0.9, 1.0] [0.4, 0.7] [0.4, 0.4] [0.4, 0.4] [0.3, 0.7] [0.43, 0.6]
Methods. We compared GLEAMS to three methods, namely LIME for tabular data, SHAP,
and PDP. We used default parameters, except for the number of feature combinations tested
in SHAP for the recall metric, which were shrinked to 500 to limit computing time. GLEAMS
results have been obtained using 𝑁 = 15 (number of Sobol points), which guaranteed a running
time in the order of 5 minutes for each of the three datasets at hand.
Evaluation. We compare GLEAMS to existing methodology using monotonicity and recall.
For each interpretability method to evaluate, for each point in the test set, we compute the
vectors of attributions 𝛼 ∈ R𝑑 and expected loss 𝑒 ∈ R𝑑 restricted to the corresponding
feature. Monotonicity is then defined as the Spearman rank correlation between |𝛼| and 𝑒 [15].
Depending on the region where the 𝑒 values are computed we obtain local monotonicity,
i.e., inside each specific GLEAMS leaf, or global monotonicity when considering the whole
input space. Let us now consider a model trained to use only a subset 𝑇 of the features. We can
actually be certain that some feature attributions should be 0. For any given example 𝜉, we can
define 𝑇 𝜉 the set of the top |𝑇 | features, ranked by |𝛼𝑗 |. Recall of Important Features [5] is
the fraction of 𝑇 features retrieved in 𝑇 𝜉 , averaged among the test units. More on this in the
Appendix C.
Results. We present our results in Table 1, reporting the average metrics taken on the test set.
All evaluation metrics are described in Appendix C.
PDP generally achieves better monotonicity metrics, since it is designed precisely to obtain
feature attributions related to the feature impact on the predictions, but it performs worse on
the recall task. We notice that GLEAMS shows better results on local and global monotonicity
compared to LIME and SHAP on the wine dataset, while GLEAMS performances start to degrade
with an increased number of features. In particular we notice the poor performance on local
monotonicity of the MLP model for the Parkinson dataset. The degradation is due to the
higher dimensionality of the two datasets, which makes models surface more complex (MLP in
particular). Increasing 𝑁 would likely improve the results, enabling smaller partitions and more
accurate local models. Unfortunately, we did not have time to run experiments with higher 𝑁 .
Regarding the recall metric, SHAP stands as the best in class, while GLEAMS is usually slightly
worse but still comparable with LIME, and systematically better than PDP.
4. Conclusion
In this paper, we presented GLEAMS, a new interpretability method that approximates a black-
box model by recursively partitioning the input space and fitting linear models on the elements
of the partition. Both local and global explanations can then be obtained in constant time, for
any new example, in sharp contrast with existing post hoc methods such as LIME and SHAP.
The main limitation of the method is the assumption that all features are continuous. As
future work, we aim to extend GLEAMS to mixed features (both categorical and continuous).
Another limitation of the method is the initial number of model queries needed. One possible
way to reduce it would be to evaluate the local regularity of 𝑓 and to sample less when the
model is smooth.
References
[1] V. Borisov, T. Leemann, K. Seßler, J. Haug, M. Pawelczyk, G. Kasneci, Deep neural networks
and tabular data: A survey, IEEE Transactions on Neural Networks and Learning Systems
(2022).
[2] S. Wachter, B. Mittelstadt, L. Floridi, Why a Right to Explanation of Automated Decision-
Making Does Not Exist in the General Data Protection Regulation, International Data
Privacy Law 7 (2017) 76–99.
[3] A. Adadi, M. Berrada, Peeking Inside the Black-Box: A Survey on Explainable Artificial
Intelligence (XAI), IEEE Access 6 (2018) 52138–52160.
[4] P. Linardatos, V. Papastefanopoulos, S. Kotsiantis, Explainable AI: A review of machine
learning interpretability methods, Entropy 23 (2020) 18.
[5] M. T. Ribeiro, S. Singh, C. Guestrin, Why Should I Trust You?: Explaining the Predictions
of Any Classifier, in: Proceedings of the 22nd ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, ACM, 2016, pp. 1135–1144.
[6] I. M. Sobol, Points which uniformly fill a multidimensional cube, Mathematics, cybernetics
series (1985) 32.
[7] L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone, Classification and regression trees,
Wadsworth & Brooks / Cole Advanced Books & Software, 1984.
[8] K.-Y. Chan, W.-Y. Loh, LOTUS: An algorithm for building accurate and comprehensible
logistic regression trees, Journal of Computational and Graphical Statistics 13 (2004)
826–852.
[9] A. Zeileis, T. Hothorn, K. Hornik, Model-based recursive partitioning, Journal of Compu-
tational and Graphical Statistics 17 (2008) 492–514.
[10] P. Cortez, A. Cerdeira, F. Almeida, T. Matos, J. Reis, Modeling wine preferences by data
mining from physicochemical properties, Decision support systems 47 (2009) 547–553.
[11] A. Tsanas, M. Little, P. McSharry, L. Ramig, Accurate telemonitoring of parkinson’s disease
progression by non-invasive speech tests, Nature Precedings (2009) 1–1.
[12] T. Chen, C. Guestrin, XGBoost: A Scalable Tree Boosting System, in: Proceedings of the
22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,
2016, pp. 785–794.
[13] J. H. Friedman, Greedy function approximation: a gradient boosting machine, The Annals
of Statistics (2001) 1189–1232.
[14] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, arXiv preprint
arXiv:1412.6980 (2014).
[15] A.-P. Nguyen, M. R. Martínez, On quantitative aspects of model interpretability, arXiv
preprint arXiv:2007.07584 (2020).
[16] M. Craven, J. W. Shavlik, Extracting tree-structured representations of trained networks,
Advances in Neural Information Processing Systems (1996) 24–30.
[17] J. R. Quinlan, C4.5: Programs for Machine Learning, Elsevier, 1993.
[18] R. D. Gibbons, G. Hooker, M. D. Finkelman, D. J. Weiss, P. A. Pilkonis, E. Frank, T. Moore,
D. J. Kupfer, The CAD-MDD: A computerized adaptive diagnostic screening tool for
depression, The Journal of clinical psychiatry 74 (2013) 669.
[19] Y. Zhou, G. Hooker, Interpreting Models via Single Tree Approximation (2016).
[20] J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, L. Wasserman, Distribution-free predictive
inference for regression, Journal of the American Statistical Association 113 (2018) 1094–
1111.
[21] S. M. Lundberg, S.-I. Lee, A unified approach to interpreting model predictions, Advances
in neural information processing systems 30 (2017).
[22] M. T. Ribeiro, S. Singh, C. Guestrin, Anchors: High-precision model-agnostic explanations,
in: Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[23] M. Setzu, R. Guidotti, A. Monreale, F. Turini, D. Pedreschi, F. Giannotti, Glocalx-from local
to global explanations of black box AI models, Artificial Intelligence 294 (2021) 103457.
[24] F. Harder, M. Bauer, M. Park, Interpretable and differentially private predictions, in:
Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 2020, pp. 4083–
4090.
[25] E. C. Merkle, A. Zeileis, Tests of Measurement Invariance without Subgroups: A General-
ization of Classical Methods, Psychometrika 78 (2013) 59–82.
[26] J. Zhou, A. H. Gandomi, F. Chen, A. Holzinger, Evaluating the quality of machine learning
explanations: A survey on methods and metrics, Electronics 10 (2021) 593.
[27] F. Doshi-Velez, B. Kim, Towards a rigorous science of interpretable machine learning,
arXiv preprint arXiv:1702.08608 (2017).
[28] C. Spearman, The proof and measurement of association between two things, The
American journal of psychology 100 (1904) 441–471.
[29] G. F. Montufar, R. Pascanu, K. Cho, Y. Bengio, On the number of linear regions of deep
neural networks, Advances in neural information processing systems 27 (2014).
A. Related work
The idea of approximating globally a complex model such as a deep neural network by a simpler
surrogate model relying on a tree-based partition of the space can be dated back at Craven and
Shavlik [16]. The proposed method, TREPAN, approximates the outputs of the network on
the training set by a decision tree, choosing the splits using the gain ratio criterion [17]. More
recently, inspired by Gibbons et al. [18], Zhou and Hooker [19] proposed to use another split
criterion, based upon an asymptotic expansion of the Gini criterion. Both these approaches
are limited to the classification setting, and also require access to the training data (which is
implicitly assumed to have a good covering of the input space).
From the interpretability side, a standard way to explain 𝑓 , which is closely related to our
approach, is to compute attributions scores for each feature. Lei et al. [20] exclude a specific
feature from 𝑓 and define its impact as the deterioration of model predictions. On the contrary,
Partial Dependence Plots (PDP) developed by Friedman [13] measure the sensitivity of 𝑓 to
changes in the specific feature, isolating its effect from the ones of the other features. Ribeiro
et al. [5] propose LIME, which proposes as attribution for a specific example the coefficients of
a linear model approximating 𝑓 locally. Similarly, Lundberg and Lee [21] introduce the idea
of decomposing 𝑓 predictions into single variables attributions, using SHAP. The technique
samples combinations of features 𝑆 and average changes in single instance prediction between
the restricted 𝑓 (𝑆 ∪ 𝑖) against 𝑓 (𝑆), obtaining local attributions for the feature 𝑖. Global SHAP
attributions arise by averaging local attributions over the entire dataset.
Attribution methods usually have to be recomputed for each new example, a caveat that we
propose to overcome with GLEAMS, computing a global surrogate and relying on it to provide
explanations. We are not the first to propose to provide explanations on a global scale: Ribeiro
et al. [22] propose Anchors, a method extracting local subsets of the features (anchors) that
are sufficient to recover the same prediction, while having a good global coverage. A caveat of
the method is that local explanations are not quantitative since all members of a given anchor
are equivalent. Additionally, the anchors can have many elements if the example at hand is
near the decision boundary. Let us also mention Setzu et al. [23], which proposes to aggregate
local explanations: starting from local decision rules, GlocalX combines them in a hierarchical
manner to form a global explanation of the model. In the ad hoc setting, Harder et al. [24]
proposes to train an interpretable and differentially private model by using several local linear
maps per class: the pseudo-probability of belonging to a given class is the softmax of a mixture
of linear models. This approach is limited to the classification setting, as with GlocalX and
Anchors.
B. Splitting criterion
Intuitively, any well-behaved function can be locally approximated by a linear component,
yielding a statistical model which we now describe. On any given leaf, for any given feature 𝑗,
we can reorder the measurement points such that the points contained in the leaf are 𝑥1 , . . . , 𝑥𝑛 ,
with 𝑥1,𝑗 ≤ · · · ≤ 𝑥𝑛,𝑗 . To these points correspond model values 𝑦1 , . . . , 𝑦𝑛 . In accordance
with the intuition given above, we write 𝑦𝑖 = 𝛽 ⊤ 𝑥
˜ 𝑖 + 𝜖𝑖 for all 𝑖 ∈ [𝑛], where 𝛽 ∈ R𝑑+1 are the
coefficients of our local linear model, 𝑥
˜ 𝑖 ∈ R𝑑+1 is the concatenation of 𝑥𝑖 with a leading 1 to
take the intercept into account, and 𝜖𝑖 is an error term. Let us now follow Merkle and Zeileis
[25] and make an i.i.d. Gaussian assumption on the 𝜖𝑖 s, giving rise to the likelihood
(︂ )︂
1 −1 ⊤
ℒ(𝛽; 𝑥𝑖 ) = exp (𝑦𝑖 − 𝛽 𝑥˜𝑖)2
, (3)
(2𝜋𝜎 2 )𝑑/2 2𝜎 2
where 𝜎 2 > 0 is the variance of 𝜖𝑖 for all 𝑖 ∈ [𝑛]. Taking the log in Eq. (3), the log-likelihood of
a single observation is given by
{︂ }︂
−1 1 ⊤
ℓ(𝛽; 𝑥𝑖 ) = (𝑦𝑖 − 𝛽 𝑥 2
˜ 𝑖 ) + 𝑑 log 2𝜋𝜎 2
. (4)
2 𝜎2
The individual scores are obtained by taking the partial derivatives of the log-likelihood with
respect to the parameters, that is, for any 𝑖 ∈ [𝑛],
(︂ )︂⊤
𝜕ℓ(𝛽; 𝑥𝑖 ) 𝜕ℓ(𝛽; 𝑥𝑖 ) 𝜕ℓ(𝛽; 𝑥𝑖 )
𝑠(𝛽; 𝑥𝑖 ) = , ,..., . (5)
𝜕𝛽0 𝜕𝛽1 𝜕𝛽𝑑
7.5
measurement points
5.0
2.5
0.0
f(xi)
2.5
5.0
7.5
10.0
0 25 50 75 100 125 150 175 200
cumulative score process (norm)
2000
1500
||B(t)||
1000
500
0
0 25 50 75 100 125 150 175 200
t
Figure 3: Evolution of the norm of the cumulative score process. Top panel: measurements of a
piecewise-linear model (dark dots) visualized along one axis. Bottom panel: evolution of ‖𝐵(𝑡)‖1 as a
function of 𝑡 (solid blue line). The process presents a clear maximum, which gives us a candidate split
for this axis (vertical red line).
A straightforward computation yields
(︁ )︁
𝑠(𝛽; 𝑥𝑖 ) = 𝑦𝑖 · 𝑥
˜𝑖 − 𝑥 ˜⊤
˜𝑖𝑥 𝑖 𝛽 𝜎 −2 . (6)
The maximum likelihood estimate 𝛽 ^ is obtained by solving ∑︀ 𝑠(𝛽; 𝑥𝑖 ) = 0: in this case this
𝑖
coincides with the ordinary least-squares estimate, in a sense the best linear fit on the entire leaf.
However, what we want is to split this leaf if the deviations from the linear model computed on
the whole leaf are too strong. Therefore, we compute the cumulative score process defined by
⌊𝑛𝑡⌋
^ ) = √1
∑︁
∀𝑡 ∈ [0, 1], 𝐵 (𝑗) (𝑡; 𝛽 ^ ; 𝑥𝑖 ) ,
𝑠(𝛽 (7)
𝑛
𝑖=1
and take as a criterion the maximum of the 𝐿1 norm of 𝐵 (𝑗) (𝑡), across all features. The
computation of the best split is described in Algorithm 1 and we provide an example in Figure 3.
Note that Eq. (7) corresponds to Eq. (13) in Merkle and Zeileis [25], with the notable difference
that Eq. (13) is normalized (by the square root of the estimated covariance matrix of the scores).
We observe empirically that normalizing yields worse results when detecting the splits.
Algorithm 1 GetBestSplit: Get the best split for a given leaf.
Require: 𝑥1 , . . . , 𝑥𝑛 : Sobol points in current leaf; 𝑦1 , . . . , 𝑦𝑛 : corresponding 𝑓 values
1: for 𝑗 = 1 to 𝑑 do
2: re-order 𝑥1 , . . . , . . . , 𝑥𝑛 according to feature 𝑗
3: re-order 𝑦1 , . . . , 𝑦𝑛 accordingly
4: compute 𝛽 ^ = OLS(𝑦; 𝑥)
5: compute predictions 𝑦^𝑖
1 ∑︀𝑛
6: set 𝜎 = 𝑛 𝑖=1 (𝑦𝑖 − 𝑦^𝑖 )2
2
7: compute scores 𝑠(𝛽 ^ ; 𝑥𝑖 ) according to Eq. (6)
8: compute 𝐵 according
(𝑗)
⃦ to Eq. ⃦
(7)
9: store 𝑚𝑗 = max𝑡∈[0,1] ⃦𝐵 (𝑗) (𝑡)⃦1
store 𝑡𝑗 = arg max𝑡∈[0,1] ⃦𝐵 (𝑗) (𝑡)⃦
⃦ ⃦
10: 1
11: return 𝑗 ⋆ = arg max 𝑗∈[𝑑] 𝑚𝑗 , feature to split
12: return 𝑡⋆𝑗 , value of the split
^ , local linear model
13: return 𝛽
Algorithm 2 RecTree: Recursive construction of 𝑓^ .
Require: 𝑅: hyper-rectangle; 𝑆: Sobol points inside 𝑅; 𝑉 : values of 𝑓 on 𝑆
1: initialize 𝑇 ← 𝒳 , tree storing partition and models
2: for 𝐿 ∈ 𝑇.leaves do
3: if 𝑅2 (𝐿) ≤ 𝜌 and 𝑛(𝐿) ≥ 2𝑛min then
4: set 𝑥 = {𝑥1 , . . . , 𝑥𝑛 } = 𝑆 ∩ 𝐿
5: set 𝑦 = {𝑦1 , . . . , 𝑦𝑛 } accordingly
6: (𝑗, 𝑡𝑗 ) = GetBestSplit(𝑥, 𝑦)
7: 𝐿ℓ ← 𝐿 ∩ {𝑥 : 𝑥𝑗 ≤ 𝑡𝑗 }
8: 𝐿𝑟 ← 𝐿 ∩ {𝑥 : 𝑥𝑗 > 𝑡𝑗 }
9: 𝐿.left_child ← RecTree(𝐿ℓ , 𝑆, 𝑉 )
10: 𝐿.right_child ← RecTree(𝐿𝑟 , 𝑆, 𝑉 )
return 𝑇
Algorithm 3 GlobalSurrogate: Compute the global surrogate model used by GLEAMS.
Require: 𝑓 : black-box model; 𝒳 or its boundaries; 𝑁 : number of Sobol points; 𝜌: 𝑅2 threshold;
𝑛min : min. number of points per leaf
1: generate 𝑆 = {𝑥1 , . . . , 𝑥𝑁 } Sobol points in 𝒳
2: compute 𝑦𝑖 = 𝑓 (𝑥𝑖 )
3: 𝑉 ← {𝑦1 , . . . , 𝑦𝑁 }
4: return 𝑇 ← RecTree(𝒳 , 𝑆, 𝑉 )
C. Evaluation
Evaluating interpretability methods is quite challenging: for a given machine learning model,
there is rarely a ground-truth available, telling us which features were used for a given prediction.
Zhou et al. [26] outline two main evaluation methodologies: human-centered evaluations, and
functionality-grounded (quantitative, note that the terminology was introduced by Doshi-Velez
and Kim [27]). We focus on the latter, since human-centered evaluations are hard to obtain
and can be unreliable. Among those, we choose to compare GLEAMS to existing methodology
using monotonicity and recall. Below we briefly describe these two metrics.
Monotonicity is defined as the correlation between the absolute value of the attributions
at a given point and the expected loss of the model restricted to the corresponding feature.
Intuitively, this takes high values if the model is very imprecise when it does not know the
feature at hand. This is Metric 2.3 in Nguyen and Martínez [15]. Following their notation, for
each interpretability method to evaluate, for each point in the test set, we compute on the one
hand a vector of attributions 𝛼 ∈ R𝑑 and on the other hand a vector of expected loss 𝑒 ∈ R𝑑 .
Monotonicity is then defined as the Spearman rank correlation [28] between |𝛼| and 𝑒. Formally,
for all 𝑗 ∈ [𝑑], 𝑒𝑗 is defined as
∫︁ 𝑏𝑗
𝑒𝑗 = ℓ(𝑓 (𝜉), 𝑓𝑗 (𝑥))𝑝(𝑥)d𝑥 , (8)
𝑎𝑗
where 𝑓𝑗 is the restriction of 𝑓 to coordinate 𝑗 (keeping all other coordinates equal to those of
𝜉), 𝑝 is a probability distribution on [𝑎𝑗 , 𝑏𝑗 ] (recall that 𝑎𝑗 and 𝑏𝑗 denote the boundaries of 𝒳
along dimension 𝑗, see Assumption 1), and ℓ is the squared loss.
Let us define 𝒰(𝐶) the uniform distribution on a compact set 𝐶. In our experiments, we
consider two natural choices of 𝑝 in Eq. (8). First, 𝑝 ∼ 𝒰([ℓ𝑗 , 𝑟𝑗 ]), where ℓ𝑗 (resp. 𝑟𝑗 ) are the left
(resp. right) boundaries of 𝑅 along feature 𝑗, where 𝑅 is the cell containing 𝜉. This corresponds
to local monotonicity: how well the attributions reflect the variations in prediction locally,
that is, from the point of view of GLEAMS, on 𝑅. Second, 𝑝 ∼ 𝒰([𝑎𝑗 , 𝑏𝑗 ]), which corresponds
to global monotonicity: how well the attributions reflect the variations in prediction on the
whole input space along feature 𝑗.
Let us conclude this section by defining formally the Recall of Important Features. For
certain models, we can actually be certain that some feature attributions should be 0. This is
the case, for instance, if we force our model 𝑓 to use only a subset of the features. As a measure
of the quality of explanations, one can then compare the top features selected by an attribution
method to the set of true features, which we know. Let us call 𝑇 the set of true features. For any
given example 𝜉, we can define 𝑇 𝜉 the set of the top |𝑇 | features, ranked by |𝛼𝑗 |. Originally
proposed by Ribeiro et al. [5], the recall of important features is then defined as
⃒ ⃒
⃒𝑇 ∩ 𝑇 𝜉 ⃒
𝜌(𝜉) := . (9)
|𝑇 |
Intuitively, 𝜌(𝜉) is large (close to one) if the considered attribution method gives large attributions
to the true features. In our experiments, we report the average recall over all points of the test
set unless otherwise mentioned.
D. Toy data experiments
3
15 15 3
10 10 2.5
2.5
5 5 2
2
0 0
1.5
1.5
−5 −5
1
1
−10 −10
0.5
0.5
−15 −15
0
0
−20 −20
−0.5
Figure 4: Approximating piecewise-linear models with GLEAMS surrogate model. Left panels: example
(i), model on the left and GLEAMS surrogate on the right. Right panels: example (ii), model on the left
and GLEAMS surrogate on the right.
As a first sanity check, we ran the partition scheme of GLEAMS on simple models and
checked whether the surrogate model 𝑓^ was indeed close to the true model 𝑓 . In order to have
a ground-truth for the partition, we chose partition-based models, i.e., there exist a partition 𝒫
of 𝒳 such that the parameters of 𝑓 are constant on each rectangular cell 𝑅 ∈ 𝒫. We considered
a simple setting where the model is piecewise-linear with rectangular cells, a situation in which
GLEAMS could, in theory, recover perfectly both the underlying partition and the coefficients of
the local models. We present here two examples: (i) a discontinuous piecewise-linear model with
arbitrary coefficients, and (ii) a piecewise-linear model with continuity constraints. Example
(i) is a generalization of the surface produced by a Random Forest regressor, while example
(ii) is reminiscent of a fully-connected, feedforward, ReLU activated neural network. Note
however that for the latter, the cells of the partition are more complicated than simple rectangle,
see Montufar et al. [29] (in particular Figure 2). In each case, GLEAMS recovers perfectly the
underlying model, as demonstrated in Figure 2.
It is interesting to notice that, despite having a stopping criterion on the coefficient of
determination, not all leaves satisfy this criterion since the other stopping criterion is a minimal
number of points per leaf. Thus it is possible to end up in situations where the 𝑅2 on a given leaf
is sub par. Nevertheless, these leaves are by construction quite small. For instance, in example
(i), the average 𝑅2 is equal to 1, and in example (ii) it is equal to .98.