TL;DR
This paper introduces a novel approach to enhance Random Forests (RFs) by integrating Logical Analysis of Data (LAD). By using minimal support sets (MSSes) from LAD to guide feature selection in decision trees, the authors achieve comparable accuracy with fewer features, leading to more concise explanations.
What Problem Does This Paper Address?
Random Forests (RFs) are powerful machine learning classifiers, but a significant drawback is their reliance on a large number of features during the construction of individual decision trees. This complexity makes it challenging to extract clear and concise explanations for the model's predictions, which is increasingly important for applications in safety-critical systems and for building user trust. While existing methods for generating explanations (like Abductive and Contrastive eXplanations) have improved, the size of these explanations can still be too large for human comprehension, especially when dealing with datasets with many features. The paper aims to address this by reducing the number of features used in RFs, thereby simplifying the resulting explanations.
Methods
The core innovation lies in integrating Logical Analysis of Data (LAD) into the Random Forest framework. LAD is a logic-based methodology that focuses on identifying "minimal support sets" (MSSes). These MSSes are minimal subsets of features that can effectively distinguish between different classes of data.
The proposed approach, termed RF-LAD, modifies the standard Random Forest algorithm in the following ways:
- MSS Generation: Instead of randomly selecting feature subsets for each decision tree, RF-LAD first generates a set of MSSes from the entire training dataset using LAD techniques. This involves formulating the problem as finding minimal hitting sets.
- Feature Selection for Trees: For each decision tree in the forest, a bootstrap sample of the training data is created. Then, instead of randomly selecting a subset of features, RF-LAD randomly selects an MSS from the pre-generated set to be used for building that specific tree.
This shift from random feature subset selection to MSS-guided feature selection is expected to focus the trees on more discriminative features, potentially leading to more compact models and explanations.
Datasets
The experiments were conducted on 23 benchmark datasets. These datasets are standard benchmarks sourced from repositories like CP4IM, Kaggle, OpenML, and UCI. Some datasets were originally binary, while others were numerical datasets that were binarized using thresholds derived from CART. For consistency, instances appearing in both positive and negative classes were removed. The evaluation employed a repeated stratified 10-fold cross-validation with 3 repetitions.
Key Insights and Ideas
- MSSes as Discriminative Feature Subsets: The fundamental insight is that MSSes, derived from LAD, represent the most concise sets of features that can separate data classes. Leveraging these directly in RFs can inherently reduce feature redundancy.
- Feature Reduction for Explanations: By forcing decision trees to use MSSes, the overall number of features used by the RF is reduced. This reduction is directly linked to the potential for generating shorter and more understandable explanations.
- Balancing Performance and Explainability: The paper demonstrates that it's possible to achieve comparable predictive accuracy to standard RFs while significantly improving the conciseness of explanations. This suggests a trade-off that can be managed effectively.
- Computational Feasibility: While generating all MSSes can be computationally expensive, the paper proposes generating a subset of MSSes and using efficient algorithms (like "pMMCS") for their enumeration, making the approach practical.
Key Results
- Accuracy: RF-LAD achieved comparable accuracy to the standard scikit-learn RF implementation, with differences typically within 1-2%. In some cases, RF-LAD even showed slightly higher accuracy.
- Feature Usage: RF-LAD significantly reduced the average number of features used in the forests. For instance, RF-LAD (soft-vote) used 3.92% to 78.83% fewer features than RF-sklearn, with reductions exceeding 50% for datasets with many features.
- Explanation Size: The average size of Abductive eXplanations (AXps) and Contrastive eXplanations (CXps) was substantially reduced by RF-LAD. AXps were reduced by 17.72% to 90.28% (majority-vote) and 18.96% to 87.86% (soft-vote), while CXps were reduced by 17.44% to 96.53% and 3.23% to 94.14%, respectively. For many datasets, these reductions exceeded 50%.
- Forest Size: RF-LAD was able to produce smaller forests in terms of the number of nodes on several benchmarks.
- Runtime: The runtime for RF-LAD includes MSS generation, which adds overhead, but the paper notes that RF-sklearn is very fast.
Limitations and Future Work
- Numerical Data: The current approach relies on binarizing numerical datasets. A future direction is to extend LAD to directly handle numerical data without this preprocessing step.
- MSS Enumeration Complexity: While a subset of MSSes is generated, the potential for an exponential number of MSSes in the worst case remains a challenge. The paper uses a heuristic to select the most effective MSSes.
- Generalization to Other Algorithms: The paper focuses on Random Forests. Future work could explore integrating LAD into other tree-based algorithms to see if similar benefits in terms of explanation conciseness can be achieved.
- Perfect Decision Trees: While Proposition 1 suggests that RF-LAD can lead to perfect decision trees for frequent examples, the paper notes that this guarantee might require modifications to the tree-building algorithm (e.g., removing depth restrictions).
Summary updated