Near-Optimal Decision Trees in a SPLIT Second

Thank you for your review! We really appreciate your feedback on the organization - since ICML allows an additional page for accepted submissions, we’d be happy to move some of the intuition for greedy splits near the leaves, as well as a discussion of RESPLIT and the Rashomon Set, from the appendix into the main paper. It is really helpful to know that you found that to be important enough to include in the main paper.

The "Blossom: An Anytime Algorithm for Computing Optimal Decision Trees" paper by Demirović et al. (2023) is a relevant work that is not cited or discussed in the submission. Both papers address the challenge of finding optimal decision trees, with a focus on improving scalability and finite-time performance. Demirović et al. (2023) propose an anytime algorithm (Blossom) based on dynamic programming, which shares similarities with the SPLIT approach in terms of aiming for efficiency and anytime behavior. A comparison with Blossom would have strengthened the paper.

Thank you for mentioning Blossom. We’re glad to add a discussion of this work to the paper, and we agree it should be cited - it's an interesting and distinct approach from our own. We’re confident incorporating Blossom does not change the conclusions of our paper - the Blossom paper mentions that Murtree outperforms Blossom for depth 5 or shallower; and we compare extensively with Murtree, with our primary paper results focusing on depth 5.

If you’d prefer to see a direct empirical comparison, we’re happy to look into that. Unfortunately, though we’ve made every attempt to do so, we haven't been able to run the approach by the end of the first rebuttal window - the codebase linked from the paper, https://gitlab.laas.fr/ehebrard/blossom , leads to a circular import error when we follow installation instructions on our machines (this looks to be a known issue that hasn’t yet been resolved - the latest commit to the repository adjusts the makefile/wrapper, and is titled “not quite”). Looking through the 9 works on google scholar that cite this work, none seem to have successfully run the approach and reported results, so we think this may be a larger issue than just our own environment. We're making our best effort to get an empirical comparison done in time.

Lookahead for policy improvement is a well-known technique in approximate dynamic programming and reinforcement learning. Maybe the authors should discuss the connection of this work to the DP and RL literature.

Lookahead for policy improvement is not quite the same as what we’re doing, though we agree discussion of these approaches in our related work would be warranted. We’re finding a globally optimal tree when behaviour is fixed to be greedy past a specific frontier, then postprocessing to improve behaviour past that frontier, with fixed behaviour beforehand. There is certainly a similar spirit of exploration and exploitation tradeoffs in our method, which we’re happy to discuss in related work.

Question 1 (How does the distribution of data affect the runtime of the method)

We’ve given standard worst-case runtime analysis in our theory section, which gives the worst case runtime even for adversarial data distributions. Even for an adversarial dataset that requires high tree complexity (i.e. a noiseless sine wave over a single continuous feature), our method is a substantial improvement to existing optimal tree methods that struggle to scale to larger depths.

It seems like this is a question about decision trees’ theoretical benefits as a model class under adversarial distributions. This question is out of scope for our work, which is about improving performance for real-world datasets relative to other decision tree approaches. We’re happy to discuss related work on trees’ ability to achieve performance comparable to other model classes (such as [1], which shows trees match other model classes’ performance when there is noise in labels), but our work’s primary contribution is an improvement targeting the specific model class of trees.

Question 2 (random retraining vs RESPLIT)

Our understanding is that you’re asking about how RESPLIT compares to an alternative approach that uses random resampling of data, then runs decision tree learning methods on these samples. Is that correct? If so, please see below.

We draw inspiration from the original paper on enumerating the entire Rashomon set for decision trees [2]. Figure 1 of that paper shows a comparison with this proposed resampling method, and demonstrates that it rarely creates models in the Rashomon set. It also leaves much of the Rashomon set unexplored. We show that the models we find are consistently within the true Rashomon set (see for example the precision result in table 2).

Based on your question, it also seems like you may be asking how close the models we find are to optimal, relative to that resampling approach. Certainly the best models in our approximate Rashomon set are almost exactly the same as the best models in the true Rashomon set - since RESPLIT always includes the SPLIT tree in its set of models, and we’ve shown earlier in the paper that the SPLIT tree is regularly comparable to the objective of the best possible tree (see also the training objective results in our response to reviewer KaCM).

If there’s another baseline you had in mind when you mention RETRAIN, please do let us know!

Question 3 (Predictive Multiplicity)

Here are some results on predictive multiplicity: https://rb.gy/axzek9. For each example in the training set, we’ve computed the variance in predictions across models in the Rashomon set. The distribution of this variance over training examples is shown as a box plot for each dataset. We see that RESPLIT exhibits similar predictive multiplicity as models in the original Rashomon set. This is yet another metric showing the approximation ability of RESPLIT.

Aspects that are typical in the Rashomon analysis are also relevant in a heuristic Rashomon search: predictive multiplicity and other variance measures, etc.

