Computing the Collection of Good Models for Rule Lists
  Since the seminal paper by Breiman in 2001, who pointed out a potential harm
of prediction multiplicities from the view of explainable AI, global analysis
of a collection of all good models, also known as a `Rashomon set,' has been
attracted much attention for the last years. Since finding such a set of good
models is a hard computational problem, there have been only a few algorithms
for the problem so far, most of which are either approximate or incomplete. To
overcome this difficulty, we study efficient enumeration of all good models for
a subclass of interpretable models, called rule lists. Based on a
state-of-the-art optimal rule list learner, CORELS, proposed by Angelino et al.
in 2017, we present an efficient enumeration algorithm CorelsEnum for exactly
computing a set of all good models using polynomial space in input size, given
a dataset and a error tolerance from an optimal model. By experiments with the
COMPAS dataset on recidivism prediction, our algorithm CorelsEnum successfully
enumerated all of several tens of thousands of good rule lists of length at
most $\ell = 3$ in around 1,000 seconds, while a state-of-the-art top-$K$ rule
list learner based on Lawler's method combined with CORELS, proposed by Hara
and Ishihata in 2018, found only 40 models until the timeout of 6,000 seconds.
For global analysis, we conducted experiments for characterizing the Rashomon
set, and observed large diversity of models in predictive multiplicity and
fairness of models.
