Hence, if

$$m>\left(\frac{W}{n}+k+1\right)\log_{2}\left(\frac{emn\big{(}k+l+1\big{)}}{W+n\big{(}k+1\big{)}}\right)\tag{52}$$

then H (n; m) < 2nm and so by definition dH (n)  m. For all a > 1, observe that x > a log2 x if x = 2a log2 2a. Setting x = emn(k + l + 1)=(W + n(k + 1)) and a = e(k + l + 1) shows that
(52) is satisfied if m = 2(W=n + k + 1) log2(2e(k + l + 1)).

Theorem 16. Let H be as in Theorem 15 with the following extra restrictions: d  3, l  k and k  d*. Then*

$$d_{\mathbb{H}}\left(n\,\right)\,\geq\,{\frac{1}{2}}\left(\,\left\lfloor{\frac{W}{2n}}\right\rfloor\,+\,k+1\,\right)$$

Proof. We bound d(H ) and d(H ) and then apply Lemma 10. In the present setting H 1contains all three-layer linear-threshold networks with d input nodes, l hidden nodes in the first hidden layer, k hidden nodes in the second hidden layer and one output node. From Theorem 13 in Bartlett (1993),
we have

$$\mathrm{VCdim}(\mathbb{H}^{1})\geq d l+{\frac{l(k-1)}{2}}+1,$$

which under the restrictions stated above is greater than W=2. Hence d(H )  W=2.

As k  d and l  k we can choose a feature weight assignment so that the feature map is the identity on k components of the input vector and insensitive to the setting of the reminaing d  k components. Hence we can generate k + 1 points in X whose image under the feature map is shattered by the linear threshold output node, and so d(H ) = k + 1.

Combining Theorem 15 with Corrolary 13 shows that

$$m\geq O\left({\frac{1}{\varepsilon^{2}}}\left[\left({\frac{W}{n}}+k+1\right)\log{\frac{1}{\varepsilon}}+{\frac{1}{n}}\log{\frac{1}{\delta}}\right]\right)$$

examples of each task suffice when learning n tasks using a linear threshold hypothesis space family, while combining Theorem 16 with Theorem 14 shows that if

$$m\,\leq\,\Omega\left(\frac{1}{\varepsilon^{2}}\,\left[\left(\frac{W}{n}+\,k+1\right)+\frac{1}{n}\log\frac{1}{\delta}\right]\right)$$

then any learning algorithm will fail on some set of n tasks.

## 4. Conclusion

The problem of inductive bias is one that has broad significance in machine learning. In this paper we have introduced a formal model of inductive bias learning that applies when the learner is able to sample from multiple related tasks. We proved that provided certain covering numbers computed from the set of all hypothesis spaces available to the bias learner are finite, any hypothesis space that contains good solutions to sufficiently many training tasks is likely to contain good solutions to novel tasks drawn from the same environment.

In the specific case of learning a set of features, we showed that the number of examples m required of each task in an n-task training set obeys m = O(k + W=n), where k is the number of