
| Symbol             | Description                        | First Referenced       |     |
|--------------------|------------------------------------|------------------------|-----|
| N ("; F; d[P;Gl ℄) | Covering number of F               | 166                    |     |
| CGl ("; F)         | Capacity of F                      | 166                    |     |
| Hw                 | Neural network hypothesis space    | 167                    |     |
| Hjx                | H restricted to vector x           | 172                    |     |
| H(m)                    | Growth function of H               | 172                    |     |
| VCdim(H)           | Vapnik-Chervonenkis dimension of H | 172                    |     |
| Hjx                | H restricted to matrix x           | 173                    |     |
| H jx               | H                                  | restricted to matrix x | 173 |
| H (n; m)                    | Growth function of H               | 173                    |     |
| dH (n)             | Dimension function of H            | 173                    |     |
| d(H )              | Upper dimension function of H      | 173                    |     |
| d(H )              | Lower dimension function of H      | 173                    |     |
| optP(H n )         | Optimal performance of H n on P    | 175                    |     |
| d                    | Metric on R+                       | 179                    |     |
| h1      hn                    | Average of h1, : : : , hn          | 179                    |     |
| H1      Hn                    | Set of h1      hn                                    | 180                    |     |
| (2m;n)             | Permutations on integer pairs      | 182                    |     |
| z                    | Permuted z                         | 182                    |     |
| dz(h; h0 )         | Empirical l1 metric on functions h | 182                    |     |
| ^erP(H)            | Optimal average error of H on P    | 185                    |     |

## 2. The Bias Learning Model

In this section the bias learning model is formally introduced. To motivate the definitions, we first describe the main features of ordinary (single-task) supervised learning models.

## 2.1 Single-Task Learning

Computational learning theory models of supervised learning usually include the following ingredients:
 An *input space* X and an *output space* Y ,

 a *probability distribution* P on X - Y , a *loss function* l : Y - Y ! R, and a *hypothesis space* H which is a set of *hypotheses* or functions h : X ! Y .
As an example, if the problem is to learn to recognize images of Mary's face using a neural network, then X would be the set of all images (typically represented as a subset of Rdwhere each component is a pixel intensity), Y would be the set f0; 1g, and the distribution P would be peaked over images of different faces and the correct class labels. The learner's hypothesis space H would be a class of neural networks mapping the input space Rdto f0; 1g. The loss in this case would be discrete loss:

$$l(y,y^{\prime}):=\left\{\begin{array}{l l}{{1}}&{{\mathrm{if}\;y\neq y^{\prime}}}\\ {{0}}&{{\mathrm{if}\;y=y^{\prime}}}\end{array}\right.$$
$$(1)$$
0 if y = y0(1)