  In any given machine learning problem, there may be many models that could
explain the data almost equally well. However, most learning algorithms return
only one of these models, leaving practitioners with no practical way to
explore alternative models that might have desirable properties beyond what
could be expressed within a loss function. The Rashomon set is the set of these
all almost-optimal models. Rashomon sets can be extremely complicated,
particularly for highly nonlinear function classes that allow complex
interaction terms, such as decision trees. We provide the first technique for
completely enumerating the Rashomon set for sparse decision trees; in fact, our
work provides the first complete enumeration of any Rashomon set for a
non-trivial problem with a highly nonlinear discrete function class. This
allows the user an unprecedented level of control over model choice among all
models that are approximately equally good. We represent the Rashomon set in a
specialized data structure that supports efficient querying and sampling. We
show three applications of the Rashomon set: 1) it can be used to study
variable importance for the set of almost-optimal trees (as opposed to a single
tree), 2) the Rashomon set for accuracy enables enumeration of the Rashomon
sets for balanced accuracy and F1-score, and 3) the Rashomon set for a full
dataset can be used to produce Rashomon sets constructed with only subsets of
the data set. Thus, we are able to examine Rashomon sets across problems with a
new lens, enabling users to choose models rather than be at the mercy of an
algorithm that produces only a single model.
