Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming
Authors: Jacobus G.M. van der Linden
Mathijs de Weerdt
Emir Demirović
Venue: NeurIPS 2023 poster (2023)
Keywords: optimal decision trees
dynamic programming
separability
TL;DR: We develop a general dynamic programming framework that can find optimal decision trees for any separable objective or constraint

Abstract: 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.

Necessary and Sufficient Conditions for Optimal Decision Trees using Dynamic Programming
Jacobus M. van der Linden Mathijs M. de Weerdt Emir Demirović
Delft University of Technology, Department of Computer Science
{J.G. G.G.MM. vanderLinden, M.M. deM.det E. D.Dem
Abstract
Global optimization of decision trees has shown be promising in terms of accuracy, size, and consequently human comprehensibility. However, many of the methods used rely on general-purpos solvers for which scalability remains an issue. Dynamic programming methods have been shown to scale much better because they exploit the 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 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-purpos solvers by large margin.
Introduction
Many high-stake domains, such as medical diagnosis, parole decisions, housing appointments, and hiring procedures, require coman-comprehensibee machine learning (MI.) models ensure transparency, safety, and reliability [74]. Decision trees offer such human comprchensibility, provided the trees are small [71]. This motivates the search for optimal decision trees, i.e., trees that globally optimize an objective for a given maximum size.
The aforementioned application domains wildly differ from one another, and therefore the objective and constraints also differ, leading to a variety of tasks: e.g., cost-sensitive classification for medical diagnosis [32. 82]; prescriptive policy generation for revenue maximization [13]; or ensuring fairness constraints are met [1]. For broad-scale application of optimal decision trees, we need methods that can generalize incorporate objectives and constraints such as the ones from these application domains, while remaining scalable to real-world problem sizes.
However, many state-of-the-art methods for optimal decision ity, for example, to optimize datasets with more than several thousands of instances or to find optimal trees beyond depth three. This includes approaches such as mixed-integer program- ming (MIP) [10, 86), constraint programming (CP) [84], boolean satisfiability (SAT) [42] or maximum satisfiability (MaxSAT) [34].
lack the required scalabil-
Dynamic programming (DP) approaches show scalability that is orders of magnitude better [3, 20, 52] by directly exploiting the structure. Each problem is solved by recursive step that involves two subproblems, each just half the size of the original problem. Additional techniques such as bounding and caching used further enhance performance.
However, unlike objectives and constraints mentioned before. For DP to work efficiently, it must be possible to solve the optimization task at hand separately for every subtree.
solvers, such as MIP, DP cannot trivially adapt to the variety of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Therefore, the main research question considered here is to what extent can this separability property be generalized? In answering this question we provide generic framework called STreeD (Separable Trees with Dynamic programming). We push the limits of DP for optimal decision trees by providing conditions for separability that are both necessary and sufficient. These conditions are less strict and extend to a larger class of optimization tasks than those of hate-of-theean DP frameworks [52, 66]. We also show that any combination of separable optimization tasks is also separable. We thus attain generalizability similar to penrpoa- solvers, while preserving the scalability of DP methods.
In our experiments, we demonstrate the flexibility of STreeD on a variety of optimization tasks, including cost-sensitive classification, prescriptive policy generation, nonlinear classification metrics, and group fairness.
As is commonly done, we assume that features are binarized beforehand. Therefore, STreeD returns optimal binary decision trees under the assumption of given binarization.
In summary, our main contributions are 1) a generalized DP framework (STreeD) for optimal decision trees that can optimize any separable objective or constraint; 2) proof for necessary and sufficient conditions for separability; and 3) extensive experiments on five application domains that show the flexibility of STreeD, while performing par or better than the state of the art.
The following sections introduce related work and preliminaries. We then further define separability, show conditions for separability, and provide a framework that can find optimal decision trees for any separable optimization task, Finally, we provide five diverse example applications and test the performance of the new framework on these applications versus the state-of-the arrt.
2 Related Work
Decision tree learning Because optimal decision tree search is an NP-Hard problem [38], most traditional solution methods for decision tree learning were heuristies. These heuristies, such as CART [14] and C4.5 [73], often employ a top-down compilation, splitting the tree based on local information gain or entropy metric. However, for each new objective, new splitting criteria need be devised, and often this splitting criterion only indirectly relates to the real objective.
With increasing computational power, optimal decision tree search for limited depth has become feasible. Bertsimas and Dunn [10] and Verwer and Zhang [85] showed that optimal trees better capture the information of the dataset than heuristics by directly optimizing the objective hand, resulting on average in a 1-5% gain in out-of-sample accuracy for trees of similar or smaller size.
However, their MIP models -and also the tf-heart MIP models [2, 37, 86, 93]- may often take several hours for medium-sized datasets, even when considering small trees up to depth three. Others have proposed to use SAT [8, 42, 64], MaxSAT [34, 76], and CP [84]. These methods also lack scalability [20], or -in the case of SAT- solve a different problem: finding a minimal tree with misclassifications Because scalability is such issue for these methods, many propose to solve the problem with variants of local search, such as coordinate descent [11, 26), tree alternating optimization [15] and heuristic SAT approach [75].
In contrast, DP approaches find globally optimal trees while achieving orders of magnitude better scalability [3], so the survey by Costa and Pedreira [18] concludes that specialized DP methods are the most promising future direction for optimal decision trees. Nijssen and Fromont [65] proposed DL8, the first dynamic programming approach for optimal decision trees, which they later generalized to broader set of objectives and constraints [66]. Aglin et al. [3, 4] improved the scalability of DL8 by adding branch and bound and new caching techniques to the updated algorithm DL8.5. Hu et al. [36] and Lin et al. [52] added sparsity-based pruning and new lower bound techniques. Demirović et al. [20] improved scalability by adding a special solver for trees of depth two, similarity lower bound, and other techniques. Recent developments include an anytime algorithm [21, 67) and learning under memory constraints [66].
Objectives and constraints Decision tree learning can be extended by considering a variety of constraints. Nanfack et al. [63] categorized these constraints into structure, attribute, and instance constraints. Structure constraints limit the structure of the tree, such as its depth or size. Attribute constraints impose limits based on the attribute values. Examples are monotonicity constraints [35], cost-sensitive classification [55] and group faimess constraints [44]. Instance constraints operate on
2

---

pairs of instances, such as robustness constraints [88], individual faimess constraints [1], and must- or cannot-link constraints clustering [78]. Among these, structure constraints are most widely included in decision tree learning methods.
Many of these constraints objectives can be added to MIP models. Therefore, the literature shows a multitude of MIP models for variety of applications, such as fairness [1], algorithm selection [87], and robustness [88]. However, scalability remains an issue.
Nijssen and Fromont [66] show how the DP-based DL8 algorithm [65] can be generalized for a variety of objectives, provided that the objectives are additive, ie.. the value of objective in a tree node is equal to the sum of the value in its children. Constraints are required to be anti- onti-monotonic, Le., constraint should always be violated for a tree whenever it is violated for any of its subtrees. They consider constraints and objectives such as minimum support in a leaf node, C4.5's estimated error rate, Bayesian probability estimation, cost-sensitive classification, and privacy preservation.
Since then, new DP approaches have improved on the runtime performance of DL.8 This, however, reduced the generalizability of those methods. DL8.5 [3, 4]. for example, can optimize any additive objective but does not support constraints. MurTree [20] provides new algorithmic techniques that result in much better scalability but only considers accuracy. GOSDT [52] can optimize additive objectives that are linear in the number of false positives and negatives but also does not support constraints. When the objective is nonlinear, they no longer use DP. Demirović and Stuckey [19] show how DP can be used to optimize even nonlinear functions, provided the objective is monotonically increasing in terms of the false positives and negatives, but they also do not consider constraints.
Summary Decision tree learning is often approached through top-down induction heuristics, which depend on developing complex custom splitting criteria for each new learning task and may perform suboptimally in terms of classification accuracy. Optimal methods often outperform heuristics in accuracy but typically lack scalability. Optimal DP approaches have better scalability but lack generalizability to other objectives and constraints. In the next sections, we address this by pushing the limits of what can be solved by a general yet efficient DP framework for optimal decision trees.
3 Preliminaries
This section introduces notation, defines the problem, and explains how dynamic programming solutions for optimal decision trees work.
Notation and problem definition Let F be a set of features and let IC be a set of labels that are used describe an instance. Let 'D be dataset consisting of instances (ær, k)), with {o, )FF] the feature vector and & E K. the label of an instance. Because the features are binary, we introduce the notation and f for every feature E F to denote whether instance satisfies feature f or not. In the same way, let D, describe the set of instances in D that satisfy feature f. and D the set of instances that does not.
Let = (B, L, b, 1) be binary tree with the internal branching nodes, the leaf nodes, b: B F the assignment of features to branching nodes and / L - K. the assignment of labels to leaf nodes. The left and right child nodes of branching node u E B are given by un and ug. respectively. Instances that satisfy feature branching test are sent to the right subtree, and the rest to the left.
Then, for example, when minimizing misclassification score (the number of misclassified instances), the cost C of decision tree can be computed by the recursive formulation:
[EE 1kk + I(u)) C(D M uL) + C(Da(1)) ug)
if E L
C(D,u) u)
if B
The task is to find an optimal decision tree T that minimizes the objective value over the training data given a maximum tree depth d. We now explain how this can be optimized with DP, and in the next section, we generalize this to any separable decision-tree optimization task.
Dynamic programming DP simplifies a complex problem by reducing it to smaller repeated subproblems for which solutions are cached. For example, minimizing misclassification score with
3

---

