(as stated, A is a deterministic bias learner, however it is trivial to extend our results to stochastic learners).

Note that in this paper we are concerned only with the sample complexity properties of a bias learner A; we do not discuss issues of the computability of A.

Since A is searching for entire hypothesis spaces H within a family of such hypothesis spaces H , there is an extra representational question in our model of bias learning that is not present in ordinary learning, and that is how the family H is represented and searched by A. We defer this discussion until Section 2.5, after the main sample complexity results for this model of bias learning have been introduced. For the specific case of learning a set of features suitable for an environment of related learning problems, see Section 3.

Regardless of how the learner chooses its hypothesis space H, if we have a uniform bound (over all H 2 H ) on the probability of large deviation between ^erz(H) and erQ(H), and we can compute an upper bound on ^erz(H), then we can bound the bias learner's "generalization error" erQ(H).

With this view, the question of generalization within our bias learning model becomes: how many tasks (n) and how many examples of each task (m) are required to ensure that ^erz(H) and erQ(H)
are close with high probability, uniformly over all H 2 H ? Or, informally, how many tasks and how many examples of each task are required to ensure that a hypothesis space with good solutions to all the training tasks will contain good solutions to novel tasks drawn from the same environment?

It turns out that this kind of uniform convergence for bias learning is controlled by the "size" of certain function classes derived from the hypothesis space family H , in much the same way as the VC-dimension of a hypothesis space H controls uniform convergence in the case of Boolean function learning (Theorem 1). These "size" measures and other auxiliary definitions needed to state the main theorem are introduced in the following subsection.

## 2.3 Covering Numbers

Definition 1. For any hypothesis h : X ! Y *, define* hl : X - Y ! [0; 1℄ by

$${\mathit{f i n e\ h_{l}}}:\,X\,\times Y\,\rightarrow[0,\,1]\,\,b y$$
$$h_{l}(x,y):=l(\,h(x),y\,)$$
hl(x; y) := l(h(x); y) (10)
For any hypothesis space H in the hypothesis space family H *, define*

$${\mathcal{H}}_{l}:=\{h_{l}:\,h\in{\mathcal{H}}\}.$$
Hl := fhl : h 2 Hg: (11)
_For any sequence of $n$ hypotheses $(h_{1},\ldots,h_{n})$, define $(h_{1},\ldots,h_{n})\colon(X\times Y)^{n}\to[0,1]$ by_
$$\mathbb{H},\,d e f i n e$$
$$(\,h_{1}\,,\ldots\,,\,h_{n}\,)_{l}(\,x_{1}\,,y_{1}\,,\ldots\,,x_{n}\,,y_{n}\,):=\frac{1}{n}\sum_{i=1}^{n}l\big{(}\,h_{i}\,(\,x_{i}\,),\,y_{i}\,\big{)}.$$

$$(10)$$
$$(11)$$
$$(12)$$
$$(13)$$
$$(14)$$

We will also use hl *to denote* (h1; : : : ; hn)l . For any H in the hypothesis space family H *, define*

$$(h_{1},\,\cdot\,\cdot\,,\,h_{n})_{l}.\,\,F o r\,\,a$$
$${\mathcal{H}}_{l}^{n}:=\{(h_{1},\ldots,h_{n})_{l}\colon h_{1},\ldots,h_{n}\in{\mathcal{H}}\}.$$

:= f(h1; : : : ; hn)l : h1; : : : ; hn 2 Hg: (13)
$$D e f i n e$$
$$\mathbb{H}_{l}^{n}:=\bigcup_{\mathcal{H}\in\mathbb{H}}{\mathcal{H}}_{l}^{n}.$$

: (14)
159