Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the interpretable decision tree by a metric called "explanation size", then presents some theoretical results about this size in relating to the tree depth in the average and worst cases.  The paper proposes a practical algorithm using adjusted Gini-index for tree splitting, based on a hyperparameter that differentiates whether using the existing split variable or using a new variable. Numerical experiments are conducted for multiple datasets. 
strengths_and_weaknesses: 1. Interpretable decision tree has been an interesting topic, which is usually measured by the tree depth or the number of terminal nodes. Explanation size is a new interesting metric in measuring the splitting rule complexity. 

2. This paper presents some theoretical bounds in relating explanation size to tree depth in average and worst cases. But it is not clear how tight these bounds are. (They seem to be rather loose bounds).

3. The authors propose a practical algorithm based on an adjusted Gini-index, which also sounds reasonable. It is desirable to see how effective such algorithm may construct the interpretable decision trees that are smaller explanation size while maintain competitive prediction performance. The numerical results on Section 6 are not very convincing in the performance comparison. 
questions: 1. For the example in Section 6,  FactorExpl  is set to be 0.97. In general, how this hyperparameter should be tuned? 

2. For the above hyperparameter, is there significant room to have better choices so that the explanation size drops more, while the performance may stay competitive or even better in generalization? 

3. How tight are the theoretical bounds in Section 4?
 
limitations: The algorithm based on adjusted Gini-index seems to be a plausible approach, but the results as illustrated in Section 6 do not show significant lifting power. In Figure 2, when FactorExpl = 0.97, explanation size drops a bit dramatic, but performance also drops in a non-negligible way. It is desirable to see more convincing results with competitive performance.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces a metric for evaluating decision trees based on explanation size. Using this metric, The authors establish theoretical bounds on identifying trees with both optimal depth and explanation size, and develop an algorithm, SER-DT, for regularizing decision trees based on explanation size. The proposed algorithm shows improvement in reducing explanation while maintaining similar performance when compared to a competing method.

strengths_and_weaknesses: 
**Strengths:**
* The proposed definition of explanation size is natural and intuitive. Decision trees are used in a number of applications for their interpretable properties; the proposed method improves on this interpretability and therefore could be of high interest to the community.
* The paper has a good theoretical exploration of the tradeoff between tree depth and explanation size.

**Weaknesses:**
* Comparisons with Pruning algorithms. While the experiments include comparisons with CART, the paper could be improved by including comparisons with methods that reduce tree complexity, such as pruning.
* High variance of results in Table 1 for test accuracy (see questions below). It would be beneficial if the authors could clarify these points. Error bars and/or significance testing in Table 1 would be helpful.

**Miscellaneous Minor Issues / Suggestions:**
* In table 1, it would be helpful to define what the bolded results indicate in the table caption.
* Typo in Line 85: "interpretabilty"
* Typo in Line 212: "Explanaible"
* Typo in Line 302: "intrepretability"
* Grammar in Line 303: "upper and lower bound"

**Summary:**
The paper introduces a novel approach to improving decision tree interpretability. While the paper has room for improvement regarding experimental results and comparisons with pruning methods, the strong theoretical analysis makes me lean towards acceptance.

questions: * Why is there such high variance in accuracy results (Table 1) between SER-DT and CART? Why is the reported accuracy is higher for SER-DT than CART for a number of datasets (e.g. dry bean, eeg eye estate)? This seems to imply that regularizing for explanation length actually increases performance.
* How was FactorExpl=0.97 chosen for the experiments? Are there any guidelines for selecting this parameter in practice?
limitations: Limitations have been adequately discussed in the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes explanation size as a novel measure to capture the interpretability of a decision tree. The explanation size of a leaf is defined as the number of distinct attributes occurring in nodes from the root to the leaf. This is an intuitively sensible notion, as it captures the size of the decision rule corresponding to the leaf. The metric is then lifted to whole trees by either considering the average or worst-case explanation size among all leafs.

As the first major contribution, the authors give a tight characterization of best possible guarantees achievable by a decision tree on the trade-off of simultaneously optimizing explanation size and the traditional criterion of tree depth. In particular, a theorem is given that states that for all datasets there are trees which have optimal explanation size and a depth within a factor of 2 of the optimal depth plus a logarithmic term in the sample size. This is complemented by a lower bound that shows that there are problem inputs for which depth and explanation size are different for all binary trees by a logarithmic factor in sample size. While not mentioned explicitly, these results seem to refer to trees that achieve zero classification error.

