首次精确枚举连续特征决策树的近似最优模型集合,提升效率与完整性。
ArborEnum: Decision Tree Rashomon Sets over Continuous Features

- 利用连续特征的有序结构,精确枚举决策树近似最优解集
- 相比传统离散化方法,避免遗漏重要特征与预测多样性
- 支持渐进式逼近,适合需要可解释性与鲁棒性的场景
Rashomon效应指出,多个模型可在同一任务上达到相近性能,这对模型鲁棒性、特征重要性和定制化具有深远影响。该现象催生了对Rashomon集(即正则化损失接近最优的所有模型集合)的计算需求。决策树是少数可完全枚举Rashomon集的模型之一,但以往方法依赖数据的二值化,要么限制分裂方式,要么极大增加原本复杂的组合问题难度。本文提出首个能直接处理连续特征的精确枚举算法,充分利用特征有序性;进一步设计近似枚举松弛和任意时算法,逐步优化候选分割点,生成逐步细化的逼近结果,收敛至连续特征下的真实Rashomon集。实验表明,粗略离散化会遗漏大量有效树、关键特征与预测多样性;本方法相较现有技术实现数量级加速,近似方案在保持近乎完美召回率的同时提供更高效率。
原文摘要 · Abstract (English)
The Rashomon effect describes the phenomenon that many models can achieve nearly equivalent performance on the same learning task, with significant ramifications for robustness, feature importance, and customizability. These use cases motivate the computation of Rashomon sets: the set of all models whose regularized loss is near-optimal. Decision trees are one of the few model classes for which Rashomon sets can be fully enumerated, but this computation has always been conditional on a binarization of the original data, either restricting which splits each tree is allowed to make or substantially increasing the complexity of an already difficult combinatorial problem. We introduce the first algorithm that exactly enumerates decision-tree Rashomon sets while exploiting the ordered structure of continuous features. We further develop a relaxation for approximate enumeration and an anytime algorithm that progressively refines the set of candidate thresholds, producing increasingly detailed approximations that converge to the continuous-feature Rashomon set. Experiments show that coarse binarization can miss many trees, important features, and predictive multiplicity; our algorithms achieve orders-of-magnitude speedups over existing enumeration methods, with approximations providing further speedups while maintaining near-perfect recall.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。