表征复杂度约束下的层级分类共形预测

基本信息

一句话摘要

针对传统层级分类仅允许预测单一内部节点导致跨分支混淆时集合失控膨胀、以及平铺分类集合缺乏语义结构的双重难题，本文将表征复杂度（Representation Complexity）约束引入分裂共形预测框架，提出单节点回退（CRSVP, $r=1$）与基于动态规划的多节点子树联合搜索（CRSVP-r, $r>1$）两种高效推断算法，在严格提供有限样本边际覆盖保证的同时实现了极具语义解释性且高度紧凑的集合值预测。

研究对象

• 研究对象：层级多分类设置下的集合值预测（Set-Valued Prediction in Hierarchical Multi-Class Classification）。在给定领域专家构建的分类阶元树结构 $\mathcal{T} = (\mathcal{V}_{\mathcal{T}}, \mathcal{E})$ 中（其中根节点 $v_1$ 代表全体类别空间 $\mathcal{Y}$，叶节点代表各个具体分类标签），针对测试样本构建包含真实标签的置信类别子集 $\hat{Y} \subseteq \mathcal{Y}$。
• 核心问题：现有集合预测在面对层级结构时陷入非此即彼的极端两难困境：
  1. 单一内部节点限制的过度泛化（Overly Restrictive $r=1$）：经典层级分类强制要求预测集必须严格对应树上的某单个内部节点（$\hat{Y} \in \mathcal{V}_{\mathcal{T}}$）。一旦分类器对属于树上不同深层分支的类别产生细微混淆（例如在百脉根与毛茛之间摇摆），能够同时覆盖二者的唯一单节点往往只能被迫退化到树的极高层甚至根节点（如 PlantCLEF 数据集中直接输出“植物界 1000 个物种”），导致预测集巨大而彻底丧失信息量；
  2. 无约束平铺分类的语义破碎（Unrestricted Flat Setting）：传统平铺共形预测（如 APS、LAC）允许输出任意离散叶类别子集，虽然集合尺寸较小，但其包含的类别在树拓扑上四分五裂，缺乏统一的高阶概念语义支撑，给人类专家的下游排查造成严重的认知碎片化；
  3. 有限样本边际覆盖率的严密统计保证：必须保证预测集在无任何数据分布假设的前提下，以严格不低于 $1-\alpha$ 的置信概率捕获真实类别，并杜绝离散概率跳跃引起的“虚假过覆盖”。
• 研究情境/范围：涵盖计算机视觉（CIFAR-10、Caltech-101、Caltech-256、包含 1000 种欧陆野生植物长尾数据的 PlantCLEF 2015）、小鼠大脑单细胞转录组（Allen Mouse Brain, AMB）以及维基百科文本分类（DBpedia219）等六大跨模态真实数据集，在 $90\%$ 名义置信水平下全面对比经验覆盖率（Coverage）、集合平均尺寸（Size）与表征复杂度（Representation Complexity, R.C.）。

研究方法

方法概述

• 方法类型：共形统计推断、受约束组合离散优化与树结构动态规划。
• 总体思路：
  1. 表征复杂度数学公理化（Representation Complexity $R_{\mathcal{T}}(\hat{Y})$）：定义表征一个类别子集 $\hat{Y}$ 在树 $\mathcal{T}$ 中所需的最少互斥不相交树节点数。当 $r=1$ 时退化为传统单节点内部推断；当 $r=K$ 时退化为平铺无约束推断；通过约束 $R_{\mathcal{T}}(\hat{Y}) \le r$（例如 $r=2, 3$），实现语义可解释性与紧凑度的连续可调；
  2. 嵌套预测集连续化随机保形机制：针对树结构上父子节点概率跳跃带来的阶跃离散性，在适形打分中引入服从标准均匀分布的随机项 $u \sim \mathcal{U}(0, 1)$，严格构建单调嵌套预测集序列，并利用留出标定集的分位数 $\tau^*$ 锁定统计保证；
  3. 算法一：限制性层级共形预测（CRSVP, $r=1$）：从后验概率最高的叶节点出发，沿父节点祖先链单调向上回退，其测试期时间复杂度仅为极低的 $O(\log K)$；
  4. 算法二：广义表征复杂度层级共形预测（CRSVP-r, $r>1$）：将问题形式化为按 Top-$k$ 类别序列逐步扩展的“极小公共祖先集合搜索”；在每次迭代中求解使子树基数与概率差值最小的优化问题；
  5. 自底向上的整数拆分动态规划求解器（Algorithm 5）：将复杂度 $r$ 递归拆分为分配给各个子树的非负整数分拆（Compositions），在每个内部节点自底向上缓存局部最优解，将原本指数级的子集枚举复杂度压缩至 $O(K 2^{rd})$（其中 $d$ 为树的最大出度），使 $r \le 3$ 时的推断速度达到实用级毫秒响应。
