Using MaxSAT for efficient explanations of tree ensembles

Alexey Ignatiev, Yacine Izza, Peter J. Stuckey, Joao Marques-Silva

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

27 Citations (Scopus)


Tree ensembles (TEs) denote a prevalent machine learning model that do not offer guarantees of interpretability, that represent a challenge from the perspective of explainable artificial intelligence. Besides model agnostic approaches, recent work proposed to explain TEs with formally-defined explanations, which are computed with oracles for propositional satisfiability (SAT) and satisfiability modulo theories. The computation of explanations for TEs involves linear constraints to express the prediction. In practice, this deteriorates scalability of the underlying reasoners. Motivated by the inherent propositional nature of TEs, this paper proposes to circumvent the need for linear constraints and instead employ an optimization engine for pure propositional logic to efficiently handle the prediction. Concretely, the paper proposes to use a MaxSAT solver and exploit the objective function to determine a winning class. This is achieved by devising a propositional encoding for computing explanations of TEs. Furthermore, the paper proposes additional heuristics to improve the underlying MaxSAT solving procedure. Experimental results obtained on a wide range of publicly available datasets demonstrate that the proposed MaxSAT-based approach is either on par or outperforms the existing reasoning-based explainers, thus representing a robust and efficient alternative for computing formal explanations for TEs.

Original languageEnglish
Title of host publication36th AAAI Conference on Artificial Intelligence (AAAI-22)
EditorsVasant Honavar, Matthijs Spaan
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages10
ISBN (Electronic)1577358767, 9781577358763
Publication statusPublished - 2022
EventAAAI Conference on Artificial Intelligence 2022 - Online, United States of America
Duration: 22 Feb 20221 Mar 2022
Conference number: 36th (Website) (Proceedings)

Publication series

NameProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


ConferenceAAAI Conference on Artificial Intelligence 2022
Abbreviated titleAAAI 2022
Country/TerritoryUnited States of America
Internet address


  • Constraint Satisfaction And Optimization (CSO)
  • Machine Learning (ML)
  • Philosophy And Ethics Of AI (PEAI)

Cite this