The no-free-lunch theorem for machine learning basically says that some set of preferences (or inductive bias) over the space of all functions is necessary to obtain generalization, that there is no completely general-purpose learning algorithm, that any learning algorithm will generalize better on some distributions and worse on others.

Typically, given a particular dataset and loss function, there are many possible solutions (e.g. parameter assignments) to the learning problem that exhibit equally "good" performance on the training points. Given a finite training set, the only way to generalize to new input configurations is then to rely on some assumptions or preferences about the solution we are looking for.

An important question for AI research aiming at human-level performance then is to identify inductive biases that are most relevant to the human perspective on the world around us. Inductive biases, broadly speaking, encourage the learning algorithm to prioritise solutions with certain properties.

Table 1 lists some of the inductive biases already used in various neural networks, and the corresponding properties. Although they are often expressed in terms of a neural architecture, they can also be about how the networks are trained, e.g., unsupervised pre-training, self-supervised learning and semi-supervised training, which all have to do with the input distribution P(X) being informative about future tasks P(Y|X).

There are many ways to encode such biases—e.g. explicit regularisation objectives, architectural constraints, parameter sharing, implicit effects of the choice of the optimization method, self-supervised learning or self-supervised pre-training, invariance or equivariance to known transformations, or choices of prior distributions in a Bayesian model.

For example, one can build translation invariance of a neural network output by replacing matrix multiplication by convolutions and pooling, or by averaging the network predictions over transformations of the input (feature averaging), or by training on a dataset augmented with these transformations (data augmentation).

Whereas some inductive biases can easily be encoded into the learning algorithm (e.g. with convolutions), the preference over functions is sometimes implicit and not intended by the designer of the learning system, and it is sometimes not obvious how to turn an inductive bias into a machine learning method, this conversion often being the core contribution of machine learning papers.

We can think of inductive biases or priors and built-in structure as "training data in disguise", and one can compensate lack of sufficiently powerful priors by more data.

Interestingly, different inductive biases may be equivalent to more or less data (even possibly exponentially more data): we suspect that inductive biases based on a form of compositionality (like distributed representations, depth and attention) can potentially also provide a larger advantage (to the extent that they apply well to the function to be learned).

In general, priors can be imperfect and this shows most with large datasets. Even for good priors, the advantage of inductive biases may be smaller on very large datasets, which suggests that transfer settings (where only few examples are available for the new distribution) are interesting to evaluate the advantage of inductive biases and of their implementation.

The classical framework for machine learning is based on the assumption of identically and independently distributed data (i.i.d.), i.e test data has the same distribution as the training data. This is a very important assumption, because if we did not have that assumption, then we would not be able to say anything about generalization to new examples from the same distribution. Unfortunately, this assumption is too strong, and reality is not like this, especially for agents taking decisions one at a time in an environment from which they also get observations.

The distribution of observations seen by an agent may change for many reasons: the agent acts (intervenes) in the environment, other agents intervene in the environment, or simply our agent is learning and exploring, visiting different parts of the state-space as it does so, discovering new parts of it along the way, thus experiencing non-stationarities along the way.

Although sequential decision-making is ubiquitous in real life, there are scenarios where thinking about these non-stationarities may seem unnecessary (like object recognition in static images). However, if we want to build learning systems which are robust to changes in distribution, it may be necessary to train them in settings where the distribution changes!

And then of course there are applications of machine learning where the data is sequential and non-stationary (like historical records of anything) or even more so, where the learner is also an agent or is an agent interacting with other agents (like in robotics, autonomous driving or dialogue systems).

That means we may need to go away from large curated datasets typical of supervised learning frameworks and instead construct non-stationary controllable environments as the training grounds and benchmarks for our learners. This complicates the task of evaluating and comparing learning algorithms but is necessary and we believe, feasible.

Instead of a fixed data distribution and searching for an inductive bias which works well with this distribution, we are thus interested in transfer learning and continual learning scenarios, with a potentially infinite stream of tasks, and where the learner must extract information from past experiences and tasks to improve its learning speed (i.e., sample complexity, which is different from asymptotic performance which is currently the standard) on future and yet unseen tasks.

