Source-linked AI summary
On the Existence of Simpler Machine Learning Models
Lesia Semenova, Cynthia Rudin, Ronald Parr
TL;DR
Finding an accurate simple model can be difficult, and it is often unclear whether searching for one is worthwhile. The paper defines the Rashomon ratio to assess the size of near-optimal model sets and explores how they relate to simpler models. It suggests similar performance across methods can be a practical clue that simpler models may be worth seeking.
Problem
The paper asks whether accurate-yet-simple models can be shown likely to exist before the potentially expensive search to find them.
Source: §1 · p. 1Method
The paper defines Rashomon sets and ratios, develops theory and estimation approaches, and studies their relationship to simpler models and algorithm performance.
Source: §1 · pp. 2–3Results
The authors report that large Rashomon sets can contain simpler models, may correlate with similar performance across algorithms, and are associated with models that generalize well.
Source: §1 · p. 3, §8 · p. 15Takeaways & Limitations
When methods perform similarly and their models generalize well on validation data, practitioners may find it worthwhile to search a simpler function class.
Source: §8 · p. 15The theorem’s population-level assumption depends on a special function in the true Rashomon set and cannot be checked directly; its guarantee applies if that assumption holds.
Source: §5.1 · p. 8
Abstract
from arXiv · showhide
It is almost always easier to find an accurate-but-complex model than an accurate-yet-simple model. Finding optimal, sparse, accurate models of various forms (linear models with integer coefficients, decision sets, rule lists, decision trees) is generally NP-hard. We often do not know whether the search for a simpler model will be worthwhile, and thus we do not go to the trouble of searching for one. In this work, we ask an important practical question: can accurate-yet-simple models be proven to exist, or shown likely to exist, before explicitly searching for them? We hypothesize that there is an important reason that simple-yet-accurate models often do exist. This hypothesis is that the size of the Rashomon set is often large, where the Rashomon set is the set of almost-equally-accurate models from a function class. If the Rashomon set is large, it contains numerous accurate models, and perhaps at least one of them is the simple model we desire. In this work, we formally present the Rashomon ratio as a new gauge of simplicity for a learning problem, depending on a function class and a data set. The Rashomon ratio is the ratio of the volume of the set of accurate models to the volume of the hypothesis space, and it is different from standard complexity measures from statistical learning theory. Insight from studying the Rashomon ratio provides an easy way to check whether a simpler model might exist for a problem before finding it, namely whether several different machine learning methods achieve similar performance on the data. In that sense, the Rashomon ratio is a powerful tool for understanding why and when an accurate-yet-simple model might exist. If, as we hypothesize in this work, many real-world data sets admit large Rashomon sets, the implications are vast: it means that simple or interpretable models may often be used for high-stakes decisions without losing accuracy.
1 Introduction
Finding an accurate simple model is difficult, so the paper asks whether its existence can be assessed before an expensive search. It proposes that large Rashomon sets help explain why simple, accurate models may exist and why different algorithms can perform similarly.
1 Introduction
- The paper aims to make difficult searches for simple accurate models worth considering, since practitioners otherwise lack assurance that a simpler model can match a black box.Finding simpler models matters especially for high-stakes decisions.Source: §1 · pp. 1–2
- The paper proposes the Rashomon effect—many almost-equally-accurate models—as a possible explanation for similar algorithm performance and the existence of simpler accurate models.The authors hypothesize that a large Rashomon set can contain a simple model and models found by different algorithms.Source: §1 · p. 2
- The Rashomon ratio measures the Rashomon set’s volume relative to the hypothesis space and is proposed as a data- and function-class-dependent gauge of simplicity.The paper distinguishes it from standard learning-theory complexity measures.Source: §1 · p. 2
- Similar performance across different machine learning methods may be an inexpensive clue that simpler models are worth seeking within the Rashomon set.This is presented as an indication, not a direct measurement of the set’s size.Source: §1 · p. 2
- The authors summarize theoretical and empirical contributions, including generalization bounds, estimation approaches, and evidence that large Rashomon sets can coincide with similar algorithm performance and sparse accurate models.They also report that larger sets might occur with label or feature noise.Source: §1 · p. 3
2 Related Work
The paper situates Rashomon sets among work on good-model sets, flat minima, and statistical learning theory. It distinguishes its focus on set size and simpler-model existence from those works’ aims and measures.
Rashomon sets
- Earlier Rashomon-set work studies close-to-optimal models, searches for extreme models, or examines variable importance and downstream costs; this paper instead studies set size and simpler-class models.The cited examples include Srebro et al. (2010), Fisher et al. (2019), and Tulabandhula and Rudin (2013, 2014a,b).Source: §2 · p. 3
Flat minima or wide valleys
- Rashomon sets differ from volume ϵ-flatness because they are defined over functional space and need not be connected, so they can include distinct minima or discrete spaces.Volume ϵ-flatness is defined in parameter space and pertains to a connected set.Source: §2 · p. 4
Statistical learning theory
- Unlike standard learning-theory bounds, the Rashomon ratio can, under assumptions in Section 5, certify that a simpler model exists and generalizes.The paper connects this result to approximating sets, including Maurey’s lemma.Source: §2 · p. 4
3 Rashomon Set Definitions and Notation
The paper defines empirical and true Rashomon sets as near-optimal models in a hypothesis space, then measures their size relative to that space. The true set can certify simpler-model existence, but empirical sets are more practical to work with.
3 Rashomon Set Definitions and Notation
- The empirical Rashomon set contains models whose training performance is close to that of an empirical risk minimizer under the chosen loss.Its definition depends on the data set, hypothesis space, loss, and Rashomon parameter θ.Source: §3 · pp. 4–5
- The Rashomon ratio is the prior mass of the Rashomon set within the hypothesis space; with a uniform prior, it is the set’s volume divided by the space’s volume.The ratio lies between 0 and 1.Source: §3 · p. 5
- For a discrete hypothesis space with a uniform prior, the empirical Rashomon ratio is the fraction of models that fit the data about equally well.The text also defines true Rashomon sets using models with low true risk relative to the optimal true risk, with parameter γ > 0.Source: §3 · p. 5
- A large true Rashomon set can certify that a simpler model exists, but it cannot be explored directly, so the paper focuses mainly on empirical sets.The hypothesis space may be a specified class or a broader space containing models from different classes.Source: §3 · p. 5
4 Rashomon ratio as a simplicity measure
The Rashomon ratio gauges a learning problem’s simplicity by measuring how many models in a data-dependent hypothesis space are near-optimal. The paper distinguishes it from other measures and describes its potential connection to finding accurate, simpler models.
4 Rashomon ratio as a simplicity measure
- A large Rashomon ratio means many models perform about equally well, which may make accurate models easier to find and the learning problem simpler.A small ratio might indicate a harder problem, especially with few deep, narrow local minima.Source: §4 · p. 5
- Unlike most other measures, the Rashomon ratio depends on both the data set and hypothesis space and can indicate whether simpler functions may match complex functions’ accuracy.The measure also depends on a loss function.Source: §4 · p. 6
- The paper also distinguishes the ratio from algorithmic stability and margins: stability concerns data changes, while margins focus on points nearest the decision boundary.The paper states that, for linear least squares, the ratio depends on features but not regression targets; its margin comparison is illustrated by Theorem 3.Source: §4 · pp. 6–7
- The Rashomon ratio and geometric margin can differ even when two data sets share an empirical risk minimizer and the same margin.The theorem states that such data sets can have different Rashomon ratios.Source: §4 · p. 7
- The Rashomon ratio and local Rademacher complexity measure different things: the former counts near-optimal models for fixed labels, while the latter measures fitting random label assignments.The Rashomon set benefits from multiple similar models; local Rademacher complexity treats them as equivalent.Source: §4 · p. 7
5 Rashomon Set Models: Simplicity and Generalization
The section develops bounds for when a simpler class can match a more complex class, then gives conditions under which a large Rashomon set implies simple-yet-accurate models.
5 Rashomon Set Models: Simplicity and Generalization
- The setup asks whether a simpler class can approximate a more complex one closely enough to retain its performance, with F1 ⊂ F2.Examples include sparse integer scoring systems within real-valued linear models, and single trees within boosted trees.Source: §5 · p. 7
5.2 Proving the Existence of Simple-yet-Accurate Models with Good Generalization
- Under natural conditions—a smooth loss and F1 serving as a cover for F2—a large Rashomon set in F2 implies simple-yet-accurate models exist.The analysis replaces random sampling with smoothness and studies empirical rather than true Rashomon sets.Source: §5 · p. 8, §5.2 · p. 9
5 Rashomon Set Models: Simplicity and Generalization
- These bounds compare the training loss of a simpler model with the test loss of the optimal complex-class model, rather than measuring one model’s generalization gap.This differs from the usual single-function generalization question.Source: §5 · p. 8, §5.1 · p. 8
5.1 The True Rashomon Set Can Be Very Helpful... But You Might Not Know When
- If the true Rashomon set contains one member of F1, the best empirical F1 model can be bounded against the true risk of the best F2 model.The theorem assumes finite F1 ⊂ F2 and bounded loss; the special member of F1 need not be known.Source: §5.1 · p. 8
- Table 2’s example gives over 99% probability of finding an accurate simple model when 0.0053% of F2 models are good and F1 has at least 100,000 functions.The example applies to a randomly sampled F1; this setup is acknowledged as artificial.Source: §5.1 · pp. 8–9, Table 2 · p. 9
5.2 Proving the Existence of Simple-yet-Accurate Models with Good Generalization
- With a K-Lipschitz loss and a simpler class covering the empirical Rashomon set, a large set guarantees multiple simpler models with good generalization.The number guaranteed is the packing number of the empirical Rashomon set at radius 2δ.Source: §5.2 · p. 10
- When the theorem’s conditions hold, knowing that simple models exist can make the difficult search for one worthwhile.A large Rashomon set and the stated smoothness conditions imply such models exist before they are found.Source: §5.2 · p. 10
6 Larger Rashomon Ratios Correlate with Similar Performance of Machine Learning Algorithms, and Good Generalization
The section tests whether Rashomon-set size tracks comparable performance and generalization across methods; large ratios accompany useful performance patterns, while low ratios yield mixed outcomes.
6 Larger Rashomon Ratios Correlate with Similar Performance of Machine Learning Algorithms, and Good Generalization
- The experiments assess whether large Rashomon sets correspond to comparable performance across different hypothesis spaces and good generalization, including for simpler models.Source: §6 · p. 10
6.1 Experimental Design
- The study uses 38 UCI classification data sets, adapting non-binary data sets to binary classification for importance sampling.Source: §6.1 · p. 10
- The complex space is a union of five algorithms’ hypothesis spaces; logistic regression and CART serve as simpler spaces compared with random forests and boosted trees.Source: §6.1 · p. 11
- The Rashomon ratio is estimated by importance-sampling depth-seven decision trees as a surrogate for the complex model space; this surrogate may not suit data such as imagery.The study samples 250,000 trees per fold and sets the Rashomon parameter to 5%.Source: §6.1 · p. 11
6.2 Experimental Results
- Within ∼5%, training results were similar across five algorithms on data sets with large ratios (10−37% or 10−38%); simpler F1 models also generalized within ∼5% train-test error.The results cover 38 data sets and use depth-seven decision trees to measure Rashomon ratios.Source: §6.2 · pp. 11–12, Figure 2 · p. 12
- Low ratios had mixed outcomes: algorithms sometimes generalized well, but could also differ sharply in performance or fail to generalize.Other data sets or metrics may produce different results.Source: Figure 2 · p. 12, §6.2 · p. 12
- Consistent train-test performance across algorithms of varying complexity may indicate a large ratio, offering an indirect alternative to computationally intensive sampling.Source: §6.2 · p. 12
- Across all 38 data sets, the experiments found no cases where a large Rashomon set coincided with performance differences among algorithms.Source: §6.2 · p. 12
7 Rashomon Sets in the Presence of Noise
Section 7 distinguishes random label noise from feature noise as possible influences on Rashomon-set size. It presents an expected nondecrease result for random classification noise and conjectures that feature noise can enlarge the set in overlapping-Gaussian settings.
7 Rashomon Sets in the Presence of Noise
- Under random classification noise, the true Rashomon set over the original distribution is, in expectation, contained in the noisy-distribution Rashomon set.The result assumes 0–1 loss and independently flipped labels.Source: §7 · p. 13
- For the two-Gaussian setting, the conjecture says Rashomon-set volume increases with feature-noise standard deviation when σ > ˜σ.The hypothesis space allows decision boundaries between the two distribution means.Source: §7 · p. 13
- Figure 3 shows larger Rashomon ratios in noisy and non-noisy data sets, alongside the Gaussian example’s noise-dependent trend.The scatter plot covers 38 data sets and compares log Rashomon ratio with maximum accuracy across five algorithms.Source: Figure 3 · p. 14, §7 · p. 14
- With both Gaussian standard deviations fixed at 1, the conjecture places minimum volume near µ2 ≈ µ1 + 2; moving the means either closer or farther increases volume.The authors report exhaustive numerical checks, but no analytical solution for the volume minimizer.Source: §7 · p. 14
- The section links overlapping Gaussian distributions to large Rashomon sets and, in turn, to the existence of simple, similarly accurate models.The authors describe criminal recidivism and loan-default prediction as possible examples, not established cases.Source: §7 · p. 14
8 Conclusion and Implications
The conclusion connects large Rashomon sets with simpler accurate models, similar performance across algorithms, and good generalization, and suggests using these patterns to decide whether a simpler-model search may be worthwhile. The appended discussion distinguishes Rashomon sets from flat minima and derives a ridge-regression calculation of the Rashomon ratio.
8 Conclusion and Implications
- The paper concludes that large Rashomon sets relate to simpler accurate models, similar algorithm performance, good generalization, and overlapping-Gaussian data, while the Rashomon ratio measures learning-problem complexity.When several algorithms perform similarly and generalize well, the authors suggest searching a simpler function class may be worthwhile.Source: §8 · p. 15
A Difference between flat minima and Rashomon set
- Volume ϵ-flatness concerns a connected component around one local minimum, whereas a Rashomon set spans near-optimal models over the full hypothesis space and may include multiple minima.Rashomon sets are also defined for discrete spaces.Source: Figure 4 · p. 19
B Connection to Simplicity Measures
- The appendix introduces ridge-regression analysis as a way to compare the Rashomon ratio with other simplicity measures, including algorithmic stability.It identifies ridge regression as a case where the ratio can be computed in closed form in parameter space.Source: B Connection to Simplicity Measures · p. 19, §B.1 · p. 19
B.1 Analytical Calculation of Rashomon Ratio for Ridge Regression
- For ridge regression with a uniform prior, Theorem 10 characterizes the Rashomon set as an ellipsoid and provides a computation of its ratio.The optimal ridge solution is given by ˆω = (X^T X + C I_p)^−1 X^T Y.Source: §B.1 · pp. 19–20
- In ridge regression, the Rashomon ratio depends on the feature space X, not regression targets Y; the authors note this differs from other algorithms.The target-independence observation follows because empirical-risk difference depends on the feature matrix and parameter step.Source: §B.1 · p. 20
B.2 Algorithmic Stability
This section distinguishes the Rashomon ratio from algorithmic stability, geometric margin, and local Rademacher complexity, and develops results on empirical and true Rashomon sets. It introduces a concentration result and assumptions for Theorem 5, then completes its proof, showing that a large true Rashomon set can make a sampled hypothesis space likely to contain a suitable model.
B.2 Algorithmic Stability
- Two distributions can have the same expected Rashomon ratio but hypothesis-stability constants differing by an arbitrarily chosen λ.The theorem constructs this contrast for least-squares linear models.Source: §B.2 · p. 21
B.3 Geometric Margin
- Two data sets can share an empirical risk minimizer and geometric margin yet have Rashomon ratios differing by at least λ.The construction uses a fixed hypothesis space and Rashomon parameter.Source: §B.3 · pp. 22, 24, Figure 5 · p. 23
B.4 Empirical Local Rademacher Complexity
- Two data sets can have equal local empirical Rademacher complexities on their Rashomon sets but different Rashomon ratios.Theorem 4 asserts this discrepancy for some data sets, hypothesis space, and Rashomon parameter.Source: §B.4 · p. 25
C.1 Proof of Theorem 5
- Theorem 5 considers finite nested hypothesis spaces F1⊂F2 with loss l(f2,z)∈[0,b], assuming the larger class’s true Rashomon set contains a model from F1.Source: §C.1 · p. 27
- The proof of Theorem 5 concludes by combining the two preceding equations.Source: §C.1 · p. 27
C.2 Proof of Theorem 6 via Lemma 14
- A sufficiently large true Rashomon ratio makes it likely that F1 contains at least one model from the true Rashomon set.Lemma 14 gives probability at least 1 − ϵ for this inclusion under its ratio condition; Theorem 6 combines that result with Theorem 5.Source: §C.2 · p. 28
- With probability at least (1 − ϵ)^2 over the function and data draws, Theorem 6’s assumptions hold and bound (1) holds.Theorem 6 considers finite hypothesis spaces F1 ⊂ F2, with F1 drawn uniformly without replacement from F2 and loss bounded by b.Source: §C.2 · p. 28
C.3 Proof of Theorem 7
Theorem 7 gives a condition under which a large Rashomon set in a broader hypothesis space implies multiple accurate models in a simpler space. Appendix examples describe classes of functions that can approximate one another within specified guarantees.
C.3 Proof of Theorem 7
- With probability greater than 1−ϵ, if every model in F2’s Rashomon set is within δ of F1, F1 contains at least B(Rset(F2, θ), 2δ) models.The theorem also provides a generalization bound for these simpler models using the Rademacher complexity of a hypothesis space.Source: §C.3 · p. 28
C.4 Examples of function approximation in different hypothesis spaces
- Appendix examples describe function classes F2 that can be approximated by F1 within δ under a specified norm.The examples illustrate the kinds of function-space pairs to which the approximation condition applies.Source: §C.4 · p. 29, Table 3 · p. 29
D Data Set Descriptions
The experiments use UCI and synthetic binary-classification data, with stated preprocessing and validation procedures. The appendix describes algorithm comparisons, regularization effects on Rashomon ratios, and constraints on their importance-sampling estimates.
D Data Set Descriptions
- UCI data sets were cross-validated over ten folds when they had more than 200 points and five folds otherwise, reserving folds for testing and validation.Real-valued data were normalized to the unit cube; records with missing values and non-numerical features without a natural categorical conversion were omitted.Source: D Data Set Descriptions · pp. 29–30
- Experiments also used twelve synthetic binary-classification data sets with two real features, and their results and implications were consistent with those on UCI data.The data sets represent different two-dimensional geometrical concepts, including large and small margins, concentric circles, and half moons.Source: D Data Set Descriptions · p. 30, Figure 7 · p. 30
E Performance of Different Machine Learning Algorithms and Rashomon Ratio
- Figures 14 and 15 compare regularized algorithms on categorical and real-valued data sets, ordered from higher Rashomon ratios to ratios too small to measure.Figures 17 and 18 show unregularized comparisons on those data types, while Figures 16 and 19 cover synthetic data with and without regularization.Source: E Performance of Different Machine… · pp. 30–31
- Regularization typically makes the Rashomon ratio larger or equal to its unregularized value by shrinking the hypothesis space and changing the empirical risk minimizer.With fixed θ, the regularized space may include more models in its Rashomon set because its empirical risk minimizer typically has higher empirical risk.Source: E Performance of Different Machine… · pp. 30–31
- The experiments restrict comparisons to binary classification because sampling importance weights become smaller with more classes, making ratios harder to compare across data sets.The text gives three-class trees as an example of having a lower sampling probability than two-class trees.Source: E Performance of Different Machine… · p. 31
- Rashomon ratios are estimated with leaf-based importance sampling, using 250,000 sampled trees; another sampling scheme could change the importance weights and estimated size.The authors note that resolving this issue by sampling a huge number of trees is difficult in practice.Source: E Performance of Different Machine… · p. 31
F Large Rashomon Ratios May Appear Artificially Small
A measured Rashomon ratio can appear artificially small when the data representation or hypothesis space is poorly chosen. The section also describes feature-quality variations used to examine the ratio.
F Large Rashomon Ratios May Appear Artificially Small
- Poor data representation or a poorly chosen hypothesis space can make the Rashomon ratio appear artificially small.Highly correlated features can deflate it, as can a hypothesis space containing an overly large number of models.Source: F Large Rashomon Ratios May Appear… · p. 31
- The Breast Cancer Wisconsin experiments vary significant, noisy, and redundant features to examine how feature quality corresponds to the Rashomon ratio.The ratios are averaged over ten folds, with θ set to 0.05, and computed relative to the best sampled model across the variations.Source: Figure 8 · p. 32
- The authors focus on what is observed under large Rashomon ratios, rather than treating small ratios as their main interest.They note that some data sets with high-performing algorithms nevertheless had small measured ratios.Source: F Large Rashomon Ratios May Appear… · p. 32
G Quality of the Features
Feature quality changes the Rashomon ratio by changing the relative sizes of the hypothesis space and the Rashomon set. Experiments show that irrelevant features can lower the ratio, while redundant relevant features can raise it.
G Quality of the Features
- Adding irrelevant noise features lowers the Rashomon ratio by enlarging the hypothesis space while leaving the Rashomon set approximately unchanged.Removing the least relevant Wine features first raises the ratio, which peaks at about six features before falling as relevant features are removed and model accuracy declines.Source: G Quality of the Features · pp. 32–33
- Adding copies of the six most significant Breast Cancer Wisconsin features increases the Rashomon ratio by creating more good-enough trees at a fixed depth.The experiment uses decision trees of depth seven.Source: G Quality of the Features · pp. 32–33
- When algorithms perform similarly but the observed Rashomon ratio is small, noisy or irrelevant features are one possible explanation.The authors suggest iteratively removing features to seek a larger ratio without changing empirical risk; redundant features could instead inflate the ratio and may be removed before measurement.Source: G Quality of the Features · p. 33
H Proof of Theorem 8
Under independent random classification noise, the theorem states that the true Rashomon set is contained in the noisy-distribution Rashomon set in expectation. The claim assumes 0–1 loss and a label-flip probability below one half.
H Proof of Theorem 8
- Under 0–1 loss, when each label is independently flipped with probability ρ, the true Rashomon set over D is, in expectation, a subset of the true Rashomon set over noisy distribution Dρ.Source: H Proof of Theorem 8 · p. 33
- The proof concludes the inclusion by showing that each model in the original true Rashomon set also belongs to the set under the noisy distribution.The authors relate the proof technique to Manwani and Sastry (2013), whose purpose was to show noise tolerance of the optimal model.Source: H Proof of Theorem 8 · p. 34
I Evidence for Conjecture 9
For balanced classes drawn from equal-variance Gaussians, the section examines how the true Rashomon-set volume changes with feature noise. It derives the volume from the set’s edge models and presents a mixture of proofs and numerical evidence for the conjectured trends.
I Evidence for Conjecture 9
- The analysis assumes balanced classes with Gaussian feature distributions sharing standard deviation σ, and considers thresholds f between the means.The stated conjecture predicts that, above a threshold noise level, increasing σ increases Rashomon-set volume.Source: I Evidence for Conjecture 9 · p. 35
- The true Rashomon-set volume is the distance between its two edge models, obtained as solutions to Equation (2).The section defines the edge condition through the loss difference from the optimal model reaching γ.Source: I Evidence for Conjecture 9 · pp. 35–36
- For fixed σ, the section proves that the excess-loss objective G(f, σ) increases with f on the right side of the optimal threshold.The authors prove this monotonicity and the resulting volume comparison in part (iii), while part (ii)'s monotonicity in σ is supported by numerical experiments rather than proved.Source: I Evidence for Conjecture 9 · pp. 36–37
- For fixed f and σ above the stated threshold, the authors numerically find that G(f, σ) decreases as σ increases, supporting conjectured part (ii).The text says exhaustive numerical calculations establish the sign over the considered parameter ranges, not a proof of the monotonicity claim.Source: I Evidence for Conjecture 9 · pp. 36–37, Figure 10 · p. 39
- The section explicitly distinguishes proven claims from conjecture: part (i) and the conditional implication in part (iii) are proved, while part (ii) remains conjectural.The authors state that there is not yet a proof for the conjecture and support part (ii) with numerical evidence.Source: I Evidence for Conjecture 9 · pp. 34, 36
- With σ fixed at 1, numerical optimization finds the Rashomon-set volume minimized when the Gaussian means are about two units apart; moving them closer or farther increases volume.At µ1=0 and µ2≈2, the optimal threshold is 1, one standard deviation from each mean; the numerical solutions and example are shown in Figures 12 and 13.Source: I Evidence for Conjecture 9 · pp. 35, 37, Figure 12 · p. 40, Figure 13 · p. 40