The Solvability of Interpretability Evaluation Metrics (2023)

Abstract: Feature attribution methods are popular for explaining neural network predictions, and they are often evaluated on metrics such as comprehensiveness and sufficiency. In this paper, we highlight an intriguing property of these metrics: their solvability. Concretely, we can define the problem of optimizing an explanation for a metric, which can be solved by beam search. This observation leads to the obvious yet unaddressed question: why do we use explainers (e.g., LIME) not based on solving the target metric, if the metric value represents explanation quality? We present a series of investigations showing strong performance of this beam search explainer and discuss its broader implication: a definition-evaluation duality of interpretability concepts. We implement the explainer and release the Python solvex package for models of text, image and tabular domains.

## introduction for neural network models deployed in high stakes domains, the explanations for predictions are often as important as the predictions themselves. for example, a skin cancer detection model may work by detecting surgery markers @xcite and an explanation that reveals this spurious correlation is highly valuable. however, evaluating the correctness (or faithfulness) of explanations is fundamentally ill-posed: because the explanations are used to help people understand the reasoning of the model, we cannot check it against the ground truth reasoning, as the latter is not available. as a result, correctness evaluations typically employ certain alternative metrics. for feature attribution explanations, they work under a shared principle: changing an important feature should have a large impact on the model prediction. thus, the quality of the explanation is defined by different formulations of the model prediction change, resulting in various metrics such as comprehensiveness and identify what feature importance means propose the explainer to reflect the meaning evaluate the explainer on the quality metric better metric value ⟺ better explainer start explicitly search for the explanation that optimizes the target quality metric optimal metric value by construction heuristic search-based sufficiency @xcite . to develop new explanation methods (fig. 1 , left), people generally identify a specific notion of feature importance (e.g., local sensitivity), propose the corresponding explainer (e.g., gradient saliency @xcite ), evaluate it on one or more metrics, and claim its superiority based on favorable results vs. baseline explainers. we call these explainers heuristic as they are motivated by pre-defined notions of feature importance. in this paper, we show that all these metrics are solvable, in that we can define an explanation as the one that optimizes a metric value and search for it. the obvious question is then: if we take a specific target metric to represent correctness, why don't we just search for the metric-optimal explanation (fig. 1 , right) but take the more convoluted route of developing heuristic explanations and then evaluating them (fig. 1 ## background and related work in this section, we give a concise but unified introduction to the popular feature attribution explainers and evaluation metrics studied in this paper. ## the solvability of evaluation metrics now we establish the central observation of this paper: the solvability of these evaluation metrics. observe that each evaluation metric, e.g., comprehensiveness κ, is defined on the input x and the explanation e, and its computation only uses the model prediction function f (or g derived from f for the two decision flip metrics). in addition, the form of feature attribution explanation constrains e to be a vector of the same length as x, or @xmath0. without loss of generality, we assume that the metrics are defined such that a higher value means a better explanation (e.g., redefining the sufficiency to be the negative of its original form). we formalize the concept of solvability as follows: definition 3.1. for a metric m and an input x, an explanation e * solves the metric m if m(x, e * ) ≥ m(x, e) for all @xmath1. we also call e * the msolving explanation. notably, there are already two explanationsolving-metric cases among the ones in sec. 2. theorem 1. the occlusion explainer solves the df mit and rank del metrics. the proof follows from the definition of the explainer and the two metrics. occlusion explainer defines token importance as the prediction change when each the token is individually removed, thus the most important token is the one that induces the largest change, which makes it most likely to flip the decision under df mit . in addition, because token importance is defined as the model prediction change, its rank correlation with the latter (i.e., rank del ) is maximal at 1.0. thm. 1 highlights an important question: if we take df mit or rank del as the metric (i.e., indicator) of explanation quality, why should we consider any other explanation, when the occlusion explanation provably achieves the optimum? a possible answer is that the metrics themselves are problematic. for example, one can argue that the df mit is too restrictive for overdetermined input: when redundant features (e.g., synonyms) are present, removing any individual one cannot change the prediction, such as for the sentiment classification input of "this movie is great, superb and beautiful." nonetheless, the perceived quality of a metric can be loosely inferred from its adoption by the community, and the comprehensiveness and sufficiency metrics @xcite are by far the most widely used. they overcome the issue of df mit by also considering inputs with more than one token removed. since a metric is scalar-valued, we combine comprehensiveness κ and sufficiency σ into comp-suff difference ∆, defined as (recall that a lower sufficiency value is better): again, we face the same question: if ∆ is solvable, why should any heuristic explainers be used instead of the ∆-solving e * ? in the next two sections, we seek to answer it by first proposing a beam search algorithm to (approximately) find e * and then explore its various properties. ## solving metrics with beam search we first define two properties that are satisfied by some metrics: value agnosticity and additivity. definition 4.1. for an input @xmath2, ..., x l ) with explanation @xmath3, ..., e l ), we define the ranked importance as r( in other word, the x l with r(x l ) = l is the most important, and that with r(x l ) = 1 is the least. a metric m is value-agnostic if for all e 1 and e 2 that induce the same ranked importance, we have a value-agnostic metric has at most l! unique values across all possible explanations for an input of length l. thus, in theory, an exhaustive search over the l! permutations of the list [1, 2, ..., l] is guaranteed to find the e * that solves the metric. definition 4.2. a metric m is additive if it can be written in the form of for some function h, where e (l) reveals the attribution values of l most important features according to e but keeps the rest inaccessible. theorem 2. comprehensiveness, sufficiency and their difference are value-agnostic and additive. the proof is straightforward, by observing that both x(l) and x (l) can be created from x and the ordering of e (l) . in fact, all metrics in sec. 2 are value-agnostic (but only some are additive). a metric satisfying these two properties admits an efficient beam search algorithm to approximately solve it. as e (l) can be considered as a partial explanation that only specifies the top-l important features, we start with e (0) , and try each feature as most important obtain e (1) . with beam size b, if there are more than b features, we keep the top-b according to the partial sum. this extension procedure continues until all features are added, and top extension is then e * . alg. 1 documents the procedure, where ext(e, v) extends e and returns a set of explanations, in which each new one has value v on one previously empty entry of e. finally, note that e * generated on line 8 has entry values in {1, ..., l}, but some features may contribute against the prediction (e.g., "this movie is truly innovative although slightly cursory."). thus, we post-process e * by shifting all values by k such that the new values (in {1k, l -k}) maximally satisfy the sign of marginal contribution of each word (i.e., the sign of the occlusion saliency). algorithm 1: beam search for finding e * . ## experiments we investigate various properties of the beam search explainer vs. existing heuristic explainers, using the publicly available textattack/roberta-base-sst-2 model on the sst dataset @xcite as a case study. the sentiment value for each sentence is a number between 0 (very negative) and 1 (very positive), which we binarize into two classes of [0, 0.4] and [0.6, 1]. sentences with sentiment values in middle are discarded. the average sentence length is 19, making the exhaustive search impossible. we use a beam size of 100 to search for ∆-solving explanation e * . all reported statistics are computed on the test set. fig. 3 presents two explanations, with additional ones in fig. 11 of app. c. while we need more quantitative analyses (carried out below) for definitive conclusions on its various properties, e * explanations at least looks reasonable and is likely to help people understand the model by highlighting the high importance of sentiment-laden words. a worthy tribute to a great humanitarian and her vibrant ' co-stars . ' so stupid , so ill-conceived , so badly drawn , it created whole new levels of ugly . ## discussion definition-evaluation duality our investigation demonstrates that some evaluation metrics can be used to find high-quality explanations, defined as the optimizers of the metrics. conversely, we could also use any explanation definition d as an evaluation metric m. a very simple one would be m(x, e) . = -||ed(x)||, where e is the explanation under evaluation, d(x) is the "reference explanation" and || • || is a suitably chosen distance metric. it is obvious that d(x) itself achieves the optimal evaluation metric value. therefore, in theory, there should not be a difference of using a concept as definition vs. evaluation, but in practice, we almost always see some used mainly as definitions and others as evaluations (fig. 2 ). a major reason of not considering to use evaluations as definitions could be the presumed intractability of the optimization, which is experimentally refuted in this paper, as the beam search demonstrates its efficacy and efficiency. conversely, why do we not see more definitions (e.g., gradients and lime) used as evaluations? such an attempt may sound trivial yet unjustifiable at the same time: trivial because it is equivalent to claiming that the corresponding explainer definition is the best, which is in turn a seemingly unjustifiable circular logic. more importantly, we motivate a new research direction opened up by the duality concept. traditionally, definitions and evaluations have been considered and developed separately, but duality suggests that any interpretability concept can be used as both. thus, we propose that we should focus on studying the intrinsic properties of these concepts, independent of their usage as one or another. for example, are some concepts inherently superior for model explanations than others? how can we measure the similarity between two concepts? what does the space of these concepts look like? none of them are currently answerable due to a complete lack of formalization, but research on it could lead to a much deeper understanding of local explanations. demonstrable utility given the duality, how should we evaluate explanations? fundamentally, local explanations are used for model understanding @xcite , and we advocate for evaluating demonstrable utility: the presence of an explanation compared to its absence, or the newly proposed explanation compared to existing ones, should lead to a measurable difference in some practically beneficial aspect. for example, people use explanations to identify spurious correlation during development, audit fairness before deployment, and assist human decision makers during deployment. however, recent findings cast doubt on the feasibility of model explanations to support any of these use cases @xcite @xcite . demonstrating such utilities would bypass discussions of solvability and directly assert their usefulness @xcite . the examples listed here are by no means comprehensive, and a systematic taxonomy is valuable. furthermore, it is likely that no single explainer is a one-size-fit-all solution. more refined knowledge of the strengths and weaknesses of each method in supporting different aspects of model understanding is highly desirable. ## conclusion we study the relationship between definitions and evaluations of local explanations. we identify the solvability property of evaluation metrics, such that for each evaluation metric, there is an explicit search procedure to find the explanation that achieves the optimal metric value. in other words, every evaluation admits a definition that solves it. compared to the current practice of defining a explainer and then evaluating it on a metric, solvability allows us to directly find the explanation that optimizes the target metric and guarantee a very favorable evaluation outcome. in this paper, we investigate the feasibility of this process. first, we propose to use beam search to find the explanation e * that optimizes for comprehensiveness and sufficiency @xcite . then, in a suite of evaluations, we find e * performing comparably or favorably to existing explainers such as lime. therefore, for practitioners, we recommend using the proposed explainer for computing local model explanations and provide the python solvex package for easy adoption (app. a). for researchers, we propose a definition-evaluation duality inspired by solvability, which opens up many new research directions.