原文地址：https://www.jianshu.com/p/81e2853cb2c9
一、概率上限值的来源
train：(A)根据给定训练集(D)在(H)中选出(g)，使得(E_{in}(g))约等于0；
test：(g)在整个输入空间(X)上的表现要约等于在训练集(D)上的表现，使得(E_{out}(g))约等于(E_{in}(g))。
对于(P_{D}(BAD D) le 2Mexp(-2epsilon^2N))这个不等式来说，
如果(|H|)小，更易保证test（不等式右式小），难保证train（选择少）；
如果(|H|)大，更易保证train（选择多），难保证test（不等式右式大）。
如果(|H|)无限呢？(2Mexp(-2epsilon^2N))可能大于1了，对于概率值上限来说失去意义。那能否用个有限值代替(|H|)呢？看一下(2Mexp(-2epsilon^2N))这个上限的来源。
从图1.2中可以看出，求概率上限值的本质是求并集，但是得出(2Mexp(-2epsilon^2N))这个式子是在默认无交集的情况下求的并集。实际上，(A)确定后，(H)形式也确定。给定(D)，在(H)里存在相似的(h)，这些(h)在(D)上的表现一致，即存在交集。所以，(2Mexp(-2epsilon^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)。
可以看出，成长函数可能是多项式型的（好的，能保证只要(N)足够大，(2m_H(N)exp(-2epsilon^2N))小），也可能是指数型的（坏的）。那对于2维及以上维数的感知机，成长函数是多项式型的吗？
三、断点
shatter（使粉碎）：如果(H)里的假设能够保证(k)个输入能够输出任意标签的组合，称(H)能shatter这(k)个输入。
break point (k)：(H)不能shatter这(k)个输入，称(k)为断点。
猜想(conjecture)，只要存在断点，就能保证成长函数是多项式型，进而保证了test？！