TL;DR
The paper introduces SORTD, a novel dynamic programming framework that enumerates the "Rashomon set"—the collection of all near-optimal sparse decision trees—in strict order of their performance. By generating the best trees first, SORTD provides true anytime behavior and delivers up to a two-orders-of-magnitude speedup and a ten-fold reduction in memory usage compared to the current state-of-the-art.
What Problem Does This Paper Address?
When training a decision tree, standard algorithms look for the single "best" model that minimizes a loss function. However, real-world datasets often exhibit the Rashomon effect: there are frequently many different tree structures that achieve nearly identical, optimal performance. This collection of approximately equally good models is called the Rashomon set.
Exploring the Rashomon set is incredibly valuable. It allows practitioners to find simpler alternative models, conduct robust variable importance analysis, or select trees that satisfy secondary criteria like fairness or robustness without hard-coding these constraints into the initial training objective.
Unfortunately, because finding even a single optimal tree is NP-hard, enumerating the entire Rashomon set is computationally daunting—the set size can easily exceed $10^{12}$ trees for a simple dataset. Existing state-of-the-art tools (like TreeFARMS) require users to pre-define a strict performance tolerance multiplier. If the multiplier is too large, the system runs out of memory or times out; if it's too small, useful models are missed. Crucially, prior methods do not return trees in any sorted order, meaning you have to wait for the entire search to finish before finding the highest-quality models.
Methods
The authors propose SORTD (Sorted Rashomon Sets of Trees using Dynamic Programming), which flips the search strategy from depth-first to a best-first, lazy enumeration approach.
Key components of the method include:
- In-Order Generation: SORTD constructs a search tree where each node maintains a sorted list of solutions. It uses a lazy evaluation strategy, computing and returning the next-best tree only when requested.
- Sorted Cartesian Sums: To build a parent tree, branching nodes combine the best solutions from their left and right child nodes using a priority queue to ensure the combined solutions are also generated in non-decreasing order of their objective value.
- Specialized Depth-Two Subroutine: To dramatically accelerate the search, SORTD adapts an optimized subroutine that uses precomputed feature frequency counts to instantly evaluate all subtrees of depth two or less, bypassing expensive recursive dataset splits.
- Flexible Post-Evaluation: Because the trees are generated based on a primary, totally ordered objective (like accuracy), SORTD can pass these trees to a secondary, partially ordered objective (like fairness metrics) to efficiently map out a Pareto-optimal front.
The search tree structure and the mechanics of how next-best solutions are calculated are illustrated below:
Datasets
The framework was evaluated using:
- 30 Benchmark Binary Classification Datasets: Standard datasets from the UCI Machine Learning Repository and fairness benchmarks, including well-known sets like COMPAS, FICO, Adult, Bank Marketing, and HTRU2.
- Regression Benchmarks: Datasets such as Airfoil Self-Noise, Air Quality, and Seoul Bike Sharing Demand were used to demonstrate SORTD's extensibility to regression tasks.
No new datasets were introduced in this paper.
Key Insights and Ideas
- The Power of "Anytime" Behavior: Because SORTD outputs trees in order of performance, users can terminate the algorithm at any moment (e.g., after finding the top 100 or 1,000 trees) and still be guaranteed that they have the absolute best models available within that budget.
- Smaller Sets Suffice for Feature Importance: The authors discovered that variable importance rankings (calculated via Leave-One-Feature-Out) stabilize significantly with just the top 100 trees. This means practitioners don't need to waste time generating millions of trees to understand feature behavior.
- Decoupling Optimization from Constraints: Instead of designing complex, custom optimization algorithms for tricky constraints like demographic parity, SORTD allows users to optimize for accuracy first, and then easily filter the resulting sorted Rashomon set for fair models post-hoc.
Key Results
- Speedups: SORTD consistently outperformed TreeFARMS across varying tree depths ($d \in \{3, 4, 5\}$), achieving runtimes up to two orders of magnitude faster. For deeper budgets ($d=5$), TreeFARMS frequently timed out (300s limit), while SORTD often finished in under 10 seconds.
- Memory Efficiency: SORTD maintained a memory footprint below 1 GB for almost all test cases, representing an order-of-magnitude reduction compared to TreeFARMS, which routinely suffered from memory exhaustion on high-dimensional datasets.
- Dimensionality Scaling: When feature counts exceeded 30, TreeFARMS failed to complete, whereas SORTD scaled gracefully, remaining well below the time limit.
Limitations and Future Work
- Binary Features Only: The current implementation of SORTD is strictly limited to datasets with binary features. Extending the dynamic programming and frequency-counting subroutines to continuous features remains a challenge.
- Scalability Ceilings: While SORTD pushes the boundaries of what is practical, the underlying problem is still NP-hard. For exceptionally large depth budgets ($d > 5$) or massive feature spaces, the combinatorial explosion will eventually make full enumeration intractable.
Future work could focus on relaxing the binary feature constraint and exploring heuristic bounds to approximate sorted Rashomon sets for even larger architectures.
Summary updated