机器学习基石-07-1-Definition of VC Dimension

VC维-how to use break point？

上一节课的结论：

More on growth function

可以明显地看到右边的数值比左边大，所以可以适当地再放宽不等式一点。

More on vc Bound

在假定集H中有任何一个假设发生“坏事情”的几率很小很小。既然已经保证了大部分的时间假设都不会发生“坏事情”，所以不论选择哪种算法，通过算法找到的g都会使得Ein(g)很接近Eout(g)。再结合上面的公式可以得到：

好的H就是他的成长函数要在k的地方露出一线曙光，也就是必须存在break point。

好的算法就是尽可能地使得Ein(g)越小越好！

第1,2步是testing，第3步是training。

VC维-最大的non-break point，也就是k-1，其中k是最小的break point。

四种VC维

在positive intervals上VC维=3-1=2，也就是在2个点时可以shatter，2个点以上一定不能shatter！

在convex sets上VC维是无穷大，不是好的VC维。

VC维 and learning

也就是在最坏的情况下，还是保证Ein(g)和Eout(g)很接近！

fun time

不能根据N个inputs是否能shatter来判断N和VC维的大小关系。在这N笔中不能被shatter，但如果在另外一笔N个inputs时可以被shatter，那么就是VC维>N；但是如果另外的任意一笔N个inputs都不能被shatter，则满足VC维<N。所以并不能得到确切的大小关系。选4