Efficient Search for Diverse Coherent Explanations

Chris Russell

Introduction

As machine learning models are increasingly deployed in high-stakes domains such as finance and law, the demand for transparency has grown. Counterfactual explanations—which answer the question, "What would I need to change to get a different result?"—have emerged as a leading solution for providing actionable feedback. However, traditional methods often produce "incoherent" explanations that are physically impossible or fail to offer a diverse set of alternatives. This paper introduces a robust framework based on Mixed Integer Programming (MIP) to ensure that explanations are both realistic and offer multiple paths to a desired outcome.

The Challenge of Coherence and Diversity

Existing counterfactual generation techniques typically rely on gradient-based optimization. While mathematically elegant, these approaches struggle with "mixed" data types common in real-world applications. For instance, a model might suggest a state where a person is simultaneously employed and retired, or suggest a value for a feature that is marked as "missing" in the database.

Furthermore, most algorithms focus on finding a single "closest" counterfactual. In practice, users benefit from a variety of options. A loan applicant might find it easier to increase their savings than to change their employment status. Providing only a single solution limits the utility of the explanation for the end-user.

Methodology: MIP and the Mixed Polytope

The proposed framework shifts the search for counterfactuals into the domain of Mixed Integer Programming. The core innovation is the mixed polytope, a set of linear constraints that define the space of valid data points.

By encoding categorical variables and handling "special values" (such as missing data codes) within the MIP constraints, the algorithm ensures that every generated explanation is coherent. For example, if a variable is categorical, the solver is constrained to select exactly one valid category. This prevents the "nonsense" states often produced by continuous optimization methods.

To achieve diversity, the paper employs a greedy iterative search. Once the primary (closest) counterfactual is found, a new constraint is added to the optimization problem that excludes the specific feature changes used in the previous solution. The solver is then re-run to find the next best alternative, resulting in a ranked list of distinct explanations.

Empirical Evaluation

The framework was evaluated on two significant datasets: the LSAT dataset and the FICO Explainability Challenge dataset.

LSAT Dataset and Algorithmic Bias

The LSAT dataset, used to predict law school success, serves as a benchmark for auditing algorithmic fairness. The diverse search revealed critical insights into model bias; for certain individuals, the "easiest" way to improve a predicted outcome was to change their race, highlighting the model's reliance on sensitive attributes.

Table 1: Sample data from the LSAT dataset, illustrating the features used for law school success prediction.

FICO HELOC Dataset

This dataset involves Home Equity Line of Credit applications and is characterized by complex "special values" (e.g., negative integers representing different reasons for missing data). The MIP approach successfully navigated these discrete states, providing meaningful suggestions like "provide a bureau record" instead of impossible continuous adjustments to missing values.

Key Results and Interpretability

The MIP-based approach demonstrates superior stability compared to traditional Lagrangian methods, as it avoids the need for fine-tuning trade-off parameters. The resulting explanations are sparse, typically involving changes to only a few features, and are presented in plain English.

Figure 1: Examples of diverse counterfactual explanations generated for the FICO dataset, showing multiple paths to change a 'bad' score to 'good'.

Qualitative analysis of the FICO results shows that the model generates intuitive, ranked lists of actions, such as reducing the number of credit inquiries or allowing trade accounts to age. By using high-performance solvers like Gurobi, the search for these explanations is fast enough for real-time use, even on datasets with dozens of features.

Conclusion and Future Work

This research provides a rigorous method for generating diverse, coherent counterfactual explanations for linear classifiers. By leveraging MIP and the mixed polytope, the framework ensures that AI transparency is both actionable and realistic. While currently focused on linear models—the workhorses of the financial and legal industries—future research will explore extending these coherence constraints to non-linear architectures and ensemble methods.

Summary updated

Abstract

This paper proposes new search algorithms for counterfactual explanations based upon mixed integer programming. We are concerned with complex data in which variables may take any value from a contiguous range or an additional set of discrete states. We propose a novel set of constraints that we refer to as a "mixed polytope" and show how this can be used with an integer programming solver to efficiently find coherent counterfactual explanations i.e. solutions that are guaranteed to map back onto the underlying data structure, while avoiding the need for brute-force enumeration. We also look at the problem of diverse explanations and show how these can be generated within our framework.
BibTeX
@inproceedings{russell2019efficient,
  author = {Chris Russell},
  title = {{Efficient Search for Diverse Coherent Explanations}},
  booktitle = {FAT},
  year = {2019},
  doi = {10.1145/3287560.3287569},
}
Figure