Decision Predicate Graphs: Enhancing Interpretability in Tree Ensembles

The paper addresses the black-box problem inherent in tree-based ensemble models, noting that the training outcome yields an exceptionally complex model... whose internal workings are not transparent or easily interpretable. To mitigate the challenges of human-in-the-loop interpretation, the authors introduce the Decision Predicate Graph (DPG) as a model-agnostic tool to provide a global interpretation of the model.

DPG is a graph structure that captures the tree-based ensemble model and learned dataset details, preserving the relations among features, logical decisions, and predictions towards emphasising insightful points. Specifically, "in this graph, nodes represent predicates, i.e., the feature-value associations present in each node of every tree, while edges denote the frequency with which these predicates are satisfied during the model training phase by the samples of the dataset. Formally, A Decision Predicate Graph (DPG(Mn)) for a model Mn is a directed weighted graph (P, E) where: P is the set of nodes, which corresponds to the predicate set P(Mn); E is the set of edges, where each edge represents the frequency with which a sample consecutively satisfies two predicates in a given base learner."

The construction of the DPG is achieved through an algorithm that iterates over each base learner in the ensemble tree model Mn and each training sample x in the training set D. The overall asymptotic complexity can be formally expressed as follows: O(b times s times (k + k 2)) = O(b times s times k 2), where b is the number of learners, s is the number of samples, and k is the size of the predicate path.

To enhance model comprehension beyond simple visualization, the paper introduces several metrics and properties:

• Constraints: These are an aggregation of predicates... which represent intervals associated with the features of each class. They allow for the calculation of the classification boundary of each feature associated with each class.

• Betweenness Centrality (BC): This metric identifies potential bottleneck nodes because they play a crucial role in facilitating interactions between different parts of the DPG. High BC nodes are considered meaningful to understanding the tree-based ensemble models as their decisions are essential to classify the elements of the dataset.

• Local Reaching Centrality (LRC): This metric gauges the extent to which decisions contained in these nodes are employed by diverse tree base learners for classifying samples in the training set, thereby offering a comprehensive perspective on the concept of feature importance (FI) by extending its definition to encompass the values associated with features across various decisions.

• Community: By using an asynchronous label propagation algorithm, the DPG can identify groups of nodes that similarly contribute to the classification of samples. This helps in identifying predominant features and those that play a marginal role in the classification process.

Empirical results demonstrate the effectiveness of DPG through two case studies. On the Iris dataset, the DPG revealed that the decision associated with petal length (cm) and the value 4.85 is pivotal. In a more challenging dataset involving a synthetic multiclass problem with 100 tree learners, DPG overcomes this obstacle [visual complexity] by providing metrics that can still offer valid insights into the model, such as providing constraints for the four classes and identifying crucial predicates via LRC.

The paper compares DPG to existing graph-based solutions like the Algebraic Decision Diagram (ADD). It notes that in ADD, the evaluation of connections between nodes and the assessment of the significance of decisions made by different tree base learners are not fully exploited, and visualisation becomes intricate, even with a modest count of 20 tree base learners. In contrast, DPG allows the computation of both global and local metrics, even with a higher number of tree base learners.

1. Automated Ensemble Pruning and Compression

• Improvement: Integrate Local Reaching Centrality (LRC) and Betweenness Centrality (BC) into the model training/optimization loop to identify and remove redundant base learners.

• What the improved system can do: The system can automatically prune trees or decision paths that exhibit low LRC (indicating they don't contribute significantly to diverse classification decisions) or low BC (indicating they aren't critical bottlenecks). This results in smaller, faster, and more computationally efficient ensemble models (e.g., XGBoost or Random Forest) that maintain high accuracy with significantly lower latency.

2. Structural Explainability Engine (XAI)

• Improvement: Replace generic feature importance scores with a DPG-based explanation layer that utilizes Community detection and Constraints.

• What the improved system can do: Instead of providing a simple list of important features, the system can provide semantic explanations such as: This prediction was driven by a cluster of related features (Community) acting within these specific value intervals (Constraints), or This specific decision point is a critical bottleneck (High BC) that shifts the classification from Class A to Class B. This allows human operators to understand the logic of the decision, not just the variables involved.

3. Boundary-Aware Adversarial Robustness Training

• Improvement: Use the Constraints metric to map the precise multidimensional decision boundaries of each class within the DPG.

• What the improved system can do: The system can automatically identify the weakest feature-value intervals where classification boundaries are most narrow or sensitive. It can then prioritize these specific regions for adversarial training (e.g., generating synthetic adversarial examples targeting those specific predicate intervals), creating a model that is specifically hardened against edge-case attacks and distribution shifts.

4. Semantic Feature Selection and Dimensionality Reduction

• Improvement: Apply the DPG Community detection algorithm to the training phase to categorize features into predominant and marginal groups.

• What the improved system can do: The system can automatically perform feature selection by discarding features that belong to marginal communities (nodes that contribute little to the overall graph connectivity or classification consensus). This reduces the input dimensionality, prevents overfitting, and simplifies the model's dependency on noise.

5. Decision-Path Uncertainty Quantification

• Improvement: Implement an uncertainty scoring mechanism based on the edge weights and node centrality within the DPG during inference.

• What the improved system can do: When a new sample is processed, the system can calculate a confidence score based on how frequently the traversed predicates and edges appear in the DPG. If a sample follows a path through nodes with low LRC or low-weight edges, the system can flag the prediction as low confidence/out-of-distribution, alerting a human-in-the-loop that the model is making a decision in a region of the predicate space it has not mastered.

Understanding the decisions of tree-based ensembles and their relationships is pivotal for machine learning model interpretation. Recent attempts to mitigate the human-in-the-loop interpretation challenge have explored the extraction of the decision structure underlying the model taking advantage of graph simplification and path emphasis. However, while these efforts enhance the visualisation experience, they may either result in a visually complex representation or compromise the interpretability of the original ensemble model. In addressing this challenge, especially in complex scenarios, we introduce the Decision Predicate Graph (DPG) as a model-agnostic tool to provide a global interpretation of the model. DPG is a graph structure that captures the tree-based ensemble model and learned dataset details, preserving the relations among features, logical decisions, and predictions towards emphasising insightful points. Leveraging well-known graph theory concepts, such as the notions of centrality and community, DPG offers additional quantitative insights into the model, complementing visualisation techniques, expanding the problem space descriptions, and offering diverse possibilities for extensions. Empirical experiments demonstrate the potential of DPG in addressing traditional benchmarks and complex classification scenarios.