VC维的几个习题
VC维的几个习题
线性分类假设空间的VC维
这是西瓜书上的一个习题,在学习计算理论的时候我也在博客上记过这个结论,二维的线性空间VC维为3,(4的时候异或类的标号就打不散)也十分显然,但是推广情形的证明和构造需要一定技巧。
把这个问题看作组合极值问题:
等号成立部分
极值证明部分:
综上,VC维为d+1维。
一个关于VC维和增长函数的不等式
设
第一部分用数学归纳法证明,先从数据集取一个出来,化归,见西瓜书。
第二部分的证明我尝试了取对数,斯特灵公式都不好证明,但是答案的证明非常巧妙。
利用这个习题的结论,可以估计PAC可学习需要的样本m和VC维的关系。