Trust Regions for Explanations via Black-Box Probabilistic Certification

What differentiates one sampling method from another if all have similar convergence rate? I would expect for a method to leverage the quality function $f$ for a better solution.

As mentioned in Section 5, although the rate of convergence is exponential in $Q$ for all three strategies, we see that for unifI (eq. 4) and adaptI (eq. 5) the exponent heavily depends on the cdfs of the quality function $f$ around the prototypes that are sampled. Hence, if we have even one good prototype that gets sampled, both unifI and adaptI will leverage this and perform better than unif. adaptI goes a step further and samples (exponentially) more around the promising prototypes. Hence, our methods do leverage $f$ and the benefit of this is seen in the experiments (see Figure 2), where adaptI is faster than all the other methods since it is able to hone in on the low fidelity examples. Moreover, looking at Tables 5 and 7 in the appendix where we report the computed bounds based on Theorem 1, we observe that the bounds for adaptI converge faster than for unifI, which in turn converge faster than for unif (see especially $Q=100$). These observations are also mentioned in the experimental section.

The paper seems to overlook the role of the quality function (f) in its analysis... I recommend that the authors emphasize these aspects (characterizing CDFs for linear models and enhancing certification for Lipschitz models) more prominently in the main body of the paper.

As mentioned in our previous response, our bounds do not overlook the quality function $f$, and in fact heavily depend on the specific sampling strategy paying close attention to where it samples. We are glad that you liked our analysis of the special cases. We have pointed to this section in the introduction and related work. In terms of adding more material from the appendix to the main body, we would be grateful if you could suggest what could be removed as given the tight page limit of 9 pages and having now added also a figure in the introduction (see our last response below), we are finding it challenging to make space for it. In the main body as it stands, we chose to focus more on cdf estimation and cdf-free bounds from extreme value theory in Section 6.1, as these approaches apply more widely than the special cases.

Identifying a hypercube in a d-dimensional space may lack practical relevance, especially since features in real-world datasets aren't always uniformly scaled.

As mentioned in the discussion, our approach could also be used to find hyper-rectangles with some additional book-keeping. The relative lengths could correspond to the non-uniform scalings. Moreover, given the scalings one could rescale when applying our algorithm so that spreads are uniform and scale back when outputting the regions. Additionally, if the data lies on a lower dimensional manifold, one could apply our methods in the latent space (e.g. latent space of an autoencoder) and then decode to obtain free-form regions in the input space. This is also mentioned in Appendix G.

there's existing literature on robust counterfactual explanations amidst noisy implementations [1] and other related works... While their formulations might differ from yours, it's essential to acknowledge and cite these works

We have now cited such works in the related works section. Thank you for pointing us to them.

'unifI' and 'adaptI', could benefit from further clarity. Incorporating a visual representation or figure summarizing the methods might be beneficial.

We have now added Figure 1 to the paper which tries to convey the main ideas behind the strategies. More detailed description is provided in Section 4. We did this to bring the benefit of the supplementary videos that you appreciated into the main paper.

What is the intuition of method design? At the least, the author should provide one figure to illustrate why the method is designed in this way and how the method works.

We have now added Figure 1 to the paper which tries to convey the main ideas behind the strategies. More detailed description is provided in Section 4. Also note that we had uploaded videos showing the working of the three strategies in our original submission.

Could the authors provide a real-world application to demonstrate the significance of the research?

One real-world application is explanation reuse. As mentioned in (Dhurandhar et al., 2019) (and also in our experience), given today's cloud-driven world where a model could exist on one cloud platform and explainability is offered as a service by a different corporation, each query to the black box model has an associated cost and hence finding explanations for many examples in a dataset can be prohibitive, not just in terms of time and network traffic but also monetarily. Finding regions where an existing explanation is valid can produce significant savings in all these three aspects, since one now does not have to find explanations for every example which typically takes $1000$s of queries (e.g. $5000$ is the default for LIME).

Another example is in finance where banks want to find cohorts where a certain action (related to credit cards, loans, etc.) might have similar effect on all members of the cohort. Our approach will provide such cohorts where a certain explanation is valid for the cohort and hence recourse may be possible. More applications can be found in (Liao et al., 2022), where they surmise that stability of explanations, which will lead to such trust regions, is important for stakeholders performing tasks such as model improvement, domain learning, adapting control and capability assessment.

What are the pros and cons of the three sampling strategies? What kind of scenario are they suitable for and what insight do they give practitioners?

As mentioned in the Experiments section, the pro of unif is that it is the simplest and also sometimes the fastest strategy. unifI and adaptI are more complicated but are preferable when you have $1000$s or $10000$s of features respectively. Our advice would be to use unif for up to $100$s of features, unifI for $1000$s of features, and adaptI for $10000$s of features or greater.

The authors claimed the method is model agnostic and quite general. So can the method generalize to graph data?

Yes, the method can work for graph data if the graphs are embedded in some compact space. For example by vectorizing adjacency matrices or using embeddings from Graph Neural Networks (GNNs).

To what extent is the found $w$ stable? i.e., the bound of $P (f (x);w) >=\theta$.

