评价一个训练集选择的好坏：

$$ P\left(\mathcal{D}_{train}\ is\ \boldsymbol{bad}\right) \leq |\mathcal{H}| \cdot 2exp(-2N\varepsilon^2) $$

$|\mathcal{H}|$：函数的可选数目。

$N$：training set 的大小。

从这个式子可以看出，$|\mathcal{H}|$ 越大或 $N$ 越小时右侧的值越小。

当右侧的值较小时，就越可以满足：

$$ L\left(h^{train}, \mathcal{D}{all}\right) - L\left(h^{all}, \mathcal{D}{all}\right) \leq \delta $$

这里有个矛盾： 当函数的可选数目多时，也就是模型复杂时，得到的 $P\left(\mathcal{D}{train}\ is \ \boldsymbol{bad}\right)$ 就会偏大，此时在测试集和训练集上的 loss 差距就会较大； 而当函数的可选数目少时，也就是模型简单时，$L\left(h^{all}, \mathcal{D}{all}\right)$ 本身将会变大，则显然这将是个坏模型。

据说深度学习可以解决这个问题，让我们拭目以待。