Leveraging Predictive Equivalence in Decision Trees
Authors: Hayden McTavish
Zachery Boner
Jon Donnelly
Margo Seltzer
Cynthia Rudin
Venue: ICML 2025 poster (2025)
Keywords: Decision Tree
Interpretability
Machine Learning
Missing Data
Variable Importance
Cost Optimization
Primary area: social_aspects->accountability_transparency_and_interpretability
TL;DR: Decision trees’ representations are not unique; we use this to improve missingness handling, variable importance, and cost optimization.

Abstract: Decision trees are widely used for interpretable machine learning due to their clearly structured reasoning process. However, this structure belies a challenge we refer to as predictive equivalence: a given tree's decision boundary can be represented by many different decision trees. The presence of models with identical decision boundaries but different evaluation processes makes model selection challenging. The models will have different variable importance and behave differently in the presence of missing values, but most optimization procedures will arbitrarily choose one such model to return. We present a boolean logical representation of decision trees that does not exhibit predictive equivalence and is faithful to the underlying decision boundary. We apply our representation to several downstream machine learning tasks. Using our representation, we show that decision trees are surprisingly robust to test-time missingness of feature values; we address predictive equivalence's impact on quantifying variable importance; and we present an algorithm to optimize the cost of reaching predictions.

Leveraging Predictive Equivalence in Decision Trees
Hayden McTavish
Zachery Boner"
Jon Donnelly
Margo Seltzer
Cynthia Rudin
Abstract
et al., 2022; Aglin et al., 2020) including algorithms for enumerating the entire set of near-optimal decision trees (the Rashomon set; Xin et al., 2022) have garnered sub- stantial research interest. These advances have enabled new perspectives on predictive multiplicity (Marx et al., 2020; "aaison-Daniels et al., 2023) and variable importance (Dong & Rudin, 2020; Fisher et al., 2019; Donnelly al., 2023).
Decision trees are widely used for interpretable machine learning due to their clearly structured reasoning process. However, this structure belies a challenge we refer to as predictive equivalence: a given tree's decision boundary can repre- sented by many different decision trees. The pres- ence of models with identical decision boundaries but different evaluation processes makes model selection challenging. The models will have dif- ferent variable importance and behave differently in the presence of missing values, but most opti- mization procedures will arbitrarily choose one such model to return. We present boolean logi- cal representation of decision trees that does not exhibit predictive equivalence and is faithful to the underlying decision boundary. We apply our rep- resentation to several downstream machine learn- ing tasks. Using our representation, we show that decision trees are surprisingly robust to test-time missingness of feature values; we address predic- tive equivalence's impact on quantifying variable importance; and present an algorithm to opti- mize the cost of reaching predictions.
However, decision correspond not just to classifier but also particular way of evaluating the classifier. Consider the two equivalent trees in Figure 1. The two trees encode the same logical AND decision function, but they suggest different orders of querying X₁ and X2. A practitioner would typically deploy only one of these trees, but either order is equally justified.
can be misleading, because they
X1
X₂
0
X2
0
X1
1
(X1 X2)
Figure I. Two decision trees, suggesting different evaluation order, but which represent the same logical formula (X₂ A X2).
1. Introduction
This phenomenon, which we call predictive equivalence (Sober, 1996), poses several distinct challenges:
Decision trees are widely used for interpretable machine learning (Rudin et al., 2022). Their structure of discrete decisions has long been leveraged for difficult tasks such as handling missing data (Therneau et al., 1997) and measur- ing variable importance (Breiman, 1984). Recent advances in decision tree optimization (Lin et al., 2020; Demirović
(1) Decision trees imply an evaluation procedure that can get stuck on irrelevant missing information. If æı is missing and 222 O, the first tree in Figure cannot be traversed, but the second tree clearly predicts O.
(2) Tree-based variable importance metrics change across predictively equivalent trees. For example, Gini importance will suggest that D2 is more important to the first tree in Figure 1, even though this order is arbitrary.
'Equal contribution 'Department of Computer Science, Duke University, Durham, North Carolina, USA *Dpartment of Computer Science, University of British Columbia, Van- couver, BC, Canada. Correspondence to: Hayden Me- Tavish Shayden.mctavide duke.edu>>, Zachery Boner <zach- ery.boner duk...du>>
(3) Logically equivalent trees with different evaluation or- ders appear in the Rashomon set as distinct trees. This phenomenon causes some models to be over-represented in the Rashomon set, which biases some downstream tasks.
Proceedings of the 42nd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
(4) A decision tree implies a constrained order for evaluating variables, but this order may be sub-optimal when each variable has an associated cost.
Code for our algorithms and experiments can be found htt.:a....//aaadddeee//rrrriiiie equivav iquivalent

---

Leveraging Predictive Equivalence in Decision Trees
We provide representation of decision-tree classifiers that abstracts away the evaluation order. To do this, we convert decision trees into disjunctive normal form (DNF; an OR of ANDs) and reduce to a minimal set of sufficient conditions for making predictions. This representation allows us to ad- dress the above challenges: we uncover many cases where decision trees can still make predictions despite some vari- ables being missing, we make variable importance metries for trees more reliable, in the Rashomon set, and we optimize the cost of variable acquisition needed to reach a prediction using a tree.
the number of variables in the Quine-McCluskey subroutine will be small, and our algorithm for simplificatinn will be efficient despite the NP-completeness of the problem.
2.2. Applications
Variable Importance. Decision trees have been used for variable importance since at least the introduction of random forests (Breiman, 2001a). Notably, specialized metrics that quantify importance based on the reduction in impurity achieved when splitting on a particular feature have been developed to measure variable importance in decision trees (Louppe et al., 2013; Kazemitabar et al., 2017). In Section 5.1, we show that predictively identical trees can yield very different impurity reduction values.
resolve predictive equivalence
2. Related Work
2.1. Decision Trees and Simplicity
There are also metrics such as SHAP (Lundberg & Lee, 2017),, permutation importance (Breiman, 2001a; Fisher et al., 2019), conditional model reliance (Fisher et al., 2019), LOCO (Lei et al., 2018), and LIME (Ribeiro et al., 2016), that quantify variable importance based on permuting data across a particular decision boundary. These metrics invariant to predictive equivalence, because they evaluate only the decision boundary.
There a substantial body of work on decision tree learning. Greedy decision tree algorithms, such as CART (Breiman, 1984) and C5.0 (Quinlan, 2014), find decision trees in greedy top-down, recursive manner. The GOSDT algo- rithm by Lin et al. (2020), the DL8.5 algorithm by Aglin et al. (2020), and the MurTree algorithm by Demirović et al. (2022) provide methods to optimize the decision tree hypoth- esis space directly. range of other approaches also afford optimal decision trees via more general solvers (Bertsimas & Dunn, 2017; Verwer & Zhang, 2019). These algorithms can be used to find highly accurate decision trees- indeed, well-optimized single decision trees can approach the perfor- mance of decision tree ensembles (Vidal & Schiffer, 2020; McTavish et al., 2022), which are often state of the art for tabular data (Grinsztajn et al., 2022). Our representation of decision trees applies to trees discovered via any method.
Recent work examines variable importance over all models in the set of near-optimal models (Fisher et al., 2019; Dong & Rudin, 2020; Donnelly et al., 2023), i.e., the Rashomon set (Breiman, 2001b; Rudin al., 2024), rather than single model. Of particular note, the Rashomon Importance Distri- bution (RID) (Donnelly et al., 2023) demonstrated that the stability of variable importance estimates can be improved by examining the distribution of variable importances over Rashomon sets computed on bootstrapped datasets. In Sec- tion 5.2, we show that predictive equivalence within each Rashomon set confounds the practical implementation of RID, and we show how to correct this.
Our work is particularly related to the problem of expla- nation redundancy in decision trees. This concept is ex- plored by Izza et al. (2022), who demonstrate that the paths taken through the tree to reach predictions ("path explana- tions") often have redundant variables in them, which are not necessary to make the prediction. The authors present polynomial-tine time algorithms to compute suceinct path ex- planations. In contrast, minimal boolean logical representation of the entire de- cision tree, using the Quine-MMelusse 1952; McCluskey, 1956) as a subroutine. This representa- tion enables succinet path explanations of predictions for free, once the global representation is computed for some up-front cost. Our representation also enables several down- stream applications beyond prediction explanations.
Missing Data. A popular approach for dealing with miss- ing feature values is to impute them - with either a simple estimator such as the mean, or a function of the other co- variates. For background on imputation, see Shadbahr et al. (2023); Emmanuel et al. (2021); Van Buuren & Oudshoom (1999). Multiple imputation accounts for uncertainty in im- putation by combining results from several estimates (Rubin, 1988; Van Buuren & Oudshoorn, 1999; Schafer & Graham,
present method to compute
algorithm (Quine,
2002: Stekhoven & Bühlmann, 2012; Mattei & Frellsen, 2019). There is also a body of work regarding surrogate splits, a tree-specific approach which learns alternative splits to make when variable is missing (Therneau al., 1997; Breiman, 1984). Each of these approaches introduces bias when the probability of a variable being missing depends on the variable's 's underlying value, beyond what can be mod- eled by the covariates - this setting is referred to as Missing Not at Random (MNAR) (Little & Rubin, 2019). We show
A line of work on the simplicity of machine learning models shows that when data has noise in the outcomes (common on many tasks we consider in our experiments), simpler decision trees will be competitive in performance with more complicated ones (Semenova et al., 2022; 2023; Boner et al., 2024). If our decision trees have a small number of leaves,
2

---

Leveraging Predictive Equivalence in Decision Trees
that our proposed representation reveals examples whose predictions are identical under any form of imputation.
it has been shown that Q-learning will produce the opti- mal policy for given problem (Watkins, 1989; Watkins & Dayan, 1992). Since the introduction of Q-learning, the field of reinforcement learning has dramatically expanded. We refer readers to recent survey papers on the field for a more complete literature review (Shakya et al., 2023; Wang et al., 2022). However, we found that the update rule and regime proposed by (Watkins, 1989) were sufficient.
Imputation can be detrimental to prediction when missing- ness provides information about the label. There are wide range of theoretical and empirical findings supporting the need to reason explicitly on missingness in this setting (Sper- rin al., 2020; Le Morvan et al., 2021; Van Ness et al., 2023; Stempile al., 2023; McTavvsh et al., 2024). Many such approaches are tree or tree-ensemble specifie, leverag- ing the simple structure of trees (Kapelner & Bleich, 2015; Twala et al., 2008; Beaulac & Rosenthal, 2020; Therneau et al., 1997; Wang& & Feng, 2010; Chen & Guestrin, 2016). modeling requires suf- ficient observation of missingness at training time. When missingness pattern occurs only at test time, or when the missingness mechanism has distribution shift from training time (the latter setting being particularly common in medical domains, e.g., Groenwold, 2020; Sperrin et al., 2020), it is difficult to learn missingness-specifi patterns.
3. Methodology
Notation. Consider a dataset D = {(x,,, WO) where each 2, E R and yi E {0. pair is sampled i.i.d. from some unknown distribution D. For the purposes of our work, these xy's may be continuous, ordinal, categorical, or binary. We refer the jah feature of the jth sample as Zi.j. We use the notation Z.j to refer to the jth feature. We consider binary classification problems in this work, though our re- sults can be extended to multiclass classification with minor adjustments to the algorithms and theorems. We also work with binarized datasets, in which feature j of D is bina- rized into B, different binary features. For example, the feature age may be binarized into binary features age S 5, age I 10, etc. We denote the 1:th binary feature correspond- ing to feature j of the 7th sample as b/g We reserve capital letters X and Y for random variables, and we index random variables via subscripts, i.e., X,.
However, such missingness--peest
Stempfle& & Johansson (2024) propose a metric to measure how often models rely on features with missing values, and they propose a model class designed to be robust to missingness. Their scoring model MINTY uses logical disjunctions such that, if any term in disjunction is known to be true, that entire disjunction can be evaluated. This allows one variable to serve as a backup when another is missing. We show that our representation for decision trees dramatically improves the trees' performance on this metrie, without changing the decision boundary.
Given a bit-vector 0 E {0, 1),, we define the mask function m(x; 0) == (mr.) if 0, = 1; NA if 0 = 0) For con- venience, we often leave out dependence m(x:) to denote masked version of 24. Let Jm(z,) == [j]m(1;)) RJ. A completion of m(x;;) is vector z E Rd s.t. 2j m(x:)z, Vj E Jm(zz)) When discussing cost sensi- tive optimization, we denote the cost associated with each input feature Z..j as Cj.
0 and write
Cost Optimization. Many real-world problems have a cost to acquire variables- for example, ordering an MRI is expensive and time-consuming. Many types of costs have been studied (Turney, 2002), but our focus is on test cost, or the minimum cost associated with obtaining a prediction from a model. There are many cost-sensitive decision tree algorithms in the literature (Lomax& & Vadera, 2013; Costa & Pedreira, 2023). However, all of these approaches directly optimize decision tree account for these costs and use that tree top-down at test time, even if there is more cost- effective way to obtain predictions from the same tree. In contrast, we optimize the cost of evaluating predictions from a given decision tree (cost-optimal or otherwise) when some or all variables are unknown. Note that we assume each feature has a fixed cost across all samples.
3.1. Representing Trees to Resolve Predictive Equivalence
Given any decision tree T, we represent TT in a simplified disjunctive normal form (an OR of ANDs), which we denote by TONE. See Figure 2 for an example of this representation.
This approach yields a number of useful properties. re- mains globally interpretable, because we can present a sim- ple logical formula for the whole tree. The new representa- tion is still faithful to all the original predictions of the tree (Propasition 3.1). It can also make predictions whenever there is sufficient information to know the prediction on the original tree (Theorem 3.2), which we leverage later in our applications. It provides non-redundant explanations, mean- ing it does not suffer from the interpretability issues Izza et al. (2022) identify in decision trees (Proposition 3.3). It maps all predictively equivalent trees to the same form (The-
We optimize the cost of applying a decision tree by applying Q-learning (Watkins, 1989). Q-learning is model- -oree-ffree approach for policy learning that estimates the value of each action in each state by allowing an agent to explore the state space. During exploration, the reward of the j-th visited state is gradually propagated back to the (j - 1) state. Given sufficient episodes- iterations of this exploration
3

---

Leveraging Predictive Equivalence in Decision Trees
X1
Algorithm 1 Compute DNF Representation from Tree
Input: A decision tree T.
X3
X2
Output: TDNE, A minimal boolean formula in disjunctive
normal form with equivalent logical form T.
Let L be the set of leaves of the decision tree, represented by a conjunction of the variables and decisions on the path to the leaf. Denote by L+ the leaves that predict positive, and I,- the leaves that predict negative. PosErrr < VIeL+l
DNF
X2) V (-X, X3) (X) V (-X, A Xa) V (x)
BCF
Figure 2. An example of decision tree where the minimal DNF and Blake canonical forms differ. The minimal DNF of this tree deseribes the tree's behaviour with two cases. The Blake canonical form includes a third reason for predicting True, which always falls into the preceding two cases but relies different variables.
Neg + VIEL-l
SimplePos os Expr t cCCnskeyy (xps QuineMcClusker (Neg Return (SimplePol Expr, Simple Eagprr))
SimpleNeg
orem 3.4). A proof for each of these statements is provided in Appendix A.
Algorithm 2 Prediction with the DNF representation
Input: m(x)), the sample to predict; TDNF.
Output: Prediction from TDN: (0, 1 or NA)
Proposition 3.1 (Faithfulness). Consider any tree T and let x E Rd be complete sample. Then ToNr(z) (z) (xx).
for term / in TDNe-Simple Sinpleeoosss Pos Expr:
Return if known feature values from m(x) satisfy t
Theorem 3.2 (Completeness). [o))(m(())) + NA if and only for all completions 2 m(x). T(2) (m)))) Proposition 3.3 (Succinctness). Let the explanation for (z)F(z) be any term in SimplePos os Expr that is satis- fied by I when (2) = 1 (or SimpleNegh eeg when To)p(x)= = -). Then no variable in this explanation is redundant.
for term & in TDNE-Simple Simple eg Expr:
Return 0 if known feature values from m(x) satisfy t expr <- Substitute known feature values of m(x) into
TONn- Pinpsleessle
expr 4- ChunneMCCluskegeegppp
Return if expr == True
Return if expr == False
Return NA
Theorem 3.4 (Resolution of Predictive Equivalence). Deci- sion trees T and T are predictively equivalent if and only T = TowE (with equality defined by Algorithm 3)
imal sufficient conditions for positive prediction, and all possible minimal sufficient conditions for a negative predic- tion. This also corresponds to identifying all partial concept classes (Alon et al., 2022) for which the tree predicts true (resp. False). This alternative form can optionally be used to simplify the prediction logic for our DNF since it is now sufficient simply to evaluate each separate term in the DNF, without needing to do further logical simplification.
Algorithm 1 describes how we transform trees into min- imal DNF representation. This algorithm combines the positive-predicting leaves of the decision tree into an ex- pression in disjunctive normal form. This expression is then simplified with slightly modified version of the Quine- McCluskey algorithm (Quine, 1952) (see Algorithm 5) to find the minimal form of the boolean expression encoding positive predictions by the tree. We perform the same proce- dure on the prreaivii-eriiiiingg leaves to obtain a minimal boolean expression for evaluating whether the tree predicts negative. Algorithm 2 explains how this method provides predictions, with 'substitute" meaning each variable with a known value is replaced by constant (e.g., if x1,1 = 1, (r., Ax., V (-x.22 becomes (1 Axx,2) V (-xr.)) 2 = Truc). Equivalence is defined in Algorithm in Appendix B.
3.2. Datasets
We consider four datasets throughout this work and eight ad- ditional datasets in Appendix C. We refer to the primary four as COMPAS (Larson et al., 2016). Wine Quality (Cortez et al., 2009), Wisconsin (Street et al., 1993), and Coupon (Wang et al., 2017). COMPAS measures 7 features for 6,907 individuals, where labels are whether the individuals were arrested within years of being released from prison. Wine Quality reports 11 features over 6,497 wines along with a numerical quality rating between 1 and 10. We binarize these ratings into high (> 5) and low (< 5) quality classes and predict this binary rating, Wisconsin is a breast cancer dataset and contains 30 features over 569 masses, where labels designate whether the tumor was malignant or benign. Coupon measures 25 features for 12,684 individuals, and
While the basic simplified form has a number of useful properties, it does not directly afford all possible sufficient conditions for positive and negative predictions. Consider, for example, the tree in Figure 2: there are 3 sufficient condi- tions for a positive prediction, but our basic simplified form will only identify two of them. We leverage a second repre- sentation, called the Blake canonical form (Blake, 1937), to solve this problem: in Algorithm 4, we find all possible min-
4

