用于特征选择的条件推断树与森林

# 条件推理树与条件推理森林在特征选择中的应用 来源：https://arxiv.org/html/2607.01417 Robert Milletich, Justin Downes, Steve Goley, Newel Hirst Amazon Web Services \{rmilleti,jusdow,sgoley,nhirst\}@amazon\.com ###### 摘要 条件推理树（CIT）和条件推理森林（CIF）通过在选择分裂阈值之前对特征进行测试来减少分裂选择偏差，但重复的置换检验和阈值搜索可能使这些方法计算开销较大。本文研究将 CIT 和 CIF 作为 top-\(k\) 特征排序方法，用于下游预测，并通过真实数据基准测试、运行时间消融实验和合成特征恢复实验进行评估。在固定节点上，如果特征和置换预算不依赖于节点响应，则经 Bonferroni 校正的 \(+1\) 蒙特卡洛置换 \(p\) 值在完全置换零假设下控制节点级拒绝率。在 22 个数据集上的 17 种分类方法中，CIF 排名第 4；在 8 个数据集上的 18 种回归方法中，CIF 排名第 3。在 Bonferroni 校正固定的情况下，CIF 运行时间消融实验表明，自适应停止和搜索的阈值数量对运行时间影响最大：关闭自适应停止和使用精确阈值搜索分别使拟合时间增加 4.0–8.4 倍和 1.9–10.8 倍，而下游评分变化最多不超过 0.011。稀疏高维模拟表明，森林特征采样可能会使信息量丰富的特征在许多分裂决策中被排除。总体而言，结果支持 CIF 作为评估的下游预测基准中的 top-\(k\) 特征排序方法。 ## 1 引言 条件推理将特征选择与阈值优化分离，以减少分裂选择偏差。经典的 CART 树通过同一依赖标签的搜索同时选择特征和阈值，这有助于解释其倾向于选择具有众多可接受分割点的特征的已知偏好 [3 (https://arxiv.org/html/2607.01417#bib.bib13), 25 (https://arxiv.org/html/2607.01417#bib.bib14), 22 (https://arxiv.org/html/2607.01417#bib.bib40), 26 (https://arxiv.org/html/2607.01417#bib.bib41), 32 (https://arxiv.org/html/2607.01417#bib.bib50), 34 (https://arxiv.org/html/2607.01417#bib.bib42), 36 (https://arxiv.org/html/2607.01417#bib.bib4)]。在条件推理框架中 [17 (https://arxiv.org/html/2607.01417#bib.bib1), 16 (https://arxiv.org/html/2607.01417#bib.bib39)]，阶段 A 测试特征与当前节点响应的关联并从中选择特征；阶段 B 则在所选特征内优化阈值。这种分离解决了分裂选择偏差，但经典方法可能因大量置换预算和每个节点上的穷举阈值扫描而需要大量计算。同样的条件推理框架也启发了后来关于条件变量重要性的工作 [35 (https://arxiv.org/html/2607.01417#bib.bib5)]。另一条相关工作线直接使用森林进行变量筛选和排序，而非仅用于最终预测 [10 (https://arxiv.org/html/2607.01417#bib.bib46)]。 本文将条件推理树（CIT）和条件推理森林（CIF）作为特征选择方法进行评估。对于每个随机种子和交叉验证折，一种方法从训练折中产生一个排序。然后，固定的下游学习器在该排序的 top-\(k\) 前缀上拟合，并在保留数据上进行评估，结果跨数据集汇总。该基准测试询问：树和森林衍生的排序是否将预测性变量足够早地放在前面，以改进固定的下游模型。我们还询问 CIT/CIF 的运行时间超参数是否能在保持排序质量的同时减少计算量，以及 CIF 在高维或合成设置中恢复能力较弱的情况。这个特征选择基准测试与将树和森林作为直接预测器或因果估计器的工作是分开的 [4 (https://arxiv.org/html/2607.01417#bib.bib15), 39 (https://arxiv.org/html/2607.01417#bib.bib17), 1 (https://arxiv.org/html/2607.01417#bib.bib18)]。由于几种方法具有可调配置，基准测试为每个方法和任务选择一种配置。作为敏感性检查，留一数据集（LODO）分析在排除每个数据集后重复配置选择，使用第 4.2 节 (https://arxiv.org/html/2607.01417#S4.SS2) 中定义的完整案例面板。定理研究固定节点处的阶段 A 特征测试。它假设在节点处测试的特征和重采样预算独立于节点响应固定，因此穷举固定 \(B\) \(p\) 值在节点级完全置换零假设下具有清晰的置换参考分布。然后，基准测试通过实验评估树和森林的特征排序。 ##### 贡献。本文为 top-\(k\) 下游预测提供了一个基于真实数据的条件推理特征排序基准测试。该基准测试比较了 CIF 与 ctree、cforest、CIT 及其他基线在分类和伴随回归分析中的表现，并包括对主要 CIT/CIF 运行时间超参数的消融实验。本文还陈述了固定节点、穷举固定 \(B\) 的阶段 A 保证（定理 1 (https://arxiv.org/html/2607.01417#Thmtheorem1) 和 推论 1 (https://arxiv.org/html/2607.01417#Thmcorollary1)）；完整的树和森林排序在基准测试中进行了评估。最后，高维和合成分析显示了 top-\(k\) 恢复较弱的情况，以及森林特征采样如何降低森林分裂使用信息量丰富的特征的频率（第 6 节 (https://arxiv.org/html/2607.01417#S6)）。 ## 2 树生长方法 在每个内部节点处，条件推理树做出两个决策。阶段 A 测试特征与响应的关联并选择一个特征进行分裂。阶段 B 随后仅搜索该选定特征的阈值；如果没有接受有效的分裂，则该节点成为叶节点。在本文中，CIT 表示由此产生的单树特征选择方法。CIF 表示此类树的 Bootstrap 集成，在每个节点处进行特征采样，并通过跨树聚合分裂重要性形成特征排序。CIF-all 禁用特征子采样：每个非恒定可用特征都可以在每个节点进入阶段 A。这会改变阶段 A 的特征集、阶段 A 的多重性校正以及每个节点的计算成本。 ### 2.1 阶段 A 和阶段 B 在节点 \(t\) 处，记 \((X_t, Y_t)\) 为到达该节点的样本。设 \(F_{t,\mathrm{avail}}\) 为树生长算法带入该节点的特征集，包括从祖先继承的任何特征静默。设 \(F_{t,\mathrm{nonconst}} \subseteq F_{t,\mathrm{avail}}\) 为节点样本上非常数的特征。在任何特征子采样之后，阶段 A 考虑一个集合 \(F_t \subseteq F_{t,\mathrm{nonconst}}\)；其大小 \(m_t = |F_t|\) 是该节点的 Bonferroni 分母。选择器使用的任何与标签无关的辅助随机性用 \(U\) 表示，并在固定节点保证中保持不变。当树生长过程中启用自适应停止时，阶段 A 可以顺序评估特征，并在 \(F_t\) 中的所有特征都被测试之前停止。设 \(E_t \subseteq F_t\) 为评估的子集；在穷举固定 \(B\) 参考规则中，\(E_t = F_t\)。第 3 节 (https://arxiv.org/html/2607.01417#S3) 中的固定节点定理适用于该参考规则：\(F_t\) 中的特征和预算 \(B\) 独立于节点响应固定，并且每个 \(j \in F_t\) 的 \(p_{t,j}\) 都使用该预算。自适应树生长增加了响应依赖的节点选择、继承的特征静默以及用于树构建的停止时间分数。 ##### 阶段 A（特征选择）。在穷举固定 \(B\) 设置中，阶段 A 遵循条件推理树的特征选择与阈值搜索分离 [17 (https://arxiv.org/html/2607.01417#bib.bib1)]。原始条件推理测试使用 Strasser 和 Weber [33 (https://arxiv.org/html/2607.01417#bib.bib2)] 的排列统计框架；此处，蒙特卡洛标签排列校准配置的选择器统计量。阶段 A 为 \(F_t\) 中的每个特征 \(j\) 计算一个选择器统计量 \(T^{\mathrm{sel}}_j(X_{t,j}, Y_t; U)\) 和排列 \(p\) 值 \(p_{t,j}\)，然后选择 $$p_t^{\star,\mathrm{ref}} := \min_{j \in F_t} p_{t,j}, \qquad M_t^{\star} := \{ j \in F_t : p_{t,j} = p_t^{\star,\mathrm{ref}} \}.$$ (1) 当启用 Bonferroni 时，令 \(\tau_t = \alpha_{\mathrm{sel}}/m_t\)，否则令 \(\tau_t = \alpha_{\mathrm{sel}}\)。如果 \(p_t^{\star,\mathrm{ref}} \ge \tau_t\)，阶段 A 不返回任何特征，节点成为叶节点。如果 \(p_t^{\star,\mathrm{ref}} < \tau_t\)，则从 \(M_t^{\star}\) 中使用水库采样均匀抽取选定的特征 \(j_t^{\star,\mathrm{ref}}\)，节点进入阶段 B。在自适应树生长过程中，阶段 A 使用相同的决策结构，但可以根据初步分数对特征进行排序，并仅评估子集 \(E_t\)。返回的值 \(q_t^{\mathrm{feat}}\) 用于生长树；它不受定理 1 (https://arxiv.org/html/2607.01417#Thmtheorem1) 覆盖的穷举固定 \(B\) \(p\) 值。在具有 Bonferroni 校正的穷举参考规则下，\(\min(1, m_t p_t^{\star,\mathrm{ref}})\) 是固定节点阶段 A 测试的保守完全零假设 \(p\) 值。当启用特征静默时，阶段 A \(p\) 值未拒绝的特征可以从后代特征池中移除。当静默禁用时，后代保留 \(F_{t,\mathrm{avail}}\)，但确定性的常数特征修剪除外。 ##### 阶段 B（阈值搜索）。给定选定的特征 \(j_t^{\star}\)，阶段 B 从 \(X_{t,j_t^{\star}}\) 有序唯一值之间的中点开始。精确方法使用所有这样的中点。随机方法采样一个有界的中点子集，而百分位数和直方图方法选择源自中点分布的有界代表性阈值。会使任一子节点低于最小叶节点大小的阈值被过滤掉。如果没有剩余阈值，阶段 B 不返回任何分裂。对于剩余的有穷阈值集合 \(C_{t,j_t^{\star}}\)，阶段 B 选择树使用的阈值。在阈值 \(c\) 处测试的统计量是加权子节点不纯度：$$\frac{|Y_t^L(c)|}{|Y_t|} \mathrm{Imp}(Y_t^L(c)) + \frac{|Y_t^R(c)|}{|Y_t|} \mathrm{Imp}(Y_t^R(c)),$$ 其中 \(\mathrm{Imp}\) 是选定的节点不纯度度量。该统计量用于左尾检验，穷举固定 \(B\) 规则选择具有最小阶段 B \(p\) 值的阈值，并在出现平局时进行均匀打结。在自适应树生长过程中，阈值扫描可能重新排序阈值并在第一个拒绝阈值后停止，因此返回的阶段 B 分数是树构建分数，而非所有保留阈值上的全局最小值。当阶段 B 启用 Bonferroni 时，令 \(\tau_t^{\mathrm{split}} = \alpha_{\mathrm{split}}/|C_{t,j_t^{\star}}|\)，否则令 \(\tau_t^{\mathrm{split}} = \alpha_{\mathrm{split}}\)。如果没有评估的阶段 B \(p\) 值低于 \(\tau_t^{\mathrm{split}}\)，则节点成为叶节点。在阈值通过阶段 B 测试后，最终的最小所需改进检查使用相应的加权不纯度减少。阶段 B 选择树使用的分裂；返回的阶段 B 分数不是有效的后选择 \(p\) 值。算法 1 (https://arxiv.org/html/2607.01417#alg1) 中的训练骨架总结了这一流程，并且对于基准测试的 CIT 和 CIF 配置，在每个分裂处存储两个值：所选特征的阶段 A 排列 \(p\) 值和所选阈值的阶段 B 排列 \(p\) 值。 ### 2.2 蒙特卡洛置换 \(p\) 值 令 \(T_{\mathrm{obs}}\) 为观察到的统计量，\(T_1, \dots, T_B\) 为在 \(B\) 次随机标签排列上计算的相同统计量。对于右尾检验，我们使用 Phipson–Smyth \(+1\) \(p\) 值 [28 (https://arxiv.org/html/2607.01417#bib.bib43), 30 (https://arxiv.org/html/2607.01417#bib.bib3)]，其中 \(\mathbf{1}\{\cdot\}\) 表示指示函数： $$p_{\mathrm{MC}}^{\ge} := \frac{1+\sum_{b=1}^{B} \mathbf{1}\{T_b \ge T_{\mathrm{obs}}\}}{B+1}.$$ (2) 对于左尾检验，我们类似地定义： $$p_{\mathrm{MC}}^{\le} := \frac{1+\sum_{b=1}^{B} \mathbf{1}\{T_b \le T_{\mathrm{obs}}\}}{B+1}.$$ (3) 阶段 A 使用右尾约定，阶段 B 使用左尾约定；在两种情况下，平局都计为超出的情况。 算法 1 条件推理树训练骨架（阶段 A \(\rightarrow\) 阶段 B） 1: 训练数据 \((X,Y)\)，超参数 \(\theta\) 2: 训练好的树 \(\mathcal{T}\) 3: \(p \leftarrow\) 矩阵 \(X\) 的列数 4: 返回 GrowNode\((X,Y,1,\{1,\dots,p\},\theta)\) 5: 函数 GrowNode\((X_t,Y_t,d,F_{\mathrm{avail}},\theta)\) 6: 如果 Stop\((X_t,Y_t,d,\theta)\) 则 7: 返回 Leaf\((Y_t)\) 8: 结束如果 9: \((j_t^{\star}, q_t^{\mathrm{feat}}, m_t, F'_{\mathrm{avail}}) \leftarrow \textsc{StageA}(X_t,Y_t,F_{\mathrm{avail}},\theta)\) 10: 如果 \(j_t^{\star} = \bot\) 则 11: 返回 Leaf\((Y_t)\) 12: 结束如果 13: \((c_t^{\star}, q_t^{\mathrm{split}}) \leftarrow \textsc{StageB}(X_t,Y_t,j_t^{\star},\theta)\) 14: 如果 \(c_t^{\star} = \bot\) 则 15: 返回 Leaf\((Y_t)\) 16: 结束如果 17: \((X_t^L,Y_t^L,X_t^R,Y_t^R) \leftarrow \textsc{Partition}(X_t,Y_t,j_t^{\star},c_t^{\star})\) 18: \(\Delta_t \leftarrow \textsc{ImpurityDecrease}(Y_t,Y_t^L,Y_t^R,\theta)\) 19: 如果 \(\Delta_t\) 低于最小所需不纯度减少，则 20: 返回 Leaf\((Y_t)\) 21: 结束如果 22: 将 \(\Delta_t\) 添加到特征重要性累加器（对应 \(j_t^{\star}\)） 23: \(u \leftarrow\) 内部节点，附带分裂 \((j_t^{\star},c_t^{\star})\) 和存储的 \(p\) 值字段 \((q_t^{\mathrm{feat}}, q_t^{\mathrm{split}})\) 24: \(u.\mathrm{left} \leftarrow \textsc{GrowNode}(X_t^L,Y_t^L,d+1,F'_{\mathrm{avail}},\theta)\) 25: \(u.\mathrm{right} \leftarrow \textsc{GrowNode}(X_t^R,Y_t^R,d+1,F'_{\mathrm{avail}},\theta)\) 26: 返回 \(u\) 27: 结束函数 ### 2.3 森林与运行时间超参数 CIF 组合 Bootstrap 树并平均其预测。对于特征选择，它对每棵拟合树的归一化分裂重要性求和，并对森林向量重新归一化。每棵 CIF 树使用与 CIT 相同的阶段 A 和阶段 B 节点规则 [4 (https://arxiv.org/html/2607.01417#bib.bib15), 15 (https://arxiv.org/html/2607.01417#bib.bib49)]。固定节点定理仅适用于阶段 A 参考...