揭示决策树剪枝的计算复杂性边界，区分可高效求解与难解情形。
Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
- 分析子树替换与提升两种剪枝操作的算法复杂度
- 子树替换可多项式时间求解，子树提升为NP完全
- 发现特征数和取值域大小决定问题是否可高效求解
我们对决策树剪枝操作进行了全面的经典与参数化复杂性分析，拓展了关于学习小规模决策树复杂性的最新研究。聚焦于子树替换与提升这两种常用启发式剪枝操作，发现虽然最优子树替换可在多项式时间内完成，但子树提升问题是NP完全的。因此，我们识别出导致固定参数可解或难解的参数及其组合，确立了两类复杂性之间的精确边界。例如，当特征数d或取值域大小D较小时，子树提升可在 $D^{2d} \cdot |I|^{O(1)}$ 时间内求解，其中 $|I|$ 为输入规模。我们还补充了初步实验结果，验证理论分析的实际意义。
原文摘要 · Abstract (English)
We present a comprehensive classical and parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decision trees. Thereby, we offer new insights into the computational challenges of decision tree simplification, a crucial aspect of developing interpretable and efficient machine learning models. We focus on fundamental pruning operations of subtree replacement and raising, which are used in heuristics. Surprisingly, while optimal pruning can be performed in polynomial time for subtree replacement, the problem is NP-complete for subtree raising. Therefore, we identify parameters and combinations thereof that lead to fixed-parameter tractability or hardness, establishing a precise borderline between these complexity classes. For example, while subtree raising is hard for small domain size $D$ or number $d$ of features, it can be solved in $D^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the input size. We complement our theoretical findings with preliminary experimental results, demonstrating the practical implications of our analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。