One-for-Many Counterfactual Explanations by Column Generation

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 counterfactual explanation is allocated to a subgroup of the instances. For the first time, we solve the problem of minimizing the number of counterfactual 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 counterfactual explanations. Our framework can be applied to any black box classifier that allows a mixed-integer program (MIP) representation, like neural networks with rectified linear unit (ReLU) activation. Compared with a simple adaptation of a MIP formulation from the literature, the column generation framework dominates in terms of scalability, computational performance and quality of the solutions. Funding: This research has been financed in part by Ministerio de Ciencia, Innovación y Universidades, Spain research projects [PID2019-110886RB-I00 and PID2022-137818OB-I00]. This support is gratefully acknowledged.