维数灾难
维度灾难由于样本中有限的时间、有限的计算能力、有限的样本数量和相对过多的特征导致的。
- 超大的难以计算的计算量
- 过拟合、泛化能力差
奥卡姆剃刀
若无必要，勿增实体
Occam’s razor的意思是对于两个模型，在其他条件等同的情况，哪个模型能够更简洁地解释数据，哪个就更好。 由Occam’s razor引申出一种叫做Occam Learning模型。它被数学抽象化，这种模型既能有预测性，另外它的简洁性（数学公式定义）小于一个关于数据真实分布本身的简洁性的式子。那么我们就说这个真实数据本身是Occam learnable的。而这种简洁的模型相对于复杂的模型理论上讲能够避免学到过多的知识避免过拟合从而会有更好的泛化能力。
VC维
对于一个指示函数集，如果存在h个数据样本能够被函数集中的函数按所有可能的2的h次方种形式分开，则称函数集能够把h个数据样本打散（shatter）。函数集的VC维就是能打散的最大数据样本数目h。若对任意数目的数据样本都有函数能将它们shatter，则函数集的VC维为无穷大。
它是统计学习理论用来衡量函数集性能的一种指标——VC维越大，则学习过程越复杂。
举例来说，一个普通的三层全连接神经网络：input layer是1000维，hidden layer有1000个neural，output layer为1个neural，则它的VC维大约为O(1000 * 1000 * 1000)。
可以看到，神经网络的VC维相对较高，因而它的表达能力非常强，可以用来处理任何复杂的分类问题。根据上一节的结论，要充分训练该神经网络，所需样本量为10倍的VC维。如此大的训练数据量，是不可能达到的。所以在20世纪，复杂神经网络模型在out of sample的表现不是很好，容易overfit。
但现在为什么深度学习的表现越来越好。原因是多方面的，主要体现在：
- 通过修改神经网络模型的结构，以及提出新的regularization方法，使得神经网络模型的VC维相对减小了。例如卷积神经网络，通过修改模型结构(局部感受野和权值共享)，减少了参数个数，降低了VC维。2012年的AlexNet，8层网络，参数个数只有60M；而2014年的GoogLeNet，22层网络，参数个数只有7M。再例如dropout，drop connect，denosing等regularization方法的提出，也一定程度上增加了神经网络的泛化能力。
- 训练数据变多了。随着互联网的越来越普及，相比于以前，训练数据的获取容易程度以及量和质都大大提升了。训练数据越多，Ein越容易接近于Eout。而且目前训练神经网络，还会用到很多data augmentation方法，例如在图像上，剪裁，平移，旋转，调亮度，调饱和度，调对比度等都使用上了。
- 除此外，pre-training方法的提出，GPU的利用，都促进了深度学习。
参考 ：vc维的来龙去脉
Original link：https://izhangzhihao.github.io//2017/11/21/维数灾难和奥卡姆剃刀/