---

Leveraging Predictive Equivalence in Decision Trees
Dataset
Total Trees
w/o Trivial
Ours
COMPAS
12785 + 3e3
3913 + 837
2135 + 448
gin 0.375
gil 0.375
samples = 100
samples- 100
Coupon
666 + 54
136 + 19
55 + 8
valus 175, 25)
value [75. 251
Wine
6936 + 700
2341 + 377
1409 + 256
Fabse
True
False
True
Wisc.
24052 + 9e3
11990 + 5e3
4637 = 2c3
ani = 0.0
gini - 0.5
X1
gni 0.0 samples = 50
gini - 0.5
X2
volue [50. 0)
samples = 50
samples - 50
value [50, 0]
semples -
value 25)
Valuee (25,
Table 1. Total number of trees, number of trees without trivial re- dundancies, and number of predictively nonequivalent trees (ours) in the Rashomon set. We abbreviate "Wine Quality" to "Wine" and "Wisconsin" to "Wisc."
False
True
False
Trua
gmn
gini
0.0
0.0 semples
samples
samples
samples 25
value [25, 0]
value [0, 25]
value [25, o]
valuo 20]
X1 Gini Importance: 0.66
Gini Importance: D.33 X2 Gini Importance: D.86
X2 Gini Importance: 0.33
labels denote whether or not the individual would accept coupon. See Appendix D.1 for complete details the preprocessing applied to each dataset.
Figure 3. Two equivalent decision trees for the setting where Y = X2X, and X2 iid Bernoulli(0.5). Although they always produce identical predictions, achieve the same objective value, and are produced by the same algorithm, these two trees produce dramatically different variable importance values. gini refers to the Gini coefficient of each leaf, samples to the number of points falling into each leaf, and value denotes the number of negative (left) and positive (right) samples in the Ieaf.
4. Quantifying Predictive Equivalence
We can directly identify predictively equivalent decision trees using Algorithm 3. We now apply these tools to the Rashomon set of decision trees, found by the TreeFARMS algorithm, to measure the prevalence of predictive equiva- lence in practice (Xin et al., 2022). The Rashomon set is de- fined as the set of all models in a hypothesis space F within e training objective of the optimal model, where the objec- tive is denoted Obj(S, D). Given an optimal model on the training data f arg min Obj(f. D), the Rashomon set is defined as:
tation revealed a substantial number of trees with identical decision logic. Appendix C.2 presents similar results across many Rashomon set parameter configurations.
5. Case Study 1: Variable Importance
RRF D) = (S E F[Obj(J D) S Obj(S", + +3).
5.1. Gini Importance
TreeFARMS uses a branch and bound algorithm with dy- namic programming to find the Rashomon set of sparse decision trees, with JF the hypothesis space of decision trees and Obj(S; D) defined as misclassification error plus con- stant penalty for each leaf in the tree (Xin et al., 2022). The algorithm maintains& a lower bound on the objective function of each possible subtree, and uses these lower bounds to prune large sections of the search space which provably cannot lead to near-optimal models.
Predictive equivalence poses an immediate challenge for variable importance methods. To demonstrate this, we con- sider the toy setting where Y X2 and X1, X2 lid. (ernoull((.5). Figure 3 presents two distinct decision trees that perfectly match this data generating process. Even in this simple case, we observe that equivalent trees can produce dramatically different variable importances when computing an impurity- such as Gini importance. The first tree claims Xo is twice as important as X2 and the second tree claims the opposite.
variable importance
We compute the Rashomon set of decision trees for the COMPAS, Coupon, Wine Quality, and Wisconsin datasets, and compare the total number of decision trees in each set to the number of unique DNF forms within each set. We use TreeFARMS (Xin et al.. 2022) with maximum depth 3 and a standard per-leaf penalty of 0.01, identifying all trees within 0.02 of the optimal training objective. TreeFARMS can optionally remove trees that are trivially equivalent to other trees in the Rashomon set (i.e., the last split along some path leads to the same prediction in both leaves), we also present the number of trees that have no such trivial splits. Going beyond trivial splits, we use our representation to identify the number of trees with unique decision logic. Table presents this measure of Rashomon set size averaged over 5 folds of each dataset. We found that our represen-
This effect becomes more pronounced with more variables. We next consider a similar data generating process with
iid. Y = I1 X, and 112 ~ Bernoulli There are 12 input variables but only variables though 10 are used in the data generation process, meaning there are unimportant variables. We greedily fit 3 predictively equivalent decision trees over the same data using different random seeds and measured the Gini importance of each variable to each tree. Figure 4 shows the distribution of importance for each variable over these trees. We observe that the importance of each variable varies widely over predictively equivalent trees. Moreover, the importance of some useful variables nearly indistinguishable from
5

---

Leveraging Predictive Equivalence in Decision Trees
Distance to Ground Truth
Gini Importance
Three Predictively Equivalent Trees
Method
X1
X2
X3
0.5
Original RID
0.120
0.136
0.232
Importance
0.4
PE Corrected RID
0.092
0.105
0.182
0.3
Table 2. The I-Wasserstein distance (Vaserstein, 1969; Kan- torovich, 1960) between the ground truth importance value (repre- sented as distribution with all weight at the single true value) and the distribution from RID with and without correcting for predic- tively equivalent trees on the synthetic case described in Section 5.2. Controlling for predictive equivalence improves the estimated importance of each variable.
0.2
0.1
0.0
Feature
Figure 4. The Gini Importance for 12 variables over 3 predictively equivalent decision trees. Here, each color represents a different tree. Even though these trees are predictively equivalent, they produce radically different variable importance values.
tance from RID with and without correcting for predictive equivalence. When predictively equivalent trees are not accounted for, RID places more weight further from ground truth on three variables.
The confounding effect of predictively equivalent trees on RID can also be observed on real data. Figure 5 shows the distribution of importance from RID before and after controlling for predictively equivalent trees for three impor- tant variables on the COMPAS dataset. While there is no known ground truth importance value to compare against here, we see that a substantial distribution shift also occurs on real data. In fact, for each variable, the two-sample Kolmogorov-Smimoo test for the equality of distributions found a significant difference between distributions for each variable with a target p-value of 0.05, with test statistics of 0.043 for age, 0.048 for juvenile crimes, and 0.059 for pri- ors count and p < 0.001 in each case. Appendix C.3 reports these values over additional datasets, and finds significant distribution shift in least one variable for every dataset except one, for which decision stump is sufficient.
the importance of the extraneous variables - c.g., X10 has importance close
5.2. Rashomon Importance Distribution
We now examine the impact of predictive equivalence on a state-of-the-art variable importance method: the Rashomon Importance Distribution (RID, Donnelly al., 2023). RID computes a stable cumulative density function (CDF) of variable importance over possible datasets using variable importance over the Rashomon set. In particular, the value of this CDF for feature j at value k (i.e., the probability that feature has importance less than or equal to k)) is computed as the expected proportion of models in the Rashomon set for which feature j has importance less than k.
RID is defined over a set of functions, meaning it expects each member of the Rashomon set to be a unique input- output mapping. In practice, however, RID operates over the Rashomon set of decision trees computed by TreeFarms (Xin et al., 2022). This set contains multiple predictively equivalent trees, which effectively places more weight on functions that can be expressed through many distinct trees and biases RID toward the variables that are important in these duplicated models. However, this bias can be removed by considering only one member of each set of predictively equivalent trees using our representation.
6. Case Study 2: Missing Data
Decision trees are regularly used in the presence of missing data because they can be easily adjusted to handle missing- ness (Therneau al., 1997). Our method allows identifica- tion of many cases where adjustments not needed.
Consider setting where data is missing from the test set, but there is no observed missingness in the training set. The standard approach is to impute missing features, but this threatens interpretability by complicating the pipeline from input data to prediction. Our representation can identify all cases where imputation is not needed across a wide range of missingness settings, avoiding this issue. Theorem 3.2 and its Corollary 6.1 establish that whenever TONE makes non- NA prediction, the prediction matches the tree's prediction under perfect oracle imputation (meaning the oracle directly provides the missing value). As per Corollary 6.2, that means we can use DNFs to handle missingness in a way that is robust to a wide range of missingness mechanisms.
To demonstrate this effect, consider the following simple data generating process (DGP). With input variables X2
(ernoulliVVO.5) and X3 (ernoulli X₂ X..005,,, let ~ (0.9) 0.05). We compute a "ground truth" variable importance value for this DGP by computing the permutation impor- lance of each variable to the model X2, = X3.
Table 2 reports the 1- W-Wasserstein distance between the ground truth importance value and the distribution of impor-
6

---

Leveraging Predictive Equivalence in Decision Trees
RID Distribution age Importance
Distribution of Javerile crimes Importance
Distribution of orfors count Importance
17.5
Original
Original Correctee
Original
Corrected ND
80
Corrected RID
15.0
12.5
Percens
Percent
30.0
30
7.5
-0
5.0
20
5
0.0
0.00
0.02
0.04
0.06
0.08
0.00
0.01
0.02
0.03
0.04
0.05
0.06 0.08
0.10
0,12
0.14
0.16
Model Rellance Value
Model Roliance Value
Mode: Rellance Value
Figure 5. The distribution of variable importance from RID for three important variables on the COMPAS dataset, with and without correcting for predictive equivalence. When adjusting for predictive equivalence (shown in orange), more probability mass is given to zero importance for age and number of juvenile crimes, while high importance values receive more probability mass for number of priors. All other variables in this dataset had all probability mass at O importance in both cases.
The only setting where we may lose information is when missingness itself is informative about the label - but in a test-time missingness setting, where we have not seen any data with missingness during training, it is not possible to train a model handle informative missingness anyway. Proofs of these corollaries are given in Appendix A.
% Samples such that CART trees can Predict without Imputation
100
COMPAS
100
Wine Quality
purs
N Predictions Proven Unaitazted
N Prodictions Unallested
80
path-based
80
60
used-festures
60
40-
40-
Corollary 6.1 (Irrelevance of Imputation). Let x E Rd. Let g R U (NA) - Ra be any imputation function. If [TNNN((((x)) + NA, then Tyy(m(z)) = Txx), which corresponds to oracle imputation.
20-
8
8.0
Wisconsin
Coupon
100
100
N Prodections Proven Unafitected
% Predictions Proven
80
80
Unartacted
Corollary 6.2 (Unbiasedness under test-time missingness). Let x E gd. When TDNF(m(x)) & N A, its predictions are an unbiased estimator for T(x) with respect to the random missingness mechanism. This holds even if the mechanism Missing Not At Random.
60-
60
8.
0.4
0.6
0.8
8.0
0.6
0.8
T.0
Mistingness per
Missingness per
Improvement 50%
Missingness per Feature:
We demonstrate empirically that decision trees rarely re- quire additional missingness handling to predict on samples with missing data. In Figure 6, we introduce synthetic miss- ingness (Missing Completely at Random) to variety of real-world datasets by independently removing each feature of each sample with probability p. Using our DNF-based prediction method, we demonstrate that decision trees can regularly predict on a substantial number of points even missing. This means decision
Compas
Wine
Wisconsin
Coupon
path features
2.4x
3.9x
2.6x
3.4x
32.8x
64.6x
28.6x
16.1x
Figure 6. Rate which decision trees can make predictions as missing values added. These results use simple CART tree, as implemented by SKLearn (Pedregosa ct al., 201 with depth and default parameters. The table shows the ratio of samples identified under our method vs the two baselines.
when many features tree's prediction is the same for most samples regardless of how practitioner handles missing data, including any choice of imputation (Corollary 6.1).
periments on more datasets and with more tree algorithms are in Appendix C.4 and Appendix E, respectively.
In Figure 6, we show trees can predict substantially more often than standard ways of determining when decision tree requires missingness handling would suggest. Since trees are ordinarily evaluated by following a path from root to leaf, the "path- "path-based" baseline reports NA when split is encountered that depends on feature of unknown value. This same approach was recently used in a study of models' reliance on missingness--peciinn logic (Stempfle & Johans- son, 2024). We also compare to function aggnosticc baseline that checks whether any feature of the model is missing. Ex-
We can extend this investigation of decision tree robustness beyond individual trees to the set of all near-optimal decision trees (the Rashomon set). We quantify how often a sample can be classified without using imputation by at least one decision tree in the Rashomon set (as found by TreeFARMS, Xin et al., 2022). We also show that when we use the best available model from the Rashomon set for each sample, we achieve comparable accuracy to the optimal model if we had not had missing data. Figure shows that a majority of
7

---

Leveraging Predictive Equivalence in Decision Trees
Propartion of non-NA Predictions and Accuracy for Selecting Rashomon Set Models Robust Missingness
with the state {a.,1 =?, =?}, purchasing x., transitions to either { 0, 2222 =?] or { 1, 2 =?]. In each episode, random row of the training dataset is selected, and the value in this row is used to determine the value of each queried feature. We restrict the actions available to the Q-learner to only include the features used in the current decision tree of interest.
COMPAS
2.4
Wine Quality
04 D11
6.8
0.9 5.6
5.4
002-
0.2 6.2
R2
0'3
Wiscorsin
3,6
Coupon
Acuniy on scomentt 2008
Reward Function. When a feature big (the h bin on the 1th feature of the 1th example) is measured, a cost of cj (i.e., reward of -c,) is incurred if there is no k' such that big has been purchased; otherwise, no cost is incurred reflect the fact that practitioner would obtain the value of the input feature, not an individual bin. If enough features are known to satisfy any clause of the Blake canonical form of a tree, a reward of Σ Cj is given, and the current episode of Q-learning is terminated.
0.0
5.0
0.4
5.2
0.
robeb Pessngmess per Halrre
hosabiit of Misingniss Feature
Accunecy tromplies
Figure 7. Rate at which at least one near-optimal tree can continue to make predictions as missing values are added, as well as ac- curacy on those predictions. These results use TreeFARMS (Xin al., 2022) with maximum depth 3 and a standard per-leaf penalty of 0.01, with an epsilon of 0.02
Q-learning generally aims to learn a num_states x num acmtaantioss matrix, indicating the quality of every ac- tion in every state. In our setting, this yields a 3 x da matrix, which is infeasible to store- this matrix would have 4.23 x 1028 entries on the largest of our datasets. We address this problem in two ways. First, we consider only "reason- able actions" actions that measure feature that is actually used in the tree, immediately ruling out any state related to measuring other features. Second, we avoid creating this large matrix by instead using a hash table that maps from state to a dg di-dimensi vector indicating the expected reward of each action in that state. This hash table is ini- tially empty; when a new state is visited during training, new de dimeennnsoa vector is added to the hash table. This procedure allows us to avoid storing information for states that are never realized - for example, if two binarized features signify age < 5 and age < 8, it is impossible for the former to be true while the latter is false.
samples can be predicted even with test-time missingness probability above 50% per feature. Note that the added ability to evaluate trees under the DNF form is built into the Rashomon set - if one tree is in the Rashomon set, all its predictively equivalent trees that are similar in sparsity and depth are also in the Rashomon set.
7. Case Study 3: Improving Cost Efficiency
When a user obtains the value for each feature in an "online setting" - -i.e., iteratively decides which feature to discover - it may be tempting to simply traverse a decision tree and purchase features in the order they are encountered. If each feature has an associated cost, this naive approach is needlessly expensive. We demonstrate that our decision tree simplification can reduce the cost of evaluating tree without changing the decision boundary at all.
We initialize our hash table using the reward obtained by directly traversing the decision tree of interest; Appendix G describes this procedure in detail. In our experiments, we run 10,000 episodes of exploration to train our Q-learner. After training, this yields a simple policy that recommends which feature to purchase in each state.
We introduce a Q-learning approach to learn the least ex- pensive way to evaluate a decision tree. If any clause in the Blake canonical form of a decision tree is satisfied, we know sufficient information to form a prediction. Thus, the goal is learn the minimum cost policy that satisfies at least one clause of this representation, yielding the following setting:
We evaluate the cost savings of this approach using the COMPAS, Wine Quality, Wisconsin, and Coupon datasets. For each dataset considered, we randomly generate an in- teger cost between 1 and 10 for each feature. We consider three purchasing policies: 1) following the BCF/Q-learning policy as outlined above, 2) purchasing features in the order suggested by traversing the tree, and 3) directly purchasing every feature in the tree. We then evaluate the average cost incurred by each policy across samples from the test dataset. We fit 50 decision trees on distinct bootstrap samples of each dataset, and perform this evaluation for each tree produced.
Each state is defined by the status of all (bina- rized) features, where each feature may be 0, 1, or unknown. With d.. := E B3 binary features, this yields 3 states. Actions: In each state, the Q-learner chooses to obtain one of the unknown features, transitioning to either the state where the measured feature is 0 or 1. For example, working
State space:
8

---

Leveraging Predictive Equivalence in Decision Trees
helpful conversations in developing Case Study 3.
Cost of Evaluating Trees Over the Test Set
40
Naive
Impact Statement
Path Based
30
Optimized
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here.
20
10
0
References
Wisconsin
Coupon
COMPAS
Wine Quality
Aglin, G., Nijssen, S., and Schaus, P. Learning optimal decision trees using caching branch-and-bound search. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 34, pp. 31 3146-3153,, 2020.
Dataset
Figure 8. The cost of evaluating tree by directly purchasing every feature in the tree (Naive), purchasing features in the order sug- gested by traversing the (Path Based), and by following our BCF/Q-llerming policy (Optimized). Error bars report standard deviation of cost 50 trees, each learned from different hoot- strap of the original dataset.
Aha, D. Tac-Tac-Tee Endgame. UCI Machine Learning Repository, 1991. DOI:
Alon, N., Hanneke, S., Holzman, R., and Moran, theory of pac learnability of partial concept classes. In 202 I IEFE 62nd Annual Symposium Foundations of Computer Science (FOCS), pp. 658-66 18-671..22 IEEE, 2022.
Figure shows the results of this evaluation over 50 trials. We find that optimizing purchases based on our repre- sentation reduces the average cost of evaluating trees on every dataset. Moreover, intelligently can dramatically reduce the cost of evaluating tree relative to the na've approach in which all features in the tree are purchased. It is important to note that this comes at no cost in terms of predictive accuracy, since the exact same decision boundary is applied in each case.
Baldi, P., Sadowski, P., and Whiteson, D. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5(1):4308, 2014.
see that purchasing features
Beaulac, C. and Rosenthal, S. BEST: decision tree
algorithm that handles missing values. Computational Statistics, (503):001-11066 2020.
Bertsimas, D. and Dunn, J. Optimal classification trees. Machine Learning, 1ea10009-880 2017.
8. Conclusion
Blake, A. Canonical expressions in Boolean algebra. PhD
We proposed a simplified boolean logical representation of decision trees that decouples the logic encoded by a decision tree from its evaluation procedure. We showed that this approach can be used to account for predictive equivalence. In several case studies, we demonstrated the practical utility achieved by our representation. Future work could analyze the group structure of decision trees, where predictive equivalence is captured by equivalence classes defined by the trees' underlying logical models. It could also explore predictive equivalence's effects on tree ensembles.
thesis, The University Chicago, 1937.
Boner, Z., Chen, H., Semenova, L., Parr, R., and Rudin, Using noise to infer aspects of simplicity without learning. In Advances In Neural Information Processing Systems, 2024.
Breiman, L. Classification and Regression Trees. Routledge, 1984.
Breiman, L. Random forests. Machine Learning, 45:5-32, 2001a.
Acknowledgments
Breiman, L. Statistical modeling: The two cultures (with comments and rejoinder by the author). Statistical Science, 16(3):199-23) 2001b.
We acknowledge funding from the National Institutes of Health under 5R01-DAR RR01-44054994, the National Science Foun- dation under award NSF 2147061, and through the Depart- ment of Energy under grant DE-SC0023194 Additionally, this material is based upon work supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE 2139754. We thank Xenia Konti for her
Chen, T. and Guestrin, C. Xgboost: A Scalable Tree Boost- ing System. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785-794, 2016.

---

Leveraging Predictive Equivalence in Decision Trees
Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, Modeling wine preferences by data mining from physic- ochemical properties. Decision Support Systems, 47(4): 547-553, 2009.
Kantorovich, L. V. Mathematical methods of organizing and planning production. Management science, 6(4):366-422, 1960.
Kapelner, A. and Bleich, J. Prediction with Missing Data via Bayesian Additive Regression Trees. Canadian Journal of Statistics, 43(2):224-239) 2015.
Costa, V. G. and Pedreira, E. Recent advances in decision trees: An updated survey. Artificial Intelligence Review, 56(5):4765-4800, 2023.
Kazemitabar, J., Amini, A., Bloniarz, A., and Talwalkar, A. S. Variable importance using decision trees. In Ad- vances in Neural Information Processing Aystems, vol- ume 30, 2017.
Demirović, E., Lukina, A., Hebrard, E., Chan, J.. Bailey, J. Leckie, C., Ramamohanarao, K., and Stuckey, P. J. Murtree: Optimal decision trees via dynamic program- ming and search. Journal of Muchine Learning Reseurch, 23(26):1-47, 2022.
Larson, J., Mattu, S., Kirchner, L., and Angwin, J. How we analyzed the compas recidivism al- gorithm. ProPublica, May 2016. URL https: / www.ppropublia.ooc wwtp/orggg/aaooee paatticeemmcchinee maachine- bias risk assessments in or criminal- sentencing.
Dong, J. and Rudin, C. Exploring the cloud of variable im- portance for the set of all good models. Nature Machine Intelligence, ((12):810-8) 824, 2020.
Donnelly, J., Katta, S., Rudin, C., and Browne, E. The Rashomon importance distribution: Getting RID of unsta- ble, single model-based variable importance. In Advances In Neural Information Processing Systems, 2023.
Le Morvan, M., Josse, J., Scornet, E., and Varoquaux, G. What's good imputation to predict with missing values? In Advances in Neural Information Processing Systems, volume 34, pp. 11530-11540, 2021.
Emmanuel, T., Maupong, T., Mpoeleng, D., Semong, T., Mphago, B., and Tabona, O. A survey missing data in machine learning. Journal of Big Data, 8(1):140, October 2021.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, J., and Wasserman, L. Distribution-Free Predictive Inference for Regression. Journal of the American Statistical Asso- ciation, 11 (1((523): 1099-1111,, 2018.
Lin, J., Zhong, C., Hu, D., Rudin, C., and Seltzer, M. Gen- eralized and scalable optimal sparse decision trees. In International Conference on Machine Learning (ICML), pp. 6150-6160. PMLR, 2020.
FICO, Google, Imperial College London, MIT, Uni- versity of Oxford, UC Irvine, and UC Berkeley. Explainable Machine Learning Challenge. https: / //comunityy..cmmmmmmmmmoomoooty/ fico.
Bachine-Leerring-chhheee
2018.
Little, R. J. and Rubin, D. B. Statistical Analysis with Missing Data, volume 793, John Wiley & Sons, 2019.
Fisher, A., Rudin, C., and Dominici, All models are wrong, but many are useful: Learning variable's impor- tance by studying an entire class of prediction models simultaneously. Journal of Machine Learning Research, 20(177):1-81, 2019.
Lomax, S. and Vadera, S. A survey of cost-sensitive decision tree induction algorithms. ACM Comput. Surv., 45(2), March 2013.
Louppe, G., Wehenkel, L., Sutera, A., and Geurts, P. Under- standing variable importances in forests of randomized trees. In Advances in Neural Information Processing Systems, volume 26, 2013.
Fisher, R. A. Iris. UCI Machine Learning Repository, 1936. DOI: https://doi.org/1..442222
Grinsztajn, L., Oyallon, E., and Varoquaux, G. Why do tree-based models still outperform deep learning on typ- ical tabular data? In Advances in Neural Information Processing Systems, volume 35, pp. 507-520, 2022.
Lundberg, S. M. and Lee, S.-I. A unified approach to inter- preting model predictions. Advances in Neural Informa- tion Processing Systems, 30, 2017.
Marx, C., Calmon, F., and Ustun, B. Predictive multiplicity in classification. In International Conference on Machine Learning (ICML), pp. 6765-6774 PMLR, 2020.
Groenwold, R. H. Informative missingness in electronic health record systems: the curse of knowing. Diagnostic and Prognostic Research, 4(1):8, 2020.
Mattei, P.-. and Frellsen, J. MIWAE: Deep Generative Modelling and Imputation of Incomplete Data Sets. In International Conference on Machine Learning (ICML), pp. 4413 PMLR, 2019.
Izza, Y., Ignatiev, A., and Marques-Sile Silva,, J. On tackling explanation redundancy in decision trees. Journal of Artificial Intelligence Research, 75:261-321 2022.
10

---

Leveraging Predictive Equivalence in Decision Trees
McCluskey, E. J. Minimization of boolean functions. The Bell System Technical Journal, 15166):141711444, 1956.
Semenova, L.,, Chen, H., Parr, R., and Rudin, C. A path simpler models starts with noise. Advances in Neural Information Processing Systems, 36, 2023.
McTavish, H., Zhong, C., Achermann, R., Karimalis, L., Chen, J., Rudin, C., and Seltzer, M. Fast sparse decision tree optimization via reference ensembles. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9604-9613, 2022.
Shadbahr, T., Roberts, M., Stanezuk, J., Gilbey, J., Teare, P., Dittmer, S., Thorpe, M., Tomé, R. V., Sala, E., Lió, P., al. The impact of imputation quality on machine learning classifiers for datasets with missing values. Com- munications Medicine, 3(1):139, 2023.
McTavish, H., Donnelly, J., Seltzer, M., and Rudin, C. In- terpretable generalized additive models for datasets with missing values. In Advances in Neural Information Pro- cessing Systems, 2024.
Shakya, A. K., Pillai, G., and Chakrabarty, Reinforcement Learning Algorithms: A Brief Survey. Expert Systems with Applications. 231: 231:120495, 2023.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V.,
Sober, E. Parsimony and predictive equivalence. Erkenntnis, 44(2):667-197, 1996.
Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
Sperrin, M., Martin, G. P., Sisk, R., and Peck, N. Missing data should be handled differently for prediction than for description or causal explanation. Journal of clinical epidemiology, 125:183-187, 2020.
Quine, W. V. The problem of simplifying truth functions. The American Mathematical Monthly, 59(8):521-531 1952.
Stekhoven, D. J. and Bühlmann, P. MissForest noon non- parametric missing value imputation for mixed-type data. Bioinformaties, 28(1): 2012.
Quinlan, J. R. C4.5: Programs for Machine Learning. Elsevier, 2014.
Stempfle, L. and Johansson, F. MINTY: Rule-based models that minimize the need for imputing features with missing values. In International Conference on Artificial Intel- ligence and Statistics (AISTATS), pp. 964-972. PMLR, 2024.
Ribeiro, M. T., Singh, S., and Guestrin, C. "Why Should Trust You?" Explaining the Predictions of Any Classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1135-11444 2016.
Stempfle, L., Panahi, A., and Johansson, F. D. Sharing pattern submodels for prediction with missing values. Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thir- leenth Symposium on Educational Advances in Artificial 2023.
Rubin, D. An Overview of Multiple Imputation. In Proceedings of the Survey Research Methods Section of the American Statistical Association, volume 79, pp. 84. Citeseer, 1988.
Intelligence,
Rudin, C., Chen, C., Chen, Z., Huang, H., Semenova, L.., and Zhong, C. Interpretable machine learning: Funda- mental principles and 10 grand challenges. Statistic Sur- veys, 16:1-85, 2022.
Street, W. N., Wolberg, W. H., and Mangasarian, O. L. Nu- clear Feature Extraction for Breast Tumor Diagnosis. In Biomedical Image Processing and Biomedical Visualiza- tion, volume 1905, pp. 861-870. SPIE, 1993.
Rudin, C., Zhong, C., Semenova, L., Seltzer, M., Parr, R., Liu, J., Katta, S., Donnelly, J., Chen, H., and Boner, Z. Amazing things come from having many good models. In Proceedings of the International Conference on Machine Learning (ICML), 2024.
Therneau, T. M., Atkinson, E. J., et al. An introduction to recursive partitioning using the rpart routines. Technical report, Technical report Mayo Foundation, 1997.
Tollenaar, N. and van der Heijden, P. G. Which Method Predicts Recidivism Best?: A Comparison of Statistical, Machine Learning and Data Mining Predictive Models. Journal of the Royal Statistical Society Series A: Statistics in Society, 176(2):565-584, 2013.
Schafer, J. L. and Graham, J. W. Missing data: Our view of the state of the art. Psychological Methods, 7(2):477, 2002.
Semenova, L., Rudin, C., and Parr, R. On the existence of simpler machine learning models. In 2022 ACM Confer- ence on Fairness, Accountability, and Transparency, pp. 1827-1858, 2022.
Turney, P. D. Types of cost in inductive concept learn- ing, 2002. URL https: http///axvvvv.. www..orgggaaa........ 0212034.

---

Leveraging Predictive Equivalence in Decision Trees
Twala, B. E., Jones, M., and Hand, D. J. Good methods for coping with missing data in decision trees. Pattern Recognition Letters, 29(7):500-556 2008.
Xin, R., Zhong, C., Chen, Z., Takagi, T., Seltzer, M., and Rudin, C. Exploring the whole Rashomon set of sparse decision trees. In Advances in Neural Information Pro- cessing Systems, volume 35, pp. 40771-1408, 2022.
Van Buuren, S. and Oudshoom, K. Flexible multivariate imputation by MICE. Leiden: TNO, 1999.
van der Linden, J., de Weerdt, M., and Demirović, E. Nec- essary and sufficient conditions for optimal decision trees using dynamic programming. Advances in Neural Infor- 2023.
mation Processing Systems,
Van Ness, M., Bosschieter, T. M., Udell, M. The Missing Indicator Method: From Low to High Dimensions. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 5004-5015, 2023.
R., and
Vaserstein, L. N. Markov processes over denumerable prod- ucts of spaces, describing large systems of automata. Problemy Peredachi Informatsii, 5(3):64-72, 1969.
Verwer, S. and Zhang, Y. Learning optimal classification trees using a binary linear program formulation. In Pro- ceedings of the AAAI Conference on Artificial Intelli- gence, volume 33, pp. 1625-1632, 2019.
Vidal, and Schiffer, M. Born-again tree ensembles. In International Conference on Machine Learning (ICML), pp. 9743-9755 PMLR, 2020.
Wang, C. and Feng, Z. Boosting with missing predictors. Biostatistics, 11(2):195-25 212, 2010.
Wang, C., Han, B., Patel, B., and Rudin, C. In Pursuit of Interpretable, Fair and Accurate Machine Learning for Criminal Recidivism Prediction. Journal of Quantitative Criminology, 3995)81 2023.
Wang. T., Rudin, C., Velez, F., Liu, Y., Klampfl, E., and MacNeille, P. A Bayesian Framework for Learning Rule Sets for Interpretable Classification. Journal of Machine Learning Research, (3770)1-37,2017
Wang, X., Wang, S., Liang, X., Zhao, D., Huang, J., Xu, X., Dai, B., and Miao, Q Deep Reinforcement Learning: A Survey. IEEE Transactions Neural Networks and Learning Systems, 35(4):5064-5078, 2022.
Watkins, C. J. and Dayan, P. Q-Learning. Machine learning, 8:279-292, 1992.
Watkins, C. J. C. H. Learning from Delayed Rewards. PhD thesis, King's College, Cambridge United Kingdom, 1989.
Danieels, J., Parkes, D. C., and Ustun, B. Predictive multiplicity in probabilistic classification. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 10306-1031 2023.
12

---

Leveraging Predictive Equivalence in Decision Trees
A. Proofs
We start with a simple lemma that is useful in showing a number of the paper's propositions.
Lemma A.l. Let T be a decision tree. Consider TINP= := (Simple Pom Expr, SimpleNeggBan Exprr) obtained from Algorithm
1. Let x E & be a complete sample. SimplePosEapr is satisfied by x if and only if 1. Likewise SimpleN eg Expr satisfied by if and only (x) = 0.
Proof. For a complete sample, we know T(x)= E {0,1}.
Denote by L* the leaves of predicting where each leaf a logical expression encoding the path from root to leaf in T. Denote Pos Papp VieL+ to be the disjunction of all leaves predicting 1.
T(x) 1 if and only if one of its positive leaves e E L+ is satisfied by Since Pos is disjunction over the leaves T, PosE is satisfied by x if and only if (xx) 1. The Muine-MeCluskey algorithm's 's output, SimplePosEapp is logically equivalent to its input Pos Expr. Thus, Simple Eapp is satisfied by æ and only if (xx) =.
Note that Expr == VeeL- is the logical complement of PosErpr, because all samples fall into exactly one leaf and all leaves are exactly one of positive or negative. Also note that because Quine-MeCluskee preserves logical equivalence, we know Simple Expr the logical complement of Simple.Ve Expr So Simple Neg Expr is satisfied by a complete sample if and only if Simple Expr is not satisfied by æ. Thus, Simple eg Expr is satisfied by æ if and only if T(x) O.
A.1. Proof of Theorem 3.2
Consider decision tree T and its corresponding minimal DNF representation TDNE- Let E Rdd be complete sample and consider an incomplete masked version m(xx). Then TTN)(m((z) 1 (resp. 0) if and only if all possible completions of m(x) are classified as (respectively 0) by T.
Proof. We proceed by cases.
Case 1: TDNE (m(x)) = N A. In this case, we will prove T does not make the same prediction on all completions of m(x). We prove this by contradiction.
Suppose that, for all completions E Rd of m(x). T(=) = ÿ. WLOG assume ý 1. Assume for contradiction that (m)))) N A. Since (m))) NA, we must have that SimplePosEEape cannot be satisfied by the variable assignments in m(x). Therefore, there must be some completion of m(x) so that PisplePosExpi is falsified by By Lemma 1, this implies T(=) = 0, but this is a contradiction since ý = 1. Thus, if (DN)(m())) NA, then T cannot make the same prediction on all completions of mx:)).
Case 2: (mxx)) * NA. Suppose WLOG (m)(m)))) = Then we know that the known variable assignments in m(x) satisfy SimplePozEzpi Pox Therefore, for any completion z of m(x), Sozp satisfied by z. Thus, by Lemma A.1, we have T T(x) ) = for all completions of m(z).
A.2. Proof of Proposition 3.1
Proposition (Faithfulness). Consider decision tree and a complete sample x. Then T(x) = (DNN(())
Proof. Consider the special case of Theorem 3.2, where m(x) = x. We have Tone(m(z)) = TTNFF()== = T(x).
A.3. Proof of Proposition 3.3
Proposition (Succinctness). Let E Rd. Assume T(x) - 10, and let the explanation for TONE(IT) (I) be any term in Simple Porprr satisfied by x if ý = 1, and any term in SimpleNeg Expr satisfied by x if ğ = O. If any term in either expression is satisfied, no variable the explanation is redundant.
Proof. WLOG assume ò = 1. Let the explanation given by ToNF(Z) be any term in Simple Porprr satisfied by x. This explanation is sufficient to guarantee that the predict algorithm (Algorithm 2) will return 1, since that algorithm returns any term in Simple Expr satisfied by x. The explanation is non-redundant because each term in the output of the
13

---

Leveraging Predictive Equivalence in Decision Trees
QuineMcCluskey algorithm is prime implicant of the input formula(Quine, 1952), and thus no subset of the literals in any term will guarantee satisfaction of the term.
A.4. Proof of Theorem 3.4
Theorem (Resolution of Predictive Equivalence), TONF TNN if and only 7 and T' are predictively equivalent.
Proof. We consider three cases: 1) the case where T and T' are not predictively equivalent: 2) the case where T and T are predictively equivalent and use exactly the same set of input features; and 3) the case where T and T' are predictively equivalent and do not use exactly the same set of input features.
First note that if and T' are not predictively equivalent, the two trees cannot be logically equivalent by the definition of predictive equivalence, As such, they cannot have the same minimal DNF form, and cannot be equivalent as defined in Algorithm 3, since
Case 1.
+ "et(('..immllePPl (osprr))sEzzrr)
Now consider the case where T and T' are predictively equivalent, and the set of features used in matches the set of features used in T'. Then truth table T' as used when simplifying T is identical to the truth table used when simplifying T'. Since Algorithm 5's output is fully determined given the truth table, we know the output is the same for both trees: that is, set(T .simplePose Popprr) set(T' simplee Posprr)) and therefore TONF TDNE.
Case 2.
Finally, we turn the case when two trees predictively equivalent and distinct set of features. In this case, the features that aren't i shared across both trees are completely irrelevant to the trees' predictions. So we know no prime implicant can contain any of those feature values. Therefore, the set of prime implicants is the same when Quine McCluskey runs on each tree.
Case 3.
We then remove the columns corresponding to features that do not occur in any prime implicant, and only preserve rows that have 0 values for all of those features. At this point, both truth tables will be the same: they will both have the same columns since the set of prime implicants is the same. They will also have the same rows in the same order: when we only consider the set of truth table rows which have 0 values for all the irrelevant features that are not in any prime implicant, these rows will have the same relative ordering across the two tables and they will both cover exactly the set of all possible assignments for features that are in at least one prime implicant.
Since the truth tables are the same and the set of prime implicants is the same, MCCll-Me gives the same output for these two trees in this case, and we will have TONP TONE-
Having covered all possible cases, we know that TONF - TINE if and only if T and T' are predictively equivalent.
A.5. Proof of Corollary 6.1
Corollary (Irrelevance of Imputation). Let x E TRd be a complete sample with an incomplete masked version m mxx). Consider a decision tree T' and its DNF representation TONE. Let a be a completion of m(x). obtained via any possible imputation method. Then, if TONN # NA, T(z) = T(x)), where T(x) corresponds to the prediction of T with Oracle imputation on m(x).
Proof. By Lemma 1, we know that TDNF = v E {0, 1} if and only T()) = ú, for all completions = of m(r). The set of all completions of m(x) includes the original values of 2, in addition any possible imputation of m(x). Therefore. for all imputations z of m(x), (=)) = ((x).
A.6. Proof of Corollary 6.2
Corollary (Unbiasedness under test-time missingness). Let e Idd be complete sample with an incomplete masked version m(x, 0) for some random missingness mask parameter 0 {0, 1]d, When (nNF(m(z, 0)) o N A, ( 0))
is an unbiased estimator over random draws of missingness for T(x). This holds even if data is Missing Not At Random.
Proof. Let 9 E {o, 1 be a random variable drawn from some unknown distribution e. Given a sample x, Theorem 6.1 tells us that when TINE can predict a non-NA value, that prediction matches the prediction of T without any missingness.
14

---

Leveraging Predictive Equivalence in Decision Trees
With this, have that (1, 0)) is an unbiased estimator of ((x) when it can make predictions:
Eg (o..0:Toonr((((300))) [DNF (m (TDN 0))] A [T())]
By Theorem 6.1
=T(x)
Expectation of constant
That is, whenever TDNF(m(x, 0)) * N A, (DNF(m 0)) is an unbiased estimator of T(x) required.
B. Algorithm Details
Algorithm 3 Equality Checking
Input: DNF: T the trees compare.
Output: True if and only if the two inputs are predictively equivalent.
Ti terms in Til ww..SiillePoolal
T2 terms in (2) Timplei Return sel(Ti) = sel(T2)
Algorithm 4 BCF
Input: T: a list of all terms in minimal DNF Tree leading specific prediction (either positive negative). (Corresponds to Blake Canonical Form)
Output: A list of all possible sufficient conditions for that specific prediction Let P be list of all pairs (q, p) of distinct terms in T
repeat
(g.p) < P.pop()
if there exists exactly one literal s.t 2 E g and -z E p then
9' + 9 (2)
p + [-)
if 0' A p' is contradiction or of Ap' E then
Continue
else
for / E T do Paappend A p t))
end for T ap A p²)
end if end if
until P = 0
15

