as a (potentially infinite) collection of distinct binary classification problems. In that case, the goal of bias learning is not to find a single n-output network that can classify some subset of n faces well. It is to learn a set of features that can reliably be used as a fixed preprocessing for distinguishing any single face from other faces. This is the new thing provided by Theorem 8: it tells us that provided we have trained our n-output neural network on sufficiently many examples of *sufficiently* many tasks, we can be confident that the common feature map learnt for those n tasks will be good for learning any new, as yet unseen task, provided the new task is drawn from the same distribution that generated the training tasks. In addition, learning the new task only requires estimating the k output node parameters for that task, a vastly easier problem than estimating the parameters of the entire network, from both a sample and computational complexity perspective. Also, since we have high confidence that the learnt features will be good for learning novel tasks drawn from the same environment, those features are themselves a candidate for further study to learn more about the nature of the environment. The same claim could not be made if the features had been learnt on too small a set of tasks to guarantee generalization to novel tasks, for then it is likely that the features would implement idiosyncrasies specific to those tasks, rather than "invariances" that apply across all tasks.

When viewed from a bias (or feature) learning perspective, rather than a traditional n-class classification perspective, the bound m on the number of examples required of each task takes on a somewhat different meaning. It tells us that provided n is large (i.e., we are collecting examples of a large number tasks), then we really only need to collect a few more examples than we would otherwise have to collect if the feature map was already known (k+W=n examples vs. k examples).

So it tells us that the burden imposed by feature learning can be made negligibly small, at least when viewed from the perspective of the sampling burden required of each task.

## 3.4 Learning Multiple Tasks With Boolean Feature Maps

Ignoring the accuracy and confidence parameters " and Æ, Theorem 8 shows that the number of examples required of each task when learning n tasks with a common neural-network feature map is bounded above by O(k + W=n), where k is the number of features and W is the number of adjustable parameters in the feature map. Since O(k) examples are required to learn a single task once the true features are known, this shows that the upper bound on the number of examples required of each task decays (in order) to the minimum possible as the number of tasks n increases.

This suggests that learning multiple tasks is advantageous, but to be truly convincing we need to prove a lower bound of the same form. Proving lower bounds in a real-valued setting (Y = R) is complicated by the fact that a single example can convey an infinite amount of information, so one typically has to make extra assumptions, such as that the targets y 2 Y are corrupted by a noise process. Rather than concern ourselves with such complications, in this section we restrict our attention to Boolean hypothesis space families (meaning each hypothesis h 2 H 1 maps to Y = f1g and we measure error by discrete loss l(h(x); y) = 1 if h(x) 6= y and l(h(x); y) = 0 otherwise).

We show that the sample complexity for learning n tasks with a Boolean hypothesis space family H is controlled by a "VC dimension" type parameter dH (n) (that is, we give nearly matching upper and lower bounds involving dH (n)). We then derive bounds on dH (n) for the hypothesis space family considered in the previous section with the Lipschitz sigmoid function  replaced by a hard threshold (linear threshold networks).