为什么计算模式而不是模型?
一个很大的分类器族,在特定样本上仍可能只有少数不同表现。例如在实数线上移动阈值虽然得到无穷多个函数,但在 个不同的有序点上只有 个标记序列。泛化分析需要理解模型在观察点上能产生多少种错误模式,而不是只数参数值。我们用有限集合上的限制来表达这一点。
定义 17.1.1
(打散与增长函数)
设 是从 到 的非空函数族。若有限集 上每个函数 都是某个 成员的限制,便称 被打散。VC 维数是被打散集合大小的最大值;若不存在有限上界,则维数为无穷。定义 为所有由 个不同输入构成的集合上,不同限制个数的最大值,并令 。若定义域少于 点,则取大小至多为 的集合。重复点不会增加模式数。
某个集合不能被打散,不代表另一个同样大小的集合也不能。要确立维数,既要展示达到该大小的集合,也要排除所有更大的集合。训练数据的标记无须可由这个函数族完全实现。
组合定理
定理 17.1.2
(Sauer–Shelah 界)
若 的 VC 维数有限且等于 ,则对每个整数 ,
其中 时令 。当 时,这比平凡界 更好;固定 时,它随 多项式增长。
证明
(删去一点后作归纳)
将标记为一的点看成子集。只须证明:若 点集 的子集族 不打散任何 点集,则 。对 归纳,并同时对所有 进行, 显然。取 ,令 ,定义
令 ,。按原子集是否含 计数,得 。若 打散某集合, 也打散它,故 的维数至多为 。若 打散 中的 点集 ,对 上每个标记模式, 的两种标记都能实现,于是 打散 ,矛盾。因此 时, 的维数至多为 ;当 时,同一论证说明 为空,计数贡献为零。分别使用归纳假设及 Pascal 恒等式,得到
故断言成立,定理也随之成立。
证明透视
为什么交集少一个维数?
证明包含一个计数恒等式和一个结构观察。恒等式 只是记账: 上有两种延拓的模式在并集中计一次,在交集中再计一次。结构观察才是不明显的一步。交集中的每个模式都能以被移除点的两种标记实现。若交集已提供其余 点上的所有模式,多出的选择便会打散 点。并集只记录哪些模式可行;交集记录哪些模式有两种延拓。
假设“没有 点集被打散”用了两次,层次不同:对 直接使用;对 则经延拓论证使用,并降为 。所以归纳必须同时对所有 进行。论证以 Pascal 恒等式 收尾,它把两个和逐项配对。
从计数到学习保证
设 为正整数, 独立同分布,,定义 及 。以下另外假设 有限且分类器可测,从而不必处理无穷函数族上确界的可测性。上述计数引理本身无须函数族有限。
定理 17.1.3
(有限分类器族的 VC 一致界)
若 且 ,则
因此若 最小化 中的经验错误,在上式事件之外有 。若右边的概率界大于一,可以改用一。
证明
(幽灵样本、随机交换与对模式的联合界)
取一个独立、大小同为 的幽灵样本,其经验错误记为 。若上确界超过 ,按有限函数族的固定次序选一个见证分类器。给定原样本后,它在幽灵样本上的均值方差至多为 ;Chebyshev 不等式给出它与真实错误相差至多 的概率至少为 。因此原事件的概率至多为以下事件概率的两倍:存在 使 。
对每一对位置上的两个观测值,以概率二分之一独立交换;联合分布不变。给定所有 个观测值后,一个预测模式决定一个错误模式,而预测模式至多有 个;重复输入只会减少个数。对固定模式,交换后的差值是 ,其中独立符号 等概率取正负一,而 是固定数。Hoeffding 不等式表明其绝对值超过 的概率至多为 。对模式用联合界,再乘以幽灵样本步骤的二,便得所需概率界。
在该事件之外,令 为有限族中真实风险最小者,则
这里无须假设训练错误为零。
例子与反例
例题 17.1.4
(实数线上的阈值)
令 ,。在单点两侧选阈值可实现两种标记;两个有序点却不能取得 ,所以 VC 维数为一。对 个不同的有序点,正标记形成后缀,而且 个后缀全部可实现。因此 ,恰好等于 。对任何有限的阈值选集,前述条件下的学习界为 。
例题 17.1.5
(区间可以打散两点)
考虑把闭区间内标为正、其余标为负的分类器。任选两个不同点,选择不含两点、只含其中一点或同时包含两点的区间,便能实现四种模式。三个有序点不能取 :包含两端点的区间必包含中点。所以 。论证用的是区间的几何性质,而不只是端点参数的个数。
例题 17.1.6
(界何时开始有内容,以及 的情形)
对有限阈值族取 、。此时 ,且 ,所以界为 。以至少 的概率,每个经验错误与其风险相差至多 ,经验最小者与类内最佳阈值相差至多 。对照下面练习中的 ,同一公式会大于一。
另一极端是 :没有任何单点被打散,所以全部成员在每个输入上都一致, 只有一个函数,。定理给出 ,而对单个固定分类器用 Hoeffding 不等式则给出 。幽灵样本的论证并不追求最优常数。
反例模式
参数个数本身不是 VC 维数的证明
无穷定义域的所有子集构成的分类器族打散每个有限集,故 VC 维数无穷。可是它在任何固定的 点样本上仍只有有限多个限制,即 个。因此每个样本上的模式数有限,并不足以推出定理所需的多项式增长。类似地,只有低维参数化而没有关于参数如何产生分类器的假设,也不能直接推得 VC 界。
维数陈述有两半,量词并不相同;计算 VC 维数时的错误大多来自把两者混淆。
常见错误
(用一个不好的配置来界定维数)
要证明 ,展示一个被打散的 点集便足够;要证明 ,则必须说明每个 点集都不能被打散。对区间而言,任何两个不同点都得到全部四种模式,而每三个有序点都缺少 ;两半合起来才得到 。只说明某一个 点集不能被打散,并不证明任何上界:平面上的半平面不能给三个共线点标记 ,因为半平面是凸集;但不共线的三点可被打散,所以半平面的 VC 维数至少为三。
常见错误
(在 点而非 点上数模式)
对称化一步同时固定原样本与幽灵样本,所以联合界遍及 点上的模式。这个证明不允许把 写成 。对阈值而言,这会把 换成 ;对较大的 ,两个计数之比可以接近 。
练习与解答
快速检查
(若 只有恒零及恒一分类器,求其 VC 维数及 时的增长函数,假设定义域至少有 个点。)
解答 · 答案
一点可打散,但两点只有 及 。故 , 时 ,而 。
快速检查
(四点上的分类器族 VC 维数至多为一,Sauer–Shelah 允许多少个模式?给出达到此数的例子。)
解答 · 答案
至多 个。空集与四个单点集达到此数;任意两点同时标正的模式不存在,所以没有一对被打散。
快速检查
(对有限阈值族,取 、,不经四舍五入写出概率界。)
解答 · 答案
,界为 ,大于一。它虽然正确但没有信息量;直接用概率至多为一更好。
快速检查
(经验错误最小者的训练错误为零,定理是否保证真实错误为零?)
解答 · 答案
不保证。一致事件上只能推出 ;事件之外甚至没有这个结论。例如分类器可能错分一个有正概率但没有在样本中出现的区域。