Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the problem of enumerating the Rashomon set for sparse decision trees.  The Rashomon set is the set of all almost-optimal models, and the paper provides the first result in enumerating it for highly nonlinear discrete models. The paper proposes an algorithm, TreeFARMS, to enumerate the Rashomon set for sparse decision trees, which stores the Rashomon set in a specialized and memory efficient data structure. The experimental evaluation, which considers several datasets from different domains, shows that the ability of enumerating the Rashomon set empowers the user with the ability to answer novel questions, such as: how does the variable importance change among trees within the Rashomon set? Do all almost-optimal models provide the same prediction for the same instance? How does the Rashomon set change if a subset of the data is removed? 
strengths_and_weaknesses: Strengths:
- overall, the paper provides a significant, high-quality, and original contribution
- the problem of enumerating the Rashomon set is very interesting in general, and very challenging for sparse decision trees
- the paper is clearly written and provides a clear motivation for the problem and a nice summary of the main contributions
- the methodological and algorithm contributions are sound
- the  experimental evaluation is clearly presented and comprehensive. It clearly shows how the proposed tool can be used to study the space of well-performing sparse decision trees
 
No weaknesses

questions: No questions
limitations:  There is no discussion, but the introduction provides some motivation for why the paper may have a positive impact.
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 present a method called TreeFARMS, which is a combination of analytical bounds and a specialized representation that produces enumerations of the Rashomon set for sparse decision trees. This methodology provides insight into the size of the Rashomon set, how variable importance changes over the set, predictive consistency across rashomon sets, and rashomon sets for other losses.
strengths_and_weaknesses: The paper presents bound to reduce the search space for Rashomon set construction. The basic lower bound and the rashomon equivalent points bound. They implement the algorithm using dynamic programming to find the optimal sparse decision trees. The work builds on existing literature focused on Rashomon sets and multiplicity to open an important discussion on variable importance and distributional shifts.
questions: What was the motivation for using the model set representation?
limitations: The authors discuss the paper's limitations. They specifically clarify that the models should not be interpreted as causal and also focuses on sparse binary decisions trees as the model class.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents the first algorithm TreeFARMS, a branch & bound algorithm with memoization (or dynamic programming with pruning bounds) to completely enumerate the Rashomon set of sparse decision trees. The Rashomon set is the set of almost-equally as good trees as the given reference tree. As recently proposed, the GOSDT algorithm [3][32] can find the empirical risk minimizer among sparse decision trees. TreeFARMS use this optimal tree as the reference for the Rashomon set, and also use its dependency graph as a model search space. The basic idea is to decompose search for decision trees into subproblems, and recursively solve child problems with maintaining these problems (dependency graph) and with pruning problem space with bounds. Extending this search strategy with a specialized data structure called Model Set (MS) representation enables the full enumeration of the Rashomon set of all sparse decision trees in the search space of GOSDT. Clear use cases of this complete enumeration such as the size of the Rashomon set, the variability of feature importances, the variability of predictions, and the sample dependency of the Rashomon set are further provided and discussed in detail.
strengths_and_weaknesses: ### Strengths

- This paper presents the first very powerful algorithm to completely enumerate the Rashomon set of optimal sparse decision trees thanks to GOSDT algorithm, pruning bounds, and MS data structures. This would be quite impactful because the instability or multiplicity of good models, for decision trees in particular, is a long standing interests in decision tree learning since Breiman.

- The paper also showed several clear use cases with detailed analysis. Full enumeration of the Rashomon set enables to analyze the size of Rashomon set, the variability of feature importances, the variability of predictions, and the sensitivity to missing groups of samples.


### Weaknesses

- Though the paper comes with a detailed supplementary document, some descriptions are hard to follow at the first glance due to the strong dependency on GOSDT. For example, the main algorithm of TreeFARMS, Algorithm 1, includes undefined procedure such as gosdt.get_graph or gosdt.configure_bounds. Since this is the main result, much more self-contained explanations would be appreciated.

