形式陈述
一个已经训练好的分类器输出分数 。若相信高分样本的正例机会不低于低分样本,却不相信分数本身已是概率,可以另学一个非降映射 ,把 转为 。这称为保序概率校准。
固定原分类器后,给定 条带标签的校准记录 ,其中 。先按分数排序;若多个样本分数相同,应先聚成同一个点,因为函数 不能给相同输入两个输出。设去重后的分数为
第 档有正权重 和平均标签 。平方损失的保序拟合解
这是带单调约束的经验风险最小化理路经验风险最小化Empirical risk minimization · ERM在假设类中选择训练样本平均损失最小的规则。。正权重使目标连续、严格凸,并随 趋于无穷;可行集合非空且闭,因此极小值取得,严格凸性再保证唯一;最终解是若干相邻块上的加权平均,自然落在 内,无需额外裁剪。[1, §3]
给未在校准集中出现的分数预测时,还须选定延拓方式,例如相邻已拟合分数之间采用右连续阶梯、两端延用端点值。式 (1) 只确定观测分数处的值,不唯一决定空隙中的整条函数。
直觉
某一低分档的经验正例率高于后一高分档时,单独照抄这两个频率会破坏排序假设。保序拟合把这两档暂时视为同一概率层,合并其样本并取平均。如果合并后的新层又低于左边一层,就继续向左合并。
它不强迫概率随分数严格上升:一些相邻分数可以被压到同一平台。平台意味着校准数据不足以在单调限制下把这些档可靠地区分,而不是证明它们的真实风险必然完全相等。
例子与边界
相邻违反块合并如何执行
PAV 算法维护一个从左到右的块栈。每块保存起止位置、总权重 、加权标签总和 和均值 。
- 读入下一档,把它作为单点块压栈
- 若栈顶左块均值大于右块均值,弹出两块,合并其 后重新压栈
- 重复第 2 步,直到栈上相邻均值不再下降,再处理下一档
- 全部读完后,把每块均值赋给块内所有位置
等权例子按分数顺序取标签
前两点形成均值 。第三点为 ,于是合并位置 ,得到均值 。第四点又为 ,把刚才的双点块和第四点合并,得到三点均值 。第五、第六点为 ,无需再合并,最终
式 (1) 不计 的平方损失总和为
直接保留原标签的损失虽为零,却不是可行的非降序列;把所有点报成总体均值 虽可行,损失为 ,又过于粗糙。
为什么合并结果是全局最优
仅说“违反就平均”还不足以证明最优。PAV 的一个关键不变量是:对每个最终块 ,其均值记为 ,则块内任意前缀满足
单点块满足它。合并均值 的两个块时,新均值介于两者之间。落在左块中的前缀,由旧前缀不等式加上非负的 项得到;越过左块的前缀,可改看右块剩余后缀:旧块的前缀非负使后缀非正,再加上 ,仍非正。整块总和为零,于是新前缀非负。不变量随每次合并保留。
令
各块总残差为零,式 (2) 给出 ;若相邻拟合值严格上升, 必为块边界,故 。这正是单调约束的KKT 证书理路KKT 条件Karush–Kuhn–Tucker conditions · KKT conditions用可行性、乘子符号、互补松弛与驻点方程刻画约束最优性的条件。,但还可以直接展开验证。
对任意非降可行序列 ,令 。目标之差为
最后一步利用分部求和,以及 。正权重使第一项只在 时为零,证明唯一最优。它体现了严格凸性理路凸函数Convex function函数在任意凸组合处不超过相同权重下函数值的凸组合。,并不依赖挑选某个局部合并顺序后碰巧得到好结果。
时间成本与统计边界
每个输入块压栈一次,每次合并把块数减少一。合并最多 次,所以排序后算法为 时间、 空间;若原始分数未排序,通常先付 比较排序成本(权重与均值运算按单位成本计)。同分数的聚合也必须先完成,不能依任意平票顺序给同一分数不同概率。
这个保证是对当前校准集的最优拟合。它不是总体概率校准理路概率校准与可靠度Probability calibration · Reliability diagram用条件正例率等于报告概率定义概率校准,计算可靠度与分箱误差,并区分校准、边际均值、分类一致性和分辨力。的有限样本保证。小数据可产生大量不稳定平台,端点全零或全一还可能给新样本带来很大对数损失。额外平滑、裁剪或正则化可以另作设计,但会改变这里精确求解的问题。
推论与应用
保序映射保留弱排序,却可能制造平票。它通常比单参数温度缩放理路温度缩放概率校准Temperature scaling固定分类 logits 后以一个正温度重新分配概率,证明类别排序不变及逆温度目标的凸性,并算出可修正和无法修正的校准例子。灵活,也需要更多数据支撑这份灵活性。如果原分数对真实风险的排序本来就错,任何非降后处理都无法任意颠倒它。
块栈的结构还能迁移到递减密度似然理路Grenander递减密度估计Grenander estimator · Monotone density maximum likelihood · 递减密度的最小凹上界估计在已知半直线支持上,以样本间距加权合并构造唯一递减密度MLE,证明它是经验CDF最小凹上界的左斜率,并交出完整似然证书与端点边界。,但块中分子是经验质量,分母是观测间距,合并高度必须用总质量除以总长度,不能把本页概率响应的权重解释照搬过去。另一个重要边界是凸回归理路有限设计的凸最小二乘回归Convex least squares regression · Multivariate convex regression · 凸回归的有限证书将凸函数类上的加权平方拟合精确化为逐对支撑平面约束,证明拟合值唯一、交付全局乘子证书,并区分非等距斜率约束、未见点延拓与统计风险。:相邻斜率需要递增,并不意味着可对原始斜率独立做PAVA。输入、响应、权重时,这样池化后最好的常数预测损失为,而真正凸拟合的损失为;算法结构相似不能替代目标函数的推导。
应按照数据角色分离理路留出法与交叉验证Holdout · Cross-validation · 交叉验证通过隔离训练、模型选择和最终评价的数据角色估计样本外风险,并识别反复查看测试集造成的选择偏差。先训练原模型,再拟合校准映射,最后用未参与这两步的数据评价。不能让原模型在同一批样本上先过拟合出极端分数,再把那些训练标签拿来证明校准有效。
参考资料