  Local surrogate models, to approximate the local decision boundary of a
black-box classifier, constitute one approach to generate explanations for the
rationale behind an individual prediction made by the back-box. This paper
highlights the importance of defining the right locality, the neighborhood on
which a local surrogate is trained, in order to approximate accurately the
local black-box decision boundary. Unfortunately, as shown in this paper, this
issue is not only a parameter or sampling distribution challenge and has a
major impact on the relevance and quality of the approximation of the local
black-box decision boundary and thus on the meaning and accuracy of the
generated explanation. To overcome the identified problems, quantified with an
adapted measure and procedure, we propose to generate surrogate-based
explanations for individual predictions based on a sampling centered on
particular place of the decision boundary, relevant for the prediction to be
explained, rather than on the prediction itself as it is classically done. We
evaluate the novel approach compared to state-of-the-art methods and a
straightforward improvement thereof on four UCI datasets.
