Interpretable Counterfactual Explanations Guided by Prototypes

Arnaud Van Looveren; Janis Klaise

Source-linked AI summary

Interpretable Counterfactual Explanations Guided by Prototypes

Arnaud Van Looveren, Janis Klaise

arXiv:1907.02584v2Jul 3, 2019cs.LGstat.ML

TL;DR

Counterfactual search must produce sparse, prediction-changing instances that remain interpretable relative to the target-class data distribution, without costly black-box gradient evaluation. The paper guides optimization with class prototypes, evaluates local interpretability using two metrics, and reports improved interpretability and search speed across image and tabular settings. It also supports meaningful categorical perturbations and actionable counterfactuals.

Problem
Counterfactual methods need to balance prediction change, sparsity, target-class interpretability, and practical search speed, while sparse solutions can remain out-of-distribution.
Method
The model-agnostic method adds a prototype loss that guides perturbations toward a nearest target-class prototype and can remove numerical gradient evaluation for black-box models.
Results
The method produces more interpretable counterfactuals and speeds search across MNIST and Wisconsin Breast Cancer; combining LAE and Lproto reduces time by 82% and iterations by 90% versus A.
Takeaways & Limitations
Prototype guidance makes counterfactual explanations more practical by improving interpretability, accelerating search, and removing the black-box numerical-gradient bottleneck.
Takeaways & Limitations
The baseline LAE term does not consistently speed search because it penalizes reconstruction distance without explicitly guiding counterfactuals toward interpretable solutions.

Abstract

from arXiv · show

We propose a fast, model agnostic method for finding interpretable counterfactual explanations of classifier predictions by using class prototypes. We show that class prototypes, obtained using either an encoder or through class specific k-d trees, significantly speed up the the search for counterfactual instances and result in more interpretable explanations. We introduce two novel metrics to quantitatively evaluate local interpretability at the instance level. We use these metrics to illustrate the effectiveness of our method on an image and tabular dataset, respectively MNIST and Breast Cancer Wisconsin (Diagnostic). The method also eliminates the computational bottleneck that arises because of numerical gradient evaluation for $\textit{black box}$ models.

1. Introduction

The paper frames counterfactual explanations as interpretable changes that alter model predictions, while requiring sparsity, proximity to the target-class distribution, and practical search speed. It proposes class prototypes to guide this search and improve counterfactual quality.

Motivation: Counterfactuals describe feature changes that alter a model’s prediction toward a predefined output.They are found by iteratively perturbing the input through an optimization objective.
Requirements: A satisfactory counterfactual should match the desired prediction, use sparse perturbations, remain interpretable, and be found quickly.Interpretability is defined relative to the training distribution, especially instances from the counterfactual class.
Interpretability: Sparse changes can still produce counterfactuals that are out-of-distribution for the target class.The house-price example shows that changing bedrooms alone may cross the prediction threshold without matching other high-value houses.
Proposed approach: Class prototypes guide perturbations toward interpretable counterfactuals while removing numerical-gradient bottlenecks for black-box models.The method is evaluated on MNIST and Wisconsin Breast Cancer, with categorical-variable handling demonstrated on Adult Census data.

2. Related Work

Prior counterfactual methods use optimization or heuristic searches but do not adequately address local, class-specific interpretability and efficient black-box search. This paper uses prototypes, interpretability metrics, and distance-based categorical embeddings to address these gaps.

Counterfactual explanations: Counterfactual explanations offer an alternative to feature-attribution methods such as LIME and SHAP for explaining individual predictions.They construct synthetic instances from real instances that change a model’s prediction.
Prior methods: Existing approaches minimize prediction and perturbation losses or use heuristic sphere searches without local, class-specific interpretability.Black-box search can also require prediction calls proportional to input dimensionality.
Prototype guidance: Class prototypes guide counterfactual search and can be computed from mean encodings or class-specific k-d trees.The approach builds on prototype-based explanations and related uses in clustering, classification, and few-shot learning.
Evaluation: Two metrics evaluate local interpretability against the training-data distribution rather than relative to a target model or human task performance.This provides an instance-level benchmark for counterfactual quality.
Categorical variables: Pairwise category distances create numerical embeddings that define meaningful perturbations for categorical variables.This addresses approaches that are computationally expensive or ignore relationships between categories.

3. Methodology

The method augments counterfactual objectives with class prototypes to guide perturbations toward interpretable target-class instances while accelerating search. It supports encoder-based or k-d-tree representations and addresses categorical features through distance-based embeddings.

