Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*

Thank you for very much for your reviews, please find our response below:

Missing literature

• Chaouki et al. (2024)'s TSDT algorithm is tailored to online classification where a data stream is observed instead of a batch of data, which is different from the batch setting we consider. Due to the online consideration, TSDT does not have a natural termination condition like Branches and GOSDT, it has to keep adjusting the prior distributions of the node values until reaching a prespecified number of iterations. For these two reasons we decided not to compare with TSDT. However, we thank you for this suggestion, and we can definitely add such a comparison in the appendix for illustration purposes.
• Nunes et al. (2020) do not solve the sparsity problem (minimising $\mathcal{H}_\lambda$). In addition, we are not aware of a public code for the authors' algorithm, which prevents us from directly comparing with their algorithm. Nevertheless, (Table 4, Nunes et al. 2020) seems to indicate that the algorithm is significantly slower than the state of the art as it runs in hours. For example, car- evaluation takes 3 hours and 19 minutes and tic-tac-toe takes 4 hours and 59 minutes. Branches and GOSDT terminate and are optimal in under 2 minutes in both of these experiments.

AND/OR representation

Thank you for this remark. In fact, in section 3.3, we state that we follow the hypergraph convention in (Nilsson, 2014, Section 3.1), which replaces the notions of AND/OR nodes with nodes and connectors. The reason we chose this convention over the AND/OR nodes is to make the graph illustration more compact. With AND/OR nodes, Figure 1 would not be able to fit in the paper. We note that both conventions are equivalent. With AND/OR nodes, OR nodes would represent states (branches) and AND nodes would represent actions (split actions and the terminal action). Furthermore, the search space of branches is represented in several papers with the hypergraph convention (albeit without specifying a link to AND/OR search), e.g:

• "Aglin, G., Nijssen, S., and Schaus, P. (2020). Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3146–3153." Figure 2.
• "Nijssen, S. and Fromont, E. (2007). Mining optimal decision trees from itemset lattices. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 530–539." Figure 2.
• "Nijssen, S. and Fromont, E. (2010). Optimal constraint-based decision tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21:9–51." Figure 1.

We thank you for this suggestion, we can try to include an equivalent representation of Figure 1 in terms of AND/OR nodes in the Appendix.

Notation

Thank you for this recommendation. In fact, we chose $F$ for transitions instead of $T$ to avoid confusion because we already use $T$ substantially with sub-DTs and DTs. The reason we chose $F$ specifically is because it is used in this context in some literature, e.g.:

• "Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and its application to MDPs" in section Models.

Thank you very much for your review, please find below our response:

Interpretability of multi-way splits

• Thank you for raising this point. The interpretability of DTs is due to their simple decision rules, it is not specific to binary DTs. On the other hand, we recognise that DTs where each node has a large number of children can become less interpretable than binary DTs. We alleviate this issue by penalising the number of splits, which leads to DTs with small number of splits and hence more interpretablity.
• In Appendix E, we directly compare ordinal encoding with binary encoding in terms of interpretability, especially when we introduce the notion of collapse. We argue in these examples that DTs that stem from ordinal encoding can be more interpretable than binary encoded DTs. This is especially the case when comparing Figure 7 and Figure 8; and also Figure 12 and Figures 9 and 10.
• In addition, Branches is not restricted to ordinal encoding, it can be applied to binary encoding in similar fashion to the state of the art. In which case, if we have a good binary encoding that we think yields interpretable DTs, we can choose to use Branches with it. The benefits of Branches compared to the other algorithms are still satisfied in this case.

Methods And Evaluation Criteria:

