本文研究了一个基于样本压缩界限的多类学习算法的贝叶斯一致性,并证明了在度量空间有限两倍维度的情况下,该算法是强贝叶斯一致的,甚至在某些无限维情况下也是连贯的,这是一项有趣的发现,当前存在几个值得研究的问题。
May, 2017
研究在线非参数分类中的一个实例,并考虑经典的 1 最近邻算法,证明它在可实现设置中针对支配或平滑对手实现次线性遗憾 - 即消失的错误率。
Jul, 2023
研究了度量空间中近似最近邻的问题,其中查询点被限制在低重复维度的子空间上,而数据则是高维的。我们展示了尽管数据是高维的,这个问题仍能得到有效的解决。
Jul, 2010
本文提出了一种新的最近邻方法,它能够适应不同空间区域的不同距离尺度,并分析其在度量空间的行为,从而得出分布相关的有限样本收敛速率,并实现了广泛数据空间的最近邻的普遍一致性。
Jun, 2014
本条研究提出了史上首个可查询到数据集中最近邻居的亚线性内存草图,并利用局部敏感哈希(LSH)估计器、在线核密度估计和压缩感知相结合来实现稳定查询的子线性内存性能,以取得内存 - 精度权衡的理论效果。
Feb, 2019
本文研究了半度量空间中的分类问题,定义并探索了密度维数在统计学和算法可行性中的中心作用,并提出了接近最优的样本压缩算法,得到了具有独立意义的广义样本压缩方案的泛化保证。
Feb, 2015
通过简单修改最近邻分类器,我们展示了一个强 Bayes 一致的学习器,优于 k-NN 分类器,并在限制样本大小和算法时间方面具有较大的优势,获得了令人鼓舞的实验结果。
Jul, 2014
本文介绍一种基于非半正定线性相似性的学习算法,用于分类,该算法能够通过最优化距离和相似度函数来在非线性特征空间中学习,该方法得到应用后,在各种数据集上比起现有方法具有更好的效果,而且速度快、防止过拟合和产生非常稀疏的分类器。
Jun, 2012
本文研究了一种用于近似最近邻搜索的紧凑编码方法,介绍了一种复合量化框架,其中包括使用不同字典中选定的若干元素的组合来准确近似 D 维向量,以此表示数据向量,实现准确搜索,从而实现距离计算成本从 O(D)降至 O(M)的近正交复合量化方法。
Dec, 2017
本文介绍了几种量子算法,用于执行最近邻学习,核心是计算距离度量,如内积和欧氏距离。证明量子算法比对应的经典算法具有多项式降低的查询复杂度。在某些情况下,证明具有指数甚至超指数降低。研究了这些算法在几个二元分类任务上的性能,并发现分类准确性与经典方法具有竞争力。
Jan, 2014