WorksComputer Science
Partially Interpretable Decision Trees
Abstract
Partially interpretable models extend simple interpretable models with the option to defer complicated inputs to an accurate but uninterpretable black-box model. By deferring more inputs, the model gets more accurate; by deferring fewer, it gets more interpretable. Existing procedures to train such partially interpretable models build on linear models or decision rules. We propose three algorithms for decision trees: a partially interpretable extension of the existing Branches algorithm, which performs exact search to optimize the tree; a conversion algorithm that we run on top of standard CART, which is computationally more efficient; and a generalized CART whose splitting criterion takes into account the option to defer while growing the tree. Perhaps surprisingly, the performance of the three algorithms is similar across many realworld datasets. We can explain this through a formal bound on the potential gain of smart tree construction, provided the black box accuracy is sufficiently homogeneous across the domain. We also construct a synthetic dataset where the accuracy of the black box is deliberately inhomogeneous. There, our deferral-aware generalization of CART does outperform regular CART and matches the performance of exact search. Finally, we evaluate an application to concept bottleneck models. Partially interpretable decision trees can replace uninterpretable neural networks after the bottleneck. On undeferred inputs, the model is fully interpretable, and deferring preserves accuracy.
Introduction
When selecting machine learning models for classification, there is a tension between interpretability and accuracy. Certain simple models, such as linear classifiers, rule lists, and decision trees [3, 28, 1] are inherently interpretable (provided they are of reasonable size), but this is only possible because they impose strong restrictions on the class of functions they can express, and as a consequence they cannot learn complicated relations. Conversely, richer function classes like neural networks or support vector machines can, for instance, approximate all continuous functions on a compact domain [15, 16], but are not inherently interpretable and behave as a black box.
A commonly proposed solution is to use simple, interpretable models to locally approximate accurate, more complicated black box models, and use the local approximation as a way to interpret the black box. For instance, LIME [27], SHAP [23], SmoothGrad [29] and Integrated Gradients [30] may all be viewed as local linear approximations [13]. Unfortunately, a major limitation of these local approximations is that their explanations provide no guarantees: we typically do not know how accurate the local approximation is, or over which region it is valid. Therefore users cannot base any decisions on the local approximations with any certainty.
To resolve this, we need explanations that are sufficient: the explanation determines the prediction and points sharing the same explanation will have the same prediction [12]. Sufficiency is satisfied by so-called partially interpretable models, which consist of a hybrid between an interpretable simple model and an accurate black-box model [33, 12]. On simple inputs, the interpretable model will make predictions itself, which are therefore interpretable, and on complicated inputs it will defer to the black box for prediction. Such hybrid models offer a trade-off between accuracy and interpretability: by deferring more inputs, the hybrid model gets more accurate, and by deferring fewer it gets more interpretable. Importantly, the decision whether to defer an input is always handled by the interpretable model, and is therefore also interpretable.
Training procedures for partially interpretable models have so far been developed when the simple model is linear [33] or consists of a list of decision rules [33, 12, 11], but not yet for the important class of decision trees. How to learn partially interpretable trees is the topic of this paper.
New algorithms First, in § 3, we introduce three algorithms to learn partially interpretable decision trees. The first, PI-Branches, is a partially interpretable extension of the existing Branches algorithm of Chaouki et al. [6], which performs exact search1 to optimize the tree. Since exact search is NP-complete already without deferring [17], this is computationally feasible only when the number of features is not too large. The second, CART-and-convert, takes the tree learned by the computationally efficient CART algorithm [3], and makes it defer on a subset of its leaves. The third, PI-CART, is also based on CART, but generalizes it by changing its splitting criterion to take into account the option to defer already while growing the tree.
A theoretical insight We originally intended CART-and-convert as a simple baseline, but it performs surprisingly well in experiments. In § 4 we provide a theoretical explanation: we compare the conversion procedure to an oracle that knows the optimal tree, and bound the gap between the corresponding curves of optimal trade-offs between expected error and proportion of inputs that are deferred. Theorem 2 shows that these curves can differ by at most , where measures the suboptimality of CART compared to the best tree that never defers, measures the suboptimality of the conversion procedure and measures how much the performance of the black box varies across the domain. Kearns and Mansour [18] show that CART can drive to 0 in the PAC learning setting, and we can expect to go to 0 as the sample size increases. Therefore, if the inhomogeneity is also small, the conversion procedure’s performance is never much more than 1/8 = 12.5% worse than the oracle. The theorem further provides a problem-dependent bound that is significantly tighter if there exists a tree that can achieve small expected error without deferring. This shows that the potential gains from more sophisticated tree growing procedures are limited.
Experiments In § 5 we provide experiments to compare the different tree learning algorithms, which show they tend to have similar performance except in special cases. On real data, the gains of PI-Branches and PI-CART over CART-and-convert are small and inconsistent: over 15 real data sets, the three methods lie within 0.60% error of one another on average. In fact, on 10 of these data sets the difference is within 1.2% error. There are larger gaps, of up to 10.9% error on several small datasets, but they do not consistently favor any single method. Inspired by Theorem 2, we further construct a synthetic data set on which the performance of the black box is deliberately inhomogeneous (see Appendix § 12.§ 2). In this case we do observe that PI-Branches and PI-CART are better able to adapt the tree structure to take this into account, and outperform CART-and-convert.
Application to concept bottleneck models Finally, we combine our methods with concept bottleneck models [20], which predict in two stages: a (potentially complicated) map from raw features to a layer of human-understandable concepts, followed by an interpretable model that maps concepts to predictions. Even though is supposed to be interpretable, it is common in the literature to use a two-layer feedforward network. Instead, we let be a partially interpretable decision tree that can defer to a black box that predicts labels from raw features directly. This has the advantage that is truly interpretable on the inputs on which it does not defer. We find that, on CUB-200 data, a depth-8 tree over hard concepts matches the accuracy of a soft concept bottleneck model with 60k parameters for the network , while providing sufficient explanations on 57% of the data.
Further related work Our setup is formally similar to learning to reject, in which binary classification is extended with the option to reject an instance at a fixed cost instead of predicting a label [7, 2, 8], and its generalization learning to defer, where predictions may be deferred to a human expert [24, 25]. Variants of these settings correspond to what we will call the Lagrangian problem formulation in § 2.2. The motivation is very different, however, because we require interpretability of the model and rejection function, whereas the goal of learning to defer is to reduce classification mistakes in uncertain situations, and interpretability plays no role.
A variant of partially interpretable models is also developed by Pan et al. [26], who allow the user to choose between a simple model and the black box. Craven and Shavlik [9, 10]; Lakkaraju et al. [21] approximate a black box model by decision rules or trees, and Bressan et al. [4] characterize theoretically when black box models can be approximated by trees.
Partially Interpretable Models
Setting
We first consider the standard binary classification setting. Let be a sample of independent draws from a common distribution , where takes values in and is a label in . Given a prediction and outcome in , let denote the 0/1-loss. For a given classifier , let
and
denote the risk and the empirical risk, respectively. Any classifier is called Bayes-optimal.
To extend this setting to allow for partially interpretable models, suppose we have access to a high-quality reference classifier , which is considered an uninterpretable black box. For instance, might be the output of boosting, a random forest or a neural network. Then we can allow for an extended prediction , where we take to mean “defer the prediction to ”. Given an extended classifier that makes such extended predictions, let denote the induced classifier that predicts
We will be interested in extended classifiers that are simple enough to be interpretable (e.g. decision trees, decision rules, linear classifiers), so that is interpretable on inputs for which . When is highly accurate, such an extended classifier can reduce its risk by deferring more inputs to , at the cost of increasing the proportion of inputs it leaves uncovered, which we will call the (empirical) uncoverage:
Constrained versus Lagrangian Optimization
There are two natural ways to formulate the trade-off between minimizing the empirical risk and the empirical uncoverage over a class of interpretable extended classifiers : the constrained problem
(CP) parametrized by , and the Lagrangian problem
(LP) for $\lambda\ge 0. The difference is that the CP sets a hard constraint on the uncoverage, whereas the LP introduces a soft cost for uncovered inputs.
The CP is the most general formulation, because, by varying , its solutions trace out the whole Pareto frontier of possible optimal trade-offs between risk and uncoverage. We can recover some of these optimal trade-offs by solving the LP with varying as well, because any solution to the LP is also a solution to the CP for , and therefore also sits on the Pareto frontier. This is attractive, because the LP is often computationally easier, but unfortunately it can miss some Pareto optimal trade-offs that do not sit on the lower convex hull of Pareto optimal trade-offs (because the optimization problem is not convex, and therefore has potentially non-zero duality gap). This is discussed further in Appendix Appendix § 9, which also shows that the gap can be substantial: the appendix exhibits a data set of points on which a Pareto optimal trade-off is not the solution to an LP for any , and extends it to a family of data sets on which the resulting suboptimality approaches .
Learning Partially Interpretable Trees
In this section we discuss three algorithms for learning partially interpretable models when the class of interpretable extended classifiers consists of binary decision trees . We will represent a binary tree by the partition of that it induces, where each partition cell is a leaf of the tree, and is an extended labeling function that assigns a label to each leaf , including the option to defer. Letting denote the leaf that contains , we then also write for the prediction of the tree on input . Each internal node splits on a threshold of a single feature (axis-aligned splits).
Exact Search with Partially Interpretable Branches
The Branches algorithm of Chaouki et al. [6] performs exact search to minimize over the class of trees that never defer. Its hyperparameter trades off between the number of leaves and the fit on the data. It further requires binary features, and takes an optional additional parameter to restrict the maximum depth of the trees, in which case the search is only approximately exact.
We extend this to a partially interpretable variant PI-Branches that allows deferring and takes the uncoverage into account by minimizing
Branches is an AO*-type algorithm performing Best-First-Search within an AND/OR graph search framework. The only modification PI-Branches requires is in how a terminal state (a leaf) is scored.
For a branch (a candidate root-to-leaf path), let be the number of training points that follow it, those in the majority class, and those the black box predicts correctly. Branches scores a leaf by its errors ; PI-Branches replaces this by the minimum of the Branches score and , which is the cost of deferring. The search heuristic is also adjusted accordingly. See Appendix § 10.§ 1 for a complete description of the algorithm.
CART and Convert
The regular CART algorithm (Breiman et al. [3]) learns a decision tree without deferring, so with . A simple, but surprisingly effective approach to turn this into a partially interpretable decision tree is to fix the tree structure and hence the leaves , but replace by an extended labeling function that optimizes either the constrained problem or the Lagrangian problem. We then obtain the following two variants.
Convert for constrained problem Given , optimize
If we do not defer on a leaf, then the optimal label is the majority class among the data points in that leaf, so the remaining decision is when to defer. This gives rise to a knapsack problem, where the leaves are the items (Kellerer et al. [19]) and a leaf is included in the knapsack when the tree defers on that leaf. (See Appendix § 10.§ 2 for details.)
Convert for Lagrangian problem Given , optimize
This formulation is easy to solve, because it makes the choice to defer independent between leaves: the optimal choice is to defer for leaf whenever the loss of deferring, penalized by , is less than the loss of not deferring:
In Appendix § 12.§ 3, we experimentally compare the two methods. We measure the difference in aggregate score (defined in § 5.1) between the two conversion approaches, and find it below 0.3 points (Table 3).
| depth | train | held out |
| 2 | +0.265 ± 0.088 | +0.268 ± 0.086 |
| 3 | +0.188 ± 0.081 | +0.159 ± 0.072 |
| 4 | +0.145 ± 0.059 | +0.177 ± 0.055 |
| 5 | +0.105 ± 0.041 | +0.118 ± 0.034 |
| 6 | +0.069 ± 0.024 | +0.086 ± 0.022 |
Table 3. Converting one fitted tree into a partially interpretable model, 13 datasets × 10 seeds: gain of the exact knapsack at each coverage budget (K) over the Lagrangian rule (L), both scored with the aggregate score of § 5.1, in points, ± one standard error across the 13 datasets. The difference is less than a percentage point.
To limit overfitting, we prune the grown trees by cost-complexity pruning (Breiman et al. [3]), which is equivalent to minimizing the PI-Branches objective (1) over all subtrees of the grown tree.
Partially Interpretable CART
CART-and-convert provides a straightforward way to train partially interpretable trees. However, information about the black box is not used when growing the tree. A natural extension is to consider a splitting criterion that incorporates information about .
To do so, we start from the entropy criterion of CART. If a fraction of the training points in a leaf are positive, the entropy of is . The entropy has a useful interpretation in terms of soft predictions. Suppose that, instead of a single label, the leaf predicts a probability distribution over the two labels and that it is evaluated by the log-loss . The best soft prediction is then , and its average log-loss is exactly the entropy:
This also explains why the entropy is a sensible splitting criterion: since , the average log-loss of any bounds its expected error , so is an upper bound on the error of the majority label, the smallest such error.
To extend the entropy criterion to partially interpretable decision trees, we want to mimic this construction with a suitable generalization of the log-loss to soft predictions , which takes the black box into account. Given that deferred points are processed by the black box, the distribution induces on the following distribution . This motivates the following definition of the PIM log-loss:
This loss upper-bounds the penalized 0/1-loss
of a prediction drawn from . Indeed, its expected value is , and applied to gives
Averaged over the leaf and minimized over , the left-hand side is the smaller of the error of the majority label and the error of on plus , which is the cost of the leaf under the deferral rule of § 3.2. The PIM-entropy defined below is therefore an upper bound on this cost, just as the entropy bounds the error of the majority label.
Let be the fraction of the points in with and , for , collected in the confusion matrix ; in particular . The average PIM log-loss on depends on the leaf only through , and we define the PIM-entropy of as its minimum:
We drop the superscript when it is clear from context.
The PIM-entropy has a closed form, given by the following lemma and proved in Appendix § 10.§ 3. Like the entropy, it can therefore be evaluated from the four counts of the confusion matrix in constant time, so PI-CART has the same computational cost as CART.
Lemma 1. Let and let be a leaf containing at least one data point. The PIM-entropy has the closed form
where
and and are, respectively, the larger roots of the following quadratics:
Bound on Conversion Accuracy
As for CART, PI-CART then chooses each split to minimize the average PIM-entropy of the two children, weighted by their numbers of points.
The CART-and-convert convert algorithm does not take the option to defer into account when choosing the tree structure. Intuitively, this should be fine if the accuracy of the black box is sufficiently homogeneous over the domain: we can defer any region on which the tree ends up having low accuracy without concern for whether this is a good or bad region for the black box. In this section we formalize this intuition for converting based on the Lagrangian problem.
The result will actually apply, not just to decision trees, but to any model class with models that can be described by a finite partition of from a class of candidate partitions , together with an extended labeling function chosen from all such labeling functions.
We measure the inhomogeneity of the black box with respect to the possible partitions in by:
where . Each summand is the excess error of in a region over the error would make if its mistakes were independent of .
We will assume that a learning algorithm (e.g. CART) selects a partition (e.g. as induced by a tree) that is close to minimizing the risk if we never defer:
for some small . In addition, suppose that, for all , we have a conversion strategy that approximately minimizes the population version of the Lagrangian conversion problem:
where denotes the population version of the Lagrangian objective for any , and is small. For instance, we have in mind that solves the corresponding empirical conversion problem (2).
We will consider the lower convex hull of trade-offs between unconverage and risk , which corresponds to the optimal trade-offs achievable by solving the Lagrangian problem formulation (see § 2.2 and Appendix § 9.§ 1). For the conversion strategy, this applies to selected from , and we denote the lower convex hull by for . We compare this to the lower convex hull of an oracle that optimizes over all . Formally, given any model class of the same type as , the achievable trade-offs between risk and uncoverage are:
Then the lowest risk on the lower convex hull with uncoverage at most is
The two lower convex hulls are then defined as:
Figure 1 illustrates and for an example.
Figure 1. Example showing the lower convex hulls of achievable trade-offs between uncoverage and risk for the conversion procedure () and the oracle (). In this case, the black box is perfect, so . We also take zero conversion error: , which implies that . The line supports at , and the line supports at . See Appendix § 11.1.1 for further details.
Theorem 2. Suppose , and satisfy (3), (4) and (5). Then the suboptimality of the conversion strategy at any maximum uncoverage is at most
This result is easiest to interpret when we think of , and as being 0. Then and the bound shows that the suboptimality of the converting algorithm, compared to the oracle, is at most , or even smaller if is far from . Although the conversion approach may seem simplistic, this means there is limited room to improve on it, because no other learning algorithm (over the same model class) can beat the oracle.
The case that may in fact hold exactly, for instance if the black box is perfect, i.e. when almost surely. But if the performance of the black box is not homogeneous across the domain, then can also be large and then the bound will be vacuous.
The bound is a deterministic statement that holds for any distribution for . This includes in particular the case that is equal to the empirical distribution , i.e. the uniform distribution over the sample . In this case the statements apply to the empirical risk and the empirical uncoverage. If indeed solves (2), we then get , and if is close to minimizing the empirical risk we also have .
Proof of Theorem 2
The proof breaks down into two lemmas, whose formal proofs are deferred to Appendix § 11.1.2.
Let . Then the first lemma is a convex duality result:
Lemma 3. For any , there exists (with a subgradient of at ) such that
Proof sketch. This is illustrated in Figure 1: supports at with slope , and the parallel line that supports at some is a lower bound on at . The vertical distance between the two lines therefore bounds .
The second lemma continues from the first:
Lemma 4. For any ,
Proof sketch. Consider the case that and are both 0, so the black box is equally good on every region . Then optimal conversion at any is at least as good as , by either never or always deferring. Conversely, the oracle can gain at most a factor compared to by deferring in any region (assuming that this factor is less than 1), because even without deferring the majority vote already achieves error at most . The difference gives a bound of . Taking the worst case over then completes the proof.
Finally, combining Lemmas 3 and 4 gives the first inequality of Theorem 2. Plugging in (4) and using that maximizes the bound then gives its second inequality.
Experiments
In this section, we discuss our experimental results. As is common, we present our results in terms of accuracy and coverage (rather than risk and uncoverage).
Datasets and protocols are detailed in Appendix § 12.§ 1; Appendices § 12.§ 3, § 12.§ 4 and § 12.§ 5 cover the cost of the Lagrangian relaxation, a comparison with decision lists, and an alternative scoring criterion.
Comparison of the Three Methods
We compare the three methods from § 3. CART-and-convert uses the regular CART algorithm with either the Gini index or entropy as a splitting criterion, PI-CART uses instead. Finally PI-Branches performs exact search. This gives four procedures in total.
Setup Our benchmark consists of 20 datasets drawn from the benchmarks of Chaouki et al. [6] and Frost et al. [12] (Table 2). PI-Branches requires binary features, so continuous attributes are thresholded at their median and categorical ones are dummy-encoded. Every method is refit at each of 20 values of with a maximum depth of 10 and the same complexity penalty , applied as the search penalty for PI-Branches and as ccp_alpha for CART. PI-Branches terminates for all values of on 18 of the 20 datasets. The exceptions are mushroom and ficobin, the two largest datasets, on which the search exhausts the available memory (Appendix § 12.§ 1). Chaouki et al. [6] also report their own solver reaching timeout on mushroom under binary encoding. We also set aside the three MONK problems, on which greedy splitting is known to fail (see below), so our averages are over the remaining 15 datasets.
| dataset | % pos. | black box | acc. | task | ||
| both tracks | ||||||
| diabetes | 768 | 8 | 65.1 | SVM | 76.0 | onset of diabetes in Pima Indian patients |
| ficobin | 10,459 | 17 | 47.8 | GBT | 73.0 | credit risk on a FICO home-equity line of credit |
| heart_statlog | 270 | 13 | 44.4 | SVM | 81.5 | presence of heart disease |
| ionosphere | 351 | 34 | 64.1 | SVM | 94.4 | whether a radar return shows structure in the ionosphere |
| mushroom | 8,124 | 112 | 51.8 | DT | 100.0 | whether a mushroom is poisonous |
| spambase | 4,601 | 57 | 39.4 | GBT | 94.7 | whether an e-mail is spam |
| method comparison only | ||||||
| banknote | 1,372 | 4 | 44.5 | RF | 87.9 | genuine or forged banknote, from wavelet features of a scanned note |
| breast_cancer | 286 | 32 | 29.7 | RF | 72.1 | recurrence of breast cancer within five years (Ljubljana) |
| credit_a | 690 | 37 | 55.5 | RF | 84.1 | accept or decline a credit-card application |
| german_credit | 1,000 | 48 | 70.0 | RF | 74.7 | good or bad credit risk for a loan applicant |
| hepatitis | 155 | 19 | 79.4 | RF | 80.9 | survival of a hepatitis patient |
| monk1 | 124 | 17 | 50.0 | RF | 89.5 | first MONK concept-learning problem (exact rule, noiseless) |
| monk2 | 169 | 17 | 37.9 | RF | 58.8 | second MONK problem (counting rule, hardest for a small tree) |
| monk3 | 122 | 17 | 49.2 | RF | 100.0 | third MONK problem (simple rule, 5% label noise) |
| pc1 | 1,109 | 21 | 6.9 | RF | 93.1 | defect-prone modules in NASA flight software |
| sick | 3,772 | 31 | 6.1 | RF | 92.6 | thyroid disease |
| sonar | 208 | 60 | 46.6 | RF | 82.5 | sonar return from a metal cylinder or a rock |
| tictactoe | 958 | 27 | 65.3 | RF | 96.5 | whether x has won, from a terminal board |
| vote | 435 | 16 | 38.6 | RF | 96.2 | a US congressman’s party, from 16 recorded votes |
| wdbc | 569 | 30 | 37.3 | RF | 95.9 | malignant or benign breast mass, from cell-nucleus measurements |
| conversion and decision lists only | ||||||
| adult | 32,561 | 36 | 24.1 | GBT | 84.6 | whether a person earns more than $50,000 |
| bank | 41,188 | 62 | 11.3 | GBT | 90.1 | whether a client subscribes after a marketing call |
| bank2 | 41,188 | 63 | 11.3 | GBT | 92.4 | the same task, with the call-duration feature retained |
| breastcancer | 683 | 10 | 35.0 | SVM | 96.4 | whether a tissue sample is benign |
| careval | 1,728 | 15 | — | NN | 100.0 | car acceptability (four classes) |
| compasbin | 6,172 | 13 | 45.5 | NN | 68.8 | whether a convicted criminal re-offends |
| mammo | 961 | 14 | 46.3 | NN | 85.0 | whether a mammography sample is malignant |
Table 2. Every dataset used in the paper, grouped by which experiments it appears in. is the pooled size and the feature count; on the method comparison track the features are binarized (four datasets ship binarized with the Branches distribution, the rest as described in the text), while the conversion and decision-list tracks keep them continuous and scale them to . black box is the model the interpretable part defers to and acc. its held-out accuracy in points: a 100-tree random forest on the datasets used for the method comparison alone, and otherwise the class selected by the grid search of Frost et al. [12]. The six datasets in both tracks use one cached black box and split throughout, so the two agree on every column here; the method comparison track calls heart_statlog. % pos. is the proportion of the positive class over the pooled data, and a dash marks careval, the one multi-class task. Sources and OpenML ids are in compute_one.DATASET_REGISTRY.
Each method produces multiple hybrid trees sitting at different accuracy/coverage trade-offs. We score them in the following manner. For each value of the coverage, we select the best model obtaining at least this value of coverage on the testing data. Integrating this over gives us our aggregate score. We also report another criterion, the best accuracy obtained for coverage set at by selecting the best model among those with training coverage , for which we report both the test accuracy and test coverage. On about half of the datasets, the methods are within a fraction of a percent of error. The notable exceptions are the MONK datasets in which PI-Branches outperforms other methods. This is expected because they are parity-like problems on which greedy splitting is known to fail because individual features are not informative about the label by themselves.
One dataset in full Figure 2 shows our methods on the spambase dataset. The four frontiers coincide almost everywhere; the numbers behind it, and the same breakdown for every other dataset, are in Table 6.
Figure 2. Coverage/accuracy on the held-out split of spambase. Markers are the models obtained for the different values of .
| dataset | method | opt. | agg. score | acc | cov | acc | cov | acc | cov |
| banknote | PI-Branches | 20/20 | 87.9 | 87.6 | 79.4 | 87.6 | 79.4 | 87.6 | 79.4 |
| gini | 87.9 | 87.6 | 79.4 | 87.6 | 79.4 | 87.6 | 79.4 | ||
| entropy | 87.9 | 87.6 | 79.4 | 87.6 | 79.4 | 87.6 | 79.4 | ||
| PI-CART | 87.9 | 87.6 | 79.4 | 87.6 | 79.4 | 87.6 | 79.4 | ||
| breast_cancer | PI-Branches | 3/20 | 75.0 | 72.1 | 17.4 | 75.6 | 60.5 | 74.4 | 87.2 |
| gini | 75.2 | 72.1 | 43.0 | 75.6 | 74.4 | 74.4 | 94.2 | ||
| entropy | 75.2 | 72.1 | 48.8 | 75.6 | 74.4 | 74.4 | 94.2 | ||
| PI-CART | 75.2 | 72.1 | 32.6 | 75.6 | 74.4 | 74.4 | 94.2 | ||
| credit_a | PI-Branches | 4/20 | 84.0 | 84.5 | 47.3 | 84.5 | 78.3 | 84.5 | 78.3 |
| gini | 84.0 | 84.5 | 47.3 | 84.5 | 78.3 | 84.5 | 78.3 | ||
| entropy | 84.0 | 84.5 | 47.3 | 84.5 | 78.3 | 84.5 | 78.3 | ||
| PI-CART | 84.0 | 84.5 | 47.3 | 84.5 | 78.3 | 84.5 | 78.3 | ||
| diabetes | PI-Branches | 20/20 | 76.7 | 76.6 | 64.9 | 76.6 | 64.9 | 77.3 | 87.0 |
| gini | 75.5 | 76.6 | 55.2 | 74.7 | 89.0 | 74.7 | 89.0 | ||
| entropy | 75.5 | 76.6 | 55.2 | 74.7 | 89.0 | 74.7 | 89.0 | ||
| PI-CART | 75.7 | 76.6 | 64.9 | 76.6 | 64.9 | 74.7 | 89.0 | ||
| ficobin | PI-Branches | — | — | — | — | — | — | — | |
| gini | 69.6 | 69.6 | 100.0 | 69.6 | 100.0 | 69.6 | 100.0 | ||
| entropy | 69.6 | 69.6 | 100.0 | 69.6 | 100.0 | 69.6 | 100.0 | ||
| PI-CART | 71.9 | 71.7 | 82.4 | 71.7 | 82.4 | 71.7 | 82.4 | ||
| german_credit | PI-Branches | 4/20 | 74.6 | 75.7 | 45.7 | 73.7 | 75.7 | 73.7 | 100.0 |
| gini | 74.6 | 75.7 | 45.7 | 73.7 | 75.7 | 73.7 | 100.0 | ||
| entropy | 74.6 | 75.7 | 45.7 | 73.7 | 75.7 | 73.7 | 100.0 | ||
| PI-CART | 73.4 | 74.3 | 26.3 | 74.7 | 65.3 | 70.0 | 100.0 | ||
| heart_statlog | PI-Branches | 20/20 | 78.2 | 85.1 | 66.0 | 85.1 | 66.0 | 80.9 | 95.7 |
| gini | 73.5 | 75.9 | 27.8 | 75.9 | 48.1 | 72.2 | 85.2 | ||
| entropy | 73.5 | 75.9 | 27.8 | 75.9 | 48.1 | 72.2 | 85.2 | ||
| PI-CART | 77.1 | 75.9 | 51.9 | 75.9 | 51.9 | 72.2 | 81.5 | ||
| hepatitis | PI-Branches | 20/20 | 83.5 | 85.1 | 66.0 | 85.1 | 66.0 | 80.9 | 95.7 |
| gini | 82.7 | 80.9 | 42.6 | 80.9 | 63.8 | 80.9 | 97.9 | ||
| entropy | 82.7 | 80.9 | 42.6 | 80.9 | 63.8 | 80.9 | 97.9 | ||
| PI-CART | 80.9 | 78.7 | 59.6 | 78.7 | 59.6 | 74.5 | 100.0 | ||
| ionosphere | PI-Branches | 7/20 | 88.0 | 87.3 | 52.1 | 87.3 | 52.1 | 90.1 | 80.3 |
| gini | 90.3 | 91.5 | 54.9 | 91.5 | 54.9 | 88.7 | 94.4 | ||
| entropy | 90.4 | 91.5 | 54.9 | 91.5 | 54.9 | 88.7 | 93.0 | ||
| PI-CART | 91.8 | 88.7 | 35.2 | 84.5 | 66.2 | 91.5 | 100.0 | ||
| monk1 | PI-Branches | 20/20 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 | 100.0 |
| gini | 94.1 | 92.1 | 89.5 | 92.1 | 89.5 | 92.1 | 100.0 | ||
| entropy | 94.1 | 92.1 | 89.5 | 92.1 | 89.5 | 92.1 | 100.0 | ||
| PI-CART | 94.7 | 94.7 | 100.0 | 94.7 | 100.0 | 94.7 | 100.0 | ||
| monk2 | PI-Branches | 20/20 | 72.5 | 62.7 | 68.6 | 62.7 | 68.6 | 72.5 | 92.2 |
| gini | 51.6 | 56.9 | 29.4 | 49.0 | 86.3 | 49.0 | 86.3 | ||
| entropy | 54.3 | 56.9 | 29.4 | 56.9 | 62.7 | 56.9 | 62.7 | ||
| PI-CART | 70.6 | 58.8 | 58.8 | 58.8 | 58.8 | 70.6 | 100.0 | ||
| monk3 | PI-Branches | 20/20 | 99.4 | 100.0 | 56.8 | 100.0 | 56.8 | 100.0 | 81.1 |
| gini | 99.8 | 100.0 | 56.8 | 100.0 | 56.8 | 100.0 | 91.9 | ||
| entropy | 99.8 | 100.0 | 56.8 | 100.0 | 56.8 | 100.0 | 91.9 | ||
| PI-CART | 99.5 | 100.0 | 81.1 | 100.0 | 81.1 | 100.0 | 81.1 | ||
| mushroom | PI-Branches | — | — | — | — | — | — | — | |
| gini | 98.9 | 98.9 | 100.0 | 98.9 | 100.0 | 98.9 | 100.0 | ||
| entropy | 98.9 | 98.9 | 100.0 | 98.9 | 100.0 | 98.9 | 100.0 | ||
| PI-CART | 99.7 | 100.0 | 72.9 | ||||||
| pc1 | PI-Branches | 20/20 | 93.1 | 93.1 | 100.0 | 93.1 | 100.0 | 93.1 | 100.0 |
| gini | 93.1 | 93.1 | 100.0 | 93.1 | 100.0 | 93.1 | 100.0 | ||
| entropy | 93.1 | 93.1 | 100.0 | 93.1 | 100.0 | 93.1 | 100.0 | ||
| PI-CART | 93.1 | 93.1 | 100.0 | 93.1 | 100.0 | 93.1 | 100.0 | ||
| sick | PI-Branches | 20/20 | 93.9 | 93.9 | 100.0 | 93.9 | 100.0 | 93.9 | 100.0 |
| gini | 93.9 | 93.9 | 100.0 | 93.9 | 100.0 | 93.9 | 100.0 | ||
| entropy | 93.9 | 93.9 | 100.0 | 93.9 | 100.0 | 93.9 | 100.0 | ||
| PI-CART | 93.9 | 93.9 | 100.0 | 93.9 | 100.0 | 93.9 | 100.0 | ||
| sonar | PI-Branches | 7/20 | 74.1 | 69.8 | 79.4 | 69.8 | 79.4 | 69.8 | 79.4 |
| gini | 66.9 | 66.7 | 61.9 | 66.7 | 61.9 | 65.1 | 100.0 | ||
| entropy | 67.0 | 68.3 | 74.6 | 68.3 | 74.6 | 65.1 | 84.1 | ||
| PI-CART | 77.9 | 73.0 | 66.7 | 73.0 | 66.7 | 66.7 | 96.8 | ||
| spambase | PI-Branches | 20/20 | 87.0 | 93.6 | 30.5 | 90.6 | 52.8 | 83.9 | 75.5 |
| gini | 87.5 | 93.6 | 30.5 | 90.9 | 53.7 | 83.0 | 79.8 | ||
| entropy | 87.5 | 93.6 | 30.5 | 90.9 | 53.7 | 83.0 | 79.8 | ||
| PI-CART | 87.5 | 93.6 | 30.5 | 90.9 | 53.7 | 83.0 | 79.8 | ||
| tictactoe | PI-Branches | 20/20 | 91.4 | 95.5 | 53.1 | 95.8 | 53.1 | 86.5 | 94.4 |
| gini | 95.1 | 95.5 | 40.6 | 95.5 | 52.4 | 95.1 | 84.0 | ||
| entropy | 95.1 | 95.5 | 40.6 | 95.5 | 52.4 | 95.1 | 84.0 | ||
| PI-CART | 90.7 | 92.4 | 39.6 | 87.5 | 52.4 | 87.5 | 100.0 | ||
| vote | PI-Branches | 20/20 | 96.1 | 96.2 | 58.0 | 96.2 | 58.0 | 96.2 | 85.5 |
| gini | 96.1 | 96.2 | 58.0 | 96.2 | 58.0 | 96.2 | 85.5 | ||
| entropy | 96.1 | 96.2 | 58.0 | 96.2 | 58.0 | 96.2 | 85.5 | ||
| PI-CART | 96.1 | 96.2 | 58.0 | 96.2 | 58.0 | 96.2 | 85.5 | ||
| wdbc | PI-Branches | 20/20 | 97.4 | 96.5 | 49.1 | 96.5 | 49.1 | 95.9 | 88.3 |
| gini | 96.4 | 96.5 | 49.1 | 96.5 | 49.1 | 95.9 | 88.3 | ||
| entropy | 96.4 | 96.5 | 49.1 | 96.5 | 49.1 | 95.9 | 88.3 | ||
| PI-CART | 96.5 | 96.5 | 49.1 | 96.5 | 49.1 | 95.3 | 79.5 |
Table 6. Score of PI-Branches, CART-and-convert (gini and entropy) and PI-CART by dataset. Columns as in Table 1; agg. score is the mean of the coverage/accuracy staircase over and the best method on each dataset is in bold. opt. counts the values of on which PI-Branches proved optimality. A dash marks mushroom and ficobin, where exact search did not finish; the greedy criteria are still reported there. Under the model with the best training accuracy among those covering at least is selected: cov is the coverage it achieves on the held-out split, often well above because none of the values of yields a model near it.
Across datasets Table 1 averages the same quantities over the 15 datasets that remain once the three MONK problems and the two datasets on which PI-Branches does not terminate are set aside, and the picture is the same there: the four procedures lie within 0.60% error of one another on the aggregate score and within 1.12% on the tightest coverage threshold. Per dataset, the methods are within 1.2% error of one another on 10 of the 15 datasets; the larger gaps (sonar, ionosphere, heart_statlog, tic tactoe, hepatitis) arise on small datasets and vary in which method they favor. Complete results by dataset can be found in Appendix § 12.7.
| PI-Branches | gini | entropy | PI-CART | |
| aggregate score | 85.39 | 84.84 | 84.86 | 85.44 |
| 86.08 | 85.35 | 85.46 | 85.15 | |
| 85.36 | 85.14 | 85.25 | 84.62 | |
| 84.13 | 83.93 | 83.93 | 83.01 |
Table 1. Comparison between methods, averaged over the 15 datasets on which every method completed, excluding the three MONK problems. Per dataset results are in Appendix § 12.7.
In particular, PI-CART and PI-Branches, which take the black box into account while growing the tree, show no advantage over CART-and-convert on real data. That is a property of the data rather than of the methods. In Appendix § 12.§ 2, we construct a dataset on which the accuracy of the black box is deliberately inhomogeneous across the domain, and there PI-CART and PI-Branches do outperform CART-and-convert.
Application to Concept Bottleneck Models
Concept bottleneck models (CBMs) ([20]) predict in two stages: a (potentially complicated) map from raw features to a layer of human-understandable concepts, followed by an interpretable model that maps concepts to predictions. This allows CBMs to deal with complex features such as pixels, to support intervention on concepts and to be human-interpreted through their concepts. Concepts are either hard (binary) or soft (continuous scores).
CBMs tend to have worse accuracy compared to an unconstrained black box. And, in spite of the promise of interpretability, the concept-to-label part is often a neural network, which is usually not considered inherently interpretable. We replace this second stage by a partially interpretable tree on the concepts, which defers to an unconstrained black box. This allows us to trade off coverage for accuracy, and match the accuracy of existing CBMs. When the hybrid model does not defer, the path is a sufficient explanation from the concepts, as discussed in the introduction. More precisely, two data points that follow the same path will get the same prediction from the tree. If that prediction is to not defer, they will get the same prediction from the hybrid model.
We demonstrate this approach on the CUB-200 bird dataset ([32]): 200 species to be identified from 112 human-interpretable concepts, in the setting of Havasi et al. [14] (Appendix § 12.§ 1). The baseline CBM maps the predicted concepts to the classes with a two-layer network of approximately 60k parameters. Our hybrid model is a decision tree on those same 112 concepts, deferring to an unconstrained Inception v3 model on pixels. Since a depth- tree has at most leaves, we consider a depth of 8 so there is at least one leaf per species. The CART-and-convert method then gives us a family of partially interpretable decision trees. The possible trade-offs between coverage and accuracy are shown in Figure 3. With hard concepts, the tree matches the accuracy of the soft CBM at 57% coverage, which means that while not losing any accuracy, we can provide a full explanation for well over half of the data. Figure 4 shows an image on which the tree predicts and Appendix § 12.§ 6 an image on which the tree defers.
Figure 3. CUB-200, 200-way species. We represent the different accuracy-coverage tradeoffs obtained by our hybrid models.
Figure 4. The output of the hybrid model on one image. The tree does not defer, so this path is the whole explanation: any image whose concepts follow the same path gets the same prediction.
Conclusion
We found all three proposed algorithms to have similar performance in experiments on real-world data. CART-and-convert has the advantage that it works with off-the-shelf CART software. At the extra effort of modifying standard CART, PI-CART has the same computational cost and can, in principle, have an advantage if the accuracy of the black box is inhomogeneous across the domain. PI-Branches is the method of choice on datasets where greedy splitting fails (such as parity-like problems), but it may become computationally infeasible on larger datasets.
Applied to concept bottleneck models, we showed that partially interpretable trees can provide an alternative to two-layer neural networks with a large number of parameters.
Limitations and future work Our bound and the PIM-entropy criterion are stated for binary classification, and the bound becomes vacuous when the black box is strongly inhomogeneous. Natural next steps are to estimate the inhomogeneity from data to decide when deferral-aware splitting is worthwhile and extend our criterion and analysis to multi-class problems. Finally, the application of partially interpretable trees in concept bottleneck models looks very promising, and deserves a systematic study across more benchmarks.
Acknowledgements
Schwartz, Berton and Van Erven were all supported by the Netherlands Organization for Scientific Research (NWO) under grant ID https://doi.org/10.61686/OWREN85146.
AI Use Statement
We used Claude Code with various versions of the Opus and Fable models between February and October 2026.
The algorithms in § 3 were designed without the use of AI.
Theorem 2 was derived with the help of AI. Lemma 1 was proved entirely without AI assistance. Their write-ups in the paper (statements and proofs) were written by hand.
For the experiments, the methods were implemented by AI, which was also used to provide feedback on research methodology and experimental setup, and to write the data-preprocessing code, which applies only the preprocessing described in Appendix § 12.§ 1. We checked the AI-written code in several ways. The authors reviewed the data-preprocessing pipeline, the implementation of every method and the code of every experiment as well as the diff between our implementation of PI-Branches and the original Branches solver. Each result in the paper is produced in two stages: one script computes and stores the results, and another generates the table or figure from the stored results. Each script has a limited scope and was reviewed individually.
The paper was mostly written without AI, but some parts were initially drafted by AI and then rewritten: Sections 1–4 were written without AI. Section 5 was drafted with AI, but then fully rewritten by hand. Appendix § 9.§ 1 was written by hand; Appendix § 9.§ 2 was initially drafted by AI, but then rewritten. Appendix § 10.§ 1 was drafted by AI and then rewritten. Appendices § 10.§ 2 and § 10.§ 3 were written without AI. Appendix § 11.1.1 was written by hand. The remaining parts of Appendix § 12 were drafted by AI and then rewritten.
The figures in the paper were all produced with AI, and AI was used for proofreading. AI was also used to identify additional related literature. Every suggested reference was read and verified by the authors, and the bibliography was compiled manually.
We have carefully reviewed all AI-assisted work. The conclusions presented here are our own. We take responsibility for the final content of this work, including text, claims, or artifacts produced with the aid of AI.
Supplement to Section 2
Potential Suboptimality of Lagrangian Optimization
To illustrate which Pareto optimal solutions are not solutions to any LP, consider the example plot in Figure 5. It was obtained by exhaustive search over all datasets of size with two binary features to maximize the suboptimality . The points obtainable as the solutions to the LP for some value of are the ones that sit on the lower boundary of the convex hull of the Pareto frontier, so the Pareto-optimal open circle point cannot be a solution to the LP. To see this, let be the value of the LP at . Then all solutions to the LP for this must lie on the line . But this line must also be a supporting line of the Pareto frontier: if there was a Pareto optimal point strictly below the line, then we could move it down by decreasing and find a better solution to the LP. It follows that all solutions to any LP sit on the lower convex hull of the Pareto frontier. In the figure, this means that (only) the filled blue points are obtainable as solutions to the LP for some value of , but the open circle point is not. If we set a strict upper bound on the uncoverage, then the resulting suboptimality of the empirical risk for the best point obtainable as the solution to an LP can be significant: it is possible to construct a dataset with points that has a gap of (Appendix § 9.§ 2), and the figure shows its case , which gives . For many randomly generated datasets the suboptimality appears to be much smaller or even non-existent, though. Pragmatically, it is therefore still reasonable to optimize for the LP when the CP is computationally infeasible.