• Yes, Table 2 reports the training accuracy with no train/test split. The objective being to find the most accurate DT with least complexity (most sparse DT). Quoting (Lin et al.2020; Section 5)[2]: "Learning theory provides guarantees that training and test accuracy are close for sparse trees". However, we recognise that a direct comparison of test performance would be insightful as well. In Appendix H.2, we compare Branches with CART and DL8.5 in terms of Pareto fronts (accuracy vs number of splits) within a 10-fold cross-validation. The reason we restrict this comparison to Branches, CART and DL8.5 is to compare different types of DT construction algorithms (Branches seeks optimal sparse DTs, CART seeks DTs greedily, and DL8.5 seeks optimal DTs subject to a hard constraint on depth), comparing Branches with GOSDT and STreeD in this context would yield the same solutions when they terminate.
• We compared with CART in Appendix H.2.
• Blossom does not solve the problem of sparsity that Branches, GOSDT and STreeD solve. It rather seeks optimal DTs subject to hard constraint on depth in similar fashion to DL8.5. Nevertheless, we included an illustrative comparison with these types of DTs in Appendix H.2, where we chose the popular DL8.5 algorithm. We note that DL8.5 is anytime as well.
• Indeed Branches struggles with highly dimensional data such as mushroom, but we showed that its handling of ordinal encoding alleviates this issue significantly, with a fast termination in only $0.15s$ for mushroom-o. Moreover, in Appendix H.4, we investigated the reason STreeD performs exceptionally well on mushroom, we found that it is mainly due to the depth 2 solver, a technique introduced in Demirovic et al.2022 [1]. This leads us to believe that a future incorporation of the depth 2 solver in Branches could further improve its current performance.
• Branches handles categorical features. Any type of discretisation preprocessing can be applied to numerical features before feeding the dataset to Branches. This is similar to other algorithms such as GOSDT, STreeD and MurTree, with the additional benefit that Branches handles multiway splits and thus does not necessitate binary preprocessing. We did not compare with Quant-BnB because it is specifically tailored to continuous features, and it does not solve the sparsity problem. Rather, Quant-BnB seeks optimal DTs subject to a hard constraint on depth that is either 2 or 3. Branches and the algorithms we compare with can find optimal sparse DTs of higher depths.
• We make text bold based on the objective $\mathcal{H}_\lambda$ first. Then we compare accuracy, splits and runtimes of the methods yielding the highest objective, with the corresponding bold text.

Other weaknesses:

• Thank you very much, this is a very interesting point. In appendix D.1, page 14, we provide a tie-break strategy "There is an additional benefit to storing -value_complete. When there are multiple split actions attribute that maximise value, then we prioritise the one maximising value_complete.". We will update the main paper to refer to this tie-break strategy. Thank you for this recommendation.
• For space concerns, we refer the reader to (Nilsson, 2014, Section 3.2) for the base AO*.

[1] Demirovic, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., and Stuckey, P. J. Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1–47, 2022.

[2] Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pp. 6150–6160. PMLR, 2020.

Thank you very much for your reviews, please find our response below:

Presentation:

Thank you for this feedback. We have included Figure 2 in the Appendix for the purpose of illustrating the notions of branches and sub-DTs. Do you have any recommendation that would improve this figure's quality? Thank you.

Mixed concepts from the RL and heuristic search community

RL and heuristic search share many common notions and terminology and we do not think that notions like policies, actions and values are exclusive to RL. In fact, several heuristic search papers employ these concepts such as:

• "LAO*: A heuristic search algorithm that finds solutions with loops".
• "Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and its application to MDPs".

The RL community also employs many concepts that are traditionally linked to heuristic search. The notions of node expansion, update... are extensively employed in the context of Monte Carlo Tree Search, e.g "Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. (2012). A survey of Monte Carlo Tree Search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43".

These unified concepts are very helpful for us in deriving the proofs of our theoretical results. If we failed to define clearly some of these notions, we kindly ask if you could refer us to the ones in question so that we incorporate the necessary modifications. Thank you very much.

AND/OR Search Graph

In section 3.3, we state that we follow the hypergraph convention in (Nilsson, 2014, Section 3.1). The reason we chose this convention over the AND/OR nodes is to make the graph illustration more compact. With AND/OR nodes, Figure 1 would not be able to fit in the paper. We note that both conventions are equivalent, with AND/OR nodes, OR nodes would represent states (branches) and AND nodes would represent actions (split actions and the terminal action). Furthermore, the search space of branches is represented in several papers with the hypergraph convention (albeit without specifying a link to AND/OR search), e.g:

• "Aglin, G., Nijssen, S., and Schaus, P. (2020). Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3146–3153." Figure 2.
• "Nijssen, S. and Fromont, E. (2007). Mining optimal decision trees from itemset lattices. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 530–539." Figure 2.
• "Nijssen, S. and Fromont, E. (2010). Optimal constraint-based decision tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21:9–51." Figure 1.

Thank you for the recommendation regarding a solution graph. A solution graph is the DT of a policy, for example, the graph constituted of the red connectors in figure 1 is a solution graph. We can add this remark to the paper, thank you.

