One-for-many Counterfactual Explanations by Column Generation
This work addresses the need for efficient and sparse counterfactual explanations for groups in machine learning, though it appears incremental as it builds on existing explanation methods with a novel optimization approach.
The paper tackles the problem of generating a set of counterfactual explanations for multiple instances with a one-for-many allocation rule, minimizing the number of explanations while limiting feature changes, and develops a column generation framework that outperforms existing methods in scalability, computational performance, and solution quality.
In this paper, we consider the problem of generating a set of counterfactual explanations for a group of instances, with the one-for-many allocation rule, where one explanation is allocated to a subgroup of the instances. For the first time, we solve the problem of minimizing the number of explanations needed to explain all the instances, while considering sparsity by limiting the number of features allowed to be changed collectively in each explanation. A novel column generation framework is developed to efficiently search for the explanations. Our framework can be applied to any black-box classifier, like neural networks. Compared with a simple adaptation of a mixed-integer programming formulation from the literature, the column generation framework dominates in terms of scalability, computational performance and quality of the solutions.