统计学习方法理论(二)
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维相关,所以避免了过拟合。