对于d维的数据集,vc = d+1
证明:
$vc \geq d+1$ : 存在d+1个点可以被H shatter
构造矩阵(注意加上$w_0$对应的$x_0$)
注意x可逆,构造$w=X^{-1}y$,有$Xw=y-----sign(Xw)=y$
$vc \leq d+1$ : 任意d+2个点不能被H shatter
注意x向量是d+1维的(注意还有$x_0$),所以对与第d+2各向量,
一定可以表示为前面d+1各向量的线性组合
取w使,$sign(x_iw)=a_i$,则此时
即不能得到第d+2个点的叉叉x情况,所以不能shatter d+2个点