Superconstant Inapproximability of Decision Tree Learning

我们考虑使用查询来正确地PAC学习决策树的任务。Koch、Strassle和Tan的最近研究表明，当要求假设树T是最优小的时候，这个任务的最严格版本是NP难的。他们的工作没有回答一个问题：如果要求T仅在最优解的因子内，比如说在2的范围内，这个任务是否仍然难以解决。我们肯定地回答这个问题并且表明即使T被允许在最优解的任意常数因子内，这个任务仍然是NP难的。更一般地说，我们的结果允许在难度假设和近似因子之间进行平滑的权衡。由于Koch等人的技术似乎不适用于这样的加强，因此我们首先用一种新的、更简单的证明方法来恢复他们的结果，同时结合一种新的决策树XOR引理。虽然有大量关于决策树XOR引理的工作，但我们的设置需要极其精确的参数，而这些参数不知道是否可以通过现有的XOR引理来实现。我们的工作还对相关的决策树最小化问题产生了新的影响。

论文研究决策树的PAC学习问题，探讨在限制条件下决策树的最优性对问题的影响

论文证明了即使在限制条件下，决策树的最优性对问题的影响仍然是NP-hard，提出了新的XOR引理

论文提供了新的简单证明方法，并且提出了新的XOR引理，为决策树最小化问题带来了新的启示

相关研究包括Koch, Strassle, and Tan的前一篇工作，以及决策树最小化问题的研究