Generating Likely Counterfactuals Using Sum-Product Networks
Jiri Nemecek Tomas Pevny Jakub Marecek
Due to user demand and recent regulation (GDPR, AI Act), decisions made by AI
systems need to be explained. These decisions are often explainable only post
hoc, where counterfactual explanations are popular. The question of what
constitutes the best counterfactual explanation must consider multiple aspects,
where "distance from the sample" is the most common. We argue that this
requirement frequently leads to explanations that are unlikely and, therefore,
of limited value. Here, we present a system that provides high-likelihood
explanations. We show that the search for the most likely explanations
satisfying many common desiderata for counterfactual explanations can be
modeled using mixed-integer optimization (MIO). In the process, we propose an
MIO formulation of a Sum-Product Network (SPN) and use the SPN to estimate the
likelihood of a counterfactual, which can be of independent interest. A
numerical comparison against several methods for generating counterfactual
explanations is provided.