  Counterfactual examples are one of the most commonly-cited methods for
explaining the predictions of machine learning models in key areas such as
finance and medical diagnosis. Counterfactuals are often discussed under the
assumption that the model on which they will be used is static, but in
deployment models may be periodically retrained or fine-tuned. This paper
studies the consistency of model prediction on counterfactual examples in deep
networks under small changes to initial training conditions, such as weight
initialization and leave-one-out variations in data, as often occurs during
model deployment. We demonstrate experimentally that counterfactual examples
for deep models are often inconsistent across such small changes, and that
increasing the cost of the counterfactual, a stability-enhancing mitigation
suggested by prior work in the context of simpler models, is not a reliable
heuristic in deep networks. Rather, our analysis shows that a model's local
Lipschitz continuity around the counterfactual is key to its consistency across
related models. To this end, we propose Stable Neighbor Search as a way to
generate more consistent counterfactual explanations, and illustrate the
effectiveness of this approach on several benchmark datasets.
