Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization


  • Kentaro Kanamori Hokkaido University
  • Takuya Takagi Fujitsu Laboratories Ltd.
  • Ken Kobayashi Fujitsu Laboratories Ltd. Tokyo Institute of Technology
  • Yuichi Ike Fujitsu Laboratories Ltd.
  • Kento Uemura Fujitsu Laboratories Ltd.
  • Hiroki Arimura Hokkaido University




Accountability, Interpretability & Explainability, Mixed Discrete/Continuous Optimization, Classification and Regression


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.




How to Cite

Kanamori, K., Takagi, T., Kobayashi, K., Ike, Y., Uemura, K., & Arimura, H. (2021). Ordered Counterfactual Explanation by Mixed-Integer Linear Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11564-11574. https://doi.org/10.1609/aaai.v35i13.17376



AAAI Technical Track on Philosophy and Ethics of AI