NBDT: Neural-Backed Decision Trees

1 INTRODUCTION

• Saliency maps identify influential pixels but do not capture the model’s decision process, while existing neural-network/tree combinations face accuracy or interpretability limitations.Source: §1 · p. 1
• NBDTs replace a neural network’s final linear layer with a differentiable oblique decision tree and preserve sequential, discrete decisions, pure leaves, and non-ensembled predictions.The paper adopts a definition of interpretability in which a human can validate a prediction and determine when the model has made a sizable mistake.Source: §1 · p. 1
• NBDTs match or outperform modern neural networks across ImageNet, TinyImageNet200, and CIFAR100, and their tree supervision loss improves the original model by up to 2%.Source: §1 · p. 2
• The proposed induced hierarchies, built from pretrained neural-network weights, outperform data-based and existing hierarchies such as WordNet in accuracy.Source: §1 · p. 2
• NBDT explanations are reported to help users identify model mistakes, support challenging classification tasks, and identify ambiguous ImageNet labels.Source: §1 · p. 2

2 RELATED WORKS

• Saliency methods identify influential pixels, but do not explain the sequence of decisions that led to a prediction.Source: §2 · p. 2
• Earlier neural-network/tree transfer methods often performed poorly on standard image-classification tasks, while many hierarchical surrogate losses lose accuracy on larger or higher-resolution tasks.Source: §2 · p. 2
• Prior neural-network/tree hybrids can use impure leaves, stochastic paths, large k-way decisions, or ensembles, limiting interpretability.Source: §2 · p. 2
• Soft inference selects by leaf path probability rather than a sequence of locally chosen children, so a confident later decision can outweigh an uncertain early mistake.Source: Figure 1 · p. 3

3 METHOD

• The method replaces the network’s final linear layer with a decision tree, using path probabilities, model-weight hierarchies, and hierarchical loss to learn high-level decisions.These design choices are intended to tolerate uncertain intermediate decisions, lessen overfitting, and better learn high-level distinctions.Source: §3 · p. 3

3.1 INFERENCE

• The final fully connected layer is run as an oblique decision tree, with leaf weights copied from classifier rows and inner-node weights averaged from descendant leaves.Child probabilities come from softmax inner products, and class probabilities are products of the probabilities along each root-to-leaf path.Source: §3.1 · p. 3
• Path-probability inference can recover from an early mistake when the incorrect path has sufficient uncertainty, unlike classic tree inference.The architecture can also run the fully connected layer either regularly or as decision rules.Source: §3.1 · pp. 3–4

3.2 BUILDING INDUCED HIERARCHIES

• The induced hierarchy clusters normalized class-weight vectors, assigning each internal node the average weight of its descendant leaves.The authors motivate this hierarchy as reflecting visual similarity while avoiding overfitting associated with data-dependent hierarchies.Source: §3.2 · p. 4, Figure 2 · p. 4

3.3 LABELING DECISION NODES WITH WORDNET

• WordNet labels each internal node with the earliest common ancestor of its subtree’s leaves, but lacks concepts for attributes and abstract visual context.The authors leave more sophisticated methods for assigning meanings to intermediate nodes to future work.Source: §3.3 · p. 4

3.4 FINE-TUNING WITH TREE SUPERVISION LOSS

• NBDT outperforms competing decision-tree-based methods by up to 18% and can also outperform the original neural network by ∼1%.Table 1 reports results for decision-tree-based methods and neural networks.Source: Table 1 · p. 5
• Tree supervision adds cross-entropy over class distributions formed from path probabilities because standard cross-entropy does not train separation at inner nodes.Its weight grows linearly from zero to 0.5 on CIFAR10 and CIFAR100, and to 5 on TinyImageNet and ImageNet; the original-loss weight decays linearly.Source: §3.4 · pp. 4–5
• The path-probability cross-entropy disproportionately upweights earlier decisions and is associated with out-generalizing the baseline neural network to unseen classes by up to 16%.The authors report that tree supervision can damage learning speed early in training, when leaf weights are nonsensical.Source: §3.4 · p. 5

4 EXPERIMENTS

• Across experiments, NBDTs improve generalization to unseen classes by up to 16%.The experiments summary reports this result across unseen classes.Source: §4 · p. 5

4.1 RESULTS

