知识卡片
VC维与打散
关键定理要找函数集中表现最差的那个函数,VC 维就是对函数集打散能力的度量。若一个含 h 个样本的集合能被函数集按全部 2^h 种标签方式分开,就称该函数集把这 h 个点打散;能被打散的最大样本数 h 就是 VC 维,再多一个点就打不散。二维平面上只有 0/1 两类输出的指示函数集能打散任意 3 个不共线点(共 8 种分法),但打不散 4 个点(会出现异或情形),故其 VC 维为 3。VC 维衡量函数集的复杂度与非线性程度:线性可分数据的维度是样本空间维数 d,线性分类器的 VC 维至少是 d+1,VC 维越大学习机器越复杂。它重新提供了判定线性可分的依据,但除少数特殊函数外,多数学习机器的 VC 维尚无通用求法。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第8章 万能分类器——支持向量机 · 查看原书依据
VC维定义:假设存在一个有h个样本的样本集能被一个函数集中的函数按照所有可能的2h 种形式分为两类,则此函数集能够把样本数为h的样本集打散。也就是说,如果存在h个样本的样本集能够被函数集打散,而不存在h+1个样本能被打散,则函数集的VC维就是h。
参考来源
- 位置:《机器学习算法原理与编程实践》第8章 万能分类器——支持向量机(源文件:extracted/机器学习算法原理与编程实践/_epub-src/OEBPS/text00028.html)
- 结论依据:原文给出打散与 VC 维定义,并用二维指示函数打散 3 点、打不散 4 点的例子及 d+1 关系支撑复杂度解释。
- 原始内容:VC维定义:假设存在一个有h个样本的样本集能被一个函数集中的函数按照所有可能的2h 种形式分为两类,则此函数集能够把样本数为h的样本集打散。也就是说,如果存在h个样本的样本集能够被函数集打散,而不存在h+1个样本能被打散,则函数集的VC维就是h。