5. VC维

• 定义
• 计算感知器的VC维
• VC维的详细解释
• 将理论泛化为简单形式

---

定义

假设集合H的VC维记为：d_VC(H) ，是对假设集合定义的数量，是增长函数为m_H(N) = 2^N的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才是我们真正关心的内容。