几何分类器可以有无限多个可能的边界,VC 维却仍然有限。问题不在于有多少条边界,而在于它们能对有限多个点作出多少独立的标记。需要两个互补的论证:构造一个能实现所有标记的集合,再证明任何更大的集合都不能有这个性质。
以下 为整数,定义域是 。
定义 2.2.1
(打散与 VC 维)
如果某个分类器类能实现有限集合上每一种二元标记,就说它打散该集合。该类的 VC 维是使得存在 个互异点的集合被打散的最大整数 ;若任意大的有限集合都能被打散,则为 。
被打散集合的每个子集也被打散:先将子集的标记任意扩展到整个集合即可。因此,排除某一大小的打散集合,也就排除了所有更大的大小。坐标和阈值均为实数,下文的几何集合都包含边界。
仿射半空间
考虑
我们允许 ,因此包含恒为零和恒为一的分类器。偏移量 使边界能够移动,而不必通过原点。
定理 2.2.2
(仿射半空间的 VC 维为 )
对于上述类,。
证明
(仿射分数的构造与仿射相关)
下界。 点 仿射无关。对于任意指定的符号 ,取 和 。那么仿射分数在原点恰为 ,在 处恰为 。因此它以严格远离零的分数实现所需标记。全部 种标记都能实现。
上界。 任取 个互异点 。它们的增广向量 线性相关。因此存在不全为零的实系数,满足
这些系数中既有正数也有负数。将 的点标为 1, 的点标为 0;系数为零的点可任意标记。若某个仿射半空间实现了该标记,其分数 在正系数点满足 ,在负系数点满足 。因此
严格不等式来自至少一个负系数与严格为负的分数相乘。但仿射相关给出 ,矛盾。因此任何 个点都不可能被打散。结合下界即证明定理。
证明透视
边界约定为何重要
证明没有假定所有带标签点的分数都被严格分开。由于边界点标为 1,一个候选实现只保证正标签侧 、负标签侧 。单凭负系数项便能迫使加权和严格为正。因此不必假设点处于一般位置,也处理了边界情况。
例题 2.2.3
(平面上的三个点)
平面上的原点和两个坐标单位向量能实现全部八种标记。若原点标为 0、 标为 1、 标为 0,取 、:三个分数为 。定理说明,无论排列如何,平面上任意四个点都不能被仿射半空间打散。
例题 2.2.4
(由仿射相关取出不可实现的标记)
取平面上的四个点 。取 ,则 ,且 。正系数在 和 ,所以证明将它们标为 1,并将 标为 0。假设分数 实现了这个标记,则 、、、。后两式相加得 ,前两式相加得 ,矛盾。这就是熟悉的异或标记,也说明加权和 正是被迫为正的量。
概念视角几何
仿射相关就是两个相交的凸包
令 。仿射相关式表明两个点 与 重合,也就是正、负两组点的凸包有一个公共点。仿射分数不可能在其中一个凸包上 ,而在另一个凸包上 。在正方形的例子里,这个公共点是 。
例题 2.2.5
(系数为零与共线的点)
取四个点 。系数 满足 ,且 。点 的系数为零,所以它的标记可以任意,在论证中不起作用。证明将 和 标为 1, 标为 0,这正是共线模式 1、0、1:中间的分数 ,不可能为负。同一个相关式也说明上面证明透视中所讲边界约定的重要性,因为 可以等于零。
反例模式
维数结论并不是关于每个集合的结论
平面上一条直线上按顺序排列的三个点,不能被仿射半空间标记为 1、0、1。中间点的分数是两个端点分数的凸组合,所以若两个端点均非负,中间分数也非负。平面中的 VC 维仍为 3,因为存在可以打散的非共线三点集。下界只需存在一个可打散集合。
坐标轴平行盒子
令 由有界闭盒子的指示函数组成,其中
不同坐标中的界可以分别选择,但每个正点必须同时满足所有坐标约束。该结论不需要把空盒子作为额外假设加入类中。
定理 2.2.6
(坐标轴平行盒子的 VC 维为 2d)
当 时,。
证明
(极端点与严格极值)
下界。 考虑 个点 。对每个坐标 ,若 要标为正,取 ,否则取 。若 要标为正,取 ,否则取 。每个区间都包含零,因此其他坐标不会限制 。所选端点恰好包含标为 1 的点。即使全零标记也可由 实现。
上界。 假设有 个互异点被打散。对每个点 ,选择一个包含其他所有点但排除 的盒子。 的某个坐标必定在盒子之外。若它低于该坐标的下端点, 便是全体点在该坐标上的严格最小值;若高于上端点,它便是严格最大值。每个坐标至多有一个严格最小点和一个严格最大点,因此至多 个点能充当这样的极值点。 个点却每个都必须是极值点,矛盾。
这个论证也适用于坐标值相同的情况:如果一个点被排除而其他点都被包含,它在某个坐标上必须是严格极值。相同坐标不能在该坐标上提供所需的证据。
例题 2.2.7
(被矩形打散的四个点)
在二维中,四个点 和 能被打散。若只包含 和 ,使用 。其余两点落在外面。即使四条边界坐标都是实数,平面上的五个点也不可能被坐标轴平行矩形打散。
例题 2.2.8
(一维情形与不能被排除的点)
当 时,盒子就是闭区间,定理给出 。点 被打散: 选中两者, 只选中 , 只选中 , 一个也不选。对三个点 ,中间点既不是严格最小也不是严格最大,所以没有区间能包含 和 而排除 。标记 1、0、1 不可能实现,这与 时的上界论证一致。
常见错误
(丢掉偏移量)
若去掉偏移量,类 的 VC 维是 ,而不是 。当 时,它包含 、 的指示函数和恒为一的函数。单个点 能被打散,两个点则不能:对点 ,标记 需要 且 ;对 ,标记 需要 且 。定理中多出的一维正是由偏移量 带来的。
常见错误
(把坐标相同当作极值证据)
在盒子的上界论证中,被排除而其他点都被包含的点,必须在某个坐标上是严格最小或严格最大。坐标相同不算数。在平面上,令 ,其他点为 。在第一个坐标上 严格处于 与 之间,在第二个坐标上严格处于 与 之间,所以任何包含其余四点的盒子都包含 。这个 永远不能被排除;同样的推理也说明,严格性正是证明至多只有 个证据点的依据。
容量与学习结论
定理统计有限集合上可能出现的标记;它没有给出具体的高效学习算法或精确样本量。VC 泛化结果还要结合独立抽样、置信度及学习规则等假设。单凭可调参数的数量也不能代替打散证明:类的定义、定义域和允许的边界都很重要。
练习与解答
快速检查
(给出 ,使 在 处分别标为 1、0、1。)
由原点处的分数决定 。
解答 · 答案
取 、,分数为 。
快速检查
(为什么实数轴上按顺序排列的三个点不能被闭区间打散?)
哪一种标记不可能实现?
解答 · 答案
包含两个端点的区间也包含中间点,所以无法实现标记 1、0、1。
快速检查
(对平面上的四个点 ,给出一个恰好选中 和 的盒子。)
分别限定每个坐标。
解答 · 答案
。
快速检查
(VC 维为 是否意味着仿射半空间能打散每个由 个点组成的集合?)
回想定义:只要求存在一个被打散的集合。
解答 · 答案
不是。定义只要求存在一个该大小的被打散集合;例如平面上共线的三个点,就不能按顺序实现 1、0、1。