VC维度

​由vc bound可以知道：

$P(exists hin H~s.t~|E_{in}(h)-E_{out}(h)|>epsilon)\ leq 4M_H(2N)exp(-frac{1}{8}epsilon^2N)\ leq 4(2N)^{k-1}exp(-frac{1}{8}epsilon^2N)~~~if~~exists k$

当break point存在时，以上公式成立：
1.好的H，存在break point，$M_H(N)$ 有限
2.好的D，N够大
3.好的算法A，能得到较小的$E_{in}$

VC维即k-1（最大的non-break point）