本节的主要内容来自Hsuan-Tien Lin的机器学习基石课程[1]。
Learning happens, if finite $d_{VC}$, large $N$, and low $E_{in}$.
学习的可行性
当$N\geq 2,k\geq 3$时，成长函数满足约束条件 \begin{equation} m_{\mathcal H}(N)\leq B(N,k)=\sum_{i=0}^{k-1}\binom{N}{i}\leq N^{k-1}， \end{equation} 由此可见，断点$k$是判断成长函数大小的重要条件。当$k\geq 3$时，才能使用上界约束$N^{k-1}$。
对于$\forall g=\mathcal A(\mathcal D)\in\mathcal H$和足够大的数据集$\mathcal D$，当$k\geq 3$时， \begin{equation} \begin{aligned} P_{\mathcal D}\left[\lvert E_{in}(g)-E_{out}(g)\rvert>\epsilon\right] \leq & P_{\mathcal D}\left[\exists h\in\mathcal H\mbox{ s.t. }\lvert E_{in}(h)-E_{out}(h)\rvert>\epsilon\right] \\ \leq & 4m_{\mathcal H}(2N)\exp\left(-{1\over 8}\epsilon^2N\right)\\ \leq & 4(2N)^{k-1}\exp\left(-{1\over 8}\epsilon^2N\right)。 \end{aligned} \end{equation}
由此可知，学习是可行的，前提是满足下列条件：
- 好的假设集$\mathcal H$：$m_{\mathcal H}(N)$的断点是$k$；
- 好的数据集$\mathcal D$：$N$足够大；
- 好的演算法$\mathcal A$：$\mathcal A$能够选到一个$g$使得$E_{in}(g)$很小。
其中，前两个条件可能得到$E_{out}\approx E_{in}$。
VC维
$\mathcal H$的VC维$d_{VC}$是指满足$m_{\mathcal H}(N)=2^N$的最大$N$，VC维也满足：
- $\mathcal H$可以打碎的最多输入数据个数；
- $d_{VC}=\mbox{‘minmum }k\mbox{‘} - 1$。
若$N\leq d_{VC}$，$\mathcal H$能够打碎某些$N$个点的数据子集；若$k > d_{VC}$，$k$必是$\mathcal H$的断点；如果$N\geq 2, d_{VC}\geq 2$， 显然有 \begin{equation} m_{\mathcal H}(N)\leq N^{d_{VC}}。 \end{equation}
1维空间的正射线和正区间的$d_{VC}$分别是$1$和$2$；2维空间感知器的$d_{VC}=3$；2维空间凸包的$d_{VC}=\infty$。
有限$d_{VC}$的$\mathcal H$就是好的假设集。若$d_{VC}$有限，存在$g$使得$E_{out}(g)\approx E_{in}(g)$，并且不需要受学习算法$\mathcal A$、输入数据分布$P$和目标函数$f$的制约。
####练习题
若存在$N$个点的数据集不能被$\mathcal H$打碎，仅仅根据这条信息，可以得到关于$d_{VC}(H)$的什么结论？
［A］$d_{VC}(\mathcal H)>N$；［B］$d_{VC}(\mathcal H)=N$；［C］$d_{VC}(\mathcal H)<N$；［D］无法得出以上任何结论。
答案：［D］。
感知器的VC维
如何证明$d$维空间感知器的VC维$d_{VC}=d+1$？若能证明$d_{VC}\geq d+1$且$d_{VC}\leq d+1$，那么就可以得到$d_{VC}=d+1$。
####练习题：以下哪个表明$d_{VC}\geq d+1$？
［A］存在$d+1$个输入能被打碎；
［B］任何$d+1$个输入都能被打碎；
［C］存在$d+2$个输入不能被打碎；
［D］任何$d+2$个输入都不能被打碎。答案：［A］。
上面练习表明，只要在$d$维空间找到一组$d+1$个点的数据集能被感知器打碎（$d+1$个点的所有二分法都能实现），那么就证明了$d_{VC}\geq d+1$。
这组数据点如上图所示，红色框中的数据点表述了上方$2$维空间3个点的坐标。最左边1列灰色的$1$，表示感知器的偏移常量。
易知，$\mathbf X$是$(d+1)\times (d+1)$的方正，且所有列线性无关（秩为$d+1$）。因此，$\mathbf X$可逆，且是$d+1$维线性空间的基。若$\mathbf y$表示任意一种二分类结果（$\mathbf X$可被打碎），那么这样的二分类方式$\mathbf w=\mathbf X^{-1}\mathbf y$总存在，因此$d_{VC}\geq d+1$。
####练习题：以下哪个表明$d_{VC}\leq d+1$？
［A］存在$d+1$个输入能被打碎；
［B］任何$d+1$个输入都能被打碎；
［C］存在$d+2$个输入不能被打碎；
［D］任何$d+2$个输入都不能被打碎。答案：［D］。
上面练习表明，若$d$维空间任意$d+2$个点的数据集均不能被感知器打碎，那么就证明了$d_{VC}\leq d+1$。
若$d$维空间中任取$d+2$个点，都存在一种不能实现的二分类方法，那么这$d+2$个点就不能被打碎。
补上常数项$1$。因为$d+2$个$d+1$维的向量必定线性相关，任意一个均可用其它$d+1$个表示，那么 \[ \mathbf x_{d+2} = a_1\mathbf x_{1} + a_2\mathbf x_{2} + \ldots a_{d+1}\mathbf x_{d+1}， \] 其中，$a_i(i=1,2,\dots,d+1)$不全为$0$。上式两边同时乘以$\mathbf w^T$可得 \[ \mathbf w^T\mathbf x_{d+2} = a_1\mathbf w^T\mathbf x_{1} + a_2\mathbf w^T\mathbf x_{2} + \ldots a_{d+1}\mathbf w^T\mathbf x_{d+1}。 \] 若要所有二分法都可行，上式不论右边$\mathbf x_i(i=1,2,\dots,d+1)$取何值，左边$\mathbf w^T\mathbf x_{d+2}$既可取正又可取负。采用反证法，找到一组左边$\mathbf x_i(i=1,2,\dots,d+1)$的取值，使得$\mathbf w^T\mathbf x_{d+2}$只能取正（或者负）。
假设这$d+2$个点能被打碎，一定存在一种分类情况使得$\mathbf w^T\mathbf x_i(i=1,2,\dots,d+1)$的符号与$a_i(i=1,2,\dots,d+1)$的符号相同，那么$a_i\mathbf w^T\mathbf x_i(i=1,2,\dots,d+1)>0$，这样$\mathbf w^T\mathbf x_{d+2}$就只能取正。那么，这$d+2$个点不能被打碎，与假设矛盾。因此，$d$维空间中，任意$d+2$个点都存在不可能二分类的情况，也就是$d$维空间中的任何$d+2$个输入都不能被打碎，那么$d_{VC}\leq d+1$。
理解VC维
VC维可以理解为假设集$\mathcal H$的自由度，它衡量了$\mathcal H$的分类能力。$d_{VC}$可以直观的认为是$\mathcal H$可调节参数的个数（但不总是这样）。
如上图所示，正射线只有一个可以调节参数，自由度是$1$，$d_{VC}=1$；正区间有两个可以调节参数，自由度是$2$，$d_{VC}=2$。感知器的参数向量$\mathbf w = (w_0,w_1,\ldots,w_d)$是$d+1$维（有$d+1$个可自由调节参数）和它的$d_{VC}$一致。
过原点的感知器的$d_{VC}=d$，因为少了一个自由度。
对于机器学习是否可行，有两个判断指标：（1）$E_{out}(g)\approx E_{in}(g)$？（2）$E_{in}(g)$是否足够小。$d_{VC}$（或$M$）可以作为这两个条件的评价指标。若$d_{VC}$较小，更大概率保证$E_{out}(g)\approx E_{in}(g)$，但$\mathcal H$的能力较弱，可选择的假设较少，难以使$E_{in}(g)$较小；若$d_{VC}$较大，$\mathcal H$的能力较强，可选择的假设较多，更容易使$E_{in}(g)$较小，但$E_{out}(g)\approx E_{in}(g)$的概率偏低。
应用VC维
对于$\forall g=\mathcal A(\mathcal D)\in \mathcal H$和大的数据集$\mathcal D$，当$d_{VC}\geq 2$时，坏事儿发生概率的$VC$界为 \begin{equation} P_{\mathcal D}\left[\left\lvert E_{in}(g)-E_{out}(g)\right\rvert>\epsilon\right]\leq 4(2N)^{d_{VC}}\exp\left(-{1\over 8}\epsilon^2N\right)。 \end{equation} 令$\delta=4(2N)^{d_{VC}}\exp\left(-{1\over 8}\epsilon^2N\right)$，可得$\Omega(N,\mathcal H,\delta)=\epsilon=\sqrt{\frac{8}{N}\ln\left({4(2N)^{d_{VC}}\over\delta}\right)}$，那么可得$E_{out}(g)$的上界 \begin{equation} E_{out}(g)\leq E_{in}(g)+\sqrt{\frac{8}{N}\ln\left({4(2N)^{d_{VC}}\over\delta}\right)}。 \end{equation}
$\Omega(N,\mathcal H,\delta)$用于度量模型的复杂度，揭示了限定$E_{out}(g)$和$E_{in}(g)$差异的方法。
上图展示了VC维和误差的关系，随着VC维$d_{VC}$的增加，模型越来越复杂，但是误差并非越来越小，$E_{out}(g)$和$E_{in}(g)$的差异却越来越大，发生坏事儿的概率变大了。由此可见，强大的$\mathcal H$（$d_{VC}$大）不总是好事儿，要选择合适的$d_{VC}^*$。
给定指标$\epsilon=0.1,\delta=0.1,d_{VC}=3$，可以计算大约需要$N\approx 30000$的数据集能满足要求。
理论上需要$N\approx 10000d_{VC}$才能满足要求，实际上通常只需$N\approx 10d_{VC}$，这是因为在推导$VC$界的时候，不等式不断放大，得到的是一个很宽松的上界。
$d_{VC}$虽是一个宽松的值，但可认为对所有模型都同样一致宽松，因此在模型之间比较时，仍有重要作用。
$d_{VC}$容易计算吗？
参考资料
- [1]H.-T. Lin, “Lecture 7: The VC Dimension.” Coursera, 2014. [Online]
