---
title: "On Explaining Random Forests with SAT"
authors:
  - "Yacine Izza"
  - "Joao Marques-Silva"
doi: "10.24963/ijcai.2021/356"
url: "https://ijcai.org/proceedings/2021/356"
pdf: "https://ijcai.org/proceedings/2021/0356.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "2584-2591"
track: "Main Track"
keywords:
  - "Constraints and SAT: Constraints and Data Mining; Constraints and Machine Learning"
  - "Constraints and SAT: SAT: Solvers and Applications"
  - "Machine Learning: Explainable/Interpretable Machine Learning"
---

# On Explaining Random Forests with SAT

Yacine Izza, Joao Marques-Silva

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 2584-2591. DOI: [10.24963/ijcai.2021/356](https://doi.org/10.24963/ijcai.2021/356)

## Abstract

Random Forest (RFs) are among the most widely used Machine Learning  (ML) classifiers. Even though RFs are not interpretable, there are no dedicated  non-heuristic approaches for computing explanations of RFs. Moreover, there is recent work on polynomial algorithms for explaining ML models, including naive Bayes classifiers. Hence, one question is whether finding explanations of RFs  can be solved in polynomial time. This paper answers this question negatively, by proving that computing one PI-explanation of an RF is D^P-hard. Furthermore, the paper proposes a propositional encoding for  computing explanations of RFs, thus enabling finding PI-explanations   with a SAT solver. This contrasts with earlier work on explaining boosted trees  (BTs) and neural networks (NNs), which requires encodings based on  SMT/MILP. Experimental results, obtained on a wide range of publicly available  datasets, demonstrate that the proposed SAT-based approach scales to  RFs of sizes common in practical applications. Perhaps more  importantly, the experimental results demonstrate that, for the vast  majority of examples considered, the SAT-based approach proposed in  this paper significantly outperforms existing heuristic approaches.