Figure 5. Empirical risk against empirical uncoverage for all Pareto optimal in a class of decision stumps (depth one trees) on a toy dataset of points with binary features, where is perfect on deferred points. The orange open circle point lies strictly above the lower boundary of the convex hull of the frontier, so it is not a solution of the LP for any , even though it solves the CP for . The best LP solution with has empirical risk larger by .
A Family Whose Gap Approaches 1/4
Figure 5 shows a dataset on which the gap between the Lagrangian and the constrained solutions is significant (). By adding more points to it, we can widen this gap up to . We use two binary features and , so a dataset is fully described by how many points of each label fall into each of the four combinations of . For , let the dataset have the following counts: So , and is the dataset of Figure 5. The labels are noiseless: exactly when , which decision stumps of depth 1 cannot represent.
Table 7 (PDF p. 13).
Let be the stumps on or , each branch either predicting its majority label or deferring to , with perfect on deferred points. Splitting on , the branch holds points labeled 1 and labeled 0: it has points, its majority label is 0 and it misclassifies points. The branch holds of each label: it has points and misclassifies whichever label it predicts. Splitting on is symmetric. The four ways to resolve the two branches give, in counts ,
, predict both; , defer ; , defer ; , defer both
and these four are exactly the Pareto-optimal points of on .
The suboptimality gap The lower convex hull of the frontier has vertices , and : the segment between the first two has slope and passes through height at , so the second Pareto point lies strictly above it. By the supporting-line argument of Appendix § 9.§ 1 it therefore solves no LP, for any .
Now constrain the uncoverage to . The constrained problem attains at that very point. Every Lagrangian solution is a hull vertex, and the only one with is , of risk . The penalty for restricting to Lagrangian solutions is thus
Supplement to Section 3
The Branches and PI-Branches Algorithms
We describe the full Branches and PI-Branches algorithms. Algorithm 1 is Branches as described by Chaouki et al. [6], with every line that PI-Branches changes or adds set in bold teal; the other lines are common to both. Running the algorithm with the highlighted lines removed, or equivalently with and absent, recovers Branches exactly.
Notation and the dynamic program Throughout this section we consider features . A branch is a conjunction of clauses on the features of the form
where is the number of clauses. For any data point , the valuation of at is defined by
One should think of a branch as a potential path in a decision tree, and the valuation of a data point in that branch is 1 if that data point would have followed that path. We define the number of points in as . We define the predicted class in as
where is the number of data points in that are of class . So is the majority class in , and the fraction of the points of that it misclassifies is the error rate
To compute an optimal decision tree Branches considers a dynamic programming approach. At a branch the algorithm chooses an action : either the terminal action , which stops the branch and makes it a leaf, or a split action, which adds a split and replaces by its two children. The search maintains a state-value for the branch and a state-action value for each action available at it. These are estimates, refined as the search proceeds; we write and for the optimal values they bound.
In particular, we need to be able to evaluate the terminal action. Stopping at makes a mistake on every point of not of the majority class, so
the fraction of the whole sample that misclassifies. It is exact because stopping leaves no further decision to make.
For a split action , the loss decomposes over the two children the split creates, and the Bellman equation suggests the recursive definition
where ranges over the two children of under . This determines only once the children have been evaluated, so the recursion has to be started somewhere: is initialized by a bound at the branches the search chooses to expand, and backpropagated through (9) thereafter.
For the terminal action we have the exact value. For a split action, the best case scenario is that every point is correctly classified after the split and we only pay the splitting cost . This gives the Purification Bound of [6],
a lower bound on , the loss of the best subtree rooted at . When no split action remains, because already uses every feature or has reached the maximum depth, the bound is exact and .
In particular, when the terminal value satisfies , stopping is optimal and the branch is closed needing no further exploration.
Extending Branches to our framework requires two ingredients. First when evaluating the value of a leaf, one must consider the possibility of deferring. A deferring leaf makes the black box’s mistakes instead of the tree’s, and pays for each of its points. Writing for the number of points of that the black box classifies correctly, the leaf takes whichever action is cheaper. That gives the terminal value of PI-Branches,
which replaces . Deferring is chosen exactly when . Second, the heuristic. The Purification Bound keeps its form,
and remains a valid lower bound (see the paragraph after Algorithm 1). is backpropagated through (9) exactly as is.
The full algorithm is Algorithm 1 below. Only the leaf evaluation changes (lines 3–5): with the highlighted lines, and are the and of (11) and (12).
Values Everything below is a loss, matching the minimization of § 3. A tree costs . All losses are normalized by the total sample size , not by , so that the contributions of sibling leaves add. (The implementation maximizes the equivalent reward ; the two differ only in sign.) Each branch carries
, the exact loss of stopping at ;
, an optimistic lower bound on the loss of the best subtree rooted at , used to order the search;
, the loss of the best subtree actually found so far, an upper bound, used to pick which sibling to descend into;
a priority queue over attributes, a flag TERMINAL (stopping is provably optimal here) and a flag COMPLETE (the optimum below is proved).
The search ends when the root is COMPLETE; the returned tree is then optimal for the objective. Capping the depth or the iteration budget forfeits that guarantee, and the algorithm returns the best tree found instead.
Algorithm 1 Branches, with the PI-Branches differences in bold teal
Require: data , complexity penalty , maximum depth , iteration budget
Require: [PI] black box predictions , deferral price
Ensure: a tree
function EvaluateTerminal
if else
end function
function Evaluate
EvaluateTerminal
if has an unused attribute and then
Purification Bound
if then
mark TERMINAL and COMPLETE stopping is provably optimal
end if
else
; mark TERMINAL and COMPLETE
end if
end function
function Split
for do
, with , and obtained from the parent’s counts
Evaluate
end for
push on ’s queue with key smallest key first
end function
function Select
root;
while has children and is not COMPLETE do
head of ’s queue
the child of under with the largest the least settled sibling
append to $path
32: end while
33: return l, path
34: end function
35: function Expand(l)
36: for each attribute a unused on l do
37: Split(l, a)
38: end for
39: $\mathcal{V}(l) \leftarrow \min \{ Q(l,\bar{a}),\ \gamma + \min_a \bigl(\mathcal{V}(l_0^a) + \mathcal{V}(l_1^a)\bigr) \}$
40: if $\mathcal{V}(l) = Q(l,\bar{a})$ then
41: mark l terminal and complete
42: else if every child under the best attribute is complete then
43: mark l complete
44: end if
45: end function
46: function Backpropagate(path)
47: for l from the parent of the selected branch up to the root do
48: discard the complete children from l’s queue, folding their values into the key
49: $a^*(l) \leftarrow \arg\min_a \bigl(\gamma + \mathcal{V}_g(l_0^a) + \mathcal{V}_g(l_1^a)\bigr);\ \mathcal{V}_g(l) \leftarrow \min \{Q(l,\bar{a}),\ \gamma + \mathcal{V}_g(l_0^{a^*}) + \mathcal{V}_g(l_1^{a^*})\}$
50: $\mathcal{V}(l) \leftarrow \min \{Q(l,\bar{a}),\ \gamma + \min_a \bigl(\mathcal{V}(l_0^a) + \mathcal{V}(l_1^a)\bigr)\}$
51: if $\mathcal{V}(l) = Q(l,\bar{a})$ then
52: mark l terminal and complete
53: else if every child under the best attribute is complete then
54: mark l complete
55: end if
56: end for
57: end function
Main loop
58: root $\leftarrow$ the empty conjunction; Evaluate(root); Expand(root)
59: for i = 1 to N do
60: if root is complete then
61: break ▷ the optimum is proved
62: end if
63: l, path $\leftarrow$ Select()
64: sib $\leftarrow$ the sibling of l under its parent’s best attribute
65: if l is not complete then
66: Expand(l)
67: end if
68: if sib is neither complete nor expanded then
69: Expand(sib)
70: end if
71: Backpropagate(path)
72: end for
73: $\mathcal{L} \leftarrow$ the branches reached by following $a^*$ from the root to a terminal branch
74: return $T = (\mathcal{L}, \sigma)$ ▷ $\sigma(l) = \bot$ on the deferring leaves
Why the optimistic bound is still valid under deferral Line 10 bounds the loss of any subtree rooted at from below by : a subtree with more than one leaf pays for at least one split, and in the best case makes no mistakes at all. Deferring cannot lower that floor, because by line 4 the loss of a leaf is non-negative whichever action it takes: the deferring alternative is for every , a count of mistakes plus a non-negative price, and it is zero only when the black box is perfect on and . The bound is therefore admissible for PI-Branches as it stands, which is why the search remains exact and why no line of Evaluate outside the leaf value had to change.
Cost The lattice of branches is shared: two paths with the same set of clauses in a different order are the same node, which is what makes the search tractable at all. Memory is nonetheless the binding constraint in our experiments rather than time, and it grows with the number of binary attributes. On the two largest datasets of § 5.1, mushroom and ficobin, the search exhausted the available memory before proving optimality; we report those datasets as incomplete, there is no optimality guarantee on those.
The Knapsack Formulation of CART-and-convert
§ 3.2 reduces the constrained conversion of a fixed tree to a 0/1 knapsack whose items are the leaves, a leaf being included exactly when the tree defers on it. The weights and values are as follows.
The weight of each leaf is , where is the number of data points in , so the sum of the weights for leaves that are included in the knapsack should not exceed .2 The value of each leaf is , which is the reduction in empirical risk by deferring for the leaf. Although knapsack problems are NP-hard in general, in our setting the number of leaves is typically small enough that the knapsack can be solved exactly by standard knapsack solvers.
The Proof of Lemma 1
Lemma 1. Let and let be a leaf containing at least one data point. The PIM-entropy has the closed form
where
and and are, respectively, the larger roots of the following quadratics:
The condition has a simple interpretation. If , then , where is Youden’s index of on : its true positive rate minus its false positive rate. Hence the minimizing defers with positive probability exactly when , that is, when the black box is informative enough on compared to the cost of deferring; otherwise and the PIM-entropy reduces to the usual entropy . Intuitively, the criterion therefore favors splits that separate regions where is informative from regions where it is not.
Proof sketch. The proof proceeds in three steps. First, writing and , so that , straightforward computations show that the objective function equals , to be minimized over with . Next, we can compute directly the unconstrained solution , which exists because each term of the objective either vanishes identically or tends to at the boundary, and is unique by strict convexity. Finally, we distinguish two cases according to the sign of . If , then , so is feasible and hence optimal: the leaf defers with positive probability. If , a convexity argument shows that the constrained minimizer satisfies . Then the leaf never defers, and the minimum equals the entropy , i.e. the splitting criterion of standard CART. This argument assumes that certain sums of the are nonzero; the degenerate cases follow from the same steps with minor modifications.
Complete proof. We follow the steps outlined in the sketch above. First, writing and , so that , we have
We denote the space of feasible solutions by . Consequently, the minimization problem becomes:
Next, observe that is strictly convex if , i.e. classifies at least one point of with the label 1, while otherwise is a decreasing linear function. Similarly, is strictly convex if , or equivalently predicts 0 on at least one data point of , and otherwise. These properties will be used several times. Furthermore, attains its minimum both on and on . Indeed, with the convention , each term of either vanishes or tends to as its argument tends to 0, so is continuous with values in . Since is finite in the interior, it attains its minimum on every compact set, in particular on and on . Moreover, the minimizer over is unique, since, by the properties above, and each have a unique minimizer on . We then define:
Next, we show that either these two minimizers coincide or the minimizer over lies on the diagonal . This follows from the fact that, as mentioned previously, and are strictly convex or decreasing linear functions. Indeed, suppose for contradiction that and . By continuity, there exists such that the point
satisfies . Then, strict convexity gives the contradiction:
where the first inequality is strict because , one lying in and the other not. In the degenerate case in which or is linear, the conclusion is immediate, since is then strictly decreasing in or , and so any minimizer over must satisfy . We denote by the minimizer of restricted to the diagonal.
We then proceed to compute and explicitly. Starting from , we first note that the derivatives of and can be written as
In particular, on , and have the same sign as and , respectively. Now, is an upward parabola with and , so its smaller root is non-positive and its larger root lies in . Hence on and on , so is decreasing on and increasing on , which gives .
The same argument applied to , with and , shows that is the larger root of .
The computation of is simpler. Recalling that , at a point of the diagonal we have
where is the binary cross-entropy, which is minimized when its second argument equals , that is, at . Hence , and , as stated in the lemma.
It remains to show that the condition that determines which of and is the minimizer over is exactly . First, note that:
Similarly, one can show that:
This allows us to set
Moreover, since the smaller roots of and are non-positive, for every we have if and only if , and if and only if . Hence
Similarly:
In the first case, is the minimizer over , which gives . In the second case, either , and the minimizer is by the previous steps, or , which forces ; in both cases .
Supplement to Section 4
Further Background for Section 4
Details for the Example in Figure 1
Here we provide the details for the example shown in Figure 1. The figure shows the case where corresponds to the partitions that can be generated by decision trees of depth at most 2. There is a single feature that is uniformly distributed on , and for the function that alternates between 1 and 0 as shown in Figure 6. The black box is perfect, so . We take the tree to be as shown in Figure 7. We assume the conversion exactly minimizes the Lagrangian objective, so . This defers the leaves one at a time in decreasing order of their error rates as decreases.
Figure 6. The function in the example of Figure 1