We evaluate predictive multiplicity above, but to address your comment about other Rashomon set evaluations, we’d like to draw your attention to the evaluation we’ve done in Table 1, which shows our Rashomon Set approximation’s ability to help in downstream variable importance tasks. The Rashomon Importance Distribution computed on the full Rashomon set gives almost identical variable importance rankings to the Rashomon Importance Distribution computed on the RESPLIT Rashomon set sample (with rank correlation near or matching the best possible result of 1.0). The full results can be seen in Figure 16 in the Appendix.

[1] Semenova, L., Chen, H., Parr, R., & Rudin, C. (2023). A path to simpler models starts with noise. Advances in neural information processing systems, 36, 3362-3401.

[2] Xin, R., Zhong, C., Chen, Z., Takagi, T., Seltzer, M., & Rudin, C. (2022). Exploring the whole rashomon set of sparse decision trees. Advances in neural information processing systems, 35, 14071-14084.

Your core concerns seem to focus on handling continuous features, number of repetitions, and showing results with training objective. We address those points in detail below. In brief, our method is fully compatible with continuous features, our results are robust to (even more) multiple repetitions, and we have an excellent tradeoff between training objective and runtime.

Requested figures/results can be found here: https://rb.gy/5w970v

Continuous features

Our method is fully compatible with continuous features. In this work, we start off with datasets with continuous features, and binarize scalably, using a method with provable guarantees on the performance of a downstream model and demonstrated practical benefit ([1]). Separating a decision tree algorithm into two steps, a binarization step and an optimization step, is a standard approach for non-greedy decision tree optimization (see, for example, [2,3]).

Further Repetitions

We originally ran experiments with 3 trials in Figures 3, 4, 5, and 6. The error bars correspond to the 95% CI obtained (i.e., 1.96x standard error). In the linked figures above, we’ve added results over 5 seeded trials. We do a random 80/20 train-test split for each trial.

Regularized Train Loss

We’ve redone Figure 2 of our paper with regularized train loss - showing the same benefits as the test loss (see Figure 3 in https://rb.gy/5w970v). Tables 1-3 in that link present some of same results in tabular form for clarity, showing our method is very close to optimal (GOSDT) in regularized training loss while being much faster. Figure 1 in the link also shows training loss for many methods.

Greedy vs (Lickety)SPLIT

Note from figures 1 and 2 in https://rb.gy/5w970v that we see a consistent benefit in runtime and performance for both training and test losses. These results do hold up in our main paper figures - greedy is sometimes within the red square, but rarely, if ever, performing equivalently on loss.

You asked us to describe when we would use SPLIT instead of CART - our answer, based on these plots, is "Always!". We’re substantially outperforming greedy methods. Even in the worst case on these real world datasets, we achieve accuracy comparable to CART with a runtime of about a second, so there is minimal cost to using our approach – no disadvantage at all.

Scalability

These distinct implementations are not quite as distinct as they may seem - MurTree, MAPTree, GOSDT, and DL8.5 all use python wrappers of C++ implementations. Cython is a python wrapper around C. We also note that there should be no concerns about the comparison between GOSDT and SPLIT, since SPLIT uses a modified version of GOSDT’s code.

Note that our scalability claims are thoroughly theoretically justified, with further details in section 5 of the main paper as well as the Appendix. For example, we prove LicketySPLIT is a polynomial-time algorithm, whereas optimal trees are NP-hard.

The number of calls to a greedy solver would be a metric unique only to SPLIT and LicketySPLIT, and none of the other algorithms we compared against. We’ve never seen a paper use that metric since it doesn’t actually measure run time fairly across algorithms. It is unfortunately not a suitable metric to facilitate comparison with other algorithms.

Additional Points

Could you compute optimal splits close to the root with some other optimal algorithm than GOSDT?

We can! One of our approach’s advantages is that you can indeed compute optimal splits up to the lookahead depth using a different optimal algorithm than GOSDT. The adjustments to SPLIT remain quite simple for any dynamic programming based approach.

Could you please explain why rashomon sets are useful for decision tree algorithms ?

Rashomon sets are useful whenever we want to understand a set of many alternative models that are all almost identically performant. Please see [4] for an approachable review of some of the many benefits of this approach.

I recommend using the benchmark from Grinsztajn et al., 2022

Figure 4 in https://rb.gy/5w970v shows results for the largest classification dataset in that benchmark. We are happy to add even further experiments on more datasets.

[1] McTavish, H., Zhong, C., Achermann, R., Karimalis, I., Chen, J., Rudin, C., & Seltzer, M. (2022). Fast Sparse Decision Tree Optimization via Reference Ensembles. AAAI, 36(9), 9604-9613

[2] Lin, J., Zhong, C., Hu, D., Rudin, C., & Seltzer, M. (2020). Generalized and Scalable Optimal Sparse Decision Trees. ICML, 119, 6150–6160.

[3] Demirović, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., & Stuckey, P. J. (2022). MurTree: Optimal decision trees via dynamic programming and search. JMLR, 23(26), 1–47.

[4] Rudin, C., Zhong, C., Semenova, L., Seltzer, M., Parr, R., Liu, J., Katta, S., Donnelly, J., Chen, H., & Boner, Z. (2024). Position: Amazing things come from having many good models. ICML, 1742, 1–13.