Partition Tree: Conditional Density Estimation over General Outcome Spaces¶

会议: NeurIPS 2026
arXiv: 2602.04042
OpenReview: https://openreview.net/forum?id=MRmk6eSAqk
领域: 其他
关键词: 条件密度估计, 决策树, 非参数估计, Radon-Nikodym导数, 集成学习

一句话总结¶

提出 Partition Tree 及其装袋集成 Partition Forest，基于 Radon–Nikodym 导数在联合协变量-目标空间上自适应划分，以贪心最小化负对数似然构建分段常数密度估计器，统一处理连续、离散及混合型目标变量。

研究背景与动机¶

条件密度估计（Conditional Density Estimation, CDE）在不确定性量化、风险敏感决策和因果推断等任务中处于核心地位。然而，传统决策树模型（如 CART）通常仅专注于单点预测（回归均值）或离散类别概率输出，难以直接输出连续或混合型目标变量的完整后验概率密度。若要借助树模型进行概率建模，现有方法通常面临两难困境：要么像 CADET 那样在叶节点强加高斯分布等参数化假设，在多峰、重尾或受约束分布下极易产生误设偏差；要么像 CDTree 那样在每个节点联合优化划分与叶节点直方图，通过最小描述长度（MDL）准则剪枝，这带来了巨大的计算开销，在大规模样本或集成森林中扩展性受阻。

这种困境的核心矛盾在于：既有概率树方法割裂了特征空间的划分与目标密度的估计，导致参数化拟合刚性过强，而非参数化联合搜索又难以在保持理论一致性的同时实现线性的分裂搜索复杂度。此外，实际场景中目标空间往往包含连续、分类及混合变量，且普遍存在异方差噪声与冗余特征干扰，亟需一种兼具非参数灵活性、统一变量类型表达与高效构建能力的树形概率密度估计范式。

本文的切入角度是回到测度论视角，将条件密度估计直接表征为主导测度下的 Radon–Nikodym 导数，并将树的叶节点形式化为协变量与目标联合空间的乘积子集。核心 idea：将条件分布建模为联合空间自适应网格上的分段常数密度，直接以经验负对数似然为分裂增益进行贪心最佳优先树生长，使分裂增益等价于 Jensen 间隙，并在连续和离散维度上分别通过前缀和与 Bregman 散度排序实现线性扫描，最后引入归一化与装袋构建强鲁棒性的非参数条件密度估计器。

方法详解¶

整体框架¶

Partition Tree 将条件密度估计统一表征在乘积空间 $\mathcal{Z} = \mathcal{X} \times \mathcal{Y}$ 上的测度划分问题中。对于连续或离散的目标空间 $\mathcal{Y}$，固定 $\sigma$-有限参考测度 $\mu_Y$（连续变量对应 Lebesgue 测度，离散变量对应计数测度），在联合分布 $\mathbb{P}_{XY} \ll \mathbb{P}_X \otimes \mu_Y$ 的绝对连续性假设下，条件密度 $f(x, y)$ 本质上是 Radon–Nikodym 导数 $\frac{d\mathbb{P}_{XY}}{d(\mathbb{P}_X \otimes \mu_Y)}$。树的每个叶节点对应一个乘积单元 $A = A_X \times A_Y$。在协变量维度 $X$ 上分裂会精细化特征空间子区域，在目标维度 $Y$ 上分裂则相当于为对应特征区域细化直方图组距（bins）。整个算法通过最佳优先（Best-First）策略动态选取使经验对数损失下降最大（即增益 $\widehat{G}$ 最大）的叶节点及其坐标进行分裂，最后对预测密度进行条件积分归一化，其集成版本 Partition Forest 则通过平均各单树的条件密度输出最终分布。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["样本数据 D = {(x_i, y_i)}<br/>联合空间 Z = X × Y"] --> Trunc["目标空间边界截断<br/>连续坐标经验 Min-Max 盒构建"]
    Trunc --> Split["Radon–Nikodym 划分与增益评估<br/>经验负对数似然与 Jensen 间隙"]
    Split --> FastSearch["高效候选分裂搜索<br/>连续维度线性前缀和 / 类别维度 Bregman 排序扫描"]
    FastSearch --> Growth["最佳优先树生长<br/>优先队列维护全局分裂预算 k_N"]
    Growth --> Norm["叶节点经验计数插值与切片归一化<br/>输出单树有效条件密度 f_bar"]
    Norm --> Bagging["装袋集成 Partition Forest<br/>密度算术平均 + 终验概率校准"]