• 为什么用这种方法：相较于平铺方法，它用最多 $r$ 个概念高度概括了预测结果；相较于单节点回退，它允许在树的不同子分支上各自保留一个紧凑祖先，避免了因单个长尾异类而直接“炸到根节点”的悲剧；动态规划避免了重复子问题计算，兼顾了数学严格性与计算高效性。

方法分析

• 分析单位：输入特征 $x_i$、多分类阶元树 $\mathcal{T} = (\mathcal{V}_{\mathcal{T}}, \mathcal{E})$ 以及在表征复杂度界限 $r$ 内选取的预测节点集合 $\hat{V} \subset \mathcal{V}_{\mathcal{T}}$。
• 关键变量/概念：
  • 互斥不相交节点子集簇 $\mathcal{S}_{\mathcal{T}}(\hat{Y})$ 与表征复杂度 $R_{\mathcal{T}}(\hat{Y}) = \min_{\hat{V} \in \mathcal{S}_{\mathcal{T}}(\hat{Y})} |\hat{V}|$；
  • 祖先路径 $\text{Path}(v)$ 与父节点操作符 $\text{pa}(v)$；
  • 连续化均匀扰动变量 $u \sim \mathcal{U}(0, 1)$；
  • 标定分位数阈值 $\tau^* = \text{Quantile}(\lceil (1-\alpha)(N+1) \rceil)$；
  • 局部表征复杂度拆分组合 $\mathcal{M} = \text{Compositions}(r_i, |T|)$。
• 识别/推断逻辑：将分类器在叶节点输出的条件概率 $P(c|x)$ 视为基底证据。算法沿着 Top-$k$ 概率排序的类别累积扩展，当发现高概率类别分布在彼此相距较远的子树时，算法自动分化出 $r$ 个局部子树节点进行并行承接，而非退化至二者的遥远公共祖先。
• 具体步骤：
  1. 基础模型输出样本在叶节点的概率分布 $\hat{P}(c|x)$ 并按降序排序；
  2. 在标定集上针对每个样本，根据算法 1 或算法 3 计算使其命中真实标签的最小阈值 $\tau_i$；
  3. 取 $\tau_i$ 的对应阶数分位数作为测试期全局判定阈值 $\tau^*$；
  4. 测试阶段逐级扩充候选子集，运行动态规划算法 5 动态更新最优祖先覆盖；
  5. 判定累积连续化概率是否越过 $\tau^*$，触发截断并返回最终包含最多 $r$ 个树节点的语义集合。

核心公式与拆解

核心公式/指标 1：表征复杂度形式化公理（Representation Complexity）

数学化定义任意类别子集在给定树拓扑上的语义表达简洁度：

$$\mathcal{S}_{\mathcal{T}}(\hat{Y}) = \left\{ \hat{V} \subset \mathcal{V}_{\mathcal{T}} : \bigcup_{v_i \in \hat{V}} v_i = \hat{Y} \land \bigcap_{v_i \in \hat{V}} v_i = \emptyset \right\}$$ $$R_{\mathcal{T}}(\hat{Y}) = \min_{\hat{V} \in \mathcal{S}_{\mathcal{T}}(\hat{Y})} |\hat{V}|$$

