改进决策树学习算法可大幅推进编码难题求解
Fast decision tree learning solves hard coding-theoretic problems
- 将决策树学习与近似码字问题关联，揭示深层联系
- 任何算法改进都能带来编码问题近似比的指数级提升
- 适用于理论计算机与机器学习交叉研究者
我们揭示了正确 PAC 学习决策树问题与参数化最近码字问题（k-NCP）之间的联系。尽管两个领域均投入大量研究，但进展停滞：决策树学习最快算法仍为准多项式时间（Ehrenfeucht and Haussler, 1989），而 k-NCP 最佳近似比仅为 $O(n/"log n)$（Berman and Karpinsky, 2002；Alon, Panigrahy, and Yekhanin, 2009）。此前两领域研究互不相通。本文证明：对 Ehrenfeucht and Haussler 算法的任意改进，都将导致 k-NCP 的 $O(\log n)$-近似算法，实现当前状态的指数级突破。这既为 k-NCP 提供新算法设计路径，也暗示该算法可能已达最优。此外，结合已有 k-NCP 不可近似性结果，可直接排除决策树正确学习的多项式时间算法可能性。特别地，本结论在弱学习设定下依然成立，而以往结果仅限强学习情形。
原文摘要 · Abstract (English)
We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem ($k$-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is $O(n/\log n)$ (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections. We show that $\textit{any}$ improvement of Ehrenfeucht and Haussler's algorithm will yield $O(\log n)$-approximation algorithms for $k$-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for $k$-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm. Furthermore, our reduction along with existing inapproximability results for $k$-NCP already rule out polynomial-time algorithms for properly learning decision trees. A notable aspect of our hardness results is that they hold even in the setting of $\textit{weak}$ learning whereas prior ones were limited to the setting of strong learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。