• On CIFAR10 and TinyImageNet, NBDT accuracy falls within 0.15% of the baseline neural network; on CIFAR100, it exceeds the baseline by ∼1%.The authors report that these results match or outperform recently state-of-the-art neural networks.Source: §4.1 · p. 5
• On ImageNet, NBDTs obtain 76.60% top-1 accuracy, outperform NofE by 15% and all competing decision-tree methods by at least 14%, while staying within 0.6% of EfficientNet-EdgeTPU-Small.The ImageNet comparison is shown in Figure 3.Source: §4.1 · p. 5, Figure 3 · p. 6

4.2 ANALYSIS

• The induced weight-space hierarchy outperforms WordNet, Info Gain, and OC1; the analysis notes data-dependent overfitting and WordNet's conceptual rather than visual focus.Table 2 compares the induced hierarchy with taxonomy-based and data-dependent alternatives.Source: Table 2 · p. 6, §4.2 · p. 6
• NBDT improvements are dominated by better distinctions between higher-level concepts, such as Animal versus Vehicle.Source: §4.2 · p. 6
• On TinyImageNet, hierarchical softmax yields ∼3% less accuracy than tree supervision loss.Source: §4.2 · p. 6
• Tree supervision loss improves the original network's accuracy by up to 2% on CIFAR100 and TinyImageNet.Source: §4.2 · p. 6
• Mid-training hierarchies improve the original network's accuracy by up to ∼0.6% and let NBDT match it, but underperform hierarchies built with fully trained weights.Source: §4.2 · p. 6

5 INTERPRETABILITY

• On TinyImageNet, hierarchical-softmax-trained NBDTs had about 3% lower accuracy than models trained with tree supervision loss.The loss comparison also includes constant-weight tree supervision and no extra loss terms.Source: Table 3 · p. 7
• The interpretability analyses rely on discrete sequential decisions, pure leaves, and non-ensembled predictions; the surveys use CIFAR10-trained ResNet18 models.The section also reports that constructing and using hierarchies early and often in training yields the highest-performing models.Source: §5 · p. 7, Table 4 · p. 7
• Tree supervision loss increased the original network’s accuracy by approximately 0.8–2.4% across the reported CIFAR100 and TinyImageNet experiments.Table 5 compares accuracy before and after tree supervision loss for ResNet18 and WideResNet.Source: Table 5 · p. 7

5.1 SURVEY: IDENTIFYING FAULTY MODEL PREDICTIONS

• 237 of 600 responses correctly identified a wrong prediction with NBDT explanations, versus 87 with saliency maps and class probabilities.The survey showed participants the predicted class sequence and child probabilities, but withheld the final leaf prediction.Source: §5.1 · pp. 7–8
• About 37% of NBDT errors occur at the final binary decision, which the survey withheld and therefore could not reveal to respondents.A majority of NBDT predictions in the survey were not correctly identified as wrong.Source: §5.1 · p. 8

5.2 SURVEY: EXPLANATION-GUIDED IMAGE CLASSIFICATION

• 42.5% of responses were correct with model guidance, versus 27.2% without it; 52% agreed with NBDT, compared with 28% agreeing with the base model.The survey used severely blurred images; neither model was correct in 40% of examples.Source: §5.2 · p. 8, Figure 4 · p. 8

5.3 SURVEY: HUMAN-DIAGNOSED LEVEL OF TRUST

• 73.5% of respondents preferred NBDT explanations for misclassified samples, compared with saliency explanations.Among 374 respondents choosing between methods, 65.9% preferred NBDT overall; samples were limited to cases where both models agreed.Source: §5.3 · p. 8

5.4 ANALYSIS: IDENTIFYING FAULTY DATASET LABELS

• NBDT path entropy highlights ImageNet samples with multiple plausible objects, while high-entropy samples from the baseline neural network do not indicate ambiguous labels.Path entropy is the disparity between entropies of intermediate decisions along the NBDT prediction path.Source: §5.4 · p. 9, Figure 6 · p. 9

6 CONCLUSION

• NBDTs out-generalize, match, or outperform state-of-the-art neural networks across CIFAR10, CIFAR100, TinyImageNet, and ImageNet while improving accuracy and interpretability.The conclusion reports out-generalization of 16%+, improvement of 2%+, matching within 0.15%, or outperforming by 1%+.Source: §6 · p. 9

B EXPLAINABILITY

• The appendix expands on interpretability with an emphasis on qualitative uses of the hierarchy.Source: B EXPLAINABILITY · p. 13

B.1 MAXIMUM SIMILARITY EXAMPLES TO VISUALIZE GENERALIZATION