• 公式拆解 1：
  • 表示内容：$\mathcal{S}_{\mathcal{T}}(\hat{Y})$ 为所有能够通过节点并集且彼此互不相交（无冗余重叠）的方式精确还原集合 $\hat{Y}$ 的树节点组合；表征复杂度 $R_{\mathcal{T}}(\hat{Y})$ 为其中包含节点数量最少的那组解的基数。
  • 关键符号：$\mathcal{V}_{\mathcal{T}}$ 为树结构中的全部节点集合（含内部与叶）；$\hat{Y} \subseteq \mathcal{Y}$ 为具体的预测类别子集；$|\hat{V}|$ 为所选代表节点的个数。
  • 对应方法步骤：度量复杂度的基石。若集合由单一节点（如‘哺乳纲’）完全涵盖，则复杂度为 1；若包含两个互斥分支的概念（如‘食肉目’与‘食草目’），则复杂度为 2；平铺无结构预测集的复杂度往往与叶标签数相同（数十至数百）。

核心公式/指标 2：随机化嵌套预测集判定准则（Nested Predictor with Continuous Randomization）

消除离散父子节点概率跃变引起的过覆盖问题：

$$\hat{Y}_1(x, u, \tau) = \arg\max_{\hat{Y} \in \text{Path}(\hat{y}(x))} \left\{ |\hat{Y}| : \hat{P}(\hat{Y}|x) + u \cdot \hat{P}(\text{pa}(\hat{Y}) \setminus \hat{Y} | x) \le \tau \right\}$$

• 公式拆解 2：
  • 表示内容：从概率最大的叶节点 $\hat{y}(x)$ 出发沿祖先路径向上回退；在判定当前节点是否纳入阈值时，除了计入当前节点自身的概率质量 $\hat{P}(\hat{Y}|x)$ 外，还引入了从其父节点跳跃增量中按均匀变量 $u$ 抽样的连续微扰。
  • 关键符号：$u \sim \mathcal{U}(0, 1)$ 为随机抽样因子；$\text{pa}(\hat{Y}) \setminus \hat{Y}$ 为从子节点晋升到父节点时骤然增加的概率差值；$\tau$ 为共形判定门限。
  • 对应方法步骤：CRSVP（$r=1$）的核心推断公式。定理 2.1 证明，引入该平滑随机项后，离散的树累积分布转化为严格连续分布，从而使得有限样本下的经验覆盖率能够精准无偏地命中理论 $1-\alpha$，杜绝了保守过拟合。

核心公式/指标 3：广义表征复杂度受约束优化序列（CRSVP-r Optimization Problem）

按概率排序逐步求解包含最多 $r$ 个不相交祖先的极小最优子集：

$$A_r(S_k; x) = \arg\min_{\hat{Y} \in 2^{\mathcal{Y}} : R_{\mathcal{T}}(\hat{Y}) \le r, \, A_r(S_{k-1}; x) \cup \{y^{(k)}\} \subseteq \hat{Y}} \left( |\hat{Y}| - \hat{P}(\hat{Y}|x) \right)$$

• 公式拆解 3：
  • 表示内容：在纳入第 $k$ 个高概率类别 $y^{(k)}$ 时，寻找一个合法的树节点并集 $\hat{Y}$，其表征复杂度不超过预设上限 $r$（$R_{\mathcal{T}}(\hat{Y}) \le r$），且严格包含前一步的解与新类别（保证嵌套单调性）；优化目标采用字典序：优先最小化所覆盖的叶节点绝对数量 $|\hat{Y}|$，在叶数量相同时最大化其累积概率 $\hat{P}(\hat{Y}|x)$。
  • 关键符号：$S_k = \{y^{(1)}, \dots, y^{(k)}\}$ 为按预测分值降序排列的 Top-$k$ 类别集合；$A_r(S_k; x)$ 为求得的极小公共祖先节点集。
  • 对应方法步骤：CRSVP-r 算法中逐级生成嵌套候选集的核心迭代，直接决定了多节点推断的紧凑性。

核心公式/指标 4：自底向上整数拆分动态规划递推（Tree DP via Integer Compositions）

算法 5 在内部节点上的状态转移方程：

