Counterfactual Maps: What They Are and How to Find Them¶

会议: NeurIPS 2026
arXiv: 2602.09128
OpenReview: https://openreview.net/forum?id=Oc0x3mRg64
代码: 待确认
领域: 可解释性
关键词: 反事实解释、树集成模型、广义沃罗诺伊图、最近区域搜索、KD-Tree

一句话总结¶

针对树集成模型反事实解释在启发式搜索缺乏最优性保证与冷启动整数规划难以满足实时交互的矛盾，本文提出“反事实地图”（Counterfactual Maps），利用 Born-Again 树将模型决策空间压缩为轴对齐超矩形划分，并在离线阶段为目标类别构建体积 KD-Tree 索引，在线查询时以毫秒级时延完成带全局最优性证书的分支限界最近区域检索与投影。

研究背景与动机¶

在信贷风控、医疗诊断与司法量刑等高风险决策场景中，反事实解释（Counterfactual Explanations）通过指出“特征做何种最小改动即可改变模型判定”，为用户提供了关键的行为追索（Actionable Recourse）与模型可解释性。树集成模型（如随机森林、梯度提升树）因在表格数据上的卓越表现而被广泛部署。几何上，树集成模型将整个输入特征空间划分成大量轴对齐的超矩形区域（Hyperrectangles），每个区域内部预测值保持恒定。因此，对于任一输入样本，全局最优的反事实解释本质上等价于寻找在给定范数（如 $L_1, L_2, L_\infty$）下距离该样本最近的目标类别超矩形，并将样本投影至该区域。

然而，现有的反事实生成算法普遍将该任务视为单实例（per-instance）的在线优化问题，面临着无法调和的精度与效率权衡。以 Feature Tweaking、LIRE 或 DiCE 为代表的启发式方法通过遍历单树决策路径或向临近区域摄动来寻找翻转解，但完全缺乏全局最优性保证；在实际测试中，启发式搜索不仅常常收敛到高代价的次优解，甚至在真实决策森林中面临高达 40% 到 90% 以上的有效反事实生成失败率。另一方面，以 OCEAN 为代表的精确求解方法依赖混合整数规划（MIP），虽能给出严格全局最优解，但每来一个用户请求就必须从头冷启动求解一次大规模数学规划，耗时通常在数秒乃至数十秒，面对高并发或交互式审计需求时完全不可用。

这种两难困境的根源在于：过往方法孤立地针对每个独立样本求解优化，忽视了模型整体决策空间所固有的几何不变性。既然树集成模型诱导的空间划分对所有查询是静态共享的，反事实搜索在本质上等价于在目标类别的超矩形集合中检索最近区域。本文的核心 idea 是：将反事实解释由“单样本在线规划”重构为“基于广义沃罗诺伊划分的最近区域检索”，通过离线构建体积 KD-Tree 索引形成全局反事实地图，在在线查询时以分支限界剪枝实现毫秒级、兼具全局最优性证书的平摊反事实生成。

方法详解¶

整体框架¶

