On the Safety of Interpretable Machine Learning: A Maximum Deviation Approach
Authors: Dennis Wei
Rahul Nair
Amit Dhurandhar
Kush R. Varshney
Elizabeth M. Daly
Moninder Singh
Venue: ICLR 2022 Submitted (2022)
Keywords: safety
interpretability
explainability

Abstract: Interpretable and explainable machine learning has seen a recent surge of interest. We posit that safety is a key reason behind the demand for explainability. To explore this relationship, we propose a mathematical formulation for assessing the safety of supervised learning models based on their maximum deviation over a certification set. We then show that for interpretable models including decision trees, rule lists, generalized linear and additive models, the maximum deviation can be computed exactly and efficiently. For tree ensembles, which are not regarded as interpretable, discrete optimization techniques can still provide informative bounds. For a broader class of piecewise Lipschitz functions, we repurpose results from the multi-armed bandit literature to show that interpretability produces tighter (regret) bounds on the maximum deviation compared with black box functions. We perform experiments that quantify the dependence of the maximum deviation on model smoothness and certification set size. The experiments also illustrate how the solutions that maximize deviation can suggest safety risks.

Under review as a conference paper at ICLR 2022
ON THE SAFETY OF INTERPRETABLE MACHINE LEARNING: A MAXIMUM DEVIATION APPROACH
Anonymous authors Paper under double-blind review
ABSTRACT
Interpretable and explainable machine learning has seen recent surge of inter- est. We posit that safety is a key reason behind the demand for explainability. To explore this relationship, we propose mathematical formulation for assess- ing the safety of supervised learning models based on their maximum deviation over certification set. We then show that for interpretable models including decision trees, rule lists, generalized linear and additive models, the maximum deviation can be computed exactly and efficiently. For tree ensembles, which are not regarded as interpretable, discrete optimization techniques can still provide informative bounds. For broader class of piecewise Lipschitz functions, re- purpose results from the multi-armed bandit literature to show that interpretability produces tighter (regret) bounds on the maximum deviation compared with black box functions. We perform experiments that quantify the dependence of the max- imum deviation on model smoothness and certification set size. The experiments also illustrate how the solutions that maximize deviation can suggest safety risks.
INTRODUCTION
Interpretable and explainable machine learning (ML) has seen a recent surge of interest because it is viewed as one of the key pillars in making models trustworthy, with implications on fairness, reliability, and safety (Varshney, 2019). It is generally accepted that the ultimate measure of ML explainability is whether human finds the explanations useful (Doshi-Velers & Kiml 2017] Dhu- randhar et al. 2017). However, less attention has been paid to deeper reasons behind the human desire for explainability. In this paper, we posit an important reason is toward achieving safety and preventing unexpected harms (Varshney & Alemzadeh] 2017). This reason is implicit in the dichotomy between directly interpretable models vs. post hoc explanations of black-box models. Some argue that only directly interpretable models should be used in high-risk applications (Rudin, 2019). The crux of this argument is that post hoc explanations leave a gap between the explana- tion and the model that is producing the predictions. Thus, unusual data points may appear to be harmless based on the explanation, but truly cause havoc. This argument however does not explic- itly address the question: What does safety mean for such models, and how is it intertwined with interpretability?
Towards answering this question, we propose mathematical definition for assessing the safety of supervised learning (i.e. predictive) models. Viewing these models as functions mapping an input space an output space, a key way in which these models can cause harm is through grossly unex- pected outputs, corresponding to inputs that are poorly represented in training data. Accordingly, we approach safety assessment for model by determining its maximum deviation over a certification se/ from the output of reference model. The idea of a certification set is that it is a large subset of the input space and is intended to cover all conceivable inputs to the model. The reference model could be simple, well-understood model or existing model that has been "tried and tested." These concepts are discussed further in Section 2
In Section 4 we discuss the computation of the maximum deviation for different model classes and show how this is facilitated by interpretability. For model classes regarded as interpretable, including trees, rule lists, generalized linear and additive models, the maximum deviation be computed exactly and efficiently by exploiting the model structure. For tree ensembles, which are not regarded interpretable, discrete optimization techniques exploit their composition in terms of trees

---

Under review as a conference paper at ICLR 2022
to provide anytime bounds the maximum deviation. The case of trees is also generalized in different direction by considering a broader class of functions that are piccewise Lipschitz, which we argue cover many popular interpretable functions. Here we show that the benefit of interpretability is significantly tighter regret bounds on the maximum deviation compared with black box functions, by appropriately repurposing results from the multi-armed bandit literature in this context. On the other hand, it is less clear that post hoc explanations, which approximate a model locally (Ribeiro) al., 2016; Lundberg & Lee, 2017; Dhurandhar et al. 2018 or globally (Buciluă al. 2006 Hinton et al. 2015), can help with evaluating the maximum deviation and hence safety.
We conduct experiments illustrate the deviation maximization methods in Section 4 decision trees, linear and additive models, and tree ensembles. The results in Section [5] quantify how the maximum deviation increases as the size of the certification set increases and as the smoothness of the models decreases. For tree ensembles, we find that the obtained upper bounds on the maximum deviation are informative, showing that the maximum deviation does not increase with the number of trees in the ensemble. We also study the feature combinations that maximize deviation, which can shed light on the sources of extreme model outputs and guide further investigation.
Overall, our discussion suggests that a reason for preferring more interpretable models is that it is easier to assess them for unexpected and potentially unsafe outputs.
2 ASSESSING SAFETY THROUGH MAXIMUM DEVIATION
We are given a supervised learning model f, which is function mapping an input feature space X' to an output space V. We wish to assess the safety of this model by finding its worst-case deviation from given reference model fu X' + V. To do this, we additionally require 1) a measure of deviation D ) x y + RR,, where R+ is the set of non-negative reals, and 2) a certification set C X over which the deviation is maximized. Then the problem to be solved is
max D(f(z),
(1)
#EC
The deviation is worst-case because the maximization is over all x E C: further implications of this are discussed in Appendix C
We view problem [I as means toward the goal of evaluating safety. In particular, a large deviation value is not necessarily indicative of safety risk, as two models may differ significantly for valid reasons. For example, one model may capture useful pattern that the other does not. What large deviation values do indicate, however, is a (possibly) sufficient reason for further investigation. Hence, the maximizing solutions in (T) (i.e., the arg max) are of operational interest.
Below we further discuss some elements in this problem formulation.
Output space y. In the case of regression, y is the set of reals lR or an interval thereof. In the case of binary classification, while ) could be f0, 1} or [-1,+1}, these limit the possible deviations to binary values as well ("same" or "different"). Thus to provide more informative results, we take Y' to be the space of real-valued scores that thresholded to produce binary label. For example, y could be a predicted probability in [0. 1] or a log-odds ratio in R. Similarly for multi- class classification with M classes, y R. could be a M-dimensional space real-valued scores. Models that abstain can also be accommodated as noted in Appendix A
Reference model fo. The premise of the reference model is that it should be "safe" above all. The simplest case mathematically is for fo to be a constant function representing a baseline value, for example zero. More generally, fo may be simple model that can be readily grasped by a human, may be validated against domain knowledge, or may be based on small number of expert-selected features. Such models are common in medical risk assessment, consumer finance, and predicting semiconductor yield. By simple, we mean for example linear model with 10 non-zero coefficients or a decision tree with 10 leaves. The reference model could also be an existing model that is not necessarily simple but has been extensively tested and deployed. In this case, f could be new version of the model, trained on more recent data or improved in some fashion, and we wish to evaluate its safety before deploying it in place of fo- In this and more complex settings, fo may not be globally interpretable, but may be so in local regions. The machinery developed in this work could be applied in these settings as well to assess the safety of f (more discussion in Appendix C
2

---

Under review as a conference paper at ICLR 2022
Certification set C. The premise of the certification set is that it contains all inputs that the model might conceivably be exposed to. This may include inputs that are highly improbable but not phys- ically or logically impossible (for example, severely hypothermic human body temperature of 27*C). Thus, while C might be based on the support set of a probability distribution or data sample, does not depend the likelihood of points within the support. The set C may also be strict perset of the training data domain. For example, a model may have been trained on data for males, and we would now like determine its worst-case behavior on an unseen population of females.
For tabular or lower-dimensional data, C might be the entire input space X. For non-tabular or dibhes-dimensional data, the choice C X may be too unrepresentative because the manifold of realistic inputs is lower in dimension. In this case, if we have a dataset {x,}== one possibility is to use a union of Ep balls centered at J3,
C=
BC (aa)
BR = {a E X' ||0 - rullp S sr..
(2)
1=1
The set C is thus comprised of points somewhat close the observed examples 24, but the radius r does not have to be "small".
In addition to determining the maximum deviation over the entire set C, maximum deviations over subsets of C (e.g.. different age groups) may also be of interest. For example, Appendix [.] shows deviation values separately for leaves of decision tree, which partition the input space.
RELATED WORK
Our work relates to number of different technical directions. Varshney & Alemzadeh (2017) and Mohseni et al. (202T) give qualitative accounts suggesting that directly interpretable models are an inherently safe design because humans can inspect them to find spurious elements; in this paper, attempt to make those qualitative suggestions more quantitative. Furthermore, several other authors have highlighted safety as goal for interpretability. but without much further development as done here (Otte) 2013 Doshi-Velez. & Kim 2017; Tomsett et al. 20188 Gilpin et al. [0018] Rudin (019)). Moreover, there no consensus on how to measure interpretabillity. which motivates the relationship explored in this paper between interpretability and the ease of evaluating safety.
In the area of ML verification, robustness certification methods aim to provide guarantees that the classification remains constant within radius of an input point, while output reachability is con- cerned with characterizing the set of outputs corresponding to a region of inputs (Wong & Kolter 2018 Raghunathan et al.) 2018 Huang et al.] 2020). Our problem of deviation maximization ( is more closely related to output reachability. The differences in our work are: I) we consider two models, model f to be assessed and a reference fo. and are interested in their difference mea- sured by deviation function D; 2) our focus is global, over a comprehensive set C, rather than local to small neighborhoods around input points; 3) study the role of interpretability in safety verifica- tion. Moreover, works in robust optimization applied to machine learning minimize the worst-case probability of error, but this worst case is over parameters of f rather than over individual values of [Lancriett et al. 2002). Thomas et al. (2019) present a framework where during the model training, a set of safety tests specified in order accept or reject the possible solution. The specification of these tests is left to the model designer but the goal of the proposed solution is to provide a reusable paradigm to support safety in ML solutions.
We build on related literature from model robustness and explainability areas that deals specifically with tree ensembles. [Kantchelian et al.) (2016) seek find the smallest perturbation of an input instance to 'evade" a classifier using mixed-integed programming (MIP). Optimization formulations are also explored by [Parmentier & Vidal (202T) for the purposes of counterfactual explanations. MIP approaches are computationally intensive however. To address this Chen et al. (2019) introduce graph based approaches for verification on trees. Their central idea, which we use, is to discretize verification computations onto graph constructed from the way leaves intersect. The verification problem is transformed to finding all maximum cliques. Devos et al. (2021) expand on this idea by providing anytime bounds by probing unexplored nodes.
Safety has become a critical issue in reinforcement learning (RL) with multiple works focusing on making RL policies safe (Amodei al. 2016 Zhu al. 2019 Inala et al. 2020 Rupprecht al.)
3

---

