Model-Agnostic Counterfactual Explanations for Consequential Decisions

Amir-Hossein Karimi, Gilles Barthe, Borja Balle, Isabel Valera

Abstract

Predictive models are being increasingly used to support consequential decision making at the individual level in contexts such as pretrial bail and loan approval. As a result, there is increasing social and legal pressure to provide explanations that help the affected individuals not only to understand why a prediction was output, but also how to act to obtain a desired outcome. To this end, several works have proposed optimization-based methods to generate nearest counterfactual explanations. However, these methods are often restricted to a particular subset of models (e.g., decision trees or linear models) and differentiable distance functions. In contrast, we build on standard theory and tools from formal verification and propose a novel algorithm that solves a sequence of satisfiability problems, where both the distance function (objective) and predictive model (constraints) are represented as logic formulae. As shown by our experiments on real-world data, our algorithm is: i) model-agnostic ({non-}linear, {non-}differentiable, {non-}convex); ii) data-type-agnostic (heterogeneous features); iii) distance-agnostic ($\ell_0, \ell_1, \ell_\infty$, and combinations thereof); iv) able to generate plausible and diverse counterfactuals for any sample (i.e., 100% coverage); and v) at provably optimal distances.

Introduction

When automated systems make life-altering decisions—such as denying a loan or a parole request—providing a simple "why" is insufficient. Individuals need actionable recourse: a clear set of steps to change the outcome. This is the goal of counterfactual explanations, which provide "what-if" scenarios (e.g., "If your income were $10,000 higher, your loan would have been approved").

Existing approaches to generating these explanations often struggle with model dependency, suboptimality, and a lack of realism. Many tools are limited to specific model types or rely on gradient-based optimization that can fail to find the truly nearest explanation or suggest impossible changes like decreasing one's age.

The MACE Framework

To address these challenges, we introduce MACE (Model-Agnostic Counterfactual Explanations). MACE reinterprets the search for counterfactuals as a formal verification problem. Instead of using continuous optimization, it treats both the predictive model and the distance metric as logic formulas.

The MACE architecture: Compiling models and distance functions into logic formulas for an SMT solver.

The core process involves:

  1. Model Compilation: The predictive model (e.g., a Random Forest or Neural Network) is represented as a program and compiled into a first-order logic formula.
  2. Constraint Specification: Distance functions and "plausibility" constraints (e.g., "age cannot decrease") are similarly encoded as logic.
  3. SMT Solving: A Satisfiability Modulo Theories (SMT) solver, such as Z3, is used to find a set of features that satisfy the desired outcome within a specific distance threshold $\delta$.
  4. Optimization via Binary Search: By iteratively adjusting $\delta$ through binary search, MACE converges on the provably optimal (nearest) counterfactual.

Experimental Evaluation

We evaluated MACE on three real-world datasets: Adult (income prediction), Credit (default prediction), and COMPAS (recidivism risk). These datasets feature heterogeneous data types, including numerical, categorical, and ordinal features.

Comparison of MACE against existing counterfactual explanation methods across various criteria.

MACE demonstrated several key advantages over baseline methods like Feature Tweaking (FT) and Actionable Recourse (AR):

  • Optimality: MACE consistently found counterfactuals at significantly smaller distances—reducing the required change by an average of 70% on the Adult and Credit datasets compared to existing approaches.
  • Coverage: It achieved 100% coverage, meaning it successfully found a valid counterfactual for every sample tested across various model architectures (Decision Trees, MLPs, etc.).
  • Actionability: By incorporating logic-based constraints, MACE ensures that suggested changes are realistic and respect user-defined boundaries, such as immutability of certain features.

Conclusion

MACE leverages the power of formal verification to provide robust, model-agnostic, and optimal counterfactual explanations. While the use of SMT solvers introduces a higher computational cost compared to heuristic methods, the guarantee of optimality and 100% coverage makes it a powerful tool for high-stakes decision-making environments. Future work will focus on improving scalability through specialized solvers and better accounting for statistical correlations between features.

Summary updated

Abstract

Predictive models are being increasingly used to support consequential decision making at the individual level in contexts such as pretrial bail and loan approval. As a result, there is increasing social and legal pressure to provide explanations that help the affected individuals not only to understand why a prediction was output, but also how to act to obtain a desired outcome. To this end, several works have proposed optimization-based methods to generate nearest counterfactual explanations. However, these methods are often restricted to a particular subset of models (e.g., decision trees or linear models) and differentiable distance functions. In contrast, we build on standard theory and tools from formal verification and propose a novel algorithm that solves a sequence of satisfiability problems, where both the distance function (objective) and predictive model (constraints) are represented as logic formulae. As shown by our experiments on real-world data, our algorithm is: i) model-agnostic ({non-}linear, {non-}differentiable, {non-}convex); ii) data-type-agnostic (heterogeneous features); iii) distance-agnostic ($\ell_0, \ell_1, \ell_\infty$, and combinations thereof); iv) able to generate plausible and diverse counterfactuals for any sample (i.e., 100% coverage); and v) at provably optimal distances.
BibTeX
@inproceedings{karimi2020model,
  author = {Amir-Hossein Karimi and Gilles Barthe and Borja Balle and Isabel Valera},
  title = {{Model-Agnostic Counterfactual Explanations for Consequential Decisions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=Teay2onJ8M},
}
Figure