另一种学习保证
分类器给出单一标签;有时我们希望输出一组可能的标签,并控制真标签落在集合外的频率。分割保形预测无需假设概率模型正确便能给出这类保证。其概率涉及同时抽取校准样本与未来例子的整个实验,并不保证每个人或每个群组都有相同覆盖率。
定义 11.1.1
(非符合度分数与校准设定)
设标签集合 。选定可测、有限值的非符合度分数 ,且其选择独立于校准及测试例子;分数愈大表示标签 与输入 愈不吻合。例如,对先前训练的 ,可取 。分数不必是校准良好的概率。它可以来自另一份训练样本,只要该训练样本独立于校准和测试例子。
设 在给定独立训练数据后仍可交换;独立同分布是充分的特例。要求 及 。校准分数为 ,其中 ;构造集合时不使用未知的测试真标签 。
有限样本规则
定义 11.1.2
(分割保形的阈值与预测集合)
将校准分数排列为 ,并设
对新输入 ,输出
索引用 而非 ,因为未知测试分数也占 个秩中的一个。若 ,此规则使用 而非观察所得的有限阈值;返回两个标签是保守而且定义良好的做法。
定理 11.1.3
(由可交换秩得到边际覆盖)
在上述假设下,。此概率在给定任何独立训练数据后,对校准及测试例子取平均。
证明
(由测试分数的秩得到边际覆盖)
先对独立训练数据取条件,使分数函数固定。给全部 个分数附上独立同分布的连续平手排序变量 ,这些变量独立于所有分数和训练数据,再按字典序排列数对 。例子可交换、排序变量独立同分布,所以这些数对可交换;它们几乎必然互不相同,因此测试数对在 个数对中的秩 均匀分布在 。
若 ,则 ,真标签以概率一被覆盖。否则 。在事件 上,测试数对属于最小的 个数对,所以排在它前面的校准数对至多有 个,第 小的校准数对排在它之后。字典序细化了分数的次序,因此 ,即 。覆盖概率因此至少为 。平手排序变量只用于证明;实际规则保留等号,无需随机化。
证明透视
可交换性与计数 $n+1$ 在哪里起作用
证明靠三个要素。可交换性恰好只用一次,使测试的秩均匀;证明没有用到分数或数据分布的任何性质,所以保证对每个分布都成立。平手排序变量把可能有平手的样本变成严格排序,却不改变所关心的事件:字典序细化分数的次序,所以 仍然推出 。这个蕴含是单向的,因此平手只会使非随机集合更大。计数 出现,是因为测试分数也是被排序的一项;若用索引 ,就等于按错误的位置个数来校准。如果分数依赖校准数据,第一个要素就会失效:这 个数对不再可交换。
保证对独立训练数据成立,但一般不对某个已实现的校准集合取条件成立。它讨论真标签,并非说集合内每个标签的后验概率至少为 。集合很大可以安全却不够有用;覆盖率本身不能控制集合大小。
命题 11.1.4
(分数没有平手时的精确覆盖率)
除上述假设外,再设 个分数几乎必然没有平手。则 ,从而
证明
(不用平手排序变量的秩计数)
没有平手时,由可交换性,测试分数在 个分数中的秩 均匀分布在 。对 :若 ,则 ;若 ,则至少有 个校准分数严格小于 ,所以 。因此覆盖率恰为 。当 时覆盖率为 。最后,由 得下界,由 得上界。
校准例子
例题 11.1.5
(阈值、集合与空集合)
取四个校准分数 和 。则 、。用分数 且 ,两个候选分数为 和 ,所以 。若 ,分数是 和 ,所得集合为空。这个规则允许空集合;定理限制它对边际未覆盖的贡献,并不排除某个特定输入出现空集合。
若用同一组四个分数但取 ,则 ,阈值为 ,返回两个标签。若改用观察所得的最大分数,便是另一个规则,不能直接套用上述所需水平的证明。
例题 11.1.6
(用秩计数得到精确覆盖率)
取 、。则 ,。分数没有平手时,测试分数等可能地占据五个秩中的任何一个,真标签恰在其秩为 、 或 时被覆盖。覆盖率因此为 ,落在 内,与命题一致;因为 不是整数,结果略为保守。
例题 11.1.7
(平手使规则保持保守)
设分数对每个例子都是常数 ,所以五个分数全部平手。取 、,得 、。测试分数 满足 ,所以真标签以概率一被覆盖,而不只是 。规则使用 且不拆开平手,所以有平手时覆盖率只会高于无平手的值。代价是集合较大:这里 保留所有分数为 的标签。
边际覆盖可以掩盖群组差异
反例模式
群组覆盖率可以远低于边际水平
考虑一个特意简化的分布:、,且 恒成立。定义真标签的固定分数为 、;对两种输入都取 。令 个校准例子独立抽取、,故 。恰好当至少两个校准输入属于 时,阈值才为一;否则为零。
若测试输入为 ,真标签恰好在阈值为一时被覆盖。因此该群组的条件覆盖率为
远低于 。在 上,真分数永远为零,覆盖率为一。整体覆盖率约为 ,仍高于 。这并不矛盾:定理对群组取平均。此例并非声称该分数是有用的分类器,而是用来分清保证中的量词。
论证何时不再适用
固定分数后,证明需要校准和测试例子可交换。如果看过同一组校准分数后才调整分数或选择 ,上述秩论证可能失效。分布转移也可能破坏可交换性。对相关数据、自适应重用校准数据、条件覆盖或群组保证,需要另行分析。训练准确度及概率模型质量可能影响集合大小,却不能使边际覆盖自动变成对每个输入的保证。
常见错误
(索引中用 而非 )
索引 看似自然,却会覆盖不足。取 、,它给出 ;分数没有平手时覆盖率为 。正确的索引 给出 。测试分数占据 个秩中的一个,所以水平必须按 计算。
常见错误
(用校准数据来拟合分数)
若函数 是用其后用来校准的同一批例子拟合的,校准数对就不再与新的测试数对可交换:拟合出的模型通常对自己的例子拟合得比新例子好,校准分数偏小, 偏小,集合可能漏掉超过 比例的新标签。应按设定所要求的,用另一份样本拟合分数。
练习与解答
快速检查
(若 、,求 。分数互不相同且可交换时,此规则的覆盖率是多少?)
使用 和无平手命题。
解答 · 答案
。若可交换分数互不相同,测试秩不超过 的概率为 ;平手可能令非随机集合更保守。
快速检查
(若 、,此规则使用什么阈值?)
先算 ,再与 比较。
解答 · 答案
,所以 ,返回两个标签。
快速检查
(若所有校准分数都是 且 ,分数恰为 的测试候选会被纳入吗?)
看 定义中的不等号。
解答 · 答案
会。此时 ,规则使用 ,保留平手而不是剔除它们。
快速检查
(当 时,定理是否保证每个子群组都有 覆盖率?)
想想概率是对哪些随机性取的。
解答 · 答案
不保证。这是对各群组取平均的边际叙述;上面的两群组例子提供反例,稀有群组的覆盖率只有约 。
关于分割保形预测的边际覆盖及其假设,可参阅 Gibbs、Cherian 和 Candès 的研究论文 第 2.1 节。