标签错误不一定使学习不可能
可实现的 PAC 学习假设每个观察到的标签都与目标概念一致。如果标签偶尔翻转,坚持拟合每个样本的学习器可能拒绝一个相当有用的假设,或转而拟合噪声。解决方法不是忽视标签假设,而是明确噪声机制,并分析由此产生的观测风险。
我们研究有限假设类上的二分类。精确模型使我们能够比较相对被污染标签的错误率和相对不可观察的干净目标的错误率,也说明为什么噪声接近二分之一时,学习在统计上更困难。这个保证针对特定的独立噪声模型,并不声称任意错误标注都无害。
干净误差与观测误差
设 服从可测实例空间 上的概率分布 , 可测, 是有限非空的可测分类器集合。采样前固定 、 和 。下文的对数均为自然对数。对 ,定义干净误差
定义 9.1.1
(随机分类噪声)
在随机分类噪声模型中,标签为 ,其中 是满足 、且独立于 的 Bernoulli 随机变量。样本使用的各对 是 的独立同分布副本。假设 。学习器看到的是 ,而不是 或干净标签。
令 为观测标签误差。按 是否与 一致分类,得到关键恒等式
干净预测正确时,恰在噪声位为一时变错;干净预测错误时,恰在噪声位为零时仍然错误。由于 ,按观测误差排序与按干净误差排序相同。但两种误差并不相等:即使目标 的观测风险也为 。
例题 9.1.2
(数值比较)
若 ,干净误差为 的分类器,其观测误差为 。另一个干净误差为 的分类器,观测误差为 。后者仍较差,但观测差距 小于干净差距 。因此需要足够样本才能克服抽样波动、检测小差距。
有限类学习保证
给定 个独立受噪声污染的样本 ,定义
选择任一经验风险最小化解 ,并固定平局规则。由于类有限,最小值存在。算法比较经验误差时不需要知道 ;但下面的样本量保证依赖于它。搜索整个类可能在计算上昂贵,因此统计界本身并不证明高效学习。
定理 9.1.3
(独立标签翻转下的干净超额误差)
对 、,令
以至少 的概率(概率针对受噪声污染的样本),
因此,对 ,若
则以至少 的概率,干净超额误差不超过 。若 ,最小干净误差为零。
证明
(一致偏差,再把观测风险换成干净风险)
对固定的 ,指示变量 相互独立,取值在 ,均值为 。双侧 Hoeffding 不等式和并集界给出
在其补事件上,选 。风险恒等式使 也最小化 。由经验最小化及两次一致偏差界,
减去 并除以正因子 ,得到干净误差界。代入所示样本量即可保证 。
证明透视
噪声带来的代价出现在哪里
并集界一致地控制含噪经验误差,因此对看到样本后选出的假设仍然有效。因子 只在将观测风险差距转成干净风险差距时出现。当 接近 ,此因子的倒数放大估计误差;样本界中的平方因子是该方法的一个充分上界,本身并不是匹配下界。
例题 9.1.4
(一个具体的样本量)
例如,取 、、、,上述条件为 ; 足够。这个不依赖分布的保守数值不是每个类和分布的精确样本需求。
在二分之一及其另一侧会怎样?
当 时,观测标签是独立公平位,与 无关,所以恒等式变成对每个 都有 。信息损失可以精确说明。
命题 9.1.5
(噪声率为二分之一时无法学习)
设实例空间只有一个点,两个可能的目标分别是常值零和常值一,噪声率为 。对任何学习器,无论是否随机化、使用多少个独立污染样本,两个目标中至少有一个满足:输出的干净误差小于 的概率至多为 。
证明
(两个目标产生相同的数据)
在任一目标下,每个观测标签都是独立公平位,所以整个样本的分布相同,学习器输出的分布也相同。要使干净误差小于 ,学习器必须在该单点预测正确的常值。若它以概率 输出零,则在两个目标下的成功概率分别为 和 ,其中至少一个不超过 。即使学习器随机化、样本数任意大,这仍然成立。
若已知 ,排序是反转而非消失。翻转每个观测标签,可将噪声率变为 ,继而应用前面的分析。若噪声率和目标均未知,不能直接假定排序方向相同。阈值 是所述标签翻转模型的性质,不是所有噪声学习问题的普适边界。
例题 9.1.6
(已知噪声率大于二分之一)
设噪声率 已知,某分类器的干净误差为 。翻转之前,它的观测误差为 ,而目标本身的观测误差是 :排序被反转。学习器把收到的每个标签翻转后,噪声率变为 ,同一个分类器的观测误差为 ,与 一致。此时在翻转后的标签上做经验风险最小化,会偏好干净误差较小的假设。若学习器不知道 是 还是 ,就无法选择方向,这正是未知情形被排除的原因。
反例模式
任意错误标注可能反转偏好
令 、 均匀,干净目标处处为 。设 的标签从不翻转, 的标签总是翻转。分类器 的观测风险为零,干净误差却为 ;目标的观测风险为 ,干净误差为零。由于翻转概率依赖 ,且在一点超过二分之一,常数独立噪声恒等式不适用。最小化受污染误差因而可能偏好错误分类器。
常见错误
(坚持训练误差为零)
为无噪声情形设计的一致假设学习器,在噪声下会失效:只要有一个标签被翻转,连目标 也与样本不一致。取 、 个例子,没有任何标签被翻转的概率是 ,所以这种学习器以约 的概率拒绝 。补救办法是最小化经验误差,容许一定比例的不一致。
常见错误
(把观测差距当作干净差距)
定理把观测差距除以 才得到干净差距。在 时, 的观测风险差距对应 的干净差距。忘记这个除法,会把干净超额误差低估为原来的五分之一。
练习与解答
快速检查
(若 ,求干净误差为 时的观测误差;并在同一模型下,由观测误差 还原干净误差。)
两个方向都使用 。
解答 · 答案
。反过来,。
快速检查
(对 、、,写出 时的一致半径 ,并给出所得的干净超额误差界。)
先算 。
解答 · 答案
,定理给出超额误差至多为 ,概率至少为 。
快速检查
(为什么当 时,即使有无限多个独立样本,学习器在单点例子中也无法区分两个常值目标?)
比较两个目标下数据的分布。
解答 · 答案
在任一目标下,每个观测标签都是独立公平位;整个数据分布完全相同,所以观察更多数据也不能区分这两个假设。对任何随机化的预测,两个成功概率之和为一。
快速检查
(设已知 ,标签以这个常数比率独立翻转。若学习器把收到的每个标签翻转,会怎样?)
问翻转后的标签何时与 不同。
解答 · 答案
所得标签与 不同,恰当原先的噪声位为零,概率为 。各例子之间的独立性保持不变,小于二分之一的分析因此适用。