Hierarchical Conformal Classification¶

会议: NeurIPS 2026
arXiv: 2508.13288
OpenReview: https://openreview.net/forum?id=k9Vms7prG3
代码: https://github.com/florisdenhengst/hierarchical-conformal-classification
领域: 学习理论
关键词: 符合预测、层次化分类、有向无环图、覆盖率保证、预测集剪枝

一句话总结¶

本文提出了层次化符合分类（HCC），将类别层次结构（DAG）融入符合预测的预测集构造与语义表达中，通过搜索无重叠叶覆盖子集并结合动态剪枝，在严格保证有限样本叶节点覆盖率的同时最小化集合大小与特异度代价。

研究背景与动机¶

符合预测（Conformal Prediction, CP）作为一种严格的非参数不确定性量化框架，能够在有限样本且无分布假设的条件下，为任意概率分类器输出具有预设覆盖率（例如 $1-\alpha$）的置信预测集合。然而，标准符合预测通常将类别标签视为平坦且孤立的符号集合，完全忽略了真实物理与语义世界中无处不在的层次化先验知识。在医疗诊断（如疾病本体）、电商产品树、欺诈分类乃至通用视觉识别（如 WordNet 组织的 ImageNet）中，类别天然以树形或有向无环图（DAG）的分类层级组织。当分类器面对高难度输入或模棱两可的细粒度类别时，标准 CP 往往被迫输出庞大散乱的叶节点集合，这不仅破坏了信息的可解释性，也使得人类决策者难以快速消化。

尽管近期部分工作尝试将标签层次融入预测集生成，但现有方案存在难以调和的结构与计算瓶颈。一类方法仅关注树形结构而无法处理更通用的多继承有向无环图，或者将目标退化为控制层级距离而非确保真实叶标签的严格覆盖；另一类引入学习后检验（Learn-Then-Test）框架的方法，则依赖高开销的整数规划求解，并在推理阶段强制限制预测集基数，导致难以根据语义特异度灵活伸缩，在大规模本体图上难以扩展。如何既保留底层分类器的有限样本覆盖保证，又能在通用的多继承 DAG 上灵活权衡预测集的紧凑性与语义特异度，构成了该领域的核心矛盾。

本文的切入视角是：若允许预测集跨越层级，用一个高层语义父节点去聚合替代一组相似的高不确定度子节点，即可大幅压缩集合视觉负担，同时不失真地兜底底层真实标签。核心 idea：将层次化预测集构建形式化为受覆盖率约束的紧凑性与特异度双目标优化问题，理论证明仅需在无重叠叶覆盖（NOL-cover）子空间内搜索即可保全最优解，并通过上推评分校准与推理期动态 LCA 剪枝实现高效求解。

方法详解¶

整体框架¶

层次化符合分类（HCC）旨在给定有向无环图 $\mathcal{T}=(\mathcal{V}, \prec)$ 及底层分类模型预测时，输出兼顾紧凑性与特异度的节点子集 $\mathcal{N} \subseteq \mathcal{V}$。其全流程分为校准阶段与推理阶段：在校准阶段，算法首先在 DAG 上递归提取所有不包含祖先-后代重叠且完整覆盖所有叶节点的无重叠叶覆盖（NOL-cover），随后将分类器预测概率与真实样本标签自底向上沿层级传播聚合，为每个候选 NOL-cover 校准对应的符合分类器；在推理阶段，面对测试样本的自底向上聚合得分，系统通过最近公共祖先（LCA）驱动的动态剪枝剔除冗余候选，在经 Bonferroni 纠正的显著水平下并行产出候选预测集，并选取使得紧凑性与叶覆盖特异度联合成本最小的最优解。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据与类别分类图 (DAG)"] --> B["1. 无重叠叶覆盖剪枝 (NOL-cover)"]
    B --> C["2. 概率得分与标签自底向上多标签传播"]
    C --> D["3. 广义多标签符合分位数校准"]
    D --> E["4. 推理阶段动态 LCA 剪枝与多重检验校正"]
    E --> F["输出最优层次化预测集合"]

关键设计¶

