Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*
Authors: Ayman Chaouki
Jesse Read
Albert Bifet
Venue: ICML 2025 poster (2025)
Keywords: Decision Trees
AND/OR search
AO*
Dynamic Programming
Branch and Bound
Primary area: general_machine_learning
TL;DR: We introduce Branches, a new AO* algorithm that efficiently seeks optimal Decision Trees balancing accuracy and interpretability.

Abstract: Decision Tree (DT) Learning is a fundamental problem in Interpretable Machine Learning, yet it poses a formidable optimisation challenge. Practical algorithms have recently emerged, primarily leveraging Dynamic Programming and Branch \& Bound. However, most of these approaches rely on a Depth-First-Search strategy, which is inefficient when searching for DTs at high depths and requires the definition of a maximum depth hyperparameter. Best-First-Search was also employed by other methods to circumvent these issues. The downside of this strategy is its higher memory consumption, as such, it has to be designed in a fully efficient manner that takes full advantage of the problem's structure. We formulate the problem as an AND/OR graph search which we solve with a novel AO*-type algorithm called Branches. We prove both optimality and complexity guarantees for Branches and we show that it is more efficient than the state of the art theoretically and on a variety of experiments. Furthermore, Branches supports non-binary features unlike the other methods, we show that this property can further induce larger gains in computational efficiency.

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*
Ayman Chaouki
Jesse Read Albert Bifet
Abstract
simple decision rules (splits). However, this interpretability weakens as the number of splits increases, which makes the joint optimisation of accuracy and sparsity (minimising the number of splits) fundamental problem in Interpretable Machine Learning. We refer to this problem as the sparsity problem. This optimisation task is particularly difficult due to its NP-completeness (Hyafil & Rivest, 1976). Conse- quently, greedy approaches, such as C4.5 (Quinlan, 2014) and CART (Breiman et al., 1984), have been historically favoured. While these methods are fast and scalable, their greedy nature often yields suboptimal and overly complex DTs.
Decision Tree (DT) Learning is fundamental problem in Interpretable Machine Learning, yet it poses a formidable optimisation challenge. Prac- tical algorithms have recently emerged, primarily leveraging Dynamic Programming and Branch & Bound. However, most of these approaches rely Depth-First--Sean
strategy. which is ineffi- cient when searching for DTs at high depths and requires the definition of a maximum depth hyper- parameter. Festt-FisttSearch was also employed by other methods to circumvent these issues. The downside of this strategy is its higher memory consumption, as such, has to be designed in a fully efficient manner that takes full advantage of the problem's 's structure. We formulate the prob- lem within an AND/OR graph search framework and we solve it with a novel AO*-type algorithm called BRANCHES. We prove both optimality and complexity guarantees for BRANCHES and we show that it more efficient than the state of the art theoretically and on a variety of experi- ments. Furthermore, BRANCHES supports non- binary features unlike the other methods, we show that this property can further induce larger gains in computational efficiency.
This issue spurred a large research effort into investigating alternatives, mainly focusing on Mathematical Program- ming (Bennett, 1992; 1994; Bennett & Blue, 1996; Bessiere et al., 2009; Norouzi et al., 2015; Bertsimas & Dunn, 2017; Narodytska et al., 2018 8; Verwer & Zhang, 2019; Hu et al., 2020; Blanquero et al., 2021; Günlük et al., 2021). However, the number of variables in these Mathematical Programs depends strongly on the dataset size and thus induces poor scalability. Moreover, these methods often fix the DT struc- ture and only optimise the internal splits and leaf predictions, overlooking the sparsity portion of the problem.
Recently, Dynamic Programming (DP) (Bellman & Dreyfus, 2015) and Branch & Bound (B&B) (Lawler & Wood, 1966) led to breakthroughs in runtimes, with most approaches employing a Depth- First-Search (DFS) strategy (Nijssen & Fromont, 2007: 2010; Aglin et al., 2020; Demirović et al., 2022; van der Linden al., 2023). While DFS is appeal- ing from storage economy perspective, its uninformed nature makes it inefficient for large problems (Pearl, 1984, p.36). On the other hand, informed strategies were also used through Sest--histtSearchh (BFS) (Hu et al., 2019; Lin et al., 2020), albeit in a sub-efficient manner that does not take full advantage of the problem's 's AND/OR structure.
1. Introduction
Black-box models are ill-suited for contexts where decisions carry substantial ramifications. In healthcare for example, misdiagnoses can delay crucial treatments and lead to severe outcomes. Likewise, in the criminal justice system, black- box models can obscure biases and result discriminatory rulings. Such risks highlight the necessity of adopting inter- pretable models in sensitive domains.
Montanari et al. (1975) showed that DP problems can be formulated within an AND/OR graph search framework, in which they can be solved efficiently with powerful heuristic search algorithms (Pearl, 1984). We follow this approach because the sparsity problem can be framed within DP, then upon defining an adequate heuristic, which we call the Purification Bound, we solve the AND/OR graph search problem with the celebrated * approach (Nilsson, 2014;
Decision Trees (DTs) are highly interpretable due to their
'LIX, Ecole Polytechnique, IP Paris 'AI Institute, University of Waikato 'LTCI, Télécom Paris, IP Paris. Correspondence to: Ayman Chaouki <chaoukiayman226 @mmaemmmmama........
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO
Martelli& & Montanari, 1978). The induced algorithm, called BRANCHES, is guaranteed return optimal solution when it terminates. In addition, BRANCHES also satisfies complexity guarantees in the form of an upper bound on the number of evaluated branches before termination. To the best of our knowledge, such analysis was only previ- ously conducted in (Hu et al., 2019, Theorem E.2). We show numerically that BRANCHES' complexity bound is significantly smaller than the bound in (Hu al., 2019, Theorem E.2). Empirically, BRANCHES always finds an op- timal solution in substantially fewer iterations than the state of the art, and despite its current Python implementation, it also displays better runtimes than its C++ competitors. Furthermore, upon reaching timeout, some methods can still propose solution, albeit with no quality guarantees. This property called the anytime behaviour and it is satisfied by BRANCHES. On this front, experiments show that BRANCHES proposes better solutions than the state of the art.
simas & Dunn, 2017). Unlike the DFS methods, OSDT employs analytical bounds and priority queue to prioritise regions with better bounds, resulting in more aggressive pruning of the search space. On the other hand, OSDT oper- ates on the space of DT's instead of the lattice of itemsets, which greatly slows it down. To alleviate this issue, Lin et al. (2020) developed GOSDT, a BFS algorithm operating on the lattice of itemsets. GOSDT can be considered the state of the art for the sparsity problem, its DP is as efficient as the DFS methods while its B&B prunes the lattice more ef- ficiently. Furthermore, GOSDT generalises OSDT to other objectives including weighted accuracy, balanced accuracy, F- F-soore, AUC and partial area under the ROC convex hull.
DFS vs BFS: (Pearl, 1984, Chapter 2) provides an excel- lent discussion on the differences between DFS and BFS, with brief summary in (Pearl, 1984, Section 2.5). The main advantage of DFS is its storage economy. However, it necessitates a maximum depth parameter to avoid long searches in one region of the search space. Moreover, the uninformed nature of DFS makes inefficient for large problems. On the other hand, the informed nature of BFS allows it to find solutions more quickly than DFS without the need for a maximum depth parameter. Nevertheless, this judicious paradigm comes at the cost of high memory consumption, hence the necessity to devise BFS algorithms that find an optimal solution as quickly as possible.
2. Related Work
In this section, we mainly survey the proposed Depth First Search (DFS) and Best First Search (BFS) algorithms.
Nijssen& & Fromont (2007; 2010) formulate a search space, called the lattice of itemsets, from which DT's can be mined. This powerful idea induced the DL8 algorithm and is the basis of many subsequent works. DL8 explores the lattice in a DFS fashion sceking an optimal DT that satisfies a certain set of constraints. Moreover, DL8 exhibits enough flexibility to solve the sparsity problem, as evident by the lex- icographical objective Argmin,-(erren (T), size (T)} con- sidered (Nijssen& & Fromont, 2010, Section 2.3). However, the immense size of the lattice, which grows exponentially with the number of features, renders DL.8 impractical many real-world applications. A decade later, Aglin et al. (2020) improved DL8 with a B&B component that prunes the lattice based on the current best found solution. The induced DL8.5 algorithm is faster than DL8 on a broader range of applications. However, it only considers constraints on the maximum depth and minimum number of data per leaf, prohibiting it from solving the sparsity problem. In subsequent work, Demirović et al. (2022) improved the computational complexity of D1.8.5 through the use of a specialised technique for handling DTs of depth 2, which resulted in the MurTree algorithm. Recently, MURTREE was generalised by van der Linden et al. (2023) to handling a wider range of objectives within the STREED framework.
DFS:
To achieve this, we frame the DP problem of sparsity as an AND/OR graph search (Martelli & Montanari, 1978). (Nilsson, 2014, Section 3.1) and (Pearl, 1984, Section 1.2.4) provide detailed overviews on AND/OR graphs. In this con- text, we can apply the popular and efficient AO* algorithm, which was introduced in (Martelli & Montanari, 1978) and (Nilsson, 2014, Section 3.2). We note that Martelli & Monta- nari (1978) employed AO (with the early name HS) to seek- ing optimal DTTs, but in a cost-sensitivity context (Lomax Vadera, 2013) that is distinct from the sparsity problem. An- other difference is that the authors sought DTs that perfectly classify dataset while we seek DTs on the pareto front jointly maximising accuracy and minimising the number of splits. Verhaeghe et al. (2020) also employ an AND/OR formulation, but within a Constraint-Prorammnigg (CP) paradigm. The induced CP algorithm does not solve the sparsity problem but rather a similar problem to DL8.5 where the maximum DT depth is constrained. In an empiri- cal comparison, Aglin et al. (2020) thoroughly showed that DL8.5 outperforms CP.
3. Problem Formulation
BFS: Hu et al. (2019) introduce OSDT, which considers the objective Argmin, (crror (T) + Aleaves (T)) where 0 < x << is a soft penalty on the number of leaves. A sim- ilar objective has been considered in prior works, e.g. (Bert-
We consider classification problems with categorical fea- tures X = (Xx), "..,,....""".... ...)) and class Y e {l.....K]
Vi E (1....q): x(0 E (1.....CC. C.), G22 2
2

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
x
x
x
4
x
x
(1,14,4)
Figure 1. Consider feature space with five hinary features x X²2) xx(3) xx(1, X {0,1), 1}. The figure provides example of
sub-DT {4, 4 rooted in that stems from splitting branch with respect feature x5) and splitting branch lg with respect
to feature ( the red perimeter emphasises the fact that T' is rooted in I. Here 8 (T) 2, I[X 1} ^ 14 03,4
IA = -0, l2 = A 1(x()) 1, = 12 A xXx() = 0}, 4 12 AXX = =}.
where y 2 2 and K 2 2. We are provided with dataset D= {(Xm Ym > n n 2 1 examples. In the following sections, we define the notions of branches and sub-DT's that are key to our formulation.
In the following, we define the notion of splitting a branch. Let i E {I.....q} fi....., is()) be an unused feature in the splits of I. We define the children of that stem from splitting with respect to as the set Ch (1, (l....,cc,) where:
3.1. Branches
Vj E (l.....C.):4. ::::C====(-"" =
(2)
branch is a conjunction of clauses on the features of the following form (where Il is the indicator function):
The dataset D = {(Xm, mm))m= provides an empirical
distribution of the data. The probability that a datum is 7 is as follows:
S(1) 1 A (xx = =
IP [1 = (1
m
where n -m> 1 (Xm) is the number of data in and want to define
such that V1 5 u (() :5 i 54 1 15 S Ci,
and:
is the total number of data. Likewise, the probability that datum is in I and correctly classified. For this purpose, we define the predicted class in I as:
Yu, E (1)) v d' io + in
(1)
This condition ensures that no feature is used in more than one clause within We refer to these clauses as rules or splits. S (1) is the number of splits in L.
(l) = Argmax (n (1)
where ng (1) Σm I (X,,) I( k} is the number of data in that are of class k. In other words. ke (1) is the majority class in l. Then the probability that a datum is in and correctly classified is:
For any datum X (X(1), ..... x())), the valuation of for X is denoted / (X) E (0, 1} and defined as follows:
S())
=1 ((x)=1
A T(x = = =
T2x-(0) (1)
(1) PP 1 (1) Y
(3)
72
When (X) = 1, we say that X is | or that contains X. The branch containing all possible data is called the root and is denoted Ω. Since the valuation of for any datum remains invariant when reordering the splits, we represent / uniquely by ordering its splits from the smallest feature index to the highest, i.c. we impose < 1 < ... < (s()) & g. This unique representation is at the core of our memoisation.
3.2. Sub-DTs
Let I be a branch, sub-DT rooted in / is a collection of branches T' = {4,.... ......,4p. 4pr that stems from successive splits starting from from I, we denote S (T) the number of these splits. Intuitively. S (T) can be see as the number of internal nodes T, and lı,..., l/T) as the leaves of T.
3

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Figure provides an example of sub-DT. T partitions 1 in the following sense:
Terminal states: For every branch we assign unique terminal state T E T, which signals that we should not consider any further splits (end of search).
1- V u=1 lu Yu, u' E (I....., [T]) u u' Lu Al. =
Actions A and transitions F: Consider a non-terminal state (a branch) I = (0 T(x = ju} E S T, there are two types of actions in A (1):
For any datum X in 1, T predicts the majority class of the branch Lu E containing X:
The terminal action ā which transitions / into its cor- responding terminal state 7 E T. Thus F (1, a) = (7).
T
(X))= = =xx==1m (X) (lw) (l....,K] K} (4)
Split actions, which is the set of all unused features {1.....q] /) fii..... (s(t)) by 1. Let i be a split action, taking i transitions to the set of children Ch (1, i),
Now we can define the probability that datum is in I and correctly classified by T:
defined in (2). Therefore F (1, = Ch (I.
H(T) = P (X) = (x) YY
Thus A() = { U (I,.... 3 \ fir.... isc) When S (1) q. then A (1) {ā} and we can only transition to 1.
|
[
Σ
P (L 1,) (lw)) =
- y1 Σ H H(w)
Reward function r: Let 1 E S \ T be non-terminal state and a E A (l), we define the reward (1, a) as follows:
The additivity property is due (4, I forming partition of I, then the result stems from the definitions (4) and (3).
If a is split action, then r (1, a) = - À regardless of 1.
À is the penalty parameter defined in Equation (5).
We define a DT as a sub-DT that is rooted in the root f. Let T be a DT, since ? (X) = 1 for any datum X then:
If = then (I, 7 (1) as per Equation (3).
(T)) P [ (X) = 1, (X) =
=
We represent our state space model as an AND/OR graph following the hypergraph convention in (Nilsson, 2014, Sec- tion 3.1). The nodes of the hypergraph represent states and its connectors represent actions. A connector is a generali- sation of the notion of edge, it connects a parent node to a set of successor nodes. In our formulation, a node (state) 7 has |AA (1) outgoing connectors, each corresponding to an action. The connector of action a E A (1) links node to the set of successor nodes F (1, a.) and has weight r (1, a). See Figure 2 for example. In the following, we introduce the notion of policy and we transform the problem into seeking an optimal policy.
which is the accuracy of T. To solve the sparsity problem, we seek the DT T maximising the following objective:
H₂ (T) = -S (T) + (T)
(5)
where 0- < A < is a penalty parameter penalising DT's with a large number of splits. This objective is employed by CART during the pruning phase, was also considered by Bertsimas& & Dunn (2017) and recently by Chaouki al. (2024). Hu et al. (2019) and Lin et al. (2020) use a slightly different version, where the total number of leaves is pe- nalised instead. In a setting with binary features, the number of leaves of a DT is always equal to the number of splits plus and the two objectives are equivalent in this case.
A policy v maps each non-terminal state / E S T to an action n (I) E (I). We define the trajectory of x from as {1} and for all 2
the sequence (TT 120
where T7,
3.3. AND/OR Graph Representation
TT
U LETTAT
F Flu, v (lw))
U
(Ta 1,,, 20
To formulate our AND/OR graph, we define the following state space model (S, A, F,r) where S is the set of states, T C S the set of terminal (or goal) states, A the set of actions with A (L) the set of permissible actions at a non- terminal state/ 1 E S \ T, F S x A > P (8) the transition function (with P (8) the power set of S) and r S A - IR the reward function.
WeTgLoT
The term UI. UL.ETH (ur is the set of terminal states in TE, while the term Ul,TTAAT F (lu, (lw)) is the set of induced states from taking the actions dictated by policy in each non-terminal state in Tī.- As such, the trajec-
tory TT. 120
stems from following x from by applying
States S: Our state space is the set of all branches along with the set of all terminal states T, which we define below. The root 52 is always our initial state.
it, each time, at the non-terminal states and retaining the terminal states.
4

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
spit
Connecoor for split action
split
1:0
C
Connector for temirral action
C1:03:00 1:000
C
:1:03:1
1:10:00
1112:
CLi
C113
0.003
C2:03:11
C2:1.30
2:1.3:1
C 0::00,:0,3.0
1: 1.0,2 0.33:
1.30
L3:1 0:.00.3::
1::22:03:
L.:00:3::
11:12:13:1
Figure ANDIOR graph for a classification problem with three binary features X x xx()) To make notation lighter, we represent any branch - (((())) = je) with in jiy...y is()) -js()). for example
0, represents the branch Tx = 0} ( =}. We colour in red the actions taken by the policy: π (f2) 1, a (1 0) (1: 1) 2, n (1 2, T 01: = (1 0) = x (1 1, 1,2:1) = a, which also depicts the DT of æ. Note that, although curved connector associated with the terminal action 7 connects the node, transitions terminal state from which action be taken. We represent it like this to avoid overloading the figure with additional nodes corresponding to the terminal states.
Proposition 3.1. Let be policy and I E S T, then there exists a minimum of 2 1 such that for any I 2 Ti" TV = (TI..... .T.z1) is composed of terminal states only.
Proposition 3.2 implies that we can seek x and then deduce T by following л. from Q. In the terminology of (Nilsson, 2014, Section 3.1), T is an optimal solution graph. Our task can be transcribed as seeking policy that induces an optimal solution graph. This can be achieved with AO*
Proposition 3.1 shows that for any branch I E S \ T, any policy x arrives at a final set of states ( 11r:p }. in which case we define 77 (4....., AIr,,11 as the sub-DT of π rooted in 1. 77 is indeed sub-DT rooted in by the definition in Section 3.2 because it stems from successive splits from I. For the root S2 we simplify the notation T T and call T the DT of æ.. Figure 2 provides an example of the DT of a policy. This definition allows us to evaluate policies as follows: we define the value of policy from a non-terminal state 1 S \T with:
4. The Algorithm: BRANCHES
To describe BRANCHES, we first derive the Bellman opti- mality equation satisfied by the problem Proposition 4.1. do this conveniently, we introduce the state-action values. For any policy म, branch I S \ and action A (l), the state-action value Q (1, a) the cumulative reward of taking action first and then following
@ (
Σ
vTT (lw)
(7)
Va (1)
Σ
Σ LETTAT
(la, π (l.)
(6)
LEFULA)
We abbreviate the notation for all quantities that are related to T" with Tý, = Tye 77 = = . = ===", ," = Proposition 4.1 (Bellman Optimality Equations). Let πt" be an optimal policy, i.e. n" E Argmmax, V* (St) and consider the set of non-terminal states in its trajectory from Q:
y" (I) is the cumulative reward incurred by following policy from until we end up in the sub-DT 77" In the example of Figure 2, V (I) is the sum over all the weights of the red connectors. Policies are evaluated and compared with respect to their value from Ω2 an optimal policy being x' E Argmax,, 'd (22). In the following, we justify why seeking n² is equivalent to seeking T Argmax, H. (T))
To S
U 1=0
Proposition 3.2. Let π be a policy and E S a non- terminal state, then a (1) satisfies the following:
Now consider a policy and suppose that for all I E S*:
vat (1)
max Q (1,a)
(8)
nad VT HA (TT) -XS (TT) H (IT)
aEAll)
Then ß is optimal and we also have:
Moreover, the optimal T the DT of an optimal policy n², other words T T"
π (1) = Argmax , 2" (1,a)
(9)
5

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO
Note that Proposition 4.1 establishes that any optimal policy r E Argmax, 1 (Q) only has to satisfy the Bellman optimality equations (8) and (9) for a subset of few relevant states S* regardless of the remaining states of S. As such, it suffices to seek nr" as a partial policy defined on these states, without the need to define it elsewhere. This implies that an efficient search strategy should focus the search effort on the relevant part of the state space to find T* quickly, this is exactly the purpose of AO* and its advantage over Dynamic Programming (Hansen & Zilberstein, 2001, p.2, 11, 12).
Equation (14) is straightforward. Indeed, A (1) (m) 0 \
means that no split action can be taken at / because we have already exhausted them all, which happens when S (1) g. i.e. when 1 employs all the features in its splits. In this case, Equation (8) implies that V (7) = - (1, = H (t). On the other hand, when A (1)) {a} A 0. the following provides the intuitive reasoning behind the Purification Bound. We want to initialise an upper bound V (I) 2 V (1). Proposi- tion 3.2 states that V* (1) HA (TT) which is the objective of the best possible sub-DT rooted in l. Initially, the only information we have about / is H (1), which is the objective of the sub-DT {4}. Furthermore, we know that any other sub-DT T rooted in I employs at least one split and has an accuracy H (T) at most equal P (X) = 1] as shown below
To adopt an A approach, we need to define adequate heuristic estimates in the form of upper bounds V (l) and Q (1, a) on V (1) and Q* (l, a) respectively.
4.1. Heuristic estimates (1) and Q (L,
H (T) = (XT)))
= 1]
Let l E S \ 'T be a non-terminal state. For the terminal action a, according to definition (7), we have direct access to Q" (l,a) = r (1, = H (1) and thus we can define Q (1. σ) straightforwardly using Equation (3) as follows:
where equality only happens if all the branches in T are pure, i.e. each branch contains only one class. As a consequence, all sub-DTs T rooted in I, including Tj', satisfy:
2 (1, - ((, = H (1) (1)(1)) (L)
H₂ (T) < max (H),
(1), -À + P (1 (X) = }
(10)
n
We emphasize that we do not initialise V (1) for all tip nodes (nodes with no successors, also called leaves) of the AND/OR graph and then run the recursive updates (11) and (12) up the AND/OR graph. This would be a purely DP approach and it would indeed find T". However, such (11) an approach defies the purpose of focused search as it would require very expensive computational resources. We need a search strategy to carefully choose the branches to evaluate (12) in order to find 7* as quickly as possible. The next section is dedicated to describing this search strategy.
Remark:
Now consider a split action a E A \ { and let us define 2 (1, a) and V (I). The definition (7) and the Bellman
equation (8) suggest the following recursive definition:
@1,a)) -
Σ ((w)
LEF(LL.)
(1) max Q a))
A()(
We note that Q (1, a) in Equation (1I) can only be calcu- lated if the heuristic estimates V ((,) are available. Thus to complete this recursive definition, we need to initialise V (Iw) adequately.
Summary: For a non- non-terminal state E S T. (1, a) is known in advance and calculated with (10). For any split action a E A (1) \ {a), Q (1, a) is calculated with (11). V (l) are first initialised with (13) (for branches / that are specifically chosen by the search strategy) and later updated with (12).
Proposition& 4.2 (Purification Bound). Let l E S \ T, we define the Purification Bound as follows:
If (1) \ {क} + 0:
4.2. The Search strategy
V (1) = max (1), = 1}}
We initialise memo and search graph G' that consist (13) solely of the root Ω. Throughout the algorithm's 's execution, we label a node | (in G) as SOLVED when we know its optimal action T² (?) = 1rgmax.e.Ac0 Q" (1, a). in which case V (l) = V (() and Q" (I, (0) = Q (1, x (I)). Until
(1)01)) (1)
x n (1)
max
1
n
Otherwise:
(1) = (1) (1)
Ω is SOLVED perform the following steps at each iteration:
(14)
n2
Selection: Starting from the root = f2, until is leaf of G. descend G by following the selection policy:
The bounds V (1) are initialised with (13) or (14), then they are recursively backpropagated to the ancestors of I in the AND/OR graph through (11) and (12). The resulting heuris- tie estimates Q (1. a) and V (I) are upper bounds on the true optimal values Q* a1 and V* (I) respectively.
न (I) = Argmax A()) (l,
(15)
Store the connector (action) मे (l) in a list path. If all the states in F (1, मे (I)) are SOLVED, choose one of them arbi-
6

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO
trarily, stop the Selection step and move the Backpropa- gation step. Otherwise, choose UNSOLVED state from F (1, 5 (1)) and make it the current state I, Appendix B pro- vides the details of how we conduct this choice. Repeat the process until reaching a leaf 7. of G.
Table 1. Comparing orders of magnitude of the complexity hounds of BRANCHES and OSDT for binary features and for different values of À and q.
q= 10
q=
7= 20
A
BRANCHES
OSDT
BRANCHES
OSDT
BRANCHES
OSDYT
The purpose of this step is to grow G with the successor nodes of I and update V (1) and Q (1. a) for all actions a A (I). For the terminal action, calculate Q (1, a) = H (I) as per (10). Generate all the successor nodes of and add them to G' as follows: for all split ac- tions a E A (1) } and all successors lu E F (1, a), if Lu E memo add a link between 7 and L, as part of the con- nector a, otherwise create a node Lu in G and add it as a successor of 1 stemming from the connector a, store L, in memo, and initialise V (lw) with the Purification Bound in Proposition 4.2. If V (Iw)) = "e*())(w))) then label lu as SOLVED because we would know that ā is optimal at Lu as shown below:
Expansion:
0.1
104
101a
10
1016
10"
1015
0.0G
10a
10
107
104Th
10"
10
0.01
10a
10aM
10
INF
10
INF
where == min [LAxd 1.9)
To our knowledge, only (Hu et al., 2019, Theorem E.2) per- forms a similar analysis for OSDT. Due to the difficulty of comparing the two bounds analytically, we rather compare them numerically. Table 1 shows that our complexity bound is significantly smaller than the bound in (Hu et al., 2019, Theorem E.2) for different settings.
º aL, = 2 (lu, = (lw) = max
2 @1a,, a) aE,((.)
5. Experiments
2 max º" (la, a) .EA((..)
We employ 11 datasets from the UCI repository. For each dataset we use different types of encodings: suffix -o indi- cates ordinal encoding, suffix -f indicates binary (one-hot) encoding where the first category of each feature is dropped and no suffix designates a binary encoding retaining all categories. An additional binary encoding dropping the last category is considered in monk1-1, the reason being to showcase that different dropping options can lead to widely differing solutions. Moreover, our motivation behind drop- ping a category in the first place pertains to reducing the number of resulting binary features, this in turn can greatly simplify the task of finding an optimal sparse DT and help the algorithms be more scalable as we observe in Table 2. The downside however is that dropping a category can also yield more complex DT solutions than keeping all the cate- gories during one-hot encoding, We note that the algorithms we compare with exclusively consider binary features, thus necessitating a preliminary binary encoding. This seemingly benign detail can significantly harm performance by intro- ducing large amount of unnecessary splits as we explain in Appendix E. BRANCHES can sidestep this issue because it supports non-binary DTs on ordinal encodings of the data, these types of DT structures are commonly known under the name multi-way splits.
For all split actions a E (1) \ { calculate 2 (l, a) with (11), then deduce (1) with (12). Update the selection policy at with Equation (15). If all the successors in F (1, 7 (1)) are SOLVED then label I as SOLVED.
Backpropagation: Update the heuristic estimates upwards in G' through the list path of selected connectors, which we stored back in the Selection step. For j = -enggh(ppah))
1,...,0. O: T (1) path [j]. update Q (1, 7 (()) y (l) and a (I) with (11), (12) and (15) respectively. If 7 (1) = a or
all the successors in F' (1, ãे (1)) are SOLVED then label / as SOLVED.
We provide implementation details and a pseudocode in Appendix D and Algorithm 1. Theorem 4.3 proves the optimality of BRANCHES.
Theorem 4.3 (Optimality). Upon termination, the selection policy पे becomes optimal. In other words:
De (S2) = V* (9)) = max T (12)
x
To accurately assess the search efficiency of BRANCHES, we analyse in Theorem 4.4 the number of branch evaluations, i.c. calculations of H (l), it performs before terminating.
We set a time limit of minutes for all algorithms and we run all the experiments on a personal Machine (Processor: 2,6 GHz 6-Core Intel Core 17: Memory: 16 GB). More- over, since it is necessary to fix maximum depth for DFS methods, we set it to 20 for MurTree and STreeD while the BFS methods GOSDT and BRANCHES run with infinite maximum depth. The aim being to analyse performance at a large maximum depth in these experiments. The results are summarised in Table 2. For a detailed comparison across
Theorem 4.4 (Complexity). Let I' (g. C, A) denote the total number of branch evaluations performed by BRANCHES for a classification problem with a number of features q 2 2, a penalty parameter 0 < X < 1, and a number of categories per feature C $2 2. Then, I' (q, C, A) satisfies:
[g C, & Σ
(q - h) hh+1 9
h
h=0
7

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Table Comparing BRANCHES with the state of the art for a large maximum depth 20. BRANCHES is the only method that is applicable to ordinal encoding. hence why we put for the remaining methods. Furthermore, we ran into memory issues with MurTree that kill the kernel, these cases also we put For STreeD, when reaches timeout, does not propose solution due to its lack of anytime well. The APIs of STreeD and MurTree do not provide the number of iterations.
behaviour, we indicate those cases with
MurTree
STreeD
GOSDT
BRANCITES
Datasel
objective
objective
time (3)
objeetive
time (6)
Herations
objectivee
Lime (6)
iterationn
sphits
time
splits
splits
splits
monk1
0.940
6
0.940
3.28
0.940
3.05
801288
0.940
0.05
146
1-
0.930
7
0.03
0.930
2.80
0.930
7
0.87
29770
0.930
7
0.02
117
monkl.f
0.983
17
0.05
0.983
17
6.18
0.983
17
4.09
92782
0.983
17
0.39
2125
monk 1-o
0,900
10
0.02
64
monk2
0.967
1
33
0.55
TO
0.368
32
91.9
352759
0.968
32
11.2
60611
m-nk2-1
0.922
78
1.07
0.933
9.78
149912
0.933
67
2.94
28968
m
0.955
45
0.18
1213
monk3
0.978
1
25
0.04
0.985
15
7.87
0.985
1
15
25.2
185974
0.985
15
4.05
14807
monk3-f
0.975
1
25
0.04
0.983
17
4.82
0.983
17
2.00
50151
0.983
17
0.36
3026
monk3-o
0.987
13
0.03
156
DC-tac-toc
TO
0.757
0.792
70
22799999
0.838
0.928
70
390000
Lic-tac-toe-1
0.850
0,915
19
16.4
0.850
0.945
19
207
0.850
0.945
19
37.8
1670379
0.850
0,945
19
16.3
74027
lic-tar-
0.773
0.858
17
0.68
3339
car eval
0.852
0.927
15
154
TO
0.852
0.927
15
TO
5893650
0.852
0.927
15
204
456452
car-eval-f 0.799
0.869
14
TO
0.799
0.869
21.1
927221
0.799
0.869
14
26.6
108640
car-eval-o
0.812
0.882
14
0.09
579
nussery
TO
0.810
0,800
5
TO
2900499
0.812
0.872
6
TO
110000
aussery-1 0.772
0.812
7
151
TO
0.765
0.835
7
TO
6296999
0.772
0.842
7
24.9
18063
nunsery-o
0.822
0.892
7
0.24
195
mushruom
0.955
0.985
3
0.955
10.8
0.925
0.945
2
TO
79999
0.955
0.985
TO
21000
mushmoomff 0.945
0.985
143
0.945
0.985
126
0.925
0.945
2
TO
98080
0.945
0.985
TO
24000
mushroom-o
0.975
0,985
0.13
6
kr kp
7O
0.815
0.845
3
70
150009
0.900
0.940
4
T0
46000
200
0.989
1
11
0.04
0.992
184
0.992
8 87.3
401 770
0.992
8
44.6
39199
200-f
0,980
0.992
23.4
0.992
33.5
300357
0.992
8
2.09
4650
200-0
0.993
7
0.87
1456
lymph
TO
0.790
0.810
2
TO
639999
0.828
0.898
7
10
100000
lymph-1
TO
0.784
0.804
2
T0
1079999
0.811
0.891
8
10
170000
lymph-o
0.852
0.952
10
12.3
16154
balance
TO
0.712
0.737
70
1119909
0.776
0.806
70
640000
balance-f
TO
0.673
0.723
10
162
2202545
0.673
0.723
10
190
676149
balancc-o
0.713
0.763
10
0.004
178
a wide range of maximum depths, refer to Appendix H.4.
timeout. In Appendix H.4 we show that the main reason behind STreeD's success on mushroom is the depth 2 solver, a technique introduced by Demirović et al. (2022). On the other hand, despite reaching timeout, BRANCHES still proposes the true optimal sparse DT unlike GOSDT, thus showcasing the superiority of BRANCHES' anytime be- haviour. On the remaining datasets, STreeD'ss DFS strat- egy suffers from the large maximum depth while GOSDT and BRANCHES achieve optimality significantly faster even while running at an infinite maximum depth, this is espe- cially the case for BRANCHES because STreeD outperforms GOSDT on monk3, monk3-f, mushroom, mushroom-f and zoo-f, while it outperforms BRANCHES only mushroom and mushroom-f. Furthermore, STreeD''s lack of anytime behaviour prevents it from proposing a solution when it reaches timeout. This happens for monk2, monk2-f, tic-tac- toe, car-eval, car-eval-f, nursery, nursery-f, kr-vs-kp, lymph, lymph-f, balance and balance-f.
Table 4 summarises the characteristics of the datasets we consider.
For MurTree, the implementation we used from https: // github. com hwtp:/Mureereeeeeeeeeeeeee wtt.rrrreeepuuuttreeeeeee git displays suboptimal behaviour (in terms of H2) unlike STreeD, GOSDT and BRANCHES. This happens for monk2, monk2- f. monk3, monk3-f, car-eval-f, nursery-f, zoo and zoo-f as shown in Table 2. According to /tttttp::/bbtbuuckee org/Emi rD/ mu ree rre waarr//maaterr.. the authors of MurTree indicate the release of a newer and more general version of the algorithm referring to STreeD, For this reason, we will focus the remaining discussion on STreeD, GOSDT and BRANCHES.
Comparing STreeD with BRANCHES and GOSDT: STreeD is always optimal when it terminates similarly to GOSDT and BRANCHES. On mushroom and mushroom- it is clearly the superior method as it terminates in 10.8s and 126s respectively while both GOSDT and BRANCHES reach
The superiority of BRANCHES and GOSDT over STreeD these experiments is mainly due their BFS strategies,
8

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO
which tend to find the optimal solution quicker than DFS at the expense of more memory consumption. We note that while neither BRANCIES nor GOSDT ran out of memory these experiments, such an undesirable outcome can happen in some cases. To alleviate this problem, hybrid methods, using BFS until exhausting a memory budget then switching to DFS, can be employed (Pearl, 1984, Section 2.5). These extensions are outside the scope of our current work and we will consider them in future work.
6. Conclusion and Future Work
In this work, we have developed BRANCHES, a novel al- gorithm seeking optimal sparse DTs. BRANCHES lever- ages an AO* approach to solve the problem within an AND/OR graph search framework and employs custom heuristic called the Purification bound. We have shown that BRANCHES is optimal and satisfies better theoretical complexity guarantees than those derived in the literature. Furthermore, we illustrated through multiple experiments that BRANCHES outperforms the state of the art in terms of runtime, number of iterations and anytime behaviour. it es- pecially worth noting that BRANCHES outperforms its C++ competitors in runtime despite being currently implemented in Python, which indicates that future C++ implementa- tion of BRANCHES promises to widen the performance gap further with the other methods.
Comparing BRANCHES with GOSDT: BRANCHES out- performs GOSDT on all the experiments except car-eval-f and balance-f where GOSDT terminates faster. Sometimes the difference in speed is so significant that BRANCHES ter- minates while GOSDT reaches timeout and as a conse- quence fails to produce the optimal solution. This happens in car-eval and nursery-f. Moreover, whenever both algo- rithms reach timcout, BRANCHES proposes better solution than GOSDT's, s. hence displaying better anytime behaviour. To see this, refer to tic-tac-toe, nursery, mushroom, kr-vs-kp, kp, lymph, fymph-f and balance. Another important point is that the experiments on ordinal encoded datasets terminate sig- nificantly faster than their binary encoded counterparts. In- deed, experiment with ordinal encoding reaches timeout, and the slowest one is lymph-o with 12.3s. In Appendix E we discuss the reasons behind this phenomenon. Further- more. on many occasions, the non-binary optimal sparse DT's obtained with ordinal encoding are of better quality (in terms of H2) than those obtained through a preliminary binary encoding. This happens for monk3-o, nursery-o, mushroom-o, z00-o and lymph-o, but this is not the case for the remaining datasets. In fact, we shall see in Appendix E that the obtained non-binary sparse DTs can themselves be collapsed into sparser solutions with fewer splits. Knowing that scalability is a major issue in the literature of optimal sparse DTs, the ability to support non-binar DTs is very helpful in this regard. BRANCHES being the only method that displays this property has a clear advantage from a scalability standpoint.
There are several ideas to extend this work in the future. straightforward one is implement BRANCHES in C++ and incorporate
follows: During the Selec- tion step, whenever we take a split action, we could choose subset of the children branches and keep running Selection from each one of them in parallel. As a consequence, the Selection step would return a subset of branches, for which we run Expansion in parallel then Backpropagation in a syn- chronous parallel fashion. This would yield a notably better pruning of the search graph and as result significantly faster optimal convergence. Another promising idea is to incorporate the depth-2 solver (Demirović et al., 2022), we saw in Appendix H.4 how it is crucial to STreeD's 's perfor- mance. Moreover, to alleviate high memory consumption issues we could design a hybrid strategy between BFS and DFS as described in (Pearl, 1984, Section 2.5). Lastly, we could improve the Purification Bound by using strong aux- iliary classifier f such as Multi-Layer Perceptron. Given branch / for which we want to initialise the heuristic V (!), if we can derive the number m of employed variables by f in then we can tighten the Purification Bound with:
Additional experiments are provided in Appendix H:
V (1) max {1(()) mm mx
Appendix H.1 compares BRANCHES with Python im- plemented algorithms OSDT and PYGOSDT.
Acknowledgements
Appendix H.2 compares BRANCHES, CART and DL8.5 in terms of their Pareto fronts with respect to the joint optimisation of accuracy and number of splits.
We would like to thank Mathijs M. de Weerdt and Pierre Schaus for their helpful discussions, and the anonymous reviewers for their valuable feedback.
Appendix H.3 investigates the suboptimality of DL8.5 with respect to the joint optimisation of accuracy and number of splits.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Appendix H.4 extends the comparison between BRANCHES, GOSDT and STreeD to a wide range of values for the maximum depth.

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
References
Hansen, E. A. and Zilberstein, S. LAO*; A heuristic search
algorithm that finds solutions with loops. Artificial
Aglin, G., Nijssen, S., and Schaus, P. Learning optimal decision trees using caching wranch-and-boue search. Proceedings of the AAAI Conference on Artificial Intel- ligence, 34004)3116-31153 Apr. 2020. doi: 10.1609/ v3a..13400. URL https: http://osssaaaaaoooooaaaaaaa.aaa index. paceex.pp///eee
Intelligence, 129(1):35-22, 2001. ISSN 0004-3702 doi:
URL.
Hu, H.,, Siala, M., Hebrard, E., and Huguet, M.-J. Learning optimal decision trees with maxsat and its integration in adaboost. In IJCAI-PRICAI 2020, 29th International Joint Conference Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelli- gence, 2020.
Bellman, R. and Dreyfus, S. E. Applied dynamic program- ming, volume 2050. Princeton university press, 2015.
Bennett, K. P. Decision tree construction via linear program- ming. Technical report, University of Wisconsin-Madison Department of Computer Sciences, 1992.
Hu, X., Rudin, C., and Seltzer, M. Optimal sparse decision trees. In Wallach, H., Larochelle, H., Beygelz- imer, A., d'Alché-Bus F., Fox, E.,, and Garnett, R. (eds.), Advances in Neural Information Process- ing Systems, volume 32. Curran Associates, Inc.. 2019. URL https: nee.eeeeeednnnnnnnnne........ cc cc/ hc//ppper_flllee/pppe/////////1
Bennett, K. P. Global tree optimization: A non-greedy decision tree algorithm. Computing Science and Statistics, pp. 156-156, 1994.
Bennett, K. P. and Blue, J. A. Optimal decision trees. Rens- selaer Polytechnic Institute Math Report, 214(24):128, 1996.
Bertsimas, D. and Dunn, J. Optimal classification trees. Machine Learning, 106: 1039-10028 2017.
pdf.
Hyafil, L. and Rivest, R. I.. Constructing optimal binary decision trees is np-complete. Information Processing Letters, 5(1):15-17, 1976. ISSN 0020-0190. doi: https://c..oo////../.f0000000000 URL httpss:/www.scieeneddieetttt cccinee/Arriaae//////22000000000
Bessiere, C., Hebrard, E., and O' Sullivan, B. Minimising decision tree size as combinatorial optimisation. In Gent, P. (ed.), Principles and Practice of Constraint Program- ming- CP 2009, pp. 173-187, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-04244-7.
Blanquero, R., Carrizosa, E.,, Molero-Río C., and Morales, D. R. Optimal randomized classification trees. Computers & Operations Research, 132: 105281, 2021.
Lawler, E. L. and Wood, E. Branch-and-bound methods: A survey. Operations research, 14(4):699-719, 1966.
Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Generalized and scalable optimal sparse deci- sion trees. In III, H. D. and Singh, A. (eds.), Pro- ceedings of the 37th International Conference on Ma- chine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6150-616 6160. PMLR, 13-18 18 Jul 2020. Utthttps: / /ttpc//coeeeeeeeeeeoooooooooccee ngs. ml press/ v119/1in200 html.
Breiman, L., Friedman, J., Stone, C. J., and Olshen, R. A. Classification and regression trees. CRC press, 1984.
Chaouki, A., Read, J., and Bifet, A. Online learning of decision trees with Thompson sampling. In Dasgupta, S., Mandt, S., and Li. Y. (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 2944-2952, PMLR, 02-04 May 2024. URL URLhttps: httptttsss/pppoeeeeeettot http://proeeeeecceeee// mlr press// v238 2238/chaouuee htt//hhaoki224.htmm
Lomax, S. and Vadera, S. A survey of cost-sensitive de- cision tree induction algorithms. ACM Comput. Surv., 45(2), March 2013. ISSN 0360-0300, doi: 10.1145/ 2431211 URL https://doi. org/10. 1145/2432211.449222
Demirović, Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., and Stuckey, P. Optimal decision trees via dynamic program- ming and search. Journal of Machine Learning Re- search, 23(26):1-47, 2022. URLhttp:: 520. html.
Murtree:
Martelli, A. and Montanari, U. Optimizing decision trees through heuristically guided search. Communications of the ACM, 21(12): 1025-1039, 1978.
McTavish, H., Zhong, C., Achermann, R., Karimalis, I., Chen, J., Rudin, C., and Seltzer, M. Fast sparse deci- sion tree optimization via reference ensembles. Pro- ceedings of the AAAI Conference on Artificial Intel- ligence, 36(9):6604-96) 9613, Jun. 2022. doi: 10.1609/
Günlük, O., Kalagnanam, J., Li, M., Menickelly, M., and Scheinberg, K. Optimal decision trees for categorical data via integer programming. Journal of global optimization, 81:233 260, 2021.
10

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
aaai.v36i..21194. URL https:///ojs wwwp://saaaa.ooooo..oo......oo.o org/ index. phceeexppppp// /ttp://AA///atttlleeeeee////1111
33001):662516322.1u 2019, doi: 10.160%aaii.v3333
3301 URL ht..ss:t: /tttttps://jjsaaaee waeeei.orgg/ai index.
phop/AAAt/arrriccle//ee////9
Montanari, U. et al. From dynamic programming to search algorithms with functional costs. 1975.
Narodytska, N., Ignatiev, A., Pereira, F., Marques-Silva. J., and Ras, I. Learning optimal decision trees with sat. In IJCAI, pp. 1362-1368, 2018.
Nijssen, S. and Fromont, E. Mining optimal decision trees from itemset lattices. In Proceedings the 13th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, KDD '07, pp- 530-539, New York, NY, USA, 2007. Association for Comput- ing Machinery. ISBN 9781595936097. 1145/1281192.12822550, URL petps:://oi... 10. 19..1145/12811922 128111.1.....1..
doi: 10.
Nijssen, S. and Fromont, Optimal constraint- de- cision tree induction from itemset lattices. Data Mining and Knowledge Discovery, 21:9-51, 2010.
Nilsson, J. Principles of artificial intelligence. Morgan Kaufmann, 2014.
Norouzi, M., Collins, M., Johnson, M. A., Fleet, D. J., and Kohli, P. Efficient non-greedy optimization of decision trees. In Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https://proceedingg neurips.... wttppppeeeiiilsspppeeee/////////
1559779999cce9ccc888886666363363 2tw.eeffd2cdddddp-ppeeee-- pdf.
Pearl, J. Hearisties: intelligent search strategies for com- puter problem solving. Addison-Wesley Longman Pub- lishing Co., Inc., 1984.
Quinlan, J. C4. 5: programs for machine learning. Elsevier, 2014.
van der Linden, J., de Weerdt, M., and Demirovié, E. Nec- essary and sufficient conditions for optimal decision trees using dynamic programming. Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances Neural Information Processing Sys- tems, volume 36, pp. 9173-9212. Curran Associates, Inc., 2023.
Verhaeghe, H., Nijssen, S., Pesant, G., Quimper, C.-G., and Schaus, P. Learning optimal decision trees using constraint programming. Constraints, 25:226-250. 2020.
Verwer, S. and Zhang, Y. Learning optimal classification trees using a binary linear program formulation. Proceed- ings of the AAAI Conference on Artificial Intelligence,

---

V" Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
A. Notation
Table 3. Table of Notation
X (x()) X X ) datum.
X
{1 .l..... Ci), feature.
Y E
(1...., KJ a class,
D
{(Xmr km))m=) dataset of examples.
1
(0( I ( = ju branch. Also, a non-terminal state.
S(1)
The size of branch I, the number of splits in I, the number of clauses in I. Valuation of / for input X. When / (X) 1, we say that X is in I. The root. Branch that valuates to for all possible inputs. Children of / when splitting it with respect feature i. Ul,.... Jc l
(X)
Ω
Ch (1,
Ch ((,
(+) =
n (1)
2==1" I (Xm) Number of examples in 1.
ni (1)
Em=i 1m=1 ( (Xmm) 1fYm = k} Number of examples in of class k.
k- (I)
Argmax (ng (2)}. majority class /
H (1)
P ( k- (1)) probability that an example in and is
correctly classified.
sub-DT rooted /
Collection of branches tha stem from a series of splits from
DT
A sub-DT rooted in the root Q.
(X)
Predicted class of X by T'. Majority class of the branch containing X. P (X) = Y1, accuracy of DT
H (T)
Hy (7)
(X) = YJ AS (7), the objective evaluating T.
(T)
Number splits to construct T from the branch where it is rooted.
Jo, 1], penalty parameter.
T
Argmaxy (T)} optimal DT.
Terminal action. Terminal state that stems from taking in I.
1
V"
(1)
Value of policy π starting at non-terminal state
Q"
(T,
a)
State-action value of policy π at non-terminal state and action a.
27
Sub-DT of π rooted in I. See Proposition 3.1.
77"
Minimum time for policy to get to 77.
T5
x²
E
Argmax, Vat (I),, an optimal policy.
T
T
V"
Q"
Q"'
7?²
(1)
Heuristic estimate of 1* (!).
(1,a)
Heuristic estimate of Q* (l,
Selection policy से (1) Argmax (l,a).
B. Choosing an UNSOLVED branch during Selection
Regarding the choice of UNSOLVED branch introduced in the Selection process in Section 4.2, choose branch of lowest HA where T; is the best sub-DT rooted in found so far in terms of the objective HA. The reason is to quickly
prune branches that contribute low Hd T to the solution. Indeed, this approach either yields better subtrees rooted in these branches, or bad subtrees that indicate this region to be unpromising, hence incentivizing the algorithm to search elsewhere. This selection approach likely induce good anytime behaviour, We note that similar idea was proposed
12

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
in (Nilsson, 2014, p.107):
Possibly the expansion of that leaf node having the highest h value would most likely result in changed estimate.
The h value in (Nilsson, 2014, p.107) refers to the heuristic value, which is akin to our V value albeit for minimisation context instead of maximisation one. As such, a direct application of (Nilsson, 2014, p.107) to our setting would yield choosing the UNSOLVED branch I with lowest V (l). We noticed practice that employing Hy (īi instead yields better anytime behaviour for the reasons explained above. Currently, have not investigated other strategies of this type, and it is promising idea for future work.
C. Anytime behaviour
There are settings where the search takes a substantial or even unfeasible amount of time to terminate. In these situations, we set a time limit on BRANCHES' execution and even if it does not terminate within this time, we expect it to still return a good solution. This property called the anytime behaviour. For BFS methods, it straightforward to implement while is less trivial for DFS algorithms. STreeD for example, does not enjoy the anytime property.
We formulate BRANCHES' anytime behaviour as follows. For each branch / that is currently in the memo, we define its greedy value (1) recursively as:
(1) (1) H (1) i is tip node (leaf) of the current search graph G.
(16)
A(MMa) (T) - Erecuu..) 1 ((')
Basically 9 (1) is the best value of the regularised objective found so far for all sub-DTs rooted in I. Based on this definition, also introduce the greedy state-action values and the greedy policy:
(1) ifa=
(1.0)= = - Σ (cn((..) (1)) if A() (α)
* (1) Argmax @ (1,a)
The estimates 1 (1) and @ (1, a) are updated in similar fashion to V (z) and Q a) during the Backpropagation step, i.e. via (12) and (11). When BRANCHES reaches timeout we unroll from to get In the best DT found so far in terms of the objective H2. T is the proposed solution by BRANCHES when runs out of time.
Unfortunately, unlike settings where BRANCHES terminates, the anytime behaviour does provide any theoretical guarantees with respect to the quality of the proposed solution. Such guarantees necessitate the assumption of some smoothness properties of HA on the state space S. Nevertheless, the use of selection strategies such the one we propose in Appendix B can lead to empirically satisfying results for BRANCHES' anytime behaviour.
D. Implementation Details
The search strategy we introduced in Section 4.2 an abstract description of BRANCHES. In this section, we provide concrete elements for the implementation of the algorithm, along with micro-optimisation techniques that substantially improve its computational efficiency.
D.1. Branch objects
For each branch = A (f.) = jul, we define an object with the following elements:
.d_anchhh: is identified with the unique string " "(11,11(i1,, ... (is()) ist))". We recall that this string is unique because we impose the condition < iz < ... < (s())- We store each encountered branch in memo dictionary using its identifier.
attributes Saw.uttees_ctegriiesseeee Dictionary containing the number of categories per unused feature in L. We recall that the set of unused features the set of split actions.
13

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
bit_vector: Vector of the indices of the data contained in l. This vector allows quick access to the data in I.
Dictionary containing the children of I, i.e. the set Ch (1, for each unused feature Initialised with an empty dictionary.
children:
The greedy action (1) as per the definition in Appendix C. If a then we set attribute_opt to None.
attribute_opt
terminal: Boolean describing whether / is terminal or not.
complete: Boolean describing whether is SOLVED not.
va value: The estimated value (1).
Sallue_terminal The value of the terminal action at L.
7ke (1) (1)
2 (1.ā)= - o- (L, - ())
value_greedyy The greedy value D (t) as per the definition in Appendix C.
freq: Proportion examples in l:
fr()=P[((X) =1] -|= (l) Σ (Xm)
m=1
pred: Majority class at I:
pred = k- (1) Argmax (1)
queue: Heap queue containing (-value, @walue_compleee attribute, children) tuples. For each
unused feature (split action) attribute: value estimate:
value = 2 a(I.attrib = -A
Σ
((')
vec(laattribute
On the other hand, Ch (1, (ttrrbuute)) that are SOLVED. By definition, the SOLVED children 1' satisfy V (Z' = V" (?), we store the sum of their values in value_come gallu__cmplete, which serves efficiently update Q (l,ttriibute) during the Backpropagation step. chi liieedeen is dictionary containing the UNSOLVED children, it from this dictionary that choose the next branch to visit during the Selection step. During Backpropagation, If an UNSOLVED branch l' in chi 1 Idren becomes SOLVED, it is discarded from children. We note that these tuples are stored in queue, thus the first element of queue is always the tuple with the highest value, i.e. queue [0] [2] is the split action maximising (1, a). This is the reason we store -value the tuple, Python implements min heaps instead of max heaps. We do not need to sort actions by their values, but rather to just keep track the action with the highest value. As result, becomes SOLVED if and only if one of the following holds:
is the sum the estimated values V (1') of the children
The terminal action is the current best action:
Q (L, Argmax (1.a)
which happens if:
-queue [0] [0] vaauueteemiiee
- The dictionary of UNSOLVED children that result from taking the current best split action / queue [0] [3] empty.
14

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
There is an additional benefit storing -value_cooo tralue_complete ete. When there are multiple split actions att rubte that maximise va ue, then we prioritise the one maximising palue_comp) ete. This further serves heuris- tic allowed by the flexibility of BRANCHES' selection step compared to GOSDT's. To see the benefit of this scheme, consider such situation and suppose that one of these split actions, attribue, maximising the esti- mate such that Ch (1,,ttriibutee are all SOLVED. Ideally we want to prioritise this action, i.e. we want queue [0] [2] attribute. The reason behind this that it allows us to immediately conclude that is SOLVED and that attribute = A
O- (l,a). This is exactly what happens by using a priority based on complete well. Indeed, if Ch (1, attribute) are all SOLVED, then by definition sttribute maximises value value_compllleeeeeeeeeeeeeeeooe cowpletoeeeeeeeeeeeeoce among all the split actions maximising value.
D.2. The Algorithm
In this section, we go over BRANCHES' search strategy, introduced in Section 4.2, and outline it from implementation perspective. We initialise the root ? then apply the search steps each iteration as follows:
Selection: Initialise the current branch = and the path list to path [1]. While is UNSOLVED and l.chiddren is not empty, i.e. I has been expanded. Consider the tuple:
(-value, -va lue ce__compeete, attribute, children) [[qquee[[]]
As have seen in Appendix D.I, attribute is the optimal split action with respect to the current estimates Q (1, a) and chi ldren is the subset of UNSOLVED children in Ch (1, attribute). Therefore, we choose the next branch from the dictionary ch i ldren. As explained in Appendix B, here choosing the UNSOLVED child of lowest value_greeseeee is our practical choice. Append / to path.
Expansion: Let be the Selected branch. If Icomplete, we go to the Backpropagation step. Otherwise, for each (unused) feature-category pair (i,j) E lattri but butes_categon satss__ctegriiiee let l.j = 1 ( j} be the child branch of I that corresponds to feature taking the value j. Our objective is calculate (44)). We first check whether 4g (gy.id_brann in the memo, if it is, then can directly access V (4zj)- Otherwise, initialise V (lyy) according to Proposition 4.2. To do this efficiently, consider fixed feature and let us go over its categories E (1.....C, C,) one by one. For 41, we first extract the data in using [bi t_ vector:
Dj (Xm E D (Xmm) = 1] = D ([.bit_vector
Since 4n (X)= =1 = ((X) 1, we extract the data in 4, directly from the smaller set Dj instead of D:
Dr, = {Xm e D: 41 (Xm) = 1} [Xm E Dj 41 (Xm)) =
The indices of the data Di, form the vector 4n .ii t_vector. Now we can initialise (I.1) with Proposition 4.2 using Dia For 42, if i is not in the memo, then initialise (42), instead of extracting Dr,, from D) via:
Dia = (Xm E Di 122 (Xm) 1}
We rather use the fact that 41 and 42 are mutually exclusive, in the sense that:
VX E & 42 (X) =
4n (X) =0
Which means that we can extract Di.,, from the smaller set D; Dia instead of Dj and then initialise V (42). We repeat this process for all categories j E (1.....c) and then we do the same thing for the remaining unused features in cnttrributee_categrrit
These micro-optimisationn we perform allow for a substantial computational gain.
Backpropagation: For j length (path) 1,..., let parent path [j-1] and child pathli], then pop the heap queue parent. queue:
I-value, -val -value_complete, attribute, children: = parent queue poupue.poppl ()
During the Selection step, attribute was the action taken at the branch parent to transition to the branch chi dd. Now during Backpropagation, we need to update the estimates (paarent, attribute) and (parent)), hence why
15

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
pop the corresponding tuple from parent eevent-queee queue, and we update its values, we will push the tuple back in the heap queue. If chilc 1d. complete then we add its value va lue_complete:
value_complete value_complets + child.valus
and we pop child 1d from the dictionary of UNSOLVED children children. poop (child). Now push the tuple back
in parent queue, this rearranges the tuples is such a way that the most promising one (with maximum va l ue) is at parent. queue [0], The next step is to check:
(-valve, -value_complee ete, attribute, children) = parpet..uueeeee [0]
attribuute the same attribute we have just treated with the last tuple, then we stop the update of parent queue. Otherwise, we pop the queue again and we update this tuple in similar fashion to what we did with the previous tuple. The reason we check this is that an update could already be made here because the UNSOLVED children in dictionary children might have been updated during other iterations of BRANCHES. We continue this process until get an attribute that has already been treated in this process, in which case there is no need for further updates. Now parent. queue [O] is the tuple corresponding to the best split action:
(-valve, -value_completee attribute, children) = parent.queut [0]
Therefore, the value of parent is equal to the maximum between the value of taking this best split action and the value of taking the terminal action:
V (parent)) max voxxf((parente a), ((parent
Which, in our implementation translates
parent.valus +- max parent.. www.pat..aaleeterrriiiieio waw.oeeeeemmiinnlllllll...
Moreover, if V (parent) = Q (parent,.a, then ) (parent,, a), and since we know that @ (parent, a) = Q (parent, a) (according to Equation (10)), then we deduce that parent is SOLVED and V (parent) = º* (parent, a). Therefore we update:
parent... compntte + True
This not the only condition that makes parent SOLVED. Indeed, parent can also be SOLVED Ch (parent, attribute) are all SOLVED, which happens when the dictionary ch ddren is empty.
16

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Algorithm BRANCHES
1: Input: Dataset = {(Xms Ym) mm)mm= penalty parameter 2 0.
2: memo 6 0
D Initialise an empty memo
3: [NITIALISE((22 D)
4: while not S.complete do
While the root 92 is SOLVED
5:
(1, path SELECT()
6:
if Lcomplete then
If / is SOLVED
7:
BACKPROPAGATT(path))
8: else
9:
EXPAND(I,
BACKPROPAGATT((patl)
end if
12: end while
13: return INFER()
14: procedure SELECT(
15:
1
16: path f- [4]
17: while Lexxanded and (not .complete) do
(I, (etuu)) return_complen i, children
children.incmplltt. incomplete) Lqquue (0]
+ children incomplete [0]
20:
path.append (l)
21: end while
22: return (1, path)
23: end procedure
24: procedure EXPAND(I, D)
lexpanded True for i E A (1) \ [T)] do
26:
27:
SPLIT(L, i, D)
28:
(I) + max (0,1,),,qquen [0] [0]}
This update comes from Equation (12)
29:
end for
30:
if V (1) = (1, a) then
this case V (1) = Q" (1. (1)
31:
..omplete + True
)" (I) is known
32:
Lterminal <- True
D Label terminal if the optimal action is (1)
end if
34: end procedure
17

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
35:
procedure BACKPROPAGATT((pat))
36:
N < length (path)
for
2 do
38:
+ path [t]
39:
(1, oeeernoooonpteee..lleeeoooooooe.
i, children.incomppeete
Lqueue.pop
40:
Q (1) <- return complete
> Initialise Q (1, i)
41:
for E children ceaadren_incopplee do
42:
2 (1. + ( + V (t')
43:
if .compllee then children children chcomplett..dscarr (?')
D. Check if is SOLVED now Delete I' from children incommplet
45:
end if end for Lqueue.push ((Q (1, return_complete, i, wwwlcchhniincooee )nnddreeiincomlleee))
46:
47:
48:
, return i", chwldhennineeee inn.impeeenmmmlte) <- l.queue [0) [0]
49:
(I) + 2 (1,
50:
( (1) = 2 (1. a)) or incooplee is empty) then
Lcomplete True
52:
Lterminal True
D Label terminal if the optimal action at / is x² (1)
53:
end if
54: end for
55: end procedure
56: procedure INFER()
57:
T ++1
58:
Q < queue ()
Q-put (22)
60:
while Q is not empty do
61:
1 + Q.pop
62:
if lttemmnnal then
63:
T Taappend (()
64:
else
(2 (1, return_completer
children,.ncomplette [qqeee(0)
for l' E L.children [i] do
67:
Q-put (!')
68:
end for
69:
end if
70:
end while
71: return
72:
end procedure
18

---

end if Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
73:
procedure INITIALISE(I, D) Lexpanded <- False
74:
D. Label as not expanded yet b Initialise the dictionary of children Initialise the priority queue of I H. (1) is calculated with D
75:
Lchildren + dict ()
76:
Lqueue queue (I)
77:
(l,āā - 7 (1)
78:
if A (1) {a} then
79:
/tterminal + True .complete t- True (1) + 2 (l
> Label I as terminal if it cannot be split
80:
> I is SOLVED, V (1) is known > this case V (1) = 2 (1, a) = (1)
81:
82:
else
83:
/.erminal <- Folse
84:
Initialise V (1) according Equation (12) and Equation (11)
85:
if V (1) = = (1, α) then
86:
Lcomplete + True
> V (1) is known, V (1) O (1, = (1)
87:
Lteeminal t- True
D Label terminal if the optimal action at / is x (1) =
88:
else
Lcomplete + False
V* (1) is still unknown
90: end if
91: end if
92:
memo.add())
Add the initialised branch to the memo
93: end procedure
94: procedure SPLIT(I, i, D)
95:
Lchildren(1] +
> Initialise the list of children that stem taking split action i in I > Initialise the Upper Bound Q (1, b Initialise the return due to SOLVED children Initialise the list of UNSOLVED children
96:
(1, -ー
return complete + -X children children.incomplee incomplete <- []
98:
99:
for j E (I...., C.) do
100:
1ij < -AT j}
101:
if by & memo then INITIALISE(1s5, D)
> Only initialise the branches that are not in the memo
102:
103:
end if
104:
Lchildrenli).appenn (4,z) (1, + 2 (1, + V (4g) if ly. complete then
105:
Update the Upper Bound Q (1,
106:
107:
return_complet t- return_complete + V (44))
108:
else
109:
children incomplete.append (1:z)
110:
111:
end for
112:
Lqueue.push
113:
end procedure
E. Drawbacks of Binary Encoding
In Table 2, we have shown that optimal sparse DTs are always found significantly faster in the context of ordinal encoding compared to binary encoding. In this section, investigate the reason behind this phenomenon.
To answer this question, let us consider the following simple binary classification problem. Suppose there is only one feature (1) with 4 categories, i.c. the feature space is X = {1, 3, 4} and that class Y satisfies Y = 1 if and only if (1) = 1 or (I) = 3. The optimal sparse DT in this case consists of only one split splitting the root with respect to feature x(), as shown in Figure 3. In this setting, BRANCHES only needs one iteration to terminate. Indeed, on its first iteration, expands 2, estimates Q (2, a) and Q (22, a) where is the split action with respect to X(1) In this case, BRANCHES can already
19

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
x
x =
x
x
Y-1
Y-0
Y-1
Y-0
Figure Optimal DT depicting the class variable that satisfies Y 1 and only x
X the space X (1,2,3,4)
X 0
x 1
Y=1
x
x =1
Y=0
Y=1
Figure 4. The new optimal sparse DT on the new feature space X'.
deduce that:
= (Q())) 11
(0) YJ 2" (9,a)
and therefore that Ω is SOLVED and Ar) Q" (2,a').
Consider now the binary encoding of feature space X', this yields new feature space X' = (0. (0, x0.1) (0.
where the new features ( (2) x x144 describe the existence of category or its absence:
Vi (1,2,3,4) x = I(x(1= =
Figure depicts the new optimal sparse DT on X', In this setting, BRANCHES can no longer achieve optimality from the first iteration, because the first iteration only explores branches of size and the optimal solution includes also branches of sizes 2. Moreover, Binary encoding introduces unnecessary branches that make the search space larger than necessary, thereby wasting some of the search time. To see this, consider the branch:
= =xx(0)) = 1} (( = =1
This branch exists in the new search space (search graph) constructed on X' and it could be explored at some point by the search algorithm. However, this would a waste of time because does not describe a possible subset of X. Indeed, translating l' to its corresponding branch on X yields:
1(x(1 =1 ( 2]
20

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Number categories per feature
15
5
10
15
20
25
30
Number
1b5
260
124
350
Log(Number unnecessary branches)
Figure 5. The number of unnecessary branches introduced Binary Encoding.
which always valuates to 0 for any datum X E X. As consequence, I can never be part of the optimal solution, in fact, it can never be part of any Decision Tree X, | is not even a proper branch by virtue of the definition in Section 3.1 as it violates condition (1). While it is true that the algorithm will prune this branch because its support set { E DD (XX) = 1} is null, it still has to waste time calculating this support set. To properly evaluate the computational inefficiency induced by binary encoding, we analyse the number of these introduced unnecessary branches. Theorem E. provides this analysis for the case where all features have an equal number categories.
Theorem F.1. Consider a classification problem where all features share the same number of categories C, i.e.
{L...., C}S the feature space. Performing binary encoding X yields the new feature space X' {0, 1) 1] We define unnecessary branch I on X' branch that valuates for any input vector X E X:
4X E X : (X) =
The number of unnecessary branches introduced by binary encoding is:
() (( = 11
B
Proof. The proof of this Theorem proceeds by counting the total number of branches possible X" and subtracting the total number of branches that are not unnecessary.
Let us start with the total number of branches on X" Any branch on X' has the form:
A ==1
X (1)) 201
Where (t)) are the features the space X',
E s1....,9C,,2, [0.1). We note that 0
corresponds to / Ω by definition.
There are qC possibilities for choosing
For each possible value w, there are (vC) possible combinations {ir,... fi,....,
For each combination fii,..., ). there are 2d possible assignments (21,..., 2w
Therefore the total number of branches on 2" is:
(qC) w
A
Σ
2
390
(17)
w=0
21

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
X 17=0 x 17=1 x 17=2
x
17=3
X_17=l x 17=5
x
17=6
X_17=7 1_17
X
Y=0
Y=1
Y=1
Y=0
Y=1
Y=0
Y=1
Y=1
Y=l
Figure 6. Optimal sparse DT for mushroom-o.
X (03.5)
Y=0
Y=1
Figure 7. Collapsed optimal sparse DT for mushroom-o.
Let us now count the number of non-unnecessary branches, To do this, we consider slightly different notation of the features on X²
T( = A branch 1 A== I(X 2o} is not unnecessary if and only if E 10.....94.h. E (I,....q),I {l...., C} 2e E 10,1].
Vi E (I,..., Vj (I....,C) C}: X
For each possible value w E {0....,g) .). there are (:) possible combinations fi1....,bul b-
For each combination (i1,..., ) there are C possible assignments Jww)
For each assignment (J,,....iw) there are 2 possible assignments (21,..., 2.
The total number of branches that not unnecessary is therefore:
g Σ
B C)
q W
2T (2C 1]7
2nh 2 C
(18)
From Equation (17) and Equation (18) we deduce that the total number of unnecessary branches is:
u A C) (g. - - -12C + 1
There a subtlety here. We define on X', which means that it involves clauses defined with the features of X", and yet the definition in Theorem E.1 pertains to valuating on inputs from the feature space X. There is no mistake or lack rigour in this definition, we are allowed to do this because Binary Encoding an injective map from X' X", thus implicitly, valuating 1 input X E X' is defined valuating the image of X in 2' with this map.
Figure 5 is a contour plot of the number of unnecessary branches as a function of and C' in Logarithmic scale. It shows how immense this number becomes as 9 and C' increase. We should note that, not all of these unnecessary branches will be explored by BRANCHES, in fact many of them (depending on the problem) will be pruned pre-emptively. Nevertheless, many will inevitably be visited, which hinders the search efficiency as we clearly demonstrated in Table 2. This inefficiency most apparent on the mushroom dataset, where GOSDT and BRANCHES reach timeout on the binary encoding. However, contrast, when applied to the ordinal encoding of mushroom, BRANCHES achieves an extremely fast optimal convergence in only 0.16s and 6 iterations. Moreover, in the mushroom dataset case, the optimal sparse DT only involves one split as depicted in Figure 6. This solution can further be collapsed into single split DT with only two leaves as shown in Figure 7, which is highly interpretable solution. On the other hand, binary encoding does not allow for such flexibility and its solution, depicted in Figure 8, is clearly less interpretable than the one in Figure 7.
When using binary encoding, it is usually good idea to drop one category per feature. The reason pertains to reducing the number of the resulting binary features, which turn makes it easier for the algorithm to quickly find the optimal
22

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
K_86==0
X 86=1
X_89=
X_89=1
Y=0
X_91=0
91=1=1
Y=0
Y=l
Y=O
Figure 8. Optimal sparse DT for mushroom.
1=
X E=
X 7=0
K_10=0
10=1
X 9=1
X-800
8-
X X-8=1
Y=0
Y=l
X
9=1
Y=0
Y=0
Y=l
Y=l
Y=0
Figure 9. Optimal sparse DT for monk 1-1, it has splits.
sparse DT. Notice in Table 2 the difference in execution times between dropping and dropping a category. In some cases like tic-tac-toc/tic-tactto--- nursery/nursery-f and balance/balance-f, just dropping the first category pushes BRANCHES to terminate in time while it reaches timeout otherwise. However, choosing the adequate category to drop is not trivial and can lead to widely varying solutions and difficulties. We illustrate this point with monk1-1 and monk I-f. Figure 9 and Figure 10 show very different optimal sparse DT's, with the option of dropping the last category leading to a solution with only 7 splits while dropping the first category induces a solution with 17 splits. Obviously in this case we prefer dropping the last category, but there no trivial way of knowing this beforehand. On the other hand, employing direct ordinal encoding yields the optimal solution in Figure 11 with 10 splits. By noticing sibling branches that share the same sub-DTss rooted in them, this solution encoding allowed us to achieve a solution of similar quality to the one induced by monk 1-1 without the need to guess an adequate category to drop.
be collapsed into the DT in Figure 12 reducing its number of splits 7. In this case, ordinal
To conclude, we demonstrated in this section the reason why finding an optimal sparse DT significantly faster via ordinal encoding than binary encoding. This discrepancy stems from the large amount unnecessary branches that binary encoding introduces, as explained in Theorem E. Furthermore, we showed that these faster to get solutions can be even more desirable from an interpretability standpoint, we showcased this for the mushroom dataset. Using the monkl dataset example. explained the notion of collapsing the non- bonabr DT solution yield better interpretable alternatives. This notion of collapse should be further investigated in the future. It could be of great use from scalability standpoint. Indeed, for large datasets, using preliminary binary encoding can greatly amplify the difficulty of the already challenging optimisation task. The idea is to rather utilise ordinal encoding to quickly find a non-binary DT solution, and then transform this solution, through some form of collapse, into a more interpretable version, maybe even a binary DT depending on how we conduct the collapsing process.
23

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
X_9=0
X-1
X_ 7=0
X 7=1
X 7=0
7=1
X 10=0
10=1
X
X_1
X-3
X 3=1
Y=l
X_8=0
X 8=1
8=0
X 8=1
X 2=0
X 2=
Y=0
X 2=0
X 2=
Y=0
Y=1
X 340
3=1
1=0
1= Y=l
3
3=
Y=
x 1= X===
Y=0
X 1=0
IE
Y=0
2=
2=
Y=0
Y=l
Y=0
Y=l
Y=0
x 2=0
2=
Y=O
Y=0
Y=l
Y=0
Figure 10. Optimal sparse DT for monk1-f, ff, it has 17 splits.
X is x2
x X
10
Vel
X
X
Ye0
Vel
Figure 11. Optimal sparse DT for monkl-o, it has 10 splits.
F. BRANCHES vs GOSDT
Among the state of the art algorithms, GOSDT is the closest to BRANCHES. Indeed, MurTree and STreeD are DFS methods unlike OSDT, GOSDT and BRANCHES. Moreover OSDT operates on the space of DTss instead of the space of branches unlike GOSDT and BRANCHES. For this reason, we dedicate this section to discussing the differences between BRANCHES and GOSDT.
Support for ordinal encoding: The first straightforward difference is BRANCHES' support for non-binary DT's that stem from ordinal encoding. In contrast, GOSDT (as well as all the algorithms we compare with) is only applicable to binary features, which necessitates preliminary binary encoding. As we see in Section and Appendix H.4, this detail crucial, it confers BRANCHES' more scalability potential as these non-binary DT solutions are always found significantly faster (in the span of few seconds). In Appendix E we explained the drawbacks of binary encoding from theoretical standpoint.
The Purification Bound: It is true that (Lin et al., 2020, bounds (9) and (10)) and the purification bound stem from the same reasoning, which we call purification when explaining the intuition behind Proposition 4.2. Furthermore (Lin et al., 2020, bounds (9) and (10)) support equivalent points, a situation that arises when the dataset includes duplicate instances with different classes, while our bound does not currently support this. However, this is straightforward to incorporate the purification bound and it will be future version of BRANCHES. Moreover, we emphasize that while (Lin et al., 2020, bounds (9) and (10) and the purification bound stem from a similar reasoning, they are different. The purification bound pertains to penalising the number of splits while (Lin et al., 2020, bounds (9) and (10)) rather correspond penalising the number of leaves. This could lead to differences when considering non-binary features. Moreover, (Lin et al., 2020, bounds (9) and (10)) are formulated for binary classification setting with binary features. On the other hand, the purification bound fordulated for the general case of multiclass classification with categorical features that are not necessarily binary. We further prove in Proposition 4.2 that the purification bound upper bounds the true optimal values Q* (I, a) and V (1) when is initialised and also when it updated during Backpropagation.
24

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
X (=
X (14=((1)
X (24=
(=5=(0)
x_5=(11,)
x_5=(02))
X_5((1)
X_5=
X_5=(2)
Y=1
X X_1=(0)
x (_
X_1=(0)
X_1=(12,33
Y=l
X [0)
X_1=(12,3)
Y=l
Y=1
Y=0
Y=1
Y=0
Y=1
Y=0
Figure 12. Collapsed optimal sparse DT for monkl-o, it has 7 splits similarly to the solution induced for monk 1-1.
The Selection process: By Selection process, refer to the strategy of choosing the branch explore, by expanding it into children branches and then updating its value estimate (or bound). For BRANCHES, this is performed within our AO framework where we start from S and follow the action with highest value estimate Argmax Q (4. a) until reaching a branch that is either SOLVED or that has not been expanded yet. This process is achieved through the use of multiple small priority queues at the level of each branch to keep track of Argınax 2 (1, a). In contrast, GOSDT employs one global priority queue where all the encountered branches are stored. Using this queue, GOSDT selects the most promising branch, i.e. the branch with the best (lowest in GOSDT's setting) bound. However, this branch would not necessarily be the most promising one for BRANCHES because it does not necessarily lie in BRANCHES' selection path. Indeed, the branch with highest V (1) does not necessarily lie in the path following Arginax Q (1, a) from Ω in the AO* terms of (Nilsson, 2014, Chapter 3), the branch chosen by GOSDT does not necessarily even lie in BRANCHES' current best partial solution graph. Due to the use of this one global priority queue, GOSDT resembles more an OR search than an AND/OR search algorithm. This difference in the selection strategies explain the large difference in the number of iterations of BRANCHES and GOSDT, which in favour of BRANCHES. In addition to this fundamental difference, our Selection process allows us incorporate heuristics for adequately choosing an UNSOLVED child, explained in Appendix B. This flexibility has the potential of improving the anytime behaviour as explained in Appendix C. and indeed our experiments in Section 5 and Appendix H.4 show BRANCHES' anytime behaviour to always outperform GOSDT's. We emphasize here that these properties are provided due to the AND/OR nature of BRANCHES.
The Backpropagation process: BRANCHES updates value estimates along the selection path only. It is true that multiple paths lead to the same selected branch I, and as such the branches along these paths could also be updated in principle. However, the number of these paths is equal to the number of permutations of the clauses of l, which quickly becomes computationally costly. Moreover, many of these branches will be pre-emptively pruned and thus updating them would be a waste of time. Those that are not pruned will inevitably be visited by BRANCHES, and only then do we update them. In contrast, GOSDT updates the values along all the ancestors of the selected branch. This idea of backpropagating along the selection path only discussed in (Nilsson, 2014, p. 106):
Therefore, not all ancestors need have cost revisions, but only those ancestors having best partial solution graphs containing descendants with revised costs (hence step 12).
In addition to this difference, we explained in Appendix D that BRANCHES further sorts split actions via their As consequence, if many split actions share the value Argmax (a) Q (1, a), then the ac- tion a for which Ch (1, a) are all SOLVED (when it exists) will always be prioritised, thus deducing immediately that I is SOLVED and avoiding wasting time exploring it again in the future.
value_complest
Caching procedure: BRANCHES uses branch caching while GOSDT uses dataset caching or support set caching. We could implement this caching procedure in the future for BRANCHES, however, we have some doubts about its soundness when it comes to the sparsity problem, even for optimisation with hard constraint on depth. Indeed, two branches I and 2 could share the same support set (subset of the dataset that they contain) but differ in their number of splits S (4) < S (12). In this case, the support set is insufficient to fully grasp the optimisation problem from each branch. From 4 we have more splits to use before reaching the maximum depth than from 1z. Using dataset caching in this situation might lead to a suboptimal solution. This warrants further investigation in the future, in the absence a proof of optimality (to our best knowledge) specific to dataset caching, we chose the conservative option of branch caching for BRANCHES.
25

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Computational complexity analysis: In Section 4.2 we analysed the computational complexity of BRANCHES by bounding the number of branch evaluations performs before terminating. Such analysis not conducted for GOSDDT (Lin et al., 2020, Theorem H.l) provides a big-O bound on the total number of binary DTs that can be constructed from set of M binary features, but it does not specifically analyse GOSDT's computational complexity. To our knowledge, only (Hu et al., 2019, Theorem E.2) provides such analysis for OSDT, hence why we compared with it in Table
The experiments we conduct in Section 5 and Appendix H.4 show that BRANCHES dominates GOSDT on the majority of experiments and for different metrics. From lower execution time and significantly fewer iterations to better anytime behaviour. This further supports the more efficient AND/OR search strategy of BRANCHES.
Empirical results:
G. Proofs and Additional Theoretical Results
Proposition G.1. Let O < À < 1 and consider T y Hy (T), for any DTT we have the following:
S (T) - S (T*) = H (T) S (TT)
Proof. Let T be a DT and suppose that S (T) < S (T*). Since T = Argmax H.. (T) we have:
H₂ (T) < H) (T") = (T) - (TS + (
- s -
Lemma G.2. Let x be a policy and E S'
T non-terminal state. If (1) = a then Tūo =1] and Vt 2 1: T7o - (1)
otherwise we can define the trajectory
TT
recursively as follows:
120
Tho
=(} U1,TTT T VI 21
T7,
Proof. The case ग (l) = is trivial by the definition of the trajectory, thus we focus on the case π (1) # a. By induction on t 2 1, for = 1 we have by definition VI, E T7; TT,,, = (lw) and thus Tú = Ul.ETT Ti,
Now suppose that the inductive hypothesis is true for some & and let us prove it for t 1. We have:
T = U ((()((1))
U
PETENT
VET
On the other hand, the inductive hypothesis states that:
=:UU UT
LETT
Moreover, we know that (TH (Th..t-1)
are mutually exclusive because they are sub-DT's rooted in mutually exclusive
roots Lu E Tf hence T ( L.ET,7
forms partition of TV and we can rewrite T [,1+1 as:
Te
U
U F(')x(1))
U
LETT
P'TT.
VETT
DT
U
Thet
L. L.T
Thus concluding the induction proof.
26

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Proposition 3.1. Let a be a policy and I E 8 T, then there exists minimum of 2 1 such that for any 2 7/.
TV. 171,11..1117771 is composed of terminal states only.
Proof. We follow a proof by induction on (1) {o......0 9).
S (1) = q:
Then (() = { and क (1) = a. Therefore Ti, = {1} and 27,11 = F (1, (1)) = ((, = -(], and thus for Ty" = 1 we
have:
14 7| Tñ, - {1}
Now assume the inductive hypothesis to hold for some 8 (1) -1)= p q and let prove for S() = pp-1 1: If (1) then 17,1 }7} and the result holds for 7/" = L. Otherwise when (1) * a. Lemma G.2 states that:
Vt > T7, U T T
On the other hand we know that vla E 77 8 (1.) 8 (1) + p, thus the inductive hypothesis implies that:
Vly E TM आ. N 1 र 2 प. T
T
TT.
Take 77" = E7,, { + 1, then get:
Vt 2 7" Th
U -
U
Th,,.
L
L. ET,,
Since VI' E Tunny l' then:
A4 77 A/ E TT.
Thus concluding the induction proof.
Proposition 3.2. Let be a policy and E ES) T non-terminal state, then V (I) satisfies the following:
v" (1) HA (TT) -XS (17) + H (TT)
Moreover, the optimal D is the DT of an optimal policy x", in other words T = =T
Proof. We proceed by induction on S (l) E .......g).
S = q: Then we have π (1) a and thus 7f" 1 and TV (1). Therefore:
y" (1) (1, (1)) (1, H (1) = H. (77)
The equality H (1) H. (TTT) stems from the fact that 77 {{} is the sub-DT rooted in that requires splits of Now let us assume the inductive hypothesis to hold true for some < S (4) p S q and let us prove the result for S 1:
If (1) = प. the result holds trivially with the same reasoning as the one we used for the case S (l) = q. Now consider the case क (?) o a. we have the following:
DC (0)= = Σ Σ
r (la (ln))
t=
L. LT
=r (1)) + Σ
Σ
r (lu: (lw))
1= LETTAT
=- Σ
Σ
r (lus (bw))
1= LETEAT
27

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
The last equality stems from the fact that (1, (1) - because क (I) @ is split action. Lemma G.2 states that
The (Ta,t1) (.EF(..(1) is partition of Ti2 and therefore write:
Va (² E
E
E
rlu: (lm)
t= ('E((la()) (. LEET
-1
=--+ Σ
Σ
Σ
(lu: t (lw))
(er(L,()) t=
LETT
1
AT
We know that VI' E 77,1 Tp S TÝ" - and thus:
V" - E
Σ
Σ
r (lus (lw))
(l)(L t=0 LeTT, AT
=
Σ V (L)
(EF((L))
On the other hand know that VI' E F (1, (I)) (() = 8 = therefore the inductive hypothesis implies:
VI' E F (1, (1) 1² (1) = 7 (TT)
Going back V (l) induces:
1"th (1) -
Σ
HA (TT)
((EF(L,())
=
Σ
(17)
+
Σ
H HTT))
('E((L(())
('F((L,()
- 1+
Σ ('F((L()
S S
Σ H(T))
('EF(l,(0)
The sub-DT T/ is constituted of the sub-DTs TF that each rooted in l' E F (1, (I)), thus the number of splits of T7 is equal (the first splits at I) plus the sum of the numbers of splits of Tp for 1' F (l, (1)),
S (TT)=
Σ ((7))
(EF((.())
Moreover (T (EF is partition of TY and thus:
H HTT) = Σ H(FF)
MEP(L.())
Going back to V" (1) we get:
VaH (1) -X (TT) + (TT) = H4 (TT)
This concludes the induction proof.
Lemma G.3. Let nt be an optimal policy, iee Argmax, 1at (9) and consider the set of non non-terminal states in its trajectory from Ω:
5- S = U T \T
t=0
Then for any policy π we have the following:
E VaT (1) - (I)
28

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Proof. We follow a proof by contradiction procedure. Suppose that there exists a policy such that:
3E E S" V (1) V* (1)
Since / S", there exists
t S Ti
such that / Th We write:
V" ( Σ
Σ
r (lu, x (lw) +
E
V" (1)++
(19)
t=0
tu
AT
PETRA V7
Now we define new policy x' as follows:
n and all of its descendents.
π = x- elsewhere.
The first term in (19) is therefore equal to:
4-1
Σ
(lu, x (lo)
Σ = 1= L.E.RAA
r rlu,, a (Iu))
t= LETG
Let us now analyse the second term ΣvETH VTVI V (I'). Since E Thin then for I' E Th \ \T (1), and I' share no descendents. Therefore, for any descendent of l' we have (1") = x² (1") and therefore:
W E E n.
AT 10 V (1") Vol (1')
E (²)()) Σ
Va (0)
PETRA ATAO)
METR. \TVO)
For the third term in (19), since n' = on / and all of its descendents, then we have V= (1) (1)= 1=)=(( V" (1). We can now rewrite (19) as follows:
V" (2)
<
Σ
r (lu, x (ld)
Σ
VT (()) + 1m (L)
t= LETT AT
rET VTM
=V)((N)
1 (Ω)
This contradicts the fact that x² is optimal, which concludes our proof.
Proposition 4.1 (Bellman Optimality Equations). Let xt be an optimal policy, iee. E Arginax, ya8 (M) and consider the set of non-terminal states in its trajectory from Ω2
S
Th T
1=0
Now consider policy x and suppose that for all l S::
Va (1)
max Q (1,a) aEA(l)
(8)
Then n is optimal and we also have:
π Argmax A() QT (l,a)
(9)
Proof. We know that VI e S* 30 t/ : Tä., \ T. We will now show that VI E : V/ (I) = V" (I) which would include yat (I2 = y (22). The proof proceeds by backward induction on 4
29

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
For 4 = 1. by definition we have:
V" (1) max 2 (1, 2 Q" (1, = (1)= @", (1,
(20)
aEAII))
On the other hand, we know that nt" (1) a. Indeed, this is true because otherwise x² (1) would be split action leading to non-terminal states, which means that f T2,7 includes non-terminal states, and this would contradict the definition of Tt2- Therefore:
v (1) = 2- (1, (1)) 0* (1,a)
(21)
From Equation (20) and Equation (21) get:
v" (1) 2 V (1)
(22)
On the other hand, since x² is optimal and / E S we have y (1) V" (1) according Lemma G.3, and deduce that:
V" (1) = V" (1)
Now suppose that Va (1) = Va (1) for all I e S* such that for some 1 s To 1 and let us show that the result
still holds for t. 1. Let E S such that t t - have va (1) max,eA()) 2 (1, On the other hand:
- (1, (1)) = r ( (0)+
Σ
V" (l,)
(23)
Moreover VL, F (l, (1)) T: Lu E S t. t. The induction hypothesis then implies that:
vua E F (1, (1) T: 1T (tw) V (la)
Going back Equation (23), get:
2 (1, Tt (1)) (1, (1))
Σ
V" (1,) 2- (1, (1)) v" (1)))
(())
Now we have:
v" (1) = max Q" (1, O a (1)) = V" (1) a(A(())
On the other hand 1AT (1) S V* (1) because x² optimal. Therefore we deduce that:
v" -1)=0000 (1)
which concludes the inductive proof.
Proposition 4.2 (Purification Bound), Let E S T, we define the Purification Bound follows:
A (1) {a} + 0:
(I) = max H (1), -X ((())((X) = 1}}
(1=(()) (1)
- + n (1) }
max
(13)
Otherwise:
n (1) (1)
( = 1z (1)
(14)
The bounds V (1) are initialised with (13) or (14), then they are recursively backpropagated to the ancestors of in the AND/OR graph through (11) and (12). The resulting heuristic estimates Q (l, a) and V (1) are upper bounds on the tree optimal values Q" (1, (1 and " (I) respectively.
30

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Proof. Let first show that the initialisations in Equation (13) and Equation (14) are upper bounds on the true optimal values V (I):
The case A (l) {a} is trivial because the only action that can be taken at / is a. which means that all policies x map / to
(1) ō. therefore:
VT 1t (1) = r =1, (1)
=
Now consider the case (1) \ { * 0. we have the following:
V (1) max H (1), - (I 1]}
max 12 (1,T), - (X) 1]}
suffices to show now that:
Ya A (1) {a}: O (1,a) - - P P((())
a E A() {ā} be a split action, we have the following:
y (1. = r(,
E
V" (la)
LEFULONT
=
Σ
V" (lw)
(24)
LEF(La)
On the other hand, Proposition 3.2 implies that:
Vl, E F (l, V" ((w) H. (TT. = XS + H. (TT.)
I PP (X) = 1,777 (X) = =Y]
< P Ih (X) = 1]
The second line stems from the definition of 7. (TT.) and the fact that S (TT:) 2 0. Going back to Equation (24) yields:
Q' (1, a) S - Σ
Ph. (X)= = 1]
LEF((
Since F (1, a) is partition of / we know that P (X) = = = ELEF((a)) P (/ (X) = 1] and thus:
@ (4,0) < - - PX(x) =1]
We deduce that:
(1) max -XP((x)) = =1]}
2 max Q" (1,a) 2 0² (1, (1) = V" (1)
aEA(())
Now let 1 E S \ and suppose that for all its children, the upper bounds V (lu) are available. For all split actions E (1) {a), the definition (11) implies that:
(1, -
Σ (1w)
1.F((L))
Since Vh E (L, (L.) 2 Va (lu), we get:
@ (1, a) 2 -X
Σ
V" (ww== = 0² (1,a)
V"
(..F(L.)))
On the other hand, the definition (12) implies that:
v = max (1,aa)
aEA(()
max Q" (1,a) aEA(1)
2 Q* (1, n" (I))
2 V (1)
which concludes our proof.
31

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Theorem 4.3 (Optimality). Upon lermination, the selection policy गř becomes optimal. In other words:
(2)) = V2 (St) max V (Ω2
Proof. To prove this show that for any / E 8 \ T SOLVED if and only if:
y (1) = (() 2 V (L)
where V" the value function of an optimal policy x². We proceed by induction on S rp S q:
If - then have:
म (1) क Argmax (0./)1(2110 (1,
(25)
On the other hand:
n (1) o² (1, Q² -1,4)
(26)
From Equation (25) and Equation (26) we deduce that:
= max aEA(())
((.))=v(1)) 2
The last inequality is due to Proposition 4.2. Note that we do not necessarily have y* (1) - V (l) even though x² is an optimal policy. Indeed this would only necessarily satisfied if E S* as per Lemma G.3.
Now suppose that the result is true for o| for some 1 S S q and let us prove it for any 8 T such that = =t+1. We have:
v (1) Q (1)
=r (1,
Vd (lw))
(.F((L.())
Since -/ = 1++22 2 then we necessarily have म (1) E (1) \ [ i.c. मे (l) is split action. Indeed, this is true because otherwise we would have T/ = 1. Therefore we get:
V -
Σ
D (lw)
(.FF(
On the other hand 1l, E F (1, which means that:
o = t and thus the inductive hypothesis implies that V (lw) = V ((a) 2 V" (lu).
aaa (1)= + Σ
2
max @11,a) = (1) aEA(()
(.EF(1,E())
2 (1)=
2" (1, (1)
N V" (1)
which concludes the inductive proof.
Now, since BRANCHES terminates when S becomes SOLVED, then we have: n (1) > V* (?)
On the other hand, since Ω E S", then by Lemma G.3, we necessarily have:
n (2) < 1" (Ω)
Hence deducing that:
nd (Ω) = V" (Ω)
32

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Lemma G.4. A branch I E ES) T can be chosen for Expansion only if there exists DT T such that:
|ETVL L -AS(T) + E ((") + 11)
Where L [1' ET: (1) - (X)
Proof. A branch E s T can only be chosen for Expansion it is tip node (leaf) of the search graph G and is selected by the selection policy i.e.
3t 2 0: TR.
We know that there exists T 2 0 such that for all I E T a tip node of G. This is true because otherwise G would be bottomless, which is false because it has maximum depth of q (the total number of features). On the other hand, the recursive definition of V yields:
( - (ū.7)
Σ v(()
VET
Since all branches l' E Tü are up nodes of G. then ((() = H (1)) if (1) 2 -X PI and V('")
+ [V' (X) 1] otherwise. Define I, {I' Rrr (H') - 11' (X)= = 1]]; have:
v V - (Tā.F)
Σ (()++
Σ (-X+P(((X) 1]}
I'LL
On the other hand, according to Proposition 4.2 and Proposition 3.2 we have the following:
(22
2 (2) = -AS (T*) H (TT)
Thus:
-XS
T
+
Σ +()+ +
Σ (-)+ = 11} 2 +H
FELL
PETRAAL
Moreover, 1 can only be expanded i E
0.r because all the branches in L are SOLVED. This concludes our proof.
Theorem G.5 (Problem-dependee complexity of BRANCHES). Let T (q, C, A) denote the total number branch evaluations performed by BRANCHES for an instance of the classification problem with 2 features, 0 < X S 1 the penalty parameter, and C 2 2 the number of categories per feature. Then, I (gg C, A) satisfies the following bound:
Σ< (q h) Ch++1 (:):
min {
1+ 1 - H (T
(g.
((T))
:9
h=0
Proof. Let / be a branch. According to Lemma G.4, for to be considered for Expansion, there has to exist DT T such that:
1 T L 1S (T) + EVeL H(')) EVvrru - ( = -
where T. = (1' : 2 - P I' (x) = 1]}. Suppose is such a branch, then we have:
-XS (T) + Σ H(') + Σ 2)
Fet (x)(
LET'L
PET
33

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Since 1 E T L, then [T L/2 and get:
+T) + -12- (T
(ST))
A
(()) 1 (T
A
Let C- = branch (())) S STT)) 1 1-x(T") [C].
Then the number of branches that are expanded is upper bounded by
We recall that we rather seek to upper bound the number of branches that are evaluated, i.e. for which we calculate H. (1). These evaluations happen during the Expansion step of BRANCHES. When branch / expanded, we evaluate all of its children. There are 9 - S (!) features left use for splitting I, and for each split, C' children branches are created. Thus, there are (q- S (1)) C children of hence (q (1)) C evaluations happen during the expansion of I. Let upper bound I' (g. C, A).
For each branch E C:
1
We choose (1) O, ....... min |s(T))
HIT')
9 } The minimum comes from the fact that E C and
S (1) S q.
For each h = S (4), we construct by choosing / features among the total features, there are (H) such choices.
For each choice among the (1) choices, for each feature among the h features, there are choices of values, therefore there are Ch (X) branches with depth h.
For each branch of depth h, when it is expanded, (q h) C evaluations occur.
With these considerations, we deduce that:
(g h) ch+11 (9): min { [(T)) - 1- H (1*))
(4,
19
h=0
Theorem 4.4 (Complexity). Let I' (g, C, A) denote the total number of branch evaluations performed by BRANCHES for classification problem with number of features 2 2, penalty parameter 0 < X < 1, and a number of categories per feature 2 2. Then, (g. C, X) satisfies:
( < Σ (q h) ch+1 !
where k = min [Lxx] 1, -
Proof. This is corollary of Theorem G.5. To make the bound problem-independent. let us upper bound and make it independent 7"" We know that:
HA ( H (0) (0) (0) 1 K
Hy (I*)=-X8 -
K
1 1- (T*)
S
< KY
Which concludes the proof.
34

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Table Number examples nt, number features g, number of classes and penalty parameter for the different datasets in our experiments. d is the depth of optimal solution, which employ in Appendix H.3.
Dataset
n
À
monk1
124
17
0.01
4
monk1-1
124
11
0.01
5
monk1-f
124
11
0.001
7
monk1-o
124
6
0.01
3
monk2
169
17
0.001
6
monk2-f
169
11
0.001
monk2-o
169
0.001 6
monk3
122
17
0.001
monk3-f
122
11
0.001
7
monk3-o
122
6
0.001
tic-tac-toe
958
27
0.005
6
tic-tac-toe-f
958
18
0.005
6
tic-tac-toe-o
958
0.005 9
car-eval
1728
21
0.005
car-eval-f
1728
15
0.005
car-eval-o
1728
6
0.005
nursery
12960
27
0.01
nursery-f
12960
19
0.01
nursery-o
12960
8
0.01
mushroom
8124
117
0.01
mushroom-f
8124
95
0.01
mushroom-o
8124
22
0.01
kr-vs-kp
3196
73
0.01
Z00
101
36
0.001
z00-f
101
20
0.001
Z00-0
101
16
0.001
lymph
148
59
0.01
lymph-f
148
41
0.01
lymph-o
148
18
0.01
balance
576
20
0.01
balance-f
576
16
0.01
10
balance-o
576
0.01
H. Additional Experiments
All the experiments were run personal Machine (2,6 GHz 6-Core Intel Core i7), they are easily reproducible. Below we provide references to the implementations we used:
BRANCHES /aacccctasttttee/////aoooooooooe
DL8.5 DaA.ft/tes/stttttccccc////aauuaa
OSDT h h5tp:ppp///tttaaooooo//////ggggp
GOSDT h0t.////////ttttoooo///////////e
MurTree wttffictttee///ttnoooooorraa/ptt
STreeD http://ttp//gghhha....///////ttt
35

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Table 5. Comparing BRANCHES with the state of the python implementations for large maximum depth 20.
OSDT
PYGOSDT
BRANCHES
Dutaset
objective
time (8)
objective
time (5)
itemiions
abjective
time (8)
itemntons
splits
splits
splits
monk1
0.940
1
6
2.38
949001
0.940
1
6
6.03
174523
0.940
6
0.05
146
monk1-1
0.930
1
71
2028577
0.930
1
181
3731292
0.930
7
0.02
117
monk1-f
0.971
1
29
TO
22308
0.970
1
30
TO
2018
0.983
17
0.39
2125
monk1-o
0.900
10
0.02
64
monk2
0.948
1
52
TO
41
0.948
1
52
TO
44
0.968
32
14.2
60611
monk2-f
0,904
0.982
76
TO
44083
0,903
0.982
77
TO
32475
0.933
67
2.94
28968
monk2-o
0.955
45
0.18
1213
monk3
0.976
0.991
15
TO
17728
0.976
0.991
15
TO
5765
0.985
15
4.05
14807
monk3-f
0.975
0.991
15
TO
11875
0.973
0.991
17
TO
897
0.983
17
0.36
3026
monk3-o
0.987
13
0.03
156
tic-tac-toe
0.794
0.869
15
TO
76
0.794
0.869
15
TO
69
0.838
0.928
18
TO
390000
tic-tac-toe-f
0.764
0.824
11
TO
40
0.808
0.824
11
TO
37
0.850
0.945
19
16.3
74627
tic-tac-toe-
0.773
0.858
17
0.68
3339
mushroom
0.955
0.985
76.2
1186819
0.955
0.985
3
211
2681260
0.955
0.985
3
TO
21000
mushroom-f
0.945
0.985
TO
170-1119
0.945
0.985
4
TO
2187909
0.945
0.985
4
TO
21000
mushroom-o
0.975
0.985
1
0.15
kr-vs-kp
0.900
0.940
TO
67161
0.900
0.940
4
TO
25379
0.900
0.940
4
TO
46000
MurTree, STreeD and GOSDT use support set caching and the similarity bound. On the other hand, the current imple- mentation of BRANCHES only supports branch caching and it does not include a similarity bound. Additionally, we set the maximum nodes for MurTree 80. We noticed that without this constraint, the kernel dies immediately. The optimal sparse DT for all the experiments we consider have less than 80 nodes, thus this constraint should not cause Mur to be suboptimal.
Table 4 summarises the properties of the datasets we employed in our experiments. The À values reported in Table 4 are those employed in the experiments of Section 5, they were chosen from a pool of values À E {0.1, 0.05, 0.025, 0.01, 0.005, 0.001] to yield meaningful solutions. Appendix H.2 provides the induced Pareto fronts by these values for a 10-fold crossvalidation.
H.1. Comparing BRANCHES with Python implementations
We have shown in Section 5 that BRANCHES outperforms its C++ competitors in terms of runtime even though it is implemented in Python. To further illustrate the importance of this achievement, we compare BRANCHES with Python implementations and show the vast difference in performance in favour of BRANCHES.
Table 5 compares BRANCHES with OSDT and PYGOSDT, it contains less datasets than Table 2 because the implementations of OSDT and PYGOSDT are restrained to binary classification problems. Table 5 shows that BRANCHES outperforms OSDT and GOSDT in terms of runtime, number of iterations and quality of the proposed solution on all the experiments except mushroom. On mushroom, OSDT and PYGOSDT terminate in 76.2s and 211s respectively while BRANCHES reaches timeout. Nevertheless, BRANCHES' anytime behaviour still allowed the retrieval of the true optimal sparse DT in this case.
Table 5 showcases the shorteomings of Python implementations for the sparsity problem as both OSDT and PYGOSDT reach timeout and are suboptimal on the vast majority of datasets. Due to the optimisation difficulty of the sparsity problem, a lot of care has to be dedicated to low-level optimisation of the proposed implementations, property that C++ offers better than Python, hence the vast adoption of C++ in the state of the art algorithms solving the sparsity problem. BRANCHES being implemented in Python and yet outperforming its C++ competitors is a testament to its efficient -bsed search strategy. Moreover, a future C++ implementation of BRANCHES is very promising especially when coupled with multi-threading.
H.2. Pareto fronts
The purpose of this section is to compare DT algorithms of different natures. BRANCHES solves the sparsity problem, CART is a greedy search algorithms for DTs and DL8.5 seeks the optimal DT subject to a hard constraint on maximum depth. Figure 13, Figure 14, Figure 15 and Figure 16 report the median and the quartiles of the accuracy and number of splits of the proposed solutions induced by 10 fold crossvalidation, branches-o the legends represents BRANCHES applied ordinal
36

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
encoding. For DL8.5, we ran it with with maximum depths raging between and 10. As for BRANCHES and CART, they with À E {0.1, 0.05, 0.025, 0.01, 0.005, 0.001). ). Note that À in the context of CART refers to the cost-complexity parameter (ccp_alpha in scikit-learn) that is used for the pruning phase. It plays similar role to the penalty parameter X, hence why we tested both with the same set of values. A similar set of experiments was conducted by Hu et al. (2020) albeit with the maximum depth for CART instead of the cost-complexity parameter. We noticed that the cost-complexity parameter yields better frontiers for CART than the maximum depth, hence our choice. Figure 15 and Figure 16 report the same results as Figure 13 and Figure 14 respectively but with the inclusion of DL8.5. We made this distinction for clarity purposes because DL8.5's solutions become so complex (high number of splits) that the differences between the frontiers of CART and BRANCHES become less apparent.
Figure 13 shows that BRANCHES displays better training frontiers than those of CART, and on many occasions branches-o yields even better training frontiers as we can see in monkl-f, I-f, monk2-f, careval-f, nursery, nursery-f, mushroom, mushroom-f, 200, zoo-f, lymph-f and balance-f. This indicates that applying BRANCHES on an ordinal encoding of the data is not only good from a scalability standpoint (as we have seen with the extremely fast convergence in Table 2) but can also yield better solutions in terms of accuracy and the number of splits. On the other hand, the differences in the test frontiers, depicted in Figure 14 are less clear than for the training frontiers. Nevertheless, we can still observe an advantage for BRANCHES' test frontiers over CART's. Moreover, Figure 14 illustrates tendency of branches-o to overfit we observe in monk2, monk2-f, tictactoe, tictactoe-f, lymph, lymph-f, balance and balance-f. This phenomenon can be explained by the tendency of non-binary DTTs on ordinal encodings to induce branches containing smaller subsets of data than those induced by their binary DTs counterparts, thus increasing the risk of overfitting. Notice that for large datasets (nursery with 12960 data and mushroom with 8124 data) branches-o does not run into this overfitting issue.
Figure 15 and Figure 16 illustrate how DL8.5 actively seeks more and more complex DT's as the maximum depth parameter increases, thus disregarding sparsity concerns and inducing poor frontiers compared BRANCHES and CART. To alleviate this tendency, Aglin et al. (2020) further include constraint on the minimum support size of DL8.5, i.e. the minimum number of data that a branch has to contain in order to be considered for expansion. In the next section, we investigate this constraint and show that even with the best configurations DL8.5 is still suboptimal.
H.3. Suboptimality of DL8.5
In all the experiments, we set the maximum depth of DL8.5 to the depth of the true optimal sparse DT that we derive using BRANCHES, these depth values are reported in Table 4. We analyse DL8.5's performance over 20 values of minimum support size (minimum allowed number of instances per branch) taken between and 50. Figure 17 shows that, even with the knowledge of the best possible maximum depth parameter and the best configuration of minimum support size, DL8.5 almost never approaches the baseline derived by BRANCHES. Figure 18 further illustrates that BRANCHES' solution is always outside the accuracy-splits frontier displayed by DL8.5, which means that BRANCIES solution always dominates DL8.5's solution from a sparsity perspective.
H.4. Comparison across a wide range of maximum depths
We compare the performance of BRANCHES, GOSDT and STreeD on a of maximum depth values ranging from 4 to 20. For all the algorithms, compare the objective HA, accuracy and number of splits of the proposed solution in addition to the execution time. Morcover, compare GOSDT and BRANCHES in terms of the number of iterations. We also compare the depth of the proposed solutions between BRANCHES and STreeD only because, to our knowledge, the implementation of GOSDT does not provide this metric. The legends of the figures contain:
branches: BRANCHES applied binary encoding.
branches-o: BRANCHES applied to ordinal encoding.
gosdt: GOSDT applied to binary encoding.
streed: STreeD applied to binary encoding.
streed1: STreeD with the depth 2 solver, introduced by Demirović et al. (2022), disabled. The reason we introduce this baseline is to assess the contribution of the depth 2 solver to STreeD's performance. We shall see that this option improves STreeD's performance significantly.
37

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO
The results are reported in Figures 19 40. We start by discussing the performance of GOSDT. Interestingly, the objective Hj reported for GOSDT does not match the one reported for BRANCHES and STreeD.. This might indicate that the implementation of max depth for GOSDT forces the solution to have depth strictly lower than max depth, unlike BRANCHES and STreeD where the solution is allowed to reach max depth. Nevertheless, this does not undermine the following discussion. Surprisingly, GOSDT performs often worse when limiting its maximum depth than otherwise. There are even cases where it runs out of memory even though this phenomenon has not been observed in Table 2. This happens for mushroom, mushroom-f, lymph, lymph-f, tic-tac-toe, krvskp, nursery and nursery-f, hence why GOSDT's results are missing in those figures. We note that this phenomenon has been observed by McTavvih et al. (2022), the authors that incorporate the maximum depth parameter into GOSDT. They state:
Interestingly, using a large depth constraint often less efficient than removing the depth constraint entirely for GOSDT, because when use a branch-and huudbooud approach with recursion, the ability re-use solutions of recurring sub-problems diminishes in the presence of a depth constraint.
On the other hand, despite being a BFS method as well and as such being more memory consuming than DFS methods, BRANCHES never ran into this issue in both sets of experiments. This is likely explained by BRANCHES' ability to terminate significantly earlier than GOSDT in terms of iterations, and thus terminating before running into memory issues. This large discrepancy in the number of iterations was observed in Table 2 and is further observed in all the experiments in this section. Furthermore, except on few cases such as balance, BRANCHES dominates GOSDT in terms of execution speed.
On these experiments the comparison with STreeD is more insightful. A common pattern that STreeD dominates BRANCHES in terms of speed for small depths up until certain point where BRANCHES becomes the dominating method. This is best observed in tic-tac-toe-f, car-eval-f, nursery-f, zoo and balance-f. We note also that in some cases such as balance, lymph-f, lymph and tic-tac-toe, STreel proposes better solutions altogether than BRANCHES because the latter reaches timeout, albeit for higher depths we cannot even compare the solutions of BRANCIES and STreeD because STreeD does not even propose solutions then. A very insightful experiment here is mushroom. We have seen in Table 2 that STreeD performs exceptionally well on mushroom and mushroom-f even for a large maximum depth. The experiments on this section further support this observation. Thus we naturally wonder: Why does STreeD perform exceptionally well on the mushroom datasets? Is it the DFS strategy or something else? To investigate this, we looked into a powerful tool in STreeD's arsenal, the depth 2 solver that was introduced by Demirović et al. (2022). This solver allows for finer estimates to be computed early on, it has been proven to yield significant runtime improvements, and moreover neither GOSDT nor BRANCIES utilise it for now. Fortunately, STreeD's 's implementation allows the disabling of the depth 2 solver. Indeed, the depth 2 solver turns out to be paramount to STreeD's performance, without it, STreeD always runs out of time on the mushroom datasets. Moreover, now BRANCHES largely dominates STreeD across the full range of max depth values, except on very few cases such as depths 13, 14 and 15 in balance-f. With this, we conclude that STreeD's 's better performance on mushroom and smaller depths is not due its DFS strategy, but rather to the depth 2 solver. This observation motivates us to consider adapting the depth 2 solver to the purification bound and incorporating it in future version of BRANCHES. This is a promising idea that could push BRANCHES to dominate STreeD for small depths as well.
Next we discuss the anytime behaviour. We have seen in Table 2 that STreeD lacks the anytime behaviour unlike GOSDT and BRANCHES, which hinders its applicability. To cite a few examples, STreeD (with the depth 2 solver) starts reaching timeout from depth 7 for lymph and depth 8 for lymph-f and tic-tac-toe. On the other hand, notice that the solutions proposed by BRANCHES even after reaching timeout always dominate those proposed by GOSDT in terms of the objective Hy, This is especially the case for car-eval, balance and balance-f and we recall that we could not report GOSDT's performance on many other datasets because it runs our of memory.
Lastly, we discuss the application of BRANCHES to ordinal encoding. On all experiments, the optimal sparse DT is found significantly faster in this setting, even for the largest dataset nursery with 12960 examples. This further supports the scalability potential of this property. Moreover, while it is true that from the objective's 's perspective, the induced solutions with ordinal encodings are not always the best compared to those induced by binary encoding, however, they happen to be better often such as in monk2-f, monk3, monk3-f, car-eval-f, nursery, nursery-f zoo, zoo-f, lymph, lymph-f, balance-f, mushroom and mushroom-f.
38

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
mank1
monk1-f
monk2
monk2-f
1.00
0.55
0.15
0.55
0.65
0.10
0.80
0.6
0.65
0.65
monk3
monk3 f
tictactoe
tictactoe-f
1.00
1.00
0.55
0.55
0.90
0.10
0.80
0.45
0.65
careval-f
nursery
nursery-f
0.65
0.55
0.40
++
0.88
Train
0.60
0.80
0.75
0.10
0.78
18
20
10
62
10
20
32
50
60
72
10
20
30
40
20
50
22
10
50
80
mushroom
mushroom-f
200
200-f
1.40
1.00
1.00
0.55
0.55
0.15
0.85
0.50
0.80
lymph
lymph-f
balance
balance-f
1.00
1.00
1.0
3.0
0.25
0.00
0.7
05
0.5
75
200
125
150
100
200
Number of splits
cart
branches
branches-o
Figure 13. Pareto fronts of training accuracy against the number of splits of the proposed solutions. branches-o indicated that BRANCHES applied to an ordinal encoding of the data.
39

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
monk1
monk1-f
monk2
monk2-f
0.2
0.5
25
94
monk3
monk3-f
tictactoe
tictactoe-f
6.55
3.60
3.4
6.45
0.85
1.0
0.7
20
careval
careval-f
nursery
nursery-F
3.40
0.5
0.40
0.75
377
0.75
Test
0.70
0.35
20
23
20
50
62
30
72
30
22
30
40
50
20
mushroom
mushroom-t
Z00
200-f
3.00
1.00
1.00
0.59
0.5
0.20
200
0.50
030
0.05
0.0
6.00
0.00
6.40
3.00
6.35
0.75
lymph
lymph-f
balance
balance-f
0.4
0.3
10
20
200
250
220
Number of splits
cart
branches
branches-o
Figure 14, Pareto fronts of test accuracy against the number of splits of the proposed solutions. branches-o indicated that BRANCHES applied to an ordinal encoding of the data.
40

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
mank2
monk2.f
0.35
0.50
0.20
0.-
0.8
0.40
0.75
0.75
0.75
0.
20
26
60
60
80
106
126
160
50
360
150
260
260
103
150
301
250
360
monk3
monk3-f
tictactoe
tictactoe-F
1.00
1.00
1.00
1.00
0.55
0.50
0.10
0.90
0.50
0.15
0.75
0.80
0.00
225
50
125
120
200
220
250
careval
careval-f
nursery
nursery-f
1.00
1.00
1.00
0.05
0.00
0.60
0.65
Train
0.00
0.73
160
160
0.55
mushroom
mushroom--
200
200-f
1.40
1.00
1.0
1.0
0.00
0.00
0.66
0.60
0.34
0.54
0.7
lymph
lymph-f
balance
balance-f
1.00
2.00
100
0.25
0.55
0.0
0.0
0.05
0.00
0.00
0.5
Number of splits
dl8.5
- cart
-
branches
branches-o
Figure Pareto fronts training accuracy against number splits the proposed solutions. This figure similar Figure but further includes DL8.5.

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
monk1-f
monk2
monk2-f
08
0.7
0.-
0.6
0.5
0.4
25
20
45
61
100
100
1:6
52
160
150
200
250
101
152
201
252
302
monk3
monk3-f
tictactoe
tictactoe-f
1.0
0.8
0.5
0.5
0.8
100
150
125
A52
120 nursery
255
32
100 nursery-f
careval
careval-f
0.8
Test
0.2
0.0 0.3
116
mushroom
mushroom-f
200
200-f
1.30
1.00
1.0
6.48
0.75
0.75
lymph
lymph-f
balance
balance-f
0.-
6.75
0.7
Number of splits
dl8.5
- cart
-
branches
branches-o
Figure Pareto fronts test accuracy against the number splits of proposed solutions. This figure similar Figure further includes DL8.5.
42

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
monk1
monk1-f
monk2
monk2-f
0.9
0.30
0.55
0.2
0.89
0.7
0.75
0.70
0.15
0.65
monk3
monk3 f
tictactoe
tictactoe-f
1.0
0.56
0.9
0.0
0.40
0.6
0.78
10
10
10
careval-f
nursery
nursery-f
0.0
0.7
0.7
0.76
Objective
0.6
0.75
0.4
0.76
0.4
0.72
22
20
40
50
10
13
22
30
60
50
10
20
33
40
50
mushroom
mushroom-f
200
200-f
0.355
0.7
0.7
5.350
0.6
0.6
0.25
00123
0.5
0.000
60
10
10
42
20
16
10
lymph
lymph-f
balance
balance-f
0.00
0.2
0.74
0.5
13
22
Minimum support size
cl8.5
branches
Figure 17. Comparing HA (T) of the proposed solutions DL8.5 for different values of the minimum support size with the BRANCHES baseline. The maximum depth of DL8.5 is set to the depth of the true optimal solution, which we derive using BRANCHES.
43

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
monk1-f
monk2-f
0.7
0.7
0.6
10
16
26
16
82
20
65
100
123
monk3
monk3
tictactoe
tictactoe-F
1.0
0.75
0.5
0.3
0.300
0.550
0.0
0.025
0.900
0.7
0.3
0.8
0.325
22
15
careval
careval-f
nursery
nursery-f
2.8315
0.20
0.56
0.32
0.54
0.32
0.10
0.19
0.18
68
0.81
25
0.57
mushroom
mushroom-f
Z00
200-F
1.0
1.01
6.446
0.640
0.922
0.600
6.300
0.00
6.66
0.666
lymph
lymph-f
balance
balance-f
1.00
0.50
0.65
0.000
0.50
0.025
0.75
Number of splits
d18.5
+
branches
Figure Comparing Accuracy and number splits the induced solution by DL8.5 for different values minimum support size with the BRANCHES baseline.
44

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
lterations
0.94
100
0.93
0.98
0.96
0.94
40000
0.89
20000
0.88
0.92
monk1
12
14
16
16
Splits
Depths
Time
3.8
3.4
3.0
16
branches
branches-o
gosdt
streed
streed1
Figure 19. Depth analysis for monk1.
Objective
Accuracy
Iterations
0.975
1.000
150000
125000
100000
0.925
0.900
50000
0.875
25,00
monk1
0.825
Splits
Depths
Time
16
25
12
5-
5-
branches
branches-o
gosdt
-
streed
streed1
Figure 20. Depth analysis for monk1-f.
45

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
0.93
1.00
0.98
30000
0.90
0.96
20000
0.89
0.94
10000
0.92
monk1
2.0
Splits
Depths
Time
2-
4.0
3.0
18
20
branches
branches-0
gosdt
streed
streed1
Figure 21. Depth analysis for monk1-1.
Objective
Accuracy
Iterations
0.95
1.0
0.90
200000
0.75
6.70
100000
0.65
monk2
18
Splits
Depths
Time
50
250
40
5.5
5.0
150
4,0
branches
branches-o
gosdt
-
streed
-+-
streed1
Figure 22. Depth analysis for monk2.
46

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
1.00
0.85
0.85
150000
0.80
0.80
100000
50000
monk2
12
14
16
Splits
Depths
Time
10
300
50
200
150
30
50
10
16
branches
branches-0
gosdt
streed
streed1
Figure 23. Depth analysis for monk2-f.
Objective
Accuracy
Iterations
1.00
300000
2500000
0.87
0.98
150000
100000
0.96
monk3
0.95
Splits
Depths
Time
120
1.6
60
40
20
branches
branches-o
gosdt
-
streed
streed1
Figure 24. Depth analysis for monk3.
47

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
1.00
100000
0.98
80000
0.97
0.96
40000
0.95
monk3 f
0.95
0.94
12
14
16
16
Splits
Depths
Time
14
10
14
12
10
16
branches
branches-0
gosdt
streed
streed1
Figure 25. Depth analysis for monk3-f.
Objective
Accuracy
Iterations
400000
0.94
0.84
0.92
300000
200000
0.80
tictactoe
0.78
16
Splits
Depths
Time
400
16
5.0
200
12
4.0
branches
branches-o
gosdt
-4-
streed
-+-
streed1
Figure 26. Depth analysis for tic-tac-toe.
48

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
166
0.50
0.84
30
0.82
0.900
0875
2.0
0.500
1.0
0.76
tictactoe
0.74
0.775
0.0
10
Splits
Depths
Time
300
16
5.5
200
14
5.0
150
10
4.0
branches
branches-o
gosdt
streed
streed1
Figure 27. Depth analysis for tic-tac-toc-f.
Objective
Accuracy
Iterations
0.85
0.83
0.88
0.86
2-
0.81
0.80
careval
Splits
Depths
Time
500
400
12
10
branches
branches-o
gosdt
-
streed
-+-
streed1
Figure 28. Depth analysis for car-eval.

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
1e6
1.25
0.80
1.00
0.79
careval f
0.78
0.25
0.00
1.0
Splits
Depths
Time
300
12
200
150
branches
branches-0
gosdt
streed
streed1
Figure 29. Depth analysis for car-eval-f.
Objective
Accuracy
Iterations
140000
0.822
0.890
120000
100000
0.880
0.836
0.675
60000
0.855
nursery
0.830
0.860
Splits
Depths
Time
350
5.5
300
5.0
4.5
150
3.5
3.0
branches
branches-o
gosdt
-
streed
streed1
Figure 30. Depth analysis for nursery.
50

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
50000
0.82
0.89
0.88
300.0
0.87
20000
0.79
0.86
nursery
20
18
20
12
16
1.8
Splits
Depths
Time
300
250
200
7.0
4.0
150
6.9
6.8
3.0
20
branches
branches-0
gosdt
streed
streed1
Figure 31. Depth analysis for nursery-f.
Objective
Accuracy
Iterations
0.975
1.02
0.965
0.98
5000
mushroom
0.955
0.34
Splits
Depths
Time
2.5
2.0
2.0
200
100
1.0
branches
branches-o
gosdt
-
streed
-
streed1
Figure 32. Depth analysis for mushroom.
51

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
0.975
1.02
30000
0.960
0.98
20000
0.955
10000
mushroom
0.945
0.94
16
10
16
Splits
Depths
Time
350
300
3.0
3.0
2.5
1.5
50
1.0
1.0
branches
branches-0
gosdt
streed
streed1
Figure 33. Depth analysis for mushroom-f.
Objective
Accuracy
Iterations
55000
0.92
50000
0.90
0.94
0.88
0.92
krvskp
0.86
35000
Splits
Depths
Time
400
3.00
4.0
1.00
3.8
3.8
branches
branches-o
gosdt
-
streed
-+-
streed1
Figure 34. Depth analysis for kr-vs-kp.
52

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
1.00
0.99
0.8
0.98
0.97
0.4
0.95
0.0
ZOO
100
Splits
Depths
Time
250
5.0
150
100
4.0
branches
branches-o
gosdt
streed
-
streed1
Pigure 35. Depth analysis for
Objective
Accuracy
Iterations
1.00
0.99
0.8
0.97
0.4
0.95
0.95
0.0
Z00
Splits
Depths
Time
7.0
300
6.5
9.0
6.0
200
8.5
5.5
150
7.5
4.5
7.0
4.0
branches
branches-o
gosdt
-4-
streed
-+-
streed1
Figure 36. Depth analysis for zoo-f.
53

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
100000
0.95
0.94
0.845
0.93
60000
0.92
40000
0.825
lymph
0.830
10
Splits
Depths
Time
300
5.0
200
100
4.0
branches
branches-o
gosdt
streed
streed1
Figure 37. Depth analysis for lymph.
Objective
Accuracy
Iterations
0.55
175000
150000
0.86
0.93
2000
100000
0.83
0.92
3.90
lymph
0.81
Splits
Depths
Time
400
6.0
10
5.5
200
4.5
4.0
branches
branches-o
gosdt
-
streed
-+-
streed1
Figure 38. Depth analysis for lymph-f.
54

---

Branches: Efficiently Seeking Optimal Sparse Decision Trees via AQ
Objective
Accuracy
Iterations
0.76
0.75
0.78
0.73
0.76
0.5
balance
0.71
0.74
0.0
1.0
16
Splits
Depths
Time
350
150
100
branches
branches-0
gosdt
streed
streed1
Figure 39. Depth analysis for balance.
Objective
Accuracy
Iterations
0.71
150
0.70
1.00
0.68
0.72
0.67
0.70
0.50
balance
0.65
0.68
0.00
Splits
Depths
Time
300
250
150
branches
branches-o
gosdt
-
streed
-+-
streed1
Figure 40. Depth analysis for balance-f.
55


Reviews:
[{"review_id": "qwm6OpFZa7", "reviewer": "Reviewer_EY1f", "summary": "This paper presents \"BRANCHES,\" a novel algorithm for learning optimal decision trees (DTs) by integrating Dynamic Programming (DP) and Branch & Bound (B&B) techniques. The study addresses the trade-offs in existing methods—where some approaches provide efficient DP strategies but lack strong pruning bounds, and others excel in pruning but sacrifice DP efficiency. The authors introduce a new analytical pruning bound, called the \"Purification Bound,\" to enhance search space reduction. Empirical evaluations demonstrate that BRANCHES surpasses state-of-the-art methods in speed, optimality, and iteration efficiency while supporting non-binary features. Theoretical analysis confirms its computational superiority.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your reviews, please find below our response.\n## Missing Literature:\n\n- (McTavish et al. 2022): We cite these authors, in fact we use their implementation of GOSDT as mentioned in Appendix H. We also directly quote them in Appendix H.4. However, we only compared with GOSDT and not with the additional guided guesses that the authors introduced. The reason is that this loses the optimality guarantee (with respect to $\\mathcal{H}_\\lambda$) of GOSDT upon termination, and our main objective in this paper is to compare methods satisfying this optimality guarantee, hence the choice of STreeD, MurTree and GOSDT. Furthermore, the guesses strategy is not exclusive to GOSDT, it can be incorporated within Branches search strategy as well in similar fashion to how the authors incorporated it in GOSDT and DL8.5. For this reason, it makes sense to compare the base algorithms and to consider an incorporation of the guesses strategy in the future for Branches.\n- (Mazumder et al.2022) is specifically tailored to continuous features. Moreover, the main objective of this work, which is (1), does not incorporate sparsity concerns in terms of actively seeking to minimise the complexity of the solution while simultaneously maximising its accuracy. Quant-BnB rather optimises its objective subject to a hard constraint on depth as either $2$ or $3$. This is different from our work, which aligns more with literature that jointly optimise accuracy and sparsity via the objective $\\mathcal{H}_\\lambda$.\n- (Hua et al. 2022) is also specifically tailored to continuous features and large scale applications as demonstrated by the costly experiments of 1000 cores and two hours run-times. Our experiments on the other hand are less costly, we run them on a personal Machine (2,6 GHz 6-Core Intel Core i7) as stated in Appendix H and for 5 minutes, which makes them easily reproducible.\n\n## Weaknesses:\n1- Indeed, Branches necessitates a discretisation of numerical features, this is common among many works in the literature of DT optimisation. Moreover, contrary to the state of the art, Branches is not restricted to binary encodings but can deal with ordinal encodings as well.\n\n2, 3 - Indeed, we have mentioned these limitations in Section 6 as avenues for future work.\n\n## Comparison with Random Forest:\nEnsemble methods such as Random Forest focus on performance in terms of accuracy (for example) but forgo interpretability. The objective of this paper is to jointly optimise for both concerns in similar fashion to papers from this literature such as:\n-  Demirovic, E.,Lukina, A., Hebrard, E., Chan, J., Bailey,J., Leckie, C., Ramamohanarao, K., and Stuckey, P. J.Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1–47, 2022.\n- Hu, X., Rudin, C., and Seltzer, M. Optimal sparse decision trees. Advances in Neural Information Processing Systems, 32, 2019.\n- Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pp. 6150–6160. PMLR, 2020.\n\nFor this reason, works from this literature generally do not compare with ensemble methods.\n\n## Questions:\n1- Being a BFS (Best First Search) method, Branches is more memory consuming than DFS methods such as MurTree and STreeD. On the other hand, its informed BFS strategy allows it to achieve optimality faster thus alleviating the issue. This is a general trade-off between BFS and DFS, and it is thus valuable to devise an BFS strategy that terminates optimally quickly before consuming too much memory. This is what we achieved with Branches, Theorem 4.4 and Table 1 analyse its time complexity (which is directly linked to its memory complexity as the search graph grows with each iteration) and show its superiority compared to the literature. Furthermore, Table 2 shows that the number of iterations to termination of Branches is significantly smaller than GOSDT (a BFS method as well), which allows it to terminate in smaller runtimes even though Branches is currently implemented in Python and GOSDT in C++ . The memory concerns of BFS and DFS are discussed in Section 2.\n\n2- Perhaps, but we have to keep in mind the optimality concerns with respect to sparsity as well. It is unclear whether a native handling of numerical features would keep this guarantee.\n\n3- As shown with the mushroom dataset, high-dimensional data can be hard to deal with as the degree of each node in the search graph becomes too large. On the other hand, Branches seems to work well on large datasets in terms of rows.", "claims_and_evidence": "See Strengths And Weaknesses.", "methods_and_evaluation_criteria": "See Strengths And Weaknesses.", "theoretical_claims": "See Strengths And Weaknesses.", "experimental_designs_or_analyses": "See Strengths And Weaknesses, and Essential References Not Discussed.", "relation_to_broader_scientific_literature": "Related to a new methods for optimal decision tree.", "essential_references_not_discussed": "Many peer works that can handle with non-binary features and large datsets are missing:\n[1] McTavish, H., Zhong, C., Achermann, R., Karimalis, I., Chen, J., Rudin, C., & Seltzer, M. (2022, June). Fast sparse decision tree optimization via reference ensembles. In Proceedings of the AAAI conference on artificial intelligence (Vol. 36, No. 9, pp. 9604-9613).\n[2] Mazumder, R., Meng, X., & Wang, H. (2022, June). Quant-BnB: A scalable branch-and-bound method for optimal decision trees with continuous features. In International Conference on Machine Learning (pp. 15255-15277). PMLR.\n[3] Hua, K., Ren, J., & Cao, Y. (2022). A scalable deterministic global optimization algorithm for training optimal decision tree. Advances in Neural Information Processing Systems, 35, 8347-8359.\n\nAuthor should cite and compare with the newest literature to validate the claimed benefits in their work.", "other_strengths_and_weaknesses": "Strengths\nThe paper successfully integrates the strengths of both methodologies, providing an effective pruning strategy while maintaining computational efficiency. This new analytical bounding strategy significantly improves search space reduction, leading to faster convergence. The authors offers rigorous theoretical proofs and extensive empirical evaluations demonstrating the superiority of BRANCHES over existing methods.\n\nWeaknesses\n1. The method currently only supports categorical data, necessitating pre-processing for numerical datasets.\n2. The Python-based implementation, while effective, lags behind C++-based state-of-the-art implementations in execution speed.\n3. Although BRANCHES is inherently parallelizable, the current implementation does not exploit multithreading capabilities.", "other_comments_or_suggestions": "While BRANCHES performs well, its complexity may still pose challenges for extremely high-dimensional datasets. The study does not compare BRANCHES to ensemble methods such as Random Forests, which could provide additional insights into practical performance trade-offs. The reliance on Python may hinder adoption in environments where execution speed is critical.\n\nOverall, this work presents a significant contribution to interpretable machine learning by improving decision tree optimization. However, addressing its limitations—particularly scalability, native numerical feature support, and parallelization—would further strengthen its impact. Minor clarifications on the empirical benchmarking methodology and additional comparisons with alternative optimization techniques would be beneficial.", "questions_for_authors": "1. How does BRANCHES handle large-scale datasets compared to existing methods in terms of memory usage and computational time?\n2. Would extending the method to numerical features via native handling (rather than discretization) significantly impact its efficiency?\n3. How does BRANCHES perform when tested on real-world applications beyond benchmark datasets?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2sjHc3wjx6", "reviewer": "Reviewer_TyUY", "summary": "The paper considers the problem of learning an optimal decision tree for a given dataset. Specifically, the DT learning problem is formulated as a heuristic search problem over an AND/OR graph representing the space of all possible DTs. Consequently, an efficient best-first search algorithm (aka AO* search) called Branches is developed to find an optimal DT in terms of splits. An empirical evaluation is carried out on standard machine learning datasets from the UCI repository. The results demonstrate that the proposed AO* search algorithm outperforms existing state-of-the-art approaches based on depth-first Branch-and-Bound search.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your reviews, please find our response below:\n\n## Presentation:\nThank you for this feedback. We have included Figure 2 in the Appendix for the purpose of illustrating the notions of branches and sub-DTs. Do you have any recommendation that would improve this figure's quality? Thank you.\n\n## Mixed concepts from the RL and heuristic search community\nRL and heuristic search share many common notions and terminology and we do not think that notions like policies, actions and values are exclusive to RL. In fact, several heuristic search papers employ these concepts such as:\n\n- \"LAO*: A heuristic search algorithm that finds solutions with loops\".\n- \"Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and its application to MDPs\".\n\nThe RL community also employs many concepts that are traditionally linked to heuristic search. The notions of node expansion, update... are extensively employed in the context of Monte Carlo Tree Search, e.g \"Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. (2012). A survey of Monte Carlo Tree Search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43\".\n\nThese unified concepts are very helpful for us in deriving the proofs of our theoretical results. If we failed to define clearly some of these notions, we kindly ask if you could refer us to the ones in question so that we incorporate the necessary modifications. Thank you very much.\n\n## AND/OR Search Graph\nIn section 3.3, we state that we follow the hypergraph convention in (Nilsson, 2014, Section 3.1). The reason we chose this convention over the AND/OR nodes is to make the graph illustration more compact. With AND/OR nodes, Figure 1 would not be able to fit in the paper. We note that both conventions are equivalent, with AND/OR nodes, OR nodes would represent states (branches) and AND nodes would represent actions (split actions and the terminal action). Furthermore, the search space of branches is represented in several papers with the hypergraph convention (albeit without specifying a link to AND/OR search), e.g:\n\n- \"Aglin, G., Nijssen, S., and Schaus, P. (2020). Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3146–3153.\" Figure 2.\n- \"Nijssen, S. and Fromont, E. (2007). Mining optimal decision trees from itemset lattices. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 530–539.\" Figure 2.\n- \"Nijssen, S. and Fromont, E. (2010). Optimal constraint-based decision tree induction from\nitemset lattices. Data Mining and Knowledge Discovery, 21:9–51.\" Figure 1.\n\nThank you for the recommendation regarding a solution graph. A solution graph is the DT of a policy, for example, the graph constituted of the red connectors in figure 1 is a solution graph. We can add this remark to the paper, thank you.\n\n## Observation regarding AO* vs DFS:\nIndeed, but to our knowledge, this advantage has not been explored for seeking optimal sparse decision trees. The contribution of our paper was to explore this and develop Branches.\n\n## Questions\n1- Yes, Proposition 4.2 proves that the purification bound is admissible as it always overestimates the optimal value of a node (overestimation as opposed to the traditional underestimation because we are in a formulation based on objective maximisation instead of cost minimisation). Moreover, Theorem 4.3 proves the optimality of Branches upon termination.", "claims_and_evidence": "The claims are supported by experimental results.", "methods_and_evaluation_criteria": "The evaluation makes sense", "theoretical_claims": "The theoretical claims appear to be sound.", "experimental_designs_or_analyses": "The experimental evaluation is sound.", "relation_to_broader_scientific_literature": "The related work seems to be addressed well.", "essential_references_not_discussed": "The related work seems to be addressed well.", "other_strengths_and_weaknesses": "Main strengths:\n-------------------\n\nThe paper considers an important yet quite challenging problem in machine learning and AI, namely learning optimal decision trees for given datasets. Despite its difficulty, the problem has many real-world applications and therefore more efficient algorithms for solving it are warranted. DTs are interpretable and therefore well suited for situations where the model's decisions must be explained such is healthcare applications.\n\nThe empirical evaluation is sound and is conducted in a principled manner. The results are presented in a relatively clear manner and therefore it is fairly easy to get the pig picture and appreciate the good performance of the proposed method.\n\nMain weakness:\n------------------\n\nI found the quality of the presentation quite poor. The presentation of the method is quite dense and it is not easy to follow the details. I think sections 3.1 and 3.2 need a good running example that would illustrate the technical details described such as the branches and sub-DTs. \n\nSection 3.2 and especially Section 4 are not easy to follow because the presentation mixes concepts common to the RL literature such as policies, actions and value functions, with concepts common to the heuristic search community such as search nodes, node expansion, node value update etc. \n\nSince the main contribution of the paper is a heuristic best-first search I suggest adopting a description closer to the search community. Specifically, I think it's important to describe clearly the search space in terms of OR nodes and AND nodes, as well as the values associated with the nodes, what these values represent and the way they are computed during search. As far as I can see, an OR nodes maximises the values of its children, while an AND node combines the values of its children by summation. The connector representation from Fig 1 is not very common and therefore is not easy to digest. Instead, I would represent the OR and the AND nodes explicitly. Also it is important to articulate clearly what the solution graph represents and perhaps illustrate it with an example.\n\nThe observation that AO*-like algorithms are more efficient than depth-first branch and bound algorithms (of course at the expense of using additional memory) is well known in the heuristic search community. Therefore, the experimental results are not very surprising.", "other_comments_or_suggestions": "See previous section.", "questions_for_authors": "1. Regarding the heuristics used, is the proposed purification bound heuristic admissible?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BDVYyyNxWj", "reviewer": "Reviewer_EG8X", "summary": "The paper presents Branches, a new approach for computing optimal decision trees by formulating the problem as AND/OR graph search and proposing an AO*-type algorithm that solves the problem. The proposed approach learns non-binary trees (i.e., trees with multiway splits) for non-binary features. The author provide a theoretical characterization of the algorithm complexity and experimental evaluation against three popular optimal decision tree baselines.\n\n## after rebuttal\nI thank the authors for their response. I think the paper would benefit from a more detailed discussion on interpretability (as noted in the author response, the number of branches in multiway splits can definitely impact interpretability). I also think a more detailed comparison of testing accuracy including approaches focused on continuous features that are very common is important (very granular discretization will lead to many categories which may hurt performance or interpretability). Overall, I maintain my evaluation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, please find below our response:\n\n## Interpretability of multi-way splits\n- Thank you for raising this point. The interpretability of DTs is due to their simple decision rules, it is not specific to binary DTs. On the other hand, we recognise that DTs where each node has a large number of children can become less interpretable than binary DTs. We alleviate this issue by penalising the number of splits, which leads to DTs with small number of splits and hence more interpretablity.\n- In Appendix E, we directly compare ordinal encoding with binary encoding in terms of interpretability, especially when we introduce the notion of collapse. We argue in these examples that DTs that stem from ordinal encoding can be more interpretable than binary encoded DTs. This is especially the case when comparing Figure 7 and Figure 8; and also Figure 12 and Figures 9 and 10.\n- In addition, Branches is not restricted to ordinal encoding, it can be applied to binary encoding in similar fashion to the state of the art. In which case, if we have a good binary encoding that we think yields interpretable DTs, we can choose to use Branches with it. The benefits of Branches compared to the other algorithms are still satisfied in this case.\n\n## Methods And Evaluation Criteria:\n- Yes, Table 2 reports the training accuracy with no train/test split. The objective being to find the most accurate DT with least complexity (most sparse DT). Quoting (Lin et al.2020; Section 5)[2]: \"Learning theory provides guarantees that training and test accuracy are close for sparse trees\". However, we recognise that a direct comparison of test performance would be insightful as well. In Appendix H.2, we compare Branches with CART and DL8.5 in terms of Pareto fronts (accuracy vs number of splits) within a 10-fold cross-validation. The reason we restrict this comparison to Branches, CART and DL8.5 is to compare different types of DT construction algorithms (Branches seeks optimal sparse DTs, CART seeks DTs greedily, and DL8.5 seeks optimal DTs subject to a hard constraint on depth), comparing Branches with GOSDT and STreeD in this context would yield the same solutions when they terminate.\n- We compared with CART in Appendix H.2.\n- Blossom does not solve the problem of sparsity that Branches, GOSDT and STreeD solve. It rather seeks optimal DTs subject to hard constraint on depth in similar fashion to DL8.5. Nevertheless, we included an illustrative comparison with these types of DTs in Appendix H.2, where we chose the popular DL8.5 algorithm. We note that DL8.5 is anytime as well.\n- Indeed Branches struggles with highly dimensional data such as mushroom, but we showed that its handling of ordinal encoding alleviates this issue significantly, with a fast termination in only $0.15s$ for mushroom-o. Moreover, in Appendix H.4, we investigated the reason STreeD performs exceptionally well on mushroom, we found that it is mainly due to the depth 2 solver, a technique introduced in Demirovic et al.2022 [1]. This leads us to believe that a future incorporation of the depth 2 solver in Branches could further improve its current performance.\n- Branches handles categorical features. Any type of discretisation preprocessing can be applied to numerical features before feeding the dataset to Branches. This is similar to other algorithms such as GOSDT, STreeD and MurTree, with the additional benefit that Branches handles multiway splits and thus does not necessitate binary preprocessing. We did not compare with Quant-BnB because it is specifically tailored to continuous features, and it does not solve the sparsity problem. Rather, Quant-BnB seeks optimal DTs subject to a hard constraint on depth that is either 2 or 3. Branches and the algorithms we compare with can find optimal sparse DTs of higher depths.\n- We make text bold based on the objective $\\mathcal{H}_\\lambda$ first. Then we compare accuracy, splits and runtimes of the methods yielding the highest objective, with the corresponding bold text.\n\n## Other weaknesses:\n- Thank you very much, this is a very interesting point. In appendix D.1, page 14, we provide a tie-break strategy \"There is an additional benefit to storing -value_complete. When there are multiple split actions attribute that maximise value, then we prioritise the one maximising value_complete.\". We will update the main paper to refer to this tie-break strategy. Thank you for this recommendation.\n- For space concerns, we refer the reader to (Nilsson, 2014, Section 3.2) for the base AO*.\n\n[1] Demirovic, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., and Stuckey, P. J. Murtree: Optimal decision trees via dynamic programming and search. Journal of Machine Learning Research, 23(26):1–47, 2022.\n\n[2] Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pp. 6150–6160. PMLR, 2020.", "claims_and_evidence": "- See specific concerns below regarding the experimental evaluation and analysis.\n- In addition, the claim of interpretability requires further justification: in particular, different from previous work this work proposes a non-binary tree, i.e., trees with multiway splits. It is not clear whether they should be perceived as equally interpretable to people and there is no clear discussion on this.", "methods_and_evaluation_criteria": "There are several concerns regarding the experimental evaluation setting:\n- The reporting of the results seem to focus on *training* accuracy rather than *test* accuracy (it is not clearly stated what accuracy is reported, but likely training accuracy as there is no mention of splitting the dataset to train and test set). Given that some algorithms time out (TO) and some reach different optimal solutions (as indicated by different objectives while both algorithms have run to completion, perhaps due to the setting of max depth), it is particularly useful to compare test accuracy in addition to training accuracy.\n- No comparison with simple baselines like CART.\n- No comparison with anytime approaches for optimal trees like Blossom [1].\n- Benchmark dataset: many of the benchmarks on the list (monks and tic-tac-toe which together account for half of the results table) are synthetic.\n- Most datasets have low-dimensionality. The only one whose dimensionality is above 100 is mushroom where it seems Murtee and STreeD are significantly faster.\n- No analysis for dataset with continuous variables and in particular comparison with approaches designed for such datasets like Quant-BnB [2].\n- Its not clear why running times and splits that are the lowest are sometimes not in bold font (if the bold font is based purely on objective, then the only thing that should be bold is the objective)\n\n[1] Demirović, Emir, Emmanuel Hebrard, and Louis Jean. \"Blossom: an anytime algorithm for computing optimal decision trees.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Mazumder, Rahul, Xiang Meng, and Haoyue Wang. \"Quant-BnB: A scalable branch-and-bound method for optimal decision trees with continuous features.\" International Conference on Machine Learning. PMLR, 2022.", "theoretical_claims": "I did not carefully check the correctness of the proofs in the supplementary material.", "experimental_designs_or_analyses": "See relevant points under \"methods and evaluation\" above.", "relation_to_broader_scientific_literature": "Overall the paper includes a reasonable review of previous work, with some notable works missing (examples provided above). It provides a new approach for optimal decision trees which is an active research area with significant interest in recent years.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n- Novel approach for optimal decision trees based on AND/OR graphs and AO*-style algorithm.\n- Experiments show significant gains in performance compared to the baselines.\n- Theoretical characterization of complexity is provided\n\nOther weaknesses:\n- No discussion of tie-breaking in search (e.g., if multiple actions have similar value in Eq. 15) and its impact on performance (also relevant for steps like \"choose one of them arbitrarily\", p.6).\n- It would be useful to provide a brief description of the base AO* algorithm.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See above for my concerns.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k6tuqDz0YB", "reviewer": "Reviewer_qYmf", "summary": "The paper introduces BRANCHES, a search method for decision trees. Using an AND/OT graph formulation for the decision tree search, the method relies an OA*-like exploration strategy with purification bounds for the heuristic.\nThe introduced method provably recovers the optimal decision tree and the efficiency compares favorably with respect to the efficiency bound from OSTD in the literature. The method shows significantly improved empirical performance and efficiency an a wide range of UCI classification task.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for very much for your reviews, please find our response below:\n\n## Missing literature\n- Chaouki et al. (2024)'s TSDT algorithm is tailored to online classification where a data stream is observed instead of a batch of data, which is different from the batch setting we consider. Due to the online consideration, TSDT does not have a natural termination condition like Branches and GOSDT, it has to keep adjusting the prior distributions of the node values until reaching a prespecified number of iterations. For these two reasons we decided not to compare with TSDT. However, we thank you for this suggestion, and we can definitely add such a comparison in the appendix for illustration purposes.\n- Nunes et al. (2020) do not solve the sparsity problem (minimising $\\mathcal{H}_\\lambda$).  In addition, we are not aware of a public code for the authors' algorithm, which prevents us from directly comparing with their algorithm. Nevertheless, (Table 4, Nunes et al. 2020) seems to indicate that the algorithm is significantly slower than the state of the art as it runs in hours. For example, car-\nevaluation takes 3 hours and 19 minutes and tic-tac-toe takes 4 hours and 59 minutes. Branches and\nGOSDT terminate and are optimal in under 2 minutes in both of these experiments.\n\n## AND/OR representation\nThank you for this remark. In fact, in section 3.3, we state that we follow the hypergraph convention in (Nilsson, 2014, Section 3.1), which replaces the notions of AND/OR nodes with nodes and connectors. The reason we chose this convention over the AND/OR nodes is to make the graph illustration more compact. With AND/OR nodes, Figure 1 would not be able to fit in the paper. We note that both conventions are equivalent. With AND/OR nodes, OR nodes would represent states (branches) and AND nodes would represent actions (split actions and the terminal action). Furthermore, the search space of branches is represented in several papers with the hypergraph convention (albeit without specifying a link to AND/OR search), e.g:\n\n- \"Aglin, G., Nijssen, S., and Schaus, P. (2020). Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3146–3153.\" Figure 2.\n- \"Nijssen, S. and Fromont, E. (2007). Mining optimal decision trees from itemset lattices. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 530–539.\" Figure 2.\n- \"Nijssen, S. and Fromont, E. (2010). Optimal constraint-based decision tree induction from\nitemset lattices. Data Mining and Knowledge Discovery, 21:9–51.\" Figure 1.\n\nWe thank you for this suggestion, we can try to include an equivalent representation of Figure 1 in terms of AND/OR nodes in the Appendix.\n\n## Notation\nThank you for this recommendation. In fact, we chose $F$ for transitions instead of $T$ to avoid confusion because we already use $T$ substantially with sub-DTs and DTs. The reason we chose $F$ specifically is because it is used in this context in some literature, e.g.:\n- \"Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and its application to MDPs\" in section **Models**.", "claims_and_evidence": "I did not find any problematic claims.", "methods_and_evaluation_criteria": "* Analyzing the method in terms of optimality and efficiency makes sense. I also appreciated the numerical comparison of the efficiency bound to the one from OSDT in order to give some perspective on how they compare to each other. \n* The method is empirically evaluated on standard classification tasks from the UCI repository (11 in total) and compared to three baselines (including a relatively recent one from 2024). Using accuracy/number of splits/time (and number of iterations, where applicable) as evaluation criteria also makes sense.", "theoretical_claims": "I did not check the proofs in Appendix G.", "experimental_designs_or_analyses": "I checked the experiment in Section 5 and did not find an issue with it.", "relation_to_broader_scientific_literature": "* the optimization objective (including the penalty term) is the same as Bertsimas & Dunn (2017),  Chaouki et al. (2024), Hu et al. (2019) and in case of binary classification, Lin et al. (2020). \n* the work is most closely related to Lin et al. (2020), but a detailed list of differences is given in the Appendix (namely: additional support for ordinal encoding, additional complexity analysis, improved empirical performance, value estimate update only along selection path, multiple local priority queues instead of a global one).", "essential_references_not_discussed": "The related work section focuses on DFS, BFS, and AO* approaches. I believe there is also a line of work applying MCTS to find optimal decision trees:\n\n* Online Learning of Decision Trees with Thompson Sampling; Chaouki et al. (2024) [This reference is already included, but it is not discussed how it relates to the proposed method]\n\n* Learning decision trees through Monte Carlo tree search: An empirical evaluation; Nunes et al. (2020).", "other_strengths_and_weaknesses": "I appreciated the relatively detailed problem formulation which was helpful even for readers without extensive background on decision trees.", "other_comments_or_suggestions": "I think it could help to add a remark for which nodes are the \"AND\" nodes and which nodes are the \"OR\" nodes.\n\nThe notation is a bit unusual (not wrong, though) in some cases:\n* Section 3, first paragraph: I think the following notation is a bit confusing: $D=\\ {X_m, Y_m\\}_{m=1}^n$. Letting the index run from $m=1,...,M$ or from $n=1,...,N$ might be a bit easier to parse. \n* Denoting the transitions in a MDP with $F$ instead of $T$ is also a bit unusual.", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The work deals with the theoretically hard task to find good decision tree models. The devised algorithm is anytime and guaranteed to return an optimal solution when it terminates. The work provides some complexity guarantees and empirical study about it. The problem is formulated as an AND/OR graph search which is attacked via an AO*-type algorithm. The resulting approach is not fully compared against other ideas in the literature (though the authors try to answer to this point in the rebuttal, it is apparent from the discussions that both theoretical and empirical comparisons could have been better conducted), and currently has some limitations in the type of data it can handle (or requires some sort of discretisation, even if that is common practice in optimisation for this purpose). The presentation is thought to be jammed and could be significantly improved, and the description could be more in line with previous work on search. All in all, this is a borderline case.
Decision: Accept (poster)