  As black box explanations are increasingly being employed to establish model
credibility in high-stakes settings, it is important to ensure that these
explanations are accurate and reliable. However, prior work demonstrates that
explanations generated by state-of-the-art techniques are inconsistent,
unstable, and provide very little insight into their correctness and
reliability. In addition, these methods are also computationally inefficient,
and require significant hyper-parameter tuning. In this paper, we address the
aforementioned challenges by developing a novel Bayesian framework for
generating local explanations along with their associated uncertainty. We
instantiate this framework to obtain Bayesian versions of LIME and KernelSHAP
which output credible intervals for the feature importances, capturing the
associated uncertainty. The resulting explanations not only enable us to make
concrete inferences about their quality (e.g., there is a 95% chance that the
feature importance lies within the given range), but are also highly consistent
and stable. We carry out a detailed theoretical analysis that leverages the
aforementioned uncertainty to estimate how many perturbations to sample, and
how to sample for faster convergence. This work makes the first attempt at
addressing several critical issues with popular explanation methods in one
shot, thereby generating consistent, stable, and reliable explanations with
guarantees in a computationally efficient manner. Experimental evaluation with
multiple real world datasets and user studies demonstrate that the efficacy of
the proposed framework.