---

Leveraging Predictive Equivalence in Decision Trees
Algorithm 5 Adjusted Quine-McCluskey (with particular processing of the data structures involved to allow for proof of
Theorem 3.4)
Input: D: a DNF equation where each variable has name feature-. for some integer j
Output: A logically equivalent DNF equation corresponding to minimal set of prime implicants.
Create truth table T for expression D, where the columns are in order of variable name j. and rows are in order of boolean
value (i.e., the first row is all variables False, then the rightmost variable True and all other variables False, and the last is all variables True)
P - all prime implicants T'
C - All columns corresponding to variables in D that are not in any prime implicant. Remove from T all rows with nonzero value in any column in C
Remove from I' all columns in C
Sort the prime implicants p E P based on the earliest-appearing row of I' that satisfies the implicant. Find and return a minimal cover deterministically given T and P. (Where cover corresponds to set of prime implicants such that all rows satisfy at least one prime implicant)
Note that removing the columns in C' and the rows with nonzero values in these columns still preserves the validity of the output. Those columns are irrelevant to whether or not any prime implicant covers any particular row, since they never occur in any prime implicant. Further, covering the rows with 0 values in those columns also corresponds to covering rows with nonzero values in those columns, so we need not consider those additional rows when computing a cover.
C. Experiments With Additional Datasets
In this section, we repeat each of the primary case studies from the main body of this work over eight additional datasets.
C.1. Overview of Additional Datasets
We consider eight additional datasets, which we refer to as Netherlands (Tollenaar & van der Heijden, 2013), Broward (Wang al., 2023), FICO (FICO et al., 2018), Spiral (McTavvis et al., 2022), Tic-Tac-Toe (Aha, 1991), and Iris Se- wwe.eesccooo//Virinnic... (Fisher, 1936). Netherlands measures 9 features for 20,000 individuals, where labels whether the individuals from the Netherlands committed another crime after being released from prison. Similarly, Broward reports 38 features from 1,955 individuals from Broward county, Florida, where labels are whether the individuals from the committed another crime after being released from prison. FICO contains 23 features from 10,459 individuals, and labels whether each individual will repay a line of credit within 2 years. In our experiments, we remove all rows from FICO that contain missing data, resulting 2,502 samples. Spiral is a synthetic dataset with features over 100 samples, where each sample is randomly drawn from one of two interweaving spirals and the features the and y coordinates of the sample. In spiral, labels indicate which spiral each sample was drawn from. Tic-Tac-Tor measures 9 features over all 958 possible games of tic-tac-toe, and labels each game as 1 if the first player won and O otherwise. The three Iris datasets - Iris Setosa, Iris Versicolor, and Iris Virginica are different tasks generated from the same multiclass classification dataset. The original Iris dataset reports features over 1 150 iris flowers, and labels each sample as Setosa, Versicolor, or Virginica. We transform this dataset into three one versus all binary classification datasets. For several appendix experiments, we also consider a ninth dataset, Higgs (Baldi et al., 2014), subsampled 1-million sample version. This dataset is too large for feasibly finding a full Rashomon set, so we only use this dataset for appendix replications of the single tree missing data results and the cost-sensitive results.
C.2. Additional Results Quantifying Predictive Equivalence
Table provides the size of the Rashomon set before and after correcting for predictive equivalence on our additional datasets. We find that, in all cases except Iris-Setosa, controlling for predictive equivalence cuts the size of the Rashomon set by at least half.
16

