一、概率上限值的来源

train： $A$ 根据给定训练集 $D$ 在 $H$ 中选出 $g$ ，使得 $E_{in}(g)$ 约等于0；
test： $g$ 在整个输入空间 $X$ 上的表现要约等于在训练集 $D$ 上的表现，使得 $E_{out}(g)$ 约等于 $E_{in}(g)$ 。

图1.1 学习的可行性

对于 $P_{D}(BAD \ D) \le 2Mexp(-2\epsilon^2N)$ 这个不等式来说，
如果 $|H|$ 小，更易保证test（不等式右式小），难保证train（选择少）；
如果 $|H|$ 大，更易保证train（选择多），难保证test（不等式右式大）。
如果 $|H|$ 无限呢？ $2Mexp(-2\epsilon^2N)$ 可能大于1了，对于概率值上限来说失去意义。那能否用个有限值代替 $|H|$ 呢？看一下 $2Mexp(-2\epsilon^2N)$ 这个上限的来源。

图1.2 概率上限的来源

从图1.2中可以看出，求概率上限值的本质是求并集，但是得出 $2Mexp(-2\epsilon^2N)$ 这个式子是在默认无交集的情况下求的并集。实际上， $A$ 确定后， $H$ 形式也确定。给定 $D$ ，在 $H$ 里存在相似的 $h$ ，这些 $h$ 在 $D$ 上的表现一致，即存在交集。所以， $2Mexp(-2\epsilon^2N)$ 这个式子作为上限来说过大了。

二、成长函数

给定 $D$ ，可通过将 $H$ 里相似 $h$ 分到同类里（同类里 $h$ 的数目可能是无限的），将 $|H|$ 变为类数，就可能将无限的 $|H|$ 变为有限的类数。
定义给定 $D$ 下，将 $|H|$ 分得的类为dichotomies（二分法），每一个dichotomy在 $D$ 上表现相同。假设 $D$ 里有2个样本点，将 $D$ 分为OO、OX、XO、XX的 $h$ 分别归为一类，共有4类。可以发现dichotomies的数量是依赖于具体 $D$ 和 $H$ 的，但是dichotomies的数量的最大值只依赖与 $D$ 里样本点的个数 $N$ 和 $H$ 。例如，在感知器算法中， $N=2$ 时，最大值不超过2的 $N$ 次方，这里是4。
定义dichotomies的数量的最大值为 $N$ 的成长函数，记为 $m_H(N)$ ，其只和 $H$ 、 $N$ 有关。即，给定样本数 $N$ ， $H$ 里假设类数是小于等于 $m_H(N)$ 的。例如，对于2维感知机， $m_H(1)=2$ ， $m_H(2)=4$ ， $m_H(3)=8$ ， $m_H(4)=14$ 。