Under review as a conference paper at ICLR 2022
2020). There are two broad themes (Garcia et al. 2013): (i) safe and verifiable policy is learned at the outset by enforcing certain constraints, and (ii) post hoc methods are used to identify bad regimes or failure points of an existing policy. Our current proposal is complementary to these works as we focus on the supervised learning setup viewed from the lens of interpretability. Nonetheless, ramifications of our work in the RL context are briefly discussed in Appendix
4 DEVIATION MAXIMIZATION FOR SPECIFIC MODEL CLASSES
In this section, we discuss approaches to computing the maximum deviation ①T for f belonging various model classes. The benefit of interpretable model structure is seen in different guises. For decision trees, generalized linear and additive models in Sections 4.1 a.2 exact and efficient computation is possible. For tree ensembles in Section 4.3 their composition terms of trees allows discrete optimization methods to provide anytime bounds. For general class of piecewise Lipschitz functions Section 4.4 the application of multi-am arm bandit results yields tighter regret bounds on the maximum deviation. The results in Sections 4. 4.4 also show that intuitive measures of model complexity, such as the number of leaves or pieces or smoothness of functions, have more precise interpretations as well in terms of the complexity of maximizing deviation. On the other hand, for post hoc explanations Appendix [B3]] we believe that more development will be needed for them to help in evaluating maximum deviation.
To develop mathematical results and efficient algorithms, we will sometimes assume that the refer- ence model fo is from the same class as f. We will also sometimes assume that the certification set C and other sets Cartesian products. This means that C I = Cj. where for continuous feature j, Cj- XXy X5] is an interval, and for a categorical feature j. Cj is a set of categories.
4.1 TREES
We begin with the case where f and fo both decision trees. A decision with L leaves partitions the input space X' into L corresponding parts, which we also refer to as "leaves". We consider only non-oblique trees. In this case, each leaf is described by conjunction of conditions on individual features and is therefore a Cartesian product as defined above. With & C X denoting the /th leaf and y E Y' the output value assigned to it, tree f is described by the function
f(x) = yn if Lt, == 1=
(3)
and similarly for tree So with leaves Zom and outputs yom. m = 1,..., Lo- Rule lists can be seen as one-sided trees (Yang al. 2017 Angelino et al.) 2018) and subsumed in this discussion.
The partitioning of X' by decision trees and their piecewise-conse of the maximum deviation (I] Specifically, the maximization can be restricted to pairs of leaves (1, m) for which the intersection Lom nC is non-empty. The intersection of two leaves L Com another Cartesian product, and we assume that it is tractable to determine whether C intersects given Cartesian product (see examples in Appendix B.I.
nature simplify the computation
For visual representation and later use in Section 4..3 is useful to define bipartite graph, with nodes representing the leaves Li of f on one side and To nodes representing the leaves Lum of fo on the other. Define the edge set E = [(1, m) : L1 n fam nC + 0): clearly |8 < Lg Then max ((f(z) = max D(y yum). (L,))ES
(4)
.EC
We summarize the complexity of deviation maximization for decision trees as follows.
Proposition 1. Let f and fo be decision trees as in (3) with L and Lo leaves respectively, and E be the bipartite edge set of leaf intersections defined above. Then the maximum deviation ( can be computed with [E] evaluations shown in
4.2 LINEAR AND ADDITIVE MODELS
In this subsection, we assume that f is generalized additive model (GAM) given by
f(x)= g- Σ f((25))
(5)
4

---

Under review as a conference paper at ICLR 2022
where each fy is arbitrary function of feature 2--- In the where fイ(z)) w,y, for all continuous features Tj, where W is a real coefficient, (5) is a generalized linear model (GLM). We discuss the treatment of categorical features in Appendix B.2 The invertible link function g R + is furthermore assumed to be monotonically increasing. This assumption is satisfied by common GAM link functions: identity, logit (g(y) log(y/(1 y))), and logarithmic.
Equation S implies that y C IR and the deviation D(y: yo) is function of two scalars and yo. For this scalar case, we make the following intuitively reasonable assumption throughout the subsection.
Assumption 1. For y. yo y S R. 1) Dyy yo) 0 whenever y yui 2) D(y. yo) is monotonically non-decreasing in for y 2 yo and non intreascraainggg in y forrr S yo-
Our approach is to exploit the additive form of (5) by reducing problem ① to the optimization
mAX #E8
Σ Kz
(6)
1=1
for different choices of S X' and where minimization is obtained by negating all f,. We discuss below how this can be done for two types of reference model fo: decision tree (which includes the constant case To 1) and additive. For the first case, we prove the following result in Appendix B.2
Proposition 2. Let I be GAM in 5 and S be subset of X where fo(æ: = yo is constant. Then if Assumption holds.
}
max (o(()), max { 0999 #ES
(
max FES
E((s)) j=1
:3/0
g
min #ES
Σ (12))) j=1
:80
Tree-structured fo- Since fo is piecewise constant its leaves Lom- 1.... Lop to be the intersection of C with each Com in turn and apply Proposition 2 then obtained as the maximum over the leaves,
take S The overall maximum is
max D(f()), ZEC
max pe..y To
}
max
9-1
D
9-1
max
Σ E5(()) f=1
D g-1
min co.. Nc
Σ fx(z)) f=1
, 30m
Com DC
This reduces T to solving 2Lg instances of (
Additive fo- For this case, we make the additional assumption that the link function in 5 is the identity function, as well as Assumption Derpptioonbboooww Ibelow. The implication of these assumptions discussed in Appendix B.2
Assumption 2. D(y, vo) D(y yo) is function only of the difference yo-
Then fo(z)= = Σラ= for (x²) and the difference fxx)
- fo (x) also additive. Using Assumptions 2 aaddd a similar argument in the proof of Proposition [ the maximum deviation again obtained by maximizing and minimizing an additive function, resulting in two instances of (6) with S = C:
{ D
d - fos(2z) .
max f(f(2),f(()) = max { DEC
min Σ for ((o(()))) DEC
max DEC
3=1
Computational complexity of (6. For the case of nonlinear additive f. we additionally assume that C is Cartesian product. It follows that S = = S, is Cartesian product (see Appendix B.2 for the brief justification) and (6) separates into one-dimensional optimizations over S,,
max RES
Σ f(,)
Σ
max fz(2)). j=1 2. cS
5

---

Under review as a conference paper at ICLR 2022
The computational complexity of (8) is thus Σÿ= Cj where Cý is the complexity of the jth one- dimensional optimization. We discuss different cases of Cj in Appendix [.2] the important point is that the overall complexity is linear in d.
In the GLM case where Σj= (zy) = w" x, problem 6 is simpler and it is less important that be a Cartesian product. In particular, if a convex set, so too is (again see Appendix B.2 for justification). Hence (6) is convex optimization problem.
4.3 TREE ENSEMBLES
We now extend the idea used for single decision trees in Section 4.1 to tree ensembles. This class covers several popular methods such as Random Forests and Gradient Boosted Trees. It can also cover rule ensembles (Friedman & Popescu 2008; Dembczyński et al. 2010) as a special case, as explained in Appendix We assume f is tree ensemble consisting of K trees and fo a single decision tree. Let Lt, denote the lth leaf of the kth tree in for 1 I..... Ln. and Com be the mth leaf So. for m = 1,..., Lo. Correspondingly let 31,, and 3/0m denote the prediction values associated with each leaf.
Define graph &(,,)), where there is a vertex for each leaf in f and fo, i.e.
,..,,,, K, I 1= 1,..., L U {m/m = 1, Lo}. V [4/ = 1,...,
(9)
Construct an edge for each overlapping pair of leaves in V, i.e
E ((((-))),nn 0. v(i,)) E V, V.
(10)
This graph is a K + 1-partite graph leaves within an individual tree do not intersect and an independent set. Denote M to be the adjacency matrix of G. Following Chen et al. (2019).
maximum clique of size K on such a graph provides a discrete region in the feature space with a computable deviation. A clique is subset of nodes all connected to each other; a maximum clique is one that cannot be expanded further by adding node. The model predictions ye and you can be ensembled from leaves in S. Denote D(S) to be the deviation computed from the clique S. Maximizing over all such cliques solves ① However, complete enumeration is expensive, so informative bounds, either using the merge procedure in Chen et al. (2019) or the heuristic function in Devos et al. (202I) can be used. We use the latter which exploits the K 1-partite structure G.
Specifically, we adapt the anytime bounds of Devos et al. (2021) follows. At each step of the enumeration procedure, an intermediate clique S contains selected leaves from trees in [I....,A, k]
and unexplored trees in [k 1..... K 1]. For each unexplored tree, we select valid candidate leaf that maximizes deviation, i.c.
Uk arg max
D(SU
(11)
4, 1ane40 ViES
Using these worst-case leaves, heuristic function
K+1 U m=k+1
H(S) D(S) D(S
vm)
(12)
provides an upper (dual) bound. In practice, this dual bound is tight and therefore very useful during the search procedure to prune the search space. Each K clique provides primal bound, so the search can be terminated early before examining all trees if the dual bound is less than the primal bound. We adapt the search procedure from Mirghorbani & Krokhmal
(2013) include the pruning arguments. Appendix B.3 presents the full algorithm. Starting with an empty clique, the procedure adds a single node from each tree to create an intermediate clique. If the size of the clique is K + 1 the primal bound is updated. Otherwise, the dual bound is computed. A node compatibility vector is used to keep track of all feasible additions. When the search is terminated at any step, the maximum deviation is bounded by (Du, D.t).
The algorithm works for the entire feature space. When the certification set is a union of balls needed. First, can disregard leaves that do not
as in Eq. (2). some additional considerations intersect with during the graph construction phase. A validation step to ensure that the leaves of a clique all intersect with the same ball in C is also needed.

---

Under review as a conference paper at ICLR 2022
4.4 PIECEWISE LIPSCHITZ FUNCTIONS
We saw the benefits of having specific (deterministic) interpretable functions as well as their exten- sions in the context of safety. Now consider richer class of functions that may also be randomized with finite variance. In this case let / and fo denote the mean values of the learned and refer- ence functions respectively. We consider the case where each function either interpretable or black box, where the latter implies that query access is the only realistic way of probing the model. This leads to three cases where either both functions are black box or interpretable, or one black box. What we care about in all these case is to find the maximum (and minimum) of a function fo(z). Let us consider finding only the maximum of Á as the other case is sym-
A(x) - f(x) - metric. Given that f and fo can be random functions A is also a random function and if A is black box a standard way to optimize it is either using Bayesian Optimization (BO) (Auer 2002) or tree search type bandit methods (Bubeck al., [001 Carpentier & Valko 2015). We repurpose some of the results from this latter literature in our context showcasing the benefit of interpretability from a safety standpoint. To do this we first define relevant terms.
Definition 1 (Simple Regret (Bubeck et al. f on the certification set C, then the simple regret r. after querying the f function times and obtaining a solution Fy is given by, v. (J) = f( f(zg)
2011). fe denotes the optimal value of the function
Definition 2 (Order 3 c-Lipschitz). Given (normalized) metric aa function f is c-Lipschitz con- tinuous of order 3 > O for any two inputs x, and for e >> O we have, (f(x)) f(y) S c- c-((2, v)². Definition 3 (Near optimality dimension (Bubeck al. 2011)). If (C, C,C,, e) is the maximum num- ber of e radius balls one can fit in C given the metric E and C. = {x E C)f(() 2 Se
c), then for (c..(C.....))
c <> O the c-near optimality dimension is given by, u = max [imsupe-so In(e-1)
Intuitively, simple regret measures the deviation between our current best and the optimal solution. The Lipschitz condition bounds the rate of change of the function. Near optimality dimension measures the set size for which the function has close optimal values. The lower the value of v, the easier is to find the optimum. We now define what it means to have an interpretable function. Assumption 3 (Characterizing
Interpretable Function). If a function f is interpretable, then we can (easily) find 1 S m & partitions { (c,,),,..,Cii)) Cim)y of the certification set C such that the function f(o = (f())x= E ((0) Vi E {1....,m} in each partition is c-Lipschitz of order B.
Note that the (interpretable) function overall does not have to be c-Lipschitz of bounded order, rather only in the partitions. This assumption is motivated by observing different interpretable functions. For example, in the case of decision trees the m partitions could be its leaves, where typically the function is a constant in each leaf (c = 0). For rule lists as well fixed prediction is usually made by each rule. For a linear function one could consider the entire input space (i.e. m = 1), where for bounded slope the function would also satisfy our assumption (c a and 3 = 1). Examples of models that are not piecewise constant or globally Lipschitz are oblique decision trees (Murthy et al., 1994), regression trees with linear functions in the leaves, and functional trees. Moreover, m is likely to be small so that the overall model is interpretable (viz. shallow trees or small rules). With the above definitions and Assumption we now provide the simple regret for the function A.
1. Both black box models: If both f and fo are black box then it seems no gains could be made in estimating the maximum of A over standard results in bandit literature. Hence, using Hierarchical Optimistic Optimization (HOO) with assumptions such as C being compact and A being weakly Lipschitz (Bubeck et al. (011) with near optimality dimension the simple regret after q queries is:
( (m((g) q
(A) S
(13)
2. Both interpretable models: If both f and fo are interpretable, then for each function based on Assumption 3 we can find my and mo partitions of C respectively where the functions are ci and co Lipishhhii of order B1 and 3o respectively. Now we take non-empty intersections of these partitions where we could have a maximum of mi partitions, the function A in these partitions would be e max(cu, Li)-Lipschitz of order min(S,, 31) as stated next (proof in appendix).
For simplicity assume (),,-) he the identity function.
7

---

Under review as a conference paper at ICLR 2022
Proposition 3. functions hg and h1 co and 01 Lipschitz of order 30 and 31 respectively, then the function = hg - h1 is c-Lipschtiz of order B, where c = 2 max((c, 01) and B = min 91).
Given that A is smooth in these partitions with underestimated smoothness of order 3, the simple regret after queries in the ith partition C(i) with near optimality dimension vi based on HOO
is: (+) 9
SOO
where Us S If we divide the overall query budget q across the
mom non-empty partitions equally, then the bound will be scaled by π म, when expressed as function of q. Moreover, the regret for the entire can then be bounded by the maximum regret across these partitions leading to the following result:
((
4+28
((A SO
(14)
Notice that for a model to he interpretable mg and ma are likely to be small (i.e. shallow trees or small rule lists or linear model where m = 1) leading to "smallish" and can be much >> & in case 1. Hence, interpretability significantly reduces the regret in estimating the maximum deviation.
3. Black box and interpretable model: Making no further assumptions on the black box model and assuming A satisfies properties mentioned case 1, the simple regret has the same behavior as equation 13 This is expected as the black box model could be highly non-smooth.
5 EXPERIMENTS
We present case study on the UCI Adult Income dataset (Dua & Graff (017). using its given par- tition into training and test sets. Additional datasets are presented in Appendix D For the reference model fo. an 8-leaf decision tree (DT) is fit (using seikit-learn's 's max max_lea feaodf parameter) on the training data. This DT has 85.0% accuracy on the test set and is easy for human to understand and validate (see Figure 3 We take the deviation function D to be the absolute difference between predicted probabilities of the positive (high-income) class. For the certification set C, we consider a union of Loo balls 22) centered at test set instances (n = 16281). The &o norm is computed on normalized feature values, where continuous features standardized and categorical features one-hot encoded. The case r = 0 yields finite set consisting only of the test set, while r - oo corresponds to C being the entire domain X.
5.1 TREES, LINEAR AND ADDITIVE MODELS
We first consider models for which the maximum deviation can be computed exactly: decision trees, generalized linear and additive models. For the first classes, we use scikit-learn (Pedregosa et al. 201T) to train DTs of varying numbers of leaves (max_leaf_node) fnndes)) and logistic regression (LR) models with varying amounts of l regularization. For additive models, we use Explainable Boosting Machines (EBM) from the InterpretML package (Nori et al. 2019) with zero interaction terms. Smoothness is controlled by the max b ns parameter, the number of discretization bins for continuous features. Statistics and plots of the resulting models can be found in Appendix D.I
Decision
LR.
GAM, r- 0.2
max dbviatinD
max Dovaatoo
max Dedettinn
6:945
0.92
0.92
DT. leaves-50
max
6.975
0.90
GAM, max bins-8
norm7.44
02
6:033
42
80
127
30
Number of leaf nodes
f norm
max_bins
Figure 1: Maximum deviation D for the three models as function of certification set size (radius r, left panel) and model smoothness (number of leaves for DTT, E norm for LR, max bins for GAM).
To evaluate the maximum deviation for DTs,, Algorithm[ is used on a bipartite graph. For the latter two cases where f is generalized additive, fo DTT, and radius r 0, we use
G 0 is
8

---

Under review as a conference paper at ICLR 2022
handled simply by evaluating the models the test set). For oo when C is union of balls, maximize separately over each intersection between ball and leaf of fo. and take their maximum.
Figure I shows summary of the maximum deviation D function of certification set radius r and each model's smoothness parameter, Appendix [.1] has breakdowns by leaves of fo- The be large even between simple models, namely the 8-leaf
first observation is that the deviation reference DT fo+ a 50-leaf DT f. sparse LR model (16 nonzeros, & norm = 7.4), and a smooth GAM (see Figure for plots of fj). At the same time, the interpretability of these models allows the deviation to be computed for range of infinite certification sets with r > 0. We can thus quantify the increase in deviation as r' increases, seen in the left of Figure I For LR and GAM, r only has to be slightly larger than for the deviation to equal that for = oo (C = X, dashed lines in figure), whereas for DT, the deviation r deviation also increases as model smoothness decreases (number of leaves for DT,, & norm for LR, max_bins for GAM). The initial increase is rapid for DT' and LR. Appendix [D.]] reports on the complexity of computing D (running time, number of cliques evaluated).
already maximal. The right panels show that the
Studying the solutions that maximize deviation (the arg max) can bring attention to unanticipated extremes in model output, which may rise to the level of safety risks. Appendix D. discusses in detail some maximizing solutions corresponding to Figure common source of large deviations is the extrapolation of linear and monotonic functions (more generally, unbounded or poorly bounded functions) to extreme points of the certification set, or even parts thereof. At these extreme points, the model and reference fo are in conflict, which may be reason for caution or call for domain expert intervention. In the GAM case, the arg max also highlights the presence of an unintuitive extreme value in one of the functions fj. which may be an artifact warranting further investigation.
5.2 TREE ENSEMBLES
2.0
cual bound
odma bound
Next, we demonstrate the methods in Section Random Forest model, where the number of estimators varied. A time limit of two hours is imposed for the search procedure for each run. There are two sets of ex- periments, one where the set is assumed to be the entire domain, and another where C is union of balls.
2.0
0.6
0.7
In Figure 2a we observe that max deviations can be large even for simpler models with fewer estimators. The upper bound on max deviation reduces as the number of estima- tors increases. The larger number of estimators increases averaging and may serve to make the model smoother. The primal lower bound here is the maximum D for com- plete K + 1-max-cliques. Due to the size of underlying graphs, fewer K + 1-max-cliques are evaluated and the lower bound is weak. For safety evaluation, i.e. worst case behavior, the lower bound is of less consequence.
160
400
502
Number cotimaters Random Forest
(a) D w.r.t. number of estimators
0.96
matimaton
For the same setting, we now consider the case where C is union of balls of the test set and the radius is varied. Figure (2b shows the upper bound on safety as a function of the certification
0.95
3.25
3.50
0.75
1:30
1.25
1.50
1.75
2.03
hall addus
(b) D w.r.t size of certification set C
size for two RF models. As the test set is large in this case. the deviations observed even for small values of are high and grow to reach the value of the full feature space quickly.
Figure 2: Maximum deviation of f. Random Forest, trained on the Adult In- come dataset.
6 CONCLUSION
We have considered the relationship between interpretability and safety in supervised learning through two main contributions: First, the proposal of maximum deviation as a means toward as- sessing safety, and second, discussion of approaches these are simplified by interpretable model structure. We believe that there is much more to explore in this relationship. Appendix C provides further discussion of several topics.
computing maximum deviation and how

---

Under review as a conference paper at ICLR 2022
ETHICS DISCUSSION
The ICLR Code of Ethics requires contributions to avoid harm and contribute to society. The safety of machine learning systems is fundamental factor in achieving these goals, and has been called out by the European Commission's 's regulatory framework (High Level Expert Group on Artificial Intelligence 2020). The commission states seven key dimensions to be evaluated and audited by cross- discplaisciyyinary team: (i) human agency and oversight, (ii) technical robustness and safety, (iii) privacy and data governance, (iv) transparency, (v) diversity, non-discrimination and faimess,, (vi) environmental and societal well-being, and (vii) accountability. The second of these dimensions safety. However, Sloanne et al. (202T) argue that algorithmic audits are ill-defined as the underlying definitions vague. The proposed work helps fill that ill-definedness using quantitative approach. One may argue against this particular choice of quantification, but it does start the community down the path toward being more concrete in its definitions.
As with many other technologies, the proposed approach may be misused. For example, the refer- ence model may be chosen in way that hides the safety concerns of the model being evaluated. Transparent documentation and reporting with provenance guarantees can help avoid this kind of purposeful deceit (Arnold et al. 2019p.
REPRODUCIBILITY DISCUSSION
To promote reproducibility, all algorithms and mathematical derivations in the paper are presented with a large amount of detail in the main body and appendix. All datasets used in the experiments are publicly-available. All parameters and their settings are fully described.
REFERENCES
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Con- crete problems in AI safety. 160,0666 2016.
Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18(234): 1-78, 2018.
URL http: /mr.
/waess//vll.. v11/ 17-716. html
Matthew Arnold, Rachel KE Bellamy, Michael Hind, Stephanie Houde, Sameep Mehta, Aleksandra Mojsilović, Ravi Nair, Karthikeyan Natesan Ramamurthy, Alexandra Olteanu, David Piorkowski, Darrell Reimer, John Richards, Jason Tsay, and Kush R. Varshney. FactSheets: Increasing trust in Al services through supplier's declarations of conformity. IBM Journal of Research and De- velopment, (3(4/5)66, 2019.
Peter Auer. Using confidence bounds for exploitation-exxllrrtion trade-offs. Journal of Machine Learning Research, 3, 2002.
Peter L.. Bartlett and Marten H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 9559):123311400 2008. URL http::/tp//// /mmr .rrg/
papers/w9/bartletttte html
Osbert Bastani, Yewen Pu, and Armando Solar-Lezama. Verifiable reinforcement learning via policy extraction. In Advances in Neural Information Processing Systems, 2018.
Sebastien Bubeck, Remi Munos, Gilles Stoltz, and Csaba Szepesvari. X-armed bandits. Journal of Machine Learning Research, 12, 201
Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizil. Model compression. In Proceed- ings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006.
Alexandra Carpentier and Michal Valko. Simple regret for infinitely many armed bandits. In Inter- national Conference Machine Learning. PMLR, 2015.
10

---

Under review as a conference paper at ICLR 2022
Hongge Chen, Huan Zhang. Si Si, Yang Li, Duane Boning, and Cho-Jui Hsich. Robustmess verifica- tion of tree-based models. Advances in Neural Information Processing Systems, 12:12317-12328, 2019.
William W. Cohen and Yoram Singer. A simple, fast, and effective rule learner. In Proc. Conf. Artif. Intell. (AAAI), pp. 335-342, 1999.
Krzysztof Dembezyński, Wojciech Kotlowski, and Roman Stowinski. ENDER: a statistical frame- work for boosting decision rules. Data Mining and Knowledge Discovery, 21(1):22-90, Jul 2010.
Laurens Devos, Wannes Meert, and Jesse Davis. Versatile verification of tree ensembles. In Inter-
national Conference on Machine Learning, pp. 2654-2664. PMLR, 2021.
Amit Dhurandhar, Vijay Iyengar, Ronny Luss, and Karthikeyan Shanmugam. TIP: Typifying the interpretabilityy of procedures. arXiv:1706.0220 2017.
Amit Dhurandhar, Pin- Yu Chen, Ronny Luss, Chun-Chen Tu, Paishun Ting, Karthikeyan Shan- mugam, and Payel Das. Explanations based on the missing: Towards contrastive explanations with pertinent negatives. In Advances in Neural Information Processing Systems, pp. 2018.
Finale Doshi- and Been Kim. Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv: 10l::080000 2017.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:://acciii ics. uci. edcieedummm
Jerome H. Friedman and Bogdan E. Popescu. Predictive learning via rule ensembles. Annals of Applied Statistics, 2(3):916 954, Jul 2008.
Javier García, Fern, and Fernández. A comprehensive survey safe reinforcement learning. Journal of Machine Learning Research, 16(42):1437-1488, 2015. URL (ttttt::// //jtt:://mm....//// org/
papers/vil https////l//aaaaaa..... ht.m
Leilani H. Gilpin, David Bau, Ben Z. Yuan, Ayesha Bajwa, Michael Specter, and Lalana Kagal. Explaining explanations: An overview of interpretability of machine learning. In Proc. IEEE Int.
Conf. Data Sci. Adv. Anal., pp. 80-89, 2018.
High Level Expert Group worthy AI for self assessment. 2020. URL https://digitall strallyysstttttee.eeeaee europa. www.e/ueeeeeeeee /ttu/////bbrrr//// assessment- tsstttruttoortty-aattt iigee altai setai-selll f-assessment
Artificial Intelligence.
Assessment list for trust- Technical report, European Commission,
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv:1503.02531 2015.
Xiaowei Huang, Daniel Kroening, Wenjie Ruan, James Sharp, Youcheng Sun, Emese Thamo, Min Wu, and Xinping Yi. A survey of safety and trustworthiness of deep neural networks: Verifica- tion, testing, adversarial attack and defence, and interpretability. Computer Science Review, 37 (100270), 2020.
Jeevana Priya Inala, Oshert Bastani, Zenna Tavares, and Armando Solar-Lezama. Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Rep- resentations, 2020. URL http::ttss:/ppeeeeee
net htttt//ormmmiddddee S11
Alex Kantchelian, J Doug Tygar, and Anthony Joseph. Evasion and hardening of tree ensemble classifiers. In International Conference on Machine Learning, pp. 2387-2396. PMLR, 2016.
Roger Koenker. Quantile Regression. Cambridge University Press, 2005. ISBN 978-0-521-60827-55
Gert R. G. Lanckriet, Laurent El Ghaoui, Chiranjib Bhattacharyya, and Michael I. Jordan. A robust minimax approach to classification. J. Mach. Learn. Res., 3:555-582, December 2002.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pp. 4775-4774, 2017.

---

Under review as a conference paper at ICLR 2022
Ronny Luss, Pin-Yu Chen, Amit Dhurandhar, Prasanna Sattigeri, Karthik Shanmugam, and Chun- Chen Tu. Leveraging latent features for local explanations. In ACM KDD, 2021.
Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7(6): 983-999, 2006.
Mohammad Mirghorbani and P Krokhmal. On finding k-cliques in k-partite graphs. Optimization Letters, 155-116,,,,,,,, 2013.
Sina Mohseni, Zhiding Yu, Chaowei Xiao, Jay Yadawa, Haotao Wang. and Zhangyang Wang. Prac- tical machine learning safety: A survey and primer. urXiv:2106.0482) 2021.
Harsha Nori, Samuel Jenkins, Paul Koch, and Rich Caruana. Interpretml: A unified framework for machine learning interpretability, 2019.
Clemens Otte. Safe and interpretable machine learning: A methodological review. In Computational Intelligence in Intelligent Data Analysis, pp. 111-122. 2013.
Axel Parmentier and Thibaut Vidal. Optimal counterfactual explanations tree ensembles. In International Conference Machine Learning, pp. 1422-8431. PMLR, 2021.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and F. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28 2011.
Gábor Petneházi. QCNN: quantile convolutional neural network. CoRR, abs/1908.07977 2019.
http:://aaxx abs///0s./111.../..// 077978
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- 2018.
ples. arXiv preprint arXiv:/801.099
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should trust you?": Explaining the predictions of any classifier. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135-1144, 2016.
Ulrich Rückert and Stefan Kramer. statistical approach to rule learning. Proc. Int. Conf. Mach. Learn. (ICML), pp. 785-792, 2006.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and interpretable models instead. Nature Mach. Intell., 1(5):206-3 20152, May 2019.
Christian Rupprecht, Cyril Ibrahim, and Christopher J. Pal. Finding and visualizing weaknesses of deep reinforcement learning agents. In International Conference Learning Representations, 2020. URL
Mona Sloane, Emanuel Moss, and Rumman Chowdhury. A silicon valley love triangle: Hiring algorithms, pseudo-science, and the quest for auditability. arXix, 2021.
Philip S Thomas, Bruno Castro da Silva, Andrew G Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468):999. 1004, 2019.
Richard Tomsett, Dave Braines, Dan Harborne, Alun Preece, and Supriyo Chakraborty. Interpretable to whom? role-based model for analyzing interpretable machine learning systems. In Proc. ICML Workshop Human Interpret. Mach. Learn., pp. 8-14, 2018
Kush R. Varshney. Trustworthy machine learning and artificial intelligence. ACM XRDS Mag., 25 (3):26-29, Spring 2019.
Kush R. Varshney and Homa Alemzadeh. On the safety of machine learning: Syber-physical sys- tems, decision sciences, and data products. Big Data, 5(3):246-253 September 2017.
12

---

Under review as a conference paper at ICLR 2022
Dennis Wei, Sanjeeb Dash, Tian Gao, and Oktay Günlük. Generalized linear rule models. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 6687-6696, 09-15 Jun 2019. / mmlr wwwppprsssee...... v97 www//willl attei99a.hmlll
Adrian Weller. Transparency: Motivations and challenges. In Explainable AI: Interpreting, Explain- ing and Visualizing Deep Learning, pp. 23-40. 2019.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286552866222 5295. PMLR, 2018.
Hongyu Yang, Cynthia Rudin, and Margo Seltzer. Scalable Bayesian rule lists. In Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 3921-3930, 2017.
He Zhu, Zikang Xiong. Stephen Magill, and Suresh Jagannathan. An inductive synthesis framework for verifiable reinforcement learning. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 686-701, Phoenix, AZ, USA, 2019.
13

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL PROBLEM FORMULATION DETAILS
Models that abstain The formulation in Section can also accommodate models that abstain from predicting (and possibly defer to a human expert or other fallback system). If f(x) = representing abstention, then may set D yo) d for any yo 3. where d >> 0 intermediate value less than the maximum value that D can take (Bartlett & Wegkamp 2008). The value d might also be less than a "typically bad" value for D. to reward the model for abstaining when is uncertain.
B ADDITIONAL DETAILS ON DEVIATION MAXIMIZATION FOR SPECIFIC MODEL CLASSES
B.1 TREES
Rule lists A rule list is nested sequence of IF-THEN-ELSE statements, where the IF condition usually involves single feature and the THEN consequent is an output value. As discussed in Yang et al. 2017)); Angelino et al. (0188), such rule lists are one-sided trees and are thus subsumed in the discussion of Section 4. I| The number of leaves in the equivalent tree is equal the number of rules in the list (including the last default rule).
Intersection of C with Cartesian product IfC - -I; Cj is also a Cartesian product, then de- termining whether the intersection is non-empty amounts to checking whether all of the coordinate- wise intersections with Cy. j ..... d, are non-empty. If not Cartesian product but is union of foo balls (which are Cartesian products), then the intersection is non-empty if the intersection with any one ball is non-empty.
Additive reference model For the case where f is decision tree and fo is a generalized additive model, the deviation function symmetric, Dyy yo) D(yo, v), then this case covered in Section 4.2
B.2 LINEAR AND ADDITIVE MODELS
Categorical features A function fy(2;) of a categorical feature æj can be represented in two ways, depending whether / is GAM a GLM. In the GAM case, may the native representation in which v, takes values in a finite set X, of categories. the GLM case, 2y is one- hot encoded into multiple binury-valued features Tyk, one for each category k. Then any function fj can be represented as a linear function.
f1
Σ WykTykk
where wyy is the value of fy for category k.
The second condition implies that the deviation increases or stays the same as y moves away from yo in either direction.
Implication of Assumption [
Proof of Proposition Let x and S(x) Ei= [z(z)). Under Assumption 1 if S(x) g(yo), then
D(f(z). D(g (g(())), vo) D yo)
As 5xx) increases from s(vo), f(x) also increases because 1 is increasing function, and (xf()) yo) increases or stays the same due to Assumption 2 Similarly, as S(x) decreases from g(Vo), f(x) decreases, and D(f(2), yo) again increases stays the same. It follows that max- imize (ff(x), yo), ) suffices to separately maximize and minimize S(x), compute the resulting values of (f{x), yo), and take the larger of the two. This yields the result.
14

---

Under review as a conference paper at ICLR 2022
Implication of Assumption identity link function g These two assumptions imply that the deviation is measured on the difference between f and fu in the space in which they are additive. For example, if and fo are logistic regression models predicting the probability of belonging to one of the classes, the difference is taken in the log-odds (logit) domain. is left to future work to determine other assumptions under which problem (T) is tractable when f and are both additive.
Cartesian product C implies Cartesian product S In the cases of constant and additive fo- S = C. In the decision tree case, since each leaf is Cartesian product Com [T Rmj. the intersections S = Com n C are also Cartesian products IT Sj where S, = Rms CC₁.
One-dimensional optimization complexities Cj For discrete-valued 2j. C2 is proportional to the number of allowed values |Sy]. For continuous zz, it is common to use spline functions or tree ensembles as f, in constructing GAMs. In the former case, C₁ is proportional to the number of knots. In the latter, the tree ensemble can be converted then proportional to the number of pieces. Lastly in the case where {イ(r;) Wyrj is linear and S, = [x X,] is an interval, Cj O() because it suffices to evaluate the two endpoints.
piecewise constant function and C₁ is
is a convex set, then in the cases of constant and additive Jo. = is also convex. In the case of tree-structured fo. S = Lum C and each leaf Lam be represented as a convex set, with interval constraints on continuous features and set membership constraints on categorical features. The latter be represented as Σ₁ = 0 constraints the one-hot encoding (see "Categorical features" paragraph above) for non-allowed categories k. Hence S is also convex.
Convex S
As specific example, suppose that S is the product of independent constraints each categorical feature and an Ep norm constraint on the continuous features jointly. The maximization over each categorical feature has complexity C₁ = | as noted above, while the maximization of w x over continuous features lying in E, ball has closed-form solutions for the common cases p 1, co.
B.3
TREE ENSEMBLES
The full algorithm for clique search from Section 4.3 is presented in Algorithm 1 It uses Z as node compatibility vector to keep track of valid leaves and B set of trees/partites not yet covered by the maximum clique. The algorithm starts with and empty clique S and anytime bounds as O. It starts the search with the smallest tree to limit the search space. This is typically fo. Each leaf added to the intermediate clique S in turn (Line 6). A stronger primal bound traversal is ordered in a meaningful way. In particular, starting with nodes with the highest heuristic function value (S)) aids the algorithm focus on better areas of the search space.
be achieved if the
the size of the clique is K +1 the primal bound is updated. Otherwise, the dual bound is computed. If the node is promising, the algorithm recurses to the next level. When the search is terminated at any step, the maximum deviation is bounded by (Dio, Dwb).
rule ensemble is linear combination of conjunctive rules, where the antecedent is a conjunction of conditions on individual features, and the consequent takes a real value if the antecedent is true and zero otherwise. They are produced by algorithms such as SLIPPER (Cohen & Singer 1999), that of Rüccerrt & Kramer (2006), RuleFit (Priedman & Popescu 2008), ENDER (Dembezúnski al., 2010) and have also been referred to generalized linear rule models (Wei et al. 2019). A rule ensemble can be converted into a tree ensemble by converting each conjunctive rule into an IF-THEN-ELSE rule list, which is one-sided tree (see Appendix B.I.. Specifically, the conditions in the conjunction are taken in any order, each condition negated to become an IF condition, and the THEN consequents all output values of zero. The final ELSE consequent, which is reached if all the IF conditions false (and hence the original rule holds), returns the output value of the original rule. The number of leaves in the resulting tree equals the number of conditions in the conjunction plus one.
Rule ensembles Similar the tree ensembles considered in Section 4.3
15

---

Under review as a conference paper at ICLR 2022
Algorithm Max clique search for maximum deviation
Require: M adjacency matrix, H heuristic function
1: Z [ I E V. = 21,2,.... K + 13.5-
D. All nodes valid, all trees uncovered
2: Q ENUMERATE( Z, B)
3: Initialize:
Dis 0, Dus 0
Anytime bounds
4: function ENUMER ATE(2, B,
5: t= arg max, [ be B)
D. Uncovered tree with fewest valid nodes
6:
for in Ze do
7:
2[i =0
Mark node as incompatiable D Add to candidate clique
8:
S S
9:
if || - K then:
> Is it max clique? > Update primal bound Add to set of max cliques b Backtrack
10:
Di = max (Du, D(S)
Q = QUS
12:
S = 5 {i}
13:
else
14:
Z++1 Ze A M(1)
P Update valid nodes b. Update uncovered trees b Update dual bound > Pruming by bound
15:
B = B { (t) Dub max (Dub: (S))
16:
17:
Dub > Dis then:
18:
end ENUMERATE( (Z411, B,
Recurse to next level
19:
S= S {i} = BU
Backtrack
21:
22: end
23:
end for
24:
end function
B.4 PIECEWISE LIPSCHITZ FUNCTIONS
Proof of Proposition Consider inputs and y then,
[h(x) h(y)) [(ho hx)()) (ho - h1)(w)) = (ho ho(v) + hi (v) h1 (z))
< [ho(x) ho(y)) + [1) hr(r)) S co ((x, + ((x,
Se ce.E(1r ((x,8))
where, max(co, 61) and min(3o. 31).
Other choices for D(...): The results assumed D(...) to be the identity function, where A D(fo,)) f). This choice of function clearly satisfies assumptions and 2. Again consistent with these assumptions look some other choices for ((.,-). If (....) were affine function with positive scaling such as D(yo. y) a(Vo y) + where a > O, then our result in equation 14 would be unchanged as only the Lipschitz constant of A would change, but not its (underestimated) order. If the function were a polynomial or exponential however, no such guarantees can be made and we would be back to case 1.
B.5 POST HoC EXPLANATIONS FOR OTHER MODEL CLASSES
For model classes beyond the ones discussed in Section 4 it is less clear whether there ist reasonably tractable algorithms that guarantee exact computation of or bounds on the maxi- mum deviation. In this case, is natural to ask whether post hoc explanations for the model can help. One way in which this could occur is if the post hoc explanation approximates the model f by a simpler model f and if the deviation function D satisfies the triangle inequality fo())))) < D(f(z), + D(f()) Then the maximum deviation in would be bounded
max ((f()),f(2)) < max D(f(s,, + max D((e))) ZEC
(15)
#EC
16

---

Under review as a conference paper at ICLR 2022
While may choose to be interpretable that the rightmost maximization is tractable, the middle maximization asks for uniform bound the deviation between and f. i.e, the fidelity of f. We are not aware of a post hoc explanation method that provides such guarantee. Indeed, in general, the middle maximization might not be any easier than the left-hand one that we set out to bound.
A (practical) possibility may be to perform quantile regression (Koenker 2005) for a large enough quantile to learn f. as opposed to minimizing expected error as is typically done. This may be an interesting direction to explore in the future as quantile regression algorithms are available for varied model classes including linear models, tree ensembles (Meinshausen) (206) and even neural networks (Petncházi] 2019). More investigation is needed into whether quantile regression methods can provide approximate guarantees the middle term in (15).
C FURTHER DISCUSSION
Worst-case approach The formulation of [1] as the worst case over a certification set represents deliberate choice to depend as little as possible probability distribution
dataset sampled from one. As stated in Section 2 Certification Set paragraph, C can depend at most on (an expanded version of) the support set of distribution. The reason for this choice is because safety is out- of-distribution notion: harmful outputs often arise precisely because they were not anticipated in the data. The trade-off inherent in this choice is that the maximum deviation may be more conservative than needed. The high maximum deviation values in e.g. Figures [ and 2 may reflect this. Given definition [ as a starting point in this paper, future work could consider variations that depend more on a distribution and are thus less conservative, but may also offer a weaker safety guarantee.
Choice of reference model The proposed definition of maximum deviation (T) depends on the choice of reference model fo. Different choices will lead different deviation values and, perhaps more importantly, different combinations of features that maximize the deviation. We have discussed possible choices in Section P interpretable forms for fo can ease the computation of maximum deviation. Beyond these guidelines, is up to ML practitioners and domain experts to decide on appropriate reference models for their application (and there may be benefit considering more than one). We mention an additional concern with the reference model in the Ethics Discussion.
and the results in Section Section[iiniccal indicaaee that, as with the assessed model f,
For some real applications it may be difficult to come up with globally interpretable reference model. But specific to particular scenarios it may be possible. For instance, it might be difficult to provide general rules for how to drive car, but in specific scenarios such there being obstacle in front, one can suggest that you stop or turn, which is a simple rule. So our machinery could potentially be applied This might help in "spot checking" a deployed model and estimating its safety by computing these maximum deviations scrupulously selected (challenging) scenarios.
local level where the reference model is interpretable in that locality.
Impossible inputs in certification set Mathematically simple sets such as Cartesian products and Ep balls permit simpler algorithms for optimizing functions over them. Accordingly, these sets have been the focus of not only the present work but also the related literature on ML verification and adversarial robustness. However, they may not serve to exclude inputs that are physically or logically impossible from the certification set C, and thus, the resulting maximum deviation values may be too large and conservative. Here it is important to distinguish between impossible inputs and those that are merely implausible (i.e., with low probability). Techniques for capturing implausibility have been proposed for contrastive/counterieee 2021), whereas we expect the set of impossible inputs to be smaller and more constrained. As a simple example from the Adult Income dataset, if we agree that a wife/husband is defined to be of female/male gender (regardless of the gender of the spouse), then the cross combinations male-wife and female-hushand cannot occur. Future work can consider the representation and handling of such constraints.
explanations (Dhurandhar et al. 2018, Luss et al.)
White-box vs. grey-box models In this paper, we have assumed full "white-box" access to both and for namely complete knowledge of their structure and parameters. Interesting questions may
17

---

Under review as a conference paper at ICLR 2022
arise when this assumption is relaxed to different "grre-box" possibilities. For example, one could further investigate the third case in Section 4.4. where one of f. fo black-box and the other is white-box interpretable. There may exist assumptions that we have not identified that would improve the query complexity compared to generic black-box optimization.
Other interpretability-sfett relationships This paper has focused on one relationship between the interpretability of a model and the safety of its outputs. It has not addressed other ways in which pitepretabiiiyyexpllaabbiyy can affect the risk of model (in the plain English sense, not the expectation of loss function). For example, in regulated industries such as consumer finance, not providing explanations or providing inadequate ones can lead to legal, financial, and reputational risks. On the other hand, providing explanations is associated with its own risks (Weller 2019). These include the leakage of personal information or model information (intellectual property), an increase in appeals of decisions for the decision-making entity, and strategic manipulation of attributes (i.e. "gaming") by individuals to gain more favorable outcomes.
Applicability to RL settings In RI., if one views the actions labels and state representation as features, one can build tree, albeit likely a deep/wide one, to represent exactly the RI policy, where the probability distribution over the actions can be viewed as the class distribution in normal supervised setting. Rolling up the states, creating leaves with multiple states, and simply averaging the probabilities for each action would yield smaller trees that approximate the policy. Our work lays foundation where in principle we can also compare f and fo that are policies using such tree representations. This may be related to a popular global explainability method (Bastani al. 2018) that samples policies and builds trees to explain them.
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 ADULT INCOME DATASET
Reference model Figure 3 depicts the 8-leaf DT reference model used in the experiments on the Adult Income dataset. The root node separates individuals based on whether the marital status Married-ci-spouse. The remaining splits divide the population into those with high and low education, high and low capital gains, and high and low capital losses. In particular, having high capital gains or losses a good predictor of high income (> $50000).
C
nonzeros
norm
accuracy
AUC
3e-4
1
0.2
0.764
0.715
le-3
2.6
0.825
0.885
3e-3
7
4.7
0.840
0.895
le-2
16
7.4
0.848
0,900
3e-2
30
12.9
0.852
0.905
le-1
38
17.3
0.853
0.905
3c-1
62
25.3
0.853
0.905
le+0
83
40.7
0.852
0,905
3e+0
92
54.6
0.852
0.905
le+1
101
65.1
0.852
0.904
3et1
73.5
0.852
0.904
le42
107
77.6
0.852
0,904
3e+2
107
79.1
0.852
0.904
Table I: Number of nonzero coefficients, é norm of coefficients, test set accuracy, and area un- der the receiver operating characteristic (AUC) for logistic regression models on the Adult Income dataset function of inverse l penalty C.
LR and GAM models In Tables and we show the values of inverse é penalty C' and max bass that were used for LR and GAM respectively, as well as statistics of the resulting classi- fiers. Test set accuracy and area under the receiver operating characteristic (AUC) increase and reach a plateau. For LR, we take the & norm of the coefficients to be the main measure of smoothness it depends on both the number of nonzero coefficients well their magnitudes, which both
18

---

Under review as a conference paper at ICLR 2022
node a0
MaritalStatus= Marriee--x--souuse <= 0.5 samples = 100 0% value (0.759, 0.241]
CapitalGain 7073.5
Education 46
12.5 [0.553,
54.0%
[0.935,
[0.951, 0.049]
53.1%
45
1.0% [0. [0.035, 0.965]
GapitalGain 5095.5
32.3% [0.669, 0.331]
CapitalGain 5095.5
13.7% [0.281, 0.719]
7 EducationNum == 8.5
#8
#11
#12 2.1% [0.004, 0. 0.996]
50.6% [0.703, 0.297]
[0.02 [0.021. 0.979]
1.6%
11.6% [0.331. 0.6691
5.1% [0.899, 0.101]
Capitall.oss 1782.5
0.336]
+13
#14
24.5% [0.682, 0.318)
0%
[0.248, 0.752)
Figure 3: Decision tree reference model with 8 leaves for the Adult Income dataset.
max bins
accuracy
AUC
4
0,858
0.910
8
0,862
0.915
16
0.865
0.920
32
0.870
0.924
0.871
0.925
128
0,871
0.925
256
0.872
0,925
512
0.871
0.925
1024
0.871
0.925
Table 2: Test set accuracy and AUC for Explainable Boosting Machines on the Adult Income dataset function of max bins parameter.
affect the extreme values attained in (6) Based in part on Tables and 2 we select C = 0.01 and max_bins 8 representative models that remain simple and have accuracies and AUCs not far from the maximum attainable. Plots for these two models are shown in Figures and 5
Maximum deviation for decision trees with small numbers of leaves In Figure expand
upon the second panel Fy focusing on decision trees with fewer than 50 leaves (plotted with linear spacing). The maximum deviation is 0.114 for trees with and 10 leaves, and remains moderate up to 26 leaves.
Relationships with accuracy and robust accuracy In Figure we show maximum deviation as a function of test set accuracy for the DT. LR, and GAM models shown in the right three panels of Figure (the LR and GAM models are listed in Tables T and 2 Broadly, the plots show two
19

---

Under review as a conference paper at ICLR 2022
intercept
MaritalStatus= Married civ spouse
CapitolSain EducationNum
Occupation=
Exec-managerial HoursPerWeek
Age
CapitalLoss
MaritalStatus- Never-mameed
Occupation service
Occupation Prof-specialty
Relationship= Own child
Relationship= Wife
WarkClass Self
Gender= Female
Occupation Farming-fssi fishing-fishing Gender- Male
Figure 4: Coefficient values of the logistic regression model with C' = 0.01 (16 nonzeros) for the Adult Income dataset.
regimes: one where accuracy increases and maximum deviation increases moderately or not at all, and one where accuracy stalls while maximum deviation increases. The latter is less desirable as suggests increasing safety risks without gain in accuracy. The last branch of the DT curve actually decreases in accuracy, indicating overfitting, while maximum deviation is high.
We also consider the relationship of maximum deviation to robust accuracy. Following Wong & Kolter 2018), robust loss for pair (x, y) is defined as the worst-case loss over an too ball centered
max L(f(# + A), |
(16)
and robust accuracy is therefore minus the average robust 0-1 loss over a dataset. While Wong & Kolter 2018) focus bounding robust loss for feedforward neural networks with ReLU activations, we find that the results in Section (42 apply to computing robust loss (16) exactly for LR and GAM models. Specifically, for 0-1 loss and fxc balls, the separable optimization (8) applies, and the worst case is obtained by minimizing f when the label y is positive and maximizing / when y is negative.
The resulting robust accuracy values for DT, LR and GAM plotted in Figure in similar fashion as Figure 7 Here we set = 0.1 and r = 0.1 as well in computing maximum deviation. The DT plot shows maximum deviation increasing with model complexity while robust accuracy is stable up to point. In the subsequent regime, when there are a large number of leaves, model robustness reduces while deviation remains high. The LR plot begins similarly to the one in Figure 7 in that robust accuracy increases along with maximum deviation, but then it stalls and decreases for maximum deviation above 0.94. In the GAM plot, robust accuracy actually decreases with the max bi parameter, i.e., the curve goes from right to left.
Breakdown by leaves of fu In Figures 9 12, we plot the maximum log-odds achieved by model (max on RHS of (7). the minimum log- oogoddds achieved by f. and the reference model log-odds ((y0m) over each leaf of the decision tree reference model in Figure
Plots are on the log-odds scale show the deviations more clearly, including those that would be compressed by the nonlinear logistic function g (x) 11(11 + =)) Figures 9 and 11 show the dependence on the certification radius while Figures I0 and 12 show dependence on the smoothness parameters for LR and GAM. These figures provide a more granular picture corresponding to the summary in Figure I and support the trends seen there. Figures and II there are jumps at r
because this the smallest radius that permits the values of categorical features of test set points (the ball centers in 2 to change to any other value. (Recall that categorical features are one-hot encoded into binary- valued features.) In Figure [1] the GAM achieves the limiting deviations corresponding to = oo (C = X, dashed lines) no later than r = 1.2. In Figure 9 the LR model achieves the lower limit on log-odds as soon r > 1 but the upper limit is not achieved for most leaves.
20

---

Under review as a conference paper at ICLR 2022
Hounfarleee
Cence
Netwes
KXC
PEC
MantalStatuss
CapitalCain
100
Dendtr
Harisphie splcce
sbbent
HoursPerWeck
DIC DE
Get
Captalloss
Race
1233
2033
buddew Lagnder
Figure 5: Feature importances and selected univariate functions for the Explainable Boosting Machine with max bins = on the Adult Income dataset.
21

---

Under review as a conference paper at ICLR 2022
Decision Tree
1.0
max deviation
10
20
Number of leaf nodes
Figure 6: Maximum deviation for decision trees on the Adult Income dataset as a function of the number of leaves.
DT. 0.2
LR. = 0.2
GAM, / 0.2
0.96
0.94
Deviston
maa deviation
0.385
0.6
0.92
0.980
0.90
0.88
0.2
0.970
0.365
0.845
0.850
0.855
0.860
0.76
0.80
0.84
0.3575 86000 8625
8 0
accuracy
Figure 7: Maximum deviation D (at certification set radius Adult Income dataset.
0.2) vs. test set accuracy on the
1.0
GAM
max deviation fr= 0.31
0.775
max max deviatio D (r- 0.1
0,8
0.6
0.900
0.675
0.4
0.88
0.2
09625
0.88
0,80 0.81 0.82 0:83 0.84
0.770
0.790
0.72
0.74
0.76
0.78
0.89
robust accuracy (e-
robust accuraty (e 0.11
robust accuracy (E 0.1)
Figure 8: Maximum deviation /) vs. robust accuracy (E 0.1, r = 0.1) on the Adult Income dataset.
22

---

Under review as a conference paper at ICLR 2022
loaf 5
leaf 6
7.5
5.
2.5
min
log-ddss
min
0.0
max
-2.
referente nco
leaf 8
leaf 9
15
6-
20
13
leaf
ing-odds
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.00
0.25
0.50
0.75
3.00
1.25
1.50
1.75
2.00
2. ball radius
2. ball radiusi
Figure 9: Minimum and maximum predicted log-odds for logistic regression model with inverse penalty C 0.01, as a function of certification set size (radius r) and broken down by leaves of the decision tree reference model.
23

---

Under review as a conference paper at ICLR 2022
30
log.odds
20
10-
-10
min
-15-
reference
-10-
leaf
leat 9
30
25
-2.
log-odis
-10.0
-15.0
30-
log-oudds
20
leaf
leaf 14
-od-ddds
log-odds
-6-
30
30
Figure 10: Minimum and maximum predicted log-odds for logistic regression models with different 4 penalties C, broken down by leaves of the decision tree reference model. The certification set loo ball radius is 0.2.
24

---

Under review as a conference paper at ICLR 2022
log 1ogodds
min Frew
max
max F-0
reference
-10
leaf
leaf 9
log-odas
11-
-10
-15
10-
loc odds
log-oods
-5-
-10
1e
leof 14
5.0
log-odos
0.8
-5-
-75
-15
1.4
radius
radius
Figure 11: Minimum and maximum predicted log-odds for Explainable Boosting Machine with max_bins 8, as a function of certification set size (radius r) and broken down by leaves of the decision tree reference model.
25

---

Under review as a conference paper at ICLR 2022
leaf
leaf
5-
16.0
0-
5.0
-5-
max
reference
-10-
-2.
-15-
lest
16
5-
log-oddss
-10
lest
7.5
10.0
log-odds
2.5
5.0
0.0
225
0.0-
7.5
5.0
leaf
5.0
5.0-
log-0355
0.9
lop
-25
-5.3
-3.0
-75-
-10.0
10'
maxBins
maxBins
Figure 12: Minimum and maximum predicted log-odds for Explainable Boosting Machines with different max bins values, broken down by leaves of the decision tree reference model. The certi- fication set foo ball radius r 0.2.
26

---

Under review as a conference paper at ICLR 2022
2500
2000
600
time [sec]
1500
1000
200
500
0-
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1:75
2.00
0.0
0.2
0.4
0.6
0.8
1.0
1.2
14
ball
radius
Figure 13: Time to compute maximum deviation for logistic regression models (left) and Explain- able Boosting Machines (right) on the Adult Income dataset as a function of certification set size (radius r). The filled-in region shows the min-max variation with model complexity (6, norm for LR. max bins for EBM).
Running time Figure 13 13 shows the time required to compute the maximum deviation for LR and GAM the Adult Income dataset. These times were obtained using single 2.0 GHz core of server with 64 GB of memory (only a small fraction of which was used) running Ubuntu 16.04 (64-bit). The times increase with the to ball radius because of the increasing number of ball-leaf intersections that become non-empty and hence need to be evaluated. The time for = 0 is minimal because this case requires only model evaluation over the finite at r = are due again to the ability of categorical features to change values, leading to an increase in ball-leaf intersections. The filled-in regions show that there was little variation due to different & norms for LR or ma x bins for GAM. This was most likely because of a vectorized implementation, which operates on all LR coefficients or all GAM bins at once (i.e., without a for loop).
set, as mentioned. The jumps
Maximal cliques evaluated for DT, RF To investigate the effectiveness of pruning by bounds in Algorithm [ we investigate the number of times all the decision trees in the Random Forest have to be processed. This represents number of times the state could not be pruned and needed to be evaluated fully.
Figure 14 shows two aspects at play. (a) Pruning by bound is effective in restricting the search space more so for Random Forests than for decision trees, and (b) for larger graphs, more time is spent in computing bounds in Eq. (1T).
37500
1030
X--3 mas diquee avauutte
200
12500
X+ w...arduuu
630
00
10000
603
1500
60
2500
Numberofice node Decisian Troe
Numba catimutors
Randam Ponic
(a) Decision Tree
(b) Random Forest
Figure 14: Effectiveness of pruning by bound for tree-based models
Feature combinations that maximize deviation In Tables 3 and 4 we report feature values that maximize deviation over selected leaves of the DT reference model, for LR and GAM respectively. For Table 3 we have chosen the minimum log-odds over leaf (corresponding to Figure 9 leaf 6, blue curve), which is of the two leaves in ( that maximize the deviation overall (the other being leaf 8). For Table 4 the minimum log-odds over leaf 12 is chosen (corresponding to Figure 11 leaf 12, blue curve) because this maximizes the deviation overall for most values of
27

---

Under review as a conference paper at ICLR 2022
The tables show the 6 features that contribute most to the minimum log-odds. These contributions are determined using (8) (with max replaced by min); since the minimum log-odds occurs in one of
the fx ball-leaf intersections and this intersection is a Cartesian product, the decomposition in (8) applies. The contribution of feature j is then minayes, (zzz) To account for the multiple r values, take average of the contributions over r.
EducationNum
HoursPerWeck
Age
MaritalStatus
Occupation
Relationship
0.0
9.0
15.0
23.0
Never-married
Sales
Own-child
0.1
4.7
33.8
26.6
Never-married
Transport Transport-moving
Not-in-fand in-in-faaily
0.2
4.5
32.5
25.3
Never-
Transport-movin moving
Not-in bot-in-family
0.4
4.0
30.1
22.5
Never-married
Transport-moving
Not-in-familly
3.5
27.6
19.8
Never-married
Transport-movine
Not-in-famill
0.8
1.0
26.1
17.0
Never-married
Harming-fishing
Not-in-family
0,999
1.0
7.7
17.0
Never-married
Other-service
Own-child
1.001
1.0
L.0
17.0
Never-
Other-service
Own-child
1.0
1.0
17.0
Never-married
Other-service
Own-child
1.0
1.0
17.0
Never-married
Other-service
Own-child
1.6
1.0
1.0
17.0
Never-married
Other-service
Own-child
1.8
1.0
1.0
17.0
Never-married
Other-service
Own-child
2.0
1.0
1.0
17.0
Never-married
Other-service
Own-child
00
1.0
1.0
17.0
Never-married
Other-service
Own-child
Table 3: Feature values that minimize log-odds for a logistic regression model (C = 0.01) over leaf 6 of the decision tree reference model. The features that contribute most to the minimum are shown as function of certification set radius
As r increases, the predominant trend of the values of continuous features is toward extremes of the domain X,, depending on the sign of the corresponding LR coefficient wy or shape of the GAM function fy. For example, EducationNum (education on an ordinal scale). hours per week, and age decrease toward minimum values, while capital gain occupies the minimal interval permitted for leaf (see Figure 3p. (These examples make sense since the log-odds of high income being minimized.) This movement toward extremes is expected in the LR case because the functions wyZj are either increasing or decreasing, and it also true for GAM the function ff is mainly increasing or decreasing. The values sometimes change abruptly in the opposite direction, for example hours per week both Tables 3 and age in the latter. These abrupt changes are due to the minimum jumping from ball in (2) another increases, but the overall trend eventually prevails. For categorical features, the trend toward values that minimize fy(2,) e.g., Never-married marital status, Without-por work class. While the contribution of each of these features minimizing log- odds may be limited, together they do add up.
CapitalLoss
Age
HoursPerWeok
WorkClass
CapitalGain
Race
0.0
0
29.0
40.0
Private
7298
White
0.1
[040] 40]
[53.6 56.4]
[18.8 20.5]
[5095 5119]
White
0.2
[0 78]
[23.3 23.5]
9..5
State-gov
[5095 5119]
White
0.4
[0.88] 78]
[20.5 23.5]
11.9]
State-gov
[5095 51
White
0.6
[0 78]
[28.8 29.5]
[30.6 31.5]
Private
[5095 5119]
Asian-Pac-Ioa Pac-dslander
0.8
[1598 1759]
[20.1 23.5]
(30.131.55
State-gov
[5095 5119]
White
0.999
[1598 1759]
(21.4
[27.731.5]
Private
[5095 5119]
Amer-Indian-EE Eskimo
1.001
[1598 1759]
[17. 23.5]
[11.6 20.5]
Without-pay
[5095 5119]
1.2
[1598 1759]
[17. 23.5]
[9.2
Without pay
[5095 5119]
1.4
[1598 17591
[17. 23.5
[6.7 20.51
Without-par pay
[5095 5119]
Amer-Indian Indian-Eskima
00
[1598 17591
[17. 23.51
20.51
Without-pay
|5095 51191
Amer-Indian Aaddian-Eskimo
Table 4: Feature values that minimize log-odds for an Explainable Boosting Machine (max_bi b na over leaf 12 of the decision tree reference model. The 6 features that contribute most to the minimum are shown as a function of certification set radius r. For > O, the minimizing values of continuous features form an interval because the corresponding functions fy are piecewise constant.
A notable exception to the trend toward extremes is capital loss in Table For this feature, the values settle into the intermediate interval [1598, 1759). The plot of the CapitalLoss function in
28

---

Under review as a conference paper at ICLR 2022
Figure shows that this interval corresponds to curiously low value of the function. This low region may be an artifact since it seems anomalous compared to the rest of the CapitalLoss function, and since individuals who report capital losses their income tax returns to offset capital gains usually have high income (hence high log-odds).
Given the results in Tables 3 and 4 one question that arises is whether the feature combinations indeed possible, not the ones for r - oo, then at least for some finite value of r. For the top features shown in the two tables, while some combinations may appear improbable (for example, EducationNum = 1 and 1 hour per week), we submit that none appear impossible. However, if one considers features beyond the top 6, then some "impossible" combinations do occur (e.g.. a female husband), although the contributions of these features to the minimum log-odds are much less. We touch upon this issue again Appendix C
The next question one might consider is the implication of these maximal deviations. From Figure 3 is seen that leaf 6 classifies individuals with high capital gains as high income with high probability (0.965). Leaf 12 adds the attributes of married status and high education, and hence classifies as high income with even higher probability (0.996). At the same time, the feature values Tables and 4 which minimize log-odds for LR and GAM, also make sense according to basic domain knowledge. For example, few hours per week and young age are associated with lower income, Without-pay work class and Amer- Inder-Indinn--e Indian-Eskimo race in the United States. When these conflicting associations occur in combination and the combination does not appear impossible, the question may be which one prevails. Such question might be resolvable by domain expert. Alternatively, the disagreement between models f and fo on the extreme examples in Tables 3 4 may be reason be cautious about using either of the models these cases. This might lead way of combining the models or abstaining from prediction altogether. Lastly, the anomalously low region in the CapitalLoss function identified Table clear, concrete example where further investigation is warranted.
29

---

Under review as a conference paper at ICLR 2022
D.2 LENDING CLUB DATASET
This dataset consists of 2.26 million rows with 14 features on loans. The target variable is whether loan will be paid-off or defaulted on. Features describe the terms of the loan, e.g. duration, grade, purpose, etc. and borrower financial information such as credit history and income. For this case study, we consider loan approval scenario using only information available the time of application. In particular, we exclude the feature 'total pymnt' (total payment over time on the loan), which becomes known essentially the same time as the target variable. (When 'total ptottl_pymmt' is included as feature, the prediction task becomes easy and accuracies in the high 90% range are possible.)
node #0
sub grade <= 11.5
samples = 100. 0% value [0.201, 0.799]
sub_gra gub_ggadeeee
sub_grade
58 6% [0.126, 0.874]
41.4%
[0.307, 0.693]
28.2% [0.091, 0.919]
a5
#6 sub _ewareeeeeee.. 8.5
30. 4% [0.169, 0.831]
term= 60 months <= 0.5 31.2%
#4 added 5.926
10.1%
[0.273, 0.727]
[0.411 0.589]
#13 12.2% [0.139, 0.861]
#14
#7 added dti 5.922
#8
#9
#10
18.2% [0.168, 0.812]
20.3% [0.244, 0.756]
[0.329, 0.671]
10.9%
1.9% [0.305, 0.695]
8.2% [0.435, 0.565]
[0.203, 0.797]
[0.265, 0.735]
Figure 15: Decision tree reference model with 8 leaves for the Lending Club dataset.
Reference model Figure 15 depicts the 8-leaf DT reference model for the Lending Club dataset. Most of the splits partition the 'sub grade' feature, which is measure of the quality of the loan (0-34 range, lower better). Node 3 differentiates between 60-month terms and 36-month terms (the only alternative), while nodes 4 and 7 split on 'added_dti' (added debt-to-income ratio), which the ratio between months worth of the loan's payment installments and the borrower's annual income. While the structure of the DT agrees with domain knowledge (lower 'sub bab_grade' and lower "added dti' correlate with higher repayment probability), the test set accuracy of 79.8% is no better than that of the trivial predictor that always returns the majority class of "paid off". The DT's AUC of 0.689 however does indicate an improvement over the trivial predictor.
LR and GAM models and the statistics of the LR and GAM classifiers that were trained on the Lending Club data. Similar to the DT reference model, the difference compared to Tables I 2 for the Adult Income dataset is that the accuracies remain no better than that of the trivial predictor, while the AUC does not show much increase either. These statistics suggest that the prediction task is difficult with the features available. Figures [6 and [7 display plots for the LR model with C 0.01 and GAM with max bing 8, which are again chosen representative
30

---

Under review as a conference paper at ICLR 2022
C
nonzeros
norm
accuracy
AUC
le44
1
0.4
0.798
0.693
3e4
2
0.6
0.799
0.695
le-3
6
1.0
0.799
0.702
3e-3
8
1.3
0.799
0.702
le-2
12
1.6
0.800
0.702
3e-2
17
2.1
0.799
0.703
3.1
0.799
0.703
3e-1
24
3.7
0.799
0.703
le+0
26
4.1
0.799
0.703
3e+0
26
4.2
0.799
0.703
Table 5: Number nonzero coefficients, l norm of coefficients, test set accuracy, and AUC for logistic regression models the Lending Club dataset function of inverse & penalty C.
max. bins
accuracy
AUC
0.798
0.696
0.798
0.703
16
0.799
0.704
32
0.799
0.705
64
0.799
0.705
0.799
0.705
256
0.799
0.705
512
0.799
0.705
1024
0.799
0.705
Table Test set accuracy and AUC for Explainable Boosting Machines on the Lending Club dataset as function of max_bins parameter.
models. The GAM in particular shows sensible monotonic behavior as functions of 'sub-grade", 'int_rate" (interest rate), 'dti' (debt-to-income ratio), etc., despite the unimpressive accuracy.
intercept
sub_grade
terms 36 months
annual_
purpose=smail business
installment
int rate
added
purpose=debt_conseee consolidation
credit history funded amnt
revoi_ util
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
1.25
Figure 16: Coefficient values of the logistic regression model with Lending Club dataset.
0.01 (12 nonzeros) for the
31

---

Under review as a conference paper at ICLR 2022
X00,2 1104
-02
papar
3.5
1nt rate
term
3
TEC 124
51% -1-
22
21
203
added_oc
103g
9
Linu
Falz, sevellatoon
Noure impooraeant restuarenn
Preate
Pupps peccimes
estemalia sote
Figure 17: Feature importances and selected univariate functions fy for the Explainable Boosting Machine with max bins = on the Lending Club dataset.
32

---

Under review as a conference paper at ICLR 2022
nonzeros,
0.92
max deviation In probabiities
0.0
0.40
0.7
0.6
05
0.4
0.84
D
0.9
0.5
1.0
1.5
ball radius
Figure 18: Maximum deviation D for logistic regression models on the Lending Club dataset as function of certification set size (radius r)) and model smoothness (6 norm).
maxBins
r= 0.2
0.290
maa deviation In probabiliees
0.275
0.30
0.265
0.20
0.88
0.200
0.255
lim D
0.240
0.
0.5
1.0
1.5
10F
ball radius
Figure 19: Maximum deviation D for Explainable Boosting Machines the Lending Club dataset as function of certification set size (radius r) and model smoothness (max bins parameter).
Decision Tree
0.9
0.8
max deviation D
0.7
bound
0.6
0.5
Dedaion
0.4
0.3
0.2
0.1
10a
102
103
Number of leaf nodes
100
400
500
Number Random Forcst
(a) Decision Tree
(b) Random Forest
Figure 20: Maximum deviations computed for tree and tree ensembles the Lending Club dataset
Maximum deviation summary Figures 18
show maximum deviation as functions certifi- cation set radius r and model complexity parameters, in similar manner as Figures [ and 2 for the Adult Income dataset. The qualitative patterns are similar to before: increasing maximum deviation in all cases except with the number of RF estimators in Figure 20b where the upper bound is stable around 0.7. A major quantitative difference is that the maximum deviations for the GAM in Fig- ure 19 are much lower than for the other models, in particular LRR in Figure 18 This likely due
33

---

Under review as a conference paper at ICLR 2022
50-
1og -3--dds
20-
min Tee
20
10
max From reference
log
10-
-10
Icef
leaf 10
50-
15.
20
Ing-odds
10-
-10
30
15.
20
log 40d5
leaf 13
lcaf 14
20-
10g -200
10-
30-
0.00
0.25
1.00
1.25
1.30
1.75
2.00
0.20
9.75
1.00
1.30
2.00
ball radius
boll radiuus
Figure 21: Minimum and maximum predicted log-odds for a logistic regression model with inverse l penalty C' 0.01 on the Lending Club dataset, as a function of certification set size (radius r) and broken down by leaves of the decision tree reference model.
the fact that the GAM functions Sj in Figure 17 are bounded while still being monotonic, unlike the linear functions wyzy in the LR model.
Breakdown by leaves of fo Figures 21 show breakdown of the deviations for LR and GAM by leaves of the reference model, similar to Figures and again on the log-odds scale. One dif- ference is that in Figure 21 the deviations for finite r do not come close to their r - counterparts in most cases. Figure 23 however, the - oo values are all attained when r is slightly greater than 1.
34

---

Under review as a conference paper at ICLR 2022
leaf
20
15
min
log odes
1.0
reference
loaf
leaf 10
log -dd5
log codd
-1-
log-adds
log
leaf 13
leaf 14
20
15.
log.odds
10-
odds
10-
-5
norm
4 norm
Figure 22: Minimum and maximum predicted log-odds for logistic regression models with different l penalties C on the Lending Club dataset, broken down by leaves of the decision tree reference model. The certification set for ball radius is 0.2.
35

---

Under review as a conference paper at ICLR 2022
leaf
leaf
15
10g oooddd
2.0
(-w
log odpodds
1.5
max (-400
1.8
05-
leaf 9
leaf 10
2.0
2.0
log 0055
lop-oodds
1.0
1.0
0.5
2.5
log 0000
log-odds
1.5
1.5
1.0-
0.5
leaf 13
leaf 14
log -d86
2.8
log-odts
1.5
1.8-
0.5
0.5
0.0
0.50
Figure 23: Minimum and maximum predicted log-odds for an Explainable Boosting Machine with max_bins = 8 on the Lending Club dataset, as a function of certification set size (radius r) and broken down by leaves of the decision tree reference model.
36

---

Under review as a conference paper at ICLR 2022
leaf
leaf
3.5
2.0
3.0
2.5
min
log-ddd
3.0
2.0
reference
1.5
1.0-
leaf 9
leaf 10
2.0
0.5
0.0
lear
leaf
15
log odds
logrodds
1.8
0.5
0.0
leaf 13
leaf 14
3.0
3.9
log 09-0085
2.0
15
1.0
05
maxBins
maxBins
Figure 24: Minimum and maximum predicted log-odds for Explainable Boosting Machines with different max max_bins values on the Lending Club dataset, broken down by leaves of the decision tree reference model. The certification set lo ball radius
0.2.
37

---

Under review as a conference paper at ICLR 2022
Running time, maximal cliques evaluated Figure 25 shows the time required to compute the maximum deviation for LR and GAM on the Lending Club dataset. Figure 26 shows the number of K + 1-maximal cliques evaluated for DT and RF well the number of nodes in the graph. The
observations are the same as in Figures 13 and 14
5000
3000
4000
2500
[sec)
3000
2000
1500
2000
1000
0.00
0.25
0.50
0.75
1.00
1:25
1.50
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
L- ball radius
1. ball radius
Figure 25: Time to compute maximum deviation for logistic regression models (left) and Explain- able Boosting Machines (right) on the Lending Club dataset as a function of certification set size (radius r). The filled-in region shows the min-max variation with model complexity (61 norm for LR, max bins for EBM).
16000
(-3mmx Sigute evlustes
X+1 max siaae extlated
14000
10000
1000
300
2000
10
2000
Humberoff Deciion
(a) Decision Tree
(b) Random Forest
Figure 26: Effectiveness of pruning by bound for tree-based models on the Lending Club dataset
Feature combinations that maximize deviation Tables and g present the feature values that maximize deviation for LR and GAM respectively. For both tables, the minimum log-odds over leaf 5 of the DT reference model is selected (corresponding to Figures 21 and 23 leaf 5, blue curve) because this choice maximizes the deviation overall for most values of
The previous trend toward extreme feature values that minimize log-odds also holds here as r in- creases. For example, debt-to-income ratios increase to outlier values above 100%, annual income drops to the minimum of $100, the term changes to 60 months in Table 7 for 1. and the pur- pose changes to small business, the category with the lowest log-odds in Figure T7] The decrease in income and increases in debt-to-income ratios are qualitatively in accordance with each other. However, these quantities are related to each other by deterministic formulas (at least theory) that also involve the interest rate and installment amount. It is not clear whether the values in Tables 7 and & violate these relationships. This may be an instance that could benefit from constraints on possible feature combinations, briefly mentioned in Appendix C
38

---

Under review as a conference paper at ICLR 2022
r
annual
term
purpose
int.rate
rredit_histors
0.0
505
1700
months
credit card
7.4
2557
0.1
506
100
months
credit card
6.9
2283
0.2
507
100
36 months
credit.card
6.4
2009
0.4
884
100
36 months
nebt_consolidation
10.1
3897
0.6
886
100
36 months
debt consooooiiiiitno
9.1
3349
0.8
889
100
months
debt.com consolidation
8.2
2801
0,999
891
100
months
debt.com consolidation
7.2
2256
1.001
891
100
60 months
small_business small business
7.2
2251
1.2
893
100
60 months
small business
6.3
1706
1.4
895
100
60 months
small. business
5.3
1158
1.6
898
100
months
small business
5.3
1095
1.8
900
100
months
business
5.3
1095
2.0
902
100 60 months
small_business
5.3
1095
999
100
60 months
small_business
5.3
1095
Table Feature values that minimize log-odds for a logistic regression model (C' 0.01) over leaf' 5 of the decision tree reference model for the Lending Club dataset. The 6 features that contribute most to the minimum are shown as a function certification set radius
term
int_rate
dti
purpose
annual inn
ndded_dtt
0.0
60 months
9.9
46.4
debt consolidation
35000
25.5
0.1
60 months
[10.4 11.
[28.6
30.9]
debt_consolidation
[31800 38001]
[10. 11.2]
0.2
60 months
[12. 13.1]
[27.8 31.8]
debi_consolidation
[36600 38001]
[10. 11.7]
0.4
60 months
[13.6
[27.8 30.4]
small_ business
[ 100 38001]
15.3)
0.6
60 months
[15.6
[27.8 36.11
small business
[19801 38001]
[12.7 15.
0.8
60 months
[15.6 16.4]
[27.8 28.4]
small business
[ [14402 38001]
15.77
0.999
60 months
[18.2 18.4]
[27.8 38.8]
small business
[33069 38001]
[12.7 14.5]
1.001
60 months
[18.2 18.88
[27.8 35.3]
small businessss
[935 38001]
[12.7 18.5]
1.2
60 months
(18.2
[27.8 33.3]
small. business
76002 38001]
[8.17
1.4
60 months
[18.2
[27.8 35.6]
small business
100 38001]
[12.7 20.4]
1.6
60 months
[18.2
[27.8 29.9]
small business
100 38001]
[1..7
1.8
60 months
118.226.11
[27.8 28.5]
small bualneess
100 38001]
(12.724.4
2.0
60 months
27.11
[27.8 30.71
small small_business business
100 38001]
[12.7 26.6
00
60 months
[18.2.31.
27.88 999.
small business
38001]
12.7 3179.3]
Table 8: Feature values that minimize log-odds for an Explainable Boosting Machine (max bins 8) over leaf of the decision tree reference model for the Lending Club dataset. The features that contribute most to the minimum are shown as a function of certification set radius r. For r > 0. the minimizing values of continuous features form an interval because the corresponding functions fy are piecewise constant.
39


Reviews:
[{"review_id": "x161TIVMff9", "reviewer": "Reviewer_dzWL", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper raises an important question regarding the assessment of model safety, defined by the authors as the minimax rate over a certification set, usually a superset of the input space, with respect to a safe and interpretable alternative model. However, the reviewer has some major concerns regarding the novelty and the development of the proposed methods. \n\nMajor issues:\n1. The definition and motivation of \"safety\" could use more justification. Though the proposed minimax rate is a legit distance measure between a given model and a interpretable model, it is also a direct measure for the extrapolation behavior / generalizability / robustness, of the model, while this will trivialize the novelty of the \"safety\" aspect and question the necessity of defining a new term. The idea of using an interpretable function as a reference should also be better motivated and supported theoretically and empirically. It is unclear why we need a two-function approach, especially: \n- The examples (existing practices / real world cases) that exercise it, which seem not available in existing literature. \n- If the intended maximum deviation is large, why not directly compare to a constant function / measure the minimax.\n- If the intended maximum deviation is small, what is the purpose of forcing another model to behavior almost identically w.r.t. the safe one.\n\n2. The discussion regarding how to compute the maximum deviation can be rebalanced. The linear and the tree parts are relatively simple, whereas the more interesting piecewise Lipschitz scenario with regrets could be further extended. The derivation in its current shape leaves a couple of questions.\n- The linear models and the tree models both have tractable extrapolation patterns, therefore it appears weird why to use them as f.\n- The setup of a cartesian set as the certification set implies compactness, which seems to result all continuous functions to piecewise Lipschitz of any order \\beta (m \\to \\infty when \\beta \\to 0). The optimal minimax rate in (14) is then likely to be dominated by the constant term overall. On the other hand, it would be useful to have examples corresponding to the functions discussed here, especially pertaining to realistic model that is discontinuous and not piece-wise constant (e.g. functional trees).\n\n3. The empirical study is also insufficient since it only covers one dataset and one f in the main body. It therefore is hard to argue the practical value of the proposed method. \n\n", "summary_of_the_paper": "In the paper the authors proposed the maximum deviation approach to study the safety of a predictive model by measuring its distance to an interpretable, \"safe\" function on a certification set. The authors explicitly showed how to compute such measure between function classes of linear, generalized additive, tree based, and piecewise Lipschitz models. ", "summary_of_the_review": "While the authors proposed a maximum deviation approach to measure model safety, the overall research question remains ambiguous and both theoretical and empirical supports for the proposed method and its claims are insufficient. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mxWctve3z-7", "reviewer": "Reviewer_uSea", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "### Strength\n#### [Strength1]\nThe idea of inspecting the safety of black-box models through the approximated white-box model wills be novel and interesting.\nThis idea will be able to relax the difficulty of directly inspecting the safety of black-box models, where some ideal assumptions are required on the black-box models under consideration.\nBy putting the approximated white-box model in the middle of the inspection, the task turns into inspecting the gap between the two models, where we will need some assumptions only on the difference of the models but not the models themselves.\n\n#### [Strength2]\nThe authors tried to inspect the maximum deviation under a piece-wise Lipschitzness assumptions.\nIn particular, the authors adopted Assumption 3 trying to characterize interpretable white-box models as piece-wise Lipschitz functions.\nAlthough this may not always be true, nevertheless this assumption itself would be an interesting idea in the area of interpretable machine learning where interpretability is ambiguous.\n\n### Weakness\n#### [Weakness1]\nThe theoretical results on specific model classes in Section 4.1 and 4.2 on the deviation between decision trees and generalized additive models are straightforward and trivial.\nThe results on tree ensembles in Section 4.3 are less trivial, although the proposed method is a simple extension of the pioneering studies of Chen et al. (2019) and Devos et al. (2021).\n\nI think the most important results are on Section 4.4 where we do not require specific model classes except that the models are piece-wise Lipschitz.\nIn practical machine learning, it is not realistic to restrict the model class to be deployed: the models can be complex deep neural networks or ensemble of several different models.\nThe current result in Section 4.4 is just borrowed from Bubeck et al., (2011).\nI would expect to see further investigations over piece-wise Lipschitz models.\nFor example, with what assumptions (without specifying model classes), we can derive nontrivial better results than the general result of Bubeck et al., (2011).\n\n#### [Weakness2]\nThe experimental results on Adult Income dataset (binary classification) showing that the maximum deviation on the positive class probability close to one seems to be trivial.\nIf the two classification models are not identical, it is not surprising that the two models have conflicted predictions for some inputs.\n\nThis observation leads to a natural question, in what circumstances we can obtain non trivial maximum deviation (e.g., the maximum deviation less than 0.1)?\nFor example, suppose the reference model is the depth 5 decision tree, and the approximation is the depth 3 decision tree.\nDo we need the depth 5 reference model to be sufficiently close to the depth 3 approximated model to obtain the non trivial maximum deviation?\nOr, is there a possibility that the maximum deviation can be small for some depth 5 reference model distinct from the depth 3 approximated model?", "summary_of_the_paper": "In this paper, the authors proposed inspecting the deviation between the reference model (e.g., black-box model) and its approximation (e.g., white-box model).\nThe major motivation is on inspecting the safety of the reference black-box model through the approximated white-box model.\nThe safety, such as the possible maximum output within the prescribed input domain, of white-box model, such as decision tree and linear model, are easier to inspect.\nThus, if we can evaluate the maximum deviation between the black-box model and the white-box model, we can evaluate the safety of the black-box model as well.\nBased on this idea, the paper considers some possible approaches for inspecting the maximum deviation between the models.\nIn the experiments, the authors demonstrated that the maximum deviation are considerably large in practice.", "summary_of_the_review": "I like the idea of inspecting the safety of black-box models through approximate white-box models, and I think some ideas (Assumption 3 in particular) are interesting and novel.\n\nHowever, the main theoretical results are trivial or simple modifications of the existing results.\nMoreover, the experimental results showing only trivial deviations lead to a question whether it is possible to obtain non trivial maximum deviation in practice.\n\nOverall, I think the paper is interesting in its underlying idea.\nHowever, the technical novelty is marginal, and there remains a fundamental question when we can have non trivial maximum deviation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kCKDL0KAfo", "reviewer": "Reviewer_6qDo", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "**Strong points:**\n* Great topic.\n* Good collection of results (to be blunt: I'm not sure the results are all that surprising, but it is nonetheless good to have them written down somewhere).\n* Paper easy to read.\n\n**Weak points:**\n* I think the experimental evaluation is not that convincing.  I get that it's kind of challenging to evaluate the methodology presented here, b/c (i) there seem to not be any real baselines, and (ii) it's hard to come up with an objective evaluation criteria.  But I do think there are a couple of things the authors could do to get around these issues:\n    * Can you generate a synthetic data set (based on some specification of $\\mathcal C$) that you essentially use as a hold out set?  I.e., evaluate both the reference and candidate model on this hold out set, and compare the two accuracies.  Now how does this number compare with the deviation you compute?  This is probably the simplest possible baseline that might still serve as \"check\" on your method, i.e., that it is doing something sensible.\n    * You cite Wong and Kolter (2018) in your related work section.  That paper produces bounds on the robust error.  If you compare those numbers for two models, how do they compare to the deviations you get?  Perhaps you could utilize other related works in a similar way.\n* As an alternative to the above, it would probably be worthwhile (and a good contribution) to carry out some kind of case study, where you run your methodology on a real-world data set, and draw out some interesting insights/findings.  (I didn't really see this being done in the appendix, but maybe I missed it.)\n\n**Questions:** see my \"Weak points\" and \"Additional feedback\" sections.\n\n**Additional feedback:**\n* If you use the black box methodology (Sec 4.4) even when you have \"closed-form\" methodology (Sec 4.1) available, what happens?  How well/poorly does the black box methodology do?  Is it a bad idea to just always use the black box methodology, by default?\n* To handle neural networks, there is some interesting recent work that reparametrizes a neural network in a certain way, winding up with a linear model.  I guess this could conceivably put neural networks into the more tractable part of your framework?  That seems like it could be pretty useful ...", "summary_of_the_paper": "**Summary:**\n* The paper puts forth methodology for (efficiently?) computing the worst-case deviation between two fitted models (one is a \"candidate\" model, the other is a \"reference\" model), over some feasible region $\\mathcal C$ (that need not be convex).\n* The takeaway message is that these kind of computations are useful for evaluating the safety of the candidate model, b/c if it (i.e., its predictions) deviate(s) too far from the reference model, then that is a bad sign and someone should \"investigate something\".\n* Some calculations are worked out showing that for a variety of model classes, these computations can be done efficiently-ish.\n* Some experimental results are presented, mainly showing how the deviation varies as the tuning parameters used to fit the candidate model are varied ...", "summary_of_the_review": "**Recommendation:** reject.  I like the paper and topic a lot.  But it's a bit hard to objectively evaluate the paper as it is currently written.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "U9aZggqD-Cg", "reviewer": "Reviewer_6m9J", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strong points of the paper include the following:\n\n+ the main idea of the paper, i.e. using the maximum deviation to assess the safety of a model w.r.t. a baseline model, is well explained\n+ the authors show that for some simple models, e.g. trees and rule lists, their proposed measure can be computed exactly\n+ the authors propose a way to characterize interpretable functions via piecewise Lipschitz functions and give an interpretation in terms of tree models\n+ the contributions seem to be technically correct\n+ the approach is empirically validated and details to parameters and data sets are provided\n\nWeaknesses include:\n- When discussing related work, the authors mention that as opposed to previous work of Mohseni et al. (2021), their proposed approach can quantify safety through interpretability.  This is a quite bold statement, since the approach needs a reference model f_0 and judges safety of a new model f based on the difference compared to that model (f_0 needs to be provided). Then the question is, whether the baseline model is safe, which is difficult to answer by itself (especially if the baseline model is not very simple).\n- Also, to me the proposed maximum deviation measure seems a bit conservative for evaluating the safety risk of a model. A large deviation between the prediction of two models could also mean that the new model is an improved estimator---i.e. it can model parts of the data that the old model did not model (put into the same leaf, for the example of decision trees). \n- Last, it would be nice if the obtained score provides a guidance for domain experts to retrain a safer model in terms of the score.\n\nMinor remark: Using H(S) in Eq. 12 is a bit confusing since H usually corresponds to entropy.\n", "summary_of_the_paper": "The authors posit that the demand for explainable/interpretable models in machine learning is linked to safety. In other words, domain experts trust explainable or interpretable models more. Based on this premise, they suggest to assess the safety of a model by measuring its maximum deviation of a model to a reference model, which is supposed to be safe. This deviation is computed on a certification set of data points. Additionally, the authors show that their proposed maximum derivation can be computed exactly for some interpretable models, such as decision trees, rule lists and generalized linear and additive models. Further, they discuss implications for tree ensembles and empirically evaluate their approach.", "summary_of_the_review": "In summary, the technical contributions and the evaluation of the approach seem solid. However, I do not see how exactly the proposed dissimilarity (the maximum deviation) can help a domain expert to retrain a safer model based in its output, which seems like the goal of such a metric. Inspecting every subset of data points on which the new model and the baseline differ substantially might take a lot of time.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a metric for the safety and interpretability of supervised learning models based on the maximum deviation from interpretable white-box models. The safety and interpretability of black-box models is an important topic, and many reviewers agree that the approach proposed by the authors is interesting. However, the maximum deviation from popular models such as decision trees, generalized linear and additive models have been intensively studied in the context of robust statistics/learning. Without explicit discussion on the connections with these existing studies, the novelty of the proposed approach cannot be properly evaluated. We thus have to conclude that the paper cannot be accepted in its current form.
Decision: Reject