用牛顿优化构建紧凑的可倾斜决策树,提升表格数据建模精度与效率。
Hinge Regression Trees and HRT-Boost: Newton-Optimized Oblique Learning for Compact Tabular Models
- 将斜向分裂转化为非线性最小二乘问题,通过牛顿法高效求解。
- 理论证明模型逼近误差为O(δ²),实测在多个数据集上优于主流单树方法。
- 提出HRT-Boost集成框架,兼顾性能与模型紧凑性,适合资源受限场景。
由于分裂优化的离散性和非凸性,学习高质量的可倾斜决策树仍面临重大挑战。本文提出铰链回归树(Hinge Regression Tree, HRT)框架,将每个可倾斜分裂重构为两个线性预测器的最大/最小包络所构成的非线性最小二乘问题,从而实现类似ReLU的表示能力。我们证明该节点级优化可解释为阻尼牛顿法,其回溯线搜索变体保证目标函数单调下降。理论上,我们建立了HRT作为通用逼近器的性质,并给出显式的$O(δ^2)$逼近率。在此基础上,我们提出HRT-Boost,一种数学上协同的集成扩展方法,将节点级牛顿更新与阶段式函数梯度下降相结合。我们证明该集成结构在平方损失下具有阶段式经验风险递减保证。在合成与真实世界基准上的实证评估表明,HRT在性能上与主流单树基线相当,而HRT-Boost则优于强集成基线,且通常生成更紧凑的模型。代码已公开于https://github.com/Hongyi-Li-sz/HRT-Boost。
原文摘要 · Abstract (English)
Learning high-quality oblique decision trees remains a significant challenge due to the discrete and non-convex nature of split optimization. We present the Hinge Regression Tree (HRT) framework, which reframes each oblique split as a nonlinear least-squares problem over two linear predictors whose max/min envelope induces ReLU-like representation capacity. We show that the resulting node-level optimization can be interpreted as a damped Newton method, and we establish the monotonic decrease of the node objective for its backtracking line-search variant. We establish, theoretically, that HRT is a universal approximator with an explicit $O(δ^2)$ approximation rate. Building upon this base learner, we propose HRT-Boost, a mathematically synergistic ensemble extension that couples node-level Newton updates with stage-wise functional gradient descent. We show that this ensemble construction admits a stage-wise empirical risk reduction guarantee under the squared loss. Empirical evaluations on synthetic and real-world benchmarks show that HRT is highly competitive with established single-tree baselines, and HRT-Boost compares favorably with strong ensemble baselines and often yields substantially more compact models. The code is publicly available at https://github.com/Hongyi-Li-sz/HRT-Boost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。