On Counterfactual Explanations under Predictive Multiplicity

Martin Pawelczyk, Klaus Broelemann, Gjergji Kasneci

Abstract

Counterfactual explanations are usually obtained by identifying the smallest change made to an input to change a prediction made by a fixed model (sparse methods). Recent work, however, has revitalized an old insight: there often does not exist one superior solution to a prediction problem with respect to commonly used measures of interest. In fact, often multiple different classifiers give almost equal solutions—a phenomenon known as predictive multiplicity. In this work, we derive a general upper bound for the costs of counterfactual explanations under predictive multiplicity. We compare sparse and data support approaches empirically on real-world data, showing that data support methods are more robust to multiplicity while having provably higher costs under a fixed model. Our results challenge the view that counterfactual recommendations should be sparse in general.

Introduction

As machine learning models are increasingly used for high-stakes decisions like loan approvals, providing actionable feedback to users becomes crucial. Counterfactual explanations (CFEs) serve this purpose by suggesting the minimal changes needed to flip an unfavorable outcome. However, most CFE methods assume the underlying model is static. In reality, multiple models can achieve similar accuracy while having different decision boundaries—a state called predictive multiplicity. This leads to the "cost of negative surprise": a user might implement a recommendation only to find it invalid if the model is updated or replaced by an equally accurate alternative.

Methods: Sparse vs. Data Support Approaches

The paper categorizes CFE methods into two main paradigms:

  1. Sparse Approaches: These seek the smallest possible change (minimal $p$-norm) to reach a decision boundary. While efficient, they are often "brittle" because they exploit narrow gaps specific to one model.
  2. Data Support Approaches: These prioritize recommendations that align with the actual distribution of successful individuals in the training data, ensuring the counterfactual is "semantically meaningful."
Visualizing sparse vs. data-support counterfactuals and the cost of negative surprise.

The authors derive theoretical bounds for CFE costs under multiplicity, showing that the cost depends on the discrepancy between how different models treat negatively predicted individuals. They also propose the "OURS" method, which uses a Variational Autoencoder (VAE) to search for counterfactuals in a latent space, ensuring strong data support.

Key Insights and Results

The research identifies a fundamental trade-off between the "upfront cost" of a recommendation and its "transferability." Sparse methods are cheaper for the user initially but frequently fail when the model changes. In contrast, data-support methods "buy" insurance against model updates by pushing individuals toward clusters where most high-performing models agree on a positive outcome.

Empirical results showing higher transferability of the "ours" (data-support) method across different model types.

Empirical evaluations on the HELOC and "Give Me Some Credit" datasets confirm that the "OURS" method provides significantly higher transferability. For instance, recommendations generated for a linear model remained valid for a Random Forest model far more often than those from sparse methods (GS and AR). While the "OURS" method requires a higher percentile shift (higher cost), it ensures the recommendation remains robust to predictive multiplicity.

Conclusion and Future Work

This work challenges the prevailing preference for sparse counterfactuals. While data-supported explanations are more computationally intensive and costly for the user, their robustness to model changes makes them more reliable in practice. Future research should explore "minimal invariant" recommendations—finding the most efficient changes that remain stable across all models in a multiplicity set—and further investigate the causal links between inputs and targets to ensure recommendations are truly actionable.

Summary updated

Abstract

Counterfactual explanations are usually obtained by identifying the smallest change made to an input to change a prediction made by a fixed model (hereafter called sparse methods). Recent work, however, has revitalized an old insight: there often does not exist one superior solution to a prediction problem with respect to commonly used measures of interest (e.g. error rate). In fact, often multiple different classifiers give almost equal solutions. This phenomenon is known as predictive multiplicity (Breiman, 2001; Marx et al., 2019). In this work, we derive a general upper bound for the costs of counterfactual explanations under predictive multiplicity. Most notably, it depends on a discrepancy notion between two classifiers, which describes how differently they treat negatively predicted individuals. We then compare sparse and data support approaches empirically on real-world data. The results show that data support methods are more robust to multiplicity of different models. At the same time, we show that those methods have provably higher cost of generating counterfactual explanations under one fixed model. In summary, our theoretical and empiricaln results challenge the commonly held view that counterfactual recommendations should be sparse in general.
BibTeX
@inproceedings{pawelczyk2020counterfactual,
  author = {Martin Pawelczyk and Klaus Broelemann and Gjergji Kasneci},
  title = {{On Counterfactual Explanations under Predictive Multiplicity}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=BLZkFcf6Lj},
}
Figure