
## 2.5 Choosing The Hypothesis Space Family H .

Theorem 2 only provides conditions under which ^erz(H) and erQ(H) are close, it does not guarantee that erQ(H) is actually small. This is governed by the choice of H . If H contains a hypothesis space H with a small value of erQ(H) and the learner is able to find an H 2 H minimizing error on the (n; m) sample z (i.e., minimizing ^erz(H)), then, for sufficiently large n and m, Theorem 2 ensures that with high probability erQ(H) will be small. However, a bad choice of H will mean there is no hope of finding an H with small error. In this sense the choice of H represents the *hyper-bias* of the learner.

Note that from a sample complexity point of view, the *optimal* hypothesis space family to choose is one containing a single, minimal hypothesis space H that contains good solutions to all of the problems in the environment (or at least a set of problems with high Q-probability), and no more.

For then there is no bias learning to do (because there is no choice to be made between hypothesis spaces), the output of the bias learning algorithm is guaranteed to be a good hypothesis space for the environment, and since the hypothesis space is minimal, learning any problem within the environment using H will require the smallest possible number of examples. However, this scenario is analagous to the trivial scenario in ordinary learning in which the learning algorithm contains a single, optimal hypothesis for the problem being learnt. In that case there is no learning to be done, just as there is no bias learning to be done if the correct hypothesis space is already known.

At the other extreme, if H contains a single hypothesis space H consisting of all possible functions from X ! Y then bias learning is impossible because the bias learner cannot produce a restricted hypothesis space as output, and hence cannot produce a hypothesis space with improved sample complexity requirements on as yet unseen tasks.

Focussing on these two extremes highlights the minimal requirements on H for successful bias learning to occur: the hypothesis spaces H 2 H must be strictly smaller than the space of all functions X ! Y , but not so small or so "skewed" that none of them contain good solutions to a large majority of the problems in the environment.

It may seem that we have simply replaced the problem of selecting the right bias (i.e., selecting the right hypothesis space H) with the equally difficult problem of selecting the right hyper-bias (i.e.,
the right hypothesis space family H ). However, in many cases selecting the right hyper-bias is far easier than selecting the right bias. For example, in Section 3 we will see how the feature selection problem may be viewed as a bias selection problem. Selecting the right features can be extremely difficult if one knows little about the environment, with intelligent trial-and-error typically the best one can do. However, in a bias learning scenario, one only has to specify that a set of features should exist, find a loosely parameterised set of features (for example neural networks), and then learn the features by sampling from multiple related tasks.

## 2.6 Learning Multiple Tasks

It may be that the learner is not interested in learning to learn, but just wants to learn a fixed set of n tasks from the environment (P; Q). As in the previous section, we assume the learner starts out with a hypothesis space family H , and also that it receives an (n; m)-sample z generated from the n distributions P1; : : : ; Pn. This time, however, the learner is simply looking for n hypotheses
(h1; : : : ; hn), all contained in the same hypothesis space H, such that the average generalization error of the n hypotheses is minimal. Denoting (h1; : : : ; hn) by h and writing P = (P1 ; : : : ; Pn),