Figure 7. The tree in the example of Figure 1. Each leaf shows its interval, the majority label predicted there, and the error rate of that label.
Deferred Proofs from Section 4
Lemma 3. For any , there exists (with a subgradient of at ) such that
Proof. Recall the model class from the definition of .
Now first suppose a subgradient of exists at some , and abbreviate . Then, by definition, for as defined in (6). Taking , it follows that
Hence, by the definition of subgradients,
In addition,
Subtracting the two inequalities gives
which is the conclusion of the lemma.
It remains to establish existence of a subgradient of at any . To this end, observe that and hence are finite, because there are only finitely many possible functions from to . It follows that is a polytope.
Let be the interval obtained by projecting onto its first coordinate. Then, in fact, , which may be seen as follows: From (5), we have that
where the last inequality follows by taking , a function that never defers, and using that . Since there are only finitely many possible functions , it follows that can only take finitely many different values when varying , and therefore (13) implies that for all sufficiently large . Consequently, includes a point for some , which means that .
Let
be the lower boundary of , defined for . Then, since is a polytope, is convex and piecewise linear with a finite number of pieces. By definition,
which implies that for and for , where is a minimizer of . Consequently, is also convex and piecewise linear with a finite number of pieces. It follows that has at least one subgradient at any point , which equals the slope of a linear piece that contains . Since is non-increasing, this slope will equal for some , which remained to be shown.
Lemma 4. For any ,
Proof. We start by showing that
The first inequality is (5). The second follows because
and simultaneously we can upper bound the minimum by the that always defers, which gives
We proceed to find a lower bound for . For readability, abbreviate
Then
Since , we have
Furthermore,
which expresses that, even without deferring, the majority vote already achieves error at most . It follows that
which shows that the oracle’s gain from deferring is at most a factor compared to the best possible labeling without deferring. Combining these inequalities, we find that
All together,
where the last equality follows because the function is linear and non-decreasing in for , linear and non-increasing on and constant on , which implies that it is maximized at . (We have used here that .)
Supplement to Section 5
Datasets
Our experiments run on four families of data. Two are built from public tabular benchmarks used by the work we compare against, so that neither comparison is run on ground of our own choosing: the branch track of § 5.1 uses a composite benchmark combining datasets from Chaouki et al. [6] and Frost et al. [12], and the conversion and decision-list tracks of Appendices § 12.§ 3 and § 12.§ 4 use that of Frost et al. [12]. The third is a synthetic generator that stipulates the selective competence the method is supposed to exploit, and the fourth is a concept bottleneck, where the interpretable features are themselves predicted.
All tabular data is public. The two tracks draw on the UCI repository, OpenML [31], the LIBSVM collection [5], ustunb/risk-slim, ProPublica’s compas-analysis, the preprocessed binary files distributed with Branches, and the dataset collection of Lin et al. [22]. The UCI datasets are released under CC BY 4.0 and the OpenML ones are marked public; the risk-slim data is BSD-3-Clause and the Branches code MIT. CUB-200-2011 is restricted to non-commercial research and educational use. ProPublica’s COMPAS data and the FICO HELOC data come without a stated open licence and are used here, as in prior work, for research only.
Comparison of the three methods § 5.1 relies on the 20 datasets listed in Table 2. Numeric columns are binarized at their median and categorical ones are dummy-encoded (one indicator per category but the last); the medians are computed on the training split for the six datasets below and on the full dataset, which uses no labels, for the others. Each dataset is split once, so that all methods, including the expensive exact search, are compared on the same data. The split is a stratified 70/30 at a fixed seed, and the black box is a 100-tree random forest trained on the binarized features, except on the six datasets this track shares with the conversion track — diabetes, ficobin, heart_statlog, ionosphere, mushroom and spambase — where the conversion track’s own cached black box and 80/20 split are reused instead, so the two tracks defer to the same black box wherever they overlap. For the greedy methods, the grown tree is pruned as in § 3.2, with , separately for each ; Theorem 2, in contrast, analyzes the conversion of a single fixed partition.
The benchmark is deliberately heterogeneous in difficulty, and that matters for how the results are read. Several datasets are degenerate for our purposes: the three MONK problems are constructed, parity-like concepts on which greedy splitting is known to fail, so they favor exact search by construction, which is why Table 1 excludes them. Others are severely imbalanced (sick at 6.1% positive, pc1 at 6.9%), where a constant predictor is already strong and there is correspondingly little for deferral to buy.
Two of the twenty are listed for completeness but carry no result: exact search runs out of memory on mushroom and ficobin, the two largest datasets of the track, so neither enters the averages of Table 1. Appendix § 12.7 still reports the greedy criteria on them. Removing these two and the three MONK problems leaves the 15 datasets over which § 5.1 averages.
Comparison with decision lists and cost of the Lagrangian relaxation A comparison between decision-list and decision tree is run in Appendix § 12.§ 4, and an estimation of the cost of the Lagrangian relaxation is done in Appendix § 12.§ 3. Both use the same datasets as the original comparison from Frost et al. [12]. Those datasets and their description are in Table 2.
Synthetic dataset Appendix § 12.§ 2 uses a synthetic dataset generator. Each draw is 2,000 rows over 13 binary features: an indicator and 12 noisy copies of a hidden class , each flipped with probability 0.35. The label is flipped with probability 0.25. The black box is correct wherever and predicts at random where , with balanced and independent of . Because is a feature, a tree can isolate the region where the black box is accurate. The split and tree settings are those of § 5.1, and results are averaged over ten draws.
CUB-200 § 5.2 uses CUB-200-2011 ([32]): 11,788 photographs of birds labeled with 200 species, with the standard 112-attribute concept mask of [20]. We split it 4,794/1,200/5,794 into train, validation and test. Unlike every other dataset here the interpretable features are not given: both the 112 concepts and the 200-way reference model are predicted by separately fine-tuned Inception v3 networks, so the tree reads estimated concepts and a path can be wrong about the bird even when its answer is right. Following Havasi et al. [14] the pipeline starts from a 299 × 299 image. The baseline CBM’s label head is a two-layer network with 200 hidden units, about 60k parameters, against the 22.2 million of the Inception v3 that predicts the species directly from pixels.
Computing infrastructure The greedy methods and the conversion and decision-list experiments ran on a laptop CPU (Intel Core i7-10510U, 16 GB of RAM), and the CUB networks were fine-tuned on an NVIDIA RTX 5070 Ti Laptop GPU (12 GB). PI-Branches ran on the CPU nodes (AMD EPYC) of a national HPC cluster, with 16 cores and up to 28 GB of memory per dataset, for about two hours each.
A Synthetic Dataset Where Deferral-Aware Splitting Does Help
The comparison in § 5.1 shows that on real data PI-CART and PI-Branches do not outperform CART-and-convert. This is consistent with Theorem 2, which bounds the gain of any tree learning algorithm over conversion when the accuracy of the black box is homogeneous across the domain, something that we observe in real data. We propose a synthetic dataset in which the accuracy of the black box is deliberately inhomogeneous.
The dataset is generated as follows. A hidden class is drawn uniformly, and the tree sees 12 binary features, each equal to flipped independently with probability 0.35, plus a balanced indicator , independent of . The label is flipped with probability 0.25. The black box is correct wherever and predicts at random where : on one half of the domain it has the information behind the label noise, which the tree does not. Since carries no information about the label, a criterion that only looks at labels has no reason to split on it, while a tree that does split on can defer exactly where the black box is accurate. All methods use the protocol of § 5.1 (a 70/30 split, maximum depth 10, , 20 values of ), and results are averaged over 10 draws.
As Figure 8 shows, both PI-Branches and PI-CART are able to exploit the structure of the problem and significantly outperform CART-and-convert. This means that deferral-aware splitting might be useful in some settings (even though we have not found them in real data yet) and that our theorem correctly identifies that homogeneity of the black box accuracy drives the gap between deferral-aware splitting and conversion.
Figure 8. Coverage/accuracy on the held-out split of the synthetic dataset: best accuracy at coverage at least , averaged over 10 draws, with a band of one standard error. The dotted line is the black box alone.
Converting a Tree: How Much Does the Lagrangian Relaxation Cost?
Figure 5 shows that the Lagrangian relaxation can miss some optimal coverage/accuracy trade-offs. We measure the difference between the Lagrangian relaxation and the exact solver on the conversion algorithm. We compare two rules on the same fitted tree: the Lagrangian rule of § 3.2, which defers a leaf when the error rate of on it plus is below the error rate of its majority label, and the exact 0/1 knapsack over cells at each coverage budget. Each is fitted on the training split and applied unchanged to the held-out split, over 13 datasets at depths 2 to 6 with 10 seeds. Figure 9 shows both rules on spambase, and Table 3 summarizes all datasets.
Figure 9. The two conversion rules on spambase at depth 6, held-out split, mean over 10 seeds with standard-error bands. The black box is refit on each seed’s split, so its accuracy differs slightly from the single split of Table 2.
An External Baseline: Partially Interpretable Decision Lists
Frost et al. [12] study the same predict-or-defer setting with a different interpretable class: a decision list that applies its rules in order and defers whatever no rule covers. Their Appendix C.5 compares that list against a decision-tree baseline built the same way ours is — fit the tree, then hand the weak leaves to the black box.
Their comparison reports one operating point per method, the largest model whose validation error stays within 0.005 of the black box’s, and tabulates its accuracy and its coverage. Because the rule fixes an error budget rather than a coverage, the two methods are read at different coverages, and the two axes can disagree: on spambase their list is slightly less accurate but covers considerably more. A single point also says nothing about the rest of either method’s frontier.
We therefore run the comparison on the whole frontier instead. Both classes are swept over the full range of deferral budgets and scored at matched coverage, so every comparison is one-dimensional: at the same fraction of the data explained, which model is more accurate? We are also deliberately generous to the baseline on both sides. The tree’s hyperparameters come from a cross-validated grid search, and its leaves defer by the Lagrangian rule of § 3.2; the list’s own and rule count are re-selected by cross-validation on every split.
Figure 10 shows the frontiers on spambase, and Table 4 gives the head-to-head on every dataset of the benchmark, over 10 redrawn splits. Read this way the two classes come out close to indistinguishable. On the four datasets large enough to resolve a difference — adult, bank, bank2 and ficobin, from 10,459 to 41,188 rows — no comparison exceeds 0.4 points in either direction, and on ficobin none exceeds 0.05. The aggregate differences of −0.61 to −0.96 points are carried entirely by the small datasets, where the standard errors are 1.3 to 1.8 and the per-dataset winner rotates.
Figure 10. The decision list against the three tree criteria on spambase, over 10 redrawn splits; lines are mean envelopes and bands one standard error. Note the vertical scale: all four lie within 1.5 points of each other across the whole range. The black box is refit on each split, so its accuracy differs slightly from the single split of Table 2.
| dataset | list | list − tree | ||
| adult | 83.85 | +0.02 | +0.03 | +0.05 |
| bank | 90.06 | +0.01 | +0.01 | +0.02 |
| bank2 | 91.34 | −0.40 | −0.38 | −0.32 |
| breastcancer | 95.03 | +0.01 | +0.80 | −0.21 |
| careval | 99.27 | +1.27 | +1.34 | — |
| compasbin | 66.92 | −0.77 | −0.98 | −0.94 |
| diabetes | 72.99 | −1.89 | −1.79 | −1.91 |
| ficobin | 71.79 | +0.05 | +0.00 | −0.04 |
| heart | 76.85 | −3.15 | −5.22 | −4.02 |
| ionosphere | 90.50 | −3.22 | −4.00 | −3.49 |
| mammo | 80.31 | −0.40 | −0.93 | −0.65 |
| mushroom | 99.99 | −0.01 | −0.01 | −0.01 |
| spambase | 94.82 | +0.51 | +0.16 | −0.04 |
| mean | −0.61 | −0.84 | −0.96 | |
| SE |
Table 4. The partially interpretable decision lists of Frost et al. [12] against our trees, datasets × 10 redrawn splits, in points. A negative difference favors the tree. Every method is evaluated at the same set of deferral budgets per split, so the comparison does not reward whichever method happens to produce more candidate models. The average differences favor the trees but come from the small datasets, where the standard errors are large; on the three largest (adult, bank, bank2) every difference is at most 0.4 points. careval has no PI-CART entry (the one multi-class dataset here).
Once both methods are tuned carefully and compared at matched coverage, we find no empirical evidence of a difference between decision lists and trees. Appendix C.5 of Frost et al. [12] reads each method at a single operating point, where the comparison favors the list; over the whole frontier, we do not observe this advantage.
Alternative Scoring Criteria
Every scoring in the main text summarizes the models a method produces over all values of . The aggregate score takes a maximum over the method’s own models at each coverage; the per-threshold columns select one model per budget. Both therefore depend on which models a method happens to produce, and not only on how good they are. We report another scoring method in this appendix with no such dependence.
Each model was fitted to minimize a Lagrangian at a particular , so we can evaluate each model on exactly that quantity, at exactly that :
One model per method per , compared against the others at the same , with no maximization and no selection. Lower is better. This is immune to the three artefacts that affect the other scorings: unequal numbers of candidate models, the resolution of the grid, and padding where no value of reaches full coverage.
We report our results in Table 5.
| dataset | gini | PI-Branches | ent. | pim_ent. |
| banknote | 0.1233 | +0.0000 | +0.0000 | +0.0000 |
| breast_cancer | 0.3229 | +0.0003 | −0.0006 | +0.0232 |
| credit_a | 0.1945 | +0.0000 | +0.0000 | +0.0000 |
| diabetes | 0.2692 | −0.0009 | +0.0000 | +0.0017 |
| ficobin | 0.3019 | — | +0.0000 | −0.0023 |
| german_credit | 0.3449 | +0.0000 | +0.0000 | +0.0270 |
| heart_statlog | 0.2989 | −0.0017 | +0.0000 | −0.0096 |
| hepatitis | 0.2065 | +0.0214 | +0.0000 | +0.0397 |
| ionosphere | 0.1464 | +0.0370 | −0.0125 | +0.0378 |
| monk1 | 0.0944 | −0.0753 | +0.0000 | −0.0083 |
| monk2 | 0.5485 | −0.1429 | +0.0004 | −0.0188 |
| monk3 | 0.0277 | +0.0146 | +0.0000 | +0.0017 |
| mushroom | 0.0132 | — | +0.0000 | +0.0031 |
| pc1 | 0.0691 | +0.0000 | +0.0000 | +0.0000 |
| sick | 0.0616 | +0.0000 | +0.0000 | +0.0000 |
| sonar | 0.3278 | −0.0337 | +0.0168 | −0.0215 |
| spambase | 0.1885 | +0.0020 | +0.0000 | +0.0000 |
| tictactoe | 0.1260 | +0.0168 | +0.0000 | +0.0520 |
| vote | 0.0542 | +0.0000 | +0.0000 | +0.0034 |
| wdbc | 0.0582 | +0.0104 | +0.0000 | +0.0068 |
| mean, 18 complete | 0.1924 | −0.0084 | +0.0002 | +0.0075 |
| mean, 18 complete (train) | 0.1138 | −0.0115 | −0.0010 | +0.0061 |
| mean, 15 ex-MONK | 0.1861 | +0.0034 | +0.0002 | +0.0107 |
| mean, 15 ex-MONK (train) | 0.1178 | −0.0046 | +0.0002 | +0.0083 |
Table 5. PIM loss on the 20 datasets, averaged over the 20 values of ; lower is better.
The ordering differs from the aggregate score, and both differences are small. We draw the same conclusion as in § 5.1: on this benchmark the four procedures perform very similarly. Being a greedy surrogate, PI-CART does not minimize the Lagrangian objective directly, and on this benchmark it does not reach a lower training value than CART-and-convert.
An Image the Rule Defers
In Figure 4, we present an image of a bird that is not deferred by our depth-8 tree. In Figure 11, we additionally provide an image of a similar bird on which the tree will defer: their concepts agree on the first four nodes of the tree, and they diverge at back color = grey.
Figure 11. Output of the partially interpretable decision tree on two Kingfisher birds. The tree predicts the class of the bird on the left and defers the prediction of the bird on the right to the blackbox model.
Per-Dataset Results
We report average scores over datasets in Table 1. Table 6 gives the scores for each dataset. Since PI-Branches performs exact search, it gives us a lower bound on the training objective wherever it proves optimality, which it does for every on 13 of the 18 datasets on which it terminates; the opt. column of Table 6 counts, for each dataset, the values of on which optimality was proved.
References
- [1]Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo I. Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18:234:1–234:78, 2017.arxiv.org/abs/1704.01701
- [2]Peter L. Bartlett and Marten H. Wegkamp. Classification with a reject option using a hinge loss. Journal of Machine Learning Research, 9:1823–1840, 2008.DOI
- [3]Leo Breiman, J. H. Friedman, Richard A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984. ISBN 0-534-98053-8.DOI
- [4]Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen. A theory of interpretable approximations. In The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pages 648–668. PMLR, 2024.arxiv.org/abs/2406.10529
- [5]Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27:1–27:27, 2011. doi: 10.1145/1961189.1961199.DOI
- [6]Ayman Chaouki, Jesse Read, and Albert Bifet. Branches: Efficiently seeking optimal sparse decision trees via AO*. In Forty-Second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025. OpenReview.net, 2025.
- [7]C. K. Chow. On optimum recognition error and reject tradeoff. IEEE Transactions on Information Theory, 16(1):41–46, 1970. doi: 10.1109/TIT.1970.1054406.DOI
- [8]Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In Algorithmic Learning Theory - 27th International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings, volume 9925 of Lecture Notes in Computer Science, pages 67–82. Springer, 2016. doi: 10.1007/978-3-319-46379-7_5.DOI
- [9]Mark W. Craven and Jude W. Shavlik. Using sampling and queries to extract rules from trained neural networks. In Machine Learning, Proceedings of the Eleventh International Conference, Rutgers University, New Brunswick, NJ, USA, July 10-13, 1994, pages 37–45. Morgan Kaufmann, 1994. doi: 10.1016/B978-1-55860-335-6.50013-1.DOI
- [10]Mark W. Craven and Jude W. Shavlik. Extracting tree-structured representations of trained networks. In Advances in Neural Information Processing Systems 8: Annual Conference on Neural Information Processing Systems 1995, NeurIPS 1995, Denver, CO, USA, November 27-30, 1995, pages 24–30. MIT Press, 1995.
- [11]Julien Ferry, Gabriel Laberge, and Ulrich Ävodji. Learning hybrid interpretable models: Theory, taxonomy, and methods. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https://openreview.net/forum?id=XzaSGIstXP.arxiv.org/abs/2303.04437
- [12]Nave Frost, Zachary C. Lipton, Yishay Mansour, and Michal Moshkovitz. Partially interpretable models with guarantees on coverage and accuracy. In International Conference on Algorithmic Learning Theory, 25-28 February 2024, La Jolla, California, USA, volume 237 of Proceedings of Machine Learning Research, pages 590–613. PMLR, 2024.
- [13]Tessa Han, Suraj Srinivas, and Himabindu Lakkaraju. Which explanation should I choose? A function approximation perspective to characterizing post hoc explanations. In Advances in Neural Information Processing Systems, volume 35, pages 5256–5268, 2022. URL https://proceedings.neurips.cc/paper_files/paper/2022/file/22b118194c7453837899689166c4cf9-Paper-Conference.pdf.
- [14]Marton Havasi, Sonali Parbhoo, and Finale Doshi-Velez. Addressing leakage in concept bottleneck models. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.DOI
- [15]Thomas Hofmann, Bernhard Schölkopf, and Alexander J. Smola. Kernel methods in machine learning. The Annals of Statistics, 36(3):1171–1220, 2008. doi: 10.1214/009053607000000677. URL https://doi.org/10.1214/009053607000000677.
- [16]Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359–366, 1989. ISSN 0893-6080. doi: 10.1016/0893-6080(89)90020-8. URL https://www.sciencedirect.com/science/article/pii/0893608089900208.DOI
- [17]Laurent Hyafil and Ronald L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1):15–17, 1976.DOI
- [18]Michael J. Kearns and Yishay Mansour. On the boosting ability of top-down decision tree learning algorithms. Journal of Computer and System Sciences, 58(1):109–128, 1999. doi: 10.1006/jcss.1997.1543.DOI
- [19]Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer Berlin, Heidelberg, 2004. doi: 10.1007/978-3-540-24777-7.DOI
- [20]Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5338–5348. PMLR, 2020.
- [21]Himabindu Lakkaraju, Ece Kamar, Rich Caruana, and Jure Leskovec. Interpretable & explorable approximations of black box models. ArXiv:1707.01154, 2017.arxiv.org/abs/1707.01154
- [22]Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo I. Seltzer. Generalized and scalable optimal sparse decision trees. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6150–6160. PMLR, 2020.arxiv.org/abs/2006.08690
- [23]Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 4765–4774, 2017.arxiv.org/abs/1705.07874
- [24]David Madras, Toniann Pitassi, and Richard S. Zemel. Predict responsibly: Improving fairness and accuracy by learning to defer. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6150–6160, 2018.arxiv.org/abs/1711.06664
- [25]Hussein Mozannar and David A. Sontag. Consistent estimators for learning to defer to an expert. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7076–7087. PMLR, 2020.arxiv.org/abs/2006.01862
- [26]Danqing Pan, Tong Wang, and Satoshi Hara. Interpretable companions for black-box models. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 2444–2454. PMLR, 2020.arxiv.org/abs/2002.03494
- [27]Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. “Why should I trust you?”: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pages 1135–1144, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342322. doi: 10.1145/2939672.2939778. URL https://doi.org/10.1145/2939672.2939778.
- [28]Ronald L. Rivest. Learning decision lists. Machine Learning, 2(3):229–246, 1987. doi: 10.1007/BF00058680.
- [29]Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. SmoothGrad: Removing noise by adding noise. ArXiv:1706.03825, 2017.arxiv.org/abs/1706.03825
- [30]Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3319–3328. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/sundararajan17a.html.arxiv.org/abs/1703.01365
- [31]Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luís Torgo. OpenML: Networked science in machine learning. CoRR, abs/1407.7722, 2014. doi: 10.48550/arXiv.1407.7722.
- [32]Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge J. Belongie. Caltech-UCSD Birds-200-2011, 2025.DOI
- [33]Tong Wang and Qihang Lin. Hybrid predictive models: When an interpretable model collaborates with a black-box model. Journal of Machine Learning Research, 22:137:1–137:38, 2021.








