The ability to explain why a machine learning model arrives at a particular
prediction is crucial when used as decision support by human operators of
critical systems. The provided explanations must be provably correct, and
preferably without redundant information, called minimal explanations. In this
paper, we aim at finding explanations for predictions made by tree ensembles
that are not only minimal, but also minimum with respect to a cost function.
To this end, we first present a highly efficient oracle that can determine
the correctness of explanations, surpassing the runtime performance of current
state-of-the-art alternatives by several orders of magnitude when computing
minimal explanations.
Secondly, we adapt an algorithm called MARCO from related works (calling it
m-MARCO) for the purpose of computing a single minimum explanation per
prediction, and demonstrate an overall speedup factor of two compared to the
MARCO algorithm which enumerates all minimal explanations.
Finally, we study the obtained explanations from a range of use cases,
leading to further insights of their characteristics. In particular, we observe
that in several cases, there are more than 100,000 minimal explanations to
choose from for a single prediction. In these cases, we see that only a small
portion of the minimal explanations are also minimum, and that the minimum
explanations are significantly less verbose, hence motivating the aim of this
work.

本文旨在通过一种高效的 Oracle 和 MARCO 算法改进，提供一个最小的、满足成本函数的解释，以解释机器学习模型的预测，并对这些解释进行了研究和分析，以进一步了解它们的特点。