---

Leveraging Predictive Equivalence in Decision Trees
Dataset
Total Trees
w/o Trivial
Ours
FICO
8086 + 2202
1969 + 643
1154 + 375
Netherlands
926 + 399
265 + 111
114 + 48
Spiral
= 14
38 + 13
20 =
Tic-Tac- Tac-Toe
354 = 158
196 77
72
Iris- vis-iiigin
196 + 124
72 41
44 + 25
Iris- Versicolor
168 + 72
73 + 26
28 = 10
Iris-Setosa
2 + 0
2 2
2 - 0
Broward
4242 + 1165
1741 = 487
899 = 284
Table Total number trees, number of trees without trivial redundancies, and number predictively nonequivalent trees (ours) in the Rashomon set.
C.3. Additional Results for Case Study 1: Variable Importance
In this section, we evaluate the shift in RID when controlling for predictive equivalence across all variables from every dataset considered in this work. For each dataset and variable, we computed RID using the parameters described in Section with predictively equivalent trees included, and with but one tree from each predictively equivalent set removed. We perform Kolmogorov-Smirnoy test determine whether each pair of resulting distributions are significantly different, Tables 4 and 5 report the maximum distance between each of the two empirical distributions, well the p-value for the relevant Kolmogorov-Sminn Smiinoo test. We find that, every dataset except Iris Setosa, at least one variable exhibits significant distribution shift at < 0.05. Figures and 10 present the distribution from RID for each variable with a significant distribution shift. Note that we do not include variables that received zero importance from both methods in these tables, filtering out 148 217 total variables.
17

