  Counterfactual explanations can be obtained by identifying the smallest
change made to a feature vector to qualitatively influence a prediction; for
example, from 'loan rejected' to 'awarded' or from 'high risk of cardiovascular
disease' to 'low risk'. Previous approaches often emphasized that
counterfactuals should be easily interpretable to humans, motivating sparse
solutions with few changes to the feature vectors. However, these approaches
would not ensure that the produced counterfactuals be proximate (i.e., not
local outliers) and connected to regions with substantial data density (i.e.,
close to correctly classified observations), two requirements known as
counterfactual faithfulness. These requirements are fundamental when making
suggestions to individuals that are indeed attainable. Our contribution is
twofold. On one hand, we suggest to complement the catalogue of counterfactual
quality measures [1] using a criterion to quantify the degree of difficulty for
a certain counterfactual suggestion. On the other hand, drawing ideas from the
manifold learning literature, we develop a framework that generates attainable
counterfactuals. We suggest the counterfactual conditional heterogeneous
variational autoencoder (C-CHVAE) to identify attainable counterfactuals that
lie within regions of high data density.