反事实地图（CF-Maps）采用“离线预处理建图（Build）+ 在线交互式查询（Query）”的双阶段解耦范式。对于训练好的树集成模型 $\mathcal{T}$，离线阶段首先通过无损提取算法将其决策空间转化为覆盖全域的无重叠带标签轴对齐超矩形集合 $\mathbb{H}$；针对每个目标分类标签 $y'$，抽取所有预测为 $y'$ 的超矩形子集 $\mathbb{H}_{y'}$，并分别构建一棵层次化体积 KD-Tree（Volumetric KD-Tree）。在线查询时，给定任意待解释样本 $x$ 和目标类别 $y'$，算法直接检索该类别对应的体积 KD-Tree，利用紧致的几何包围盒下界执行分支限界搜索，迅速收敛至距离 $x$ 最近的目标超矩形 $\mathcal{H}^\star$，最后通过坐标截断投影直接输出最优反事实样本 $x_{\text{cf}}$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：已训练树集成模型"] --> B["阶段1：决策空间超矩形划分提取<br/>Born-Again Tree 紧凑保真提取"]
    B --> C["阶段2：类别级体积 KD-Tree 索引构建<br/>离线为每个类别构建层次包围盒"]
    C --> D["阶段3：分支限界最近区域检索<br/>优先队列遍历 + 紧致距离下界剪枝"]
    D --> E["阶段4：闭式坐标截断投影<br/>闭式映射生成全局最优反事实"]
    E --> F["输出：全局最优反事实样本与证书"]

关键设计¶

1. 决策空间超矩形划分提取：摆脱暴力正交相交的组合爆炸

构建反事实地图的前提是获得一个既覆盖整个特征空间又与原始集成模型严格保真的超矩形划分 $\mathbb{H}=\{\mathcal{H}_1,\ldots,\mathcal{H}_n\}$。若通过简单相交所有单树的阈值划分面，产生的区域数量将随树的深度和棵数呈指数级爆炸，内存与计算均不可行。本文基于 Born-Again Tree（BA-Trees）技术，将多棵树的复杂决策逻辑无损压缩为一棵单树的等价表达，高效抽取出紧凑、互不相交且预测值完全一致的轴对齐超矩形集。每个超矩形 $\mathcal{H}_i=[a^{(i)}, b^{(i)}]$ 由各维度的上下界标定，并携带唯一的类别标签 $\mathcal{T}(\mathcal{H}_i)$。

2. 类别级体积 KD-Tree 索引构建：将反事实地图隐式表达为几何索引

从几何结构分析，在目标类别超矩形集 $\mathbb{H}_{y'}$ 诱导下，特征空间被隐式划分为一组广义沃罗诺伊单元（Generalized Voronoi Cells）。当采用 $L_1$ 或 $L_\infty$ 范数时，不同超矩形之间的等距平分面是有限个多面体的并集；而在 $L_2$ 范数下，平分面则包含二次超曲面。由于直接在多维空间中显式计算和存储这些非线性沃罗诺伊边界极其困难，CF-Maps 采用体积 KD-Tree（Volumetric KD-Tree）对反事实地图进行隐式几何索引。对于每个目标类别 $y'$，算法独立建立一棵二叉树：叶子节点存放不超过设定容量的真实决策超矩形 $\mathcal{H}$，而每个内部节点 $v$ 则动态维护其所有后代叶子区域的最小轴对齐外包围盒 $B(v)=[\ell(v), u(v)]$，确保满足树包围盒单调包含不变性： $$\bigcup_{\mathcal{H}\in\mathbb{H}(v)}\mathcal{H}\subseteq B(v)$$

3. 分支限界最近区域检索：基于包围盒下界实现亚线性在线搜索

在线查询阶段，面对输入样本 $x$ 和目标类别 $y'$，如果线性扫描 $\mathbb{H}_{y'}$ 中的所有超矩形，查询代价依然偏高。CF-Maps 引入了带全局最优性保证的优先队列式分支限界算法。核心在于利用包围盒距离作为单调下界：由于对任意子树节点 $v$ 及其中包含的任意超矩形 $\mathcal{H}$，均恒成立包围盒距离不大于区域距离，即 $d_p(x, B(v)) \le d_p(x, \mathcal{H})$。算法维护一个以包围盒下界 $lb(v) = d_p(x, B(v))$ 为优先级的最小优先队列，每次弹出下界最小的节点。一旦堆顶节点的下界不小于当前已发现的最优距离 $d^\star$，即可依据理论严格提前终止，安全剪枝掉整棵子树中的数百万个候选区域。

4. 闭式坐标截断投影：从最优超矩形即时恢复反事实特征

当分支限界搜索定位到全局最近超矩形 $\mathcal{H}^\star=[a^\star, b^\star]$ 后，反事实样本的生成无需再跑任何二次优化迭代，而是通过闭式坐标截断投影算子 $\Pi_{\mathcal{H}^\star}(x)$ 一步到位得到。对于任意 $p \ge 1$ 范数，样本 $x$ 沿各特征维度的投影均为其在区间 $[a_k^\star, b_k^\star]$ 上的截断值： $$(\Pi_{\mathcal{H}^\star}(x))_k = \max\bigl(a_k^\star, \min(x_k, b_k^\star)\bigr)$$ 这一设计使样本生成在找到超矩形后的计算耗时基本为零，且自然支持特征重要性加权与不可变特征的无穷大惩罚。

理论分析与设计权衡¶

定理 3.1（最近超矩形精确搜索定理）保证了算法的全局最优性：优先队列在循环中保持“未访问矩形覆盖不变量”（Coverage Invariant），即任何未被显式评估的矩形要么被挂在优先队列中的某个节点下，要么属于已被证明下界不小于 $d^\star$ 的被剪枝节点。因此，当堆顶下界超越 $d^\star$ 或队列排空时，绝不可能漏掉更优的候选区域。

在不同范数之间存在搜索效率的权衡：在 $L_1$、$L_2$ 与 $L_\infty$ 距离下，超矩形坐标维度的距离聚合方式不同。在轴对齐超矩形几何中，$L_\infty$ 范数的包围盒下界最为紧致，因而分支限界剪枝力度最大、遍历节点数最少、查询时延最低；$L_1$ 范数下剪枝边界相对宽松，单次查询访问的节点数略多，但整体时延依然在几十毫秒以内。

实验关键数据¶

主实验¶

实验在五个权威高风险表格数据集（Breast-Cancer, COMPAS, FICO, Pima-Diabetes, Seeds）上评估，基模型为由 100 棵最大深度为 5 的决策树组成的随机森林。对比方法包括：全局精确规划方法 OCEAN、树启发式方法 Feature Tweaking（FT）、数据支持域启发式方法 LIRE、以及基于采样的模型无关方法 DiCE。实验统计了离线预处理时间 $T_P$（秒）、生成 1000 个反事实的总耗时 $T_{1000}$（秒）、生成失败率 $\%F$、以及相对于最优解的反事实距离膨胀比 $D$（$D=1.0$ 代表全局最优）。

数据集	方法	预处理 $T_P$ (s)	1000次耗时 $T_{1000}$ (s)	失败率 %F (%)	距离膨胀比 D
BC (Breast-Cancer)	OCEAN CF-Maps (本文) LIRE FT DiCE	3.0 556.7 3.9 - -	1142.9 45.2 1.3 106.9 1950.8	0.0 0.0 0.0 93.2 2.2	1.0 1.0 2.3 1.6 2.8
CP (COMPAS)	OCEAN CF-Maps (本文) LIRE FT DiCE	5.0 0.2 2.0 - -	618.7 1.4 1.2 239.4 1482.8	0.0 0.0 0.0 41.4 15.1	1.0 1.0 1.1 1.0 1.0
FI (FICO)	OCEAN CF-Maps (本文) LIRE FT DiCE	5.9 0.9 33.0 - -	1273.0 17.6 23.6 731.9 1884.7	0.0 0.0 0.0 63.0 16.6	1.0 1.0 1.3 1.0 1.3
PD (Pima-Diabetes)	OCEAN CF-Maps (本文) LIRE FT DiCE	13.9 467.5 15.9 - -	42983.2 32.1 2.4 177.6 1278.4	0.0 0.0 0.0 79.3 1.0	1.0 1.0 2.4 3.2 4.4
SE (Seeds)	OCEAN CF-Maps (本文) LIRE FT DiCE	2.9 120.1 2.2 - -	5068.6 8.5 0.5 55.6 866.1	0.0 0.0 0.0 78.5 1.0	1.0 1.0 3.4 1.9 4.8

消融实验与索引特性分析¶

为探究体积 KD-Tree 索引的结构开销与搜索效率，统计了 100 棵深度为 5 的随机森林构建出的 KD-Tree 节点数、内存占用以及每次反事实查询实际访问的节点数（均值与标准差）：

数据集	KD-Tree 总节点数	内存开销 (MB)	单次查询访问节点数
BC	$(2.48 \pm 0.58) \times 10^6$	$(1.80 \pm 0.42) \times 10^3$	$2738.8 \pm 1026.2$
CP	$(2.80 \pm 0.18) \times 10^2$	$(2.30 \pm 0.20) \times 10^{-2}$	$17.5 \pm 2.1$
FI	$(4.79 \pm 0.14) \times 10^3$	$5.02 \pm 0.15$	$85.0 \pm 9.3$
PD	$(4.54 \pm 0.82) \times 10^6$	$(3.21 \pm 0.58) \times 10^3$	$711.3 \pm 177.4$
SE	$(1.64 \pm 0.34) \times 10^6$	$(1.12 \pm 0.23) \times 10^3$	$546.0 \pm 91.7$

树规模伸缩性分析（随树深度由 2 增至 7，或树数量由 5 增至 100）： - 启发式方法退化严重：随着森林规模扩大，FT 在 BC 数据集上的失败率飙升至 93.2% 到 94.4%；LIRE 虽然保证有效反事实（%F=0），但距离膨胀比 $D$ 从小树的 1.7× 恶化至大树的 2.3×-3.4×；DiCE 的反事实距离比最优解高出 2.8×-4.8×，且伴随 15% 以上的失败率。 - 精确优化扩展性受限：OCEAN 在 Pima-Diabetes 数据集上生成 1000 个反事实需要 42983.2 秒（约 12 小时），而 CF-Maps 仅需 32.1 秒在线查询时间，提速超过 1300 倍。

关键发现¶

平摊收益显著：在需要批量审核、在线交互式服务的场景中，一次性离线构建反事实地图后，CF-Maps 单次查询时延稳定在 1.4ms 到 45.2ms 之间，彻底消除了每查询一次重新解 MIP 的高昂开销。
树集成特征属性决定索引规模：纯连续数值型特征（如 BC, PD）诱导了密集的分割阈值，使得提取的超矩形数量达到数百万级，KD-Tree 需占用数 GB 内存；而分类/有序特征为主的数据集（如 CP, FI）生成的超矩形数量极为紧凑，KD-Tree 内存仅数 KB 至数 MB，查询时仅需遍历数十个节点。

亮点与洞察¶

视角转换的范式创新：将反事实解释从孤立的单实例约束最优化问题，重新阐释为特征空间中模型决策区域的广义沃罗诺伊划分与最近几何邻域检索，使离线平摊（amortization）成为可能。
理论最优性与极速响应兼备：利用分支限界下界剪枝定理，证明了 KD-Tree 搜索既能提前退出获得毫秒级时延，又能保留与全局数学规划完全相同的严密理论最优证书。
支持多解多样性扩展：在寻找最近超矩形的过程中，由于优先级队列天然按距离排序，算法可无缝扩展至枚举所有与最优解距离相等或处于 $\epsilon$-容差范围内的所有超矩形，以几何方式天然生成多路径、多样化的反事实建议。

局限与展望¶

预处理阶段的算力与内存瓶颈：在特征维度极高且包含大量连续变量的深层森林中，Born-Again 树划分提取与数百万节点的 KD-Tree 构建可能需要数分钟到数十分钟，内存占用可达数 GB。
流式更新不友好：当在线集成模型发生再训练或增量树更新时，全局超矩形划分和 KD-Tree 需要全量重建，缺乏低成本局部动态增量更新机制。
未来方向：探索超矩形划分的上/下包络（Envelopes）近似算法，在离线阶段牺牲可控的精度换取更小规模的索引树；或设计混合门控机制，常态下走 KD-Tree 快速分支，极端未索引角落再退化至冷启动 MIP 求解。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出反事实地图概念，将树集成模型反事实解释成功重构为最近区域搜索与广义沃罗诺伊索引问题。
实验充分度: ⭐⭐⭐⭐⭐ 在五个标准高风险数据集上全面覆盖多种树规模、深度与范数距离，多维度对比了时延、失败率、距离膨胀与内存。
写作质量: ⭐⭐⭐⭐⭐ 几何直觉明晰，定理与不变量证明完备，两阶段框架图与算法阐述严密。
价值: ⭐⭐⭐⭐⭐ 为金融信贷、医疗与司法等受监管场景中的实时可解释 AI 与追索系统提供了工业级实用的精确解决方案。

数据集	KD-Tree 总节点数	内存开销 (MB)	单次查询访问节点数
BC	\((2.48 \pm 0.58) \times 10^6\)	\((1.80 \pm 0.42) \times 10^3\)	\(2738.8 \pm 1026.2\)
CP	\((2.80 \pm 0.18) \times 10^2\)	\((2.30 \pm 0.20) \times 10^{-2}\)	\(17.5 \pm 2.1\)
FI	\((4.79 \pm 0.14) \times 10^3\)	\(5.02 \pm 0.15\)	\(85.0 \pm 9.3\)
PD	\((4.54 \pm 0.82) \times 10^6\)	\((3.21 \pm 0.58) \times 10^3\)	\(711.3 \pm 177.4\)
SE	\((1.64 \pm 0.34) \times 10^6\)	\((1.12 \pm 0.23) \times 10^3\)	\(546.0 \pm 91.7\)