我们考虑了在查询的条件下正确地进行 PAC 学习决策树的任务，通过使用新的简化证明以及决策树的新异或引理，我们证明了即使允许在最优大小的任意常数因子内，该任务仍然是 NP 难的。

Jul, 2024

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

Nov, 2013

本文提出了一种新的分布学习模型，即在分布数据的随机样例附近进行局部查询来学习，并证明在该模型下，一些多项式和决策树相关的问题可以通过局部查询在多项式时间内进行学习。

Nov, 2012

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

Apr, 2023

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

Jan, 2013

本文研究从数据中学习离散变量贝叶斯网络的算法的复杂度结果，结果表明即使具有独立性、推理或信息神谕，识别高得分的结构也很困难，负面结果也适用于每个节点最多有 K 个父母的离散变量贝叶斯网络，其中 k > 3。

Oct, 2012

对于一个具有未知权重的图，如果我们知道一些节点子集关联的最小 Steiner 树，那么我们能否找到一对节点的最短路径？本文研究了这样一个原型问题，称为具有任务转换的查询 - 决策回归，重点关注最短路径问题和最小 Steiner 树问题。我们提供了关于构建评分模型的可实现假设空间设计的理论洞察，并提出了两个有原则的学习框架。我们的实验研究显示，这样的问题可以在统计显著性的程度上得到较好的解决。

Feb, 2024

本文研究了专家与问题实例之间的知识差异，提出了一种新算法 —— 专业树，解决了现有方法在选择适当模型时存在的问题，从而提高了性能。

May, 2023

本文研究了树模型中对抗样本和模型稳健性的问题，并提出了一种优化决策树构建过程的算法，通过在最坏情况下的输入特征扰动下优化性能，可以显著提高树模型对抗样本的稳健性。

Feb, 2019

本文研究了关于合取查询 (conjunctive queries) 的一些决策问题，发现针对无环或几乎无环查询的问题虽然一般来说是 NP 完全，但限制到这些查询中节点的树宽度和循环度是有界的，变得易于处理。针对查询的宽度这一最普遍的概念，我们证明没有多项式时间的算法可以高效地判断查询的宽度是否小于等于 k，而引入的超树分解概念和超树宽度则可以周旋这一难点，使得相应的问题变得可解。

Dec, 1998