7.The VC Dimension

前几节着重介绍了机器能够学习的条件并做了详细的推导和解释。机器能够学习必须满足两个条件：

• 假设空间H的Size M是有限的，即当N足够大的时候，那么对于假设空间中任意一个假设g，$E_{out} \approx E_{in}$Eout​≈Ein​。
• 利用算法A从假设空间H中，挑选一个g，使 $E_{in}(g) \approx 0$Ein​(g)≈0，则 $E_{out} \approx 0$Eout​≈0。

这两个条件，正好对应test和trian两个过程。train 的目的是使损失期望 $E_{in}(g) \approx 0$Ein​(g)≈0；test 的目的是使将算法用到新的样本时的损失期望也尽可能小，$E_{out} \approx 0$Eout​≈0。

正因为如此，上次课引入了 break point，并推导出只要 break point 存在，则M有上界，一定存在 $E_{out} \approx E_{in}$Eout​≈Ein​。

本文主要介绍VC Dimension的概念。同时总结VC Dimension与 $E_{in}(g) \approx 0$Ein​(g)≈0，$E_{out} \approx 0$Eout​≈0 ，模型复杂度的关系。

---

7.1 Definition of VC Dimension

如果一个假设空间 $H$H 有break point k，那么它的成长函数是有界的，它
的上界称为Bound function。由数学归纳法知，Bound function也是有界的，且上界为 $N^{k-1}$Nk−1。从下面的表格可以看出，$N(k-1)$N(k−1) 比 $B(N,k)$B(N,k) 松弛很多。

则根据上一节课的推导，VC bound就可以转换为：

这样，不等式就只与k和N相关，一般情况下样本N足够大，所以只考虑k值。有如下结论：

• 若假设空间H有break point k，且N足够大，则根据VC bound理论，算法有良好
  的泛化能力；

• 在假设空间中选择一个矩g，使 $E_{in}(g) \approx 0$Ein​(g)≈0，则其在全集数据中的错误率会较低。
  

VC Dimension：某假设集H能够shatter的最多inputs的个数，即最大完全正确的分类能力。（注意，只要存在一种分布的inputs能够正确分类也满足）。

shatter ：英文意思是“粉碎”，即对于inputs的所有情况都能列举出来。例如对N个输入，如果能够将 $2^N$2N 种情况都列出来，则称该N个输入能够被假设集H shatter。

break point：假设空间（假设集）H 不能被shatter任何分布类型的inputs的最少个数，亦即不能满足完全分类情形的样本数量。完全二分类（shattered）是可分出 $2^N$2N 种二分类（dichotomy）的情形。则VC Dimension等于break point的个数 $k$k 减一。

回顾一下之前介绍的4种例子，它们对应的VC Dimension是多少：

用 $d_{vc}$dvc​ 代替 $k$k，VC bound的问题就转换为与 $d_{vc}$dvc​ 和 N 相关了。同时，如果一个假设空间H的 $d_{vc}$dvc​ 确定了，则就能满足机器能够学习的第一个条件，与算法、样本数据分布和目标函数都没有关系。

---

7.2 VC Dimension of Perceptrons

回顾2D PLA算法，已知Perceptron的k=4，即 $d_{vc} = 3$dvc​=3。以下两个条件保证了2维线性可分的数据是可以学习的。

1. 线性可分的数据通过PLA算法运行足够长的时间（T步骤足够大），则会找出一条可以正确分类的直线，使得样本中没有产生分错类的情况，即$E_{in}(g) \approx 0$Ein​(g)≈0；

2. 在训练样本和整个数据集都服从同一分布P的前提下，有VC限制，保证了在$d_{vc} = 3$dvc​=3 训练样本N足够大时，$E_{out}(g) \approx E_{in}(g)$Eout​(g)≈Ein​(g) 。
   以上两个条件共同得出：如果找到一个g，使$E_{in}(g) \approx 0$Ein​(g)≈0，那么就能证明PLA是可以学习的。
   

如果是多维的Perceptron，它对应的$d_{vc}$dvc​又等于多少呢？已知在1D Perceptron，$d_{vc} = 2$dvc​=2，在2D Perceptron，$d_{vc} = 3$dvc​=3，那么有如下假设：$d_{vc} = d+1$dvc​=d+1 ，其中d为维数。

要证明的话，只需分两步证明：

首先证明第一个不等式： $d_{vc} \ge d+1$dvc​≥d+1。

