Where Tree Ensembles Decide: Structural Local Explanation with Decision Predicate Graphs
Organizations: Department of Engineering and Architecture, University of Trieste, Via Alfonso Valerio 6/1, 34127 Trieste, Italy · School of Computer Science and Information Technology, University College Cork, Cork, T12 XF62, Ireland
Abstract
Tree ensembles are among the most accurate models for tabular data, yet the computation behind a single prediction is spread over hundreds of decision rules. Feature attributions and counterfactuals explain such predictions through the influence of features or a change of the input, leaving open which of the thresholds applied by the trees a prediction responds to, while structural explanations compress these rules and lose the trees behind them. To address this gap, we propose a local Decision Predicate Graph (local DPG), which gathers the rules executed for a sample into a verifiable record of the computation, with a class support that reproduces every explained prediction. From these rules we select the critical predicate, the executed predicate whose crossing is estimated to move the model most strongly toward a chosen class, which offers the user a concrete threshold and the trees that share it, without an external explainer. Across 16 datasets and four ensemble families, it separates differently predicted neighbours better than random and nearest-threshold predicates. A single crossing recovers the true class in 46-69% of wrong predictions, against 29-50% when the same rule is applied to the feature ranked first by TreeSHAP, a measure close to the selection criterion, and on planted faults it finds the faulty threshold in 46-71% of the resulting errors, against 6-21% at random. Although training-free edits of these predicates did not reduce the error on unseen data, the critical predicate complements attributions and counterfactuals by naming where a prediction can be changed.
Figures & tables
| Question about the prediction | What is returned | Support |
| Where is the prediction contested? | the critical predicate toward the top competitor, , the change and whether crossing it changes the prediction | RQ1, Table 3 |
| Can a wrong prediction be changed to the true class? | the critical predicate toward the true class, , whose crossing recovers it in 46% to 69% of the cases | RQ2, Tables 4 and 5 |
| On which feature, threshold and trees? | the feature , the threshold , the value of the sample, its slack and the set of trees that share the predicate | Section 3.3 , Table 5 |
| Which change of the input would alter it? | a single threshold crossing, which complements the multi-feature change of a counterfactual and is crossed by the counterfactual found by feature tweaking in 31% to 40% of the cases | RQ1, Table 2 |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Meaning | Symbol | Meaning |
| Model and data | Model output | ||
| set of classes | contribution of tree | ||
| ensemble of trees | , | initial score, state of the model | |
| sample with numeric features | link function | ||
| true class of , when known | , | class support, support of | |
| maximum depth of the trees | predicted class | ||
Interpretable ML
Interpretable machine learning develops models and explanations that make predictions, evidence, and decision processes understandable to people.
See all 329 papers