统计查询请求的是期望值,而不是单个带标签样本。独立标签翻转会以有结构的方式扭曲这些期望。若翻转率已知且低于二分之一,每个有界的干净查询都能转换成有界的噪声查询。这种转换在期望层面是精确的,但噪声接近二分之一时,其容差必须变小。
定义 7.2.1
(已知噪声率的分类噪声)
设 位于可测实例空间 ,干净标签为 ,其中目标 可测。观察到的标签为 ,其中 独立于 ,满足 ,并对每个样本重新独立抽取。假设已知噪声率满足 ,记
定义 7.2.2
(干净统计查询 oracle)
干净统计查询由可测函数 和容差 组成。查询 oracle 可返回与 的距离不超过 的任意值。学习器必须适用于每个有效答案序列,包括自适应选择的答案。
模拟任意查询
定理 7.2.3
(有界噪声查询恢复干净期望)
假设精确翻转率 已知。对任意干净查询 ,定义
并提出噪声查询
则 ,且
因此,若噪声 SQ 答案与其期望的距离至多为 ,将其除以 就得到容差为 的有效干净答案。
证明
(分离与标签无关的部分和关于标签的奇部分)
对 ,有 。此外,
因为 ,所以 。独立性给出 ,故
取期望便得 (2)。在这个可实现模型中,计算实际上只需要 ;独立性是充分条件。若干净标签本身随机,相应的充分条件是 。如果只知道 的上界,用错误的 除一般会引入偏差;未知速率需要单独的估计或学习论证。若噪声 oracle 返回 ,满足 ,则 。除法后的答案不一定位于 ;有效性只要求容差不等式。若约定还要求答案落在 ,将它裁剪到该区间不会增加其与干净期望的距离。
证明透视
为什么要缩放整个查询
与标签无关的部分 不受噪声改变,而关于标签的奇部分 被缩小为 倍。若只把后者乘以 ,结果可能超出允许范围 。(1) 转而把整个目标期望缩小为 倍,使查询保持有界,再通过更小的容差支付反演代价。
例题 7.2.4
(校正分类误差查询)
设 ,令 。则 、,而 (1) 的有界查询为
它取值 和 ,期望为 ,其中 。等价地,噪声误差满足 。例如,、 时,。一般构造适用于所有有界查询,而不只是误差查询。
概念视角代数
噪声是缩小奇部分的算子
把查询写成 。因为 ,它的带噪期望为 :噪声不改变与标签无关的偶部分,只把标签的奇部分乘以 。要使它等于 ,就必须取 、,这正是 (1)。
例题 7.2.5
(带噪声 oracle 的相关性查询)
设 ,即 ,并设 在质量为 的集合上与目标 一致、在其余部分不一致,所以 。对 ,有 、、,期望为 。干净容差为 时,噪声 oracle 可以相差 ,即可回答 内任何值。假设它回答 ,除以 得 ,与真值 相差 ,仍在容差内;另一个极端答案 给出 ,同样相差 。因此两端都满足容差,与 (2) 的保证一致。
例题 7.2.6
(两个边界情形:无噪声与重噪声)
若 ,则 ,(1) 成为 ,因为 :这个构造原样返回干净查询。在 (3) 中取 、、。 时批量为 。 时 ,,约为前者的一百倍,与因子 吻合。当 时这个因子无界增长,这预示了下面的下界。
用新鲜噪声样本回答自适应查询
定理 7.2.7
(可模拟有限的自适应 SQ 计算)
假设精确速率 已知,固定一对 ,并预先固定整数查询上限 与容差 。假设确定性的干净 SQ 算法至多提出 个查询,容差均为该 ,并对同一对 的每个有效答案序列都成功。给定 ,使用一批新鲜独立样本回答每个噪声查询,其批量为
将每批样本平均值除以 。以至少 的概率,每个模拟答案对对应干净查询都有效,因此干净算法成功。最多使用 个噪声样本。
证明
(对先前的自适应记录取条件)
在某轮,以此前全部查询和答案为条件。下一个查询于是固定,而它的新鲜批次独立于先前记录。其转换后查询在 中有界。因此 Hoeffding 不等式将样本均值偏离 超过 的条件概率控制为
令 为第 轮被到达且其答案无效的事件。这个估计对到达该轮的每段先前记录都成立,故 。对 使用并集界,得到同时有效事件。在此事件上,由 (2),每个除法后的答案都是有效干净答案,尽管后续查询依赖先前答案。干净算法的假设于是给出成功。对随机化干净学习器,类似结论还需要干净保证适用于可依赖学习器随机种子的有效自适应回答策略;干净失败概率随后与 相加。这里没有暗中假设这个更强量词。
这是统计模拟上界。高效计算还要求查询和干净学习器可高效求值。新鲜批次使条件集中论证直接成立;对自适应选择的查询重复使用同一批次,需要另行分析。
噪声代价无法消除
上界含有 。一个两目标问题说明,对单个干净查询、常数容差和常数置信度, 确实必要。它没有证明一般 SQ 计算对 、 或 的联合依赖最优。
定理 7.2.8
(噪声样本的两目标下界)
设 。在单点实例空间上,考虑两个可能的恒定目标 和 ,标签以速率 独立翻转。即使知道 ,任何使用固定最坏情况样本数 、并对两个目标都以至少 的概率输出正确标签的学习器,必须满足
该结果包括使用此固定样本预算的随机化学习器;随机样本数需要单独论证。干净问题可由容差 的单个查询 解决,因为答案的符号就是目标标签。这是例子上的下界,并非声称每个学习类都需要这么多样本。
证明
(两个相近的乘积分布难以区分)
在目标为 时,一个噪声标签为 的概率是 ;在目标为 时,该概率为 。令 、 为两个 标签分布。其 Hellinger 亲和度为
对 使用柯西–施瓦茨(Cauchy–Schwarz)不等式,得到
若学习器对两个目标都以至少 的概率正确,则其输出是一个对两个分布错误概率均不超过 的检验。因此事件“输出 ”的概率差至少为 ,全变差至少为 。对随机化学习器,可在两个分布中加入同一个独立随机种子;亲和度不变。故 ,并有
因为 且 。
当 时,两个目标产生完全相同的噪声标签分布,故无论样本数多少,都无法对两个目标同时达到严格大于 的成功概率。这个极限中的不可能性解释了为何 时不能反演 (1)。
反例模式
已知平均噪声率不等于独立噪声
设 在 上均匀分布,始终取 ,并在 处以概率 、在 处以概率 翻转标签。平均翻转率为 ,但翻转并不独立于 。对查询 ,干净期望为 。在 (1) 中使用 得到 ;其噪声期望仍为 ,不是 。因此除以 得 ,而非 :偏差 即使样本无限也存在,且当 时模拟答案无效。这里 ;问题是所需的条件缩放关系失败。纯无标签查询不受影响。
常见错误
(把观察到的噪声误差当成干净误差)
当 时,观察误差为 的假设,其误差并不是 。观察误差为 ,所以干净误差是 。即使完美的假设,观察误差也是 。在不同噪声率之间比较观察误差,或把 当作必须突破的下限,都混淆了这两个量。
常见错误
(对自适应查询重复使用同一批样本)
自适应模拟的证明先对至今的记录取条件,再使用与它独立的一批样本。若用同一批样本回答所有查询,后面的查询就依赖于由同一批样本算出的先前答案,条件步骤便不再成立,Hoeffding 不等式也不能对它使用。样本总量 正是为 批新鲜样本付出的代价。
练习与解答
快速检查
(纯无标签查询。若 且 ,计算 。)
先求 和 。
解答 · 答案
此时 、,所以 。 等于 。在这个特殊情形,也可以直接查询 而无需付出噪声代价。
快速检查
(相关性查询。对 、,求转换后的查询及其期望。)
的哪一部分关于 是奇的?
解答 · 答案
、,故 ,且 。
快速检查
(计算批量。若 、、、,求 (3) 给出的整数 。)
先算 。
解答 · 答案
,故 ;这里使用自然对数。
快速检查
(抛硬币式噪声。为什么 时模拟失败?)
先看 ,再看单点实例空间。
解答 · 答案
此时 ,无法做除法。更根本地,在单点空间上,两种恒定目标产生相同的独立公平噪声标签,因此两种目标的成功概率之和至多为一,不可能对二者同时以超过 的成功概率识别。
快速检查
(置信度核算。若 个自适应查询中每一个的条件批量失败概率至多为 ,至少有一个失败的概率是多少?)
各轮并不独立。
解答 · 答案
对每一轮,只在该轮被执行时才定义失败。对条件界取平均,其无条件失败概率至多为 。并集界给出至多 ;各轮失败不必独立。