证明了使用查询从头系统地学习决策树是 NP 难的，解决了学习理论中悬而未决的一个问题。在证明中，通过引入硬度凝聚的概念，简化并加强了决策树极小化的最优下界，并研究了决策树复杂度的硬度凝聚。结果展示了分布假设在该问题上的戏剧性影响。

Jul, 2023

本文研究了决策树的 delta - 充分原因的最小尺寸计算问题的逼近难度。

Apr, 2023

本文研究最优决策树，自适应 TSP 问题以及如何在度量空间中访问子集，并给出了多项式对数逼近算法。

Mar, 2010

本文考虑从数据中学习最大似然多叉树的任务，首先证明了最优分支（或 Chow-Liu 树）是最佳多叉树的很好近似，随后证明了该学习问题是 NP 难的，甚至在某些恒定因子的近似解中也无法很好地解决。

Jan, 2013

这篇论文介绍了第一种针对二进制变量进行最佳决策树生成的实用算法，该算法结合了分析界限和数据结构等现代技术，在可扩展性、速度和最优性方面具有明显优势。

Apr, 2019

这篇论文介绍了一种新的证明不适当学习难度的技术，基于难以处理的问题的规约，通过与密码假设相结合，发现了学习 $DNF$，半平面和超平面的交集等问题的困难性。

Nov, 2013

给出了一种算法，该算法在任意插入和删除已标记示例的序列上维护了一棵近似的决策树，并具有最坏情况下的运行时间保证。

Feb, 2023

通过简单特征的决策树是否能够逼近深度神经网络的问题，以及该问题的变体，正是对可由人类解释的机器学习模型不断增长的需求。本文通过引入可解释逼近的概念来研究这些问题，这一概念捕捉了通过一些基类概念的小聚合来逼近目标概念 c 的想法。我们的主要贡献是：对于给定的 H 和 c，对于任何给定的 pair，只有下列三种情况之一成立：(i) c 无法以任意精度通过 H 来逼近；(ii) c 可以以任意精度通过 H 来逼近，但不存在一种普遍的速率来限制逼近的复杂度与精度之间的关系；或者 (iii) 存在一个只依赖于 H 和 c 的常数 kappa，对于任何数据分布和任何期望的精度水平，c 可以通过 H 来逼近，并且复杂度不超过 kappa。这种分类法与监督分类的情况形成鲜明对比，后者提供了复杂的分布自由和普遍可学习的场景。我们表明，在可解释逼近的情况下，即使对逼近的复杂度有一个略微非平凡的先验保证，也可以得到具有常数（与分布和精度无关）复杂度的逼近。我们将我们的分类法扩展到具有无界 VC 维度的类 H，并给出了基于 H 生成的代数的可解释性的特征。

Jun, 2024

本研究提出一种新的框架，超越了传统统一收敛方法的限制，将排列不变预测器的交叉检验误差转化为高概率风险界，并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中，我们证明了该框架的优越性能。

Apr, 2023

研究表明，对于部分可观察的马尔可夫决策过程的多种变化形式，寻找控制策略的多项式时间算法难以或没有确保在最优解的常数因子或常数项内找到策略。除非某些复杂度类崩溃，否则任何控制策略设计师都必须在性能保证和有效计算之间做出选择。

Jun, 2011