As well as the bound on the number of examples required per task for good generalization across those tasks, Theorem 8 also shows that features performing well on O(W) *tasks* will generalize well to novel tasks, where W is the number of parameters in the feature map. Given that for many feature learning problems W is likely to be quite large (recall Note 4 in Section 3.3.3), it would be useful to know that O(W) tasks are in fact *necessary* without further restrictions on the environmental distributions Q generating the tasks. Unfortunately, we have not yet been able to show such a lower bound.

There is some empirical evidence suggesting that in practice the upper bound on the number of tasks may be very weak. For example, in Baxter and Bartlett (1998) we reported experiments in which a set of neural network features learnt on a subset of only 400 Japanese characters turned out to be good enough for classifying some 2600 unseen characters, even though the features contained several hundred thousand parameters. Similar results may be found in Intrator and Edelman (1996)
and in the experiments reported in Thrun (1996) and Thrun and Pratt (1997, chapter 8). While this gap between experiment and theory may be just another example of the looseness inherent in general bounds, it may also be that the analysis can be tightened. In particular, the bound on the number of tasks is insensitive to the size of the class of output functions (the class G in Section 3.1),
which may be where the looseness has arisen.

3.4.1 UPPER AND LOWER BOUNDS FOR LEARNING n TASKS WITH BOOLEAN HYPOTHESIS
SPACE FAMILIES
First we recall some concepts from the theory of Boolean function learning. Let H be a class of Boolean functions on X and x = (x1; : : : ; xm) 2 Xm. Hjx is the set of all binary vectors obtainable by applying functions in H to x:

$${\mathcal{H}}_{|x}:=\{(\,h(x_{1}),\ldots,h(x_{m})\,)\colon h\in{\mathcal{H}}\,\}.$$
$$\mathrm{\,\,\,r l y\,}|{\mathcal{H}}_{|x}|\leq2^{m}.\ \mathrm{If\,}|{\mathcal{H}}_{|x}|\,=\,2^{m}\ \mathrm{\bf{v}}$$

Clearly jHjxj  2m. If jHjxj = 2mwe say H *shatters* x. The *growth function* of H is defined by

$$\Pi_{\mathcal{H}}\left(m\right):=\operatorname*{max}_{x\in X^{m}}\left|{\mathcal{H}}_{|x}\right|.$$
$\iota\left(m\right)\,=\,2^m$ }  

The *Vapnik-Chervonenkis dimension* VCdim(H) is the size of the largest set shattered by H:

$\mathbb{X}$ 4. 
VCdim(H) := maxfm : H(m) = 2mg:
An important result in the theory of learning Boolean functions is Sauer's Lemma (Sauer, 1972), of which we will also make use. Lemma 9 (Sauer's Lemma). For a Boolean function class H *with* VCdim(H) = d,

$$\Pi_{\mathcal{H}}\left(m\right)\leq\sum_{i=0}^{d}\binom{m}{i}\,\leq\,\left(\frac{e m}{d}\right)^{d}\,,$$

for all positive integers m.

We now generalize these concepts to learning n tasks with a Boolean hypothesis space family.