论文标题
部分可观测时空混沌系统的无模型预测
Efficient Quantum Agnostic Improper Learning of Decision Trees
论文作者
论文摘要
不可知论设置是PAC模型最难的概括，因为它类似于用对抗性噪声学习。在本文中，我们给出了一个poly $（n，t，{\ frac {1} {\ varepsilon}}）$量子算法，用于学习尺寸$ t $ t $决策树，而在不合时宜的环境中，没有成员资格查询的情况下具有均匀的边际边缘。我们的算法是在多项式时间内学习决策树的第一种算法（经典或量子），而无需成员查询。我们通过设计具有强烈偏见的函数座的经典Goldreich-Levin算法的量子版本来展示如何构建量子不可知论弱学习者。我们展示了如何量化Kalai和Kanade（NIPS 2009）的不可知论增强算法，以获得第一个有效的量子不可知算法。我们的量子增强算法在所有自适应量子增强算法上的偏差偏差的依赖性具有多项式改善，同时在VC维度中保留了VC维度的标准速度，而不是经典的增强算法。然后，我们使用量子增强算法来增强上一步中获得的弱量子学习者，以获得决策树的量子不可知论。使用上述框架，我们还为可实现的设置和随机分类噪声模型提供了量子决策树学习算法，而无需成员查询。
The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a poly$(n,t,{\frac{1}{\varepsilon}})$ quantum algorithm for learning size $t$ decision trees with uniform marginal over instances, in the agnostic setting, without membership queries. Our algorithm is the first algorithm (classical or quantum) for learning decision trees in polynomial time without membership queries. We show how to construct a quantum agnostic weak learner by designing a quantum version of the classical Goldreich-Levin algorithm that works with strongly biased function oracles. We show how to quantize the agnostic boosting algorithm by Kalai and Kanade (NIPS 2009) to obtain the first efficient quantum agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial improvement in the dependence of the bias of the weak learner over all adaptive quantum boosting algorithms while retaining the standard speedup in the VC dimension over classical boosting algorithms. We then use our quantum boosting algorithm to boost the weak quantum learner we obtained in the previous step to obtain a quantum agnostic learner for decision trees. Using the above framework, we also give quantum decision tree learning algorithms for both the realizable setting and random classification noise model, again without membership queries.