- Also due to the implicit dependency on GOSDT, several important points would be unclearly presented. For example, one big issue is why the paper title includes "sparse" although Algorithm 1 and 2 have no sparsity-inducing parts apparently. If I understand it, the model search space for complete enumeration comes from GOSDT targeting sparse decision trees, and thus, TreeFARMS also results in enumerating sparse trees. Furthermore, it uses "GOSDT lookahead bounds" in actual that are not directly described in this paper.

questions: - Because the title includes "sparse", and thus could you explain why enumeration is limited to "sparse", and what does the paper mean by the word "sparse", or explicitly (but concisely?) explain the dependency inherited from GOSDT? 

- Could you add the table of contents for the supplementary document? I wanted to know the results for "the size of Rashomon set", which is the first example use-case mentioned in Introduction, but at the first glance, they are sort of hidden by other detailed information.

- Is the "dependency graph" actually a tree, a DAG, or a cyclic graph? I'm not sure about the connection, but I felt some abstract similarity to topics such as decision diagram (DD) representation of logical functions and traversing an enumeration tree, the search space of gSpan algorithm for all subgraph patterns, with bounds as in https://doi.org/10.1109/TPAMI.2016.2567399 for example.


limitations: No specific concerns on limitations and negative societal impact of this work.
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 authors propose the TreeFARMS method, which is able to enumerate the Rashomon set of all sparse decision trees over binary variables and labels that are optimal within a user-provided multiplicative factor in terms of 0-1 loss, which they also show to be sufficient for the derivation of balanced accuracy and F1 score. This algorithm employs a branch-and-bound search over the search state of trees represented as their leaves, some of which are fixed and some as of yet "unfixed"; it then uses a simple bound (that ignores "unfixed" leaves) and another that tightens the former by considering data point groups with identical features (termed equivalent points). TreeFARMS heavily relies on implementation details of the existing GOSDT algorithm and extensions for storing different decision trees. The authors show that their proposal outperforms heuristic methods in terms of accuracy, and demonstrate the model class reliance of the variables on an intuitive example dataset.
strengths_and_weaknesses: First work on providing the complete Rashomon set for optimal sparse trees.

Provide theoretical foundations for deriving the Rashomon set for other losses (balanced accuracy+F1).

Provide experimental evaluations for theoretically interesting applications of the Rashomon set: variable importance, and sensitivity to missing values.

Although overall solid work, the key novelty of the manuscript is limited to Sections 5.2 and 5.3 as it otherwise effectively extends an existing algorithm to enumerate the Rashomon set and the investigation of existing MCR.

The writing is good in general, but the authors are guilty of overselling; the manuscript will improve by removing exaggerations (e.g., “at the mercy of an algorithm”, “only scratch the surface of”) or allegations “this complexity explains why no previous works”, in lieu of a formal complexity result.

A clear limitation is the use of only binary labels and variables. The experiments show that setting the multiplicative and regularisation parameters provides little a-priori control on the number of models in the resulting set (e.g. it can be up to 10e12 in given configurations, line 190). 

The statistics during sampling are not clear to this reviewer. 

questions: 1. What is the sampling distribution? If not uniform among the entire Rashomon set, what is your intuition on which models are preferably included?

2. What is the relation between your method and the MCR method of Smith et al. for Random Forests?

[1] Gavin Smith, Roberto Mansilla, and James Goulding. Model Class Reliance for Random Forests.

limitations: The manuscript does not include a discussion of the limitations of the proposal.
review_title: null

Meta-review: metareview: This paper presents an algorithm to completely enumerate the Rashomon set of sparse decision trees using  a branch-and-bound search over a set of hierarchical maps. The reviewers were in agreement that this paper is an important contribution to the field. The method is particularly useful for identifying near-optimal decision trees and variable importance scoring. 

The problem of the Rashomon effect, where many equally good models could explain the data well, is a longstanding concern across nearly all machine learning applications. The Rashomon set is the set of such nearly-optimal models. While researchers would have liked to explore the Rashomon set, computational feasibility has limited such endeavors. This paper enables a shift in focus from a single optimal model to set of near-optimal models for a large and widely used class of models. Therefore, it can be expected that this work will have groundbreaking impact on multiple areas of machine learning.
confidence: Certain
Decision: Accept