From Rashomon Theory to PRAXIS: Efficient Decision Tree Rashomon Sets

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 users to incorporate domain knowledge and preferences that would otherwise be difficult to specify directly in an objective, and they quantify diversity among valid models for a given training dataset and objective function. However, computation of Rashomon sets, even for simple, interpretable model classes such as sparse decision trees, continues to require immense memory and runtime resources. We present PRAXIS, an algorithm to approximate this Rashomon set with orders of magnitude improvement in runtime and memory usage. We validate that PRAXIS regularly recovers almost all of the full Rashomon set. PRAXIS allows researchers and practitioners to scalably model the Rashomon set for real-world datasets.

In machine learning, there are often many good models that a practitioner could use, not just one. There has been interest in finding and exploring the whole set of models with good performance. This lets practitioners study what reasoning is common across good models, learn where equally good models disagree, and understand what would be missed by choosing just one model arbitrarily. One of the settings where researchers can find and explore this set is decision trees: these are simple flowchart-like structures to make predictions. While researchers can find the set of good trees, doing so often requires a lot of time and computation. We propose a way to find this set much more quickly than before. We are not guaranteed to find every good tree, but in practice, we find we usually recover all or the vast majority of them. In a number of cases, we can find these trees in seconds where baselines take days.