- 定义
- 计算感知器的VC维
- VC维的详细解释
- 将理论泛化为简单形式
定义
假设集合H的VC维记为：dVC(H) ，是对假设集合定义的数量，是增长函数为mH(N) = 2N的N集的最大值。
其意义是假设H可以彻底二分的最大点集。
当N大于d_vc时，N可以作为一个 break point（k）
相较于break point 使用d_vc描述增长函数更加方便
VC维反映了假设空间H 的强大程度(powerfulness)，VC 维越大，H也越强，因为它可以打散(shatter)更多的点。
计算感知器的VC维
d_vc 举例
d_vc与学习的关系
d_vc是有限的，那么g∈H是可泛化的。
d_vc与学习算法无关
d_vc与数据输入无关
d_vc与目标函数无关
感知器模型的d_vc：
维度d = 2，d_vc = 3
概括而言，d_vc = d + 1
证明：
证明d_vc ≥ d+1 且 d_vc ≤ d+1
- d_vc ≥ d+1的证明
结果显而易见：
- d_vc ≤ d+1的证明
但是这样的感知器不存在，因为：
综上d_vc = d + 1
VC维的详细解释
- 数学意义
- VC维在应用中的意义
数学意义
自由度：参数决定了假设模型的自由度，因为参数通过数字模拟了其自由程度。
d_vc的意义在于它将通过参数模拟的自由度转为了二元进行表示。它反应的不是参数的原始数量，而是有效参数的数量。
Positive ray 中，d_vc = 1 ，其自由度反应在 a 的选择上。
Positive interval 中，d_vc = 2 ，其自由度反应在起止端位置的选择上。
d_vc可以用来刻画所需要的数据量N
下图中横轴为N，纵轴为概率P，自蓝色线条到黑色线条d_vc依次取5、10、15...
P-d_vc-N图
VC维在应用中的意义
虽然从P-d_vc-N图中看出，VC维越大你所需要的N也越大。
其规则为：
N ≥ 10 * d_vc
将之前的理论整理为公式
因为样例的原因 Ein始终小于Eout ，因此去掉绝对值后将式子转为：
右部为泛化界限，随着N的增加Ein降低而Ω增加，两者有一个平衡点使得Eout最小，Eout才是我们真正关心的内容。