Moreover, the authors present a greedy top-down tree induction algorithm called Short Explainable Rules (SER-DT) that aims to find minimum explanation size trees by using a novel splitting criterion called weighted pairwise misclassification. This algorithm guarantees an O(ln n) approximation for binary decision trees of approximately optimal average / worst-case explanation size and depth, and the experiments over 20 datasets indicate that the new algorithm is competitive with the commonly used CART algorithm. 
strengths_and_weaknesses: The introduced explanation size is a simple, apparently useful, yet, to my knowledge, novel metric to measure the interpretability of decision trees. However, note that this notion is closely related to rule sizes (as in number of queries in a rule), which is considered in the rule learning literature, e.g.,
* Ignatiev, Alexey, Filipe Pereira, Nina Narodytska, and Joao Marques-Silva. “A SAT-Based Approach to Learn Explainable Decision Sets.” In International Joint Conference on Automated Reasoning, 627–45. Springer, 2018.
* Proença, Hugo M., and Matthijs van Leeuwen. “Interpretable Multiclass Classification by MDL-Based Rule Lists.” Information Sciences 512 (February 2020): 1372–93.
* Probably has been considered in early rule learning work as well; I recommend checking the survey “Seperate-and-conquer Rule Learning” by Furnkranz for an overview of work from the 1990s.
 
The presented algorithm is simple yet shown theoretically and practically to achieve its goal. It would be useful though to discuss why the proposed splitting criterion based on reducing the number of discrepancy pairs leads to this result, as this as well as the other steps of the algorithm do not seem to directly relate to explanation size. In this context it would also be useful to discuss the relation to tree optimization that minimizes the total size of the tree (number of nodes), e.g.,

* Bessiere, Christian, Emmanuel Hebrard, and Barry O’Sullivan. “Minimising Decision Tree Size as Combinatorial Optimisation.” In International Conference on Principles and Practice of Constraint Programming, 173–87. Springer, 2009.
 
Related to that, the empirical study, while overall showing good accuracy/explanation size trade-offs relative to CAR, does not contain a comparison with a method that directly optimizes depth, which seems relevant given the theoretical results of the paper, and the cited empirical work that assesses that depth is indicative of interpretability. A further caveat is that theoretical and empirical results might relate to different variants of the algorithm: the parameter FactrorExpl seems to not play a role in the theoretical analysis. However, it is tuned for the experiments.
 
This relates to the clarity of the presentation, which is overall good. However, there are some missing implicit definitions and assumptions. Most importantly, the underlying problem definition seems to assume that the resulting trees have to perfectly classify the given training data. This is a reasonable definition. However, it is different from the usual ML problem, in which either tree pruning or other forms of regularization are applied, allowing the returned tree to have non-zero classification error. See for example:

* Hu, Xiyang, Cynthia Rudin, and Margo Seltzer. “Optimal Sparse Decision Trees.” In 33rd Conference on Neural Information Processing Systems, 9, 2019.
 
With this definition, it is also implicitly assumed that the there are perfectly classifying trees, which is not necessarily guaranteed in the usual statistical settings.
 
Other minor issues the term “n” is used without definition (e.g., Theorem 1), and, as mentioned, the hyper-parameter “FactorExpl”, which seems to be introduced as an afterthought in the empirical section.

questions: Why is there no comparison between the proposed algorithm and algorithms from the literature that optimize depth? Given the demonstrated compatibility of small depth and small explanation size, this seems like a relevant baseline.
 
What is the significance of the example weights in the problem definition? Most commonly, we consider unweighted prediction problems, which are equivalent to using constant weights. The theorem as given allows us to choose these constant weights arbitrarily small, in effect letting the log n term vanish. This seems counterintuitive.

limitations: Besides the above mentioned limitations in terms of comparison to other tree optimisation paradigms, there is also a lack of guarantees / discussion for the tradeoff between explanation size and accuracy – once such a tradeoff is allowed by considering, as usual, no perfect classification.
review_title: null

Meta-review: metareview: The paper presents an interesting approach for using decision trees in order to provide explainable classifiers
confidence: Certain
Decision: Accept