1. 无重叠叶覆盖剪枝：压缩组合搜索空间并保留全局最优性

若直接在全部节点子集空间 $2^{|\mathcal{V}|}$ 中寻找使得目标最小化的预测集，即使对于小规模图也会遭遇严重的组合爆炸。HCC 提出将候选空间严格限定于无重叠叶覆盖集合（Non-Overlapping Leaf Cover, NOL-cover）。一个节点子集 $\mathcal{S} \subseteq \mathcal{V}$ 被定义为 NOL-cover，当且仅当其满足两大条件：其一为叶覆盖性（$\text{leaf-cov}_{\mathcal{T}}(\mathcal{S}) = \mathcal{Y}$），即所有叶节点必须被 $\mathcal{S}$ 中的节点及其后代完全覆盖；其二为祖先独立性（$\forall u, v \in \mathcal{S}, u \neq v \implies \neg(u \prec\prec v) \land \neg(v \prec\prec u)$），即集合内任意两个节点不得存在祖先-后裔从属关系。论文给出了严格的理论论证：任何违背叶覆盖性的解必定会导致特定叶标签的边际覆盖率崩溃（命题 1）；而对于任何包含祖先后代依赖的冗余可行解，剔除冗余祖先后均可在不破坏覆盖率的前提下单调减少预测集大小与叶覆盖数量，获得成本更优或相等的合法 NOL-cover（命题 2）。对于深度为 $d$ 的满二叉树，候选假设空间从 $2^{2^d}$ 骤降至主导项为 $2^{d-1}$，使离线离散搜索具备可计算性。

2. 概率得分与标签自底向上多标签传播：赋能高层语义节点置信推断

基础黑盒分类器 $\hat{f}(\mathbf{x})$ 仅在底层叶节点 $\mathcal{Y}$ 输出预测概率，而高层抽象节点没有直接的监督打分。为支持任意内部节点上的不确定度量化，HCC 定义了自底向上的得分传播机制：对于任意图节点 $v \in \mathcal{V}$，其聚合预测得分 $\hat{g}(\mathbf{x})_v$ 严格定义为其所支配的所有叶节点预测概率之和： $$\hat{g}(\mathbf{x})_v := \sum_{w \in \text{leaf-cov}_{\mathcal{T}}(\{v\})} \hat{f}(\mathbf{x})_w$$ 与此对应，样本的层次化真实标签集合 $\mathcal{Y}'_i$ 包含该样本真实叶类别 $y_i$ 的全部祖先节点。在树形结构中，每个 NOL-cover 恰好仅包含一个真实标签；但在允许多继承的有向无环图中，同一个叶节点的多个上游祖先可能同时出现在同一个 NOL-cover 内，形成天然的多标签分类问题。为此，HCC 将每个候选 NOL-cover 视作一个多标签预测切片，通过布尔指示向量 $\mathbf{y}_i \in \{0, 1\}^{|\mathcal{S}|}$ 记录各节点是否覆盖真实叶节点，从而消除了图拓扑结构对高层校准的阻碍。

3. 广义多标签符合分位数校准：达成确界层次化覆盖保证