Observation regarding AO* vs DFS:

Indeed, but to our knowledge, this advantage has not been explored for seeking optimal sparse decision trees. The contribution of our paper was to explore this and develop Branches.

Questions

1- Yes, Proposition 4.2 proves that the purification bound is admissible as it always overestimates the optimal value of a node (overestimation as opposed to the traditional underestimation because we are in a formulation based on objective maximisation instead of cost minimisation). Moreover, Theorem 4.3 proves the optimality of Branches upon termination.

Thank you very much for your reviews, please find below our response.

Missing Literature:

• (McTavish et al. 2022): We cite these authors, in fact we use their implementation of GOSDT as mentioned in Appendix H. We also directly quote them in Appendix H.4. However, we only compared with GOSDT and not with the additional guided guesses that the authors introduced. The reason is that this loses the optimality guarantee (with respect to $\mathcal{H}_\lambda$) of GOSDT upon termination, and our main objective in this paper is to compare methods satisfying this optimality guarantee, hence the choice of STreeD, MurTree and GOSDT. Furthermore, the guesses strategy is not exclusive to GOSDT, it can be incorporated within Branches search strategy as well in similar fashion to how the authors incorporated it in GOSDT and DL8.5. For this reason, it makes sense to compare the base algorithms and to consider an incorporation of the guesses strategy in the future for Branches.
• (Mazumder et al.2022) is specifically tailored to continuous features. Moreover, the main objective of this work, which is (1), does not incorporate sparsity concerns in terms of actively seeking to minimise the complexity of the solution while simultaneously maximising its accuracy. Quant-BnB rather optimises its objective subject to a hard constraint on depth as either $2$ or $3$. This is different from our work, which aligns more with literature that jointly optimise accuracy and sparsity via the objective $\mathcal{H}_\lambda$.
• (Hua et al. 2022) is also specifically tailored to continuous features and large scale applications as demonstrated by the costly experiments of 1000 cores and two hours run-times. Our experiments on the other hand are less costly, we run them on a personal Machine (2,6 GHz 6-Core Intel Core i7) as stated in Appendix H and for 5 minutes, which makes them easily reproducible.

Weaknesses:

1- Indeed, Branches necessitates a discretisation of numerical features, this is common among many works in the literature of DT optimisation. Moreover, contrary to the state of the art, Branches is not restricted to binary encodings but can deal with ordinal encodings as well.

2, 3 - Indeed, we have mentioned these limitations in Section 6 as avenues for future work.

Comparison with Random Forest:

Ensemble methods such as Random Forest focus on performance in terms of accuracy (for example) but forgo interpretability. The objective of this paper is to jointly optimise for both concerns in similar fashion to papers from this literature such as:

• Demirovic, E.,Lukina, A., Hebrard, E., Chan, J., Bailey,J., Leckie, C., Ramamohanarao, K., and Stuckey, P. J.Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1–47, 2022.
• Hu, X., Rudin, C., and Seltzer, M. Optimal sparse decision trees. Advances in Neural Information Processing Systems, 32, 2019.
• Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pp. 6150–6160. PMLR, 2020.

For this reason, works from this literature generally do not compare with ensemble methods.

Questions:

1- Being a BFS (Best First Search) method, Branches is more memory consuming than DFS methods such as MurTree and STreeD. On the other hand, its informed BFS strategy allows it to achieve optimality faster thus alleviating the issue. This is a general trade-off between BFS and DFS, and it is thus valuable to devise an BFS strategy that terminates optimally quickly before consuming too much memory. This is what we achieved with Branches, Theorem 4.4 and Table 1 analyse its time complexity (which is directly linked to its memory complexity as the search graph grows with each iteration) and show its superiority compared to the literature. Furthermore, Table 2 shows that the number of iterations to termination of Branches is significantly smaller than GOSDT (a BFS method as well), which allows it to terminate in smaller runtimes even though Branches is currently implemented in Python and GOSDT in C++ . The memory concerns of BFS and DFS are discussed in Section 2.

2- Perhaps, but we have to keep in mind the optimality concerns with respect to sparsity as well. It is unclear whether a native handling of numerical features would keep this guarantee.

3- As shown with the mushroom dataset, high-dimensional data can be hard to deal with as the degree of each node in the search graph becomes too large. On the other hand, Branches seems to work well on large datasets in terms of rows.