Background: The baseline objective combines prediction, elastic-net distance, and autoencoder reconstruction losses, but can produce sparse counterfactuals outside the target-class distribution.The autoencoder term penalizes out-of-distribution instances without explicitly modeling each prediction class.
Prototype loss term: Prototype guidance aims to produce counterfactuals in the counterfactual-class distribution and speed search without extensive hyperparameter tuning.These are the two stated purposes of the prototype loss.
Prototype loss term: Encoder-based prototypes average the K nearest same-class training instances in latent space, where the prototype is explicitly defined rather than in the original feature space.The predictive model labels the representative training set before nearest-neighbor selection and averaging.
Prototype loss term: Adding Lproto yields an objective that guides perturbations toward a prototype from a different class, with the autoencoder term becoming optional.The prototype loss is Lproto = θ · ∥ENC(x0 + δ) − protoj∥2, and the full objective adds it to prediction, distance, and reconstruction terms.
Using k-d trees as class representations: Without an encoder, separate class-specific k-d trees identify a target-class prototype in the original feature space for the counterfactual optimization.The algorithm builds one tree per predicted class, selects a nearest target-class item, and optimizes distance to that prototype.
Categorical variables: Categorical variables are handled by inferring pairwise category distances and embedding categories into numerical space for meaningful perturbations.This approach is intended to account for relationships between categories during counterfactual generation.
Prototype loss term: Prototype guidance can remove repeated numerical-gradient prediction calls for black-box models, reducing a 28 × 28 MNIST update from 1568 calls to one class-check call.The prediction function is still called once per gradient update to check whether the perturbed instance changes class.

4. Experiments

Experiments on MNIST and Breast Cancer Wisconsin evaluate prototype-guided counterfactuals for speed, sparsity, and local interpretability. Across both datasets, prototype terms generally improve search efficiency and interpretability, while sparsity may decrease as distributional guidance is added.

Experimental setup: The experiments evaluate counterfactuals on MNIST, Breast Cancer Wisconsin, and Adult, using autoencoder or k-d-tree prototypes depending on dataset structure.MNIST uses an autoencoder, Breast Cancer Wisconsin uses k-d trees, and Adult illustrates categorical-feature handling.
Evaluation measures: Sparsity is measured with EN(δ), while search speed is measured by time and gradient updates until a satisfactory counterfactual is found.A satisfactory counterfactual is defined as the optimal counterfactual found using FISTA for a fixed c when counterfactuals exist.
Evaluation measures: IM1 and IM2 quantify local interpretability through class-specific and all-class autoencoder reconstructions, with lower values indicating more interpretable counterfactuals.IM1 compares reconstruction errors across the counterfactual and original classes; IM2 compares reconstructions from the counterfactual-class and all-class autoencoders.
MNIST results: On MNIST, combining LAE and Lproto reduces search time by 82% and gradient iterations by 90% compared with A.Adding Lproto alone reduces time by 77% and iterations by 84% compared with A.
Interpretability and sparsity: Prototype-guided counterfactuals can trade sparsity for interpretability, and in visual examples they produce clear target-class digits supported by autoencoder reconstructions.Loss A produces the sparsest counterfactuals, whereas prototype-guided losses generate more interpretable examples.

5. Discussion

The paper concludes that prototype-guided, model-agnostic counterfactual search improves interpretability and speed while supporting actionable explanations and open-source use.

Prototype-guided counterfactual search produces more interpretable instances according to two novel interpretability metrics.
Prototypes speed up counterfactual search and remove numerical-gradient bottlenecks for black-box models.
Fixing selected features during search yields actionable counterfactuals describing concrete steps for changing predictions.
The authors provide an open-source library implementing the method.

A. Breast Cancer Wisconsin experiment details and results

The Breast Cancer Wisconsin experiment uses a neural classifier and class-specific autoencoders to evaluate prototype-guided counterfactuals, including hyperparameter robustness and feature-change patterns.

The classifier is a two-layer feedforward neural network reaching 100% test accuracy on standardized features.It uses 40-neuron ReLU layers and is trained with stochastic gradient descent for 500 epochs.
Class-specific autoencoders evaluate IM1 and IM2 using a three-layer encoder and a mirrored decoder.The autoencoders are optimized with Adam for 500 epochs using batches of 128 instances.
The experiment keeps c, κ, and β fixed at 1, 0, and 0.1, respectively, and visualizes results in Figure 6.
A broad range of θ and k values performs well in the hyperparameter studies shown in Figures 7 and 8.
Figure 9 compares the total and unique feature changes produced by the three loss functions.
All experiments were run on a ThinkPad T480 with an Intel Core i7-8550U processor.

B. MNIST experiment details

The MNIST experiments evaluate counterfactual objectives with convolutional models and autoencoders, varying θ and k while examining speed, interpretability, sparsity, and feature changes.

