Leveraging Predictive Equivalence in Decision Trees

Thank you for your review! We are glad that you appreciated the novelty of our method through our experimental results.

To 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}}).

We 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.

Finally, 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.

Thank you for your thoughtful and thorough review! We hope that the comments below address your concerns.

Complexity of Algorithm 1 and Quine-McCluskey

The 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.

We 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.

Alternative Tree Simplification Methods

It 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. In 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. Thus, the conclusions of our experiments likely wouldn't be affected by changing the method of decision tree optimization.

While 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.

Random Forests

Yes, the proposed representation could absolutely be extended to ensemble methods such as random forests! See our response to Reviewer Nmzb for details.

Binary Decision Diagrams

While 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.

Dataset Size

We'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.

We 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.

Hyperparameter Sensitivity of Q-learning

Thank 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.

[1] Izza, Y., Ignatiev, A., and Marques-Silva, J. On tackling explanation redundancy in decision trees. Journal of Artificial Intelligence Research, 75:261–321, 2022.

Thank you for the thorough and thoughtful review and for the suggested additions in describing the Rashomon set and TreeFARMS. If accepted, we will use our extra page to incorporate this discussion into the camera-ready version. Thank you also for flagging the off-by-one typo in lines 258-259, and the need to clarify figure 3.

Q1. Evaluating a DNF with Missing Values

When 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$. It 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.

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.

While 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].

The 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.

The Group Structure of Decision Trees

Our 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).

Random Forests

Our 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.

[1] Semenova, L., Rudin, C., and Parr, R. On the existence of simpler machine learning models. In 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 1827–1858, 2022.

[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

[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.

[4] Vidal, T., Schiffer, M. Born-again tree ensembles. International Conference on Machine Learning. PMLR, 2020. https://arxiv.org/abs/2003.11132