Fast Rashomon Sets of Sparse Rule Sets

Abstract A sparse rule set (SRS) is a small predictive model that is a disjunctive normal form – an “OR of ANDs”. SRS models are understandable to human experts and robust to outliers. Constructing an SRS efficiently has always been one of the fundamental problems of interpretable machine learning. However, the practical challenge goes beyond simply optimizing for a single sparse SRS; the first interpretable model an algorithm finds often has flaws that need to be fixed. Thus, constructing a model for practical use involves human interaction with an algorithm. If we work within the Rashomon set paradigm, we would generate many models that a human can explore; this simplifies the interaction, but requires generating a large pool of models, which is computationally demanding. This work presents FastSRS, an efficient algorithm for generating a large quantity of high quality SRS models. Its key advantage is a set of theoretical bounds that efficiently reduces the size of the search space to enable fast computation. FastSRS produces models on the accuracy vs. sparsity frontier more consistently and efficiently than previous approaches, scales better to larger datasets, and sets a new state of the art for generating Rashomon sets for SRSs.