  Many learning algorithms have invariances: when their training data is
transformed in certain ways, the function they learn transforms in a
predictable manner. Here we formalize this notion using concepts from the
mathematical field of category theory. The invariances that a supervised
learning algorithm possesses are formalized by categories of predictor and
target spaces, whose morphisms represent the algorithm's invariances, and an
index category whose morphisms represent permutations of the training examples.
An invariant learning algorithm is a natural transformation between two
functors from the product of these categories to the category of sets,
representing training datasets and learned functions respectively. We
illustrate the framework by characterizing and contrasting the invariances of
linear regression and ridge regression.
