首个最优形状广义树算法Literati问世，24个数据集准确率碾压SOTA！
Literati: Towards Anytime Optimal Shape Generalized Trees via AO*
📖 AI 总结
本文提出 Literati，首个能够实现最优形状广义树（SGT）归纳的算法。决策树因可解释性强而在表格数据上表现优异，但传统贪心自顶向下算法常产生次优且冗余的结构；已有的最优决策树方法虽通过全局优化改善结构，却局限于轴对齐阈值分裂，难以高效表达非线性特征效应。形状广义树将阈值分裂推广为可学习的单变量形状函数，提升了表达能力并有助于构建更紧凑的树，但现有归纳算法均为贪心，缺乏最优性保证。Literati 通过新颖的 AND/OR 图公式联合优化树结构与形状函数复杂度，并设计了基于 AO* 的求解算法，引入 OR 节点选择的次级启发式和 AND 节点探索的轮询策略，在保持最优性的同时提升 anytime 性能。在 24 个真实数据集上，Literati 的训练与测试准确率均优于当前最先进的树模型方法。
🔑 关键词速览
| Shape Generalized Trees (SGT) | 形状广义树，一种将传统阈值分割推广为可学习单变量形状函数的决策树，能提高表达能力和紧凑性。 |
| AO* | 一种用于求解AND/OR图的启发式搜索算法，常用于最优决策树归纳。 |
| AND/OR graph | 与或图，一种用于表示问题分解的图结构，其中AND节点表示子问题必须全部解决，OR节点表示选择其中一个子问题解决。 |
| anytime performance | 随时性能，指算法在运行过程中任何时刻都能返回一个可行解，并且随着时间推移解的质量逐渐提高。 |
| optimal decision tree | 最优决策树，通过全局优化方法构建的决策树，旨在最小化某种损失函数，通常比贪婪方法更优。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