As seen in the experiments (see Tables 2-4 in the appendix), the found $w$ is quite stable from $Q=1000$. Even $Q=100$ is sufficient for low dimensions. The bounds are also quite tight from $Q=1000$ (see Tables 5, 7 in the appendix).

What is the purpose of ZO and why is it used as a baseline?

As mentioned in the related work, ZO is a standard approach used for black-box adversarial attacks. We adapted this method to our setup since ours is a novel problem in XAI with no prevalent baselines, where we thought an adapted version of ZO would be the closest and fairest baseline.

Why does the convergence of $w$ to a similar value indicate the accuracy of the explanation?

First note that the convergence of $w$ relates to the accuracy of the estimated trust region width for a given threshold $\theta$ and has nothing to do with the quality or accuracy of an explanation. For the synthetic experiments, we know the true $w$ and hence we can validate the different methods with certainty. For the real datasets, the true $w$ are unknown. Thus the different methods converging to similar values gives some confidence that the methods are returning an accurate enough $w$, as the mechanics behind the methods are quite different (especially between ZO and the others) and hence their converging to a similar value just by chance is unlikely.

Despite that the authors mentioned in Section 8 Discussion that the $l_\infty$ ball can potentially be generalized to hyper-rectangles or $l_p$ balls, all these hyper-balls may not carry semantic meanings of the samples. Therefore even if we can certificate that the pseudo-samples within the hyper-balls have high fidelity, those pseudo-samples may not carry meaningful information...

Yes you are right that all examples in a region may not be realistic input examples in the domain lying on the data manifold. In such cases one could after the region is found consider only realistic examples in the region for their downstream task. In a sense we would provide a superset of examples for which the explanation is valid.

Another option as discussed in Appendix G is one could simply apply our methods to the latent space (e.g. as learned by an auto-encoder) rather than the input space. Thus, although the regions will be hypercubes in the latent space they will be more free-form in the input space which might be interesting. As such, our approaches should still apply.

The connection between the Algorithm 1 and Algorithm 2 proposed in Section 4 seems to be detached from the original optimization formulated in equation 1.

Algorithm 1 decides on a width $w$ and Algorithm 2 tries to certify that width (i.e. check if $f_{x_0}(x) \ge \theta \quad \forall x \in B_\infty(x_0, w)$). If certified, Algorithm 1 chooses a bigger width which again Algorithm 2 tries to certify. Thus, the two algorithms are tightly linked to the optimization formulated in eq. 1, where we are trying to find the maximum possible (certified) width.

It is encouraged that the authors include more discussion on different explanation functions, or give concrete examples in Section 2.

Example explanation functions would be linear like in LIME, logistic regression, small decision trees, rule lists, interpretable neural architectures such as CoFrNet. We have now mentioned some of these in Section 2.

Is it possible to extend the techniques to features?

A thing to note here is that when we find trust regions we are finding instances in the input space where an explanation, which are typically feature importances, is valid for all of them. In other words, the feature importances hold for all examples in that region. Hence, we are highlighting important features in that region.

However, if your goal is to find features that are similar one could potentially transpose the data matrix and find regions of similar features, where the explanations would now point to important instances.

It is encouraged that the authors add visualization of the regions, provide some intuitive explanations, with simple (semi-)synthetic data.

We have now added Figure 1 to the paper which tries to convey the main ideas behind the strategies. More detailed description is provided in Section 4. Also note that we had uploaded videos showing the working of the three strategies in our original submission.

The authors mention several advantages of the novel explainability certificate, including stability of the explanations and explanation reuse, but did not provide numerical results or analysis on these benefits over existing explainable AI tools.

Our approach compliments the current work in XAI where XAI toolkits (viz. AIX360, Captum, InterpretML, etc.) contain predominantly explanation methods and/or (quality) metrics. One can take these methods and metrics and apply our approach on top to obtain trust regions, which could be used for any of the applications outlined in the introduction. As such in the experiments we do provide a comparison between LIME and SHAP using our methodology that is of a different flavor than previous works. This type of analysis can be used to compare and contrast XAI methods on individual examples, on regions, as well as on entire datasets, and across different models. Also note that our methods perform quite well around $Q=1000$ where we obtain a region (i.e. a set of examples) in which an explanation is valid. This is (potentially) much fewer queries than say LIME-like methods which by default query a model $5000$ times per example it wants to find an explanation for.

There is insufficient motivation for this problem. For instance, why would one care for the explanations to remain the same in a region?

As mentioned in the third paragraph of the introduction, there are multiple motivations for this work. We elaborate on some of them here.

Explanation reuse: As mentioned in (Dhurandhar et al., 2019), given today's cloud-driven world where a model could exist on one cloud platform and explainability is offered as a service by a different corporation, each query to the black box model has an associated cost and hence finding explanations for many examples in a dataset can be prohibitive, not just in terms of time and network traffic but also monetarily. Finding regions where an explanation is valid can produce significant savings.

