接着 vc维的笔记（上）。。。。继续写。。。
Effective Number of Hypotheses
对于这个有效的假设函数值，我们尝试用一个数学定义来说明：
从H中任意选择一个方程h，让这个h对样本集合D进行二元分类，输出一个结果向量。例如在平面里用一条直线对2个点进行二元分类，输出可能为{1,–1}，{–1,1}，{1,1}，{–1,–1}，这样每个输出向量我们称为一个dichotomy。
下面是hypotheses与dichotomies的概念对比：
这里换句话讲，hypotheses里的所有的h可以分出len(dichotomy) 个类。。。。
注意到，如果对平面上的4个点来分类，根据前面分析，输出的结果向量只有14种可能，即有14个dichotomies。
如果有N个样本数据，那么有效的假设个数定义为： effective(N) = H作用于样本集D“最多”能产生多少不同的dichotomy。
所以有一个直观思路，能否用effective(N)来替换hoeffding不等式中的M（假设函数的个数）。接下来我们来分析下effective(N)。
Growth Function
H作用于D“最多”能产生多少种不同的dichotomies？这个数量与假设空间H有关，跟数据量N也有关。将H作用于D“最多”能产生的dichotomies数量(即effective(N) )表示为数学符号：max_H(x1,x2,…,xN)
这个式子又称为“成长函数”(growth function)。在H确定的情况下，growth function是一个与N（这里N是资料量）相关的函数。
换句话讲，就是，在假设空间确定的情况下，一个用N就可以得到最多产生多少dichotomies的一个函数。
下图举4个例子，分别计算其growth function：
对于第一个例子，positive ray，相当于是正向的射线。该假设空间，作用于1个样本点，可以产生2种dichotomies：(–1)，(+1)。作用于2个样本点，可以产生3种dichotomies：(–1,+1)，(–1,–1)，(+1,+1)。作用于3个样本点，可以产生4种dichotomies。依次类推，可以推导出其成长函数 m_H(N)=N+1；求解出m_H(N)后，那是不是可以考虑用m_H(N)替换M（别忘了我们的目标：换掉M !!!!）? 如下所示：
Break Point与Shatter
这两个概念很重要，一定要搞清楚，《机器学习基石》课程这两个概念搞不懂，后面几节课都是懵逼的。。。。
Shatter的概念：当假设空间H作用于N个input的样本集时，产生的dichotomies数量等于这N个点总的组合数2^N是，就称：这N个inputs被H给shatter掉了。（就是，在这个假设空间下，在N个样本下，刚好产生了2^N个dichotomies）
要注意到 shatter 的原意是“打碎”，在此指“N个点的所有(碎片般的)可能情形都被H产生了”。所以mH(N)=2^N的情形是即为“shatter”。
对于给定的成长函数m_H(N)，从N=1出发，N慢慢变大，当增大到k时，出现mH(N)<2k的情形，则我们说k是该成长函数的break point。对于任何N > k个inputs而言，H都没有办法再shatter他们了。
举例来说，对于上面的positive ray的例子，因为m_H(N)=N+1，当N=2时，m_H(2)<22， 所以它的break point就是2。
VC Bound
说完break point的概念后，再回到成长函数。我们将成长函数的上界，设为B(N,k)，意为：maximum possible m_H(N) when break point = k。（就是说：在m_H(N)的break point=k的时候，可以最多分出多少个dichotomies）
那么我们做一些简单的推导：
B(2,2)=3。因为break point=2，任意两个点都不能被shatter，m_H(2)肯定小于22，所以B(2,2)=3。
B(3,2)=4。因为任意两个点都不能被shatter，那么3个点产生的dichotomies不能超过4，所以B(3,2)=4。
B(N,1)=1。
B(N,k)=2N for N < k；B(N,k)=2N–1 for N=k；
B(4,3)=？去掉其中的一个数据点x4后，考虑到break point=3，余下数据(x1,x2,x3)的dichotomies数目不能超过B(3,3)。当扩展为(x1,x2,x3,x4)时，(x1,x2,x3)上的dichotomies只有部分被重复复制了，设被复制的dichotomies数量为a，未被复制的数量为b。于是有B(3,3) = a+b; B(4,3) = 2a + b。因为a被复制了，表示x4有两个取值，那么(x1,x2,x3)上的a应该小于等于B(3,2)。所以推导出B(4,3) = 2a + b <= B(3,3) + B(3,2)。
对于任意N>k，类推可以得到，B(N,k) ≤ B(N−1,k)+B(N−1,k−1)
这个式子显然是多项式的，多项式的最高幂次项为：N^(k–1)。
（不得不说，原文真的很尽力的写的通俗易懂，但是，确实不是很通俗易懂，因为。。。。字好多啊 _||，让我们翻到《机器学习基石》6.3中关于这个证明的推导，用图片说话吧！）
这里把B(4,3)产生出来，是11种，然后，分成了两部分，一部分是前面有重复的（2a），一部分是前面没重复的（紫色的β）
这里是任意三个点不能shatter那么，a+β<=B(3,3)
下面，只看橘色的部分。。。那么，橘色的是成双成对的，那么，如果有两个点被ko掉，那么加上x4肯定就shatter了。。。。那么，a<=B(3,2)
那么：
数学归纳法。。。。得：
证毕。。。。
所以我们得到结论：如果break point存在（有限的正整数），生长函数m(N) 是多项式的。
再重复一遍，H作用于数据量为N的样本集D，方程的数量看上去是无穷的，但真正有效(effective)的方程的数量却是有限的，这个数量为m_H(N)。H中每一个h作用于D都能算出一个Ein来，一共有m_H(N)个不同的Ein。
OK，到目前为止，关于m_H(N)的推导结束。回到growth function小节提出的问题，能否用m_H(N)直接替换M?
既然得到了m(N)的多项式上界，我们希望对之前的不等式中M 进行替换，用m_H(N)来替换M。这样替换后，当break point存在时，N足够大时，该上界是有限的。
然而直接替换是存在问题的，主要问题是：Ein的可能取值是有限个的，但Eout的可能取值是无限的。可以通过将Eout 替换为验证集(verification set) 的Ein’ 来解决这个问题（通俗来讲，就是用一个有限的验证集，替换无限的Eout）。 下面是推导过程：
最后，我们得到下面的VC bound
关于这个公式的数学推导，我们可以暂且不去深究。我们先看一下这个式子的意义，如果假设空间存在有限的break point，那么m_H(2N)会被最高幂次为k–1的多项式上界给约束住。随着N的逐渐增大，指数式的下降会比多项式的增长更快，所以此时VC Bound是有限的。更深的意义在于，N足够大时，对H中的任意一个假设h，Ein(h)都将接近于Eout(h)，这表示学习可行的第一个条件（第一个条件是，Ein≈Eout）是有可能成立的。
说了这么多，VC维终于露出庐山真面目了。此概念由Vladimir Vapnik与Alexey Chervonenkis提出。
一个假设空间H的VC dimension，是这个H最多能够shatter掉的点的数量，记为dvc(H)。如果不管多少个点H都能shatter它们，则dvc(H)=无穷大。还可以理解为：vc-dim就是argmax_n {growth function=power(2,n)}。
根据定义，可以得到一个明显的结论：
k = d_vc(H) + 1。。。。这里的k是break point点
根据前面的推导，我们知道VC维的大小：与学习算法A无关，与输入变量X的分布也无关，与我们求解的目标函数f 无关。它只与模型和假设空间有关。
我们已经分析了，对于2维的perceptron，它不能shatter 4个样本点，所以它的VC维是3。此时，我们可以分析下2维的perceptron，如果样本集是线性可分的，perceptron learning algorithm可以在假设空间里找到一条直线，使Ein(g)=0；另外由于其VC维=3，当N足够大的时候，可以推断出：Eout(g)约等于Ein(g)。这样学习可行的两个条件都满足了，也就证明了2维感知器是可学习的。
总结回顾一下，要想让机器学到东西，并且学得好，有2个条件：
H的d_vc是有限的，这样VC bound才存在（这里就是说Ein≈Eout）。(good H)；N足够大(对于特定的d_vc而言)，这样才能保证vc bound不等式的bound不会太大。(good D)
算法A有办法在H中顺利的挑选一个使得Ein最小的g。(good A)
回到最开始提出的学习可行的两个核心条件，尝试用VC维来解释：
从上图可以看出，当VC维很小时，条件1容易满足，但因为假设空间较小，可能不容易找到合适的g 使得Ein(g)约等于0。当VC维很大时，条件2容易满足，但条件1不容易满足，因为VC bound很大。
VC维反映了假设空间H 的强大程度(powerfulness)（这里是反映了强大程度，而不是反映了假设空间的函数的个数，我们是用(2N)^dvc代替掉假设空间的个数M的），VC 维越大，H也越强，因为它可以打散(shatter)更多的点。
定义模型*度是，模型当中可以*变动的参数的个数，即我们的机器需要通过学习来决定模型参数的个数。
一个实践规律：VC 维与假设参数w 的*变量数目大约相等。dVC = #free parameters。
我们将原不等式做一个改写，如下图所示：
上面式子中的第3项表示模型复杂度。模型越复杂，VC维大，Eout 可能距离Ein 越远。如下图所示，随着d_vc的上升，E_in不断降低，而模型复杂度不断上升。
它们的上升与下降的速度在每个阶段都是不同的，因此我们能够寻找一个二者兼顾的，比较合适的d_vc，用来决定应该使用多复杂的模型。
可以理解为，如果这个模型太复杂了（dvc太大），就很有可能过拟合了
模型较复杂时(d_vc 较大)，需要更多的训练数据。 理论上，数据规模N 约等于 10000*d_vc（称为采样复杂性，sample complexity）；然而，实际经验是，只需要 N = 10*d_vc。 造成理论值与实际值之差如此之大的最大原因是，VC Bound 过于宽松了，我们得到的是一个比实际大得多的上界（我的理解：就是把不等式右边不断地放大）。
注意在前述讨论中，理想的目标函数为f(x)，error measure用的是“0–1 loss”。如果在unknown target上引入噪声(+noise)，或者用不同的error measure方法，VC theory还有效吗？这里只给出结论，VC theory对于绝大部分假设空间(or 加入噪声)和error度量方法，都是有效的。
除此外，我们为了避免overfit，一般都会加正则项。那加了正则项后，新的假设空间会得到一些限制，此时新假设空间的VC维将变小，也就是同样训练数据条件下，Ein更有可能等于Eout，所以泛化能力更强。这里从VC维的角度解释了正则项的作用。
深度学习与VC维
对于神经网络，其VC维的公式为：
dVC = O(VD)，其中V表示神经网络中神经元的个数，D表示weight的个数，也就是神经元之间连接的数目。(注意：此式是一个较粗略的估计，深度神经网络目前没有明确的vc bound)
举例来说，一个普通的三层全连接神经网络：input layer是1000维，hidden layer有1000个nodes，output layer为1个node，则它的VC维大约为O(1000*1000*1000)。
可以看到，神经网络的VC维相对较高，因而它的表达能力非常强，可以用来处理任何复杂的分类问题。根据上一节的结论，要充分训练该神经网络，所需样本量为10倍的VC维。如此大的训练数据量，是不可能达到的。所以在20世纪，复杂神经网络模型在out of sample的表现不是很好，容易overfit。
但现在为什么深度学习的表现越来越好。原因是多方面的，主要体现在：
1、通过修改神经网络模型的结构，以及提出新的regularization方法，使得神经网络模型的VC维相对减小了。例如卷积神经网络，通过修改模型结构(局部感受野和权值共享)，减少了参数个数，降低了VC维。2012年的AlexNet，8层网络，参数个数只有60M；而2014年的GoogLeNet，22层网络，参数个数只有7M。再例如dropout，drop connect，denosing等regularization方法的提出，也一定程度上增加了神经网络的泛化能力。
2、训练数据变多了。随着互联网的越来越普及，相比于以前，训练数据的获取容易程度以及量和质都大大提升了。训练数据越多，Ein越容易接近于Eout。而且目前训练神经网络，还会用到很多data augmentation方法，例如在图像上，剪裁，平移，旋转，调亮度，调饱和度，调对比度等都使用上了。
3、除此外，pre-training方法的提出，GPU的利用，都促进了深度学习。
但即便这样，深度学习的VC维和VC Bound依旧很大，其泛化控制方法依然没有强理论支撑。但是实践又一次次证明，深度学习是好用的。所以VC维对深度学习的指导意义，目前不好表述，有一种思想建议，深度学习应该抛弃对VC维之类概念的迷信，尝试从其他方面来解释其可学习型，例如使用泛函空间（如Banach Space）中的概率论。
至此，这篇文章算是读完了，收获不少Emmmm….
