  In this paper we suggest NICE: a new algorithm to generate counterfactual
explanations for heterogeneous tabular data. The design of our algorithm
specifically takes into account algorithmic requirements that often emerge in
real-life deployments: (1) the ability to provide an explanation for all
predictions, (2) being able to handle any classification model (also
non-differentiable ones), and (3) being efficient in run time. More
specifically, our approach exploits information from a nearest unlike neighbour
to speed up the search process, by iteratively introducing feature values from
this neighbour in the instance to be explained. We propose four versions of
NICE, one without optimization and, three which optimize the explanations for
one of the following properties: sparsity, proximity or plausibility. An
extensive empirical comparison on 40 datasets shows that our algorithm
outperforms the current state-of-the-art in terms of these criteria. Our
analyses show a trade-off between on the one hand plausibility and on the other
hand proximity or sparsity, with our different optimization methods offering
users the choice to select the types of counterfactuals that they prefer. An
open-source implementation of NICE can be found at
https://github.com/ADMAntwerp/NICE.