Insights for different stakeholders: In (Liao et al., 2022)'s award winning work it was surmised through (AI and domain expert) user studies that stability of explanations is particularly important in recourse for stakeholders performing tasks such as model improvement, domain learning, adapting control and capability assessment. This is because without stability actions may produce unintended outcomes. Of course, as you mention, depending on the degree of non-linearity of the black box model, the sizes of the regions in which these explanations are valid will change, but this is precisely where approaches like ours would be useful in informing the user of how broadly the provided explanation would be applicable.

Meta-metric: Given a quality metric (viz. fidelity, stability, etc.) that the user cares about, our approach could be used to ascertain which explanation method obeys the quality metric better, which would correspond to larger trust regions (on average) returned by our method.

The term black-box access is unclear since here they are not only accessing the model output but also its local explanation function.

Access to the model is only through querying, a.k.a. black-box access as it is called in the literature. The local explanation function is typically separate from the model (e.g. LIME, SHAP, etc.). In fact, it could even be just feature attributions provided through some unknown process (viz. domain knowledge from a subject matter expert). Our approach works irrespective of how the explanation is obtained, and thus accesses not only the (black-box) model but also the explanation function only through querying. This justifies in our opinion the use of the term black-box.

... to certify multiple points, the query would significantly increase. Could the authors comment further on this computational complexity?

We see from the experiments that $Q=1000$ typically gives accurate enough regions. Also note that once we obtain a region, we would not certify other points within that region since we already know that the computed explanation is valid for them. This would reduce the number of queries. More importantly, LIME-like methods (by default) query around $5000$ times to obtain an explanation for a single point and are heavily used despite this cost. In contrast, our approach could potentially find an explanation for a bunch of points (those lying in the region) with say $Q=1000$.

How do the results vary when trying to certify different points? Could you discuss more on the average over the entire dataset?

In Appendix F we report results with more points. The results will of course vary depending on the point and the behavior of the black-box model around it. The key point here is not that the region sizes will vary but that we have provided a mechanism to find these regions for a wide range of explanation methods, quality metrics (with their thresholds) and black-box models. The averages over a dataset will again depend on the non-linearity of the black-box model, the stability of the explanation method and the threshold set for the quality metric. For instance, for FICO using Boosted Trees, we find that for $\theta=0.75$ LIME produces larger regions than SHAP (on average) and hence is possibly more favorable at this threshold, but for a larger threshold such as $\theta=0.9$ SHAP is more favorable.

The experimental section needs some clarity on what should one expect to see.

As mentioned in the first line of Section 7, we are trying to show through the experiments that our methods recover accurate regions and do so more efficiently than say adapted ZO approaches. We are also trying to show that our bounds derived in Section 5 are computable (see Tables 5,6,7 in the appendix). As discussed in the last paragraph of the "Observations" section, we also show how our approach can be used to compare explanations methods.

I felt only the first of the three techniques is well motivated

In Section 4 last paragraph, we motivate the three strategies. As mentioned there and further referenced in Appendix D, we previously shared videos to provide more intuition about the methods. Now in the introduction we have added a figure to further clarify the working of these methods.

As such, unifI ($2^{\text{nd}}$ technique) resembles a dynamic grid search where we randomly pick different locations in the current region and search around them. The $3^{\text{rd}}$ technique adaptI does a dynamic adaptive search where we again randomly pick different locations in the current region and search around them, but additionally focus our search more and more around the locations that we find more promising points (a.k.a. low fidelity examples).

it would be nice to have a simple example to illustrate what a certification looks like.

As mentioned above we have now added Figure 1 to the paper which tries to convey the main ideas behind the strategies. More detailed description is provided in Section 4. Also note that we had uploaded videos showing the working of the three strategies in our original submission.

Certification in Figure 1 would be our algorithm outputting $w=0.5$ with the (certification) probability based on Theorem 1 being $1$ for all three strategies.

What is fidelity?

As you rightly mentioned, the exact definition of fidelity is not critical to the exposition but, to improve clarity, we now in Section 2 point to eq. 14 in the appendix, where we have defined fidelity consistent with previous works (Dhurandhar et al., 2022; 2023; Ramamurthy et al., 2020).

... but the pseudo-code seems to be executing a binary search, in which case it is needlessly obscured.

Algorithm 1 doubles or halves the width depending on if the current region was certified or not. It is similar to binary search but with subtle differences such as the doubling and also what upper bound width to set when a region is found to be invalid (i.e. the "else" statement). Algorithm 2 embodies the three strategies for certifying a fixed region and is very different than binary search.

For w1>w2>w3, it seems to be possible that hypercubes of halfwidth w1 and w3 could be valid trust regions while w2 isn't.

This is not possible. We are trying to find a connected (indeed, convex) region in the input space around a point where its explanation is valid for all examples within this region (with high probability). If w2 is found to be invalid our approach will return only w3 in this case.

A respectful request to reconsider: We see that you expressed relatively low confidence (2) in your initial assessment. We hope that we have addressed what seems to be your main comment about having an illustrative example to clarify and contrast the three algorithms. We have also answered your other questions (fidelity, binary search, w1>w2>w3). In light of our response and the nature of your comments, we hope that you will reconsider your rating of 3 (reject). Many thanks in advance.