Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization

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

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.

Causal DAG and feature ranges used to model interactions.

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.

Transitive reduction of a sequence into a partial order DAG.

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

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