Efficient Rashomon Set Approximation for Decision Trees

Standard machine learning pipelines often admit many near-optimal models. These "Rashomon sets'' pose a range of challenges and opportunities for uncertainty-aware, robust decision making. They allow incorporation of domain knowledge and user preferences that would otherwise be difficult to specify directly in an objective, and they quantify diversity in the plausible models and predictions for a given training dataset and objective function. However, the applicability of Rashomon sets has been limited by computational intractability. Computation of Rashomon sets even for simple, interpretable model classes like sparse decision trees continues to require immense memory and runtime resources. We present LicketyRESPLIT, an algorithm to approximate this Rashomon set with orders of magnitude improvement in runtime and memory usage. We validate that LicketyRESPLIT regularly recovers almost all of the full Rashomon set. This work dramatically expands the ability of researchers and practitioners to model the Rashomon set for real-world datasets.