Previous research in interpretable machine learning (IML) and explainable artificial intelligence (XAI) can be broadly categorized as either focusing on seeking interpretability in the agent's model (i.e., IML) or focusing on the context of the user in addition to the model (i.e., XAI). The former can be categorized as feature or instance attribution. Example- or sample-based methods such as those using or inspired by case-based reasoning (CBR) rely on various approaches to select instances that are not necessarily attributing instances responsible for an agent's decision. Furthermore, existing approaches have focused on interpretability and explainability but fall short when it comes to accountability. Inspired in case-based reasoning principles, this paper introduces a pseudo-metric we call Longitudinal distance and its use to attribute instances to a neural network agent's decision that can be potentially used to build accountable CBR agents.
The literature in interpretable machine learning (IML) and explainable artificial
intelligence (XAI) have proposed various categorization schemes and taxonomies
to describe their methods. One of those is through attribution – attribution
methods attempt to explain model behavior by associating a classified (or
predicted) test instance to elements of the model (e.g., [
There are two main categories of attribution methods. Instance attribution
methods select instances as integral elements to associate with a classification or
prediction (e.g., [
When using case-based reasoning (CBR), a third category is often mentioned:
example- or sample-based. CBR can offer instances as examples but it does
not make attributions. The most successful use of CBR for explainability or
interpretability is in the ANN-CBR twin by [
Both instance and feature attribution methods suffer strong criticisms. DeepLift
[
If we extend the analysis beyond interpretability and explainability and
consider accountability, then feature attribution methods pose more challenges. An
accountable decision-making process should demonstrate its processes align with
legal and policy standards [
Instance attribution methods are also target of criticisms. One criticism has
been directed to instances attributed when using influence functions [
This paper proposes a new instance attribution method. It is intuitive and
thus simple to explain to users. It is also simple to compute. It has limitations as
well. It shares with influence functions the overlap between sets of instances
attributed to multiple test instance. It shares with ROAR [
Longitudinal distances are a class of distances based on a heuristic that an iterative learning model such as NN can be used as an oracle for instance attribution. Longitudinal distances operate in the metric space of instance elements that are used to train and to be solved by NN methods through a series of iterations (or epochs).
Given a classification model trained with neural networks (NN) on a space where x ∈ X are instances mapped by features f ∈ F , Xtrain ∈ X are training instances and hence include labels y ∈ Y to indicate the class they belong, and Xtest are testing instances. The classifier Ce(xi) is a NN classifier that learns to assign labels y using a set of n training instances xi through e epochs, e = 1, . . . , k, xi = 1, . . . , n. We assume that the ability of a classifier to solve a previously unseen instance is represented in the weights learned through a sequence of learning iterations from a set of training instances. We therefore hypothesize that there is at least one (or more) training instance(s) responsible for the classification of an unseen instance, be it correct or incorrect, and that the relation between the training and unseen instances are somehow represented throughout the sequence of learning iterations.
We justify the proposed hypothesis based on the fact that when a previously
known solution, i.e., a known class, is selected to classify an unseen problem,
that both the training instance and the unseen instance, now both labeled as
members of the same class, meet some condition that causes their solutions
to be interchangeable, that is, their labels are the same. This condition is an
abstract concept that we wish to represent, let us call it the oracle condition.
We know that two instances together met this oracle condition when they are
members of the same class. Consequently, a trained classifier can be perceived as
a function that indicates that two instances meet said oracle condition. However
a trained classifier may not be ideal to distinguish, among all instances that
meet the oracle condition, which ones are responsible for the classification of an
unknown instance. We consider, for example, the problem known as catastrophic
interference [
We first propose the pseudometric Longitudinal Distance, dL to produce the ratio of incorrect classifications to the total number of epochs.
dL(xi, x) = 1 − (
δe(xi, x)) (1)
Now we propose the non-pseudometric Strict Longitudinal Distance, dSL(xi, x) = 1 − ee==1k we(xi)δe(xi, x) ee==1k we(xi)
We define the distance space as (d, X) for the distance pseudo-metric dL(xi, x), along with dSL(xi, x) where xi, x ∈ X are instances mapped by features f ∈ F that are classified by a classifier Ce at epoch e and receive a label y ∈ Y to indicate their outcome class.
In the above expressions, the 1Ce(xi)=Ce(x) in Equation 3 is the indicator function taking the value of 1 when they are equal and 0 otherwise.
For assigning relevance, we incorporate we(xi) as a binary weight to Equation 2 that indicates whether the classifier Ce(xi) is correct or wrong. When we(xi) = 1, this means the label y predicted by the classifier Ce(xi) for xi is equal to the label of the instance and thus it is correct, otherwise we(xi) = 0. We observe that Equation 1 assumes xi as a training instance and therefore there is a label y designated as its class and thus we(xi) can be computed. Note that only the correctness of the classification of the training instance is verified as the correct label of unseen instances is unknown. Consequently Equation 2 is suited for computing the distances between a training instance xi ∈ Xtrain and a testing instance x ∈ Xtest, which is the goal of this paper.
Note that we can rewrite (3) (5) which is the mean number of classifier mismatches over all the epochs.
Next we demonstrate that dL a pseudo-metric. Recall the pseudo-metric properties: 1. d(x, x) = 0 2. d(x, y) = d(y, x) 3. d(x, y) ≤ d(x, z) + d(z, y) What makes d a pseudo-metric and not necessarily a metric is that in order to be a metric, if d(x, y) = 0, then x = y. Because of mapping into feature space to evaluate the classifier, there may exist predictors, xi and x, for which xi = x, but d(xi, x) = 0.
For dL(xi, x), dL(xi, x) =
1 e=k 1Ce(xi)=Ce(x) = k e=1 0 = 0. The symmetry property is also obvious. For the triangle property, given x, y, and z, suppose Ce(x) = Ce(y). Then, regardless of what the two terms on the right are. If, instead, Ce(x) = Ce(y), then
1Ce(x)=Ce(y) = 1 Now we argue by contradiction. Suppose for some choice of z, For this to be true, each of these two terms must be zero, so 1Ce(x)=Ce(z) + 1Ce(z)=Ce(y) = 0
Ce(x) = Ce(z) = Ce(y) (6) (7) (8) (9) (11) 1Ce(x)=Ce(z)+1Ce(z)=Ce(y) = dC (x, z)+dC (z, y) But this contradicts the assumption that Ce(x) = Ce(y). Thus, 1Ce(x)=Ce(z) + 1Ce(z)=Ce(y) ≥ 1, and Consequently the triangle equality holds for each epoch, and it must then hold over any finite sum of epochs: 1Ce(x)=Ce(y) ≤ 1Ce(x)=Ce(z) + 1Ce(z)=Ce(y) (10) dL(x, y) = The variant Strict Longitudinal Distance considers a relevance weight based on how correct the classifier Ce(x) is throughout its life cycle.
If the we were independent of the xi and x arguments, then the analogous computations would demonstrate dSL, Equation 2, to also be a pseudo-metric. However, because of dSL’s dependence on the binary weights, we(xi), on the first argument, xi, it fails to be a pseudo-metric when x ∈ Xtest is an element of the training set. It does, however, satisfy the properties that dSL(x, y) ≥ 0 and dSL(x, x) = 0, so it provides some weaker notion of distance between points. 3
To use the proposed metrics dL and dSL for explaining decisions of an NN, it is necessary that the weight matrices produced at every epoch are preserved. If those have not been preserved, then it is necessary to retrain the NN preserving its weight matrices. Due to its non-deterministic nature, the instance to be explained has to be solved again by the trained classifier for an explanation to be provided. To explain a given target instance, we propose to compute the distance between the target instance and all training instances using the longitudinal distance or the strict longitudinal distance. With the results of distances, it is then possible to determine the minimum (i.e., shortest) distance observed between the target and training instances. Now note that multiple training instances can be equidistant to the target, and this is exactly why longitudinal distances fail the axioms for being metrics.
Definition 1 The shortest distance observed between a given target instance and all training instances computed through longitudinal distances is defined as the explainer distance.
Definition 2 The set of instances that are equidistant to the target instance at the explainer distance constitute the positive explainer set.
The positive explainer set and the negative explainer set are further specified in that the explainer set computed via longitudinal instances is, by nature of equations (1) and (2), the positive explainer set. The premise of the longitudinal distances may be reversed to compute the negative explainer set by modifying Equation (3) as follows: the 1Ce(xi)=Ce(x) in Equation 12 is the indicator function taking the value of 1 when they are not equal and 0 otherwise.
Definition 3 The negative explainer set is the set of instances computed via longitudinal distances that represent negative instances in classifying a given target instance.
Definition 4 The explainer set results from the combination of the positive explainer set and the negative explainer set.
The instances belonging to the explainer set we theorize are responsible for producing the solution to the target instance and consequently can explain its solution. Once the explainer set is known, some considerations are needed. First, the explainer distance needs to be defined based on a precision value E . The value for E depends on the domain given that explanations tend to be domaindependent. Second, a training instance may produce a direct or indirect explanation. A direct explanation would be one that does not require any further processing as in all contents of the training instance(s) suffices to explain the target instance. An indirect explanation may require further processing such as comparing whether all features of the target instance match the instances of the training instance chosen to explain the target. Third, the explainer set may include one or more training instances. When cardinality is greater than one, then a process to select the most loyal explanation may be needed. As a result of this process, it may be that no explanation is given. Fourth, if the explanation is meant to foster human trust, the explainer set may need to be interpreted. When the set is meant to produce accountability, then it has to be logical.
We note that the negative explainer set is needed to demonstrate positive and negative instances that could be potentially used to train a classifier. When used to select the best candidate for explanation, the positive explainer set suffices. 4
We used the MNIST data set consisting of 55k training instances, and 10k testing instances. We implemented a convolutional neural network design consisting of 1 convolutional layer with 28 3x3 kernels, 1 max pool layer of size 2x2 and stride of 1. The resultant layer is flattened and then connected to 1 hidden layer with 128 nodes with ReLU activation function for every node. A dropout of 20% is introduced following the hidden layer. The resultant output is passed to the output layer with 10 nodes (each corresponding to the label) with the Softmax activation function. This entire network is trained with 55,000 28x28 MNIST images in batches of 64 over 10 epochs. This training reached an accuracy of 83.9%1.
Fig. 1 shows the images of the entire positive explainer set for one of the testing instances from MNIST labeled as a number nine. This positive explainer set was selected for illustration because its cardinality is 12 and thus we can show all the 12 images that are at distance zero from the target testing instance, measured by dL. The negative explainer set contains 3,569 images. Figure set shown circled in blue is a 0.4% sample of the complete set of images at distance 1, which included 3,569 images.
Although not a validation of accuracy, images are often presented to illustrate feature attribution methods. In Fig. 1 the negative explainer set is a random selection of the large overall set. In that sample, the types of nines are still nines but they are of a different category from those in the positive explainer set and the target instance. 4.2
Fidelity of explanations with longitudinal distances
Fidelity of an explanation is a metric that aims to determine how well an
explanation generated by an XAI method aligns with ground-truth [
Data set and deep neural network classifier. We selected 403,200 instances for training and 100,000 for testing and validation. We trained a deep learning architecture with 1 hidden layer and 8 nodes. The activation for the input and hidden layers was done using ReLU functions and for the output layer using the Softmax activation function. The loss calculated was categorical cross entropy. The 403,200 training instances were trained in batches of 128 over 15 epochs and reached an accuracy of 95% in the testing set. As required to implement the longitudinal distances, we preserved the classifiers at each epoch. Accuracy metric and hypothesis. As earlier described, the data in this experiment was designed with equations that are known and are used to designate the class of the instances. This way, an XAI method produces a correct 1 Code and results are available https://github.com/Rosinaweber/LongitudinalDistances explanation if it selects to explain a target instance with a training instance that implements the same equation with which the instance being explained was built. The explanation will be given by an existing training instance, which has a label. Consequently, correctness is observed when the class label of the training instance selected to explain the target instance has the same label as the target instance being explained. With the definition of a correct explanation, we can define accuracy as the ratio of correct explanations to the total explanations produced by the proposed approach. Our hypothesis is that the proposed method using both longitudinal distances will select instances to explain the classifications produced by the deep NN architecture with average accuracy above 95%. Methodology. With the classifier trained, we randomly selected 1,000 from the 100,000 testing instances to measure the accuracy of the proposed approach. This evaluation, as the metric describes, only seeks the selection of the class of explanations, and thus it does not use the negative explainer set. For each instance, we followed these steps: 1. Compute the positive explainer set using dL and dSL. 2. Use the label of each instance to create subsets of instances for each label. 3. Determine the largest subset and use its label as explanation. 4. Assess whether label is correct. 5. Compute average accuracy.
Results. Of the 1,000 testing instances, there were 978 and 980 correct explanations for the approach when using dL and dSL, respectively. Both average accuracy levels are above 95%, which is consistent with our hypothesis. The classifier is correct for 968 instances out of 1,000 (96.8%), being wrong in 32 instances. Both distances led to the selection of the wrong explanation only when the classifier’s predictions were wrong. However, the distances do not indicate the wrong explanations whenever the classifier is wrong. Interestingly, both distances dL and dSL were correct, respectively, in 10 and 12 instances for which the classifier was incorrect.
Discussion. It is curious that the distances led to the selection of the correct explanation in instances when the classifier was wrong because the distances are based on the results of the classifier. We examined whether there was anything else unusual about those instances. We found that when dL was able to select correct explanations while the classifier was wrong, the cardinality of the explainer sets was much smaller than in other instances. Considering when the classifier was wrong, the average size of the explainer set was 274 instances when the correct explanation was selected in comparison to 23,239 when the explanation was not correct. We then examined the predictions of the classifier throughout the 15 epochs and computed two values, namely, the number of distinct predictions and the number of times the prediction changed. Table 1 shows the values for all instances where dL selected the correct explanation when the classifier was wrong. The correlation between the explainer set and the respective number of distinct predictions and changes is 0.60 and 0.74. We also computed the correlation between the explainer set and the respective number of distinct predictions and changes for when dL was not correct, and the results are 0.82 and 0.72. These correlations suggest that the more changes in labels the classifier makes as it is learning, the more demanding the distances become causing the explainer sets to be more efficient. There is a lot to investigate further on this finding. 5
In this paper, we introduced longitudinal distances to be computed between an unseen target instance classified by an NN and all training instances used to train it. The training instances at the shortest distance from the target instance constitute its explainer set. The training instances that are members of the explainer set are hypothesized to have contributed to classify the target instance. As such, they can be potentially used to explain the target instance.
Longitudinal instances are inspired by the similarity heuristics and the principle that similar problems have similar solutions. Although not demonstrated yet, instance attribution methods have the potential to bring to example-based XAI, particularly when implemented with CBR, the facet of attribution, currently missing in those approaches.
In this paper, the positive explainer set was used to select the best candidate for explanation. We did not use the negative explainer set. It is obvious that, if we are interested in accountability, as this paper described in its motivation, then we first need to demonstrate that the explainer set produces the explained decision; this is when we will use the negative explainer set. Ultimately, we also need to determine how to modify the set to change its decisions.
New XAI and IML approaches should demonstrate how they address any criticisms. Demonstrating how they perform in presence of noise, the proportion of outliers in the explainer set, and the proportion of overlap across explainer sets for multiple instances are future work for longitudinal distances. Acknowledgments. Support for the preparation of this paper to Rosina O Weber and Prateek Goel was provided by NCATS, through the Biomedical Data Translator program (NIH award 3OT2TR003448-01S1). Gideon Simpson is supported by NSF Grant no.DMS-1818716.