分层保形分类：利用类别层次结构构建紧致且具覆盖保证的预测集 (Hierarchical Conformal Classification)¶
会议: NeurIPS 2026
arXiv: 2508.13288
代码: https://github.com/florisdenhengst/hierarchical-conformal-classification
领域: 最优化
关键词: 保形预测, 分层分类, 类别分类体系, 约束优化, 不确定性量化
一句话总结¶
本文提出分层保形分类（HCC）框架，将有向无环图（DAG）形式的类别层次结构显式引入保形预测的预测集构建中，通过非重叠叶覆盖剪枝将原本组合爆炸的搜索空间急剧缩减，在严格保持有限样本覆盖率理论保证的同时，自适应权衡预测集合紧凑度与语义特异性，显著生成更符合人类认知且实用的预测集。
研究背景与动机¶
保形预测（Conformal Prediction, CP）作为一种严格的无分布不确定性量化框架，能够在有限样本条件下为任意黑盒概率分类器提供无偏的统计覆盖率保证，即以用户指定的显著性水平 \(1-\alpha\) 生成包含真实类别的预测集合。然而，标准保形预测方法普遍将类别标签空间视为完全平坦且非结构化的离散集合。在面对高不确定性输入时，标准分类器往往会输出庞大且杂乱的候选类别集合，例如在图像识别任务中同时包含十几个外观相似的狗品种标签，严重削弱了预测结果的可解释性与下游决策效用。
事实上，绝大多数真实任务的类别体系均具备天然的层次拓扑结构（如 WordNet 分类网络、DBpedia 本体库及疾病分类树），通常形式化建模为有向无环图（DAG）。当分类器对具体叶节点（如“惠比特犬”与“灵缇犬”）存在混淆时，直接输出它们的高层抽象父节点（“猎犬”甚至“犬科动物”）远比给出一个长篇叶类别枚举更符合终端用户的认知与操作逻辑。然而，现有尝试融入层次结构的保形方法面临着尖锐矛盾：部分工作仅局限于严格树结构或高概率质量区域而放弃严格覆盖保证；部分方法仅通过惩罚树距离将预测限制在最可能预测的祖先路径上；而基于整数规划的结构化保形预测方法则面临巨大的组合搜索复杂度，且无法动态平衡预测集合大小与语义抽象度。
面对候选节点子集指数级爆炸（\(2^{|\mathcal{V}|}\)）与多层语义粒度权衡的挑战，本文提出从受约束组合优化的视角系统性重构层次保形预测。核心 idea：将层次化预测集构建形式化为最小化“集合基数+被覆盖叶节点加权惩罚”的约束优化问题，利用非重叠叶覆盖（NOL-cover）从理论上严格排除无效与次优候选解，配合自底向上的分数传播与动态推理剪枝，在保证严格有限样本叶覆盖的前提下生成兼顾紧致性与特异性的最优分层预测集。
方法详解¶
整体框架¶
分层保形分类（Hierarchical Conformal Classification, HCC）旨在基于已知的类别 DAG \(\mathcal{T} = (\mathcal{V}, \prec)\)，构造一个自适应预测器 \(h_{\beta, \mathcal{V}}^*(\mathbf{x}_t, \alpha)\)。该预测器不仅包含叶类别，还允许包含具有概括语义的内部祖先节点。整个流程由离线校准（校准集 \(\mathcal{D}_c\)）与在线推理（测试样本 \(\mathbf{x}_t\)）两个核心阶段组成： 1. 搜索空间剪枝与候选集构建：基于层次 DAG 识别所有合法的非重叠叶覆盖（Non-Overlapping Leaf Covers, NOL-covers），将组合搜索空间从 \(2^{|\mathcal{V}|}\) 降低至多项式级别； 2. 分数与标签自底向上双向传播：将基础黑盒分类器的叶节点输出概率向上求和汇聚为内部节点的传播预测分数，并将真实叶标签的所有祖先标记为传播真实多标签； 3. 分层多标签保形校准：为每个候选 NOL-cover 校准对应的保形分类器，计算针对多标签场景广义化的保形分位数； 4. 动态剪枝与自适应推理：在推理阶段利用叶节点保形集合的最近公共祖先（LCA）动态剪枝候选集，并经过多重检验校正后，在满足覆盖率约束的前提下选取最小化紧致性与特异性加权代价的目标子集。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入样本与基础分类器叶节点预测分数"] --> B["自底向上得分与多标签传播"]
B --> C["非重叠叶覆盖剪枝 NOL-covers"]
C --> D["广义多标签保形校准与分位数计算"]
D --> E["动态推理剪枝与多重检验校正"]
E --> F["加权代价最小化的分层预测集输出"]关键设计¶
1. 层次保形分类的受约束优化形式化：平衡集合紧凑度与语义特异性 针对平坦保形预测集合过大且缺乏结构的问题，HCC 将预测目标建模为双重惩罚优化问题。设 \(\text{leaf-cov}_\mathcal{T}(\mathcal{N})\) 表示节点集合 \(\mathcal{N}\) 所覆盖的全部叶类别集合，目标是在确保以 \(1-\alpha\) 概率包含真实类别 \(y_t\) 的前提下，优化预测集的可用性： $\(h_{\beta, \mathcal{V}}^*(\mathbf{x}_t, \alpha) = \arg\min_{\mathcal{N} \subseteq \mathcal{V}} |\mathcal{N}| + \beta \left|\bigcup_{v \in \mathcal{N}} \text{leaf-cov}_\mathcal{T}(\{v\})\right| \quad \text{s.t.} \quad \mathbb{P}\left(y_t \in \text{leaf-cov}_\mathcal{T}(\mathcal{N})\right) \ge 1-\alpha\)$ 在此目标中，\(|\mathcal{N}|\) 惩罚预测集中包含的节点总数，促使集合简短易读；第二项则惩罚预测集覆盖的底层叶节点总数，代表预测的模糊度。超参数 \(\beta \in \mathbb{R}_+\) 充当杠杆：较大的 \(\beta\) 鼓励模型深入叶节点提供具体的细粒度预测，而较小的 \(\beta\) 则允许模型在分类器把握不足时，用高层抽象概念（如“哺乳动物”）代替一长串具体类别。为消除人工调参成本，本文提出自适应设定基准权重，取 DAG 中非叶节点覆盖叶数中位数的倒数：\(\beta = (\text{median}[\{|\text{leaf-cov}_\mathcal{T}(\{v\})| : v \notin \text{leaves}(\mathcal{T})\}])^{-1}\)。
2. 候选解空间结构化剪枝：非重叠叶覆盖（NOL-cover）理论 在任意拥有数十至数千个节点的 DAG 中，直接对所有可能子集 \(2^{|\mathcal{V}|}\) 进行优化在计算上完全不可行。HCC 证明了搜索空间可被无损压缩至“非重叠叶覆盖”（NOL-cover）子集族。一个合法的 NOL-cover \(\mathcal{S} \subseteq \mathcal{V}\) 必须严格满足两个条件：其一为叶覆盖完备性（\(\text{leaf-cov}_\mathcal{T}(\mathcal{S}) = \mathcal{Y}\)），所有真实类别必须在 \(\mathcal{S}\) 中至少存在一个对应祖先或自身；其二为祖先独立性（\(\forall u, v \in \mathcal{S}, u \ne v \implies \neg(u \prec\prec v) \land \neg(v \prec\prec u)\)），集合内严禁同时出现互为祖先与后代的冗余节点。 作者在理论上给出了严格支撑：命题 1 证明任何满足概率覆盖要求的可行解都必须覆盖全部叶节点，否则存在漏失风险；命题 2 证明任何包含祖先-后代重叠的解，均可通过移除后代节点构造出目标函数值更低或相等的纯净祖先解，即任何最优解必然祖先独立。以深度为 \(d\) 的满二叉树为例，朴素搜索空间为 \(2^{2^d}\)，而 NOL-cover 族仅约为 \(2^{d-1}\)，使原本完全停滞的组合优化转化为高效拓扑遍历。
3. 自底向上概率融合与面向 DAG 的广义保形评分函数 为在内部抽象节点上评估预测可信度，HCC 定义了自底向上的传播得分与传播标签机制。对于任意节点 \(v \in \mathcal{V}\)，其预测分数定义为其覆盖的所有后代叶节点概率之和：\(\hat{g}(\mathbf{x})_v := \sum_{w \in \text{leaf-cov}_\mathcal{T}(\{v\})} \hat{f}(\mathbf{x})_w\)；对于样本 \((\mathbf{x}_i, y_i)\)，其多标签真值集合 \(\mathcal{Y}'_i\) 包含真实叶节点 \(y_i\) 的全部祖先节点。 由于 DAG 允许多重继承（一个叶节点属于多个上层父节点），在某个特定的 NOL-cover 中，一个样本可能同时命中多个有效节点。标准单标签保形分数在此失效。HCC 设计了基于局部最大兼容性的广义非一致性评分函数： $\(s(\mathbf{x}_i, \mathbf{y}_i, \mathcal{S}) = \hat{g}(\mathbf{x}_i)_{v'_i}, \quad \text{其中} \quad v'_i := \arg\max_{j: \mathbf{y}_{i,j}=1} \hat{g}(\mathbf{x}_i)_j\)$ 定理 1 证明，仅需在该样本命中的合法标签中选取模型打分最高者作为校准统计量，即可通过校准分位数 \(\hat{q} = \lceil(n_c+1)(1-\alpha)\rceil / n_c\) 的标准经验分位数构造保形预测集 \(C(\mathbf{x}_t)\)，并在理论上无偏保证 \(\mathbb{P}[y_t \in \text{leaf-cov}_\mathcal{T}(C(\mathbf{x}_t))] \ge 1-\alpha\)。
4. 基于最近公共祖先（LCA）的动态推理剪枝与多重比较校正 在测试阶段，若直接对预先提取的所有 NOL-cover 并行运行保形预测，面临多重假设检验引起的显著性稀释问题。若简单应用保守的 Bonferroni 校正 \(\alpha' = \alpha / m\)，庞大的候选数 \(m\) 会迫使保形阈值过度严苛，使预测集合虚胖。 HCC 提出针对单样本的推理期动态剪枝策略：算法首先利用标准平坦叶节点保形预测器计算该样本的基础叶预测集，并提取该集合在 DAG 中的最近公共祖先（Lowest Common Ancestor, LCA）。根据层次拓扑单调性，任何包含了位于 LCA 之上更深层祖先的 NOL-cover，其所生成的预测集合必然会覆盖比该 LCA 更宽泛的无用叶空间，在目标函数中劣于 LCA 所在候选集。HCC 在推理期动态剔除所有包含此类退化祖先的 NOL-cover，将有效比较集合 \(m\) 压缩到极小规模，大幅缓解了 Bonferroni 校正的保守性。
一个完整示例¶
考虑论文中的西餐分类示例（包含 7 个叶类别：凯撒沙拉、希腊沙拉、奶酪三明治、火腿三明治、金枪鱼三明治、煎蛋卷、松饼；内部节点包含沙拉、三明治、早餐、午餐等，根节点为菜品）：
- 传统平坦 CP：面对一张模糊的三明治图像，基础分类器给出分散概率，标准 CP 为满足 \(99\%\) 覆盖率，被迫输出 {奶酪三明治, 火腿三明治, 金枪鱼三明治, 煎蛋卷}，集合大小为 4，阅读冗长且缺乏焦点。
- HCC 流程：
1. 系统将各叶子概率向上求和，发现内部节点“三明治”获得了三个具体三明治叶子的累加概率（例如 \(0.45 + 0.30 + 0.15 = 0.90\)）。
2. 在评估各 NOL-cover 时，候选集 A 为全部叶节点（集合代价包含 4 个元素与对应惩罚）；候选集 B 包含了内部节点 {三明治, 煎蛋卷, ...}。
3. 内部节点“三明治”凭借 \(0.90\) 的高累加置信度一举跨过校准阈值，HCC 直接输出 {三明治, 煎蛋卷}。
4. 最终预测集大小由 4 骤降至 2，用抽象概念精准概括了分类器的不确定性来源，既避免了用户被海量细分标签淹没，又严格保障了真实三明治类别位于预测集的覆盖范围内。
损失函数 / 训练策略¶
分层保形分类为免训练的后处理校准范式，无需修改底层分类器权重。其优化与推理策略集中于校准和分位数计算： - 离线校准计算：在独立校准集 \(\mathcal{D}_c = \{(\mathbf{x}_i, y_i)\}_{i=1}^{n_c}\) 上，对离线筛选得到的每个合法 NOL-cover \(\mathcal{S} \in \mathcal{H}\)，依次计算各样本评分 \(s(\mathbf{x}_i, \mathbf{y}_i, \mathcal{S})\)，排序后以公式 \(\hat{q}_\mathcal{S} = \text{Quantile}(\{s_i\}, \lceil(n_c+1)(1-\alpha')\rceil/n_c)\) 确定对应的判定阈值。 - 在线推理选择：对测试样本 \(\mathbf{x}_t\)，经过动态剪枝确定活跃候选集族 \(\mathcal{H}_t \subseteq \mathcal{H}\)（大小为 \(m_t\)），设定校正后容错率 \(\alpha' = \alpha / m_t\)。计算每个活跃候选集的预测集 \(C_\mathcal{S}(\mathbf{x}_t) = \{v \in \mathcal{S} \mid \hat{g}(\mathbf{x}_t)_v \ge 1 - \hat{q}_\mathcal{S}\}\)，最终输出满足式 (3) 加权成本最小的 \(C^*(\mathbf{x}_t)\)。
实验关键数据¶
主实验¶
论文在涵盖文本（DBpedia14, 14 类/25 节点/深度 6/BERT）、图像（ImageNet1K, 1000 类/1860 节点/WordNet 深度 17/ResNet-152）及音频（GTZAN, 10 类/15 节点/深度 3/XGBoost）三大模态的基准上进行了全面评测（划分 80% 校准 / 20% 测试）。主实验结果对比了标准 CP（Standard CP）、最近公共祖先基线（LCA）及 HCC（本文方法）。
| 数据集 | 目标覆盖保证 \(1-\alpha\) | 权重 \(\beta\) | 方法 | 经验覆盖率 (Coverage ↑) | 加权目标总成本 (Costs ↓) | 预测集大小 (PS size ↓) | 覆盖叶节点数 (# covered leaves ↓) |
|---|---|---|---|---|---|---|---|
| DBpedia14 (dbp) | 0.9997 | 0.19 | Standard CP | 0.9998 ± 0.02 | 3.18 ± 2.62 | 2.67 ± 2.20 | 2.67 ± 2.20 |
| LCA | 0.9999 ± 0.01 | 2.20 ± 1.13 | 1.00 ± 0.00 | 6.32 ± 5.94 | |||
| HCC (本文) | 0.9999 ± 0.01 | 2.07 ± 1.00 | 1.25 ± 0.55 | 4.30 ± 4.65 | |||
| ImageNet1K (img) | 0.9800 | 0.04 | Standard CP | 0.9807 ± 0.14 | 11.49 ± 20.49 | 11.04 ± 19.70 | 11.04 ± 19.70 |
| LCA | 0.9951 ± 0.07 | 14.79 ± 15.63 | 1.00 ± 0.00 | 344.70 ± 390.64 | |||
| HCC (本文) | 0.9846 ± 0.12 | 8.09 ± 11.01 | 4.41 ± 6.54 | 92.12 ± 245.12 | |||
| GTZAN (gtz) | 0.9000 | 0.25 | Standard CP | 0.9613 ± 0.19 | 2.73 ± 0.97 | 1.19 ± 0.39 | 6.17 ± 4.14 |
| LCA | 0.9812 ± 0.14 | 2.86 ± 1.01 | 1.00 ± 0.00 | 7.45 ± 4.02 | |||
| HCC (本文) | 0.9637 ± 0.19 | 2.76 ± 0.98 | 1.11 ± 0.32 | 6.57 ± 4.24 |
注：粗体表示满足标称覆盖率约束下的最优指标。所有方法均以均值 ± 标准差报告。
消融实验与对比分析¶
为验证动态剪枝、多重比较校正及广义保形评分设计的必要性，论文报告了完整的模块消融实验，并在 ImageNet1K 上与基于整数规划的结构化保形预测（SCP, Zhang et al., 2025）进行了横向对比。此外，论文在 500 个真实样本上开展了涉及 4 位专业标注人员的用户偏好双盲测试。
消融实验与基线对比分析表：
| 数据集 | 配置 / 变体 | 覆盖率 (Coverage ↑) | 总成本 (Costs ↓) | 预测集大小 (PS size ↓) | 覆盖叶节点数 (# covered leaves ↓) | 核心机制说明 |
|---|---|---|---|---|---|---|
| img (\(\alpha=0.02\)) | HCC (完整模型) | 0.9846 ± 0.12 | 8.09 ± 11.01 | 4.41 ± 6.54 | 92.12 ± 245.12 | 完整架构，兼顾紧凑与特异性 |
| w/o 动态剪枝 | 0.9791 ± 0.14 | 15.90 ± 13.40 | 2.46 ± 1.94 | 336.04 ± 327.04 | 缺乏 LCA 剪枝，多重校正致叶膨胀 | |
| w/o 校正 (Bonferroni) | 0.9630 ± 0.19 | 4.51 ± 4.76 | 2.02 ± 1.59 | 62.17 ± 107.35 | 覆盖率崩溃 (破保 98%) | |
| w/o 分层保形分数 | 0.9497 ± 0.22 | 2.90 ± 3.43 | 2.57 ± 3.22 | 8.38 ± 25.92 | 改用 Recall 风险，覆盖率严重破保 | |
| img (\(\alpha=0.10\)) | Standard CP | 0.8982 | 1.82 | 1.75 | 1.75 | 平坦基线，缺乏高层概念概括 |
| LCA | 0.9494 | 5.58 | 1.00 | 114.59 | 过于抽象，包含过多无用叶节点 | |
| SCP (\(M=4\)) | 0.9262 | 2.78 | 1.64 | 21.27 | 整数规划求解，效率低且叶膨胀偏大 | |
| SCP (\(M=8\)) | 0.9188 | 2.50 | 2.13 | 10.54 | 强行限定集合规模，难以精细控制 | |
| HCC (本文) | 0.9036 | 1.63 | 1.49 | 3.57 | 综合指标全面优于 SCP 各设定 |
用户偏好研究统计表（4位标注员，500个样本）：
| 数据集 | 指标维度 | HCC 偏好占比 | Standard CP 偏好占比 | 无显著偏好 (No Preference) | 二项分布显著性检验 \(p\) 值 |
|---|---|---|---|---|---|
| DBpedia14 (dbp) | 样本标注分布 (# / %) | 523 (52.4%) | 401 (40.2%) | 74 (7.4%) | \(p = 3.4 \times 10^{-5}\) (偏好率 ~57%) |
| 多数票投票分布 (# / %) | 126 (50.4%) | 90 (36.0%) | 12 (4.8%) | Fleiss' \(\kappa = 0.47\) (中度一致) | |
| ImageNet1K (img) | 样本标注分布 (# / %) | 577 (57.9%) | 239 (24.0%) | 180 (18.1%) | \(p = 2.4 \times 10^{-33}\) (偏好率 ~71%) |
| 多数票投票分布 (# / %) | 126 (50.4%) | 35 (14.0%) | 46 (18.4%) | Fleiss' \(\kappa = 0.53\) (良好一致) |
关键发现¶
- 严格覆盖率的成立边界：消融实验揭示，若去掉多重检验校正（w/o correction），ImageNet 经验覆盖率直接从 98.46% 跌落至 96.30%，违反了标称的 98% 下界；而改用多标签召回率损失（w/o conformity）覆盖率进一步恶化至 94.97%。这证明了本文定制设计的广义保形评分函数对于维系有限样本理论保证的不可替代性。
- 动态剪枝的威力：去掉动态剪枝后，虽然集合大小表观上变小（2.46），但其覆盖的叶节点数剧增至 336.04，总优化成本翻倍（从 8.09 恶化到 15.90）。这表明动态剪枝成功避免了模型退化到过于空泛的高层根节点（如无意义的“实体”或“物体”）。
- 人类实际偏好与认知负荷：在用户研究中，HCC 在复杂视觉任务上获得了压倒性的偏好（71% 用户显著偏好，二项检验 \(p < 10^{-32}\)）。标注人员反馈，当遇到细粒度犬种或鸟类时，输出高层标签（如
{蜥蜴}）比输出一长串平坦的叶类别枚举（如{飞蜥, 变色龙, 绿蜥, 鞭尾蜥}）更容易被人类核实与采信。
亮点与洞察¶
- 将语义抽象程度纳入不确定性度量：传统保形预测仅将预测集合大小作为评估不确定性的唯一尺度，而忽视了类别的语义距离。HCC 首次将 DAG 层次拓扑直接内化为优化惩罚项，实现了“预测集长度”与“语义抽象粒度”之间的数学平滑插值。
- NOL-cover 理论剪枝构筑的数学优雅性：通过形式化证明“非完备叶覆盖必然破保”以及“包含祖先关系的集合必然次优”，HCC 将原本无法穷举的 \(2^{|\mathcal{V}|}\) 离散解空间严格压缩至互不相交的非重叠边界，无需借助昂贵的商用求解器即可实现轻量多项式搜索。
- 通用可插拔的后处理机制：HCC 完全独立于底层模型的训练过程与神经网络架构，仅依赖分类器的输出概率分布和类别分类 DAG，能够无缝嫁接到任何预训练的多模态、视觉或自然语言分类系统中。
局限与展望¶
- Bonferroni 校正的保守性倾向：在大型复杂分类体系中，即使经过动态剪枝，候选集数量依然可能导致校正后的 \(\alpha'\) 偏小。未来可探索将有序假设检验（如 Holm 逐步检验或基于依赖关系的图拓扑检验）引入分层保形推理中，进一步收紧置信区间。
- 严重不确定性下的过抽象现象：当输入样本极度模糊或存在多目标干扰时，模型可能会倾向于退化输出过于抽象的内部节点（例如 WordNet 中的 “artifact” 或 “object”）。此类预测虽然数学上覆盖正确，但实际信息增益极低，未来需探索自适应深度下界截断机制。
- 依赖预定义 DAG 的完备性：算法强依赖于高质量的先验类别层次结构。面对缺乏清晰本体论定义或存在环路关系的弱结构领域，如何自动诱导构建稳健的类别拓扑仍待深入探索。
相关工作与启发¶
- vs. 标准保形分类 (Standard CP, Angelopoulos et al., 2021): 标准 CP 仅在平坦叶节点上寻找阈值，遇到复杂混淆类别时集合急剧膨胀，缺乏结构概括能力；HCC 允许输出内部节点，在保持覆盖率的同时显著压缩有效集合大小。
- vs. 层次树风险控制 (Angelopoulos et al., 2024 / Mortier et al., 2025): 先前层次工作多数仅限定于严格树形拓扑（Tree），且往往以损失叶覆盖率或仅在顶层最可能预测的祖先链上做截断为代价；HCC 支持泛化 DAG 结构，并提供了严格的有限样本叶覆盖保证。
- vs. 结构化保形预测 (Structured Conformal Prediction, Zhang et al., 2025): SCP 采用学习-检验框架与整数规划（MILP），在大规模 WordNet 树上求解极慢且需要预设最大预测集容量 \(M\)；HCC 基于 NOL-cover 与动态 LCA 剪枝，无需求解复杂优化器，运行效率高且能显式调节特异性。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ (首次形式化解决基于通用 DAG 的分层保形预测集合优化问题，提出 NOL-cover 理论剪枝)
- 实验充分度: ⭐⭐⭐⭐⭐ (覆盖文本、图像、音频三大真实跨模态基准，包含详尽消融实验与大样本双盲用户偏好研究)
- 写作质量: ⭐⭐⭐⭐⭐ (数学定义严谨清晰，理论命题与证明完备，图文与动机呼应紧密)
- 价值: ⭐⭐⭐⭐⭐ (为高风险决策中的不确定性量化与人类可解释性交互提供了极具实用价值的理论工具)