---

Leveraging Predictive Equivalence in Decision Trees
Dataset
Variable
Sup. Distance
p- Value
Broward
fta two year
0.01 1583
0.516924
three-year
0.037849
0,000001
one-year
0.009685
0.738680
six_month
0.009828
0.722117
p.dui
0,010082
0.692329
p.am p.arrest
0.020327
0.033135
p.misdemeanor
0.049235
0,000000
age current charge
0.006845
0.973439
age_at.first.caage
0.028369
0.000685
charges
0.025376
0.003370
p-pending.charge
0.008679
0.847098
COMPAS
age
0,043373
0.000016
priors_count
0.067886
0.000000
juvenile _riimes
0.048217
0.000001
FICO
NelFractionRevoovnnguuuddddd
0,015801
0.999146
ExternalRiskEstmmate
0,079168
0.002619
NumSatiiffcttoryTrnae Tradee
0.025707
0.867512
MSinceMossReecmmnnnexc///a
0.105930
0.000014
Iris Setosa
petal length petal width
0.085000
0.466286
0.030000
0.999992
Iris Versicolor
petal length
0.145259
0.000417
petal width
0. 0.172575
0.000013
Iris Virginica
petal length
0.079877
0.004517
petal width
0.080317
0.004225
Netherlands
> 20 previous case
0.220336
0,000000
age at first penal case
0.234413
0.000000
log of previous penal cases
0.154640
0.000000
11-20 previous case
0.156908
0.000000
Spiral
feat
0.056763
0.000218
feat2
0.046307
0.004580
Table The amount of distribution shift in RID when controlling for predictive equivalence across all datasets considered this work. We do not report results for variables that receive importance under either method. Continued in Table 5.
18

---

Leveraging Predictive Equivalence in Decision Trees
dataset_nice
ks_test_stat
ks_test_p
Tic-Tac- Tic-TecTToe
Feat5_x
0.015350
0.596928
Feat6
0.032067
0.011964
Feat8_
0.043873
0.000140
Feató
0.021761
0.188094
Feat7_x _x
0.010089
0.959806
Feat8
0.019266
0.311956
Feat5 o
0.007327
0.999217
Feat7_o
0.007696
0.998273
Feat4 x
0.125572
0.000000
Feat3_o
0.005579
0.999998
Feat3
0.010545
0.942370
Feat2_x
0.062774
0.000000
Feat2_o
0.021888
0.182977
Feat _x
0.008896
0.988349
Featl Lo
0.005991
0.999989
FeatO x
0.062457
0.000000
FeatO_o
0.017226
0.448192
Feat4_o
0.081569
0.000000
Wine Quality
alcohol
0.028608
0.002097
volatile_acidity
0.020111
0.067 145
citric acid
0.002099
1.000000
free_sulfur_dioxian
0.001559
1.000000
Wisconsin
area2
0.004952
0.902248
area3
0.011916
0.047488
loncave.points!
0.007035
0.531 103
concave.points3
0.029109
0.000000
concavity3
0.007328
0.478215
perimeter3
0.010055
0.139228
radius3
0.006122
0.705633
texturel
0.003626
0.994981
texture3
0.022322
0.000004
Table The amount of distribution shift in RID when controlling for predictive equivalence across all datasets considered in this work. We do not report results for variables that receive zero importance under either method. Continued from Table 4.
19

---

Leveraging Predictive Equivalence in Decision Trees
Rin Diertbutinn of test ze3 Importence
Rin Distriuttion of seea Importence
RID Distibution points1 importanee
70
Odginaa
Original R.D Corneteed
Originll
00
Coreeced 922
Conrected
Paccan
20
10
000000
Hocel Rellance Value
Model feliace Valun
Madel Rallance Vinu
Datribution
17.5
Originel RI
rE Comected NJ
rt Conssted I113
Drignel R.D.
20
Driginel RID PE Comocied ND
15.0
12.5
60
15
50
5.0
Model Refance Volue
Model Rcflance value
Model Rellance Value
passenger1 Importance
bution weatherd importance
Distribution couponO Importance
Original
Original R.D
Original
80
Conecctd AID
PE Conrected RIO
Conrected R.
Purart
60
Parcert
20
0.00
0.04
8.05
0.50
0.02
0.54
0.02
0.05
Model Rellance
Model Rellance
Model Rellance
neerthution ro poc? importance
RID Distributionn of coupon's Impostance
BID Dytribucionn Coffenticusel Importance
RD
Original
30
PE Corrected RID
Cormeted
Corrected
Percent
Percent
3.5
0.0
02
0.04
0.05
0.08
0.50
0.01
0.02
0.55
0.04
0.45
0.00
0.00
0,02
0.04
0.06
17.5
RID Disorbutionn of alcohel Importance
RID Ditribbttinn of ats_at_fistt charg Importano
RIO Distribution of phcchggss Importance
15.0
Comected
Cornected
Conrected
10.0
Perrent
300
7.5
20
10
8.0
0.05
0.30
5.12
0.14
0.16
0.18
6.50
0.02
0.04
0.66
0.00
0.19
0.12
0.00
0.02
0.04
0.06
6.08
0.10
Rellance
RID Distrii Eion of vdemmanor Importance
RID Distribut on of aned importante
R12 2istrit fion of three, year importente
40
20
10
0.02
6.62
0.04
5.06
0.05
0.10
0.50
0.03
0.02
0.03
0.04
0.05
0.00
0.52
0.04
0.06
0.08
Mocal Raliance Value
Modil hellance Wilue
Kodel Pasiance Value
Figure 9, Importance distribution before (in blue) and after (in orange) controlling for predictive equivalence across all variables where RID showed significant distribution shift. Continued in Figure 10.
20