The MNIST classifier is a convolutional network trained for three epochs that reaches 98.6% test accuracy.It uses two convolutional layers, max pooling, dropout, and a softmax output over ten classes.
Figure 6 reports Breast Cancer Wisconsin counterfactual search time, gradient updates, IM1, IM2, and sparsity for objectives A, B, and C.Lower values are better for IM1 and IM2; error bars show variability or 95% confidence bounds as specified.
Figures 7 and 8 vary θ and k to assess their effects on counterfactual search time, interpretability, and sparsity.The tested θ values are 10, 20, 50, 100, 150, and 200; k values are 1, 2, 5, and 10.
The MNIST autoencoder for objectives B to F uses convolutional encoder and decoder layers with pooling and upsampling.It is trained with Adam for four epochs using mean squared reconstruction error.
Class-specific MNIST autoencoders use three convolutional encoder layers and reversed decoder architectures with upsampling.They are trained with Adam for 30 epochs and batches of 128 instances.
Parameters c, κ, β, and γ are fixed at 1, 0, 0.1, and 100, while θ is set according to the reconstruction loss used.
All experiments were run on a ThinkPad T480 with an Intel Core i7-8550U processor.

C. MNIST additional results

Additional MNIST results examine black-box gradient costs, the effect of K on generated counterfactuals, and examples across objective functions.

Table 3 measures the time required for 100 optimization steps when numerical gradients are needed for black-box models.It compares objective functions A′, E, and F using mean seconds with 95% confidence bounds.
A′ is objective A evaluated without model-architecture access, requiring prediction queries and numerical gradient evaluation.
Figure 10 examines how K affects the speed, quality, and sparsity of MNIST counterfactuals.
Figures 12 and 13 provide additional MNIST counterfactual examples generated with various objective functions.

D. Categorical feature embedding details

The method embeds categorical features into one-dimensional numerical spaces so perturbations can be defined while reflecting relationships between categorical values.

Each categorical feature is embedded into one-dimensional numerical space to support counterfactual search through feature perturbations.The embedding is intended to reflect the underlying relation between categorical values.
The embedding procedure first computes a k × k distance matrix for each categorical variable, then applies multidimensional scaling.MVDM and ABDM are considered for constructing the pairwise distance matrices.

D.1. Pairwise distances

Pairwise distances between categorical values are inferred using class-distribution similarity or conditional-distribution dissimilarity, with Figure 10 documenting prototype-related settings for MNIST.

MVDM: MVDM takes the data, classifier labels or predictions, and parameter α as inputs for comparing two categories of a categorical feature.The data representation assumes columns are numerical variables or ordinally encoded categorical variables.
MVDM: MVDM measures categorical similarity by comparing relative frequencies across classifier prediction classes.The method sets α = 1; categories are more similar when their class-frequency profiles match.
ABDM: ABDM defines distance through dissimilarities between conditional probability distributions of other features given two values of a categorical feature.The implementation uses Kullback-Leibler divergence and discretizes every numerical feature.

D.2. Multidimensional scaling

After estimating category distances, the method uses multidimensional scaling and norms of the resulting embeddings to create scaled one-dimensional categorical values.

Embedding construction: Multidimensional scaling first embeds each category into 2-dimensional Euclidean space, whose embedding norms become one-dimensional numerical values.The datapoint with the largest Frobenius norm is used as the origin.
Scaling: The one-dimensional category values are standard-scaled or min-max-scaled so embedded categorical features share a common range.The origin is chosen before scaling from the datapoint with the largest Frobenius norm.

E. Multiple model comparison test description and results on MNIST

The MNIST evaluation compares six counterfactual-generating losses with kernel multiple-model tests performed separately for each predicted class. Prototype-containing losses are generally favored for classes with more than 200 samples, while class-specific sample sizes constrain some tests.

Test setup: Kernel multiple-model comparison tests evaluate how well counterfactual instances from each loss model the counterfactual predicted-class distribution.The tests use the open-source implementation of Lim et al. (2019).
Test procedure: The test compares six loss-function models using MMD-based reference selection followed by conditional testing against the selected reference model.The null hypothesis states that each non-reference model is worse than the reference, conditional on the selection event.
Test variants: RelMulti uses independent fitting and testing samples, whereas RelPSI reuses the same sample to address false-positive-rate control differently.RelMulti partitions samples 50:50 for fitting and testing.
Sample generation: Counterfactual samples are generated from shared MNIST test instances for losses A–F, recording original and counterfactual predicted classes.Differences in total sample counts arise from computational constraints.
Limitations: Some predicted classes have very few generated instances because the method cannot control which class a counterfactual reaches.For counterfactual class 1, loss B produced only 8 instances, limiting that class’s test sample size.
Sample balancing: Per-class tests use the minimum available class count across losses, with larger samples subsampled without replacement.The corresponding MNIST test-set comparison uses the same number of instances per class.
Results: For classes with sample size > 200, non-zero rejection rates mostly correspond to losses A and B, which omit the prototype term.Figure 11 reports selection and rejection rates by counterfactual class for RelMulti and RelPSI.
Interpretation: Class-specific testing is necessary because aggregating classes can make sparsity-only loss A appear to perform well despite producing adversarial-like counterfactuals.Loss A can resemble the original instance while changing the model prediction, yielding small aggregate rejection rates.