层级共形分类

基本信息

一句话摘要

针对传统共形预测忽略类别层级结构而导致不确定性预测集冗长膨胀的缺陷，本文提出层级共形分类（HCC）框架，将类别有向无环图（DAG）先验转化为平衡预测集基数与特异性的受约束优化目标，通过严格证明“无重叠叶覆盖”（NOL-cover）将搜索空间指数级剪枝，在严格维持有限样本置信度覆盖保证的同时大幅压缩了预测集规模，并获得了人类用户的高度认知偏好。

研究对象

• 研究对象：层级共形分类（Hierarchical Conformal Classification, HCC）。在多分类任务中，类别标签不再是孤立平铺的离散集合，而是组织为一个已知的有向无环图（DAG）或分类体系 $\mathcal{T} = (\mathcal{V}, \prec)$（其中叶节点 $\mathcal{Y} \subseteq \mathcal{V}$ 为基分类器的具体分类标签，内部节点为高层语义概念，边 $\prec$ 代表严格的“父子”偏序关系）。
• 核心问题：标准共形预测（Conformal Prediction, CP）存在固有的结构性脱节：
  1. 平铺无结构缺陷（Flat & Unstructured Limitation）：标准 CP 将所有类别视作平权独立的个体，完全无视领域语义层级。当模型对具体亚型（例如埃及猫、虎斑猫、短毛猫）产生不确定性时，标准 CP 会输出一大串细粒度叶节点，造成认知过载；而人类专家更期望用一个紧凑的高层概念（如“家猫”）进行精准概括；
  2. 紧凑性（Compactness）与特异性（Specificity）的失衡：现有少数层级预测尝试要么单纯预测概率质量区域（无法保证有限样本覆盖率），要么退化为仅在最优叶节点的祖先链上机械爬升，无法自由组合不同深度的内部节点与叶节点；
  3. 组合爆炸的搜索复杂性：在包含成百上千个节点的 DAG 中，所有可能节点子集的搜索空间为 $2^{|\mathcal{V}|}$（在深度为 $d$ 的二叉树上高达 $2^{2^d}$），精确求解具有覆盖保证的最优预测子集在计算上是 NP-hard 的。
• 研究情境/范围：跨越三种异构数据模态与典型分类器架构——文本（DBpedia14 维基百科摘要 + BERT）、图像（ImageNet-1k + ResNet-152）以及音频（GTZAN 音乐流派 + XGBoost），并在覆盖率（Coverage）、总成本（Costs）、预测集标称大小（PS size）、覆盖叶节点数（# covered leaves）及人类用户主观盲测偏好度上展开系统性实证评估。

研究方法

方法概述