$$s_{r_i}(v) = \arg\min_{(i_0, \dots, i_{|T|-1}) \in \text{Comp}(r_i, |T|)} \left| \bigcup_{j=0}^{|T|-1} s_{i_j}(T[j]) \right| - \hat{P}\left( \bigcup_{j=0}^{|T|-1} s_{i_j}(T[j]) \,\middle|\, x \right)$$

• 公式拆解 4：

  • 表示内容：对于当前内部节点 $v$，若分配给它的局部表征复杂度配额为 $r_i$，算法考察将其整数分拆为 $|T|$ 个子树配额 $(i_0, \dots, i_{|T|-1})$ 的所有组合方式（满足 $\sum i_j = r_i$）；直接调用其子节点已经预先计算好的局部最优解 $s_{i_j}(T[j])$ 进行并集组合，选取综合代价最小的组合作为节点 $v$ 在配额 $r_i$ 下的最优表征。
  • 关键符号：$T$ 为节点 $v$ 包含目标候选类别的非空子节点集合；$\text{Comp}(r_i, |T|)$ 为整数 $r_i$ 拆分为 $|T|$ 个非负整数的分拆全集。
  • 对应方法步骤：算法 5 的核心剪枝递推，彻底消除了全局指数搜索，保证在 $r \le 3$ 时算法以极高吞吐运行。

• 方法优势：

  1. 泛化能力强：无缝架起了单节点树回退与平铺离散集合预测之间的桥梁，支持用户根据实际场景通过调整整数 $r$ 定制解释颗粒度；
  2. 统计严密：引入连续化随机项保证了严格无偏的有限样本边际有效性（经验覆盖率精确稳定在 0.900）；
  3. 算法高效：利用整数拆分树形动态规划，以多项式时间求解了复杂的子树划分组合难题。

• 方法局限：

  1. 动态规划的理论最坏复杂度随树的最大分叉度 $d$ 和设定复杂度 $r$ 呈指数增长，若用户设定 $r \ge 5$ 且树非常扁平时，整数拆分枚举将面临计算压力；
  2. 当前算法依赖预先给定的单父节点树拓扑，未推广至具备环路或交叉图结构的 DAG 本体。

数据来源

• 数据类型：跨领域多分类基准数据集（包含计算机视觉、生物单细胞基因转录、百科文本）及其配套的真实层级分类树。
• 样本来源：
  1. CIFAR-10（10类，图像，深度3）；
  2. Caltech-101（97类，图像，深度3）；
  3. Caltech-256（256类，图像，深度5）；
  4. PlantCLEF 2015（1000类野生植物，图像，浅层树，严重类不确定性）；
  5. Allen Mouse Brain (AMB)（93类小鼠脑皮层细胞类型，单细胞基因表达，深度4）；
  6. DBpedia219（219类维基实体百科，长文本，深度4）。
• 时间范围：AISTATS 2026 最新基准测评协议，所有实验均采用 10 次独立随机标定/测试集重采样（Resampling）。
• 样本量/案例数：CIFAR-10 样本量 60,000；DBpedia219 样本量高达 337,739；PlantCLEF 2015 样本量 113,204；标定集与测试集严格隔离（例如 PlantCLEF 标定与测试各 10,723 样本）。
• 数据局限：PlantCLEF 树结构较浅（科-属-种仅3层），内部节点子分支庞大，导致单节点模式下回退代价极高。

研究结论

• 主要发现 1：所有提出的共形预测算法在全部六大数据集上均精准无误地达成了预设的名义覆盖率（名义值 0.900，实验测得均稳定在 0.899–0.901）；对比实验表明，如果不引入随机化项（朴素版本 NCRSVP 与 NCRSVP-3），因树节点的概率离散跃迁，经验覆盖率会严重失真偏高至 0.997–1.000，验证了随机化嵌套集在消除保守过覆盖中的不可替代性。
• 原文引用 1：

“The confidence level is set to 90%, and calibration and test sets are resampled 10 times… The results clearly indicate that naïve set-valued predictors fail to deliver prediction sets with exact coverage, thereby highlighting the importance of randomized prediction sets. Moreover, increasing the representation complexity generally improves efficiency, demonstrating its practical value.” (Page 8, Table 2)

