# Trading Complexity for Sparsity in Random Forest Explanations arXiv: https://arxiv.org/abs/2108.05276 ยท HTML: https://mlsanity.com/paper/2108.05276/ ## Key facts - Cited by 32 papers in the map (data through 14 Oct 2026). - Builds on 12 of its 39 references that are in the map. - First posted on arXiv 11 Aug 2021. ## Builds on (most cited first, 12 of 12) - ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016) - [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017) - [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018) - [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018) - [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020) - [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020) - [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021) - [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020) - [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021) - [Interpretable Random Forests via Rule Extraction](https://mlsanity.com/paper/2004.14841/) (2020) - [On Symbolically Encoding the Behavior of Random Forests](https://mlsanity.com/paper/2007.01493/) (2020) - [Once Upon a Crime: Towards Crime Prediction from Demographics and Mobile Data](https://mlsanity.com/paper/1409.2983/) (2014) ## Built on by (most cited first, 30 of 32) - [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022) - [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022) - [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023) - [Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation](https://mlsanity.com/paper/2405.08297/) (2024) - [SpArX: Sparse Argumentative Explanations for Neural Networks [Technical Report]](https://mlsanity.com/paper/2301.09559/) (2023) - [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025) - [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025) - [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026) - [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025) - [Abductive explanations of classifiers under constraints: Complexity and properties](https://mlsanity.com/paper/2409.12154/) (2024) - [Self-Explaining Neural Networks for Business Process Monitoring](https://mlsanity.com/paper/2503.18067/) (2025) - [Axiomatic Characterisations of Sample-based Explainers](https://mlsanity.com/paper/2408.04903/) (2024) - [On the Complexity of Global Necessary Reasons to Explain Classification](https://mlsanity.com/paper/2501.06766/) (2025) - [FAME: Formal Abstract Minimal Explanation for Neural Networks](https://mlsanity.com/paper/2603.10661/) (2026) - [Logic-Based Explainability: Past, Present & Future](https://mlsanity.com/paper/2406.11873/) (2024) - [Understanding XAI Through the Philosopher's Lens: A Historical Perspective](https://mlsanity.com/paper/2407.18782/) (2024) - [Learning Model Agnostic Explanations via Constraint Programming](https://mlsanity.com/paper/2411.08478/) (2024) - [Robust Explanations Through Uncertainty Decomposition: A Path to Trustworthier AI](https://mlsanity.com/paper/2507.12913/) (2025) - [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026) - [Finding Minimum-Cost Explanations for Predictions made by Tree Ensembles](https://mlsanity.com/paper/2303.09271/) (2023) - [Uncovering Bugs in Formal Explainers: A Case Study with PyXAI](https://mlsanity.com/paper/2511.03169/) (2025) - [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026) - [Rectifying Mono-Label Boolean Classifiers](https://mlsanity.com/paper/2206.08758/) (2022) - [On the Trade-off between the Number of Nodes and the Number of Trees in a Random Forest](https://mlsanity.com/paper/2312.11540/) (2023) - [Efficient & Correct Predictive Equivalence for Decision Trees](https://mlsanity.com/paper/2509.17774/) (2025) - [A Rectification-Based Approach for Distilling Boosted Trees into Decision Trees](https://mlsanity.com/paper/2510.18615/) (2025) - [Leveraging Association Rules for Better Predictions and Better Explanations](https://mlsanity.com/paper/2510.18628/) (2025) - [Formally Explaining Decision Tree Models with Answer Set Programming](https://mlsanity.com/paper/2601.03845/) (2026) - [Aligned explanations in neural networks](https://mlsanity.com/paper/2601.04378/) (2026) - [Rigorous Explanations for Tree Ensembles](https://mlsanity.com/paper/2603.29361/) (2026) ## Abstract (arXiv) Random forests have long been considered as powerful model ensembles in machine learning. By training multiple decision trees, whose diversity is fostered through data and feature subsampling, the resulting random forest can lead to more stable and reliable predictions than a single decision tree. This however comes at the cost of decreased interpretability: while decision trees are often easily interpretable, the predictions made by random forests are much more difficult to understand, as they involve a majority vote over hundreds of decision trees. In this paper, we examine different types of reasons that explain "why" an input instance is classified as positive or negative by a Boolean random forest. Notably, as an alternative to sufficient reasons taking the form of prime implicants of the random forest, we introduce majoritary reasons which are prime implicants of a strict majority of decision trees. For these different abductive explanations, the tractability of the generation problem (finding one reason) and the minimization problem (finding one shortest reason) are investigated. Experiments conducted on various datasets reveal the existence of a trade-off between runtime complexity and sparsity. Sufficient reasons - for which the identification problem is DP-complete - are slightly larger than majoritary reasons that can be generated using a simple linear- time greedy algorithm, and significantly larger than minimal majoritary reasons that can be approached using an anytime P ARTIAL M AX SAT algorithm.