量子提升
在这篇论文中,我们研究了用于学习的弱到强增强算法的并行成本,结果表明即使是对增强的轻微并行化也需要训练复杂度指数级增长,我们证明了这个上限并且给出了一些补充的结果和权衡,首次提供了并行性和增强所需总工作之间的权衡。
Feb, 2024
本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果,其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题,并提高了期望严格学习的新下界,以达到经典 PAC 学习的已知上界。
Nov, 2004
本文提出一种量子支持向量机分类器模型,实现有监督分类并取得了明显的量子加速,要求仅具备经典数据访问能力。在构造的数据集中,基于普遍认为的离散对数问题的困难性假设,该量子分类器实现的分类效果均优于无法逆多项式地超越瞎猜的经典学习器。这个模型可以通过一个容错的量子计算机来估算内积核函数,并且将数据映射为一个量子特征空间。此外,该分类器对由有限采样误差产生的内积核函数的加性误差具有一定的鲁棒性。
Oct, 2020
我们描述了一种用于训练支持向量机的绝热量子方法,该方法的量子计算时间复杂度比经典方法好一个数量级,我们在五个基准数据集上比较了量子方法和经典方法的测试准确度,在可扩展性研究中,我们发现量子方法在具有许多特征的数据集上比经典方法快 3.5-4.5 倍。
Jan, 2024
本文演示了量子计算如何提供感知器模型计算和统计复杂度的非平凡改进, 对感知器学习发展了两个量子算法,用于确定一个分离的超平面,并通过应用量子振幅扩大到感知器模型的版本空间诠释来实现准确度进一步的改进。
Feb, 2016
通过提出一种随机增强算法,我们构建了一个通用框架,将样本压缩方法扩展到支持基于子采样的随机学习算法,并输出具有单对数依赖性的投票分类器的泛化误差,相比于已知可实现的一般的弱到强学习器,我们的算法在训练样本数量方面具有更好的表现。
Feb, 2024
本文报道了第一个用可编程超导量子位的量子对抗学习实验,结果表明量子学习系统在对抗场景下存在一定的易受攻击性,并证明了对抗训练过程可以显著增强其抵御干扰性攻击的鲁棒性。
Apr, 2022
我们提出了一种新的在线增强算法,用于调整分类器权重,该算法与 Freund 和 Schapire 的 AdaBoost 算法更接近,同时还贡献了一种得出在线算法的新方法,其将以前的在线增强工作联系在一起。
Oct, 2008
我们设计了基于量子算法的子线性算法,用于分类问题和矩阵零和游戏问题的求解,其复杂度都是量级上界的平方根,相较现有技术有瓶颈的常数。我们的算法生成与传统算法完全相同的结果,推荐用于端到端应用,同时探讨了实现方式以及机器可达到的限制。
Apr, 2019
研究在线提升的两种算法:boost-by-majority 和自适应在线提升算法,证明其在可接受精度下基本上是最优的。两种算法都能处理样本的重要性权重,并且使用了在线损失最小化技术。
Feb, 2015