Trading Complexity for Sparsity in Random Forest Explanations

Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche, Jean-Marie Lagniez, Pierre MarquisAAAI 2022 · DOI

Introduction

Random Forests (RFs) are widely used in machine learning due to their robustness and predictive accuracy. However, their ensemble nature makes them notoriously difficult to interpret. Unlike a single decision tree, where a prediction can be explained by a single path from root to leaf, an RF prediction is the result of a majority vote across hundreds or thousands of trees.

In the field of eXplainable AI (XAI), researchers seek abductive explanations (also known as "sufficient reasons"). These are minimal sets of input features that, if held constant, guarantee the model will maintain its prediction regardless of the values of other variables. The gold standard for such explanations has been the Prime-Implicant (PI) explanation. Unfortunately, finding PI explanations for RFs is computationally intensive (DP-complete), and finding the absolute smallest one is even harder ($Σ_2^p$-complete). In practice, this complexity often leads to a trade-off: either explanations are too long for human consumption, or the computational time required to find short ones is prohibitive.

Proposed Methodology: Majoritary Reasons

To address this complexity-sparsity trade-off, this paper introduces the concept of Majoritary Reasons.

Example of a Random Forest ensemble consisting of three decision trees.

Instead of requiring a set of features to force the entire forest to agree, a majoritary reason only requires that a strict majority of individual trees agree on the prediction. This relaxation significantly lowers the computational hurdle:

  1. Greedy Generation: A single majoritary reason can be found in polynomial time using a simple greedy algorithm that iteratively removes features while checking if a majority of trees still support the prediction.
  2. Optimization (minMAJ): To find the shortest possible majoritary reason (minMAJ), the authors frame the task as a Partial MaxSAT problem. This allows the use of modern constraint solvers to find sparse, human-readable explanations efficiently.

The key insight is that while a majoritary reason might technically contain features that are redundant relative to the global forest logic, it is much easier to compute than a PI explanation and often results in smaller explanations in practice due to the efficiency of MaxSAT solvers compared to PI-finding algorithms.

Experimental Evaluation

The approach was evaluated on 15 binary classification datasets, ranging from low-dimensional sets like compas to high-dimensional ones like dorothea (100,000 features).

Key Results

  • The Computational Sweet Spot: The researchers identified a clear advantage for majoritary reasons in terms of the time-sparsity trade-off. As shown in the performance analysis, minMAJ methods occupy a middle ground between the fast but bloated "Direct Reasons" and the slow, often-timing-out "Sufficient Reasons" (PI).
  • Superior Sparsity: In high-dimensional datasets like gisette, "Direct Reasons" (the union of paths from the majority trees) often involved over 500 features. Majoritary reasons reduced this to approximately 25–30 features, making them far more interpretable.
  • Anytime Performance: Using a MaxSAT solver for minMAJ allows for "anytime" explanations. Even with a strict 10-second timeout, the solver typically provides an explanation significantly smaller than those produced by standard PI solvers.
Comparison of explanation size versus computation time across different methods.

Discussion and Future Work

While majoritary reasons provide a powerful new tool for RF interpretability, some limitations remain. The current framework is optimized for Boolean random forests (binary classification with binarized features). Extending this logic to multi-class classification or regression is a primary area for future research. Additionally, while majoritary reasons are not guaranteed to be prime implicants of the entire forest, empirical results suggest they are highly effective for practical interpretability, offering a scalable path toward explaining complex ensemble models.

Summary updated

BibTeX
@inproceedings{audemard2022trading,
  author = {Gilles Audemard and Steve Bellart and Louenas Bounia and Frédéric Koriche and Jean-Marie Lagniez and Pierre Marquis},
  title = {{Trading Complexity for Sparsity in Random Forest Explanations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20484},
}
Figure