首次实现高维曲面分裂的最优决策树，提升表达力并加速计算。
Optimal hypersurface decision trees
- 基于超曲面分裂构建最优决策树，突破轴向平行限制。
- 时间复杂度为 $O(K! \times N^{DG+G})$，可处理高维数据。
- 支持向量化与并行化，适合大规模数据与高效优化场景。
近年来，最优决策树研究备受关注，但仍面临两大挑战：现有算法构造的决策树表达能力有限，通常仅限于轴向平行分割或二值特征；且难以扩展至大规模数据集。这两者相互关联：更具表现力的分割规则会带来更高的组合复杂性，使最优决策树问题更难求解。本文在 He 和 Little 的合理决策树框架基础上，提出首个求解最优超曲面决策树问题的算法，时间复杂度为 $O(K! \times N^{DG+G})$，其中 $G$ 是依赖于树大小 $K$、超曲面多项式阶数 $M$ 及数据维度 $D$ 的变量。据我们所知，目前尚无已知算法能生成具有超曲面分割的决策树。此外，该算法天然支持向量化，便于并行计算，其通用设计还可用于加速其他最优决策树变体（如轴向平行决策树）。我们还提出一种有效的剪枝策略，使算法实际运行速度显著快于最坏情况上界，并引入增量过程，将单个配置可行性检查成本从二次降至线性时间。
原文摘要 · Abstract (English)
The study of optimal decision trees has gained increasing attention in recent years; however, despite substantial progress, it still suffers from two major challenges: First, trees constructed by existing optimal decision tree (ODT) algorithms have limited expressivity, as they are typically restricted to axis-parallel splits or binary features. Second, these algorithms generally do not scale well to large datasets. These two challenges are intertwined: decision trees with more expressive splitting rules incur significantly higher combinatorial complexity, making the ODT problem even more difficult to solve when using complex splits. Building on He and Little's proper decision tree framework, we propose the first algorithm for solving the optimal hypersurface decision tree problem with time complexity $O\left(K!\times N^{DG+G}\right)$, where $G$ is a variable depends on both $K$ (tree size), $M$ (polynomial degree of hypersurface) and $D$ (data dimension). To the best of our knowledge, no known algorithm is capable of producing decision trees with hypersurface splits. Moreover, the proposed algorithm is inherently amenable to vectorization, enabling efficient parallelization. Its generic design pattern also allows it to be used to accelerate other ODT variants, such as axis-parallel decision trees. Furthermore, we identify an effective pruning strategy for the optimal hypersurface decision tree problem, which enables our algorithm to run significantly faster than the worst-case upper bound, together with an incremental procedure that reduces the cost of checking the feasibility of a single configuration from quadratic to linear time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。