One-for-many Counterfactual Explanations by Column Generation
Andrea Lodi Jasone Ramírez-Ayerbe
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.