在 $d$d 维里，只要找到某一类的 $d+1$d+1 个输入（inputs）可以被 shatter ，那么必然可证上式成立。所以，有意构造一个 $d$d 维的矩阵 $X$X 能够被 shatter 即可。不妨构造一个输入样本集，假设样本为一个行向量，其中第一个样本为0向量，第二个样本是其第一个分量为1其他分量为0的向量，第三个样本是其第二个分量为1其他分量为0的向量，以此类推，第d+1个样本是其第d个分量为1其他分量为0的向量，如：$X_1 = [0,0,...,0]$X1​=[0,0,...,0]，$X_2 = [1,0,...,0]$X2​=[1,0,...,0]，$X_3 = [0,1,...,0]$X3​=[0,1,...,0]，…，$X_{d+1} = [0,0,...,1]$Xd+1​=[0,0,...,1]， $X$X 是 $d$d 维的，有 $d + 1$d+1 个输入，每个输入加上第0个维度的分量，其值为1（阈值 $b$b 变为 $w_0$w0​ 所乘的样本分量），得到的 $X$X 矩阵为：

矩阵中，每一行代表一个inputs，每个inputs是 $d+1$d+1 维的，共有 $d+1$d+1 个inputs。这里构造的很明显是可逆的（从第 2 行到第 $d+1$d+1 行，每一行都减去第一行得到一个对角矩阵，满秩，所以可逆）。

需要证明的是可以完全二分，关注的重点为输出标记向量 $y^T = [y_1,y_2, ... , y_{d+1}]$yT=[y1​,y2​,...,yd+1​]。只要找出各种权值向量 $w$w 能将上述输入样本集X映射到全部的二分情况下的 $y$y 上就可以了。

已知感知器可以使用 $sign(X \cdot w) = y$sign(X⋅w)=y 表示。而只要权值向量使得 $X \cdot w = y $ 成立，就一定满足 $sign(X \cdot w) = y$sign(X⋅w)=y 的需求。假设其中输入矩阵如上图中公式所示，即 $X$X 是可逆矩阵，输出向量 $y$y 的任意一种 二分类情况都可以被一个假设函数 $W$W 划分出（ $d$d 维的所有输入都能被shatter。shatter的本质是假设空间H对的所有情况的判断都是对的，即总能找到权重 $W$W，满足 $X \cdot w = y, w = X^{-1} \cdot y$X⋅w=y,w=X−1⋅y。），原因是权重向量 $w$w 满足 $w = X^{-1} \cdot y$w=X−1⋅y，即任何一种二分类情况都会有一个权重向量 $w$w 与之对应，因此满足 $d_{vc} \ge d+1$dvc​≥d+1 成立，也就证明了第一个不等式。

然后证明第二个不等式：$d_{vc} \le d+1$dvc​≤d+1。思路：证明该式不能如上，因为其要证明在所有的情况下，证明过程稍复杂，先以一个2维空间的例子为切入点。

假设一个2维空间，则需要观察在2+2个输入数据量，不妨假设这四个输入样本分别是：$x_1 = [0,0], x_2 = [1,0], x_3 = [0,1], x_4 = [1,1]$x1​=[0,0],x2​=[1,0],x3​=[0,1],x4​=[1,1]。输入数据集 $X$X 如下式所示。

$X = \left[\begin{matrix} 1&x_1\\1&x_2\\1&x_3\\1&x_4 \\ \end{matrix}\right] = \left[\begin{matrix} 1&0&0\\1&1&0\\1&0&1\\1&1&1 \\ \end{matrix}\right]$X=⎣⎢⎢⎡​1111​x1​x2​x3​x4​​⎦⎥⎥⎤​=⎣⎢⎢⎡​1111​0101​0011​⎦⎥⎥⎤​

可以想象在标记 $y_1 = -1$y1​=−1 ， $y_2 = +1, y_3 = +1$y2​=+1,y3​=+1时，$y_4$y4​ 不能为-1，如图所示。

用数学的形式如何表达？首先根据这四个样本可以确保 $x_4 = x_3 + x_2 - x_1$x4​=x3​+x2​−x1​ 成立。该式等号两边同时左乘权值向量 $w^T$wT 可得上图中式所示，这种样本间线性依赖（linear dependence）的关系导致了无法二分。

在d维里，如果对于任何的d+2个inputs，一定不能被shatter，则不等式成立。