在多标签 DAG 拓扑下，若要求集合覆盖所有有效祖先，会导致预测集迅速膨胀并失去实用价值。HCC 抓住核心事实：为了确保真实叶节点被捕捉，只要预测集中包含该叶节点的至少一个祖先或该叶节点自身即可。基于该洞察，HCC 扩展了最小模糊度符合预测理论，为每个 NOL-cover $\mathcal{S}$ 设计了极值符合得分函数： $$s(\mathbf{x}_i, \mathbf{y}_i, \mathcal{S}) = \hat{g}(\mathbf{x}_i)_{v'_i}, \quad \text{其中 } v'_i := \arg\max_{j:\mathbf{y}_{i,j}=1} \hat{g}(\mathbf{x}_i)_j$$ 即在候选集合 $\mathcal{S}$ 中，仅选取属于真实标签祖先且被模型赋予最高置信度得分的那个节点 $v'_i$ 来计算符合性分数。在校准集 $\mathcal{D}_c$ 上计算经验分位数 $\hat{q} = \lceil(n_c + 1)(1 - \alpha)\rceil / n_c$ 后，测试样本的候选预测集定义为所有得分不低于临界门槛的节点：$C(\mathbf{x}_t) := \{v \in \mathcal{S} \mid \hat{g}(\mathbf{x}_t)_v \ge 1 - \hat{q}\}$。定理 1 在交换性假设下证明了：由该评分机制导出的预测集合，其叶节点覆盖概率严格满足 $\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 引入了依赖于测试样本的动态剪枝策略：首先由叶节点层级的基础 CP 产生一个初步预测集，并提取该集合在 DAG 中的最近公共祖先（Lowest Common Ancestor, LCA）；随后，算法在测试期动态剪除所有包含该 LCA 之严格祖先的 NOL-cover，并将包含该 LCA 的解视作等价类进行压缩合并。在此基础上，对保留的精简候选子集应用 Bonferroni 校正，各自分别推断出满足覆盖率保证的局部集合，最终显式求解目标函数以选出综合成本最小的最优解： $$h^*_{\beta, \mathcal{V}}(\mathbf{x}_t, \alpha) = \arg\min_{\mathcal{N} \in \mathcal{C}_{\text{pruned}}} |\mathcal{N}| + \beta \left| \bigcup_{v \in \mathcal{N}} \text{leaf-cov}_{\mathcal{T}}(\{v\}) \right|$$ 式中超参数 $\beta > 0$ 显式平衡预测集离散元素个数 $|\mathcal{N}|$（紧凑性）与所覆盖的叶节点基数（特异度），赋予了系统在抽象概括与精细定位之间的弹性调谐能力。

损失函数 / 训练策略¶

HCC 作为免重训的后处理（Post-hoc）外挂框架，完全冻结底层分类器权重。其优化与超参数设定策略如下： 1. 显著性水平设定：$\alpha$ 根据分类任务的基础难度反比例确定（例如在准确率 $99\%$ 的 DBpedia 上设为 $1-\alpha=0.9997$；在准确率 $79\%$ 的 ImageNet1K 上设为 $1-\alpha=0.98$；在准确率 $63\%$ 的 GTZAN 上设为 $1-\alpha=0.90$）。 2. 权衡系数 $\beta$ 校准：论文通过 DAG 内部非叶节点所涵盖叶节点数的中位数倒数进行无监督自适应确定： $$\beta := \left( \text{median}\left[ \{ |\text{leaf-cov}_{\mathcal{T}}(\{v\})| \mid v \notin \text{leaves}(\mathcal{T}) \} \right]_{v \in \mathcal{V}} \right)^{-1}$$ 该设定消除了昂贵的交叉验证调参开销，在文本任务中设为 $0.19$，在 ImageNet1K 中设为 $0.04$，在音频任务中设为 $0.25$。

实验关键数据¶

主实验¶

实验在文本（DBpedia-14，BERT）、图像（ImageNet-1K，ResNet-152）及音频（GTZAN，XGBoost）三大跨模态公开基准上进行，采用统一的 80/20 校准/测试划分。评估对比了标准符合预测（Standard CP，仅在叶节点预测）、最近公共祖先基线（LCA，返回标准 CP 预测集的最近公共祖先单一节点）以及本文 HCC 方法。

数据集	保证置信度 $1-\alpha$	评估方法	实际覆盖率 (Coverage $\uparrow$)	综合代价 (Costs $\downarrow$)	预测集大小 (PS size $\downarrow$)	覆盖叶节点数 (# Leaves $\downarrow$)
dbp (文本, 14类)	0.9997	Standard CP	0.9998 ± 0.02	3.18 ± 2.62	2.67 ± 2.20	2.67 ± 2.20
	0.9997	LCA Baseline	0.9999 ± 0.01	2.20 ± 1.13	1.00 ± 0.00	6.32 ± 5.94
	0.9997	HCC (本文)	0.9999 ± 0.01	2.07 ± 1.00	1.25 ± 0.55	4.30 ± 4.65
img (图像, 1000类)	0.9800	Standard CP	0.9807 ± 0.14	11.49 ± 20.49	11.04 ± 19.70	11.04 ± 19.70
	0.9800	LCA Baseline	0.9951 ± 0.07	14.79 ± 15.63	1.00 ± 0.00	344.70 ± 390.64
	0.9800	HCC (本文)	0.9846 ± 0.12	8.09 ± 11.01	4.41 ± 6.54	92.12 ± 245.12
gtz (音频, 10类)	0.9000	Standard CP	0.9613 ± 0.19	2.73 ± 0.97	1.19 ± 0.39	6.17 ± 4.14
	0.9000	LCA Baseline	0.9812 ± 0.14	2.86 ± 1.01	1.00 ± 0.00	7.45 ± 4.02
	0.9000	HCC (本文)	0.9637 ± 0.19	2.76 ± 0.98	1.11 ± 0.32	6.57 ± 4.24

消融实验¶

为了验证动态剪枝（Dynamic Pruning）、多重检验纠正（Bonferroni Correction）与多标签最大聚合符合得分（Conformity Formulation）的必要性，论文在三大数据集上进行了逐项消融分析。

数据集	消融变体配置	实际覆盖率 (Coverage $\ge 1-\alpha$)	综合代价 (Costs $\downarrow$)	预测集大小 (PS size $\downarrow$)	覆盖叶节点数 (# Leaves $\downarrow$)	结论与机制分析
dbp	HCC (完整模型)	0.9999 ± 0.01 (达标)	2.07 ± 1.00	1.25 ± 0.55	4.30 ± 4.65	综合代价值最低，兼顾紧凑性与语义特异度
	w/o 动态剪枝	0.9999 ± 0.01 (达标)	2.40 ± 1.08	1.22 ± 0.47	6.18 ± 5.61	缺乏测试期剪枝导致检验集合庞大，叶覆盖范围扩大 $43.7\%$
	w/o 多重检验校正	0.9997 ± 0.02 (达标)	1.88 ± 0.85	1.22 ± 0.43	3.44 ± 3.69	虽然代价表面降低，但在高难度数据上存在欠覆盖风险
	w/o 极值符合得分	0.9999 ± 0.01 (达标)	2.11 ± 1.05	1.29 ± 0.63	4.36 ± 4.71	改用多标签风险控制的召回损失后代价略有上升
img	HCC (完整模型)	0.9846 ± 0.12 (达标)	8.09 ± 11.01	4.41 ± 6.54	92.12 ± 245.12	综合代价较 Standard CP 下降 $29.6\%$，预测集压缩 $60.1\%$
	w/o 动态剪枝	0.9791 ± 0.14 (⚠️未达标)	15.90 ± 13.40	2.46 ± 1.94	336.04 ± 327.04	静态全集校正极度保守，退化严重且覆盖率轻微失真
	w/o 多重检验校正	0.9630 ± 0.19 (❌严重未达标)	4.51 ± 4.76	2.02 ± 1.59	62.17 ± 107.35	失去 Bonferroni 控制导致真实覆盖率跌破目标 $0.98$
	w/o 极值符合得分	0.9497 ± 0.22 (❌严重未达标)	2.90 ± 3.43	2.57 ± 3.22	8.38 ± 25.92	替代符合损失无法在深层 DAG 维持有效的统计置信界
gtz	HCC (完整模型)	0.9637 ± 0.19 (达标)	2.76 ± 0.98	1.11 ± 0.32	6.57 ± 4.24	音频小图上达到平衡，满足统计确界
	w/o 动态剪枝	1.0000 ± 0.00 (达标)	3.41 ± 0.35	1.07 ± 0.26	9.35 ± 2.11	覆盖率过于饱和（100%），过度抽象导致叶节点数扩大 $42.3\%$
	w/o 多重检验校正	0.9275 ± 0.26 (达标)	2.47 ± 0.94	1.33 ± 0.47	4.56 ± 3.75	虽达标但缺少统计理论支撑，方差增大
	w/o 极值符合得分	0.9575 ± 0.20 (达标)	2.67 ± 0.97	1.18 ± 0.38	5.97 ± 4.22	在简单 3 层分类图上表现稳定

关键发现¶

显著压缩预测集合大小：在具 1000 个类别的深度 WordNet 分类层级（ImageNet-1K）上，标准符合预测在 $1-\alpha=0.98$ 的严苛置信度下平均产生 $11.04$ 个散碎的叶类别；而 HCC 巧妙将相似类别收拢至高层语义概念，将预测集大小压缩至 $4.41$（降幅达 $60.1\%$），使得人类仅需阅读不到一半的候选词条。
避免最近公共祖先（LCA）的过度抽象陷阱：基线 LCA 虽能将预测集大小强行固定为 $1.00$，但对于异质性候选集，其极易退化到本体树顶层过于宽泛的概念（在 ImageNet1K 上平均涵盖多达 $344.70$ 个叶类别，退化为如 "object"、"artifact" 等无实质信息的祖先）。HCC 通过参数 $\beta$ 约束，在 ImageNet 上仅涵盖 $92.12$ 个叶类别，在特异度与概括力间保持了健康均衡。
消融印证理论严格性：消融表明，在复杂结构（如 ImageNet1K）下，去除多重检验纠正或极值符合得分都会直接导致实际覆盖率（$96.30\%$ 与 $94.97\%$）大幅跌破理论下界 $98\%$；而动态剪枝则成功化解了静态全集 Bonferroni 校正导致的过度保守化问题。
真实用户偏好显著：在 4 位标注员针对 500 个样本的双盲用户调研中，二项式检验表明人类在 DBpedia 和 ImageNet 上分别有 $57\%$ 和 $71\%$ 的案例显著更偏好层次化预测集（$p$ 值达 $3.4 \times 10^{-5}$ 和 $2.4 \times 10^{-33}$）。

亮点与洞察¶

NOL-cover 理论剪枝证明：巧妙利用概率测度的单调性与子集剔除的代价单调性，从理论上证明了全局最优受限预测集必定落在无重叠且全覆盖的 NOL-cover 切片中，将指数级爆炸搜索空间规约至可计算阶次。
多标签极大池化符合得分：针对 DAG 多继承导致的潜在多祖先问题，定义了只取最可信预测得分的指标函数，以最简形式完美嫁接了经典符合预测理论与层次化多标签结构，保证了严格的有限样本覆盖界。
动态 LCA 剪枝兼顾严谨与紧凑：将测试样本特异的预测子集转化为动态假设检验修剪条件，成功规避了全集 Bonferroni 校正带来的过分保守性惩罚。

局限与展望¶

Bonferroni 纠正仍具保守性：当前多重检验校正采用 Bonferroni 联合界，当拓扑较深且候选 NOL-cover 较多时，校正后的显著性水平 $\alpha'$ 仍相对偏小。未来若结合序列假设检验或根据各校准预测器的先验期望成本进行序贯过滤（如 Holm 步进式检验），有望进一步减小预测集开销。
超深超宽 DAG 的候选爆炸：对于数万节点规模的大型本体图，完全枚举 NOL-cover 仍可能面临长耗时问题。尽管作者提供了按层（level-by-level）划分的深度近似策略，但自适应局部拓扑构建仍需深入探索。
多目标图像的单标签假设局限：在自然图像中如果单张图片存在多个不同主体，单标签分类器输出分布分散，HCC 倾向于选择极端抽象的祖先节点（如 "whole" 或 "artifact"）。未来可拓展至具有多实例多标签真值的多重层次预测场景。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次形式化基于 DAG 层次的受约束优化符合分类，并证明 NOL-cover 搜索空间的完备性与最优性。
实验充分度: ⭐⭐⭐⭐☆ 涵盖文本、图像、音频三大多模态基准及严谨消融实验，配合具有统计显著性的用户主观评测。
写作质量: ⭐⭐⭐⭐⭐ 理论证明完备，符号定义严谨，方法逻辑与推导链条清晰流畅。
价值: ⭐⭐⭐⭐⭐ 为具有层级本体的高风险安全决策领域（如医疗诊断、金融风控）提供了理论保真且用户友好的不确定性量化利器。