在可实现学习中,每个标签都与某个目标假设一致。在不可知学习中,即使最好的假设也可能犯错。要做到接近最好的假设,学习器必须检测许多点上标签的细微偏差。我们在一个被打散的集合上构造含噪分布族,证明样本太少时,超额风险以常数概率过大。证明允许随机化和非正规学习器。
困难分布族
定义 2.4.1
(被打散集合上的困难含噪分布族)
设二元假设类 打散互异点 ,其中 。也就是说,每个符号向量 都能由 的某个假设在这些点上实现。固定 。对每个 ,定义分布 :先从这 个点中均匀抽取 ,再抽取 ,使
标签有噪声,但 是逐点 Bayes 最优标记,且 中有成员实现它。
若二元分类器 在 个点中有 个与 不同,则
事实上,预测 的条件错误率为 ,预测相反符号时为 。即使输出不属于 ,只要它在每个点输出二元标签,该恒等式仍成立。
两个检验不可能同时过于准确
我们使用以下有限样本检验不等式。对有限集合上的分布 ,令 ,,端点采用通常约定,对数为自然对数。则
这称为 Pinsker 不等式。在这里的有限情形中,可以选择达到总变差的事件 ,对 及其补集应用对数和不等式,再使用 Bernoulli 参数满足的 ,其中 。后者可由对 的二阶导数 得到,因为在 处函数值和一阶导数都为零;边界情形取极限。
对先验概率相等、根据数据猜测分布是 还是 的任何检验,其平均错误概率至少为
若检验在事件 上输出“”,平均错误为 。对检验使用的独立随机种子取平均后,同一不等式仍成立。
单个坐标难以推断
引理 2.4.2
(由含噪标签猜测单个符号)
固定下标 ,并固定 的符号 。令 在 上均匀,学习器(可带独立种子而随机化)根据来自 的 个独立同分布样本猜测 。它猜错的概率至少为
在不揭示其他符号时同样成立。
证明
(对乘积分布使用 Pinsker 不等式)
固定指标 ,并将所有 的符号 作为额外信息告诉学习器。令 和 表示其他符号固定且分别有 和 的两个分布。对数为自然对数。它们的单样本 KL 散度为
因子 是观察到 的概率;在其他每个输入点,两个标签分布一致。对 个独立样本,KL 散度为此值的 倍。由于 ,
由 Pinsker 不等式和二元检验界,即使已经知道其他符号,在其他符号固定时,对均匀的 、样本和独立种子取平均,错误猜测 的概率仍至少为
当 较大时,该界可能为负,此时只是没有提供信息。它适用于学习器在 上的预测,包括使用独立内部随机性计算出的预测。揭示额外信息只会使检验更容易,所以没有得到其他符号的学习器也满足同一下界。
先平均,再固定一个困难分布
定理 2.4.3
(具体的不可知样本下界)
设 且 。对任何由 个带标签样本可测地输出二元分类器的学习器,允许其使用独立随机种子;若
则上述分布族中存在一个固定的 ,使得以关于样本与学习器随机性的至少 的概率,
因此,在这一范围内,若分布无关的不可知保证要求失败概率严格小于 ,当 时必须有 。
证明
(对随机符号取平均)
取 ,并且只在证明中令各符号独立均匀。样本量条件使 。对坐标检验界先按其他符号取平均,再对 求和;由线性性,对符号、样本和独立学习器种子取平均后的错误比例期望至少为 。由超额风险恒等式,
对有限多个符号向量取平均,说明至少有一个固定的 使期望超额风险至少为 。对这个分布,超额量 位于 。若 ,则
困难的 在算法确定后选取,但在样本和随机种子抽取之前固定;它不会响应实际抽到的样本而改变。
证明透视
随机目标只是证明工具
打散只用一次:它使 Bayes 标记 属于 ,于是类内最优风险为 ,超额风险恰为 。样本量条件也只用一次:它使 ,把坐标界变成每个符号至少 的错误概率。核心的一步是对随机符号取平均,这使所有坐标对称,引理便可逐个坐标应用;然后再取出一个期望超额风险至少为 的固定 。
最后一步把期望换成概率。它要求超额风险 被 界住, 就在这里起作用:。若允许在看到每个样本后再选目标,那将是不同且更弱的陈述。
例题 2.4.4
(困难分布族中 的超额风险)
取 、、。在 处标签以概率 为 ,在 处标签以概率 为 。Bayes 分类器 在每个点上的错误为 ,所以 。分类器 在 处正确(错误 ),在 处错误(错误 ),风险为 。超额风险为 ,与 一致。
例题 2.4.5
(应用下界)
取 、、,所述条件恰好取等。此时 ;定理保证在这些被打散的点上存在一个固定含噪分布,使超额风险以至少 的概率超过 。若不知道学习器,定理不会指出具体是哪一个分布。
例题 2.4.6
(坐标界不提供信息的情形)
取 、。单样本散度为 ,所以 个样本时精确值约为 ,由 Pinsker 不等式,总变差至多为 。文中使用的放宽界为 ,得到总变差至多为一,错误界为 。这是有用范围的边缘:从 起,放宽后的引理不再提供信息,虽然精确散度在这里仍能给出非零的界。定理的条件 使 远在有用范围之内。
适用范围与可实现性警示
反例模式
困难分布族不是无噪声可实现的
当 时,每个点上的两种标签都有正概率出现。虽然 Bayes 标记属于 ,但没有确定性分类器能在 上取得零风险。把假设无噪声可实现性的定理应用到这个分布族,会忽略造成下界的标签不确定性。
常数 为了使证明透明而选取,并不声称最优。我们没有证明任意置信参数 的依赖、计算下界,或假设类没有打散指定点时的下界。论证也不要求学习器输出 中的成员。
常见错误
(准确度目标缩小时却固定偏差)
困难分布族中的超额风险为 ,所以偏差 必须随 缩放。若固定 ,同一论证只迫使需要约 个样本,期望超额风险才可能降到 以下;这是 的量级,不会随 增长。正是 的选择产生了 的依赖。
常见错误
(把概率 当成置信参数)
定理对一个固定常数证明失败概率至少为 。它没有说明当允许的失败概率 趋于零时样本量必须如何增长,也没有排除这种增长。失败概率严格小于 的分布无关保证需要 ;仅此而已。
练习与解答
快速检查
(若分类器只在 个点中的一个上与 不同,超额风险是多少?)
用“困难分布族”一节的恒等式。
解答 · 答案
。
快速检查
(当 时,困难分布族中的类内最优风险是多少?)
它就是每个点上的 Bayes 错误。
解答 · 答案
。
快速检查
(在检验 对 时,为什么只有 才产生非零 KL 散度?)
比较两个分布在 的输入 处的情形。
解答 · 答案
两个候选分布的输入分布相同,在其他每个点上的条件标签分布也相同。在 处散度为 ,再乘以 。
快速检查
(若 、,定理中下界条件覆盖的最大整数 是多少?)
计算 。
解答 · 答案
。
快速检查
(证明使用随机符号,为什么最终定理仍给出一个固定困难分布?)
想一想有限个分布的平均意味着什么。
解答 · 答案
有限分布族的平均至少为 ,故某个固定成员的期望至少为该值。对这个分布, 给出 。