保序概率校准与相邻块合并

某一低分档的经验正例率高于后一高分档时，单独照抄这两个频率会破坏排序假设。保序拟合把这两档暂时视为同一概率层，合并其样本并取平均。如果合并后的新层又低于左边一层，就继续向左合并。

它不强迫概率随分数严格上升：一些相邻分数可以被压到同一平台。平台意味着校准数据不足以在单调限制下把这些档可靠地区分，而不是证明它们的真实风险必然完全相等。

相邻违反块合并如何执行 ​

PAV 算法维护一个从左到右的块栈。每块保存起止位置、总权重 $W$、加权标签总和 $T$ 和均值 $T/W$。

1. 读入下一档，把它作为单点块压栈
2. 若栈顶左块均值大于右块均值，弹出两块，合并其 $W,T$ 后重新压栈
3. 重复第 2 步，直到栈上相邻均值不再下降，再处理下一档
4. 全部读完后，把每块均值赋给块内所有位置

等权例子按分数顺序取标签

前两点形成均值 $0,1$。第三点为 $0$，于是合并位置 $2,3$，得到均值 $1/2$。第四点又为 $0$，把刚才的双点块和第四点合并，得到三点均值 $1/3$。第五、第六点为 $1$，无需再合并，最终

式 (1) 不计 $1/2$ 的平方损失总和为

直接保留原标签的损失虽为零，却不是可行的非降序列；把所有点报成总体均值 $1/2$ 虽可行，损失为 $3/2$，又过于粗糙。

为什么合并结果是全局最优 ​

仅说“违反就平均”还不足以证明最优。PAV 的一个关键不变量是：对每个最终块 $[a,b]$，其均值记为 $v$，则块内任意前缀满足

单点块满足它。合并均值 $v_L>v_R$ 的两个块时，新均值介于两者之间。落在左块中的前缀，由旧前缀不等式加上非负的 $v_L-v$ 项得到；越过左块的前缀，可改看右块剩余后缀：旧块的前缀非负使后缀非正，再加上 $v_R-v\le 0$，仍非正。整块总和为零，于是新前缀非负。不变量随每次合并保留。

令

各块总残差为零，式 (2) 给出 ${\lambda }_k\ge 0$；若相邻拟合值严格上升，$k$ 必为块边界，故 ${\lambda }_k=0$。这正是单调约束的KKT 证书公理库KKT 条件Karush–Kuhn–Tucker conditions · KKT conditions用可行性、乘子符号、互补松弛与驻点方程刻画约束最优性的条件。，但还可以直接展开验证。

对任意非降可行序列 $q$，令 $v_i=q_i-{\hat{q}}_i$。目标之差为

最后一步利用分部求和，以及 ${\lambda }_k({\hat{q}}_{k+1}-{\hat{q}}_k)=0$。正权重使第一项只在 $q=\hat{q}$ 时为零，证明唯一最优。它体现了严格凸性公理库凸函数Convex function函数在任意凸组合处不超过相同权重下函数值的凸组合。，并不依赖挑选某个局部合并顺序后碰巧得到好结果。

时间成本与统计边界 ​

每个输入块压栈一次，每次合并把块数减少一。合并最多 $m-1$ 次，所以排序后算法为 $O(m)$ 时间、$O(m)$ 空间；若原始分数未排序，通常先付 $O(n\log (n+1))$ 比较排序成本（权重与均值运算按单位成本计）。同分数的聚合也必须先完成，不能依任意平票顺序给同一分数不同概率。

这个保证是对当前校准集的最优拟合。它不是总体概率校准公理库概率校准与可靠度Probability calibration · Reliability diagram用条件正例率等于报告概率定义概率校准，计算可靠度与分箱误差，并区分校准、边际均值、分类一致性和分辨力。的有限样本保证。小数据可产生大量不稳定平台，端点全零或全一还可能给新样本带来很大对数损失。额外平滑、裁剪或正则化可以另作设计，但会改变这里精确求解的问题。

保序映射保留弱排序，却可能制造平票。它通常比单参数温度缩放公理库温度缩放概率校准Temperature scaling固定分类 logits 后以一个正温度重新分配概率，证明类别排序不变及逆温度目标的凸性，并算出可修正和无法修正的校准例子。灵活，也需要更多数据支撑这份灵活性。如果原分数对真实风险的排序本来就错，任何非降后处理都无法任意颠倒它。

应按照数据角色分离公理库留出法与交叉验证Holdout · Cross-validation · 交叉验证通过隔离训练、模型选择和最终评价的数据角色估计样本外风险，并识别反复查看测试集造成的选择偏差。先训练原模型，再拟合校准映射，最后用未参与这两步的数据评价。不能让原模型在同一批样本上先过拟合出极端分数，再把那些训练标签拿来证明校准有效。