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:
- 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.
- 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."
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 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