  Finding the model that best describes a high dimensional dataset is a
daunting task. For binary data, we show that this becomes feasible when
restricting the search to a family of simple models, that we call Minimally
Complex Models (MCMs). These are spin models, with interactions of arbitrary
order, that are composed of independent components of minimal complexity
(Beretta et al., 2018). They tend to be simple in information theoretic terms,
which means that they are well-fitted to specific types of data, and are
therefore easy to falsify. We show that Bayesian model selection restricted to
these models is computationally feasible and has many other advantages. First,
their evidence, which trades off goodness-of-fit against model complexity, can
be computed easily without any parameter fitting. This allows selecting the
best MCM among all, even though the number of models is astronomically large.
Furthermore, MCMs can be inferred and sampled from without any computational
effort. Finally, model selection among MCMs is invariant with respect to
changes in the representation of the data. MCMs portray the structure of
dependencies among variables in a simple way, as illustrated in several
examples, and thus provide robust predictions on dependencies in the data. MCMs
contain interactions of any order between variables, and thus may reveal the
presence of interactions of order higher than pairwise.
