—————————红色石头机器学习课程笔记7 <节选>—————————————
在前几节课中，我们推导出机器要能够学习，必须满足两个条件：
- hypothesis $H$中的size M是有限的，N足够大，那么对于$H$中的任意一个假设$h$，$E_{o u t} \approx E_{i n}$
- 利用算法$A$从hypothesis中，挑选出一个$g$，使$E_{in}(g) \approx 0$，则$E_{o u t} \approx 0$。
这第二个条件对应了train和test，train的目的是让损失期望$E_{i n}(g) \approx 0$；test目的是将算法运用到新样本时，损失期望也尽可能小，即$E_{o u t} \approx 0$。
正因为如此，上次课引入了break point，并推导出只要break point存在，则M有上界，一定存在$E_{o u t} \approx E_{i n}$。
这周的课程介绍VC Dimension，也是总结VC Dimension与$E_{i n}(g) \approx 0$，$E_{o u t} \approx 0$，Model Complexity Penalty的关系。
Definition of VC Dimension
dichotomy的上限是成长函数，成长函数的上限是$B(N,k)$，$B(N,k)$的上限是$N^{k-1}$。
由下图可以更明显的看出，当$k \geq 3，N \geq 2$时，$N^{k-1}$大于$B(N,k)$。
因此这条结论的不等式为：
$m_{H}(\mathrm{N})\leq B(\mathrm{N}, \mathrm{k})=\sum_{i=0}^{k-1} C_{N}^{i} \leq N^{k-1}$
因此上一周的VC bound就可以转换为只和K，N有关的式子：
通常情况N都足够大，因此只需要k满足条件即可。这时候我们就说$h$泛化能力不错，即$E_{o u t} \approx E_{i n}$。如果再有一个好的演算法$A$使得$E_{in} \approx 0$，那么理论上就这个模型就具有学习能力了。（真的好不好用还得要点运气….）
VC dimension
通常来说break point越大的$H$，其复杂度也越高，这个复杂度比较抽象，通俗理解，就是$H$中的$h$，特征多，数量多，复杂度越高。
这篇文章《机器学习（周志华）》学习笔记（一）里对假设空间$H$的说明可以参考一下，能够帮助直观理解$H$的复杂度。
根据VC Theory，还可以用VC-dimension来描述$H$的复杂度，记为$d_{v c}(\mathcal{H})$。更重要的是
$k=d_{vc}(\mathcal{H})+1$，也就是说，$d_{vc}(\mathcal{H})$是$\mathcal{H}$能够shatter掉的数目，也就是比break point小1的点。如果不管多少个点$\mathcal{H}$都能shatter，那么$d_{v c}(H)=\infty$。
因此之前的条件，我们都可以把k替换成$d_{v c}(\mathcal{H})$：
那么无论采取什么样的$\mathcal{A}$，输入，目标函数，$d_{v c}(\mathcal{H})$都只和$H$有关，只要它finite，那么至少能保证$E_{o u t} \approx E_{i n}$。
VC Dimension of Perceptrons
通过前面的证明，我们知道在2D情况下$d_{v c}=3$，PLA算法是可以学习的：
那么多个feature或者说多维的情况下，对应的$d_{v c}$又是多少？我们先给出结论（1D perceptron（pos/neg rays）$d_{vc}=2$；2D perceptrons $d_{vc}=3$，其中$d$为维数）：
$d_{v c}=d+1$
证明”=”通常我们分两步：
- $d_{v c} \geq d+1$
- $d_{v c} \leq d+1$
首先证明第一个不等式：$d_{v c} \geq d+1$，因为$d_{vc}$是break point-1，也就是$m_{H}(N)=2^{N}$成立且最大时的N值，所以要证明这个不等式，只需要证明存在某一个含有$d+1$个数据的数据集能够被shatter即可，即
$m_{H}(d+1)=2^{d+1}$。
假设我们有一个$d$维的矩阵$X$，含有$d+1$个inputs，每个inputs加上偏置项1，得到的新的矩阵$X$如下：
可以明显看出$X$是可逆的，shatter的本质是假设空间$\mathcal{H}$里的每个$h$对$X$都能进行分类，也就是说总能找到权重$W$，满足$\operatorname{sign}(\mathbf{X} \mathbf{w})=\mathbf{y}$，而只要使得$\mathbf{X}_{\mathbf{W}}=\mathbf{y}$成立，$sign(\mathbf{X}_{\mathbf{W}})=\mathbf{y}$就一定成立，那么这个权重$W$存在吗？答案显而易见，只要令$W=X^{-1}y$（别忘了这里$X$可逆），那么$\mathbf{X}_{\mathbf{W}}=\mathbf{y}$就一定成立。
结论：$d$维 perceptrons，存在$N=d+1$时被shattered，因此$d_{v c} \geq d+1$。
接着证明第二个不等式$d_{v c} \leq d+1$。在$d$维里，对于任意的d+2个inputs都不能被shattered，则不等式成立。
添加偏置项后$X$为$d+1$列，矩阵秩不满，因此$\mathbf{X}_{d+2}$可以由$a_{1} \mathbf{x}_{1}+a_{2} \mathbf{x}_{2}+\ldots+a_{d+1} \mathbf{x}_{d+1}$线性表示：
$\mathbf{x}_{d+2}=a_{1} \mathbf{x}_{1}+a_{2} \mathbf{x}_{2}+\ldots+a_{d+1} \mathbf{x}_{d+1}$………………….(1)
现在用反证法来证明，我们假设$X$能被shattered，且存在一个$W$，使得$W^{T}X$的值(也就是y值，+1或-1)和系数$a_{i}$(i=1,2,….,d+1)符号一致。结合公式(1)得出：
其中，蓝色$a_{i}$为正，红色$a_{i}$为负。
但是由上面可以知道，此时$\mathbf{w}^{T} \mathbf{x}_{d+2} >0$是恒成立的，也就是说第$\mathbf{w}^{T}\mathbf{x}_{d+2}$只能为”o”不能为”x”。同理，当
$\mathbf{w}^{T} \mathbf{x}_{d+2}<0$，则$\mathbf{w}^{T}\mathbf{x}_{d+2}$只能为“x”，不能为“o”。
这就违背了shattered的原则，假设不成立，任意$d+2$个inputs都不可能被shattered。所以$d_{v c} \leq d+1$。
综上所述：d维perceptrons，$d_{v c}=d+1$。
Physical Intuition of VC Dimension
从上一part我们得知VC Dimension中的Dimension和perceptron中数据的Dimension是有关的，这也是VC维中维字的由来。而在perceptron中，数据样本的dimension加上偏置，就和权值的dimension一致，且权值又构成了假设函数。因此如果把hypothesis set想象成一个空间（即假设空间），那么其中的假设函数可以用权值参数向量$\mathbf{w}^{T}=\left[w_{0}, w_{1, \cdots} w_{d}\right]$来表示，向量的个数d就是假设空间的维度，即模型学习的参数个数，也称为”自由度”(degree of freedom)。
对于$d_{vc}$较小的$\mathcal{H}$，可以从它最多能够shatter的点的数量，得到$d_{vc}$，但对于一些较为复杂的模型，寻找能够shatter掉的点的数量，就不太容易了。此时我们可以通过模型的自由度，来近似的得到模型的$d_{vc}$。
因为假设空间的数量$|H|$是无限的，所以自由度也是无限的。当然如果我们从感知器在二元分类上这一限制条件入手，是可以使用VC维作为自由度的衡量。
举几个直观例子：
因此，
最后整理一下，通过这图，我们可以将假设空间中的假设函数个数$M$用$d_{vc}$来代替。这张图里说明了很多问题，比如large $d_{vc}$就证明了在特征很多的情况下，只要样本数量N够多，学习得到的模型$E_{in}(g)$都比较小，错误率也较低。
Interpreting VC Dimension
之前定义过VC Bound：
BAD发生的概率$\leq \delta$，反过来说good，即$\left|E_{\mathrm{in}}(g)-E_{\mathrm{out}}(g)\right|<\epsilon$发生的概率$\geq 1-\delta$。因此我们可以推导出$E_{in}(g)$和$E_{out}(g)$的接近程度$\epsilon$：
我们又把接近程度$\left|E_{\mathrm{in}}(g)-E_{\mathrm{out}}(g)\right|$称为泛化误差(generalization error)，$\epsilon$称为泛化误差界。再进一步，可以确定$E_{out}(g)$的范围：
其中带根号这一项就被称为模型复杂度(model complexity)，由样本数量N，假设空间$\mathcal{H}$($d_{vc}$)，$\delta$有关。我们通常不关注左边灰色的式子，因此得到：
可以绘制出$E_{out}(g)$、模型复杂度、$E_{in}(g)$随$d_{vc}$变化的函数图像：
从图中可以看出，$d_{vc}$越大，假设空间就越大，就有可能选到更小的$E_{in}$；模型复杂度从公式中也可以看出和$d_{vc}$正相关。而我们希望的是能够让$E_{out}$最小，因此在学习中如何选择到$d_{vc}^{*}$就非常关键。
sample complexity
VC Dimension还可以表示样本复杂度(sample complexity)。如果选定了$d_{vc}$，那么数据样本D选择多少合适？
假设你帮老板进行股票分析，老板要求：$E_{in}(g)$和$E_{out}(g)$之间的误差上限$\epsilon=0.1$；置信区间90%，即$\delta=0.1$；所用模型的VC Dimension $d_{vc}=3$。你经过一番计算，跟老板汇报：
如果想要满足条件，大概需要30000条数据作为训练集，也就是10000$d_{vc}$。这么多条数据，显然老板也无法解决这个问题。
好消息是，实际经验告诉我们，其实需要的数据量大概是10$d_{vc}$。那么为什么导致理论值和实际值差别如此大？原因是我们再推导VC Bound的时候考虑的都是比较泛化的情况，换句话说VC Bound过于”宽松“了，回顾我们的推导过程：
加个中文版的：
为了能够适用于这么多的‘any’，导致了VC Bound的理论值变得非常宽松。因此我们得到的是一个比实际上大得多的上界。尽管VC Bound看起来非常宽松，但也很难找到一个比它更好的模型。值得欣慰的是，对于不同模型，VC Bound的宽松程度还是基本一致的。尽管在实际使用时我们不会严格根据VC Bound来选择，但它的推导过程还是能够帮助进一步理解为什么机器学习是成立的。