• 方法类型：不确定性集合预测、保形统计推断与受约束组合离散优化。
• 总体思路：
  1. 受约束优化建模：将层级共形分类形式化为一个目标优化问题——在满足“测试样本的真实叶标签以至少 $1-\alpha$ 的概率被预测集所管辖的叶覆盖所包含”的硬性统计约束下，最小化预测集的元素个数 $|N|$（提升可用性与紧凑性）加上惩罚项 $\beta \times$ 覆盖的叶节点总数（惩罚过度泛化、提升特异性）；
  2. 搜索空间结构化剪枝理论（NOL-cover）：从理论上证明最优解必须满足两大公理：(i) 叶覆盖完备性（必须覆盖全部叶标签，否则无法在任意 $\alpha$ 下保真）；(ii) 祖先后代独立性（不得同时包含具有包含关系的祖先后代节点，否则必能精简出更优解）。由此定义“无重叠叶覆盖”（Non-Overlapping Leaf Cover, NOL-cover），将搜索空间从天文数字 $2^{|\mathcal{V}|}$ 极度缩减至 $\sim 2^{d-1}$；
  3. 自底向上的分值与标签传播：对任意内部节点，其预测分值为后代叶节点 Softmax 分值之和，其实际标签为后代包含真实叶标签的指示变量（在 DAG 存在多重继承时转化为多标签场景）；
  4. 广义适形性打分（Conformity Score for DAGs）：设计兼顾多重继承的适形度打分函数 $s(x, y, S) = \hat{g}(x)_{v'}$，选取相关真实祖先中预测分最高者作为衡量准绳，严格证明其满足有限样本覆盖定理；
  5. 动态 LCA 剪枝与多重校正推断：推理时为每个候选 NOL-cover 对应的分类器应用 Bonferroni 校正 $\alpha' = \alpha/m$，并借助标准叶预测集的最长公共祖先（LCA）进行动态剪枝，剔除冗余的高层无效解，最终输出成本最低的最优预测集。
• 为什么用这种方法：相较于启发式规则，该方法具有无分布假设的严密数学理论托底；相较于整数线性规划，NOL-cover 结构剪枝使算法在深层大规模图谱上具备毫秒级推理能力；相较于单纯单节点回退，它允许在同一预测集中灵活并存“高确信度的叶节点”与“不确定子树的概括性父节点”。

方法分析

• 分析单位：输入样本 $x_t$、类别有向无环图 $\mathcal{T} = (\mathcal{V}, \prec)$ 及输出预测子集 $N \subseteq \mathcal{V}$。
• 关键变量/概念：
  • 叶覆盖算子 $\text{leaf-cov}_{\mathcal{T}}(N)$：集合 $N$ 中所有节点及其在树拓扑中所有后代叶节点的并集；
  • 权衡系数 $\beta \in \mathbb{R}^+$：控制预测集“物理元素个数”与“概念语义宽泛度（覆盖叶总数）”之间的张力；
  • 无重叠叶覆盖集 NOL-covers：同时满足全叶覆盖与祖先独立的极小子集；
  • 向上聚合分值 $\hat{g}(x)_v = \sum_{w \in \text{leaf-cov}(\{v\})} \hat{f}(x)_w$；
  • 多重检验校正容限 $\alpha' = \alpha / m$。
• 识别/推断逻辑：将复杂的“结构化标签选取”转化为“多个预标定共形分类器的并行推断与动态代价最小化筛选”。若基础模型对某一细分类别群（如猫科）高度混淆但能确定其上级门类，算法通过将叶集合并为单一内部节点，仅牺牲微小的 $\beta$ 惩罚即可大幅缩减集合基数 $|N|$，从而在帕累托前沿上达到最优代价。
• 具体步骤：
  1. 离线分析分类体系 DAG $\mathcal{T}$，枚举生成所有极小 NOL-cover 拓扑切面；
  2. 在标定集 $D_c$ 上计算各节点的聚合分值 $\hat{g}(x)$ 与传播标签，基于公式 (4) 计算各 NOL-cover 的共形分位数 $\hat{q}$；
  3. 在线接收测试样本 $x_t$ 与目标错误率 $\alpha$；
  4. 运行标准叶共形预测，计算其最低公共祖先（LCA）并动态剪除包含 LCA 祖先的无效 NOL-covers；
  5. 使用 Bonferroni 校正后的 $\alpha'$ 在剩余 NOL-cover 分类器上生成候选预测集；
  6. 评估公式 (3) 的目标成本函数，返回总代价最小的节点集合作为最终预测集。

核心公式与拆解

核心公式/指标 1：层级共形分类受约束优化目标（HCC Formulation）

构建平衡预测集基数紧凑性与语义特异性的数学规划：

$$h^*_{\beta, \mathcal{V}}(x_t, \alpha) = \arg\min_{N \subseteq \mathcal{V}} \left( |N| + \beta \left| \bigcup_{v \in N} \text{leaf-cov}_{\mathcal{T}}(\{v\}) \right| \right)$$ $$\text{subject to } \mathbb{P}\left( y_t \in \text{leaf-cov}_{\mathcal{T}}(N) \right) \ge 1 - \alpha$$

• 公式拆解 1：
  • 表示内容：在所有可能的节点子集 $N \subseteq \mathcal{V}$ 中，寻找一个使总代价最小的预测集。总代价由两部分组成：第一项 $|N|$ 为预测集包含的节点总数（越少越紧凑，对人类用户越友好）；第二项为这些节点所管辖的所有细粒度叶节点总数（乘以调节系数 $\beta$，防止模型无脑退化为包含海量叶节点的高层抽象节点）；约束条件硬性规定真实标签 $y_t$ 落在所选子集后代叶覆盖中的边际概率不低于 $1-\alpha$。
  • 关键符号：$N$ 为选取的预测节点集合；$\text{leaf-cov}_{\mathcal{T}}(N)$ 为 $N$ 的叶覆盖；$\beta$ 为特异性惩罚权重（$\beta$ 越大越偏好细粒度叶节点）；$\alpha$ 为允许的最大错误率。
  • 对应方法步骤：HCC 框架的核心决策准则，确立了不确定性集合预测的最优权衡曲面。

核心公式/指标 2：无重叠叶覆盖集充分必要性公理（NOL-cover Pruning Propositions）

用于将搜索空间从组合爆炸压缩至可计算集合：

$$\mathcal{S} \in \text{NOL-covers} \iff \begin{cases} \text{leaf-cov}_{\mathcal{T}}(\mathcal{S}) = \mathcal{Y} & \text{(Leaf Coverage)} \\ \forall u, v \in \mathcal{S}, u \neq v \implies \neg(u \prec\prec v) \land \neg(v \prec\prec u) & \text{(Ancestral Independence)} \end{cases}$$

• 公式拆解 2：
  • 表示内容：命题 1（Proposition 1）证明了任何可行解必须覆盖全部叶节点（否则存在至少一个叶节点无法满足任意 $\alpha$ 的统计覆盖要求）；命题 2（Proposition 2）证明了若解集中存在祖先-后代共存（如同时包含‘猫’与‘虎斑猫’），剔除冗余祖先后不仅覆盖不变，且代价绝对更低或相等。
  • 关键符号：$\prec\prec$ 为 DAG 偏序关系的传递闭包；$\mathcal{Y}$ 为全局叶类别全集。
  • 对应方法步骤：离线校准阶段的搜索空间剪枝，将深度为 $d$ 的二叉树候选假设空间从 $2^{2^d}$ 骤降为 $\sim 2^{d-1}$，使理论最优求解在工程上完全可控。

核心公式/指标 3：DAG 多标签广义适形性打分（Conformity Score for Hierarchical DAGs）

用于在图谱多重继承结构下确定样本与候选集的相符程度：

$$s(x_i, \mathbf{y}_i, \mathcal{S}) = \hat{g}(x_i)_{v'_i}, \quad v'_i := \arg\max_{j: y_{i,j} = 1} \hat{g}(x_i)_j$$

• 公式拆解 3：
  • 表示内容：对于给定的 NOL-cover 切面 $\mathcal{S}$，样本可能同时具有多个合法的祖先类（在 DAG 具备多个父节点时）。适形性打分取该样本所有真实祖先标签中由基模型聚合得分 $\hat{g}$ 最高的那一个作为其标定打分。
  • 关键符号：$\hat{g}(x_i)_j = \sum_{w \in \text{leaf-cov}(\{j\})} \hat{f}(x_i)_w$ 为节点 $j$ 的后代叶概率累加分；$\mathbf{y}_i \in \{0, 1\}^{|\mathcal{S}|}$ 为标签指示向量。
  • 对应方法步骤：定理 1（Theorem 1）的证明核心。该打分函数巧妙克服了 DAG 的多标签复杂性，将多标签覆盖数学化等价于单标签分位数选取，严格保证了 $\mathbb{P}(y_t \in \text{leaf-cov}(C(x_t))) \ge 1 - \alpha$。

核心公式/指标 4：动态 LCA 剪枝与 Bonferroni 多重校正（Dynamic Pruning via LCA）

用于解决推断阶段评估多个 NOL-cover 导致的假阳性泛滥与多重假设保守性：

$$\alpha' = \frac{\alpha}{m_{\text{pruned}}}, \quad m_{\text{pruned}} = \left| \{ \mathcal{S} \in \text{NOL-covers} \mid \text{Anc}(\text{LCA}(C_{\text{flat}}(x_t))) \cap \mathcal{S} = \emptyset \} \right|$$

• 公式拆解 4：

  • 表示内容：在推断时，先运行标准叶分类共形预测得到平铺集合 $C_{\text{flat}}(x_t)$，计算其最低公共祖先 $\text{LCA}$；若某个 NOL-cover 包含该 LCA 的更高级祖先，其概括粒度已过度泛化且必定在代价函数中劣于 LCA，故直接将其从候选库中剔除。最终 Bonferroni 校正分母由全局 $m$ 锐减为剪枝后的有效集合数 $m_{\text{pruned}}$。
  • 关键符号：$\text{LCA}$ 为最低公共祖先；$\alpha'$ 为校正后的严密显著性水平。
  • 对应方法步骤：在线推断优化步，显著缓解了经典 Bonferroni 校正因比较次数过多导致的极端保守与集合虚胖问题。

• 方法优势：

  1. 泛化至通用有向无环图（DAG），打破了先前工作仅局限于单继承树结构的重大瓶颈；
  2. 理论严谨：在有限样本下无条件满足真实的置信度覆盖保证（严格达到 $1-\alpha$）；
  3. 形式优雅：支持用户通过单一参数 $\beta$ 直观掌控“预测集元素数量”与“语义抽象深浅”的自由滑移。

• 方法局限：

  1. 当 DAG 拓扑极其复杂、节点数达到数十万量级时，极小 NOL-cover 的离线枚举仍可能面临图分割开销；
  2. Bonferroni 校正属于联合界的保守估计，在不同 NOL-cover 相关度极高时仍有进一步收窄置信区间的优化空间。

数据来源

• 数据类型：跨文本、图像、音频多模态的多分类基准测试集及配套权威本体/分类阶元 DAG。
• 样本来源：
  1. DBpedia14 (dbp)：文本模态，基于 Wikipedia 摘要文本，利用 DBpedia Ontology 构建深度为 6、包含 25 个节点的类别体系，基分类器为 BERT（精度 0.99）；
  2. ImageNet1K (img)：视觉模态，1000 类物体映射至深度为 17、包含 1860 个节点的 WordNet 词汇网层级树，基分类器为 ResNet-152（精度 0.79）；
  3. GTZAN (gtz)：音频模态，10 种音乐流派按 Sturm (2012) 分类树组织为深度为 3、包含 15 个节点的声学层次图，基分类器为 XGBoost（精度 0.63）。
• 时间范围：经典跨模态层级评估标准，数据采用固定 80/20 标定/测试集划分。
• 样本量/案例数：DBpedia14 样本量 56,000，ImageNet1K 抽样测试 10,000，GTZAN 样本量 1,000；并针对 500 个样本执行了 4 位标注员的人类双盲偏好打分。
• 数据局限：GTZAN 音频样本量较小；ImageNet 树深度极大（17层），导致深层路径多重检验校正较为严格。

研究结论

• 主要发现 1：HCC 在所有测试模态上均严格达成了预设的有限样本覆盖率要求（$1-\alpha$），并且相较于所有基线与消融设置，输出了全面最优或最具竞争力的总体成本（Costs）；在 ImageNet（img）复杂树上，HCC 的目标代价达到 8.09，显著低于标准 CP 的 11.49 与 LCA 单一回退的 14.79。
• 原文引用 1：

“We observe that the coverage requirement of 1−α is met for all baselines but not for all ablations, and that HCC produces solutions with the lowest (dbp, img) or comparable to the lowest cost (gtz)… In the column PS size, which denotes the average number of elements in the prediction set, HCC produces significantly smaller prediction sets on average for all data sets.” (Page 7)

• 主要发现 2：在预测集合的标称大小（PS size）方面，HCC 展现了极其显著的精简压缩能力；在 ImageNet 上，标准 CP 输出的预测集合平均包含高达 11.04 个混乱的叶节点标签，而 HCC 凭借高层概念自适应吸收，将预测集合元素个数大幅压缩至 4.41 个，极大改善了信息承载负荷。
• 原文引用 2：

“img (ImageNet1K): Standard CP produces PS size of 11.04 ± 19.70; LCA produces PS size of 1 ± 0.00 (covering 344.7 leaves); HCC (ours) produces PS size of 4.41 ± 6.54 covering 92.12 leaves.” (Page 6, Table 2)

• 主要发现 3：单一回退至最低公共祖先（LCA）虽然集合大小为 1，但其涵盖的细粒度叶节点数量会急剧失控爆炸（在 ImageNet 上 LCA 集合平均涵盖 344.7 个叶节点，在 DBpedia 上涵盖 6.32 个），造成毁灭性的语义稀释；而 HCC 成功将 ImageNet 叶覆盖稳定在 92.12 个，以适度合理的语义范畴保留了最大化的特异性。
• 原文引用 3：

“LCA forms a prediction set by returning the lowest common ancestor of a prediction set created by standard CP… nominally smaller prediction sets produced by HCC come at a moderate cost to the total number of covered leaves… Figure 5 shows how HCC allows a fine-grained control of the prediction set size against the number of covered leaves.” (Page 7)

• 主要发现 4：人类标注员盲测（User Study）从主观实用性层面强力印证了层级预测集的压倒性优势；在 500 个独立测试样本的二项检验中，标注员在 57%（文本 DBpedia）和 71%（图像 ImageNet）的样本中显著更偏好 HCC 的层级预测集而非标准 CP 的平铺叶列表。
• 原文引用 4：

“The results of a binomial test indicate a significant preference for HCC over standard CP in approximately 57% and 71% of cases, respectively, for dbp and img, highlighting HCC’s practical utility.” (Page 7)

我的判断

• 最有启发的点：
  1. 将人类认知负荷显式写入损失函数：过去的数学家做保形预测只关注数学覆盖率，导致给用户报出一份包含 50 个类别的密密麻麻清单；本文敏锐地意识到“集合里有几个词（$|N|$）”与“这些词代表了多少种可能性（后代叶数）”是两个正交维度，用受约束规划在二者之间找到了极具认知美感的黄金分割点；
  2. NOL-cover 剪枝的纯代数威力：从 $2^{|\mathcal{V}|}$ 到 $\sim 2^{d-1}$ 的降维证明极其漂亮，排除了互为祖先的冗余重叠节点，给大规模层级搜索树的剪枝优化提供了经典范式；
  3. 普适的跨模态包容力：无论是图像 ResNet、NLP BERT 还是音频树模型 XGBoost，无需对底层模型进行任何再训练或参数修改，纯后处理即可为任意黑盒模型套上严密的层级置信区间安全气囊。
• 可借鉴的方法：
  • 基于最长公共祖先（LCA）的动态候选剪枝（Dynamic Pruning）：在任何多假设检验或多模型并行后处理中，利用初始粗判结果的上界直接剔除更上层的冗余检验，大幅减少 Bonferroni 校正的测试惩罚。
• 可继续追问的问题：
  • 目前多重检验校正采用的是最为严厉保守的 Bonferroni 准则；如果引入依赖结构感知的按序测试（如 Holm 步进过程或加权因果图检验），能否在更紧凑的预测集下达成更高的有效覆盖度？
• 与我的研究关联：
  • 本文为“树模型知识图谱”在面对分类查询、层级概念归属推理与模型不确定性报告时，提供了一套数学严格、人类友好且跨模态兼容的置信集合输出机制。