通过上节所学,有如下总结,从而大大的简化了成长函数。
在VC Bond理论中,可以有如下的替换:
由此得出可以让机器学习有效果的几个条件:
1.mH(N)在k有break point
2.N足够大
3.可以算出使得Ein最小的g
VC Dimension is the formal name of maximum non-break point.
如果VC Dimension是有限的,那么机器学习就是可行的。(Ein和Eout是接近的)
从VC Dimension的角度重新审视2D PLA:
而在多维度的情况下,可以证明dvc=d+1.
VC Dimension的物理意义:二元分类的情况下,到底有多少的自由度,也就是多我们可以自由选择我们想要的hypothesis的程度。
M和dvc的关系:
dvc可以替代M做类似上图的trade off。
根据霍夫丁不等式,BAD事件发生的概率经过dvc的替换之后:
而好事件发生的概率就是1–P(BAD):
可以推导出出Eout被限制在了一个区间内。不等式右边的部分表示了Eout的上限(最坏的时候)是什么。Ein加上的那一部分就是从样本内到样本外所付出的代价。
The VC Message:很高的模型复杂度是有代价的,虽然Ein很好看,但是Eout不一定很好看。
VC Bound Rephrase: Sample Complexity:样本总量N和dvc是有关系的。
Losseness of VC Bound:VC Bound的限制条件很少。
对于机器学习的应用拓展来说,VC Bound的哲学意义比实际意义更大。
shatter的意义是N个点所有可能的分类情况都被hypothesis set考虑到了。
总结: