统计学习方法理论（二）
1.ERM下的样本复杂度
如果假设函数h是由d个实数作为参数，那么样本复杂度的上届是参数个数的线性。但这是非正式的证明方法。
下面用VC维的l理论证明。
2.VC维（VC dimension）
分散（shatter）：如果假设函数h能实现在样本集S上的任意标记（label），则说h可以分散样本集S
VC维（VC dimension）：假设函数能够分散的最大样本集合的大小。
在n维特征空间上，线性分类器h的参数为n+1，而h的VC维的大小也正好为n+1
一个学习理论（learning theory）中最重要的推论：
为什么SVM不会出现过拟合的危险？因为考虑那些具有较大间隔γ的分类器H，它们的VC（H）比较小，模型的复杂度和VC维相关，所以避免了过拟合。