---

Leveraging Predictive Equivalence in Decision Trees
Distrbbuion Extemaftiiesttaae ImportanciD Distr bution NS resnsetessthcccrrgggglllll imp
Distibutiin petal lengch Importance
Orinnd 113
Original RDD
Driginal RDD
15.0
Corrected RD
50
PE Correctedd RID
23
PE Correctee R.D
12.5
10.0
5.0
20
2.5
Model Re lance Value
Model Re lance Value
Model Reilance Value
Distribution
stribucinn length
Distribution witth
Origin RID
Original RD
Original Ni
Corrected RID
Comected RID
Corrected
3.0
0.0
0-3
0.4
0.0
Mode Rel arce Value
Model Re lance Value
Modtl Rellance Value
HVD Listribut of feats importance
HuD Distnibttion of featz importance
H122 Usstribtiin Healt importance
Original MD
Original RD
Origin
10
Correcee
3.50
0.05
3.10
0.15
0.20
0.00
0.05
5.10
0.15
6:30
0.35
0.003 8.007, 8,000 D.75
0,300 0.125 6.150
Value
Value
RE3 Decrtbuttin of Teat2 x Imporfance
RDD Dittribution of Fealt Imcortance
30
RJD Ditribittin of Testt Importance
30
40
10
0 0.000 0.025, 0,000 0.075 1.8 0.125 0.150
0.00
0.05
1.10
0.15
0.20
0.00
05
0.10
0.15
0.20
Model
RIO Diggdiuttion of Feent x imporranne
RLO Distctutionn of Foat& Imoortance
9D Distrbuttion log pocstous pepol casod Impor
50
Coreetted RD
PE Conecttd RID
FE Coneccedd RDD
0.000 0.025 0.120 0.125
0.00 Model Valua
2,86 008
0.00
Hodil
Model Itllance Value
Importanc
Grignnl RD
Orginsi RID
Driiin RID
PE Comscted RID
Consctad RD
rE Conected RID
10
00000
0.00
0.05
0.00
0.05
Mocel Relance Value
Model Ro lance Valuee
prddel Relaance Value
Figure 10. Importance distribution before (in blue) and after (in orange) controlling for predictive equivalence across all variables where RID showed significant distribution shift. Continued from Figure 9.
21

---

Leveraging Predictive Equivalence in Decision Trees
% Samples such that CART trees can Predict without Imputation
FICO
Netherlands
Spiral
% Predictions Proven Unaffected
100
% Predictions Proven
100
% Predictions Proven
100
ours
75
path-based
Unaffected
75
Unaffected
75
50
used-features
50
50
25
25
25
8.00
0.25
0.50
0.75
1.00
8.00
0.25
0.50
0.75
1.00
8.00
0.25
0.50
0.75
1.00
Tic-Tac-Toe
Iris Virginica
Iris Versicolor
% Predictions Proven
100
% Predictions Proven
100
% Predictions Proven
100
Unaffected
75
Unaffected
75
Unaffected
75
50
50
50
25
25
25
8.00
8.00
8.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
Iris Setosa
Broward General
Higgs (1M)
Predictions Proven
100
% Predictions Proven Unaffected
100
% Predictions Proven
100
Unaffected
75
Unaffected
50
25
25
8.00 0.25 0.50 0.75 1.00
8.00
0.25
0.50 0.75 1.00
8.00
0.25
0.50 0.75 1.00
Missingness Prob per Feature
Missingness Prob per Feature
Missingness Prob per Feature
Figure 11. Rate at which decision trees can make predictions as missing values are added. These results use a simple CART trec, as implemented by SKLeam (Pedregosa et al., 2011), 1), with depth 3 and default parameters.
C.4. Additional Results for Case Study 2: Missing Data
Figures 11 and 12 include results on additional datasets. Results similar the main paper figures 6 and with the exception of iris-setosa (where the tree found for each fold is usually trivial depth decision stump and exhibits no predictive equivalence).
22

---

Leveraging Predictive Equivalence in Decision Trees
C.5. Additional Results for Case Study 3: Improving Cost Efficiency
We repeat the experimental setup from Case Study 3 for each of the additional datasets over 50 trials; the results of this evaluation are presented in Figure 13. We find that combining Q-learning with our tree representation allows to improve the cost of forming a prediction every dataset but one. On the Iris Sctosa dataset, each method yields the same cost because the tree is simply a decision stump, meaning there is only one variable to purchase.
23

---

Leveraging Predictive Equivalence in Decision Trees
D. Experimental Details
D.I. Dataset Preprocessing
For Section 5.2 and Section C.3, we used the internal binarization procedure of RID (Donnelly et al., 2023), which binarizes according to Threshold Guessing from (McTavish al., 2022), using the thresholds selected based on 40 boosted decision stumps.
For the Missing Data Section, we split datasets into 5 folds, and binarized according to Threshold Guessing from (McTavish et al., 2022), using the thresholds selected based on 40 boosted decision stumps. Standard errors reported are the standard deviation across folds divided by the square root of the number of folds.
Most datasets contained no pre-existing missing data; when they did, however (for the COMPAS dataset and Coupon) we removed rows with missing data in preprocessing.
For our experiments on cost sensitive optimization, we performed quantile-based binning on each feature using two quantiles per feature (the 0.33 quantile and the 0.66 quantile).
D.2. Hyperparameter Settings
In all of our experiments with RID, we computed RID over 100 bootstrap iterations with additive Rashomon bound of 0.02, sparsity penalty of 0.02, and maximum tree depth of 3 (i.e., the depth. bound parameter set 4). Note that, when using RID, we applied a larger sparsity penalty than we did in our other experiments (0.02 instead of 0.01) because we ran into computational constraints when running RID over very large Rashomon sets. We did not include "trivial extension" in these Rashomon sets because that is the default behavior of RID.
In our missing data experiments, we decision trees using SKLearn's 's Decision Tree implementation (Pedregosa et al., 2011), with maximum depth of 3 and all other parameters left as their default values. Our Rashomon sets used depth (i.e., the heppth_bounte parameter was set to 4), additive Rashomon bound 0.02, and sparsity penalty 0.01. (we did not include trivial extensions because those irrelevant to what we were investigating; trivial extension never allows handling of additional missing data). Missingness is injected into complete datasets synthetically. For each sample, we introduced missingness independently into each binarized feature with probability [0.1, 0. 0.9]. We investigate alternative depths of sklearn and pre- neebbinarization missingness in Appendix Section E.
In our cost sensitive optimization experiments, we fit decision trees using SKLearn's Decision Tree implementation (Pedregosa al., 2011) with a maximum depth of 3, and all other parameters left their default values. our Q-learner, we used a discount factor of 0.9, a learning rate of 0.1, and exploration rate of 0.5, with each term defined in (Watkins, 1989).
24

---

Leveraging Predictive Equivalence in Decision Trees
E. Additional Missing Data Results
E.1. nre-binarization Missingness
The main paper presents results for a simple way of introducing MCAR missingness: each binary feature has an independent chance of being missing with probability p E [0. 1]. However, we might also consider MCAR missingness injected in the original feature space, pre-binarization. Here each feature is still missing with probability p. but binary features from the same original feature not independently missing they must either all be missing have none of them missing.
We reproduce the main paper's results with this alternative form of missingness in Figures 14 and 15. The number of cases where trees can still make predictions is diminished to some extent, but there remains a substantial proportion of trees completely robust to missingness, as identified with our method as opposed to the baselines, and as identified within an entire rashomon set.
E.2. Robustness to Missingness on Near-Optimal Trees
We reproduce Figure with optimal trees GOSDT (Lin et al., 2020) and dI85 (Aglin et al., 2020) in Figure 16. We find that, for each these trees, we can predict on substantially more samples than the baseline methods.
E.3. Results at different depths
Figure 17 shows results from Figure 6 across different potential depths of decision tree for sklearn. The left column corresponds to results from the main paper, with depth 3. Deeper decision trees lead to similar conclusions. Two instances COMPAS and Wine Quality did not terminate within 12 hours, so for these two datasets we used slightly relaxed version of the simplification procedure for our method (not running the Quine-Mclluskey simplification step instances with more than 8 variables), giving lower bound the number of unaffected predictions (the basclines remained unchanged).
25

---

Leveraging Predictive Equivalence in Decision Trees
F. Additional Cost Sensitive Optimization Results
F.I Cost Optimization With an Additional Baseline
In the main paper, we presented three methods of evaluating a decision tree in a cost sensitive setting: naive approach, in which every variable used by the decision tree purchased; path-bat aath-base approach, in which variables are purchased as they encountered while traversing a path in a decision tree; and our BCF based Q-learning approach, in which aim to satisfy clause in the BCF of the tree as cheaply as possible. Here, we aim disentangle how much of the observed gain in cost efficacy was due to the Q-learning approach, and how much could be directly obtained through the BCF.
To do so, we introduce another method to our cost-sensitive evaluation in which we iteratively purchase the cheapest unknown feature used by the tree, and check whether any clause in the BCF has been satisfied. This approach leverages the early stopping enabled by BCF, but follows a simple heuristic instead of a learned policy. We refer to this approach as "Greedy".
Figure 18 presents the results of this evaluation across all datasets considered. We observe that, expected, our Q-learning based approach achieves equal better performance than this baseline every dataset. We also observe that this greedy approach sometimes obtains substantially better performance than path-based traversal, but is very inconsistent in some cases, it is almost as inefficient as the naive baseline. As such, we conclude that the Q-learning component of our approach is necessary to reliably reduce cost.
F.2 Hyperparameter Analysis for Q-Learning
In the main paper. we presented the cost of traversing trees using our BCF based Q-learning approach with one particular set of hyperparameters. Here, we aim to evaluate the sensitivity of these results to our hyperparameter selection.
Across the four primary datasets evaluated in the main paper, we consider three different settings for three important hyperparameters: alpha, gamma, and the exploration rate. Figure 19 presents the results of this evaluation. We observe that, across reasonable hyperparameter settings, our BCF Q-learning framework produces almost identical results. This suggests that the method is in fact converging, and our analysis is not substantially impacted by the hyperparameters we chose.
E3. Cost Optimization on Cost-Optimal Trees
When evaluating our cost optimization approach, we have primarily considered decision trees that were optimized for predictive accuracy alone. Here, we instead start with cost-optimal decision trees as produced by STreeD (van der Linden et al., 2023). We consider the same evaluation methods and datasets as in prior experiments.
Figure 20 shows the results of this evaluation across different levels of priority given to cost minimization. We find that our Q-learning approach never produces a substantial increase evaluation cost, although in some settings we observe a very slight increase.
Surprisingly, we also observe cases (e.g., Wine Quality, Wisconsin, and Iris Virginica for weight 0.0001) where evaluate "cost-optimal" decision tree in cheaper way than directly traversing the tree. This reveals interesting nuance. The trees produced by (van der Linden et al., 2023) are guaranteed to be optimal with respect to a given cost-accuracy tradeoff, where cost corresponds to the cost of variables when predicting with a tree from the top down, and trees are subject to depth and sparsity constraints. These constraints are used to ensure the classifier can be represented as an interpretable, small tree, and help with computation time. However, a given tree can have predictively equivalent forms that are deeper and/or less sparse, but yield lower average cost. In effect, our Q-learning framework allows us to use one predictively equivalent form communicate the tree simply, and less-constrained predictively equivalent evaluation procedure for the tree that is completely faithful to the other form while being more cost-effective.
26

---

Leveraging Predictive Equivalence in Decision Trees
G. Detailed Description of Q-learner Initialization
this section, we describe how we use direct traversal the target decision tree to initialize our Q-learner. Algorithm provides pseudo-code describing the procedure; at high level, we recursively traverse the decision tree until a leaf is reached. We pay the cost of each feature purchased along the way, and compute the reward given node as the weighted average of the reward of that node's two child nodes, where the weight is determined by the empirical probability of taking each path across the training dataset.
Algorithm Initialization Q-Learner Using Path Traversal
Input: T, the tree to optimize for cost; D, the training split of the dataset; Q, the (empty) hash table for our Q-learner; the reward given when prediction is possible; d, the number of possible actions.
function initialize(Teur- Dear, state)
if Teur is a leaf node then return
else
+- next split
De t subset of Deur where i 0
+ proportion of Deur where I. =0
state, + copy of state with feature set to
r -e
D2, state,)
D, subset of Dear where F...
Pr proportion of Deur where I. = state, t- copy of state with feature j set to 1
+ initialize(Teur-ri Teew-right..subree. D,, state,)
f Pett + p,r, - cjst(j)
Q[state] t 0 Rd
[state]] [i]
return end if end function
state < initial state with all features unknown
initialize(T, D, state)
27

---

Leveraging Predictive Equivalence in Decision Trees
Proportion of non-NA Predictions and Accuracy for Selecting Rset Models Robust to Missingness
FICO
Netherlands
Spiral
1.0
1.0
1.0
1.0
1.0
Proce retn Robust Predictions
Acturacy on Incomplete Data
Propertion Bobust Predictions
0.8
0.8
0.8-
0.8
0.8
0.8
0.6
0.0.0
0.2
100
0.0
0.2
0.4
0.6
1000
0.6
0.0
1.0
Probebillty Missingness per Fealure
Virginica
1.0
1.0
1.0
1.0
1.0
1.0
Ploce riinn Robuzt Predictions
Accuracy on Incomplete Data
Propertion ritonion Robust Predicions
0.8
0.8
0.8-
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.000
0.2
0.4
0.6
0.8
10
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.0
1.0
0.0
Probebility of Missingness Feature
Probsbility of Missingness per Feature
Probabiliyy of Missingness per Feature
Iris Setosa
Broward General
1.0
propertion Robust Preditions
Accuracy Incompplete Data
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.4-
0.4
0.4
0,4
0.4-
0.2-
0.2
0.2
0.2
0.0:
0.0
0.2
0.4
0.6
0'8
1.0
.0.0
0.04
0.2
0'4
0.6
100
0
0.2
0'4
0'6
0.0
1.0
Probebility Missingness Feature
Probability of Missingness Feature
Proportion Predictions
Accuracy on Incompiete data
Figure 12. Rate at which at least one near-optimal tree can continue to make predictions as missing values are added, as well as accuracy those predictions. These results use TreeFARMS (Xin al., 2022) with maximum depth and standard per-leaf penalty of 0.01, finding all trees within 0.02 of the optimal objective.
28