构造一个任意的矩阵，其包含 $d+2$d+2 个inputs，该矩阵有 $d+1$d+1 列，$d+2$d+2 行。这$d+2$d+2 个向量的某一列一定可以被另外 $d+1$d+1 个向量线性表示，例如对于向量 $X_{d+2}$Xd+2​，可表示为：

$X_{d+2} = a_1 \cdot X_1 + a_2 \cdot X_2 + a_3 \cdot X_3 + \cdots + a_d \cdot X_d$Xd+2​=a1​⋅X1​+a2​⋅X2​+a3​⋅X3​+⋯+ad​⋅Xd​。其中，假设 $a_1 > 0,a_2, \cdots, a_d <0 $。如果 X_1 是正类，$。如果X1​是正类，X_2, \cdots, X_d$ 均为负类，则存在 $W$W ，得到如下表达式：

$X_{d+2} \cdot W = a_1 \cdot X_1 \cdot W + a_2 \cdot X_2 \cdot W + a_3 \cdot X_3 \cdot W + \cdots + a_d \cdot X_d \cdot W > 0$Xd+2​⋅W=a1​⋅X1​⋅W+a2​⋅X2​⋅W+a3​⋅X3​⋅W+⋯+ad​⋅Xd​⋅W>0

因为其中第一项大于0，代表正类；剩余项小于0，代表负类。所有对于这种情况，一定是正类（因为 $a_i$ai​ 和 $y^T$yT 的第 $i$i 个分量同号，$i = 1,2,...,d+1$i=1,2,...,d+1）。因此在任何d+2个输入数据集中必然都存在不能满足的二分类（ 个inputs无法被shatter），即刻证得：$d_{vc} \le d+1$dvc​≤d+1。

---

7.3 Physical Intuition VC Dimension

上一节内容将感知器中数据的维度与VC维联系到了一起，也明白了VC Dimension中的 Dimension 的含义。而在感知器中，数据样本的维度又与权值向量的维度一致，不同的权值向量对应着不同的假设函数，因此称假设函数的参数 $ w^T = [w_0,w_1,…,w_d]$是假设空间上的自由度（degree of freedom）。自由度是可以任意调节的，如同上图中的旋钮一样，可以调节。如果从假设空间的数量M = |H|角度上描述，则自由度是无限大的；但是从感知器在二元分类上这一限制条件入手，则可以使用VC维作为自由度的衡量。VC Dimension代表了假设空间的分类能力，即反映了H的自由度，产生dichotomy的数量，也就等于features的个数，但也不是绝对的。

上图中Positive Rays 的例子中，VC Dimension $d_{vc} = 1$dvc​=1时，假设空间有1个参数，即阈值；Positive Intervals 的例子中，VC Dimension $d_{vc} = 1$dvc​=1 时，假设空间有2个参数，即左右边界点。因此在大部分情况下，VC Dimension $d_{vc}$dvc​ 大致 $=$= 假设空间参数的个数。

例如，对2D Perceptrons，线性分类，$d_{vc} = 3$dvc​=3 ，则 $W = {w_o,w_1,w_2}$W=wo​,w1​,w2​，亦即只要3个features就可以进行学习，自由度为3。M与 $d_{vc}$dvc​ 是成正比的，从而得到如下结论：

	$d_{vc}$dvc​很小的时候	$d_{vc}$dvc​很大的时候
第一个条件 ①	满足，$P_D[BAD D] \le 4 \cdot (2N)^{d_{vc}}\cdot exp(...)$PD​[BADD]≤4⋅(2N)dvc​⋅exp(...)时，不好情况出现的几率变小了	不满足，$P_D[BAD D] \le 4 \cdot (2N)^{d_{vc}} \cdot exp(...)$PD​[BADD]≤4⋅(2N)dvc​⋅exp(...) 时，不好情况出现的几率变大了
第二个条件 ②	不满足，在 $d_{vc}$dvc​变小时，假设的数量变小，算法的选择变小，可能无法找到 $E_{in}(g) \approx 0$Ein​(g)≈0的假设	满足，在 $d_{vc}$dvc​变大时，假设的数量变大，算法的选择变大，找到 $E_{in}(g) \approx 0$Ein​(g)≈0的假设

