SORTeD Rashomon Sets of Sparse Decision Trees: Scalable Anytime Enumeration
Elif Arslan, Jacobus van der Linden, Serge Hoogendoorn, Marco Rinaldi, Emir Demirović
Sparse decision tree learning provides accurate and interpretable predictive models that are ideal for high-stakes applications by finding the single most accurate tree within a (soft) size limit. Rather than relying on a single “best” tree, Rashomon sets—trees with similar performance but varying structures—can be used to enhance variable importance analysis, enrich explanations, and enable users to choose simpler trees or those that satisfy stakeholder preferences (e.g., fairness) without hard-coding such criteria into the objective function. However, since finding the optimal tree is NP-hard, the scalability of enumerating the Rashomon set is challenging. Therefore, we introduce SORTD, a novel framework that improves scalability and enumerates Rashomon sets in order of the objective value, thus offering anytime behavior. Our experiments show that SORTD reduces runtime by up to two orders of magnitude compared with the state of the art. Moreover, SORTD can compute Rashomon sets for any totally ordered objective and supports post-evaluating the set using other (partially ordered) objectives. Together, these advances make exploring Rashomon sets more practical in real-world applications.