我如何证明HH, 和五CVC方面dd, 粉碎所有大小小于d− 1d−1?

人工智能 证明 计算学习理论 vc-维度 vc理论 假设类
2021-11-18 07:06:26

如果某个假设类H有一个VC方面d在一个域上X, 我怎么证明H将粉碎所有子集X尺寸小于d, IEH会粉碎AX在哪里|A|d1?

1个回答

我们可以通过一个反例来证明它是不正确的。例如,X={1,2,3}H={{},{1},{2},{1,2}}是有限集假设类。根据定义,在这种情况下,VC尺寸H在域上Xd=2. 虽然A={3}X,其尺寸小于VC维度,即|A|<d=2, 它不会被H.