当(Nge2)，(kge3)时，易得：(m_H(N))被(N^{k-1})给bound住。

VC维：最小断点值(-1)或(H)能shatter的最大(k)值。
这里的(k)指的是存在(k)个输入能被(H)给shatter，不是任意(k)个输入都能被(H)给shatter。如：2维感知机能shatter平面上呈三角形排列的3个样本点，却shatter不了平面上呈直线排列的3个样本点，因为当另外2个点标签值一致时，中间那个点无法取与它们相反的标签值。若无断点，则该(H)下，VC维为无穷。所以，存在断点即可以推出有限VC维。

(d)维感知器算法下，VC维(=d+1)？！

证明如下：

• 当(D)的大小为(d+1)时，
  对于矩阵(X)，易得(X)是((d+1)*(d+1))的矩阵，(X)的秩小于等于(d+1)。
  所以，存在(X)，行向量之间线性无关，每一行向量可取任意标签值。
  因此，(H)能shatter这个(X)对应的(d+1)个样本点，即VC维(ge d+1)。
• 当(D)的大小为(d+2)时，
  对于矩阵(X)，易得(X)是((d+2)*(d+1))的矩阵，(X)的秩小于(d+2)。
  所以，任意(X)，总有一行与其他行向量线性相关，该行的标签值受到限制。
  因此，(H)不能shatter这个(X)对应的(d+2)个样本点，即VC维(le d+1)。

综上所述，易得对于(d)维感知器，其VC维(=d+1)。

二、VC维的意义

VC维，反映的是(H)的*度，可粗略认为是*参数的个数（不总是）。

VC维增大，(E_{in})减小，模型复杂度增大；VC维减小，(E_{in})增大，模型复杂度减小。

给定差异容忍度(epsilon)、概率容忍度(delta)、VC维，求满足条件需要多少样本。
理论上，(N)约等于10000倍的VC维；实际上，(N)取10倍的VC维就足够了。

可见，VC维是十分松弛的，

1. 使用霍夫丁不等式，不管(f)、输入分布(P)；
2. 使用成长函数，不管具体的(D)；
3. 使用(N)的多项式，不管(H)（VC维相同）；
4. 使用联合bound，不管(A)。

之所以使用VC维是为了定性分析VC维里包含的信息，而且它对所有模型都近似松弛。