想象一下，你正在尝试教计算机做决策，比如像医生诊断病人或银行决定是否发放贷款那样。你选择的工具通常是“决策树”。把它想象成一个巨大的流程图：“如果患者发烧，向左走；如果不发烧，向右走。”最终，你会到达底部的叶子节点，那里给出了答案。这些树之所以闻名遐迩，是因为它们易于人类阅读和理解，而当我们需要知道机器为什么做出某种选择时，这一点至关重要。
几十年来，构建这些树的标准方法一直是“贪婪式”的。想象一下你在浓雾中爬山。一个贪婪的登山者只看眼前的每一步，并沿着最陡峭的路径向上爬，希望这能通向顶峰。他们不会向前展望，去观察这条陡峭的路径是否会在稍后导致死路。这种方法很快，而且通常能让你爬到相当高的高度。然而，有一种更新颖、更具野心的做法，叫做“最优”决策树。这种方法不再仅仅只看眼前的一步，而是试图一次性绘制出整座山的地图，以找到通往最高点的绝对最佳路径。这就像其他人还在雾中蹒跚前行时，你已经拥有了一张卫星地图。一个大问题是：这种缓慢的、制图式的方法究竟是真的更好，还是仅仅在浪费时间？
这篇由代尔夫特理工大学研究人员撰写的论文，深入探讨了这场辩论。他们运行了同类实验中规模最大的实验，在 109 个真实世界的数据集和数千个合成数据集上测试了这两种方法。他们的发现为机器学习界带来了一个小小的剧情反转。他们发现，“最优”方法确实更胜一筹，但前提是你必须遵循正确的规则。
首先，他们发现“最优”决策树具有极高的灵活性。虽然贪婪法受限于使用特定的、僵化的规则（例如检查“基尼不纯度”，这是一个关于“混乱程度”的专业数学术语）来决定下一步该怎么走，但最优法可以直接瞄准目标：纯粹的准确率。这就像贪婪的登山者被迫只能寻找最陡峭的岩石，而最优的登山者可以直接寻找最高点，无论地形看起来如何。论文表明，当你让最优法直接瞄准准确率时，它构建出的决策树比贪婪树更小且更准确。
然而，研究人员还揭穿了两个流行的迷思。第一个迷思是，随着你给计算机更多的数据，贪婪法会赶上来，两者之间的差距会消失。论文显示情况恰恰相反：随着数据的增加，贪婪法实际上落后得更多，构建出庞大、混乱且难以阅读的决策树，而最优法则保持精简且精准。第二个迷思是，最优树存在“过拟合”问题——即它们过度记忆了训练数据，导致在处理新数据时表现不佳。研究发现，当进行正确调优时，最优树实际上比贪婪树更不容易发生过拟合。
但这里有一个代价。最优法在计算上非常沉重。这就像是在尝试解决一个巨大的拼图，你需要检查每一个可能的碎片组合；这需要耗费大量的时间和能量。论文证实，虽然这些决策树可以处理巨大的数据集（高达 10 万个实例），但如果特征（即拼图碎片）的数量过多，它们就会显得力不从心。因此，研究人员得出结论：当你需要一个小型、高精度且易于理解的模型时，尤其是当你的数据具有噪声或复杂性时，最优决策树是最佳选择。但如果你只需要一个快速的答案且不在乎决策树的大小，那么老派的贪婪法仍然是一个可靠且快速的老朋友。核心启示是：如果你想要两全其美，你必须仔细调优你的最优树，否则它将无法名副其实。
技术摘要：最优决策树还是贪心决策树？重新审视其目标、调优与性能
问题陈述
决策树（DT）因其可解释性和建模非线性关系的能力而被广泛使用。然而，在贪心自顶向下归纳（如 CART、C4.5）与**最优决策树（ODT）**学习之间存在着根本性的张力。贪心方法计算效率高，但优化的是局部不纯度指标（如基尼指数或熵），而非全局目标函数。相反，ODT 在规模限制下全局优化目标（通常是准确率），但历史上受限于 NP 困难的复杂度，使其应用仅限于小型数据集和浅层树。
以往的文献对 ODT 的价值提出了相互矛盾的证据。一些研究声称 ODT 比贪心方法提高 1-2% 的准确率，而另一些研究则认为贪心方法表现更好，或者认为 ODT 容易过拟合。这些矛盾通常源于实验设置的不一致，例如变化的深度限制、缺乏超参数调优以及在小规模合成数据上的比较。本文通过一项可扩展的大规模实证研究，旨在解决五个开放性问题以化解这些冲突。
方法论
作者进行了迄今为止规模最大的评估，利用了来自 OpenML 的 109 个真实世界二分类数据集以及各种合成数据集（包括具有地面真值树和线性分隔器的合成数据）。本研究专注于二元、轴对齐的决策树。
实验设置
- 算法：
- ODT： 研究采用了 STreeD，这是一种基于动态规划的算法，能够处理包含数十万个实例的数据集。
- 贪心： 标准 CART 实现（scikit-learn），并针对特定的目标比较进行了自定义实现。
- 数据预处理： 数值型和类别型特征被二值化（使用分位数阈值和独热编码/one-hot encoding），以确保公平比较和可扩展性，尽管实验证实结果在原始数值数据上也成立。
- 评估指标：
- 基于排名的分析： 分析各数据集的平均测试准确率排名，并使用 Nemenemi 临界距离检验进行统计显著性分析。
- 新指标： 规模-误差曲线下面积（SE-AUC），它衡量了在不同规模限制下，树的大小（可解释性）与误差之间的权衡，而非单一的点估计。
- 结构指标： 用于合成地面真值比较的真实发现率（TDR）和错误发现率（FDR）。
- 超参数调优： 研究对 ODT 和贪心方法进行了严格的调优，测试了各种策略（深度、节点数、复杂度代价、最小支持度、平滑处理），以确保公平比较。
核心贡献
- 解决文献冲突： 本文系统地指出，以往相互矛盾的结果主要是由于实验设计缺陷造成的，特别是未能对超参数进行调优，以及在贪心方法和最优方法之间未统一应用深度限制。
- 展示可扩展性： 通过利用现代动态规划技术，本研究证明了 ODT 可以用于训练具有高达 100,000+ 实例和 250 个二值特征的数据集，从而超越了以往 ODT 研究中的“玩具数据集”限制。
- 回答五个开放性问题： 本文为关于目标、调优、准确率、数据效率和过拟合的五个特定问题提供了明确答案。
关键结果
1. 目标的影响（开放问题 1）
- 发现： 对于 ODT，直接优化目标对象（如准确率）比优化传统的凹函数代理（如基尼不纯度或熵）能获得显著更好的样本外性能。
- 对比： 对于贪心方法，严格凹函数目标（基尼指数、熵）仍然更优，因为自顶向下的归纳启发式算法需要它们才能正常工作。
- 启示： ODT 提供了一个独特的优势：无需代理分裂准则即可灵活地直接优化真实的靶向指标。
2. 超参数调优的影响（开放问题 2）
- 发现： 超参数调优对于 ODT 实现高准确率并防止过拟合至关重要。
- 调优方法： 虽然调优深度是最快的方法，但调优节点数、复杂度代价或平滑参数可以获得相似的准确率结果。选择哪种调优方法主要影响树的大小和运行时间，而非最终准确率。
- 启示： 未经调优的 ODT 通常表现不佳或容易过拟合；妥善的调优是其成功的先决条件。
3. 准确率 vs. 贪心方法（开放问题 3）
- 发现： 在相同的深度限制下，ODT 显著优于贪心 CART（在深度为 3-5 时平均提升 1.3%–1.7%）。
- 权衡： 如果不应用深度限制，不受约束的贪心 CART 可以达到或略微超过 ODT 的准确率，但代价是生成规模大出几个数量级的树（例如，100+ 个节点 vs. 8 个节点）。
- 结论： ODT 的主要价值不在于在不受约束情况下的原始准确率，而在于卓越的准确率-可解释性权衡。它们能在保持紧凑、可解释结构的同时实现高准确率。
4. 数据效率（开放问题 4）
- 发现： “随着数据增加，贪心方法与最优方法之间的差距会缩小”这一假设被驳回。
- 观察： 随着数据量的增加，两种方法之间的差异实际上增加了，而不是减少。不受约束的贪心树为了维持或略微提高准确率，其规模增长显著；而 ODT 则保持了紧凑性。即使在海量数据下，受深度约束的贪心树也往往无法恢复出最优结构，而 ODT 则能在规模限制内成功找到最优树。
- 启示： ODT 并不会在效率上“追赶”上贪心方法；相反，随着数据规模扩大，它们在结构紧凑性和在规模限制下恢复真实树结构的能力方面保持着明显的优势，而贪心方法要么无法找到最优结构，要么需要指数级增长的树才能匹配性能。
5. 过拟合（开放问题 5）
- 发现： 只要经过适当调优，“ODT 更容易过拟合”的说法被驳回。
- 观察： 在没有调优的情况下，ODT 可能会在小型数据集上过拟合。然而，通过适当的超参数调优，ODT 比贪心对应方法对噪声（包括特征噪声和类别噪声）更不敏感。
- 启示： 感知到的过拟合风险是由于不当的训练实践，而非最优方法本身固有的缺陷。
意义与主张
本文认为，最优决策树的“价值”一直被其可扩展性限制和不一致的实验实践所掩盖。作者主张：
- ODT 在处理大规模现实世界数据集时是可行的，前提是使用像 STreeD 这样的现代动态规划求解器。
- 直接优化目标对象是 ODT 优于贪心方法的一个关键优势，因为贪心方法受限于需要凹函数代理指标。
- 妥善调优是不可逾越的底线；当调优正确时，ODT 比贪型树更不容易过拟合，且对噪声更具鲁棒性。
- 可解释性是核心差异点： ODT 在高准确率和极小模型规模之间提供了最佳平衡，使其成为需要人类理解力的高风险领域的理想选择。
作者总结道，对于需要紧凑、可解释且准确的模型的应用场景，特别是面对噪声数据或需要直接优化非标准目标时，ODT 优于贪心方法。他们提供了一套训练和比较这些方法的最佳实践，以指导未来的研究与应用。
每周获取最佳 machine learning 论文。
受到斯坦福、剑桥和法国科学院研究人员的信赖。
请查收邮箱确认订阅。
出了点问题，再试一次？
无垃圾邮件，随时退订。