Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization

Kentaro Kanamori, Takuya Takagi, Ken Kobayashi, Yuichi Ike, Kento Uemura, Hiroki Arimura

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.

Causal interactions between features like Education, JobSkill, and Income demonstrate why the order of changes matters.

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.

OrdCE provides a clear sequence of actions, specifying the order and magnitude of changes for each feature.

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

Abstract

Post-hoc explanation methods for machine learning models have been widely used to support decision-making. One of the popular methods is Counterfactual Explanation (CE), also known as Actionable Recourse, which provides a user with a perturbation vector of features that alters the prediction result. Given a perturbation vector, a user can interpret it as an "action" for obtaining one's desired decision result. In practice, however, showing only a perturbation vector is often insufficient for users to execute the action. The reason is that if there is an asymmetric interaction among features, such as causality, the total cost of the action is expected to depend on the order of changing features. Therefore, practical CE methods are required to provide an appropriate order of changing features in addition to a perturbation vector. For this purpose, we propose a new framework called Ordered Counterfactual Explanation (OrdCE). We introduce a new objective function that evaluates a pair of an action and an order based on feature interaction. To extract an optimal pair, we propose a mixed-integer linear optimization approach with our objective function. Numerical experiments on real datasets demonstrated the effectiveness of our OrdCE in comparison with unordered CE methods.
BibTeX
@inproceedings{kanamori2021ordered,
  author = {Kentaro Kanamori and Takuya Takagi and Ken Kobayashi and Yuichi Ike and Kento Uemura and Hiroki Arimura},
  title = {{Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17376},
}
Figure