Abstract
Counterfactual Explanation (CE) is a post-hoc explanation method that provides a perturbation for altering the prediction result of a classifier. An individual can interpret the perturbation as an "action" to obtain the desired decision results. Existing CE methods focus on providing an action, which is optimized for a given single instance. However, these CE methods do not address the case where we have to assign actions to multiple instances simultaneously. In such a case, we need a framework of CE that assigns actions to multiple instances in a transparent and consistent way. In this study, we propose Counterfactual Explanation Tree (CET) that assigns effective actions with decision trees. Due to the properties of decision trees, our CET has two advantages: (1) Transparency: the reasons for assigning actions are summarized in an interpretable structure, and (2) Consistency: these reasons do not conflict with each other. We learn a CET in two steps: (i) compute one effective action for multiple instances and (ii) partition the instances to balance the effectiveness and interpretability. Numerical experiments and user studies demonstrated the efficacy of our CET in comparison with existing methods.
Introduction: The Challenge of Actionable Recourse
Imagine a bank denies your loan application based on an AI model. A Counterfactual Explanation (CE) tells you what would have needed to be different: "If your income were $5,000 higher, you would have been approved." This is called Actionable Recourse.
However, most existing CE methods are "individualized"—they calculate a unique path for every single person. In a corporate or regulatory setting, this creates two major headaches:
- Inconsistency: Two very similar people might receive wildly different (and seemingly unfair) advice.
- Opacity: It is difficult for a manager or auditor to see the "big picture" of how the model suggests people should change.
The authors address the challenge of providing recourse to multiple instances at once while ensuring the reasons are easy to understand and do not conflict with one another.
Methodology: Counterfactual Explanation Trees (CET)
The authors introduce the Counterfactual Explanation Tree (CET). While a standard decision tree predicts a label (e.g., "Will this employee leave?"), a CET predicts an action (e.g., "Increase salary by 10%").
The framework operates in two main phases:
- Group-wise Formulation: Instead of a hard requirement to flip a prediction, they use an "invalidity score" that balances the cost of an action (how hard it is to do) with its effectiveness (how likely it is to actually change the model's mind).
- Stochastic Local Search: Finding the perfect tree is computationally "hard" (NP-hard). The authors developed a specialized search algorithm that starts with a random tree and iteratively improves it by adding, deleting, or swapping rules. They also proved a mathematical "Leaf Size Bound" to prevent the tree from becoming too complex and unreadable.
Experimental Setup
The researchers evaluated CET on two popular real-world datasets:
- IBM HR Analytics Employee Attrition: Predicting which employees are likely to leave and suggesting actions (like reducing overtime) to retain them.
- German Credit: Predicting loan defaults and suggesting financial changes to improve creditworthiness.
They tested these against complex "black-box" models like LightGBM and TabNet.
Key Insights
- Leaves as Actions: By placing "actions" in the leaves, the path from the root to the leaf becomes the "reason" for that specific advice.
- Transparency by Design: Because it's a tree, the logic is hierarchical. You can easily say, "For all employees who work overtime and travel frequently, the recommended action is X."
- Guaranteed Consistency: A decision tree partitions the space so that every person falls into exactly one leaf. This eliminates "conflicts" where one person might qualify for two different pieces of advice.
- The Cost of Recourse: Group-level advice is naturally more "expensive" than individualized advice because the action must work for a broader range of people, not just one specific point.
Key Results
The evaluation shows that CET consistently outperforms baseline methods in terms of both effectiveness and interpretability.
- Better Performance: CET achieved lower "invalidity" scores (meaning more effective actions at lower costs) compared to clustering-based baselines.
- Superior to Rule Sets: Compared to AReS (a state-of-the-art rule-based method), CET provided 100% coverage and zero conflicts. AReS failed to provide a rule for up to 51% of instances in some tests.
- Human-Centric Success: In a user study with 35 participants, CET was the clear winner. Users achieved 100% accuracy in understanding the model's suggestions using CET, and they did so faster than with any other method.
Limitations and Future Work
The authors identify a few areas for improvement:
- Scalability: The current algorithm solves a complex optimization problem at every node, which might be slow for massive datasets with millions of rows.
- Feature Interactions: The model currently treats actions as independent perturbations; it doesn't yet account for complex causal relationships.
- Beyond Binary: The current work focuses on binary classification. Expanding this to multi-class problems or regression is a logical next step.
Summary updated