EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Finding Minimum‐Cost Explanations for Predictions Made by Tree Ensembles

John Törnblom, Emil Karlsson, Simin Nadjm‐Tehrani

Software: Practice and Experience · 2026-06 · 56 (6) · 615-642

DOI: 10.1002/spe.70061 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Software: Practice and Experience, online erschienen am 12.03.2026. Verfasst von John Törnblom und 2 weiteren Autor:innen. Die Arbeit nennt 55 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Knut och Alice Wallenbergs Stiftelse.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The ability to reliably 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. Secondly, we adapt an algorithm called MARCO from the optimization field (calling the adaptation m‐MARCO) to compute a single minimum explanation per prediction, and demonstrate an overall speedup factor of 2.7 compared to a state‐of‐the‐art algorithm based on minimum hitting sets (MHS), and a speedup factor of 27 compared to the standard MARCO algorithm which enumerates all minimal explanations. Finally, we study the obtained explanations from a range of use cases, leading to further insights into their characteristics. In particular, we observe that in several cases, there are more than 500,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.

Förderung

  • Knut och Alice Wallenbergs Stiftelse

Zitieren

APA

Törnblom, J., Karlsson, E., & Nadjm‐Tehrani, S. (2026). Finding Minimum‐Cost Explanations for Predictions Made by Tree Ensembles. Software: Practice and Experience, 56(6), 615-642. https://doi.org/10.1002/spe.70061

Vancouver

Törnblom J, Karlsson E, Nadjm‐Tehrani S. Finding Minimum‐Cost Explanations for Predictions Made by Tree Ensembles. Software: Practice and Experience. 2026;56(6):615-642. doi:10.1002/spe.70061

BibTeX
@article{Trnblom2026,
  author = {Törnblom, John and Karlsson, Emil and Nadjm‐Tehrani, Simin},
  title = {Finding Minimum‐Cost Explanations for Predictions Made by Tree Ensembles},
  journal = {Software: Practice and Experience},
  year = {2026},
  volume = {56},
  number = {6},
  pages = {615--642},
  doi = {10.1002/spe.70061}
}
Kostenlos starten →