Introduction
Explainable AI (XAI) has become a cornerstone of trustworthy machine learning. Among its most practical tools is Counterfactual Explanation (CE), often referred to as actionable recourse. CE provides users with a specific set of feature changes (a perturbation vector) required to flip a model's decision—for instance, telling a loan applicant exactly how much to increase their income to move from "Denied" to "Approved."
However, standard CE methods treat these changes as a single, simultaneous jump. This approach ignores the reality that features often interact. If "Increasing Job Skills" naturally leads to "Increasing Income," the order in which a user takes these actions significantly impacts the total effort or "cost." This paper introduces Ordered Counterfactual Explanation (OrdCE), a framework that optimizes both the actions and their sequence.
The Problem: Ignoring Feature Interactions
In practice, showing only a perturbation vector is often insufficient. If there is an asymmetric interaction among features, such as causality, the total cost of the action depends on the order of execution.
As shown in the causal DAG above, a change in Education influences JobSkill, which in turn influences Income. If a user improves their education first, the subsequent "cost" to improve job skills is reduced because of the natural causal flow. Existing CE methods fail to capture this "discount," potentially suggesting inefficient or illogical paths to recourse.
The OrdCE Framework
The authors propose OrdCE to find an optimal pair: a perturbation vector (the "what") and a permutation (the "order").
Mixed-Integer Linear Optimization (MILO)
To solve this, the problem is formulated using Mixed-Integer Linear Optimization (MILO). This approach is chosen for its ability to handle discrete permutations and provide exact, globally optimal solutions. The objective function incorporates an Interaction Matrix ($M$)—derived from domain knowledge or causal discovery algorithms like DirectLiNGAM—and a new Ordering Cost Function ($C_{ord}$). This cost function calculates the "actual perturbation" needed at each step, subtracting the "free" changes induced by interactions from previous steps.
The output, as seen in the table above, is a prioritized list of actions. Unlike standard methods that might suggest changing income and health status simultaneously, OrdCE identifies a logical progression (e.g., improving HealthStatus first, then WorkPerDay, then Income).
Key Results and Insights
The researchers evaluated OrdCE across four real-world datasets (FICO, German Credit, WineQuality, and Diabetes) and various model types, including Tree Ensembles and MLPs.
- Cost Efficiency: OrdCE consistently achieved lower total costs compared to greedy baselines. The benefit was most significant in complex models like MLPs, where ordering costs were sometimes reduced by over 50%.
- Causal Alignment: The framework naturally aligns its suggestions with the underlying causal structure. In medical datasets, it correctly prioritized interventions in a sequence reflecting biological reality (e.g., managing insulin before glucose).
- Interpretability through Posets: To further enhance human readability, the authors provide a post-processing step that converts the strict sequence into a Partially Ordered Set (Poset). This allows users to see which actions can be done in parallel and which must follow a specific order.
Conclusion and Future Work
OrdCE represents a significant step toward making AI explanations truly actionable. By accounting for the "free" perturbations provided by feature interactions, it offers a more realistic and cost-effective path for users. While the current framework assumes linear interactions, future work aims to extend this to non-linear relationships and conduct user studies to validate the practical utility of ordered instructions.
Summary updated