VC维的定义
第六讲证明，如果样本数\(N\)足够大且假设集合\(\mathcal{H}\)的成长函数\(m_{\mathcal{H}}(N)\)存在突破点，那么就有\(E_{\rm out} \approx E_{\rm in}\)。其中更具体地，如果成长函数存在突破点\(k\)，那么当\(N > k\)时，成长函数的值由上限函数\(B(N, k)\)所限制，该值等于\(\sum_{i=0}^{k-1}{N \choose i}\)，其最高项为\(N^{k-1}\)是\(N\)的多项式函数。而观察\(B(N, k)\)的值表和\(N^{k-1}\)的值表，可以发现当\(N \ge 2, k\ge 3\)时，\(B(N, k)\)就已经很小于\(N^{k-1}\)了。因此可以得到成长函数一个宽松的上界，即 \[ m_\mathcal{H}(N) \le B(N, k) = \sum_{i=0}^{k-1}{N \choose i} \le N^{k-1} \] 由于机器学习算法\(\mathcal{A}\)最后只会选择出一个模型\(g\)，因此这个模型遭遇“坏事情”（即\(|E_{\rm in}(g) - E_{\rm out}(g)|\)比较大）的概率肯定小于\(\mathcal{H}\)中任意一个模型\(h\)遭遇“坏事情”的概率。再代入前面推出的VC上界和成长函数的上界，对统计上足够大的数据集\(\mathcal{D}\)和算法\(g = \mathcal{A(D) \in H}\)，如果\(k \ge 3\)有（因为已经说了\(\mathcal{D}\)足够大，因此肯定有\(N\)足够大，即\(N \ge 2\)） \[ \begin{align*} &P_\mathcal{D}\left[|E_{\rm in}(g) - E_{\rm out}(g)| > \epsilon \right] \\ \le &P_\mathcal{D}[\exists h \in \mathcal{H}{\rm\ s.t.\ }|E_{\rm in}(h) - E_{\rm out}(h)| > \epsilon ] \\ \le &4m_{\mathcal{H}}(2N)\exp\left(-\frac{1}{8}\epsilon^2N\right) \\ \le &4(2N)^{k-1}\exp\left(-\frac{1}{8}\epsilon^2N\right)\hspace{3ex}({\rm if\ }k{\rm\ exists}) \end{align*} \] 即在以下三种条件同时满足的情况下，机器可能会学习。包括
- 成长函数的停止点为\(k\)（\(\mathcal{H}\)足够好）
- \(N\)足够大，可以一般化结论\(E_{\rm out} \approx E_{\rm in}\)（\(\mathcal{D}\)足够好）
- 算法\(\mathcal{A}\)选出的模型\(g\)能有足够小的\(E_{\rm in}\)（\(\mathcal{A}\)足够好）
（以及一点好的运气）
那么这些推导与VC维有什么关系？简单说，VC维是“最大非停止点”的更正式的说法，是假设函数集\(\mathcal{H}\)的一种性质。在\(N\)小于等于\(\mathcal{H}\)的VC维（记为\(d_{\rm VC}(\mathcal{H})\)）时，存在某种形式的\(N\)个输入可以被\(\mathcal{H}\)打散；当\(N > d_{\rm VC}(\mathcal{H})\)时，任意\(N\)个输入都不能被\(\mathcal{H}\)打散，即达到了停止点。这个定义可以写作
\(\mathcal{H}\)的VC维，记做\(d_{\rm VC}(\mathcal{H})\)，指的是满足\(m_\mathcal{H}(N) = 2^N\)的最大的\(N\)。从数值上，其等于最小的停止点\(k\)减去1
如果\(\mathcal{H}\)没有停止点，则\(d_{\rm VC}(\mathcal{H}) = \infty\)
化用前面的结论，有当\(N\ge 2, d_{\rm VC} \ge 2\)时，\(m_\mathcal{H}(N) \le N^{d_{\rm VC}}\)
那么第六讲中分析的一些\(\mathcal{H}\)的VC维如下所示：
- 正射线的VC维是1
- 正区间的VC维是2
- 凸集的VC维是\(\infty\)
- 二维空间中感知机的VC维是3
即“好的假设集”总是有有限的VC维，这意味着其会将\(E_{\rm out}(g) \approx E_{\rm in}(g)\)一般化，而且与算法\(\mathcal{A}\)的形式、数据的分布\(P\)和目标函数\(f\)的形式都无关
（注意由本节的fun time，即便对某\(N\)个输入不能被\(\mathcal{H}\)打散，也不能确定\(d_{\rm VC}(\mathcal{H})\)与\(N\)的关系。如果要有\(d_{\rm VC}(\mathcal{H}) < N\)，要求的是任意\(N\)个输入都不能被\(\mathcal{H}\)打散）
感知机的VC维
对于二维的感知机，一方面，如果数据集\(\mathcal{D}\)线性可分，意味着感知机PLA算法可以收敛，即当迭代了足够的步数\(T\)以后，有\(E_{\rm in}(g) = 0\)。另一方面，如果数据来自于某个概率分布，且标签由某个确定的目标函数所产生（即\({\bf x}_n \sim P, y_n = f({\bf x}_n)\)，那么由于二维感知机的VC维是3，因此“坏事情”发生的概率很小，\(N\)足够大时，有\(E_{\rm out}(g) \approx E_{\rm in}(g)\)。两者综合起来，有\(E_{\rm out}(g) \approx 0\)，即二维感知机算法是能达到学习效果的
同样的推论能否应用在\(\bf x\)有多于两个特征的情况？回顾之前的分析，一维感知机（正/负射线）的VC维是2，二维感知机的VC维是3，那么是否有\(d\)维感知机的VC维是\(d+1\)？接下来试着证明之（本节简记“\(d\)维空间感知机的VC维”为\(d_{\rm VC}\) ）：
首先证明\(d_{\rm VC} \ge d + 1\)。若要证明该命题，只需构造\(d + 1\)个输入，使得该输入可以被感知机假设集\(\mathcal{H}\)打散即可。我们做如下构造：这\(d+1\)条数据中，第一条是\(d\)维空间的零点，第二条到第d+1条中第\(i\ (i = \{1,2,\ldots, d\})\)个分量为1其它分量为0。将\(x_0 = 1\)补入矩阵，有 \[ {\rm X} = \left[\begin{matrix} -{\bf x}_1^\mathsf{T} - \\ -{\bf x}_2^\mathsf{T} - \\ -{\bf x}_3^\mathsf{T} - \\ \vdots \\ -{\bf x}_{d+1}^\mathsf{T} - \end{matrix}\right] = \left[\begin{matrix}1 & 0 & 0 & \cdots & 0\\ 1 & 1 & 0 & \cdots & 0 \\ 1 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & & \ddots &\vdots \\ 1 & 0 & 0 & \cdots & 1\end{matrix}\right] \] 注意\(\rm X\)是可逆的，即其逆矩阵存在且唯一。而“打散”意味着，对于任意一种\(y_1, y_2 ,\cdots, y_{d+1}\)的排列组合\(\bf y\)，总有\({\rm sign}({\rm X}{\bf w}) = {\bf y}\)。而由于若\({\rm X}{\bf w} = {\bf y}\)，前面的式子也成立。又因为\(\rm X\)可逆，因此只需要使权重\(\bf w\)为\({\rm X}^{-1}{\bf y}\)，就可以满足对任意的\(\bf y\)有\({\rm sign}({\rm X}{\bf w}) = {\bf y}\)，因此这个\({\rm X}\)可以被\(\mathcal{H}\)打散，\(d_{\rm VC} \ge d + 1\)
接下来证明\(d_{\rm VC} \le d+1\)，即任何\(d+2\)个输入都不能被\(\mathcal{H}\)打散。要证明这个任意性比较困难，但是可以先回到二维空间再仔细研究一番。
之前提到，如果输入三个点位于直角坐标系中\((0,0), (0,1), (1,0)\)这三个点，那么输入可以被\(\mathcal{H}\)打散。如果加入第四个点\((1,1)\)会怎么样？首先可以把这四个点写出来放进矩阵中，即 \[ {\rm X} = \left[\begin{matrix} -{\bf x}_1^\mathsf{T} - \\ -{\bf x}_2^\mathsf{T} - \\ -{\bf x}_3^\mathsf{T} - \\ -{\bf x}_{4}^\mathsf{T} - \end{matrix}\right] = \left[\begin{matrix}1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 1\end{matrix}\right] \] 进一步，假设\(y_2 = y_3 = \circ (+1), y_1 = \times (-1)\)，由前面的分析可知\(y_4\)一定不能为\(\times\)，否则整个数据集线性不可分。接下来解释为什么会出现这样的情况（或者说，来看如果数据集线性可分那为什么\(y_4\)一定为\(\circ\)）
根据矩阵中的关系，可以得到\({\bf x}_4 = {\bf x}_2 + {\bf x}_3 - {\bf x}_1\)。由于数据集线性可分，因此存在一个最优的权重\(\bf w\)。将这个权重左乘到等式中，有\({\bf w}^\mathsf{T}{\bf x}_4 = {\bf w}^\mathsf{T}{\bf x}_2 + {\bf w}^\mathsf{T}{\bf x}_3 - {\bf w}^\mathsf{T}{\bf x}_1\) 。又\(y_2 = y_3 = +1, y_1=-1\)，由\(\rm sign\)函数的性质可知必然有\({\bf w}^\mathsf{T}{\bf x}_2 > 0, {\bf w}^\mathsf{T}{\bf x}_3 > 0, {\bf w}^\mathsf{T}{\bf x}_1 < 0\)。但是由于\({\bf w}^\mathsf{T}{\bf x}_1\)这一项前面是符，因此将这些负号系代入，可知\({\bf w}^\mathsf{T}{\bf x}_4\)必然大于0，对应为\(y_4\)必然是正的。造成这种现象的根源是\({\bf x}_4\)是其它三项的线性组合，数据集线性相关。因此可以得到结论：输入数据的线性相关性限制了二分法分类器的种类数目
将上面的推导过程推广到\(d\)维空间。假设\({\bf x}\)有\(d\)个维度，补入\(x_0\)以后有\(d+1\)个维度，现在数据集里有\(d+2\)条数据。由线性代数的知识可知，这\(d+2\)个变量肯定线性相关，因此存在不全为0的\(a_i\)使得\({\bf x}_{d+2} = a_1{\bf x}_1 + a_2{\bf x}_2 + \ldots + a_{d+1}{\bf x}_{d + 1}\)。如果\(\bf w\)与各个\(\bf x_i\)的内积得到的符号恰好是\(a_i\)的符号，那么\({\bf w}^\mathsf{T}{\bf x}_{d+2}\)的符号一定是正的，\(y_{d+2}\)不可能属于负类。因此任何\(\rm X\)不能被打散
（这里有一种更直接而且更严谨的说法：由于线性相关性的存在，\({\bf x}_{d+2}\)的符号完全剩余\(d+1\)个\({\bf x}\)决定。如果最优的\(\bf w\)也存在，那么\({\bf w}^\mathsf{T}{\bf x}_{d+2}\)的符号一定是确定的，如果\(y_{d+2}\)的符号和这个确定的符号不一致，那么就会线性不可分，也就是说\(\rm X\)不能被打散）
因此，\(d_{\rm VC} \ge d + 1, d_{\rm VC} \le d + 1 \Rightarrow d_{\rm VC} = d+1\)
\(\blacksquare\)
VC维的物理意义
在前面的证明中可以发现一个有趣的现象：\(d\)维感知机的VC维是\(d+1\)，同时其权重又有\(d+1\)个分量，两者之间是否存在关系？可以认为假设参数\({\bf w} = （w_0, w_1, \ldots, w_d)\)定义了自由度的概念，而VC维的物理意义可以理解为假设集\(\mathcal{H}\)在做二元分类问题时自由度的的大小。自由度越大，VC维越大，分类器能力越强。
例如，正射线的VC维是1，其自由变量正好也有一个，是\(a\)（大于\(a\)的都标为正）。正区间的VC维是2，其自由变量正好也有两个，是\(\ell\)和\(r\)（落在区间\([\ell, r)\)的都标为正）。因此，大致上可以理解为，VC维就是模型可调节的自由参数数量（不过这个说法并不总是对的）。
既然VC维代表了\(\mathcal{H}\)的自由度，回顾第五讲，当时有一个大\(M\)小\(M\)的权衡问题：小\(M\)可以保证\(E_\rm{in}\)和\(E_\rm{out}\)接近，但是选择太少，可能找不到使\(E_\rm{in}\)很小的\(g\)；而大\(M\)可以找到使\(E_{\rm in}\)很小的\(g\)，却不能保证“坏事情”发生的概率很小。由于前面对VC上界的推导证明当\(\mathcal{H}\)无限时\(M\)可以被\(2(2N)^{d_\rm{VC}}\)所代替，因此可以类似地说，VC维小可以保证\(E_\rm{in}\)和\(E_\rm{out}\)接近，但是模型的能力太弱，可能找不到使\(E_\rm{in}\)很小的\(g\)；而VC维大意味着模型能力足够强，可以找到使\(E_{\rm in}\)很小的\(g\)，却不能保证“坏事情”发生的概率很小。这说明，选择合适的VC维（也就是选择合适的假设集合\(\mathcal{H}\)），是非常重要的！
对VC维的更深入解释
要想更深入地解释VC维，需要对原有VC上界的形式做一个改写。记原有的VC上界为\(\delta\)，即 \[ \delta = 4(2N)^{d_{\rm VC}}\exp\left(-\frac{1}{8}\epsilon^2N\right) \] 从另一个角度看，该上界是“坏事情”发生概率的上界，同时也可以据此求出是“好事情”（即\(|E_\rm{in} (g) - E_\rm{out}(g)| \le \epsilon\)）发生的概率的下界。有 \[ P[|E_\rm{in} (g) - E_\rm{out}(g)| \le \epsilon] \ge 1-\delta \] 对刚才\(\delta\)的表达式做简单代数变换，可以得到\(\epsilon\)的表达式 \[ \epsilon = \sqrt{\frac{8}{N}\ln\left(\frac{4(2N)^{d_{\rm VC}}}{\delta}\right)} \] 称\(|E_\rm{in} (g) - E_\rm{out}(g)|\)为一般化误差，可知 \[ |E_\rm{in} (g) - E_\rm{out}(g)| \le \sqrt{\frac{8}{N}\ln\left(\frac{4(2N)^{d_{\rm VC}}}{\delta}\right)} \] 因此可以得到\(E_\rm{out}\)类似“置信区间”的范围，为 \[ E_{\rm{in}}(g) - \sqrt{\frac{8}{N}\ln\left(\frac{4(2N)^{d_{\rm VC}}}{\delta}\right)} \le E_{\rm out}(g) \le E_{\rm in} + \sqrt{\frac{8}{N}\ln\left(\frac{4(2N)^{d_{\rm VC}}}{\delta}\right)} \] 一般不关心\(E_\rm{out}\)的下界，但是会关心其上界。其中根号里面的项称为模型复杂度，可以看作是关于样本大小、假设集合和VC上界的函数\(\Omega(N, \mathcal{H}, \delta)\)，而\(\sqrt{\Omega(N, \mathcal{H}, \delta)}\)称作模型复杂度提升带来的代价。
可以把VC维和模型在样本内外的误差之间的关系作图表示
从图中可知，随着\(d_\rm{VC}\)变大，模型可以打散的输入越多，因此\(E_\rm{in}\)会变小。但是这样会使得模型复杂度提高。当\(d_\rm{VC}\)维不那么大的时候，\(E_{\rm in}\)下降的速度超过模型复杂度提升的速度，\(E_{\rm out}\)会下降。但是超过某个临界点\(d_{\rm VC}^\ast\)以后，模型复杂度提升的速度更快，\(E_{\rm out}\)经过最小值以后会上升。这意味着最好的VC维\(d_{\rm VC}^\ast\)通常在中间取得，并不是越大越好。考虑到VC维和模型复杂度的关系，这说明\(\mathcal{H}\)并非总是越强大越好！
VC维的另外一个作用就是可以决定样本复杂度，即做多大的采样能够将“坏事件“（训练集内外误差差值大于\(\epsilon\)）发生的概率控制在\(\delta\)以内。例如，如果\(\epsilon=0.1, \delta=0.1, d_\rm{VC} = 3\)，那么理论上需要采集29300条数据才能满足要求，此时样本数\(N \approx 10000d_\rm{VC}\)。不过实践中，通常\(N \approx 10d_{\rm VC}\)就够用了。这意味着，VC上界是一个非常宽松的上界，这是因为
- 使用了Hoeffding不等式，这个上界估计独立于产生数据的概率分布，也独立于目标函数的形式
- 使用了成长函数\(m_\mathcal{H}(N)\)而没有使用假设函数个数\(|\mathcal{H}({\bf x}_1 , \ldots {\bf x}_N)|\)，因此独立于具体的数据（成长函数也是高估）
- 使用了多项式上限\(N^{d_\rm{VC}}\)来代替成长函数\(m_\mathcal{H}(N)\)，因此独立于任何假设函数集合\(\mathcal{H}\)，只用考虑VC维这一个参数
- 使用了事件并的发生概率的上界，即将算法\(\mathcal{A}\)选出遇到”坏事件“假设函数的概率提高了很多
即计算VC上界时采用了很多宽松的估计。不过在理论上，这个上界想改进，让它更紧一些，也比较难。因此之后设计算法时，更多要注意的是VC上界背后透露的哲学思想，以此来作指导（例如不能让\(\mathcal{H}\)太过强大等等）。
