Sparse decision trees are one of the most common forms of interpretable models. While recent advances have produced algorithms that fully optimize sparse decision trees for prediction, that work does not address policy design, because the algorithms cannot handle weighted data samples. Specifically, they rely on the discreteness of the loss function, which means real-valued weights cannot be directly used. For example, none of the existing techniques produce policies that incorporate inverse propensity weighting on individual data points. We present three algorithms for ecfiient sparse weighted decision tree optimization. The first approach directly optimizes the weighted loss function but is computationally ineficient. Our second approach scales better by transforming weights to integer values and using data duplication to transform the weighted decision tree optimization problem into an unweighted, but larger, counterpart. Our third algorithm, which scales to much larger datasets, uses a randomized procedure that samples each data point with a probability proportional to its weight. We present theoretical bounds on the error of the two fast methods and show experimentally that these methods can be two orders of magnitude faster than the direct optimization of the weighted loss, without losing significant accuracy.
disease could be diferent. To create an optimal policy, we weight the loss from each patient and minimize the Sparse decision trees are a leading class of interpretable sum of the weighted losses. While it is possible to conmachine learning models that are commonly used for pol- struct a model using CART’s suboptimal greedy splitting icy decisions [e.g., 1, 2, 3]. Historically, decision tree opti- procedure [5], the current fastest optimal decision tree mization has involved greedy tree induction, where trees method, GOSDT [14], does not support this approach. are built from the top down [4, 5, 6], but more recently We extend the framework of GOSDT-withthere have been several approaches that fully optimize Guesses [13] to support weighted samples. GOSDTsparse trees to yield the best combination of performance with-Guesses produces sparse decision trees with and interpretability [7, 8, 9, 10]. Optimization of sparse closeness-to-optimality guarantees in seconds or optimal trees is NP-hard, and recent work has leveraged minutes for most datasets; we refer to this algorithm as the fact that the loss takes on a discrete number of val- GOSDTwG. Our work introduces three approaches to ues to provide a computational advantage [11, 12, 13, 14]. allow weighted samples.
However, if one were to try to create a policy tree or esti- A key contributor to GOSDTwG’s performance is its mate causal efects using one of these algorithms, it would use of bitvectors to compute the loss function. However, become immediately apparent that such algorithms are introducing weights requires multiplying the weights by not able to handle weighted data, because the weights this bitvector representation, which introduces a runtime do not come in a small number of discrete values. This penalty of one to two orders of magnitude. We demonmeans that common weighting schemes, such as inverse strate this efect in our first approach. Our second appropensity weighting or simply weighting some samples proach introduces a normalization and data duplication more than others [15, 16], are not directly possible with technique to mitigate the slowdown due to real-valued these algorithms. weights. Here, we transform the weights to small integer
For example, consider developing a decision tree for values and then duplicate each sample by its transformed describing medical treatment regimes. Here, the cost weight. Our third approach, which scales to much larger for misclassification of patients in diferent stages of the sample sizes, uses a stochastic procedure, where we sample each data point with a probability proportional to its Advances in Interpretable Machine Learning and Artificial Intelligence weight. Our experimental results show that: (1) the sec’AIMLAI, October 21, 2022, Atlanta, GA $ alibez@cs.ubc.ca (A. Behrouz); mathias.lecuyer@ubc.ca ond and third techniques decrease run time by up to two (M. Lécuyer); cynthia@cs.duke.edu (C. Rudin); mseltzer@cs.ubc.ca orders of magnitude relative to that achieved by the the (M. Seltzer) direct approach, (2) we can bound the accuracy loss that © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License data duplication introduces; and (3) the weighted optimal CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) decision tree technique can outperform natural baselines -th feature of x. To handle continuous features, we in terms of running time, sparsity, and accuracy. binarize them either by using all possible split points to create dummy variables [25] or by using a subset of these splits as done by McTavish et al. [13]. We let x˜, the 2. Related Work binarized covariate matrix, be notated as x˜ ∈ {0, 1}. Decision trees are one of the most popular forms of interpretable models [17]. While full decision tree optimiza- 3.1. Objective tion is NP-hard [18], it is possible to make assumptions, Let be a decision tree that gives predictions {ˆ }=1. e.g., feature independence, that simplify the hard op- The weighted loss of on the is: timization to cases where greedy methods sufice [ 19]. pOHetorhwfeeercvtaleyprp,strehopeaascrehateaessds[u2wm0i,tph2t1izo]enraosssaeurrmerouerntahrneadatluitshsteeicSdiAantTapsrcoaaclnvtiebcrees. ℒw( , x˜, y) = ∑︀=11 ∑=︁1 1[ ̸= ˆ ] × . (1) to find optimal decision trees; however, real data are generally not separable. To achieve interpretability and prevent overfitting, we
Recent work has addressed optimizing accuracy with provide the option to use either soft sparsity regularizasoft or hard sparsity constraints on the tree size. Such tion on the number of leaves, hard regularization on the decision tree optimization problems can be formulated tree depth, or both [see 13]: 2u3s,in2g4]m,bixuetdMinIPtegsoelrvperrsogtreanmd mtoinbge (sMloIwP). [S9e,v1e0r,a1l2n,e2w2, minimizeℒw( , x˜, y)+ ..depth( ) ≤ , (2) algorithms use customized dynamic programming algorithms with branch-and-bound techniques to improve where is the number of leaves in and is a perdecision tree optimization scalability. In particular, an- leaf regularization parameter. We define w( , x˜, y) = alytical bounds combined with bitvector-based compu- ℒw( , x˜, y) + . We refer to 1[ ̸= ˆ ] as ( ), tation eficiently reduce the search space and improve for simplicity. While in practice, depth constraints beruntime [25, 26, 27]. Lin et al. [14] extend this approach tween 2 and 5 are usually suficient, McTavish et al. [13] to use dynamic programming, which leads to even better provide theoretically-proven guidance to select a depth scalability. Demirović et al. [28] introduce constraints constraint so that a single tree has the same expressive on both depth and the number of nodes to improve scal- power (VC dimension) as an ensemble of smaller trees ability. Recently, McTavish et al. [13] proposed smart (e.g., a random forest or a boosted decision tree). The guessing strategies, based on knowledge gleaned from parameter trades of between the weighted training black-box models, that can be applied to any optimal loss and the number of leaves in the tree. branch-and-bound-based decision tree algorithm to reduce the run time by multiple orders of magnitude. While 3.2. Learning Weighted Trees these studies focus on improving runtime and accuracy, they handle only uniform sample importance and do not consider weighted data points. Our work neatly fills this gap; our weighted objective function, data duplication method, and sampling approach enable us to find nearoptimal decision trees quickly.
Several studies focus on learning tree- and list-based treatment regimes from data [29, 30, 31, 32, 33, 34, 35].
However, none of these methods fully optimize the policy, because the techniques used for optimization were not known when the work was done.
Direct Approach. We begin with the branch-and-bound algorithm of McTavish et al. [13] and adapt it to support weighted samples. Given a reference model , they prune the search space using three “guessing” techniques: (1) guess how to transform continuous features into binary features, (2) guess tree depth for depth-constrained models, and (3) guess tight lower bounds on the objective for subsets of points to allow faster time-to-completion. Theorem 1. (Performance Guarantee). Let (g, x˜, y) It is straightforward to see that the first two techniques denote the objective of g on the full binarized dataset (x˜, y) apply directly to our weighted loss function. However, for some per-leaf penalty . Then for any decision tree we need to adapt the third guessing technique to have that satisfies the same depth constraint , we have: an efective and tight lower bound for the weighted loss fpulenxctrieofne.reLnecteˆm obdeelth(ee.gp.r,eadbicotoiostnesdodfeacipsiootnenttrieaellmyocodmel)- (g, x˜, y) ≤ ∑︀1 ⎝⎛ ∑︁ on training observation . The reference model is used =1 ∈,incorrect as an upper bound on the performance of the sparse de- ⎞ cision tree we are optimizing. Let be the subset of + ∑︁ 1[ ̸= ˆ] × ⎠ + . training observations that satisfy a boolean assertion : ∈,correct := { : (x˜) = True, ∈ {1, ..., }} x˜() := {x˜ : ∈ } , y() := { : ∈ } w() := { : ∈ } .
Motivated by McTavish et al. [13], we define our guessed lower bound on the achievable loss on subset as: guess() := ∑︀1 ∑︁ 1[ ̸= ˆ ] × + . (3) =1 ∈
That is, the objective of the guessing model g is no worse than the union of errors of the reference model and tree .
Hence, the model g achieves a weighted objective that is as good as the error of the reference model (which should be small) plus (something smaller than) the error of the best possible tree of the same depth. The proof appears in our supplementary material [36].
Motivation for Data Duplication. Surprisingly, inEq. 3 is a lower bound guess for w(, x˜(), y()), creasing the dataset size by replicating data is substanbecause we assume that the (possibly black box) reference tially faster than using the direct approach. Decision model has a loss less than or equal to that of tree on tree optimization requires repeatedly evaluating the obdata , and we know that any tree has at least one node jective. Small improvements in that computation lead (hence the regularization term’s lower bound of × 1). to a large improvement (possibly orders of magnitude)
Accordingly, in the branch-and-bound algorithm, to in execution time. In the direct approach, computing optimize the weighted loss function introduced in Equa- the objective (2) requires computing the inner product taiosunb2t,reweethcoantsaicdheirevaessuabnproobbjelecmtivteolbesesstohlavnedoirfewqeu afinldto was ·aℐll ,wwehigehretsℐare=11,t[his̸ =coˆmp]u. tIantitohnecuannwbeeigphetrefodrcmaesed, its guess. If we find such a subtree, our training perfor- using bitvectors, which is extremely fast. In the weighted mance will be at least as good as that of the reference case, we resort to standard inner products, which are two model. For a subset of observations , we let be the orders of magnitude slower (see Section 4). The datasubtree used to classify points in , and be the num- duplication approach allows us to use bitvectors as in the ber of leaves in that subtree. We can define the subset’s unweighted case, preserving fast computation. contribution to the objective as: w()(, x˜(), y())
1 = ∑︀ ∑︁ 1[ ̸= ˆ ] × + .
=1 ∈ For any dataset partition , where ∈ corresponds to the data handled by a given subtree of : w(, x˜, y) = ∑︁ w()(, x˜(), y()) .
∈
Data-duplication Algorithm. The data-duplication algorithm is shown in Algorithm 1. We first normalize all weights and scale them to (0, 1]. Given an integer, > 0, we then multiply each normalized weight by and round to integers. We then duplicate each sample, x, by its corresponding integer weight, ˆ. Once the data are duplicated, we can use any optimal decision tree technique.
Our experimentsshow that if we choose the value of appropriately, this method improves training runtime
for = 1, 2, . . . , ˜ do ˜ ←
˜ ∪ {}; ˜ ← ˜ ∪ {}; significantly without losing too much accuracy. After data-duplication, there are no weights associated with samples, and we can use the fast bit-vector computations from the unweighted case.
Correctness of Data Duplication. One might ask if the data duplication approach produces suboptimal solutions, because its loss function is an approximation to the weighted loss. If the weights do not change very much when rounding to integers, the minimum of the data duplication algorithm’s objective is very close to the minimum of the original weighted objective. Recall Define the objective with the approximate weights as () := ˜() := 1 1 ∑︀
=1 ∑︀ =1 ˜ ∑︁ () + #leaves.
∑︁ ˜() + #leaves.
By design, the rounding phase rounds amplified weights, ensuring that the absolute change in weights remains small. That is, we know that ‖w −
w˜ ‖∞ ≤ that multiplying s by a scalar cannot change the value of the objective function. Accordingly, normalizing or . Note Therefore, without loss of generality, we can assume that s are weights right before rounding. loss function as ˜ ∈ arg min ˜(). If ‖w − Theorem 2. Let * be a minimizer of the objective as * ∈ arg min (), and ˜ be a minimizer of the approximate w˜ ‖∞ ≤ , |(* )− ˜(˜ )| ≤ { ( − 1) + ( − 1) + , } scaling weights by does not change the value of (). 4. Experiments where = max1≤ ≤ and = mmainx{{,,˜˜}} .
In other words, the rounded solution provably will not lose substantial performance, as long as both the additive and multiplicative changes in weights due to rounding are small. The value of and are usually small and near 1, if the original weights do not have extreme imbalances.
If the value of is large, then the direct approach is more {︁ }︁, = max1≤ ≤ ˜ {︁ ˜ }︁, an objective means of comparision [17].
pretability, because it can be quantified, thus providing
We use seven publicly available real-world datasets; Table 1 shows sizes of these datasets: The Lalonde dataset [37, 38], Broward [39], the coupon dataset, which was collected on Amazon Mechanical Turk via a survey [40], Diabetes [41], which is a health care related dataset, the Dataset Lalonde Broward Coupon Diabetes COMPAS FICO Netherlands 723 1954 2653 5000 6907 10459 20000 samples features binary features 7 38 21 34 7 23 9 447 588 87 532 134 1917 53890 eficient, so we should duplicate data. When we use data duplication, the value of should also be small. The proof is in our supplementary material [36].
Weighted Sampling.
biggest and smallest weights is large, data duplication might be ineficient if it requires creating many samples. To address this issue, we present a stochastic sampling process based on weights. Given an arbitrary amplificaw that the probability of choosing x is ∑︀=1 w tion number , we sample = × data points such . After this step, we can use any unweighted optimal decision tree algorithm on the sampled dataset.
Quality Guarantee of Weighted Sampling. Let ℒ˜ (.) be the loss function on the sampled dataset, it is not hard to see that E[ℒ˜ ] = ℒw, where ℒw is the value of the misclassification (Eq. 1) on the weighted dataset. Based on this fact, we have the following theorem: ˜ = {(x˜, ˜)}=1, we have: Theorem 3. Given a weighted dataset {(x, , )}=1, an arbitrary positive real number > 0, an arbitrary positive real number > 0, and = a tree , if we sample = × data points from , P ︁( |ℒ˜ ( , x˜, y˜) − ℒ w( , x, y)| ≥ ≤ 2 exp − ︁) ︂( 22 )︂ Our evaluation addresses the following questions: (1) When is the direct approach more eficient than dataduplication and weighted sampling? (2) In practice, how well do the second and third proposed methods perform relative to the direct approach? (3) How sparse and fast are our weighted models relative to state-of-the-art optimal decision trees? (4) How can our approach be used for policy making? We use sparsity as a proxy for inter) (s103 e m i gT102 n i n un101 R without data duplication with data duplication.
) (s103 e m i gT102 n i n un101
R
Fair Isaac (FICO) credit risk dataset [42] from the Explainable ML Challenge, and the COMPAS [43] and Netherlands [44] datasets, which are recidivism datasets. Unless stated otherwise, we use inverse propensity score with respect to one of the features as our weights.
We ran the experiments with diferent depth bounds and regularization; each point in each plot shows the results for one setting. A full description of the data sets and configurations appear in our supplement [36].
because it uses only subsets of the data. Data duplication, while slower than weighted sampling, is faster than the direct method, without losing much accuracy.
Sparsity vs. accuracy. The dotted line and round and diamond shapes in Figures 2 and 3(a) illustrate the accuracysparsity tradeof for diferent decision tree models (the black line represents accuracy for GBDT). GOSDTwG produces excellent training and test accuracy with a small number of leaves, and, compared to other decision tree models, achieves higher accuracy for every level of sparsity. Results of other datasets can be found in [36].
Training time vs. test accuracy. Figures 3(b) and 3(c) show the training time and accuracy for diferent methods. While the training times of GOSDTwG and CART are almost the same, GOSDTwG achieves the highest training and test accuracy in almost all cases. As DL8.5 timed out at one hour on all datasets except Lalonde, it did not reach optimality and was outperformed by both CART and GOSDTwG. Results of other datasets can be found in our supplement [36].
We compared our methods with the following baseline models: (1) CART [5], (2) DL8.5 [45], and (3) Gradient Boosted Decision Trees (GBDT) [46, 47]. CART and GBDT can both handle weighted datasets, so we use their default weighted implementation as the baselines.
As DL8.5 does not supported weighted datasets, we use the data-duplication approach with it.
Lalonde Case Study. The Lalonde dataset is from the National Supported Work Demonstration [38, 37], a labour market experiment in which participants were randomized between treatment (9-12 month on-the-job training) and control groups. Each unit has a pre-treatment covariate vector and observed assigned treatment .
Let 1 be the outcome if unit received the treatment and 2 be the outcome if it was not treated. When a unit 4.3. Results is treated, we do not observe the outcome had it not been treated and vice versa. We use the MALTS model [48] Data duplication. We begin by demonstrating how to estimate these missing values by matching, producing much the direct approach penalizes runtime relative to an estimate of the conditional average treatment efect. data-duplication. We use the unweighted FICO dataset We classify participants into three groups—“should be and randomly pick % of the original data points. We treated,” “should be treated if budget allows,” and “should assign each selected point ℎ = 2 by duplicating not be treated” -– based on their conditional average treatit, producing a dataset of size (1 + 100 ) × , where ment efect estimate. Then we labelled the data points as is the size of the original data set, ||. We then com- 2, 1, and 0 if the estimated treatment efect is larger than pare runtimes for this data-duplicated data set and the 2000, between − 5000 and 2000, and less than − 5000, original dataset in which we assign ℎ = 2 to the respectively. We define the penalty for each misclassiselected samples and ℎ = 1 to the remaining sam- fication as (i) cost = 0 if correctly classified, (ii) cost = ples. We run this experiment on two machines, with 200 + 3 × if label = 0 and misclassified, (iii) cost = diferent processors and amounts of memory, to show 100 + 3 × if label = 1 and misclassified, and (iv) cost the consistency of the results on diferent machines. The = 300 if label = 2 and misclassified. We linearly scale the full machine descriptions appear in our supplementary above costs to the range from 1 to 100, and in the case material [36]. Figure 1 shows that when the size of the du- of data-duplication, we round them to integers and treat plicated dataset is less than 100 times the original dataset, them as weights of the dataset. Figure 4 shows the tree the data-duplication approach is always faster. produced by GOSDTwG with a depth limit of 3; trees with other depth limits appear in [36].
Comparison of our approaches. We next compare the relative accuracy achieved using all three approaches.
The star-shaped points in Figures 2 and 3 show the result of this comparison. These results suggest a trade-of between accuracy and running time. Weighted sampling is the fastest approach, but it has the worst accuracy,
To find the optimal weighted decision tree, we first suggest directly optimizing a weighted loss function. To 101 Number of Leaves (log scale)
101 Number of Leaves (log scale)
101
Number of Leaves (log scale) Training Accuracy vs Run Time (Lalonde)
Train Accuracy vs Run Time (Broward) (a) Sparsity vs. test accuracy:
Training Accuracy vs Run Time
(Diabetes) 101 Training Time (log scale) 101 102 Training Time (log scale) 103
Training Time (log scale)103 102 93 Test Accuracy vs Run Time (Lalonde)
Test Accuracy vs Run Time (Broward) (b) Training time vs. training accuracy:
Test Accuracy vs Run Time (Diabetes) Training Accuracy vs Number of Leaves (Lalonde)
Training Accuracy vs Number of Leaves (Broward)
Training Accuracy vs Number of Leaves (Compas)
Training Accuracy vs Number of Leaves (Coupon) 101
Number of Leaves (log scale) Training Accuracy vs Number of Leaves (FICO)
101
Number of Leaves (log scale) Training Accuracy vs Number of Leaves (Netherlands)
101
Number of Leaves (log scale) Training Accuracy vs Number of Leaves (Diabetes)
101 Number of Leaves (log scale) Acknowledgments 1 0 1 0 1 2 1 0 We acknowledge the following grant support: NIFigure 4: The tree generated by GOSDTwG (depth limit 3) H/NIDA under grant number DA054994 and NSF unon the Lalonde dataset. der grant number IIS-2147061. This research was enabled in part by support provided by WestGrid improve eficiency, we present the data-duplication ap- (https://www.westgrid.ca) and The Digital Research Alproach, which rounds all weights to integers and then liance (https://alliancecan.ca/en). We acknowledge the duplicates each sample by its weight. To further improve support of the Natural Sciences and Engineering Reeficiency, we present a stochastic process in which we search Council of Canada (NSERC). learning falling rule lists, in: International Confer- measurement on hospital readmission rates: Analence on Artificial Intelligence and Statistics (AIS- ysis of 70,000 clinical database patient records, TATS), 2018. BioMed Research International 2014 (2014) 781670. [28] E. Demirović, A. Lukina, E. Hebrard, J. Chan, URL: https://doi.org/10.1155/2014/781670. doi:10.
J. Bailey, C. Leckie, K. Ramamohanarao, P. J. 1155/2014/781670.
Stuckey, Murtree: Optimal classification trees via [42] FICO, Google, Imperial College London, dynamic programming and search, arXiv preprint MIT, University of Oxford, UC Irvine, UC arXiv:2007.12652 (2020). Berkeley, Explainable Machine Learning [29] H. Lakkaraju, C. Rudin, Learning cost-efective Challenge, https://community.fico.com/s/ and interpretable treatment regimes, in: Artificial explainable-machine-learning-challenge, 2018. intelligence and statistics, PMLR, 2017, pp. 166–175. [43] J. Larson, S. Mattu, L. Kirchner, J. Angwin, How [30] Y. Zhang, E. B. Laber, A. Tsiatis, M. Davidian, Using we analyzed the COMPAS recidivism algorithm, decision lists to construct interpretable and parsi- ProPublica (2016). monious treatment regimes, Biometrics 71 (2015) [44] N. Tollenaar, P. Van der Heijden, Which method 895–904. predicts recidivism best?: a comparison of statisti[31] F. Wang, C. Rudin, Causal falling rule lists, arXiv cal, machine learning and data mining predictive preprint arXiv:1510.05189 (2015). models, Journal of the Royal Statistical Society: [32] E. B. Laber, Y.-Q. Zhao, Tree-based methods for Series A (Statistics in Society) 176 (2013) 565–584. individualized treatment regimes, Biometrika 102 [45] G. Aglin, S. Nijssen, P. Schaus, Learning opti(2015) 501–514. mal decision trees using caching branch-and-bound [33] Y. Cui, R. Zhu, M. Kosorok, Tree based weighted search, in: AAAI Conference on Artificial Intellilearning for estimating individualized treatment gence, volume 34, 2020, pp. 3146–3153. rules with censored data, Electronic Journal of [46] Y. Freund, R. E. Schapire, A desicion-theoretic genStatistics 11 (2017) 3927–3953. eralization of on-line learning and an application to [34] K. Doubleday, H. Zhou, H. Fu, J. Zhou, An algorithm boosting, in: Conference on Computational Learnfor generating individualized treatment decision ing Theory, Springer, 1995, pp. 23–37. trees and random forests, Journal of Computational [47] J. H. Friedman, Greedy function approximation: and Graphical Statistics 27 (2018) 849–860. a gradient boosting machine, Annals of Statistics [35] Y. Sun, L. Wang, Stochastic tree search for estimat- (2001) 1189–1232.
ing optimal dynamic treatment regimes, Journal [48] H. Parikh, C. Rudin, A. Volfovsky, MALTS: Matchof the American Statistical Association 116 (2021) ing after learning to stretch, arXiv preprint 421–432. arXiv:1811.07415 (2018). [36] A. Behrouz, M. Lecuyer, C. Rudin, M. Seltzer, Fast optimization of weighted sparse decision trees for use in optimal treatment regimes and optimal policy design, 2022. URL: https://arxiv.org/abs/2210.06825.
doi:10.48550/ARXIV.2210.06825. [37] R. Lalonde, Evaluating the econometric evaluations of training programs with experiment data, American Economic Review 76 (1986) 604–20. [38] R. H. Dehejia, S. Wahba, Causal efects in nonexperimental studies: Reevaluating the evaluation of training programs, Journal of the American statistical Association 94 (1999) 1053–1062. [39] C. Wang, B. Han, B. Patel, F. Mohideen, C. Rudin, In pursuit of interpretable, fair and accurate machine learning for criminal recidivism prediction, Journal of Quantitative Criminology (2022). [40] T. Wang, C. Rudin, F. Doshi-Velez, Y. Liu, E. Klampfl,
P. MacNeille, A bayesian framework for learning rule sets for interpretable classification, Journal of Machine Learning Research 18 (2017) 1–37. URL: http://jmlr.org/papers/v18/16-003.html. [41] B. Strack, J. P. DeShazo, C. Gennings, J. L. Olmo,
S. Ventura, K. J. Cios, J. N. Clore, Impact of hba1c