binary class can be solved with DP as follows (adapted from [20]):
min [2-}] minfee dT(D,, + d(D;,d-))
d 0 > 0
T(D,d)
This equation computes the minimum possible misclassification score for dataset D and given maximum tree depth d. Recursively, as long as d > 0, feature f is selected for branching such that the of the misclassification score of the left and right subtree is minimal. In the leaf node (when d = 0), the label of the majority class is selected: either the positive (D+) or negative (D-) label. This approach is further optimized by using caching and bounds.
As is common with DP notation, Eq. (2) returns the solution value (or cost) and not the solution (the tree). In the remainder of the text, we refer solution values and solutions interchangeably, with one implying the other and vice versa.
While Eq. (2) yields single optimal solution, Demirović and Stuckey [19] investigated the use of DP for nonlinear bi-objective optimization by searching for Pareto front of optimal solutions: i.e.. the set of solutions that are not Pareto dominated (>) by any other solution:
nondom(6) () = {u E θ -EE d' (v' > b)}
Consequently, every subtree search also longer returns just one solution but Pareto front. For this, they introduce merge function that combines every solution from one subtree with every solution from the other subtree, resulting in new Pareto front
4 Framework for separable objectives
In this section, we generalize previous DP methods for optimal decision trees to a new general framework that can solve any separable optimization task. First, we define the problem. Second, we formalize what is meant by separability in the context learning decision trees and then we prove necessary and sufficient conditions for optimization tasks to be separable. Third, we present the generalized framework. Finally, we show separable optimization task formulations for four example domains.
4.1 Problem definition and notation
We now generalize the previously introduced problem of minimizing misclassification score to any decision tree optimization task by using common DP notation. Given a state space and solution space V, we define:
Definition 4.1 (Optimization task). An optimization task is described by six components:
1. a cost function g: S x (F UC) + V that returns the cost of action a E FUK in state 8 E S, where the action is either assigning label E K. or branching on feature f E F; S that provides the next state after branching
2. transition function 1. S x F (0, left or right on fcature f. denoted by f or f E F (0.
3. comparison operator >
V + {0, 1) that determines Pareto dominance;
4. a combining operator @ : V x V - V that combines solution values to one value;
> {0, 1) that determines feasibility of given solution and state s; 6. and an initial state su E S.
5. constraint e:
For all optimization tasks in this paper, the state s can be described by the dataset DD and the branching decisions in parent nodes. The transition function is given by ((D F); f) = (D,, F {f)), and the initial state is (D.0). But our framework extends beyond this as well.
When minimizing misclassifications, the cost function is ((, k) [( k) E D D k}}; the comparison operator > <; the combining operator @ is addition and constraint e returns all solutions as feasible. Similarly, more complex objectives, such as F1-score and group fairness, which do not fit the conditions of DL.8 [66], can be defined by using these building blocks. We show four examples in Section 4.4.

---

L1
F1
1.2
Figure I: An example tree of depth two with five decision variables: two branching decisions Fl and F2, and three leaf node label assignments: L1, L22, and L3.
The final cost of a tree (B,L, b, with root node is now given by calling C(so, the following recursive function, which generalizes Eq. (1):
if E C(s. u) ( C(t(s, b(u)), uz) @ O(t(s,b(u)), un) @ g(s, u B
[g(s
(4)
In leaf nodes, the of tree given by cost function g. In branching nodes, the combining operator @ combines the cost of the left and right subtree and the branching costs.
Given optimization task (g t,, se) and maximum tree depth d, the aim is to find tree (or Pareto front trees) that satisfies the constraint and optimizes (according to the comparison operator >-) the cost C.
With this definition of an optimization task, we can generalize several of the concepts introduced in the preliminaries. Let @ describe set of possible solutions and let
feas( θ s) = {or E θ c(v, s) = 1}
(5)
be the subset of all feasible solutions in é for state s. The optimal set of solutions is given by
opt (+; 8) = nondom (feas( (0, +)),
(6)
the Pareto front of feasible solutions in θ, with nondom depending on the comparison operator > Furthermore, we generalize the definition for merge from [19]:
merge(01, θ2 8, (V1 U/2 g(s, f) 01 E O1 U2 O2)
This returns all combinations of solutions from sets O and O₂ by using the combining operator e
4.2 Separability
An optimization task is separable if optimal solutions to subtrees be computed independently of other subtrees. For example, in the tree in Fig. 1, the optimal label L3 should be independent the branching decision F2 and labels LI and L2. Label L2 should be independent of LI and L3.
Definition 4.2 (Separable). An optimization task is separable and only the optimal solution to any subtree can be determined independently of any of the decision variables that are not part of that subtree or the parent nodes' branching decisions.
The general idea to prove that an optimization task satisfies Def. 4.2 is to use complete induction over the maximum tree depth d. For the base step (d 0) sufficient to require the cost and transition functions to be Markovian: their output should depend only the current state and the chosen decision. For the induction step (d >> O), we need to show that the optimization task satisfies the principle of optimality [9]: that optimal solutions for trees of depth d can be constructed from only the optimal solutions to its subtrees and the new decision (see Def. A.1). summary:
Proposition 4.3. An optimization task (g, >, O C, so) is separable if and only if its cost function and transition function are Markovian and the task satisfies the principle of optimality,
A full proof for this and all subsequent propositions and theorems can be found in Appendix A.
To satisfy the principle of optimality, the combining operator @ must preserve order over and the constraint e must be monooonic. These two notions are explained next.
We introduce the new notion order preservation that guarantees that any combination of optimal solu- tions using the combining operator @ always dominates a combination with at least one suboptimal solution. Many objectives, such as costs, are additive with < as the > operator. Addition preserves order over <. However, addivity is not a necessary condition. We present order preservation instead necessary condition (see Appendix A.2).
5

---

Definition 4,4 (Order preservation). A combining operator @b preserves order over given compara- tor > if for any given state s, feature f and solution sets I and Ø2 with i = t(s, f), $2 t(s, f). E opt (01,81 81), of E 1 and 12 opt (02, 82), with in > fi. then t 02 o @ v2 (and U/ G 0 12 i oi, if @ not commutative).
To guarantee that applying feas defined in Eq. (5) does not prune any partial solution that is part of the final optimal solution, constraint must be anti-monotonic [66]: if constraint violated in tree, it is also violated in any tree of which this tree is subtree. However, in order to speak of necessary condition, we redefine anti- aattmmonotonicity to require that any solution which is constructed from at least one subsolution that is infeasible, cannot be an optimal solution.
Definition 4.5 Anti-mmootoonic). A constraint is anti-monotonic if for any state s, feature f and solution sets 1 and 22 with 81 t(s, f), $2 = ((s, f), with 2i 2 and U/ E O2 -c(1,, 81) or if (c $2), then @ U/2 & opt (0, s).
Minimum support (minimum leaf node size) is an example of an anti-monotonic constraint [66].
With these conditions and definitions in place, we have the necessary and sufficient conditions for separability and can present the main theoretical result of this paper:
Theorem 4.6. An optimization task o (g. t, >, O c, so) separable if and only if cost function and transition function L are Markovian, its combining operator 4 preserves order over its comparison operator > and the constraint e anti-monotonic.
4.3 Dynamic programming formulation
We now present the general DP framework STreeD (Separable Trees with Dynamic programming, pronounced as street):
{ opt (Ukext ((s,) ((,,) ):s) opt (UJEz merge (T(t(s, f), 1), 1), f). 1)
d=
T(s,d)
(8)
d>0
Pseudo-code for STreeD and additional algorithmic techniques for speeding up computation, such as a special depth-two solver, caching. and upper and lower bounds, as well as techniques for sparse trees and hypertuning, the use of these techniques. Furthermore, in Appendix we prove the following Theorem:
be found in Appendix B. The appendix also provides the conditions for
Theorem 4.7. STreeD, as defined Eq. finds the Pareto front for any optimization task that is separable according Def. 4.2.
4.4 Examples of separable optimization tasks
To illustrate the flexibility of STreeD, we present four diverse example applications for which separable optimization tasks can be formulated. The first two are also covered by the additivity condition from [66]. The last two do not fit this condition but are covered by our framework.
Cost-sensitive classification Cost-sensiting classification considers costs related to obtaining (mea- suring) the value of features in addition to misclassification costs [55]. Typical applications are in the medical domain when considering expensive diagnostic tasks and asymmetrical misclassification costs. See Appendix C for a more comprehensive introduction and related work.
Let D be the instances in leaf node and let Mg,e be the misclassification costs when instance with true label & is assigned label h and let m (F, [F be the costs of obtaining the value of feature f (this value also depends on the set previously measured features F, because we consider that some tests can be performed in group and share costs). This results in the following cost function:
(( R) = Σ M
((DD, F), = |D] mF(Ff1
(x.A)D
This optimization task separable because the function g is Markovian, the combination operator ( is addition, and the comparison operator is <.

---

Prescriptive policy generation Decision trees can also be used to prescribe policies based on historical data, to maximize the expected reward (revenue) of the policy [12, 45]. An example is medical treatment assignment based on historical treatment response. This is done by reasoning over counterfactuals (the expected outcome if an action other than the historical action was taken).
In Appendix D we provide related work and show three different methods for calculating the expected reward from the literature: regress and compare, inverse propensity weighting, and the doubly robust method. The cost function for each of these is Markovian and the combining operator is addition. Therefore, prescriptive policy generation can be formulated as a separable optimization task. It also possible to add constraints to the policy, for example, when maximizing revenue under a capacity constraint. We show in Appendix A.4 that capacity constraints are also separable.
Nonlinear classification metrics Nonlinear objectives such as F1-score and Matthews correlation coefficient are typically used for unbalanced datasets. Demirović and Stuckey [19] provide a globally optimal DP formulation for optimizing such nonlinear objectives for binary classification. STreeD can also optimize for these metrics. For Fl-score, for example, one can formulate a combined optimization task that measures the false positive rate for each class k E {0. 1} as separate optimization task:
{ H(x,)) k))
E
D
W +RH
k= otherwise
9b (D,
(10)
Both of these tasks are separable, and in Appendix A.5 we show that multiple separable tasks can be combined into a new separable optimization task that results in the Pareto front for misclassifications for each class. This Pareto front can then be used to find the decision tree with, e.g., the best Fl-score. See Appendix for more related work and other details.
Group fairness Optimizing for accuracy result in unfair results for different groups and therefore several approaches have been recommended to prevent discrimination [60]. one of which is demographic parity [28], which states that the expected outcome for two classes should be the same. Previous MIP formulations for group fairness have been formulated [1, 44] and recently also a DP formulation, even though at first hand group fairness constraint does not seem separable [53].
Let a denote a discrimination-senniin sensiiivve binary feature and y a binary outcome, with y = the preferred outcome and & the predicted outcome; then demographic parity can be described as satisfying Più = 1 a 1) P(ù = 1 a = 0). This requirement is typically satisfied by limiting the difference to some percentage 5. Let (aa) be the number of people in group a, and (a)) the people not in group a. The demographic parity requirement can now be formulated as two separable threshold constraints:
[Dal
k ==
IDa N
h
(D, =
Nia
9a (D( =
(11)
D
k = 0
ID
h
[(a)
((a)
These cost functions with the two threshold constraints that limit both to 1 + ō, and an accuracy objective can be combined into one separable optimization task as shown in Appendix A.4 and A.5, and therefore it can be solved to optimality with STreeD. We show the derivation of these constraints, similar derivation for equality of opportunity, and more related work in Appendix F. Note that we require demographic parity on the whole tree and not on every subtree. In fact, requiring demographic parity on every subtree is an example of constraint that does not satisfy anti-monotonicity.
4.5 Comparison to previous theory and methods
Dynamic programming theory In contrast to what is common in general DP theory, our theory does not assume solution values to be real valued [48] or totally ordered [29]. For example, Karp and Held [48] formulate the monotonicity requirement of a DP as follows: for a given state action cost c and data p. let h(c, s, a. p) be the cost of reaching state t(s, a) through an input sequence that reaches state with cost c. Monotonicity holds iff c1 S C2 implies h((1, a. p) S h(C2, 8, a, p). In words: if a partial input sequence A, with cost e₁ dominates another input sequence Ag with 02, then any other input sequence that starts with A₁ dominates any other input sequence that starts with A2, thus satisfying the principle of optimality. This notion is símilar to our order preservation, but we do not assume that the costs are real valued or that the costs are totally ordered.
7

---

Similarly. Li and Haimes [51] show how multiple optimization tasks can be combined into one, as we also show in Appendix A.5. They construct separable DP formulation for optimization tasks that can be deconstructed into a series of optimization tasks, each of which is separable and monotonic. Their method also returns the set of nondominated solutions. However, their theory assumes that the solution value for each sub-objective is real, completely ordered, and additive. This limits their theory to element-wise additive optimization tasks. Our theory does not share these limitations.
Dynamic programming approaches In comparison to the DP methods DL8 [66] and GOSDT [52], STreeD covers wider variety of objectives and constraints. Both STreeD and DL8 require constraints to be anti-monotonic. GOSDT does not support constraints. DL8 and GOSDT require additivity, whereas STreeD requires the less restrictive condition order preservation (see Def. 4.4). Moreover, STTeee) can cover a range of new objectives by also allowing for objectives and constraints with a partially defined comparison operator, and by allowing to combine several such objectives and constraints. Examples of problems that could not be solved to global optimality by DL8 and GOSDT, but can be solved with our framework, are group fairness constraints, nonlinear metries, and revenue maximization under a capacity constraint. Moreover, compared to DL8 and GOSDT, STreeD implements several algorithmic techniques for increasing scalability, such as a specialized solver for trees up to depth two (see Appendix B).
Other approaches MIP can be used model many optimization tasks, including non-separable optimization tasks. For example, optimizing decision tree policies for Markov Decision Processes can be optimized with MIP [89], but it is not clear how to do this with DP. However, MIP cannot deal with separable, but non-linear objectives, such Fl-score. Moreover, our experiments also show, DP outperforms the scalability of MIP for the considered optimization tasks by several orders of magnitude.
CP so far has only been applied maximizing accuracy [84] and (Max)SAT only maximizing accuracy [34, 76] or finding the smallest perfect tree [42, 64].
Dunn [26] proposes framework that can optimize many objectives for decision trees (see also [11]). Because of MIP's scalability issues, they propose a local search method based on coordinate descent. However, this method does not guarantee globally optimal solution. Moreover, their method is not able to find Pareto front that optimizes multiple objectives at the same time.
Experiments
To show the flexibility of STreeD, we test it on the four example domains introduced in Section 4.4. Additionally, we compare STreeD with two state-of-the-aar dynamic programming approaches for maximizing classification accuracy. STreeD is implemented in C++ and is available Python package.' All experiments are run on 2.6 GHz Intel i7 CPU with 8GB RAM using only one thread. MIP models are solved using Gurobi 9.0 with default parameters [33].
In our analysis, we focus on scalability performance comparison to the saae-of-the-art optimal methods (if available). The following shows a summary of the results. The setup of all experiments, more extensive results, and related work of the application domains is provided in the appendices C-G.
5.1 Cost-sensitive classification
For cost-sensitive classification, we compare STreeD with TMDP [58] both in terms of average expected costs and scalability. A direct fair comparison with TMDP is difficult, because TMDP provides no guarantee of optimality, allows for multi-way splits, and is run without a depth limit, We test STreeD and TMDP on three setups for 15 datasets from the literature and report normalized costs. We tune S STreeD with a depth limit of d = 4. In Appendix C we show extended results and also compare with several heuristics from the literature. To our knowledge, no MIP methods for cost-sensitive classification including group discounts (i.e., when certain features are tested together, the feature cost decreases) exist, and therefore are not considered here.
For 21 out of 45 scenarios STreeD generates trees with significantly lower average out-of-sample costs than TMDP (p-value 5%). TMDP has lower costs in I out of 45 scenarios. In all other scenarios,
8

---

100%
100%
Trees compated
Teees computed
73%
73%
50%
50%
STreeD
STreeD
Jo-PPG-MIP
TMDP
CAIPWL-OR
0%
0%
10
10'
10a
10
10
10
1000%
20%
40%
Runtime
Runtime (8)
MIP gap at lime--ut
(a) Cost-sensitive classification
(b) Prescriptive policy generation (synthetic & Warfarin)
100%
100%
Tress computed
Tres computed
STreeD r... Fair MIP
73%
73%
Aghaci MIP
50%
50%
STree
MurTree (nonlinear)
0%
0%
10"
10
10a
10a
10
10a
0%
20%
40%
Runtime (s)
Runtime (s)
MIP gap at time-out
(c) Nonlinear classification metrics: Fl-score
(d) Group fairness: Demographic parity
The percentage instances for which the algorithm returns the (optimal) tree within the given runtime (higher is better). When MIP methods hit the timeout, the plot shows which percentage of problems are solved within the reported MIP gap. Instances for which all methods return a tree within second left out. Note the logarithmic x-axis.
Figure 2:
there is no significant difference. Both methods return trees that perform better and are smaller than those constructed by heuristics. Fig. 2a shows that STreeD is significantly faster than TMDP. Thus, can be concluded that STreeD on average has slightly better out-of-sample performance than TMDP, returns trees of similar size, and is significantly faster than TMDP
5.2 Prescriptive policy generation
For prescriptive policy generation, we compare our method with the MIP model Jo-PPG-MIP [43] and the recursive tree search algorithm CAIPWL-opt [92]. Jo et al. [43] show both analytically and through experiments the benefit of their method over [12] and [45]. Their method constructs optimal binary trees based on three different teacher models: regress and compare, inverse propensity weighting, and a doubly robust method. CAIPWI--ppt constructs optimal binary trees based on the doubly robust method. Our method implements the same teacher models; thus, all methods find the same solution. Therefore, we compare here only the runtime performance.
As described in detail in Appendix D. we test on the Warfarin dataset [39] and generate 225 training scenarios with 3367 instances and 29 binary features and run each algorithm with a given maximum depth of d E [1, 5). We also generate 275 synthetic datasets with 10, 100, and 200 binary features, each with 500 training samples, and run each algorithm on every scenario with given maximum depth of d = 2, and 3. When Jo-PPG-MIP hits the timeout of 300 seconds, we report the MIP gap.
Fig. 2b shows that STreeD find optimal solutions orders of magnitude faster than both Jo- PPG-MIP and CAIPWL-opt while obtaining the same performance in maximizing the expected outcome.
5.3 Nonlinear classification metrics
For assessing STreeD's performance on optimizing nonlinear metrics such Fl-score, we first compare it with the existing nonlinear MurTree method [19]. We tasked both methods to find optimal trees of depth 3-4 according to an Fl-score metric for 25 binary classification datasets from literature. Fig. 2c shows that STreeD, while being more general, is on average seven times faster than MurTree (computed with geometric mean). This performance gain part due to a more efficient computation of the lower and upper bounds, explained in Appendix B.

---

This shows that STreeD can be applied to nonlinear objectives and even improves on the performance of satl--of-thharrtt specialized DP method for this task.
5.4 Group fairness
For group fairness, we follow the experiment setup from [53] as explained in Appendix F. The task is to search for optimal trees for 12 datasets and for trees of depth d [1,3] under demographic parity constraint with at most 1% discrimination on the training data. We compare to the DP-based method DPF [53] and the MIP methods Aghaei-Fair-MIP [1] and Jo-Fair-MIP [44]. When the MIP methods hit the timeout of 600 seconds, we report the MIP gap.
Fig. 2d shows the runtime results. As expected, DPF performs best since it is a DP method specifically designed for this task. STreeD is more general and yet remains close to DPF, while being several orders of magnitude faster than both MIP methods. In Appendix F we further show how STreeD is the first optimal DP method for optimizing an -oulity-of-opportunity constraint.
It can be concluded that STreeD allows for easy modeling of complex constraints such as demographic parity and equality of opportunity while outperforming MIP methods by a large margin.
5.5 Classification accuracy
Finally, we compare STreeD with two state-of-the-at dynamic programming approaches for optimal decision trees that maximize classification accuracy: DL8.5 [3, 4] and MurTrre [20]. All three methods find optimal decision trees for maximum depth four and five for 25 binary classification datasets from the literature. The results in Appendix G show that on average STreeD is more than six times faster than DL8.5 and is close to MurTree, with MurTree being 1.25 faster (computed with the geometric mean). Since DL8.5 outperforms DL8 [3] and MurTree outperforms GOSDT by large margin [20], we can conclude that STreeD not only allows for a broader scope of optimization tasks than DL8 and GOSDT, but is also more scalable.
6 Conclusion
We present STreeD: a general framework for finding optimal decision trees using dynamic program- ming (DP). STreeD can optimize broad range of objectives and constraints, including nonlinear objectives, multiple objectives, and non-additive objectives, provided that these objectives are sep- arable. We apply DP theory to provide necessary and sufficient requirements for such separability in decision tree optimization tasks and introduce the new notion order preservation that guarantees the principle of optimality [9]. We show that these results are more general than the state-of-the- general DP solvers for decision trees [52, 66].
We illustrate the generalizability of STreeD in five application domains, two of which are not covered by the previous general DP solvers. For each, we present a separable optimization formulation and compare STreeD's scalability to the domain-specific STreeD sustains or improves the scalability performance of DP methods, while being flexible, and outperforms mixed-integer programming methods by large margin on these example domains.
oftte-of-the-rrt, The results show that
STreeD allows for a much broader set of applications than presented here. Therefore, future work should further investigate STreeD's performance additive objectives. STreeD could also be used to further develop optimization of trees that lack explanation redundancy [40]. Finally, STreeD could further be improved by adding multi-way branching and allowing for continuous features.
for example, regression tasks and other non-
References
[1] Sina Aghaei. Mohammad Javad Azizi, and Phebe Vayanos. Learning Optimal and Fair Decision Trees for Non-Discriminative Decision-Making. In Proceedings of AAAI-19, pages 1418-1426, 2019.
[2] Sina Aghaei, Andrés Gómez, and Phebe Vayanos. Strong Optimal Classification Trees. arXiv preprint urXiv:2103115663 2021.
[3] Gael Aglin, Siegfried Nijssen, and Pierre Schaus. Learning Optimal Decision Trees Using Caching Branch-and Bound Search. In Proceedings of AAAI-20, pages 1446-115,,,, 2020.
10

---

[4] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. PyDL8.5: Library for Learning Optimal Decision Trees. In Proceedings of LJCAI-20, pages 5222-5224, 2020.
[5] Maxime Amram, Jack Dunn, and Ying Daisy Zhuo Optimal Policy Trees, Machine Learning, 111(7): 2741-2768, 2022.
[6] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine Bias, May 2016. URL https:// www www.proppe www.propublice wttpiiaa..rrrrrrreeee orw.artticleeencciieeeeeee-eeeee blas risk assessments in- criminal- sentencing.
[7] Susan Athey and Guido Imbens. Recursive partitioning for heterogeneous causal effects. Proceedings of the National Academy of Sciences, 113(27):7333-766 2016.
Florent Avellaneda. Efficient Inference of Optimal Decision Trees. In Proceedings of AAAI-20, pages 3195-3202, 2020.
Richard Bellman. Dynamic Programmning. Princeton University Press, Princcton, NJ, 1957.
[10] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7): 1032)) 2017.
[11] Dimitris Bertsimas and Jack Dunn. Machine Learning Under a Modern Optimization Lens. Dynamic Ideas, Belmont, MA. 2019.
[12] Dimitris Bertsimas, Jack Dunn, and Nishanth Mundru. Optimal Prescriptive Trees. INFORMS Journal on Optimization, 1(2):164-188) 2019.
[13] Max Biggs, Wei Sun, and Markus Eul. Model distillation for revenue optimization: Interpretable personal- ized pricing. In Proceedings of MLR-21, pages 946-956, 2021.
[14] Leo Breiman, Jerome Friedman, Richard A. Olshen, and Charles J. Stone. Classification and Regression Trees. Wadsworth and Brooks, Monterey, CA, 1984.
[15] Miguel A. Carreira- Carreira-Perpinán and Pooya Tavallali. Altemating Optimization of Decision Trees, with Application to Learning Sparse Oblique Trees. In Advances in NeurlPS- 18, 2018.
[16] Simon Caton and Christian Haas. Fairness in Machine Learning: A Survey. ACM Computing Surveys, 2023.
[17] Paulo Cortez and Alice Maria Gonçalves Silva. Using data mining to predict secondary school student performance. In A. Brito and J. Teixeira, editors, Proceedings of 5th FUture BUsiness TEChnology Conference, pages 12, 2008.
[18] Vinícius G. Costa and Carlos E. Pedreira. Recent Advances in Decision Trees: An Updated Survey. Artificial Intelligence Review, 56:4765-4880 2023.
[19] Emir Demirović and Peter J. Stuckey. Optimal Decision Trees for Nonlinear Metrics. In Proceedings of AAAI-21, pages
2021.
[20] Emir Demirović, Anna Lukina, Emmanuel Hebrard, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Peter Stuckey. MurTree: Optimal Classification Trees via Dynamic Programming and Search. Journal of Machine Learning Research, 23(26):1 47, 2022.
[21] Emir Demirović, Emmanuel Hebrard, and Louis Jean. Blossom: an Anytime Algorithm for Computing Optimal Decision Trees. In Proceedings of ICML-23, pages 7533-7562, 2023.
[22] Thomas G. Dietterich. Overfitting and Undercomputing in Machine Learning. ACM Computing Surveys, 2763)332 1995.
[23] Pedro Domingos. Metacost: A General Method for Making Classifiers Cost-Sensitive. In Proceedings of KDD-99, pages 155-164, 1999.
[24] Dheeru Dua and Casey Graff. archive.ics.uci. edu/ml.
UCI Machine Learning Repository, 2017. URL http://
[25] Miroslav Dudík, John Langford, and Lihong Li. Doubly Robust Policy Evaluation and Learning. In Proceedings of ICML-11, pages 1097-1104, 2011.
[26] Jack William Dunn. Optimal Trees for Prediction and Prescription. PhD thesis, Massachusetts Institute of Technology, 2018

---

[27] Dutch Central Bureau for Statistics. Dutch Census 2001 public use files (anonymized 1% samples from the microdata files). DANS, 2001. URL https::/easa...teeee/e dans. www.kkawwwlln.........m www.a///aaaaatttta/e/eeeee/////e : 32357.
[28] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairesss Through Awareness. In Proceedings of ICTS '12, pages 214-226, 2012.
[29] Salah E. Elmaghraby. The Concept of "State" in Discrete Dynamic Programning. Journal of Mathematical Analysis and Applications, 29(3)5523-577, 1970.
[30] FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berkeley. Ex- plainable Machine Learning Challenge, 2018. URL https: www.ooitt...icoo..omooooo exppa///eeeeaaleeeeeeee machine- Sechine-learning learning- challenge.
[31] Philip J. Fleming and John J. Wallace. How not to lie with statistics: the correct way to summarize benchmark results. Communications of the ACM, 29(3)2218-221, 1986.
[32] Alberto Freitas, Altamiro Costa-Pereira, and Pavel Brazdil. Cost-Sensitive Decision Trees Applied to Medical Data. In Proceedings of the International Conference on Data Warehousing and Knowledge Discovery (DaWaK-2007) pages 303 003-312,27 2007.
[33] Gurobi Optimization LLC. Gurobi Optimizer Reference Manual, 2022. URL httpps:/www.gurobbr
[34] Hao Hu, Mohamed Siala, Emmanuel Hebrard, and Marie-José Huguet. Learning Optimal Decision Trees with MaxSAT and its Integration in AdaBoost. In IJCAI-PRICAI 2020, pages 17701176 2020.
[35] Qinghua Hu, Xunjian Che, Lei Zhang, David Zhang, Maozu Guo, and Daren Yu. Rank Entropy- Based Decision Trees for Monotonic Classification. IEEE Transactions on Knowledge and Data Engineering, 24 (11):2052-2064, 2011.
[36] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal Sparse Decision Trees. In Advances in NeurlPS-19. pages 7267-7275, 2019.
[37] Kaixun Hua, Jiayang Ren, and Yankai Cao. A Scalable Deterministic Global Optimization Algorithm for Training Optimal Decision Tree. In Advances in NeurlPS-22, pages 8347-8359, 2022.
[38] Laurent Hyafil and Ronald L. Rivest. Constructing optimal binary decision trees is comoleeee Informa- tion processing letters, 5(1):1--7,, 1976.
[39] International Warfarin Pharmacogenetics Consortium. Estimation of the Warfarin Dose with Clinical and Pharmacogenetic Data. New England Journal of Medicine, 360(8);753-764 2009.
[40] Yacine 1z7a, Alexey Ignatiev, and Joao Marques-Silva. On Tackling Explanation Redundancy in Decision Trees. Journal of Artificial Intelligence Research. 75:261-321, 2022.
[41] Andras Janosi, William Steinbrunn, Matthias Pfisterer, and Robert Detrano. Heart Cleveland Dataset, 1988.
URL. https://archhii www.rriicc...ieeue.. wwt.c/ed.///.aaatatteeeeee//e//e http///taasttteeeerreeeeeee
[42] Mikoláš Janota and António Morgado. SAT-Based Encodings for Optimal Decision Trees with Explicit Paths. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (SAT 2020), pages 501-518, 2020.
[43] Nathanael Jo. Sina Aghaei, Andrés Gómez, and Phebe Vayanos. Learning Optimal Prescriptive Trees from Ohservational Data. arXiv preprint arXiv:2/08. 13628, 2021.
[44] Nathanael Jo, Sina Aghaei, Jack Benson, Andrés Gómez, and Phebe Vayanos. Learning Optimal Fair Classification Trees, arXiv preprint arXiv:2201.0990 2022.
[45] Nathan Kallus. Recursive Partitioning for Personalization using Observational Data. In Proceedings of ICML-17, pages 1789-1798, 2017.
[46] Faisal Kamiran and Toon Calders. Classifying without discriminating. In 2nd International Conference on Computer, Control and Communication, pages 333-338, 2009.
[47] Faisal Kamiran, Toon Calders, and Mykola Pechenizkiy. Discrimination Aware Decision Tree Learning. In Proceedings of ICDM-10, pages 869 869-874, 2010.
[48] Richard M. Karp and Michael Held. State Processes and Dynamic Programming. SIAM Journal on Applied Mathematics. 15(3):693-718) 1967.
12

---

[49] Jakub Kuzilek, Martin Hlossa, and Zdenek Zdrahal. Open university learning analytics dataset. Scientific data, 4:170171, 2017.
[50] Tai Le Quy. Arjun Roy, Vasileios Iosifidis. Wenbin Zhang, and Eirini Ntoutsi. A survey on datasets for fairness-aware machine learning. Wiley Intendisciplinary Reviews: Data Mining and Knowledge Discovery. page e1452, 2022.
[51] Duan Li and Yacov Y. Haimes. Extension of Dynamic Programming to Nonseparable Dynamic Optimiza- tion Problems. Computers Mathematics with Applications. 21 56, 1991.
[52] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and Scalable Optimal Sparse Decision Trees. In Proceedings of ICML-200, pages 6150-6160, 2020.
[53] Jacobus G. M. van der Linden, Mathijs M. de Weerdt, and Emir Demirović. Fair and Optimal Decision Trees: A Dynamic Programming Approach. In Advances in NeurlPS-22, pages 38899-38911, 2022.
[54] Charles X. Ling, Victor S. Sheng, and Qiang Yang. Test Strategies for Cost-Sensitive Decision Trees.
IEEE Transactions on Knowledge and Data Engineering, 18(9):1055-106, 2006.
[55] Susan Lomax and Sunil Vadera. A Survey of Cost-Sensitive Decision Tree Induction Algorithms. ACM Computing Surveys, 45(2):1-35, 2013.
[56] Susan Lomax and Sunil Vadera. A Sost-Sensitive Decision Tree Learning Algorithm based on a Multi- Armed Bandit Framework. The Computer Journal, 60(7):941 9566, 2017.
[57] Susan Elaine Lomax. Cost-Sensitive Decision Tree Learning using Multi-Armed Bandit Framework. PhD thesis, University of Salford, 2013.
[58] Shlomi Maliah and Guy Shani. Using POMDPs for learning cost sensitive decision trees. Artificial Intelligence, 292: 103400, 2021.
[59] O. L. Mangasarian and W. H. Wolberg. Cancer Diagnosis via Linear Programming. SIAM News, 23(5): 1-18, 1990.
[60] Ninarch Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A Survey on Bias and Fairness in Machine Learning. ACM Computing Surveys, 54(6):1-35, 2021.
[61] Fan Min and William Zhu. A Competition Strategy to Cost-Sensitive Decision Trees. In Proceedings of the International Conference on Rough Sets and Knowledge Technology (RSKT), pages 359-368, 2012.
[62] Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank telemarketing, Decision Support Systems, 62:22-31 2014.
[63] Géraldin Nanfack. Paul Temple, and Benoît Frénay. Constraint Enforcement on Decision Trees: A Survey.
ACM Computing Surveys, 54(10):1-36, 2022.
[64] Nina Narodytska, Alexey Ignatiev, Filipe Pereira, and João Marques-Sin Silva. Learning Optimal Decision Trees with SAT. In Proceedings of IJCAI-18, pages 1362-1368, 2018.
[65] Siegfried Nijssen and Elisa Fromont. Mining Optimal Decision Trees from Itemset Lattices. Proceedings of SIGKDD-07, pages 530-539, 2007.
[66] Siegfried Nijssen and Elisa Fromont. Optimal constraint- decision tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21(1))9-51, 2010.
[67] Siegfried Nijssen and Vinasétan Ratheil. Time constrained DL8. 5 using Limited Discrepancy Search. In Proceedings of ECML-PKDDD-22, pages 443-459, 2022.
[68] Steven W. Norton. Generating Better Decision Trees. In Proceedings of IJCAI-89, pages 800-805, 1989.
[69] Marlon Núñez. The Use of Background Knowledge in Decision Tree Induction. Machine Learning, 6(3): 231-2 1991.
[70] Dino Pedreschi, Salvatore Ruggieri, and Franco Turini. Discrimination-awan Data Mining, In Proceedings of SIGKDD-08, pages 560 568, 2008
[71] Rok Piltaver, Mitja Luštrek, Matjaž Gams, and Sandra Martinčić-Ipšie What makes classification trees comprehensible? Expert Systems with Applications, 62:333-344 346, 2016.
[72] J. Ross Quinlan. Induction of Decision Trees. Machine Learning, 1(1):81-106, 1986.
13

---

[73] J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc, San Francisco, CA, 1993.
[74] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Noture Machine Intelligence, 1(5):206-215, 2019.
[75] André Schidler and Stefan Szeider. SAT-based Decision Tree Learning for Large Data Sets. In Proceedings AAAI-21, pages 3904-3912, 2021.
[76] Pouya Shati, Eldan Cohen, and Sheila A. Mcllraith. SAT-based optimal classification trees for non-binary data. Constraints, 28(2):166-22)) 202, 2023.
[77] Beata Strack, Jonathan P DeShazo, Chris Gennings, Juan L Olmo, Sebastian Ventura, Krzysztof Cios, and John N Clore. Impact HbAlc measurement on hospital readmission rates: analysis of 70,000 clinical database patient records. BioMed research international, 2014.
[78] Jan Struyf and Sašo Džeroski. Clustering Trees with Instance Level Constraints. In Proceedings of ECML-07, pages 359-370, 2007.
[79] Shivaram Suhramanian, Wei Sun, Youssef Drissi, and Markus Ett. Constrained Prescriptive Trees via Column Generation. In Proceedings of AAAI-22, pages 4602-46101 2022.
[80] Ming Tan. Cost-Sensitive Learning of Classification Knowledge and its Applications in Robotics, Machine Learning, 13(1):7-33, 1993.
[81] Turing Institute (Glasgow). Statlog (Vehicle Silhoucttes) Dataset, 1987. wrchive.ics.uci.ee
URL. https://
[82] Peter D. Turney, Cost-Sensitics Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm. Journal of artificial intelligence research, 2:369-409, 409, 1995.
[83] Peter D. Turney. Types of Cost in Inductive Concept Learning. In Proceedings of the ICML'2000 Workshop Cost-Sensitive Learning, pages 15-21, 2000.
[84] Hélene Verhaeghe, Siegfried Nijssen, Gilles Pesant, Claude-Guy Quimper, and Pierre Schaus. Learning Optimal Decision Trees using Constraint Programming. Constraints, 25(3):226-22 2500, 2020.
[85] Sicco Verwer and Yingqian Zhang. Learning decision trees with flexible constraints and objectives using integer optimization. In Proceedings of CPAJOR-17, pages 94-103, 2017.
[86] Sicco Verwer and Yingqian Zhang. Learning Optimal Classification Trees Using Binary Linear Program Formulation. In Proceedings of AAAI-19, pages 1625-1632, 2019.
[87] Matheus Guedes Vilas Boas, Haroldo Gambini Santos, Luiz Henrique Campos Merschmann, and Greet Vanden Berghe. Optimal Decision Trees for the Algorithm Seleetion Problem: Integer Programming Based Approaches. International Transactions Operational Research, 28(5):2759 2781, 2021.
[88] Daniel Vos and Sicco Verwer. Robust Optimal Classification Trees against Adversarial Examples. In Proceedings of AAA1-22, pages 1920-8528, 2022.
[89] Daniël Vos and Sicco Verwer Optimal Decision Tree Policies for Markov Decision Processes. arXiv preprint 2rXiv:2001.13185 2023.
[90] Jingbo Wang. Yannan Li, and Chao Wang. Synthesizing Fair Decision Trees via Iterative Constraint Solving. In Proceedings of the International Conference on Computer Aided Verification, pages 364-385, 2022.
[91] Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi, Margo Seltzer, and Cynthia Rudin. Exploring the Whole Rashomon Set of Sparse Decision Trees. In Advances in NeurlPS-22, pages 14071-14084, 2022.
[92] Zhengyuan Zhou, Susan Athey, and Stefan Wager. Offline Aulti-Action Policy Learning: Generalization and Optimization. Operations Research, (1):1148-18, 2022.
[93] Haoran Zhu, Pavankumar Murali, Dzung T. Phan, Lam M. Nguyen, and Jayant R. Kalagnanam. A Scalable blP-based Method for Learning Optimal Multivariate Decision Trees. In Advances in NeurlPS-20, pages 1771-1781, 2020.
[94] Valentina Bayer Zubek and Thomas G. Dietterich. Pruning Improves Heuristic Search for Cost-Sensitive Learning. In Proceedings of [CML-02, pages 19-26, 2002.
14

---

[95] M. Zwitter and M. Soklic. Breast Cancer Dataset. URL htt.bpppr.aarraae....ccedeee/aas Braner.
[96] M. Zwitter and M. Soklic. Lymphhgraphy Dataset, 1988. URI. UEL..ttp:e//aaccheeeeeaad.ddtddd
datasetss/Lmmphogaapyy
[97] M. Zwitter and M. Soklic. Primary Tumor Dataset, 1988. URL http:://archiie..c.......tt
intaseta/primarytuurre
15

---

A Proofs
The following sections provide proof' for the propositions and theorems from the main text. We first prove Prop. 4.3 that claims that an optimization task is separable if it has a Markovian cost and transition function and if it satisfies the principle of optimality. We then prove Theorem 4.6 about the necessary and sufficient conditions for an optimization task to be separable. Next, we prove Theorem 4.7 about STreeD being able to solve separable optimization tasks to optimality. We extend the theory of the main text by introducing anti onti-monotonic threshold constraints. Finally, we show how multiple separable optimization tasks can be combined into a new separable optimization task.
A.1 Proof of Prop. 4.3 about Separability
Def. 4.2 defines separability by stating that for a given optimization task the optimal solution to any subtree in tree search should be independent of any of the decision variables other than the decision variables of the subtree search and the parent node branching decisions. Prop. 4.3 states that this is the same saying that the optimization task has Markovian cost and transition function and satisfies the principle of optimality [9), i.e., optimal solutions can only be constructed from optimal solutions to subproblems:
Definition A.1 (Principle of Optimality). Let o = (g, t, G c, Su) be an optimization task, let s be a state, let, f be a branching decision, and let O, and O2 be all the solutions to subproblems with state (s, J) and J),, and let θ = merge(@), I 22, f). Then optimization task satisfies the principle of optimality if and only if for every state 8, branching decision f and solution sets O₁ and O2, the following holds:
opt (0, s) opt (merge(opt (O), f)), opt ((2, f)
(12)
With this definition in place, we can prove Prop. 4.3.
Proof. Prop. 4.3 requires two conditions: a Markovian cost and transition function, and the principle of optimality. To prove Prop. 4.3, we need to show that both conditions are necessary and sufficient. Therefore, we first show that if both conditions hold, the optimization task must be separable. We then show that if one of the two conditions of Prop. 4.3 fails, the optimization task is not separable.
Sufficient: To show that the two conditions of Prop. 4.3 are sufficient we use total induction over the tree depth d.
The base step (d = 0), considers the search for optimal leaf nodes. If a Markovian cost function g(s,, k) exists, the optimal label assignment can be determined by opt (s) This does
not depend on any decision variable other than the state & and the leaf node label assignment k: and therefore Def. 4.2 is satisfied for all tree searches up depth zero
The induction step (for d > 0) assumes Def. 4.2 is satisfied for all tree searches up to depth d 1. For these tree searches, optimal solutions can now be constructed by iterating over all possible branching decisions for the root node, using Eq. (12) to find optimal solutions when the root node branching decision is fixed, and using opt to select the optimal solution from the union of all these solution sets. Since neither the subtree search, nor Eq. (12), nor the transition function, nor the branching cost function, nor the union operator, nor the opt function depend on any decision variable other than the decision variables for this tree search and the parent node decisions, the optimal solution for this search can also be constructed independently of those variables.
Necessary conditions: If an optimization task is separable, a Markovian cost function and transition function necessarily exist. Since a node's state is the product of applying the transition function on the previous state, this state can be considered as a function of the initial state so, the parent nodes' branching decisions F, and the immediate action: the branching decision or the label assignment. Now assume that no Markovian cost and transition function exist. This means that the cost of an action cannot be expressed in terms of only the state, the immediate action, and the parent's branching decisions. This means that Def. 4.2 is not satisfied: a contradiction. Therefore a Markovian cost and transition function necessarily exists if optimization task is separable.
For tree searches with a depth larger than zero, optimal solutions should be able to be constructed from optimal solutions to subtree scarches, as defined in Eq. (12). Consider such subtree search,
16

---

which after deciding on the branching decision in its root node, creates two subproblems for the resulting children nodes. The optimal solution should be constructible from the optimal solution to these subproblems according to Eq. 12. If the optimal solution to this tree search cannot be constructed from the optimal solution to its subtree searches, then the optimal solutions to the subtree searches are not optimal: contradiction. Therefore Eq. (12) is a necessary condition.
L
A.2 Proof of Theorem 4.6 about Conditions for Separability
Theorem 4.6 states that an optimization task is separable if its cost and transition functions are Markovian, its combining operator preserves order over the comparison operator and its constraint is anti-monotonic.
To prove that these conditions are both sufficient and necessary, we need to show that the conditions mentioned in Theorem 4.6 are equivalent to those mentioned in Prop. 4.3. We will first show that these conditions are sufficient, and then that they are also necessary.
Proof. Let o (g, >, C C, so) be optimization task, for which it holds that the cost function g and transition function ć is Markovian, the combining operator @ preserves order over > and the constraint is mati-monotonic.
We will call an optimization task that satisfies Eq. (12) splittable. We begin by proving that is splittable. Consider any state s, any branching feature f. such that t(s. f) and 82 = t(s, f). and let O, 9 and 2₂ be sets of solutions such that = merge( 1 θ2 8, f). and let the optimal solutions from these sets be given by 0 == opt(O, s). 0 = (Pt 81) and 02 = 0pt((2,82)) Then, according to Eq. (12) an optimization task splittable if and only if:
B (mergeeee(f) 82, s)
(13)
For this to hold the solution 0 must be both a subset and superset of the right-hand side of Eq. (13). We consider both next. However, for brevity of notation, we leave out the states 81, $2 and the branching feature f.
1. 0 a subset:
A S opt(mergo(8) 02))
(14)
By definition Oe) C O, and therefore Eq. (14) is always true if
0 C merge(f1, 02)
(15)
This can be shown by contradiction: Assume that Eq. (15) is false. This means there must exist solution (pt O1, 22)). This means that this solution can be written as v = 01 4 U2, with U1 O₁ and 1/2 E O2. Because of the definition of merge, either v1 & 0g or vi & 0g. Assume w.l.o.g. that this is true for U1. If & 0,, this is either because it is filtered out by feas by nondom.
for which e & merge (0,, 0z). By definition
opt(O)
(a) If ei is filtered out by feas, then U1 E feas( Q1). This means that -c(r1). Because o is anti-monotonic, then by Def. 4.5 also in @ U2 & 0, which contradicts the assumption made before.
(b) If en is filtered out by nondom, then 3o1 0, vf V1- Now construct solution o vf @ U2. Because ( preserves order over > it holds that o' > v. This means that $ 6, contradicting our assumption.
In either case, the assumption is contradicted, and therefore Eq. (14) must be true
2. A a superset:
0 2 opt(merge(01.0.) 02),
(16)
Again, by contradiction, assume that Eq. (16) is false. This means there must exists solution v = in @ 12, with E opt (merge(0), 02)), such that e & 0. This means that either filtered out of 0 by feas by nondom.
17

---

(a) If is filtered out by feas, it cannot be member of opt(merge(8), 82)), since it also applies feas.
(b) u is dominated by another solution in 8, then there must exist a solution e' E 0 > but v' & (pt(mecg)(81; 02)). However, because of Eq. (14), this cannot be the case.
Again, either case, the assumption is contradicted, and therefore Eq. (16) is true.
Since both Eq. (14) and Eq. (16) are true, Eq. (13) must be true and thus o splittable.
Since both Prop. 4.3 and Theorem 4.6 share the conditions that the cost and transition function must be Markovian, and because o's cost and transition function are Markovian and is splittable, optimization task is separable by Def. 4.2. Since this holds for any optimization task that satisfies conditions of Theorem 4.6, these conditions are sufficient to prove separability.
The conditions are also necessary. The condition of Markovian cost and transition function is shared among Prop. 4.3 and Theorem 4.6 and therefore obviously necessary. Therefore, what is left to show is that order preservation and anti-monotonic constraints are necessary conditions to show the principle of optimality. For brevity of notation, we again leave out the states 8, 81, 82 and the branching feature f.
Order preservation Let θ merge(@), 92), with 0 opt(O), opt(@1) and 02 opt(O2).
Now assume that the splitting property holds: This means that for all v = dj @v2, with also V1 E 01 and 02 E 02 and the other way around. Now assume that order preservation is not necessary. This means 3o1 $ 01, with o' ví @ U2 Consider two cases: v' E 0, then of E 01: contradiction. However, if o' & 0, then also 6: contradiction.
Anti-monotonicity If the constraint is not anti- mnti-monotonic, then there exists solution 01 12 with -c(01), but with u E opt(O). If -c(v1), then vn & opt(O)). Thus, the splitting property is not satisfied.
Since each condition separately is necessary and all conditions together are sufficient, Theorem 4.6 holds.
A.3 Proof of Theorem 4.7 about the Optimality of STreeD
Theorem 4.7 states that any separable optimization task can be solved to optimality using Eq. (8) from the main text. Here, we provide proof for this theorem.
Proof. Let ((s, d) denote the set of all possible solution values to a decision tree search problem with state s, and the maximum depth of the tree, and let ((s, d) be the set of nondominated and feasible solutions for a given separable optimization task (g. c,),
(s, d)
(17)
We need to prove that for every state s and depth d, Eq. (8) returns the optimal solution:
0(s d) = T(x,d)
(18)
We will prove this by induction over d.
Base step: If d = 0, because the cost function g is Markovian, the solution set O(x, 0) can be described as:
(ss,
U
k))
(19)
&Ex
Therefore the optimal solution set as defined by Eq. (17) is precisely what Eq. (8) returns for
0(s, 0) T(s, 0)
(20)
Therefore, since we made no further assumptions, the base step of this proof holds.
18

---

Induction step: For d > O, we assume that Eq. (8) returns the optimal solution for d - 1:
8(s, d - 1) = T(s, d
(21)
We now need to show that Eq. (8) when > 0 returns the optimal solution:
((s, d) opt(O(ss. d)) = opt (Urez merge (T(t(s. f). (). 1))
(22)
Define (s, d) denoting the set of all possible solution values with feature f as the branching feature of the root:
(,(s, d) merge (0(t(s, f), - 1), ((t(s, f),
(23)
When O, the set (s, d) can be described as the combination of all sets
( d) = U
(s(s,d)
(24)
fer
Any solution that would be filtered out in a subset would also be filtered out in the whole set, therefore:
opt(Ug. opt(Uar opt(O'))
(25)
We can now derive the following:
((s, d) = opt((((sd)) d))
opt (UserO,(s,
(26)
= opt (USEF opt ()((sd)))
Because of Eq. (26), in order to prove Eq. (22), we only need to show the following:
(5(5,d) d) = opt (merge (T(1(s; f), 1), T(((s, f) - 1), f)
(27)
Since the induction step assumes computes optimal trees for d 1, we may here substitute with Eq. (21):
(s = opt (merge (f(t(s, f) 1), ((ts, f) d
1), f)
(28)
Because the optimization task is separable, it is splittable, and therefore Eq. (27) holds.
Therefore the induction step also holds. Since this proof is shown without any further assumptions, by mathematical induction Theorem 4.7 is true.
A.4 Threshold constraints
Many constraints, such as capacity constraints, can be considered as an objective with threshold value
ca s) 1 x B)
(29)
Eq. (29) means that solution feasible its solution value better (>) than the threshold. E.g.. when minimizing, any solution with value lower than the bound is feasible.
Constraints need to be anti-monotonic to be separable. Threshold constraints anti anti-monotonic provided that the combining operator @ worsening and the comparison operator > transitive: Definition A.2. (Worsening operator) A combining operator is called worsening if and only if V = 01 + 02 + Ui ž v A 02 = v.
For example, when setting prices to maximize revenue under maximum supply constraint, you can calculate the expected demand each node, sum demand from several nodes by using addition, and then prune trees that exceed this maximum supply by using threshold constraint.
Proposition A.3. Given an optimization task (g, t, >, C Cg 8o); if the combining operator i satisfies the worsening property and if the comparison operator > is transitive, then the threshold constraint eg is anti-monotonic.
Proof. Given any e1 E 11, E O₂ with 3 > (or w.l.o.g. 3 > v2), such that ei & 0,. Let = #1 @ U2 with @ worsening, then B > V1 > e and therefore v & 0, and therefore eæ anti-monotonic.
19

---

A.5
Combining multiple optimization tasks
We now show that combination of separable optimization tasks is also separable. This is important for multi-objective optimization or for optimizing with a constraint. For example, we can maximize revenue in the first task, while respecting maximum supply constraint in the second task. Let
a. @a. Ca, Two (or more) of such tasks can now be combined with the following equations:
Og = (Ba= la, aa
Ca,86) 86) and os (gb, lb, 6,, Gb, cb; sn) be two separable optimization tasks.
(((sa; sb), k) (ga(sa: 90),, k))
(30)
g((sa) sb), f) = (ga(sa: f6.9((5. f))
(31)
t((sa, sb), f) = (ta(Sa: tobb, f))
(32)
(ef, at) (og, uy) iff (vf, uz) * (ug, 22) A of 2 A
(33)
(uf, of) @ (eg, ub) = (of ta ug of 2 v
(34)
c((ea, vb), (Say 86)) = 1 (cca(va. A (bb,
(35)
so = ($6. si)
(36)
Eqs. (30)-(31) define the cost function as returning a uple of the values that fa and Ib return. Eq. (32)
returns the result of both transition functions. Eq. (33) gives a partially defined comparison operator
which states that solution only dominates another solution if the solution values for both optimization tasks dominate both values of another solution. Eq. (34) defines the combination operator by applying the combination operator of the sub-tasks to the corresponding values of the left and right-hand side. Eq. (35) defines new constraint that is only feasible when the solution is feasible according to both sub-constraints. Finally, Eq. (36) sets the starting state as the combination of both starting states.
Proposition A.4. Let (ga: tas aa Day Ca. S0) and o₁, (gb. tb, b, Db. cb: si) be two separable optimization tasks. Then the combined optimization task (g. t, >,, O. c, su) defined by Eqs. (30)-(36) is also separable.
To prove Prop. A.4 it is necessary to show that the optimization task resulting from applying Eqs. (30)- (36) satisfies all the properties of being separable optimization task.
Proof. Given two separable optimization tasks On = (gas las >a. Da. Ca. *8) and Os (gb, to. by Gb. Cb sb)), and an optimization task o = (g, t, >, 3, 5o) which is the result of ap- plying Eqs. (30)-(36) to Oa and og-
Markovian: If Ja: 9b: ta and i, Markovian, then g and t are also Markovian since their value can be fully expressed by calling the functions of the subtasks, which are Markovian, without considering any other decision variables.
Order preservation: If th preserves order over >a and @d preserves order over > then e also preserves order over > because of the following.
Consider solutions (vf. uf) E opt (01, s1), (of', ,ef)) E O1, so that (vf, ut) > (of' .uf ) consider (ug, rg)) E opt (02, #2) and assume that @ is commutative. Then, because of Eq. (33), there are two options: either u >a of A of 2s ef', or ott Za uf' Aut > of W.L.ogg, choose the first. Since @ preserves order over >a a and @5 preserves order over >n. we can now say that of Ba 2g >a of @. og and also of @b og Zb of @b uz. Because of Eqs. (33)-(34), it follows:
(of,el) @ (ug, o
(of' of @ (16,00) x
(37)
Therefore @ also preserves order over >
If ( is not commutative, the proof above should be repeated with the operands for every use of ( switched around.
Anti-monotonicity: If c, and cs are both anti-monotonic, then for any given solution 1a = (eff vf) and U2, and (v", 2²)
@ 12 and any given state and branching decision f. such that $1 = t(s, f) and 82 = t(s, F): -c, (uf, s1) (or similarly for o, and U2 and $2), then also -c, (v", s), and therefore -c(v, s), thus is also anti-monotonic.
Conclusion Since the combined optimization task o satisfies all necessary properties, o is also separable.
20

---

(0,8)
(1.3)
(4.6)
(5,2)
(1.3)
(8.3)
(5.2)
(1.3)
(14.0)
(5.2)
Figure 3: The result of subtracting the left solutions {(1,3), 3). (5, 2)} from the upper bound
{(0,8), (4, (8,3), (14, Subtracting the solution (1,3) results in the blue Pareto
front ((0,5) (3, (7,0) Subtracting the solution (5,2) results in the red Pareto front
{(0, 4), (3, (), 0)). Combining these Pareto fronts results in the green Pareto front
(7,1),
B Pseudo-code and Implementation
This section gives further details on the implementation of STreeD. First, we explain how upper and lower bounding works. Second, we expand on how to search for sparse trees and how to tune the number of nodes. Third, we provide conditions for caching. Fourth, pseudo-code for STreeD given. Finally, special solver for trees of depth two is discussed.
Upper bounds no solution in ub exists that is equal or dominates it:
solutions ub an upper bound to another θ for all solution v in +
Vu E θ -3v' ub uub:v' : v
(38)
An upper bound can be used prune solutions that are dominated by it. The upper bound ub dominates a solution e there exists a solution o' E ub that is equal to or dominates e:
ub < 3v ub : o' >
(39)
This upper bound is used to prune poor solutions earlier in the search. To signify this introduce the following new notation:
opt O ub) = opt (f E
θ v S sb}
(40)
Subtracting In a branching node, when solutions θ are known for one subtree, these can be used update the upper bounds for the other subtree, provided that an appropriate subtraction operator O exists. For totally ordered optimization tasks, the upper bound for the other subtree can be simply computed by subtracting the solution from the current upper bound. However, for partially ordered objectives, the procedure is more complicated.
Consider the example shown in Fig. 3 where the goal is minimize both dimensions, and the subtraction e is defined as element-wise subtraction (but values below zero are set to zero). The idea find first for each solution O the upper bound ub, when subtracted from the upper bound ub (the blue and red plusses in Fig. 3).
ub, nondom {u θ ub))
(41)
21

---

The final new upper bound uby is the Pareto front that covers precisely the outer edge of all upper bounds ub,, such that if any solution is dominated by all ub, it is dominated by ub2.
To compute this new upper bound, we need to define some more functions. Let x decide if one solution is reverse Pareto dominated. Similarly, let nondom be the set of reverse nondominated solutions. Let the operator A combine
solutions V/ and 2/2 such that A 12 I 01 and also vi U/2 N 1/2 Similarly, let the operator v combine two solutions vi and 12 such that 11 V 02 t 01 and also 81 v 22 ž U/2. Egg. (0, A (3. 3) (3, 5).
For the example domains considered in this paper, all of these operators (θ, x, A, and v)) can be defined. If @ is (element-wis addition, then θ is (element-wise) subtraction, and - is defined like > but with the comparison reversed. In this case, A and v are defined as (element-wise) max and min respectively.
With help of the functions above, one can compute the reverse Pareto front of ub, (the blue and red crosses in Fig. 3).
reverse (+) - nondom((w), A U2 UI, 01 +))
(42)
And similarly, to reverse back:
reverse ()) = nondom
U1 02 E θ))
(43)
The upper bounds ub, can be combined using nondom:
U ub L
ub₃ nondom
(44)
However, the set ub; is not always the best upper bound. E.g., in Fig. 3 it would not include (7, 1), and therefore would not consider the solution (8, 2) dominated, even though it is.
The quality of the upper bound can be improved by also considering the reverse Pareto fronts. The reverse Pareto fronts of the solutions v E θ can be combined using nondom and then reversed back with reverse follows:
U reverse(ub.)) Le
ub² = reverse nondom
(45)
The final upper bound for the other subtree (the green circles in Fig. 3) is obtained by combining the two sets with nondom:
ub2 ub θ nondom(ub; ub²)
(46)
Lower bounds The set lb is a lower bound to θ if for all solutions in O there is no solution in lb which is dominated by
Vu E θ -Eo' Eb:
(47)
We compute lower bounds similarly as Demirović and Stuckey [19]. We use the notation LB(s, d) for retrieving lower bound from the cache by computing it by using similarity bound for state s = (D, F). Any optimal solution in the cache is also a lower bound. Furthermore, a tree search node is infcasible (no feasible solution below the upper bound ub exists), then the upper bound for this node becomes a lower bound that is stored in the cache.
The lower bound may also be computed by using similarity bound, but this only applies when the optimization task
1. has subtraction operator θ;
2. does not have constraints;
3. is context independent; and
4. and the optimization task is per-instance (element-wise) additive.
Definition B.I (Context independent). optimization task is context independent if and only if the cost function does not depend on any of the parent nodes' branching decisions.
22

---

For example, cost-sensitive classification with discounts, as introduced in this paper, is not context independent.
Definition B.2 (Per-instance (element- wise) additive). An optimization task is per-instance (element- wise) additive, if the cost function for label assignments can be written as the sum of the costs from a per-instance cost function h:
o( k)
E ka, (a.
(48)
If all these four conditions are met, the similarity bound can be used. Its definition is generalized from the definition given in [19]. Instead of subtracting the misclassification score per class from an existing solution, the worst-case value for instances of that class is subtracted by use of e. Let wg be the worst case contribution of single instance with class k to the objective, and let ng be the number of instances in a dataset 'D that are not part of dataset for cached solution D i.e. D2 = {(x, k)) E D k' k)), then ng D DE Now assume each of these ni instances is misclassified and therefore wi is added to the objective for each of these instances, then lower bound can be computed from a cached solution O as follows:
Ib(D) {ue e
Σ Engwx 8 E 0*)
(49)
In this equation, the sum operator uses ① to sum.
Once the lower bound for search node is computed, it can be compared to the upper bound ub to check if any possible improvement exists, and not, the node is pruned from the tree search, This happens whenever lb >> ub, i.e., every element of the upper bound is reverse dominated by at least one element of the lower bound:
lb ub + Vo E 3o E lb o 12
(50)
Computing these upper and lower bounds be quite costly since it involves a product operation of two sets. To reduce the computation time for applying the subtraction or to combine two lower bounds for two subtrees, we apply a new procedure in which we first reduce the two sets to a representative subset using A in such a way that the resulting bounds are still valid. These representative subsets are then combined get new valid upper or lower bound. This decreases the computation time of the bound but prunes slightly fewer nodes.
Sparse trees Optimal decision trees may overfit on the training data [22] and therefore typically a sparsity coefficient is introduced that adds a cost for every branching node, as for example done in [10, 36, 52]. In the work presented here, we do not consider such a sparsity coefficient, although could trivially be added. Instead, STreeD optimizes directly for given maximum number of nodes. This number of nodes can then be tuned (as explained below). In the DP formulation the main text, this is left out for brevity. For completeness, the DP formulation should be changed by considering the following equation a branching node (d >> 0), as is similarly proposed in [20]:
opt (USEFie(anni) merge (T(t(s, f), d (((ss, f) 1, 1), f)
(51)
With this addition, STreeD can be tuned to optimize the number of nodes to prevent overfitting. This is done by using part of the training data as validation data and train STreeD the rest of the training data for an increasing number of nodes. This is repeated five times and the number of nodes that yields average the best result is used as the final maximum number of nodes.
Caching STreeD supports two forms of caching: branch caching and dataset caching. Dataset caching is typically slightly faster than branch caching [20]. However, dataset caching cannot be used for context-dependent optimization tasks, because dataset similarity is no longer sufficient to identify similar subproblems. Similarly, for some optimization tasks, branch caching should be replaced by equivalent state caching, which we leave as future work. In this paper, dataset caching is used, except for cost-sensitive classification and group fairness, which are context dependent and use branch caching.
23

---

Algorithm 1: Tree search of depth d for an optimization task (g, 1,,,,,,, @ so) for state for a feature set F and a maximum number nodes 7t.
T(s, d. n, ub) if d = VV
then return opt (UEEK((S, k,, ub)
if n > 2d then
return (ss, d, 2d 1, ub)
if n then
return (s, d, d, ub)
(0,1b,stat) 6- (scceelsdd,,,
lb > ub then return 0 stat -optimal then return opt (0, ub)
++0
for f E F,nz E [0 do an + n n2 -1
lb, + LB(t(s, - [) 1 1,) lbR f
nR)
lb merge((br, (bb,, 8,
lb > ub then continue
uby = ub θ gs
or f- ((t(s,
1, n, ub2)
if 1 then continue
ubg ub e O2 + f)
θд < T(,(s,
1, ng ubR)
if R @ then continue
O new +
Rn 8, f),
ub opt J O neww, 8)
θ +- opt θ new: 8, ub)
θ- = / then cachols. n] +- (0, ub, lower bound)
return
cache(s, d, n]] < (0, O, optimal)
return +
Pseudo-code Pseudo-code for STreeD is given in Algorithm 1. If leaf node is reached, the cost function is used to compute optimal solutions. The next two checks in the pscudo-code check if the maximum number of nodes and the maximum depth are compatible. If they are, the cache is checked for optimal solutions or lower bound. The search is stopped if the cached lower bound is dominated by the current upper bound. If the eached solution is optimal, it is returned.
Then, for every possible branching feature and every possible node division, the algorithm does the following. It computes lower bounds for the left and right subtree, merges these lower bounds, and skips this feature if the upper bound dominates the lower bound. Then recursive call is performed compute optimal solutions the left subtree. The upper bound for the left tree is updated by subtracting the branching costs. Solutions from this recursive call are used to update the upper bound for the right subtree and the right subtree is also solved. Solutions from both subtrees are merged into a new set of solutions which are used to update the current set of solutions and the upper bound.
When all branching features have been checked and feasible solution is found (better than the upper bound), the current upper bound is stored as lower bound. If feasible solutions have been found, the current set of solutions is stored in the cache and the solutions returned.
In case the comparison operator > is fully defined (a total ordering of all solutions exists), such as the case with minimizing misclassification score, then the nondom operation always returns a set of precisely one solution (or zero if infeasible). In this case, nondom can be replaced by min (as defined by >), simplifying the implementation and computation.

---

Depth-two solver Demirović et al. [20] have shown that the runtime of optimal decision tree search can be improved considerably by use of special solver for trees of maximum depth two. The core idea is to pre-compute class frequencies by looping over only the preseni features for every instance in dataset. We generalize this concept in STreeD and explain below.
STreeD's 's use of the depth-two solver is restricted under the following conditions:
1. the cost of a leaf node can be expressed as function over the contributions of individual instances;
2. the cost of leaf node is context independent (see Def. B.1, note that the branching costs may be context dependent); and
3. the branching costs are equal for datasets with the same size, ie., (Dil [D2 g((D), f) = (P2, f) f) for all f E F x 10.
For all optimization tasks considered in this paper, these conditions are met.
To use the depth-two solver, the following functions and values need be defined:
1. a 'depth-two' solution space W;
2. 'empty' initial solution value wo E W (typically zero), the solution value of leaf with zero instances;
3. a per-instance cost function j X x K. - W such that j(r, k, k) returns the 'depth-two" costs of instance (z, k) when assigned label k;
4. 'depth-two' combining operator @' W x W + W that combines two solution values into one;
5. 'depth-two' subtract operator e' W W W, such that (wn 4' w2) e' w2 w for
all W1, W2 E W:
6. a transformation function g : W + that transforms 'depth-two' solution value into solution value in the original solution value space V:
7. branching cost function r S N+ cost of branching on f' in state with = [D].
{0, + V. such that r(s, n, returns the
In this paper, for all optimization tasks W = V, @/ = C and j(r, k) (x)((x))))))..)))))))))))>>))))) k), but this is not necessarily true for future optimization tasks.
The function j provides per-instance breakdown of the costs which are summed with the @ operator. These used to precompute the costs of all possible leaf nodes. Let n(fx) and n(fi, fz) be the size of Dj, and DR.ss respectively. Similarly, let wik be the cost of assigning all instances in D label and let w(kk, fi) and w(k,, fo. f2) be the cost of assigning all instances in D,; and D respectively, By generalizing the result from Demirović et al. [20], the following statements hold:
a(f)) = [D] n(fii)
(52)
m(fs, J5) = n(f.)) n(fs:
(53)
n(Fs. f5) = n(f,) n(f(,fs)
(54)
m(Fs. J5) = (D) -n(fi) n(f)) + ((f(sf))
(55)
w(k,Ft) = w(k) ø' w(k
(56)
w(k, fo. f,) w(kk fa) e w(k, frr
(57)
wolk, J., J5) = w(k, fs) @ wok, S1,
(58)
w((h J)) w(k) e wilk fi) e' w(k. f3) o wikk fz)
(59)
Furthermore, let f E x denote that feature ʃ is satisfied by x. The depth-two solver can now be generalized shown in Algorithm 2. It first precomputes the dataset sizes and costs, then finds the best left and right solutions for each possible split, and finally returns the best solution.
C Cost-Sensitive Classification
For our cost-sensitive classification experiment, we consider constant but asymmetric misclassifica- tion costs, test costs (feature costs) that are constant may depend previous selected tests. For
25

---

Algorithm 2: Tree search of depth two using a special depth-two solver.
(8, (D,F)
1/ Pre-compute dataset sizes
m(f() < EF
n(fc, +- 0 fj F Fstiis
for (a, E do
for f. E do
n(fi) +- n(fi) +1
for fj do
n(Ji,jj) t n(i, fj) +
1/ Pre-compute costs
wo(k) wo vk
w(k: fi) + wo V wokk fz) - wo fi
for (I, do
w(kh + w(k) e' j(xx
for E do
w(k, wik, fi) 0 j(r,k,k)
for fj F do
w(k, fi. f w(k, fú, fi) @ j(r,k,k)
// Find optimal subtrees for Ji, Ji F s.t. Ji ! do
for kL, kR E K.t.t. s.t. kL + kR do
cost + q(w(kr, Js. J,) t q( Jisfs)
cost, + cost, + r(((s, f.), (r)t
cost < q(w(k,, I,. 2 (ww(k,
cost t cost @ r(((s, ft), ((..
if cost > best-costz then
best-costz (fs) + cost
if cost best-cost (fr) then
(f)t + cost
return opt (USEr merge((est-coss) best-oos (()s
costs, we follow the naming conventions of [83]. Misclassification costs or test costs that depend on individual cases or on feature values are easy extensions and also fit in the STreeD framework, but not considered here.
The following sections present the related work, the experiment setup and results, and discussion of the results. The objective formulation is given in Eq. (9) in the main text.
C.1 Related Work
Lomax and Vadera [55] provide an overview of methods for cost-sensitive classification with decision trees, most of which use top-down induction with varying cost functions for deciding on the best split [54, 68, 69, 80]. Each of these splitting criteria is mostly the same, except for slight difference in the trade-off between accuracy and feature costs. This therefore is a good example the drawback of top-down induction by splitting criteria: the objective is not directly translatable to good splitting criterion. To address this issue Min and Zhu [61] generalize a number those methods using a hyperparameter that decides on the trade-off between information gain and feature costs. ICET [82] does the same but uses genetic algorithm to decide the hyperparameter. All these methods except ICET, however, do not consider misclassification costs, and even ICET only does so indirectly.
Lomax and Vadera [56] co-optimize accuracy and costs by approaching the problem multi-armed bandit scenario. This means that in every branching node, they repeatedly try random splits (possibly
26

---

Table Datasets used in cost-sensitive classification. Fasee is the number of categorical features in the dataset as preprocessed by [57]. [ is the number of resulting binary features.
Dataset
[
Faisc
Fbin
[A]]
Annealing
898
24
82
5
Breast
277
38
Car
1728
21
Diabetes
768
Flare
323
10
25
Glass
214
Heart
297
11
20
Hepatitis
154
20
Iris
150
4
12
Krk
28056
40
18
Mushroom
8124
21
111
Nursery
8703
26
Soybean
562
35
80
15
Tictactoe
958
9
27
Wine
178
13
32
multiple consecutive random splits) and choose the split which on average has the best expected costs based on this random exploration.
Maliah and Shani [58] formulate the problem Partially Observable Markov Decision Process (POMDP). However, they observe that the action and state space of their model is too big, and therefore they present smaller MDP that approximates the POMDP. For the MDP model, they generate trees for all possible subsets of features using a standard heuristic that ignores costs. The MDP's state space is the set of all leaf nodes of all those generated trees. The resulting MDP is acyclic, and therefore its value function can be computed in one bottom-up up pass through the belief' states.
As far as we know, Nijssen and Fromont [66] and Zubek and Dietterich [94] are the only ones to provide optimal formulation. The latter do by formulating experiments, they decide to use relaxed formulation instead because memory limitations.
MDP. However, in their
C.2 Experiment Setup
Table lists the datasets used in this experiment [24, 41, 95]. These datasets were preprocessed and discretized according to the instructions in [57]. For methods that require binary features, the discretized features were binarized using one-hot encoding. Every dataset is split randomly 100 times in train and test set, with 80% and 20% of the instances respectively.
We use the fixed feature costs as defined in [57]. The cost of misclassification strongly impacts the behavior of cost-sensitive algorithms. When misclassification costs low, feature costs comparatively high and branching is discouraged. Conversely, when misclassification costs are high, feature costs are comparatively low and therefore less important. In this case, overfitting also becomes more likely. Therefore, similar to the experiment setup in [57, 58] we vary the misclassification costs and generate misclassification matrices with low, middle, and high misclassification costs. These matrices are defined based on the feature costs and the class frequency as follows: First, calculate the maximum possible feature costs C' by summing the costs for all features. The default cost Caef for low, middle, and high-cost experiments are defined as 1/6 C. 1/3 C, and C respectively. By considering the relative frequency Ji. of class k; the misclassification costs C2. for class k are defined as follows:
Caes
C₂
(60)
Kr
For each run, a timeout of 300 seconds is used.
27

---

Normalized costs We report normalized costs, defined in [82]. The normalized costs are calculated by dividing the obtained costs by the standard costs. As before, let C' be the sum of all feature costs, let f& be the relative frequency of class k, and let Cx,& & be the misclassification cost when an instance with true label l is assigned label k. Then the standard costs is defined as follows:
C++min (1 fi) mmx R,K
(61)
These standard costs lower than the maximum possible costs, but function as good upper bound on the average costs [82].
In one aspect deviate from the original definition. In the original definition, fu was calculated based on the whole dataset, but here is based on the dataset that is examined (the train or test set),
C.2.1 Methods
Apart from STreeD, the following methods are evaluated in our experiments:
C4.5 [73] is an extension of the ID3 algorithm [72] and uses top-down induction (TDI) based on information gain measure. After construction, pruning mechanism used remove branching nodes that are likely to result in overfitting. C4.5 is cost-insensitive and therefore functions as a baseline heuristic.
CSID3 [80] is variant of ID3 with updated splitting criterion. Instead of only information gain, it makes a trade-off between the information gain (f) and the cost C(f) of feature f by the splitting criterion:
T()²
C(f)
CSID3 does not consider varying misclassification costs.
EG2 [69] is also variant of ID3 with updated splitting criterion:
2 -1
(C()) + 1)
The parameter w, with values 0 S w S 1, determines the weight of the cost factor. Following Turney [82], we set EG2 also does not consider varying misclassification costs. IDX [68] is yet another variant of ID3 with the splitting criterion:
I(f)
C()
The look-ahead procedure of IDX is not implemented. IDX also does not consider varying
misclassification costs.
MetaCost [23] can be used to turn any error-based classifier into a cost-sensitive classifier. It iteratively fits model, computes class probabilities per sample, and updates the training input labels such that the expected costs are minimized based on the class probabilities. Note that MetaCost only considers misclassífication costs and ignores feature costs. We run MetaCost with 10 iterations.
TMDP [58) formulates the problem as Markov Decision Process (MDP). For every possible subset features, it uses C4.5 to generate a normal cost-inssnsitive tree, and every leaf from the resulting tree is added as state to the MDP. Each state is described by the path to the leaf. The state with the empty path is the starting state. In every state, the possible actions are measure feature to classify sample. If feature is measured, the next state is the one described by the path that results from appending the measured feature to the current path. When classifying, the MDP moves the terminal state. This MDP therefore is acyclic, and the values of the states can be computed in reverse topological order by using the training data. Based on these values, the tree can now be constructed by choosing the action with maximum value, beginning in the start node, and splitting into multiple nodes when selecting a feature to measure. This is repeated until all nodes are leaf nodes.
Because TMDP creates trees for every possible subset of the feature set, the total number of possible states explodes for increasing number of features. Therefore, the authors
28

---

Table 2: Out-of-sample normalized costs (%). Significantly (p 5%) best results marked in bold. Timeouts are marked as '
Dataset
C4.5
CSID3
EG2
IDX
MetaCost
TMDP
STreeD
Annealing
5.6
5.6
2.2
2.2
5.7
1.6
1.2
Breast
43.9
43.4
41.0
40.7
54.8
21.0
20.4
Car
43.1
42.2
39.8
39.9
42.2
16.1
14.8
Diabetes
50.2
44.5
43.4
43.4
55.9
14.2
14.1
Flare
17.9
15.7
15.4
15.3
21.8
18.0
16.7
Glass
37.7
35.6
30.1
29.0
39.4
14.3
14.4
Heart
45.4
23.0
20.0
19.9
44.7
9.5
9.3
Hepatitis
32.2
24.3
20.0
19.7
32.2
16.2
15.6
Iris
38.8
34.0
29.5
29.7
40.9
12.8
12.8
Krk
6.2
6.3
6.3
6.5
1.7
Mushroom
16.4
8.3
5.6
4.5
16.4
1.9
Nursery
0.4
0.4
0.4
0.4
0.4
0.1
0.1
Soybean
12.8
16.3
19.8
21.1
12.6
15.4
11.4
Tictactoe
45.0
45.0
45.0
45.0
45.0
16.1
16.1
Wine
25.0
18.8
18.1
17.5
24.8
12.2
10.4
propose that for larger number of features, TMDP only tests all possible subsets of the 10 most costly features together with all the cheap features considered by default. In the analysis of TMDP here, the same approach used.
Note that TMDP is the only method that is evaluated here that considers multi-way splits instead of binary splits.
For these methods, we use an implementation that available online. C4.5 implemented in Weka, with CSID3, EG2, and IDX implemented C4.5 but with the new splitting criterion. Leaf nodes do not select the majority class, but the class with the lowest total misclassification costs.
C.3 Results
Normalized costs Table 2 shows the normalized cost results for all methods on a variety of datasets. On 14 out of datasets STreeD has the best performance or not statistically significantly worse than the method with the best performance. The results show that TMDP and STreeD have similar performance and significantly outperform the other heuristics on all datasets except Flare. Therefore, the rest of the analysis will focus on TMDP and STreeD.
Table 3 shows the results for TMDP and STreeD for low, middle, and high misclassification costs. The difference in the results can be explained by several factors: multi-way splits versus binary splits, and the quality of the binarization. TMDP considers multi-way splits and therefore has larger solution space, but does not necessarily find the best tree in this solution space according to the training data. STreeD, on the other hand, only considers binary decision trees and solution quality depends on the binarization. However, it always finds the best binary decision tree for the training data.
Runtime Figure 4 shows the difference in runtime for STreeD (hypertuned with d = 4) and TMDP. As can be seen, STreeD is often order of magnitude faster than TMDP, and is significantly faster than TMDP for all datasets (p < 5%), except for Iris, the smallest dataset.
Interpretability Table shows how the methods compare in terms interpretability metrics. When only looking at the numbers, TMDP has the best score, and STreeD follows shortly after. The heuristics, as expected, score much worse. However, TMDP allows for multi-way split trees and the others do not. According Piltaver al. [71], higher branching factor increases the classifying time of an average user, although this effect can only be seen with branching factors higher than 3.
29

---

Table 3: Test normalized cost (%) for varying misclassification costs. Significantly (p 5%) best results are marked in bold. Timeouts are marked as '-'.
Low costs
Middle costs
High costs
Dataset
STreeD
TMDP
STreeD
TMDP
STreeD
TMDP
Annealing
1.3
1.6
1.2
1.6
1.2
1.5
Breast
8.3
8.3
15.7
15.6
37.3
39.1
Car
9.8
9.8
14.0
15.8
20.5
22.9
Diabetes
7.3
7.2
11.6
11.8
23.4
23.5
Flare
9.9
9.8
15.2
16.3
24.9
28.0
Glass
10.9
10.8
13.8
14.1
18.5
18.1
Heart
4.0
4.0
7.2
7.5
16.7
17.1
Hepatitis
8.4
9.2
12.9
13.5
25.6
26.0
Iris
7.5
7.5
10.7
10.7
20.2
20.3
Krk
1.8
1.8
1.7
Mushroom
1.7
1.8
2.1
Nursery
0.1
0.1
0.1
0.1
0.1
0.1
Soybean
10.9
18.7
11.6
16.3
11.8
11.3
Tictactoe
6.8
6.8
12.7
12.7
28.8
28.9
Wine
8.0
11.3
11.9
12.5
11.2
12.8
100%
Trees computed
75%
STreeD
50%
TMDP
25%
MetaCost
TDI Heuristics
0%
10
10a
10a
Runtime (s)
Figure 4: Runtime (s) comparison. The top-down induction heuristics (C4.5, CSID3, EG2, and IDX) have been grouped together as "TDI Heuristics' because they almost do not differ in runtime. A timeout of 300 seconds is used. Note the logarithmic x-axis.
Table 4: Interpretability metrics. Significantly (p 5%) best results are marked in bold. Datasets for which TMDP exceeded the timeout limit are ignored.
C4.5
CSID3
EG2
IDX
MetaCost
TMDP
STreeD
Tree depth
7.9
7.1
7.1
7.1
7.2
1.9
2.2
Leaf nodes
26.1
27.2
28.6
28.7
24.8
7.4
5.4
Question length
4.4
4.7
5.0
5.0
4.7
1.7
2.8
Therefore, we can conclude that both TMDP and STreeD clearly outperform the heuristics in terms of interpretability.
C.4 Discussion
The results above clearly show the advantage of TMDP and STreeD over the heuristics. For most datasets, the cost performance of TMDP and STreeD was much better than the heuristics. This is best explained by the fact that the splitting criteria of the heuristics do not directly capture the objective, and in these cases even ignore the misclassification costs.
Comparing TMDP and STreeD more difficult. In terms costs, both times perform best, although on average STreeD's out-of-sample costs are (significantly) lower: 13.3% normalized costs versus TMDP's 14.3%. Both methods show some overfitting and this could be further addressed. Direct comparison is difficult though, because they differ in many ways: TMDP has categorical data
30

---

with multi-way splits and seeks tree without depth limit. STreeD has binary data with binary splits and seeks the best tree up to some maximum size.
The runtime of STreeD is at least an order of magnitude lower than TMDP. One of the consequences not able find good trees for several datasets within the given time limit.
here is that TMDP Moreover, these results are produced with TMDP's limit of considering only subsets for the 10 most costly features. Without this limit, TMDP's runtime would have been worse. STreeD therefore is more scalable than TMDP.
Both STreeD and TMDP have good interpretability and clearly outperform the heuristies. The trees returned by the heuristics are often too large to be considered interpretable.
From these results it can be concluded that STreeD can successfully be applied to cost-sensitive classification, outerforming the state-of-the-art in cost performance and runtime, while providing small interpretable trees.
D Prescriptive Policy Generation
Decision trees can also be used to prescribe policies. Given a set of instances, actions, and outcomes, the decision tree prescribes which action for an unseen instance will give the best predicted outcome. An example use case is prescribing medical treatment on basis of historical treatment response.
However, since historical data does not necessarily have the outcome for every possible action, the prescriptive model needs to reason about the counterfactuals. Therefore, conceptually, this problem can be split into prediction and prescription problem. The prediction problem predicts the counterfactuals. The prescription problem decides what action to take.
The following sections present first the related work and then formal problem definition and other preliminaries. We then describe the experiments and conclude with discussion.
D.1 Related Work
Athey and Imbens [7] use trees to estimate the causal effect of treatments. They use part of the dataset estimate heterogeneous partitions and the rest is used to estimate treatment effects in the leaves, including confidence intervals for these values. However, this method does not directly assign policies, and in the case of non-binary treatments, several trees need to be combined produce policy tree, reducing its interpretability.
Kallus [45] combines the prediction and prescription into one learning problem and proposes both top-down induction heuristic and an optimal MIP method that directly optimizes prescription error. Their methods work under the assumption that the training data is either produced in randomized experiment or that the generated tree partitions the data such that the historical treatment assignment becomes independent of the individual. However, in practice, the optimal MIP method does not scale to sufficient depth to reach such partition. Their results therefore also show that the optimal MIP method in most situations performs worse than other solution methods.
Bertsimas et al. [12] improve on [45] by observing that the performance of prescriptive trees relies not only on good heterogeneous partition but also the quality of the prediction of outcomes. Therefore they propose an optimal MIP formulation that co-optimizes both the prescription and prediction error in one objective. To circumvent the scalability issues for finding the global optimum, they repeatedly use a coordinate descent method [11] to find local optima and select the best tree.
Biggs et al. [13] and Zhou et al. [92] note the visadvantage of trying incorporate the predictive aspect into the MIP model. Instead they use a separate predictive teacher model and use this model to guide a top-down greedy heuristic. Zhou et al. [92] also provide optimal recursive search method, but they did not incorporate any of the scalability improvements from similar approaches [3, 20] such as caching and lower-bounding bounding.
Amram et al. [5] take a similar approach, but instead of greedy heuristic, they propose to adapt the MIP model of [12) by updating the objective to incorporate the counterfactual data obtained from predictive model, using objectives from causal inference. Their experiments show its advantage over both the greedy heuristics and the method by Bertsimas et al. [12].
31

---

Jo et al. [43] analytically show the limitations of both [45] and [12]: their assumption is generally not satisfied in conditionally randomized experiments. Both methods can return trees that actively violate their own assumption. Therefore Jo et al. [43], like Amram et al. [5], propose to drop this assumption and use separate predictive and prescriptive models. Apart from this, they show that under mild conditions their method provides an optimal out-of-sample policy when the number of training samples approaches infinity. Their model also allows for the addition budget constraints. They propose to use the same objectives as Amram et al. [3], but their MIP formulation is based on the more scalable formulation of Aghaei et al. [2], so unlike Bertsimas et al. [12] and Amram et al. [5] they do not need to fall back coordinate descent for local optima. However, despite their scalability improvements, almost half of the instances in their experiments are still not solvable within one hour.
Finally, Subramanian et [79] find near-optimal solutions by using column generation to improve scalability. Furthermore, their model allows for the addition of variety of constraints.
D.2 Preliminaries
We consider dataset D containing instances (z, k. with E X' the feature vector, A XC the label or historically assigned treatment, and y E R the observed outcome value. We assume no information on the historical treatment assignment policy. Let Y (x, k) be the value outcome when assigning treatment to an individual described by æ. The goal now is to find a policy π that maximizes the expected outcome Q(T)= E|y (æ, (x))]]
KC
Because not every treatment was applied each person, we do not have full information on the values of (x,, k), and therefore we need a teacher model that provides information on the counterfactuals, based on the data that we do have. Similar to [5, 43), we will here consider three teacher models: the direct method (DM), inverse propensity weighting (IPW), and the doubly robust approach (DR).
Direct method The direct method (also called Regress and Compare) trains teacher model 0j for the expected outcome y for each possible treatment by splitting the training data based on the historical treatment. The objective value Q can therefore be formulated as follows:
1
(D, m)
Σ (ar,E.N)
(x(
(62)
D
Inverse propensity weighting The propensity scores P(k | give the probability of treatment & for a given feature vector z. IPW implicitly models the counterfactuals by reweighing the actual data based on the inverse of their propensity scores. This requires the training of propensity score model fa(,, k)). Any ML model can be used to learn P.. Given a model for ft, the objective value Q of the policy becomes:
=
1(<(x) = k)
QIPw QIpw(D, R)
Σ
(63)
D
((x k)
(a.Ry))
Doubly robust
Finally, the doubly robust method [25] combines IPW and DM as follows:
1
Σ (a.A.))E
(Crc)(())+ (y -x((x) 1TT(x) = k)
(64)
D
M(x, k)
D.3 Objective Task Formulation
Once the objective value function Q is known as stated above, this can be directly applied in our framework since each of the objectives Qipw, QUM and QDR separable, once the teacher model values resulting from f and e have been precomputed. For each of these functions, the combining (maximization) and the cost function is determined by the
operator is addition, the comparator value of the policy गy that assigns treatment & to all individuals:
9 k) Q(D,
(65)
32

---

Table 5: Mean effect and treatment effect functions for the synthetic dataset, based on [7].
((x)
M(x))
1
f f=2
11
22
21
2
2
2
6
2
1
f ==10
Σ
2j
+
max (0,
2
j=1
j=3
==1
1 Σ
f f= 20
2j +
Σ
2j
max (0,
2
j=1
j=5
1=1
D.4 Experiments
The following experiments compare the performance of STreeD with the state-of-the-ar optimal methods for prescriptive policy generation. In this analysis, our main consideration is runtime performance, since the other methods optimize precisely the same objective. We examine the methods on synthetic data and on a real-life dataset from the literature.
Jo-PPG-MIP [43] is a MIP model based on a max-flow formulation for optimal decision trees from [2] but with the aforementioned Q-function as the objective. We call this method Jo- PPG-MIP, after their first author. Their experiments show their advantage over previous MIP methods [12] and [45]. Our implementation of Po-PPG-MIP is based on the open-source code for [2]. for which we updated the objective.? 3
CAIPWL-opt [92] also observe the scalability issues with MIP-based methods and therefore propose recursive search algorithm that maximizes the doubly robust metric. Their method does not use caching, and therefore this method does not qualify as a dynamic programming approach. They suggest their optimal method is best for trees of at most depth three. For deeper trees, they suggest using approximate methods. our experiments we use their publicly available R- package.
D.4.1 Synthetic Data
For the experiment with synthetic data, we follow the setup as done in [7, 43). We consider two possible treatments K = {0, 1}, input vectors X, which consist of ff independent variables with distribution N (0, 1) and for each X; corresponding potential outcomes (k)::
(k)) o(x,) ] -(22 - -)(,))(X)))))))))))))( +
(66)
In this equation, (xx) the mean effect, <(x)) is the treatment effect, and & ~ 0.0,0.1) is independent noise. Based on [7] we consider three variations of á and K, for f = 10, 20, as shown in Table 5. As can be seen from this table, for f = 2, the mean effect á depends on both variables, and the treatment effect only on one. For f 10 and 20, the mean effect depends on subset of the variables. The treatment effect also depends on subset of the variables, but only when those values are positive. Moreover, for these two cases, some variables are not related to the potential outcomes at all and function as noise in the dataset. For the training dataset, per instance, we then select the optimal treatment (the treatment with the maximum value Y;) as the historical treatment with probability p E {0.1, 0.25, 0.5, 0.75, 0.9) and store the corresponding outcome in the dataset. We repeat this process five times and generate training sets and test sets with sizes 500 and 10000 respectively.
We binarize each of the original features into 10 bins with similar frequency count. The teacher models are then trained on the original data. For IPW we train a decision tree model (dt, computed with CART), logistic regression (log), and the true propensity scores. For DM we train a linear regression (Ir) and lasso regression with a 0.08. For DR we use all six combinations of the IPW and DM methods.
"https://ee www.tthhomomgg.laaaeeeeee
33

---

100%
Trees computed
75%
50%
STreeD
Jo-PPG-MIP
25%
CAIPWL-opt
0%
10
10a 0%
20%
Runtime (s)
MIP gap at time-out
Figure 5: Proportion instances that can be solved per method for the synthetic datasets within a given runtime (s). Note the logarithmic x-axis for runtime.
Table 6: Results for the Warfarin dataset. The reported runtime the average of runs that did result in timeout (300s).
Jo
CAIPWL-opt
STreeD
OOS Correct
d
Timeout
Time (s)
Timcout
Time (s)
Time (s)
Treatment
30
< 1
1
83.1% 1%
2
62%
215
5
< l
84.6%
3
100%
96
86.6%
4
100%
100%
< 1
88.0%
5
100%
100%
89.7%
The setup above results in 75 scenarios that are solved with 11 different teacher methods. We all three methods with maximum tree depth of 1, 2, and 3, resulting in 2475 problems for each method to solve.
Runtime
Figure shows the runtime performance by listing how many instances of the synthetic dataset can be solved within the specified amount runtime. Note that this is only the time required to build the tree. It does not include the time train the teacher model. These results show that STreeD is several orders of magnitude faster than Jo-PPG-Ma PPG-MIP and also scales much better than CAIPWL-opt while providing exactly the same solutions.
D.4.2 Warfarin Dosing
Similar to previous studies, we test our method on the Warfarin dosing use-case [12, 43, 45J. Warfarin an anticoagulant, but the appropriate dose may vary up a factor 10 among patients. Based on experimental tests, dataset is compiled which prescribes for 5700 patients suggested dose [39]. For our experiment, unless otherwise specified, we follow the setup by [43].
We calculate the square root of the suggested weekly dose by the formula presented in the supple- mentary material section Sle of [39] and add noise of N (0, 0.02). This number then squared and divided by seven to give the suggested daily dose. The features used in their formula are also the features used for the dataset, preprocessed as specified by them. The only three non-binary features (age, weight, and height) are binarized by splitting them into five buckets with approximately the same number of instances. Instances with missing values for weight, height, age, and the therapeutic dose of Warfarin are removed. This leaves 4490 instances. The daily suggested dose is discretized into three groups, with hopt
if the dose is less than 3 mg/day, oott if the dose between and 7 mg/day, and cppt 2 if the dose is larger than 7 mg/day. The observed outcome is Y((k) 1. if k; koPe; and Y, (k,) = 0 otherwise.
For simulating historical data, three different setups are tested. the first, every individual receives uniformly random treatment k; in the historical data with the corresponding outcome Y,, to simulate a marginally randomized setting. the second and third setups, historical treatments are obtained by using the formula for the weekly dose from [39] mentioned above with each coefficient in this formula perturbed by a random amount from (-0.06, 0.06) and (00.111, 0.11) respectively, to change the probability of the historical data having the correct assignment. Each setup is used five
34

---

Table 7: Runtime (s) for minimizing biobjective misclassification score for classes, with timeouts beyond 600s denoted with Best results are shown in bold. Average of five runs.
Dataset
[D]
[D*]
D
[F]
MurTree
STreeD
MurTree
STreeD
Anneal
812
625
187
93
<1
24
2
Audiology
216
57
159
148
<1
<1
54
Eestralian-Credee
653
357
296
125
2
<1
139
19
Breast- Wisconsin
683
444
239
120
<1
<1
7
COMPAS
6907
3196
3711
12
2
<1
1
Diabetes
768
500
268
112
<1
117
13
Fico
10459
5000
5459
17
<1
26
3
German-Credit
1000
700
300
112
6
<1
164
34
Heart-Cleveland
296
160
136
95
<1
43
6
Hepatitis
137
111
26
68
<
<1
6
<1
Hypothyroid
3247
2970
277
88
<1
28
3
Ionosphere
351
225
126
445
26
11
Kr-vs-kp
3196
1669
1527
73
<1
22
Letter
20000
813
19187
224
46
7
469
Lymph
148
81
68
<1
1
Mushroom
8124
4208
3916
119
<
<1
<1
<1
Pendigits
7494
780
6714
216
13
240
Primary-Tumor
336
82
254
31
<
<1
<1
<1
Segment
2310
330
1980
235
<1
<1
<1
Soybean
630
92
538
50
<1
<1
<1
Splice-1
3190
1655
1535
287
17
9
Tic-Tac-Tor
958
626
332
27
<1
<1
1
<1
Vehicle
846
218
628
252
2
130
Vote
435
267
168
48
<1
<1
1
Yeast
1484
463
1021
89
5
<1
68
8
times to generate historical treatments. Each of these 15 datasets then randomly split five times into training and test set with 75% and 25% of the instances respectively. For each of these, a decision tree is trained for IPW scores and a random forest regressor for DM estimates.
Results Table 6 shows the results for applying Jo-PPG-MIP and STreeD to the Warfarin case. The results are very similar for the different teacher methods and the probability having correct assignment in the historical data. Therefore we just show the average results for trees of depth 1-5.
These results show that STreeD several orders of magnitude faster than both Jo-PPG-MIP and CAIPWL-opt. Because of this, STreeD can find optimal trees for larger depth, which for this problem results in better out-of-sample (OOS) correct treatment rate.
E Nonlinear Classification Metrics
For imbalanced datasets, it beneficial to metrics other than accuracy, such as Fl-score and Matthews correlation coefficient. However, these metrics are nonlinear and can therefore not (casily) be optimized with state-of-the-an methods for optimal decision trees. To address this, Demirović and Stuckey [19] developed a DP-based approach for binary classification that can optimize any function that is monotonie with respect to the misclassification score for both classes. This class of functions includes Fl-score and Matthews-correlatin coefficient.
STreeD can also optimize this whole class of functions by using the fact that multiple separable optimization tasks can combined to form new separable optimization task, according to Prop. A.4.
'This is different from the results in [43]. We have corresponded with the authors about this but were not able reproduce their results, We will include the test setup in repository enable reproducibility of the results.
35

---

The next section provides more related work. Then we show experimental results for applying STreeD nonlinear objectives.
E.1
Related Work
Lin et al. [52] also propose DP method for solving variety of objectives, such as balanced accuracy and F1-score. However, they observe that F1-score harder to optimize than other metries that are monotonic in relation to the number of false positíves and negatives because the best assignment in one leaf node dependent on the assignment another node. Therefore, they simplify the problem by introducing parameter w that helps determine which label should be assigned in leaf nodes, but as a result, the solution is no longer guaranteed to be optimal.
Xin et al. [91] present DP method for finding the full Rashomon set of sparse decision trees, which the set of almost-optimal decision trees (including the optimal). They then show how Rashomon set for trees optimized for accuracy can be used to find the Rashomon set for Fl-score. For this, they provide a bound on the accuracy score such that an Aceuracy Rashomon set covers the F1-score Rashomon set.
E.2 Experiments
In our experiments, we evaluate STreeD's performance on finding trees that maximize Fl-score. Fl-score is the harmonic mean of precision and recall and can be calculated as follows based on the number of true positives (tp), false positives (fp), and false negatives (fn): tp/ (tp + 0.5(fp + fn)).
Setup We compare STreeD with the MurTree algorithm from [19] on a set of binarized datasets with binary class described in Table 7. The datasets are originally from the UCI repository [24] and from [6, 30, 41, 59, 81, 96, 97]. We use the binarized datasets from the MurTree repository." 6 For each dataset, both algorithms need to find tree of depth three and four that optimizes Fi-score. We repeat the tests five times and report the average runtime.
Results Table 7 shows how STreeD compares to MurTree on optimizing nonlinear metrics. By using the geometric mean of the relative performance [31], we can see that for trees of depth three, STreeD is on average 7.1 times faster than MurTree; for trees of depth four, it is on average 6.8 times faster. This performance difference can be partly explained by the new upper and lower bound technique, as explained in Appendix B.
This same method could also be used to optimize other nonlinear metrics that are monotonic with respect to the false positive and negative scores, such as Matthews correlation coefficient.
F
Group Fairness
In many cases, removing sensitive features is not sufficient to prevent discrimination [28, 70], and therefore fairness constraints are imposed on ML models. We here consider two versions of group fairness: demographic parity and equality of opportunity [16, 60]. We leave individual faimess notions as future work.
Group fairness metrics impose equality on groups defined by some sensitive feature. Demographic parity requires equal probability of a positive result for each group, and equality of opportunity requires equal true positive rate for each group. Both of these can be optimized using STreeD by adding the threshold constraints defined in Eq. (11) for demographic parity and Eq. (71) for equality of opportunity, as introduced below.
The next section provides more related work incorporating fairness constraints in decision tree search. We then derive how threshold constraints can be used to model fairness constraints STreeD. The final section shows experimental results for imposing fairesss constraints in STreeD.
36

---

F1 Related Work
Fairnsss in decision trees was first considered by Kamiran and Calders [46] who proposed to preprocess the data to guide the decision tree training process to less discriminating trees. Later, Kamiran et al. [47] proposed new splitting criteria to enable top-down induction using a mix of information gain in the outcome label and the sensitive feature. However, they concluded that this was not sufficient and instead proposed after-the-face relabeling to get good results.
Fairness constraints were first considered in MIP models for optimal decision trees by Verwer and Zhang [85]. Aghaei al. [1] later developed MIP model for optimal trees for either a group fairness or individual fairness constraint. Jo et al. [44] propose a new MIP model based on max-flow formulation that scales better than previous models.
These MIP models, however, still do not scale well beyond small datasets and small tree depths. Therefore Wang al. [90] propose break down the problem and use MIP as look-ahead procedure that decides on the best feature to split on, but does not solve the whole problem as monolith. Their experiments show better scalability, but their method is no longer guaranteed to return optimal solutions.
Van der Linden et al. [53], the other hand, propose optimal DP method that optimizes global fairness constraint by considering upper and lower bounds on the final discrimination value for sub- trees enable early comparison and pruning. Their results show order-of --ggnniude improvements on runtime, and their method can handle much larger datasets than both the MIP methods and the iterative approach.
F.2 Optimization Task Formulation
In this section we derive threshold constraints for demographic parity and equality of opportumity.
Demographic parity As stated in the main text, demographic parity means that the probability of the positive outcome is the same for people of different groups:
P = 1 1) P(ù = 1 =
(67)
Typically, this is simplified to limiting the difference between the probabilities to some small per- centage 8. Let (y, a) be the number of group receiving the positive outcome, and Ñ Ñ(j a) the number group a receiving the negative outcome, etc. Then Eq. (67) becomes:
(g. (yy,a) a) N(a) N(a)
(68)
By observing that N aa)N(a) = Nyy
- a/N(a), and (g a))N(a) a Eq. (68) can be rewritten to the two constraints shown in the main text:
(v. N(a) N(a)
(g.
(y. (g.a) N(a)
+
51+6
11+8
(69)
N(a)
Equality of opportunity Similarly, can optimize for other group concepts of fairness, such as equality of opportunity, which is satisfied when:
P(ğ = 1 y a,a 1) = P(ù = - 0)
(70)
This can computed by two separable threshold constraints:
ID.all N(y.a)
k k=
Ry.ul h 0
ga (D,
(D,
N(y.a)
(71)
k=0
D Dy.a
h
((y.a)
N(y.a)
In this equation D and D are the number of instances with positive outcome in the dataset for group a and a, and (y, a) and N Nyy,a) represent the number of group a and à that have the positive outcome in the data.
37

---

Table 8: Runtime (s) results for optimizing with demographic parity constraint. Timeouts (>600s) are marked with" '-'.
Aghaei
[1]
Jo
[44]
DPF
[53]
STreeD
Dataset
[D]
[F]
d=2
d=3
d=2
d=3
d=2
d=3
d=2
d=3
Adult
45222
17
<1
<1
<1
2
Bank
45211
46
<1
Crime
1994
97
<1
5
<1
29
COMPAS r.
6172
9
<1
<1
<1
<1
COMPAS v.r.
4020
9
<1
<1
<1
<
1
Dutch
60420
58
<1
6
<1
German
1000
69
<
2
<1
62
KDD
284556
117
39
26
OULAD
21562
45
<1
3
<1
19
Ricci
118
4
3
44
2
13
<1
<1
<1
<1
Stud. Math
395
55
473
<1
Stud. Port.
649
55
<1
<1
<1
Table 9: Runtime (s) results for optimizing with an equality of opportunity constraint. Timeouts (>600s) are marked with '-'.
STreeD
Dataset
[D]
[F
d
=
2
d
Adult
45222
Bank
45211
46
<1
7
1994
97
<1
11
COMPAS
6172
<1
<1
COMPAS v.r.
4020
<1
Dutch
60420
58
<1
German
1000
<1
50
KDD
284556
117
3
37
OULAD
21562
45
<1
19
Ricci
118
4
<1
<1
Stud. Math
395
55
<1
<1
Stud. Port.
649
55
<1
F.3 Experiments
In our experiments we compare STreeD with the two MIP methods Aghaei-Fair-he [1] and Jo-Fair- MIP [44]; and the DP method DPF [53]. The comparison focuses on scalability.
Setup We follow the setup from [53], by testing each method on 12 datasets, preprocessed and binarized as described in [50]. Categorical variables are binarized using one-hot encoding. Categorical variables with twenty or more categories are removed. For each of these datasets, the task is find an optimal decision tree of depth 2-3 with at most 1% discrimination. A timeout of 600 seconds is used. Tests are repeated five times we report averages. For all methods, we show results for enforcing demographic parity constraint. For STreeD, we also show runtime results for optimizing with an equality gruualty--ofoppoone opportunutt constraint.
References to the original datasets can be found here [6, 17, 24, 27, 49, 62, 77].
Results Table 8 shows the runtime results. Both MIP methods almost always hit the time limit, except for the smallest datasets. In contrast, both DP methods find optimal decision trees depth two in less than one second except for the KDD-Census income dataset. For depth three DPF outperforms STreeD. This is partly because how the fairness constraint is formulated for STreeD: two threshold constraints. For better performance, objective more like the presented in DPF
38

---

Table 10: Runtime (s) for maximizing accuracy, with timeouts beyond 600s denoted with '-', Best results are shown bold. Average of five runs. Datasets for which all methods finish within one second are left out.
d
5
Dataset
[D]
[F]
DL8.5
MurTree
STreeD
DL8.5
MurTree
STreeD
Anneal
812
93
<1
17
5
Audiology
216
148
4
<1
<
1
<1
<
< 1
Australian- Credit
653
125
2
37
Breast-Wisconsin
683
120
4
<1
1
15
7
Diabetes
768
112
24
2
34
Fico
10459
17
<1
<1
<1
<1
2
German- -redit
1000
112
36
2
3
61
94
Heart-Clevelann
296
95
6
<1
<1
80
7
Hepatitis
137
68
<1
<1
<1
2
<
<1
Hypothyroid
3247
88
<1
94
13
11
lonosphere
351
445
69
152
146
112
Kr-vs-kp
3196
73
<1
<1
18
4
Letter
20000
224
547
200
145
Lymph
148
68
<1
<1
Mushroom
8124
119
3
<1
<1
<1
<1
Pendigits
7494
216
160
74
240
109
Soybean
630
50
<1
<1
<1
6
<1
1
Splice-1
3190
287
148
156
Tic-TacTToe
958
27
<1
<1
<1
2
<1
<1
Vehicle
846
252
15
137
343
Vote
435
48
<1
<1
<1
5
<1
1
Yeast
1484
89
10
<1
1
280
18
Average rank
3.0
1.29
1.71
2.89
1.39
1.72
could be formulated for STreeD. However, formulating and implementing fairness constraint in STreeD is much easier than developing a specialized method such as DPF. For equality of opportunity, STreel shows similar results when optimizing demographie parity.
In summary, STreeD shows performance not too far off from an existing specialized DP method; allows for easy formulation of new types of constraints, and outperforms both MIP methods by large margin.
G Classification Accuracy
The most studied use case for optimal decision trees is maximizing accuracy. Since STreeD general- izes previous dynamic programming approaches for optimal decision trees, here we evaluate how STreeD performs compared to two state-of-the-art dynamic programming approaches to optimal decision trees: DL8.5 and MurTree.
DL8.5 4] is dynamic programming approach that improves DL8 [65, 66) by adding branch- and-bound and new caching techniques. We use their publicly available Python package." Note that compared to their latest available version, which incorporates ideas from MurTree [20].
MurTree [20] also dynamic programming approach for optimal decision trees. Like DL.85 incorporates branch-and-bour and caching. Other improvements are a similarity lower bound and a special depth-two solver. We use the publicly available Python package."
39

---

100%
Trees computed
75%
50%
STreeD
25%
Mur Tree
DL8.3
0%
10
10
10
Runtime (s)
Figure 6: Runtime (s) comparison. A timeout of 300 seconds is used. Note the logarithmic x-axis.
We test both methods and STreeD on set of binarized datasets with binary class as described in Table 10. These are the same datasets as used in Appendix E." For each dataset, all three algorithms need find
of depth four or five with minimum misclassification score. We repeat the tests five times and report the average runtime in Table 10. Runtime results are also shown in Fig. 6.
By using the geometric mean of the relative performance [31], we 1.25 times faster than STreeD and STreeD on average is 6,4 times faster than DL8.5. According to Wilcoxon signed rank test with significance level 5%, both results are significant.
that MurTree on average is
Since STreeD outperforms DL8.5 and DL8.5 outperforms DL8, we can conclude that STreeD also outperforms DL8 in terms of scalability. Furthermore, Demirović et al. [20] compared MurTree with GOSDT [52] and observed that GOSDT' resulted in timeout for 65% the 68 datasets when computing optimal trees with maximum depth four, whereas Mur' TreeTree did not result in single timeout. Since STreeD's performance is only a factor of 1,25 slower than MurTree, we conclude that STreeD also outperforms GOSDT.
40


Reviews:
[{"review_id": "C8E7kfoRCh", "reviewer": "Reviewer_L3H7", "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.\n\n*****\n\nFollowing the rebuttal by the authors, I am updating my score accordingly.", "questions": "1) Can you please describe the intuition for order preservation and where it would be useful whereas additivity would not?\n\n2) Can you please explain how anti-monotonicity relates to the applications considered?\n\n3) Can you please describe an application that can be addressed by your setting that was not possible previously?\n\n4) 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?\n\n5) Do you see a possible application of this or a related setting to optimally train decision diagrams for classification?\n\nIn 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)).", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "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.\n\nAlong 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.\n\nAlong 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?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review and for the positive words about our work! We here respond to each of your questions:\n\n**Novelty**\n1. \"What is it that we gain from the more generalized setting described in this paper?\"\n\nRecent publications at premier venues on using DP for optimal DTs for varying optimization tasks show that there is a great interest in this topic. E.g.:\nAccuracy (Aglin et al., AAAI-20);\nNonlinear metrics (Demirović & Stuckey, AAAI-21);\nGroup fairness (Van der Linden et al., NeurIPS-22); and\nRegression (Zhang et al., AAAI-23).\n\nWe provide a general framework that covers all these cases, including regression. Normally, for each of these a specialized method had to be developed. We also precisely characterize necessary and sufficient conditions for the use of DP for new optimization tasks.\n\nThis adds to our understanding of decision tree algorithms and allows us to quickly model solutions to new optimization tasks, such as for example, individual fairness, for which currently no optimal DP method exists (see next answer).\n\n2. (Q3) \"Can you please describe an application that can be addressed by your setting that was not possible previously?\"\n\nConsider individual fairness as an example. Aghaei et al. (AAAI-19) have proposed a MIP method for individual fairness, but currently no optimal DP solution for individual fairness exists yet. However, this is possible within our framework. We provide details at the end of this response.\n\n**Order preservation**\n\n3. (Q1) \"Can you please describe the intuition for order preservation and where it would be useful whereas additivity would not?\"\n\nRecent work showed that DP could also be used for problems that are not additive, e.g., nonlinear metrics (Demirović and Stuckey, AAAI-21) and group fairness (Van der Linden et al., NeurIPS-22). This motivates the search for the limits of the use of DP for optimizing decision trees, which we provide.\n\nThe intuition behind order preservation is the principle of optimality (Bellman, 1957): optimal solutions can only be constructed from optimal solutions to subproblems.\n\n**Anti-monotonicity**\n\n4. (Q2) \"Can you please explain how anti-monotonicity relates to the applications considered?\"\n\nWe model group fairness as an anti-monotonic constraint. If it can be proven for a subtree that it could never be part of a tree that satisfies demographic parity, this subtree can be discarded.\n\n**Performance**\n\n5. (Q4) \"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?\"\n\nWe employ dynamic programming, which exploits the fact that subtrees can be solved independently (if the conditions we present hold) and repeated subproblems can be cached. Other methods, such as MIP, do not consider this, so these methods end up doing exponentially more work, which is reflected in our experiments.\n\nThe disadvantage of DP is that it is specific to each possible application. The added value of the STreeD framework compared to existing DP approaches addresses exactly this: it provides a general approach to using DP for building optimal decision trees.\n\n**Decision Diagrams**\n\n6. (Q5) \"Do you see a possible application of this or a related setting to optimally train decision diagrams for classification?\"\n\nDecision diagrams are not separable in the same way as decision trees: i.e., subdiagrams may share nodes, whereas subtrees never share nodes. Therefore, the same breakdown into independent subproblems cannot trivially be applied and the question whether one could devise a DP algorithm that is more efficient for decision diagrams, remains an open question.\n\n\n**Appendix: Individual fairness separable formulation**\n\nIndividual fairness optimizes the number of similar individuals (as defined by some distance function) that receive the same label.\nThe following provides the details of how individual fairness could be modeled as a separable optimization task.\n\nLet $d(x_1, x_2)$ be a distance function that returns one if $x_1$ and $x_2$ are similar, and zero otherwise. Let $O(D) = \\\\{ (x_1, x_2) \\in D | d(x_1, x_2) = 1 \\\\}$. Let $n = |O(D)|$ over the original dataset $D$.\n\nWhenever a node is split, the transition function should update the state $s$ to record which pairs in $O(D)$ end up in different subtrees. For the subtree with dataset $D’$, call this record $M = \\\\{ (x_1, x_2) \\in O(D) | (x_1 \\in D’ \\wedge x_2 \\notin D’) \\vee (x_1 \\notin D’ \\wedge x_2 \\in D’) \\\\}$.\n\nA solution value consists of bounds on the worst and best case value for the individual fairness, and a label for each pair in $M$: $(worst, best, L: M \\rightarrow K)$. This is computed as follows: $g(D, M, \\hat{k}) = (|O(D)| / n, 1, L(m) = \\hat{k},  \\forall m \\in M)$. \nThe worst case is lower bounded by $|O(D)|/n$ because all pairs in $O(D)$ receive the same label. The best case is still 1, in case all instances in $M$ receive the same label. The label of all pairs in $M$ are set to $\\hat{k}$. \nWhen we merge two solution values $(worst_1, best_1, L_1)$ and $(worst_2, best_2, L_2)$ for solutions generated for state $(D_1, M_1)$ and state $(D_2, M_2)$, we check which split pairs in $O(D)$ are joined again: $J = \\\\{ M_1 \\cap M_2 \\\\}$. Let $v = |\\\\{m \\in J|L_1(m) = L_2(m)\\\\}|$ be the number of pairs with the same label. The merged solution value becomes:  \n$(worst_1 + worst_2 + (|J| - v)/n, 1 - ((1-best_1) + (1-best_2) + v/n)$, $L(m) = L_1(m) \\text{ if } m \\in M_1, \\text{otherwise } L_2(m)~\\forall m \\in M )$.\n\nA solution is dominated if its worst fairness value is higher than another solution’s best fairness value.\nA solution is infeasible if its worst fairness value is higher than a predetermined threshold.\n\nThe optimization task described above is separable, but not additive. it satisfies all conditions of our framework, and thus results in optimal solutions.\n\n"}, {"review_id": "tC1rUjNB6q", "reviewer": "Reviewer_VtkV", "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.", "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.", "limitations": "No limitations were discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "+ Very well written and rigorously formalized.\n+ Framework expands the class of optimization models that can be addressed via DP in an intuitive way.\n\nThe 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. \n ", "weaknesses": "- The originality of the generalization is unclear. \n- More details needed to justify the benchmarks in the numerical section.\n\n\nMy 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. \n\nMore 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. \n\nHowever, 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,\n\nKarp, Richard M., and Michael Held. \"Finite-state processes and dynamic programming.\" SIAM Journal on Applied Mathematics 15.3 (1967): 693-718.\n\nand references therein. The multiobjective-representable DP concept is also classical, e.g., \n\nLi, Duan, and Yacov Y. Haimes. \"Extension of dynamic programming to nonseparable dynamic optimization problems.\" Computers & Mathematics with Applications 21.11-12 (1991): 51-56.\n\nand the idea of the *merge* also shares some similarities with the concatenation concept by\n\nElmaghraby, Salah E. \"The concept of “state” in discrete dynamic programming.\" Journal of Mathematical Analysis and Applications 29.3 (1970): 523-557.\n\nOther related works include:\n- Smith, Douglas R. Representation of discrete optimization problems by discrete dynamic programs. Naval Postgraduate School, 1980.\n- Pollock, Stephen M., and Robert L. Smith. A formalism for dynamic programming. 1985.\n\nMany 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. \n\nMy 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. \n\n*Other notes* \n- 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.\n- 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.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive words about our work! In response to your questions:\n\n**Novelty**\n\n1. \"My major concern is that I struggle to understand the novelty of the work and its relationship to more fundamental DP theory.\"\n\nWe provide a tailored DP theory for decision trees. This has several benefits.\n\n- We draw the deep connection between decision trees and DP. It seems that the community is not aware of this connection: papers are published at prime venues on specific problems that naturally fit within our framework, e.g., nonlinear metrics (Demirović & Stuckey, AAAI-21 ); group fairness (Van der Linden et al., NeurIPS-22) and regression (Zhang et al., AAAI-23).\n\n- Given our specific setting, we show how order preservation is a necessary condition to satisfy the classic DP principle of optimality (Bellman, 1957). We also show that additivity, as required in previous general DP methods for optimal decision trees (Nijssen and Fromont, DM&KD-10) and Lin et al., ICML-20), is not necessary.\n\n- As a consequence, this also allows us to exploit tailored algorithms for decision trees, namely a specialized algorithm for computing trees of depth-two, caching subtrees, and bounds. This third point is a minor point conceptually (we include it in the Appendix) but in practice it gives significant benefits.\n\n- Lastly we also provide code for our framework which further supports the adoption of our general DP approach in the community.\n\nIn regards to specific questions about general DP theory in relation to the papers mentioned:\n\n- The _monotonicity_ condition from Karp et al. indeed has similarities with our _order-preservation_ condition. Both our work and Karp et al. point out the similarity with the principle of optimality, as stated by Bellman (1957). However, a difference is that Karp et al.’s definition assumes costs to be real, completely ordered, and additive, whereas we prove that in the context of finding optimal decision trees these assumptions are not needed.\n\n- The _right congruence_ notion discussed in Karp et al. relates to identifying equivalent states, which in DP relates to identifying equivalent subproblems, but is orthogonal to anti-monotonicity and order preservation. Similar to previous DP approaches, our method caches and reuses cached solutions for equivalent subproblems.\n\n- The _multi-objective_ notation from Li et al. has similarities with our proposition (A.4) about combining separable optimization tasks into a new separable optimization task. However, Li et al. also restrict their analysis to solutions in $R^n$. The solution value for each objective is still assumed to be real, completely ordered, and additive, which limits their theory to element-wise additive optimization tasks. Our theory does not share these limitations, which we hope to exploit in future work.\n\n- Our _merge_ operation has similarities with _output concatenation_ by Elmaghraby. However, Elmaghraby assumes that the output space (solution value space) is completely ordered, whereas our work does not make this assumption.\n\n- Smith and Douglas (1980) and Pollock and Smith (1985) both  also assume a real-valued completely ordered solution value space.\n\nTo strengthen our theoretical contribution we will mention these similarities and extensions on existing theory in our final version.\n\n2. \"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.\"\n\nYes, we agree: one of the contributions of our work indeed is to make DP more accessible for optimizing decision trees. It also corrects previous work that limited DP for optimal decision trees to only additive optimization tasks (Nijssen and Fromont, DM&KD-10) and Lin et al., ICML-20).\n\n**Paper title**\n\n3. \"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\"\n\nWe will adopt the suggested title to highlight, as suggested, the theoretical contributions of the paper.\n\n**Benchmarks**\n\n4. \"More details needed to justify the benchmarks in the numerical section\"\n\nWe are surprised by this comment since we invested a considerable effort in the experimental section. We evaluated our approach on four diverse applications, surveyed related work for each application and compared to the state-of-the-art methods for each application (including heuristic and optimal methods) on many datasets. We took extra care to make sure the experiments are detailed and have a clear outcome. Note that the main points are summarized in the paper, but more details are provided in the Appendix (we will emphasize this in the paper). We would be happy to expand the experimental part should the reviewer have further suggestions.\n\n**CP and other methods**\n\n5. \"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\"\n\nWe surveyed the literature and compared to the state-of-the-art optimal methods for the application domains considered, except for cost-sensitive classification, where for lack of an open source optimal method, we compare with a state-of-the-art method without optimality guarantees. We can clarify this in the text.\n\nAs for CP specifically, as far as we know, CP formulations for optimal decision trees have only been proposed for maximizing accuracy and not for the optimization tasks considered in our work. For maximizing accuracy, Aglin et al. (AAAI-20) already showed that the DP approach scales better than the state-of-the-art CP solution.\n\n"}, {"review_id": "9tP5k3SWFv", "reviewer": "Reviewer_46BC", "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. \nTheoretical 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.\nDetailed 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.", "questions": "-", "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.\n", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This is a strong generalization of existing DP frameworks for Optimal Decision Trees solving. \n- 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.\n", "weaknesses": "- No major or minor weaknesses.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive words about our work!\n\nAn example of a problem for which we expect no efficient separable optimization task can be formulated is the optimization decision tree policies for Markov decision processes, for which Vos and Verwer present a MIP formulation (Vos & Verwer, arXiv:2301.13185, 2023). In this problem, the optimal policy in a subtree depends on the frequency of each Markov state being reached. However, the frequency of each state being reached is dependent on the policy, which depends on all decision variables in the rest of the tree. This makes it hard to see how an optimal solution for the current subtree can be found independently from the rest of the tree.\n\nWe will mention this example in the final version of our work.\n\n"}, {"review_id": "H71cyjmS2N", "reviewer": "Reviewer_4G5j", "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.", "questions": "see weaknesses.", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "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?\n\n- 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.\n\n- 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))?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive words about our work! In response to your questions:\n\n1. \"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?\"\n\nAn example of a problem for which we expect no efficient separable optimization task can be formulated is the optimization decision tree policies for Markov decision processes, for which Vos and Verwer present a MIP formulation (Vos & Verwer, arXiv:2301.13185, 2023). In this problem, the optimal policy in a subtree depends on the frequency of each Markov state being reached. However, the frequency of each state being reached is dependent on the policy, which depends on all decision variables in the rest of the tree. This makes it hard to see how an optimal solution for the current subtree can be found independently from the rest of the tree.\n\nWe will mention this example in the final version of our work.\n\n2. \"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?\"\n\nThe plot is a cumulative distribution plot with on the vertical axis the percentage of problem instances which were a) solved within the given runtime (left side of the plot), or b) solved up to a certain MIP gap (right side of the plot).\n\nFor example in Fig. 2b, our method finds the optimal tree for all problem instances within 20 seconds. The state-of-the-art MIP method Jo-PPG-MIP (Jo et al., 2021), finds the optimal solution for 50% of the problem instances within the time-out of 300 seconds. This means the MIP gap is 0% for 50% of the problem instances (middle of the plot). At timeout, 80% of the instances are solved with a MIP gap below 50% (right side of the plot). This means that at timeout 20% of the instances still had a remaining MIP gap higher than 50%: far from being solved.\nWe will add this clarification in the paper.\n\n3. \"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))?\"\n\n$b(u)$ is the branching feature of node $u$. $g(s, b(u))$ is the cost of branching on feature $b(u)$ in state $s$\n\n"}, {"review_id": "XhXBaS1SC4", "reviewer": "Reviewer_khZh", "summary": "The authors present a dynamic programming (DP) method for constructing optimal decision trees.\nThe method is more general than previous DP methods. The authors report extensive experiments\nto compare with previous methods which including MIPS and DP methods.", "questions": "(1) Is the 'only if' part of Prop. 4.3 correct with the standard definition of 'Markovian'?\n\n(2) Is there a typo in lines 114-116 of Appendix A?\n\n(3) When you say in line 266 'This Pareto front can then be used to find the decision tree with, e.g., \nthe best F1-score', is the Pareto front of possibly exponential size?\n\n(4) In lines 268-282 (Group fairness): Are the actual constraints you apply\nstronger than demographic parity. Are you imposing that you have parity down each branch, which would be much stronger?\n\n****ADDED AFTER REBUTTAL****\nI 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.", "limitations": "There are no obvious negative societal impacts.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and there is extensive supplementary material including code.\nThere appears to be a real contribution in the integration of diverse types of constraints\nwithin the DP framework. The DP method is conclusively shown to be much faster than MIPS methods.\nThere is a welcome theoretical analysis of the problem which allows the authors to state weaker\nsufficient 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\nof conditions are not only sufficient but also necessary for the DP method to work.\nI believe that these conditions are sufficient, but I have some doubts about necessity.\n\nFirstly, in lines 193-194 you give a definition of a Markovian cost function:\nit is a cost function that depends just on the state and the current branching decision.\nIn Appendix A (lines 46-47) you give the impression that a Markovian cost function can depend on\nthe 'history' of branching decisions, which seems to go against standard definitions (including your own) \nof Markovian. Would the DP method still work if the cost depended, for example, on the order of the\nbranching decisions in the history? If so, then the claim that having a Markovian cost function is\na necessary condition for the DP method to work appears false.\n\nSecondly, you give a definition of anti-monotonicity (Def. 4.5) which appears non-standard.\nI would expect c to be anti-monotonic iff (c(Y) and X a part of Y implies c(X)) but you say\nc is anti-monotonic iff (opt(Y) and X a part of Y implies c(X)). You could call this, for example, \nanti-monotonicity on optimal solutions. A proof of necessity can only work with this weaker version\nbut Appendix A (lines 114-116) seems to be saying that the stronger version is necessary (which is wrong).\n\nOne obvious fix would be to weaken your claims by dropping the 'only if' parts of Prop. 4.3 \nand Theorem 4.6. This would leave a very solid paper. The other solution is to try and produce\na watertight proof of the 'only if' directions in the rebuttal.\n\nThere are also a few minor presentation improvements that can be made in terms of presentation:\n- In last sentence of the abstract you should say something about the quality of the trees you find \n(otherwise being faster is a vacuous piece of information).\n- lines 166-170: This paragraph is confusing. One possible interpretation is that constraints \nare never taken into account, which is surely not the case. It is not clear what 'building blocks' refers to. \n- Definition 4.4 (line 209): you should avoid phrases such as 'and thus' in a definition. \nThis is a consequence of the definition not part of it. This could be stated after the definition.\n- Definition 4.5: again the 'and thus v_1 \\notin opt(\\Theta_1,s_1)' is out of place in a definition.\nIt is implicit that Theta/Theta_i are the set of feasible solutions for s/s_i. It would be better to recall \nwithin the definition.\n- line 218: give an example of a non-anti-monotonic constraint.\n- line 229: why 'street' instead of 'streed'?\n- equation (10): 'else' should be 'otherwise'\n- line 285: do you mean monotonic or anti-monotonic?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive words about our work! In response to your questions and comments:\n\n**Markovian**\n\n1. \"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\"\n\nThe parents’ branching decisions can be included in the state, as explained in line 163-164. This is a common trick applied in MDPs. Such an MDP is called a _history dependent_ Markov Decision Process, which is equivalent to a normal Markov Decision Process (see, for example, Section 1.4.1 in Sigaud and Buffet, _Markov decision processes in artificial intelligence_, John Wiley & Sons, 2013). \n\n2. \"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\"\n\nYes, the DP method would still work. The order of the parents’ branching decisions could be recorded in the state. Given our answer at point 1, this does not violate our claim that a Markovian cost function is a necessary condition.\n\n3. (Q1) \"Is the 'only if' part of Prop. 4.3 correct with the standard definition of 'Markovian'?\"\n\nPoints 1 and 2 show that the only if part of Prop 4.3 is correct and in accordance with the standard definition of Markovian.\n\n**Anti-monotonicity**\n\n4. \"The definition of anti-monotonicity is non-standard.\"\n\nWe indeed only require anti-monotonicity on optimal solutions, in order to have a necessary condition. Anti-monotonicity on all solutions is sufficient, but not necessary. We will update the text to make this more clear.\n\n5. \"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).\"\n\nAppendix A (lines 114-116) uses the weaker version, and not the stronger version. There is no typo in these lines (Q2), but we understand the confusion of our notation. We will update the text to make this more clear by replacing $\\theta$ with $opt(\\Theta)$ and $\\theta_1$ with $opt(\\Theta_1)$ in lines 114-116 in the appendix.\n\n6. \"line 285: do you mean monotonic or anti-monotonic?\"\n\nThis should indeed be anti-monotonic. Thanks!\n\n**Pareto front**\n\n7. (Q3) \"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?\"\n\nLet $N_0$ and $N_1$ be the number of negative and positive instances in a dataset. The maximum size of the Pareto-front is $M = \\min(N_0, N_1)$. This Pareto-front could for example have the values $\\\\{ (M-x, x) ~ | ~ x \\in \\\\{0, 1, ..., M\\\\} \\\\}$. \n\n**Demographic Parity**\n\n8. (Q4) \"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?\"\n\nWe enforce the demographic parity on the whole tree only, and not on each branch individually.\n\nEnforcing demographic parity on every branch would be an example of a non-anti-monotonic constraint: a subtree that exceeds a discrimination limit could be balanced out by another subtree with an opposite bias, yielding a combined tree that does not violate the demographic parity constraint.\n\n**Pronunciation**\n\n9. \"Why 'street' instead of 'streed'?\"\n\nThis is a play on words, since \"t\" and \"d\" are often pronounced the same (incorrectly).\n\n**Other suggestions**\n\nWe also thank the reviewer for the other suggestions for improving the text. We will include the suggestions in our final version.\n\n\n"}]

Author rebuttal:

Meta-review: I am happy to propose acceptance of the paper to NeurIPS.

Two of the reviewers suggested a change in the title, which I would like to encourage the authors to seriously consider as well. All other comments of the review team have been answered convincingly; in those places where the reviewers have not confirmed that themselves, I checked myself that the responses resolve any of the raised issues.

Thank you for submitting your work to NeurIPS!
Decision: Accept (poster)