Suppose the learner faces a sequence of tasks, A, B, C and then we want the learner to perform well on a new task D. Short of any assumptions it is nearly impossible to expect the learner to perform well on D. However if there is some shared structure, between the transfer task (i.e task D) and source tasks (i.e tasks A, B and C), then it is possible to generalize or transfer knowledge from the source task to the target task.

Hence, if we want to talk meaningfully about knowledge transfer, it is important to talk about the assumptions on the kind of data distribution that the learner is going to face, i.e., (a) what they may have in common, what is stable and stationary across the environments experienced and (b) how they differ or how changes occur from one to the next in case we consider a sequential decision-making scenario.

This division should be reminiscent of the work on meta-learning, which we can understand as dividing learning into slow learning (of stable and stationary aspects of the world) and fast learning (of task-specific aspects of the world). This involves two time scales of learning, with an outer loop for meta-learning of meta-parameters and an inner loop for regular learning of regular parameters.

In fact we could have more than two time scales: think about the outer loop of evolution, the slightly faster loop of cultural learning which is somewhat stable across generations, the faster learning of individual humans, the even faster learning of specific tasks and new environments within a lifetime, and the even faster inner loops of motor control and planning which adapt policies to the specifics of an immediate objective like reaching for a fruit.

Ideally, we want to build an understanding of the world which shifts as much of the learning to the slower and more stable parts so that the inner learning loops can succeed faster, requiring less data for adaptation.

In this paper, we focus on the objective of out-of-distribution (OOD) generalization, i.e., generalizing outside of the specific distribution(s) from which training observations were drawn. A more general way to conceive of OOD generalization is with the concept of sample complexity in the face of new tasks or changed distributions. One extreme is zero-shot OOD generalization while the more general case, often studied in meta-learning setups, involves k-shot generalization (from k examples of the new distribution).

Whereas the notions of OOD generalization and OOD sample complexity tell us what we want to achieve (and hint at how we might measure it) they say nothing about how to achieve it. This is where the notion of systematic generalization becomes interesting.

Systematic generalization is a phenomenon which was first studied in linguistics because it is a core property of language: the meaning for a novel composition of existing concepts (e.g. words) can be derived systematically from the meaning of the composed concepts.

This very clearly exists in language, but humans benefit from it in other settings, e.g., understanding a new object by combining properties of different parts which compose it. Systematic generalization even makes it possible to generalize to new combinations that have zero probability under the training distribution: it is not just that they did not occur in the training data, but that even if we had seen an infinite amount of training data from our training distribution, we would not have any sample showing this particular combination.

For example, when you read a science fiction scenario for the first time, that scenario could be impossible in your life, or even in the aggregate experiences of billions of humans living today, but you can still imagine it and make sense of it (e.g., predict the end of the scenario from the beginning).

Empirical studies of systematic generalization were performed by (Bahdanau et al., 2018, 2019), where particular forms of combinations of linguistic concepts were present in the training distribution but not in the test distribution, and current methods take a hit in performance, whereas humans would be able to answer such questions easily.

Humans use inductive biases providing forms of compositionality, making it possible to generalize from a finite set of combinations to a larger set of combinations of concepts. Deep learning already benefits from a form of compositional advantage with distributed representations, which are at the heart of why neural networks work so well.

There are theoretical arguments about why distributed representations can bring a potentially exponential advantage, if this matches properties of the underlying data distribution. Another advantageous form of compositionality in deep nets arises from the depth itself, i.e., the composition of functions, with provable up to exponential advantages under the appropriate assumptions.

However, a form of compositionality that we propose here and should be better incorporated in deep learning is the form called systematicity defined by linguists, and more recently systematic generalization in machine learning papers.

Current deep learning methods tend to overfit the training distribution. This would not be visible by looking at a test set from the same distribution as the training set, so we need to change our ways of evaluating the success of learning because we would like our learning agents to generalize in a systematic way, out-of-distribution.

This only makes sense if the new environment has enough shared components or structure with previously seen environments, which corresponds to certain assumptions on distributional changes, bringing back the need for appropriate inductive biases, about distributions (e.g., shared components) as well as about how they change (e.g., via agents' interventions).