---

Leveraging Predictive Equivalence in Decision Trees
Cost of Evaluating Trees Over the Test Set
40
Method
35
Naive
Path Based
30
Optimized
25
Cost
20
15
10
0
Netherlands
Broward General 2Y
Higgs
Iris Setosa
Iris Versicolor
Iris Virginica
Spiral
Tic-Tac-Toe
Fico Complete
Dataset
Figure 13. The cost of evaluating by directly purchasing every variahle in the tree (Naive), purchasing variables in the order suggested by traversing the tree (Path Based), and by following our BCF/Q-leaming policy (Optimized). Error bars report standard deviation of over trees, each learned from a different bootstrap of the original dataset.
29

---

Leveraging Predictive Equivalence in Decision Trees
% Samples such that CART trees can Predict without Imputation
COMPAS
Wine Quality
100
100
% Predictions Proven Unaffected
% Predictions Proven
ours
80
80
path-based used-features
Unaffected
60
60
40
40
20
20
8.0
8.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Wisconsin
Coupon
100
100
% Predictions Proven Unaffected
% Predictions Proven Unaffected
80
80
60
60
40
40
20
20
8.0
8.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Missingness Prob per Feature
Missingness Prob per Feature
Figure 14. Rate at which decision trees can make predictions as missing values are added pre- nre-binarization. These results use simple CART tree, implemented by SKLearn (Pedregosa et al., 2011), with depth default parameters.
30

---

Leveraging Predictive Equivalence in Decision Trees
Proportion of non-NA Predictions and Accuracy for Selecting Rset Models Robust to Missingness
COMPAS
Wine Quality
Proportion Robust Predictions
1.0
1.0
1.0
1.0
Accuracy Incomplete Data
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Wisconsin
Coupon
Proportion Robust Predictions
1.0
Accuracy Incomplete Data
0.8
0.8
0.8
0.8
0.6
0.6
0.6
0.6
0.4
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Probability of Missingness per Feature
Probability of Missingness per Feature
Proportion Robust Predictions
Accuracy on Incomplete data
Figure 15. Rate which at least near-optimal tree continue to make predictions missing values added pre-binarization. These results use TreeFARMS (Xin et al., 2022) with maximum depth and a standard per-leaf penalty 0.01, finding all trees with objective within 0.02 of optimal.
31

---

Leveraging Predictive Equivalence in Decision Trees
% Predictions Completely Robust to Missingness
COMPAS sklearn
COMPAS gosdt
COMPAS dI85
100
Unaffected
path-
Predictions
used-feature
40
20
8.0
0.2
0.4
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Wine Quality skleam
Wine Quality gosdt
Wine Quality dl85
100
Predictions Proven Unaffected
20
8.0
0.4
0.8
0.0
0.4
0.8
0.2
0.6
1.0
Wisconsin sklearn
Wisconsin gosdt
Wisconsin dI85
100
% Predictions Proven
80
Unaffected
60
20
0.0
0.4
0.8
1.0
0.2
0.4
0.8
0.2
0.4
0.6
0.8
1.0
Coupon skleam
Coupon gosdt
Coupon dl85
100
% Predictions Proven Unaffected
80
60
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Missingness Prob per Feature
Missingness Prob per Feature
Missingness Prob per Feature
Figure 16. Rate which decision trees make predictions. These results simple CART tree, implemented by SKT.eam (Pedregosa et al., 2011), with depth 3 and default parameters, a simple GOSDT tree (Lin al., 2020) with depth 3 and per- penalty 0.01, and simple dI85 tree (Aglin al., 2020) with depth 3 and default parameters.
32

---

Leveraging Predictive Equivalence in Decision Trees
% Predictions Completely Robust to Missingness
COMPAS sklearn depth 3
COMPAS sklearn depth 4
COMPAS sklearn depth 5
100
% Predictions Proven
Unaffected
80
path-based
used-features
40
20
8.0
0.4
0.4
0.6
0.2
0.6
1.0
Wine Quality sklearn depth
Wine Quality sklearn depth 4
Wine Quality sklearn depth
100
% Predictions Proven
80
Unaffected
60
20
8.0
0.2
0.4
0.6
0.8
1.0
0.0
0.4
0.6
0.8
0.2
0.4
0.6
0.8
1.0
Wisconsin skleam depth
Wisconsin skleam depth 4
Wisconsin skleam depth 5
100
% Predictions Proven Unaffected
80
60
8.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Coupon sklearn depth 3
Coupon sklearn depth 4
Coupon sklearn depth 5
100
Predictions Proven Unaffected
80
60
40
20
8.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Missingness Prob per Feature
Missingness per Feature
Missingness Prob per Feature
Figure 17. Rate at which decision trees can make predictions across decision tree depths. These results use a simple CART tree, as implemented by SKLeam (Pedregosa al., 2011), with depth 3, 4, or and default parameters.
33

---

Leveraging Predictive Equivalence in Decision Trees
Cost of Evaluating Trees Over the Test Set
40
Naive
Path Based
35
Optimized
30
Greedy
25
Cost
20
15
10
5
0
Coupon
Wine Quality
COMPAS
Wisconsin
Broward General 2Y
Fico Complete
Iris Versicolor
Iris Virginica
Spiral
Tic-Tac-Toe
Netherlands
Iris Setosa
Dataset
Figure 18. The cost of evaluating tree by directly purchasing every feature the (Naive), purchasing features the order suggested by traversing the tree (Path Based), following our BCF//-learming policy (Optimized), and by greedily purchasing the cheapest feature used by the tree until clause in the BCF satisfied (Greedy). Error bars report standard deviation of cost over 50 trees, each learned from different bootstrap of the original dataset.
34

---

Leveraging Predictive Equivalence in Decision Trees
Effect of Hyperparameter Choice on Q-Learning Performance
gamma 0.75
gamma 0.9
gamma 0.95
Coupon
Wisconsin
Exploration Rate
0.3
0.5
0.7
Wine Quality
Cost
COMPAS
0.05
0.05
alpha
alpha
alpha
Figure 19. The cost of evaluating a tree by following our BCFFQ- policy under different Q Q-learning hyperparameters. Each row corresponds to different dataset, each column different value for gamma, each grouping along the axis different value of alpha, and each color different exploration rate. Error bars report standard deviation of cost over 50 trees, each leamed from a different bootstrap of the original dataset.
35

---

Leveraging Predictive Equivalence in Decision Trees
Weight
Weight on
cost
Weight Cost 0.001
Weight on Cost 0.01
Path Based
30
Optimized Greedy
Cost.
20
10
Weight Cost
Weight
Cost
Wine Quality
COMPAS
Broward General
Wisconsin
Fico Complete
Fit Setena
iris versfkolor
the Wrginica
Spiaal
Hetherlards
Coupan
Higge
Quality
COMPAS
Broward General
Wisconsin
Rico Complete
ris Satosa
irts Versicalar
Virgnica
Spiral
Thc Eat
Notheriandd Fands
Coupon
Higge
Dataset
Dataset
Figure 20. The cost of evaluating cost-optimal tree under different weightings by directly purchasing every feature in the tree (Naive), purchasing fcatures in the order suggested by traversing the tree (Path Based), following our BCF/Q-lcarnng policy (Optimized), and by greedily purchasing the cheapest feature used by the until clause in the BCF satisfied (Greedy). Error hars report standard deviation of cost over 50 trees, each learned from a different bootstrap of the original dataset.
36


