Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization
Introduction
Machine learning models are increasingly used in high-stakes decision-making, such as loan approvals or medical diagnoses. To improve transparency, researchers have developed Counterfactual Explanations (CE). A CE provides actionable recourse by suggesting minimal changes to input features that would result in a desired outcome (e.g., "If your income were $5,000 higher, your loan would be approved").
However, standard CE methods typically provide a static "perturbation vector"—a final destination without a roadmap. They ignore the fact that features often interact causally. For instance, increasing one's "Job Skill" might naturally lead to a higher "Income." Ignoring these dependencies can lead to inefficient or even impossible recommendations. This paper introduces Ordered Counterfactual Explanation (OrdCE), a framework that optimizes both the required changes and the sequence in which they should be performed.
The OrdCE Framework
The core innovation of OrdCE is treating an explanation as a pair: a perturbation vector (the "what") and a permutation (the "order").
Modeling Feature Interactions
The authors assume that feature interactions can be represented by an interaction matrix $M$, often derived from a causal Directed Acyclic Graph (DAG). This matrix captures how a change in one variable propagates to others.
As shown in the figure above, a causal DAG defines the relationships between features like Education and JobSkill. If Education has a causal effect on JobSkill, acting on Education first may reduce the total effort required to reach a target state.
Optimization via MILO
Finding the optimal sequence is a complex combinatorial problem. The authors formulate this as a Mixed-Integer Linear Optimization (MILO) problem. This approach allows the simultaneous optimization of the feature changes and their order, ensuring the lowest "ordered cost" ($C_{ord}$). The framework is versatile enough to handle various underlying models, including Logistic Regression, Tree Ensembles (like Random Forests), and Multilayer Perceptrons (MLPs).
From Sequences to Partial Orders
In many cases, certain features do not interact and can be changed simultaneously. To make the explanations more practical, the authors include a post-processing step that converts the strict sequence into a partial order.
This partial ordering, illustrated in the figure above, provides a clearer roadmap for the user, highlighting which actions are independent and which must follow a specific sequence.
Experimental Results
The researchers evaluated OrdCE across five datasets, including FICO and German Credit. Key findings include:
- Cost Efficiency: OrdCE consistently outperformed "Greedy" baselines, which first determine the changes and then attempt to order them. In some neural network tests, OrdCE reduced the total cost by over 50%.
- Causal Alignment: The suggested orders naturally aligned with the underlying causal structures of the data, making the instructions more intuitive for human users.
- Computational Viability: Despite the NP-hard nature of the optimization, modern MILO solvers typically found optimal solutions for standard explanation tasks within a few minutes.
Conclusion and Future Directions
OrdCE represents a significant step toward more realistic and actionable AI explanations. By accounting for causal flow, it provides users with a path of least resistance toward their goals. Future work will focus on extending the framework to handle non-linear feature interactions and conducting user studies to validate the practical utility of ordered instructions.
Summary updated