Information theory provides a sharp definition of the complexity of statistical models.
Simple models are those with a small stochastic complexity, which is computed in terms of the susceptibility
matrix (Fisher Information). We study the stochastic complexity of spin models (in the exponential family)
with interactions of arbitrary order.
Invariance with respect to bijections within the space of operators allows us to classify models in complexity
classes. This invariance also shows that simplicity is not related to the order of the interactions,
but rather to their mutual arrangement. Models where statistical dependencies are localized on
non-overlapping groups of few variables (and that afford predictions on independencies that are
easy to falsify) are simple. On the contrary, fully connected pairwise models, which are often used
in statistical learning, are highly complex because of their extended set of interactions.
Since the stochastic complexity is a penalty term in Bayesian model selection, our results suggests that
models that should be privileged in statistical learning for high dimensional datasets are not the ones that
are currently used.