  With the rapid growth of machine learning, deep neural networks (DNNs) are
now being used in numerous domains. Unfortunately, DNNs are "black-boxes", and
cannot be interpreted by humans, which is a substantial concern in
safety-critical systems. To mitigate this issue, researchers have begun working
on explainable AI (XAI) methods, which can identify a subset of input features
that are the cause of a DNN's decision for a given input. Most existing
techniques are heuristic, and cannot guarantee the correctness of the
explanation provided. In contrast, recent and exciting attempts have shown that
formal methods can be used to generate provably correct explanations. Although
these methods are sound, the computational complexity of the underlying
verification problem limits their scalability; and the explanations they
produce might sometimes be overly complex. Here, we propose a novel approach to
tackle these limitations. We (1) suggest an efficient, verification-based
method for finding minimal explanations, which constitute a provable
approximation of the global, minimum explanation; (2) show how DNN verification
can assist in calculating lower and upper bounds on the optimal explanation;
(3) propose heuristics that significantly improve the scalability of the
verification process; and (4) suggest the use of bundles, which allows us to
arrive at more succinct and interpretable explanations. Our evaluation shows
that our approach significantly outperforms state-of-the-art techniques, and
produces explanations that are more useful to humans. We thus regard this work
as a step toward leveraging verification technology in producing DNNs that are
more reliable and comprehensible.