• 主要发现 2：适度放宽表征复杂度约束（由 $r=1$ 增至 $r=3$）能带来惊人的集合紧凑度提升；在深层大型图谱 Caltech-256 上，平均预测集大小从 CRSVP ($r=1$) 的 44.69 骤降至 CRSVP-3 的 20.30（缩减超过 54%）；在极端困难的 PlantCLEF 2015 上，集合大小由 520.9 显著精简至 389.7，且实际表征复杂度仅由 1.000 微增至 1.632，有效终结了“动辄退回根节点”的尴尬局面。
• 原文引用 2：

“Caltech-256: CRSVP (r=1) size is 44.69 ± 1.252 with R.C. 1.000; CRSVP-3 size drops to 20.30 ± 0.830 with R.C. 1.498 ± 0.009. PlantCLEF 2015: CRSVP size is 520.9 ± 4.745; CRSVP-3 size drops to 389.7 ± 5.898 with R.C. 1.632 ± 0.010.” (Page 8, Table 2)

• 主要发现 3：无约束平铺方法（如 APS、LAC）虽然名义集合较小，但其代价是表征复杂度在大型数据集上彻底失控爆炸；在 DBpedia 上，APS 输出集合的表征复杂度高达 11.90，NPS 高达 53.18；在 PlantCLEF 上，APS 表征复杂度突破 40.19，LAC 达到 24.33；这意味着人类需要阅读分散在数十个不同门类下的碎片化标签，完全丧失了层级本体的引导价值。
• 原文引用 3：

“In extreme cases, when representation complexity is unrestricted, such as with LAC, NPS, and APS, optimal performance in terms of efficiency is observed. However, this comes at the cost of significantly increased representation complexity in the prediction sets, in particular for large K, which may not be practical when predictions need to adhere to a predefined hierarchy.” (Page 8)

• 主要发现 4：树拓扑的几何深度对复杂度的敏感性具有显著调节作用；在浅层宽分叉树（如 PlantCLEF）中，内部节点涵盖子节点过多，增加表征复杂度带来的收益远大于深层窄分叉树，证明多节点联合推断是攻克扁平宽泛长尾分类体系的决定性利器。
• 原文引用 4：

“In such cases, a shallow hierarchy can lead to imprecise predictions for low representation complexity, as internal nodes in shallow trees often have many children. For example, the PlantCLEF 2015 dataset, characterized by 1,000 classes and a shallow hierarchy… requires a higher representation complexity to achieve manageable prediction sets.” (Page 8–9)

我的判断

• 最有启发的点：
  1. “表征复杂度”概念的降维打击：在机器学习中，人们往往机械地以为“预测集合小就是好”；本文提出了一个极为深刻的反直觉视角——如果一个包含 5 个类别的集合来自 5 个八竿子打不着的领域，其认知负担远重于包含 10 个同科物种的集合；通过定义表征复杂度 $R_{\mathcal{T}}$，首次将“人类理解的认知模块数”作为硬约束纳入统计推断；
  2. 巧妙利用整数拆分化解组合爆炸：将集合挑选转化为树上整数配额 $r_i$ 的分拆，自底向上像拼积木一样缓存状态，将原本不可做的 NP-hard 搜索优雅地限制在极低毫秒级。
• 可借鉴的方法：
  • 随机平滑嵌套预测集（Randomized Nested Sets）：在任何涉及离散层级或树状打分的置信区间估计中，必须引入如公式 (7) 的均匀扰动项，否则离散跳跃必将导致经验覆盖率严重失真与过宽的悲观区间。
• 可继续追问的问题：
  • 目前动态规划是在静态树结构上进行离散优化；如果树拓扑本身包含带有权重的语义距离（不同父子边的语义跃迁跨度不同），如何将表征复杂度与语义距离惩罚进行加权共融？
• 与我的研究关联：
  • 本文是“树模型知识图谱”在面对跨领域长尾实体链接与类别抽象时的关键理论支撑，尤其是其实用性极强的动态规划算法可直接用于知识图谱复杂查询结果的聚合呈现。