Source-linked AI summary
Efficient Search for Diverse Coherent Explanations
Chris Russell
TL;DR
The paper addresses the difficulty of generating reliable, coherent counterfactual explanations for complex mixed data without brute-force enumeration. It uses mixed polytopes with mixed-integer programming and reports coherent, informative diverse explanations on standard tasks and FICO data, while acknowledging non-causal and optimization-related limitations.
Problem
Existing counterfactual methods left technical questions about efficient, reliable generation, especially for mixed data and diverse explanations.
Method
The paper combines mixed-polytope constraints with integer programming to generate coherent counterfactuals for mix-encoded data and integrates criteria for generating diverse explanations.
Results
The fully automatic approach generates coherent and informative diverse explanations for a range of sample inputs on standard explainability problems and the FICO explainability dataset.
Takeaways & Limitations
The methods extend counterfactual explanations to mixed financial data while avoiding brute-force enumeration and supporting explanations that map back to the underlying data structure.
Takeaways & Limitations
The counterfactual definition is looser than causal definitions, and the Lagrangian approach has stability issues requiring sufficiently large λ.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The paper addresses the gap between powerful but opaque machine-learning decisions and the need for coherent, diverse counterfactual explanations. It introduces mixed-integer methods for generating such explanations on mixed data and evaluates them on standard tasks and FICO data.
- Complex machine-learning models can achieve high performance while remaining difficult for even their creators to understand.
- Counterfactual explanations focus on how a person’s data would need to change to obtain a different classifier outcome.
- The paper targets unanswered technical questions about generating counterfactuals efficiently and reliably for standard classifiers.
- A mixed-polytope integer program generates coherent counterfactuals for linear classifiers applied to mix-encoded data, mapping solutions back to the original data structure.
- The authors introduce criteria for diverse counterfactuals and integrate them with the mixed-polytope method.
- The fully automatic approach generates coherent and informative diverse explanations across standard explainability problems and the FICO explainability dataset.
2 PRIOR WORK
Prior work includes surrogate, case-based, and counterfactual explanations, but leaves gaps around coherent mixed-data search and concrete diversity-generation methods. The paper formulates counterfactual search with explicit optimization constraints while noting important stability and scope limitations.
- Surrogate methods approximate complex decision functions globally or locally, while case-based methods show similar training examples.
- Counterfactual methods seek minimal data changes that alter an algorithm’s response, with applications to continuous and discrete data.
- Users have been found to prefer counterfactual explanations over case-based reasoning.
- The paper minimizes weighted ℓ1 distance subject to the desired classifier response, using explicit constraints and integer programming for binary variables.
- The paper’s counterfactual definition is looser than causal-literature definitions, so the distance function must be chosen carefully.
- The weighted inverse-MAD distance encourages sparse changes, is scale-free in a limited sense, and is robust to outliers.
- The Lagrangian formulation can have stability problems because sufficiently large λ creates a deep, narrow objective valley near the decision boundary.
3 COHERENT COUNTERFACTUALS ON MIXED DATA
The paper formulates coherent counterfactual generation for linear classifiers on mixed data, where variables combine contiguous ranges with discrete states. Its mixed-polytope constraints and integer programming formulation prevent invalid encoded solutions while supporting distance-weighted search.
- Mixed-data setting: Mixed data variables may take contiguous values or special discrete states, making counterfactual distance and search nontrivial.The FICO delinquency example distinguishes changing a numeric value from switching between qualitatively different special states.
- Mixed-data setting: One-hot-style embeddings introduce extra degrees of freedom that can produce encoded states with no counterpart in the original data space.For example, multiple indicator variables may be active simultaneously even though the original variable has one valid state.
- Mixed-polytope formulation: The mixed polytope uses linear constraints plus binary indicator variables to guarantee that generated counterfactuals remain coherent and map back to the original data structure.The formulation assumes a linear classifier over the mixed encoding and constrains contiguous and discrete components jointly.
- Mixed-polytope formulation: The resulting integer program enforces the classifier boundary while minimizing a weighted ℓ1 change objective over the encoded counterfactual.The boundary may use f(x′) ≤ 0 because changing a discrete state can cross the boundary rather than reach it exactly.
- Parameter choices: Weights are chosen with inverse MAD for contiguous variables and a normalized standard deviation for binary variables, with transition costs adapted to the original state.The binary-variable adjustment addresses the zero MAD produced by binary distributions.
- Parameter choices: The encoding baseline F_i is selected per explanation so transitions between contiguous and discrete states do not incur an additional penalty while remaining representative.F_i is set to the current value for contiguous states and to median(X_i) for discrete states.
4 DIVERSE EXPLANATIONS
The paper treats diversity as a separate requirement because one counterfactual may be restrictive or unusable even when other favorable changes exist. It generates alternatives by prohibiting previously used variable-state transitions and iteratively retaining only feasible constraints.
- Motivation: Multiple counterfactuals can help when a single suggested change is restrictive or cannot be altered by the data subject.Providing no alternative can also convey that no other explanation exists.
- Motivation: For linear classifiers, convexity means local optima do not provide a source of diverse counterfactuals because the objective has only one minimum.The paper therefore uses explicit diversity constraints instead.
- Diversity constraints: The method induces diversity by restricting states or values previously altered in generated counterfactuals while allowing other transitions for the same variable.Rules differ for discrete-to-discrete, discrete-to-contiguous, and contiguous-to-new-contiguous changes.
- Diversity constraints: Each diversity constraint is added individually and removed immediately if it makes the mixed integer program infeasible.Generation stops when the new explanation is identical to the previous one.
5 EXPERIMENTS
Experiments on LSAT and FICO show that the method automatically generates human-readable, coherent, and diverse counterfactual explanations, while exposing model behavior and practical presentation limits.
- Experimental setup: The approach generates sparse, human-readable counterfactuals automatically for mixed-data classification problems.Explanations specify score changes and the variables whose values would need to change.
- 5.1 LSAT: On LSAT, diverse explanations make the classifier’s racial bias more apparent than the previous approach.The earlier method heavily penalized race changes because only 6% of the dataset was identified as black.
- 5.1 LSAT: The LSAT explanations avoid gratuitous diversity when changing LSAT score alone is sufficient and necessary for a different outcome.The method does not add explanations that jointly vary LSAT score and GPA in that case.
- Experimental limitations: The experiments do not compare against Wachter et al.’s baseline because brute-force enumeration would require approximately 4 million runs.This limits direct baseline comparison in the reported experiments.
- 5.2 The FICO Explainability Challenge: For similar FICO individuals, generated explanation sets are broadly stable and provide similar amounts of information.However, complete sets can overwhelm users, and further work is needed to identify the most comprehensible and useful explanations.
- 5.2 The FICO Explainability Challenge: Later diverse counterfactuals become less diverse and less comprehensible because greedy selections can keep large changes active while toggling incidental variables.Stopping earlier or using a less greedy procedure are proposed responses.
- 5.2 The FICO Explainability Challenge: The generated FICO counterfactuals provide insight into general classifier behavior, including how strong credit factors can compensate for a missed payment.The paper notes that using counterfactuals to improve scores raises concerns about gaming the system.
6 CONCLUSION
The paper presents coherent and diverse counterfactual explanations for mixed datasets as a step toward practical use. It addresses scalability problems in linear mixed financial data while identifying broader generalization as future work.
- The paper is the first to generate coherent counterfactual explanations for mixed real-world datasets and propose a concrete method for diverse counterfactuals.
- Generalizing the approach to nonlinear and nondifferentiable classifiers such as k-nearest neighbour or random forests remains a useful direction for future work.
- Brute-force enumeration from previous approaches does not scale to mixed financial datasets, motivating more reliable methods that work out of the box.
- The methods address major technological issues for linear models, an important machine-learning setting used widely by industry and data scientists.