Skip to main content
Back to timeline
arXivSource publication:

Decision trees learn to hand hard cases to a black box: three training methods tie on average across real data, and deferral-aware splitting pays off on synthetic data

Synopsis

Partially interpretable models let a simple model decide for itself and defer hard inputs to an accurate black box, trading interpretability for accuracy. Training procedures existed for linear models and decision rules but not for decision trees. Three tree-training algorithms differ on average by amounts within error across many real datasets, and a bound ties this to how uniformly accurate the black box is; on synthetic data built with deliberately inhomogeneous black-box accuracy, the deferral-aware CART variant clearly beats building a tree and then converting it.

Source-provided article image: Partially Interpretable Decision Trees
arXiv

Interpretation

A decision tree can now serve as the interpretable part of a partially interpretable model: at each leaf the tree decides whether to predict itself or defer the input to the black box, so deferring more raises accuracy and deferring less widens interpretable coverage. Earlier training procedures for partially interpretable models were built on linear models or decision rules, leaving decision trees without a corresponding method. Across many real datasets, the accuracy-coverage trade-off curves of the three tree-training algorithms lie close together, with average differences within error.

Three procedures are used: one extends the existing Branches exact search by scoring a leaf as the smaller of its own error and the cost of deferring; one runs standard CART and then decides which leaves defer; one folds the deferral option into CART's splitting criterion. The third replaces ordinary entropy with PIM-entropy, an upper bound on a leaf's deferral cost that accounts for the black box and is computed in constant time from the four counts of the confusion matrix. Experiments use tabular datasets drawn from existing benchmarks, with continuous features binarized at the median, each method refit at several deferral penalties under the same complexity penalty.

Perspective

The demonstrated scope is binary classification with axis-aligned decision trees; real-data experiments use public tabular benchmarks, and the concept-bottleneck experiment uses CUB-200 bird data. The theorem and the PIM-entropy criterion are both stated for binary classification.

The bound becomes vacuous when black-box accuracy is strongly inhomogeneous across the domain; exact search exhausts memory on the two largest datasets and gives no optimality guarantee there; multi-class extension and estimating inhomogeneity from data remain open.