• NBDT maximum-similarity examples drawn from ImageNet contain more unseen classes than ResNet18 examples, suggesting better capture of high-level concepts such as Animal.The paper says this is quantitatively confirmed by the superclass evaluation in Table 6, but the supplied passage gives no table values.Source: §B.1 · p. 13

B.2 EXPLAINABILITY OF NODES’ VISUAL MEANINGS

• The WordNet Animal-versus-Vehicle hypothesis accurately predicts which child receives unseen CIFAR100 validation samples at the root of a CIFAR10-trained WideResNet28x10 tree.The figure reports 80–95% classification accuracy for unseen CIFAR100 Vehicle and Animal samples at that node.Source: Figure 9 · p. 14, §B.2 · p. 14
• A four-step node test posits a meaning, gathers labeled OOD samples from unseen classes, checks their selected child, and measures the percentage routed correctly.If the hypothesis accuracy is low, the test is repeated with a different hypothesis.Source: §B.2 · p. 14

B.3 HOW MODEL ACCURACY AFFECTS INTERPRETABILITY

• The 97.62%-accurate WideResNet groups Animals separately from Vehicles, unlike the 93.64%-accurate ResNet hierarchy, which groups Frog, Cat, and Airplane.The authors attribute the difference to the WideResNet’s 4% higher accuracy and suggest that higher-accuracy models have more visually sound weight spaces.Source: §B.3 · p. 14, Figure 10 · p. 15

B.4 VISUALIZATION OF TREE TRAVERSAL

• For the seen Horse class, path traversals concentrate on the correct route; unseen Seashore samples are classified as “vehicle with blue context” 88% of the time.The Seashore example illustrates reliance on context for decision-making.Source: Figure 11 · p. 15, §B.4 · p. 15
• For unseen Teddy Bear samples, 90% are classified as Animal, but traversals spread among animals, with Dog receiving the largest share at 30%.Source: Figure 11 · p. 15, §B.4 · p. 15

C HIERARCHICAL SOFTMAX AND CONDITIONAL EXECUTION

• Conditional execution is used in neural-network and decision-tree hybrids to improve computational efficiency, including for large-scale classification.Source: C HIERARCHICAL SOFTMAX AND CONDITIONAL… · p. 15

C.1 HARD TREE SUPERVISION LOSS

• Soft tree supervision computes each leaf probability from the probabilities along its path, then applies cross-entropy over the leaf distribution.The illustrated green leaf probability is 0.6 × 0.7.Source: Figure 12 · p. 16
• Hard tree supervision adds a child-node cross-entropy for each internal node to the original class cross-entropy, weighting the loss terms equally by default.For a node with c children, its loss is a c-way cross-entropy between predicted child probabilities and labels.Source: §C.1 · p. 16

C.2 HARD INFERENCE

• Hard inference repeatedly selects the most probable child until reaching a leaf, but it underperforms soft inference, including when trained with hard tree supervision.Source: §C.2 · p. 16

• Table 7 states that hard inference performs worse than soft inference.Source: Table 7 · p. 17
• Table 8 states that tree supervision loss outperforms hierarchical softmax and omitting extra loss terms; Δ is the accuracy difference between soft loss and hierarchical softmax.Source: Table 8 · p. 17
• Tree inference can be performed directly from network logits, using the equivalence between averages of inner products and inner products of averages.Source: D IMPLEMENTATION · p. 17

• Tree-loss weights were 1 for CIFAR10 and CIFAR100 and 10 for TinyImageNet and ImageNet; hard-loss weights were 10 times the corresponding soft-loss weights.Source: E EXPERIMENTAL SETUP · p. 17
• CIFAR and TinyImageNet training lasted 200 epochs, using batch sizes of 512 and 128, respectively, on one Titan Xp.The described CIFAR training used SGD with 0.9 momentum and weight decay of 5−4.Source: E EXPERIMENTAL SETUP · p. 17
• When WideResNet baseline accuracy could not be reproduced, the authors fine-tuned a pretrained checkpoint with a starting learning rate of 0.01.Source: E EXPERIMENTAL SETUP · p. 17
• ImageNet models were retrained from scratch, but the reported 77.23% baseline came from EfficientNet authors because results used one model rather than an average of eight.Source: E EXPERIMENTAL SETUP · pp. 17–18

• CIFAR100 WideResNet28x10 subtrees group classes by WordNet concepts or visual and contextual attributes such as color, shape, and background.Source: F CIFAR100 TREE VISUALIZATION · p. 18, Figure 14 · p. 19