On the Existence of Simpler Machine Learning Models

Abstract

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.

Revisited sections 1,3,4,5,6. Added new section 7

References in corpus (6)

• Reconciling modern machine learning practice and the bias-variance trade-off
• All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously
• Underspecification Presents Challenges for Credibility in Modern Machine Learning
• Predictive Multiplicity in Classification
• Robust Optimization using Machine Learning for Uncertainty Sets
• Detecting Underspecification with Local Ensembles

Cited by in corpus (11)

• Learning Optimal Fair Classification Trees: Trade-offs Between Interpretability, Fairness, and Accuracy
• Designing deep neural networks for driver intention recognition
• Arbitrary Decisions are a Hidden Cost of Differentially Private Training
• Investigating the Impact of Balancing, Filtering, and Complexity on Predictive Multiplicity: A Data-Centric Perspective
• Who Are We Missing? A Principled Approach to Characterizing the Underrepresented Population
• What Constitutes a Less Discriminatory Algorithm?
• Allocation Multiplicity: Evaluating the Promises of the Rashomon Set
• Scalable Rule Lists Learning with Sampling
• Beyond the Single-Best Model: Rashomon Partial Dependence Profile for Trustworthy Explanations in AutoML
• Why Shallow Networks Struggle to Approximate and Learn High Frequencies
• "A 6 or a 9?": Ensemble Learning Through the Multiplicity of Performant Models and Explanations