Finding Regions of Counterfactual Explanations via Robust Optimization
- 1 September 2024
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 36 (5) , 1316-1334
Abstract
Counterfactual explanations (CEs) play an important role in detecting bias and improving the explainability of data-driven classification models. A CE is a minimal perturbed data point for which the decision of the model changes. Most of the existing methods can only provide one CE, which may not be achievable for the user. In this work, we derive an iterative method to calculate robust CEs (i.e., CEs that remain valid even after the features are slightly perturbed). To this end, our method provides a whole region of CEs, allowing the user to choose a suitable recourse to obtain a desired outcome. We use algorithmic ideas from robust optimization and prove convergence results for the most common machine learning methods, including decision trees, tree ensembles, and neural networks. Our experiments show that our method can efficiently generate globally optimal robust CEs for a variety of common data sets and classification models. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was supported by the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant OCENW.GROOT.2019.015, Optimization for and with Machine Learning (OPTIMAL)]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0153 .Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Generating collective counterfactual explanations in score-based classification via mathematical optimizationExpert Systems with Applications, 2023
- On the robustness of sparse counterfactual explanations to adverse perturbationsArtificial Intelligence, 2022
- The Robustness of Counterfactual Explanations Over TimeIEEE Access, 2022
- Multi-Objective Counterfactual Explanations2020
- Strong mixed-integer programming formulations for trained neural networksMathematical Programming, 2020
- ReLU networks as surrogate models in mixed-integer linear programsComputers & Chemical Engineering, 2019
- Deep neural networks and mixed integer linear optimizationConstraints, 2018
- Reformulation versus cutting-planes for robust optimizationComputational Management Science, 2015
- Cutting-set methods for robust convex optimization with pessimizing oraclesOptimization Methods and Software, 2009
- Computing robust basestock levelsDiscrete Optimization, 2008