Efficient Search for Diverse Coherent Explanations

TLDR

Complex data involve variables that can take any value from a contiguous range or a discrete set of states. The study proposes new search algorithms for counterfactual explanations using mixed integer programming and introduces mixed polytope constraints to generate diverse, coherent explanations. These algorithms employ mixed integer programming with mixed polytope constraints to efficiently find coherent counterfactual explanations and produce diverse solutions. The resulting solutions are guaranteed to map back onto the underlying data structure, eliminating the need for brute‑force enumeration.

Abstract

This paper proposes new search algorithms for counterfactual explanations based upon mixed integer programming. We are concerned with complex data in which variables may take any value from a contiguous range or an additional set of discrete states. We propose a novel set of constraints that we refer to as a "mixed polytope" and show how this can be used with an integer programming solver to efficiently find coherent counterfactual explanations i.e. solutions that are guaranteed to map back onto the underlying data structure, while avoiding the need for brute-force enumeration. We also look at the problem of diverse explanations and show how these can be generated within our framework.