同时选择模型与分类器
较大的假设类可以更好地拟合样本,但额外的灵活性也可能使拟合误差过于乐观。对于嵌套类,最小训练误差不会随类扩大而增加,即使选出的分类器总体误差更大。结构风险最小化通过为每个类的经验误差加上复杂度余量来处理这一选择,然后同时选出类和分类器。
困难在于,所选的类依赖于评估它所用的同一份样本。事先固定一个类时成立的界,不能直接用于事后获胜的类。我们先在各类之间分配置信额度,使所需比较同时成立。下面的结果允许任意标签,包括不能由任何一个类实现的分布。
类、风险与权重
定义 3.1.1
(加权有限类与类半径)
设 独立同分布于可测实例空间和二值标签上的固定分布 。设 是事先固定的可数序列,每个 都是有限非空的可测分类器 的集合。类之间可以重叠,也不要求嵌套。在看到样本前固定权重 ,满足 。
对 定义
对 ,为第 类设定半径
对数均为自然对数。权重较小,表示分配给该类的失败概率较少,因此罚项较大。这些权重不是各类为真的概率。半径可能超过一;此时偏差界虽仍有效,但不能提供有效信息。
概念视角算法
把半径看作描述长度
把对数拆开:。第一项是在长度为 的编码中指明类 的代价,第二项是指明其中一个成员的代价,所以 就是总描述长度除以 。对下面例子中的 ,,。
同时成立的事件与预言机不等式
定理 3.1.2
(类权重一致界与结构风险选择)
以至少 的概率,对所有 和所有 同时有
先固定每个有限类中假设的次序。对每个 ,按此次序选择第一个经验风险最小化解 。再选使 最小的最小指标 ,输出 。经验损失可测,因此这些固定的可数平局规则使所选指标和分类器可测。下面的同时事件是可测事件的可数交。则在同一事件上,
这是一个预言机不等式:数据驱动的输出与每个类中的最优风险加上该类余量进行比较。右侧是分析基准,不假定算法知道其值。
这里可数列表上的最小化解确实存在。因为正权重的和有限,。对固定的 ,半径趋于无穷,而经验风险在 中,所以任何固定有限水平之下只能有有限个类得分。这证明了所述选择存在,而不是假设下确界必然达到。有限列表的情形更简单。
证明
(并集界,再接四个不等式的链)
对固定的 和 ,损失指示变量相互独立、取值在 、均值为 。双侧 Hoeffding 不等式给出
对有限类使用并集界,该类的失败概率至多为 。再使用可数并集界,总失败概率至多为 。类重叠时可能重复计数,但不影响界的有效性。
在同时成立的事件上,对任意固定 ,选 ;有限性保证它存在。由选择规则及两次偏差不等式,
在同一个事件上,这对每个 都成立,因此取下确界得到预言机不等式。
证明透视
为什么这里选择类不需要第二份测试样本
所选指标依赖数据。证明没有假设它事先固定;而是先用预分配权重为所有类构造一个同时成立的事件。该事件成立后,便可将不等式应用于获胜指标。这样无需再支付一次选择罚项,因为类权重已经计入了选择;但这既不能取消观测值独立性的要求,也不使选择后的训练误差本身成为无偏估计。
比较两个得分
例题 3.1.3
(两个罚后得分的比较)
设 、、权重为 。考虑 、 两个类,其经验最小化解的误差分别为 和 。相应半径和得分约为
第二个类拟合样本更好,但在这两个类之间第一个罚后得分更低。完整可数比较中,第三个类仍可能获胜。这些得分是同时事件上的上界,不是精确总体风险;因此例子并不能证明在这次抽样中第一类的真实风险较低。
例题 3.1.4
(小权重的代价)
保持 、、,比较权重 与 。半径为 。 时为 ; 时为 。权重缩小到原来的 ,半径只增加约 ,因为权重是通过 进入的。排在清单很靠后位置的类会受到惩罚,但惩罚并不会高到无法接受。
例题 3.1.5
(大于一的半径)
取 、,一个 的类,权重 。则 ,所以 。由于风险落在 ,事件 平凡地成立。这个界有效,却什么也没有说;该类的罚后得分至少为 ,只有其他每个类得分更差时才会被选中。小样本与极小权重会使保证变得空洞,定理并没有掩盖这一点。
为什么先分配权重再看数据?
反例模式
依数据选出的单元素类可以隐藏大类
令 上均匀分布,标签处处为零。观察样本后,定义 在观测过的点上输出零,在未观测点上输出一。它的经验风险为零,而至少 个点未被观察,所以 。若事后称 是预先指定的单元素类并给它权重一,所谓固定类半径为 。当 、 时,该半径约为 ,所声称的界在每个样本上都失败。这个单元素类依赖观测到的输入,并未指定为定理中预先固定的类之一。把它当作预先指定的类是错误的一步。
如果类和权重确实预先固定且可数,之后可以根据数据作选择,因为定理同时控制每个候选。依赖数据的类或权重需要其他论证,例如用独立样本构造它们,或额外计入选择机制的代价。
常见错误
(只按经验风险选择)
对嵌套的类,最小训练误差不会随类变大而增加,所以只按 排序,永远不会严格偏好某个类而不选包含它的更大的类,无论更大的类的容许量有多大。定理控制的是罚后得分 。从选择规则中去掉 ,保证就不复存在。
常见错误
(预言机不等式中漏掉因子二)
基准是 ,而不是 。半径被付了两次:一次用来把所选分类器的经验风险换成总体风险,另一次用来把基准分类器的总体风险换成经验风险。最优风险为 、半径为 时,保证的界是 ,而不是 。
近似与估计
预言机表达式区分两个作用。 是第 类所能达到的近似误差; 是估计余量。扩大类可能降低前者,却增大后者。单凭一次训练样本,一般不能知道二者的精确值。
令 。假设同一独立同分布序列的前 项供每个 使用,并在选择规则中取 。第一 Borel–Cantelli 引理不要求失败事件相互独立;由于 ,同时事件几乎必然只失败有限次。对每个固定 ,。因此预言机不等式对每个 给出 ,继而 。每个被选分类器属于类的并,所以其风险至少为 。因此
这是相对于固定类并的一致性,并非自动得到 Bayes 一致性:后者还要求该并能对所研究的分布逼近最佳可测分类器。结果是统计性的;枚举所有类或寻找经验最小化解可能在计算上不可行。
练习与解答
快速检查
(设 、、、。写出该类半径的精确表达式。)
代入 。
解答 · 答案
,所以 。
快速检查
(在同时成立事件上,一个类的最优真实风险为 、半径为 。预言机不等式给所选分类器怎样的上界?)
记住半径要算两次。
解答 · 答案
在同时成立事件上,所选风险至多为 。
快速检查
(为什么不能把类设为一个依赖样本的单元素集合,再不加论证地使用固定类半径?)
比较这个单元素的训练风险与真实风险。
解答 · 答案
单类 Hoeffding 计算要求所用假设在抽样之前已固定;所提出的单元素可以编码样本,使训练误差人为地变小。上面的反例给出真实风险至少为 ,训练风险却为零。
快速检查
(对固定 和 ,解释为什么 。)
看根号下的分子和分母。
解答 · 答案
对固定的 ,分子为 ,分母为 。两者之比趋于零,其平方根也趋于零。