PLA 多维情况下的vc维
时间：2015-06-28 16:48:23
收藏：0
阅读：226
对于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个点
原文：http://www.cnblogs.com/porco/p/4605648.html
评论（0）