Reviews:
[{"review_id": "wwTdjXVIVb", "reviewer": "Reviewer_Nmzb", "summary": "The paper addresses the challenge of predictive equivalence in decision trees, where multiple trees with identical decision boundaries but different evaluation processes complicate model selection. To resolve this, the authors propose a Boolean logical representation of decision trees that eliminates predictive equivalence, ensuring faithfulness to the underlying decision boundary, and demonstrate its applications to robustness under missing feature values, variable importance quantification, and prediction cost optimization.", "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 the review! We are glad that you appreciated our theory, experiments, and motivation. We would be happy to engage in further discussion on the modernity of our work. We interpreted Weakness 1 as saying that research on decision trees is outdated -- if we misunderstood the weakness, please correct us.\n\nWhile decision trees have long been established as a type of machine learning model, their study is still relevant. Recent advances in both theory (see [1] for the existence of competitive simple models) and practice (see [2] for advances in decision tree optimization) have shown that, for many datasets, a single decision tree can achieve state-of-the-art performance. In addition, thanks to recent progress in both computing and in algorithms research, decision trees are now one of the few model classes for which study of the entire Rashomon set is possible [3]. \n\nThe problem of predictive equivalence is relevant in modern decision tree literature. Predictive equivalence occurs in any model that is built upon decision trees, including random forests and boosting models, meaning the findings in this paper apply to a wide class of models.  In our response to reviewer AgS4, we discuss a recent paper that found that modern tree optimization algorithms often construct trees with redundant path explanations, which we show are related to predictive equivalence. Predictive equivalence is also relevant for modern Rashomon set research - see section 4, where we show predictive equivalence is rampant throughout the Rashomon set, and section 5.2, where we explore the implications on a variable importance task that leverages the Rashomon set.\n\n**The Group Structure of Decision Trees**\n\nOur approach defines a natural equivalence relation, characterized by identical logical formulae, for decision trees. This relation identifies when two or more trees are predictively equivalent, but we know of no efficient way to enumerate every predictively equivalent form of a given tree. If we knew the operations that could be performed on a tree to generate all the other trees in its equivalence class, we could materialize all (non-trivial) predictively equivalent trees to a particular tree. As a byproduct, this would improve the efficiency of our cost optimization approach (see our response to Reviewer 1yAS).\n\n**Random Forests**\n\nOur approach focuses on the ramifications of predictive equivalence for individual trees. Future work could explore the consequences of predictive equivalence on ensembles. The simplest approaches for this might involve exploring predictive equivalence for each component tree, and investigating how costs, robustness to missing data, and variable importance change across different versions of the same ensemble, where individual trees are replaced with predictively equivalent alternatives. There's also a possibility to explore the random forest as a single large decision tree (see, for example, [4]) to identify additional predictive equivalence beyond what can be observed by equivalence of individual component trees. These single trees can contain hundreds of nodes, however, so analyzing the entire tree all at once would require innovations in scalability as a part of future work.\n\n[1] Semenova, L., Rudin, C., and Parr, R. On the existence of\nsimpler machine learning models. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp.\n1827–1858, 2022.\n\n[2] Costa, V.G., Pedreira, C.E. Recent advances in decision trees: an updated survey. Artif Intell Rev 56, 4765–4800 (2023). https://doi.org/10.1007/s10462-022-10275-5\n\n[3] Xin, R., Zhong, C., Chen, Z., Takagi, T., Seltzer, M., \\& Rudin, C. (2022). Exploring the whole rashomon set of sparse decision trees. Advances in neural information processing systems, 35, 14071-14084.\n\n[4] Vidal, T., Schiffer, M. Born-again tree ensembles. International Conference on Machine Learning. PMLR, 2020. https://arxiv.org/abs/2003.11132", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I have reviewed all the theorems in Section 3.1, and I believe they are both profound and meaningful.", "experimental_designs_or_analyses": "I have reviewed the first two case studies, and I believe they are valid.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strength: The theoretical and experimental work in this paper is comprehensive, the motivation is clear, and it meets the theoretical standards expected of an ICML paper.\n\nWeaknesses：\n1.The research problem addressed in the paper is somewhat outdated.\n\n2. I would like to ask how the method proposed in this work and the methods discussed in the future outlook, such as the group structure of decision trees and forest methods like random forests, differ from each other.\nf the author provides a good answer to this question, I would be willing to raise my score.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please refer to the secion of the Weaknesses.", "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": "M1aVztDizg", "reviewer": "Reviewer_fcd7", "summary": "The authors propose the use of a minimal Boolean formula as a DNF in order to represent a decision tree that has been learnt.  This representation is useful for the authors, as one no longer requires the evaluation of the learnt function to happen in a top-down manner (i.e., start from the root node of the tree and proceed all the way down to some leaf).  A consequence that is investigated in the paper, is how this new representation can help with missing attribute values.  Another point of investigation is in terms of explainability, where it is shown that different trees that are predictively equivalent may indicate very different attributes as being the most important ones.  Finally, there can also be applications of the DNF representation to cost-sensitive applications.  The authors provide some theoretical results early on that justify the faithfulness, completeness, succinctness of the proposed DNF form with respect to some decision tree, as well as a theorem explaining that structurally different decision trees that are nevertheless predictively equivalent to will have the same minimal DNF form.  Near the end of the paper, the effectiveness of the proposed method is investigated using four different data sets: COMPAS, wine quality, Wisconsin, and Coupon.", "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 the thorough and thoughtful review and for the suggested additions in describing the\nRashomon set and TreeFARMS. If accepted, we will use our extra page to incorporate this discussion into\nthe camera-ready version. Thank you also for flagging the off-by-one typo in lines 258-259, and the need to\nclarify figure 3.\n\n**Q1. Evaluating a DNF with Missing Values** \n\nWhen we have a sample with missing values, we substitute all known values from that sample into our DNF formula. If a term in either the positive or negative DNF is satisfied, we return 1 or 0, resp. If not, then we simplify the expression again and check if it simplifies to 1 or 0. For the example in question, if $X_1$ is unknown and $X_2 = 0$ (or vice versa), then one of the forms of the tree will be unable to predict with the usual path-based evaluation method. However, substitution into the DNF expression gives $X_1 \\land X_2 \\to X_1 \\land 0 \\to 0$. Alternatively, if $X_1$ is unknown, and $X_2 = 1$, then substitution yields $X_1 \\land 1 = X_1$, and we know that no predictively equivalent form of the tree will be able to make a prediction without knowing $X_1$.\nIt is easy to see this in our toy example, but in more complicated trees this phenomenon can be much harder to identify without our approach.", "claims_and_evidence": "Yes, to the extent that I checked, the claims are adequately supported by convincing evidence; be it theorems or experiments.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria make sense.  They are actually pretty standard.", "theoretical_claims": "The proofs of the theorems are in the appendix.  In all honesty I did not thoroughly check the proofs.  The reason is that all these results should be known for perhaps 40+ years now (i.e., since the beginning of decision-tree theory.  The authors are basically saying that any decision tree can be represented in DNF form and argue about this in three different theorems (faithfulness, completeness, succinctness).  For example, this is discussed in a book from the 90's (Machine Learning, by Tom Mitchell).  As for the other result on having a unique minimal description of a DNF that corresponds to two predictively equivalent trees; well, this should also be known for 40+ years in the context of Boolean functions.  I appreciate the exposition of these results in the paper, as well as the fact that the proofs are stated in the appendix, but there is no surprise here and most likely no new result that has not been known for four decades now.  Nevertheless, again, there is merit that these results are part of the paper, and they should stay.", "experimental_designs_or_analyses": "I did go through the experiments as these are described in the paper.  The results seem very intuitive to me and along the lines of what I would expect to see.", "relation_to_broader_scientific_literature": "I appreciate the insights that are gained for situations where we have missing data as well as the insights in terms of which attributes are important for explainability concerns.", "essential_references_not_discussed": "I cannot think of something.  I think the authors have done a good job citing existing literature.", "other_strengths_and_weaknesses": "As mentioned above, I do not believe that this paper is offering any new theoretical insights.  However, the experimental part does provide substantial new information (to the extent that I know) and the insights on missing attribute values, the importance of various attributes to be more robust, and the use of the ideas in situations where we have different costs in order to obtain attribute values, are all very important in the real world and therefore the paper has a lot of merit.  Furthermore, the presence of known theoretical results allows someone to appreciate better the content of the paper (I am one of them).", "other_comments_or_suggestions": "I think the authors have done a good job writing a good paper.  Nevertheless, some part of the paper can be improved.\n\n1. The Rashomon set is never defined.  It should be defined somewhere in the text.\n\n2. Along these lines, I believe TreeFARMS is being used in order for the authors to be able to argue about the Rashomon set.  Hence, I would personally prefer to see a small paragraph describing the mechanics of TreeFARMS, so that it is easy for everyone to understand what is happening without too much effort.\n\n3. Lines 258-259: X_0, X_1 -> X_1, X_2\n\n4. Figure 3: Please describe the information that what we see in each node.", "questions_for_authors": "Q1.  One of the issues that is presented near the beginning of the paper explains how two structurally different trees that are equivalent w.r.t. the function that they compute may give rise to situations where one of them is able to process an instance with missing values, while the other one may not.  This is due to the order by which one evaluates attributes from root to a leaf.  What is not clear to me is how a DNF formula that is equivalent with both of the above trees would not have such an issue.  Can you please clarify?", "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": "tlv3QZpWXz", "reviewer": "Reviewer_AgS4", "summary": "This paper addresses the issue of \"predictive equivalence\" in decision trees, where different tree structures can represent the same decision boundary but imply different evaluation procedures.  The authors propose a boolean logical representation using Disjunctive Normal Form (DNF) to abstract away the evaluation order and provide a representation faithful to the underlying decision boundary.  They demonstrate the utility of this representation in handling missing data, quantifying variable importance, and optimizing the cost of reaching predictions.", "questions": "", "limitations": "", "rating": 4, "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 your thoughtful and thorough review! We hope that the comments below address your concerns.\n\n**Complexity of Algorithm 1 and Quine-McCluskey**\n\nThe DNF simplification problem solved by the Quine-McCluskey algorithm is NP-Complete in the number of variables used by the tree. Since trees never split on the same binary variable twice in a path from root to leaf, our problem is NP-Hard in tree depth (a tree of depth $d$ can split on between $d$ and $2^d-1$ features). The DNF transformation is applied to trees that have already been fit, so the complexity of the transformation depends only on the size of the tree, not the size of the dataset.\n\nWe do not mind this worst-case runtime (DNF simplifications were very fast in our experiments), because decision trees are often favored in practical problems that are noisy and for which data is not abundant. In this scenario, prior work has shown that simpler decision trees are near optimal (see the end of Section 2.1 in our paper), so in this situation we are solving small instances of the DNF simplification problem. If accepted, we will use the extra page to further elaborate on the computational complexity of our algorithms as it relates to the practical problems we seek to address.\n\n**Alternative Tree Simplification Methods**\n\nIt is important to note that our method applies to decision trees found via any algorithm, even those which inherently regularize or otherwise simplify trees. Izza et al. ([1]) enumerated many decision trees from textbooks and research papers exhibiting explanation redundancy, and thus predictive equivalence (see Proposition 3.3 in our paper). Some of these trees were found with methods that regularize or simplify trees as part of an optimization objective, yet they still exhibited predictive equivalence. \nIn our experiments with the Rashomon set of sparsity-regularized decision trees, we found many predictively equivalent models, even though all models in the Rashomon set were quite simple.\nThus, the conclusions of our experiments likely wouldn't be affected by changing the method of decision tree optimization.\n\nWhile alternative post-processing approaches could be applied to simplify a given decision tree (e.g., specialized pruning), we are unaware of any such approach that is guaranteed to produce a predictively equivalent tree. As such, these methods are not solving the same problem as ours.\n\n**Random Forests**\n\nYes, the proposed representation could absolutely be extended to ensemble methods such as random forests! See our response to Reviewer Nmzb for details.\n\n**Binary Decision Diagrams**\n\nWhile exploring methods to resolve predictive equivalence, we did not see a particular benefit to using binary decision diagrams over our chosen DNF representation. It is NP-Hard to find the variable ordering leading to the simplest BDD, which we would need to find in order to fully resolve predictive equivalence. Thus, BDDs do not offer us a direct computational advantage over the Quine McCluskey algorithm. We also feel that it is easier to interpret a DNF's terms as 'reasons' to predictive positive than it is to understand a tree's predictive behavior from a BDD.\n\n**Dataset Size**\n\nWe've extended the results in figures 6 and 8 to a one million sample version of the Higgs dataset (https://www.openml.org/search?type=data&sort=runs&id=42769&status=active). The results are similar to those of other datasets in our paper and can be found here: https://docs.google.com/document/d/e/2PACX-1vR-i5kxlIeEK1tBIBFqXOcxhHaXqs6WQPTmjzRv7iIaNy90zevAiX8YawK2ICib0cu-tX6uG9SQdqCM/pub.\n\nWe would also like to note that two of the further datasets in our appendix -- Netherlands and FICO -- each have more than 10,000 training samples and are from real-world industry (FICO) or government (Netherlands) settings.\n\n**Hyperparameter Sensitivity of Q-learning**\n\nThank you for this suggestion. We performed a sweep over reasonable values for the key hyperparameters in the Q-learning framework, the results of which can be seen by following https://docs.google.com/document/d/e/2PACX-1vRCgUtuqu7AX9sOjM6AOXzj0ieyNe-krvzoj9048Wb-SkbH6-n3dZQOIQ3bPksGgRelMC77gqY96MSO/pub. We find that our Q-learning approach yields similar evaluation costs to the values reported in the main paper across 27 different hyperparameter settings.\n\n[1] Izza, Y., Ignatiev, A., and Marques-Silva, J. On tackling\nexplanation redundancy in decision trees. Journal of\nArtificial Intelligence Research, 75:261–321, 2022.", "claims_and_evidence": "The claims in the submission are generally well-supported by clear and convincing evidence. The paper provides theoretical proofs in the appendix to support its claims.  Empirical evidence is provided through experiments on multiple datasets.", "methods_and_evaluation_criteria": "The proposed method of converting decision trees into DNF and using the Quine-McCluskey algorithm for simplification is appropriate for addressing the problem of predictive equivalence.  The evaluation criteria, including experiments on real-world datasets and comparisons with baseline methods, are sound and suitable for demonstrating the effectiveness of the proposed representation.", "theoretical_claims": "The paper includes several theoretical claims, such as the faithfulness of the DNF simplified form, completeness, succinctness, and resolution of predictive equivalence.  The correctness of the proofs for these claims was checked, and no issues were identified.", "experimental_designs_or_analyses": "The experimental setup is well-designed, with comparisons across multiple datasets and tasks. However, some limitations exist:\n\n- The datasets used, while diverse, are relatively small. A study on larger datasets (e.g., industry-scale data) would be valuable.\n- The method is compared primarily against baseline decision tree methods but lacks comparisons with other approaches that attempt to regularize or simplify decision trees.\n- Sensitivity analysis on hyperparameters (e.g., Q-learning settings) is missing and could provide deeper insights into practical deployment.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-related to the broader scientific literature. The authors discuss prior work on decision tree learning, variable importance, missing data, and cost optimization.  They clearly articulate how their work builds upon and extends previous research in the field.", "essential_references_not_discussed": "The paper adequately discusses relevant prior work. No essential references were identified that are not currently cited or discussed in the paper.", "other_strengths_and_weaknesses": "Strengths:\n* The paper is well-written and clearly explains the problem of predictive equivalence in decision trees.    \n* The proposed DNF representation is a novel and effective approach to address this problem.    \n* The paper provides strong theoretical and empirical evidence to support its claims.    \n* Applications of the proposed representation to missing data, variable importance, and cost optimization are relevant and well-demonstrated.\n\nWeaknesses:\n* The computational feasibility of the approach for deep trees is not discussed in depth.\n* Comparisons with alternative tree simplification methods are missing.", "other_comments_or_suggestions": "It would be beneficial to provide a more detailed discussion of the computational complexity of Algorithm 1 and the Quine-McCluskey algorithm, especially in relation to the size and depth of the input decision tree.", "questions_for_authors": "* How does the computational complexity of the DNF transformation scale with tree depth and dataset size?\n* Could the proposed representation be extended to ensemble methods like random forests?\n* How does the method compare to approaches using Binary Decision Diagrams (BDDs)?", "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": "JqaYtit5yz", "reviewer": "Reviewer_1yAS", "summary": "The paper presents an intuitive boolean logical representation of decision trees. This representation removes predictive equivalence. They then show in 3 settings (feature importance, missing data, and improving cost efficiency) that this representation can yield improvements over standard tree representations.", "questions": "", "limitations": "", "rating": 4, "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 your review! We are glad that you appreciated the novelty of our method through our experimental results. \n\nTo answer your question, we are unaware of any substantially simpler procedure to improve cost efficiency. Naïvely, we could attempt to perfectly fit an optimal, cost sensitive decision tree to a version of the dataset in which the labels were replaced with predictions from our reference tree. However, to preserve predictive equivalence over all possible inputs, we would need to exactly fit to a version of the dataset that realized every possible set of input features, which could be prohibitively large (for binary data, $2^{\\\\# \\\\textrm{features}}$).\n\nWe felt that the problem naturally lent itself to representation as a Markov decision process (MDP). While it is not viable to directly solve this MDP because of the extremely large state space, there are a number of alternative approaches to solving MDPs that could be considered, although we see none as notably simpler than Q-learning.\n\nFinally, if we were able to enumerate every predictively equivalent decision tree for a given DNF, we could simply iterate through them and select the most cost efficient one. However, we cannot yet map from a DNF to the set of equivalent trees. Understanding the group structure of predictively equivalent trees, as we briefly proposed as future work, would allow us to do this, but this remains to be solved. See our response to Reviewer Nmzb for more details on this direction.", "claims_and_evidence": "Yes, the claims are clearly supported through the reduction of redundancies in the Rashomon set and the three case studies.", "methods_and_evaluation_criteria": "The authors propose interesting, non-obvious evaluations for their introduced representation.", "theoretical_claims": "I briefly checked the proofs and believe they are correct.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The authors do a good job contextualizing their paper in the Related works section. It fits into a large line of work that is displayed through their 3 case studies, and unites them in a simple way.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is well written and the methods are clear. At first glance, the approach seemed potentially overly simplistic but I am convinced from the experiments that the author's contribution is substantial.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Besides the Q-learning approach in Sec 7, is there a simpler optimization-based procedure for leveraging this representation to improve cost efficiency?", "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: This paper addresses the issue of predictive equivalence in decision trees, i.e., the existence of decision trees that represent the exact same decision boundary but differ in their evaluation processes. The authors present a boolean logical representation of decision tree that does not exhibit predictive equivalence. The positive impact of this representation is highlighted in three downstream tasks: missing value handling, variable importance measures and cost efficiency optimization.

The reviewers have praised the quality of the writing, the novelty and effectiveness of the proposed representation, the soundness of the theoretical analyses, the diversity and relevance of the experiments. They have also identified a few weaknesses, such as the limited size of the datasets used in the experiments, some lack of novelty in the proofs, and the high computational cost of the approach. The authors have, however, convincingly addressed them in the rebuttal, for example, by providing new results on larger datasets. The incorporation of these discussions and new results will improve the paper's overall quality.

In light of the reviewers’ recommendations, I suggest accepting the paper. It represents a solid contribution to the field.
Decision: Accept (poster)