  Feature attribution methods are popular for explaining neural network
predictions, and they are often evaluated on metrics such as comprehensiveness
and sufficiency. In this paper, we highlight an intriguing property of these
metrics: their solvability. Concretely, we can define the problem of optimizing
an explanation for a metric, which can be solved by beam search. This
observation leads to the obvious yet unaddressed question: why do we use
explainers (e.g., LIME) not based on solving the target metric, if the metric
value represents explanation quality? We present a series of investigations
showing strong performance of this beam search explainer and discuss its
broader implication: a definition-evaluation duality of interpretability
concepts. We implement the explainer and release the Python solvex package for
models of text, image and tabular domains.
