- 正确与不正确的量子 PAC 学习
用量子 Coupon Collector 问题,作者研究了 PAC 学习模型中的正确学习和错误学习,发现其样本复杂性。进而提出了量子 Coupon Collector 问题的解算法,并设计了量子 Padded Coupon Collecto - AAAI学习离散动力系统的拓扑结构和行为
在 PAC 模型下,本文研究了学习系统行为和底层拓扑结构的问题,并表明在一般情况下,这一学习问题是计算上难以处理的;然而,在底层图属于某些特定类别时,我们提出了高效的学习方法;另外,对于拓扑结构部分已知的未知系统,我们开发了一个高效的 PA - 关于非高效 PAC 学习无环连通查询的研究
本文研究在 PAC 模型下共识查询的学习问题,证明了共识查询类不具有多项式大小匹配的性质,给出了许多限制类共识查询的负 PAC 可学性结果,最后提出了利用成员查询实现共识查询的高效 PAC 学习方法。
- 普适性学习理论
本文研究了一种更贴近于实际机器学习应用的学习模型,但仍然在学习可能性方面提供了完整的理论,并通过探索万能学习问题的学习曲线发现,每个概念类的学习曲线都以指数、线性或任意缓慢的速率衰减,并提出了最优学习算法来实现每种情况下最佳的可能速率。
- 在结构化分布下学习带有 Massart 噪声的半空间
在特定分布的 PAC 模型下,我们针对学习带有 Massart 噪声的半空间问题进行了研究。我们提出了第一种基于 SGD 的、针对广泛分布(包括对数凹分布)的问题求解的计算机高效算法,并解决了先前研究中的一个悬而未决的问题。
- 学习算法的最优量子样本复杂度
在本文中,我们研究了量子样本复杂性,使用了二种方法证明了量子和经典样本复杂性在 PAC 和 agnostic 模型上差不多,其中第一种方法可以得到与经典边界相同或仅相差一个对数的量子边界,而第二种方法可以不丧失对数因子的情况下完成分析。
- 安全博弈中对手行为的学习 ——PAC 模型视角
本研究使用 PAC 模型,直接学习对手响应功能,通过实验验证了新的对手建模方法,在提高对手模型准确性时,探讨了实际需要的数据量,提供了最佳防御策略的条件。
- 从平均情况复杂度到不当学习复杂度
这篇论文介绍了一种新的证明不适当学习难度的技术,基于难以处理的问题的规约,通过与密码假设相结合,发现了学习 $DNF$,半平面和超平面的交集等问题的困难性。
- 使用本地成员查询进行学习
本文提出了一种新的分布学习模型,即在分布数据的随机样例附近进行局部查询来学习,并证明在该模型下,一些多项式和决策树相关的问题可以通过局部查询在多项式时间内进行学习。