Global optimization of decision trees has shown to be promising in terms of accuracy, size, and consequently human comprehensibility. However, many of the methods used rely on general-purpose solvers for which scalability remains an issue. Dynamic programming methods have been shown to scale much better because they exploit the tree structure by solving subtrees as independent subproblems. However, this only works when an objective can be optimized separately for subtrees. We explore this relationship in detail and show the necessary and sufficient conditions for such separability and generalize previous dynamic programming approaches into a framework that can optimize any combination of separable objectives and constraints. Experiments on five application domains show the general applicability of this framework, while outperforming the scalability of general-purpose solvers by a large margin.
Paper
Similar papers
Peer review
Summary
The authors present a dynamic programming (DP) method for constructing optimal decision trees. The method is more general than previous DP methods. The authors report extensive experiments to compare with previous methods which including MIPS and DP methods.
Strengths
The paper is well-written and there is extensive supplementary material including code. There appears to be a real contribution in the integration of diverse types of constraints within the DP framework. The DP method is conclusively shown to be much faster than MIPS methods. There is a welcome theoretical analysis of the problem which allows the authors to state weaker sufficient conditions (than were previously known) for the DP method to work.
Weaknesses
My main (and only major) criticism of this paper is that the authors try to prove that their list of conditions are not only sufficient but also necessary for the DP method to work. I believe that these conditions are sufficient, but I have some doubts about necessity. Firstly, in lines 193-194 you give a definition of a Markovian cost function: it is a cost function that depends just on the state and the current branching decision. In Appendix A (lines 46-47) you give the impression that a Markovian cost function can depend on the 'history' of branching decisions, which seems to go against standard definitions (including your own) of Markovian. Would the DP method still work if the cost depended, for example, on the order of the branching decisions in the history? If so, then the claim that having a Markovian cost function is a necessary condition for the DP method to work appears false. Secondly, you give a definition of anti-monotonicity (Def. 4.5) which appears non-standard. I would expect c to be anti-monotonic iff (c(Y) and X a part of Y implies c(X)) but you say c is anti-monotonic iff (opt(Y) and X a part of Y implies c(X)). You could call this, for example, anti-monotonicity on optimal solutions. A proof of necessity can only work with this weaker version but Appendix A (lines 114-116) seems to be saying that the stronger version is necessary (which is wrong). One obvious fix would be to weaken your claims by dropping the 'only if' parts of Prop. 4.3 and Theorem 4.6. This would leave a very solid paper. The other solution is to try and produce a watertight proof of the 'only if' directions in the rebuttal. There are also a few minor presentation improvements that can be made in terms of presentation: - In last sentence of the abstract you should say something about the quality of the trees you find (otherwise being faster is a vacuous piece of information). - lines 166-170: This paragraph is confusing. One possible interpretation is that constraints are never taken into account, which is surely not the case. It is not clear what 'building blocks' refers to. - Definition 4.4 (line 209): you should avoid phrases such as 'and thus' in a definition. This is a consequence of the definition not part of it. This could be stated after the definition. - Definition 4.5: again the 'and thus v_1 \notin opt(\Theta_1,s_1)' is out of place in a definition. It is implicit that Theta/Theta_i are the set of feasible solutions for s/s_i. It would be better to recall within the definition. - line 218: give an example of a non-anti-monotonic constraint. - line 229: why 'street' instead of 'streed'? - equation (10): 'else' should be 'otherwise' - line 285: do you mean monotonic or anti-monotonic?
Questions
(1) Is the 'only if' part of Prop. 4.3 correct with the standard definition of 'Markovian'? (2) Is there a typo in lines 114-116 of Appendix A? (3) When you say in line 266 'This Pareto front can then be used to find the decision tree with, e.g., the best F1-score', is the Pareto front of possibly exponential size? (4) In lines 268-282 (Group fairness): Are the actual constraints you apply stronger than demographic parity. Are you imposing that you have parity down each branch, which would be much stronger? ****ADDED AFTER REBUTTAL**** I appreciated the authors' rebuttal and replies to my comments. I am generally positive about this paper, but it is important that the authors make perfectly clear to the reader what the necessary and sufficient conditions are. I found the terms Markovian and anti-monotonicity confusing and the authors should consider using history-dependent Markovian and anit-monotonicity on optimal solutions, for example.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
3 good
Limitations
There are no obvious negative societal impacts.
Summary
The paper introduces STreeD, a novel dynamic programming (DP) framework designed for learning optimal decision trees. By expanding the range of solvable objectives and constraints, STreeD offers significant advancements in decision tree optimization. The authors also offer theoretical insights to aid in determining the solvability of specific optimal decision tree problems using DP. The effectiveness of STreeD is showcased through its successful application in various tasks, such as revenue maximization under capacity constraints, group fairness, and optimization for nonlinear classification metrics.
Strengths
The contributions of the paper include a new cost function that allows for more flexible optimization, a new framework for learning decision trees that can handle a wider range of objectives and constraints, and empirical results demonstrating the effectiveness of the approach on several tasks. Overall, this paper is well organized and easy to follow. Additionally, the claims made in the paper are well-supported by comprehensive experimental evaluations.
Weaknesses
- Regarding section 4.4, would it be possible for you to provide an example that illustrates a situation where the optimization task is non-separable? - Regarding Figure 2, could you kindly provide a description of the relationship between the Remaining Gap at Time-out and the number of Trees Computed? The current plot exhibits an unusual pattern where the gap appears to increase as the number of computed trees increases, which appears unexpected. - Concerning the final cost of a tree as expressed in Equation (4), could you please provide a precise explanation of the meaning of the term g(s, b(u))?
Questions
see weaknesses.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
4 excellent
Limitations
The limitations of this work are thoroughly discussed in the conclusion section. However, it is important to acknowledge that the current framework is limited to parallel splits only. In future investigations, exploring other types of splits, such as oblique splits, could be considered.
Summary
The paper a proposes a novel framework for constructing Dynamic Programming (DP) algorithms for learning decision trees on Separable objectives. Historically DP methods are among the fastest methods that build optimal decision trees, and generatlization to a wide class of objectives is a useful contribution. Theoretical contribution includes a rigorous definition of Separable objective, and a main theorem that defined multiple properties that must be satisfied by the objective to be separable. A mathematical formulation of the DP recursive algorithm is given, that is guaranteed to work for any separable objective. Detailed evaluation is done on multiple datasets and objectives, some of which were previously considered in the literature, and other problems settings are novel and suitable only to the proposed framework.
Strengths
- This is a strong generalization of existing DP frameworks for Optimal Decision Trees solving. - According to the experiments, this paper may set a new state of the art in terms of being the most efficient and flexible DP solver for Optimal Decision Trees.
Weaknesses
- No major or minor weaknesses.
Questions
-
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
It would be nice to add examples of non-separable objectives to outline the scope of applicability of the proposed framework; to quantify how frequently such objectives are encountered in real-world tasks and datasets.
Summary
The paper investigates the conditions under which an optimal binary decision tree problem can be formulated as a dynamic programming (DP) problem, proposing the so-called *STreeD* framework. More specifically, the text establishes a general concept of separability for the objectives and constraints of DP-representable optimization problems. This concept requires state transitions to be order-preserving (for optimality) and anti-monotonic (for feasibility). The authors demonstrate that these properties hold for non-trivial decision tree constraints and evaluate their approach across four application domains, wherein it outperforms general-purpose solvers.
Strengths
+ Very well written and rigorously formalized. + Framework expands the class of optimization models that can be addressed via DP in an intuitive way. The paper contributes to the recent and growing body of work on optimization models for training decision trees. I appreciated that the paper is nicely written and formalized, proposing a more intuitive framework to verify if a binary decision tree can be more compactly written as a DP. The numerical results are also well designed and inform model choice between DP and more traditional mathematical programming methods, which is a valuable contribution. Finally, another interesting aspect is that the application to non-binary trees also seems theoretically feasible to me, as it would require a discrete action set as opposed to a binary one.
Weaknesses
- The originality of the generalization is unclear. - More details needed to justify the benchmarks in the numerical section. My major concern is that I struggle to understand the novelty of the work and its relationship to more fundamental DP theory. I believe this is an issue of presentation and framing of the work, which attempts to be somewhat broad in Section 4. More precisely, any discrete optimization problem can conceptually be represented as a DP model given sufficient information to encode within a state. The effectiveness of the DP is directly correlated with the space complexity of the resulting state space, since models are typically solved via value enumeration or state recursion. The paper's main contribution is to show that one can leverage a more compact state representation (the dataset-depth pair) for many classes of objectives/constraints, i.e., that no additional state variables are required to enforce constraints or optimality. However, these are fundamental questions of DP representability, and my understanding is that the paper could possibly be reinterpreting existing classical results in the area. For example, the notion of order-preserving and anti-monotonicity seems to be quite close to the concepts of monotonicity and $\thicksim$-congruence of the seminal work by Karp & Held, Karp, Richard M., and Michael Held. "Finite-state processes and dynamic programming." SIAM Journal on Applied Mathematics 15.3 (1967): 693-718. and references therein. The multiobjective-representable DP concept is also classical, e.g., Li, Duan, and Yacov Y. Haimes. "Extension of dynamic programming to nonseparable dynamic optimization problems." Computers & Mathematics with Applications 21.11-12 (1991): 51-56. and the idea of the *merge* also shares some similarities with the concatenation concept by Elmaghraby, Salah E. "The concept of “state” in discrete dynamic programming." Journal of Mathematical Analysis and Applications 29.3 (1970): 523-557. Other related works include: - Smith, Douglas R. Representation of discrete optimization problems by discrete dynamic programs. Naval Postgraduate School, 1980. - Pollock, Stephen M., and Robert L. Smith. A formalism for dynamic programming. 1985. Many of the conditions discussed in the works above establish when the optimal policy will be optimal and feasible, in that any state is actually capturing all the necessary information of all paths that reach it; that is, the "merge" deriving from the state transitions are sound. My understanding is that this paper could possibly be offering a more intuitive way of checking whether these conditions hold for the special case of binary decision trees (in contrast to building more complex automata, for example). However, the paper lacks this discussion, which I believe is important because I am not sure if order-preserving is novel, or whether it can be derived from the classical body of work above. *Other notes* - It is not clear from the text if the benchmark methods correspond to the state of the art; e.g., there are nonlinear formulations (such as CP) that could also be used for training. - The paper is very well written, but in my opinion, the term "pushing the limits of DP" is not appropriate because the paper does not exhaust all possible DP-based methodologies for these problems. I would suggest something along the lines of "Dynamic Programming Representability of Optimal Decision Trees" to highlight the theoretical contributions of the paper.
Questions
It would be great if authors could comment on the relationship between Proposition 4.3 and Theorem 4.6, and existing works mentioned above.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
No limitations were discussed.
Summary
This paper discusses the necessary and sufficient conditions for training optimal classification trees using dynamic programming (DP). In particular, the authors replace the commonly used -- and suficient -- notion of additivity by order preservation, which is shown to be necessary. The authors also present a generalized framework for modeling optimal classification trees using DP, which presents better results in some benchmarks. ***** Following the rebuttal by the authors, I am updating my score accordingly.
Strengths
The authors present a very comprehensive review of existing work and initial explanation of the ideas. I was not aware of some of the references used, such as Verwer and Zhang's proposing optimal training with MIP at the same time as Berstimas & Dunn. Along those lines, the authors make it clear why training with DP is beneficial, as well as how much was already done in prior work.
Weaknesses
I have a hard time grasping the meaning of the main result in the paper, Theorem 4.6. This is not so much about its correctness, but rather about the feeling that the definitions preceding it seem reverse-engineered to ensure that they are both necessary and sufficient. For example, there is no example helping the reader understand what order preservation means and how it is more general than additivity. If order preservation is the key element in this paper, my lack of understanding about it makes me unsure about the relevance of the main contribution. Along the same lines, I would have appreciated a real example and discussion of anti-monotonicity, even if it is a concept already used in other papers. I would have expected that to occur with the examples in Section 4.4, but they are very briefly explained - and in cases such as prescriptive policy generation not explained at all. Moreover, DP has already been previously used to obtain optimal classification trees in all of the cases studied. And if so, what is it that we gain from the more generalized setting described in this paper?
Questions
1) Can you please describe the intuition for order preservation and where it would be useful whereas additivity would not? 2) Can you please explain how anti-monotonicity relates to the applications considered? 3) Can you please describe an application that can be addressed by your setting that was not possible previously? 4) It is not clear to me how the STreeD framework benefits from the setting described in this paper to such a point that it outperforms other methods. In your opinion, what makes the setting considered in your work also more convenient computationally? 5) Do you see a possible application of this or a related setting to optimally train decision diagrams for classification? In terms of notation, I would caution the authors about the use of $\mathcal{D}$ to sometimes represent the entire dataset (as it seems implied in Lines 112 and 165) and sometimes represent a subset of the dataset (such as in the recurrence in equation (2)).
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
I do not recall seeing a discussion about limitations, but it would be fair to say that outlining what optimal classification trees can and cannot be trained with DP represents an important study about the limitations of a particular form of training algorithm.
I appreciate the comments by the authors and have updated my score accordingly. I agree with the points raised by reviewer VtkV about the scope and significance of the work, and I second that reviewer's suggestion of a more specific and meaningful title for this paper. I am counting on the word of the authors about changing it.
Thank you for carefully answering my questions and outlining the connection with previous works - I believe this helps in broadening the impact of the methodology. I also appreciate the clarification of the numerical results. My concern here is why those specific four benchmarks were chosen (not sure what was the measure of diversity). I have updated my score accordingly.
Thank you once again for your comments, we agree that adding the discussion to the paper will indeed deepen our paper. Regarding the benchmark selection: our aim was to select a diverse set of benchmarks such that it is not easy to trivially adapt the algorithm of one of the applications for the other. There is no formal measure of diversity, but the problem formulations and the applications are intuitively very different. Note that typically, decision tree papers only consider one or two similar benchmarks, whereas we demonstrated the generality of our method on four benchmarks
I would like to thank the authors for providing detailed responses to all referee reports, and I apologize that some of the referees have not responded to the rebuttals despite multiple reminders. I will account for that in my final recommendation.
I would like to thank Authors for their response and thorough examples in the rebuttals that showcase the generality and applicability of the proposed framework, which confirms my original evaluation score.
Reply to the authors' rebuttal
Dear authors, Thank you for your detailed rebuttal. The rebuttal makes sense and all my questions have been answered. However, I am a little concerned that you have to make a change to an important claim in the paper (anti-monotonicity on optimal solutions not on all solutions) which it will not be possible to verify by another review.
The changes we will make to our final text concerning anti-monotonicity will not change any important claim in our paper. These changes are only small changes to improve clarity and avoid misunderstanding, namely: 1. Addition of one sentence in the main text where we highlight that our definition of anti-monotonicity only requires anti-monotonicity of optimal solutions and that requiring all solutions to satisfy anti-monotonicity, as Nijssen and Fromont (2010) require, is not necessary. 2. We will update the notation in Appendix line 114-116 as specified to avoid misunderstanding. Our definitions, theorems and proofs in our first version already used anti-monotonicity on optimal solutions only. Therefore, none of these changes affect our theorems, proofs and definitions. The changes also do not affect our experimental results.
Decision
Accept (poster)