用牛顿法优化斜向决策树分割，更快更准。
Hinge Regression Tree: A Newton Method for Oblique Regression Tree Splitting
- 将分裂问题转化为非线性最小二乘，用牛顿法迭代求解。
- 在真实和合成数据上表现优于基线，结构更紧凑。
- 理论证明可逼近任意函数，适合需要高效模型的场景。
斜向决策树结合了树结构的可解释性与多变量决策边界的强大表达能力，但高质量斜向分裂的学习是NP难问题，现有方法依赖缓慢搜索或无理论依据的启发式。本文提出铰链回归树（HRT），将每个分裂重构为两个线性预测器的最大/最小包络构成的非线性最小二乘问题，具有类似ReLU的表达能力。其交替拟合过程等价于固定分区内的阻尼牛顿（高斯-牛顿）法。我们分析该节点级优化，并证明采用回溯线搜索的变体能单调降低局部目标函数并收敛；实际中，固定与自适应阻尼均实现快速稳定收敛，可结合可选的岭正则化。进一步证明HRT的模型类是通用逼近器，具有显式的$O(δ^2)$逼近率。在合成与真实世界基准测试中，其性能匹配或超越单棵树基线，且结构更紧凑。
原文摘要 · Abstract (English)
Oblique decision trees combine the transparency of trees with the power of multivariate decision boundaries, but learning high-quality oblique splits is NP-hard, and practical methods still rely on slow search or theory-free heuristics. We present the Hinge Regression Tree (HRT), which reframes each split as a non-linear least-squares problem over two linear predictors whose max/min envelope induces ReLU-like expressive power. The resulting alternating fitting procedure is exactly equivalent to a damped Newton (Gauss-Newton) method within fixed partitions. We analyze this node-level optimization and, for a backtracking line-search variant, prove that the local objective decreases monotonically and converges; in practice, both fixed and adaptive damping yield fast, stable convergence and can be combined with optional ridge regularization. We further prove that HRT's model class is a universal approximator with an explicit $O(δ^2)$ approximation rate, and show on synthetic and real-world benchmarks that it matches or outperforms single-tree baselines with more compact structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。