文人：通过 AO* 实现随时最优形状的广义树

arXiv:2609.09299v1 公告类型：新 摘要：决策树因其在表格数据上的可解释性和强大性能而受到重视，但流行的贪婪自上而下归纳算法可能会产生次优且不必要的复杂结构。最优决策树方法通过全局优化解决了这个问题，但仍然局限于轴对齐的阈值分割，这限制了每个节点的表达能力，并且常常迫使深层、复杂的树捕获非线性特征效应。形状广义树 (SGT) 将阈值分割概括为可学习的单变量形状函数，从而提高表达能力并实现更紧凑的树。然而，现有的 SGT 归纳算法是贪婪的并且不提供最优性保证。在这项工作中，我们引入了 Literati，这是第一个最佳 SGT 归纳算法。我们提出了一种新颖的 AND/OR 图表述来联合优化树结构和形函数复杂性。为了解决这个 AND/OR 图，我们开发了一种基于 AO* 的算法，该算法具有两项增强功能，可在保持最优性的同时提高随时性能：用于 OR 节点选择的辅助启发式和用于 AND 节点探索的循环策略。在 24 个现实世界数据集中，Literati 实现了比最先进的树方法更高的训练和测试准确性。