  We present a model-agnostic algorithm for generating post-hoc explanations
and uncertainty intervals for a machine learning model when only a static
sample of inputs and outputs from the model is available, rather than direct
access to the model itself. This situation may arise when model evaluations are
expensive; when privacy, security and bandwidth constraints are imposed; or
when there is a need for real-time, on-device explanations. Our algorithm uses
a bootstrapping approach to quantify the uncertainty that inevitably arises
when generating explanations from a finite sample of model queries. Through a
simulation study, we show that the uncertainty intervals generated by our
algorithm exhibit a favorable trade-off between interval width and coverage
probability compared to the naive confidence intervals from classical
regression analysis as well as current Bayesian approaches for quantifying
explanation uncertainty. We further demonstrate the capabilities of our method
by applying it to black-box models, including a deep neural network, trained on
three real-world datasets.