关键设计¶

1. 基于 Radon–Nikodym 导数的分段常数密度估计：统一连续与离散目标

传统概率树通常需为分类与连续回归设计两套完全不同的分裂指标与叶节点模型。本文从测度论切入，设 $\nu = \mathbb{P}_X \otimes \mu_Y$，在任意非空可测乘积单元 $A = A_X \times A_Y$ 上，为使分段常数密度 $c_A$ 匹配真实联合概率质量 $\int_A c_A \, d\nu = \mathbb{P}_{XY}(A)$，单元最佳常数估计自然导出为 $c_A = \frac{\mathbb{P}_{XY}(A)}{\mathbb{P}_X(A_X) \mu_Y(A_Y)}$。对于有限样本 $\mathcal{D}$，记落在单元 $A$ 内的双变量样本数为 $n_{XY}(A) = \sum_{i=1}^N \mathbf{1}\{(x_i, y_i) \in A\}$，特征投影落入 $A_X$ 的样本数为 $n_X(A) = \sum_{i=1}^N \mathbf{1}\{x_i \in A_X\}$，则经验密度插值形式为： $$\hat{c}_A = \frac{n_{XY}(A)}{n_X(A) \, \mu_Y(A_Y)}$$ 对于无界连续空间，方法通过自适应数据经验极值盒 $\bar{\mathcal{Y}}_N^{(c)} = \prod_{j=1}^{d_{y,c}} [\underline{y}_{N,j} - \delta_N, \overline{y}_{N,j} + \delta_N]$ 实施外侧截断，并证明截断外测度以概率 1 趋于 0。在预测阶段，给定任意查询点 $x$，取出所有满足 $x \in A_X$ 的叶节点，其 $A_Y$ 构成对 $Y$ 空间的划分直方图；为保证对 $\mu_Y$ 积分为 1，执行逐切片积分归一化： $$\bar{f}_{\pi_N}(x, y) = \frac{\hat{f}_{\pi_N}(x, y)}{\int_{\bar{\mathcal{Y}}_N} \hat{f}_{\pi_N}(x, y') \, d\mu_Y(y')}$$ 这一设计消除了对目标分布形式的先验约束，分类任务中 $\mu_Y$ 为计数测度退化为离散概率，回归任务中则自然退化为非参数直方图密度。

2. 对数损失分裂准则与 Jensen 间隙增益：内在自适应异方差与噪声

