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.
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:
- 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.
- 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,
minMAJmethods 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
minMAJallows 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.
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