在一些书中，参数较多的模型都称为复杂模型，很少给出解释，这一节的内容给出了很好的解释，因为在很多情况下模型参数的个数大致等于VC维的个数。参数越多或者说模型越复杂，越有可能找出使 $E_{in}$Ein​ 最小的假设函数g，但是这需要大量训练样本的支持，因为只有在训练样本数量N足够大时，才能使更复杂（即参数更多或者说VC维更大）的模型出现不好情况的几率变小，如上表的右列。

---

7.4 Interpreting VC Dimension

进一步探讨 VC Dimension的意义。VC Bound：

根据之前的泛化不等式，如果$|E_{in} - E _{out}|> \epsilon$∣Ein​−Eout​∣>ϵ，即出现 BAD 情况的概率最大不超过 $\delta$δ。反过来，归于GOOD情况发生的概率最小为 $1-\delta$1−δ，则对上述不等式进行重新推导：

$\epsilon$ϵ 表现了假设空间H的泛化能力，$\epsilon$ϵ 越小，泛化能力越大。

至此，已经推导出泛化误差 $E_{out}$Eout​ 的边界，因为我们更关心其上界（ $E_{out}$Eout​ 可能的最大值），即：

上述不等式的右边第二项称为模型复杂度（model complexity），其模型复杂度与样本数量N、假设空间H( $d_{vc}$dvc​)、$\epsilon$ϵ 有关。$E_{out}$Eout​ 由 $E_{in}$Ein​ 共同决定。$E_{out}$Eout​、模型复杂度、 $E_{in}$Ein​ 随 $d_{vc}$dvc​变化的关系如上图所示。由上图可知：

• $d_{vc}$dvc​ 越大，$E_{in}$Ein​ 越小，$\Omega$Ω 越大（复杂）。
• $d_{vc}$dvc​ 越小，$E_{in}$Ein​ 越大，$\Omega$Ω 越小（简单）。
• 随着 $d_{vc}$dvc​ 增大， $E_{out}$Eout​ 会先减小再增大。

所以，为了得到最小的 $E_{out}$Eout​，不能一味地增大 $d_{vc}$dvc​ 以减小$E_{in}$Ein​，因为 $E_{in}$Ein​ 太小的时候，模型复杂度会增加，造成 $E_{out}$Eout​ 变大。也就是说，选择合适的 $d_{vc}$dvc​，选择的features个数要合适。

VC维除了表示模型复杂度之外还可以表示样本复杂度（Sample Complexity）：

如果选定 $d_{vc}$dvc​，样本数据D选择多少合适呢？通过下面一个例子可以帮助我们理解：

通过计算得到N=29300，刚好满足 $\delta = 0.1$δ=0.1 的条件。N大约是 $d_{vc}$dvc​ 的10000倍。这个数值太大了，实际中往往不需要这么多的样本数量，大概只需要 $d_{vc}$dvc​ 的10倍就够了。N的理论值之所以这么大是因为VC Bound 是非常宽松的约束，得到的是一个比实际大得多的上界。宽松约束的四个主要原因：

1. 霍夫丁不需要知道未知的 $E_{out}$Eout​，VC限制可以用于各种分布，各种目标函数；
2. 成长函数 $m_H(N)$mH​(N) 取代真正的二分类个数本身就是一个宽松的上界，VC限制可以用于各种数据样本；
3. 使用二项式 $N^{d_{vc}}$Ndvc​ 作为成长函数的上界使得约束更加宽松，VC限制可以用于任意具有相同VC维的 $d_{vc}$dvc​ 假设空间；
4. 联合限制（union bound）并不是一定会选择出现不好事情的假设函数，VC限制可以用于任意算法。
   
   值得一提的是，VC Bound是比较宽松的，而如何收紧它却不是那么容易，这也是机器学习的一大难题。但是，令人欣慰的一点是，VC Bound基本上对所有模型的宽松程度是基本一致的，所以，不同模型之间还是可以横向比较。从而，VC Bound宽松对机器学习的可行性还是没有太大影响。

---

summary

本节课主要介绍了VC Dimension的概念就是最大的nonbreak point。然后，得到了Perceptrons在d维度下的VC Dimension是 $d+1$d+1。接着，在物理意义上，将 $d_{vc}$dvc​ 与自由度联系起来。最终得出结论 $d_{vc}$dvc​ 不能过大也不能过小。选取合适的值，才能让 $E_{out}$Eout​ 足够小，使假设空间H具有良好的泛化能力。

参考：
https://www.cnblogs.com/ymingjingr/p/4300092.html
https://github.com/RedstoneWill/HsuanTienLin_MachineLearning