模型以条件负对数似然 $\mathcal{L}(\pi) = -\mathbb{E}_{\mathbb{P}_{XY}}[\log f_\pi(Z)]$ 作为划分优劣的评分准则。当把叶节点 $A$ 沿某一坐标分裂为 $A_l$ 与 $A_r$ 时，总体增益 $G(\pi', \pi) = \mathcal{L}(\pi) - \mathcal{L}(\pi')$ 在数学上被严格证明等价于凸函数 $\varphi(u) = u \log u$ 在归一化限制测度下的 Jensen 间隙乘以 $\nu(A)$： $$G(\pi', \pi) = \left( \frac{\nu(A_l)}{\nu(A)} \varphi(c_{A_l}) + \frac{\nu(A_r)}{\nu(A)} \varphi(c_{A_r}) - \varphi(c_A) \right) \nu(A) \ge 0$$ 在经验样本下，经验分裂增益 $\widehat{G}(\pi', \pi)$ 仅依赖子节点的计数值： $$\widehat{G}(\pi', \pi) = \frac{n_{XY}(A_l)}{N} \log \left( \frac{n_{XY}(A_l)}{n_X(A_l) \mu_Y(A_{l,Y})} \right) + \frac{n_{XY}(A_r)}{N} \log \left( \frac{n_{XY}(A_r)}{n_X(A_r) \mu_Y(A_{r,Y})} \right) - \frac{n_{XY}(A)}{N} \log \left( \frac{n_{XY}(A)}{n_X(A) \mu_Y(A_Y)} \right)$$ 当沿 $X$ 坐标分裂时，$A_{l,Y} = A_{r,Y} = A_Y$，测度项在对数差分中完全对消；当沿 $Y$ 坐标分裂时，$n_X(A_l) = n_X(A_r) = n_X(A)$。该准则使得树能够根据不同区域的方差分布自动调整叶节点分割粒度，天然适应异方差噪声。

3. 高效分裂扫描与 Bregman 散度前缀排序：消除组合爆炸

若直接枚举分裂，计算开销不可承受。本文针对连续和离散特征分别给出了精细算法优化： - 连续维度：在叶节点内维护两组排序索引（样本协变量索引 $I_x$ 与联合样本索引 $I_{xy}$）。沿排序值扫描候选阈值（相邻相异值中点）时，利用权重前缀和累加数组在 $O(1)$ 时间内更新 $n_X(A_l)$、$n_X(A_r)$ 与 $n_{XY}(A_l)$、$n_{XY}(A_r)$，使得单特征连续分裂评测复杂度从朴素遍历的平方级降至线性扫描 $O(n_X(A) \log n_X(A))$。 - 离散类别维度：针对字母表大小为 $|\Sigma|$ 的离散坐标，避免枚举全部 $2^{|\Sigma|-1}-1$ 种非空子集组合。作者将目标函数转化为 Bregman 散度极小化形式，严格证明了最优子集必对应于按比值 $r_c = \frac{a_c}{b_c}$（对于 $X$ 分裂，$a_c = n_{XY}(A \cap \{z_\ell=c\})$, $b_c = n_X(A \cap \{z_\ell=c\})$）升序排列后的前缀子集。因此仅需排序一次并线性扫描 $|\Sigma|-1$ 个前缀分割点，耗时仅 $O(n_{XY}(A) + |\Sigma| \log |\Sigma|)$，彻底解决了高基数类别的组合爆炸。

损失函数 / 训练策略¶

模型采用基于增益的贪心最佳优先（Best-First）生长策略。全局维护一个以当前叶节点最大经验增益 $\widehat{G}^\star$ 为键的优先队列。每次弹出增益最大的叶节点及其对应最优分裂坐标实施切分，并仅对生成的两个子节点重新评估最优候选切分并压入队列，直至达到全局设定的最大分裂预算 $k_N$。

在集成阶段，Partition Forest 引入类似随机森林的双重扰动：每棵树在自助采样样本（Bootstrap Sample）上独立拟合，且节点分裂时随机子采样特征子集（比例参数 max_features 与 max_samples）。森林对各单树的未归一化密度进行简单算术平均： $$\hat{f}_{\pi_N}^{\mathrm{F}}(x, y) = \frac{1}{B} \sum_{b=1}^B \hat{f}_{\pi_N}^{(b)}(x, y)$$ 最后再执行式 (6) 所示的切片积分归一化，得到满足全概率公理的平滑集成条件密度。

实验关键数据¶

主实验¶

论文在 9 个 UCI 分类数据集和 10 个标准回归数据集上进行了 5 折交叉验证（嵌套 Optuna 贝叶斯超参数调优，以 Log-Loss 为优化准则）。回归任务中，CART 与随机森林通过 skpro 的 ResidualDouble 架构拟合高斯残差方差以提供概率预测。

任务类型与数据集	指标 (Log-loss $\downarrow$)	Partition Tree (单树)	CART / 传统单树	Partition Forest (集成)	Random Forest (RF)
分类: iris	Log-loss	0.46 ± 0.38	0.46 ± 0.46	0.50 ± 0.43	0.15 ± 0.08
分类: breast	Log-loss	0.64 ± 0.05	0.70 ± 0.26	0.58 ± 0.02	0.56 ± 0.04
分类: wine	Log-loss	1.02 ± 0.06	1.47 ± 0.50	0.86 ± 0.04	0.88 ± 0.11
分类: digits	Log-loss	0.45 ± 0.04	1.48 ± 0.22	0.29 ± 0.01	0.29 ± 0.01
分类: spam	Log-loss	0.22 ± 0.04	0.29 ± 0.06	0.17 ± 0.03	0.16 ± 0.02
分类: letter	Log-loss	0.62 ± 0.17	1.42 ± 0.06	0.49 ± 0.01	0.28 ± 0.01
分类平均排名	Avg. Rank	1.33	1.67	1.44	1.56
回归: diabetes	Log-loss	5.65 ± 0.11	17.93 ± 2.49	5.49 ± 0.10	14.21 ± 2.43
回归: boston	Log-loss	2.90 ± 0.17	8.39 ± 3.33	2.53 ± 0.13	4.60 ± 1.08
回归: concrete	Log-loss	3.70 ± 0.06	7.45 ± 0.90	3.36 ± 0.03	3.86 ± 0.40
回归: kin8nm	Log-loss	-0.18 ± 0.02	9.42 ± 0.15	-0.45 ± 0.02	3.30 ± 0.12
回归: air	Log-loss	2.12 ± 0.11	13.49 ± 1.00	2.02 ± 0.10	11.35 ± 0.88
回归: california	Log-loss	0.69 ± 0.02	7.07 ± 0.36	0.42 ± 0.02	3.11 ± 0.14
回归: protein	Log-loss	2.22 ± 0.02	12.31 ± 0.20	2.10 ± 0.02	6.19 ± 0.04
回归平均排名	Avg. Rank	2.30 (单树)	3.70 (单树)	1.20 (集成)	1.80 (集成)

注：回归单树对比中，CDTree 平均排名为 1.70，CADET 为 2.30；而在集成组中 Partition Forest 占据绝对领先。

消融与扩展实验（回归基准多模型对比与计算耗时）¶

下表展示单树概率回归中与参数化方法（CADET）和直方图方法（CDTree）的详细表现，以及在大规模样本（Protein 数据集，样本量 $N=10,000$）上的纯训练耗时对比：

数据集 / 实验项	Partition Tree	CADET (参数化)	CDTree (MDL直方图)	说明
air (Log-loss $\downarrow$)	2.12 ± 0.11	13.78 ± 17.54	6.42 ± 0.00	大规模样本上非参数优势明显，CADET方差极大
power (Log-loss $\downarrow$)	2.87 ± 0.02	2.90 ± 0.10	2.93 ± 0.03	Partition Tree 显著优于两基线
california (Log-loss $\downarrow$)	0.69 ± 0.02	0.88 ± 0.16	0.58 ± 0.02	CDTree 略优，但无法有效扩展至森林集成
protein (Log-loss $\downarrow$)	2.22 ± 0.02	3.13 ± 0.22	2.18 ± 0.02	样本量达到 45,730，非参数模型大幅领先参数树
Protein 训练耗时 ($N=10^4$)	~1.2 s	~6.0 s ($\approx 5\times$)	~30.0 s ($\approx 25\times$)	Partition Tree 相比 CADET 提速 5 倍，比 CDTree 提速 25 倍

关键发现¶

样本规模红利：在 Air、Power、California 和 Protein 等中大规模回归数据集上，Partition Tree 均显著优于参数化概率树 CADET。这表明当样本量充分时，数据自适应的无分布假定分段常数估计器能有效捕捉复杂的非高斯分布结构。
异方差与噪声抗性：在半合成加噪实验中，无论引入同方差噪声还是异方差噪声（$\sigma_i(\lambda) = \lambda |y_i|$），Partition Tree 的对数损失退化斜率均与 CDTree 相当，而 CADET 在各折交叉验证间展现出剧烈的方差波动。
点估计与分布估计的权衡：在均方根误差（RMSE）指标上，传统 Random Forest 略胜一筹（平均排名 1.10 对 1.90），但在衡量预测分布置信度的 Log-loss 上，Partition Forest 在 10 个回归数据集中有 8 个完胜 Random Forest，展现出优异的概率校准能力。

亮点与洞察¶

测度论统一框架：巧妙利用 Radon–Nikodym 导数将分类与连续回归归结为乘积空间上的统一概率覆盖问题，消除算法在不同预测目标上的形式分歧。
Bregman 散度单调性排序：证明类别特征的最优子集划分等价于按经验比例排序后的前缀截断，将指数级子集搜索降为严格对偶的线性前缀扫描，极大释放了离散树的训练效率。
理论一致性闭环：不仅在算法上高效，还在附录中严格推导了在有限 VC 维和单元直径收缩条件下经验估计器收敛至真实条件密度的 $L^1(\nu)$ 强相合性，并证明切片积分归一化操作完好保持相合性。

局限与展望¶

作者承认的局限：目前 Partition Tree 仅扩展至 Bagging（装袋）集成框架；对于 Boosting（梯度提升）集成以及专为条件负对数似然设计的后剪枝算法尚未深入探索。
潜在不足与适用范围：当特征维度极高且存在高度相关的噪声特征副本时，Partition Tree 贪心切分会发生分散，其经验负对数似然退化速度略快于带 MDL 正则的 CDTree；此外高维连续目标空间下的网格划分可能会遇到维数灾难。
改进方向：可进一步将 Partition Forest 集成到连续因果推断（如广义倾向评分估计）管线中，或引入正则化收缩先验以提升极端高维冗余特征下的抗噪鲁棒性。

评分¶

新颖性: ⭐⭐⭐⭐☆ 基于测度论 Radon–Nikodym 导数重塑树形概率密度估计，离散分裂的最优前缀理论推导巧妙。
实验充分度: ⭐⭐⭐⭐☆ 覆盖 19 个经典数据集与合成加噪、特征冗余实验，消融与复杂度对比完整。
写作质量: ⭐⭐⭐⭐⭐ 数学形式严谨自洽，从测度定义到算法工程实现层层递进，结构清晰。
价值: ⭐⭐⭐⭐☆ 为表格数据上的非参数不确定性量化与概率预测提供了计算高效且理论完备的全新工具。

数据集 / 实验项	Partition Tree	CADET (参数化)	CDTree (MDL直方图)	说明
air (Log-loss \(\downarrow\))	2.12 ± 0.11	13.78 ± 17.54	6.42 ± 0.00	大规模样本上非参数优势明显，CADET方差极大
power (Log-loss \(\downarrow\))	2.87 ± 0.02	2.90 ± 0.10	2.93 ± 0.03	Partition Tree 显著优于两基线
california (Log-loss \(\downarrow\))	0.69 ± 0.02	0.88 ± 0.16	0.58 ± 0.02	CDTree 略优，但无法有效扩展至森林集成
protein (Log-loss \(\downarrow\))	2.22 ± 0.02	3.13 ± 0.22	2.18 ± 0.02	样本量达到 45,730，非参数模型大幅领先参数树
Protein 训练耗时 (\(N=10^4\))	~1.2 s	~6.0 s (\(\approx 5\times\))	~30.0 s (\(\approx 25\times\))	Partition Tree 相比 CADET 提速 5 倍，比 CDTree 提速 25 倍