Explaining Cross-Label Decision Structure in Multi-Output Tree Ensembles
Organizations: University of Trieste, Trieste, Italy · Institute of Mathematics and Computer Sciences, University of São Paulo, São Carlos, Brazil · SENAI, Londrina, Brazil
Abstract
A multi-output tree ensemble predicts several binary labels through decision paths that it largely shares across those labels, yet the attribution methods commonly used to explain such models treat each output in isolation. We propose multi-sink Decision Predicate Graphs (ms-DPGs), which extend decision predicate graphs with one sink per label: each leaf contributes to the sink of every label its in-bag positive count for that label. On this representation we define Shared Predicate Flow (SPF), the share of a label's decision mass that passes through conditions active for both labels of a pair, and a contracted view of the graph in which label-specific lifts indicate whether a shared condition raises the probability of both labels or of one at the expense of the other. Controlled experiments show that SPF captures shared decision conditions rather than mere feature overlap. On nine multi-label benchmarks, native multi-output forests share substantially more decision structure than Binary Relevance on eight, including five of the six on which the two are at predictive parity, even at equal hyperparameters, whereas per-label TreeSHAP rankings register the change of architecture without showing whether more is shared. Because a native forest routes every label through the same splits, SPF describes the fitted model rather than the data, and on eight of the nine benchmarks it rises when the feature-label signal is removed; a high SPF is therefore not evidence of shared predictive information. ms-DPG offers a global, predicate-level account of how a multi-output ensemble reuses decision conditions across its labels.
Figures & tables
| Method | Explanatory unit | Outputs | Cross-output |
|---|---|---|---|
| MDI [ 5 ] | feature | one at a time | – |
| TreeSHAP [ 17 ] | feature | one at a time | – |
| RuleFit [ 13 ] | rule | single | – |
| Petković et al. [ 24 ] | feature | multi-target | – |
| DPG [ 2 ] | directional predicate | single | – |
| IOP-Score [ 7 ] | directional predicate | inlier/outlier | – |
| Component | Question it answers |
|---|---|
| SPF matrix | Which label pairs does the forest decide through common conditions? |
| Predicate node | Which conditions carry decision mass toward both labels? |
| Lift | Is the predicted rate of on the traces through the condition above ( ) or below ( ) its forest-wide rate? |
| Lifts of a pair | Are these traces enriched in both labels (co-enriching) or in one and depleted in the other (separating)? |
| Transition arc | In which order do the trees test the conditions? |
| Class node | Which labelset for the pair do the leaves reached through these conditions store? |
| Dataset | Domain | Card. | |||
|---|---|---|---|---|---|
| emotions | Music | 593 | 72 | 6 | 1.87 |
| scene | Images | 2407 | 294 | 6 | 1.07 |
| yeast | Gene function | 2417 | 103 | 8 (14) | 3.55 |
| image | Images | 2000 | 135 | 5 | 1.24 |
| birds | Audio | 645 | 259 | 8 (19) | 0.73 |
| genbase | Proteins | 662 | 112 | 8 (27) | 0.90 |
| Dataset | SPF excess [IQR] | Pos. | Equal HP | Rand. | Holm | F1 gap | Par. |
|---|---|---|---|---|---|---|---|
| emotions | .419 [.338, .462] | 10 | .207 | .016 | .0088 | .0142 | 6 |
| scene | .107 [.085, .129] | 10 | .101 | .019 | .0088 | .0179 † | 4 |
| yeast | .426 [.409, .467] | 10 | .281 | .044 | .0088 | .0058 | 9 |
| image | .376 [.348, .396] | 10 | .298 | .047 | .0088 | .0140 | 6 |
| birds | .421 [.383, .488] | 10 | .456 | .053 | .0088 | .0261 † | 3 |
| genbase | .377 [.326, .390] | 10 | .377 | .039 | .0088 | .0000 | 10 |
| Dataset | SPF excess | Pos. | Equal HP | F1 gap | ||
|---|---|---|---|---|---|---|
| yeast | 14 | .465 | 10 | .374 | .001 | .0043 |
| birds | 12 | .374 | 10 | .375 | .001 | .0296 † |
| genbase | 13 | .000 | 4 | .000 | .0625 | .0046 |
| enron | 35 | .264 | 10 | .168 | .001 | .0097 |
| slashdot | 16 | .129 | 10 | .253 | .001 | .0136 |
| langlog | 25 | .028 | 9 | .010 | .0049 | .0026 |
| SPF | Test AUC | |||||||
|---|---|---|---|---|---|---|---|---|
| Dataset | Obs. | Cond. | Joint | Ind. | Obs. | Cond. | Obs. | Cond. |
| emotions | .482 | .464 | .625 | .707 | .850 | .814 | .325 | .203 |
| scene | .123 | .060 | .685 | .668 | .951 | .925 | .185 | .108 |
| yeast | .641 | .563 | .735 | .727 | .751 | .695 | .241 | .063 |
| image | .475 | .348 | .692 | .711 | .838 | .778 | .220 | .059 |
| birds | .483 | .457 | .201 | .176 | .896 | .794 | .078 | .073 |
| Dataset | Architecture | Randomization | Hyperparameters |
|---|---|---|---|
| emotions | .71 | .93 | .90 |
| scene | .69 | .90 | .93 |
| yeast | .71 | .93 | .94 |
| image | .80 | .92 | .94 |
| birds | .81 | .92 | .92 |
| genbase | .96 | .97 | 1.00 |
| Property | Meaning for ms-DPG | Evidence |
|---|---|---|
| Correctness | Graph and sinks reproduce the forest’s traces, masses and probabilities | Proposition 1 ; identity with the reference DPG implementation (Section 6 ) |
| Completeness | Share of the decision mass that the explanation covers | Holds for the retained traces of the full graph; the contracted views cover 37–82% (Section 7.8 ) |
| Consistency | (a) Same model, same explanation; (b) refitted models, similar explanations | (a) Deterministic extraction; (b) displayed predicates recur moderately across repetitions, lift classes agree in 65–99.7% (Section 7.8 ) |
| Parameter sensitivity (in place of continuity) | Dependence on the extraction settings | Sign of the native–BR excess stable under 36 settings on seven of nine benchmarks, magnitude not (Section 7.5 ); continuity with respect to the input was not assessed |
| Contrastivity | Distinguishes labels, directions and architectures | Scenario D5, Propositions 3 – 4 ; co-enriching against separating predicates; native against BR (Section 7.3 ) |
| Covariate complexity | Interpretability of the explanatory unit | Directional predicates on the original features, readable as far as the features are (Appendix 0.D ) |
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Excess range | Same sign | Jacc. | Empty | ||
|---|---|---|---|---|---|---|
| emotions | .044 to .620 | 36 | .92 | .032 | 340/96 | .13/.53 |
| scene | .004 to .531 | 36 | .93 | .006 | 360/283 | .20/.53 |
| yeast | .089 to .630 | 36 | .78 | .033 | 878/500 | .00/.07 |
| image | .059 to .569 | 36 | .85 | .038 | 872/418 | .00/.05 |
| birds | .159 to .641 | 36 | .81 | .049 | 323/125 | .00/.04 |
| genbase | .000 to .377 | 24 | .01 | .106 | 4.4/3.9 | .23/.86 |
| emotions | flags | |
|---|---|---|
| SPF | .88 [.92] | .97 [.97] |
| Shared active | 75 [131] | 30.5 [31] |
| Co-enriching | 74.5 [130] | 17.5 [17] |
| Coverage | .44/.52 [.37/.44] | .79/.82 [.77/.82] |
| Omitted, both | .42 [.51] | .16 [.16] |
| Omitted, source only | .81 [.84] | .30 [.34] |
| Native | BR | |||||||
|---|---|---|---|---|---|---|---|---|
| Dataset | Trees | Nodes | Mean d. | Max d. | Trees | Nodes | Mean d. | Max d. |
| emotions | 200 | 49,521 | 13.4 | 20 | 1,200 | 56,801 | 7.7 | 8 |
| scene | 200 | 101,766 | 18.6 | 28 | 1,200 | 110,575 | 8.0 | 8 |
| yeast | 200 | 225,598 | 21.7 | 32 | 1,600 | 199,421 | 8.0 | 8 |
| image | 200 | 133,961 | 19.3 | 27 | 1,000 | 117,063 | 8.0 | 8 |
| birds | 200 | 39,212 | 15.9 | 28 | 1,600 | 51,603 | 7.6 | 12 |
Interpretable ML
Interpretable machine learning develops models and explanations that make predictions, evidence, and decision processes understandable to people.
See all 329 papers